Day 20 K-近邻演算法(KNN)

介绍完决策树和随机森林後，今天来介绍的是 K-近邻演算法(k-nearest neighbor classification)，简称为 KNN 。而它的判断逻辑其实也相当简单，就是物以类聚。

什麽意思呢？因为它的判断逻辑就是：
就是假设你的邻居都是有钱人，那麽你有十之八九也是有钱人。

所以它的运作原理就是先找出距离最近的 K 个邻居，然後再去分别察看这些邻居的类别，最後再决定自身的类别。

举个例子：

以上图为例，测试样本为绿色圆型。
如果 K=3 （实线圆圈），测试样本会被归类为红色三角形。
而如果 K=5 （虚线圆圈），测试样本会被归类为蓝色正方形。

那麽问题来了，我们该如何决定K值？如果K为偶数的话又该怎麽办呢？

K 值该如何决定？如果是偶数的话该怎麽办？

如果 K 太大的话，可能会造成欠拟合(underfitting)，准确率过低；
如果 K 太小的话，可能会造成过度拟合(Overfitting)，在测试集内准确率高，但是拿出去做验证时就成效不加。

由於 KNN 分类对 K 值相当敏感，不同的值有可能带来不同的结果。在实际中，一般采用交叉验证（一部分样本做训练集，一部分做测试集）或者依靠经验的方法来选取 K 值。K 值一开始通常都会取一个比较小的数值，之後再不断来调整 K 的大小直到分类表现达到最佳即可。

通常 K 值一般都会设为奇数。有一个经验规则是：K 一般低於训练样本数的平方根。而我们在选择 K值的时候，通常都会尽量去避免采用偶数的情况。

那如果 K 真的是偶数的话该怎麽办？还有一种用加权来解决的方法：
给予距离较近的分类较高的权重，最後由加权後最高的分类胜出。

KNN 的优点与缺点：

优点：

1. 简单且容易理解，易於实现且无需训练
2. 精度高、对异常值不敏感
3. 适合於多分类问题

缺点：

1. 时间复杂度高、空间复杂度高、计算量大，记忆体开销也大
2. 可解释性较差，无法给出决策树那样的规则
3. 当样本不平衡时，可能导致特定分类占大多数

实作

透过 iris 资料集，测试其分类的准确率：

from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split

iris=datasets.load_iris()
X=iris.data
y=iris.target

# x是花萼与花瓣的长度、宽度的原始资料
# y是将花分类之後的正确答案

X_train, X_test, y_train, y_test = train_test_split(X, y,test_size=0.3,random_state=1)
clf=KNeighborsClassifier(n_neighbors=3,p=2,weights='distance',algorithm='brute')
clf.fit(X_train,y_train)

# n_neighbors: 要取几个邻居(尽量设置奇数)
# p: 选择距离的计算方式
# weights: 投票方式为距离等权重或加权
# algorithm:演算法的选择 (计算效率的考虑)

print(clf.score(X_test,y_test))  # 印出准确度分数

## ===============以下为找出 K 的最佳值并秀出来
# accuracy = []
# for k in range(1, 100):
#     knn = KNeighborsClassifier(n_neighbors=k)
#     knn.fit(X_train, y_train)
#     y_pred = knn.predict(X_test)
#     accuracy.append(metrics.accuracy_score(y_test, y_pred))

# k_range = range(1,100)
# plt.plot(k_range, accuracy)
# plt.show()