剪枝网格采样的非平衡数据集分类算法.doc

《剪枝网格采样的非平衡数据集分类算法.doc》由会员分享，可在线阅读，更多相关《剪枝网格采样的非平衡数据集分类算法.doc（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流剪枝网格采样的非平衡数据集分类算法.精品文档.摘 要非平衡数据集分类问题是模式识别、机器学习和数据挖掘领域中的常见问题，也是热点问题，吸引着众多学者的眼球。非平衡数据集是指数据集类别之间存在倾斜，某一类别样本比其它类别样本要多。传统分类器为了追求高准确率，侧重于非平衡数据集中的多数类样本分类的准确性。而恰恰相反，非平衡数据集中的少数类样本往往是我们所要关心的，这时分类性能不仅要考虑分类精度高低，同时要考虑分类代价大小。传统分类器对这种非平衡数据的处理会更多关注多数类别的样本，导致大量重要的少数类别的样本错分且真实信息受损。因此，研究非平衡数据

2、处理问题是非常重要。目前，国内外学者在非平衡数据集分类问题上的研究已取得一定的成就，主要表现在数据预处理和算法两大层面上，在算法层面上，主要是试图改进传统算法，提高在非平衡数据集上的分类性能。而在数据预处理层面上，学者们研究大体是对负类样本进行欠采样，去除噪声数据和远离分类面数据，对正类样本过采样，加入噪声数据以至于达到数据平衡，再采用已有分类器进行分类，试图提高准确率。然而，去除数据还是加入数据，不同学者处理的方法也是不同的。本文在前人研究基础上，进一步对处理非平衡数据集分类的采样方法进行研究，防止一般欠采样方法所带来的重要信息数据的丢失，结合园艺工人们培植盆景的技巧，提出一种新的欠采样方法

3、剪枝网格采样方法，通过剪枝技术将多数类样本分类，分成绝对安全数据、边缘数据和噪声数据三类，然后进行网格采样，再利用自适应增强法对采样后数据进行学习。以ROC曲线为评价标准，对人造数据和典型的UCI数据集分别进行验证，其AUC值要大于其他几类算法，说明该模型具有良好的性能。接着，又将该方法和Random-SMOTE方法结合，提出混合采样方法，利用ROC曲线评价标准，通过两组数据对模型进行性能测试，结果发现该模型性能也很优越。关键字：非平衡数据集；剪枝；网格采样；自适应增强法；ROC曲线AbstractImbalanced data sets classification problem is c

4、ommon problems in the field of pattern recognition, machine learning and data mining as well as a hot issue. Imbalanced data set is a data set of categories because of the presence of skew, namely a kind of category samples more than other categories of sample. The traditional classifiers in order t

5、o pursue a high rate of accuracy focus on classification accuracy of the majority class samples of Imbalanced data sets, on the other hand the minority class samples of imbalanced data sets should be considered because of the cost of classification and its true information. Therefore, research of Im

6、balanced data processing problem is very important.At present, domestic and foreign scholars have obtained some achievements in data preprocessing and algorithms of two level about imbalanced data sets classification problem. Scholars are trying to improve the traditional algorithms and improve the

7、classification performance in Imbalanced data set on the algorithm level. In the data pretreatment level, scholars generally remove the negative samples of noise data and separate from the classification of surface data in under-sampling, otherwise they add noise data to over-sampling data in order

8、to balance. In a word , many methods are different on data reduction or data additionIn this paper, new sampling methods about imbalanced data sets classification are considered in order to prevent the important data loss from general under-sampling method on the basis of previous studies. Grid samp

9、ling method by pruning puts forward , namely the majority class of the samples will be divided into absolute safety data, data of edge and noise data before grid sampling basing on adaptive boosting method to carry out sampling data learning. The artificial data and typical UCI data sets are verifie

10、d with ROC curve as the evaluation criterion by test. In light of test conclusion, the AUC value is greater than the other types of algorithms, which shows the model has good performance. The other new method , namely the mixed sampling on the Random-SMOTE method, put forward and is valid by test.Ke

11、ywords: Imbalanced data sets; Pruning; Grid sampling; AdaBoost; ROC curve目 录摘 要IABSTRACTII第一章 绪论11.1研究背景及意义11.2非平衡数据集分类方法的研究现状31.3本文的主要工作及结构安排4第二章 基于采样技术的数据预处理方法52.1欠采样技术理论与方法52.2过采样技术理论与方法112.3本章小结15第三章 增强分类器算法和K-近邻算法153.1模式分类的概念153.2合并分类器的增强法(Boosting)理论163.3 k-近邻算法203.4本章小结21第四章 基于剪枝网格采样的非平衡数据集分类

12、算法224.1剪枝技术224.2非平衡数据集的采样处理技术254.3基于采样技术的非平衡数据集的增强分类算法324.4本章小结33第五章 算法性能分析345.1非平衡数据集分类器的性能评价标准345.2人工数据集上的实验365.3典型UCI数据集上的实验40第六章 总结与展望436.1本文相关工作的总结436.2对未来的展望43参考文献44攻读硕士学位期间的主要工作48致 谢49第一章 绪论1.1研究背景及意义分类是模式识别、机器学习和数据挖掘中的一个重要研究内容，已取得一定的成果。各种分类算法层出不穷，现有的分类算法有贝叶斯分类、BP神经网络、决策树、聚类和支持向量机等。这些经典而又传统的分

13、类算法在现实世界中都有着广泛的应用，但是随着应用的深入，使得这些经典的分类算法面临着极大考验和挑战。在分类问题中，就有这样一类数据集，待分的数据集各类别之间严重倾斜，某一类别数据远多于其它类别，把这样的数据集称为非平衡数据集。其中，数据集中样本比另外一类别多的类别称为多数类样本，也称为负类样本；数据集中样本比另外一类别少的类别称为少数类样本，也称为正类样本1。就两类分类问题举一个例子说明非平衡数据集分类问题的特殊性，在现实生活中，信用卡欺诈用户一般只有2%，而98%是正常的信用卡用户。如果全部检测为正常的信用卡用户，这样的分类精确度也达到了98%，显然这个结果是毫无价值的。即便只有这2%的欺诈

14、用户被检测错误也会给银行带来巨大损失，这是因为，如果把正常的信用卡用户检测为欺诈用户，那么银行要投入大量的人力和财力，但是如果把这2%的欺诈用户误分为正常的信用卡用户，那么会使银行经济损失远远大于银行检测正常的信用卡用户所要投入的人力和财力。非平衡数据集中少数类样本分类的正确性，往往比多数类样本分类的正确性要重要的多。不幸地是，在如今世界里，这种非平衡数据分类问题是随处可见，广泛存在于各个领域中。如在医疗诊断领域中，进行体内感染监测问题2，进行心脏护理问题3和阐明蛋白质蛋白质相互作用问题4以及科学与工程领域中的检测欺诈问题5,6，检测网络入侵问题7和管理电信问题8等等，都涉及非平衡数据分类问题

15、。我们在看一个例子，在医疗诊断方面，如果把正常人(多数类样本)误诊为病人(少数类样本)，会给正常人带来一些精神打击，但是一旦把病人误诊为正常人，就会影响病人治病，可能错过最佳治疗期，会要人家的性命的。在这些应用领域中，人们关心的都是少数类样本，因为她的误分会导致巨大的代价损失。正如一些研究学者这样认为：非平衡数据集分类问题研究具有重要的商业价值和环保意义。由于非平衡数据集存在如下分类困难的原因：1. 不恰当的采样方法现存的采样技术，不管是欠采样还是过采样都存在一定的缺陷，如欠采样，当随机的去掉一些多数类样本时，那么一些潜在的有用信息也同时被去掉，这样会导致一些多数类样本数据的重要信息丢失；过采

16、样随机的复制样本也有可能会导致数据的过度拟合。因此如何选择一种适当的采样方法以改变非平衡数据集的不平衡程度是目前分类的一个难题。2. 不科学的性能评价指标目前常用的分类器评估标准就是准确率、查准率和查全率。他们不适合对非平衡数据集分类器的评价，需要另外选择评估度量，最通用的是进行 ROC曲线分析以及用 AUC（ROC曲线的下区域）来进行性能评估。3. 噪声数据在现实世界中，我们得到的数据集会或多或少的出现一类影响分类器分类性能的数据，即噪声数据。在非平衡数据集中不例外的存在这种噪声数据，它在非平衡数据集分类问题中严重的影响着少数类样本的正确分类。如果噪声数据偏向于少数类样本的区域中，想正确识别

17、少数类样本更是难上加难了。如何去噪，也是非平衡数据集分类问题的一个难题。4. 归纳偏置应用不当有时在进行数据处理时会对数据集进行归纳偏置，提高处理方法的泛化能力。但是在非平衡数据集分类时，这种操作不仅提高不了学习的能力，反而使得对正类的学习更加困难。不幸的是，传统分类算法的设计者当时是在类平衡的前提下设计算法的，未能足够的考虑到非平衡数据集分类问题，导致传统的分类算法在非平衡数据集分类问题面前显得捉襟见肘了。例如在检测网路入侵问题时，网络入侵的概率一般不到0.01%，传统分类器比如决策树算法，还有神经网络算法为了考虑整体的精确度，即便把所有的网路访问都分为正常的网路访问，其分类精确度也达到99

18、.9%。但是这肯定不是我们想要的结果，而我们想要的是那0.01%重要的少数类样本正确分类。如何有效的解决非平衡数据集分类问题，在保障分类整体的准确性下，突出少数类样本分类的重要性。她已成为模式识别、机器学习和数据挖掘中的一个重要研究课题，具有一定的研究价值。1.2非平衡数据集分类方法的研究现状随着时代的进步，数据信息的处理问题成为科技领域的一个重要问题。有一类数据的处理问题渐渐成为数据挖掘、模式识别和机器学习领域9,10,11的热点问题，它就是非平衡数据集分类问题。纵观国内外学者对非平衡数据集问题的研究成果，总的来说，对非平衡数据集处理分类问题的研究主要在两个层面上，一个是在前期的数据预处理层

19、面上，另一个层面上就是对已有算法的修正。非平衡数据集分类问题的数据预处理层面主要思想是克服训练集的类别不平衡状况，消除或减少类别间的倾斜程度。常见的方法有过采样方法(Over-sampling)和欠采样方法(Under-sampling)。欠采样方法具体做法是对非平衡数据集中的多数类样本进行压缩，文献12中就是一个典型的欠采样方法，运用粒度计算的理论知识和主要思想，对多数类样本进行粒度计算，减少其样本数量，试图改变不平衡的状况。Show-Jane Yen等13人提出的聚类欠采样方法，还有Kubat.M等人14提出one-sided selection方法，也是常见而又典型的处理非平衡数据集分类

20、问题的预处理方法。另一方面就是过采样方法，具体做法恰恰相反，它是对少数类样本进行添加。最具代表的是Chawla.N等15人提出了一种经典的Synthetic Minority Over-sampling Technique过采样方法，运用插值的方法，在少数类样本间添加新样本改变平衡性。接着他们又进行改进提出了SMOTEBoost方法16 ，还有学者H.Han等17人也对其进行修改，它仅对分类器决策面处样本进行采样处理，提出了Borderline-smote方法。算法修正层面主要思想是改进和修正已有的算法，克服在非平衡数据集分类问题上的弊端，提高算法性能。最常见的是对支持向量机(SVM)算法进行

21、改进，如文献18中优化SVM算法中参数因子，结合遗传算法优化参数，提高 SVM算法在非平衡数据集分类问题上的效果，Wu Gang等19人以及Japkowicz等20人基于SVM算法进行了修正。也有学者对Boost做了进一步的改进提出SMOTEBoost方法。1.3本文的主要工作及结构安排本文的主要工作是研究基于采用技术的非平衡数据集分类问题，结合前人已有的经验做法和园艺工人培植盆景的剪枝技巧，为非平衡数据集分类问题添加一种新的采样思路剪枝和k-近邻密度网格相结合采样方法，提出剪枝和采样相结合的非平衡数据集分类算法模型，并结合实验对分类模型的有效性进行了验证。本文结构内容安排如下：第一章绪论，介

22、绍了非平衡数据集分类问题的研究背景、意义和现状。第二章基于采样技术的数据预处理方法，阐述了欠采样和过采样方法的思想和具体算法。第三章增强分类器算法和k-近邻算法，详细介绍了本文将要使用的两类分类算法主要思想和理论推导过程。第四章基于采样技术的非平衡数据集增强分类算法，重点叙述了剪枝技术和k-近邻密度网格采样及其在非平衡数据集分类中运用。第五章算法性能分析，对本文提出的模型进行实验验证。第六章总论，对全文的研究工作进一步总结。第二章 基于采样技术的数据预处理方法现实世界中数据大都是不完整，残缺或含有噪声数据，无法直接进行数据分析和研究。为了提高数据分析和研究的质量必须进行数据预处理。 数据预处理

23、有多种方法：清理数据，集成数据，变换数据，归约数据等。采样技术也是数据预处理的一个重要方法与手段。目前，采样技术形式虽然多种多样，但是都归结两大类采样技术：欠采样技术和过采样技术，有时人们根据需要还结合两类采样技术对数据进行预处理，即混合专家模型22，混合专家模型由学者Japkowicz提出，它把对两类样本进行不同倍率采样作为训练样本的众多分类器组合，使分类结果更好。这些数据处理技术在数据分析和研究之前使用，有效地提高了数据分析和研究的质量，降低实际分析和研究所需要的时间和成本。2.1欠采样技术理论与方法欠采样技术(Under-sampling Technology)也称向下采样，通过采样减少

24、数据中的噪声数据或者是富含信息量较少的冗余数据，留下富含信息量较多的数据，以便更好的进行数据分析与研究。下面介绍几类常见的欠采样技术：2.1.1随机压缩采样随机压缩 (Random Compression)是通过随机的选择数据集中的某些数据，然后把这些数据从原来数据集中剔除。如图2-1和图2-2，图2-1是没有进行预处理的原始数据集，图2-2是通过随机压缩后的数据集。图2-1 原始数据集分布图图2-2 通过随机压缩后数据集分布图随机压缩技术可以减少数据个数，给数据分析和研究时带来简便，提高效率。但是它的随机性无法真正的去掉噪声数据，减少数据集中的冗余数据，反而可能剔除了部分富含信息量较多的有用

25、数据，这样就会适得其反，不能有效的进行下一步的数据分析研究。Hart改进随机压缩技术，提出一种压缩最近邻(Condensed Nearest Neighbor Rule,CNN)23技术,具体做法是找一个一致子集(如果能够将集合A中的全部样本进行正确分类的训练样本集合B，且该集合是集合A的一个子集，那么该集合称为一致性子集)。已有文献14给出了一致性子集的具体求法，其方法如下：第一步，从集合A中随机选取一多数类样本数据存放到集合B中，再把所有的少数类样本也存放到B中；第二步，把集合B中的所有数据样本拿出来，用这些样本对集合A中样本进行训练学习，采用的学习算法是最近邻算法，凡是集合A中学习错误的

26、样本存放到集合B。第三步，不断改变集合B，直至全部正确学习集合A的样本，此时，集合B就是所求的一致子集。生成一致性子集的目的，在于剔除大类中远离边缘的不安全样本即噪声数据。还有一种改进方法，是由Tomek提出的Tomek links24。其基本思想如下: 随机地选定一个样本对它们来之不同类别的样本中，用度量他们之间的距离。如果不存在第三个样本使得或者，这时和之间距离最近，那么样本对就是一个Tomek links。这样的样本对要么其中一个是噪声数据，要么两者都是边缘数据。由上述描述，Tomek links可以用于数据约简和预处理。具体做法是：找出要约简和预处理数据的Tomek links样本对，

27、这些Tomek links样本对或者是数据集中的边缘数据，或者是数据集中的噪声数据，把这些Tomek links样本对删除，其他数据不变。2.1.2聚类采样聚类(clustering)是研究分类问题的一种统计分析方法25，聚类起源于生物学分类学。随着人类科学技术的发展，聚类应用于多个研究领域，包括数据挖掘、图像处理、模式识别、机器学习、统计学等。聚类分析方法多种多样、内容非常丰富，有顺序聚类法、层次聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、二值形态聚类法等等26。接下来介绍一种最常用也是最著名的聚类算法K-均值算法27。K-均值算法也称Isodata算法和C-均值算法，由麦克

28、奎因(J.B.MacQueen)于1976年提出28。该算法由于其算法简洁，操作容易，又提出较早，备受人们的青睐，成为最常用且最著名的一类聚类算法，广泛应用在科技领域中。该算法原始思想如下28：随机地选择K个数据作为初始簇类中心(这K个数据可以是需要聚类的样本集中数据，也可以不是)，计算需要聚类的样本集中每个数据到这K个初始簇类中心样本间距离，距离哪个初始簇类中心样本最近的就地划分到该簇类中，计算新的簇类中心，也就是每个簇类中所有数据的平均值，这样就完成了第一次聚类，在如此迭代，如果K个簇类的均值在某一次迭代后就趋于不变，那么样本集就聚类完成了。由上述思想我们给出原始K-均值算法的具体算法流程

29、如下：1输入：需要聚类的数据集：，聚类数目数K2输出：K个簇类3执行循环： 3.1 给定初始条件：m=1，随机的选定K个数据作为初始族类中心：3.2 for i=1:n 计算每个数据与这K个族类中心的距离，如果满足，那么即此时数据 被分到第族类中 3.3 计算K个新的族类中心：， 3.4 直至，否则，返回到 3.2我们通过聚类技术可以对数据进行欠采样，通过对数据集进行K-均值算法聚类，聚类后的族类中心代替原来的样本集进行数据分析研究，我们通过下面的图2-4和前面的图2-2可以清楚的看到它比随机压缩技术进步不少。图2-3 原始数据集分布图图2-4 通过k-均值聚类后数据分布图2.1.3网格采样网

30、格(Grid)采样的思想源于粒度计算(Granular Computing)，粒度计算由Lin在1997年首次提出，主要包括Zadeh的模糊集理论2932、Pawlak的粗糙集理论33和我国学者张钹、张铃的商空间理论34。网格采样方法也是简单易行的，它的基本思想是：将数据集空间分成若干个互不相交的子空间，从每个含有样本数据的子空间中适当选取样本数据，剔除没有被选中的数据，然后把每个子空间剩下的样本数据留下作为需要研究分析的数据集。下面就二维数据集阐述网格采样的具体设计方法。记为二维数据空间，是我们需要研究分析的数据集，中含有个样本数据为。把分成个子空间为，并且它们之间彼此不相交，即当时，这样便

31、形成了个网格，接着找出每个网格中样本，计算出它们的平均值，然后利用k-近邻算法留下网格中的适当样本，最后把所有网格中留下的样本放在一起，剔除未留下的样本，这便是网格采样的具体设计思路。根据这一思想设计出最简单的网格采样算法：1输入：需要研究分析的数据集2输出：网格采样后的数据集3找出中数据第维度的最大值和最小值，再把区间分成若干份,这样就生成个网格了4找出每个网格中包含中数据，并算出每个网格中数据的平均值5利用k-近邻算法，找出每个网格中与近邻的适当样本，删除每个网格余下样本上面的网格采样算法称作k-近邻网格采样算法，如图2-5和图2-6所示。比较两图中数据分布，k-近邻网格采样算法对数据集采

32、样基本保持原来数据分布情况。其实，我们还可以把上面的第四步与第五步合并改为“随机删除每个网格中包含中数据”设计出更简单地随机网格采样算法，它也基本保持原来数据分布情况。图2-5 原始数据集分布图图2-6 网格采样后数据集分布图为了更好的保持与原来数据分布，我们进一步改进k-近邻网格采样算法，提出了k-近邻概率密度网格采样算法，该算法将在第四章详细叙述。总之，网格采样方法进行欠采样基本不改变原始数据集的分布。2.2过采样技术理论与方法过采样技术(Over-sampling Technology)也称向上采样，通过采样增加数据集中的残缺数据或者尽可能的还原数据集丢失数据，以获取更多的有用信息进行数

33、据分析与研究。接着介绍几类常见的过采样技术：2.2.1随机插值采样随机插值采样的基本思想是：通过随机复制原数据集中的样本数据，弥补原数据集数据不足。这种方法虽然简单易行，但是重复复制很难取得更多的有用信息，达不到对数据进行有效的分析研究。2.2.2 SMOTE采样Synthetic Minority Over-sampling Technique(SMOTE)采样是由Chawla等人在2002年提出的一种过采样技术15，处理非平衡数据集问题常见方法。SMOTE采样的基本思想为：利用K-近邻算法，找出个距离数据集中的每个样本数据的个样本，由实际需要采样的倍数，在刚才个样本中随机地选取所需要的个数

34、据，这个数据记为，然后在和之间的线段上随机的生成一个新的样本，假设过采样倍率为，也就是在需要采样样本的7个较近距离样本中随机地选取3个样本，再在这3个样本和需要插值的样本线段上添加一个新样本数据，这样就由一变三了。表达式为： (2.1)(其中是01之间的一个随机数)。举一个具体的二维空间数据的例子，其中，。比如二维空间中有一个样本数据需要合成产生新的样本数据，和是它的5个近邻样本数据，我们从这5个近邻样本数据随机选择3个，每个按照式(2.1)生成的三个新的数据，它们分别为 (2.2) (2.3) (2.4)这样，就原来的一个样本变成了三个新的样本了。SMOTE采样的具体算法如下：1输入：需要S

35、MOTE过采样的数据集，过采样倍率2. 输出：经过SMOTE过采样的数据集3. 执行循环： 3.1 每次在数据集中选择一个样本数据3.2 利用k-近邻算法找出的个最近邻样本3.3 从个最近邻样本随机选择个样本3.4在和之间线段上随机的生成一个新的样本(用公式(2.1)计算) 3.5 直至数据集中每个样本数据被执行一次3.6 算法结束以一个包括50个样本点的二维数据集为例，假设需要生成新样本的数量是比原来的数量多3倍，即倍率，采用SMOTE方法生成，其中，原始数据用红色星号表示，新生成的数据用蓝色点号表示，如图2-7所示。图2-7 SMOTE采样前后数据分布比较图通过上图数据分布中可以看出，SM

36、OTE方法优点是可以保持原来数据集的大致原貌，没有改变原始数据集的基本分布情况，却有一个致命的缺点只是在每个样本附近生成新的样本，结果疏密仍然未变，疏的地方还是那样，而密的地方也未改变。2.2.3 Random-SMOTE采样为了更好的使用SMOTE采样，在SMOTE采样基础上提出Random-SMOTE采样，Random-SMOTE采样方法的具体思想是：假设需要采样的数据为，再在剩下的数据集中随机选择两个不同数据，以此三个样本数据为顶点便构成一个区域D，接着在此区域D内生成所需要的(为采样倍率)个新的样本。根据这一思想，Random-SMOTE采样的具体算法如下：1. 输入：需要Random

37、-SMOTE过采样的数据集，过采样倍率2. 输出：经过Random-SMOTE过采样的数据集3. 执行循环： 3.1 每次在数据集中选择一个样本数据3.2 在数据集中随机选择两个样本数据，3.3 在之间用SMOTE技术生成临时个样本数据，计算公式如下： (2.5) 3.4 在每个样本数据和之间用SMOTE技术生成一个样本数据，计算公式如下： (2.6) 3.5 直至数据集中每个样本数据被执行一次3.6 算法结束根据上述算法，我们同样还是以一个包含50个样本点的二维数据集为例，假设需要生成新样本的数量是比原来的数量多3倍，即倍率，用Random-SMOTE方法生成。原始50个样本数据用红色星号表

38、示，Random-SMOTE方法新生成的150个样本数据用蓝色点号表示，如图2-8所示。图2-8 Random-SMOTE采样前后数据分布比较图比较图2-7和2-8，我们发现Random-SMOTE采样技术比SMOTE采样技术更能考虑到稀疏部分的数据采集。2.3本章小结本章第一部分重点介绍了欠采样技术，主要阐述了随机压缩采样、聚类采样和网格采样三种常见的欠采样技术，第二部分阐述了过采样技术，也是阐述了三类过采样技术，重点叙述了SMOTE采样和Random-SMOTE采样，他们在非平衡数据集研究问题中有着广泛的应用。第三章 增强分类器算法和k-近邻算法3.1模式分类的概念模式分类(Pattern

39、 Classification)也叫模式识别，模式识别(Pattern Recongnition)是一门以应用为基础的学科，目的是将对象进行分类。模式识别具有悠久的历史，20世纪60年代以前，她主要是统计学中的研究理论。随着计算机的出现，促进了她的发展并成为一门应用性及其广泛的学科。比如，字符识别、遥感、计算机辅助诊断、语音识别和数据库中的数据挖掘和知识发现都是模式识别的重要应用领域，而且远不止这些。首先让介绍一个简单的模式识别问题来进一步了解模式分类。我们都清楚的知道男性和女性在发声的声调上有着明显的差别，只要某人一发声，即便我们没看见他(或她)，我们也立即分辨出他(或她)的性别，这就是人工

40、模式分类。那么怎样让计算机来分辨呢？其实可以模仿人工模式分类，设计出计算机模式分类的步骤，其步骤如下：图3.1 模式分类的基本步骤模式(Pattern)就是识别对象，可以是语音、图像、信号波形或者任何可以测量的对象。传感器组件一般有敏感元件和转换元件，它通过敏感元件测量识别对象，再通过转换元件转换识别对象的装置。模式通过传感器后就是特征提取，再选择分类器所需要的特征进行分类器设计，最后就是评估模式分类系统性能。3.2合并分类器的增强法(Boosting)理论模式分类有五个基本步骤，其中分类器的设计是一个非常重要的研究课题，它涉及到人工智能的多个领域。分类器(classifier)是使待分对象被

41、划归某一类而使用的分类装置或数学模型，常见的分类器有贝叶斯(Bayes)分类器，BP神经网络分类器，决策树算法，支持向量机(SVM)算法等，还有一种是合并分类器。合并分类器目的是，发掘驻留在各种分类器中的互补信息，使最终分类器性能进一步提高，如图3.2所示。图3.2 合并分类器3.2.1合并分类器的增强法(Boosting)早在20世纪90年代诞生一种增强法(Boosting)，或者叫提升法，是一种提高给定分类器性能的普遍方法，它与广泛流行的支持向量机一起构成最有效的技术之一。它的渊源要追溯到Viliant和Kearns的最初工作3536,他们曾经提出了一个问题：一个“弱”分类器可不可以被提升

42、为一个性能很好的“强”分类器呢？提升核心是：对一系列基分类器进行迭代学习，且每次所使用的训练样本都不一样，接着计算分布函数或不同训练集样本在每一步迭代学习的权值，根据算出的权值强调最活跃(分类错误)样本，最终获得的分类器是先前分层设计分类器的加权均值。可以证明，当达到一定的迭代次数，这种方法在训练集上测量最终合并的分类器误差可以达到任意的小37。3.2.2合并分类器的自适应增强法(AdaBoost)作为增强法的代表，自适应增强法(Adaboost)38有着广泛应用，主要思想是：首先给每个训练样本数据赋以同等大小的权值，根据训练样本的权值大小选择样本，对所谓“弱”的分类器进行训练，然后用原数据集

43、来进行测试，改变样本的权值，正确分类的样本权值减小，错误分类的样本权值加大。如此循环迭代K后，“弱”的分类器就可以增强为“强”分类器。下面是Adaboost算法在二维空间的理论推导过程：记训练数据集为，其中，为类标签。目的是设计一个最优分类器，其形式如下： (3.1)其中 (3.2)其中是一个基分类器，返回二值类标签，即。为了求出未知参数的值，可以通过最优下面式子的过程得到： (3.3)在分类过程中，加大对分类错误样本的惩罚程度。如果直接对式(3.3)进行优化是困难而又复杂的。一般在优化理论中解决复杂优化问题时，常用的方法是次优方法，也就是逐段最优方式进行优化。每一步仅仅优化一个新的参数，其他

44、参数暂时保持不变。我们用下面的式子来定义，它表示项的部分和的结果，即 (3.4)由这个定义，下面的递归过程就显而易见了： (3.5)现在，运用逐段优化方法处理问题。在第步时，假设上一步中的各个参数是已经优化的了，目前的任务是计算第步的和的最优值。也就是说，计算下式的和值。 (3.6)其中代价函数被定义为 (3.7)为了计算和最优值，优化过程将分两步完成。首先，固定，即定义为常量，最优基分类器，即最小化代价被简化为 (3.8)其中 (3.9)因为每个值是不依赖和 ，而是依赖于采样点的权值。再由于基分类器的二值性，容易看出最小化式(3.8)与最优分类器是等价的，所以权值的经验误差(训练样本被错误分

45、类的部分)是最小的，即 (3.10)函数 也是二值函数，取值是或，这取决于它的自变量是还是正数。即自变量是0时取值为0，正数时取值为1。为控制加权的经验误差率值在一定区间内，同时保证权值总和必须等于。可以通过相应的归一化方法实现；即用每一个权值除以各自的和值，它不影响优化过程，而且还很容易合并到最终的迭代过程中去。在第步已经计算出最佳的分类器后，由各自的定义很容易得到 (3.11) (3.12)式(3.11)、(3.12)和(3.7)、(3.9)式结合，可以由下面的式子得出最优值： (3.13)先对求导数，再使它等于零，可以得到 (3.14)一旦计算出和，就可以容易通过迭代得到下一步的权值：

46、(3.15)归一化因子是 (3.16)Adaboost算法具体描述如下：1.输入：初始化，2.循环： 2.1 在中通过最小化计算最优的； 2.2 计算最优的； 2.3 ， 2.4 For to 结束For 2.5 For to结束For2.6 , 直到满足终止条件3 输出：3.3 k-近邻算法k-近邻(K-Nearest Neighbor)算法是模式分类常用的方法之一，也是本文多次使用的思想方法。下面就对k-近邻分类算法进行详细叙述。作为一个重要非参数分类方法的k-近邻39算法，有着广泛应用。它具有一定的统计理论基础的，而且直观、容易操作，测试样本类别直接由测试样本的k个近邻样本决定，k个样本中哪个类别数量多，该测试样本属于那个类别，不需要先前的统计知识。具体