k-近邻算法
存在一个样本数据集合，也称训练数据集。样本集中每个数据都有标签，即知道数据是属于哪个分类。当我们提供一个无标签的数据时，将新数据的每个特征和现有数据集进行比对，然后找出最相似的标签。通常我们选择样本数据集中前 k 个最相似的数据，k 通常不大于 20。在 k 个数据中，找到出现次数最多的分类作为新数据的分类。
比如，有电影的分类。按亲吻、打斗、追车等特征镜头的数量来进行电影类别的划分。爱情片的亲吻数、打斗、追车数和动作电影，和科幻电影等都不大一样。假设我们已经有一系列数据：
| 电影名 | 亲吻 | 打斗 | 飞车 | 类别 |
| 电影一 | 2 | 9 | 3 | 动作 |
| 电影二 | 7 | 1 | 1 | 爱情 |
| 电影三 | 1 | 4 | 5 | 科幻 |
| 电影四 | 1 | 6 | 5 | 科幻 |
如果现在已经有一个电影，亲吻数、打斗数、飞业数分别是：1,3,6 我们就可以用 k 近邻算法去找出他应该属于哪个类别。该算法可以用来对数据进行类别划分。
优点: 精度高，对异常值不敏感。
缺点: 计算复杂度高，需要大量的训练数据，要大量的资源。数据只能为数值型或标称型。
案例:约会网站推荐对象
约会网站上，每个人都有不同的属性。用户登录并使用服务时，系统会根据你以往的反馈推荐一些对象。比如系统之前推荐过A,B,C，而你反馈的是对A很感兴趣，对B一般，对C讨厌。那么，后续系统就会按A的属性给你推荐相似的人。
用户属性有很多，假设有如下：每年旅行公里数、玩游戏所占时间比例、每周吃甜筒公升数。测试数据如：
| 张三 | 40920 | 8.32 | 0.95 | 3 |
| 李四 | 14488 | 7.15 | 1.67 | 2 |
| 王五 | 26052 | 1.44 | 0.80 | 1 |
| 赵六 | 75136 | 13.14 | 0.42 | 1 |
| 吴七 | 38344 | 1.66 | 0.13 | 1 |
最后一列的数值是喜欢指数。如果现在有一个人，前三列的值分别是：28488、10.52、1.30，我们就可以计算，推测出你对该对象的喜欢指数是多少。
目前有许多用户数据，以 csv 格式保存在文本文件中：user_data.txt 格式就是上述表格。 计算代码如下：
test1.py
# -*- coding: utf-8 -*-
from numpy import *
import operator
# 计算两点之间的距离
# inX 是要测试的数据
# dataSet 是测试样本数据
# labels 是标签向量,即测试数据中的结果列
# k 表示要取多少个相似的结果
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
# 要把输入的向量和测试数据进行比较.测试数据是一个 1000 * 3 的矩阵,而输入数据是 1 * 3
# 所以要用 tile 把输入数据进行填充成和测试数据一样长.然后再计算差值
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
# 根据欧氏距离公式.两个向量的距离计算公式是: 向量 [xa, ya] 和 [xb, yb] 距离: (xa-xb)^2 + (ya-yb)^2 然后再取平方根
# 距离计算.向量的各值相减后分别计算平方值
sqDiffMat = diffMat ** 2
# 将各平方值相加
sqDistances = sqDiffMat.sum(axis=1)
# 取平方根
distances = sqDistances ** 0.5
# 将矩阵比较结果(输入向量和矩阵中其它每个向量计算的距离值)按从小到大排序
sortedDistIndicies = distances.argsort()
classCount = {}
# 选择最靠前的 k 个结果
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]
# 将文件中的内容读取到向量中
def file2matrix(filename):
fr = open(filename)
# 得到文件中数据的行数
numberOfLines = len(fr.readlines())
# 准备矩阵.长度是文件的行数，内容是空，向量长度为 3
returnMat = zeros((numberOfLines, 3))
# 准备返回的标签
classLabelVector = []
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
# 将文件中每一行用 \t 分割成列表
listFromLine = line.split('\t')
# 取列表每行的前 3 列.把这三列数据读取到矩阵中
returnMat[index, :] = listFromLine[0:3]
# 最后一列做为标签
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat, classLabelVector
# 归一化数值.将任意范围内的数值处理成 0-1 之间的值.
# 因为计算两个值之间的距离时，有可能某一个数据特别大（诸如旅行公里数）。那这一项数据对结果的影响就非常大。
# 但在实际中，不应该让这一个属性就左右计算结果。所以要归一处理。
# 可以用公式: new_value = (old_value - min) / (max - min)， 用当前值减去最小值，除以取值范围
def autoNorm(dataSet):
# 矩阵中,各列的最小值组成新的向量
minVals = dataSet.min(0)
# 矩阵中,各列的最大值组成新的向量
maxVals = dataSet.max(0)
# 差值.取值范围
ranges = maxVals - minVals
# 矩阵总长度
m = dataSet.shape[0]
# dataSet 是 1000 * 3 的矩阵, minVals, ranges 都是 1 * 3的。
# 要想进行矩阵的计算，需要把 min 和 ranges 都用它的值填充满，即 tile(min, (m, 1)); tile(ranges, (m, 1))
old_min = dataSet - tile(minVals, (m, 1))
normDataSet = old_min / tile(ranges, (m, 1))
return normDataSet, ranges, minVals
# 测试算法准确度
# 从总数据中取一部分出来,通过算法去计算推测的结果.和真实的结果进行比较,看是否准确.
# 这里用 1/10 的数据做为测试
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: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount += 1.0
print "算法错误率: %f" % (errorCount * 100 / float(numTestVecs))
print "算法错误次数: %d 次" % errorCount
# 推算某个属性的人会是什么样的结果
def classifyPerson():
resultList = ['不喜欢！', '一般！', '感兴趣！']
fmiles = float(raw_input("每年旅行公里数:"))
gamecnt = float(raw_input("花在游戏上的时间比例:"))
creamCnt = float(raw_input("每周吃甜筒数:"))
# 从文件中加载测试数据
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
# 归一处理
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([fmiles, gamecnt, creamCnt])
# 将输入的内容归一化, 然后再进行推算
classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels, 3)
print "你对这个人的态度可能是：" + resultList[classifierResult - 1]
#datingClassTest()
classifyPerson()
案例:手写识别系统
目前，手头上有许多二进制图像矩阵，如：
00000000000000111110000000000000
00000000000001111111000000000000
00000000000011111111110000000000
00000000001111111111111000000000
00000000001111111111111000000000
00000000001111111111111000000000
00000000001111100111111100000000
00000000001111000001111110000000
00000000001111000000011111000000
00000000111110000000011111000000
00000000111110000000011110000000
00000001111110000000001110000000
00000001111110000000001111000000
00000001111100000000001111000000
00000011111100000000001111000000
00000011111100000000011110000000
00000011111100000000011110000000
00000011111100000000011110000000
00000001111110000000011110000000
00000001111110000000111110000000
00000001111111000001111100000000
00000001111111000001111100000000
00000001111111000001111000000000
00000000111111000001111000000000
00000000011111111111111000000000
00000000001111111111110000000000
00000000001111111111110000000000
00000000000111111111100000000000
00000000000011111111000000000000
00000000000011111110000000000000
00000000000001111100000000000000
00000000000000001000000000000000
每张图都采用 32 * 32 的方式来表示一个数字。同一个数字的写法可能不同，比如上面的 0，还有另外的写法：
00000000000111111000000000000000
00000000001111111100000000000000
00000000011111111110000000000000
00000000011111111111000000000000
00000000111111111111100000000000
00000000111111111111100000000000
00000000111111111111100000000000
00000000111110001111110000000000
00000000111110000111111000000000
00000001111110000011111000000000
00000001111110000001111100000000
00000001111110000001111100000000
00000001111110000000111110000000
00000001111110000000011111000000
00000001111110000000011111000000
00000001111000000000001111000000
00000001111000000000001111000000
00000011111000000000001111000000
00000011111000000000011111000000
00000011111000000000011111000000
00000011111000000000011111000000
00000001111000000000111110000000
00000001111000000001111100000000
00000001111100000111111100000000
00000001111100011111111100000000
00000001111111111111111000000000
00000000111111111111100000000000
00000000111111111111100000000000
00000000011111111111100000000000
00000000011111111111000000000000
00000000001111111000000000000000
00000000000010000000000000000000
此案例的想法是：通过一定数量的这种图片训练，让程序能自动识别这种二进制图像矩阵中 0 - 9 的数字。因为同为数字，每个数字的写法不一样，它的矩阵肯定不同。但是通过算法，来计算差异，取最相似的。
每个二进制图像矩阵都保存在一个 txt 文件中。文件名如：0_1.txt，0_3.txt。0 表示该文本里的矩阵表示的数字是 0。_1, _2 表示是第几个文件，无实际意义。那么，现在我们就需要许多用来训练的文本，如：0_1.txt – 0_90.txt; 1_1.txt, 1_90.txt。
由于此例中数据都是二进制的，所以不需要对向量中的值进行归一处理。
整体代码如下：
# -*- coding: utf-8 -*-
from numpy import *
import operator
from os import listdir
# 计算两点之间的距离
# inX 是要测试的数据
# dataSet 是测试样本数据
# labels 是标签向量,即测试数据中的结果列
# k 表示要取多少个相似的结果
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
# 要把输入的向量和测试数据进行比较.测试数据是一个 1000 * 3 的矩阵,而输入数据是 1 * 3
# 所以要用 tile 把输入数据进行填充成和测试数据一样长.然后再计算差值
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
# 根据欧氏距离公式.两个向量的距离计算公式是: 向量 [xa, ya] 和 [xb, yb] 距离: (xa-xb)^2 + (ya-yb)^2 然后再取平方根
# 距离计算.向量的各值相减后分别计算平方值
sqDiffMat = diffMat ** 2
# 将各平方值相加
sqDistances = sqDiffMat.sum(axis=1)
# 取平方根
distances = sqDistances ** 0.5
# 将矩阵比较结果(输入向量和矩阵中其它每个向量计算的距离值)按从小到大排序
sortedDistIndicies = distances.argsort()
classCount = {}
# 选择最靠前的 k 个结果
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]
# 把图片数据转换成向量
# 该数据是用 32 * 32 的二进制图像矩阵
def img2vector(filename):
# 创建一个矩阵,长度为 1，也就是一个向量。向量长度是 1024.正好用来存储 32 * 32 的矩阵值
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
def handwritingClassTest():
hwLabels = []
# 加载训练数据
trainingFileList = listdir('trainingDigits')
m = len(trainingFileList)
# 创建矩阵，长度是训练数据的条数.每一个向量长度是 1024
trainingMat = zeros((m, 1024))
# 遍历训练数据。把每张图的向量和真实值进行对应。把真实值作为 label(标签)
# 文件名的格式是 2_24.txt, 通过 _ 把前面的 2 分割出来.表示这个文件里的内容真实值应该是 2
for i in range(m):
fileNameStr = trainingFileList[i]
# 去除文件名中的点和后缀名( .txt )
fileStr = fileNameStr.split('.')[0]
# 根据文件名的规则，切割出真实值
classNumStr = int(fileStr.split('_')[0])
# 标签数据，后面算法中要用到.和训练数据一并传到计算方法中
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/%s' % fileNameStr)
# 待测试数据
testFileList = 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 "算法得到的值是: %d, 真实值是: %d" % (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount += 1.0
print "\n错误总数: %d" % errorCount
print "\n错误比例: %f" % (errorCount/float(mTest))
handwritingClassTest()