k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。
它的工作原理是:存在一个样本数据集合,也称作为训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数据与所属分类的对应关系。
输入没有标签的新数据后,将新的数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本最相似数据(最近邻)的分类标签。
一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。
最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。
我们已经知道k-近邻算法根据特征比较,然后提取样本集中特征最相似数据(最邻近)的分类标签。
那么,如何进行比较呢?比如,我们还是以表1.1为例,怎么判断红色圆点标记的电影所属的类别呢? 如下图所示。
我们可以从散点图大致推断,这个红色圆点标记的电影可能属于动作片,因为距离已知的那两个动作片的圆点更近。
k-近邻算法用什么方法进行判断呢?没错,就是距离度量。这个电影分类的例子有2个特征,也就是在2维实数向量空间,
可以使用我们高中学过的两点距离公式计算距离,
通过计算可知,红色圆点标记的电影到动作片 (108,5)的距离最近,为16.55。
如果算法直接根据这个结果,判断该红色圆点标记的电影为动作片,这个算法就是最近邻算法,
而非k-近邻算法。那么k-近邻算法是什么呢?k-近邻算法步骤如下:
比如,现在我这个k值取3,那么在电影例子中,按距离依次排序的三个点分别是动作片(108,5)、动作片(115,8)、爱情片(5,89)。
在这三个点中,动作片出现的频率为三分之二,爱情片出现的频率为三分之一,所以该红色圆点标记的电影为动作片。这个判别过程就是k-近邻算法。
(1) 准备数据集合
对于表1.1中的数据,我们可以使用numpy直接创建,代码如下:
结果内容如下。
(2)k-近邻算法
根据两点距离公式,计算距离,选择距离最小的前k个点,并返回分类结果。
数据输出结果:
group [[ 1 101]
[ 5 89]
[108 5]
[115 8]]
labels ['爱情片', '爱情片', '动作片', '动作片']
datasetsize 4
diffmat [[100 -81]
[ 96 -69]
[ -7 15]
[-14 12]]
sqdiffmat [[10000 6561]
[ 9216 4761]
[ 49 225]
[ 196 144]]
sqdistances [16561 13977 274 340]
distances [ 128.68954892 118.22436297 16.55294536 18.43908891]
sortedDistIndices [2 3 1 0]
voteIlabel 0 动作片
classCount[voteIlabel] 1
voteIlabel 1 动作片
classCount[voteIlabel] 2
voteIlabel 2 爱情片
classCount[voteIlabel] 1
sortedClassCount [('动作片', 2), ('爱情片', 1)]
动作片
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。