《机器学习实战》学习笔记 --chapter2 K-近邻算法

时间：2022-01-24 10:32:53

kNN算法概述

看完kNN算法，其本质就是 找到待预测点和其余已知点的距离，并且对其从小到大进行排序，并且取其前K个点，用这K个点来进行判别。
伪代码如下：

  1. 求得待预测点和已知样本点中的特征值的距离：
    具体是利用几何中的线性距离来进行判别，即欧几里得距离。
  2. 按距离递增进行排序
  3. 选取与当前预测距离最小的K个点
  4. 确定这K个点所在的类别的概率
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类

用python3来表示该算法如下：

from numpy import *
import operator

#为简化特征为一维
#其中inX为我们要预测的点，dataSet为训练点，labels为对应的标签，k为选取的前k个点
def classify0(inX, dataSet, labels, k): 
#得到总共的训练样本个数
    dataSetSize = dataSet.shape[0];     
#tile可用于返回dataSetSize,1维的值为inX的向量 
    diffMat = tile(inX, (dataSetSize,1)) - dataSet; 
#以下为计算距离
    sqDiffMat = diffMat ** 2;   
    sqDiffMat = sqDiffMat.sum(axis=1);
    distance = sqDiffMat**0.5;
#得到排序之后的下标
    sortedDistindex = distance.argsort();   
    classCount={};
#统计出现的标签的次数
for i in range(k):                      
        voteLabel = labels[sortedDistindex[i]];
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1;
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse=True);
#返回出现最多的标签
return sortedClassCount[0][0];

可以看出来kNN的思想还是比较简单的，下面利用一组简单的数据来验证刚写的算法

#定义特征集合和标签
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]);
labels = ['A','A','B','B'];
#定义测试的预测用例
test = array([0,0]);
#定义取前k个值来判别
k = 2;
classify0(test,group.labels.k);

运行后的效果如下：

'B'

注意之处

归一化数值
由于每一个维度的数值大小是不一样的，所以我们一定要注意不同的数值大小对于预测值和训练样本的特征值距离的影响，这里给出个例子：

#其中x为训练值的特征，t为预测值的特征
sqrt((x1 - t1)^2 + (x2 - t2)^2+(x3 - t3)^2+(x4 - t4)^2);

如果这个时候x1 - t1 比其他的特征都要大很多，那么它的影响就会急剧的侵占整个距离计算，也就是说这个特征的重要性由于其较大的数值，所以被过度的放大了。
举个例子：每个人跑步和里程数和考试分数（满分一百分）作为特征输入，那么跑步里程数的差值必然是要比考试分数的差值大很多的。
因此我们要消除这一方面带来的影响，具体的方法是：

#其中min为value所在的特征值的最小值，max为最大值
value = (value - min) / (max - min);
标签：

相关文章