基于矩阵的覆盖粗糙集算法研究

发布时间：2018-04-09 20:40

本文选题：覆盖粗糙集　切入点：矩阵　出处：《安徽大学》2017年硕士论文

【摘要】：波兰学者Z.Pawlak提出了粗糙集理论,它是能够有效处理不完整和不确定性信息的数学工具。经典粗糙集理论是基于等价关系和划分的,只有完备的离散型数据集中的属性才能导出论域上的划分。但是,在现实情况中,信息系统中存在多种类型的数据,例如集值型数据、缺省型数据和实值型数据,经典粗糙集不能直接正确有效的处理这些数据,这就限制了经典粗糙集的应用,因此,扩展经典粗糙集成为了粗糙集研究的热点。在这些扩展研究中,Zakowski通过把经典粗糙集中论域的划分放宽为论域的覆盖,并首先提出基于覆盖的粗糙集模型。自该模型提出以来,研究者对覆盖粗糙集模型的研究重心主要集中于集合的近似集和属性约简,并提出了很多集合近似集的定义和属性约简算法,但这些方法仍然存在时间复杂度较高的问题,针对这个问题本文做了下面的研究:(1)提出了改进的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的定义。首先,证明现有的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的方法存在一些没有必要的运算,这会导致时间复杂度高。然后,提出了改进的基于矩阵的计算集合下近似集和覆盖决策信息系统正域的定义,它们能够有效的减少之前计算集合下近似集和覆盖决策信息系统正域的时间。最后,通过实例和实验结果验证了这两个方法的有效性。(2)本文为了克服现有的寻找分辨矩阵中全部极小元素的算法时间复杂度高的问题。首先,定义了基于矩阵的覆盖决策信息系统的相对分辨函数,然后,基于这个定义,给出基于矩阵的寻找分辨矩阵中全部极小元素的算法,该算法能够有效的降低计算覆盖决策信息系统所有约简的时间。最后,通过实例和实验验证了该算法的有效性。(3)在实际应用中,属性值的改变会导致覆盖信息系统中某一个覆盖发生变化,此时使用非增量的方法计算集合的上下近似集的时间开销较大。因此,本文针对属性值变化产生的动态覆盖信息系统,提出了基于矩阵的增量方法计算集合的上下近似集。首先,给出增量的方法计算动态覆盖的两种特征矩阵。然后,基于给定的两种特征矩阵分别给出计算集合上下近似集的增量算法,通过实例呈现了使用增量算法计算集合近似集的过程。最后,通过实验证明了本文提出的增量算法是有效的。
[Abstract]:Z.Pawlak, a Polish scholar, put forward rough set theory, which is a mathematical tool which can deal with incomplete and uncertain information effectively.The classical rough set theory is based on the equivalence relation and partition. Only the attributes of the complete discrete data set can derive the partition on the domain.However, in reality, there are many types of data in the information system, such as set-valued data, default data and real-valued data.This limits the application of classical rough sets, so the extension of classical rough sets is a hotspot in the research of rough sets.In these extended studies, Zakowski extends the partition of classical rough set domains to cover domains, and proposes a covering based rough set model.Since the model was put forward, the focus of researchers on covering rough set model is mainly on the approximate set of sets and attribute reduction, and many definitions and attribute reduction algorithms of set approximation set are proposed.However, these methods still have high time complexity. In this paper, the following research is done: 1) an improved definition of approximate set under matrix based computing set and positive domain of overlay decision information system is proposed.First of all, it is proved that there are some unnecessary operations for the existing methods of approximate set and positive domain covering decision information system under the matrix based computing set, which will lead to high time complexity.Then, an improved definition of approximate set and positive domain of overlay decision information system based on matrix is proposed, which can effectively reduce the time of computing approximate set and covering decision information system.Finally, the effectiveness of the two methods is verified by examples and experimental results.) in order to overcome the problem of high time complexity of existing algorithms for finding all the minimal elements in the discernment matrix.Firstly, the relative resolution function of the covering decision information system based on matrix is defined. Then, based on this definition, the algorithm of finding all the minimal elements in the matrix is given.This algorithm can effectively reduce the time of computing all reduction of overlay decision information system.Finally, the effectiveness of the algorithm is verified by examples and experiments. In practical application, the change of attribute value will lead to the change of one coverage in the overlay information system.In this case, the time cost of computing the upper and lower approximate sets of the set by using the non-incremental method is large.Therefore, in this paper, an incremental method based on matrix is proposed to calculate the upper and lower approximate sets of the set for the dynamic overlay information system caused by the change of the attribute value.Firstly, two characteristic matrices of dynamic coverage are calculated by incremental method.Then, based on the two given characteristic matrices, the incremental algorithm for computing the upper and lower approximate sets of the set is presented, and the process of computing the approximate set of the set using the incremental algorithm is presented by an example.Finally, the experimental results show that the proposed incremental algorithm is effective.
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】