基于粗糙集和Trie树的知识约简方法研究

《基于粗糙集和Trie树的知识约简方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号!旦墨1l密级公开重庆邮电大学硕士学位论文论文题目基于粗糙集和Trie树的知识约简方法研究英文题目onTrieTreeandRoughSetTheory论文提交日期2Q12生垒月论文答辩日期2Q12生5目论文评阅人答辩委员会主席王越教授重庆理工大学2012年5月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽由g鱼太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意

2、。学位论文作者签名：壬心、藏签字日期：2012．年5月30日-_’、、_、、、学位论文版权使用授权书本学位论文作者完全了解重麽邮电太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重麽由g电太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：王小燕，导师签名：签字日期：2012年f月3D日签字日期吾历仁年占月J日重庆邮电大学硕士论文摘要粗糙集理论作为一种新的处理模糊信息和不确定信息的软计算工具，于198

3、2年由波兰科学家Z．Pawlak创立。知识约简是粗糙集理论研究中的核心内容之一，如何快速有效地对海量数据进行知识约简，并从中挖掘出有效的知识是粗糙集理论研究的一个热点。至今，很多学者已提出了大量关于属性约简和属性值约简的研究方法。但是，现有的粗糙集知识约简算法的时间复杂度较高，对于大数据集的处理效率不高。这大大的限制了粗糙集的实际应用。因此，研究高效的处理海量数据的知识约简方法很有必要。Trie树是一种树形结构，它是一种哈希树变种，典型应用于统计、排序和保存大量的字符串，因此经常被搜索引擎系统用于文本词频统计。由于它的查询效率比哈希树高，如果把它运用到粗糙集知识约简算法的研究中，则可

4、能得到能处理海量数据的快速知识约简算法。本文结合Trie树查找效率高的特点，开展了基于Trie树以及粗糙集理论的知识约简算法的研究。首先，将Trie树用于求取决策表的正区域中，当决策表中一个对象插入Trie树时，表现为一个从根节点到叶子节点的分支，在叶子节点计算决策表的正区域，在此基础上，结合贪心算法提出了一种时间复杂度较低的属性约简算法。其次，将Trie树用于属性约简后的决策表覆盖计算，由于属性值约简过程中的决策表是一个存在部分缺省值的不完备决策表，当决策表中对象插入Trie树时，必须考虑Trie树中的空值节点与同一层其它兄弟节点的匹配问题，并同样在叶子节点得到决策表的覆盖，利用此

5、覆盖计算方法，提出了一种时间复杂度较低的属性值约简算法。本文结合Trie树，以提高粗糙集知识约简算法的处理效率为出发点，提出了一种高效的知识约简算法。通过仿真对比实验结果进行分析，本文的知识约简算法处理大数据集的时间效率相对更高，说明了本文算法的有效性。关键词：粗糙集，Trie树，属性约简，属性值约简，正区域，覆盖重庆邮电大学硕士论文AbstractAsanewkindofsoftcomputingtoolfordealingwithfuzzyanduncertaininformation，Roughsettheoryfoundedin1982byaPolishscientistZ．

6、Pawlak．Knowledgereductionisoneofthecorecontentoftheroughsettheory．Howtoobtainknowledgereductionandminevaluableknowledgequicklyfromhugedatasetshasbeenahotissueofroughsettheory．Sofar,manyscholarshaveproposedalargenumberofmethodsaboutattributereductionandattributevaluereduction．Buttheexistedalgori

7、thmsaboutknowledgereductionusuallyhaveahightimecomplexitywhenprocessingdatasets，especiallyduringtheprocessofhugedatasets．Thisgreatlylimitsthepracticalapplicationofroughset．Therefore，it’Snecessarytoresearchtheefficientknowledgeredu