k-近邻算法
优点: 精度高、对异常值不敏感、无数据输入假定。
缺点: 计算复杂度高、空间复杂度高。
适用数据范围: 数值型和标称型。
1.实现分类器
from numpy import *
import operator
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.items(), \
key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
??在这段代码中，我们首先导入numpy和operator模组。通过numpy中的shape方法，获取dataSet矩阵的行数(数据个数)。
??然后利用输入数据inX创建一个与dataSet行数相同的矩阵，其中每行的数据都为inX。利用此矩阵，与dataSet矩阵进行基于欧式距离公式的矩阵运算。
欧式距离公式
??通过numpy中的argsort()方法，对计算出的距离向量进行排序(非in-place)，并返回排序后的各数在原向量中的索引值(从小到大)。
??之后创建空白哈希表，遍历距离最小的前k个特征，以特征的分类标签为键，记录分类标签出现次数。然后使用标准库operator的itemgetter方法，对哈希表以第2个域(哈希表的值)的大小，从大到小排序。此方法返回的数组中，原哈希表的键与值以元组形式表示。
??最后返回出现次数最多的标签。
2.数据矩阵化
def file2matrix(filename):
fr = open(filename)
numberOfLines = len(fr.readlines())
returnMat = zeros((numberOfLines, 3))
classLabelVector = []
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
returnMat[index, :] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
??原始数据必须要格式化为numpy矩阵才能进行各种运算操作。
??首先输入数据并获得数据的行数。以文件行数，3为列数创建初始全0矩阵。
??遍历数据每行，以制表符分割每行元素，前3个元素为数据的特征值，放入矩阵，最后1个元素为分类标签，放入标签列表。
??最后返回特征矩阵与标签列表。
交友网站特征数据(分别为里程数、花费在电子游戏上的时间比、冰激凌消费(升/年)、吸引程度标签)
3.数据归一化
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m, 1))
normDataSet = normDataSet / tile(ranges, (m, 1))
return normDataSet, ranges, minVals
??特征值因为单位或者本身的数据特点，从而导致取值范围相差很大。我们不希望某一个特征值对程序影响过大(或过小)，所以机器学习算法中通常会对数据进行归一化操作。
归一化公式
??这段代码中，首先用numpy的最小值min和最大值max方法，对矩阵每列(每一种特征)取最小最大值。
??然后用tile函数创建和原特征矩阵相同大小的矩阵(方便矩阵运算)，对每个特征值一并进行归一化。
??最后返回归一化后的矩阵。另外返回的特征范围向量以及最小值向量在之后会需要。
归一化后的矩阵(特征值转化为0~1的取值范围)
4.测试分类器
def datingClassTest():
hoRatio = 0.10
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], \
datingLabels[numTestVecs:m], 3)
print("the classifier came back with: %s, the real answer is : %s" \
% (classifierResult, datingLabels[I]))
if (classifierResult != datingLabels[I]):
errorCount += 1.0
print("the total error rate is: %f" % (errorCount/float(numTestVecs)))
??机器学习算法在实装之前通常需要测试效果。这里利用训练数据的后10%作为测试数据，进行算法测试。
??使用计数器记录错误分类的次数，并输出语句提示。最后输出错误率。
错误率为5%
5.实装分类器
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(input(\
"percentage of time spent playing video games? "))
ffMiles = float(input("frequent flier miles earned per year? "))
iceCream = float(input("liters of ice cream consumed per year? "))
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([ffMiles, percentTats, iceCream])
classifierResult = classify0((inArr-minVals) / ranges, normMat, datingLabels, 3)
print("You will probably like this person: ", resultList[int(classifierResult)-1])
??利用实现的分类器和训练数据，对用户输入的数据进行预测分类。
??因为训练数据中的标签是以数字代替的，所以首先以标签数字为索引，创建文字版标签的立标。
??提示用户输入数据，Python的input输入默认为str类型，所以这边要转换为float类型。
??然后就是常规操作的训练数据矩阵化，归一化。另外用户输入的数据也要转化为一个矩阵。
??利用autoNorm归一化函数返回的特征范围向量和最小值向量，对用户输入的数据归一化处理。
??用classify0分类器函数对输入数据进行分类，返回分类标签。最后输出对应索引的文字版标签。
6.手写数字识别之图像向量化
def img2vector(filename):
returnVect = zeros((1, 1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
??我们可以利用实现的分类器识别手写数字。
??首先要对数字图像进行预处理。这边的图像并不是像素化的，而是处理后以0、1数字为元素的图像。稍后会介绍简单的图像转化为0、1数字的方法。
数字0的{0,1}图像
??这里使用的是32x32的图像，所以初始化一个1024x1的全0向量。
??读取文件，把每行的数字依次塞进向量里。最后返回向量。
7.手写数字识别之测试分类器
import os
def handwritingClassTest():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
fileNameStr = trainingFileList[I]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = os.listdir('testDigits')
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[I]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
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:", errorCount)
print("\nthe total error rate is:", (errorCount/float(mTest)))
??这里的程序和之前的没有太大区别。但是不像之前的交友网站数据都在一个文件里，数字图像都是一个个独立的文件，所以在文件输入操作上花了一点功夫。
??使用os模组的listdir方法，以列表方式获取目标路径的所有文件名。然后遍历所有训练数据，将图像向量化。这里的标签名是文件名下划线前的数字(例如0_0是数字0的第一个图像，分类标签为0)。利用split分割文件名，将下划线前的数字依次存入标签列表。
??对测试数据也用上述方法处理。遍历时使用分类器进行分类，对错误分类计数，输出语句。最后输出错误次数和错误率。
8.像素图像的{0,1}数字化
from PIL import Image
def pic2array(filename):
img =Image.open(filename)
pix = img.load()
width = img.size[0]
height = img.size[1]
li = [[0 for x in range(height)] for y in range(width)]
for i in range(height):
for j in range(width):
if (pix[i, j][0] < 150 and
pix[i, j][1] < 150 and
pix[i, j][2] < 150):
li[i][j] = 1
f = open(filename.split(".")[0]+'.txt', "w")
for i in range(height):
for j in range(width):
f.write(str(li[j][I]))
f.write("\n")
f.close()
??使用PIL 库进行图像处理?；袢⊥枷袼邢袼氐膔gb值，存入pix变量。获取图像的高宽像素数，初始化对应大小的全0矩阵。
??然后将rgb同时小于150的像素在矩阵中的对应元素改为1。最后保存到txt文件中。
实际效果
注意，图像向量化的程序只对应32x32的图像，所以在数字化之前请先使用图像处理工具进行缩小处理。
9.实装手写数字识别
def myHandwriting():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
fileNameStr = trainingFileList[I]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
myHandwritingFileList = os.listdir('myHandwritings')
n = len(myHandwritingFileList)
for j in range(n):
fileNameStr = myHandwritingFileList[j]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('myHandwritings/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
??和测试分类器的程序基本一样，区别是这边导入的是自己的数据。
参考
