陳燕云　肖坤楠　邱建林

摘要：將MATLAB模糊工具箱和粗糙集數(shù)據(jù)處理工具Rosetta結(jié)合在一起使用，提出一種基于模糊C聚類劃分的并行粗糙集屬性值約簡算法，將數(shù)據(jù)集劃分到一個個子系統(tǒng)中處理，大大提高了約簡的效率。采用聚類算法進(jìn)行劃分，將相似度高的規(guī)則放到一個簇中，便于約簡，同時由于不同簇的相異程度較高，可以采用直接合并的方式進(jìn)行全局選擇。

關(guān)鍵詞：粗糙集；屬性值約簡；聚類；并行

中圖法分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）12-0176-03

A Parallel Rough Set Attribute Value Reduction Algorithm Based on Clustering Partition

CHEN Yan-yun1 ，XIAO Kun-nan1， QIU jian-lin2

（1.Nantong University Engineering Training Center， Nantong 226019，China；2.College of Computer Science and Technology， Nantong University， Nantong 226019，China）

Abstract： Adopt the parallel idea into rough set attribute value reduction， diving the data set into several sub-systems and processing at the same time， which greatly improve the reduction efficiency. Using clustering division to put the high similarity rules into a cluster to reduce easily， meanwhile， the difference between different clusters contributes to merger directly in global section. Apply the algorithm to corn breeding and it performs better.

Key words： rough set； attribute value reduction； clustering； parallel

粗糙集是由波蘭科學(xué)家Z.Pawlak[1]提出的一種處理不確定、不精確、不完整信息的新的數(shù)據(jù)挖掘工具，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的信息。與人工智能領(lǐng)域其他一些處理不確定問題的數(shù)學(xué)工具相比，粗糙集有著它自身的優(yōu)點。比如統(tǒng)計理論需要知道數(shù)據(jù)先驗概率、模糊集理論需要知道隸屬函數(shù)等，而粗糙集無需提供問題所需處理的數(shù)據(jù)集合之外的任何先驗信息，避免了帶入人為的模糊性，從而更具客觀性，這一優(yōu)點也決定它成為分析不精確系統(tǒng)的一種理想方法。

約簡是粗糙集理論的核心問題，可以作為大規(guī)模數(shù)據(jù)集處理的預(yù)處理工具，為進(jìn)一步的數(shù)據(jù)挖掘工作做準(zhǔn)備。約簡包括屬性約簡和屬性值約簡。屬性約簡是刪除冗余的或不重要的屬性，是一個橫向約簡，目前關(guān)于粗糙集屬性約簡的研究已經(jīng)比較成熟。但屬性約簡后的數(shù)據(jù)集還不是最簡的，屬性值約簡實際就是除去多余的屬性值，用較少的條件屬性來區(qū)分每個決策類，從而得到最簡的規(guī)則集。目前已經(jīng)提出了一些屬性值約簡算法，比較經(jīng)典的是文獻(xiàn)[2]，它根據(jù)刪除某個屬性值后決策表出現(xiàn)的不同狀況標(biāo)記不同的符號，并對不同的符號用不同的處理方法，從而刪除冗余的記錄。此外，還有黃燕等[3]提出的基于相似矩陣的約簡算法，以及張學(xué)斌等[4]提出的啟發(fā)式的屬性值約簡算法等等。

本文在常規(guī)屬性值約簡算法的基礎(chǔ)上，用并行的思想來處理約簡。決策表的每一行代表一條規(guī)則，采用基于聚類的劃分思想，將相似度較高的規(guī)則放到一個簇中，這樣容易產(chǎn)生冗余或矛盾，并且由于簇與簇之間的相異度較大，因而在全局選擇時，就將個子系統(tǒng)約簡后的規(guī)則之間合并得到最終結(jié)果。

1 基礎(chǔ)知識

定義1：知識表達(dá)系統(tǒng)S可以表示為四元組，即S=（U， A， V， f）。其中，U是一個有限的非空集合，稱為論域；A=[C?D]是屬性集合，C是條件屬性，D為決策屬性，[C?D=φ，V=a∈AVa]，性值的集合；f ： U [×]A [→]V 是一個信息函數(shù)，它為每個對象賦予一個信息值。在粗糙集理論中，知識表達(dá)系統(tǒng)又被稱為信息系統(tǒng)，通常用S=（U，A）表示[2]。

定義2：設(shè)S=（U，A）為一信息系統(tǒng)，[B?A]，則不可分辨關(guān)系表示如下：

[IND（B）=（x，y）∈U×U|?b∈B，f（x，b）=f（y，b）]

若[（x，y）∈IND（B）]，則稱[x]和[y]是B不可區(qū)分的，即相對于B是不可分辨的。不可分辨關(guān)系又稱為等價關(guān)系。對于[x∈U]，它的B等價類定義為[[x]B=y∈U|（x，y）∈IND（B）]，[U/IND（B）=X1，X2…，XK]表示關(guān)系[IND（B）]在U上的等價類族，簡記為[UB]。

定義3：對于任意的[x?U，B?A]， X 的 B下近似集和 B上近似集分別描述為：

[B（X）=?x∈U：IB（x）?X]

[B（X）=?x∈U：IB（x）?X≠φ]

集合X的B邊界域為：[BNB（X）=B（X）-B（X）]

[B（X）]是由那些根據(jù)B判斷一定屬于X的U中元素組成的集合；[B（X）]是那些根據(jù)B判斷可能屬于X的U中的元素組成的集合；而那些根據(jù)B判斷可能屬于但又不能完全肯定屬于X的對象所組成的集合稱為邊界域。

另外，正域、負(fù)域定義如下：

正域：[POSB（X）=BX]；

負(fù)域：[NEGB（X）=BX]。

定義4：粗糙度是表示知識的不完全程度，由等價關(guān)系B定義集合X的粗糙度為：

[ρB（X）=1-B（X）B（X）]

其中[X≠φ，X]表示集合X的基數(shù)，顯然有[0≤ρR（X）≤1]。

2 基于模糊聚類劃分的并行粗糙集屬性值約簡算法

2.1 劃分策略

對于并行約簡來說，最終的約簡是建立在對子表進(jìn)行并行計算的基礎(chǔ)上實現(xiàn)的，因此，如何劃分子表是并行約簡的前提，并且劃分策略的好壞將直接影響到最終并行約簡的結(jié)果。找到一種高效、易實現(xiàn)、兼顧精準(zhǔn)性的子表劃分策略一直都是并行計算研究工作的重點。

本文將采用基于聚類的劃分思想，將將相似度較高的規(guī)則放到一個簇中，這樣容易產(chǎn)生冗余和矛盾，便于約簡，另外由于簇與簇之間的相異度較大，因而在全局選擇時，就將個子系統(tǒng)約簡后的規(guī)則之間合并得到最終結(jié)果。這里的聚類算法我們選擇模糊C均值聚類，算法對于滿足正態(tài)分布的數(shù)據(jù)聚類效果會很好，但對孤立點是敏感的。不過我們這里只是進(jìn)行劃分，聚類的效果不用特別精確。我們可以采用MATLAB模糊工具箱中的聚類函數(shù)直接處理數(shù)據(jù)。用到的幾個函數(shù)如下：

[center， U， obj_fcn]=fcm （data， cluster_n）；

maxU=max（U）；

index1=find（U（1，：）==max U）； %查看第一類別的元素

……；

Index n=find（U（n，：）==max U）；

其中：data為給定數(shù)據(jù)集，cluster_n為用戶提供的聚類中心的個數(shù)，center為迭代以后得到的聚類中旬，U為所有數(shù)據(jù)點對聚類中心的隸屬度函數(shù)矩陣，obj_fcn為迭代計算過程中的變化值。

2.2 基于模糊聚類劃分的并行粗糙集屬性約簡算法

輸入：決策系統(tǒng)[S=（U，C?D，V，f）]；

輸出：約簡后的決策規(guī)則。

1） 用值在0，1間的隨機數(shù)初始化隸屬矩陣U，使其滿足式[i=1cuij=1，?j=1，2，…，n]

2） 用式[ci=j=1nuijmxjj=1nuijm]計算c個聚類中心[ci]，i=1，…，c。

3） 根據(jù)[J（U，c1，…，cc）=i=1cJi=i=1cjnuijmdij2]，計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)值的改變量小于某個閥值，則算法停止。

4） 用[uij=1k=1c（dijdkj）2/（m-1）]計算新的U矩陣。返回步驟2

5） 并行地在各類別中進(jìn)行屬性值約簡；

6） 將各值約簡后的規(guī)則合并，去除冗余得整體的最終約簡。

本文的模糊C均值聚類算法采用MATLAB模糊工具箱里的FCM函數(shù)進(jìn)行處理，而屬性值約簡在粗糙集數(shù)據(jù)處理軟件Rosetta上進(jìn)行。

3 實例分析

實例選用屬性約簡后的南通市2006年年終匯總（Y組）玉米樣本集（表1）為例，實現(xiàn)粗糙集屬性值約簡算法的應(yīng)用。該樣本集包括51個玉米樣本和9個重要屬性，分別是生育期、株高、穗高、穗長、穗粗、千粒重、穗行數(shù)、行粒數(shù)、小區(qū)產(chǎn)量。其中前面八個是條件屬性，區(qū)產(chǎn)量為決策屬性。

1） 如果采用對該數(shù)據(jù)集直接進(jìn)行屬性值約簡，得到的結(jié)果如表2。

2） 我們采用并行處理方法：① 用MATLAB得到的聚類結(jié)果如表3。

②各類簇分別進(jìn)行屬性值約簡最終合并的規(guī)則如表4。

3） 實驗結(jié)果分析

將實例最后的約簡結(jié)果與不進(jìn)行劃分而直接屬性約簡的結(jié)果進(jìn)行對照分析可以看到，并行處理結(jié)果無論在規(guī)則的數(shù)量上減少了，并且在規(guī)模上有了很大的壓縮，這說明，該數(shù)據(jù)集得到了較好的數(shù)據(jù)挖掘，得到了大量數(shù)據(jù)中最為關(guān)鍵的知識，并行方法的運用是切實有效的。

4 結(jié)束語

粗糙集理論已經(jīng)被證明是十分有效的工具，它在工業(yè)、商業(yè)等領(lǐng)域都已經(jīng)成功運用，本文采用并行粗糙集屬性約簡方法來處理農(nóng)業(yè)領(lǐng)域的玉米品種資源數(shù)據(jù)，為后續(xù)步驟中選育優(yōu)良品種提供了有效支持。最后這樣一個并行的處理方式將便于增量式管理，可以新增加的樣本可以的單獨作為一個簇參與處理，因而它將發(fā)揮更大的作用。

參考文獻(xiàn)：

[1] Pawlak Z. Rough Set [J]. International Journal of Information and Computer Science， 1982，11（5）： 314-356.

[2] 常犁云，王國胤， 吳渝. 一種基于Rough Set理論的屬性約簡及規(guī)則提取方法[J].軟件學(xué)報， 1999， 10（11）： 1206-1211.

[3] 黃艷， 沈維燕. 基于粗集理論的屬性值約簡算法研究[J]. 金陵科技學(xué)院學(xué)報， 2009， 25（4）： 29-32.

[4] 張學(xué)斌， 丁曉明. 一種基于關(guān)聯(lián)規(guī)則的屬性值約簡算法[J]. 西南師范大學(xué)學(xué)報， 2005， 30（3）： 440-443.