k-近邻算法

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 1,948字 | 阅读时长 ≈ 9 分钟

k-近邻算法

一、基本原理

  已知一个样本数据集合，包括每组数据及对应的标签，即数据集已经分类好。当再次输入一组数据时，将新数据的每个特征与样本集中的数据对应的特征进行比较，选择样本集中特征最相似（最近邻）的分类标签。
  我们只选择样本集中前k个最相似的数据，这也就是k-近邻算法的出处。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类，即判断这k个数据中在数据集中的分类标签各自是什么，最后判断最多的分类标签是什么，将此作为新数据的分类。

二、算法实现

  对未知类别属性的数据集中的每个点依次执行以下操作：
(1)计算已知类别数据集中的点与当前点之前的距离；(特征比较)
(2)按照距离递增次序排序；
(3)选取与当前点距离最小的k个点；(最近邻)
(4)确定前k个点所在的类别出现频率；(判断标签)
(5)返回前k个点出现频率最高的类别作为当前点的预测分类。

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def classifyKNN(inputData, dateSet, labels, k):
    dataSetSize = dataSet.shape[0]  # 返回dataSet的行数

    # 计算距离，输入的数据与每一个数据集里面的数据求距离
    diffMat = np.tile(inputData, (dataSetSize, 1)) - dataSet  
    # tile()：将数据重复m行n列
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5

    # 返回距离中元素从小到大排序后的索引值，可理解为从小到大排序，返回是值对应的索引值
    sortedDistIndices = distances.argsort()
    # argsort(): 返回数组值从小到大的索引值

    classCount = {}
    for i in range(k):
        # 按照从小到大的顺序依次获得 对应距离的类别属于label的哪一类，并计数
        voteLabel = labels[sortedDistIndices[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1        

    # 将字典按照对应键的值排序，即根据出现的频率次数排序    
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)       
    
    return sortedClassCount[0][0]

代码说明：
  函数有4个输入参数：输入数据inputData(1行m列)，原始数据集dateSet(m行n列)，分类标签label，即原始数据集中每行数据属于哪一类，分类基准k，即算法中的k。
  首先要计算输入数据与原始数据集中每行数据的距离。先将输入数据重复m行，在依次和数据集中的每行数据做距离运算。(最简单的距离为欧式距离。)
  其次对计算过的距离进行排序并计数，按照从小到大的顺序选取前k个。
  最后统计这前k个中出现频率最高的分类标签，并将此作为输入数据的分类标签。

三、项目实战——约会网站的配对效果

  项目流程：
(1)收集数据：提供文本文件
(2)准备数据：使用Python解析文本文件
  将收集到的原始数据转换为numpy数据，以便于后续分析
(3)分析数据：使用matplotlib画二维散点图
(4)训练算法：即编写KNN算法
(5)测试算法：利用部分原始数据集中的数据作为测试样本，对于KNN算法进行测试
(6)使用算法：输入一个新的数据进行预测
python代码：

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
# 项目1：优化约会网站的配对效果
import numpy as np
import operator


# 将数据分为两部分，即特征矩阵和对应的分类标签向量
def file2matrix(filename):
    # 获取特征矩阵的行（numberOfLines）和列（3）
    fr = open(filename)
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines)
    returnMat = np.zeros((numberOfLines, 3))

    classLabelVector = []
    index = 0  # 行的索引值
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        # 前3列为特征矩阵
        returnMat[index, :] = listFromLine[0:3] 

        # 最后1列为标签值
        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):
    # min()获取矩阵每一行的最小值，min(0)获取矩阵每一列的最小值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]

    # 每一行数据均需要归一化处理
    # tile()：将数据重复m行n列
    normDataSet = dataSet - np.tile(ranges, (m, 1))
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    return normDataSet, ranges, minVals


def classifyKNN(inputData, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]  # 返回dataSet的行数

    # 计算距离，输入的数据与每一个数据集里面的数据求距离
    diffMat = np.tile(inputData, (dataSetSize, 1)) - dataSet  
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5

    # 返回距离中元素从小到大排序后的索引值，可理解为从小到大排序，返回是值对应的索引值
    sortedDistIndices = distances.argsort()

    classCount = {}
    for i in range(k):
        # 按照从小到大的顺序依次获得 对应距离的类别属于label的哪一类，并计数
        voteLabel = labels[sortedDistIndices[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1        

        # 将字典按照对应键的值排序，即根据出现的频率次数排序    
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)       
        return sortedClassCount[0][0]


def datingClassTest():
    hoRatio = 0.1  # 选取10%的数据集
    datingDataMat, datingLabels = file2matrix(filename)
    normMat, ranges, minVals = autoNorm(datingDataMat) 
    m = normMat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        # 选取后10%作为测试数据：第numTestVecs行到第m行
        classifierResult = classifyKNN(normMat[i, :], normMat[numTestVecs:m, :], 
                                       datingLabels[numTestVecs:m], 3)
        if (classifierResult != datingLabels[i]):
            errorCount += 1.0
    print("the total error rate is : %f" % (errorCount / float(numTestVecs)))


def classifyPerson():
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))

    datingDataMat, datingLabels = file2matrix(filename)
    normMat, ranges, minVals = autoNorm(datingDataMat)   

    inputData = np.array([ffMiles, percentTats, iceCream])
    classifierResult = classifyKNN((inputData - minVals) / ranges, normMat, datingLabels, 3)

    resultList = ['not at all', 'in small doses', 'in large doses']
    print("You will probably like this person: ", resultList[classifierResult])


if __name__ == '__main__':
    filename = "datingTestSet.txt"
    datingClassTest()
    classifyPerson()

四、感悟

4.1 python知识

(1)np.zero((m,n)):创建一个m*n的零矩阵
(2)str.strip():删除字符串中的空白;str.split(‘\t’):TAB键切分字符串
(3)np.shape(A):返回A矩阵的行数和列数;A.shape[0]:返回A的行数;A.shape[1]:返回A的列数
(4)np.title(a,(m,n)):将数据a重复m行n列

4.2 算法

(1)k-近邻算法也称为KNN算法，属于有监督的算法。因为其原始数据集的分类标签是已知的。
(2)k-近邻算法最重要的一部分为计算新数据与原始数据集的距离。其核心思想为距离越近越认为是该分类标签。
(3)最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。这句话意思是，比如第1个距离最近的分类为好，第2个距离最近的分类为好，第3个距离最近的分类为坏，第4个距离最近的分类为好，那么前4个中，分类为好为3次，分类为坏为1次，则判定该新数据的分类为好。因此一般k的取值为奇数。
(4)在k-近邻算法中，使用的距离为欧式距离，即平面内两点间的距离，在其他算法会使用其他的距离来判断。

谢谢老板！
-------------本文结束感谢您的阅读给个五星好评吧~~-------------
欢迎光临
❤️
NJTech Cxx
请多关照
❤️
❤️