机器学习笔记：K-近邻算法（KNN）
一、介绍
KNN算法称为邻近算法，或者说K邻近算法（kNN，k-NearestNeighbor），分类算法。
KNN核心思想：一个样本在特征空间中的k个最相邻的样本中的大多数属于的某一个类别，则认为该样本也属于这一类别，并具有这个类别上的样本特性。
KNN算法优点：
-
简单，易于理解，易于实现，无需估计参数，无需训练；
-
适合对稀有事件进行分类；
-
特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。
KNN算法缺点：
-
K邻近算法必须保存全部数据集，存储空间需求大。
-
必须对数据集中的每个数据计算距离值，计算量大，时间开销大。
-
无法给出任何数据的基础结构信息，无法知晓平均实例样本和典型实例样本 具有什么特征。
二、原理
2.1 欧式距离
欧式距离又称欧几里得度量（euclidean metric），是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
二维空间下，欧式距离计算公式，如图1-1所示：
图1-1 二维空间欧式距离
d表示坐标（x1，y1）到坐标（x2，y2）之间的直线距离。
三维空间下，欧式距离计算公式，如图1-2所示：
图1-2 三维空间欧式距离
n维空间下，欧式距离计算公式，如图1-3所示：
图1-3 n维空间欧式距离
2.2 KNN算法
KNN是通过测量不同特征值之间的距离进行分类。它的的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
例如：如下图2-1所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，因此绿色圆被赋予红色三角形那个类；如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
图2-1 KNN算法示例图
我们要使k-近邻算法将每组数据划分某个类中，首先需要准备好已知类别数据集，我们需要对未知类别属性的数据集中的每个点都依次执行以下操作：
-
计算已知类别数据集中的点到当前未知点之间的距离；
-
按照距离递增次序排序；
-
选取与当前点距离最小的k个点；
-
确定前k个点所在类别出现的概率；
-
返回前k个点出现频率最高的类别作为当前未知点的预测分类。
三、代码实现
参考《机器学习实战》第二章K-近邻算法样例-约会对象分类
首先导入已分类好的数据作为判断依据，代码如下：
#提取数据
def file2matrix(filename):
#导出文件中数据，初始化returnMat为Mx3,M为数据数量
with open(filename,'r')as r:
arrayOLines = r.readlines()
numberOLines = len(arrayOLines)
returnMat = np.zeros((numberOLines,3))
classLabelVector = []
index =0
#分别获取数据和数据标签
for line in arrayOLines:
line = line.strip()
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
已分类好数据集格式如图 3-1 所示：
图3-1 已分类好数据示例图
第一列是每年获得的飞行常客里程数的特征值，第二列是玩游戏所耗时间百分比，第三列是每周消费冰淇淋公升数。最后一列是分类好的标签，1~3表示喜欢程度，1表示不喜欢，2表示一点喜欢，3表示很喜欢。
首先实现KNN算法，代码如下所示：
#计算距离，排序，选取K个最近的点，以K个点中频率最高的为预测类别
def classify0(test_point,dataSet,dataSetlabels,k):
dataSetSize = dataSet.shape[0] #得到已知数据集点个数
#计算已知类别数据集中点和当前点之间的距离
diffMat = np.tile(test_point,(dataSetSize,1)) - dataSet
sqDiffMat = diffMat **2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
sortedDistIndicies = distances.argsort() #对距离按照递增顺序排序
classCount ={}
#确定k个点所在类别出现频率
for i in range(k):
voteIlabel = dataSetlabels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0)+1 #dict.get(key,def) 查找key值value 没有返回def
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #按照k个点中类别出现次数排序
return sortedClassCount[0][0]
classify0函数传入四个参数，test_point是需要预测的点坐标，dataSet是已分类好的数据点，dataSetlabels分类好的数据标签，k指以几个点来作为预测类别的依据。返回KNN算法预测类别。
但是由于我们通过欧式距离公式来计算样本点之间的距离发现，数字差值最大的属性对计算结果影响很大。比如(20000, 0, 0.1)和(32000, 67, 0.1)这两组数据，可以发现第一列对结果影响很大，但我们认为这三种特征对结果是同等重要的。所以我们要对样本数据进行“数值归一化”处理。
数值归一化做法就是将任意取值范围的特征值转化为0到1区间内的值，公式：newValue = (oldVlue - min) / (max - min)
代码如下所示：
#归一化特征值
def autoNorm(dataSet):
minVals = dataSet.min(0)#每列最小值
maxVals = dataSet.max(0)#每列最大值
ranges = maxVals-minVals #得到取值范围
normDataSet = np.zeros(np.shape(dataSet)) #初始化为dataSet大小全为0的矩阵
m = dataSet.shape[0] #得到数据行数
normDataSet = dataSet - np.tile(minVals,(m,1)) #tile将minvals复制成m行1列矩阵
normDataSet = normDataSet/np.tile(ranges,(m,1))
return normDataSet
归一化后我们得到的数据集如图3-2所示：
图3-2 数值归一化示例图
接下来我们讲测试分类效果，代码如下所示：
#约会网站测试代码
def datingClassTest():
hoRatio = 0.10 #用来测试数据占比
datingDataMat,datingLabels = file2matrix('C:/Users/hyt/Desktop/machinelearninginaction/Ch02/datingTestSet2.txt')
normMat = autoNorm(datingDataMat) #得到归一化数据
m = normMat.shape[0]
numTestVecs = int(m*hoRatio) #得到测试数据下标值
errorcount = 0.0 #测试分类错误结果
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,],datingLabels[numTestVecs:m],3) #得到分类标签
print('the classifier came back with: %d,the real answer is : %d '%(classifierResult,datingLabels[i]))
if (classifierResult != datingLabels[i]): #比较预测结果和正确值
errorcount += 1.0
print('the total error rate is : %f'%(errorcount/float(numTestVecs)))
hoRatio表示测试数据占源数据比重，这里选用数据集中的10%用来做测试数据。
normMat是特征值归一化后的数据
normMat[i,:]表示第i行的数据作为测试数据，normMat[numTestVecs:m,]表示用除去测试集后的所有数据作为用来预测分类的点。参考numTestVecs=int(m*hoRatio)。
运行结果如图3-3所示：
图3-3 约会分类预测结果
分类处理约会数据集错误率是5%，我们可以尝试改变datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值变化而变化。
四、总结
综上，了解了KNN算法原理以及使用实例：
- 首先，我们知道kNN算法就是计算预测点到所有已知点的直线距离，计算距离方法是欧式距离法。
- 接着，我们需要对数据预处理，为了避免较大数据差值的干扰，我们需要将数据进行归一化处理，newValue = (oldVlue - min) / (max - min)。
- 最后，我们只需要选择合适的k值，便很容易得到计算结果。
