knn 算法简介与python代码片

算法简介与python代码片"/>

knn 算法简介与python代码片

学习了一些算法理论整理一下，便于记忆
如有帮助，点赞收藏关注
如需转载请注明出处

=1000.2115.3001.5343

KNN（K Near Neighbor）：

k个最近的邻居，即每个样本都可以用它最接近的k个邻居来代表。KNN算法属于监督学习方式的分类算法，计算某给点到每个点的距离作为相似度的反馈。

区分于聚类（如Kmeans等），KNN是监督学习分类，是一种基于实例的学习，属于懒惰学习。而Kmeans是无监督学习的聚类，聚类将无标签的数据分成不同的簇。

工作原理：

存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类对应的关系。输入没有标签的数据后，将新数据中的每个特征与样本集中数据对应的特征进行比较，提取出样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k近邻算法中k的出处，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类作为新数据的分类。

KNN算法的一般流程：

1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

knn 的三个决定性要素：

• k值的选择：
  当K值较小时，那么在测试时选择的领域范围就大，学习的近似误差减小(只有与输入较近的实例才会对预测结果起作用)，估计误差增加(对近邻的实例点非常敏感，收益受噪声影响)；当K值过大时，选择的领域范围就大，会减小模型的估计误差，但会增加学习的近似误差。

• 距离度量：
  常用的距离度量就是欧式距离，但其实任何距离度量都可以。不同度量下得到的最近邻可能不一样

• 分类决策原则：多数表决

#计算两个向量之间的欧氏距离
def calDist(X1 , X2):sum = 0for x1 , x2 in zip(X1 , X2):sum += (x1 - x2) ** 2return sum ** 0.5def knn(data , dataSet , labels , k):n = shape(dataSet)[0]for i in range(n):dist = calDist(data , dataSet[i])#记录两点之间的距离和已知点的类别labels[i].append(dist)#按照距离递增排序labels.sort(key=lambda x:x[1])count = {}#统计每个类的频率for i in range(k):key = labels[i][0]if count.has_key(key):count[key] += 1else : count[key] = 1#按频率递减排序sortCount = sorted(count.items(),key=lambda item:item[1],reverse=True)#返回频率最高的key --->labelreturn sortCount[0][0]

K近邻算法虽然简单，但其局限性也非常明显。算法并没有根据数据显著地构建一个模型，而是存储了所有训练集特征，当训练数据很大时，时间和空间复杂度将会非常高。因此为了进一步提高计算效率，采用kd树进行优化。以后有时间给大家介绍kd树

如有帮助，点赞收藏关注我！
如需转载请注明出处！

=1000.2115.3001.5343