王秀秀, 王阿巖, 王長忠(渤海大學(xué) 數(shù)理學(xué)院, 遼寧 錦州 121000)

?

連續(xù)型目標信息系統(tǒng)的屬性約簡

王秀秀, 王阿巖, 王長忠
(渤海大學(xué) 數(shù)理學(xué)院, 遼寧 錦州 121000)

針對連續(xù)型數(shù)據(jù)的屬性約簡問題, 提出了一種新的屬性約簡方法----基于分配可辨識矩陣的屬性約簡方法。給出了基于連續(xù)型數(shù)據(jù)的分配協(xié)調(diào)集的概念, 研究了基于連續(xù)型數(shù)據(jù)的分配協(xié)調(diào)集的基本性質(zhì), 定義了基于分配協(xié)調(diào)集的辨識矩陣。在此基礎(chǔ)上提出了基于辨識矩陣的連續(xù)型數(shù)據(jù)的屬性約簡方法, 并給出了計算辨識矩陣的算法。實例分析表明, 該方法能有效地對連續(xù)型數(shù)據(jù)進行屬性約簡。

粗糙集； 辨識矩陣； 屬性約簡； 連續(xù)值域信息系統(tǒng)

0 引 言

粗糙集理論[1,2]是由波蘭數(shù)學(xué)家Pawlak[3]于1982年提出的一種數(shù)據(jù)分析理論, 目前已發(fā)展成為一種處理模糊和不確定性知識的數(shù)學(xué)工具。近年來, 被廣泛應(yīng)用于人工智能[4,5]、 過程控制、 數(shù)據(jù)挖掘[6,7]、 決策支持和分析以及知識發(fā)現(xiàn)[8]等領(lǐng)域。利用粗糙集進行數(shù)據(jù)挖掘、 知識規(guī)則[9,10]和特征選擇[11-13]是基于粗糙集的屬性約簡理論[14,15]進行的, 屬性約簡是粗糙集理論的重要研究內(nèi)容之一。

傳統(tǒng)的粗糙集理論是基于論域上的等價關(guān)系描述的, 由等價關(guān)系形成劃分, 構(gòu)造論域上的上、 下近似算子, 并研究相應(yīng)的知識約簡與知識獲取問題。 但這只適用于離散型的數(shù)據(jù), 對于連續(xù)型目標信息系統(tǒng), 對象之間的等價關(guān)系很難構(gòu)造, 或?qū)ο笾g本質(zhì)上沒有等價關(guān)系。筆者通過構(gòu)造樣本之間的一種相似關(guān)系對整個樣本集進行粒化, 從而得到每個樣本的相似類, 然后定義上、 下近似算子[16]以及分配協(xié)調(diào)函數(shù), 研究連續(xù)型目標信息系統(tǒng)的辨識矩陣以及基于辨識矩陣的屬性約簡。

1 連續(xù)型數(shù)據(jù)的粗糙集

定義1[16]設(shè)(U,A,F,d,G)為一個目標信息系統(tǒng), 其中U是非空有限樣本集,U={x1,x2,…,xn}；A是條件屬性集,A={a1,a2,…,am}；d是目標屬性；F是U與A的關(guān)系集,F={fk:U→Vk,k≤m},Vk是連續(xù)型數(shù)據(jù), 是ak的值域；G是U與d的關(guān)系集,G={gd:U→Vd},Vd={1,2,3,…,r}。則稱(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng)。

設(shè)(U,A,F,d,G)是連續(xù)型目標信息系統(tǒng),ε∈[0,1]。對于B?A, 令

RB={(x,y)∈U×U: |fk(x)-fk(y)|≤ε, ?ak∈B}

δB(x)={y∈U: (x,y)∈RB}

Rd={(x,y)∈U×U:gd(x)=gd(y), ?ak∈B}

顯然,RB是自反和對稱的, 傳遞性則一般不成立, 所以RB是相似關(guān)系。ε是刻畫樣本相似性所允許的誤差。Rd顯然是論域上的等價關(guān)系, 從而產(chǎn)生論域上的一個劃分, 即U/Rd={D1,D2,…,Dr}, 其中Di={x:gd(x)=i,x∈U}。

定義2[16]設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), 對于?X?U, 在關(guān)系RB下的上、 下可近似定義為

2 分配函數(shù)的概念及其性質(zhì)

性質(zhì)1 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), 給定ε≥0, 設(shè)B?A, 則PosB(D)?PosA(D)。

定義3 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), 給定ε≥0, 對于B?A, 記φB(x)={Dl:Dl∩δB(x)≠?}, 稱φB(x)為相關(guān)決策類函數(shù)。若?x∈U,φB(x)=φA(x), 則B是ε分配協(xié)調(diào)集。當(dāng)B是ε分配協(xié)調(diào)集, 且?C?B, ?x0使φA(x0)≠φc(x0), 則B為ε分配約簡。

性質(zhì)2 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), 給定ε≥0, 當(dāng)B?A時, 則φA(x)?φB(x)(?x∈U)。

證明 因為B?A, 所以RA?RB, 即?x∈U,δA(x)?δB(x)。因為φB(x)={Dl:Dl∩δB(x)≠?}, 所以φA(x)?φB(x)。

3 連續(xù)型目標信息系統(tǒng)的辨識矩陣以及屬性約簡

定理1 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng),B?A, 若B是ε分配協(xié)調(diào)集, 當(dāng)且僅當(dāng)?x,y∈U, 當(dāng)gd(y)?φA(x)時有y?δB(x)。

證明1 充分性。?x,y∈U, 若y∈δB(x), 則gd(y)∈φB(x)。因為B是ε分配協(xié)調(diào)集, 所以φB(x)=φA(x), 從而gd(y)∈φA(x), 得證。

證明2 必要性。?x∈U, 若Dj∈φB(x), 則δB(x)∩Dj≠?, 所以?y∈δB(x)使gd(y)=Dj。若y∈δB(x), 則gd(y)∈φB(x), 即Dj∈φA(x), 所以φB(x)?φA(x)。 因為B?A, 所以φA(x)?φB(x), 從而φA(x)=φB(x)。

定義4 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng)。若?x∈U, |φA(x)|=1, 則稱(U,A,F,d,G)為一致連續(xù)型目標信息系統(tǒng)。

定理2 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng),B?A。則PosA(D)=PosB(D)當(dāng)且僅當(dāng)?x∈U, 當(dāng)|φA(x)|=1時, 有|φB(x)|=1。

證明 略。

定義5 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), ?x,y∈U, 定義

稱E(x,y)為ε分配可辨識矩陣。

定理3 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng),B?A。B是約簡當(dāng)且僅當(dāng)?x,y∈U,B滿足

B∩E(x,y)≠?, ?b∈B, {B-b}∩E(x,y)=?。

基于分配協(xié)調(diào)集的辨識矩陣算法如下。

Input： 數(shù)據(jù)庫系統(tǒng)D=(U,A,F)以及參數(shù)ε//ε是樣本相似時所允許的誤差。

Output：E//E是辨識矩陣。

1) 將樣本集進行歸一化處理。

2) 計算樣本的個數(shù)row, 條件屬性個數(shù)col。

3) 求d//d是個數(shù)組是樣本的決策形成的等價類。

4) 求h//h是個數(shù)組, 每個細胞數(shù)組表示一個樣本的相似類。

5) 求Q//Q是個數(shù)組, 每個細胞數(shù)組表示一個樣本的相關(guān)決策類。

6)E={}；

7) fori=1:row

forj=1:row

ifgd(xj)∈Q(xi)//Q(xi)表示xi的相關(guān)決策類。

E{i,j}=1:col

Else

nosimilei={k∈A: |fk(xi)-fk(xj)|>ε}//k表示第k個條件屬性。

E{i,j}=nosimiler

End

End

End

定義6 設(shè)(U,A,F,d,G)為連續(xù)型目標信息系統(tǒng), 定義基于辨識矩陣的辨識公式

M=∧{∨{ai:ai∈E(x,y)}:x,y∈U}。

辨識公式M的最小表達式為

則M最小表達式的每一項為連續(xù)型目標信息系統(tǒng)的約簡。

4 實例分析

表1是石油勘探信息表, 其中No為石油井編號,a1為平均振幅,a2為能量半衰減時間,a3為瞬時頻率,a4為均方根振幅,d為決策。

表1 石油信息表Tab.1 The information of petroleum

圖1 分類精度Fig.1 Accuracy of selected features

筆者采用Matlab實現(xiàn)對筆者算法有效性進行檢驗, 實驗結(jié)果如圖1所示。

從圖1明顯可以看出, 當(dāng)ε∈[0.1,0.35]時精度最高, 可以達到100%, 所以筆者的算法是有效的。例如, 當(dāng)ε=0.3時, 分類精度是100%, 應(yīng)用上述求辨識矩陣算法可得： 在ε=0.3時表1的辨識矩陣如表2所示。

表2 表1的辯識矩陣Tab.2 Discernibility matrix of table1

根據(jù)辨識公式

M=∧{∨{ai:ai∈E(xi,xj)}:i,j≤7}=∧{∨(E(xi,xj)):i,j≤7}=(a2∨a3)∧(a1∨a2∨a3)∧(a1∨a2∨a3∨a4)∧a2∧(a1∨a2∨a4)∧(a2∨a3∨a4)=a2

表1在參數(shù)ε=0.3的情況下, 屬性{a1,a2,a3,a4}的約簡是{a2}, 即在保持樣本相關(guān)決策類不變的情況下, 屬性可約簡為{a2}。

5 結(jié) 語

筆者根據(jù)基于辨識矩陣的符號型信息系統(tǒng)的屬性約簡方法提出了基于辨識矩陣的連續(xù)型數(shù)據(jù)的屬性約簡方法, 并通過實例測試了方法的有效性。實例分析說明了方法能有效地對連續(xù)型數(shù)據(jù)進行屬性約簡。由于連續(xù)型數(shù)據(jù)的屬性約簡方法比較匱乏, 以后筆者還可以就變精度連續(xù)型數(shù)據(jù)的屬性約簡以及變精度優(yōu)勢關(guān)系下的屬性約簡進行研究。

[1]BONIKOWSKI Z, BRYNIARSKI E, WYBRANIEC U. Extensions and Intentions in the Rough Set Theory [J]. Information Sciences, 1998, 107: 149-167.

[3]PAWLAK Z, SKOWRON A. Rudiments of Rough Sets [J]. Information Sciences, 2007, 177: 3-27.

[4]WITOLD PEDRYCZ, SONG Mingli. Analytic Hierarchy Process(AHP) in Group Decision Making and Its Optimization with an Allocation of Information Granularity [J]. IEEE Transactions on Fuzzy System, 2011, 19(3): 527-539.

[5]任海軍, 張曉星, 肖波, 等. 基于概念格的神經(jīng)網(wǎng)絡(luò)日最大負荷預(yù)測輸入?yún)?shù)選擇 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版, 2011, 49(1): 87-93. REN Haijun, ZHANG Xiaoxing, XIAO Bo, et al. Input Parameters Selection in Neural Network Load Forecasting Made Based on Concept Lattice [J]. Journal of Jilin University: Science Edition, 2011, 49(1): 87-93.

[6]YAO Yiyu, ZHAO Liquan. A Measurement Theory View on the Granularity of Partitions [J]. Information Sciences, 2012, 213: 1-13.

[7]WANG Changzhong, CHEN Degang, SUN Baiqing, et al. Communication between Information Systems with Covering Based Rough Sets [J]. Information Scienceset, 2012, 216: 17-33.

[8]SWINIARSKI R W, SKOWRON A. Rough Set Methods in Feature Selection and Recognition [J]. Pattern Recognition Letters, 2003, 24(6): 833-849.

[9]BLASZCZYNSKI J, SLOWINSKI R, SZELAG M. Sequential Covering Rule Induction Algorithm for Variable Consistency Rough Set Approaches [J]. Information Sciences, 2011, 181(5): 987-1002.

[10]DU Y. Rule Learning for Classification Based on Neighborhood Covering Reduction [J]. Information Science, 2011, 181(5): 5457-5467.

[11]楊杰明, 劉元寧, 曲朝陽, 等. 文本分類中基于綜合度量的特征選擇方法 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版, 2013, 51(5): 887-893. YANG Jieming, LIU Yuanning, QU Chaoyang, et al. Feature Selection Algorithm Based on Comprehensive Measurement for Text Categorization [J]. Journal of Jilin University: Science Edition, 2013, 51(5): 887-893.

[12]鮑捷, 楊明, 何志芬. 基于SVM評價準則的高維數(shù)據(jù)混合特征選擇算法 [J]. 吉林大學(xué)學(xué)報： 理學(xué)版, 2012, 50(6): 1192-1198. BAO Jie, YANG Ming, HE Zhifen. Ensemble Feature Selection Algorithm Based on SVM-Based Criteria for High-Dimensional Data [J]. Journal of Jilin University: Science Edition, 2012, 50(6): 1192-1198.

[13]JENSEN R, SHEN Q. New Approaches to Fuzzy-Rough Feature Selection [J]. IEEE Transactions on Fuzzy Systems, 2009, 17(4): 824-838.

[14]WU W Z. Attribute Reduction Based on Evidence Theory in Incomplete Decision Systems [J]. Information Sciences, 2008, 178: 1355-1371.

[15]MAJI P, GARAI P. Fuzzy-Rough Simultaneous Attribute Selection and Feature Extraction Algorithm [J]. IEEE Transactions on Cybernetic, 2013, 43(4): 1166-1177.

[16]張文修, 梁怡, 吳偉志. 信息系統(tǒng)與知識發(fā)現(xiàn) [M]. 北京： 科學(xué)出版社, 2003. ZHANG Wenxiu, LIANG Yi, WU Weizhi. Information System and Knowledge Discovery [M]. Beijing: Science Press, 2003.

(責(zé)任編輯： 張潔)

Attribute Reduction in Numerical Decision Systems

WANG Xiuxiu, WANG Ayan, WANG Changzhong
(College of Mathematics and Physics, Bohai University, Jinzhou 121000, China)

A method which aims at attribute reduction based on assignment set in numerical data sets is proposed. Firstly, the concept and some important properties of assignment set based on numerical data sets was presented. Then, authors defined dicernibility matrix based on assignment set, and proposed a new method for attribute reduction based on discernibility matrix in numerical data sets. Finally, an algorithm for computing discernibility matrix was presented. Example analysis show that this method can effectively handle attribute reduction in numerical decision systems.

rough sets； discernibility matrix； attribute reduction； numerical decision systems

1671-5896(2014)05-0534-05

2013-11-13

國家自然科學(xué)基金資助項目(61070242); 遼寧省優(yōu)秀人才支持計劃基金資助項目(LR2012039)

王秀秀(1988— ), 女, 遼寧莊河人, 渤海大學(xué)碩士研究生, 主要從事粒計算與模式識別理論與方法研究, (Tel)86-15241622803(E-mail)wangxiuxiujiayou@126.com； 王長忠(1968— ), 男, 內(nèi)蒙古商都人, 渤海大學(xué)副教授, 博士, 碩士生導(dǎo)師, 主要從事粒計算、 模式識別和數(shù)據(jù)挖掘研究, (Tel)86-15041656439(E-mail)changzhongwang@126.com。

TP18

： A