python机器学习系列：K近邻算法(KNN)的实现及应用

发表于 | 分类于 ， |
| 字数统计: 2.7k

还是老样子，这篇文章不适合纯粹的小白，仅仅注重实践，基础知识说的比较浅，基本上一笔带过。

我在作者的原代码和数据上进行了一点修改以符合当今的实际情况。

此篇文章将实现K近邻算法的基本原理，以及实现K邻近算法并且应用到实际数据集之中，之后会有一个实战项目。

算法实现

欧几里得原理以及代码实现

欧几里得公式：

实际上很简单，想想求解两点值之间的距离的问题吧…

代码实现：

1
2
3
4
5
6
7
8
from math import sqrt
#数据自制
feature_1 = [1,3]
feature_2 = [2,6]
euclidean_distance = sqrt((variable_2[0]-variable_1[0])**2 + (variable_2[1]-variable_1[1])**2)
print(euclidean_distance)

这里是中文相关一节的地址：https://www.yxgapp.com/video/c8426884-2b56-494f-a274-0aa3105503f1.html

实现KNN

KNN的工作机制(来自志华哥的《机器学习》)：

给定测试样本，基于某种距离度量找出训练集中与其最近的k个训练样本，然后基于这k个“邻居”的信息来进行预测，通常，在分类任务中可使用“投票法”(在本文当中明显就是分类问题)，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

这样就能好理解之后写的算法了，这毕竟不是给纯粹的小白写的。

简单说说下面写的代码的原理：通过原有的数值与新的数值代入欧几里得原理得出各点与新数值的距离，然后对这些数值进行从小到大排序并且选取前面K个数值(即所谓的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
import numpy as np
import matplotlib.pyplot as plt
import warnings
from collections import Counter
#自制数据集
dataset = {'k':[[1,2],[2,3],[3,1]], 'r':[[6,5],[7,7],[8,6]]} #这个字典的key值为何这样命名看到下面就知道了，作为color参数的输入
new_features = [5,7]
def k_nearest_neighbors(data, predict_feature, k=3): #特别说明：k值在sklearn中的模型默认为5
    if len(data) >= k:
        warnings.warn('你这样就没有意义了...笨猪！')
    distances = []
    for group in data:
        for features in data[group]: #这两段代码与for group, features in dateset.items():意义一致
            euclidean_distance = np.linalg.norm(np.array(features)-np.array(predict_feature)) #使用numpy的相关的模块会显得更加的快速以及更加的高级
            distances.append([euclidean_distance, group])
            
    votes = [i[1] for i in sorted(distances)[:k]] #从小到大的排序，选择出现在前面的K个样本作为投票得出的结果
    vote_result = Counter(votes).most_common(1)[0][0]
    
    return vote_result
result = k_nearest_neighbors(dataset, new_features, k=3)
print(result)
plt.style.use('ggplot')
#可通过图表展示出结果信息
[[plt.scatter(ii[0],ii[1], s=20, color=i) for ii in dateset[i]] for i in dateset] #color输出为'r'，可见上面作者命名的含义
result = k_nearest_neighbors(dataset, new_features)
plt.scatter(new_features[0], new_features[1], s=20, color = result) #color输出为'r'，可见上面作者命名的含义
plt.show()

可帮助理解的链接：

看完并且理解了上面的代码之后，你就会发现KNN算法为何对于异常值不敏感了吧，因为异常值太大，得出的距离也很大，所以一般在投票选择排序时就被out了。

展示图表以及运行结果

如图：

这样就一目了然了。

项目实践

这是加州大学的一个用于机器学习数据的仓库，基本上是开放数据给我们使用的。

下载其中的breast-cancer-wisconsin.data，查看特征系数情况查看breast-cancer-wisconsin.names。

因为需要对数据进行一些特征增加的修改，所以我贴上修改后的数据在下，也可查看上面的作者的YouTube教程来进行修改。

也就是添加了特征名而已。

这是一个关于乳腺癌判断的数据集。从breast-cancer-wisconsin.names中可得知缺失的数据由'?'来表示。

  1. Missing attribute values: 16

    There are 16 instances in Groups 1 to 6 that contain a single missing (i.e., unavailable) attribute value, now denoted by “?”.

这样一来就能开始整个项目了。

数据预处理

数据集中的特征意喻：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Attribute Information: (class attribute has been moved to last column)
   #  Attribute                     Domain
   -- -----------------------------------------
   1. Sample code number            id number
   2. Clump Thickness               1 - 10
   3. Uniformity of Cell Size       1 - 10
   4. Uniformity of Cell Shape      1 - 10
   5. Marginal Adhesion             1 - 10
   6. Single Epithelial Cell Size   1 - 10
   7. Bare Nuclei                   1 - 10
   8. Bland Chromatin               1 - 10
   9. Normal Nucleoli               1 - 10
  10. Mitoses                       1 - 10
  11. Class:                        (2 for benign(良性), 4 for malignant(恶性))

因为缺失的数据并不多，并且在我修改了那几个缺失值测试了好几次用于训练之后发现差距基本上可以忽略，所以这里的关于缺失值改为异常值来处理，因为基本上对于模型训练基本上没有什么影响。

1
2
3
4
5
6
7
8
import numpy as np
import pandas as pd
df = pd.read_csv('breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True) #替换异常值为-99999，inplace=True表示文件中也将进行同步更改
#去除不相关的特征列
df.drop(['Id'], 1, inplace=True)

数据量本身也就是那么点…所以数据预处理也就这样了…KNN算法对于异常值不敏感。

模型训练及预测

分割数据集，进行训练，并且制作简易数据集来进行预测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sklearn import preprocessing,neighbors
from sklearn.model_selection import train_test_split
X = np.array(df.drop(['Class'], 1)) #去除标签列，自制数据集
y = np.array(df['Class'])
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
clf = neighbors.KNeighborsClassifier()
clf.fit(X_train, y_train)
accuracy = clf.score(X_test, y_test) #得出准确值
print(accuracy)
#创建数据集来进行简单的预测
example_maasurse = np.array([[4,2,1,1,2,1,2,1,2],[4,2,1,1,2,2,2,2,1]])
example_maasurse = example_maasurse.reshape(len(example_maasurse),-1) #重朔,其中的-1可理解为，只想输出2行的情况下，后面的列我写上-1由numpy自行得出对应相符的数组，有点抽象...其实也就那么回事
prediction = clf.predict(example_maasurse)
print(prediction)

输出如下：

如果还是对于这条代码example_maasurse.reshape(len(example_maasurse),-1)中的-1还是不理解，可参考如下链接或者是官网：

其实也就那么回事…

完整代码

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
import numpy as np
from sklearn import preprocessing,neighbors
from sklearn.model_selection import train_test_split
import pandas as pd
df = pd.read_csv('breast-cancer-wisconsin.data')
df.replace('?',-99999,inplace=True) 
df.drop(['Id'], 1, inplace=True)
X = np.array(df.drop(['Class'], 1)) 
y = np.array(df['Class'])
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
clf = neighbors.KNeighborsClassifier()
clf.fit(X_train, y_train)
accuracy = clf.score(X_test, y_test) 
print(accuracy)
example_maasurse = np.array([[4,2,1,1,2,1,2,1,2],[4,2,1,1,2,2,2,2,1]])
example_maasurse = example_maasurse.reshape(len(example_maasurse),-1)
prediction = clf.predict(example_maasurse)
print(prediction)

用手动实现的KNN训练此数据集

代入以上的实际数据，转换数据类型打乱整体(俗称“洗牌”)的数据集并且分割对应标签制作成可代入上面写的算法中的数据集形式，然后根据计算出的距离结合K的取值得出最终的测试数据集的整体预测标签(计算在训练数据集与测试数据集之间进行)，然后将预测得出的标签与实际的结果进行比较，最终即可得出整体的算法准确性(Accuracy)。

下面是实现的整体代码：

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
import numpy as np
import matplotlib.pyplot as plt
import warnings
from collections import Counter
def k_nearest_neighbors(data, predict_feature, k=3): #特别说明：k值在sklearn中的模型默认为5
    if len(data) >= k:
        warnings.warn('你这样就没有意义了...笨猪！')
    distances = []
    for group in data:
        for features in data[group]: #这两段代码与for group, features in dateset.items():意义一致
            euclidean_distance = np.linalg.norm(np.array(features)-np.array(predict_feature)) #使用numpy的相关的模块会显得更加的快速以及更加的高级
            distances.append([euclidean_distance, group])
            
    votes = [i[1] for i in sorted(distances)[:k]] #从小到大的排序，选择出现在前面的K个样本作为投票得出的结果
    vote_result = Counter(votes).most_common(1)[0][0]
    confidence = Counter(votes).most_common(1)[0][1] / k #在预测的样本中正确预测的比例，但是数据量小，一般不靠谱，所以不采用，当然可写入代码中以便学习
    return vote_result, confidence
df = pd.read_csv('breast-cancer-wisconsin.data')
df.replace('?', -99999, inplace=True)
df.drop(['Id'], 1, inplace=True)
full_data = df.astype(float).values.tolist() #转化为float、列表类型以便下面的随机打乱
random.shuffle(full_data) #随机打乱所有数据,洗牌函数
test_size = 0.2
train_set = {2:[], 4:[]}
test_set = {2:[], 4:[]}
#取训练数据集比例0.8:0.2
train_data = full_data[:-int(test_size*len(full_data))]
test_data = full_data[-int(test_size*len(full_data)):]
#数据分割对应
for i in train_data:
    train_set[i[-1]].append(i[:-1]) #模版套入对应数据即可
for i in test_data:
    test_set[i[-1]].append(i[:-1])
    
correct = 0
total = 0
for group in test_set:
    for data in test_set[group]: #亦可理解为for group, data in test_set.items():
        vote, confidence = k_nearest_neighbors(train_set, data, k=5) 
        if group == vote:
            correct += 1 #若是准确预测了则加1
        total += 1
print('Accuracy:', correct/total)

铺助理解：Python3 shuffle() 函数

运行可得预测准确性：

其中有必要说明一下：Accuracy与confidence的关系，就相当于查准率(Precision)(预测正确的样本数与总体使用样本数的比例)和查全率(Recall)(预测正确样本数与全部使用数据数量的比例)的关系。另外补充一点关于平常常用的score参数的计算公式：

这些知识都是基础知识，可在网友整理的吴恩达老师的机器学习笔记中找到，也可完整的学习相关的知识，吴恩达老师的必看啊。

最后

以上的算法没有完全的实现，仅仅是实现基础的构想，还需要改进的地方有很多，比如数据量大了一点之后，需要用到的多线程等。

另外，KNN算法的优缺点值得去了解，上面我也说过一点，比如数据量大了之后它的效率会受到影响，但是它对于异常值处理的都很好，基本上不受异常值之类的影响等，自行翻书了解去吧。

---------------本文终---------------

文章作者:刘俊

最后更新:2019年01月02日 - 14:01

许可协议: 转载请保留原文链接及作者。

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多