K近邻算法

---

K-近邻算法（KNN）是分类数据最简单最有效的算法。

核心思想

采用不同特征值之间的距离方法进行分类
首先：

我们有一个样本集（也称训练样本集），样本中的每个数据都存在标签，即样本集中每一个数据对应与所属分类的对应关系。

之后：

输入没有标签的新数据时，将新数据的每个特征与样本集中数据的特征进行比较，（一般是计算欧氏距离）然后算法提取样本集中特征最相近数据（最近邻）的分类标签

附：一本只选择样本数据集中前K个最相近的数据，这就是k近邻中的k。k一般不超过20的整数

KNN算法的过程为:

• 选择一种距离计算方式, 通过数据所有的特征计算新数据与已知类别数据集中的数据点的距离
• 按照距离递增次序进行排序，选取与当前距离最小的k个点
• 对于离散分类，返回k个点出现频率最多的类别作预测分类；对于回归则返回k个点的加权值作为预测值

kNN的优缺点

优点：简单有效
缺点：
一是必须有接近实际数据的训练样本数据，且要保存全部数据集，占用存储空间且计算耗时；
二是无法给出任何数据的急促结构信息，无法知晓平均实例样本和典型实例样本具有什么特征。使用概率测量方法可以解决这个问题

算法实例

创建kNN.py
(1)创建数据集

#创造数据集
def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

有四个数据，其标签分别为（A,A,B,B）
(2) 构照kNN分类器

#第一个kNN分类器  
#inX-测试数据 dataSet-样本数据  labels-标签 k-邻近的k个样本
def classify0(inX,dataSet,labels,k):  
    dataSetSize = dataSet.shape[0]  #dataSet.shape[0]是第一维的数目    
    '''
    计算与所有点的距离，并进行排序
    '''
    diffMat = tile(inX,(dataSetSize,1)) - dataSet #要分类的新数据与原始数据做差 
    sqDiffMat = diffMat**2  #求差的平方  
    sqDistance = sqDiffMat.sum(axis=1)  #求差的平方的和    
    distances = sqDistance**0.5 #求标准差   
    sortDistIndicies = distances.argsort() #距离排序    
    classCount = {}  #定义元字典   
    '''
    遍历前k个元素,选择距离最小的k个点
    '''
    for i in range(k):  
        voteIlabel = labels[sortDistIndicies[i]]  #获得前k个元素的标签 
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#计算前k个数据标签出现的次数   
    '''
    排序
    '''
    sortedClassCount =sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True) #对得到的标签字典按降序排列   
    return sortedClassCount[0][0] #返回出现次数最多的标签  

结果测试

group, labels = kNN.createDataSet( )
kNN.classfy0([0,0],group,labels,3)

结果为B

(3)读取文本文件中的数据

def file2matrix(filename):

    fr = open(filename)# 打开文件
    numberOfLines = len(fr.readlines()) # 计算文本文件的行数
    returnMat = zeros((numberOfLines,3))# 创建返回的数据矩阵
    classLabelVector = []# 创建类标签
    fr = open(filename) # 打开文件
    index = 0 # 定义索引
    # 读取文件的每一行并处理
    for line in fr.readlines():
        line = line.strip()# 去除行的尾部的换行符
        listFromLine = line.split('\t') # 将一行数据按空进行分割
        returnMat[index,:] = listFromLine[0:3] # 0：3列为数据集的数据
        classLabelVector.append((listFromLine[-1])) # 最后一列为数据的分类标签
        index += 1# 索引加1
   
    return returnMat,classLabelVector # 返回数据集和对应的类标签

(4)显示散点图

import matplotlib.pyplot as plt
fig = plt.figure()
ax1 = fig.add_subplot(111)
datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')
#ax.scatter(datingDataMat[:,1], datingDataMat[:,2])

ax1.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))

ax.axis([-2, 25, -0.2, 2.0])
plt.xlabel(u"玩游戏视频所耗时间百分比")
plt.ylabel(u"每周消费的冰淇淋公升数")
plt.show()

(5)归一化数值
为了防止特征值数量的差异对预测结果的影响(比如计算距离，量值较大的特征值影响肯定很大)，我们将所有的特征值都归一化到[0,1]

def autoNorm(dataSet):
    minVals = dataSet.min(0) # 求数据矩阵每一列的最小值
    maxVals = dataSet.max(0)# 求数据矩阵每一列的最大值
    ranges = maxVals - minVals# 求数据矩阵每一列的最大最小值差值
    #normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0] # 返回数据矩阵第一维的数目
    normDataSet = dataSet - tile(minVals, (m, 1)) # 求矩阵每一列减去该列最小值，得出差值
    normDataSet = normDataSet / tile(ranges, (m, 1)) # 用求的差值除以最大最小值差值，即数据的变化范围，即归一化
    return normDataSet, ranges, minVals # 返回归一化后的数据，最大最小值差值，最小值

附：numpy函数小结

#coding=utf-8
__author__ = 'Administrator'
from numpy import *

a = array([[0, 1, 0], [1, 1, 2]])
print a

aSize = a.shape[0] #可以认为是输出列数
print aSize

b = arange(7, dtype=uint16) #dtype为数据类型对象
print b

'''
tile
将数组a重复n次
'''
c = array([0, 1])
d = tile(c, (3, 1))
print d

c = zeros((3, 1), dtype=int)
print c

输出结果

[[0 1 0]
[1 1 2]]
2
[0 1 2 3 4 5 6]
[[0 1]
[0 1]
[0 1]]
[[0]
[0]
[0]]

参考文献：

http://www.aichengxu.com/yejie/512129.htm
http://blog.csdn.net/quincuntial/article/details/50471423
http://blog.csdn.net/suipingsp/article/details/41964713