Python程序设计基础 Chap13 程序开发进阶.pdf

内衮提纲13.1 分治算法.O13.2 莺尾花的分类.-.O13.3 设讨分类算法.-.-.O13.4 详细设计.O13.5 其他有趣的算法问题O13.1分澹算法:什么是分治策略将一些大问题分解成很多的小问题，小问题的解决应 该是比较容易了，当这些小问题都得到了解决，那么,大问题也就迎刃而解了。使用分治策略时，主要采用自顶向下，逐步细化的原 则来进行程序设计。自顶向下设计是从顶层开始描述 问题的解决方案，把大问题分解成一个个小问题。小 问题不需要立刻进行编程或者解决，而是以函数的形 式把它们描述出来，等到大问题分解完成之后，再一 步步对这些小问题（函数）进行编程。13.2卷尾龙的分类:莺尾花数据集的数据主要由五个维度组成，分别 是花萼长度、花萼宽度、花瓣长度、花瓣宽度、莺尾花的种类。:前4维主要是莺尾花的特征项，后一维是莺尾花的 种类项。殳莺尾花有三个种类，分别代表山莺尾(seto sa)、变色莺尾(ver sico lo r)和维吉尼亚莺尾(vir ginica）。山莺尾(setosa)变色莺尾(versicolor)图13-1 三种莺尾花川维吉尼亚莺尾(virginica):我们的问题是，能否编写一个机器自动识别程序,只要录入前4维的特征项，机器就能根据前4维 的特征项来判定莺尾花的种类？KNN(K-NearestNeighbor)算法介绍:.KNN算法，简称邻近算法，它是数据挖掘分类技术 中最简单的方法之一。:所谓K最近邻，就是K个最近的邻居的意思，说的 是每个样本都可以用它最接近的K个邻居来代表。KNN(K-NearestNeighbor)算法介绍最近邻分类算法思路 是：如果一个样本在 特征空间中的K个最相 似（即特征空间中最邻 近）的样本中的大多数 属于某一个类别，则 该样本也属于这个类 别。图13-2 KNN分类示意图K个最近邻居:欧氏距离计算 是一个通常采用的距离 定义，指在m维空间中两 个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）e（x,=%）2 其中，/表飘数。K是可以调节的，一般来 说应该是个单数:莺尾花数据集共有150条数据，其中山莺尾、变色 莺尾、维吉尼亚莺尾三种类型的记录各占50条。我 们选取2/3的数据作为样本数据，1/3的数据作为测 试数据。可以通过人工选取的方法来选择样本，也 可以随机选取样本。:样本越多，维数越多，计算量就越大，因为每一个 测试数据都要与每一个样本进行距离计算，而每个 样本的计算量又和样本的维数相关。然后再选取K 个最近的数据，才能确定测试数据的类型。:自然语言描述算法(1)从文件中创建训练数据集和测试数据集。-(2)让每个测试数据进行训练，得到预测的类型。计算测试数据与所有训练数据集的距离。获得k个最近的邻居，并预测自己的类型。(3)打印预测类型与实际类型。(4)用预测的类型与实际数据进行比较，查看分类算 法的正确率。程序对算法的描述 y11-def mainOw2 trainings et=#训练集数据列表一3 testSet二口#测试数据列表一a split=0.67#训练与测试数据集的分段值，意味着2/3为训练数据集，1/3为测试数据集5 loadDatasetCe:iris.txt,split,trainingSet,testSet)6 printfTrain set:*+repr(len(trainingSet)#获得训练集的数据-printfTest set:*+repr(len(testSet)#获得测试的数据&predictions二口#预测数据列表910 for i in range(len(testSet):#让每一个测试数据进入分类器进行分类一neighbors=getNeightbors(trainingSet,testSeti,k)12 result=getResponse(neighbors)-13 predictions,append(res ult)#把分类的结果加入预测列表一14.一15#把分类的结果与实际结果打印出来”16 pint(predicted=+rep(es ult)+,actual=+rep(testsaccuracy=getAccuracy(t estSet,predictions)一17 print(,Accuracy:,+repr(accuracy)+,%t)算法描述:定义了三个列表：tr ainingSet、testSet pr edictio nso:定义了四个函数：lo adDataset、getNeightbo r s、getRespo nse、getAccur acyo1#打开文件，并把文件的内容加载到数据集之中2-def lo adDataset(filename,split5tr ainingSet=5testSet=):3-#没有返回结果，通过参数tr ainingSet和testSet返回结巢4#获得训练集中所有实例与测试实例之间的最短距离，选择k个最接近的邻居，加入到neighbo r s列表中：5-def getNeightbo r s(tr ainingSet5testlnstance5k):6-r etur n 7.#从K个邻居中找出类型最多的那种，从而确定测试实例属于哪一种类型8-def getRespo nse(neighbo r s):9-r etur n 10-#计算KNN正确率11 def getAccur acy(testSet,pr edictio ns):12-r etur na#定义主函数14-def main():文件格式属 性最大值最大值平均值1sepal length in cm4.37.95.842sepal width in cm2.04.43.053petal length in cm1.06.93.764petal width in cm0.12.51.205Class(分成三种)Iris setosa、Iris versicoloury Iris virginica其中前4维分别代表莺尾花的萼片长、宽，花瓣的长、宽。第5维代表的是 类型，分别代表山莺尾(setosa)、变色莺尾(versicolor)、维吉尼亚莺 尾(virginica)。数据共150条，如下图13-4所示原始数据5.1,3-5,1.4,0.2 Jris-setosa4.93-0.1.4,0.2 Jris-setosa4.793-2,1.3,0.2 Jris-setosa 7.0,3.2,4.7.41ris-versicolor6.4,3.294.591.5 Jris-versicolor6.93-1,4.9,1.5 Jris-versicolor 63,3.3,60,2.5ris-virgiiiica5.8,2.7511.9 Jris-virginica7.13-0.5.9,2.1 Jris-virginica/oadOataset 函数:/。2。2七5家函数的作用是打开文件，并把莺尾花 的记录通过分拣工作，分别放入a/c/cgSe环口 festSef两个数据集中。:函数中有四个参数，分别是打开文件、split.trainingSet.testSeto:没有返回结果，但是能通过两个列表把结果带出 来。/oadOataset 函数:算法思想。(D打开文件。在做测试的时候，应该要确保文件是 存在的，如果文件名不存在，需要给用户提示。目前,我们假设文件是存在的，出错检查部分在后续的工 作中再完善。(2)把文件中所有的记录的加入dataset中。(3)把文件中的14的数据进行处理，变成可计算的 浮点型。(4)通过一个随机数进行分拣，分别放入trainingSet、招stS中，通常训练集与测试集的数据比例为2:1。getNeightborsM*getNeightbors函数是获得训练集中所有实例与 测试实例之间的最短距离，并选择K个最接近的 邻居，加入到neighbo r s列表中。这个函数在整个 程序的核心，它的计算量最大，获得最原始的数 据。:函数的算法如下。(1)获取一个测试用例，用于以下操作。通过欧几里德函数的计算，得到每一个训练集中实例 与测试实例的最路径。把数据加入distance列表中。(2)对distance列表进行排序，得到一个按从小到大 的排序列表。(3)获得k个最近邻居实例。ge出espo use函数是从k个邻居中找出类型最多的 那种，从而确定测试实例属于哪一种类型。采用 的方法是利用字典来记录每种类型的邻居有多少 个，比如字典中有如下的数据/s-seto sa：1,Iris-versicolor：2,再对字典而Key值进行排序，得到一个按key值大小排列的列表（7s wer s/cH。，,Iris-setosa）,那么测试实例就应该/swes/co/o r 这种类型。:算法如下：(1)遍历每个ae/g/7bBs中的每一个训练实例。获取每个实例的类型；查看这种类型是否存在于字典中：-a)如在字典中，类型值加1-b)如不在字典中，类型值为1(2)对字典以g/ue值进行从大到小排序，获得测试实 例的类型。getAccuracy 函数:这个函数主要用于计算KNN算法的正确率。把预 测结果与实际的情况做一下比较，就能确定预测 的正确率了。:程序代码如下：1def getAccur acy(testSet,pr edictio ns):2.3.4.5.6.co r r ect=0fo r i in r ange(len(testSet):if testSeti-1=pr edictio nsi:co r r ect+=1r etur n(co r r ect/flo at(len(testSet)*10 0.0不足之处值的选择这是一个难点，不知道应该选多少，虽然还是有一定的 规则，但是选多选少是会影响到准确率的。这与KNN算 法的局限性有关。回到13.3.1节中，当k=3时，未知圆应 该归于三角形这一类；当k=5时，未知圆却要归于四方 形这一类了。显示，k值的不同会很大影响到测试类型。:如何改进可以采用权值的方法（和该样本距离小的邻居权值大）来改进，从图13-2中，可以看出，由于未知圆在距离三 角形最近（距离小的权值大），所以不管M直为多少也改 变不了未知圆的类型。13.5其他有题的算法问题0:乳腺癌分类:葡萄酒品质分类应用实例:乳腺癌分类(br east-cancer-classifier)问题问题描述：(机器学习仓库,很多数据集)http:ar chive.ics.uci.edu/ml 其中的切除肿瘤的数据集，现在希望能否根据肿瘤数据 对其进行判定是恶性的(malignant)还是良性的(benign)数据集有如下9个肿瘤属性，可以做成9个类别。（j uvuSq vui jqj/以lunq joj 乙）0 1-1 0 1-I 0 1-1 0 1-I 0 1-1 0 1-1 0 1-1 0 1-I 0 1-1 j nq iunu piUIEUIOQSSE【On o iS3SOJipijopnu eiujon 6UUELUOJip puEj g ginpnu9ZTS ipo r eipq j ido 艰ui uo is叫pe 心11但叫 ndeq s j pD j o Xjrujoiuq ms j pD j o Xj nuj o puQ ss u Diip dumj 2）j q iunu 叩co nj diUESL 9 C V ojnqijjjy#问题描述:数据集如下所示：1000025,5,1,1,1,2,1,3,1,1,2 1002945,5,4,4,5,7,10,3,2,1,2 1015425,3,1,1,1,2,2,3,1,1,2 1016277,6,8,8,1,3,4,3,7,1,2 1017023,4,1,13,2,1,3,1,1,2 1017122,8,10,10,8,7,10,9,7,1,4 1018099,1,1,1,1,2,10,3,1,1,2问题描述:数据集如下所示：(,10 0 0 0 25,b,5,1,1,1,2,1,3,1,1)(,10 0 294 5,b,5,4,4,5,7,10,3,2,1)(,10 15 4 25,b,3,1,1,1,2,2,3,1,1)(,10 16 277,b,6,8,8,1,3,4,3,7,1)(,10 170 23,b,4,1,1,3,2,1,3,1,1)(,10 17122,m,8,10,10,8,7,10,9,7,1)(,10 18 0 99,b,1,1,1,1,2,10,3,1,1)(,10 18 5 6 1,b,2,1,2,1,2,1,3,1,1)问题描述:通过研究这些属性，能否找到肿瘤预测模式，根 据肿瘤属性来判定肿瘤性质？:如何实现实现方法:分类给出一定数量的样本，根据样本进行分类，找出良性 与恶性的阈值。实现方法:构造分类器构造方法：在给出的样本中，找到所有的良性肿瘤和恶性肿瘤。并找出良性肿瘤和恶性肿瘤平均值的中值，即阈值。高 于中值的即为恶性肿瘤，低于中值的即为良性。ID:100025Tumor vals:5 11112 13 112Diagnosis:benignID:1017122Tumorvals:8 10 10 8 7 10 9 7 1 4Diagnosis:malignantBenign patientsAverage each characteristicMalignant patientsMalignant averagesBenign averagesAverage of the two averages:设计分类器算法如下：从训练文件中创建训练集 创建分类器，使用训练集中确定每个属性的分类值 从测试文件中创建测试集 使用分类器，对测试集进行分类 同时计算这些判定的准确性Adef main():实现方法*pr int”读取训练数据。”tr ainfile=test_data.txt tr ainingSet=makeTr ainingSet(tr ainfile)pr int”创建分类器”classifier=tr ainClassifier(tr ainingSet)pr int”使用分类器，对测试集进行分类”r esults=classifyTestSet(tr ainingSet,classifier)pr int”计算这些判定的准确性”r epo r tResults(r esults):在电视上经常看到有一些品酒师，只要品一品手 中的葡萄酒便能对酒的产地、品质如何做出评价,真是很神奇。那么，能不能利用机器学习的方 法也实现对葡萄酒质量的评判呢？今天讲一个例 子，只要输入一些数据，计算机也能预测葡萄酒 的质量。葡萄酒品质9J 输入参数，基于物理化学测试信息1fixed acidity（非挥发性酸）2vo latile acidity（挥发性酸）3citr ic acid（咛檬酸）4r esidual sugar（天然残留糖分）5chlo r ides（氯）6fr ee sulfur dio xide（游离二氧化硫）7to tal sulfur dio xide（总二氧化硫）8Density（密度）9P H（酸碱度）10sulphates（硫酸盐）11Alco ho l（酒精含量）输出参数（基于感官数据）1q uality（分值从0到10,10最高）葡萄酒品质 Wine Quality 数据集分为 Red Wine 和 White Wine两种，其中Red Wine有15 99个实例，White Wine有4898个实例。:以下是数据集样本：7.4;0.7;0;1.9;0.076;11;34;0.9978;3.51;0.56;9.4;5 7.8;0.88;0;2.6;0.098;25;67;0.9968;3.2;0.68;9.8;5 7.8;0.76;0.04;2.3;0.092;15;54;0.997;3.26;0.65;9.8;5 11.2;0.28;0.56;1.9;0.075;17;60;0.998;3.16;0.58;9.8;6 7.4;0.36;0.3;1.8;0.074;17;24;0.99419;3.24;0.7;11.4;8:从样本中看出，111项都是描述项，后一项是结 论项。:算法如下：(1)加载样本数据a/c/agSet,加载需预测的数据 testSet；(2)设置K；(3)使用KNN计算预测值，根据KNN算法定义，包 括以下步骤。a.计算需预测数据与所有丁3m77gset中数据的距离。b.找出K个距离最短的点。c.由这K个点决定该预测数据的预测值是多少，由这K 个点投票表决，看这K个点中哪个结果出现的次数最多,那就是它的预测值。