KNN实战（一）-爱编程
KNN实战（一）
& & & 这两天一直忙于比赛还有各种培训什么的，今天也算是有时间看看书，调调程序了，我的小心脏辣个兴奋啊。言归正传，之前，对KNN进行了一个简单的验证，今天我们使用KNN改进约会网站的效果，个人理解，这个问题也可以转化为其它的比如各个网站迎合客户的喜好所作出的推荐之类的，当然，今天的这个例子功能也实在有限。
& & &在这里根据一个人收集的约会数据，根据主要的样本特征以及得到的分类，对一些未知类别的数据进行分类，大致就是这样。
& & &我使用的是python 3.4.3,首先建立一个文件，例如date.py,具体的代码如下：
#coding:utf-8
from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt
###导入特征数据
def file2matrix(filename):
fr = open(filename)
contain = fr.readlines()###读取文件的所有内容
count = len(contain)
returnMat = zeros((count,3))
classLabelVector = []
for line in contain:
line = line.strip() ###截取所有的回车字符
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]###选取前三个元素，存储在特征矩阵中
classLabelVector.append(listFromLine[-1])###将列表的最后一列存储到向量classLabelVector中
index += 1
##将列表的最后一列由字符串转化为数字，便于以后的计算
dictClassLabel = Counter(classLabelVector)
classLabel = []
kind = list(dictClassLabel)
for item in classLabelVector:
if item == kind[0]:
elif item == kind[1]:
classLabel.append(item)
return returnMat,classLabel#####将文本中的数据导入到列表
##绘图（可以直观的表示出各特征对分类结果的影响程度）
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()
## 归一化数据,保证特征等权重
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))##建立与dataSet结构一样的矩阵
m = dataSet.shape[0]
for i in range(1,m):
normDataSet[i,:] = (dataSet[i,:] - minVals) / ranges
return normDataSet,ranges,minVals
def classify(input,dataSet,label,k):
dataSize = dataSet.shape[0]
####计算欧式距离
diff = tile(input,(dataSize,1)) - dataSet
sqdiff = diff ** 2
squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
dist = squareDist ** 0.5
##对距离进行排序
sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标
classCount={}
for i in range(k):
voteLabel = label[sortedDistIndex[i]]
###对选取的K个样本所属的类别个数进行统计
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
###选取出现的类别次数最多的类别
maxCount = 0
for key,value in classCount.items():
if value & maxCount:
maxCount = value
classes = key
return classes
##测试(选取10%测试）
def datingTest():
rate = 0.10
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
testNum = int(m * rate)
errorCount = 0.0
for i in range(1,testNum):
classifyResult = classify(normMat[i,:],normMat[testNum:m,:],datingLabels[testNum:m],3)
print("分类后的结果为:,", classifyResult)
print("原结果为：",datingLabels[i])
if(classifyResult != datingLabels[i]):
errorCount += 1.0
print("误分率为:",(errorCount/float(testNum)))
###预测函数
def classifyPerson():
resultList = ['一点也不喜欢','有一丢丢喜欢','灰常喜欢']
percentTats = float(input("玩视频所占的时间比?"))
miles = float(input("每年获得的飞行常客里程数?"))
iceCream = float(input("每周所消费的冰淇淋公升数?"))
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
inArr = array([miles,percentTats,iceCream])
classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3)
print("你对这个人的喜欢程度:",resultList[classifierResult - 1])
新建test.py文件了解程序的运行结果，代码：
#coding:utf-8
from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt
import sys
sys.path.append("D:\python\Mechine learing in Action\KNN")
import date
date.classifyPerson()
运行结果如下图：
这样就算是成功了吧，当然，在这其中也遇到了很多的问题，我看的《机器学习实战》这本书主要还是针对于python2.7的，理所应当的我遇到了不少问题。有在学习这本书的朋友咱们可以交流下哈~
最后还是想说一点，就是在敲代码的时候，编完一段还是先调试一下比较好，这样到最后就不会有什么太大的问题啦，这次我就是这么干的~~~
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&我是萌萌哒分隔线&&&&&&&&&&&&&&&&&&&&&&&&
最近依旧一个字 ：&忙&！暑假呢，想想也还真是苦了自己，爸爸麻麻打电话都催着回家，看来二老还真是想我了。当时期末考结束之后就好好计划了这个暑假应该怎么过，现在一大半过去了，确实也没有什么后悔的。其实有时候在想，一个遥不可及的梦想到底值不值得坚持，我的行动告诉了我我在坚持，虽结果不可知，但时间会证明一切吧。
我从不悲观，相信不劳无获，更相信劳有所获！
我喜欢的生活是：该吃吃，该玩玩，该忙依旧得忙~
又快一点了，明早还得早起去上课，早点休息吧，各位晚安~
版权所有 爱编程 (C) Copyright 2012. . All Rights Reserved.
闽ICP备号-3
微信扫一扫关注爱编程，每天为您推送一篇经典技术文章。先拉一下仇恨，这篇文章是在喝着走亲戚时带来的饮料，单曲循环着成龙版本的《拯救》的情况下完成的，哈哈，过年难免有些活的太潇洒，于是还是需要写些代码，看些书来收收心，另外新的一年开始了，也该对“懒”开刀了，准备养成写博客这一及其装逼的技能，祝各位同行新年快乐！（开始写的的时候还是大年初一，发布的时候过期了可别怪我）
KNN是机器学习中最简单，最基础的算法之一，算法实现起来没什么难度，但是它的使用范围依然十分广泛，比如书中提到的电影的分类，婚姻网站的配偶分类，手写识别系统，和轨迹预处理中选择候选轨迹等。
二、KNN介绍
2.1监督学习和非监督学习
监督学习：利用一组已知类别的样本调整分类器的参数，使其达到所要求性能的过程，也称为监督训练或有教师学习
举个例子，教婴儿学习的时候，过来一只鸡，就让他叫鸡，过来一只鸭子的时候就让他叫鸭子，教会了一会，随便找一些鸡和鸭子他就能分辨了。这就是监督学习
无监督学习：其中很重要的一类叫聚类
举个例子，过来两种动物（假设还是鸡和鸭子，但是婴儿不知道），然后他根据动物的相像程度把动物分成两群
2.2欧几里得距离
这个在论文中经常能见到，它是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
n维下的两个点的欧氏距离：
　　两个点 A = (a[1]，a[2]，…，a[n]) 和 B = (b[1]，b[2]，…，b[n]) 之间的距离 ρ(A，B)
　 定义为下面的公式：ρ(A，B) =√ [ ∑( a[i] - b[i] )^2 ] (i = 1，2，…，n)
2维下就是最常见的距离公式了 sqrt( (x1-x2)^2+(y1-y2)^2 )了
2.3KNN算法介绍
KNN属于监督学习，他需要一个训练集来训练，然后才能对后面给出的东西（测试集）进行分类。
通俗的过程:
1.通过训练集训练它，如上图，红色和蓝色就是训练集，他们的类别是已知的，于是现在来了一个未知的东西
（标为绿色），希望通过knn来给它分类，看应该是属于蓝色的还是红色的。
2.计算所有红色点和蓝色点到绿点的距离
3.排序找到最近的k个，上图中实线表示k取3（即取距离最近的三个点），同理虚线表示k取5
4.这k个里面哪个类别的东西多，就判断这个绿色点是属于哪一类的。如果上图看实线，红的比蓝的多那么
绿点画为红的，如果是虚线，则标为蓝的
代码我自己用了C++风格的python写了一遍，也就是说不用矩阵计算，那些矩阵被我当作多维数组来用了，代码写的很粗糙，未优化，望见谅。
另外还要再说明一个知识点–归一化&
这个很常见，数学课上也讲过就是把数值缩小到0-1之间，这里是把训练集中的样本数据归一化，使用的公式是newValue=（oldValue-min）/（max-min）
# -*- coding: UTF-8 -*-
2 from numpy import *
3 from math import *
7 class Student(object):
def __init__(self, distance, label):
self.distance = distance
self.label = label
13 #KNN算法
14 def classify0(inX, dataSet, labels, k):
size=shape(dataSet)
line=size[0]
column=size[1]
# print (inX)
if(len(inX)!=column):
print(&unequal！！&)
23 #计算当前项inX与其余训练集的欧氏距离
disList=[]
for i in range(line):
for j in range(column):
sum+=(inX[j]-dataSet[i,j])**2
tmp=Student(sqrt(sum),labels[i])
disList.append(tmp)
32 #排序：欧氏距离从小到大
disList.sort(lambda x,y:cmp(x.distance,y.distance))
35 #取k项判断分类
for item in disList:
if(index==k):
index+=1
if(dict.has_key(item.label)):
dict[item.label]+=1
dict[item.label]=1
dict=sorted(dict.iteritems(),key=lambda d:d[1],reverse=True)
#返回最可能的值
return dict[0][0]
51 # 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)
print sortedClassCount[0][0]
return sortedClassCount[0][0]
67 #读取数据
68 def file2matrix (filename):
fr=open(filename)
lines=fr.readlines()
totalCnt=len(lines)
totalCol=len(lines[0].strip().split('\t'))
resultMatrix=zeros((totalCnt,totalCol-1))
labelMatrix=[]
for line in lines:
tmp=line.strip().split('\t')
resultMatrix[index,:]=tmp[0:totalCol-1]
labelMatrix.append((tmp[-1]))
index+=1
return resultMatrix,labelMatrix
86 # def file2matrix(filename):
fr=open(filename)
arrayOlines=fr.readlines()
numberOfLines=len(arrayOlines)
returnMat=zeros((numberOfLines,3))
classLabelVector=[]
for line in arrayOlines:
line=line.strip()
listFromLine=line.split('\t')
returnMat[index,:]=listFromLine[0:3];
classLabelVector.append((listFromLine[-1]))
index+=1
return returnMat,classLabelVector
102 #归一化处理
newValue=（oldValue-min）/（max-min）
103 def autoNorm(dataSet):
size=shape(dataSet)
line=size[0]
column=size[1]
min=zeros((1,column))
max=zeros((1,column))
# print min
for value in dataSet[0,:]:
min[0,index]=value
max[0,index]=value
index+=1
116 #求每一列的最小值和最大值
for i in range(line):
for j in range(column):
if(i==0 and j==0):
if(dataSet[i,j]&max[0,j]):
max[0,j]=dataSet[i,j]
if(dataSet[i,j]&min[0,j]):
min[0,j]=dataSet[i,j]
ranges = max-min
# print ranges
result=zeros((line,column))
for i in range(line):
for j in range(column):
result[i,j]=(dataSet[i,j]-min[0,j])/ranges[0,j]
return result,ranges,min
137 # def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
print ranges
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1))
#element wise divide
return normDataSet, ranges, minVals
150 def datingClassTest():
hoRatio = 0.50
#hold out 10%
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
#load data setfrom file
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))
print errorCount
165 datingClassTest()
四、代码以及测试数据的下载
/wlmnzf/Machine-Learning-train/tree/master/KNN
1.《机器学习实战》这本书写的不错，值得学习
2.百度百科提供的图片和解释也不能忘
3.[《什么是无监督学习》 知乎](/question/)
4.感谢 网易云音乐 《拯救》-成龙
& 扫码或者搜索 “会打代码的扫地王大爷”&关注公众号
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：35824次
排名：千里之外
原创：31篇
评论：18条
微博：/u/ 公众平台：会写代码的扫地王大爷
(1)(1)(1)(4)(4)(2)(1)(1)(1)(1)(1)(2)(1)(1)(5)(2)(2)(2)馆藏&21827
TA的最新馆藏[转]&5898人阅读
机器学习（36）
1：简单概念描述
&&&&&& Adaboost是一种弱学习算法到强学习算法，这里的弱和强学习算法，指的当然都是分类器，首先我们需要简单介绍几个概念。
1：弱学习器：在二分情况下弱分类器的错误率会低于50%。其实任意的分类器都可以做为弱分类器，比如之前介绍的KNN、决策树、Na?ve Bayes、logiostic回归和SVM都可以。这里我们采用的弱分类器是单层决策树，它是一个单节点的决策树。它是adaboost中最流行的弱分类器，当然并非唯一可用的弱分类器。即从特征中选择一个特征来进行分类，该特征能使错误率达到最低，注意这里的错误率是加权错误率，为错分样本(1)与该样本的权重的乘积之和(不明白看后面代码)。
更为严格点的定义：
强学习：一个概念如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么，这个概念是强可学习的；
弱学习：一个概念如果存在一个多项式的学习算法能够学习它，并且学习的正确率仅比随机猜测略好(高于50%)，那么，这个概念是弱可学习的；
强可学习与弱可学习是等价的。并且理论证明可以将若干个弱学习分类器通过线性叠加提升为强学习分类器。
2：强学习器：识别准确率很高并能在多项式时间内完成的学习算法
3：集成方法：就是将不同的分类器组合在一起，这种组合的结果就是集成方法或者称为元算法。它可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集的不同部分分配给不同分类器后的集成。
4：通常的集成方法有bagging方法和boosting方法，adaboost是boosting的代表算法，他们的区别在于：bagging方法(bootstrapaggregating)，中文为自举汇聚法，是从原始数据集重选择(有放回，可以重复)得到S个新数据集的一种技术，每个新数据集样本数目与原数据集样本数目相等，这样就可以得到S个分类器，再对这S个分类器进行叠加，他们的权重都相等(当然这里S个分类器采用的分类算法不一样的话，可以考虑使用投票)，这样就可以得到一个强学习器。
而boosting方法是通过集中关注被已有分类器错分的那些数据来获得新的分类器，boosting算法中分类的权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。这里不是太明白的话，看完后面adaboost算法就会明白这句话的含义。
5：adaboost算法：机器学习实战这本书上的描述和论文中的描述是一致的，见下面(前两幅是书中描述，后一副是论文中描述)。
问题：上题中的alpha为什么是这个公式呢？解释为：-----再看没看懂！！
2:python代码的实现
(1)&&&基于单层决策树构建分类器
def loadSimDat():
dataMat = matrix([[1, 2.1],
[2.0, 1.1],
[1.3, 1.0],
[1.0, 1.0],
[2.0, 1.0]])
classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
return dataMat, classLabels
# 单层决策树生成函数
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
retArray = ones((shape(dataMatrix)[0],1))
if threshIneq == 'lt':
retArray[dataMatrix[:,dimen] &= threshVal] = -1.0
retArray[dataMatrix[:,dimen] & threshVal] = -1.0
return retArray
def buildStump(dataArr, classLabels, D):
dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
m,n = shape(dataMatrix)
numSteps = 10.0; bestStump = {}; bestClassEst = mat(zeros((m,1)))
minError = inf
for i in range(n):
rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
stepSize = (rangeMax - rangeMin)/numSteps
for j in range(-1, int(numSteps)+1):
for inequal in ['lt','gt']:
threshVal = (rangeMin + float(j)*stepSize)
predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
errArr = mat(ones((m,1)))
errArr[predictedVals == labelMat] = 0
weightedError = D.T * errArr
#这里的error是错误向量errArr和权重向量D的相应元素相乘得到的即加权错误率
#print &split: dim %d, thresh %.2f, thresh inequal: %s, the weighted error is %.3f& %(i, threshVal, inequal, weightedError)
if weightedError & minError:
minError = weightedError
bestClassEst = predictedVals.copy()
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
return bestStump, minError, bestClassEst
注意这里有三层循环构建了单层决策树，最外层循环为遍历特征，次外层循环为遍历的步长，最内层为是否大于或小于阀值。构建的最小错误率为加权错误率，这就是为什么增加分错样本的权重，因为分错样本的权重增加了，下次如果继续分错，加权错误率会很大，这就不满足算法最小化加权错误率了。此外，加权错误率在每次迭代过程中一定是逐次降低的。。
(2)&&&完整adaboost算法
# 基于单层决策树的adaboost训练过程
def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
weakClassArr = []
m = shape(dataArr)[0]
D = mat(ones((m,1))/m)
aggClassEst = mat(zeros((m,1)))
for i in range(numIt):
bestStump, error, classEst = buildStump(dataArr, classLabels, D)
# print &D:&, D.T
alpha = float(0.5 * log((1.0 - error)/max(error, 1e-16)))
#确保在没有错误时不会发生除零溢出
bestStump['alpha'] = alpha
weakClassArr.append(bestStump)
#print &classEst:&, classEst.T
expon = multiply(-1 * alpha * mat(classLabels).T, classEst)
#乘法用于区分是否正确或者错误样本
D = multiply(D, exp(expon))
D = D/D.sum()
# 归一化用的
aggClassEst += alpha * classEst
#累加变成强分类器
aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m,1)))
errorRate = aggErrors.sum()/m
print &total error: &, errorRate, &\n&
if errorRate == 0.0: break
return weakClassArr, aggClassEst
注意代码中的一个技巧max(error,le-16)用于确保在没有错误时不会发生除零溢出。
(3)&&&测试算法：基于adaboost的分类
#adaboost分类函数
def adaClassify(datToClass, classifierArr):
dataMatrix = mat(datToClass)
m = shape(dataMatrix)[0]
aggClassEst = mat(zeros((m,1)))
for i in range(len(classifierArr)):
classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])
aggClassEst += classifierArr[i]['alpha']*classEst
print aggClassEst
return sign(aggClassEst)
3:案例—从疝气病症预测病马的死亡率
# 案例-通过马疝病预测马的死亡率
def loadDataSet(fileName):
#general function to parse tab -delimited floats
numFeat = len(open(fileName).readline().split('\t')) #自动检测特征的数目
dataMat = []; labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr =[]
curLine = line.strip().split('\t')
for i in range(numFeat-1):
lineArr.append(float(curLine[i]))
dataMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return dataMat,labelMat
注意上图中会发现在错误率达到了一个最小值之后又开始上升，这种现象称之为过拟合现象。
此外如何理论上证明弱学习分类器可以通过线性叠加提升为强学习分类器，有两种证明方法：(1)通过误差上界，(2)通过adaboost的损失函数来证明。推导看以参看：http://blog.csdn.net/v_july_v/article/details/， 其中我只看了误差上界的推导。
误差上界的结论表明，AdaBoost的训练误差是以指数速率下降的。另外，AdaBoost算法不需要事先知道下界γ，AdaBoost具有自适应性，它能适应弱分类器各自的训练误差率 。
只要保证弱分类器的错误率小于0.5，每次e^(2Mr^2))肯定是不断减小的
注明：1：本笔记来源于书籍&机器学习实战&
2：参考blog：http://blog.csdn.net/haidao2009/article/details/7514787
作者：小村长 &出处：&欢迎转载或分享，但请务必声明文章出处。 （新浪微博：小村长zack, 欢迎交流！）
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：697627次
积分：8392
积分：8392
排名：第1883名
原创：160篇
转载：32篇
评论：267条
文章：15篇
阅读：102466
文章：16篇
阅读：148265
(2)(1)(1)(1)(1)(4)(14)(13)(34)(13)(5)(8)(4)(3)(4)(6)(7)(6)(1)(1)(4)(9)(19)(5)(8)(1)(6)(6)(6)2375人阅读
模式识别与机器学习（22）
Python（10）
之前学习了k-近邻算法的实现后，参考《机器学习实战》中的例子进行了k-近邻算法的测验，主要测试了针对约会网站和手写识别系统的数据分类，这两个测试使用的是《机器学习实战》提供的数据集。
在编写函数前，需在.py文件中添加以下内容：
from numpy import *
import numpy as np
import operator
from os import listdir
第一部分是针对约会网站的数据分类，用于改进约会网站的配对效果。该实例的简介如下：
海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：
1.不喜欢的人（ 以下简称1 ）；
2.魅力一般的人（ 以下简称2 ）；
3.极具魅力的人（ 以下简称3 ）
尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会哪些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好的帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。
这里提取一下这个案例的目标：根据一些数据信息，对指定人选进行分类（1或2或3）。为了使用kNN算法达到这个目标，我们需要哪些信息？前面提到过，就是需要样本数据，仔细阅读我们发现，这些样本数据就是“海伦还收集了一些约会网站未曾记录的数据信息 ”。
针对以上的描述，需要进行以下步骤：
设计算法分析数据
1.收集数据
海伦收集的数据是记录一个人的三个特征：每年获得的飞行常客里程数；玩视频游戏所消耗的时间百分比；每周消费的冰淇淋公升数。数据是txt格式文件，如下图，前三列依次是三个特征，第四列是分类（1：代表不喜欢的人，2：代表魅力一般的人，3：代表极具魅力的人），每一行数据代表一个人。
2.准备数据
计算机需要对数据文件txt读取数据，因此需要把数据进行格式化，对于数学运算，计算机擅长把数据存放在矩阵中。以下代码中file2matrix(filename)函数完成了这一工作，该函数输入数据文件名（字符串），输出训练样本矩阵和类标签向量。
这一过程返回两个矩阵：一个矩阵用于存放每个人的三个特征数据，一个矩阵存放每个人对应的分类。
3.设计算法分析数据
k-近邻算法的思想是寻找测试数据的前k个距离最近的样本，然后根据这k个样本的分类来确定该数据的分类，遵循“多数占优”原则。因此，如何寻找样本成为主要的问题，在信号处理和模式识别领域中，常常使用“距离”来度量信号或特征的相似度。在这里，我们假定可以使用三个特征数据来代替每个人，比如第一个人的属性我们用[40920， 8.326976， 0.953952]来代替，并且他的分类是3。那么此时的距离就是点的距离。
求出测试样本与训练样本中每个点的距离，然后进行从小到大排序，前k位的就是k-近邻，然后看看这k位近邻中占得最多的分类是什么，也就获得了最终的答案。这一部分是k-近邻算法的核心，代码中classify()函数就实现了k-近邻算法的核心部分。
一个优化算法效果的步骤——归一化数据：
打开数据文件我们可用发现第一列代表的特征数值远远大于其他两项特征，这样在求距离的公式中就会占很大的比重，致使两个样本的距离很大程度上取决于这个特征，其他特征的特性变得可有可无，这显然有悖于实际情况。因此通常我们可用使用归一化这一数学工具对数据进行预处理，这一处理过后的各个特征既不影响相对大小又可以不失公平。Normalize(data)函数实现了这一功能。
4.测试算法
经过了对数据进行预处理后、归一化数值，可用验证kNN算法有效性，测试代码为：WebClassTest() 由于数据有1000条，我们设置一个比率ratio = 0.1 也就是令 1000 * ratio = 100 条作为测试样本，其余900条作为训练样本，当然，ratio的值可用改变，对算法效果是有影响的。
实现代码：
def classify(data, sample, label, k):
SampleSize = sample.shape[0]
DataMat = tile(data, (SampleSize, 1))
delta = (DataMat - sample)**2
distance = (delta.sum(axis = 1))**0.5
sortedDist = distance.argsort()
classCount = {}
for i in range(k):
votedLabel = label[sortedDist[i]]
classCount[votedLabel] = classCount.get(votedLabel, 0) + 1
result = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)
return result[0][0]
def file2matrix(filename):
fil = open(filename)
fileLines = fil.readlines()
lenOfLines = len(fileLines)
Mat = zeros((lenOfLines, 3))
classLabel = []
for line in fileLines:
line = line.strip()
listFromLine = line.split('\t')
Mat[index,: ] = listFromLine[0:3]
classLabel.append(int(listFromLine[-1]))
index += 1
return Mat, classLabel
mat,label = file2matrix('datingTestSet2.txt')
import matplotlib
import matplotlib.pyplot as plt
fil = open('datingTestSet2.txt')
fileLines = fil.readlines()
lenOfLines = len(fileLines)
figure = plt.figure()
axis = figure.add_subplot(111)
lab = ['didntLike', 'smallDoses', 'largeDoses']
for i in range(3):
for j in range(lenOfLines):
if label[j] == i + 1:
n.append(list(mat[j,0:3]))
l.append(label[j])
n = np.array(n)
axis.scatter(n[:,0], n[:,1], 15.0*array(l), 15.0*array(l), label = lab[i])
print type(mat)
print type(n)
plt.legend()
plt.show()
def Normalize(data):
minValue = data.min(0)
maxValue = data.max(0)
ValueRange = maxValue - minValue
norm_data = zeros(shape(data))
k = data.shape[0]
norm_data = data - tile(minValue, (k, 1))
norm_data = norm_data / tile(ValueRange, (k, 1))
return norm_data, ValueRange, minValue
def WebClassTest():
ratio = 0.1
dataMat, dataLabels = file2matrix('datingTestSet2.txt')
normMat, ValueRange, minValue = Normalize(dataMat)
k = normMat.shape[0]
num = int(k * ratio)
errorCount = 0.0
for i in range(num):
result = classify(normMat[i,:], normMat[num:k,:],\
dataLabels[num:k], 7)
print "The classifier came back with: %d, the real answer is %d"\
% (result, dataLabels[i])
if (result != dataLabels[i]): errorCount += 1
print "The total error rate is %f " % (errorCount / float(num))
WebClassTest()
在程序设计过程中，需要注意list、array、adarray等数据结构的使用，numpy.ndarray和标准Python库类array.array功能是不相同的。以上代码中print type(mat)和print type(n) 就是为了观察各变量的类型。允许以上代码，可用画出散点图如下：
以上散点使用数据集中第二维和第三维数据绘制而出，当然，你可用选择其他维度的数据画二维散点图，或者使用所有维度的数据画高维图（未实现），如下图所示：
对约会网站分类的测试，由于分类效果依赖于参数k和测试样本占样本数目的比例，开始测试按照书中的参数进行，取k=3，测试样本占总样本比例为0.1进行测试，结果如下：
理论上来说，增大k的取值可以提高准确率，但实际上若k值太大，也会造成准确率下降，而且运算复杂度增大。
另一方面，降低ratio值（即增大训练样本集的比率）也可以提高算法的准确率，但由于每次算法需要比较更多的样本，因此算法复杂度也会增加。
第二部分是手写数字识别：
首先来看看书本给出的数据集：
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
def handwritingClassTest():
hwLabels = []
trainingFileList = 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 = 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 = classify(vectorUnderTest, trainingMat, hwLabels, 3)
print "The classifier came back with: %d, the real answer is: %d"\
% (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount = errorCount + 1.0
print "\nThe total number of errors is: %d" % errorCount
print "\nThe total error rate is: %f" % (errorCount/float(mTest))
handwritingClassTest()
一个结果（k = 3）：
k = 7时的结果，正确率并不比k = 3时要好：
在手写数字识别过程中，随着k值得增大，准确率反而降低了。k的取值并不是越大越好。
至此，完成了k-近邻算法的学习和实例验证。比起其他机器学习方法，k-近邻算法是最简单最有效的分类数据算法，使用算法时必须有接近实际数据的训练样本数据。但是如前一节所说的，该算法的缺点也很多，最大的一点是无法给出数据的内在含义。事实上k决策树是k-近邻算法的优化版本，比起前者，决策树有效减少了储存空间和计算空间的开销，后期需继续深入学习！
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：468520次
积分：8205
积分：8205
排名：第1943名
原创：248篇
评论：247条
阅读：8032
文章：146篇
阅读：177870
阅读：19195
阅读：5478
文章：11篇
阅读：55702
阅读：18392
文章：23篇
阅读：71934
(7)(10)(6)(18)(26)(26)(21)(29)(29)(9)(11)(7)(8)(8)(22)(10)(7)(3)