徐怡 肖鵬

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

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

中圖分類號：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]。在保持分類能力不變的前提下，這種理論方法將知識視為一種分類的能力，通過知識約簡導(dǎo)出決策規(guī)則。目前，粗糙集理論已在醫(yī)療診斷、模式識別、專家系統(tǒng)、預(yù)測分析以及機(jī)器學(xué)習(xí)等方面取得了巨大的成功[2-6]。

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

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

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

4 結(jié)語

在不完備信息系統(tǒng)中，數(shù)據(jù)可能會隨著時間不斷完善，當(dāng)缺失值獲取屬性值時快速更新近似集對于獲取知識非常重要。為了提高更新近似集的時間效率，本文在容差關(guān)系多粒度粗糙集模型中討論了缺失值獲取屬性值時動態(tài)更新近似集的相關(guān)過程，并提出對應(yīng)的近似集動態(tài)更新算法。最后通過實驗驗證了本文算法在時間效率上優(yōu)于靜態(tà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)中的不確定性與知識獲取[M].北京：科學(xué)出版社，2005：13-113.（LIANG J Y.Uncertainty and Knowledge Acquisition in Information Systems[M]. Beijing： Science Press，2005： 13-113.）

[3] ??? 王國胤. Rough集理論與知識獲取[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)與知識發(fā)現(xiàn)[M].北京：科學(xué)出版社， 2003：15-25.（ZHANG W X.Information System and Knowledge Discovery[M].Beijing： Science Press， 2003：15-25.）

[5] ??? 李元誠， 方廷健. 基于粗糙集理論的支撐向量機(jī)預(yù)測方法研究[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] ?? 胡成祥， 趙國柱. 優(yōu)勢關(guān)系多粒度粗糙集中近似集動態(tài)更新方法[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報， 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ī)應(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.