论文部分内容阅读
目前的数据库系统可以高效地实现数据的录入、查询、统计等功能,但无法发现数据中存在的关系和规则,无法根据现有的数据预测未来的发展趋势,缺乏挖掘数据背后隐藏的知识的手段,导致了“数据爆炸但知识贫乏”的现象。于是知识发现(Knowledge Discovery in Data,KDD)和数据挖掘(Data Mining,DM)技术应运而生。知识发现是近几年随着数据库和人工智能发展起来的一门新兴的数据库技术。通过知识发现技术,我们可以将信息变为知识,从“数据矿山”中找到蕴藏的“知识金块”。因此,研究高效智能的知识发现方法具有很大的现实意义。粗糙集理论是1982年由波兰数学家Z.Pawlak教授提出来的,它是一种处理不完整、不确定信息的新型数学工具。由于粗糙集理论不需要任何预备的或额外的有关数据信息,这样就避免了对知识的主观评价所带来的误差。经过20多年的发展,粗糙集理论不但在理论本身研究方面不断完善,而且在其它领域中也得到了成功的应用,如机器学习,决策分析,近似推理,图像处理,专家系统,过程控制,冲突分析,数据库知识发现(KDD),医疗诊断,金融数据分析等方面得到了较为成功的应用。近几年在粗糙集理论研究中对求解属性的最小约简和较小约简以及求取最简规则集的算法已经进行了一些研究,但这些研究都是针对静态数据的。而数据库是动态的,因此许多研究者建议,数据库知识发现算法应该是增量式的。属性最小约简的增量式算法以及增量式更新概念格的算法已经开始被研究,但对于增量式规则获取算法的研究工作还比较少。在以上工作的基础上,本文研究了基于粗糙集的增量式规则获取问题。本文所做的主要工作有:介绍了粗糙集理论的发展历程、特点、应用领域和基本理论。给出了决策表中对象“相关”和“相互独立”的定义,证明了当新对象加入时哪些规则需要更新,提出了一个基于粗糙集和搜索树的增量式规则提取算法。该算法在深度优先搜索中将已获取规则作为启发信息,大大提高了算法的效率;在时间复杂度不变的条件下,无需建立传统算法中的差别矩阵,具有较好的空间复杂度。由于现实中的决策表往往是不一致的,为了能够提取不确定性规则,本文引入可变精度粗糙集模型给出了基于可变精度粗糙集的增量式规则获取算法。最后,通过实验对比证明了算法的正确性和有效性。本文的主要创新点在于:(1)给出了一个基于粗糙集理论和搜索树的增量式规则提取算法(RDBRDFST)。该算法引入启发信息,无需建立差别矩阵,具有较好的时空复杂性。(2)引入可变精度粗糙集模型给出了基于可变精度粗糙集的增量式规则获取算法。该算法较好的解决了不一致决策表中不确定性规则的增量式获取问题,可通过设置不同的规则置信度来调整规则的获取。