搜索
第三章k-近邻算法分类问题分类问题•爱情片、剧情片、喜剧片、家庭片、伦理片、文艺片、音乐片、歌舞片、动漫片、西部片、武侠片、古装片、动作片、恐怖片、惊悚片、冒险片、犯罪片、悬疑片、记录片、战争片、历史片、传记片、体育片、科幻片、魔幻片、奇幻片Supervisedlearning提纲•KNN算法原理和流程•Python程序调试•Python文件类型•模块•Idle调试环境•数据载入•算法和关键函数分析•算法改进和实验作业K-NearestNeighbors算法原理?Dependentofthedatadistributions.Canmakemistakesatboundaries.K=7NeighborhoodK=1NeighborhoodK-NearestNeighbors算法特点•优点•精度高•对异常值不敏感•无数据输入假定•缺点•计算复杂度高•空间复杂度高•适用数据范围•数值型和标称型K-NearestNeighborsAlgorithm•工作原理•存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。•输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。•一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类K近邻算法的一般流程•收集数据：可以使用任何方法•准备数据：距离计算所需要的数值，最后是结构化的数据格式。•分析数据：可以使用任何方法•训练算法：（此步骤kNN）中不适用•测试算法：计算错误率•使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。距离度量•Lp距离：•欧式距离：•曼哈顿距离•L∞距离距离度量K值的选择•如果选择较小的K值•“学习”的近似误差（approximationerror)会减小，但“学习”的估计误差（estimationerror)会增大，•噪声敏感•K值的减小就意味着整体模型变得复杂，容易发生过拟合.•如果选择较大的K值，•减少学习的估计误差，但缺点是学习的近似误差会增大.•K值的增大就意味着整体的模型变得简单.Python程序调试•Python传统运行模式：•Python解释器：运行Python程序的程序；•Python字节码：Python将程序编译后所得到的底层形式；Python自动将字节码保存为名为.pyc的文件中；•录入的源码转换为字节码-字节码在PVM（Python虚拟机）中运行-代码自动被编译，之后再解释m.pym.pycPVM源代码字节码运行时Python程序调试•Python无“build”和“make”的步骤，代码写好后立即运行•Python字节码不是机器的二进制代码（so不能像C++运行速度那么快，其速度介于传统编译语言和传统解释语言之间）•raw_input（）的使用Python模块•每一个.py文件都是一个模块，其他文件可以通过导入一个模块读取这个模块的内容，•相当于C中的include……•一个大型程序往往呈现出多模块的形式。•其中一个模块文件被设计为主文件（or顶层文件）。•模块是Python程序最大的程序结构•每个模块文件是一个独立完备的变量包装，即一个命名空间模块的导入•import，from和reload•import语句将模块作为一个整体引用，相当于引入一个类的object。•From增加了对变量名的额外赋值，也就是拷贝模块的属性，因此能够以主模块导入，而不是原来的对象•例子：•A=“this”•B=“is”•C=“test”•PrintA，B，C•Importtest1•Test1.A•Fromtestimport*•AReload和重编译•修改文件如kNN注意•Reload（）•或者：重新编译•importpy_compile•py_compile.compile('D:\python\machinelearninginaction\Ch02\kNN.py')•最好不要用中文，如果需要，用编码转换工具codecIdle调试环境•Idle的使用：•Copy的结果是什么？•For语句•Reload的好处•修改程序，显示修改时间•Import和fromAimport*的关系•空间，如numpyPython导入数据•importos•os.getcwd()•'D:\\python'•os.chdir('D:\\python\\machinelearninginaction\\Ch02')•os.getcwd()•'D:\\python\\machinelearninginaction\\Ch02'•open('.\\testDigits\\0_0.txt')•openfile'.\\testDigits\\0_0.txt',mode'r'at0x00D1FCD8Python导入数据•fromnumpyimport*•importoperator•defcreateDataSet():•group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])•labels=['A','A','B','B']•returngroup,lables•group,labels=kNN.createDataSet()算法和关键函数分析•分类算法流程和关键函数•Shape•Tile•Argsort•字典的使用•文本中解析数据•文件读取相关函数•用matplotlib绘制散点图•数据归一化•使用k-近邻算法的手写识别系统分类算法流程•对未知类别的数据集中的每个点依次执行以下操作•计算已知类别数据集众多点与当前点之间的距离•按照距离递增次序排序•选取与当前点距离最小的k个点•群定前k个点所在类别的出现频率•返回前k个点出现频率最高的类别作为当前点的预测分类分类算法•kNN中的分类算法：•defclassify0(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={}•foriteminrange(k):•voteIlabel=labels[sortedDistIndicies[item]]•classCount[voteIlabel]=classCount.get(voteIlabel,0)+1•sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)•returnsortedClassCount[0][0]Shape函数•group,labels=kNN.createDataSet()•group.shape•group.shape[0]Tile函数•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],(4,1))-group•array([[0.,0.1],•[0.,0.2],•[1.,1.2],•[1.,1.1]])•a=(tile([1.0,1.2],(4,1))-group)**2•array([[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={}#字典•foriinrange(k):#列表的扩展•voteIlabel=labels[sortedDistIndicies[i]]•classCount[voteIlabel]=classCount.get(voteIlabel,0)+1•sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)•returnsortedClassCount[0][0]•kNN.classify0([0,0.2],group,labels,3)'B'从文本文件中解析数据-打开文件•deffile2matrix(filename):•fr=open(filename)•numberOfLines=len(fr.readlines())#getthenumberoflinesinthefile•returnMat=zeros((numberOfLines,3))#preparematrixtoreturn•classLabelVector=[]#preparelabelsreturn•fr=open(filename)•index=0•从文本文件中解析数据-获得数据•forlineinfr.readlines():•line=line.strip()•listFromLine=line.split(‘\t’)截取掉所有回车符号，\t分割成列表•returnMat[index,:]=listFromLine[0:3]•classLabelVector.append(int(listFromLine[-1]))•index+=1•returnreturnMat,classLabelVector文件读取相关函数•Open()的使用•Readlines的使用•Zeros()的使用文件读取相关函数•Open()的使用•工作路径和绝对路径•Readlines的使用•Zeros()的使用•fr=open('test1.txt')•forlineinfr.readlines():•printline•执行a=fr.readlines()•a•结果是什么呢？•fr.seek(0)•a=fr.readlines()文件读取相关函数•a=fr.readlines()•a•['13412\n','57813\n','9101114']•b=a[0]•b•'13412\n'•c=b.strip()•c•'13412'•d=c.split('\t')•d•['13412']•d[0]•'13412'•文件读取相关函数•forlineina:•line=line.strip()•line=line.split()•printline••['1','3','4','12']•['5','7','8','13']•['9','10','11','14']文件读取相关函数•forlineina:•line=line.strip()•line=line.split()•printline••['1','3','4','12']•['5','7','8','13']•['9','10','11','14']文件读取相关函数•forlineina:•line=line.strip()•line=line.split()•line=[int(x)forxinline]•printline••[1,3,4,12]•[5,7,8,13]•[9,10,11,14]数组和矩阵•Python数组和numpy矩阵的关系•a=[[1,2,3,4],[5,6,7,8],[9