kNN算法

发表于 |

1、knn?

k-近邻算法采用测量不同特征值之间距离的方法进行分类.思想很简单：如果一个样本的特征空间中最为临近（欧式距离进行判断）的K个点大都属于某一个类，那么该样本就属于这个类。这就是物以类聚的思想。

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

通过计算新数据与训练数据特征值之间的距离，然后选取K（K>=1）个距离最近的进行分类判断

1.1 关键

1、数据的所有特征都要做可比较的量化。
若是数据特征中存在非数值的类型，必须采取手段将其量化为数值。另外，样本有多个参数，每一个参数都有自己的定义域和取值范围，他们对distance计算的影响也就不一样，so样本参数必须做一些scale处理，usually所有特征的数值都采取归一化处置。

2、需要一个distance函数以计算两个样本之间的距离。
距离的定义有很多，如欧氏距离、余弦距离、汉明距离、曼哈顿距离等等.about相似性度量的方法可参考‘漫谈：机器学习中距离和相似性度量方法’。usually选欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，汉明距离可以用来作为度量。btw，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法。

3，确定K的值
K是一个自定义的常数，K的值也直接影响最后的估计，一种选择K值得方法是使用 cross-validate（交叉验证）误差统计选择法(就是数据样本的一部分作为训练样本，一部分作为测试样本，比如选择95%作为训练样本，剩下的用作测试样本。)通过训练数据训练一个机器学习模型，然后利用测试数据测试其误差率。 cross-validate（交叉验证）误差统计选择法就是比较不同K值时的交叉验证平均误差率，选择误差率最小的那个K值。例如选择K=1,2,3,… ， 对每个K=i做100次交叉验证，计算出平均误差，然后比较、选出最小的那个。

2、原理

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

3.1机器学习实战上的电影例子

用 K-近邻算法来分来爱情片和动作片

即使不知道未知电影属于哪种类型，我们也可以通过某种方法计算出来。首先要计算未知电影与样本集中其他电影的距离，计算方法很简单，即欧式空间距离(Euclidean Distance)

现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到 k 个距离最近的电影，例如 k=3

K-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。

3.2knn流程

距离计算所需要的值，最好是结构化的数据。

KNN算法的过程为:
选择一种距离计算方式, 通过数据所有的特征计算新数据与已知类别数据集中的数据点的距离
按照距离递增次序进行排序，选取与当前距离最小的k个点
对于离散分类，返回k个点出现频率最多的类别作预测分类；对于回归则返回k个点的加权值作为预测值

使用算法：首先需要输入样本数据和待分类数据，然后运行k-近邻算法判定待分类数据分别属于哪个分类，最后应用计算出的分类执行后续的处理

4.python实现knn

4.1python导入数据

将下面的代码保存到名为 kNN.py 的文本文件中：

1
2
3
4
5
6
7
8
from numpy import *
def createDataSet():
dataSet = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) # 创建一个2x2的数组
labels = ['A', 'A', 'B', 'B'] # 创建一个长度为4的列表
return dataSet, labels
1
2
3
4
>>> import kNN
>>> group,labels=kNN.createDataSet()
>>> kNN.classify0([0,0],group,labels,3)

4.2实现knn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from operator import itemgetter
# inVec为待分类向量，dataSet和labels为数据集，k是最近点的个数
def classify0(inVec, dataSet, labels, k):
numberOfLines = dataSet.shape[0] # 获得数据集样本数量
diffMat = tile(inVec, (numberOfLines, 1)) - dataSet # 将数据集中每个点都与待分类点相减，即各个特征相减
squareDiffMat = diffMat**2 # 求差的平方
squareDistance = squareDiffMat.sum(axis=1) # 求差的平方的和
distances = squareDistance**0.5 # 对平方和开方得到距离
# 对距离进行排序，argsort()函数默认按升序排列，但只返回下标，不对原数组排序
sortedDistIndicies = distances.argsort()
classCount = {} # 用于保存各个类别出现的次数
for i in range(k): # 统计最近的 k 个点的类别出现的次数
label = labels[sortedDistIndicies[i]]
classCount[label] = classCount.get(label, 0) + 1
# 对类别出现的次数进行排序，sorted()函数默认升序
sortedClassCount = sorted(classCount.iteritems(), key=itemgetter(1), reverse=True)
return sortedClassCount[0][0] # 返回类别出现次数最多的分类名称

1、shape()函数：返回数组的尺寸信息

1
2
>>> x = tile((1,2),(3,2))
>>> x.shape[0]

2、tile()函数

1
>>> tile([1,2],(3,2))

3、sum()函数

1
2
3
4
5
6
7
8
>>> x = tile((1,2),(3,2))
>>> x
array([[1, 2, 1, 2],
       [1, 2, 1, 2],
       [1, 2, 1, 2]])
>>> x.sum(axis=0)
array([3, 6, 3, 6])
>>> x.sum(axis=1)

4、argsort()函数，返回排序后的原来位置的索引

1
2
>>> v = [1, 4, 2, 3]
>>> argsort(v)

5、sorted()函数，按参数 key 排序

1
2
3
4
5
6
7
8
9
10
11
>>> d = {'a':2,'b':1,'c':6,'d':-2}
>>> d
{'a': 2, 'c': 6, 'b': 1, 'd': -2}
>>> from operator import itemgetter
>>> sorted(d.iteritems(),key=itemgetter(1),reverse=True)
```		
## 4.3测试分类器
# 5.knn改进配对算法
## 5.1从文本中解析数据

def file2matrix(filename):
f = open(filename) # 打开文件
dataSet = f.readlines() # 读取文件的全部内容
numberOfLines = len(dataSet) # 获得数据集的行数
returnMat = zeros((numberOfLines, 3)) # 创建一个初始值为0，大小为 numberOfLines x 3 的数组
classLabelVector = [] # 用于保存没个数据的类别标签
index = 0
for line in dataSet: # 处理每一行数据
line = line.strip() # 去掉行首尾的空白字符,(包括’\n’, ‘\r’, ‘\t’, ‘ ‘)
listFromLine = line.split() # 分割每行数据，保存到一个列表中
returnMat[index, :] = listFromLine[0:3] # 将列表中的特征保存到reurnMat中
classLabelVector.append(int(listFromLine[-1])) # 保存分类标签
index += 1
return returnMat, classLabelVector

1
2
3
```
>>> reload(kNN)
 >>> datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.txt')

5.2分析数据

使用 Matplotlib 创建散点图

1
2
3
4
5
6
>>> import matplotlib
>>> import matplotlib.pyplot as plt
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
>>> plt.show()

Matplotlib 库提供的 scatter 函数支持个性化标记散点图上的点。

1
2
3
4
5
>>> from numpy import *
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
>>> plt.show()

将每年获得的飞行常客里程数作为 x 轴，玩视频游戏所耗时间百分比作为 y 轴

1
2
3
4
>>> fig = plt.figure()
>>> ax = fig.add_subplot(111)
>>> ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))
>>> plt.show()

另外，为了方便画图，不用每次都输入上面几行代码，我们可以写一个函数 showPlots 来完成同样的功能(将代码添加到 kNN.py 中)：

1
2
3
4
5
6
7
8
from numpy import *
import matplotlib.pyplot as plt
def showPlots(x, y, labels): # x:x轴数据，y:轴数据，labels:分类标签数据
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(x ,y, 15.0*array(labels), 15*array(labels))
plt.show()

重新载入 kNN.py ，输入如下代码即可画图：

1
2
>>> reload(kNN)
>>> kNN.showPlots(datingDataMat[:,0], datingDataMat[:,1], datingLabels)

5.3归一化

处理这种不同取值范围的特征值时，我们需要对数据进行归一化处理(权重一样，但是数值范围不同）

1
2
3
4
5
6
7
8
9
10
def autoNorm(dataSet):
minVals = dataSet.min(0) # minVals保存每列最小值
maxVals = dataSet.max(0) # maxVals保存每列最大值
ranges = maxVals - minVals # ranges保存每列的取值范围
normedDataSet = zeros(shape(dataSet))
numberOfLines = dataSet.shape[0]
normedDataSet = dataSet - tile(minVals, (numberOfLines, 1))
normedDataSet = normedDataSet / tile(ranges, (numberOfLines, 1))
return normedDataSet, ranges, minVals
1
2
3
4
>>> reload(kNN)
>>> normMat, ranges, minVals = kNN.autoNorm(datingDataMat)
>>> normMat
>>>

5.4测试

分类器的错误率=错误分类次数/分类测试总次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def datingClassTest():
testRatio = 0.10 # 测试比例
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') # 获得原始数据
normedMat, ranges, minVals = autoNorm(datingDataMat) # 归一化
m = normedMat.shape[0] # 原始数据行数
numTestVecs = int(m*testRatio) # 测试数据行数
errorCount = 0 # 错误分类计数器
for i in range(numTestVecs): # 测试
classifierResult = classify0(normedMat[i,:], 
normedMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4)
print "The classifier came back with: %d, the real answer is: %d"\
% (classifierResult, datingLabels[i])
if(classifierResult != datingLabels[i]):
errorCount += 1
print "The total error rate is: %f" % (errorCount/float(numTestVecs))
1
2
>>> reload(kNN)
>>> kNN.datingClassTest()

5.5完整系统

1
2
3
4
5
6
7
8
9
10
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTime = float(raw_input("percentage of time spent playing video games: "))
ffMiles = float(raw_input("frequent flier miles earned per year: "))
iceCream = float(raw_input("liters of ice cream consumed per year: "))
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normedMat, ranges, minVals = autoNorm(datingDataMat)
inVec = array([ffMiles, percentTime, iceCream])
classifierResult = classify0((inVec-minVals)/ranges, normedMat, datingLabels, 4)
print "You will probably like this person", resultList[classifierResult-1]
1
2
>>> reload(kNN)
>>> kNN.classifyPerson()

6.手写识别系统

书本配备了两个数据集，一个是存储在文件夹 trainingDigits 内的训练集，大约2000个样本；另一个是存储在 testDigits 文件夹内的测试集，大约900个样本。如下图所示。两组数据没有重叠，尺寸均为 32行 x 32列。

文件夹 trainingDigits 和文件夹 testDigits 的内容都是如下形式的样列：

将 32x32 的文本处理为一个尺寸为 1x1024 向量

1
2
3
4
5
6
7
8
def img2vector(filename):
returnVec = zeros((1,1024)) # 用于保存1x1024的向量
f = open(filename) # 打开文件
for i in range(32): # 读取每一行并转换为1x1024的向量
lineStr = f.readline()
for j in range(32): # 处理第i行j列的一个字符
returnVec[0,32*i+j] = int(lineStr[j]) # 字符需要强制类型转换成整数
return returnVec

检查

1
2
3
4
5
>>> reload(kNN)
>>> testVec = kNN.img2vector('testDigits/0_13.txt')
>>> testVec
array([[ 0.,  0.,  0., ...,  0.,  0.,  0.]])
>>> testVec[0,0:32]

6.2 测试算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from os import listdir
def handwritingClassTest():
print "Loading data..."
hwLabels = [] # 保存手写数字的分类标签
trainingFileList = listdir('trainingDigits') # 得到文件夹trainingDigits下的所有文件名
m = len(trainingFileList) # 训练集样本的个数
trainingMat = zeros((m, 1024)) # 保存训练集
for i in range(m):
filenameStr = trainingFileList[i] # 得到文件名
classNum = int(filenameStr.split('_')[0]) # 得到样本的分类标签
hwLabels.append(classNum)
trainingMat[i,:] = img2vector('trainingDigits/%s' % filenameStr)
testFileList = listdir('testDigits') # 得到文件夹testDigits下的所有文件名
errorCount = 0 # 错误分类计数器
mTest = len(testFileList) # 测试集样本个数
for i in range(mTest): # 开始测试
filenameStr = testFileList[i]
classNum = int(filenameStr.split('_')[0])
testVect = img2vector('trainingDigits/%s' % filenameStr)
classifierResult = classify0(testVect, trainingMat, hwLabels, 3)
print "The classifier came back with: %d, the real answer is: %d"\
% (classifierResult, classNum)
if(classifierResult != classNum):
errorCount += 1
print "The total number of errors is: %d" % errorCount
print "The total error rate is: %f" % (errorCount/float(mTest))

输入下面的命令对分类器进行测试（k=3）

1
2
>>> reload(kNN)
>>> kNN.handwritingClassTest()

如果选择最近的一个作为分类标签，那么准确率会非常的高：

1
2
3
>>> reload(kNN)
<module 'kNN' from 'kNN.pyc'>
>>> kNN.handwritingClassTest()

总结

1、kNN缺陷是无法给出任何数据的基础结构信息。而决策树能够解决这个问题，并且速度很快。
2、另一个缺点就是既占空间速度又慢