近邻算法
K-近邻算法是机器学习分类算法中最简单的方法之一。在讲清楚K-近邻算法之前，我们先来看看它的一个简化版---近邻算法。假设我们要对一部电影分类：判断它是动作片还是爱情片（假设全世界的电影只有这两类）。我们发现有两个指标可以帮助我们判断：电影中的打斗镜头和接吻镜头。我们有一批数据，记录了电影里面两种镜头的个数及专家对它们的分类（这个数据集经常被称之为训练集）。数据如下：
| 电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
|---|---|---|---|
| California Man | 3 | 104 | 爱情片 |
| He's Not Really into Dules | 2 | 100 | 爱情片 |
| Beautiful Woman | 1 | 81 | 爱情片 |
| Kevin Longblade | 101 | 10 | 动作片 |
| Robo Slayer 3000 | 99 | 5 | 动作片 |
| Amped II | 98 | 2 | 动作片 |
我们现在要判断某电影X的电影类型，它的打斗镜头为18，接吻镜头为90。
近邻算法的思想是在已知的六部电影中，找到与这部电影X最接近的电影，并将该电影的类型作为X的类型。
如何求“最相近”
在机器学习算法中，有很多计算距离的方法，我现在介绍两个最常用的距离：L1距离和L2距离。假设有两个点p1(x1, y1), p2(x2,y2)，则L1距离的公式为：
d(p1,p2) = |x1-x2| + |y1-y2|
L2 的计算公式为:
d(p1,p2) = sqrt((x1-x2)^2 + (y1-y2)^2)
现在我们用L2距离来计算相似度，并求出与X最接近的电影，代码如下：
#coding=utf-8
import numpy as np
data = np.array([[3,104], [2,100], [1,81], [101,10], [99,5], [98,2]])
label = np.array(['爱情片','爱情片','爱情片','动作片','动作片','动作片'])
target = np.array([18,90])
diffs = data-target
diffSum = []
for diff in diffs:
diffSum.append(np.sqrt(diff[0]**2 + diff[1]**2))
print np.argmin(diffSum)
print label[np.argmin(diffSum)]
输出的结果表明，X电影与He's Not Really into Dules 最相似。所以我们可以把它归为爱情片。
理解了近邻算法，k-近邻算法就非常容易理解了。k-近邻算法就是计算与电影X最接近的K（具体数目可以自己设定）个电影，然后取这个K个电影中类别数目最多的类别，并把它作为目标电影X的类别（代码在实战篇中会讲到）。
数据的可视化
我们可以使用matplotlib来对数据可视化，从而可以直观的感受我们为什么将X归为爱情片类别。可视化的代码为：
import matplotlib.pyplot as plt
import numpy as np
fig = plt.figure()
ax = fig.add_subplot(111)
data = np.array([[3,104], [2,100], [1,81], [101,10], [99,5], [98,2]])
label = np.array([1.,1.,1.,2.,2.,2.])
ax.scatter(data[:,0], data[:,1], np.pi*20*(label**2), label)
ax.scatter(18,90,np.pi*20*3, [[1,0,0]])
plt.xlim(0)
plt.ylim(0)
plt.savefig('fig.png')
plt.show()
输出的结果图为：
归一化特征
现在我们知道要计算两个物体的相似度，就是计算它已知特征的距离之和。由于各个特征的变化范围不一样，导致各个特征在计算最终的相似度时权重不一样，如果我们假设各个特征的权重都一样，那么就必须对各个特征进行归一化处理。比如，我们现在使用k-近邻算法找最合适的相亲对象。我们有一批数据，记录每个人的几个特征及你对她们的喜爱程度，表格如下：
|样本序号|玩视频游戏所耗时间百分比|每年获得的飞行常客里程数|每周消耗的冰激凌公升数|样本分类|
|----|
|1|0.8|400|0.5|1|
|2|12|134000|0.9|3|
|3|0|20000|1.1|2|
|4|67|32000|0.1|2|
我们发现里程数的差异已经远远大于其他特征的差异，这就导致其他特征几乎无法影响样本之间的差异了。所以，为了消除这些影响，我们将各个特征都归一化到[0,1]（归一到任何相同的范围都可）之间，转换的代码为：
newValue = (old_value-min)/(max-min)
这个每个特征的范围都被归一化到[0,1]。
理论知识已经讲解完毕，下面进入实战。
