信息数据的分类方法研究
皖西学院本科毕业论文(设计)信息数据的分类方法研究
作者吴法民
何富贵指导教师
摘要:近年来随着互联网的快速发展,信息量与日俱增,其规模越来越大,信息的表现形式也越来越多样化。面对大量而复杂的数据信息,要找到我们需要的有用信息难度也越来越大,因此对信息数据的分类具有很大的意义,分类方法的研究自然就成为具有研究意义的课题。
面对目前分类算法种类很多,在遇到实际问题时如何选用合适的一个算法或者几个算法的结合,而达到理想的分类效果,本文对经典的分类算法产生的条件、使用的范围、优缺点、局限性等方面做出研究,以实现在遇到问题时能够根据实际情况的需要选择高效、准确的分类算法的目标。
分类算法应用的领域非常广泛,其典型应用有:信用卡系统中的信用分级、市场调查、疗效诊断等。对于信息数据来说,其信息的表现形式虽然复杂化多样化,但是信息的主要载体依然是文本信息,大部分信息都是以文本形式表现出来的,因此本文针对分类方法应用讨论研究文本信息的分类算法。关键词:信息数据;分类算法;文本分类
I
皖西学院本科毕业论文(设计)
Dataclassificationmethodresearch
Abstract:Inrecentyears,withtherapiddevelopmentoftheInternet,theamountofinformationisverylargeandgrowingwitheachday,.Andvariousformsofdatainformationhaveemerged..Basedonlargeandcomplexinformation,discoveringtheusefulinformationthatweneedismoreandmoredifficult.researchontdataclassificationofinformationasahottopichavegreatsignificance.
Formanykindsofclassificationalgorithm,wemustlearnhowtochooseanappropriatealgorithmorcombinedwithseveralalgorithmstosolvepracticalproblems,andachievethedesiredclassificationeffect.Inthispaper,producecondition,userange,advantagesanddisadvantages,andlimitationsofclassicclassificationalgorithmsaredicussed.Itcontributestochooseefficientandaccurateclassificationalgorithmtosolvepracticeproblems.
Atpresent,classificationalgorithmapplicationfieldisveryextensive.Itstypicalapplicationsincludes:creditcardcreditgradingsystem,marketinvestigation,theefficacyofdiagnostic.Althoughtheinformationformiscomplex,butthemainbodyofinformationistextinformation.textformofinformationincludesmuchinformation.Therefore,asoneapplicationofdataclassification,inthispapertextclassificationalgorithmisdiscussed
Keywords:Informationdata;Classificationalgorithm;Textclassification
II
目录
1引言........................................................................................................................................................1
1.1.研究意义.......................................................................................................................................1
1.2研究现状.......................................................................................................................................1
1.3研究目标.....................................................................................................................................3
2.经典分类方法.......................................................................................................................................4
2.1分类的概念..................................................................................................................................4
2.2经典分类算法介绍.....................................................................................................................5
2.2.1基于概率统计的分类算法..............................................................................................5
2.2.2基于粒计算的分类算法..................................................................................................7
2.2.3基于智能优化的分类算法...............................................................................................8
2.2.4其他经典分类算法..........................................................................................................11
2.3小结............................................................................................................................................15
3文本分类算法.......................................................................................................................................16
3.1文本分类介绍............................................................................................................................16
3.1.1文本分类的意义和目标.................................................................................................16
3.1.2文本分类的研究现状:.................................................................................................16
3.1.3文本分类的概念..............................................................................................................18
3.2文本分类算法............................................................................................................................18
3.2.1神经网络..........................................................................................................................18
3.2.2支持向量机......................................................................................................................19
3.2.3决策树..............................................................................................................................19
3.2.4贝叶斯算法......................................................................................................................20
3.2.5KNN算法........................................................................................................................21
4.结论和展望.........................................................................................................................................22
致谢..........................................................................................................................................................23
参考文献..................................................................................................................................................24
1
1引言
1.1.研究意义随着数字技术的不断发展,导致数据的规模不断增大,数据的研究领域不断深入,出现了海量数据。这些海量数据含有大量的有用的重要的信息,人们开始对数据进行统计分析,提取需要的信息,于是数据分类技术应运而生。
数据分类作为数据挖掘的一个分支,是在一组类别已知的数据中发现分类模型,然后将新数据映射到对应分类模型中的一个类别中去,以此来预测新数据的类别。是一种有监督的机器学习方法。从科学研究、商业、医疗卫生、银行、金融等行业都有着广泛的应用。一个我们日常生活中的例子比如:可以根据以往的生活经验,利用日照,温度,适度,风向等指标对今天的气象状况进行分类,得出两个类别:1今天适合出行2今天不适合出行。天文学家利用分类技术从海量的天文观测数据中发现稀有的天现象和天体,如恒星和星系的区分、不同活动星系核的光谱区分、APM星系的形态分类。将分类方法用于医学诊断,可以从大量的临床病例中发现某些疾病的关键特征,从而帮助医生做出更准确的诊断。
同时随着计算机和通信技术的发展,互联网的普及使用,各种文本信息发展迅速。给人们提供了大量的信息,但是同时准确而快速的查找信息变得越来越困难。因此如何合理有效地管理和组织海量的文本信息,具有很大的研究意义。
近年来,人们更重视对自动文本技术的研究,所谓的自动文本就是在给定的分类下,根据文本的内容或者属性,计算机自动的把大量文本归于所属的类别中。通过分类减轻人们处理信息的工作量。通过对文本进行的自动过滤和归类,把相关的主题的文本组织在一起实现对文本的有序组织,提高检索信息的准确率,但是这些操作的所需的共同技术基础就是文本的自动分类。可以这样认为文本分类的目标就是对文本进行有效地组织,把相同相似相关的文本组织在一起,为信息的检索和管理提供的有效地工具。所以本论文先介绍目前比较流行的和比较成熟的分类算法,在此基础上简单介绍分类算法的一个应用——文本分类
1.2研究现状
分类算法是随着信息的增长而发展起来的,也就是说分类算法的研究源于信息数据的大量增加。因此分类算法在最近几年取得了很快的发展,但是分类的概念由来已久,早在多年以前人们就已经开始着手研究分类算法。目前,形成了多种分类算法,不同的算法有其形成的背景和条件,其使用范围也不一样,应用的广度也各有不同。已经研究出的比较成熟的分类算法有:
(1)贝叶斯网络[12]:1973年,Duda和hart提出朴素贝叶斯分类器,但是由于不现实的条
第1页
皖西学院本科毕业论文(设计)
件独立性,在当时并没被看好,仅仅用于对复杂问题分类的比较对象,直到1980年之后人们才渐渐意识到贝叶斯算法的优越性,并且在某些领域的应用表现出很好的性能,由此推动了贝叶斯算法的实际应用;
(2)决策树算法[13]:1986年quinlan提出以信息论为基础的ID3算法,随着问题的出现,随后又出现对ID3改进的ID4、ID5算法,在九十年代又出现了ID4.5算法等;
(3)神经网络[14]起源于1940年左右,当时有心理学家mcculloch和数学家pitts提出的,1984年,Hopfiedld提出了神经网络中的经典的BP算法,其中160多年来神经网络经历由萧条时期到复兴时期,就目前而言,神经网络方面的理论已经相当成熟。国内方面,吴凌云[4]于2003年提出了带动量的权值批量累计调节法,王庆海提出了权值修正法;
(4)KNN算法[17]:1968由Cover和Hart提出,理论上是一个成熟的方法;
(5)粗糙集算法[7]:波兰数学家Z.Pawlak在1982年提出的。粗糙集以等价关系(不可分辨关系)为基础,它将分类理解为等价关系,用于分类问题;
(6)模糊集算法;
(7)支持向量机算法(SupportVectorMachine)法[15],由Vapnik等人于1995年提出,具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法,SVM可以自动寻找出那些对分类有较好区分能力的支持向量,由此构造出的分类器可以最大化类与类的间隔,因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果;
(8)遗传算法(geneticalgorithmsGA)[7]是一种借鉴生物界自然遗传机制和自然选择过程的搜索方法。适用于并行处理。在由上个世纪70年代产生到现在的40年里,实现了大量的应用,取得人们高度的关注。遗传算法产生于上个世纪70年代,在80年代迎来了兴盛发展时期,进入90年代遗传算法的应用研究显得非常活跃,不但其应用领域扩大而且利用遗传算法进行优化和规则学习的能力也显著提高;
[15]由Dorigo等人于1991年在第一届欧洲人工生命会议上提出,(9)蚁群算法(ACO)
是模拟自然界中真实的蚂蚁寻食过程的一种随机搜索算法。蚁群算法的基本流程包括:路径构造和信息素更新。
(10)微粒群算法(PSO)是仿生算法的一个有名的代表。是由Eberhart和Kennedy[15]于1995年提出的一种全局搜索算法,同时也是模拟自然界的生物活动以及群体智能的随机搜索方法。
近年来,传统分类方法得到改进,新的分类算法又不断出现
1.3研究目标
第2页
皖西学院本科毕业论文(设计)
本论文从四个方面对分类算法进行了研究。这四个方面是:(1)基于概率统计的分类算法:此类主要包括贝叶斯算法(2)基于粒计算的分类算法:模糊集算法、粗糙集算法(3)基于智能优化的分类算法:主要包括遗传算法,蚁群算法,粒子群算法;(4)其他经典分类算法:主要有决策树、支持向量机,神经网络,KNN算法等。研究了当前流行算法的形成背景、思想、内容等。指出一些算法的优缺点、局限性和适应范围等等。在遇到实际问题时可以根据各个算法的特点选择相应的算法,也可以采取几个算法的结合使用等。
在此基础上研究下分类算法的一个典型的应用领域——文本分类。本论文研究没有拘泥于单个算法,也没详细介绍每个算法的情况,而是从整体的角度进行研究。
第3页
皖西学院本科毕业论文(设计)
2.经典分类方法
2.1分类的概念分类[7]是在聚类的基础上,对已确定的类找出该类别的概念性描述,反应的是该类别的整体信息,是类的内涵的描述。可以采用一定的模式描述例如规则或者决策树模式。模式的作用就是能够把数据库中的元素映射到给定类别的一个或者几个。
特征描述和辨别性描述构成一个类的内涵描述。特征描述可以允许存在不同的类中的共同特性,也就是关于类中对象的共同性的描述。辨别性描述针对的是不同类的区别,就是描述不同类之间的区别,也就是说不同的类不能存在共同的特征。在实际应用中,辨别性描述用得比较多。
分类是利用数据样本通过相关的算法求得。可以通过建立分类规则和分类决策树的方法实现。常用的分类规则有遗传分类方法和粗糙集方法,常用的分类决策树方法有ID3,C4.5等
分类方法种类很多,可以从对非样本数据的判别准确度,模式的简洁度和方法实现时对时间和空间的复杂度这三个方面进行判别分类算法的好坏。
分类的方法不同则模型表示的形式不同。贝叶斯分类的模型是数学公式;决策树方法构造的模型为树状结构;神经网络的分类模型表示为网络结构
一个完整的分类过程一般包括模型构造,模型测试及模型应用。文献[16]给出了分类的三个模型即分类的的三个步骤。
第4页
皖西学院本科毕业论文(设计)
图1.分类的三个步骤
2.2经典分类算法介绍
2.2.1基于概率统计的分类算法
贝叶斯分类方法
Bayes分类法是统计学分类方法,是一种在已知先验概率与类条件概率的情况下的分类方法,待分样本的分类结果由各类域中样本的全体决定。利用Bayes定理可以预测未知类别的样本属性,选择可能性最大的类别为样本的类别。
贝叶斯分类主要有朴素贝叶斯(NB)和贝叶斯分类网络两种方法。
朴素贝叶斯是机器学习中一种基于概率统计的方法,他的理论基础是后验概率,也就是概率统计中的条件概率。基本思想是概率论的贝叶斯公式和简化假设,采取的是用类别和属性的联合概率来估计新的样本的类别。
贝叶斯网络使用图形的方法来描述数据间的关系,与朴素贝叶斯方法有些区别,它由于朴素贝叶斯方法的地方是语义清晰和可理解些强,而且有助于利用数据的因果关系进行预测分析。
下面分别介绍朴素贝叶斯方法和贝叶斯网络:
朴素贝叶斯方法
设训练样本集分为L类,记为k={k1,…,ki,…kL},每类的先验概率为P(ki),i=1,2,…,L。当样本集非常大时,可以认为P(ki)=ki类样本数/总样本数。对于一个待分样本M,
第5页
皖西学院本科毕业论文(设计)
其归于kj类的类条件概率是P(M/Ki),则根据Bayes定理,可得到kj类的后验概率P(ki/M):p(ki/M)=p(x/ci)•p(ki)/p(M)(公式1)
若p(ki/M)=Maxp(kj/X),i=1,2,...,L,J=1,2,...,N则有x∈ki(公式2)
若p(K/ki)p(ki)=Max[p(x/kj)],i=1,2,...,N,J=1,2,...,N,则M∈ki
这是用于贝叶斯分类的标准。经过长期的研究,贝叶斯分类方法在理论论据更加充分,应用非常广泛。
贝叶斯(Bayes)网络
贝叶斯(Bayes)网络作为一种快速而高效的算法而受到人们的重视,但是其要求属性独立性并不符合现实世界例如要求表达文本的关键词相互独立,这样的条件在实际文本中满足的可能性不大.这样的假设大大降低了贝叶斯网络的性能;但是如果为了考虑所有属性之间的依赖关系,使其表达依赖关系能力增强,这样又使得贝叶斯网络难以学习,因为那样使属性之间能够形成任意的有向图,增加其其结构的任意性。Bayes方法的薄弱环节还在于,类别总体的概率分布和各类样本的概率分布一般是不知道的。为了获得它们,就要求样本非常大。所以,Bayes法因此在效果上难以达到理论的最大值。
贝叶斯算法的优点[12]:1.由于贝叶斯算法综合了先验信息和样本信息,因此在样本难得的情况下非常有用;2.由于可以发现数据间的因果关系,特别适合处理不完整数据集3.在先验概率正确的前提下,准确率高。
同时贝叶斯算法也有它的不足的地方:1.如何选取先验概率,是来自以前的结论还是干脆来自于经验,这一点很受争议。2.贝叶斯方法需要进行后验概率的计算、区间估计和假设检验,所以空格复杂度和时间复杂度高。
由于贝叶斯网络的以上特征,目前对于贝叶斯网络的改进主要有:
1)基于属性选择的方法,以便确保选定的属性之间具有最大的属性独立性
2)扩展贝叶斯网络的结构,考虑属性之间的相互依赖关系,降低属性独立性的假设。
2.2.2基于粒计算的分类算法
基于粒计算的分类算法主要包括模糊集算法和粗糙集算法:
(1)模糊集算法
人类的思维中,许多概念是模糊的,如:胖子,怎么样才算胖子?不同的标准不一样,没有明确的界定,同样的体重有的人认为胖有的人认为瘦;还有身高等等。这些问题都是你无法确定那些人属于这个集合,那些人不属于这个集合。数学上,可以用特征函数或者
第6页
皖西学院本科毕业论文(设计)
数字来描述某一集合,但是对于模糊事物这种方法显然是不行的
就精确分类来说,分类就是采取一定的方法把某些特征类似的数据划分在一起,把一个对象的集合划分为若干子集,在每个自己的数据具有某些类似的特征。而在实际中有时候不能把某一对象确定的划分为某一类,只能说某一对象划分为某一类的可能性多大,人们据这一现象引入了模糊集的概念。
利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的杂性越高,模糊性越强,一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人[6]在传统模糊理论和概率统计的基础上,提出了定性定量不确定性转换模型--云模型,并形成了云理论。
(2)粗糙集分类方法[7]是波兰数学家Z.Pawlak在1982年提出的。粗糙集(roughset)粗糙集以等价关系(不
可分辨关系)为基础,它将分类理解为等价关系,用于分类问题。从粗糙集的本质来看,反映的就是认知过程在非模型化、非确定化信息处理方面的机制和特点因此成为一种有效的非单调推理方法
它用上下近似两个集合来逼近任意一个集合,该集合的边界区域被定义为上近似集和下近似集之差集。上下近视集可以通过等价关系给出确定的描述,边界域的含糊元素数目可以被计算出来。这一点与模糊集不同,虽然粗糙集和模糊集都是人们根据不确定问题提出来的,模糊集需要依靠先验知识对不确定问题的定量描述就如统计中的先验概率,而粗糙集知识依靠数据间的内部知识即数据间的近似来表示数据的不确定性。可以说模糊集是用隶属度来描述集合边界的不确定性,隶属度是人为给定的,不是计算出来的。所以我们可以得出粗糙集在处理不确定问题的优势在于不需要数据的预先信息。
运用粗糙集的理论和方法可以从数据中发现分类规则。粗糙集的思想[7]是:对待分样本中的属性分为条件属性和结论属性,对样本数据中的元祖根据各个属性的不同属性值让其分为不同的子集,最后对条件属性划分的子集与结论属性划分的子集之间的上下近似关系生成判定规则。
粗集方法有几个优点:不需要给出额外信息;简化输入信息的表达空间;算法简单,易于操作。粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统,为粗集的数据挖掘奠定了坚实的基础。但粗集的数学基础是集合论,难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗集理论实用化的难点
2.2.3基于智能优化的分类算法
第7页
皖西学院本科毕业论文(设计)
主要包括遗传算法、蚁群算法、粒子群算法。
(1)遗传算法遗传算法(geneticalgorithmsGA)是一种借鉴生物界自然遗传机制和自然选择过程的搜索方法。适用于并行处理。在由上个世纪70年代产生到现在的40年里,实现了大量的应用,取得人们高度的关注。遗传算法产生于上个世纪70年代,在80年代迎来了兴盛发展时期,进入90年代遗传算法的应用研究显得非常活跃,不但其应用领域扩大而且利用遗传算法进行优化和规则学习的能力也显著提高。
遗传算法是一种基于遗传学的搜索优化方法。遗传算法的流程图如下[7]:
图2.遗传算法流程示意图
遗传算法首先把问题的每个可能出现的解进行编码,编码好的解称为个体(染色体)。随机选取N个染色体构成初始种群,在根据预定的评价函数对每个染色体计算适应值,使得性能较高的染色体具有较高的适应性选择适应值高的染色体进行复制,通过遗传算子的选择、交叉,变异来产生一群新的更适应环境的染色体,形成新的种群。这样一代代不断
第8页
皖西学院本科毕业论文(设计)
繁殖进化,最后收敛到一个最适应环境的个体,求得问题的最优解。
遗传算法的理论基础是Holland提出的模式理论(schematatheorem)[1]。遗传算法是模拟自然选择和生物遗传机制的优化算法,利用3个遗传算子产生后代,通过群体的迭代,使个体的适应性不断提高,最终群体中适应值最高的个体即优化问题的最优或者次优解。遗传算法相比传统的优化方法有不同的特点[7]:
1)遗传算法是进行群体的搜索。对多个个体进行群体的搜索也就是在问题空间中多个个体在不同的区域进行搜索,构成一个不断进化的群体序列。在对于复杂问题的多峰情况,遗传算法也能以最大的概率全局最优解;
2)遗传算法是个随机搜索方法;
3)遗传算法处理的对象是个体的编码,而不是参变量本身;
4)遗传算法不需要导数或者其他辅助信息;
5)隐含并行性。
隐含并行性是遗传算法优于传统的搜索方法的关键所在。
对于遗传算法文献[2]指出存在收敛速度慢和易于陷入局部最优的问题,在需要优化的参数比较多时,更加凸显了遗传算法的不足。因此如何提高遗传算法跳出局部最优的能力和如何提高遗传算法的收敛速度成为近年来遗传算法的研究重点。许多学者从不同的角度对遗传算法提出来改进。主要有以下改进算法:混合遗传算法;自适应遗传算法;变长染色体遗传算法;小生境遗传算法;并行遗传算法
(2)基于群的分类方法
自然是人们创作的源泉,人们很早起社会就对自然界的群集现象发生了兴趣。如大雁在飞行过程中排成人字形;蝙蝠在狭小的洞中快速的飞行而不发生碰撞。对这一现象的令人信服的解释是:群里中的每个个体都遵循一定的规则,他们按各自的规则相互作用而完成这一复杂的行为。在自然界中,鸟类、蚂蚁等等以集体的力量生存和觅食。人们以群体为主要的载体,通过他们之间的直接或者间接的通讯进行并行式问题的解决模型提出来基于群的算法
可以将这种方法分为两类:一类是蚁群算法(ACO);另一类称为微粒群算法(PSO)。蚁群算法(ACO)[15]由Dorigo等人于1991年在第一届欧洲人工生命会议上提出,是模拟自然界中真实的蚂蚁寻食过程的一种随机搜索算法。蚁群算法的基本流程包括:路径构造和信息素更新。
蚁群算法的特点[3]:多解性;较强的鲁棒性;分布式计算;实验结果优;速度快;易于和其他方法结合。
第9页
皖西学院本科毕业论文(设计)
蚁群算法虽然有很多优点,但是也有不足的地方。需要较长的搜索时间,其算法具有很大的时间复杂度,如果处理的问题的规模很大时,这种不足就更为明显。针对这一问题目前提出来一些改进算法如:变异群算法;快速改进的蚁群算法;排序加权的蚁群算法。
微粒群算法(PSO)有的著作上也称为粒子群算法,是仿生算法的一个有名的代表。是由Eberhart和Kennedy[15]于1995年提出的一种全局搜索算法,同时也是模拟自然界的生物活动以及群体智能的随机搜索方法。。
在动物的群体行为中,比如鱼群、鸟群的迁移、扑食往往高度的组织性和规律性。在自然界鸟群扑食的过程中,小鸟是如何找到事物的?实际上,扑食的鸟群在各自的寻找和群体的合作过程中找到食物的。假设这种情况,有一群分散的小鸟在寻找食物,他们都不知道食物在哪。其中有一只小鸟发现了食物的位置,于是各个小鸟会在他们飞行的过程中不断地记录和更新他们距于食物的最佳位置,同时他们通过信息交流的方式比较大家找到的最好的位置,得到当前群体已经找到的最佳位置。这样,每个小鸟在飞行的时候就有一个寻找的方向,他们会结合自身的经验和群体的经验,不断调整自己的飞行速度和所在位置,不断地寻找更加接近事物的位置,最终可以得到群体到食物的位置。
上面的例子中,鸟群的每个小鸟就是一个“粒子",通过随机产生的粒子作为问题搜索空间的有效解,然后进行迭代搜索,求出最优的结果。
由于PSO算法用于分类问题还处于初期,因此要将其运用到大规模的应用中还要大量的研究。
2.2.4其他经典分类算法
包括决策树、支持向量机、神经网络、KNN算法等。
(1)决策树的分类方法
基于决策树的分类算法是数据挖掘中最为典型的分类算法。
决策树(DecisionTree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。由以上描述可知,决策树的建立的过程可以认为是数据分类规则的生成过程,实现了数据分类规则的可视化,其输出结构也容易理解。
决策树是个类似于流程图的树形结构,采用的方式是自顶而下的递归方式,在其内部节点进行属性值的比较,并根据不同的属性值判断由该节点向下的分支,最终在决策树的叶节点得到结论,纵观整个过程都是以新节点为根的子树上重复。下图就是一个决策树的
第10页
皖西学院本科毕业论文(设计)
图3.决策树示意图
决策树算法是一种常用和直观的分类算法。目前决策树方法中比较流行的算法[1]有ID3、C4.5、SLIQ、CART、SPRINT等。这些算法都是对数据样本集建立一颗决策树,从而对数据进行预测的。在这些算法中ID3算法最为经典,其他算法都是由此算法发展改变而来的,因此在决策树算法中重点介绍ID3算法。最典型的决策树学习算法是ID3,它采用自顶向下的无回溯策略,可以保证找到一个简单的树。
ID3算法的核心[17]是:在决策树各级结点上选择属性时,用信息增益(informationgain)作为属性的选择标准,以使得在每一个非叶结点进行测试时,能获得关于被测试记录最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。
ID3算法的优点是算法的理论清晰、方法简单、学习能力较强。其缺点是只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变。
以下是决策树工作原理流程图:
第11页
皖西学院本科毕业论文(设计)
图4.决策树工作原理流程图
ID3算法是较早的决策树归纳算法。C4.5是ID3的改进算法,不仅可以处理离散值属性,还能处理连续值属性,但是也不能进行增量学习。算法C4.5和C5.0是ID3的扩展,它们将分类领域从类别属性扩展到数值型属性。决策树善于处理数值数据,从决策树可以很容易地使用在分类规则提取。其主要优点是描述简单、分类速度快,特别适用于大型数据处理。缺陷是相比遗传算法往往选择属性更倾向于经常使用的最佳属性:学习简单的逻辑表达能力弱。
(2)支持向量机方法
SVM法即支持向量机(SupportVectorMachine)法[11],由Vapnik等人于1995年提出,具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法,SVM可以自动寻找出那些对分类有较好区分能力的支持向量,由此构造出的分类器可以最大化类与类的间隔,因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。
支持向量机算法的目的在于寻找一个超平面H(d),该超平面可以将训练集中的数据分开,且与类域边界的沿垂直于该超平面方向的距离最大,故SVM法亦被称为最大边缘(maximummargin)算法。待分样本集中的大部分样本不是支持向量,移去或者减少这些样本对分类结果没有影响,SVM法对小样本情况下的自动分类有着较好的分类结果。
文献[11]提出了一种多分类问题的改进支持向量机,将GA和SVM相结合,构造了一种参
第12页
皖西学院本科毕业论文(设计)
数优化GASVM,该方法在多分类非平衡问题上,提高了分类正确率,也提高了学习时间。文献[18]提出了一种新的支持向量机增量算法,提出了一种误分点回溯增量算法,先找出新增样本中误分的样本,然后在原样本集寻找距误分点最近的样本作为训练集的一部分,重新构建分类器,有效保留样本的分类信息,结果表明比传统的SVM有更高的分类精度。
(3)神经网络
神经网络是分类技术中重要方法之一。目前神经网络分类算法研究较多集中在以BP为代表的神经网络上。文献[4]提出了粒子群优化算法用于神经网络训练,在训练权值同时删除冗余连接,与BP结果比较表明算法的有效性。文献[14]提出旋转曲面变换粒子群优化算法的神经网络,使待优化函数跳出局部极值点,提高训练权值的效率。
神经网络主要有前向神经网络、后向神经网络和自组织网络。是大量的简单神经元按一定规则连接构成的网络系统。它能够模拟人类大脑的结构和功能,采用某种学习算法从训练样本中学习,并将获取的知识存储在网络各单元之间的连接权中。
神经网络分类算法的重点是[4]构造阈值逻辑单元,一个值逻辑单元是一个对象,它可以输入一组加权系数的量,对它们进行求和,如果这个和达到或者超过了某个阈值,输出一个量。如有输入值X1,X2,...Xn和它们的权系数:W1,W2,...Wn,求和计算出的Xi*Wi,产生了激发层a=(X1*W2)+(X2*W2)+...+(Xi*Wi)+...+(Xn*Wn),其中Xi是各条记录出现频率或其他参数,Wi是实时特征评估模型中得到的权系数。神经网络的学习就是通过迭代算法,就是对权值进行逐步修改的优化过程。学习的目的是通过改变权值使样本都能被正确分类。
神经网络适合以下情况:
数据量比较小,而缺少足够的样本来建立数学模型;X1,X2,...Xn
分类模型难以用传统的统计模型表示;
数据的结果用传统的统计方法描述;
神经网络的优点:具有联想记忆的功能;分类准精度高;分布储存和学习能力高;能很比较复杂的线性关系;对噪声有容错能力
缺点:学习时间长;需要的参数多;中间的学习过程不能观测等等。神经网络是基于经验风险最小化原则的学习算法,有一些本身的缺陷,比如层数和神经元个数难以确定,容易陷入局部极小,还有过学习现象,这些在支持向量机算法中可以得到很好的解决
神经网络分类算法的研究主要集中在由BP为代表的神经网络。
(4)KNN法(K-NearestNeighbor)
第13页
皖西学院本科毕业论文(设计)
KNN法即K最近邻法,最初由Cover和Hart[7]于1968年提出的,是一个理论上比较成熟的方法。该方法的思路非常简单直观:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
K近邻分类算法是最简单有效的分类方法之一,因为是在多维空间中找到与未知样本最近邻的K个点,并根据这K个点的类别判断未知样本的类别。但是有两个最大缺点:1)由于要存储所有的训练数据,所以对大规模数据集进行分类是低效的;2)分类的效果在很大程度上依赖于K值选择的好坏。文献[17]提出一种有效的K近邻分类算法,利用向量方差和小波逼近系数得出两个不等式,根据这两个不等式,分类效率得到了提高。文献[18]提出用粒子群优化算法对训练样本进行有指导的全局随机搜索,掠过大量不可能的K向量,该算法比KNN方法计算时间降低了70%[18]。
该方法虽然原则上也依赖于极限定理,但在分类中起决定作用的只有很小数量的相邻样本。因此,利用这种方法可以有效地避免样本不平衡。此外,由于方法主要依赖于周围的有限相邻的样本,而不是依靠判别的方法来确定各自的类别,所以对于交叉或重叠域较多的样本,该方法比其他方法更好,更适合。
KNN法的优点是原理简单,实现起来比较方便。支持增量学习。能对超多边形的复杂决策空间建模。该方法的缺点:计算开销大,需要有效的存储技术和并行硬件的支撑。
该算法是适用于样本大小是比较大的域的自动分类,小样本的域中的应用这种算法比较容易产生错误点。
2.3小结
本节从四个方面对分类算法进行了研究。研究了当前流行算法的形成背景、思想、内容等等。指出一些算法的优缺点、局限性和适应范围等等。是遇到实际问题时可以根据各个算法的特点选择相应的算法,也可以采取几个算法的结合使用等。随着信息数据的快速增长,分类算法具有广阔的应用空间,在处理问题时大量使用,下面一节就分类算法在文本分类中的应用做下研究。
第14页
皖西学院本科毕业论文(设计)
3文本分类算法
3.1文本分类介绍
3.1.1文本分类的意义和目标
随着计算机和通信技术的发展,互联网的普及使用,各种文本信息发展迅速。给人们提供了大量的信息,但是同时准确而快速的查找信息变得越来越困难。因此如何合理有效地管理和组织海量的文本信息,具有很大的研究意义。近年来,人们更重视对自动文本技术的研究,所谓的自动文本就是在给定的分类下,根据文本的内容或者属性,计算机自动的把大量文本归于所属的类别中。通过分类减轻人们处理信息的工作量。通过对文本进行的自动过滤和归类,把相关的主题的文本组织在一起实现对文本的有序组织,提高检索信息的准确率,但是这些操作的所需的共同技术基础就是文本的自动分类。可以这样认为文本分类的目标就是对文本进行有效地组织,把相同相似相关的文本组织在一起,为信息的检索和管理提供的有效地工具。
3.1.2文本分类的研究现状:整体来说,我国国内文本分类的研究起步较晚[5],大多理论是借鉴于国外的技术,比如说,国内学者在英文分类研究的基础上采取相应的策略,结合中文文本的特征和汉字的特点,提出了中文文本分类体系。
当前,国外的文本分类已经由最初的理论研究进入实用阶段,在信息过滤,电子邮件等等方面得到了应用。比如:自动web叶的文本分类器;自动跟踪用户阅读兴趣的分类分析器等。
无论是那种分类系统所用的都是目前比较流行的文本分类方法。比如文献[19]提出:nativebayes、SVM、神经网络、遗传算法、KNN等在文本分类的应用。而且指出其中KNN、nativebayes、SVM分类效果较好。
文本分类问题与其它分类问题没有本质上的区别,其方法可以归结为根据待分类数据的某些特征来进行匹配,当然完全的匹配是不太可能的,因此必须(根据某种评价标准)选择最优的匹配结果,从而完成分类
综观目前的文本分类算法,文献[5]提出可以归结为三个方面:传统文本分类;层次分类;基于知识的分类。
下面就这三个方面做出介绍:
传统文本分类
文本分类一直是人们重视并且研究的领域,互联网和搜索引擎的发展更是促进了对文本分类的研究。早在20世纪五十年代,就有学者开始对文本分类进行研究,但是直到上个
第15页
皖西学院本科毕业论文(设计)
世纪末,在有限样本情况下的机器学习理论研究才逐渐成熟起来。当今,人们已经提出来许多与分本分类相关的算法如支持向量机模型(SVM)、k值临近模型(KNN),贝叶斯模型(NB)等,这些都是基于机器学习理论的,其中支持向量机是最为广泛的研究应用的方法之一。
在面对标准数据集方面,大量的实验表明,这些分类在传统的文本分类应用中是非常有效地
但是随着互联网规模的发展,web文档所属的类别规模越来越庞大,这就涉及到多类别分类,甚至大规模类别分类。
传统文本分类的理论虽然很成熟,但是近年来也面临不少问题。比如:当类别规模增大时,准确度会下降,以致分类结果会出现问题;类别规模增大时,传统的分类算法会产生很长的训练时间。类别通常都是层次结构的,存在父子关系,是树形的结构,或者图形结构,这些都对传统的文本分类提出了挑战。
层次分类
现实中很多类别体系都很庞大,而传统的文本分类只是关注于水平分类,按这种平面分类显然是不行的。所谓的水平分类是指类别之间是孤立的,没有任何联系的。大规模分类体系通常是树形的层次结构。所以,面对这种大规模的分类体系应该采取层次结构。通常层次结构采取的方法是:Big-bang方法和Top-down[19]方法。
(1)Big-bang方法
主要采取的实现方式是:基于SVM,基于关联规则,基于规则的分类器等。Big-bang分类器是将待分文档分类到类别树中的一个或者多个类别。此方法只采用一个分类器。所以不够灵活,而且无法应付待分类别结构的变化,很难利用不同层类别的特征。
(2)Top-down方法。
Top-down方法,即自顶而下方法,主要用SVM和贝叶斯方法实现。与Big-bang方法只使用一个分类器不同的是在每个类别层构造多个分类器,每个分类器只是作用于该层。整个分类过程是由最顶层开始逐步分类直到最底层。但是正是由于这种层次特点,一旦上层分类出现错误就会逐级传递到下层。同样的,灵活性差,一旦类别发生改变,每个分类就要进行重新训练。但是总体来说,在许多方面还是比Big-bang方法好。
对比层次分类的两种方法,他们都有个共同的不足就是灵活性差,由于Top-down方法采用多个分类器所以灵活性更差。因此,都不太适合应付类别体系的变化。
基于知识的分类
此类方法研究的主要问题是怎么利用互联网文本丰富的语义进行分类。基于知识的分
第16页
皖西学院本科毕业论文(设计)
类主要采取的方法是支持向量机,所以仍然具有SVM算法面临新问题表现的不足方面。
3.1.3文本分类的概念
文本分类问题就是将一篇文档归入预先定义的几个类别中的一个或几个,而文本的自动分类则是使用计算机程序来实现这样的分类。
注意这个定义当中着重强调的两个事实。
第一,用于分类所需要的类别体系是预先确定的。例如新浪新闻的分类体系,Yahoo!网页导航的分类层次。这种分类层次一旦确定,在相当长的时间内都是不可变的,或者即使要变更,也要付出相当大的代价(基本不亚于推倒并重建一个分类系统)。
第二,一篇文档并没有严格规定只能被分配给一个类别。这与分类这个问题的主观性有关,例如找10个人判断一篇文章所陈述的主题究竟属于金融,银行还是财政政策领域,10个人可能会给出10个不同的答案,因此一篇文章很可能被分配到多个类别当中,只不过分给某些类别让人信服,而有些让人感觉模棱两可罢了(置信度不一样)。
当然,目前真正大量使用文本分类技术的,仍是依据文章主题的分类,而据此构建最多的系统,当属搜索引擎。文本分类还不完全等同于网页分类。网页所包含的信息远比含于其中的文字(文本)信息多得多,对一个网页的分类,除了考虑文本内容的分类以外,链入链出的链接信息,页面文件本身的元数据,甚至是包含此网页的网站结构和主题,都能给分类提供莫大的帮助(比如新浪体育专栏里的网页毫无疑问都是关于体育的),因此说文本分类实际上是网页分类的一个子集也毫不为过。当然,纯粹的文本分类系统与网页分类也不是一点区别都没有。文本分类有个重要前提:即只能根据文章的文字内容进行分类,而不应借助诸如文件的编码格式,文章作者,发布日期等信息。而这些信息对网页来说常常是可用的,有时起到的作用还很巨大!因此纯粹的文本分类系统要想达到相当的分类效果,必须在本身的理论基础和技术含量上下功夫。
除了搜索引擎,诸如数字图书馆,档案管理等等要和海量文字信息打交道的系统,都用得上文本分类。
3.2文本分类算法
3.2.1神经网络可以构造神经网络用于文本分类。一般,网络的输入节点接受特征值,输出接点可以用来产生类别状态值,连接权值代表依赖关系。为了实现文本分类,可以把特征权值加载到输入节点,被激活的节点通过网络向前传播,进而输出节点得到最终值决定。分类神经网络通过反向传播训练,也就是文本在输入节点加载。即使分类错误发生,错误通过网络反馈,通过修改连接权重,可以使分类错误较少发生,。
第17页
皖西学院本科毕业论文(设计)
简单的神经网络是感知机。只有输入节点和输出节点两层,相当于现行分类器。相对简单的神经网络,包括一个输入层、一个输出层、多个隐藏层的网络属于复杂网络。其实在文本分类中,很少或者没有非线性网络能对线性网络改进。
3.2.2支持向量机
图5.最大边界例子
SVM超平面完全由很小实例确定,具有这种特性的示例被叫做支持向量,而其他的示例对分类器的训练不影响。在这一方面,支持向量机算法不同于其他分类算法
3.2.3决策树
在决策树文本分类算法中,类别是通过从树根开始根据所满足的条件依次向下直到叶节点为止,叶的类别表示的就是文本的类别。下面引用文献[19]上的对二值文本表示的二叉决策树分类器
第18页
皖西学院本科毕业论文(设计)
图6.对二值文本表示的二叉决策树分类器
大多数的决策树系统采用ID3、C4.5进行归纳。一般情况下,树是递归的创建。在每个步骤选择一定的特征
F,把训练划分为两个子集,一个包含F,另一个不包含F,如此反复,直到每个子集只有一个类别的文本而生成叶节点。
不过一般在分类任务中很少单独使用此算法。
3.2.4贝叶斯算法
第19页
皖西学院本科毕业论文(设计)
首先,p(d/Ci)之所以能展开成(公式)的连乘积形式,就是假设一篇文章中的各个词之间是彼此独立的,其中一个词的出现丝毫不受另一个词的影响(概率论中变量彼此独立的概念),但这显然不对,即使不是语言学专家的我们也知道,词语之间有明显的所谓“共现”关系,在不同主题的文章中,可能共现的次数或频率有变化,但彼此间绝对谈不上独立。其二,使用某个词在某个类别训练文档中出现的次数来估计p(wi/Ci)时,只在训练样本数量非常多的情况下才比较准确
3.2.5KNN算法
kNN算法则又有所不同,在kNN算法看来,训练样本就代表了类别的准确信息(因此此算法产生的分类器也叫做“基于实例”[13]的分类器),而不管样本是使用什么特征表示的。其基本思想是在给定新文档后,计算新文档特征向量和训练文档集中各个文档的向量的相似度,得到K篇与该新文档距离最近最相似的文档,根据这K篇文档所属的类别判定新文档所属的类别(注意这也意味着kNN算法根本没有真正意义上的“训练”阶段)。这种判断方法很好的克服了无法处理线性不可分问题的缺陷,也很适用于分类标准随时会产生变化的需求(只要删除旧训练文档,添加新训练文档,就改变了分类的准则)。kNN唯一的也可以说最致命的缺点就是判断一篇新文档的类别时,需要把它与现存的所有训练文档全都比较一遍,这个计算代价并不是每个系统都能够承受的(比如我将要构建的一个文本分类系统,上万个类,每个类即便只有20个训练样本,为了判断一个新文档的类别,也要做20万次的向量比较!)。一些基于kNN的改良方法比如GeneralizedInstanceSet[19]就在试图解决这个问题。
第20页
皖西学院本科毕业论文(设计)
4.结论和展望本论文回顾了分类算法产生的背景即信息数据的快速增长,出现了海量的信息数据,导致人们在查找有效的数据时出现困难,进而出现分类算法。研究的重点在于数据分类算法,主要从四个方面对分类算法进行研究(1)基于概率统计的分类算法:此类主要包括贝叶斯算法(2)基于粒计算的分类算法:模糊集算法、粗糙集算法(3)基于智能优化的分类算法:主要包括遗传算法,蚁群算法,粒子群算法;(4)其他经典分类算法:主要有决策树、支持向量机,神经网络,KNN算法等。研究了每个算法的内容,比较了一些算法的优缺点及其使用范围等情况。在次基础上研究下分类算法的一个典型的应用领域——文本分类
文本分类的内容很丰富,涉及多学科知识,也是当今研究的热点。虽然文本分类算法种类繁多,本文总结了目前的文本分类算法发展可以归结为三个方面:传统文本分类;层次分类;基于知识的分类。其实这三个方面都离不开基本文本分类算法,因此本论文介绍文本分类算法发展的三方面的趋势之后介绍了基本的五类文本分类算法。在介绍五种基本分类算法时是基于算法的角度进行了介绍了,这五种文本分类算法是神经网络、支持向量机、决策树、贝叶斯算法、KNN算法。主要介绍了每个分类算法在文本分类的应用,及其局限性和发展潜力。至于文本分类的实现过程在本文没有详细介绍。文本分类的各个算法在文本分类的具体应用和实现过程并非本论文的重点,有待以后进一步研究。
第21页
皖西学院本科毕业论文(设计)
致谢在此我要感谢我的论文老师何富贵老师,从选题到论文完成过程中给我很多指导和建议。
还有感谢辅导员和信息工程学院的各位老师在我大学四年里给我生活上的关心和学业上的指导。使我能够顺利完成学业,深表感谢!
感谢我身边的同学和朋友,感谢他们在论文完成过程中提的建议和给予的帮助。
第22页
皖西学院本科毕业论文(设计)
参考文献
[1]朱明.数据挖掘[M].中国科学技术出版社,2008.
[2]李明,.王燕,年福忠.智能信息处理和应用[M].电子工业出版社,2010.
[3]曹承志.人工智能技术[M].清华大学出版社,2010.
[4]蔡绍斌.基于神经网络的数据分类研究[D].大连理工大学,2007.
[5]金海,袁平鹏.语义网数据管理技术及应用[M].科学出版社,2010.
[6]张军,詹志辉.计算机智能[M].清华大学出版社,2009.
2010.[7]陈文伟.知识工程和知识管理[M].清华大学出版社,
[8]徐宏伟.数据挖掘中决策树分类算法的研究与改进[D],哈尔滨工程大学,2010.
[9]谢作将.面向朴素贝叶斯算法的离散化方法研究[D],北京交通大学,2008.
[10]王俊艳.浅谈分类算法的发展[J].2010,31(4):1085-1097.
[11]熊浩勇.基于SVM的中文文本分类算法研究与实现[D],武汉理工大学,2010.
[12]谢作将.面向朴素贝叶斯算法的离散化方法研究[D],北京交通大学,2008.
[13]胡可云,田凤站,黄厚宽.数据挖掘理论与应用[M].清华大学出版社,2008.
[14]蔡绍斌.基于神经网络的数据分类研究[D],大连理工大学,2007.
[15]张军,詹志辉.计算机智能[M].清华大学出版社,2009.
[16]杨春燕,李小妹,陈文伟,蔡文.可拓数据挖掘方法及其计算机实现[M].广东高等教育出版社,2010.
[17]乔玉龙,潘正祥,孙圣和.一种改进的快速K近邻分类算法[J].电子学报,2005,6.第6期p1147—1149.
[18]张国英,沙芸,江惠娜.基于粒子群优化的快速KNN分类算法[J].山东大学学报,2006,6.第4l卷第3期p34—42.
[19]程显毅,朱倩.文本挖掘原理[M].科学出版社,2010.
第23页