论文部分内容阅读
进入网络信息时代,随着计算机技术和网络技术的飞速发展,使得各个行业领域的信息急剧增加,如何从大量的、杂乱无章的数据中发现潜在的、有价值的、简洁的知识呢?数据挖掘(DM)和知识发现(KDD)技术应运而生。粗糙集理论与方法作为数据挖掘或者知识发现方法的一种,它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法最显著的区别是它不需要提供问题所需处理的数据集之外的任何先验知识,而且与处理其他不确定性问题的理论有很强的互补性,特别是模糊理论。 但是,粗糙集理论的基本运算是建立在求集合的并交补和求等价关系基础之上的,利用粗糙集理论挖掘一般决策表的最简规则或者所有规则是一个NP—Hard问题,NP—Hard问题是计算数学的一个普遍难题,它的解决依赖于某个NP—Hard问题的解决,因此,如何降低算法的复杂度成为限制粗糙集理论应用的一个根本性问题。 本文介绍了粗糙集理论的基本概念和扩展的粗糙集理论模型,研究了粗糙集理论进行数据挖掘算法的特点,通过证明一个半群一有限集合代数系统的可表示定理,将有限集合代数系统用一个与之同构的位向量代数系统来描述,将集合的并交补运算转化为位向量代数系统的与或非运算,该定理具有一定的普适性—基本上所有的基于粗糙集理论的各种算法都可以适用。在该定理的基础上,设计了一种基于粗糙集论的数据挖掘属性约简算法和规则挖掘算法,与一般的算法比较,时间复杂度大大降低;空间的复杂度降为一般算法的八分之一。利用该算法开发了一个原型系统RSDM和一个MATLAB仿真软件包,以进行数据挖掘的进一步研究和应用。 另一方面,粗糙挖掘算法的时间复杂度问题并没有得到完全的解决,因此本文介绍了基于消息传递的并行计算模型,在此模型基础上,利用MPICH并行计算软件包,初步研究了粗糙挖掘的并行计算算法。 现将本文的主要工作列举如下: 1.给出并证明有限集合代数系统可表示定理,设计基于粗糙集理论的数据挖掘(以下简称粗糙挖掘)串行实现算法。 2.介绍了一般知识发现过程,研究了粗糙挖掘的过程,设计开发了粗糙挖掘的原型系统RSDM和一个MATLAB粗糙挖掘软件包。 3.研究了基于Windows2000集群式系统上,采用消息传递的并行计算模型,利用MPI初步研究了基于粗糙理论的数据挖掘并行实现算法。