最近在看机器学习实战这本书。刚开始看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
