基于容差關(guān)系的多粒度粗糙集中近似集動(dòng)態(tài)更新方法

徐怡 肖鵬

摘 要：針對(duì)不完備信息系統(tǒng)變化時(shí)缺失值獲取具體屬性值的特性，為解決多粒度粗糙集中更新近似集時(shí)間效率低的問題，提出了一種基于容差關(guān)系的近似集動(dòng)態(tài)更新算法。首先，討論了基于容差關(guān)系的近似集變化的性質(zhì)，并根據(jù)相關(guān)性質(zhì)得出樂觀、悲觀多粒度粗糙集的近似集的變化趨勢(shì); 然后，針對(duì)更新容差類效率低的問題，提出了動(dòng)態(tài)更新容差類的定理;最后，在此基礎(chǔ)上，設(shè)計(jì)出基于容差關(guān)系的近似集動(dòng)態(tài)更新算法。采用UCI數(shù)據(jù)庫(kù)中4個(gè)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，當(dāng)數(shù)據(jù)集變大時(shí)，所提更新算法的計(jì)算時(shí)間遠(yuǎn)小于靜態(tài)更新算法的計(jì)算時(shí)間，即所提動(dòng)態(tài)更新算法的時(shí)間效率高于靜態(tài)算法，驗(yàn)證了所提算法的正確性和高效性。

關(guān)鍵詞：不完備信息系統(tǒng);多粒度;動(dòng)態(tài)更新;容差關(guān)系多粒度粗糙集;近似集

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)志碼：A

英文標(biāo)題

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.

英文關(guān)鍵詞Key words： incomplete information system; multigranulation; dynamic update; tolerance relationship multigranulation rough sets; approximations

0 引言

波蘭數(shù)學(xué)家Pawlak于1982年提出了一種能夠處理不精確數(shù)據(jù)的方法，即粗糙集理論[1]。在保持分類能力不變的前提下，這種理論方法將知識(shí)視為一種分類的能力，通過知識(shí)約簡(jiǎn)導(dǎo)出決策規(guī)則。目前，粗糙集理論已在醫(yī)療診斷、模式識(shí)別、專家系統(tǒng)、預(yù)測(cè)分析以及機(jī)器學(xué)習(xí)等方面取得了巨大的成功[2-6]。

在現(xiàn)實(shí)生活中，數(shù)據(jù)的規(guī)模正在以前所未有的速度增長(zhǎng)，數(shù)據(jù)可能隨時(shí)間變化而不斷變化，這可能會(huì)導(dǎo)致粗糙集中近似集的動(dòng)態(tài)變化。當(dāng)處理動(dòng)態(tài)變化的數(shù)據(jù)時(shí)，傳統(tǒng)方法需要重新計(jì)算近似集，導(dǎo)致近似集更新時(shí)間增加。為了提高數(shù)據(jù)動(dòng)態(tài)變化下近似集更新的時(shí)間效率，有必要設(shè)計(jì)一種近似集動(dòng)態(tài)更新方法。這種動(dòng)態(tài)更新方法是利用之前的計(jì)算結(jié)果來(lái)更新近似集，已被用于多種信息系統(tǒng)中的知識(shí)獲取。粗糙集背景下，學(xué)者們?cè)谡撚蜃兓傩约兓蛯傩灾涤蜃兓齻€(gè)方面對(duì)知識(shí)的動(dòng)態(tài)更新進(jìn)行了大量研究。通過論域變化來(lái)更新知識(shí)方面：考慮到在集值有序信息系統(tǒng)中動(dòng)態(tài)獲取知識(shí)的問題，Luo等[7]分析了計(jì)算近似集的更新機(jī)制，并提出了更新析取集值系統(tǒng)、合取集值系統(tǒng)中近似集增量算法;Zhang等[8]提出了鄰域粗糙集模型，并且利用矩陣的計(jì)算優(yōu)勢(shì)設(shè)計(jì)出基于矩陣的近似集更新方法;Liu等[9]針對(duì)動(dòng)態(tài)系統(tǒng)定義了一個(gè)基于精度和平均值的重要概念，并根據(jù)所提概念設(shè)計(jì)出近似集更新方法。通過屬性集的變化來(lái)更新知識(shí)方面：Zhang等[10]探討了由關(guān)系矩陣推導(dǎo)的基本向量的概念，并在屬性集變化時(shí)提出了通過更新矩陣來(lái)更新近似集的增量算法。通過屬性值域的變化來(lái)更新知識(shí)方面：Chen等[11-13]定義了粗化和細(xì)化屬性值的概念，并且在完備信息系統(tǒng)和不完備有序決策系統(tǒng)中分別提出了更新近似集的方法。

目前，Pawlak提出的經(jīng)典粗糙集及擴(kuò)展粗糙集理論都是建立在單一的二元關(guān)系基礎(chǔ)之上的。粒計(jì)算理論中的多粒度是一個(gè)重要概念，表示多個(gè)不同的粒度角度。錢宇華等通過對(duì)決策進(jìn)行分析，說(shuō)明了多個(gè)決策者之間的關(guān)系是相互獨(dú)立的，并使用多個(gè)二元關(guān)系來(lái)對(duì)目標(biāo)概念進(jìn)行近似逼近。根據(jù)上述理論分析：Qian等[14]提出了多粒度粗糙集的概念。在多粒度環(huán)境下，學(xué)者們對(duì)多粒度粗糙集的近似集動(dòng)態(tài)更新方法進(jìn)行了一系列深入的研究：Yang等[15]針對(duì)粒度結(jié)構(gòu)增加的情況，提出了一種快速更新多粒度粗糙集的近似集方法;Hu等[16]通過對(duì)增加或刪除單個(gè)粒度的情況進(jìn)行討論，設(shè)計(jì)出基于矩陣的多粒度粗糙集的近似集動(dòng)態(tài)更新方法;胡成祥等[17]針對(duì)優(yōu)勢(shì)關(guān)系多粒度粗糙集中屬性集的變化，定義了近似集動(dòng)態(tài)更新的性質(zhì)與定理，并根據(jù)提出的定理給出了近似集增量方法;Ju等[18]在多粒度模糊粗糙集環(huán)境中，提出了粒度結(jié)構(gòu)變化時(shí)動(dòng)態(tài)更新近似集和屬性約簡(jiǎn)的方法;Hu等[19]首先討論了粗化和細(xì)化屬性值的動(dòng)態(tài)機(jī)制，之后根據(jù)對(duì)應(yīng)的動(dòng)態(tài)機(jī)制設(shè)計(jì)了動(dòng)態(tài)更新近似集算法。

目前，大多數(shù)多粒度粗糙集理論都是在完備信息系統(tǒng)下進(jìn)行研究的。在完備信息系統(tǒng)下，處理的信息是完備的，所有對(duì)象的屬性值都是已知的，但在現(xiàn)實(shí)生活中，由于數(shù)據(jù)的龐大，我們很難保證每個(gè)對(duì)象屬性值的完備性。這時(shí)，多粒度粗糙集已經(jīng)不適合處理這種不完備信息系統(tǒng)（Incomplete Information System， IIS）， 因此，Qian等[20]設(shè)計(jì)了不完備多粒度粗糙集模型，該模型采用一族容差關(guān)系來(lái)對(duì)目標(biāo)概念進(jìn)行近似逼近，因而適用于處理具有缺失值的不完備信息系統(tǒng)。然而，關(guān)于不完備多粒度粗糙集的研究主要集中在理論框架上，卻很少有學(xué)者來(lái)研究這些模型的近似集動(dòng)態(tài)更新方法。隨著信息技術(shù)的飛速發(fā)展，數(shù)據(jù)的及時(shí)性具有重要意義， 因此，為了提高知識(shí)獲取的效率，缺失值獲取對(duì)應(yīng)的屬性值時(shí)，近似集動(dòng)態(tài)更新方法至關(guān)重要。本文著重研究了缺失值獲取屬性值時(shí)容差類動(dòng)態(tài)更新的方法，并給出了缺失值獲取屬性值時(shí)，容差關(guān)系多粒度粗糙集中近似集動(dòng)態(tài)更新算法。在UCI數(shù)據(jù)集中進(jìn)行的仿真實(shí)驗(yàn)表明，本文提出的近似集動(dòng)態(tài)更新算法在缺失值獲取屬性值時(shí)是有效的，并且提高了時(shí)間效率。

4 結(jié)語(yǔ)

在不完備信息系統(tǒng)中，數(shù)據(jù)可能會(huì)隨著時(shí)間不斷完善，當(dāng)缺失值獲取屬性值時(shí)快速更新近似集對(duì)于獲取知識(shí)非常重要。為了提高更新近似集的時(shí)間效率，本文在容差關(guān)系多粒度粗糙集模型中討論了缺失值獲取屬性值時(shí)動(dòng)態(tài)更新近似集的相關(guān)過程，并提出對(duì)應(yīng)的近似集動(dòng)態(tài)更新算法。最后通過實(shí)驗(yàn)驗(yàn)證了本文算法在時(shí)間效率上優(yōu)于靜態(tài)算法。在未來(lái)工作中，將拓展本文算法，并應(yīng)用到其他類型的不完備信息系統(tǒng)當(dāng)中。

參考文獻(xiàn) （References）

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

[2] ??? 梁吉業(yè).信息系統(tǒng)中的不確定性與知識(shí)獲取[M].北京：科學(xué)出版社，2005：13-113.（LIANG J Y.Uncertainty and Knowledge Acquisition in Information Systems[M]. Beijing： Science Press，2005： 13-113.）

[3] ??? 王國(guó)胤. Rough集理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社， 2001：99-134.（WANG G Y.Rough Set Theory and Knowledge Acquisition[M].Xian：Xian Jiaotong University Press，2001：99-134.）

[4] ??? 張文修. 信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M].北京：科學(xué)出版社， 2003：15-25.（ZHANG W X.Information System and Knowledge Discovery[M].Beijing： Science Press， 2003：15-25.）

[5] ??? 李元誠(chéng)， 方廷健. 基于粗糙集理論的支撐向量機(jī)預(yù)測(cè)方法研究[J]. 數(shù)據(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] ?? 胡成祥， 趙國(guó)柱. 優(yōu)勢(shì)關(guān)系多粒度粗糙集中近似集動(dòng)態(tài)更新方法[J]. 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)， 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] ?? 許韋， 吳陳， 楊習(xí)貝. 基于容差關(guān)系的不完備可變精度多粒度粗糙集[J]. 計(jì)算機(jī)應(yīng)用研究， 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.