机器学习实战1（k-近邻算法篇）

目录

1、k-近邻算法

2、kNN算法实例1--电影分类

3、kNN算法实例2--改进约会网站的配对效果

4、kNN算法实例3--手写识别系统

5、K-means与KNN的区别

1、k-近邻算法

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

        ②缺点：计算复杂度高、时间复杂度高

        ③适用数据范围：数值型和标称型

        ④原理：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

        ⑤k-近邻算法的一般流程：

                （1）收集数据：可以使用任何方法。
                  (2)   准备数据：距离计算所需要的数值，最好是结构化的数据格式。
                  (3） 分析数据：可以使用任何方法。
                  (4)   训练算法：此步骤不适用于化近邻算法。
                  (5)   测试算法：计算错误率。
                  (6)   使用算法：首先需要输入样本数据和结构化的输出结果，然后运行算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

2、kNN算法实例1--电影分类

        使用k-近邻算法分类一个电影是爱情片还是动作片。

        有人曾经统计过很多电影的打斗镜头和接吻镜头。如图下显示了6部电影的打斗数和接吻数。假如有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们可以用kNN来解决这个问题。

​

         即使不知道未知电影属于哪种类型，我们也可以通过某种方法计算出来。

        首先计算未知电影与样本集中其他电影的距离，使用欧氏距离公式。

​

​

         现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He 's Not Really into Dudes、Beautiful Woman和California Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。

       

        代码部分：

 在构造完整的k-近邻算法之前，用函数，我们还需要编写一些基本的通在kNN.py文件中增加下面的代码:

        1、准备数据集createDataSet()

from numpy import *
import operator
import numpy as np

def createDataSet():
    group = array([[3,3],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['A','A','A','B','B','B'] #特征的标签
    return group,labels

        2、对未知类别属性的数据集中的每个点依次执行以下操作:

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

        (2)按照距离递增次序排序;

        (3)选取与当前点距离最小的k个点;

        (4)确定前k个点所在类别的出现频率;

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

        

变量： inX - 用于分类的数据(测试集)           dataSet - 用于训练的数据(训练集)

            labes - 分类标签                                k - kNN算法参数,选择距离最小的k个点

def classify(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]#计算有几个训练集样本
    distance = np.power(sum(np.power(inX-group,2),1),0.5)#欧式距离公式
    sortedDistIndices = distance.argsort()#返回小到大排序后的索引值
    classCount = {} #定义一个用来记录类别的字典
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]#取出前k个元素的类别
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0] #取频率出现最高

         3、完整代码：

from numpy import *
import operator
import numpy as np

def createDataSet():
    group = array([[3,3],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['A','A','A','B','B','B'] #特征的标签
    return group,labels


def classify(inX,dataSet,labels,k):
    #1
    dataSetSize = dataSet.shape[0]#计算有几个训练集样本
    distance = np.power(sum(np.power(inX-group,2),1),0.5)#欧式距离公式
    sortedDistIndices = distance.argsort()#返回小到大排序后的索引值
    classCount = {} #定义一个用来记录类别的字典
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]#取出前k个元素的类别
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0] #取频率出现最高


X = np.array([50,0])
group,labels = createDataSet()
ans = classify(X,group,labels,2)
print(ans)

3、kNN算法实例2--改进约会网站的配对效果

        海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人:

        1 不喜欢的人

        2 魅力一般的人

        3 极具魅力的人

        海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包含以下3种特征:

        ① 每年获得的飞行常客里程数        

        ② 玩视频游戏所耗时间百分比        

        ③ 每周消费的冰淇淋公升数

        datingTestSet.txt：数据在这！

        1、准备数据，将文本记录转化为Numpy的解析程序

        从下面的代码可以看到，Python处理文本文件非常容易。首先我们需要知道文本文件包含多少行。打开文件，得到文件的行数。然后创建以零填充的矩阵NumPy(实际上，NumPy是一个二维数组，这里暂时不用考虑其用途)。为了简化处理，我们将该矩阵的另一维度设置为固定值3，你可以按照自己的实际需求增加相应的代码以适应变化的输入值。循环处理文件中的每行数据，首先使用函数line.strip()截取掉所有的回车字符，然后使用tab字符t将上一步得到的整行数据分割成一个元素列表。接着，我们选取前3个元素,将它们存储到特征矩阵中。Python语言可以使用索引值-1表示列表中的最后一列元素，利用这种负索引，我们可以很方便地将列表的最后一列存储到向量classLabelVector中。需要注意的是，我们必须明确地通知解释器，告诉它列表中存储的元素值为整型，否则Python语言会将这些元素当作字符串处理。以前我们必须自己处理这些变量值类型问题，现在这些细节问题完全可以交给NumPy函数库来处理。

#文本转换
def filematrix(filename):
    fr = open(filename)
    arrayLine = fr.readlines()
    numberLine = len(arrayLine)#得到文件行数
    returnMat = zeros((numberLine,3))
    classLabelVector = []
    index = 0
    for line in arrayLine:
        line = line.strip()#接去掉所有的回车符
        listFromLine = line.split('t')#使用tab字符t将上一步得到的整行数据分隔为一个元素列表
        returnMat[index,:] = listFromLine[0:3]#获取三种特征
        classLabelVector.append(int(listFromLine[-1]))#获取分类结果
        index+=1
    return returnMat,classLabelVector

        2、分析数据

        首先我们使用Matplotlib制作原始数据的散点图，记得引用：

import matplotlib.pyplot as plt

#创建散点图
def matplot(X,Labels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(X[:,1],X[:,0],15*array(Labels),15*array(Labels))
    plt.show()

        可以看到可视化结果如图下，当然你还可以自己尝试去改变x,y轴的坐标，画其他的图。

        3、归一化处理

        如果想要计算样本3和样本4之间的距离，可以使用下面的方法：

       我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于表2-3中其他两个特征——玩视频游戏的和每周消费冰淇淋公升数——的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。         

         在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化,如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值:

                                              

        其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。        

#归一化特征值
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals-minVals
    dataSet = (dataSet-minVals)/ranges
    return dataSet,ranges,minVals

        4、分类器函数

        和电影分类一样。

#分类器
def classify(X,dataSet,labels,k):
    dataSetSize = dataSet. shape[0]
    distance = np.power(sum(np.power(X-dataSet,2),1),0.5)#欧式距离公式
    sortedDistIndices = distance.argsort()
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistIndices[i]]
        classCount[voteLabel] = classCount.get(voteLabel,0)+1
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]

        5、测试算法

        函数datingClassTest，它首先使用了filematrix和autoNorm函数从文件中读取数据并将其转换为归一化特征值。接着计算测试向量的数量，此步决定了normMat向量中哪些数据用于测试，哪些数据用于分类器的训练样本。然后将这两部分数据输入到原始kNN分类器函数classify。最后，函数计算错误率并输出结果。

#测试算法
def datingClassTest():
    hoRatio = 0.1#取所有数据的百分之十
    datingDataMat,datingLabels = filematrix('datingTestSet.TXT')
    normX,ranges,minVals = autoNorm(datingDataMat)
    m = normX.shape[0]#返回dataSet的行数
    numTestVecs = int(m*hoRatio)#百分之十的测试数据的个数
    errorCount = 0.0#分类错误计数
    for i in range(numTestVecs):
        #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
        classifierResult = classify(normX[i,:],normX[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("错误率：%f"%(errorCount/numTestVecs*100))

        可计算出错误率为5%，这是一个相当不错的结果。我们也可以尝试改变k、hoRatio的值，检测错误率的变化。

        6、约会网站预测函数

        上面我们已经在数据上对分类器进行了测试,现在终于可以使用这个分类器为海伦来对人们分类。我们会给海伦一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息。程序会给出她对对方喜欢程度的预测值。

#预测
def classifyPerson():
    resultList = ['讨厌','有些喜欢','非常喜欢']
    precentTats = float(input("玩视频游戏所耗时间百分比:"))
    fMiles = float(input("每年获得的飞行常客里程数:"))
    iceCream = float(input("每周消费的冰激淋公升数:"))

    filename = "datingTestSet.txt"
    datingDataMat, datingLabels = filematrix(filename)
    normX, ranges, minVals = autoNorm(datingDataMat)#训练集归一化
    inArr = np.array([fMiles, precentTats, iceCream])#生成NumPy数组,测试集
    norminArr = (inArr - minVals) / ranges #测试集归一化
    classResult = classify(norminArr,normX,datingLabels,3)
    print("你可能%s这个人" % (resultList[classResult-1]))

        预测结果如下图：

         7、完整代码

from numpy import *
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import operator
#文本转换
def filematrix(filename):
    fr = open(filename)
    arrayLine = fr.readlines()
    numberLine = len(arrayLine)#得到文件行数
    returnMat = zeros((numberLine,3))
    classLabelVector = []
    index = 0
    for line in arrayLine:
        line = line.strip()#接去掉所有的回车符
        listFromLine = line.split('t')#使用tab字符t将上一步得到的整行数据分隔为一个元素列表
        returnMat[index,:] = listFromLine[0:3]#获取三种特征
        classLabelVector.append(int(listFromLine[-1]))#获取分类结果
        index+=1
    return returnMat,classLabelVector


#创建散点图
def matplot(X,Labels):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(X[:,1],X[:,0],15*array(Labels),15*array(Labels))
    plt.show()


#归一化特征值
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals-minVals
    dataSet = (dataSet-minVals)/ranges
    return dataSet,ranges,minVals

#分类器
def classify(X,dataSet,labels,k):
    dataSetSize = dataSet. shape[0]
    distance = np.power(sum(np.power(X-dataSet,2),1),0.5)#欧式距离公式
    sortedDistIndices = distance.argsort()
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistIndices[i]]
        classCount[voteLabel] = classCount.get(voteLabel,0)+1
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]


#测试算法
def datingClassTest():
    hoRatio = 0.1#取所有数据的百分之十
    datingDataMat,datingLabels = filematrix('datingTestSet.TXT')
    normX,ranges,minVals = autoNorm(datingDataMat)
    m = normX.shape[0]#返回dataSet的行数
    numTestVecs = int(m*hoRatio)#百分之十的测试数据的个数
    errorCount = 0.0#分类错误计数
    for i in range(numTestVecs):
        #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
        classifierResult = classify(normX[i,:],normX[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("错误率：%f"%(errorCount/numTestVecs*100))

#预测
def classifyPerson():
    resultList = ['讨厌','有些喜欢','非常喜欢']
    precentTats = float(input("玩视频游戏所耗时间百分比:"))
    fMiles = float(input("每年获得的飞行常客里程数:"))
    iceCream = float(input("每周消费的冰激淋公升数:"))

    filename = "datingTestSet.txt"
    datingDataMat, datingLabels = filematrix(filename)
    normX, ranges, minVals = autoNorm(datingDataMat)#训练集归一化
    inArr = np.array([fMiles, precentTats, iceCream])#生成NumPy数组,测试集
    norminArr = (inArr - minVals) / ranges #测试集归一化
    classResult = classify(norminArr,normX,datingLabels,3)
    print("你可能%s这个人" % (resultList[classResult-1]))


X,Labels = filematrix('datingTestSet.txt')
# autoNorm(X)
matplot(X,Labels)
# NormX,ranges,minVals = autoNorm(X)
# datingClassTest()
classifyPerson()

4、kNN算法实例3--手写识别系统

        本节我们一步步地构造使用k-近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字0到9。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小:宽高是32像素×32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

        实际图像存储在源代码的两个子目录内:目录trainingDigits中包含了大约2000个例子，每个例子的内容如图下所示，每个数字大约有200个样本;目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。两组数据没有覆盖，你可以检查一下这些文件夹的文件是否符合要求。

 数据：数字数据在这！

1、准备数据，将图像转换为测试向量

        为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个32×32的二进制图像矩阵转换为1×1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。

def imgvector(filename):
    returnVect = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        linestr = fr.readline()
        for j in range(32):
            returnVect[0,i*32+j] =int(linestr[j]) #读取数据
    return returnVect

2、识别部分代码

        在写入这些代码之前，我们必须确保将from os import listdir写人文件的起始部分，这段代码的主要功能是从os模块中导入函数listdir，它可以列出给定目录的文件名。

from os import listdir

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = np.zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]#获得文件的名字
        fileStr = fileNameStr.split('.')[0]
        ClassNumber = int(fileStr.split('_')[0])#获得分类的数字
        hwLabels.append(ClassNumber)#将获得的类别添加到hwLabels中
        trainingMat[i,:] = imgvector('trainingDigits/%s'%fileNameStr)#将每一个文件数据存储到矩阵中
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]#获得文件的名字
        fileStr = fileNameStr.split('.')[0]
        ClassNumber = int(fileStr.split('_')[0])#获得分类的数字
        vectorUnderTest = imgvector('testDigits/%s'%fileNameStr)
        vectResult = classify(vectorUnderTest,trainingMat,hwLabels,3)
        if(vectResult!=ClassNumber):
            errorCount+=1
    print("总共错了%d个数据"%errorCount)
    print("错误率为%f"%(errorCount/mTest*100))

输出为：

        k-近邻算法识别手写数字数据集，错误率为1.1%。改变变量k的值、修改函数handwriting--classTest随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值，观察错误率的变化。

        实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢?k决策树就是k-近邻算法的优化版，可以节省大量的计算开销。

        3、完整代码

import numpy as np
from os import listdir
import operator
from numpy import  *

#将图像转化为测试向量
def imgvector(filename):
    returnVect = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        linestr = fr.readline()
        for j in range(32):
            returnVect[0,i*32+j] =int(linestr[j]) #读取数据
    return returnVect

#分类器
def classify(X,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    distance = sum(np.power(X-dataSet,2),1)**0.5#欧式距离公式
    sortedDistIndices = distance.argsort()
    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistIndices[i]]
        classCount[voteLabel] = classCount.get(voteLabel,0)+1
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]

#识别数字
def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = np.zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]#获得文件的名字
        fileStr = fileNameStr.split('.')[0]
        ClassNumber = int(fileStr.split('_')[0])#获得分类的数字
        hwLabels.append(ClassNumber)#将获得的类别添加到hwLabels中
        trainingMat[i,:] = imgvector('trainingDigits/%s'%fileNameStr)#将每一个文件数据存储到矩阵中
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]#获得文件的名字
        fileStr = fileNameStr.split('.')[0]
        ClassNumber = int(fileStr.split('_')[0])#获得分类的数字
        vectorUnderTest = imgvector('testDigits/%s'%fileNameStr)
        vectResult = classify(vectorUnderTest,trainingMat,hwLabels,3)
        if(vectResult!=ClassNumber):
            errorCount+=1
    print("总共错了%d个数据"%errorCount)
    print("错误率为%f"%(errorCount/mTest*100))




testVector = imgvector('testDigits/0_3.txt')
handwritingClassTest()
# print(testVector)

5、K-means与KNN的区别

        在学习KNN算法的时候可以将K-means算法结合起来学习。之前在我的博客上有对K-Means 算法原理进行讲解（根据的是吴恩达教授课程做的笔记）。

链接附下：K-Means算法_吃花生的图图的博客-CSDN博客

        在这里我先讲一下K-means与KNN之间的区别：

        ①K-means本质上是无监督学习，而KNN是监督学习；

        ②K-means是聚类算法，KNN是分类（或回归）算法。

        ③K-means算法把一个数据集分割成簇，使得形成的簇是同构的，每个簇里的点相互靠近，K-means中的K代表的是簇中心。KNN算法尝试基于其k（可以是任何数目）个周围邻居来对未标记的观察进行分类，KNN的K代表的是选择与新测试样本距离最近的前K个训练样本数。

        ④KMeans算法的训练过程需要反复迭代的操作（寻找新的质心），但是KNN不需要。