本文参考：常用数据挖掘算法总结及 Python 实现，机器学习实战，以及网友http://www.cnblogs.com/jtianwen2014/p/4249003.html

算法思路：

　　存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。

算法优缺点

1) 优点

 简单，易于理解，易于实现，无需估计参数，无需训练；

 适合样本容量比较大的分类问题

 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能

分类，kNN 比 SVM 的表现要好

2) 缺点

 懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢；

 可解释性较差，无法给出决策树那样的规则

 对于样本量较小的分类问题，会产生误差

适用情况：

由于 kNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此

1、适合样本容量比较大的分类问题

2、对于类域的交叉或重叠较多的待分样本集来说，kNN 方法较其他方法更为适合

实例：

一、KNN 算法 Python 实现实例之电影分类

电影名称                                打斗次数 接吻次数 电影类型

California Man                           3              104       Romance

He’s Not Really into Dudes         2              100      Romance

Beautiful Woman                        1                81     Romance

Kevin Longblade                      101              10        Action

Robo Slayer 3000                     99                 5       Action

Amped II                                    98                 2      Action

未知                                           18                90     Unknown

任务描述：通过打斗次数和接吻次数来界定电影类型

调用 Python 的 sklearn 模块求解

1. import numpy as np

2. from sklearn import neighbors

3. knn = neighbors.KNeighborsClassifier() #取得 knn 分类器

4. data = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]) # <span style="font-family:Arial, Helvetica, sans-serif;">data 对应着

打斗次数和接吻次数</span>

5. labels = np.array([1,1,1,2,2,2]) #<span style="font-family:Arial, Helvetica, sans-serif;">labels 则是对应 Romance 和 Action</span>

6. knn.fit(data,labels) #导入数据进行训练'''

7. #Out：KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',

8. metric_params=None, n_jobs=1, n_neighbors=5, p=2,

9. weights='uniform')

10. knn.predict([18,90])

解读：

首先，用 labels 数组中的 1 和 2 代表 Romance 和 Aciton，因为 sklearn 不接受字符数组作为标志，只

能用 1,2 这样的 int 型数据来表示，后面处理可以将 1 和 2 映射到 Romance 和 Action 上来。fit 则是

用 data 和 labels 进行训练，data 对应的是打斗次数和接吻次数构成的向量，称之为特征向量。labels

则是这个数据所代表的电影所属的类型。调用 predict 进行预测，将未知电影的特征向量代入，则能

分析出该未知电影所属的类型。此处计算结果为 1,也就是该未知电影属于 Romance，和直觉相符。

二、

例子中的案例摘《机器学习实战》一书中的，代码例子是用python编写的（需要matplotlib和numpy库）。

海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：1.不喜欢的人（以下简称1）；2.魅力一般的人（以下简称2） ；3.极具魅力的人（以下简称3） 

尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好的帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。

我们先提取一下这个案例的目标：根据一些数据信息，对指定人选进行分类（1或2或3）。为了使用kNN算法达到这个目标，我们需要哪些信息？前面提到过，就是需要样本数据，仔细阅读我们发现，这些样本数据就是“海伦还收集了一些约会网站未曾记录的数据信息”。好的，下面我们就开始吧！

----1.收集数据

海伦收集的数据是记录一个人的三个特征：每年获得的飞行常客里程数；玩视频游戏所消耗的时间百分比；每周消费的冰淇淋公升数。数据是txt格式文件，如下图，前三列依次是三个特征，第四列是分类（1：不喜欢的人，2：魅力一般的人，3：极具魅力的人），每一行代表一个人。

2.准备数据

何为准备数据？之前收集到了数据，放到了txt格式的文档中了，看起来也比较规整，但是计算机并不认识啊。计算机需要从txt文档中读取数据，并把数据进行格式化，也就是说存到矩阵中，用矩阵来承装这些数据，这样才能使用计算机处理。

需要两个矩阵：一个承装三个特征数据，一个承装对应的分类。于是，我们定义一个函数，函数的输入时数据文档（txt格式），输出为两个矩阵。

代码如下：

1 def file2matrix(filename): 2     fr = open(filename) 3     numberOfLines = len(fr.readlines()) 4     returnMat = zeros((numberOfLines, 3)) 5     classLabelVector = [] 6     fr = open(filename) 7     index = 0 8     for line in fr.readlines(): 9         line = line.strip()10         listFromLine = line.split('\t')11         returnMat[index, :] = listFromLine[0:3]12         classLabelVector.append(int(listFromLine[-1]))13         index += 114     return returnMat, classLabelVector

简要解读代码：首先打开文件，读取文件的行数，然后初始化之后要返回的两个矩阵（returnMat、classLabelsVector），然后进入循环，将每行的数据各就各位分配给returnMat和classLabelsVector。

----3.设计算法分析数据

对训练集做以下操作：

1. 计算训练集中各点与当前点之间的距离(本文采用最经典的欧式距离)

2. 按照距离递增次序对各点排序

3. 选取与当前点距离最小的k个点

4. 确定前k个点所在类别的出现频率

5. 返回前k个点出现频率最高的类别，即为分类结果。

k-近邻算法的目的就是找到新数据的前k个邻居，然后根据邻居的分类来确定该数据的分类。

首先要解决的问题，就是什么是邻居？当然就是“距离”近的了，不同人的距离怎么确定？这个有点抽象，不过我们有每个人的3个特征数据。每个人可以使用这三个特征数据来代替这个人——三维点。比如样本的第一个人就可以用（40920， 8.326976， 0.953952）来代替，并且他的分类是3。那么此时的距离就是点的距离：

A点(x1, x2, x3)，B点(y1, y2, y3)，这两个点的距离就是：(x1-y1)^2+(x2-y2)^2+(x3-y3)^2的平方根。求出新数据与样本中每个点的距离，然后进行从小到大排序，前k位的就是k-近邻，然后看看这k位近邻中占得最多的分类是什么，也就获得了最终的答案。

这个处理过程也是放到一个函数里的，代码如下：

 

1 def classify0(inX, dataSet, labels, k): 2     dataSetSize = dataSet.shape[0] 3     diffMat = tile(inX, (dataSetSize,1)) - dataSet 4     sqDiffMat = diffMat**2 5     sqDistances = sqDiffMat.sum(axis=1) 6     distances = sqDistances**0.5 7     sortedDistIndicies = distances.argsort() 8     classCount={} 9     for i in range(k):10         voteIlabel = labels[sortedDistIndicies[i]]11         classCount[voteIlabel] = classCount.get(voteIlabel,0) + 112     sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)13     return sortedClassCount[0][0]

 

简要解读代码：该函数的4个参数分别为新数据的三个特征inX、样本数据特征集（上一个函数的返回值）、样本数据分类（上一个函数的返回值）、k表示你想去前k个临近值，函数返回位新数据的分类。第二行dataSetSize获取特征集矩阵的行数，第三行为新数据与样本各个数据的差值，第四行取差值去平方，之后就是再取和，然后平方根。代码中使用的排序函数都是python自带的。

好了，现在我们可以分析数据了，不过，有一点不知道大家有没有注意，我们回到那个数据集，第一列代表的特征数值远远大于其他两项特征，这样在求距离的公式中就会占很大的比重，致使两点的距离很大程度上取决于这个特征，这当然是不公平的，我们需要的三个特征都均平地决定距离，所以我们要对数据进行处理，希望处理之后既不影响相对大小又可以不失公平：

 

这种方法叫做，归一化数值，通过这种方法可以把每一列的取值范围划到0~1或-1~1:，处理的公式为：

newValue = (oldValue - min)/(max - min)

归一化数值的函数代码为：

1 def autoNorm(dataSet):2     minVals = dataSet.min(0)3     maxVals = dataSet.max(0)4     ranges = maxVals - minVals5     normDataSet = zeros(shape(dataSet))6     m = dataSet.shape[0]7     normDataSet = dataSet - tile(minVals, (m, 1))8     normDataSet = normDataSet / tile(ranges, (m, 1))9     return normDataSet, ranges, minVals

---4.测试算法

经过了格式化数据、归一化数值，同时我们也已经完成kNN核心算法的函数，现在可以测试了，测试代码为：

1 def datingClassTest(): 2     hoRatio = 0.10 3     datingDataMat, datingLabels = file2matrix('datingTestSet.txt') 4     normMat, ranges, minVals = autoNorm(datingDataMat) 5     m = normMat.shape[0] 6     numTestVecs = int(m * hoRatio) 7     errorCount = 0.0 8     for i in range(numTestVecs): 9         classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)10         print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])11         if (classifierResult != datingLabels[i]): errorCount += 1.012     print "the total error rate is: %f" % (errorCount / float(numTestVecs))

通过测试代码我们可以在回忆一下这个例子的整体过程：

• 读取txt文件，提取里面的数据到datingDataMat、datingLabels；
• 归一化数据，得到归一化的数据矩阵；
• 测试数据不止一个，这里需要一个循环，依次对每个测试数据进行分类。

代码中大家可能不太明白hoRatio是什么。注意，这里的测试数据并不是另外一批数据而是之前的数据集里的一部分，这样我们可以把算法得到的结果和原本的分类进行对比，查看算法的准确度。在这里，海伦提供的数据集又1000行，我们把前100行作为测试数据，后900行作为样本数据集，现在大家应该可以明白hoRatio是什么了吧。

整体的代码：

1 from numpy import * 2 import operator 3  4 def classify0(inX, dataSet, labels, k): 5     dataSetSize = dataSet.shape[0] 6     diffMat = tile(inX, (dataSetSize,1)) - dataSet 7     sqDiffMat = diffMat**2 8     sqDistances = sqDiffMat.sum(axis=1) 9     distances = sqDistances**0.510     sortedDistIndicies = distances.argsort()11     classCount={}12     for i in range(k):13         voteIlabel = labels[sortedDistIndicies[i]]14         classCount[voteIlabel] = classCount.get(voteIlabel,0) + 115     sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)16     return sortedClassCount[0][0]17 18 def file2matrix(filename):19     fr = open(filename)20     numberOfLines = len(fr.readlines())21     returnMat = zeros((numberOfLines, 3))22     classLabelVector = []23     fr = open(filename)24     index = 025     for line in fr.readlines():26         line = line.strip()27         listFromLine = line.split('\t')28         returnMat[index, :] = listFromLine[0:3]29         classLabelVector.append(int(listFromLine[-1]))30         index += 131     return returnMat, classLabelVector  32 33 def autoNorm(dataSet):34     minVals = dataSet.min(0)35     maxVals = dataSet.max(0)36     ranges = maxVals - minVals37     normDataSet = zeros(shape(dataSet))38     m = dataSet.shape[0]39     normDataSet = dataSet - tile(minVals, (m, 1))40     normDataSet = normDataSet / tile(ranges, (m, 1))41     return normDataSet, ranges, minVals42 43 def datingClassTest():44     hoRatio = 0.1045     datingDataMat, datingLabels = file2matrix('datingTestSet.txt')46     normMat, ranges, minVals = autoNorm(datingDataMat)47     m = normMat.shape[0]48     numTestVecs = int(m * hoRatio)49     errorCount = 0.050     for i in range(numTestVecs):51         classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)52         if (classifierResult != datingLabels[i]): 53             print "分类结果: %d, 实际结果: %d" % (classifierResult, datingLabels[i]) 54             errorCount += 1.0

55 print "总错误率: %.2f" % (errorCount/float(numTestVecs)) 56 print "总错误数:%.2f" % errorCount

运行代码：

 

最后的错误率为0.05。

使用算法构建完整可用系统 参考网友

       下面，可以在这个训练集和分类器之上构建一个完整的可用系统了。

       系统功能很简单：用户输入要判断对象三个特征 - "每年获得的飞行常客里程数"，"玩网游所消耗的时间比"，"每年消耗的冰淇淋公升数"。

       PS：在真实系统中，这部分输入可不由用户来输入，而从网站直接下载数据。

       程序帮你判断你是不喜欢还是有点喜欢，抑或是很喜欢。

       这部分代码如下：

按 Ctrl+C 复制代码

按 Ctrl+C 复制代码

       运行结果：

       

至此完毕。