The K Nearest Neighbor Algorithm

活着的目的不在于永远活着,而在于永远活出自己。
在模式识别领域中,最近邻居法(KNN算法,又译K-近邻算法)是一种用于分类和回归的非参数统计方法。
在这两种情况下,输入包含特征空间(Feature Space)中的k个最接近的训练样本。

这次主要实现了使用原生 Python 来模拟一个 KNN 算法。


k-nearest neighbors algorithm

K-NN 是一种基于实例的学习,或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。

  • k-NN 分类中,输出是一个分类族群。一个对象的分类是由其邻居的 “多数表决” 确定的,k个最近邻居(k为正整数,通常较小)中最常见的分类决定了赋予该对象的类别。若 k = 1,则该对象的类别直接由最近的一个节点赋予。
  • k-NN 回归中,输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

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

邻居都取自一组已经正确分类(在回归的情况下,指属性值正确)的对象。虽然没要求明确的训练步骤,但这也可以当作是此算法的一个训练样本集。
k-近邻算法的缺点是对数据的局部结构非常敏感。本算法与K-平均算法(另一流行的机器学习技术)没有任何关系,请勿与之混淆。

Algorithm

训练样本是多维特征空间向量,其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。

在分类阶段,k是一个用户定义的常数。一个没有类别标签的向量(查询或测试点)将被归类为最接近该点的k个样本点中最频繁使用的一类。

一般情况下,将欧氏距离作为距离度量,但是这是只适用于连续变量。在文本分类这种离散变量情况下,另一个度量——重叠度量(或海明距离)可以用来作为度量。例如对于基因表达微阵列数据,k-NN 也与 PearsonSpearman 相关系数结合起来使用。通常情况下,如果运用一些特殊的算法来计算度量的话,k近邻分类精度可显著提高,如运用大间隔最近邻居或者邻里成分分析法

“多数表决” 分类会在类别分布偏斜时出现缺陷。也就是说,出现频率较多的样本将会主导测试点的预测结果,因为他们比较大可能出现在测试点的 K 邻域而测试点的属性又是通过 k 邻域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将样本到 k 个近邻点的距离考虑进去。k 近邻点中每一个的分类(对于回归问题来说,是数值)都乘以与测试点之间距离的成反比的权重。另一种克服偏斜的方式是通过数据表示形式的抽象。例如,在自组织映射(SOM)中,每个节点是相似的点的一个集群的代表(中心),而与它们在原始训练数据的密度无关。K-NN 可以应用到 SOM 中。

发展

然而 k 最近邻居法因为计算量相当的大,所以相当的耗时,Ko 与 Seo 提出一算法 TCFPtext categorization using feature projection),尝试利用特征投影法来降低与分类无关的特征对于系统的影响,并借此提升系统性能,其实验结果显示其分类效果与 k 最近邻居法相近,但其运算所需时间仅需k最近邻居法运算时间的五十分之一。

除了针对文件分类的效率,尚有研究针对如何促进k最近邻居法在文件分类方面的效果,如 Han 等人于 2002 年尝试利用贪心法,针对文件分类实做可调整权重的k最近邻居法 WAkNNweighted adjusted k nearest neighbor),以促进分类效果;而 Li 等人于 2004 年提出由于不同分类的文件本身有数量上有差异,因此也应该依照训练集合中各种分类的文件数量,选取不同数目的最近邻居,来参与分类。

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
# -*- coding: utf-8 -*-
"""
author: Wang Qinhong
date: 2019/10/14
title: 模拟 K Nearest Neighbor Algorithm
IDE: Jet Brains PyCharm 2019.2
"""

from sklearn.datasets import load_iris # 从 sklearn 中导入鸢尾花数据集
import math # 数学计算标准库
from collections import Counter # Collection标准库
import numpy as np # 导入 numpy 科学计算库


class k_nearest_neighbor_algorithm:
""" Main K Nearest Neighbor Algorithm

定义了有关 KNN 算法的基础操作

Attributes:
x_train: training test of X
y_train: training test of Y
k: The numbers of neighbors
"""

def __init__(self, k):
"""
Default Constructor
:param k: The numbers of neighbors
"""
self.k = k
self.x_train = None
self.y_train = None

def fit(self, x_train, y_train):
"""
监督训练
:param x_train: training test of X
:param y_train: training test of Y
:return: This object
"""
self.x_train = x_train
self.y_train = y_train
return self

def predict(self, x_pretest):
"""
给定待预测数剧集,给出预测结果向量
:param x_pretest: 给定结果的数据集
:return: 预测结果向量
"""
y_pretest = [self.get_answer(x) for x in x_pretest]
return np.array(y_pretest)

def get_answer(self, test_data):
"""
给定单个数据,返回预测类别
:param test_data: 测试数据
:return: 预测结果
"""
# 计算距离
d = [math.sqrt(np.sum((test_data - self.x_train[iter]) ** 2)) for iter in range(len(self.x_train))]
near = np.argsort(d)
top_k = [self.y_train[iter] for iter in near[0:6]]
votes = Counter(top_k) # 计算k个最近邻
return votes.most_common(1)[0][0] # 预测结果


# 载入数据集,有iris.data和iris.target
iris = load_iris()

print("TEST DATA: ")
for i in iris:
print(i + ":")
print(iris.get(i))

knn = k_nearest_neighbor_algorithm(6) # 设置 K = 6
knn.fit(iris.data[0:149], iris.target[:149])

answer_target = knn.predict([iris.data[149]])
print("*" * 80, )
print("\nThe answer is: ")
for i, j in zip(iris.feature_names, iris.data[149]):
print(i + ": ", end="")
print(j)
print("\n" + r"iris.date[149]'s target is : " + str(answer_target), end="")
print(r", It's " + iris.target_names[int(str(answer_target)[1])] + "\n")
print("*" * 80, )

输出结果

run01.png

run02.png

run03.png

run04.png

参考文献

-------------本文结束 Euphoria 在此感谢您的阅读-------------

本文标题:The K Nearest Neighbor Algorithm

文章作者:王钦弘

发布时间:2019年10月15日 - 11:34

最后更新:2019年12月08日 - 00:37

原始链接:https://www.wqh4u.cn/2019/10/15/The-K-Nearest-Neighbor-Algorithm/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

您的支持将鼓励 Euphoria 继续创作!
(如果你还是学生请千万不要打赏,留点钱在学习上啊!)
0%