KNN算法简介

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

KNN算法简介 前言一、KNN算法原理二、KNN代码实现1.引入库2.定义KNN分类器3.生成数据集

---

前言

提示：本文主要介绍KNN算法和实现，部分介绍引用李航老师的《统计学习方法》，编程语言为python，转载请注明来源。

---

应用了python的矩阵计算包Numpy，简化大量数据的处理过程。

一、KNN算法原理

KNN算法全称K近邻算法。KNN算法不需要训练模型，或者说训练集就是KNN的模型。

基本思想是在模型现有数据集中寻找和输入的样本距离最近的K个样本点，K个样本点中类别多者判决为输入样本的类别，特殊的当K = 1时，称为最近邻算法。

KNN算法的参数K值选择对KNN的计算结果会产生很大影响，机器学习问题中存在“过拟合”和“欠拟合”的问题。就如下图所示： K小值——过拟合（判决范围小，对噪声敏感） K大值——欠拟合（判决范围大，更容易引入噪声） 在K=3时，根据KNN算法，会将输入样本点判决为 红； 而K=5时，输入样本被判决为 蓝，增大K值为整个判决引入了不确定性。

采用小K值时，对于临近点会更加敏感，若里输入样本最近的点恰好是噪声，就会使模型判决错误。 在实际应用中K值一般选取较小的值。

样本距离的衡量标准有很多，最常用的有以下几种：

曼哈顿距离欧氏距离明氏距离（Minkowski distance）。。。

明氏距离的表达式 学过矩阵理论就很好理解 就是在高维空间中向量的p范数定义，当p=1时和曼哈顿距离等价；p=2时和欧式距离等价。

二、KNN代码实现

1.引入库

import numpy as np from collections import Counter from math import sqrt from sklearn.datasets import make_classification

2.定义KNN分类器

class KNN(object): def __init__(self,k): self.k = k self.data = None self.label = None def train(self,data,label): self.data = data self.label = label def predict(self,x): dis = [sqrt(np.sum((xtrain-x)**2)) for xtrain in self.data] nearest = np.argsort(dis) topk_y = [self.label[i] for i in nearest[:self.k]] votes = Counter(topk_y) return votes.most_common(1)[0][0]

3.生成数据集

使用sklearn.datasets中的make_classification生成数据集，包括数据和标签 注意！！！ 该函数生成数据集是随机的，每次运行得到的都不一样

def createdata(n): x,y = make_classification(n_samples=n, n_features=2,n_redundant=0,n_informative=1,n_clusters_per_class=1) ''' #n_samples:生成样本的数量 #n_features=2:生成样本的特征数，特征数=n_informative（） + n_redundant + n_repeated #n_informative：多信息特征的个数 #n_redundant：冗余信息，informative特征的随机线性组合 #n_clusters_per_class ：某一个类别是由几个cluster构成的 make_calssification默认生成二分类的样本，上面的代码中，x代表生成的样本空间（特征空间） y代表了生成的样本类别，使用1和0分别表示正例和反例 y=[0 0 0 1 0 1 1 1... 1 0 0 1 1 0] ''' return x,y

生成120个样本，前100个样本用作训练集，其余的用作测试集 建立KNN分类器，K值取2，进行测试

data,label = createdata(120) knncla = KNN(2) knncla.train(data[:100],label[:100]) ty = [knncla.predict(x) for x in data[100:]] y = [i for i in label[100:]] print(y) print(ty) # 标注成功情况下y与ty是一样的

---

后面会更新与KD树相关的理解和实现