论文部分内容阅读
粗糙集理论作为一种新的处理模糊信息和不确定信息的软计算工具,于1982年由波兰科学家Z.Pawlak创立。知识约简是粗糙集理论研究中的核心内容之一,如何快速有效地对海量数据进行知识约简,并从中挖掘出有效的知识是粗糙集理论研究的一个热点。至今,很多学者已提出了大量关于属性约简和属性值约简的研究方法。但是,现有的粗糙集知识约简算法的时间复杂度较高,对于大数据集的处理效率不高。这大大的限制了粗糙集的实际应用。因此,研究高效的处理海量数据的知识约简方法很有必要。
Trie树是一种树形结构,它是一种哈希树变种,典型应用于统计、排序和保存大量的字符串,因此经常被搜索引擎系统用于文本词频统计。由于它的查询效率比哈希树高,如果把它运用到粗糙集知识约简算法的研究中,则可能得到能处理海量数据的快速知识约简算法。本文结合Trie树查找效率高的特点,开展了基于Trie树以及粗糙集理论的知识约简算法的研究。首先,将Trie树用于求取决策表的正区域中,当决策表中一个对象插入Trie树时,表现为一个从根节点到叶子节点的分支,在叶子节点计算决策表的正区域,在此基础上,结合贪心算法提出了一种时间复杂度较低的属性约简算法。其次,将Trie树用于属性约简后的决策表覆盖计算,由于属性值约简过程中的决策表是一个存在部分缺省值的不完备决策表,当决策表中对象插入Trie树时,必须考虑Trie树中的空值节点与同一层其它兄弟节点的匹配问题,并同样在叶子节点得到决策表的覆盖,利用此覆盖计算方法,提出了一种时间复杂度较低的属性值约简算法。
本文结合Trie树,以提高粗糙集知识约简算法的处理效率为出发点,提出了一种高效的知识约简算法。通过仿真对比实验结果进行分析,本文的知识约简算法处理大数据集的时间效率相对更高,说明了本文算法的有效性。