基于粗糙集的海量數(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ù)量處理帶來(lái)的效率問(wèn)題。

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

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

0 引 言

信息時(shí)代，數(shù)據(jù)（尤其是海量數(shù)據(jù)）已被各企業(yè)、各研究機(jī)構(gòu)當(dāng)成重大的知識(shí)來(lái)源、決策的重要依據(jù)[1]，對(duì)數(shù)據(jù)的急速增長(zhǎng)，如何有效地解決數(shù)據(jù)挖掘過(guò)程中空間和時(shí)間的可伸縮性已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中迫切需要解決的難題[2]。從知識(shí)發(fā)現(xiàn)的過(guò)程中可以看到，數(shù)據(jù)挖掘不僅面臨著數(shù)據(jù)庫(kù)中的龐大數(shù)據(jù)問(wèn)題[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è)問(wèn)題[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)算法都可以通過(guò)引進(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ù)集。以下通過(guò)引入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ǔ)上通過(guò)引入CDL，使得該算法能夠處理海量數(shù)據(jù)。

3 算法測(cè)試

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

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

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

3.1.2 可伸縮性測(cè)試

當(dāng)訓(xùn)練集的大小從10萬(wàn)條逐漸增加到100萬(wàn)條時(shí)，測(cè)試集的記錄數(shù)是訓(xùn)練集的30%。生成海量數(shù)據(jù)集，數(shù)據(jù)集有8個(gè)條件屬性和一個(gè)決策屬性。圖1顯示了正確率以及識(shí)別率的變化情況，圖2顯示了知識(shí)獲取所用的時(shí)間變化情況。在數(shù)據(jù)集的量級(jí)增大時(shí)，傳統(tǒng)的Rough Set方法已經(jīng)不能適用。

從圖1和圖2可以看出，新改進(jìn)的算法可以提高原算法的可伸縮性，使得能夠適應(yīng)更大的數(shù)據(jù)集，而且性能很好，不失正確率及識(shí)別率。至于知識(shí)發(fā)現(xiàn)所花的時(shí)間比較長(zhǎng)，與測(cè)試平臺(tái)所用的SQL服務(wù)器效率有關(guān)，利用并行算法則可以提高處理的速度。

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]表示。

使用基于動(dòng)態(tài)聚類的離散化算法進(jìn)行了動(dòng)態(tài)聚類之后，如表6所示，從SONA，PIMA，IRIS等可以看出，每個(gè)數(shù)據(jù)集的候選斷點(diǎn)數(shù)目都有了明顯的降低?；趧?dòng)態(tài)聚類的兩步離散化算法的運(yùn)行速度效率更快，針對(duì)正確識(shí)別率、屬性重要性等方面，貪心算法、基于斷點(diǎn)重要性的離散化算法與基于動(dòng)態(tài)聚類的兩步離散化算法保持一致。

4 結(jié) 論

基于目前常用的數(shù)據(jù)挖掘算法，采用了類分布鏈表來(lái)改進(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)存限制的問(wèn)題。同時(shí)，提高了基于動(dòng)態(tài)聚類的兩步離散化算法的運(yùn)行效率。

參考文獻(xiàn)

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

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

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

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

[5] 陳貞，邢笑雪.粗糙集連續(xù)屬性離散化的k均值方法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），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.