基于局部粗糙集研究不完備信息系統的理論

劉瑤瑤

摘 要：為了進一步有效處理不完備數據，本文將完備信息系統上的局部粗糙集理論擴展推廣到不完備信息系統中，首先基于不完備信息系統的容差關系給出了局部粗糙集的定義，其次，研究了不完備信息系統上局部粗糙集的性質并基于不完備局部粗糙集給出了計算下近似的算法。最后，基于局部下近似的兩部分，給出了不同的局部屬性約簡。

關鍵詞： 不完備; 局部粗糙集; 屬性約簡; 信息系統

【Abstract】 In order to further effectively deal with incomplete data， this paper extends the local rough set theory on complete information systems to incomplete information systems. Firstly， the definition of local rough sets is given based on the tolerance relationship of incomplete information systems. Secondly， the properties of local rough sets on incomplete information systems are studied， and the corresponding algorithms of finding local low approxi is designed. Finally， different attribute reductions are proposed based on two parts of the local lower approximation.

【Key words】 ?incomplete; local rough sets; attribute reduction; information system

0 引 言

粗糙集理論已成為不確定性管理和不確定性推理的有效工具，并已在人工智能領域得到了成功應用。粗糙集理論的優勢在于是其所有的參數都是從給定的樣本集中獲得的，這可以從文獻[1]中看出：“不精確的數值不是預先假設的，而是在近似值的基礎上計算出來的，這里的近似值用來表達知識的不精確性”。迄今為止，粗糙集數據分析已廣泛應用于特征選擇[2-3]、模式識別[4]、數據挖掘[5]和知識發現[6]等。

在粗糙集理論中，概念近似和屬性約簡[7]是2個非常重要的問題。概念近似包括：上近似和下近似。給定樣本集U和二元關系R，可以構造其等價類[8]，可以構建樣本集上的任何子集的粗糙集、即上下近似。目前研究粗糙集時，必不可少地會提到Pawlak的經典粗糙集，但是在經典粗糙集中，可以看到集合的上下近似的計算需要掃描給定集合U中的所有對象，同時還要獲得近似目標概念的信息粒子[9]。通常將這種粗糙集稱為全局粗糙集，而研究即需標記數據[10]。然而，隨著大數據時代的到來，標簽數據是一件非常耗時費力的工作，為了解決時間復雜度的問題，文獻[1]提出了一種新的理論框架：局部粗糙集降低了數據量大時下近似計算和屬性約簡的時間復雜度。但是在文獻[5]中只考慮到了完備信息系統[9]下的局部粗糙集，尚未涉及到不完備[10]的問題。因為目前海量的數據中很多數據的值是不確定的，本文的研究就是在文獻[5]的基礎上引入不完備的思想，進一步研究上下近似的計算以及相關算法，該研究非常具有現實意義。

本文的安排如下：首先簡要闡述不完備信息系統、完備信息系統、以及局部粗糙集的相關概念;其次，基于不完備信息系統，重新對上下近似進行新的定義;接著，研究不完備信息系統下局部粗糙集的相關性質;而后，設計了計算不完備信息系統中局部粗糙集下近似的算法;最后，給出了全文總結。

1 基礎知識

5 結束語

本文在不完備信息系統中，引入了局部粗糙集的理論。討論了在不完備信息系統的局部粗糙集的相關性質，重點是研究該系統下，如何計算下近似，也給出了計算下近似的相關的算法。

本文只是在局部粗糙集和不完備粗糙集結合下的一個初步探索。基于本文的結果，可以深入研究局部屬性約簡的算法，以及進一步降低算法的時間復雜度等內容。

參考文獻

[1]PAWLAK Z. Rough sets[J]. International Joumal of Computer and Information Sciences， 1982， 11（5）：341-356.

[2]BHATT R B， GOPAL M. On fuzzy-rough sets approach to feature selection[J]. Pattern Recognition Letters， 2005， 26 （7）： 965-975.

[3]ESKANDARI S， JAVIDI M M. Online streaming feature selection using rough sets[J]. International Journal of Approximate Reasoning， 2016， 69： 35-57.

[4]SWINIARSKI R W， SKOWRON A. Rough set methods in feature selection and recognition[J]. Pattern Recognition Letters， 2003， 24 （6）：833-849.

[5]QIAN Yuhua，LIANG Xinyan，WANG Qi， et al. Local rough set： A solution to rough data analysis in big data[J]. International Journal of Approximate Reasoning，2018，97：38-63.

[6]陳志恩.基于粒關系包含度矩陣的屬性約簡[J].西北師范大學學報（自然科學版），2017，53（5）：24-28.

[7]張晶，李德玉，王素格，等. 基于穩健模糊粗糙集模型的多標記文本分類[J].計算機科學， 2015，42（7）：270-275.

[8]MA Fumin， ZHANG Tengfei. Generalized binary discernibility matrix for attribute reduction in incomplete information systems[J].The Journal of China Universities of Posts and Telecommunications， 2017，24（4）：57-68，75.

[9]SHAO Mingwen， ZHANG Wenxiu. Dominance relation and rules in an incomplete ordered information system[J]. International Journal of Intelligent Systems ， 2005， 20（1）：13-27.

[10]YANG X B， YANG J Y， WU C. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information Sciences，2008，178：1219-1234.

[11]張文修，吳偉志. 粗糙集理論介紹和研究綜述[J].模糊系統與學報，2000， 14（4）：1-12.

[12]WANG Guoyin. Extension of rough set under incomplete information system[C]∥2002 IEEE World Congress on Computational Intelligence. 2002 IEEE International Conference on Fuzzy Systems. FUZZ-IEEE'02. Proceedings （Cat. No.02CH37291）.Honolulu， HI， USA： IEEE，2002：1098-1103.

[13]羅豪，續欣瑩，謝珺，等.基于擴展容差關系的不完備信息系統屬性約簡[J]. 計算機應用，2016，36（11）：2958-2962.

[14]DAI Jianhua， HUHu， ZHENG Guojie， et al. Attribute reduction in interval-valued information systems based on information entropies[J]. Frontiers of Information Technology & Electronic Engineering，2016，17（9）：919-928.