01-kNN算法实战-(机器学习实战)

最近在看机器学习实战这本书。刚开始看kNN算法，并写了些程序，分享下一些感悟和细节。

什么是kNN

kNN中文又称为k-近邻算法，其基本思想是通过计算输入样本点 和 训练集样本点之前的这两个向量之前的距离，距离越近的话，说明其特征越靠近，通过取出其k个距离最近的样本点，然后计算这k个样本点中类别占比最大的类比以此来预测输入样本点(被测样本点)的类别。

kNN的优势

• kNN是ML里最简单，最基本的算法。
• kNN不会受到差别特别大的样本中的特征元素的影响(对异常值不敏感)。因为采用了归一化技术
• kNN的精度高

kNN的劣势

• kNN算法时间复杂度较高，需要计算被测样本点和训练集中所有样本点的距离

kNN算法的实现

from numpy import *
import operator
# 该分类器模型，只需要输入向量， 训练数据集矩阵dataSet，每一行是一个样本。labels(每一行的样本标签)。k取前几个
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(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)
    return sortedClassCount[0][0]

• 这里的dataSet是numpy模块里的数组(也可以看成矩阵)，不是python中内置的数组，shape属性会返回这个数组的纬度.(比如是2 * 3的二维数组，则会返回(2, 3)表示这是一个2纬数组，每个纬度的大小分别是2，3)
• tile函数用来创建矩阵，其中(dataSetSize， 1)表示沿着inX向量的行方向(inX是一个行向量)，赋值dataSetSize次，沿着列方向复制1次(既列不变)。
• diffMat矩阵计算出了各个向量之前的距离的平方值。其中2表示平方，0.5表示开平方

使用kNN来改进婚恋网站的匹配

这里的数据集如下

image.png

datingTestSet.txt存放了该网站关于个人信息的集合。每一行代表一个人，一共有三个特征属性，和一个标签属性用来标识是哪一类人。
datingTestSet2.txt 存放的是处理过的datingTestSet数据，将类别标签处理成数字

• 三个特征属性分别是: 每年航班的行程公里数，玩游戏的时间所占的时间百分比，每周消费的冰淇淋公升数
• 人一共分为三类(不喜欢的、魅力一般、极具魅力)

两个文件的内容如下

image.png

目的

现在的需求是，我们必须根据提供的数据，来准确的划分出这三类人。才能精确的从数据中挑选出的人是用户感兴趣的。

分析

• 根据之前总结的kNN分类器模型，我们需要将数据进行处理。分别分离出训练数据集、测试数据集、数据集对应的标签。其实最重要的是准本和分析数据集，然后进行建模，但是由于这里数据集已经是现有的，直接用就行。
• 接着我们编写测试程序，将测试数据集、训练数据集、标签丢入改模型进行计算
• 统计识别的错误率，如果错误率很低。那基本上可以使用。如果错误率高，那就要改进数据集，进行其他特征点的抽取。

步骤

处理数据(提取数据，归一化)

改函数用来读取训练集数据将其转化为矩阵，并提取出标签集合。具体代码看下面

from numpy import *
def file2matrix(filename):
    file = open(filename)
    arrayOfLines = file.readlines()
    numberOfLines = len(arrayOfLines)
    returnMat = zeros((numberOfLines,3))
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))  # 这边要十分小心，必须强制转换为整形，不然编译器会当做字符串处理
        index += 1
    return returnMat, classLabelVector

将特征数据都归一化
因为航程特征的数字太大，对其他两个影响太大，但是又不能忽略，为了减少这种影响。将数据进行归一行，既处理层0到1之前的小数。利用了如下原理
newValue = oldValue - minValue/(maxValue - minValue)

# 数据归一化 newValue = oldValue - minValue/(maxValue - minValue)
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normaMat = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normaMat = dataSet - tile(minVals, (m, 1))
    normaMat = normaMat / tile(ranges, (m, 1))
    return normaMat, ranges, minVals

通过图形分析数据

• (x轴为游戏时间占比，y轴为每周吃冰淇淋的公斤数)

# 列2和列1的比较
datingDataMat,datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
print datingDataLabels
import matplotlib
import matplotlib.pyplot as plt
from numpy import *
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0 * array(datingDataLabels), 15.0 * array(datingDataLabels))
plt.show()

image.png

• (x轴为航班占比，y轴为游戏时间耗时占比)

# 列2和列1的比较
datingDataMat,datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
print datingDataLabels
import matplotlib
import matplotlib.pyplot as plt
from numpy import *
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0 * array(datingDataLabels), 15.0 * array(datingDataLabels))
plt.show()

image.png

通过上面的分析，可以很明显的发现，使用前两个特征，我们就可以将这三类人比较精确的分离出来。但如果只使用第二个和第三个特征难以分离出该三类。

编写测试用例，测试kNN分类器的效果

# 针对约会网站的测试代码,测试分类器的效果
def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingDataLabels = file2matrix('/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]   # 获取训练集行数
    numTestVecs = int(m * hoRatio)  # 取10%的行数作为测试集  
    errorCount = 0.0
    for i in range(numTestVecs):  
        classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,], datingDataLabels[numTestVecs:m], 3)  # 取从小到的前三个
        print "分类的结果是: %d, 目标结果是: %d" % (int(classifierResult), int(datingDataLabels[i]))
        if (classifierResult != datingDataLabels[i]): errorCount += 1.0
    print "总的错误率为: %f%%" %(errorCount / float(numTestVecs) * 100.0)

运行datingClassTest()方法我们可以看到如下结果(其中1，2，3分别代表三类人的标签映射。)，改分类器的错误率为5%，也就是说95%的情况下匹配都是准确的，算是还不错的分类器。

image.png

使用KNN实现识别手写数字

具体思路和上面的例子一样。这边有个比较不一样的步骤是我们需要对图片进行处理，这里我们统一对图片做了以下处理。

• 将图片的大小处理层一样的黑白图。

• 对于每张图片，我们使用 正确的对应数字_样本索引.txt来命名。(之所以处理成文本是为了在这里比较直观)

  
  image.png
  image.png

分析

1.为了使用kNN模型，我们需要将图片转化为一个行向量。由于图片大小事32*32，我们需要一个1024大小的行向量即可存储。

from numpy import *
def img2vector(filename):
    fr = open(filename)
    returnVect = zeros((1, 1024))
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVec[0, 32 * i + j] = int(lineStr[j])
    return returnVect

2.使用kNN模型进行测试

from os import listdir
from numpy import *
def handwritingClassTest():
# 遍历训练数据集，将数据集装载进矩阵。
    trainingFilesPath = "/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/digits/trainingDigits/"
    arrayOfTrainingFiles = listdir(trainingFilesPath)
    m = len(arrayOfTrainingFiles)
    trainingMat = zeros((m, 1024))
    classLabels = []
    for i in range(m):
        fileNameStr = arrayOfTrainingFiles[i]
        fileStr = fileNameStr.split('.')[0]
        classNum = int(fileStr.split('_')[0])
        classLabels.append(classNum)
        trainingMat[i,:] = img2vector(trainingFilesPath + fileNameStr)
    
    testFilePath = "/Users/sixleaves/Dropbox/DeepLearning/machinelearninginaction/Ch02/digits/testDigits/"
    arrayOfTestFiles =  listdir(testFilePath)
    mTest = len(arrayOfTestFiles)
    errorCount = 0.0;
    for j in range(mTest):
        testFileNameStr = arrayOfTestFiles[j]
        testFile = testFileNameStr.split('.')[0]
        testNum = testFile.split('_')[0]
        testImageVec = img2vector(testFilePath + testFileNameStr)
        classifierResult = classify0(testImageVec, trainingMat, classLabels, 3)
        print "识别结果为: %d, 正确结果为: %d" % (int(classifierResult), int(testNum))
        if classifierResult != int(testNum): errorCount += 1.0
    print "识别错误个数为: %d" % (int(errorCount))
    print "识别错误率为: %f%%" % (errorCount / float(mTest) * 100.0)    

image.png

效果还是相当不错，基本达到了99%识别效率

总结:

• 一般机器学习解决问题需要以下步骤(准备数据，分析数据，训练算法(kNN不适用，kNN无需训练)，测试算法，使用算法)。
• 对于kNN算法模型来说，分析数据过程由于重要，只有有价值的数据使用kNN才能有精确的结果。
• kNN算法比较简单，稳定。但是效率低。其思想主要是计算相似度(通过计算向量距离)，并使用概率来得出分类结果。

---

by sixleaves 20170726 FuZhou