机器学习实战之K-近邻算法

发表于 | 分类于
字数统计: 1.3k

K-近邻算法

k近邻算法通过选择样本集中前k个最相似的数据，这也是k-近邻算法中k的出处，通常k不大于20的整数，

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

预测约会网站配对

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
# -*- coding: UTF-8 -*-
from numpy import *
import operator
import matplotlib
import matplotlib.pyplot as plt

# k 近邻算法第一个分类器
def craetaDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A','A','B','B']
    return group,labels

# k近邻分类器   inX 分类输入的向量  dataSet 输入的训练样本集  labels标签  k选择临近的数目
def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]   # numpy函数shape[0]返回dataSet的行数
    diffMat = tile(inX,(dataSetSize,1)) - dataSet   # 在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
    sqDiffMat = diffMat**2  #二维特征相减后平方
    sqDistances = sqDiffMat.sum(axis=1)  #sum()所有元素相加，sum(0)列相加，sum(1)行相加
    distances = sqDistances**0.5  #开方，计算出距离
    sortedDistIndices = distances.argsort()  #返回distances中元素从小到大排序后的索引值
    classCount = {}  #定一个记录类别次数的字典
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]  #取出前k个元素的类别
        #dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1  #计算类别次数
    #python3中用items()替换python2中的iteritems()
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    #reverse降序排序字典
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]  #返回次数最多的类别,即所要分类的类别

# 打开数据集 转化成矩阵
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()   # 删除首尾空白符
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        if listFromLine[-1] == 'didntLike':
            classLabelVector.append(1)
        elif listFromLine[-1] == 'smallDoses':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'largeDoses':
            classLabelVector.append(3)
        index += 1
    return returnMat,classLabelVector


# 数据归一化   newValue = (oldValue - min) / (max - min)
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]   # m为 dataSet 的行数
    normDataSet = dataSet - tile(minVals,(m,1))  # 原始值减去最小值
    normDataSet = normDataSet/tile(ranges,(m,1))
    return  normDataSet , ranges , minVals

# 测试分类器错误率
def datingclassTest():
    hoRatio = 0.10  #取所有数据的前百分之10 进行测试
    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
    normalMat, ranges, minVals = autoNorm(datingDataMat)
    m = normalMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normalMat[i,:], normalMat[numTestVecs:m,:],datingLabels[numTestVecs:m], 4)
        print("分类结果:%d\t真实类别:%d" % (classifierResult, datingLabels[i]))
        if(classifierResult != datingLabels[i]):
            errorCount += 1
    print("错误率:%f%%" % (errorCount / float(numTestVecs) * 100))


def classifyperson():
    resultList = ['not at all','in small doses','in large doses']
    percentTats = float(raw_input("玩视频游戏所耗时间百分比:"))
    ffMiles = float(raw_input("每年获得的飞行常客里程数:"))
    iceCream = float(raw_input("每周消费的冰激淋公升数:"))
    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
    normalMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normalMat,datingLabels,3)
    print "You will probably like this person:  %s"  %(resultList[classifierResult-1])

if __name__ == '__main__':
    # group,labels = craetaDataSet()
    # print(group)
    # print(labels)
    # k = classify0([0,0],group,labels,3)
    # print  k

    #datingDataMat,datingLabels = file2matrix('datingTestSet.txt')
    # fig = plt.figure()
    # ax = fig.add_subplot(111)
    # ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
    # plt.show()
    # print datingLabels
    #
    # normalMat,ranges , minVals = autoNorm(datingDataMat)
    # print(datingDataMat)
    # print normalMat

    #datingclassTest()
    classifyperson()

手写识别系统

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
40
41
42
43
44
45
46
47
48
49
50
# -*- coding: UTF-8 -*-
from os import listdir  # 列出给定目录的文件名
from numpy import *
from kNN import classify0


def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect


# 因为值为0,1 所以不用归一化
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('G:\机器学习\机器学习实战\机器学习实战（中文版+英文版+源代码）\machinelearninginaction\Ch02\\trainingDigits')
    m = len(trainingFileList)
    trainMat = zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainMat[i, :] = img2vector(
            'G:\机器学习\机器学习实战\机器学习实战（中文版+英文版+源代码）\machinelearninginaction\Ch02\\trainingDigits\\%s' % fileNameStr)
    testFileList = listdir('G:\机器学习\机器学习实战\机器学习实战（中文版+英文版+源代码）\machinelearninginaction\Ch02\\testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector(
            'G:\机器学习\机器学习实战\机器学习实战（中文版+英文版+源代码）\machinelearninginaction\Ch02\\testDigits\\%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainMat, hwLabels, 3)
        print('分类结果为:%d'  '真实结果为:%d' % (classifierResult, classNumStr))
        if (classifierResult != classNumStr):
            errorCount += 1.0
    print('\n 错误个数为:%d' % errorCount)
    print('\n 错误比例为:%f' % (errorCount / float(mTest)))


if __name__ == '__main__':
    # tesstVector = img2vector('G:\机器学习\机器学习实战\机器学习实战（中文版+英文版+源代码）\machinelearninginaction\Ch02\\trainingDigits\\0_13.txt')
    # print(tesstVector)
    handwritingClassTest()

总结

K-近邻算法 简单有效 但是执行效率低，占用大量存储空间，而且必须对数据集中的每个数据计算距离值，耗时。

-------------The End-------------