基于决策树的属性约简方法研究

《基于决策树的属性约简方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河北科技大学硕士学位论文基于决策树的属性约简方法研究姓名：李萍申请学位级别：硕士专业：应用数学指导教师：李法朝20090501摘要摘要分类是数据挖掘的～项核心任务，而分类的依据常常是所关心的问题的某些方面的特征(通常称之为属性)。由于数据库中的数据往往与给定的属性集中的某些属性的状态(即取值)无关或关联不大，直接采用给定的属性集来挖掘知识将增大数据挖掘的难度，特别，对于巨型数据库而言，可能会导致相关数据挖掘算法的失效，因而，如何精练数据挖掘的属性集(称之为属性约简)，是数据挖掘的一个关键环节。目前的属性约简算法大都是以波

2、兰数学家Z．Pawlak于1982年提出的粗糙集作为理论基础，其主要思想就是在保持分类能力不变的前提下，通过约简，导出问题的决策或分类规则。虽然这些算法均具有良好的理论基础，但它们的空间复杂度和时间复杂度都较高，不能有效地处理大型数据库的属性约简问题。决策树算法是目前机器学习领域中最为成熟的内容，其优点为：1、)决策树方法结构简单，无需了解很多的背景知识；2)决策树模型效率较高，对训练样本集数据量较大的情况尤为适合；3)决策树算法的计算量相对较小；4)决策树方法具有较高的分类精确度。因此，本文结合决策树算法操作简单、分类

3、速度快的特点，通过将知识库抽象为规则族及规则族之间的相似性比较，建立了一种基于决策树的属性约简方法(简记为BD—RED)，具体工作如下：1)建立了规则的形式化描述模式；2)从结构化的角度讨论了规则族之间的相似性度量的构建问题；3)给出了BD—RED的具体实施原则；4)结合具体实例分析了BD．RED的特征和性能。结果表明，BD．RED具有良好的结构特征和较强的可操作性，可以有效地实现不同决策理念下的属性约简，适合不同类型的大规模数据库的属性约简。最后，我们提出了改进的ID3算法(C．ID3算法)，本文针对归纳学习所依赖的示

4、例存在缺失值的情况，先对数据库做一个初步的可信度计算，然后结合ID3算法作出决策树，该算法生成的规则更精确，而且还能根据具体需要得到合适的规则。理论分析和试验仿真都表明，该方法不仅具有较强的可操作性，而且能够提高所得知识的精确度。关键词数据挖掘；属性约简；决策树；粗糙集；C．ID3算法；规则；信息增益；节点纯度；可信度；相似度量河北科技大学硕士学位论文j％I=

5、自；目I

6、===自j％=====≈========自==目============；===================：；====：=AbstractClas

7、sificationisacoretaskofdatamining，andthebasisofwhichisthecharacteristicsofsomeconcems(usuallycalledattributes)．AsthedatainthedatabaseiSusuallyunrelatedtOorhavesmallrelationwithstates(thatis，value)ofsomeattributesofagivenattributeset，usingthegivenattributesetdirec

8、tlytomineknowledgewillincreasethedifficultyofdatamimng．Inparticular,forthehugedatabase，itmayresultinfailuretodataminingalgorithm．Therefore，howtosimplifyattributeset(knownastheattributereduction)isakeylinkofdatamining．Atpresent，theoreticalfoundationoftheattributer

9、eductionalgorithmiSbasedmostlyonroughsetbyaPolishmathematiciannamedZ．Pawlakin1982．Underthepremiseofkeepingtheconstantabilityofcategorize，themainideaofthetheoryistooutputthedecisionoftheproblemorthecategorizedrulethroughthereductionofknowledge．Althoughallthesealgo

10、rithmshavegoodtheoreticalbase，theyhaveacommonweakness，thatis，forthehugedatabase，thecomplexityofspaceandtimeishigher．Atpresent，decisiontreealgorithmisthemostsop