1、第三章k-近邻算法分类问题分类问题 爱情片、剧情片、喜剧片、家庭片、伦理片、文艺片、音乐片、歌舞片、动漫片、西部片、武侠片、古装片、动作片、恐怖片、惊悚片、冒险片、犯罪片、悬疑片、记录片、战争片、历史片、传记片、体育片、科幻片、魔幻片、奇幻片Supervised learning提纲 KNN算法原理和流程 Python程序调试 Python文件类型 模块 Idle调试环境 数据载入 算法和关键函数分析 算法改进和实验作业K-Nearest Neighbors算法原理?Dependent of the data distributions.Can make mistakes at boundar
2、ies.K=7 NeighborhoodK=1 NeighborhoodK-Nearest Neighbors算法特点 优点 精度高 对异常值不敏感 无数据输入假定 缺点 计算复杂度高 空间复杂度高 适用数据范围 数值型和标称型K-Nearest Neighbors Algorithm 工作原理 存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，只选择样本数据集中前N个最相似的数据。K
3、一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类K近邻算法的一般流程 收集数据：可以使用任何方法 准备数据：距离计算所需要的数值，最后是结构化的数据格式。分析数据：可以使用任何方法 训练算法：（此步骤kNN）中不适用 测试算法：计算错误率 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。距离度量 Lp距离：欧式距离：曼哈顿距离 L距离距离度量K值的选择 如果选择较小的K值“学 习”的近似误差（approximation error)会减小，但“学习”的估计误差（estimation e
4、rror)会增大，噪声敏感 K值的减小就意味着整体模型变得复杂，容易发生过 拟合.如果选择较大的K值，减少学习的估计误差，但缺点是学习的近似误差会增大.K值的增大 就意味着整体的模型变得简单.Python程序调试 Python传统运行模式：Python解释器：运行Python程序的程序；Python字节码：Python将程序编译后所得到的底层形式；Python自动将字节码保存为名为.pyc的文件中；录入的源码转换为字节码-字节码在PVM（Python虚拟机）中运行-代码自动被编译，之后再解释m.pym.pycPVM源代码字节码运行时Python程序调试 Python无“build”和“make
5、”的步骤，代码写好后立即运行 Python字节码不是机器的二进制代码（so 不能像C+运行速度那么快，其速度介于传统编译语言和传统解释语言之间）raw_input（）的使用Python模块 每一个.py文件都是一个模块，其他文件可以通过导入一个模块读取这个模块的内容，相当于C中的include 一个大型程序往往呈现出多模块的形式。其中一个模块文件被设计为主文件（or顶层文件）。模块是Python程序最大的程序结构 每个模块文件是一个独立完备的变量包装，即一个命名空间模块的导入 import，from 和 reload import语句将模块作为一个整体引用，相当于引入一个类的object。Fr
6、om 增加了对变量名的额外赋值，也就是拷贝模块的属性，因此能够以主模块导入，而不是原来的对象 例子：A=“this”B=“is”C=“test”Print A，B，C Import test1 Test1.A From test import*AReload和重编译 修改文件如kNN注意 Reload（）或者：重新编译 import py_compile py_pile(D:pythonmachinelearninginactionCh02kNN.py)最好不要用中文，如果需要，用编码转换工具codecIdle调试环境 Idle 的使用：Copy的结果是什么？For语句 Reload的好处 修
7、改程序，显示修改时间 Import 和from A import*的关系 空间，如numpyPython导入数据 import os os.getcwd()D:python os.chdir(D:pythonmachinelearninginactionCh02)os.getcwd()D:pythonmachinelearninginactionCh02 open(.testDigits0_0.txt)Python导入数据 from numpy import*import operator def createDataSet():group=array(1.0,1.1,1.0,1.0,0,0,
8、0,0.1)labels=A,A,B,Breturn group,lables group,labels=kNN.createDataSet()算法和关键函数分析 分类算法流程和关键函数 Shape Tile Argsort 字典的使用 文本中解析数据 文件读取相关函数 用matplotlib绘制散点图 数据归一化 使用k-近邻算法的手写识别系统分类算法流程 对未知类别的数据集中的每个点依次执行以下操作 计算已知类别数据集众多点与当前点之间的距离 按照距离递增次序排序 选取与当前点距离最小的k个点 群定前k个点所在类别的出现频率 返回前k个点出现频率最高的类别作为当前点的预测分类分类算法kNN
9、中的分类算法：def classify0(inX,dataSet,labels,k):dataSetSize=dataSet.shape0 diffMat=tile(inX,(dataSetSize,1)-dataSet sqDiffMat=diffMat*2 sqDistances=sqDiffMat.sum(axis=1)distances=sqDistances*0.5 sortedDistIndicies=distances.argsort()classCount=for item in range(k):voteIlabel=labelssortedDistIndiciesitem
10、classCountvoteIlabel=classCount.get(voteIlabel,0)+1 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)return sortedClassCount00Shape函数 group,labels=kNN.createDataSet()group.shape group.shape0Tile函数tile(1.0,1.2,(4,1)array(1.,1.2,1.,1.2,1.,1.2,1.,1.2)tile(1.0,1.2,(
11、4,1)-grouparray(0.,0.1,0.,0.2,1.,1.2,1.,1.1)a=(tile(1.0,1.2,(4,1)-group)*2array(0.,0.01,0.,0.04,1.,1.44,1.,1.21)Argsort（）b=a.sum(axis=1)c=b*0.5 d=c.argsort()d array(0,1,3,2)字典的使用 classCount=#字典 for i in range(k):#列表的扩展 voteIlabel=labelssortedDistIndiciesi classCountvoteIlabel=classCount.get(voteIlab
12、el,0)+1 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)return sortedClassCount00 kNN.classify0(0,0.2,group,labels,3)B从文本文件中解析数据-打开文件 def file2matrix(filename):fr=open(filename)numberOfLines=len(fr.readlines()#get the number of lines in the file returnMat=zeros
13、(numberOfLines,3)#prepare matrix to return classLabelVector=#prepare labels return fr=open(filename)index=0 从文本文件中解析数据-获得数据 for line in fr.readlines():line=line.strip()listFromLine=line.split(t)截取掉所有回车符号，t分割成列表 returnMatindex,:=listFromLine0:3 classLabelVector.append(int(listFromLine-1)index+=1 retu
14、rn returnMat,classLabelVector文件读取相关函数 Open()的使用 Readlines的使用 Zeros()的使用文件读取相关函数 Open()的使用 工作路径和绝对路径 Readlines的使用 Zeros()的使用 fr=open(test1.txt)for line in fr.readlines():print line 执行a=fr.readlines()a 结果是什么呢？fr.seek(0)a=fr.readlines()文件读取相关函数 a=fr.readlines()a1 3 4 12n,5 7 8 13n,9 10 11 14 b=a0 b1 3
15、4 12n c=b.strip()c1 3 4 12 d=c.split(t)d1 3 4 12 d01 3 4 12 文件读取相关函数 for line in a:line=line.strip()line=line.split()print line 1,3,4,12 5,7,8,13 9,10,11,14文件读取相关函数 for line in a:line=line.strip()line=line.split()print line 1,3,4,12 5,7,8,13 9,10,11,14文件读取相关函数 for line in a:line=line.strip()line=lin
16、e.split()line=int(x)for x in line print line 1,3,4,12 5,7,8,13 9,10,11,14数组和矩阵 Python 数组和numpy矩阵的关系 a=1,2,3,4,5,6,7,8,9,10,11,12 c=zeros(3,4)c array(0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.)c0,:=a0 c array(1.,2.,3.,4.,0.,0.,0.,0.,0.,0.,0.,0.)解析数据 fr=open(datingTestSet.txt)a=fr.readlines()b=len(a)line=a0
17、line=line.strip()list=line.split(t)r0,:=list0:3 r List-1 ClassLat=classLab.append(list-1)classLab使用Matplotlib创建散点图 import matplotlib import matplotlib.pyplot as plt fig=plt.figure()ax=fig.add_subplot(111)ax.scatter(datingDataMat:,1,datingDataMat:,2)plt.show()使用Matplotlib创建散点图 fig=plt.figure()ax=fig.
18、add_subplot(111)ax.scatter(datingDataMat:,1,datingDataMat:,2,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)m=dataSet.shape0 normDataSet=dataSet-tile(minVals,(m,
19、1)normDataSet=normDataSet/tile(ranges,(m,1)#element wise divide return normDataSet,ranges,minVals数据归一化 n,r,m=kNN.autoNorm(datingDataMat)n array(0.44832535,0.39805139,0.56233353,0.15873259,0.34195467,0.98724416,0.28542943,0.06892523,0.47449629,.,0.29115949,0.50910294,0.51079493,0.52711097,0.43665451,
20、0.4290048,0.47940793,0.3768091,0.78571804)r array(9.12730000e+04,2.09193490e+01,1.69436100e+00)m array(0.,0.,0.001156)测试算法：验证分类器 def datingClassTest():hoRatio=0.50#hold out 10%datingDataMat,datingLabels=file2matrix(datingTestSet2.txt)#load data setfrom file normMat,ranges,minVals=autoNorm(datingData
21、Mat)m=normMat.shape0 numTestVecs=int(m*hoRatio)errorCount=0.0 for i in range(numTestVecs):classifierResult=classify0(normMati,:,normMatnumTestVecs:m,:,datingLabelsnumTestVecs:m,3)print the classifier came back with:%d,the real answer is:%d%(classifierResult,datingLabelsi)if(classifierResult!=datingL
22、abelsi):errorCount+=1.0 print the total error rate is:%f%(errorCount/float(numTestVecs)print errorCount使用k-近邻算法的手写识别系统准备数据，将图像转换为测试向量 32x32def img2vector(filename):returnVect=zeros(1,1024)fr=open(filename)for i in range(32):lineStr=fr.readline()for j in range(32):returnVect0,32*i+j=int(lineStrj)retu
23、rn returnVect测试算法 testVector=kNN.img2vector(testDigits/0_13.txt)tesVector0,0:31KNN算法改进和实验作业 KNN面临的挑战 算法改进 距离度量 马氏距离 KD树 实验要求KNN面临的挑战Instance-Based LearningNo explicit description of the target functionCan handle complicated situations.KNN面临挑战 K值确定 Non-monotonous impact on accuracy Too Big vs.Too Sma
24、ll Rule of thumbs 特征的选择 Different features may have different impact 距离函数确定 There are many different ways to measure the distance.Euclidean,Manhattan 复杂度 Need to calculate the distance between X and all training data.In proportion to the size of the training data.KAccuracyDistance Metricskdikiikyxyx
25、L/11,2/1122,diiiyxyxLdiiiyxyxL11,Mahalanobis Distance马氏距离Distance from a point to a point set马氏距离马氏距离(Mahalanobis Distance)由由P.C.Mahalanobis提出提出 基于样本分布的一种距离测量基于样本分布的一种距离测量 考虑到各种特性之间的联系（例如身高考虑到各种特性之间的联系（例如身高和体重），可以消除样本间的相关性和体重），可以消除样本间的相关性 广泛用于分类和聚类分析广泛用于分类和聚类分析一维数据马氏距离马氏距离(Mahalanobis Distance)例：0,8
26、,12,20 8.3 8,9,11,12 1.8均值：标准差：方差：多维向量协方差矩阵协方差矩阵马氏距离马氏距离 定义定义马氏距离马氏距离 定义续定义续马氏距离马氏距离 计算示例计算示例马氏距离马氏距离 NUMPYNUMPY示例示例import numpyx=numpy.array(3,4,5,6,2,2,8,4)xT=x.TD=numpy.cov(xT)invD=numpy.linalg.inv(D)tp=x0 x1print numpy.sqrt(dot(dot(tp,invD),tp.T)Mahalanobis DistancexSxxDTM1)(xxxDTM)(For identity
27、 matrix S:niiiiMxxD122)(For diagonal matrix S:KD树 kd树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形数据结构.Kd树是二叉树，表示对K维空间的一个划分（partition).构造Kd树相 当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域.Kd树的每个结点对应于一个k维超矩形区域.KD树 构造kd树：对深度为j的节点，选择xl为切分的坐标轴 例：KD 树(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)，建立索引KD树搜索作业要求 作业里包含如下文件：源代码（改进部分要有注释），实验报告：包含对改进算法的描述以及实验结果对比情况。给分依据：代码质量（包含可读性），改进算法难度 实验报告的详细性。若有疑惑，可联系助教邱鑫。Q&A？
