近朱者赤近墨者黑的K近邻算法

一. KNN算法原理

KNN算法在机器学习里面，属于相对简单的算法。KNN即K近邻（K Nerest Neighbor）算法，KNN算法原理用一句话说，就是“近朱者赤近墨者黑”原理。举个例子，KNN算法是知道我朋友的是什么人，来判断我是什么人的算法。根据我所有的朋友中，如果我多数朋友属于待人诚恳的人，那我多半也是个待人诚恳的人（：））。

二. KNN算法的步骤

KNN算法可以用于分类和回归，所谓的分类，比如要把电影分为功夫片，喜剧片，爱情片等，得到的值是相当于一个枚举值；回归问题，结果是连续值中的一个，比如要求一个人的身高，求一个而房屋的房价估值，这就算回归。

KNN算法，中的K是距离待分类物体的K个离它最近的邻居，一般套路是：

计算要待分类与其他物体之间的距离。
得到与待分类物体的最近的K个物体。
判断这K个物体属于什么类别，那么这个待分类的物体就属于什么类别。
K近邻算法从上面看出，其实不需要拟合什么模型，只是基于存储的算法。
也可以看出两个最为关键：
1.K值如何选择？
2.距离如何计算。
K值不能选的太小，太小，有可能是噪音节点和待分类节点靠近，那么就造成分类的错误；如果K值过大，不在一类的物体分到一类里面了，容易造成欠拟和，有可能没有把物体的分类真正分出来。

举个例子：

K近邻算法

如上面的例子：
1）选择K=3的时候，离绿色待分类点最近的三个点中，2个属于红色三角形，1个属于蓝色正方形这一类，我们把绿色节点归于红色三角类。
2）选择K=5的时候，离绿色待分类点最近的5个点中，3个属于蓝色正方形类，2个属于红色三角类，所以绿色待分类的节点属于蓝色正方形类。
至于这些蓝色正方形和红色三角形确定好的分类，是以前标记过的。
好的，下面来看看KNN中的几种计算距离的算法：
欧式距离
1.欧式距离，就是空间中两个点的直线距离。
空间两个点的坐标分别为：(x1,y1)和(x2,y2)那么它们的欧式距离为：

公式

这个公式其实就是求出了如下图中的AB之间的这个斜线的长度。

欧式距离

N维空间中的AB两点的欧式距离公式为：
A点的坐标为(x1,x2,x3...xn)
B点的坐标为(y1,y2,y3...yn)

N维空间中AB两点中欧式距离

曼哈顿距离
2.曼哈顿距离是两点的坐标的之差的绝对值之和。点A坐标为(x1,y1),点B的坐标为（x2，y2）
公式为：

曼哈顿距离公式

曼哈顿距离

图中的黄色的和灰色也就是最外面两个折线就是曼哈顿距离，红色和蓝色也是等价的曼哈顿距离，绿色的为上面说的欧式距离。

N维的曼哈顿距离为：

N维曼哈顿距离

切比雪夫距离
3.切比雪夫距离在 二维空间 内，两个点之间的切比雪夫距离为它们横坐标之差的绝对值与纵坐标之差的绝对值的最大值。比如A点坐标为(X1,Y1) B点坐标为(X2,Y2) .则 A,B 之间的切比雪夫距离用公式可以表示为：

切比雪夫距离

闵可夫斯基距离
这个闵可夫斯基距离不是一个距离，是一组距离的定义，公式如下：

闵可夫斯基距离

p表示维度，如果p为1，则为曼哈顿距离，如果p为2则为欧式距离，p为无穷大，则为切比雪距离。

余弦距离
余弦距离以前的文章有介绍，其实算是求两个向量的夹角，可以用来计算物品的相似度，或搜索文本的相似度，适合做搜索。

KNN的近邻算法需要大量计算两个物体的距离，所以性能比较低，为了提升性能，就有了KD数，这是对N维向量的二叉树表示的数据结构，

三实战

sklearn里面也有knn算法，里面的核心函数说明如下：

def KNeighborsClassifier(n_neighbors = 5,
                       weights='uniform',
                       algorithm = '',
                       leaf_size = '30',
                       p = 2,
                       metric = 'minkowski',
                       metric_params = None,
                       n_jobs = None
                       )

参数说明：

n_neighbors：这个值就是指 KNN 中的 “K”。
weights：权重，这个参数有三个可选参数的值，决定了如何分配权重。参数选项如下：
• 'uniform'：不管远近权重都一样，就是最普通的 KNN 算法的形式。
• 'distance'：权重和距离成反比，距离预测目标越近具有越高的权重。
• 自定义函数：自定义函数，根据输入的坐标值返回对应的权重，达到自定义权重的目的。
algorithm: 在 sklearn 中，要构建 KNN 模型有三种构建方式：

暴力法，就是直接计算距离存储比较的，适合小数据集合。
使用 kd 树构建 KNN 模型
使用球树构建。
如果数据量比较大一般会选择用 KD 树构建 KNN 模型，而当 KD 树也比较慢的时候，则可以试试球树来构建 KNN。参数选项如下：
• 'brute' ：蛮力实现
• 'kd_tree'：KD 树实现 KNN 适合数据量大的情况
• 'ball_tree'：球树实现 KNN 适合的数据量很大的情况。
• 'auto'：默认参数，自动选择合适的方法构建模型。
不过当数据较小或比较稀疏时，无论选择哪个最后都会使用 'brute'

leaf_size：如果是选择蛮力实现，那么这个值是可以忽略的，当使用KD树或球树，它就是是停止建子树的叶子节点数量的阈值。默认30，但如果数据量增多这个参数需要增大，否则速度过慢不说，还容易过拟合。
p：和metric结合使用的，当metric参数是"minkowski"的时候，p=1为曼哈顿距离， p=2为欧式距离。默认为p=2。

metric：指定距离度量方法，一般都是使用欧式距离。
• 'euclidean' ：欧式距离
• 'manhattan'：曼哈顿距离
• 'chebyshev'：切比雪夫距离
• 'minkowski'：闵可夫斯基距离，默认参数
6.n_jobs：指定多少个CPU进行运算，默认是-1，也就是全部都算。

利用sklearn里面的手写数据集合做测试，手写数据集合一共有1797个样本，每个样本都是8*8 个像素点，每个点的值为一个0-255的灰度值，可以先运行看看数据情况：

from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_digits
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.naive_bayes import MultinomialNB
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt


# 加载数据
digits = load_digits()
data = digits.data
# 数据探索
print(data.shape)
# 查看第2幅图像
print(digits.images[1])
# 第2幅图像代表的数字含义
print(digits.target[1])
# 将第2幅图像显示出来
plt.gray()
plt.imshow(digits.images[1])
plt.show()

数据展示

最后展示下课中代码，注意这里面在做多项式朴素贝叶斯分类的时候采用的是采用Min-Max规范化，是因为算法不准许为负数。

from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_digits
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.naive_bayes import MultinomialNB
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt


# 加载数据
digits = load_digits()
#这个data可以看成一个二维数组，第一维度为1797个，
#每一个是由一个8*8个像素点的灰度值组成
data = digits.data
# 数据探索
print(data.shape)
# 查看第2幅图像
print(digits.images[1])
# 第2幅图像代表的数字含义
print(digits.target[1])
# 将第2幅图像显示出来
plt.gray()
plt.imshow(digits.images[1])
plt.show()

# 分割数据，将20%的数据作为测试集，其余作为训练集
train_x, test_x, train_y, test_y = train_test_split(data, digits.target, test_size=0.2, random_state=33)
# 采用Z-Score规范化
ss = preprocessing.StandardScaler()
train_ss_x = ss.fit_transform(train_x)
test_ss_x = ss.transform(test_x)


# 创建KNN分类器
knn = KNeighborsClassifier() 
knn.fit(train_ss_x, train_y) 
predict_y = knn.predict(test_ss_x) 
print("KNN准确率: %.4lf" % accuracy_score(test_y, predict_y))



# 创建SVM分类器
svm = SVC()
svm.fit(train_ss_x, train_y)
predict_y=svm.predict(test_ss_x)
print('SVM准确率: %0.4lf' % accuracy_score(test_y, predict_y))
# 采用Min-Max规范化
mm = preprocessing.MinMaxScaler()
train_mm_x = mm.fit_transform(train_x)
test_mm_x = mm.transform(test_x)
# 创建Naive Bayes分类器
mnb = MultinomialNB()
mnb.fit(train_mm_x, train_y) 
predict_y = mnb.predict(test_mm_x) 
print("多项式朴素贝叶斯准确率: %.4lf" % accuracy_score(test_y, predict_y))


# 创建CART决策树分类器
dtc = DecisionTreeClassifier()
dtc.fit(train_mm_x, train_y) 
predict_y = dtc.predict(test_mm_x) 
print("CART决策树准确率: %.4lf" % accuracy_score(test_y, predict_y))

看下结果：

计算结果

近朱者赤近墨者黑的K近邻算法

一. KNN算法原理

二. KNN算法的步骤

三 实战

三实战