kNN算法的python实现

发表于 | | 阅读次数: |

一、概述

简单的说KNN是通过测量某样本与已知样本的距离来进行分类的。
工作原理如下：
首先我们有一个带标注的训练样本集。当我们输入一个新的样本，将新样本的每个特征与训练样本集中数据的对应特征进行比较。选择k个在坐标系中与新样本最接近的数据，这些数据中出现次数最多的分类即可看作新数据的分类。

通常k<=20

如我们要下图绿色图形的分类
image_1bhu8q6441tqi7lg14taffa1cq9.png-70.6kB
如果k=3 则被分类为三角形

如果k=5 则被分类为正方形

所以knn算法的结果很大程度上取决于k的选择

knn算法的描述：

  • 列表项
  • 计算测试数据与各个训练集之间的距离
  • 按照距离的递增关系进行排序
  • 选取距离最小的k个点
  • 确定前k个点所在类别的频率
  • 返回前k个点出现频率最高的类别作为测试数据的分类

特点：

优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用范围：数值型和标称型

二、python实现

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
# -*- coding: utf-8 -*-
from numpy import *
import operator

def creatDataset():
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels=['A','A','B','B']
    return group,labels

#inX:分类向量
#dataSet:测试数据集

def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]#shape返回行列数,shape[0]返回行数
    diffmat=tile(inX,(dataSetSize,1))-dataSet
    seqdiffmat=diffmat**2
    seqdistance=sum(seqdiffmat,axis=1)##axis=1按行相加 anxis=0按列相加
    distances=seqdistance**0.5
    sortedDistindex=argsort(distances)#从大到小排序，返回下标

    classCount={}

    for i in range(k):
        votelabel=labels[sortedDistindex[i]]
        classCount[votelabel]=classCount.get(votelabel,0)+1##相当于classcount+=1 但该没有数据时用get可返回0
    maxCount=0
    for key,value in classCount.items():
        if value>maxCount:
            maxCount=value
            classes=key
        return classes

dataSet,labels=creatDataset()
inX=array([1.1,0.3])
K=3
output=classify0(inX,dataSet,labels,K)
print('测试数据为：',inX,'分类结果为：',output)

三、总结

这是《机器学习实战》书中的第一个算法，实现起来比较简单。书中有几个实战的内容就不详细写了，代码都已放在github上。
这个算法中用到了Numpy和Matplotlib库，对这些库的使用还需要继续学习（会新开一篇写一下常用的用法）