论文部分内容阅读
随着信息技术的高速发展,数据库应用的规模不断扩大,原有的数据库处理方法己经远远不能满足现实需要,数据挖掘正是为迎合这种需要而产生并迅速发展起来的一种新的数据处理技术。它能够在没有明确假设的前提下,自动地从数据中抽取隐含的、具有潜在应用价值的信息,经过检验和验证,然后返回对用户最有用的结果。目前数据挖掘已经被越来越多的领域所采用,具有广泛的应用前景。 在数据挖掘的过程中,存在大量冗余数据影响我们的决策,粗糙集理论在得到的决策规则和推理过程方面是最有利的工具。它不但可以在不影响数据表达信息的前提下使原来的数据量大为减少(数据浓缩),而且还可以产生决策规则,从而挖掘出数据中的有效模式。粗糙集理论不同于其他处理不确定性问题的理论,如概率方法、模糊集方法和证据理论方法等,它无需提供任何所需处理数据集合之外的先验信息。 本文首先对基于粗糙集的数据挖掘过程——数据预处理、约简及规则获取进行研究。其次,对挖掘过程中的核心问题——约简,进行了深入的探讨,对目前的约简算法展开分析,指出了其中存在的问题。 其次,针对目前较多的启发式算法为了减少时间代价,无法得到决策表最小约简,且时间复杂度与空间复杂度仍然在|U|~2(|U|为决策表中记录数)的问题,提出一种既可以降低时间复杂度和空间复杂度,又可以求得最小约简的算法——基于DMI(区分矩阵属性约简改进算法)的改进算法。主要内容如下: 1.对DMI算法进行了分析,举例说明了该算法对于不相容决策表的不正确性:然后给出了一种对相容决策表与不相容决策表都适合的改进约简算法。 2.针对目前的约简算法必须反复遍历决策表各个数据项,使时间复杂度、空间复杂度较高的现状进行了改进,改进后的算法不用遍历完一次决策表就可以实现约简,大大减少了算法的时间和空间复杂度。 3.突出了属性值约简对数据约简的重要性,真正实现了决策表的最简化。并提出改进的值约简算法,时间复杂度在原有基础上大大减少。 4.将3个对约简的改进思想融合在一个算法当中,成为真正意义上的约简算法,实现了属性约简和属性值约简的一体化。同目前普遍存在的用不同算法独立处理属性约简和属性值约简的方法相比,本算法的空间复杂度大大减少。因此,本算法具有很强的实践意义和应用前景。 5.算法的整个约简过程都是针对所有对象同时进行,真正考虑到了整个决策类对约简的意义,避免了发生求得局部最优的错误。