基于容差关系的多粒度粗糙集中近似集动态更新方法

徐怡 肖鹏

摘 要：针对不完备信息系统变化时缺失值获取具体属性值的特性，为解决多粒度粗糙集中更新近似集时间效率低的問题，提出了一种基于容差关系的近似集动态更新算法。首先，讨论了基于容差关系的近似集变化的性质，并根据相关性质得出乐观、悲观多粒度粗糙集的近似集的变化趋势; 然后，针对更新容差类效率低的问题，提出了动态更新容差类的定理;最后，在此基础上，设计出基于容差关系的近似集动态更新算法。采用UCI数据库中4个数据集进行仿真实验，当数据集变大时，所提更新算法的计算时间远小于静态更新算法的计算时间，即所提动态更新算法的时间效率高于静态算法，验证了所提算法的正确性和高效性。

关键词：不完备信息系统;多粒度;动态更新;容差关系多粒度粗糙集;近似集

中图分类号：TP18

文献标志码：A

英文标题

Abstract： Focused on the issue that missing attribute values are obtained when an incomplete information system changes， in order to solve the problem of low time efficiency of updating the approximations in a multigranulation rough sets， a dynamic update algorithm based on tolerance relationship was proposed. Firstly， the properties of the approximations change based on tolerance relationship were discussed， and the change trends of the approximations of optimistic and pessimistic multigranulation rough sets were obtained according to the relevant properties. Then， a theorem of dynamic update tolerance class was proposed for the problem of low efficiency of updating tolerance class. Based on this， a dynamic update algorithm based on tolerance relationship was proposed. The simulation experiments were carried out using four data sets in UCI database. When the data set becomes larger， the calculation time of the proposed update algorithm is much smaller than that of the static update algorithm. The experimental results show that the time efficiency of the proposed dynamic update algorithm is higher than that of the static algorithm， which verifies the correctness and efficiency of the proposed algorithm.

英文关键词Key words： incomplete information system; multigranulation; dynamic update; tolerance relationship multigranulation rough sets; approximations

0 引言

波兰数学家Pawlak于1982年提出了一种能够处理不精确数据的方法，即粗糙集理论[1]。在保持分类能力不变的前提下，这种理论方法将知识视为一种分类的能力，通过知识约简导出决策规则。目前，粗糙集理论已在医疗诊断、模式识别、专家系统、预测分析以及机器学习等方面取得了巨大的成功[2-6]。

在现实生活中，数据的规模正在以前所未有的速度增长，数据可能随时间变化而不断变化，这可能会导致粗糙集中近似集的动态变化。当处理动态变化的数据时，传统方法需要重新计算近似集，导致近似集更新时间增加。为了提高数据动态变化下近似集更新的时间效率，有必要设计一种近似集动态更新方法。这种动态更新方法是利用之前的计算结果来更新近似集，已被用于多种信息系统中的知识获取。粗糙集背景下，学者们在论域变化、属性集变化和属性值域变化三个方面对知识的动态更新进行了大量研究。通过论域变化来更新知识方面：考虑到在集值有序信息系统中动态获取知识的问题，Luo等[7]分析了计算近似集的更新机制，并提出了更新析取集值系统、合取集值系统中近似集增量算法;Zhang等[8]提出了邻域粗糙集模型，并且利用矩阵的计算优势设计出基于矩阵的近似集更新方法;Liu等[9]针对动态系统定义了一个基于精度和平均值的重要概念，并根据所提概念设计出近似集更新方法。通过属性集的变化来更新知识方面：Zhang等[10]探讨了由关系矩阵推导的基本向量的概念，并在属性集变化时提出了通过更新矩阵来更新近似集的增量算法。通过属性值域的变化来更新知识方面：Chen等[11-13]定义了粗化和细化属性值的概念，并且在完备信息系统和不完备有序决策系统中分别提出了更新近似集的方法。

目前，Pawlak提出的经典粗糙集及扩展粗糙集理论都是建立在单一的二元关系基础之上的。粒计算理论中的多粒度是一个重要概念，表示多个不同的粒度角度。钱宇华等通过对决策进行分析，说明了多个决策者之间的关系是相互独立的，并使用多个二元关系来对目标概念进行近似逼近。根据上述理论分析：Qian等[14]提出了多粒度粗糙集的概念。在多粒度环境下，学者们对多粒度粗糙集的近似集动态更新方法进行了一系列深入的研究：Yang等[15]针对粒度结构增加的情况，提出了一种快速更新多粒度粗糙集的近似集方法;Hu等[16]通过对增加或删除单个粒度的情况进行讨论，设计出基于矩阵的多粒度粗糙集的近似集动态更新方法;胡成祥等[17]针对优势关系多粒度粗糙集中属性集的变化，定义了近似集动态更新的性质与定理，并根据提出的定理给出了近似集增量方法;Ju等[18]在多粒度模糊粗糙集环境中，提出了粒度结构变化时动态更新近似集和属性约简的方法;Hu等[19]首先讨论了粗化和细化属性值的动态机制，之后根据对应的动态机制设计了动态更新近似集算法。

目前，大多数多粒度粗糙集理论都是在完备信息系统下进行研究的。在完备信息系统下，处理的信息是完备的，所有对象的属性值都是已知的，但在现实生活中，由于数据的庞大，我们很难保证每个对象属性值的完备性。这时，多粒度粗糙集已经不适合处理这种不完备信息系统（Incomplete Information System， IIS）， 因此，Qian等[20]设计了不完备多粒度粗糙集模型，该模型采用一族容差关系来对目标概念进行近似逼近，因而适用于处理具有缺失值的不完备信息系统。然而，关于不完备多粒度粗糙集的研究主要集中在理论框架上，却很少有学者来研究这些模型的近似集动态更新方法。随着信息技术的飞速发展，数据的及时性具有重要意义， 因此，为了提高知识获取的效率，缺失值获取对应的属性值时，近似集动态更新方法至关重要。本文着重研究了缺失值获取属性值时容差类动态更新的方法，并给出了缺失值获取属性值时，容差关系多粒度粗糙集中近似集动态更新算法。在UCI数据集中进行的仿真实验表明，本文提出的近似集动态更新算法在缺失值获取属性值时是有效的，并且提高了时间效率。

4 结语

在不完備信息系统中，数据可能会随着时间不断完善，当缺失值获取属性值时快速更新近似集对于获取知识非常重要。为了提高更新近似集的时间效率，本文在容差关系多粒度粗糙集模型中讨论了缺失值获取属性值时动态更新近似集的相关过程，并提出对应的近似集动态更新算法。最后通过实验验证了本文算法在时间效率上优于静态算法。在未来工作中，将拓展本文算法，并应用到其他类型的不完备信息系统当中。

参考文献 （References）

[1]     PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences， 1995， 38（11）：88-95.

[2]     梁吉业.信息系统中的不确定性与知识获取[M].北京：科学出版社，2005：13-113.（LIANG J Y.Uncertainty and Knowledge Acquisition in Information Systems[M]. Beijing： Science Press，2005： 13-113.）

[3]     王国胤. Rough集理论与知识获取[M].西安：西安交通大学出版社， 2001：99-134.（WANG G Y.Rough Set Theory and Knowledge Acquisition[M].Xian：Xian Jiaotong University Press，2001：99-134.）

[4]     张文修. 信息系统与知识发现[M].北京：科学出版社， 2003：15-25.（ZHANG W X.Information System and Knowledge Discovery[M].Beijing： Science Press， 2003：15-25.）

[5]     李元诚， 方廷健. 基于粗糙集理论的支撑向量机预测方法研究[J]. 数据采集与处理， 2003， 18（2）：199-203.（LI Y C， FANG T J. Study of forecasting algorithm for support vector machines based on rough sets[J]. Journal of Data Acquisition & Processing，2003，18（2）199-203.）

[6]     FAKIH S J， DAS T K. LEAD： a methodology for learning efficient approaches to medical diagnosis[J]. IEEE Transactions on Information Technology in Biomedicine， 2006， 10（2）： 220-228.

[7]     LUO C， LI T， CHEN H， et al. Incremental approaches for updating approximations in setvalued ordered information systems[J]. KnowledgeBased Systems， 2013， 50： 218-233.

[8]     ZHANG J， LI T， DA R， et al. Neighborhood rough sets for dynamic data mining[J]. Information Sciences， 2014， 257（4）：81-100.

[9]     LIU D， LI T， DA R， et al. An incremental approach for inducing knowledge from dynamic information systems[J]. Fundamenta Informaticae， 2009， 94（2）： 245-260.

[10]    ZHANG J， LI T， DA R， et al. Rough sets based matrix approaches with dynamic attribute variation in setvalued information systems[J]. International Journal of Approximate Reasoning， 2012， 53（4）：620-635.

[11]    CHEN H， LI T， QIAO S， et al. A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values[J]. International Journal of Intelligent Systems， 2010， 25（10）：1005-1026.

[12]    CHEN H， LI T， DA R. Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining[J]. KnowledgeBased Systems， 2012， 31（7）：140-161.

[13]    CHEN H， LI T， RUAN D. Dynamic maintenance of approximations under a roughset based variable precision limited tolerance relation[J]. Journal of MultipleValued Logic and Soft Computing， 2012， 18（5）： 577-598.

[14]    QIAN Y， LIANG J， YAO Y， et al. MGRS： a multigranulation rough set [J]. Information Sciences， 2010， 180（6）： 949-970.

[15]    YANG X， QI Y， YU H， et al. Updating multigranulation rough approximations with increasing of granular structures[J]. KnowledgeBased Systems， 2014， 64（1）：59-69.

[16]    HU C， LIU S， LIU G. Matrixbased approaches for dynamic updating approximations in multigranulation rough sets[J]. KnowledgeBased Systems， 2017， 122： 51-63.

[17]    胡成祥， 趙国柱. 优势关系多粒度粗糙集中近似集动态更新方法[J]. 中国科学技术大学学报， 2017（1）：40-47.（HU C X， ZHAO G Z. Multigranularity rough set approximation set dynamic update method[J]. Journal of University of Science and Technology of China， 2017（1）： 40-47.）

[18]    JU H， YANG X， SONG X， et al. Dynamic updating multigranulation fuzzy rough set： approximations and reducts[J]. International Journal of Machine Learning & Cybernetics， 2014， 5（6）：981-990.

[19]    HU C， LIU S， HUANG X. Dynamic updating approximations in multigranulation rough sets while refining or coarsening attribute values[J]. KnowledgeBased Systems， 2017， 130（15）： 62-73.

[20]    QIAN Y， LIANG J， DANG C. Incomplete multigranulation rough set[J]. IEEE Transactions on Systems， Man， and Cybernetics-Part A： Systems and Humans， 2010， 40（2）：420-431.

[21]    许韦， 吴陈， 杨习贝. 基于容差关系的不完备可变精度多粒度粗糙集[J]. 计算机应用研究， 2013， 30（6）：1712-1715. （XU W，WU C，YANG X B. Incomplete variable precision multigranulation rough sets based on tolerance relation[J]. Application Research of Computers，2013，30（6）：1712-1715.）

[22]    YANG H L， GUO Z L. Multigranulation decisiontheoretic rough sets in incomplete information systems[J]. International Journal of Machine Learning & Cybernetics， 2015， 6（6）：1005-1018.