机器学习四 KNN算法

---

前言

KNN解决的是分类问题。

• k-Nearest Neighbor算法,也叫K最近邻算法
• K近邻算法KNN就是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中
• 通俗地讲，就是“物以类聚，人以群分”。
• 分类策略，就是“少数从属于多数”。
  

---

提示：K一般取奇数
样本类别的分布足够好的话，那么K值越大，划分的类别就越正确。而KNN中的K表示的就是划分数据时，所取相似样本的个数。

一、距离常量

KNN可以采用Euclidean（欧几里得）、Manhattan（曼哈顿）、Mahalanobis（马氏距离）等距离用于计算。

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

二、KNN算法步骤

• 算距离：给定待分类样本，计算它与已分类样本中的每个样本的距离；
• 找邻居：圈定与待分类样本距离最近的K个已分类样本，作为待分类样本的近邻；
• 做分类：根据这K个近邻中的大部分样本所属的类别来决定待分类样本该属于哪个分类；

三、算法优点

• 算法本身简单有效，精度高,对异常值不敏感,易于实现，无需估计参数，分类器不需要使用训练集进行训练，训练时间复杂度为0。
• 特别适合于多分类问题(multi-modal,对象具有多个类别标签)
• 适合对稀有事件进行分类；

四、算法缺点

• 算法计算量较大
• 分类时需要先计算待分类样本和全体已知样本的距离，才能求得所需的K近邻点，计算量较大，尤其是样本数量较多时。
• 加入某些类别的样本容量很大，而其他类样本容量很小，即已知的样本数量不均衡，有可能当输入一个和小容量类相同的的新样本时，该样本的K个近邻中，大容量类的样本占多数，从而导致误分类。

五、代码示例

代码如下（示例）：

import numpy as np
import matplotlib.pyplot as plt
import matplotlib

#数据集
x_data = np.array(
                  [[3,104],
                   [2,100],
                   [101,10],
                   [1,81],
                   [99,5],
                   [98,2]
                  ]
                  )
#标签
y_data = np.array(['R','R','A','R','A','A'])

#测试数据
x_test = np.array([18,90])

#计算数据大小
num = x_data.shape[0]

#打印散点图
for i in range(num):
    if y_data[i] == 'R':
        scat1 = plt.scatter(x_data[i][0],x_data[i][1],c='r')
    else:
        scat2 = plt.scatter(x_data[i][0],x_data[i][1],c='b')

scat3 = plt.scatter(x_test[0],x_test[1],c='k')

plt.legend(handles=[scat1,scat2,scat3],labels=['Romatic','Action','X'],loc='best')
#plt.show()

#从测试点复制一个矩阵，存储和样本之间的距离
x_mat = np.tile(x_test,(num,1))

#计算距离
x_diff_mat = x_mat - x_data
sql_diff_mat = x_diff_mat**2
distance = sql_diff_mat.sum(axis=1)
distance = distance**0.5

print(distance)
#距离排序
sort_dist = distance.argsort()
print(sort_dist)

k = 5
FilmCount = {'R':0,'A':0}

#统计最近K个距离每个标签的个数
for i in  range(k):
    n_label =  y_data[sort_dist[i]]
    FilmCount[n_label] = FilmCount[n_label]+1
print(FilmCount)

sortedFilmCout = sorted(FilmCount.items(),key=lambda x:x[1],reverse=True)
print(sortedFilmCout)

knn_ret = sortedFilmCout[0][0]
print(knn_ret)