Python与机器学习 K近邻算法及实现

Reply Share

通过计算向量间的距离衡量相似度来实现分类，就是k-NN(k-Nearest Neighbor)算法，一种基于向量间相似度的分类算法。

Python与机器学习 K近邻算法及实现

一、算法原理

k-最近邻（k-Nearest Neighbor）算法是一种较简单的机器学习算法。它采用测量不同特征值之间的距离方法进行分类。它的基本思想如下：如果一个样本在特征空间中的k个最近邻的样本中的大多数都属于某一个类别，则该样本也属于这个类别。
算法流程：
第一阶段：确定k值（最近邻居的个数），一般为一个奇数。
第二阶段：确定距离度量公式，文本分类一般使用 余弦夹角 进行度量。
第三阶段：统计k个样本点中各个类别的数量，根据k各样本中数量最多的样本的类别确定输入数据的类别。

二、算法评估

优点：
1.简单，易于理解，无需估计参数，无需训练；
2.适合对稀有事件进行分类；
3.特别适合于多分类问题，在此领域k-NN比SVM表现要好。
缺点：
1.样本不平衡时，可能会影响分类结果；
2.计算量相对较大，原因是对每一个样本，都要计算它到全体样本的距离；
3.可理解性差，无法给出类似于决策树那样的规则。

三、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
#第一阶段：导入所需的库，进行数据的初始化。

import sys
import os
from numpy import *
import numpy as np 
import operator
from Nbayes_lib import *

#配准UTF-8输出环境
reload(sys)
sys.setdefaultencoding('utf-8')

k=3   

#第二阶段：实现夹角余弦的距离公式
def cosdist(vector1,voctor2):
    return dot(vector1,voctor2)/(linalg.norm(vector1)*linalg.norm(voctor2))

#第三阶段：kNN实现分类器
#测试集：testdata; 训练集：trainSet; 类别标签：listClasses; k：k个近邻数
def classify(testdata,trainSet,listClasses,k):
    dataSetSize=trainSet.shape[0]   #样本集的行数
    distances=array(zeros(dataSetSize))
    for indx in xrange(dataSetSize):   #计算测试集与训练集之间的距离：余弦夹角
        distances[indx]=cosdist(testdata,trainSet[indx])
    sortedDistIndicies=argsort(-distances)
    classCount={}
    for i in range(k):     #获取角度最小的前k项作为参考项
        #按排序顺序返回样本集对应的类别标签
        voteIkabel=listClasses[sortedDistIndicies[i]]
        clssCount[voteIkabel]=classCount.get(voteIkabel,0)+1
    #对分类字典按value排序
    sorted(data.iteritems(),key=operator.itemgetter(1),reverse=True)
    #该句按字典值排序的固定用法
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

四、改进策略

k-NN算法的改进主要分为分类效率和分类效果两个方面：
分类效率： 事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
分类效果： 采用权值的方法（和该样本距离小的邻居权值大）来改进该算法，由于不同分类的文件本身有数量上差异，因此也可以选取不同数目的最近邻居，来参考分类。

五、相关工具箱

MATLAB：MATLAN 2016版集成了机器学习和深度学习相关的工具箱，其中DeepLearnToolbox-master中包含k-N等多种算法；
Python: scikit-learn 库中有该函数的实现
C++:CSDN 上有C++版的代码实现
R语言：>http://blog.csdn.net/liulewei/article/details/8288412

1