一種基于聚類劃分的并行粗糙集屬性值約簡(jiǎn)算法

陳燕云　肖坤楠　邱建林

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

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

中圖法分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)隱含的知識(shí)，揭示潛在的信息。與人工智能領(lǐng)域其他一些處理不確定問(wèn)題的數(shù)學(xué)工具相比，粗糙集有著它自身的優(yōu)點(diǎn)。比如統(tǒng)計(jì)理論需要知道數(shù)據(jù)先驗(yàn)概率、模糊集理論需要知道隸屬函數(shù)等，而粗糙集無(wú)需提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息，避免了帶入人為的模糊性，從而更具客觀性，這一優(yōu)點(diǎn)也決定它成為分析不精確系統(tǒng)的一種理想方法。

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

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

1 基礎(chǔ)知識(shí)

定義1：知識(shí)表達(dá)系統(tǒng)S可以表示為四元組，即S=（U， A， V， f）。其中，U是一個(gè)有限的非空集合，稱為論域；A=[C?D]是屬性集合，C是條件屬性，D為決策屬性，[C?D=φ，V=a∈AVa]，性值的集合；f ： U [×]A [→]V 是一個(gè)信息函數(shù)，它為每個(gè)對(duì)象賦予一個(gè)信息值。在粗糙集理論中，知識(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ū)分的，即相對(duì)于B是不可分辨的。不可分辨關(guān)系又稱為等價(jià)關(guān)系。對(duì)于[x∈U]，它的B等價(jià)類定義為[[x]B=y∈U|（x，y）∈IND（B）]，[U/IND（B）=X1，X2…，XK]表示關(guān)系[IND（B）]在U上的等價(jià)類族，簡(jiǎn)記為[UB]。

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

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

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

集合X的B邊界域?yàn)椋篬BNB（X）=B（X）-B（X）]

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

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

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

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

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

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

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

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

2.1 劃分策略

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

本文將采用基于聚類的劃分思想，將將相似度較高的規(guī)則放到一個(gè)簇中，這樣容易產(chǎn)生冗余和矛盾，便于約簡(jiǎn)，另外由于簇與簇之間的相異度較大，因而在全局選擇時(shí)，就將個(gè)子系統(tǒng)約簡(jiǎn)后的規(guī)則之間合并得到最終結(jié)果。這里的聚類算法我們選擇模糊C均值聚類，算法對(duì)于滿足正態(tài)分布的數(shù)據(jù)聚類效果會(huì)很好，但對(duì)孤立點(diǎn)是敏感的。不過(guò)我們這里只是進(jìn)行劃分，聚類的效果不用特別精確。我們可以采用MATLAB模糊工具箱中的聚類函數(shù)直接處理數(shù)據(jù)。用到的幾個(gè)函數(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為用戶提供的聚類中心的個(gè)數(shù)，center為迭代以后得到的聚類中旬，U為所有數(shù)據(jù)點(diǎn)對(duì)聚類中心的隸屬度函數(shù)矩陣，obj_fcn為迭代計(jì)算過(guò)程中的變化值。

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

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

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

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

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

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

3） 實(shí)驗(yàn)結(jié)果分析

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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