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

发表于 | 更新于: | 分类于 |
字数统计: 1,881字

一、概述

1. 原理：

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

2. 优缺点

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

3. 懒惰算法：

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

二、算法流程

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

三、算法框架

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

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

2. 使用欧氏距离公式

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

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

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

  • 准备数据 

    1
    2
    3
    4
    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

  • 算法 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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行） 

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

  • 读取txt的数据 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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

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

  • 使用Matplotlib 创建散点图 

    1
    2
    3
    4
    5
    6
    7
    8
    # 命令行中输入
    >>>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

4. 数据的归一化

  • 由于每个属性的取值数量级相差过大，会造成每个属性的权重不同，这显然是海伦不希望的。所以我们还要写一个函数实现数据归一化，公式如下:
  • newValue=(oldValue-min)/(max-min)
  • 这个公式可以将特征值转化为0~1之间的值。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #归一化特征值
    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
1
2
>>>reload(kNN) 
>>>normMat,ranges,minVals=kNN.autoNorm(datingDataMat)

5. 原始分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#原始测试分类器
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. 接口

1
2
3
4
5
6
7
8
9
10
11
# 约会网站预测函数
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 image

7. 识别手写数字

1
2
3
4
5
6
7
8
9
10
11
# 将图片格式处理为一个向量（把一个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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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代码