博客

k-近邻算法实现手写体识别

k-近邻算法采用测量不同特征值之间的距离解决分类问题

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

K 近邻算法适用数据范围为：数值型和标称型。

K 近邻算法的工作原理是：

1.存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。

2.输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 K 近邻算法中 k 的出处，通常 k 是不大于 20 的整数。最后，选择 k 个最相似数据中出现次数最多的分类，作为新数据的分类。

K近邻算法的一般流程：

1、收集数据：可以使用任何方法。

2、准备数据：距离计算所需要的数值，最好是结构化的数据格式。

3、分析数据：可以使用任何方法。

4、训练算法：此步骤不适用于 K 近邻算法。

5、测试算法：计算错误率。

6、使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K 近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

准备数据

trainingDigits 存放训练集 testDigits 存放测试集 样本为文本格式。

用img2vector()将图像有32

32 的二进制图像矩阵转换为1

1024的向量

def img2vector(filename):
# 创建向量格式
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect
   

k-近邻算法实现过程：

对未知类别的数据集中的每个点一次执行一下操作：

1、计算已知类别数据集中的点与当前点之间的距离；

2、按照距离递增次序排序；

3、选取与当前点距离最小的 k 个点；

4、确定前 k 个点所在类别的出现频率；

5、返回前 k 个点出现频率最高的类别作为当前点的预测分类。

def classify0(inX, dataSet, labels, k):
    """
    -inX ：输入变量
    -dataSet: 训练样本集
    -labels: 标签向量
    -k：选择最近邻居的数目
    """
    # 获取样本数据数量
    dataSetSize = dataSet.shape[0]
    
    # 矩阵运算，计算测试数据与每个样本数据对应数据项的差值
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    
    # sqDistances 上一步骤结果平方和
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
            
    # 取平方根，得到距离向量
    distances = sqDistances**0.5
    
    # 按照距离从低到高排序
    sortedDisIndicies = distances.argsort()
    classCount = {}
    
    # 依次取出最近的样本数据
    for i in range(k):
         # 记录该样本数据所属的类别
        voteIlabel = labels[sortedDisIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        
    # 对类别出现的频次进行排序，从高到低
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    
    # 返回出现频次最高的类别
    return sortedClassCount[0][0]

测试算法：

1.读取训练集数据，从文件名读取样本标签

2.读取测试锯数据，从文件名读取样本标签

3.测试集、训练集输入分类器测试得到分类结果

4计算误差，错误率。

def handwritingClassTest():
     # 样本数据的类标签列表
    hwLabels = []
    
    # 样本数据文件列表
    trainingFileList = listdir('trainingDigits')
    
    #样本数量
    m= len(trainingFileList)
    
    # 初始化样本数据矩阵（M*1024
    trainingMat = zeros((m,1024))
    
    # 依次读取所有样本数据到数据矩阵
    for i in range(m):
        
         # 提取文件名中的数字
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        
        # 将样本数据存入矩阵
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    
    # 循环读取测试数据
    testFileList = listdir('testDigits')
    errorCount = 0.0
    
    mTest = len(testFileList)
    
     # 循环测试每个测试数据文件
    for i in range(mTest):
        
         # 提取文件名中的数字
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        
        # 提取数据向量
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        
        # 对数据文件进行分类
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        
        # 打印 K 近邻算法分类结果和真实的分类
        print ("the classifier came back with: %d the real answer is: %d"  % (classifierResult,classNumStr))
        
        # 判断K 近邻算法结果是否准确
        if classifierResult != classNumStr : errorCount += 1.0
    
    # 打印错误率
    print("total number of errors is: %d"  %errorCount)
    print("total error rate is: %f" %(errorCount/float(mTest)))

handwritingClassTest()

存在问题

执行效率不高，因为为每个测试向量做2000次距离计算，，每个距离计算包括了1024个维度浮点运算，总计要执行900次，辞海还需为测试向量准备2MB的存储空间。

k决策树是k-近邻算法的优化版