試論一種基于粗糙集的海量數(shù)據(jù)挖掘算法

中國(guó)計(jì)量大學(xué)信息工程學(xué)院 蔡叢豫

引言：就傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)來說，其在數(shù)據(jù)量級(jí)方面存在著一定的局限性，影響最終的效果，所以將粗糙集理論應(yīng)用其中。對(duì)此，本文以算法的優(yōu)化為切入點(diǎn)，對(duì)一種基于粗糙集的海量數(shù)據(jù)挖掘算法進(jìn)行分析。結(jié)合本文的分析，其目的就是優(yōu)化海量數(shù)據(jù)挖掘算法，并以全新的并行算法等為基礎(chǔ)，提高海量數(shù)據(jù)挖掘的效率，以期為相關(guān)人員提供參考。

1.基于粗糙集對(duì)Rough Set知識(shí)約簡(jiǎn)算法的改進(jìn)

1.1 離散化算法

在Rough Set知識(shí)獲取方法中，數(shù)據(jù)離散化是其關(guān)鍵的構(gòu)成內(nèi)容之一，本文就采用屬性重要性的方式，將CDL引入到原算法之中，保證這種算法能夠?qū)崿F(xiàn)對(duì)海量數(shù)據(jù)的挖掘。具體來說，這種算法的具體步驟為：

（1）對(duì)每一個(gè)連續(xù)的條件屬性，進(jìn)行循環(huán)遍歷，同時(shí)能夠生成條件信息熵，即ICDL（{ai}）的信息熵。

（2）結(jié)合條件信息，對(duì)信息熵以降序的方式進(jìn)行排序，即將所有連續(xù)的屬性均進(jìn)行排列。

（3）對(duì)于完成排序的DT，并每個(gè)條件的ai進(jìn)行循環(huán)遍歷，從而能夠形成ICDL（C{ai}）。在這一條件下，可以將Szone設(shè)置為null，而Szone實(shí)際上是ai值域的子集。

（4）對(duì)（Sa，Sb）區(qū)間的額每一個(gè)斷點(diǎn)，進(jìn)行循環(huán)遍歷，而Sa、Sb是ai的連續(xù)屬性值，并設(shè)Szone的值為Szone與Sa的和。

（5）對(duì)DT中所有滿足條件SVj（ai）=Sh的樣本，進(jìn)行循環(huán)遍歷，即SVj，而其中的Sh=屬于Szone。

（6）對(duì)DT中所有滿足條件SVj（ai）=Sb的樣本，進(jìn)行循環(huán)遍歷，即SVk，如果樣本SVk、SVj屬于ICDL（{ai}）的同一分類中，并且使用@的符號(hào)進(jìn)行連接，在需要將（Sa，Sb）的斷點(diǎn)選擇出來，并對(duì)Szone進(jìn)行重置（空）。

1.2 值約簡(jiǎn)算法

基于粗糙集理論，能夠?qū)χ导s簡(jiǎn)算法進(jìn)行改進(jìn)，以此來實(shí)現(xiàn)對(duì)海量的挖掘，保證數(shù)據(jù)分析結(jié)果的穩(wěn)定性。具體來說，值約簡(jiǎn)算法的具體步驟如下：

（1）輸入一個(gè)完備的信息系統(tǒng)DT，最終輸出的結(jié)果為規(guī)則集RT。假設(shè)Index為樣本標(biāo)號(hào)，DA表示決策屬性，C則為條件屬性的集合，然后進(jìn)行以下的計(jì)算步驟。

（2）對(duì)RT進(jìn)行初始化，使其轉(zhuǎn)化為DT。

（3）對(duì)所有的條件屬性ai進(jìn)行循環(huán)遍歷，并將SSCDL（ai）中的所有樣本，均以“？”的符號(hào)標(biāo)記在ai之上。

（4）對(duì)MSCDL（ai）中的所有樣本ai，均以“*”進(jìn)行屬性值的標(biāo)記。另外，在MSCDL（ai）中剩余的樣本，其ai的屬性值并不需要進(jìn)行改變。

（5）在后續(xù)的計(jì)算步驟，只需要按照傳統(tǒng)的值約簡(jiǎn)算法進(jìn)行即可。

2.基于粗糙集的兩步離散化算法并行化

2.1 離散化算法

實(shí)際上，本文所提及的離散化算法，其是以動(dòng)態(tài)聚類為基礎(chǔ)的。對(duì)于這種算法的具體步驟，本文將做出如下的分析：

（1）輸入決策表，即S=＜U，同時(shí)R=C∪D，還包括V、F＞。輸出的結(jié)果為：對(duì)S進(jìn)行篩選而形成具體的斷點(diǎn)集，即CUTfirst，以此來對(duì)S中的每一個(gè)屬性k進(jìn)行遍歷，然后進(jìn)行如下的計(jì)算。

（2）對(duì)k斷點(diǎn)的重要性進(jìn)行計(jì)算、分析，并按照由小到大的順序進(jìn)行排序。然后，在數(shù)組Importantk[]中對(duì)計(jì)算結(jié)果進(jìn)行保存，數(shù)組的索引m表示斷點(diǎn)最為重要的位置。具體來說，Importantk[m]=max{Importantk[i],i∈并設(shè)l等于0，n等于|h-l+1|，而h等于m。

（3）采用歸一化的方式對(duì)數(shù)據(jù)進(jìn)行處理，并對(duì)Importantk[]進(jìn)行循環(huán)遍歷，最終得出：Importantk[i]=Importantk[i]/Importantk[m]。

（5）對(duì)聚類的個(gè)別數(shù)進(jìn)行初始化，并對(duì)變量v=e+1進(jìn)行循環(huán)控制。

（6）如果v的數(shù)值大于e，則應(yīng)該進(jìn)行以下的循環(huán)：1）建立中心表T，定在Importantk中對(duì)l～h的范圍進(jìn)行隨機(jī)選擇K個(gè)中心；2）對(duì)e1=0的循環(huán)變量進(jìn)行設(shè)定；3）如果e1不等于v時(shí)，其所執(zhí)行的循環(huán)為：e1等于v，應(yīng)對(duì)Importantk中數(shù)值距離、數(shù)值類別進(jìn)行統(tǒng)計(jì)，然后將其與距離最小的類別進(jìn)行同類處理，并對(duì)聚類中心的數(shù)值進(jìn)行調(diào)整，明確T中各類標(biāo)準(zhǔn)差的數(shù)值，并使v等于

（8）在每一個(gè)聚類類別中，選擇最重要的斷點(diǎn)，添加至CUT-ifrst之中?；谶@樣的方式，就能夠基于粗糙集理論實(shí)現(xiàn)對(duì)離散化算法的優(yōu)化，以便于對(duì)海量數(shù)據(jù)進(jìn)行挖掘與計(jì)算。

2.2 并行離散化算法

依據(jù)粗糙集理論，可以在動(dòng)態(tài)聚類的基礎(chǔ)上，實(shí)現(xiàn)兩步并行理算化算法，其具體的計(jì)算步驟為：

（1）輸入S=＜U，同時(shí)R=C∪D，還包括V、F＞。輸出的結(jié)果為：決策表S中的斷點(diǎn)集，即CUTlast，然后進(jìn)行如下的計(jì)算。

（2）在沒有進(jìn)行離散化的基礎(chǔ)上，對(duì)決策表中區(qū)域的POSc（D）進(jìn)行詳細(xì)的計(jì)算[2]。

（3）在散播屬性的階段，可以在主進(jìn)程中設(shè)置證其能夠滿足條件條件屬性的全集，并將S1分配給P1……。并保

（4）在進(jìn)行并行處理的過程中，假設(shè)進(jìn)程為Pi，則可以通過兩步離散化算法進(jìn)行處理，實(shí)現(xiàn)對(duì)斷點(diǎn)的聚類，并將其發(fā)送至CUTfirst中。

（6）在并行離散化算法的過程中，實(shí)際上需要對(duì)斷點(diǎn)補(bǔ)充進(jìn)行修正，這一階段的具體方式，與兩步離散化算法相同。

（7）在斷點(diǎn)散播階段之中，其中的斷點(diǎn)集可以由各個(gè)進(jìn)程L進(jìn)行表示，將以等價(jià)類的方式對(duì)集合進(jìn)行實(shí)例劃分，即CUTlast為空集，而L則等于{U}。在計(jì)算的過程中，可以設(shè)置滿足條件另外還包括條

（8）在對(duì)數(shù)據(jù)進(jìn)行并行處理的階段，可以根據(jù)斷點(diǎn)的重要性，進(jìn)行選擇與發(fā)送。

（9）在斷點(diǎn)的歸約階段之中，其主進(jìn)程應(yīng)該接受所有的結(jié)果[3]。

（10）對(duì)各個(gè)進(jìn)程的CUTlast進(jìn)行更新。

（11）依據(jù)X∈L的條件，對(duì)相關(guān)的數(shù)據(jù)進(jìn)行處理，最終將其中的X取掉。

（12）如果L中的實(shí)例并沒有形成相同的決策，在需要從步驟（3）進(jìn)行重復(fù)，反之則可以結(jié)束算法。

結(jié)語：綜上所述，為了能夠?qū)崿F(xiàn)對(duì)海量數(shù)據(jù)的挖掘，就應(yīng)該打破傳統(tǒng)算法的限制。在本文的分析中，對(duì)于算法的改進(jìn)，其創(chuàng)新點(diǎn)在于以粗糙集為基礎(chǔ)，結(jié)合傳統(tǒng)算法實(shí)現(xiàn)了對(duì)海量數(shù)據(jù)挖掘算法的優(yōu)化，而本文的研究能夠在一定程度上為豐富文獻(xiàn)類的類型做出貢獻(xiàn)，基于這一條件，提高了數(shù)據(jù)算法的簡(jiǎn)便性，并實(shí)現(xiàn)了對(duì)數(shù)據(jù)深入挖掘的目標(biāo)，發(fā)揮了基于粗糙集的海量數(shù)據(jù)挖掘算法的價(jià)值。通過這樣的優(yōu)化方式，在根本上強(qiáng)化了數(shù)據(jù)挖掘算法的準(zhǔn)確性，在未來的發(fā)展中，很可能會(huì)應(yīng)用在各個(gè)行業(yè)的大數(shù)據(jù)分析中，為其制定決策、戰(zhàn)略提供有價(jià)值的數(shù)據(jù)依據(jù)。另外，所以，結(jié)合本文的分析發(fā)現(xiàn)，文中所論述的一種基于粗糙集的海量數(shù)據(jù)挖掘算法，其具有較強(qiáng)的可行性。