机器学习KNN算法学习笔记

2017-05-19 本文已影响0人曹俊_413f

基本概念

KNN是分类算法。

数据类型：数值型和标称型。

工作原理

存在一个训练样本集，并且训练样本集中每个数据都存在标签，即知道训练样本集中每一条数据与所属分类对应关系。输入没有标签的新数据后，与训练样本集中数据对应的特征做比较，然后提取样本集中特征最相似数据（最临近，用距离公式，距离最近）的分类标签。一般来说，我们只取训练样本集中前k个最相似的数据，这就是k的出处。通常k是不大于20的整数。

距离公式

49b476ef-7c62-4da0-8648-5a1c5715d4ab

多特征时，如(1,0,0,1)和(7, 6, 9, 4)

d3b42a96-1c5a-4eac-83cb-d4041a242464

分类算法

from numpy import *
import operator
from os import listdir

def classify0(inX, dataSet, labels, k):
    # inX为待分类数据
    # dataSet为训练数据集
    # labels对应dataSet每一行数据的标签(类型)

    # 有多少行数据 shape反回一个元组。(行, 列)
    dataSetSize = dataSet.shape[0] 
    
    # tile(inX, (dataSetSize,1)) 创建一个numpy的array，dataSetSize行，每行数据是inX
    # - dataSet 矩阵减法 m*n矩阵A - m*n矩阵B
    diffMat = tile(inX, (dataSetSize,1)) - dataSet 
    
    # 矩阵的每个值平方
    sqDiffMat = diffMat**2

    # 横向求和，得到一个一维数组，每个值都是和
    sqDistances = sqDiffMat.sum(axis=1)
    
    # 数组中每个值开根
    distances = sqDistances**0.5

    # 得到排序后的下标数组
    sortedDistIndicies = distances.argsort()

    classCount={}
    # 只取前k个        
    for i in range(k):
        # 找到下标对应的标签
        voteIlabel = labels[sortedDistIndicies[i]]
        # 如果找到相同标签利用map来计数
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    # 排序加反转
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    print sortedClassCount
    # 把计数最大的值所对应的标签返回出去
    return sortedClassCount[0][0]

数据归一化

如果某个特征值数量级特别大，比如A特征是5位数，而其他特征是个位数。那么就会发现A特征的值大大会影响最终结果。所以需要把每个特征值都归到0-1这个范围。

数据归一化算法

9061c50-3104-11e7-8aca-e882fa09a8a8

def autoNorm(dataSet):
    # 每一列最小值
    minVals = dataSet.min(0)
    # 每一列最大值
    maxVals = dataSet.max(0)
    # 每一列的差
    ranges = maxVals - minVals
    # 复制矩阵 dataSet的行，列。值都是0
    normDataSet = zeros(shape(dataSet))
    # 得到多少行
    m = dataSet.shape[0]

    # tile(minVals, (m,1)) 创建datSet的行列的矩阵，每一个值都是minVals。
    # dataSet - 矩阵相减
    normDataSet = dataSet - tile(minVals, (m,1)) 

    # tile(ranges, (m,1)) 创建datSet的行列的矩阵，每一个值都是ranges。
    # 并非矩阵除法，而是对应位置的值相除
    normDataSet = normDataSet / tile(ranges, (m,1))
    return normDataSet, ranges, minVals

实际使用

def datingClassTest():
    # 预留出10%来做测试数据验证准确率
    hoRatio = 0.10
    # 读取数据和标签
    datingDataMat,datingLabels = file2matrix('Ch02/datingTestSet.txt')       #load data setfrom file
    # 把数据归一化处理
    normMat, ranges, minVals = autoNorm(datingDataMat)
    # 取到数据有多少行
    m = normMat.shape[0]
    # 取出测试数据的长度
    numTestVecs = int(m*hoRatio)
    # 错误计数
    errorCount = 0.0

    for i in range(numTestVecs):
        # normMat[i,:] 取出第i行的 所有数据
        # normMat[numTestVecs:m,:] 取出numTestVecs之后到m的每行数据
        # datingLabels[numTestVecs:m] 取出numTestVecs之后到m的每行的标签
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
        # 如果结果不一致，则错误+1
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    # 最后打印出错误率和错误数
    print "the total error rate is: %f" % (errorCount/float(numTestVecs))
    print errorCount

优点

分类算法中最简单最有效的算法

缺点

必须保存全部训练集，如果训练集样本很大会使用大量存储空间
计算距离时可能非常耗时
无法给出任何数据的基础结构信息，无法得知平均实例样本和典型实例样本具有什么特征