临近取样（KNN）算法基本原理&sklearn实现

1 KNN定义

KNN可以说是最简单的分类算法之一，同时，它也是最常用的分类算法之一，KNN算法是有监督学习中的分类算法，它看起来和Kmeans有点像（Kmeans是无监督学习算法），但却是有本质区别的。

KNN的全称是K Nearest Neighbors，意思K个最近邻居。

KNN的原理就是当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。

KNN核心功能是解决有监督的【分类问题】。
KNN能够快速高效地解决建立在特殊数据集上的预测分类问题，但其不产生模型，因此算法准确性并不具备强可推广性。

2 k近邻法三要素

1) 距离度量
     常用的距离度量是 ### 欧氏距离 ### 及更一般的 ### pL距离 ###
2) k值的选择
     k值小时，k近邻模型更复杂，容易发生过拟合；
     k值大时，k近邻模型更简单，又容易欠拟合，
     因此k值得选择会对分类结果产生重大影响。
     k值的选择反映了对近似误差与估计误差之间的权衡，通常由 ### 交叉验证 ### 选择最优的k。
3）分类决策规则
     分类决策规则往往是 ### 多数表决 ### ，即由输入实例的k个邻近输入实例中的多数类决定输入实例的类。KNN使用的分类决策规则是多数表决，如果损失函数为0-1损失函数，那么要使误分类率最小即使经验风险最小，
1
2
3
4
5
6
7
8
9

3.距离度量

KNN算法最简单粗暴的就是【将预测点与所有点距离进行计算】，然后保存并排序，选出前面K个值看看哪些类别比较多。

1）距离计算公式
2) p=1 曼哈顿距离
p = 2 欧氏距离
p = ∞ 切比雪夫距离
一般采用二维欧式距离

4. 交差验证选择K值

在许多实际应用中数据是不充足的。为了选择好的模型，可以采用交叉验证方法。
交叉验证的基本想法: 是 重复地使用数据
把给定的数据进行切分，将切分的数据组合为训练集与测试集，在此基础上反复进行训 练测试以及模型的选择。 在实现过程中将采用sklearn.model_selection.cross_val_score() 实现交叉验证选取k值。

5. sklearn api

from sklearn import neighbors

from sklearn import neighbors

# 建立模型
model = neighbors.KNeighborsClassifier(n_neighbors=,weights='xx',algorithm='xxx', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=1)
'''
    @param n_neighbors: 指定kNN的k值
    @param weights:  
    'uniform': 本节点的所有邻居节点的投票权重都相等
    'distance': 本节点的所有邻居节点的投票权重与距离成反比
    @param algorithm:  惩罚项系数的倒数，越大，正则化项越小
    'ball_tree': BallTree算法
    'kd_tree': kd树算法
    'brute': 暴力搜索算法
    'auto': 自动决定适合的算法
    @param leaf_size:  指定ball_tree或kd_tree的叶节点规模。他影响树的构建和查询速度
    @param p:  p=1:曼哈顿距离; p=2:欧式距离
    @param metric:  指定距离度量，默认为'minkowski'距离
    @param n_jobs: 任务并行时指定使用的CPU数，-1表示使用所有可用的CPU

    @method fit(X,y): 训练模型
    @method predict(X): 预测
    @method score(X,y): 计算在(X,y)上的预测的准确率
    @method predict_proba(X): 返回X预测为各类别的概率
    @method kneighbors(X, n_neighbors, return_distance): 返回样本点的k近邻点。如果return_distance=True，则也会返回这些点的距离
    @method kneighbors_graph(X, n_neighbors, mode): 返回样本点的连接图
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6 实例

1）导入sklearn 包
from sklearn.neighbors import KNeighborsClassifier
2）准备数据，特征集&标签集
3）实例化KNN模型
knn = KNeighborsClassifier(n_neighbors=5)
4）KNN模型训练（拟合）
knn.fit(x_train, y_train)
knn.score(x_train, y_train)
5）预测新的特征集
knn.predict(X_new)

from sklearn import datasets  # 导入数据模块
from sklearn.model_selection import train_test_split  # 导入切分训练集、测试集模块
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

# 加载 iris 的数据，把属性存在 X，类别标签存在 y：
iris = datasets.load_iris()
iris_x = iris.data
iris_y = iris.target

# 观察一下数据集，X 有四个属性，y 有 0，1，2 三类：
print(iris_x)
print(iris_y)

# 把数据集分为训练集和测试集，其中 test_size=0.3，即测试集占总数据的 30%：
x_train, x_test, y_train, y_test = train_test_split(iris_x, iris_y, test_size=0.3)
print(y_train)
print(y_test)

# 训练+预测
# 实例化KNN模型，不传参数时，n_neighbors默认值为5
knn = KNeighborsClassifier(n_neighbors=5)  

knn.fit(x_train, y_train)  # 放入训练数据进行训练

print(knn.predict(x_test))  # 打印预测内容
print(y_test)  # 实际标签
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27