KNN

K邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法

k-近邻算法(kNN,k-NearestNeighbor),是一种监督分类算法,是最简单的机器学习分类算法之一。其核心思想在于用距离目标最近的 k 个样本数据的分类来代表目标的分类(这k个样本数据和目标数据最为相似)。kNN 是一种惰性学习方法

无论是分类还是回归,衡量邻居的权重都非常有用,使较近邻居的权重比较远邻居的权重大。例如,一种常见的加权方案是给每个邻居权重赋值为1/ d,其中d是到邻居的距离。

k-近邻算法的缺点是对数据的局部结构非常敏感

算法描述

  1. 计算分类未知数据 x_new 与训练样本集数据 x 的欧氏距离 distance
  2. 将 distance 递增排序
  3. 选取 distance 的前 k 个点
  4. 选取前 k 个点中,出现频率最高的类别 y 作为 x_new的分类

代码实现

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
import numpy as np

def createDataSet():
group = np.array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels

"""
定义knn算法分类器函数
:param inX: 测试数据
:param dataSet: 训练数据
:param labels: 分类类别
:param k: k值
:return: 所属分类
"""
def classify(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] #shape(m, n)m列n个特征
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5 #欧式距离
sortedDistIndicies = distances.argsort() #排序并返回index

classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #default 0

sortedClassCount = sorted(classCount.items(), key=lambda d:d[1], reverse=True)
return sortedClassCount[0][0]

测试

1
2
3
4
if __name__ == '__main__':
dataSet, labels = createDataSet()
r = classify([0, 0.2], dataSet, labels, 3)
print(r)

输出 B


THE END.

评论