多粒度环境下基于矩阵方法增量更新近似集的算法研究

摘要

粗糙集理论作为一种处理不确定性和不完备数据的数学方法，最初由Z.Pawlak在1982年提出。经典粗糙集理论通过单个二元关系对集合进行划分，并利用上近似和下近似两个精确集合来描述数据的不确定性。然而，从粒计算的角度来看，经典的粗糙集模型是建立在单粒度、单层次上的，忽略了数据自身存在的层次性。为了克服经典粗糙集理论的不足，钱宇华等人通过结合粒计算思想，提出了多粒度粗糙集模型。多粒度粗糙集作为经典粗糙集模型的扩展，其通过论域上的多重等价关系来描述集合的近似，因此可以从不同视角、不同层次上对问题进行分析，从而可以更好地洞察问题的本质。然而，在一些实际应用场景中可能存在对象、属性或属性值等类型的变化而导致信息系统发生动态改变的情况，此时在多粒度环境中使用传统非增量方法更新近似集的时间开销较大。如何在多粒度环境下克服此类问题并有效地获取潜在信息，依然是粗糙集领域中研究的重点。因此本文以多粒度粗糙集及其扩展模型为研究对象，以矩阵作为主要运算工具，以基于动态信息系统的近似集更新为主要研究目的，做了如下研究: (1)由一族邻域关系构成的邻域多粒度粗糙集可以有效地处理连续的数值型数据，因而有着较为广泛地应用。然而邻域信息系统中论域的改变会导致多粒度环境下粒度的划分发生变化，进而导致原有的知识发生改变，例如邻域多粒度粗糙集中的正域、负域、边界域。此时使用非增量方法计算集合的三个域时需要重新遍历整个论域，因此会花费大量的时间。为了解决邻域多粒度粗糙集中知识更新效率不高的问题，本文针对论域动态变化的情况，提出了基于矩方法增量更新知识的算法。首先，给出邻域多粒度粗糙集模型中的矩阵更新策略。然后，证明了论域动态变化时更新知识的过程存在冗余计算，并定义了更新粒度矩阵的计算方法。接着，根据本文给定的矩阵动态更新策略，设计了更新邻域多粒度粗糙集正域、负域、边界域的矩阵增量算法，利用所提方法降低了算法的时间复杂度，大大减少了更新正域、负域、边界域所需要的计算量，有效地提高了算法的执行效率。最后，通过具体的数据集和对比实验验证了本文所提算法是有效的。 (2)在实际应用中，往往存在对象变化、属性变化或属性值变化等若干种类型的变化同时进行并导致近似集发生改变的情形，而目前的研究主要还是针对单一类型变化下的近似集更新问题。考虑当前单一变化方式下更新近似集的局限性，本文将信息系统的动态变化问题扩展至二维，研究信息系统中对象和属性同时发生变化、对象和属性值同时发生变化时更新近似集的问题，并提出多粒度环境下基于二维变化的矩阵增量更新近似集算法。首先，给出多粒度粗糙集中近似集和矩阵的定义。接着，提出在对象和属性同时变化、对象和属性值同时变化的情况下，基于矩阵动态更新乐观和悲观多粒度近似集的策略。并基于提出的更新策略，设计了增量更新近似集的算法。所提算法降低了时间复杂度，减少更新近似集时所花费的时间。最后，通过具体的实验数据和对比实验验证了所提算法的有效性。