论文部分内容阅读
在自然科学、社会科学和工程技术的很多领域中,人们都不同程度地要面对不确定性和不完备信息的处理问题。数据是信息的载体,由于数据采集过程中各种因素的干扰或数据存储介质的损坏等原因,从实际系统中采集到的数据常常不够精确甚至不够完整。通过对数据附加纯数学上的主观假设,或者直接删除含有缺失数据的实例来回避这种不确定性,往往会导致获得的模型由于先验假设难以被满足而失去应用意义,或者不能真实反映现实系统的特性。粗糙集理论是一种刻划不完整性和不确定性的数学工具,能有效地分析和处理不精确、不一致、不完整等各种不完备信息,并从中发现隐含的知识,揭示潜在的规律。本文主要研究基于粗糙集理论的不完备信息系统框架下的知识粒度刻画和知识获取问题,主要工作与结论如下:(1)关于极大相容块的构造。极大相容块是不完备信息系统的最小知识单元。尽管基于极大相容块的粗糙集模型可以更高的精度对目标概念进行近似,获取系统约简时也不改变系统原有的拓扑结构,但极大相容块的构造相对于相似类要复杂得多。为此,本文通过定义区分关系及其布尔函数,利用布尔推理技术实现了极大相容块的构造和获取。证明了极大相容块与构造的布尔公式的素蕴含存在一一对应关系,这种基于布尔推理技术的极大相容块获取方法有助于人们对极大相容块本质的理解和不完备信息系统中的知识获取。(2)关于不完备系统中的约简。约简是基于粗糙集理论的数据降维、压缩,以及知识获取的重要技术手段。针对不完备系统,与以往基于相似关系(相容关系)不同,本文基于区分关系等价地重新定义了各类约简,并构造了相应的区分函数,证明了区分函数的素蕴涵与约简的一一对应关系,给出了求解各类约简的理论方法。(3)关于约简算法。众所周知,在粗糙集理论中,最优约简的求解是一个NP-困难问题。导致该问题的主要原因是属性的组合爆炸。高效的约简算法是粗糙集理论应用于知识发现的基础。为了有效地求解各类约简,本文证明了约简问题等价于一个集合的极小覆盖问题,并利用成熟的集合极小覆盖问题求解方法——拉格朗日乘子法实现约简问题的求解。这一工作的意义在于,它将约简问题转化为一般的0-1线性规划问题,为求解约简问题提供了新思路。最后,利用上述思想设计了相应的启发示约简算法。(4)关于方法的实验验证。采用来自于UCI的标准数据集,通过实验验证了本文提出的方法、算法的有效性,实验表明本文提出的方法可获得较好的约简结果。