机器学习1——k近邻算法

k近邻(k-Nearest Neighbor，kNN)算法是经典的带监督的分类算法，核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则针对该样本的划分结果也属于这个类别。

1. 算法步骤

• 准备训练数据和测试数据；
• 确定参数 k；
• 计算测试数据与各个训练数据之间的距离，距离的递增关系进行排序；
• 选取距离最小的 k 个点；
• 确定前 k 个点所在类别的出现频率；
• 返回前 k 个点中出现频率最高的类别作为测试数据的预测分类。

2. Python代码实现kNN

2.1 算法实现

# python 3.7.2

from numpy import *
import operator

def kNNClassify(testData, trainData, labels, k):
    dataSize = trainData.shape[0]  # 测试数据矩阵的行数，4
    diffMat = tile(testData, (dataSize, 1)) - trainData  # numpy中的tile用于重复矩阵中的元素，构造和dataSize规格一样
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)  # 计算矩阵的行和
    distances = sqDistances ** 0.5  # 采用欧式距离计算
    sortedDisindexes = distances.argsort()  # 返回 排序 后对应的索引数据
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDisindexes[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  # 根据第2维进行排序
    return sortedClassCount[0][0]

假设训练数据为：

trainData= [[1, 1.1], [1, 1], [0, 0], [0, 0.1]]
labels = ['A', 'A', 'B', 'B']

测试数据为：

testData = [[1.1 , 1], [0.1, 0]]

2.2 实战：约会网站对象匹配

小明在某约会网站上浏览妹子，对看到的每一个妹子进行评价： largeDoses , smallDoses , didntLike ，评价的依据有3条：

• 每年旅行里程数
• 玩游戏占一天时间比重
• 每周吃的甜品数量

收集了1000条相关数据，存储在datingTestSet.txt文件中

40920    8.326976    0.953952    largeDoses
14488    7.153469    1.673904    smallDoses
26052    1.441871    0.805124    didntLike
75136    13.147394    0.428964    didntLike
38344    1.669788    0.134296    didntLike
72993    10.141740    1.032955    didntLike
35948    6.830792    1.213192    largeDoses
42666    13.276369    0.543880    largeDoses
67497    8.631577    0.749278    didntLike
35483    12.273169    1.508053    largeDoses
50242    3.723498    0.831917    didntLike
63275    8.385879    1.669485    didntLike
5569    4.875435    0.728658    smallDoses
51052    4.680098    0.625224    didntLike
...

2.2.1 读取文本文件数据，构造矩阵

def file2Matrix(filename):
    love_dictionary = {'largeDoses': 1, 'smallDoses': 0, 'didntLike': -1}
    fr = open('datingTestSet.txt')
    arrayOfLines = fr.readlines()
    numOfLines = len(arrayOfLines)
    dataMatrix = zeros((numOfLines, 3))  # 数据矩阵
    classLabels = []  # 标签数组
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        dataMatrix [index, :] = listFromLine[0:3]
        classLabels.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabels

2.2.2 数据归一化处理

各个维度的数值差异较大，直接使用会严重影响分类效果，因此需要进行归一化处理:

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

def autoNorm(dataSet):
    minVals = dataSet.min(0)  # min(0)返回列的最小值， min(1)返回行的最小值
    maxVals = dataSet.max(0)  # max(0)返回列的最大值， max(1)返回行的最大值
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = normDataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet

最后调用 kNNClassify 函数进行测试。此处省略

3. 算法优缺点

3.1 优点

• 简单，易于理解，易于实现；
• 适合数值型属性分类；
• 适合于多分类问题(multi-modal，对象具有多个类别标签)， kNN比SVM的表现要好。

3.2 缺点

• 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数，分类出现偏差。
• 计算量较大，每一个待分类的文本都要计算它到全体已知样本的距离。

4. 改进策略

改进策略主要分成了 分类效率 和 分类效果 两个方向：

• 分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
• 分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，如可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)；依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类

参考资料

• 《机器学习实战》