机器学习-KNN算法

1. 算法原理（K-Nearest Neighbor）

• 本质是通过距离判断两个样本是否相似，如果距离够近就认为他们足够相似属于同一类别
• 找到离其最近的 k 个样本，并将这些样本称之 为「近邻」(nearest neighbor)。
• 对这 k 个近邻，查看它们的都属于何种类别（这些类别我们称作「标签」 (labels)）。
• 然后根据“少数服从多数，一点算一票”原则进行判断，数量最多的的标签类别就是新样本的标签类别。
• 其中涉及到的原理是“越相近越相似”，这也是KNN的基本假设。

2. 实现过程和距离的确定

1） 实现过程

• 假设 X_test 待标记的数据样本，X_train 为已标记的数据集。
  • 遍历已标记数据集中所有的样本，计算每个样本与待标记点的距离，并把距离保存在 Distance 数组中。
  • 对 Distance 数组进行排序，取距离最近的 k 个点，记为 X_knn.
  • 在 X_knn 中统计每个类别的个数，即 class0 在 X_knn 中有几个样本，class1 在 X_knn 中有几个样本等。
  • 待标记样本的类别，就是在 X_knn 中样本个数最多的那个类别。

2） 距离的确定

• 该算法的「距离」在二维坐标轴就表示两点之间的距离，计算距离的公式有很多。

• 我们常用欧拉公式，即“欧氏距离”。(x1、x2、x3为特征)
  $$
  \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 - y_3)^2+...+(x_n - y_n)^2} =\sqrt{ \sum_{i=1}{n}{(x_i-y_i)2}}
  $$

3. 算法优缺点

算法超参数是 k（人为设置的参数为超参数），k 可以理解为标记数据周围几个数作为参考对象，参数选择需要根据数据来决定。（通过学习曲线找最优的k）

• k 值越大，模型的偏差越大，对噪声数据越不敏感。
• k 值很大时，可能造成模型欠拟合。
• k 值越小，模型的方差就会越大。
• 但是 k 值太小，容易过拟合

4. 算法的变种

变种一：默认情况下，在计算距离时，权重都是相同的，但实际上我们可以针对不同的邻居指定不同的距离权重，比如距离越近权重越高。

• 这个可以通过指定算法的 weights 参数来实现。

变种二：使用一定半径内的点取代距离最近的 k 个点

• 在 scikit-learn 中，RadiusNeighborsClassifier 实现了这种算法的变种。
• 当数据采样不均匀时，该算法变种可以取得更好的性能。

5. Python代码实现KNN

# 红酒参数
rowdata = {'颜色深度':[14.13,13.2,13.16,14.27,13.24,12.07,12.43,11.79,12.37,12.04],
'酒精浓度': [5.64,4.28,5.68,4.80,4.22,2.76,3.94,3.1,2.12,2.6],
'品种': [0,0,0,0,0,1,1,1,1,1]}
# 0 代表 “黑皮诺”，1 代表 “赤霞珠”
wine_data = pd.DataFrame(rowdata)

   def KNN(x):  #x是输入的点  返回类别
       # 1.把10个训练数据提取到data中
       data = wine_data.iloc[:,:2].values #将前两列提取出来----data
   
       # 2. 新数据点与10个一维数组的欧式距离
       # 数据点第一个特征与10个点的欧式距离
       a = ((x-data) ** 2)[:,0] #第一列抽取出来
       # 数据点第二个特征与10个点的欧式距离
       b = ((x-data) ** 2)[:,1] #第二列抽取出来
       # 得到数据点与10个点的欧氏距离
       Distance = np.sqrt(a+b)
       np.sort(Distance)
       # 3.排序找出最近的K个点   K=3
       K3 = np.argsort(Distance)[:3] #得到开始表的索引值     6 1 4
   
       # 4.判断类别
       y = wine_data.品种
       # 根据频数统计判断属于哪一类
       return pd.Series([y[i] for i in K3]).value_counts().idxmax()

   KNN([[12.3,4.1]])
   # OUT：0

6. SCIKIT-LEARN算法库实现KNN（见WineSortKNN.ipynb）

• scikit-learn，简称 sklearn， 支持了包括分类、回归、降维和聚类四大机器学习算法，以及特征提取、数据预处理和模型评估三大模块。

• 主要设计原则：
  1） 一致性

  ​ 所有对象共享一个简单一致的界面(接口)。

  • 估算器：fit()方法。基于数据估算参数的任意对象，使用的参数是一个数据集(对应 X, 有监督算法
    还需要一个 y)，引导估算过程的任意其他参数称为超参数，必须被设置为实例变量。
  • 转换器：transform()方法。使用估算器转换数据集，转换过程依赖于学习参数。可以使用便捷方
    式: fit_transform()，相当于先 fit()再 transform()。(fit_transform 有时被优化过，速度更快)
  • 预测器：predict()方法。使用估算器预测新数据，返回包含预测结果的数据，还有score()方法:用
    于度量给定测试集的预测效果的好坏。(连续 y 使用 R 方,分类 y 使用准确率 accuracy)
  • 检查所有参数，所有估算器的超参数可以通过公共实例变量访问，所有估算器的学习参数都可以通过有下划线后缀的公共实例变量访问。

  3）防止类扩散

  • 对象类型固定，数据集被表示为 Numpy 数组或 Scipy 稀疏矩阵，超参是普通的 Python 字符或数字。
  • 现有的构件尽可能重用，可以轻松创建一个流水线 Pipeline。

  5）合理默认值

  • 大多数参数提供合理默认值，可以轻松搭建一个基本的工作系统

  6）SKlearn KNN 实现

  class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, *, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None)[source]
  

from sklearn.neighbors import KNeighborsClassifier

clf = KNeighborsClassifier(n_neighbors=3)
clf = clf.fit(wine_data.iloc[:,0:2].values,wine_data.iloc[:,-1].values)

#测试单个点
clf.predict([[12.3,4.1]])

# OUT: array([0]) 属于“黑皮诺”红酒