k近邻算法（KNN）
简介
KNN算法是数据挖掘分类技术中最简单的方法之一。它通过测量不同特征值之间的距离进行分类的。其基本思路为：如果一个样本在特征空间中的k个最近邻样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在决定类别上只依据最近的一个或者几个样本的类别来决定待分类样本所属的类别。
原理
给定一个样本数据集（称为训练集），样本集内每一个数据都已经存在标签。（例如：'兔子'这个数据的标签是'动物'）。现在，输入一个新的数据，含有诸多属性，将每一个属性与样本集中的数据对应的属性进行比较，通过算法找到样本集中与它最相似的k个数据， 再获得这k个样本数据出现最多的标签作为这个新数据的标签。
例如
这时，一个新的数据需要分类。
我们将待标记的数据和样本集里面的数据比对，发现它的每一个属性均和data1一致，也只有data1和它完全一致，不难给与标签为A。
在上面这个看似简单的过程中其实有很多值得思考的东西。
首先我是如何判断data1和它一致呢？
我是相同属性去比较的，然后发现每一个属性值完全相同。可是这是因为属性少，数据量少，而且一个“等与不等”就能给出结论。但是事实上很多时候（几乎所有时候）完全一致的两个数据是几乎不存在的，那种情况下那么多的属性，我如何度量两个数据的接近程度，如何得到最接近的k个数据呢？
那么如何得到最接近的k个数据呢？
这个问题其实不难回答，只要求出待标记数据与已知数据的属性距离就ok了，至于距离怎么求？这个也不难，如果只有两个属性，可以建立二维坐标系，求出新数据的点与其他所有点的距离即可。如果属性更多，可以从二维上推广，得到高维两点之间的距离公式。
这个公式其实就是欧几里得度量公式。（也可以使用曼哈顿距离公式，当然这两个都是闵可夫斯基距离公式的特例,但是只有欧式距离保证收敛）
就这样，我们计算出了待标记数据和所有样本数据的距离，这是个数值，比较得到最接近的k个数据，统计这k个数据的标签频率，选取出现频率最高的或者最高的中的一个，为新数据打上标签。
k值的选择
统计学方法中参数选择一般是要在偏差（Bias）与方差（Variance）之间取得一个平衡（Tradeoff）。对KNN而言，k值的选择也要在偏差和方差之间取得平衡。若k取值太小，则分类结果可能因为噪声点的干扰而出现错误，此时方差较大；若k取值太大，假设达到样本数据总量，那么对所有的测试样本而言，结果都一样，分类的结果都是样本最多的类别，这样稳定是稳定了，但是预测结果与真实值相差太远，偏差过大。因此，k值既不能太大也不能太小，通常的做法是，利用交叉验证（Cross Validation）评估一系列不同的k值，选取结果最好的k值作为训练参数。
实战
使用KNN实现约会网站的配对效果
项目描述
假设存在这样一种情况，海伦使用在线约会网站寻找合适自己的约会对象，尽管网站时常推荐，但是她没有找到合适的人。经过总结，她发现交往过三类人。
不喜欢的（类别1）魅力一般的（类别2）极具魅力的）类别3）
尽管发现了这个规律，但是海伦依然无法将约会网站匹配的对象划分到恰当类别中，海伦希望分类软件可以更好地帮助她将匹配对象划分到正确的分类中。此外，海伦还收集到一些约会网站未曾记录的信息，她认为这些数据有助于匹配对象的分类。
根据已有数据集，不难发现每个样本数据有三个特征一个类别，但是发现飞行里程数都是上万的，而其他两项的值都不超过10，在计算距离时就会造成这个特征值权重极大，这是不合理的，因为三个特征影响程度应该相当，这里通过归一化处理数据集的特征值。
代码实现（注意区别）
自行编写KNN算法
# -*-coding:utf-8-*-from numpy import *import operatordef classify0(inX, dataSet, labels, k):'''利用距离公式计算出最接近的k个样本中出现最多的标签:param inX: 待分类的样本:param dataSet: 特征矩阵:param labels: 类别矩阵:param k: k值:return: 最接近的标签'''print(inX)dataSetSize = dataSet.shape[0]diffMat = tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat ** 2sqDisttances = sqDiffMat.sum(axis=1)distances = sqDisttances ** 0.5sortedDistIndicies = distances.argsort()classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1# 依照标签出现的频率排序sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)# 选取频率最大的标签return sortedClassCount[0][0]def file2matrix(filename):'''数据读取为矩阵:param filename: 文件名:return: 特征矩阵， 标签矩阵'''fr = open(filename)arrayOLines = fr.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines, 3))classLabelVector = []index = 0for line in arrayOLines:line = line.strip()listFromLine = line.split('\t')returnMat[index, :] = listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat, classLabelVectordef autoNorm(dataSet):'''归一化数据:param dataSet: 数据集:return: 归一化后的数据集'''minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsm = dataSet.shape[0]normDataSet = dataSet - tile(minVals, (m, 1))normDataSet = normDataSet / tile(ranges, (m, 1))print(normDataSet)return normDataSet, ranges, minValsdef classifyPerson():'''网站实测:return: 可能标签'''resultList = ['不喜欢', '一般喜欢', '特别喜欢']percentTats = float(input("玩游戏占的百分比"))ffMiles = float(input("每年坐飞机多少公里"))iceCream = float(input("每年吃多少公升的冰淇淋"))datingDataMat, datingLabels = file2matrix('data/datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)inArr = array([ffMiles, percentTats, iceCream])print((inArr - minVals) / ranges)classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)print("你将有可能对这个人是:", resultList[int(classifierResult) - 1])if __name__ == '__main__':classifyPerson()
使用sklearn的KNN模块
# -*-coding:UTF-8 -*-from sklearn.neighbors import KNeighborsClassifierfrom sklearn.preprocessing import MinMaxScalerfrom numpy import *def file2matrix(filename):'''数据读取为矩阵:param filename: 文件名:return: 特征矩阵， 标签矩阵'''fr = open(filename)arrayOLines = fr.readlines()numberOfLines = len(arrayOLines)returnMat = zeros((numberOfLines, 3))classLabelVector = []index = 0for line in arrayOLines:line = line.strip()listFromLine = line.split('\t')returnMat[index, :] = listFromLine[0:3]classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat, classLabelVectordef autoNorm(dataSet):'''归一化数据:param dataSet: 数据集:return: 归一化后的数据集'''minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsmin_max_scaler = MinMaxScaler()normDataSet = min_max_scaler.fit_transform(dataSet)return normDataSet, ranges, minValsdef classifyPerson(model):'''网站实测:return: 可能标签'''resultList = ['不喜欢', '一般喜欢', '特别喜欢']percentTats = float(input("玩游戏占的百分比"))ffMiles = float(input("每年坐飞机多少公里"))iceCream = float(input("每年吃多少公升的冰淇淋"))datingDataMat, datingLabels = file2matrix('data/datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)inArr = array([[ffMiles, percentTats, iceCream]])model.fit(normMat, datingLabels)print((inArr - minVals) / ranges)rst = model.predict((inArr - minVals) / ranges)print("你将有可能对这个人是:", resultList[int(rst) - 1])if __name__ == '__main__':model = KNeighborsClassifier(n_neighbors=3, weights='uniform', algorithm='auto', leaf_size=30,p=2, metric='minkowski', metric_params=None, n_jobs=1)classifyPerson(model)
补充说明
参考《Python3数据分析与机器学习实战》，具体的代码和数据集可以在我的GitHub找到，欢迎star或者fork。
如果觉得《机器学习-分类之K近邻算法(KNN)原理及实战》对你有帮助，请点赞、收藏，并留下你的观点哦！
