分类算法001.docx
- 文档编号:17230178
- 上传时间:2023-07-23
- 格式:DOCX
- 页数:16
- 大小:33.71KB
分类算法001.docx
《分类算法001.docx》由会员分享,可在线阅读,更多相关《分类算法001.docx(16页珍藏版)》请在冰点文库上搜索。
分类算法001
分类算法目录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算法...................................................................9
2.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算法..........................................................................18
1.分类算法分类的目的是通过分类函数或分类模型(也常常称作分类器),把数据库中的数据项映射到给定类别中的某一个。
用于提取描述重要数据类的模型或预测未来的数据趋势。
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算法分类介绍主要的决策树算法有ID3、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三种典型贝叶斯分类器2.2.1算法概述贝叶斯分类是统计学分类算法,它是一类利用概率统计知识进行分类的算法。
它在先验概率与条件概率已知的情况下,预测类成员关系可能性的模式分类算法。
2.2.2算法分类介绍2.2.2.1朴素贝叶斯算法2.2.2.1.1算法概述朴素贝叶斯分类器以简单的结构和良好的性能受到人们的关注,它是最优秀的分类器之一。
朴素贝叶斯分类器建立在一个类条件独立性假设(朴素假设)基础之上:
给定类结点(变量)后,各属性结点(变量)之间相互独立。
朴素贝叶斯分类器可以看作是贝叶斯网络的一种最简化的模型。
根据朴素贝叶斯的类条件独立假设,则有:
mP(X|Ci)P(X|Ci)Kk1条件概率P(X1|Ci),P(X2|Ci),„,P(Xn|Ci)可以从训练数据集求得。
根据此方法,对一个未知类别的样本X,可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci),然后选择其中概率最大的类别作为其类别。
朴素贝叶斯算法成立的前提是各属性之间相互独立。
当数据集满足这种独立性假设时,分类的准确度较高,否则可能较低。
另外,该算法没有分类规则输出。
2.2.2.1.2算法优缺点优点:
(1)朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。
(2)NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。
(3)在接受大量数据训练和查询时速度很快。
尤其当训练量递增时更是如此(我们可以分多次的对其进行学习的训练,而一些其他的方法如决策树和支持向量机要一次传送整个训练数据集)(4)其对分类器的学习情况有着比较简单的解释,可以简单的通过查询学习时计算的一些概率值来了解其分类原理。
缺点:
(1)理论上,NBC模型与其他分类方法相比具有最小的误差率。
但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的(可以考虑用聚类算法先将相关性较大的属性聚类),这给NBC模型的正确分类带来了一定影响。
在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。
而在属性相关性较小时,NBC模型的性能最为良好。
(2)它无法处理特征符合所产生的变化。
(3)需要知道先验概率。
(4)分类决策存在错误率。
2.2.2.2TAN算法TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的额假。
它是在NB网络结构的基础上增加属性对之间的关联(边)来实现的。
实现方法是:
用结点表示属性,用有向边表示属性之间的依赖关系,把类别属性作为根结点,其余所有属性都作为它的子节点。
通常,用虚线代表NB所需的边,用实线代表新增的边。
属性Ai和Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的值。
这些增加的边满足下列条件:
类别变量没有双亲结点,每个属性有一个列别变量双亲结点和最多另外一个属性作为其双亲结点。
找到这组关联边之后,就可以计算一组随机变量的联合概率分布如下:
nP(A1,A2,...,An)p(C)P(Ai|Ai)i1
其中代表的是Ai的双亲结点。
由于在TAN算法中考虑了n个属性之Ai间独立性的假设有了一定程度的降低,但是属性之间可能存在更多其它的关联性仍没有考虑,因此其使用范围仍然受到限制。
2.2.2.3贝叶斯网络分类器贝叶斯网络分类器放弃了朴素贝叶斯分类器的条件独立性假设,所以最能与领域数据相吻合。
在贝叶斯网络的结构中类结点地位同其他属性结点一样,也可以有父节点。
本文采用基于搜索打分的方法构造贝叶斯分类器,搜索打分算法采用K2搜索算法和BIC评分函数。
贝叶斯网络分类方法如下:
1)输入:
训练集D;变量顺序;变量父结点个数上界u;2)K2算法构造BNC:
a、所有结点组成无向图b、确定变量jX的父结点个数,等于u则停止为它寻找父结点;c、如果父节点的个数大于u,则从中按顺序选择jX之前的节点,但不是jX父结点的变量iX做为jX的父结点;d、使用BIC测度对新结构打分;e、同前次打分比较,如果评分高,则添加iX为jX的父节点;如果BIC评分低,则停止为jX寻找父结点;3)使用训练数据集进行参数学习(最大似然估计法);4)对测试集分类,得出分类准确度。
2.2.3三类方法比较下面主要从分类准确度和分类耗时这两个方面分析比较这三种分类器。
(1)朴素贝叶斯分类器。
从分类准确度上看,NBC虽然结构简单但是它的分类准确度并不低。
从分类耗时看,NBC普遍比其它两种分类器花费的时间少,这与它不需要结构学习,计算复杂度低是密切相关的。
NBC在现实中有着广泛的适应性,这主要还因为在大部分领域中属性之间的依赖关系要明显低于属性和类别之间的依赖关系,所以NBC的条件独立性假设是具有一定的现实意义的。
(2)基于BIC测度的TAN分类器是所有NBC改进分类器中效果最好的一个。
TAN分类器的分类准确度普遍高于NBC,TAN分类器放松了条件独立性假设这是同现实世界相符合的,当属性之间关联性越大时,TAN分类器的效果就越好。
TAN分类器中需要设置根节点,根节点就是选择除去类节点以外的属性节点作为其它属性节点的根节点,根节点的设置对分类准确度并没有很大的影响。
从分类时间上看,TAN分类器在这三种分类器中是花费时间最长的。
(3)理论上BNC分类器应该有最好的分类效果,但是实际中,BNC的分类效果并不理想,这主要与两个因素有关:
(1)数据集的规模。
BNC对大样本的数据集有较好的分类效果,在小规模数据集情况下就不如NBC和TAN;
(2)在使用K2算法进行结构学习的过程中有一个重要的参数,用来确定结点变量的次序,它对先验知识的依赖性很大。
在不了解相关的领域或没有专家的指导的情况下,确定变量的次序就变得相当困难。
从分类耗时上看,BNC分类器的分类耗时比NBC要长,同TAN比较有一定的不确定性,它普遍要比TAN分类时间短。
这三种分类器并不是对每种数据集都有好的分类效果,因此在对数据集选择分类器的时候还需要具体情况具体对待,主要考查属性之间的关联性、数据的规模和时间限制等方面。
数据集属性相关性小的时候选择NBC有较好的分类效果,数据集属性相关性大时候选择TAN分类器。
在数据集规模较大且具有一定先验知识时选择贝叶斯网络分类器。
2.3k-近邻2.3.1算法概述k-近邻(kNN,k-NearestNeighbors)算法是一种基于实例的分类方法,是一种非参数的分类技术。
基本原理:
KNN分类算法搜索样本空间,计算未知类别向量与样本集中每个向量的相似度,在样本集中找出K个最相似的文本向量,分类结果为相似样本中最多的一类。
2.3.2算法优缺点优点:
(1)简单、有效。
(2)重新训练的代价较低(类别体系的变化和训练集的变化,在Web环境和电子商务应用中是很常见的)。
(3)计算时间和空间线性于训练集的规模(在一些场合不算太大)。
(4)由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
(5)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
缺点:
(1)KNN分类算法是懒散的分类算法(lazylearning,基本上不学习,一些积极学习的算法要比KNN要快很多),对于分类所需的计算均推迟至分类进行,故在其分类器中存储有大量的样本向量。
在未知类别样本需要分类时,在计算所以存储样本和未知类别样本的距离时,高维样本或大样本集所需要的时间和空间的复杂度均较高。
(2)KNN分类算法是建立在VSM模型上的,其样本距离测度使用欧氏距离。
若各维权值相同,即认定各维对于分类的贡献度相同,显然这不符合实际情况。
(3)类别评分不是规格化的(不像概率评分)。
(4)输出的可解释性不强,例如决策树的可解释性较强。
(5)该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。
该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。
无论怎样,数量并不能影响运行结果。
可以采用权值的方法(和该样本距离小的邻居权值大)来改进。
(6)计算量较大。
目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。
基于上述缺点,人们也采用了一些改进算法:
当样本数量较大时,为减小计算,可对样本集进行编辑处理,即从原始样本集中选择最优的参考子集惊醒KNN计算,以减少样本的存储量和提高计算效率。
2.4基于数据库技术的分类算法虽然数据挖掘的创始人主要是数据库领域的研究人员,然而提出的大多数算法则没有利用数据库的相关技术。
在分类算法中,致力于解决此问题的算法有MIND(miningindatabase)和GAC-RDB(groupingandcounting-relationaldatabase)。
2.4.1MIND算法2.4.1.1算法概述IND算法是采用数据库中用户自定义的函数(user-definedfunction,UDF)实现发现分类规则的算法。
MIND采用典型的决策树构造方法构建分类器。
具体步骤与SLIQ类似。
其主要区别在于它采用数据库提供的UDF方法和SQL语句实现树的构造。
简而言之,就是在树的每一层,为每一个属性建立一个维表,存放各属性的每个取值属于各个类别的个数以及所属的结点编号。
根据这些信息可以为当前结点计算每种分裂标准的值,选出最优的分裂标准,然后据此对结点进行分裂,修改维表中结点编号列的值。
在上述过程中,对维表的创建和修改需要进行多次,若用SQL实现,耗时很多,因此用UDF实现。
而分类标准的寻找过程则通过创建若干表和视图,利用连接查询实现。
2.4.1.2算法优缺点优点:
通过采用UDF实现决策树的构造过程使得分类算法易于与数据库系统集成。
缺点:
(1)算法用UDF完成主要的计算任务,而UDF一般是由用户利用高级语言实现的,无法使用数据库系统提供的查询处理机制,无法利用查询优化方法,且UDF的编写和维护相当复杂。
(2)MIND中用SQL语句实现的那部分功能本身就是比较简单的操作,而采用SQL实现的方法却显得相当复杂。
2.4.2GAC-RDB算法2.4.2.1算法概述GAC-RDB算法是一种利用SQL语句实现的分类算法。
该算法采用一种基于分组计数的方法统计训练数据集中各个属性取值组合的类别分布信息,通过最小置
信度和最小支持度两个阈值找出有意义的分类规则。
在该算法中,首先利用SQL语句计算每个属性进行类别判定的信息量,从而选择一个最优的分裂属性,并且按照信息量的大小对属性进行排序,然后重复地进行属性的选择、候选分类表的生成、剪裁以及分类误差的计算,直到满足结束条件为止。
比如,直到小于误差阈值和误差没有改变为止。
2.4.2.2算法优缺点优点:
(1)具有与现有的其他分类器相同的分类准确度,执行速度有较大提高。
(2)具有良好的伸缩性,应用程序易于与数据库系统集成。
缺点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分类 算法 001