信息检索与分析能力训练3报告课题名称：分类方法专业软件工程（NIIT）学生学号(姓名) B12040914 吴凡学生学号(姓名) B12040920 沈一州指导教师成小惠指导单位计算机学院日期2014.9.9目录（一号宋体，居中）目录自动生成（小四号宋体，左对齐，单倍行距）摘要模式识别（英语：Pattern Recognition），就是通过计算机用数学技术方法来研究模式的自动处理和判读。
模式识别的目标往往是识别，即分析出待测试的样本所属的模式类别。
分类方法即通过比较事物之间的相似性，把具有某些共同点或相似特征的事物归属于一个不确定集合的逻辑方法，是模式识别中常采用的方法，包括近邻法、Bayes方法、决策树与SVM等方法。
分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。
分类可用于预测。
从利用历史数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行类推测。
关键词：1.近邻法2.Bayes法3.决策树法4.SVM法Abstract模式识别（英语：Pattern Recognition），就是通过计算机用数学技术方法来研究模式的自动处理和判读。
模式识别的目标往往是识别，即分析出待测试的样本所属的模式类别。
分类方法即通过比较事物之间的相似性，把具有某些共同点或相似特征的事物归属于一个不确定集合的逻辑方法，是模式识别中常采用的方法，包括近邻法、Bayes方法、决策树与SVM等方法。
分类的目的是学会一个分类器（分类函数或模型），该分类器能把待分类的数据映射到给定的类别中。
分类可用于预测。
从利用历史数据记录中自动推导出对给定数据的推广描述，从而能对未来数据进行类推测。
Key Words：1.近邻法2.Bayes法3.决策树法4.SVM法绪论我们周围的世界,是个无限丰富、无限多样的世界。
植物王国就有55万种绿色的居民。
而由800多万种动物组成的王国，那就更加千姿百态、精彩纷呈。
这是商品的世界，琳琅满目，多姿多彩。
世界上的事物如此多样，要一件一件地认识它们，是多么地艰难啊！分类方法，就是认识纷繁复杂的世界的一种工具。
分类，把世界条理化，它使表面上杂乱无章的世界变得井然有序起来。
分类，基本上有两种方法。
一种是人为的分类，它是依据事物的外部特征进行分类，为了方便，人们把各种商品分门别类，陈列在不同的柜台里，在不同的商店出售。
这种分类方法，可以称之为外部分类法。
另一种分类方法是根据事物的本质特征进行分类。
生活在海洋中的鲸鱼，体型象鱼，但是，它不属于鱼类，它胎生、哺乳，身上没有鳞片、不用鳃而用肺呼吸，具有哺乳动物的特征。
把鲸鱼划为哺乳类，这就是一种本质的分类。
称之为本质分类法。
当然,事物的属性是多方面的,分类的方法也是多样的,在不同的情况下,可以采用不同的分类方法。
鲸鱼、海豚，属于哺乳类。
但是，有时侯，我们也可以把它们分为海洋动物，而把牛羊之类的动物分为陆生动物。
分类，它使事物高度有序化，从而极大地提高了我们的认识效率和工作效率。
第一章1.1 项目国内外研究现状主要分类方法介绍解决分类问题的方法很多，单一的分类方法主要包括：决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等；另外还有用于组合单一分类方法的集成学习算法，如Bagging和Boosting等。
（1）决策树决策树是用于分类和预测的主要技术之一，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。
构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。
它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论。
主要的决策树算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。
它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。
（2）贝叶斯贝叶斯（Bayes）分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯（Naive Bayes）算法。
这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。
由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。
为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。
（3）人工神经网络人工神经网络（Artificial Neural Networks，ANN）是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。
在这种模型中，大量的节点（或称”神经元”，或”单元”）之间相互联接构成网络，即”神经网络”，以达到处理信息的目的。
神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。
训练改变了网络节点的连接权的值使其具有分类的功能，经过训练的网络就可用于对象的识别。
目前，神经网络已有上百种不同的模型，常见的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络（Boltzmann机）、竞争神经网络（Hamming网络，自组织映射网络）等。
但是当前的神经网络仍普遍存在收敛速度慢、计算量大、训练时间长和不可解释等缺点。
（4）k-近邻k-近邻(kNN，k-Nearest Neighbors)算法是一种基于实例的分类方法。
该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类。
k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销，因此无法应用到实时性很强的场合。
（5）支持向量机支持向量机（SVM，Support Vector Machine）是Vapnik根据统计学习理论提出的一种新的学习方法[43] ，它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。
对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由此确定该区域中未知样本的类别。
（6）基于关联规则的分类关联规则挖掘是数据挖掘中一个重要的研究领域。
近年来，对于如何将关联规则挖掘用于分类问题，学者们进行了广泛的研究。
关联分类方法挖掘形如condset→C 的规则，其中condset是项(或属性-值对)的集合，而C是类标号，这种形式的规则称为类关联规则（class association rules，CARS）。
关联分类方法一般由两步组成：第一步用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规则；第二步使用启发式方法从挖掘出的类关联规则中挑选出一组高质量的规则用于分类。
属于关联分类的算法主要包括CBA[44] ，ADT[45] ，CMAR[46] 等。
（7）集成学习（Ensemble Learning）实际应用的复杂性和数据的多样性往往使得单一的分类方法不够有效。
因此，学者们对多种分类方法的融合即集成学习进行了广泛的研究。
集成学习已成为国际机器学习界的研究热点，并被称为当前机器学习四个主要研究方向之一。
集成学习是一种机器学习范式，它试图通过连续调用单个的学习算法，获得不同的基学习器，然后根据规则组合这些学习器来解决同一个问题，可以显著的提高学习系统的泛化能力。
组合多个基学习器主要采用（加权）投票的方法，常见的算法有装袋[47] （Bagging），提升/推进[48, 49] （Boosting）等。
第二章分类方法核心技术分析和瓶颈2.1分类方法核心技术2.1.1 决策树决策树算法是一种逼近离散函数值的方法。
它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。
本质上决策树是通过一系列规则对数据进行分类的过程。
决策树方法最早产生于上世纪60年代，到70年代末。
由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。
但是忽略了叶子数目的研究。
C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。
决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。
决策树构造可以分两步进行。
第一步，决策树的生成：由训练样本集生成决策树的过程。
一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。
第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。
1）树以代表训练样本的单个结点开始。
2）如果样本都在同一个类．则该结点成为树叶，并用该类标记。
3）否则，算法选择最有分类能力的属性作为决策树的当前结点．4）根据当前决策结点属性取值的不同，将训练样本数据集tlI分为若干子集，每个取值形成一个分枝，有几个取值形成几个分枝。
匀针对上一步得到的一个子集，重复进行先前步骤，递4'I形成每个划分样本上的决策树。
一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑它。
5）递归划分步骤仅当下列条件之一成立时停止：①给定结点的所有样本属于同一类。
②没有剩余属性可以用来进一步划分样本．在这种情况下．使用多数表决，将给定的结点转换成树叶，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布，③如果某一分枝tc，没有满足该分支中已有分类的样本，则以样本的多数类创建一个树叶。
决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。
二叉树的内部节点(非叶子节点)一般表示为一个逻辑判断，如形式为a=aj 的逻辑判断，其中a是属性，aj是该属性的所有取值：树的边是逻辑判断的分支结果。
多叉树(ID3)的内部结点是属性，边是该属性的所有取值，有几个属性值就有几条边。
树的叶子节点都是类别标记。
由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。
因此，简化决策树是一个不可缺少的环节。
寻找一棵最优决策树，主要应解决以下3个最优化问题：①生成最少数目的叶子节点；②生成的每个叶子节点的深度最小；③生成的决策树叶子节点最少且每个叶子节点的深度最小。