KNN算法原理及代码实现

发表于
字数统计: | 阅读时长 ≈

k邻近算法的原理和使用

1.算法原理

1. KNN算法三要素

KNN算法我们主要要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。这三个最终的要素是k值的选取，距离度量的方式和分类决策规则。

  1. 对于分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与k值的选择和距离的度量方式。
  1. 对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。
  • 选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
  • 选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
  • 一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。
  1. 对于距离的度量，我们有很多的距离度量方式，但是最常用的是欧式距离。
2.核心思想

计算待标记的数据样本和数据集中的每个样本的距离，取距离最近的K个样本，待标记的数据样本就由这k个距离最近的样本投票产生

算法原理的伪代码

  • 遍历x_train中的所有样本，计算每个样本与X_test的距离，并吧距离保存在Distance数组中
  • 对Distance数组进行排序，取距离最近的k个点，即为X_knn
  • 对X-knn中统计每个类别的个数，即在class0在X_knn中有几个样本，class1在X_knn中有几个样本…..
  • 待标记的样本类别，就是在X_knn中样本个数最多的那个类别。
3.算法优缺点
  • 优点:准确性高，对异常值和噪声有较高的容忍度
  • 缺点:计算量大，对内存需求大

    2.简单运用(使用k邻近算法进行分类)

    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
    28
    29
    30
    31
    32
    33
    34
    35
    from sklearn.datasets.samples_generator import make_blobs
    from matplotlib import pyplot as plt
    import numpy as np
    #生成数据

    centers=[[-2,2],[2,2],[0,4]]
    X,y=make_blobs(n_samples=600,centers=centers,random_state=0,cluster_std=0.6)

    #画出数据
    plt.figure(figsize=(16,10),dpi=144)
    c=np.array(centers)
    plt.scatter(X[:,0],X[:,1],cmap='cool',c=y,s=100)
    plt.scatter(c[:,0],c[:,1],s=100,marker='^',c='orange')

    #调用训练器来进行分类
    from sklearn.neighbors import KNeighborsClassifier
    k=5
    #训练模型
    clf=KNeighborsClassifier()
    clf.fit(X,y)

    #预测
    X_sample=[[0,2]]
    y_sample=clf.predict(X_sample)
    neighbors=clf.kneighbors(X_sample,return_distance=False)

    #画出该点和临近点
    print(X_sample)
    print(neighbors)
    print(X_sample[0][0])
    plt.scatter(X_sample[0][0],X_sample[0][1],c="red",s=100)

    for i in neighbors[0]:
        #print(X[i][0])
        plt.plot([X[i][0],X_sample[0][0]],[X[i][1],X_sample[0][1]],'k--',linewidth=0.8);

3.示例运用(使用k邻近算法进行回归拟合)

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
28
29
30
31
32
#生成数据集
import numpy as np
n_dots=400
X=5*np.random.rand(n_dots,1)
y=np.cos(X).ravel()#将多为数组将为一维
#print(X)
print("******************")
#print(y)

#添加一些噪声
y=y+0.2*np.random.rand(n_dots)-0.1

#训练模型
from sklearn.neighbors import KNeighborsRegressor
k=5
knn=KNeighborsRegressor(k)
knn.fit(X,y)

#将所有的预测点用吸纳画起来，形成回归曲线
T=np.linspace(0,5,500)[:,np.newaxis]#np.newaxis 在使用和功能上等价于 None，其实就是 None 的一个别名. 
print(T.shape)
y_pred=knn.predict(T)
print("得分为{0}".format(knn.score(X,y)))

#画出拟合曲线
from matplotlib import pyplot as plt
plt.figure(figsize=(16,10),dpi=144)
plt.scatter(X,y,c='g',label='data',s=100)#画出训练样本
plt.plot(T,y_pred,c='k',label='prediction',lw=4)#画出拟合曲线（T为横坐标，y_pred为纵坐标
plt.axis('tight')
plt.title("KNeightborsRessor")
plt.show()

4.实际运用

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
![gg](C:\Users\wuxun\Desktop\gg.PNG)from sklearn import datasets
import numpy as np
from sklearn.model_selection import train_test_split

text=datasets.load_iris()
#print(text)
target=text.target
data=text.data
#print(target)
print("***********")
#print(data)

data.shape
#将样本分为训练集和测试集
X_train,X_test,Y_train,Y_test=train_test_split(data,target,test_size=0.2)

#通过使用普通的k-均值算法，带权重的k-均值算法，指定半斤的k-均值算法对数据进行拟合
from sklearn.neighbors import KNeighborsClassifier,RadiusNeighborsClassifier

#构造三个模型

models=[]
models.append(("KNN",KNeighborsClassifier(n_neighbors=2)))
models.append(("KNN with weight",KNeighborsClassifier(n_neighbors2,weightsh="distance")))
models.append(("Radius Neighbors",RadiusNeighborsClassifier(n_neighbors=2,radius=500.0)))

#分别训练三个模型
results=[]
for name,model in models:
    model.fit(X_train,Y_train)
    results.append((name,model.score(X_test,Y_test)))
for i in range(len(results)):
    print("name: {}: score:{}".format(results[i][0],results[i][1]))

#由于随机测验数据存在的差异，所以我们用KFold计算一般的算法性质
from sklearn.model_selection import KFold
from sklearn.model_selection import cross_val_score
results=[]
for name,model in models:
    kfold=KFold(n_splits=10)#将数据集分成十份，一份作为验证集
    cv_result=cross_val_score(model,data,target,cv=kfold)#函数计算出十次数据集组合而得的模型得分
for i in range(len(results)):
    print("name {} :scor {}".format(results[i][0],results[i][1].mean()))
    
#模型训练及分析
#普通的knn训练模型可能更优，我们使用普通的knn模型训练数据

knn=KNeighborsClassifier(n_neighbors=2)
knn.fit(X_train,Y_train)
train_score=knn.score(X_train,Y_train)
test_score=knn.score(X_test,Y_test)
print("tsin score:{},test score:{}".format(train_score,test_score))

from sklearn.model_selection import ShuffleSplit
#from common.utils import plot_learning_curve

#knn.KNeighborsClassifier(n_neighbors=2)
#cv=ShuffleSplit(n_splits=10,test_size=0.2,random_state=0)

from sklearn.feature_selection import SelectKBest#选择相关性最大的两个特征

selector=SelectKBest(k=2)
X_new=selector.fit_transform(data,target)
X_new[0:5]

#选择最好的两个特征在对三个模型进行检测
results=[]
for name,model in models:
    kfold=KFold(n_splits=10)
    cv_result=cross_val_score(model,X_new,target,cv=kfold)
    results.append((name,cv_result))
for i in range(len(results)):
    print("name:{}; cross val score:{}".format(results[i][0],results[i][1].mean()))
    
    
#画出二维数据
from matplotlib import pyplot as plt
plt.figure(figsize=(10,6),dpi=200)
plt.ylabel("BMI")
plt.xlabel("Glucose")
plt.scatter(X_new[:,0],X_new[:,1],c=target)
#plt.scatter(X_new,target,c='r',s=20,marker='o')