机器学习实战一（K-邻近算法（KNN））

一、概述

1. 原理：

工作机制：给定测试样本，基于某种距离度量找出训练集中的与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测.
通常k是不大于20的整数

2. 优缺点

优点：精度高、对异常值不敏感、无数据输入假定
缺点：
- 计算复杂度高、空间复杂度高，占用存储空间
- 无法给出数据的内在含义
适用数据范围：数值型和标称型

3. 懒惰算法：

此类学习技术在训练阶段仅仅把样本保存起来
==训练开支为零==，待收到测试样本后再进行处理

二、算法流程

收集数据
准备数据
分析数据
训练算法（不适合KNN算法，因为K是“懒惰算法”的著名代表）
测试算法
使用算法

三、算法框架

1. classify0()函数的4个输入参数：

inX：用于分类的输入向量
dataSet：用于输入的训练样本集
labels：标签向量
k：参数k用于选择最佳邻居的数目

2. 使用欧氏距离公式

计算两个向量点xA和xB之间的距离
计算存在4个特征值的数据集的距离

3. 在约会网站上使用算法

海伦用三个属性来测试自己对于约会对象的喜爱程度
每年的飞行里程数
玩视频游戏所耗时间百分比
每周消费的冰激凌公升数
她积攒了一些数据，该数据保存在datingTestSet.txt中，共1000行。
准备数据

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

算法

def classify0(inX,dataSet,labels,k):
        #训练数据集的行数
        dataSetSize=dataSet.shape[0]
        #计算距离
        #这里要说一下tile()函数，以后我们还会多次用到它
        #tile(A,B)表示对A重复B次，B可以是int型也可以是数组形式
        #如果B是int，表示在行方向上重复A，B次，列方向默认为1
        #如果B是数组形式，tile(A,(B1,B2))表示在行方向上重复B1次，列方向重复B2次
        diffMat=tile(inX,(dataSetSize,1))-dataSet
        print(diffMat)
        sqDiffMat=diffMat**2
        print(sqDiffMat)
        sqDistances=sqDiffMat.sum(axis=1)
        distances=sqDistances**0.5
        #排序，这里argsort()返回的是数据从小到大的索引值,这里这就是第几行数据
        sortedDisIndicies =distances.argsort()
        print(sortedDisIndicies)
        classCount={}
        #选取距离最小的k个点，并统计每个类别出现的频率
        #这里用到了字典get(key,default=None)返回键值key对应的值；
        #如果key没有在字典里，则返回default参数的值，默认为None
        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)
        print(sortedClassCount)
        return sortedClassCount[0][0]

py3.5中iteritems改为items（上倒数第4行）

#进入python界面： 
>>>import kNN 
>>>group,labels=kNN.createDataSet() 
>>>kNN.classify0([0,0],group,labels,3)

读取txt的数据

def file2matrix(filename):
        fr=open(filename)
        #读取文件
        arrayOLines=fr.readlines()
        #文件行数
        numberOfLines=len(arrayOLines)
        #创建全0矩阵
        returnMat=zeros((numberOfLines,3))
        #标签向量
        classLabelVector=[]
        index=0
        #遍历每一行，提取数据
        for line in arrayOLines:
                line=line.strip();
                listFromLine=line.split('\t')
                #前三列为属性信息
                returnMat[index,:]=listFromLine[0:3]
                #最后一列为标签信息
                classLabelVector.append(int(listFromLine[-1]))
                index +=1
        return returnMat,classLabelVector

# 重新加载kNN，得倒解析数据 
>>>reload(kNN) 
>>>datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')

使用Matplotlib 创建散点图

# 命令行中输入
>>>import matplotlib 
>>>import matplotlib.pyplot as plt 
>>>from numpy import array 
>>>fig = plt.figure() 
>>>ax=fig.add_subplot(111) 
>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
>>>plt.show()

利用github存储图片并以markdown的链接形式显示
[图片上传失败...(image-2b31b0-1512123353929)]

4. 数据的归一化

由于每个属性的取值数量级相差过大，会造成每个属性的权重不同，这显然是海伦不希望的。所以我们还要写一个函数实现数据归一化，公式如下:
newValue=(oldValue-min)/(max-min)
这个公式可以将特征值转化为0~1之间的值。

#归一化特征值
def autoNorm(dataSet):
        #每列的最小值
        minVals=dataSet.min(0)
        #每列的最大值
        maxVals=dataSet.max(0)
        #最大值与最小值的差值
        ranges=maxVals-minVals
        normDataSet=zeros(shape(dataSet))
        m=dataSet.shape[0]
        #minVals是1*3的矩阵，使用tile函数复制成和dataSet同样大小的矩阵，方便计算
        normDataSet=dataSet-tile(minVals,(m,1))
        normDataSet=normDataSet/tile(ranges,(m,1))
        return normDataSet,ranges,minVals

>>>reload(kNN) 
>>>normMat,ranges,minVals=kNN.autoNorm(datingDataMat)

5. 原始分类器

#原始测试分类器
def datingClassTest():
        hoRatio=0.10
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat,ranges,minVals=autoNorm(datingDataMat)
        m=normMat.shape(0)
        #10%的数据用于测试数据集
        numTestVecs=int(m*hoRatio)
        errorCount=0.0
        for i in range(numTestVecs):
                classifierResults=classify0(normMat[i,:],normMat[numTestVecs:m,:], datingLabels[numTestVecs:m],3)
                print("the classifier came back with: %d,the real answer id: %d"%(classifierResults,datingLabels[i]))
                if(classifierResults!=datingLabels[i]):errorCount +=1.0
        print("the total error rate is: %f" %(errorCount/float(numTestVecs)))

6. 接口

# 约会网站预测函数
def classifyPerson():
        resultList=['not at all','in small doses','in large doses']
        percentTats=float(input("在游戏上花费的时间占比( )?"))
        ffMiles=float(input("每年航空的里程数?"))
        iceCream=float(input("每年吃的冰淇淋（升）?"))
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat, ranges, minVals=autoNorm(datingDataMat)
        inArr=array([ffMiles,percentTats,iceCream])
        classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
        print("你可能是属于以下这类人：",resultList[classifierResult - 1])

[图片上传失败...(image-77db49-1512123353929)]
[图片上传失败...(image-dd2d24-1512123353929)]

7. 识别手写数字

# 将图片格式处理为一个向量（把一个32*32的二进制图形矩阵转换为1*1024的向量）,然后使用分类器处理图形信息
def img2vector(filename):
    # 创建一个1*1024的NumPy数组
    returnVect = zeros((1,1024))
    fr = open(filename)
    # 循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    # 将trainingDigits目录中的文件存储在列表中
    trainingFileList = listdir('trainingDigits')
    # 获得文件数赋值给m
    m = len(trainingFileList)
    # 创建一个m行1024列的训练矩阵，每行数据存储一个图像
    trainingMat = zeros((m,1024))
    for i in range(m):
        # 从文件名解析分类数字（eg：文件9_45.txt表示数字9的第45个实例）
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        # 将类代码存储在 hwLabels向量中
        hwLabels.append(classNumStr)
        # 使用 img2vector函数载入图像
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)

    # 将testDigits目录中的文件存储在列表中，步骤同上
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        # 不同的是要使用 classify0函数测试目录下的每个文件（文件中的值介于0-1之间，无需用autoNorm()函数
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

github代码