基于粗糙集的海量數(shù)據(jù)挖掘算法研究

牛詠梅

摘 要： 針對(duì)傳統(tǒng)數(shù)據(jù)挖掘算法在數(shù)據(jù)量級(jí)方面的局限性，提出在粗糙集理論的基礎(chǔ)上，采用類分布鏈表結(jié)構(gòu)改進(jìn)傳統(tǒng)的基于屬性重要性的數(shù)據(jù)離散化算法、屬性約簡(jiǎn)算法以及基于啟發(fā)式的值約簡(jiǎn)算法。討論了基于動(dòng)態(tài)聚類的兩步離散化算法，當(dāng)算法適應(yīng)大數(shù)據(jù)處理之后，采用并行計(jì)算的方法提高算法的執(zhí)行效率。算法測(cè)試結(jié)果表明，改進(jìn)算法能有效地處理大數(shù)據(jù)量，同時(shí)并行計(jì)算解決了大數(shù)據(jù)量處理帶來的效率問題。

關(guān)鍵詞： 數(shù)據(jù)挖掘； 粗糙集； 大數(shù)據(jù)處理； 并行計(jì)算

中圖分類號(hào)： TN911?34； TQ028.1 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）07?0115?05

Abstract： Since the traditional data mining algorithm has the limitation in the aspect of data magnitude， on the basis of rough set theory， the class distribution list structure is used to improve the traditional data discretization algorithm based on attribute importance， attribute reduction algorithm and heuristic?based value reduction algorithm. The two?step discrete algorithm based on dynamic clustering is discussed. When the algorithm adapts to the big data processing， the parallel computing method is used to improve the execution efficiency of the algorithm. The test results of the algorithm show that the improved algorithm can effectively process the big data size. The parallel computing can solve the efficiency problem causing by big data size processing.

Keywords： data mining； rough set； big data processing； parallel computing

0 引 言

信息時(shí)代，數(shù)據(jù)（尤其是海量數(shù)據(jù)）已被各企業(yè)、各研究機(jī)構(gòu)當(dāng)成重大的知識(shí)來源、決策的重要依據(jù)[1]，對(duì)于數(shù)據(jù)的急速增長(zhǎng)，如何有效地解決數(shù)據(jù)挖掘過程中空間和時(shí)間的可伸縮性已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中迫切需要解決的難題[2]。從知識(shí)發(fā)現(xiàn)的過程中可以看到，數(shù)據(jù)挖掘不僅面臨著數(shù)據(jù)庫(kù)中的龐大數(shù)據(jù)問題[3]，而且這些數(shù)據(jù)有可能是不整齊的、不完全的、隨機(jī)的、有噪聲的、復(fù)雜的數(shù)據(jù)結(jié)構(gòu)且維數(shù)大[4]。傳統(tǒng)的數(shù)據(jù)挖掘算法還限制于單機(jī)內(nèi)存的容量[5]，當(dāng)一次性需要分析的數(shù)據(jù)不能全部進(jìn)入內(nèi)存時(shí)，算法的性能就會(huì)嚴(yán)重降低[6]，甚至得不到預(yù)期的結(jié)果，使用基于粗糙集理論的算法策略將有效解決這個(gè)問題[7]。

本文針對(duì)傳統(tǒng)數(shù)據(jù)挖掘算法在數(shù)據(jù)量級(jí)方面的局限性，提出了結(jié)合類分布鏈表，把數(shù)據(jù)挖掘算法推廣到可以處理更高數(shù)據(jù)量級(jí)，最后采用并行計(jì)算的方法提高基于動(dòng)態(tài)聚類的兩步離散化算法適應(yīng)大數(shù)據(jù)處理之后的執(zhí)行效率。

1 改進(jìn)的Rough Set知識(shí)約簡(jiǎn)算法

許多經(jīng)典的Rough Set知識(shí)約簡(jiǎn)算法都可以通過引進(jìn)CDL（類分布鏈表）改進(jìn)，CDL可以反映某個(gè)條件屬性組合對(duì)論域的分類情況。CDL分為不相容類分布鏈表（ICDL）和相容類分布鏈表（CCDL）兩部分，CCDL根據(jù)鏈表中每個(gè)分類的樣本數(shù)目又可分為單例相容類分布鏈表（SSCDL）和多例相容類分布鏈表（MSCDL）[7]。引進(jìn)CDL后相對(duì)于原始的經(jīng)典算法，改進(jìn)后的算法將具有更好的可伸縮性，能夠更好地處理海量數(shù)據(jù)集。以下通過引入CDL對(duì)包括離散化、屬性約簡(jiǎn)和值約簡(jiǎn)的一組Rough Set知識(shí)約簡(jiǎn)算法進(jìn)行改進(jìn)。

1.1 改進(jìn)的離散化算法

數(shù)據(jù)離散化是Rough Set知識(shí)獲取方法中的重要組成部分。在此采用基于屬性重要性的離散化算法，在原算法的基礎(chǔ)上通過引入CDL，使得該算法能夠處理海量數(shù)據(jù)。

算法1.1 基于屬性重要性的離散化算法

算法輸入：一個(gè)完備的決策表信息系統(tǒng)DT

算法輸出：離散化后的決策表信息系統(tǒng)DT

算法步驟如下：

（1） 循環(huán)遍歷每一個(gè)連續(xù)的條件屬性，并且通過生成[ICDLai]計(jì)算屬性[ai]的條件信息熵。

（2） 根據(jù)條件信息熵降序排序，排列所有連續(xù)的條件屬性。

（3） 針對(duì)排序后的DT，循環(huán)遍歷每一個(gè)連續(xù)的條件屬性[ai，]生成[ICDLC＼ai；]設(shè)置[Szone=null，]其中[Szone]是屬性[ai]的值域的一個(gè)子集。

（4） 循環(huán)遍歷區(qū)間[Sa，Sb]上的每一個(gè)斷點(diǎn)。其中[Sa]和[Sb]是屬性[ai]上兩個(gè)連續(xù)的屬性值；令[Szone=Szone+Sa。]

（5） 循環(huán)遍歷DT中滿足[SVjai=Sh]的每個(gè)樣本[SVj，]其中[Sh∈Szone。]

（6） 循環(huán)遍歷DT中滿足[SVkai=Sb]的每個(gè)樣本[SVk；]如果樣本[SVj]和[SVk]出現(xiàn)在[ICDLai]中的同一個(gè)條件分類中而且它們之間存在符號(hào)“@”，則選擇[Sa，Sb]的斷點(diǎn)，并把 [Szone]重新置為空。

1.2 改進(jìn)的屬性約簡(jiǎn)算法

使用基于信息熵的CEBARKNC算法。根據(jù)類分布鏈表求取條件信息熵的方法[8]，通過某個(gè)條件屬性組合的ICDL很容易求得決策屬性相對(duì)于該條件屬性組合的條件信息熵。因此可以通過ICDL改進(jìn)CEBARKNC算法的可伸縮性，改進(jìn)的算法與原算法在計(jì)算信息熵的過程不一樣。

1.3 改進(jìn)的值約簡(jiǎn)算法

在此改進(jìn)啟發(fā)式值約簡(jiǎn)算法，該算法在原算法的基礎(chǔ)上加上CDL，使得該算法能夠處理海量數(shù)據(jù)。原算法在執(zhí)行第一步的時(shí)候按照[CDL（a）]中的三部分更新決策表S。

（1） 把[SSCDL（a）]中的樣本在屬性[a]上的值標(biāo)記為“？”；

（2） 把[MSCDL（a）]中的樣本在屬性[a]上的值標(biāo)記為“*”；

（3） [ICDL（a）]中的樣本在屬性[a]上的值不變。

由（3）可知[ICDL（a）]中的樣本不需要處理，而在處理[SSCDL（a）]和[MSCDL（a）]的樣本時(shí)，不把生成實(shí)際的鏈表放在內(nèi)存中處理而是直接在數(shù)據(jù)庫(kù)中進(jìn)行處理。具體的算法描述如下：

算法1.2 改進(jìn)啟發(fā)式值約簡(jiǎn)算法

輸入：一個(gè)完備的離散的決策表信息系統(tǒng)DT

輸出：規(guī)則集RT

假設(shè)樣本標(biāo)號(hào)為Index，決策屬性為DA，條件屬性集合[C，]則算法步驟如下：

（1） 把RT初始化為DT。

（2） 循環(huán)遍歷每一個(gè)條件屬性[ai，]把[SSCDL（ai）]中的所有樣本在[ai]上的屬性值標(biāo)記為“？”。

（3） 把[MSCDL（ai）]中的所有樣本在[ai]上的屬性值標(biāo)記為“*”。此外剩下的樣本都在[ICDL（ai）]中，它們?cè)赱ai]上的屬性值不需要改變。

（4） 接下的操作步驟與原始的值約簡(jiǎn)算法相同。

2 基于動(dòng)態(tài)聚類的兩步離散化算法的并行化

基于動(dòng)態(tài)聚類的兩步離散化算法的第一步是利用動(dòng)態(tài)聚類算法對(duì)決策表第一次進(jìn)行離散化，然后利用斷點(diǎn)重要性離散化算法進(jìn)行再次離散化，從而得到最終的斷點(diǎn)集。

算法2.1 基于動(dòng)態(tài)聚類的離散化算法

輸入：決策表[S=]

輸出：決策表[S]首次篩選后的斷點(diǎn)集[CUTfirst]循環(huán)遍歷[S]的每一個(gè)條件屬性[k，]執(zhí)行以下步驟：

（1） 計(jì)算屬性[k]每一斷點(diǎn)的重要性，并按斷點(diǎn)值從小到大排序，計(jì)算結(jié)果保存在數(shù)組[Importantk[]]中，數(shù)組的索引[m]表示最重要的斷點(diǎn)在數(shù)組中的位置，即：

決策表經(jīng)過上述的算法離散化之后，其效果僅相當(dāng)于基于屬性重要性離散化算法的局部離散化效果。下面通過把斷點(diǎn)集[CUTfirst]輸入到斷點(diǎn)重要性算法中進(jìn)行一次全局離散化便得到基于動(dòng)態(tài)聚類的兩步離散化算法。

算法2.3對(duì)算法2.2進(jìn)行了并行化處理，得到的離散化結(jié)果與算法2.2是一致的，但算法2.3帶來的好處是提高了離散化算法的運(yùn)行效率。

3 算法測(cè)試

3.1 改進(jìn)的Rough Set知識(shí)約簡(jiǎn)算法測(cè)試

3.1.1 算法正確性測(cè)試

選擇UCI數(shù)據(jù)庫(kù)中的5個(gè)數(shù)據(jù)集（見表1）來比較經(jīng)過CDL改進(jìn)的知識(shí)約簡(jiǎn)算法與原始經(jīng)典Rough Set算法的正確性，雙方都應(yīng)用了相同的算法組合。比較的結(jié)果見表2，從結(jié)果中可得出：使用經(jīng)過CDL改造后的知識(shí)約簡(jiǎn)算法不影響原始的經(jīng)典Rough Set算法的正確率及識(shí)別率等性能。

3.2 基于動(dòng)態(tài)聚類的兩步離散化算法的并行化處理算法測(cè)試

從UCI數(shù)據(jù)庫(kù)中選取6組數(shù)據(jù)集對(duì)算法2.2進(jìn)行測(cè)試。表3是實(shí)驗(yàn)使用的數(shù)據(jù)集。表4，表5展示了基于動(dòng)態(tài)聚類的離散化算法、基于動(dòng)態(tài)聚類的兩步離散化算法、貪心算法、基于斷點(diǎn)重要性的離散化算法等5種算法的運(yùn)算對(duì)比結(jié)果。其中，算法的運(yùn)行時(shí)間用符號(hào)[T]表示，規(guī)則集的正確識(shí)別率用符號(hào)[P]表示。

4 結(jié) 論

從目前常用的數(shù)據(jù)挖掘算法出發(fā)，采用類分布鏈表來改進(jìn)傳統(tǒng)的數(shù)據(jù)挖掘算法，使該算法能直接處理海量數(shù)據(jù)集，實(shí)現(xiàn)處理超大規(guī)模數(shù)據(jù)集的目標(biāo)。系統(tǒng)采用并行計(jì)算的核心思想，基于動(dòng)態(tài)聚類的并行離散化算法，提出分布確定類分布鏈表的方法，有效解決了系統(tǒng)內(nèi)存限制的問題。同時(shí)，提高了基于動(dòng)態(tài)聚類的兩步離散化算法的運(yùn)行效率。

參考文獻(xiàn)

[1] 黃朝輝.基于變精度粗糙集的數(shù)據(jù)挖掘方法研究[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2014（8）：3?4.

[2] 要照華，閆宏印.基于粗糙集的海量數(shù)據(jù)挖掘[J].機(jī)械管理開發(fā)，2010，25（1）：17?18.

[3] 石凱.基于粗糙集理論的屬性約簡(jiǎn)與決策樹分類算法研究[D].大連：大連海事大學(xué)，2014：22?25.

[4] 劉華元，袁琴琴，王保保.并行數(shù)據(jù)挖掘算法綜述[J].電子科技，2006（1）：65?68.

[5] 陳貞，邢笑雪.粗糙集連續(xù)屬性離散化的K均值方法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2015（5）：642?646.

[6] CORNELIS C， KRYSZKIEWICZ M， SLEZAK D， et al. Rough sets and current trends in soft computing [M]. Berlin： Springer， 2014： 11?15.

[7] 劉建.并行程序設(shè)計(jì)方法學(xué)[M].武漢：華中科技大學(xué)出版社，2000：11?13.

[8] 陳小燕.機(jī)器學(xué)習(xí)算法在數(shù)據(jù)挖掘中的應(yīng)用[J].現(xiàn)代電子技術(shù)，2015，38（20）：11?14.