變精度下不完備鄰域決策系統的屬性約簡算法

王映龍，曾淇，錢文彬，楊珺

(1.江西農業大學 計算機與信息工程學院,江西 南昌 330045; 2.江西農業大學 軟件學院,江西 南昌 330045)

變精度下不完備鄰域決策系統的屬性約簡算法

王映龍1，曾淇1，錢文彬2，楊珺2

(1.江西農業大學 計算機與信息工程學院,江西 南昌 330045; 2.江西農業大學 軟件學院,江西 南昌 330045)

鄰域粗糙集模型在處理完備的數值型數據中得到廣泛應用，但針對不完備的數值型和符號型混合數據進行屬性約簡的討論相對較少。為此，首先結合鄰域粗糙集給出了可變精度模型下不完備鄰域決策系統的上、下近似算子及屬性約簡；然后通過鄰域粒化的方法構建了廣義鄰域下可變精度的粗糙集模型，并提出了一種屬性重要度的評價方法；在此基礎上，設計出了面向不完備鄰域決策系統的屬性約簡算法，該算法可直接處理不完備的數值型和符號型混合數據；最后，通過實例分析驗證了本文提出的算法能夠求解出變精度下不完備鄰域決策系統的屬性約簡結果。

粗糙集理論；鄰域關系；不完備信息系統；變精度分類粗糙集；粒計算；多粒度；約簡；決策粗糙集

中文引用格式：王映龍，曾淇，錢文彬，等. 變精度下不完備鄰域決策系統的屬性約簡算法[J]. 智能系統學報， 2017, 12(3): 386-391.

英文引用格式：WANG Yinglong, ZENG Qi, QIAN Wenbin, et al. Attribute reduction algorithm of the incomplete neighborhood decision system with variable precision[J]. CAAI transactions on intelligent systems, 2017, 12(3): 386-391.

波蘭數學家Pawlak提出的粗糙集理論能有效處理信息系統中不精確、不確定信息[1]，其在模式識別、市場決策、醫療診斷等領域廣泛應用[2-3]。 經典Pawlak粗糙集理論的研究對象是完備的信息決策表。然而在現實生活中，往往很多決策系統存在多種數據類型，如連續型數據、不完備型數據和集值型數據等[4-6]。由于經典粗糙集在處理連續型數據時需進行離散化預處理，將不可避免地造成信息的丟失，且對于含有不完備型數據的決策系統，傳統的粗糙集模型較難直接處理。近年來，針對混合、模糊、不完備的粗糙集模型擴展及應用成為粒度計算研究的熱點問題[7-13]。

基于粒計算的屬性約簡研究已取得許多有意義的成果[14-18]:文獻[14]研究了混合數據下的知識發現及鄰域粒化問題;文獻[15]提出了悲觀多粒度粗糙集的概念，解決了利用“求同消異”的決策策略處理多個不可分辨關系之間存在相互獨立的情況;文獻[16]將多粒度粗糙集擴展到鄰域多粒度粗糙集;為提高分類的效果，文獻[17]在多粒度粗糙集的基礎上引入了錯誤分類率的概念，即在允許一定程度分類率的前提下，尋找數據之間的相關性，以解決屬性間不確定關系的數據分類問題;對于不完備信息系統，文獻[18]提出了一種基于容差關系的不完備可變精度多粒度粗糙集模型。

上述研究分別針對不完備粗糙集、變精度粗糙集進行研究。由于現實生活中同時存在大量的不完備、連續數值型、符號型屬性數據的情況，現有的鄰域粗糙集計算方法對上述情況和數據集的可控性調節劃分的討論相對較少。為此，本文結合多粒度粗糙集，分析了可變精度模型下不完備鄰域決策系統的上、下近似算子及屬性約簡，并通過鄰域粒化方法構建了廣義鄰域下可變精度的粗糙集模型；在此基礎上，構造了一種衡量屬性重要度的方法，并設計了不完備鄰域系統的屬性約簡算法；最后，通過實例分析驗證了算法的有效性。

1 基本知識

給定一個決策系統DS=(U,C,D,V)，其中：U={x1,x2,…,xn}表示非空有限樣本集合，稱為論域；C是條件屬性集合；D是決策屬性，C∩D=φ,若D=φ，則決策系統轉換為信息系統。V為屬性值域，對于?a∈C，Va為屬性a的值域；xi(a)為樣本xi在屬性a上的取值。對于屬性子集R?C，可得到R在U上的劃分U/R={R1,R2,…,Rm}。

如果V中包含連續型和符號型等屬性類型的對象，則該決策系統稱為鄰域決策系統。在鄰域決策系統中，當部分樣本的條件屬性值缺失時，則該鄰域決策系統稱為不完備鄰域決策系統，缺失值用“*”表示。

1)?x,y∈U, ΔA(x,y)≥0, 當ΔA(x,y)=0時, ?ai∈A,ai(x)=ai(y)；

2)?x,y∈U,ΔA(x,y)=ΔA(y,x)；

3)?x,y,z∈U,ΔA(x,z)≤ΔA(x,y)+ΔA(y,z)。

對于連續型的數據，采用歐式距離度量：

對于符號型的數據，可定義：

當δ=0時，變為經典粗糙集模型。

定義2[19]將鄰域等價關系擴展到符號型、連續型和缺失型等未知屬性共存下的不完備模糊系統，可得到以下廣義鄰域關系：

R(x)= {(x,y)∈U2:?a∈x∩f1(x)=

f1(y),a(x)∈δ(y,a)∪a(y)∈

δ(x,a)∪a(x)=*∪a(y)=*}

廣義鄰域關系滿足自反性，但不一定滿足對稱性和傳遞性，因為任意樣本與其自身是不可分辨的，所以任何等價關系均滿足自反性。在這里放寬了對稱性和傳遞性的限制，擴展了應用范圍。

定義4 給定DS=(U,C,D,V)是不完備鄰域決策系統，X和Y是U上的兩個非空子集，定義集合X關于集合Y的相對錯誤分類率：

如果將集合X中的元素分到集合Y中，則出現分類錯誤的比例為e(X,Y)×100%。

2 不完備可變精度粗糙集模型

定義5 給定DS=(U,C,D,V)是不完備鄰域決策系統，B?C，決策屬性集合D={d1,d2,…,dn}，0≤k<0.5，在可變精度k下，屬性集B相對于決策屬性D的上、下近似分別為

決策屬性值di在可變精度k的上近似是U中以不小于k的分類樣本劃分到di上的鄰域信息粒子的集合，下近似是U中以不小于1-k的分類樣本劃分到di上的鄰域信息粒子的集合。根據多粒度粗糙集的思想，在可變精度不完備鄰域決策系統中，通過對鄰域粒度δ和可變精度k的控制來區分不同的信息。鄰域粒度δ越小，可變精度k取值越優，區分能力越強。

定理1 由定義5可得以下性質：

從以上性質可知：隨著可變精度k的增大，{di}的正區域和負區域減小，而邊界域則增大;反之，隨著k的減小，{di}的正區域和負區域將增大，而邊界域在縮小。如上所說，在一個合適的可變精度k范圍下，di有較大的可分辨性。

性質1 在不完備鄰域決策系統中，對缺失的條件屬性值的判定：當決策屬性值一致時，如果符號型條件屬性取值相同，連續型屬性取值在相同鄰域內的對象歸為同一類，否則視為不同類。

在不完備鄰域決策系統DS=(U,C,D,V)中，條件屬性集合為C={C1,C2,C3,C4}，決策屬性集為D={d1,d2}，{C1,C2,C3}為連續型數值屬性，{C4}為符號型屬性，下面通過表1的實例說明。

表1 不完備鄰域決策系統(1)

令δ=0.1，k=0.2，因為樣本x1與x5的決策屬性D取值不同，就算連續型的屬性值都在鄰域范圍內，符號型條件屬性取值相同，也不能視為同一類；因為當k=0.2時，即兩個樣本在C1,C2,C3,C4屬性中只能有一個屬性取值不同或不在同一鄰域中，所以x1,x2屬于同一類，x1與x3,x4不屬于同一類。

定義7 給定DS=(U,C,D,V)是不完備鄰域決策系統，決策屬性集合D={d1,d2,…,dn}，B?C，若屬性子集B是不完備鄰域決策系統的一個約簡集，則B滿足：

該定義的條件1)保證了在可變精度k下，約簡集與系統中含有全部條件屬性時的集合具有相同的分辨能力；條件2)保證了屬性子集B是獨立的，所有的屬性都是必不可少的，沒有冗余的屬性。這一定義與經典粗糙集模型中的定義在形式上是完全一致的。然而，由于該模型定義了數值空間中的粒化和逼近，而經典粗糙集是定義在離散空間的，因此適合于完全不同的應用場合。

定義8 給定DS=(U,C,D,V)是不完備鄰域決策系統，B?C，對于?a∈C-B，則屬性a相對于B的重要性計算方式為

3 變精度下不完備鄰域系統的屬性約簡

3.1 變精度下不完備鄰域系統的屬性約簡算法

輸入 不完備鄰域決策系統DS=(U,C,D,V)，鄰域半徑δ，可變精度k。

輸出 屬性約簡結果RED。

1)初始化RED=φ；

2) 根據決策屬性D的值對論域U進行劃分U/D={D1,D2,…,Dm}；

7)輸出約簡RED，算法結束。

算法復雜度分析：

3.2 與經典粗糙集及鄰域模型比較

與經典粗糙集及鄰域模型相比較，本文提出的變精度不完備鄰域系統的屬性約簡模型具有以下優點：

1)經典粗糙集的屬性約簡適用于離散型屬性約簡，需先離散化連續型數據，這將不可避免地造成信息的丟失。而變精度不完備鄰域系統的屬性約簡模型既可處理離散型屬性約簡，也可直接用于連續型屬性約簡。本文的屬性約簡模型是對經典粗糙集模型的擴展。

2)對于含有不完備型數據的決策系統，經典的粗糙集模型較難直接處理，而本文提出的屬性約簡模型可直接對數據進行分析，并在可變精度的調節下，能得到數據不同層次的信息粒度。

3)變精度不完備鄰域系統的屬性約簡模型是對鄰域模型的進一步擴展，基于鄰域的屬性約簡需計算各樣本的鄰域，而本文的屬性約簡模型因為在可變精度的調控下先對樣本進行初步篩選，再進行鄰域計算，有效減少了計算量。

4 實例分析

為了驗證該方法的有效性，我們選擇了一個不完備鄰域決策系統進行詳細分析，表2中共有10個樣本對象，條件屬性集為{C1,C2,C3,C4}, 決策屬性為{D}。設置鄰域半徑δ=0.1，即兩樣本之間的鄰域半徑小于等于0.1；可變精度k=0.2，即兩個樣本在條件屬性集中只能有一個屬性取值不同或不在同一鄰域中。

表2 不完備鄰域決策系統(2)

D1(x)={x3,x4,x5,x8,x9}

D2(x)={x1,x2,x6,x7,x10}

根據鄰域半徑δ=0.1和可變精度k=0.2，通過算法的第3)步可分別計算每個屬性的鄰域關系和所對應的依賴度，即

則可知C3為所對應的屬性重要度最大的屬性，將屬性C3放入RED中，有RED={C2,C3}。

上述實例是對10組樣本對象進行的計算和分析，本文算法中可變精度k值和鄰域半徑δ值是可變的，在現實應用中可根據具體需求設定可變精度和鄰域半徑以滿足知識的細化程度。

5 結束語

針對不完備鄰域決策系統的屬性約簡問題，本文通過鄰域粒化的方法，構建了廣義鄰域下可變精度的粗糙集模型，同時構造了一種屬性重要度的評價方法，并設計了不完備鄰域系統的屬性約簡算法。通過實例分析，該方法能對不完備的數值型和符號型混合數據進行屬性約簡。在大數據時代，數據的不斷產生，需實時更新信息系統，下一步將在此背景下研究，當不完備鄰域決策系統中的數據動態變化時如何對屬性約簡進行增量更新。

[1]PAWLAK Z. Rough sets and intelligent data analysis[J]. Information sciences, 2002, 147(1): 1-12.

[2]ZHANG Junbo, WONG Jiansyuan, PAN Yi, et al, A parallel matrix-based method for computing approximations in incomplete information systems[J]. IEEE transactions on knowledge and data engineering, 2015, 27(2):326-339.

[3]WU Weizhi, QIAN Yuhua, LI Tongjun, et al. On rule acquisition in incomplete multi-scale decision tables[J]. Information sciences, 2017, 378: 282-302.

[4]張文修, 吳偉志, 梁吉業, 等. 粗糙集理論與方法[M]. 北京：科學出版社, 2001: 123-131.

[5]劉芳,李天瑞. 基于邊界域的不完備信息系統屬性約簡方法[J]. 計算機科學, 2016, 43(3): 242-245. LIU Fang, LI Tianrui. Method for attribute reduction based on rough sets boundary regions[J]. Computer science, 2016, 43(3): 242-245.

[6]WU Jianrong, KAI Xuewen, LI Jiaojiao. Atoms of monotone set-valued measures and integrals[J]. Fuzzy sets and systems, 2015, 183: 972-979.

[7]王國胤, 張清華. 不同知識粒度下粗糙集的不確定性研究[J]. 計算機學報,2008, 31(9):1588-1598. WANG Guoyin, ZHANG Qinghua. Uncertainty of rough set in different knowledge granularities[J]. Chinese journal of computers, 2008, 31(9): 1588-1598.

[8]錢文彬,楊炳儒,謝永紅,等. 一種基于屬性度量的快速屬性約簡算法[J]. 小型微型計算機系統, 2014, 35(6): 1407-1411. QIAN Wenbin, YANG Bingru, XIE Yonghong, et al. A quick algorithm for attribute reduction based on attribute measure[J]. Journal of chinese computer systems, 2014, 35(6): 1407-1411.

[9]鞠恒榮, 馬興斌, 楊習貝, 等. 不完備信息系統中測試代價敏感的可變精度分類粗糙集[J]. 智能系統學報, 2014, 9(2):219-223. JU Hengrong, MA Xingbin, YANG Xibei, et al. Test-cost-sensitive based variable precision classification rough set in incomplete information system[J]. CAAI transactions on intelligent systems, 2014, 9(2): 219-223.

[10]陳昊, 楊俊安, 莊鎮泉. 變精度粗糙集的屬性核和最小屬性約簡算法[J]. 計算機學報, 2012, 35(5): 1011-1017. CHEN Hao, YANG Junan, ZHUANG Zhenquan. The core of attributes and minimal attributes reduction in variable precision rough set[J]. Chinese journal of computers, 2012, 35(5):1011-1017.

[11]張清華,薛玉斌,王國胤. 粗糙集的最優近似集[J]. 軟件學報, 2016, 27(2):295-308. ZHANG Qinghua, XUE Yubin, WANG Guoyin. Optimal approximate sets of rough sets[J]. Journal of software, 2016, 27(2): 295-308.

[12]孟慧麗,馬媛媛,徐久成. 基于下近似分布粒度熵的變精度悲觀多粒度粗糙集粒度約簡[J]. 計算機科學, 2016, 43(2): 83-85,104. MENG Huili, MA Yuanyuan, XU Jiucheng. Granularity reduct of variable precision pessimistic multi-granulation rough set based on granularity entropy of lower approximate distribution[J]. Computer science, 2016, 43(2): 83-85,104.

[13]續欣瑩, 劉海濤, 謝珺, 等. 信息觀下基于不一致鄰域矩陣的屬性約簡[J]. 控制與決策, 2016, 31(1):130-136. XU Xinying, LIU Haitao, XIE Jun, et al. Attribute reduction based on inconsistent neighborhood matrix under information view[J]. Control and decision, 2016, 31(1): 130-136.

[14]胡清華,于達仁, 謝宗霞. 基于鄰域粒化和粗糙逼近的數值屬性約簡[J]. 軟件學報, 2008, 19(3): 640-649. HU Qinghua, YU Daren, XIE Zongxia. Numerical attribute reduction based on neighborhood granulation and rough approximation[J]. Journal of software, 2008, 19(3): 640-649.

[15]QIAN Yuhua, LI Shunyong, LIANG Jiye. Pessimistic rough set based decisions: a multigranulation fusion strategy[J]. Information sciences, 2014, 264: 196-210.

[16]LIN Guoping, QIAN Yuhua, LI Jinjin. Neighborhood based multigranulation rough sets[J]. International journal of approximate reasoning, 2012, 7(53): 1080-1093.

[17]沈家蘭, 汪小燕, 申元霞. 可變程度多粒度粗糙集[J]. 小型微型計算機系統, 2016, 37(05): 1012-1016. SHEN Jialan, WANG Xiaoyan, SHEN Yuanxia. Variable Grade multi-granulation rough set [J]. Journal of Chinese computer systems, 2016, 37(5): 1012-1016.

[18]許韋,吳陳,楊習貝. 基于容差關系的不完備可變精度多粒度粗糙集[J]. 計算機應用研究, 2013, 30(6):1712-1715. XU Wei, WU Chen, YANG Xibei. Incomplete variable precision multigranularity rough set based on tolerance relation[J]. Application research of computers, 2013, 30(6):1712-1715.

[19]徐久成, 張靈均, 孫林, 等. 廣義鄰域關系下不完備混合決策系統的約簡[J]. 計算機科學, 2013, 40(4): 244-248. XU Jiucheng, ZHANG Lingjun, SUN Lin, et al. Reduction in incomplete hybrid decision systems based on generalized neighborhood relationship[J]. Computer science, 2013, 40(4): 244-248.

Attribute reduction algorithm of the incomplete neighborhooddecision system with variable precision

WANG Yinglong1, ZENG Qi1, QIAN Wenbin2, YANG Jun2

(1. School of Computer and Information Engineering, Jiangxi Agricultural University, Nanchang 330045, China; 2. School of Software, Jiangxi Agricultural University, Nanchang 330045, China)

Neighborhood rough set model has been widely used in numerical data processing complete, but the discussion of attribute reduction for numeric and symbolic mixed incomplete data is relatively small. Therefore, to resolve this problem, by combining the neighborhood rough set, first, the upper and lower approximation operators and the attribute reduction of the incomplete neighborhood decision system were analyzed based on the variable precision model. Subsequently, based on the generalized neighborhood relation, a rough set model was constructed using the neighborhood granulation method. Furthermore, a method evaluating the attribute significance degree was proposed. Based on this method, an attribute reduction algorithm for the incomplete neighborhood decision system was designed, which can deal with incomplete values directly type and symbolic mixed data. Finally, through the example analysis, the algorithm can solve the attribute reduction result of incomplete neighborhood decision system with variable precision.

rough set theory; neighborhood relation; incomplete information system; variable precision classification; granular computing; multi-granulation; reducation; decision-theoretic rough sets

10.11992/tis.201705027

http://kns.cnki.net/kcms/detail/23.1538.TP.20170705.1654.004.html

2017-05-19. 網絡出版日期：2017-07-05.

國家自然科學基金項目(61502213,71461013,61462038)；江西省自然科學基金項目(20151BAB217009,20132BAB201045)；江西省教育廳科學技術項目(GJJ150399,GJJ150505).

錢文彬. E-mail：qianwenbin1027@126.com.

TP311

A

1673-4785(2017)03-0386-06

王映龍，男，1970年生，教授，博士，主要研究方向為知識發現、數據挖掘和計算智能。

曾淇，女，1991年生, 碩士研究生，主要研究方向為粗糙集理論與知識發現。

錢文彬，男，1984年生，講師，博士, 主要研究方向為粗糙集、粒計算與知識發現。