動(dòng)態(tài)云模型大規(guī)模數(shù)據(jù)挖掘算法

黃取治

（福建師范大學(xué)信息技術(shù)學(xué)院，福建福州 350007）

0 引 言

云計(jì)算的發(fā)展為互聯(lián)網(wǎng)的發(fā)展提供了新的機(jī)遇，它有效地降低了企業(yè)在IT設(shè)備上的成本投入，提高了企業(yè)的工作效率。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中找到需要、有用數(shù)據(jù)中有的過(guò)程。數(shù)據(jù)挖掘從統(tǒng)計(jì)學(xué)上可以認(rèn)為，是通過(guò)計(jì)算機(jī)對(duì)大量的復(fù)雜數(shù)據(jù)集的自動(dòng)分析。數(shù)據(jù)挖掘是為了確定數(shù)據(jù)的模式，它需要對(duì)觀察到的數(shù)據(jù)庫(kù)進(jìn)行處理。數(shù)據(jù)挖掘涉及對(duì)數(shù)據(jù)庫(kù)管理、人工智能、模式識(shí)別以及數(shù)據(jù)可視化等內(nèi)容。

1 云計(jì)算和數(shù)據(jù)挖掘簡(jiǎn)介

云計(jì)算是一種新的計(jì)算模型，它可以將計(jì)算任務(wù)用分布式技術(shù)通過(guò)大量互連的計(jì)算機(jī)協(xié)同工作，從而得到需要的計(jì)算資源和其它服務(wù)信息。云計(jì)算為互聯(lián)網(wǎng)時(shí)代海量數(shù)據(jù)的處理和分析提供了高效的平臺(tái)。云計(jì)算可以將海量數(shù)據(jù)分解為同樣大小的信息并且進(jìn)行分布存儲(chǔ)，然后利用MapReduce等模型進(jìn)行編程，這種技術(shù)已經(jīng)在搜索引擎中得到了廣泛的應(yīng)用并且取得了良好的效果［1］。用云計(jì)算的方式來(lái)進(jìn)行數(shù)據(jù)挖掘，主要是由于數(shù)據(jù)挖掘所面臨的數(shù)據(jù)是海量的，在云技術(shù)出現(xiàn)以前都希望由高性能機(jī)或者是大規(guī)模的計(jì)算設(shè)備來(lái)完成，但是計(jì)算機(jī)服務(wù)器的功能總是有限的。同時(shí)，在海量數(shù)據(jù)的挖掘中還有比較特殊的要求，這對(duì)數(shù)據(jù)挖掘的開(kāi)發(fā)環(huán)境和應(yīng)用環(huán)境提出了新的要求，而云計(jì)算的方式能夠有效滿足數(shù)據(jù)挖掘的特殊需要。

數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中挖掘出有用的信息，來(lái)滿足人們的特定需要。有專家預(yù)測(cè)隨著互聯(lián)網(wǎng)時(shí)代數(shù)據(jù)的不斷積累和計(jì)算機(jī)的普及，數(shù)據(jù)挖掘?qū)⒃谖覈?guó)形成一個(gè)新的高科技產(chǎn)業(yè)。數(shù)據(jù)挖掘使數(shù)據(jù)庫(kù)技術(shù)進(jìn)入到了一個(gè)新的發(fā)展階段，它不僅能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)的查詢，而且能夠找到數(shù)據(jù)之間的聯(lián)系，從而促進(jìn)信息的應(yīng)用和傳遞。數(shù)據(jù)挖掘能夠?qū)崿F(xiàn)真正的按需服務(wù)，用戶可以根據(jù)自己的需求選擇相應(yīng)的服務(wù)模式?；谠朴?jì)算的數(shù)據(jù)挖掘計(jì)算的一般過(guò)程如圖1所示。

圖1 云計(jì)算數(shù)據(jù)挖掘計(jì)算過(guò)程

2 云計(jì)算和數(shù)據(jù)挖掘之間的關(guān)系分析

云計(jì)算是一種基于互聯(lián)網(wǎng)的的計(jì)算模式，其計(jì)算過(guò)程、計(jì)算能力、交互能力等功能是一個(gè)動(dòng)態(tài)、虛擬化的過(guò)程［2］。云計(jì)算的動(dòng)態(tài)和可伸縮的計(jì)算能力為數(shù)據(jù)挖掘技術(shù)的實(shí)現(xiàn)帶來(lái)了可能性，云計(jì)算環(huán)境為新的數(shù)據(jù)挖掘方法的研究提供了新的環(huán)境，云計(jì)算也使面向大眾的數(shù)據(jù)挖掘成為了可能。同時(shí)，云計(jì)算的發(fā)展也離不開(kāi)數(shù)據(jù)挖掘的支持，在基于云計(jì)算的搜索中就包含了網(wǎng)頁(yè)存儲(chǔ)、搜索處理等內(nèi)容。數(shù)據(jù)挖掘在搜索服務(wù)中具有廣泛應(yīng)用，在網(wǎng)頁(yè)存儲(chǔ)中網(wǎng)頁(yè)去重、搜索處理中網(wǎng)頁(yè)排序等，其中每項(xiàng)服務(wù)的實(shí)現(xiàn)都需要數(shù)據(jù)挖掘技術(shù)來(lái)提供支持［3］。

新型的數(shù)據(jù)挖掘技術(shù)包括了面向異構(gòu)數(shù)據(jù)、同構(gòu)數(shù)據(jù)和跨域數(shù)據(jù)等不同的數(shù)據(jù)挖掘方法，在同構(gòu)海量數(shù)據(jù)挖掘方法中，節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)都具有同樣的屬性。云計(jì)算平臺(tái)采用集成學(xué)習(xí)的方式來(lái)完成預(yù)測(cè)分析，并且在同構(gòu)節(jié)點(diǎn)的基礎(chǔ)上實(shí)現(xiàn)了數(shù)據(jù)挖掘的增量學(xué)習(xí)方法，從而滿足了實(shí)時(shí)性的要求。在異構(gòu)數(shù)據(jù)挖掘技術(shù)中，云計(jì)算平臺(tái)能夠根據(jù)數(shù)據(jù)的模態(tài)將數(shù)據(jù)進(jìn)行分類，并提供數(shù)據(jù)相關(guān)性度量和集成。同時(shí)數(shù)據(jù)挖掘技術(shù)還存在特殊性的應(yīng)用，而云計(jì)算平臺(tái)能夠?yàn)楹Ａ繑?shù)據(jù)的遷移挖掘提供方法上的支持，這不僅擴(kuò)大了云計(jì)算環(huán)境下數(shù)據(jù)挖掘應(yīng)用的范圍，同時(shí)也更好地滿足了數(shù)據(jù)挖掘用戶的需要。

3 數(shù)據(jù)挖掘算法研究

樹(shù)型機(jī)構(gòu)是一種非線性的結(jié)構(gòu)，在數(shù)據(jù)庫(kù)的信息組織中得到了廣泛的應(yīng)用。1986年，Quinlan提出了數(shù)據(jù)網(wǎng)挖掘的ID3算法，然后Quinlan在ID3算法的基礎(chǔ)上又提出了C4.5算法。同時(shí)為了滿足海量數(shù)據(jù)處理的需要，又提出了一系列的改進(jìn)的算法，其中SLIQ和SPRINT是比較有代表性的兩個(gè)算法［4］。

ID3算法是一種分類預(yù)測(cè)算法，其核心是信息熵，信息上是一種數(shù)據(jù)所包含的信息。一組無(wú)序數(shù)據(jù)的信息熵越高，那么其熵也就越大。分類預(yù)測(cè)法可以對(duì)目標(biāo)數(shù)據(jù)進(jìn)行分級(jí)處理，具體表現(xiàn)在構(gòu)建決策樹(shù)的過(guò)程中。通過(guò)生成決策樹(shù)并且按照相應(yīng)的規(guī)則來(lái)判斷數(shù)據(jù)。ID3算法用信息增益作為屬性的選擇標(biāo)準(zhǔn)，ID3算法在工作中需要檢測(cè)所有數(shù)據(jù)的屬性，然后將信息增益最大的屬性來(lái)作為決策樹(shù)的結(jié)點(diǎn)。信息增益作為判斷屬性的標(biāo)準(zhǔn)，通過(guò)計(jì)算每個(gè)屬性的信息增益，然后比較它們的大小，就能夠得到最大信息增益的屬性?？梢约僭O(shè)S是包含了s個(gè)數(shù)據(jù)樣本的集合，其中類標(biāo)號(hào)屬性有m個(gè)不同值，定義為m個(gè)不同類Ci（i＝1，2，…，m），其中假設(shè)si是類Ci中的樣本數(shù)量。假設(shè)屬性A具有v個(gè)不同的值，其集合為｛a1，a2，…，av｝。用屬性A將S劃分為v個(gè)不同的子集｛S1，S2，…，Sv｝，其中Sj中的樣本表示在屬性A上具有同樣的值aj（j＝1，2，…，v），設(shè)sij是子集Sj中Ci的樣本數(shù)量。C4.5算法延續(xù)了ID3算法的優(yōu)點(diǎn)，并且對(duì)ID3算法進(jìn)行了優(yōu)化改進(jìn)。用信息增益率來(lái)選擇屬性，避免了利用信息增益過(guò)程中屬性不足的現(xiàn)象。在構(gòu)建樹(shù)的過(guò)程中進(jìn)行了剪枝處理，并且對(duì)連續(xù)屬性的離散化處理。C4.5算法具有獨(dú)特的優(yōu)點(diǎn)，其分類規(guī)則更容易被理解，而且準(zhǔn)確率也比較高。但是其缺點(diǎn)也比較明顯，需要對(duì)數(shù)據(jù)集進(jìn)行多次排序，因此在數(shù)據(jù)挖掘的過(guò)程中其算法的效率比較低。C4.5在一些駐留內(nèi)存的數(shù)據(jù)集中應(yīng)用比較廣泛，當(dāng)數(shù)據(jù)集在內(nèi)存無(wú)法容納時(shí)程序就難以有效地運(yùn)行［5］。

SLIQ算法對(duì)C4.5分類算法進(jìn)行了有效的改進(jìn)，在決策樹(shù)的構(gòu)造過(guò)程中采用了預(yù)排序和廣度優(yōu)先策略兩種技術(shù)來(lái)對(duì)數(shù)據(jù)的采集進(jìn)行優(yōu)化。在C4.5算法中預(yù)排序是在連續(xù)屬性內(nèi)部結(jié)點(diǎn)中尋找最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，對(duì)訓(xùn)練集按屬性值的大小進(jìn)行排序，而排序則需要一定的時(shí)間等待。為了提高數(shù)據(jù)采集的效率，SLIQ算法應(yīng)用了預(yù)排序技術(shù)。預(yù)排序是通過(guò)對(duì)每個(gè)屬性進(jìn)行取值，并且把所記錄的數(shù)據(jù)屬性值按照從小到大的順序進(jìn)行排序，從而避免在決策樹(shù)建立的過(guò)程中對(duì)每個(gè)結(jié)點(diǎn)數(shù)據(jù)集進(jìn)行排序而花費(fèi)大量額外的時(shí)間。在實(shí)際的操作時(shí)需要根據(jù)訓(xùn)練數(shù)據(jù)集的屬性來(lái)創(chuàng)建針對(duì)性的屬性列表，同時(shí)根據(jù)類別的屬性創(chuàng)建相應(yīng)的類別列表。在C4.5算法中樹(shù)的構(gòu)造是根據(jù)深度的優(yōu)先來(lái)進(jìn)行的，在具體的工作時(shí)需要對(duì)每個(gè)屬性列表的結(jié)點(diǎn)都進(jìn)行掃描，需要花費(fèi)大量的時(shí)間。為了提高數(shù)據(jù)挖掘的效率，SLIQ算法采用了廣度優(yōu)先的方法來(lái)構(gòu)建決策樹(shù)，在決策樹(shù)的每一層上只需要對(duì)屬性列表掃描一次就可以為決策樹(shù)中的每個(gè)結(jié)點(diǎn)找到最佳的分裂標(biāo)準(zhǔn)［6］。

Bayes法是一種在已知先驗(yàn)概率與類條件概率的情況下的模式分類方法，待分樣本的分類結(jié)果取決于各類域中樣本的全體。設(shè)訓(xùn)練樣本集分為M類，記為C＝｛c1，…，ci，…cM｝，每類的先驗(yàn)概率為P（ci），i＝1，2，…，M。當(dāng)樣本集非常大時(shí)，可以認(rèn)為P（ci）＝ci類樣本數(shù)／總樣本數(shù)。對(duì)于一個(gè)待分樣本X，其歸于cj類的類條件概率是P（X／ci），則根據(jù)Bayes定理，可得到cj類的后驗(yàn)概率P（ci／X）：

若

則

式（2）是最大后驗(yàn)概率判決準(zhǔn)則，將式（1）代入式（2），則有，若

則

這就是常用到的Bayes分類判決準(zhǔn)則。經(jīng)過(guò)長(zhǎng)期的研究，Bayes分類方法在理論上論證得比較充分，在應(yīng)用上也是非常廣泛的。Bayes方法的薄弱環(huán)節(jié)在于實(shí)際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)（或密度函數(shù)）常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達(dá)文本的主題詞相互獨(dú)立，這樣的條件在實(shí)際文本中一般很難滿足，因此，該方法往往在效果上難以達(dá)到理論上的最大值。

為了減少內(nèi)存中的數(shù)據(jù)量，SPRINT算法又對(duì)決策樹(shù)中的算法數(shù)據(jù)結(jié)構(gòu)進(jìn)行了進(jìn)一步的改進(jìn)，SPRINT算法改變了SLIQ算法中保存在內(nèi)存中的類別列表，將類別列表合并到了屬性列表中。這樣在掃描屬性列表尋找結(jié)點(diǎn)的最佳分裂標(biāo)準(zhǔn)時(shí)，不需要參考其它的信息就可以將結(jié)點(diǎn)的分裂劃歸到屬性列表中進(jìn)行分裂，將每一個(gè)屬性列表分成兩個(gè)分別存放各個(gè)結(jié)點(diǎn)的記錄。SPRINT算法使尋找每個(gè)結(jié)點(diǎn)的最佳分裂標(biāo)準(zhǔn)變得更簡(jiǎn)單，但是也存在著對(duì)非分裂屬性列表進(jìn)行分裂時(shí)比較困難［7］。為了改變這種缺點(diǎn)，在對(duì)分裂屬性進(jìn)行分裂時(shí)，可以用哈希表記錄屬于某個(gè)屬性的結(jié)點(diǎn)，如果內(nèi)存能夠容下整個(gè)哈希表，那么其它不同的屬性列表的分裂可以只參照哈希表。哈希表的大小和訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時(shí)，哈希表仍然可能完成保存在內(nèi)存中，這種情況下分裂只能進(jìn)行分批進(jìn)行，這說(shuō)明了SPRINT算法的可伸縮性仍然需要繼續(xù)改進(jìn)。

基于云計(jì)算的并行數(shù)據(jù)挖掘服務(wù)模式是將同一個(gè)算法分布到不同的多個(gè)節(jié)點(diǎn)上，這些算法在工作的過(guò)程中是并行的、互不干擾的，而且計(jì)算資源能夠進(jìn)行按需分配。分布式計(jì)算采用了云計(jì)算的模式，而數(shù)據(jù)挖掘的關(guān)鍵就是實(shí)現(xiàn)數(shù)據(jù)挖掘算法的并行化。云計(jì)算采用MapReduce等新的計(jì)算模型，所以現(xiàn)有的數(shù)據(jù)挖掘算法和并行化不能直接應(yīng)用到云計(jì)算平臺(tái)上，它需要經(jīng)過(guò)一系列的改造才能滿足數(shù)據(jù)挖掘的要求。因此在云計(jì)算的模式下，需要研究數(shù)據(jù)挖掘算法的并行化策略，從而實(shí)現(xiàn)云計(jì)算平臺(tái)下的并行數(shù)據(jù)挖掘算法。并行數(shù)據(jù)挖掘算法包括并行分類算法和并行聚類算法等，能夠進(jìn)行數(shù)據(jù)分類或者預(yù)測(cè)，以及數(shù)據(jù)總結(jié)、聚類、異常和趨勢(shì)發(fā)現(xiàn)等。通過(guò)借助并行處理技術(shù)，在基于數(shù)據(jù)挖掘算法的特點(diǎn)上對(duì)云計(jì)算模型進(jìn)行優(yōu)化，使其能夠更加滿足數(shù)據(jù)挖掘的需要。分布式計(jì)算是解決數(shù)據(jù)挖掘任務(wù)的需要，它能夠有效地提高數(shù)據(jù)挖掘的效率。分布式數(shù)據(jù)挖掘技術(shù)主要有基于網(wǎng)格的分布式數(shù)據(jù)挖掘、基于云的分布式數(shù)據(jù)挖掘等，同時(shí)數(shù)據(jù)挖掘一個(gè)核心問(wèn)題是實(shí)現(xiàn)數(shù)據(jù)挖掘算法的并行化［8］。

在利用云計(jì)算進(jìn)行數(shù)據(jù)挖掘時(shí)需要選擇恰當(dāng)?shù)乃惴?，不是所有的算法都能夠滿足數(shù)據(jù)挖掘的策略。通過(guò)選擇合適的算法，并且應(yīng)用相應(yīng)的并行辦法才能有效地提高數(shù)據(jù)挖掘的效率。在數(shù)據(jù)挖掘中存在著很多不確定性，所以在應(yīng)用數(shù)據(jù)挖掘算法的過(guò)程中，應(yīng)當(dāng)注意不確定性所帶來(lái)的消極影響。數(shù)據(jù)挖掘任務(wù)存在著比較大的不確定性，數(shù)據(jù)的預(yù)處理和采集也存在非常多的不確定性，數(shù)據(jù)挖掘方法和結(jié)果也存在比較大的不確定性，所以要快速找到需要的數(shù)據(jù)信息［9］。在利用云計(jì)算進(jìn)行數(shù)據(jù)挖掘時(shí)還需要對(duì)評(píng)價(jià)的結(jié)果進(jìn)行評(píng)價(jià)，用戶的需求不同評(píng)價(jià)的目標(biāo)也不同，所以導(dǎo)致了對(duì)挖掘結(jié)果評(píng)價(jià)的不確定性。同時(shí)在云計(jì)算環(huán)境下進(jìn)行數(shù)據(jù)挖掘，對(duì)于云服務(wù)軟件的可信度也比較重要，例如其服務(wù)是否正確或者恰當(dāng)，對(duì)隱私數(shù)據(jù)的保護(hù)等，都是數(shù)據(jù)挖掘所關(guān)注的內(nèi)容。數(shù)據(jù)挖掘的算法和模型應(yīng)當(dāng)保持一致性，這樣才能保證數(shù)據(jù)挖掘結(jié)果的正確性。

4 結(jié) 語(yǔ)

通過(guò)云計(jì)算的海量數(shù)據(jù)存儲(chǔ)和分布計(jì)算，為云計(jì)算環(huán)境下的數(shù)據(jù)挖掘提供了新方法和手段，有效解決了海量數(shù)據(jù)挖掘的分布存儲(chǔ)和高效計(jì)算問(wèn)題。通過(guò)開(kāi)展基于云計(jì)算特點(diǎn)的數(shù)據(jù)挖掘算法的研究，可以為更多、更復(fù)雜的數(shù)據(jù)挖掘提供新的應(yīng)用平臺(tái)。通過(guò)云計(jì)算滿足了數(shù)據(jù)挖掘的個(gè)性化和多樣性的需要，同時(shí)由于數(shù)據(jù)的多樣性，如高維的、動(dòng)態(tài)的數(shù)據(jù)，都需要云計(jì)算技術(shù)來(lái)實(shí)現(xiàn)。

［1］ 郭鑫，顏一鳴，徐洪智，等.動(dòng)態(tài)云平臺(tái)下的快速閉樹(shù)聚類并行算法［J］.計(jì)算機(jī)工程，2013（9）：80-83.

［2］ 郭鑫，李云，黃云，等.最小閉樹(shù)特征集的聚類與分類方法［J］.計(jì)算機(jī)應(yīng)用，2010，30（2）：423-426，448.

［3］ 郭鑫，顏一鳴.一種動(dòng)態(tài)云模型下樹(shù)數(shù)據(jù)挖掘算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34（12）：2749-2752.

［4］ 宋晶.基于云模型和粗糙集的分類挖掘方法研究［D］：［碩士學(xué)位論文］.成都：西南交通大學(xué)，2007.

［5］ 遲慶云.基于決策樹(shù)的分類算法研究和應(yīng)用［D］：［碩士學(xué)位論文］.濟(jì)南：山東師范大學(xué)，2005.

［6］ 黃華.基于大云數(shù)據(jù)快速挖掘過(guò)程的研究與仿真［J］.計(jì)算機(jī)仿真，2013，30（4）：386-389.

［7］ 宛婉，周?chē)?guó)祥.基于并行抽樣的海量數(shù)據(jù)關(guān)聯(lián)挖掘算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（8）：933-937.

［8］ 程苗.基于云計(jì)算的用戶瀏覽偏愛(ài)路徑挖掘算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（29）：85-89.

［9］ 陳湘濤，張超，韓茜.基于Hadoop的并行共享決策樹(shù)挖掘算法研究［J］.計(jì)算機(jī)科學(xué)，2013，47（11）：258-259.