《机器学习实战》笔记(1)：kNN

前言

《机器学习实战》(Machine Learning in Action)确是一本入门的好教材，学习过后权且做个总结。

正文

1. 算法目的

未知分类的数据集进行预测分类

2. 原理(伪代码)

对未知类别属性的数据集中的每个点依次执行以下操作：
(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离递增次序排序；
(3) 选取与当前点距离最小的k个点(k<20)；
(4) 确定前k个点所在类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。

3. 原理详解

3.1 数据集(dataset)

机器学习是基于大数据的，因此收集准备数据集是很重要的一环。数据集有n行或者n列相同的数据组成(为了简化以后都说n行)，每行数据对应着一个标签，例如以下一个依据打斗镜头和接吻镜头数来进行电影分类的例子：

每部电影的打斗镜头数、接吻镜头数以及电影评估类型
电影名称	打斗镜头	接吻镜头	类型
California	3	104	爱情片
He’s Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	2	动作片
?	18	90	未知

其中每个电影的打斗镜头和接吻镜头数目就是每行数据的内容，类型即为标签，下面要预测未知电影的分类，就可以采用合适的分类方法，例如本篇的kNN算法。为了编程的方便可直接将以上内容抽象为：

(3,104)  A
(2,100)  A
(1,81)   A
(101,10) B
(99,5)   B
(98,2)   B

其中(3,104)是一行数据，在python中可以array形式储存，A表示爱情片，B表示动作片，它们都是标签，标签也用另外的array储存，注意以上数据集一般指的是已知分类的数据集，未知分类的可另外列出。数据集也可以以.txt的文件给出，利用python的文件读取将数据和标签储存为array形式即可，一般.txt内容如下

3.2 原理步骤详解

(1) 计算已知类别数据集中的点与当前点之间的距离

 对于二维的两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，他们的距离计算公式如： $d=sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 。

例如上面电影未知分类的数据集只有一个点(18,90)，已知分类的数据集中第一个点与当前点的距离为：

$d=sqrt{(3-18)^2+(104-90)^2}=28.30$

对于高维的情况，例如(1,0,0,1)和(1,3,1,4)：

$d=sqrt{(1-1)^2+(0-3)^2+(0-1)^2+(1-4)^2)}$

其余计算略，列表如下

3 104 A 28.30
2 100 A 18.87    
1 81 A 19.24
101 10 B 115.28
99 5 B 117.41
98 2 B 118.93

(2) 按照距离递增次序排序

直接排序如下：

2 100 A 18.87    
1 81 A 19.24
3 104 A 28.30
101 10 B 115.28
99 5 B 117.41
98 2 B 118.93

(3) 选取与当前点距离最小的k个点(k<20)

这里的k为正整数，一般小于20，也是为什么叫做k邻近算法的原因，k一般如何取值这里不讲，这里就取k=3

2 100 A 18.87    
1 81 A 19.24
3 104 A 28.30

(4) 确定前k个点所在类别的出现频率

由步骤(3)可知，类别A出现的频率为1，B为0

(5) 返回前k个点出现频率最高的类别作为当前点的预测分类

由于A出现的频率最高，即可以预测当前未知点(18,90)的类别为A，即爱情片

3.3 代码实现

此处暂时略过，具体可参考《机器学习实战源码》，慢点本人贴出下载链接