分类算法

分类算法目录1.分类算法....................................................................................32.典型分类算法.............................................................................32.1决策树分类算法......................................................................32.1.1算法概述.........................................................................32.1.2算法优缺点......................................................................32.1.3算法分类介绍..................................................................42.1.3.1ID3（C4.5）算法......................................................42.1.3.2SLIQ分类算法.........................................................42.1.3.3SPRINT分类算法.......................................................52.2三种典型贝叶斯分类器...........................................................52.2.1算法概述.........................................................................52.2.2算法分类介绍..................................................................52.2.2.1朴素贝叶斯算法........................................................52.2.2.2TAN算法...................................................................62.2.2.3贝叶斯网络分类器....................................................72.2.3三类方法比较..................................................................72.3k-近邻....................................................................................82.4基于数据库技术的分类算法....................................................92.4.1MIND算法........................................................................92.4.2GAC-RDB算法...................................................................92.5基于关联规则的分类算法......................................................102.5.1Apriori算法.................................................................102.6支持向量机分类....................................................................112.7基于软计算的分类方法.........................................................112.7.1粗糙集...........................................................................122.7.2遗传算法.......................................................................122.7.3模糊逻辑.......................................................................132.7.4人工神经网络算法.........................................................142.7.4.1算法概述................................................................142.7.4.2算法优缺点.............................................................142.7.4.3算法分类................................................................152.7.4.3.1BP神经网络分类算法.......................................152.7.4.3.2RBF神经网络...................................................162.7.4.3.3SOFM神经网络.................................................172.7.4.3.4学习矢量化（LVQ）神经网络...........................173其他分类算法...........................................................................183.1LB算法..............................................................................183.2CAEP算法..........................................................................181.分类算法分类的目的是通过分类函数或分类模型（也常常称作分类器），把数据库中的数据项映射到给定类别中的某一个。用于提取描述重要数据类的模型或预测未来的数据趋势。2.典型分类算法2.1决策树分类算法2.1.1算法概述决策树（DecisionTree）是一种有向无环图（DirectedAcyclicGraphics,DAG）。决策树方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，在根据该属性字段的不同取值建立树的分支，在每个子分支子集中重复建立树的下层结点和分支的一个过程。构造决策树的具体过程为：首先寻找初始分裂，整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，以决定哪个属性域（Field）作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。量化的标准是计算每个分裂的多样性（Diversity）指标。其次，重复第一步，直至每个叶节点内的记录都属于同一类且增长到一棵完整的树。2.1.2算法优缺点优点：（1）决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。（2）对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。（3）能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。（4）决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。（5）易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。（6）在相对短的时间内能够对大型数据源做出可行且效果良好的结果。（7）可以对有许多属性的数据集构造决策树。（8）决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。缺点：（1）对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。（2）决策树处理缺失数据时的困难。（3）过度拟合问题的出现。（4）忽略数据集中属性之间的相关性。2.1.3算法分类介绍主要的决策树算法有ＩＤ３、C4.5(C5.0)、CART、PUBLIC、SLIQ和SPRINT算法等。2.1.3.1ID3（C4.5）算法2.1.3.1.1算法概述ID3算法中，将信息增益作为属性的选择标准，以使得在对每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。ID3总是选则具有最高信息增益的属性作为当前结点的测试属性。具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。ID3算法通过不断的循环处理，初步求精决策树，直到找到一个完全正确的决策树。在选择重要特征时利用了信息增益的概念。2.1.3.1.2算法优缺点优点：（1）算法的基础理论清晰，方法简单，计算速度快；（2）搜索空间是完全的假设空间，目标函数就在搜索空间中，不存在无解的危险；（3）全盘使用训练数据，可得到一棵较为优化的决策树。缺点：（1）不能增量地接受训练例，这就使得每增加一次实例都必须废除原有的决策树，重新计算信息增益并构造新的决策树，这造成极大的开销；（2）智能处理离散属性，在分类前需要对其进行离散化的处理；（3）在建树时，每个结点仅含一个特征，这是一种变元的算法，特征间的相关性强调不够；（4）对噪声较为敏感，数据质量差将直接导致生成的决策树过于庞大或决策树中很多分支的信息量很少；（5）在建树的过程中每当选择一个新属性时，算法只考虑了该属性带来的信息增益，未考虑到选择该属性后为后续属性带来的信息增益，即未考虑树的两层节点；（6）其信息增益存在一个内在偏置，它偏袒属性值数目较多的属性。2.1.3.2SLIQ分类算法2.1.3.2.1算法概述针对C4.5改进算法而产生的样本集反复扫描和排序低效问题，SLIQ分类算法运用了预排序和广度优先两项技术。2.1.3.2.2算法优缺点优点：能处理比C4.5大得多的样本集（1）预排序技术消除了结点数据集排序。（2）广度优先策略为决策树中每个叶子结点找到了最优分裂标准。缺点：占用内存较多（1）限制了可以处理的数据集的大小；（2）预排序技术使算法性能不能随记录数目进行线性扩展。2.1.3.3SPRINT分类算法2.1.3.3.1算法概述为了减少驻留于内存的数据量，SPRINT算法进一步改进了决策树算法的数据结构，去掉在SLIQ中需要驻留于内存的类别列表，将类别合并到每个属性列表中。2.1.3.3.2算法优缺点优点：由于在遍历每个属性列表中寻找当前结点的最优分裂标准时，不必参照其他信息，使寻找每个结点的最优分裂标准变得相对简单。缺点：对非分裂属性列表进行分裂却变得非常困难。因此，该算法的扩展性能较差。2.2三种典型贝叶斯分类器