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

(1.江西農(nóng)業(yè)大學(xué) 計算機與信息工程學(xué)院,江西 南昌 330045; 2.江西農(nóng)業(yè)大學(xué) 軟件學(xué)院,江西 南昌 330045)

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

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

(1.江西農(nóng)業(yè)大學(xué) 計算機與信息工程學(xué)院,江西 南昌 330045; 2.江西農(nóng)業(yè)大學(xué) 軟件學(xué)院,江西 南昌 330045)

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

粗糙集理論；鄰域關(guān)系；不完備信息系統(tǒng)；變精度分類粗糙集；粒計算；多粒度；約簡；決策粗糙集

中文引用格式：王映龍，曾淇，錢文彬，等. 變精度下不完備鄰域決策系統(tǒng)的屬性約簡算法[J]. 智能系統(tǒng)學(xué)報， 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.

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

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

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

1 基本知識

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

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

1)?x,y∈U, ΔA(x,y)≥0, 當(dāng)Δ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)。

對于連續(xù)型的數(shù)據(jù)，采用歐式距離度量：

對于符號型的數(shù)據(jù)，可定義：

當(dāng)δ=0時，變?yōu)榻?jīng)典粗糙集模型。

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

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

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

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

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

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

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

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

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

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

定理1 由定義5可得以下性質(zhì)：

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

性質(zhì)1 在不完備鄰域決策系統(tǒng)中，對缺失的條件屬性值的判定：當(dāng)決策屬性值一致時，如果符號型條件屬性取值相同，連續(xù)型屬性取值在相同鄰域內(nèi)的對象歸為同一類，否則視為不同類。

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

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

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

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

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

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

3 變精度下不完備鄰域系統(tǒng)的屬性約簡

3.1 變精度下不完備鄰域系統(tǒng)的屬性約簡算法

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

輸出 屬性約簡結(jié)果RED。

1)初始化RED=φ；

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

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

算法復(fù)雜度分析：

3.2 與經(jīng)典粗糙集及鄰域模型比較

與經(jīng)典粗糙集及鄰域模型相比較，本文提出的變精度不完備鄰域系統(tǒng)的屬性約簡模型具有以下優(yōu)點：

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

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

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

4 實例分析

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

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

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

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

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

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

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

5 結(jié)束語

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

[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]張文修, 吳偉志, 梁吉業(yè), 等. 粗糙集理論與方法[M]. 北京：科學(xué)出版社, 2001: 123-131.

[5]劉芳,李天瑞. 基于邊界域的不完備信息系統(tǒng)屬性約簡方法[J]. 計算機科學(xué), 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]. 計算機學(xué)報,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]. 小型微型計算機系統(tǒng), 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]鞠恒榮, 馬興斌, 楊習(xí)貝, 等. 不完備信息系統(tǒng)中測試代價敏感的可變精度分類粗糙集[J]. 智能系統(tǒng)學(xué)報, 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]陳昊, 楊俊安, 莊鎮(zhèn)泉. 變精度粗糙集的屬性核和最小屬性約簡算法[J]. 計算機學(xué)報, 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]張清華,薛玉斌,王國胤. 粗糙集的最優(yōu)近似集[J]. 軟件學(xué)報, 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]. 計算機科學(xué), 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]續(xù)欣瑩, 劉海濤, 謝珺, 等. 信息觀下基于不一致鄰域矩陣的屬性約簡[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]胡清華,于達仁, 謝宗霞. 基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡[J]. 軟件學(xué)報, 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]. 小型微型計算機系統(tǒng), 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]許韋,吳陳,楊習(xí)貝. 基于容差關(guān)系的不完備可變精度多粒度粗糙集[J]. 計算機應(yīng)用研究, 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]徐久成, 張靈均, 孫林, 等. 廣義鄰域關(guān)系下不完備混合決策系統(tǒng)的約簡[J]. 計算機科學(xué), 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. 網(wǎng)絡(luò)出版日期：2017-07-05.

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

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

TP311

A

1673-4785(2017)03-0386-06

王映龍，男，1970年生，教授，博士，主要研究方向為知識發(fā)現(xiàn)、數(shù)據(jù)挖掘和計算智能。

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

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