机器学习实战 - 分类-2 k近邻算法

机器学习入门资料

---

1.1 k-近邻算法概述

k-近邻算法采用测量不同特征值之间的距离方法进行分类。

其优点在于：精度高、对异常值不敏感、无数据输入假定。
其缺点在于：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型

工作原理：

1. 需要存在一个训练样本集，已知每个数据与所属分类之间的对应关系。
2. 输入新数据，比较样本集中数据和新数据的特征，提取样本集中特征最相似数据（最近邻）的分类标签。
3. 一般取前k个最相似的数据，k不大于20的整数。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

1.1.1准备，使用Python导入数据

from numpy import *
import operator
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
\\Python Shell
import kNN
group，labels=kNN.createDataSet()

1.1.2实施kNN分类算法

伪代码：
对未知类别属性的数据集中的每个点依次执行以下操作：
（1）计算已知类别数据集中的点与当前点之间的距离。
（2）按照距离递增的次序进行排序
（3）选取与当前点距离最小的k个点
（4）确定前k个点所在类别的出现频率
（5）返回前k个点出现频率最高的类别当做当前点的预测分类。

def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]//获得样本集的样本个数
    diffMat = tile(inX,(dataSetSize,1))-dataSet//tile(A,B)是重复A，B次
    sqDiffMat=diffMat**2//平方
    sqDistances=sqDiffMat.sum(axis=1)//求和axis=0是普通相加，axis=1是行相加
    distances=sqDistances**0.5//开方
    sortedDistIndicies=distances.argsort()
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1//排序
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)//True是降序，False是升序
    return sortedClassCount[0][0]

1.1.3如何测试分类器

认识：分类器并不会百分百正确，分类器的性能受到多种因素的影响，如分类器设置和数据集等等。
完美分类器：错误率为0
最差分类器：错误率是1.0
用错误率来评估分类器在某个数据集上的执行效果

$$错误率=\frac{分类器给出的错误结果次数}{测试执行的总数}$$

1.2示例：使用k-近邻算法改进约会网站的配对效果

（1）收集数据：提供文本文件
（2）准备数据：使用Python解析文本文件
（3）分析数据：使用Matplotlib画二维扩散图
（4）训练数据：此步骤不适用k-近邻算法
（5）测试算法：使用海伦提供的部分数据作为测试样本
（6）使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

1.2.1准备数据：从文本文件中解析数据

1000行，datingTestSet2.txt

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰淇淋公升数

转换格式：
- 输入为文件名字符串
- 输出为训练样本矩阵和类标签向量

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()//读取文件
    numberOfLines = len(arrayOLines)//得到文件行数
    returnMat = zeros((numberOfLines,3))//生成零填充矩阵
    classLabelVector = []//空向量
    index = 0
    for line in arrayOLines:
        line = line.strip()//截取所有的回车字符
        listFromLine = line.split('\t')//使用tab字符\t将上一步得到的整行数据分割成一个元素列表
        returnMat[index,:] = listFromLine[0:3]//取前3个元素存储为特征矩阵中
        classLabelVector.append(int(listFromLine[-1]))//Python语言可以使用索引值-1表示列表中最后一列元素。
        index += 1
    return returnMat,classLabelVector
//Python Shell
import kNN
datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')

1.2.2分析数据：使用Matplotlib创建散点图

使用centos7 安装 matplotlib的最便捷办法
http://blog.csdn.net/vickyrocker1/article/details/49070733

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2])//比较矩阵的第二列和第三列数据
plt.show()

没有样本标签的约会数据散点图
scatter函数支持个性化标记散点图上的点。利用颜色及尺寸标识了数据点的属性类别，可以看到数据点所属于三个样本分类的区域轮廓

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

带有样本分类标签的约会数据散点图

前两个特征对比的约会数据散点图

1.2.3准备数据：归一化数值

如果不归一化数值就会发生：
当某个特征值的范围远远大于其他特征值范围时，该特征值对计算结果的影响远大于其他特征值对计算结果的影响。
常采用将取值范围处理为0到1或者-1到1之间

$$newValue=\frac{oldValue-min}{ma-min}$$

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))//oldValue-min
    normDataSet = normDataSet/tile(ranges,(m,1))//特征值相除，这不是矩阵除法
    return normDataSet,ranges,minVals

在numpy中矩阵除法为：

linalg.solve(matA,matB)

1.2.4测试算法：作为完整程序验证分类器

def datingClassTest():
    hoRatio = 0.10//校验样本
    datingDataMat,datingLabels = file2matrix('datingTestSet.txt')//数据格式转换
    normMat,ranges,minVals = autoNorm(datingDataMat)//归一化
    m = normMat.shape[0]//获取行数
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0//计算误差
    for i in range(numTestVecs):
        calssifierResult = 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])
        if(classifierResult !=datingLabels[i]):    errorCount += 1.0
    print "the total error rate is: %f" % (errorCount/float(numTestVecs))

1.2.5 使用算法：构建完整可用系统

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTat = float(raw_input("percentage of time spent playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))
    iceCream = float(raw_input("liters of ice cream consumed per year?"))
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    inArr = array([ffmiles,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
    print "You will probably like this person: ",resultList[classifierResult - 1]