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. 改进策略
改进策略主要分成了分类效率和分类效果两个方向:
分类效率: 事先对样本属性进行约简, 删除对分类结果影响较小的属性. 该算法比较适用于样本容量比较大的类域的自动分类, 而那些样本容量较小的类域采用这种算法比较容易产生误分.
分类效果:1 采用权值的方法 (和该样本距离小的邻居权值大) 来改进, 如可调整权重的 k 最近邻居法 WAkNN (weighted adjusted k nearest neighbor);2 依照训练集合中各种分类的文件数量, 选取不同数目的最近邻居, 来参与分类;3 类中心算法, 求出各个样本的类中心到测试数据的距离, 划分到最近的类.
参考资料
《机器学习实战》
来源: https://www.2cto.com/kf/201904/805772.html