kNN算法

2018-03-13

k近邻法是基本且简单的分类与回归方法。k近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的k个最近邻训练实例点，然后利用这k个训练实例点的类的多数来预测输入实例点的类。

k近邻模型对应于基于训练数据集对特征空间的一个划分。k近邻法中，当训练集、距离度量、k值以及分类决策规则确定后，其结果唯一确定。（相当于这几个要素将特征空间划分为一些子空间，确定子空间里的每个点所属的类。）
三要素：距离度量、k值得选择、分类决策规则。

距离度量

常用的距离度量是$L_p$距离：

当$p=1$时，是曼哈顿距离；
当$p=2$时，是欧氏距离；
当$p=\infty$时，是各个坐标距离的最大值；

k值得选择

k值小时，k近邻模型越复杂，学习的近似误差会小，估计误差会增大，容易发生过拟合；
k值大时，k近邻模型越简单，学习的估计误差会小，近似误差会增大；
所以通常用交叉验证选择最优的k值。

分类决策规则

规则常是多数表决，对应于经验风险最小化。

k近邻的实现：kd树

当训练数据集很大或者维数大时，需要考虑如何快速地搜索k个最近邻点。
kd树是可以对k维空间中的数据进行快速检索的数据结构，其实是二叉树，每个结点对应于k维空间划分中的一个超矩形区域。
kd树优点是可以省去对大部分数据点的搜索，减少计算量。

手写数字识别代码实例

from numpy import *
import operator
from os import listdir

def classify(testData, trainData, trainLabel, k):
    train_len = trainData.shape[0]
    diff = tile(testData, (train_len, 1)) - trainData
    squar = diff**2
    sqDistance = squar.sum(axis = 1)
    distance = sqDistance**0.5
    sort_distance = distance.argsort()#stored index
    classCount = {}
    for i in range(k):
        voteClass = trainLabel[sort_distance[i]]
        classCount[voteClass] = classCount.get(voteClass, 0)+1
        
    sort_classCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
    return sort_classCount[0][0]

def img2vector(filename):
    data = zeros((1,1024))
    fr = open(filename)
    #rowLen = len(fr.readline())
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            data[0, (32*i + j)] = int(lineStr[j])
    
    return data

def handwritingClassTest():
    handLabels = []
    trainDataFileNames = listdir("trainingDigits")
    train_len = len(trainDataFileNames)
    trainData = zeros((train_len,1024))
    for i in range(train_len):
        trainDataName = trainDataFileNames[i]
        trainDataNameFront1 = trainDataName.split('.')[0]
        tainDataNameFront2 = trainDataNameFront1.split('_')[0]
        trainDataClass = int(tainDataNameFront2)
        handLabels.append(trainDataClass)
        trainData[i,:] = img2vector("trainingDigits/%s" % trainDataName)
    
    errorCount = 0
    testDataFileNames = listdir("testDigits")
    test_len = len(testDataFileNames)
    for i in range(test_len):
        testDataName = testDataFileNames[i]
        testDataNameFront = testDataName.split('.')[0]
        testDataClass = int(testDataNameFront.split('_')[0]) 
        testData = img2vector("testDigits/%s" % testDataName)
        
        classifierResult = classify(testData, trainData, handLabels, 3)
        print 'classify : %d,  real label: %d\n' % (classifierResult, testDataClass)
        if (classifierResult != testDataClass):
            errorCount += 1
    
    print 'error count: %d\n' % errorCount
    print 'error rate: %d\n' % (errorCount / test_len)
 
if __name__ == "__main__":
    handwritingClassTest()