论文部分内容阅读
波兰学者Z.Pawlak提出了粗糙集理论,它是能够有效处理不完整和不确定性信息的数学工具。经典粗糙集理论是基于等价关系和划分的,只有完备的离散型数据集中的属性才能导出论域上的划分。但是,在现实情况中,信息系统中存在多种类型的数据,例如集值型数据、缺省型数据和实值型数据,经典粗糙集不能直接正确有效的处理这些数据,这就限制了经典粗糙集的应用,因此,扩展经典粗糙集成为了粗糙集研究的热点。在这些扩展研究中,Zakowski通过把经典粗糙集中论域的划分放宽为论域的覆盖,并首先提出基于覆盖的粗糙集模型。自该模型提出以来,研究者对覆盖粗糙集模型的研究重心主要集中于集合的近似集和属性约简,并提出了很多集合近似集的定义和属性约简算法,但这些方法仍然存在时间复杂度较高的问题,针对这个问题本文做了下面的研究:(1)提出了改进的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的定义。首先,证明现有的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的方法存在一些没有必要的运算,这会导致时间复杂度高。然后,提出了改进的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的定义,它们能够有效的减少之前计算集合下近似集和覆盖决策信息系统正域的时间。最后,通过实例和实验结果验证了这两个方法的有效性。(2)本文为了克服现有的寻找分辨矩阵中全部极小元素的算法时间复杂度高的问题。首先,定义了基于矩阵的覆盖决策信息系统的相对分辨函数,然后,基于这个定义,给出基于矩阵的寻找分辨矩阵中全部极小元素的算法,该算法能够有效的降低计算覆盖决策信息系统所有约简的时间。最后,通过实例和实验验证了该算法的有效性。(3)在实际应用中,属性值的改变会导致覆盖信息系统中某一个覆盖发生变化,此时使用非增量的方法计算集合的上下近似集的时间开销较大。因此,本文针对属性值变化产生的动态覆盖信息系统,提出了基于矩阵的增量方法计算集合的上下近似集。首先,给出增量的方法计算动态覆盖的两种特征矩阵。然后,基于给定的两种特征矩阵分别给出计算集合上下近似集的增量算法,通过实例呈现了使用增量算法计算集合近似集的过程。最后,通过实验证明了本文提出的增量算法是有效的。