机器学习——k近邻算法

转载自https://blog.csdn.net/xundh/article/details/73611249

本文内容来自《机器学习实战》中国工信出版集团 人民邮电出版社

一、简介

简单地说，k-近邻算法采用测量不同特征值之间的距离方法进来分类
特点：

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

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

二、示例

电影分类。
样本数据：

电影名称	打斗镜头	接吻镜头	电影类型
California Man	3	104	爱情片
He’s Not Really into Dudes	2	100	爱情片
Beautiful woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	22	动作片
?	18	90	未知

如果我们计算出已知电影与未知电影的距离：

电影名称	与未知电影的距离
California Man	20.5
He’s Not Really into Dudes	18.7
Beautiful woman	19.2
Kevin Longblade	115.3
Robo Slayer 3000	117.4
Amped II	118.9

按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是：

1. He’s Not Really into Dudes
2. Beautiful woman
3. California Man

kNN按照距离最近的三部电影的类型，决定未知电影的类型——爱情片。

三、Python操作

1. 使用Python导入数据

from numpy import *
import operator

def createDataSet():
#用来创建数据集和标签
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group , labels

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

这里有4组数据，每组数据有两个我们已知的属性或者特征值。向量labels包含了每个数据点的标签信息，labels包含的元素个数等于group矩阵行数。这里将数据点（1,1.1）定义为类A，数据点（0,0.1）定义为类B。为了说明方便，例子中的数值是任意选择的，并没有给出轴标签。

kNN，带有4个数据点的简单例子。

2. 实施kNN分类算法

代码流程为：
计算已知类别数据集中的每个点依次执行以下操作

1. 计算已知类别数据集中的点与当前点之间的距离
2. 按照距离递增次序排序
3. 选择与当前点距离最小的κ个点
4. 确定前κ个点所在类别的出现概率
5. 返回前κ个点出现频率最高的类别作为当前点的预测分类

classify0函数：

def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = 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]

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

参数说明：

• inX：用于分类的输入向量
• dataSet：输入的训练样本集
• labels：标签向量
• k：用于选择最近邻居的数目

其中标签向量的元素数目和矩阵dataSet的行数相同。程序使用的是欧氏距离公式，计算向量xA与xB之间的距离：

d=(xA0−xB0)2+(xA1−xB1)2” role=”presentation” style=”text-align: center; position: relative;”>d=(xA0−xB0)2+(xA1−xB1)2−−−−−−−−−−−−−−−−−−−−−−−−√d=(xA0−xB0)2+(xA1−xB1)2

计算完距离后，对数据按照从小到大排序，确认前k个距离最小元素民在的主要分类。输入k总是正整数；最后，将classCount字典分解为元组列表，然后使用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序，最后返回发生频率最高的元素标签。
运行测试：

group , labels = createDataSet()
print(classify0([0,0],group,labels,3))

• 1
• 2

3. 如何测试分类器

错误率是评估常用方法，完美的错误率为0，最差错误率是1.0。

四、示例：使用kNN改进约会网站的配对效果

1.使用Matplotlib创建散点图

准备一份样本数据。

每年获得的飞行常客里程数 玩视频游戏所耗时间百分比 每周消费的冰淇淋公升数
40920   8.326976    0.953952    3
14488   7.153469    1.673904    2
26052   1.441871    0.805124    1
75136   13.147394   0.428964    1
38344   1.669788    0.134296    1
...

• 1
• 2
• 3
• 4
• 5
• 6
• 7

代码：

from numpy import *
import operator

def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = 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):
    fr = open(filename)
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines)
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1

datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')

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

• 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
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39

获得的散点图示例：

样本数据可以在网上通过搜索”datingTestSet2.txt”获得。这里散点图使用datingDataMat矩阵的第二、第三列数据，分别表示特征值“玩视频游戏所耗时间百分比”和“每周所消费的冰淇淋公升数”。

由于没有使用样本分类的特征值，在图上很难看出任何有用的数据模式信息。一般来说，可以采用色彩或其他的记号来标记不同样本分类，以便更好地理解数据信息。进行这样的修改：

ax.scatter(datingDataMat[:,1],datingDataMat[:,2] ,15.0*array(datingLabels),15.0*array(datingLabels))

• 1

利用变量datingLabels存储的类标签属性，在散点图上绘制了色彩不等、尺寸不同的点。

2.准备数据：归一化数值

归一化数值将不同取值范围的特征值进行数值归一化，如将取值范围处理为0到1或者-1到1之间。通过下面公式可以将取值范围特征值转化为0到1区间内的值：

newValue=(oldValue−min)/(max−min)” role=”presentation” style=”text-align: center; position: relative;”>newValue=(oldValue−min)/(max−min)newValue=(oldValue−min)/(max−min)

其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。下面autoNorm()函数实现归一化:

def autoNorm(dataSet):
      minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals -minVals
    nromDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals,(m,1))
    normDataSet = normDataSet/tile(ranges,(m,1))
    return normDataSet , ranges , minVals

normMat , ranges , minVals = autoNorm(datingDataMat)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

3.测试算法

通常我们使用已有数据的90%作为训练样本来训练分类器，而使用10%的数据去测试分类器，检测分类器的正确率。创建一个测试函数：

def datingClassTest():
    hoRatio = 0.10
    datingDataMat , datingLabels = file2matrix('datingTestSet.txt')
    normMat,ranges,minVals = 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)))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

使用

normMat , ranges , minVals = autoNorm(datingDataMat)
datingClassTest()

• 1
• 2

4.补全程序，实现完整功能

def classifyPerson():
    resultList = ['not at all','in small doses','in large doses']
    percentTats = float(input("percetage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("listers of ice cream consumed per year?"))
    datinDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    normMat,ranges ,minVals=autoNorm(datingDataMat)
    inArr = array([ffMiles,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
    print ("You will probably like this person:",resultList[classifierResult - 1])

classifyPerson()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

运行结果示例：