高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用DATAMINING數(shù)據(jù)挖掘第七章常用大數(shù)據(jù)挖掘算法優(yōu)化改進of572高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用

隨著“信息爆炸”時代的來臨，數(shù)據(jù)挖掘的應(yīng)用日趨廣泛。許多商業(yè)決策者利用數(shù)據(jù)挖掘技術(shù)從海量的數(shù)據(jù)中獲取有用的信息，為以后企業(yè)更好地決策提供幫助。然而，傳統(tǒng)的數(shù)據(jù)挖掘算法在面對海量數(shù)據(jù)的時候，由于各種原因，執(zhí)行效率低下，已經(jīng)不能夠滿足人們?nèi)找嬖鲩L的性能需求，需要尋找更加高效的算法或者執(zhí)行策略。為了解決這一系列效率低下的問題，本章對常用大數(shù)據(jù)挖掘算法進行優(yōu)化和改進，并將改進后的算法應(yīng)用到具體的實例中。More7.1分類算法第七章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.2聚類算法7.3關(guān)聯(lián)規(guī)則

習(xí)題of573高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用1.并行算法簡介7.1.1分類算法的并行化of5747.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

簡單的說，算法就是求解問題的方法和步驟。并行算法，就是在并行機上用很多個處理器聯(lián)合求解問題的方法和步驟。

所謂分類，簡單來說，就是根據(jù)數(shù)據(jù)的特征或?qū)傩裕瑒澐值揭延械念悇e中。2.并行算法的常規(guī)研究內(nèi)容1）并行計算模型

并行計算模型的第一代是共享存儲模型，如SIMD-SM和MIMD-SM的一些計算模型，模型參數(shù)主要是CPU的單位計算時間。第二代是分布存儲模型。在這個階段，人們逐漸意識到對并行計算機性能帶來影響的不僅僅是CPU，還有通信。第三代是分布共享存儲模型。of5757.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

簡單的說，算法就是求解問題的方法和步驟。并行算法，就是在并行機上用很多個處理器聯(lián)合求解問題的方法和步驟。

2）并行算法的設(shè)計技術(shù)

雖然并行算法研究還不是太成熟，但并行算法的設(shè)計依然是有章可循的，例如劃分法、分治法、平衡樹法、倍增法等都是常用的設(shè)計并行算法的方法。另外人們還可以根據(jù)問題的特性來選擇適合的設(shè)計方法。3）并行算法分為多機并行和多線程并行

多機并行，如MPI技術(shù)；多線程并行，如OpenMP技術(shù)。of5767.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

1）并行計算

從處理器的角度看，并行計算可劃分為時間并行和空間并行，時間并行即流水線技術(shù)，空間并行則是使用多個處理器同時計算。從算法設(shè)計的角度來看，并行計算可分為數(shù)據(jù)并行和任務(wù)并行。

從體系結(jié)構(gòu)來說，空間并行導(dǎo)致兩類并行機的產(chǎn)生：單指令流多數(shù)據(jù)流（SIMD）和多指令流多數(shù)據(jù)流（MIMD）。MIMD類的機器又可分為常見的五類：并行矢量處理機（PVP）、對稱多處理機（SMP）、大規(guī)模并行處理機（MPP）、工作站集群（COW）和分布式共享存儲處理機（DSM）。

從訪存模型來說，并行計算有以下5種訪存模型：均勻訪存模型（UMA）、非均勻訪存模型（NUMA）、全高速緩存訪存模型（COMA）、一致性高速緩存非均勻存儲訪問模型（CC-NUMA）和非遠程存儲訪問模型（NORMA）。

2）并行算法

并行算法是用多臺處理機聯(lián)合求解問題的方法和步驟，其執(zhí)行過程是將給定問題先分解成若干個盡量相互獨立的子問題，然后使用多臺計算機同時進行求解，從而最終求得原問題的解。3.并行計算和并行算法of5777.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

共享內(nèi)存技術(shù)是指開辟一塊特殊內(nèi)存區(qū)域，使得多個進程可以共享這塊內(nèi)存進行讀寫操作。一旦進程將共享內(nèi)存區(qū)映射到它的地址空間，這些進程間數(shù)據(jù)的傳遞就不再涉及內(nèi)核，有利于進程間交換大批量數(shù)據(jù)。

4.共享內(nèi)存of5787.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

共享內(nèi)存系統(tǒng)的應(yīng)用程序開發(fā)有多進程和多線程兩種方式。多進程程序中的各進程管理各自的計算資源，進程間的數(shù)據(jù)共享通過消息方式數(shù)據(jù)傳遞實現(xiàn)；而多線程程序中的各線程可以分享主進程程序分配的所有計算資源，直接共享程序中的數(shù)據(jù)，如下圖所示。of5797.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進MapReduce本身就是一個并行計算框架，但是任務(wù)可以在MapReduce框架下并行計算的前提是，任務(wù)所對應(yīng)的數(shù)據(jù)集可分，且分割后的各子數(shù)據(jù)集可以并行地被計算，它們之間并沒有依存關(guān)系，最終只需要合并它們各自產(chǎn)生的結(jié)果為最終結(jié)果。

在MapReduce框架下，一個任務(wù)通常會被分為兩個階段：Map階段和Reduce階段，且所有的操作都是基于<key，value>鍵值對的。下圖為MapReduce任務(wù)工作過程。5.MapReduce并行計算框架of57107.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.1.2并行化的決策樹算法優(yōu)化1.決策樹算法的并行策略

關(guān)于決策樹算法的并行訓(xùn)練策略主要有以下兩種實現(xiàn)方式。根據(jù)數(shù)據(jù)劃分方式的不同可以分為動態(tài)數(shù)據(jù)劃分和靜態(tài)數(shù)據(jù)劃分；根據(jù)程序設(shè)計模式的不同可以分為主從模式和對等模式。

1）數(shù)據(jù)劃分方式

（1）動態(tài)數(shù)據(jù)劃分法。

動態(tài)數(shù)據(jù)劃分方式就是根據(jù)任務(wù)進行分片。在構(gòu)建決策樹之前，主處理機上存儲著整個訓(xùn)練數(shù)據(jù)集。假設(shè)當(dāng)前系統(tǒng)中有可供運行的n臺處理機，則要將訓(xùn)練數(shù)據(jù)集劃分為n個訓(xùn)練子集，主處理機將劃分好的n個訓(xùn)練子集分配給包含自己在內(nèi)的n臺處理機。這n臺處理機接收到訓(xùn)練子集后，并行地構(gòu)建決策樹的子樹。主處理機重復(fù)上面的過程，為完成任務(wù)的處理機分配訓(xùn)練集直至所有的處理機都得到任務(wù)。of57117.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

（2）靜態(tài)數(shù)據(jù)劃分法。

為了解決動態(tài)數(shù)據(jù)方式需要各處理機之間大量通信和頻繁數(shù)據(jù)移動的缺點，給出了靜態(tài)數(shù)據(jù)劃分方式。靜態(tài)數(shù)據(jù)劃分方式又可以分為橫向數(shù)據(jù)劃分和縱向數(shù)據(jù)劃分。

①橫向劃分方式。

橫向數(shù)據(jù)劃分方式是指將訓(xùn)練數(shù)據(jù)集進行水平分割，各個處理機保存的訓(xùn)練數(shù)據(jù)子集的大小一樣。假設(shè)訓(xùn)練數(shù)據(jù)集為N，處理機的個數(shù)為m，則每個處理機處理的數(shù)據(jù)集大小為N/m。每個處理機按照同樣的擴展策略負責(zé)統(tǒng)計本地數(shù)據(jù)，獲取并計算每個屬性分裂點相關(guān)的信息，各個處理機之間需要互相通信，按照算法所采用的最佳屬性測試標(biāo)準(zhǔn)，找出最佳屬性和分裂點。在劃分數(shù)據(jù)集到各子節(jié)點的過程中，各處理機只對本機數(shù)據(jù)進行劃分。

②縱向劃分方式。

縱向劃分就是將一個或若干個完整的屬性列表分配給一個單獨的處理機進行處理，每個處理機并行地完成一個或者多個屬性分裂點相關(guān)信息的計算過程。of57127.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2）程序設(shè)計模式

（1）主從模式。

基于主從模式的并行決策樹方法中選擇一個處理機運行主進程，其余處理機運行從進程。各從進程之間不相互通信，也不要求進行同步。

在主從模式下，主處理機先將訓(xùn)練數(shù)據(jù)集橫向劃分后平均分配到N個從處理機上，各從處理機接收數(shù)據(jù)后并行統(tǒng)計和計算各分裂點的信息；然后，各從處理機把結(jié)果信息傳送給主處理機，主處理機綜合各從處理機的結(jié)果信息，得出最佳分裂屬性；最后，主處理機根據(jù)最佳分裂屬性的分裂結(jié)果形成哈希表后發(fā)送到各從處理機上，從處理機再根據(jù)哈希表分割本機上的數(shù)據(jù)子集。

（2）對等模式。

在對等模式下，系統(tǒng)中所有處理機都是對等的，沒有主從之分，處理器之間通過相互通信完成決策樹的創(chuàng)建。13of57137.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.決策樹中C4.5算法并行化

對于C4.5決策樹分類算法，如果給定數(shù)據(jù)集和屬性集，在構(gòu)造樹的過程中需要計算所有剩余屬性各自對應(yīng)的分裂指標(biāo)值，此過程就需要對數(shù)據(jù)集進行劃分，耗時最長，此時可以利用MapReduce并行框架，可大大縮短時間。根據(jù)劃分結(jié)果，分別計算各屬性對應(yīng)的分裂指標(biāo)值，從中找出最佳的分裂屬性，以此屬性為節(jié)點，再根據(jù)此屬性的取值，進行分枝，遞歸地進行即可得到一顆完整的決策樹。

對于經(jīng)典的C4.5算法，基于MapReduce的并行算法，在構(gòu)造決策樹時，分裂指標(biāo)的計算方法相同，所以邏輯上若數(shù)據(jù)集相同，它們構(gòu)造的決策樹應(yīng)該相同，只是MapReduce是一并行計算框架，數(shù)據(jù)集較大時，執(zhí)行效率高，而經(jīng)典的決策樹算法對大數(shù)據(jù)卻無能為力。

基于Hadoop平臺的C4.5算法是為了解決傳統(tǒng)的C4.5算法不能處理大規(guī)模數(shù)據(jù)的問題。

C4.5算法的并行化實現(xiàn)方法見《數(shù)據(jù)挖掘》一書的第157頁。of57147.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.1.3一種新的樸素貝葉斯改進方法

針對樸素貝葉斯分類方法要求數(shù)據(jù)集獨立性假設(shè)的問題，應(yīng)用統(tǒng)計量分布的方法給出一種

分布加權(quán)的貝葉斯分類改進方法，有效地改進了卡方獨立性假設(shè)對樸素貝葉斯方法獨立性假設(shè)難以廣泛適用的情況。1.屬性間的相關(guān)關(guān)系見《數(shù)據(jù)挖掘》一書的第159頁。

2.算法設(shè)計

設(shè)分類表T具有n個條件屬性和m個決策屬性，分別用隨機變量Xi(i=1,2,…,n)和Y表示，則在加權(quán)樸素貝葉斯算法分類模型中權(quán)值表示為：

公式中wi就作為分類表中第i個條件屬性的權(quán)值系數(shù)。基于權(quán)值系數(shù)的改進樸素貝葉斯算法的實現(xiàn)關(guān)鍵在于求解各條件屬性與決策屬性之間的相關(guān)系數(shù)。其算法的具體描述步驟見《數(shù)據(jù)挖掘》一書的第159頁。of57157.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.1.4支持向量機并行優(yōu)化改進

常見的并行支持向量機設(shè)計模式主要有分組式、級聯(lián)式、反饋式和混合式4種。

1）分組式并行支持向量機（GroupedPSVM）

設(shè)計思路是：將原始訓(xùn)練集TD按照一定原則切分成n個子訓(xùn)練樣本集，每個子訓(xùn)練樣本集中均勻分布著各類樣本，之后利用Map操作在集群各節(jié)點上并行訓(xùn)練這n個子訓(xùn)練樣本集，訓(xùn)練結(jié)果為n個子支持向量集，最后采用Reduce簡單地合并n個子支持向量集，從而得到全局最優(yōu)支持向量集。

2）級聯(lián)式并行支持向量機（CascadePSVM）

同樣采用數(shù)據(jù)分割的思想，通過并行處理樣本子集節(jié)省大量時間，對子樣本集的合并并非像分組式那樣全部合并，而是兩兩合并子集按照分而治之的原則進行再次訓(xùn)練，直至最終得到全局支持向量模型。將原始訓(xùn)練集TD按照一定原則切分成n個子訓(xùn)練樣本集（n為偶數(shù)，且n>=2），SV為訓(xùn)練子樣本集所得的支持向量。1.并行支持向量機發(fā)展of57167.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

3）反饋式并行支持向量機（FeedbackPSVM）

在CascadePSVM的基礎(chǔ)上引入反饋，即將最后一步得到的全局支持向量反饋到初始數(shù)據(jù)子集中進行再次訓(xùn)練，從而避免不合理的數(shù)據(jù)劃分對分類模型性能產(chǎn)生的潛在影響，該策略以迭代的方式進行，通過判斷迭代停止條件來終止迭代，從而提高訓(xùn)練精度。

4）混合式并行支持向量機（HybridPSVM）

常見的混合式并行SVM是分組式和級聯(lián)式并行SVM的某種組合，該模型先將原始訓(xùn)練樣本集分成n個子集，分別對這些子集進行訓(xùn)練生成各子集的支持向量，這一步與分組式SVM一樣。之后根據(jù)預(yù)設(shè)值k，將這些支持向量合并到k個子集，再次并行訓(xùn)練后得到最終結(jié)果，k個子集中，每個子集含有n/k個原始訓(xùn)練樣本子集，這一步并非像分組SVM整體合并，也不像級聯(lián)SVM兩兩合并，而是選取適合的子集數(shù)進行合并。最后合并這些支持向量，得到最終的SVM分類模型。of57177.1分類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

反饋式并行支持向量機就是將原始訓(xùn)練數(shù)據(jù)集分塊，通過并行訓(xùn)練子樣本集加速全局支持向量的訓(xùn)練速度，為消除初始數(shù)據(jù)集劃分對分類器性能和訓(xùn)練結(jié)果的潛在影響，特地引入迭代反饋機制，通過反饋，將本次迭代的結(jié)果返回初始分類器進行調(diào)整和更新，從而進一步提高分類準(zhǔn)確率。

設(shè)計和實現(xiàn)基于MapReduce編程框架的反饋式并行支持向量機時，需要格外重視數(shù)據(jù)集的劃分和如何迭代這兩個問題。右圖給出了FeedBackSVM的流程圖。2.反饋式并行支持向量機算法實現(xiàn)7.2聚類算法第七章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.1

分類算法7.3關(guān)聯(lián)規(guī)則

習(xí)題of5718高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用1.目前聚類分析研究的主要內(nèi)容7.2.1聚類分析研究的主要內(nèi)容及算法應(yīng)用of57197.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

（1）從對傳統(tǒng)的聚類分析方法所做的總結(jié)來看，不管是k-means方法，還是CURE方法，在進行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目。然而在現(xiàn)實數(shù)據(jù)中，聚類的數(shù)目是未知的，通常要經(jīng)過不斷的實驗來獲得合適的聚類數(shù)目，得到較好的聚類結(jié)果。

（2）傳統(tǒng)的聚類方法一般都是適合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類。因此如何解決這個問題成為當(dāng)前的一個研究熱點，有學(xué)者提出將不同的聚類思想進行融合以形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點，在一次聚類過程中綜合利用多種聚類方法，能夠有效地緩解這個問題。

聚類就是對大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個類別，使類別內(nèi)的數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相似度較小。20of57207.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

（3）隨著信息時代的到來，對大量的數(shù)據(jù)進行分析處理是一個很龐大的工作，這就關(guān)系到一個計算效率的問題。有文獻提出了一種基于最小生成樹的聚類算法，該算法通過逐漸丟棄最長的邊來實現(xiàn)聚類結(jié)果，當(dāng)某條邊的長度超過了某個閾值，那么更長邊就不需要計算而直接丟棄，這樣就極大地提高了計算效率，降低了計算成本。

（4）處理大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的能力有待于提高。目前許多聚類方法處理小規(guī)模數(shù)據(jù)和低維數(shù)據(jù)時性能比較好，但是當(dāng)數(shù)據(jù)規(guī)模增大，維度升高時，性能就會急劇下降，而現(xiàn)實生活中的數(shù)據(jù)大部分又都屬于規(guī)模比較大、維度比較高的數(shù)據(jù)集。有文獻提出了一種在高維空間挖掘映射聚類的方法PCKA，它從多個維度中選擇屬性相關(guān)的維度，去除不相關(guān)的維度，沿著相關(guān)維度進行聚類，以此對高維數(shù)據(jù)進行聚類。

（5）目前的許多算法都只是理論上的，經(jīng)常處于某種假設(shè)之下，比如聚類能很好地被分離，沒有突出的孤立點等，但是現(xiàn)實數(shù)據(jù)通常是很復(fù)雜的，噪聲很大，因此如何有效地消除噪聲的影響，提高處理現(xiàn)實數(shù)據(jù)的能力還有待進一步提高。of57217.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.聚類算法的應(yīng)用

聚類主要應(yīng)用于模式識別中的語音識別、字符識別等，機器學(xué)習(xí)中的聚類算法應(yīng)用于圖像分割和機器視覺，圖像處理中聚類用于數(shù)據(jù)壓縮和信息檢索。聚類的另一個主要應(yīng)用是數(shù)據(jù)挖掘（多關(guān)系數(shù)據(jù)挖掘）、時空數(shù)據(jù)庫應(yīng)用（GIS等）、序列和異類數(shù)據(jù)分析等，聚類分析對生物學(xué)、心理學(xué)、考古學(xué)、地質(zhì)學(xué)、地理學(xué)以及市場營銷等研究也都有重要作用。of57227.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

典型的聚類過程主要包括數(shù)據(jù)（或稱之為樣本或模式）準(zhǔn)備、特征選擇、特征提取、接近度計算和聚類（或分組）、對聚類結(jié)果進行有效性評估等步驟。

典型的聚類過程步驟如下：

1.數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降維。2.特征選擇：從最初的特征中選擇最有效的特征，并將其存儲于向量中。3.特征提取：通過對所選擇的特征進行轉(zhuǎn)換形成新的突出特征。4.聚類（或分組）：首先選擇合適特征類型的某種距離函數(shù)（或構(gòu)造新的距離函數(shù)）進行接近程度的度量；而后執(zhí)行聚類或分組。5.聚類結(jié)果評估：是指對聚類結(jié)果進行評估。評估主要有3種：外部有效性評估、內(nèi)部有效性評估和相關(guān)性測試評估。of57237.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進1.并行聚類相關(guān)技術(shù)7.2.2并行聚類相關(guān)技術(shù)及算法體系結(jié)構(gòu)和模型

并行計算體系結(jié)構(gòu)主要有以下四種：

1）集群（Cluster）

具有免費、穩(wěn)定、開源的Unix和Linux操作系統(tǒng)的計算機集群系統(tǒng)，已成為當(dāng)下最流行的高性能計算平臺，在高性能計算方式中占有越來越大的比重。

2）對稱多處理（SMP）

由高速緩存Cache、處理單元、總線、交叉開頭、共享內(nèi)存以及輸入/輸出等組成。

3）分布式共享存儲多處理（DSM）

它能夠很好改善SMP的可擴展能力，當(dāng)前主流的高性能計算機很多都采用這種方式。

4）大規(guī)模并行處理（MPP）

它是目前并行計算機發(fā)展過程的主要方向，大規(guī)模并行處理可在上萬臺機器上進行并行處理，并可應(yīng)用多種并行計算框架和文件存儲系統(tǒng)等。of57247.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.并行聚類算法體系結(jié)構(gòu)和模型

1）并行算法的基本體系結(jié)構(gòu)

相對于串行計算來說，如果按照劃分方式來分，并行計算可以劃分為時間上的并行和空間上的并行。空間上的并行主要是利用多個處理器并發(fā)計算執(zhí)行的，目前主要的研究工作是空間上的并行，而時間上的并行又叫作流水線技術(shù)。從程序和算法設(shè)計人員的角度看，并行計算按邏輯又可分為數(shù)據(jù)并行和任務(wù)并行，數(shù)據(jù)并行的方法就是將大的數(shù)據(jù)任務(wù)分割成若干個子任務(wù)；任務(wù)并行和數(shù)據(jù)并行相似，就是將大的任務(wù)分割成若個子任務(wù)，這種方式要比數(shù)據(jù)并行復(fù)雜一些。

2）并行計算模型

并行計算模型現(xiàn)在沒有一個統(tǒng)一的模型，目前計算采用的都是馮·諾伊曼的串行模型，這種模型一直用到今天，其他并行模型沒有馮·諾伊曼式模型這么成熟和應(yīng)用廣泛。of57257.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進1.k-means聚類算法的局限性7.2.3k-means聚類算法的一種改進方法k-means聚類算法使用了迭代的方式，后來被稱為勞埃德算法。無論是在隨機或使用其他一些啟發(fā)式數(shù)據(jù)時，勞埃德算法首先將輸入點劃分成初始值集。然后計算出每個集合的平均點或重心。它通過關(guān)聯(lián)每一個點構(gòu)造一個新的分區(qū)。然后再重新計算出新的集群點，并通過交替應(yīng)用這兩個步驟的算法程序，直到收斂，這是獲得當(dāng)前點不再開關(guān)集群，利用coresets原始數(shù)據(jù)相類似的一種算法設(shè)計。

在性能方面的算法并不保證返回全局最優(yōu)。該算法的結(jié)果質(zhì)量在很大程度上依賴于初始集合的數(shù)據(jù)集，并且在實踐中比全局最優(yōu)要差得多。由于算法的速度非常快，一個常用的方法是運行算法幾次迭代并返回最好的解到集群中去。k-means算法的一個缺點是：數(shù)據(jù)集的k數(shù)目是一個輸入?yún)?shù)。如果選擇不適合的k值，可能會產(chǎn)生糟糕的結(jié)果。該算法還假定了方差集群分散的適當(dāng)措施。

聚類一直以來都是研究最廣泛的學(xué)科之一。現(xiàn)在基于劃分數(shù)據(jù)的聚類算法已經(jīng)成為數(shù)據(jù)挖掘和k-means聚類算法的熱點研究對象。然而k-means聚類算法也有很多的不足之處。of57267.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.算法流程描述k-means聚類算法的主要流程描述步驟見下表。of57277.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進3.改進算法的主要思想

4.改進算法的基本流程

改進算法的基本流程步驟見《數(shù)據(jù)挖掘》一書的第166頁。

如果第一類n存在于任何樣品中，具有大的第i級中心取得的抽樣小于最大歐幾里德距離的點，那么第一類和第i類就可以組合起來。實踐證明，通過基于改變初始聚類中心的k-means聚類算法比隨機選取k-means算法初始聚類中心的聚類結(jié)果質(zhì)量要好得多。of57287.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.2.4基于Spark的k-means算法并行化設(shè)計與實現(xiàn)Spark與Hadoop之間最大相異之處為Spark對所有類簇中心點的全部迭代計算基本都是于內(nèi)存中計算完成的，當(dāng)數(shù)據(jù)處理量遠小于節(jié)點的內(nèi)存容量時，計算過程中幾乎不需要再與磁盤進行I/O，而Hadoop則不行，基于Spark的k-means算法的并行實現(xiàn)流程如下圖所示。of57297.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.2.5基于Spark的k-means改進算法的并行化

為了提高k-means聚類算法對維度比較高的海量數(shù)據(jù)集的聚類效率，同時也解決k-means算法類簇初始中心點的選取和k值的選取問題，選取Canopy粗糙聚類算法來對基于Spark分布式框架的k-means并行算法進一步改進。通過Canopy算法優(yōu)化初始中心點和k值可以降低k-menas算法的迭代次數(shù)，從而改進k-means聚類算法在處理大數(shù)據(jù)集時數(shù)據(jù)挖掘的效率和實用性，也可以避免局部最優(yōu)解。1.Canopy算法思想概述Canopy算法適用于高維度的大數(shù)據(jù)集預(yù)聚類分析，它使用簡單粗糙的距離測量方法可以把數(shù)據(jù)對象集高效地分割為多個不完全重疊卻可以相交的子集Canopy，接著再在各個Canopy中執(zhí)行精細聚類算法，這樣粗細聚類的結(jié)合能提高海量數(shù)據(jù)處理的效率和準(zhǔn)確性。30of57307.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進Canopy算法聚類邏輯過程是這樣的，首先從數(shù)據(jù)對象點集中隨機地選擇一個數(shù)據(jù)對象點A作為第一個子集E1的聚類中心點，然后再根據(jù)其他數(shù)據(jù)對象點與A的相似度（一般以歐式距離作為相似度計算準(zhǔn)則），將一些數(shù)據(jù)對象點劃分到子集E1中；接著通過子集Canopies的創(chuàng)建，將數(shù)據(jù)對象集中的所有數(shù)據(jù)對象劃分到各個子集Canopy中，使這些Canopy子集必須完全包含全部數(shù)據(jù)對象。每個數(shù)據(jù)對象至少要屬于其中的任何一個Canopy子集，而且它還有可能同時屬于一個以上的Canopy子集。

由上述Canopy算法定義可知：任意兩個數(shù)據(jù)對象點如果沒有歸屬于同一個子集Canopy，那么這兩個數(shù)據(jù)對象點就一定不可能是同一類簇的數(shù)據(jù)對象。of57317.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.Canopy算法流程詳述

雖說Canopy算法可以不用如k-means算法那樣人為設(shè)置聚類的數(shù)目，但仍需要設(shè)置兩個相似性度量標(biāo)準(zhǔn)T1、T2來間接決定聚類后子集Canopy的數(shù)目和每個子集Canopy中數(shù)據(jù)對象點的數(shù)目，Canopy算法的詳細計算流程步驟見下表。of57327.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進3.基于Spark的Canopy_K-means（CKM）算法的并行化設(shè)計CKM算法主要由Canopy和k-means兩部分組成，基于Spark的并行化思路就是依據(jù)CKM算法的兩部分來執(zhí)行并行化設(shè)計。基于Spark的CKM并行算法與其串行邏輯大致相同，不同之處就在于CKM并行算法在使用DAG并行編程模型的同時也利用了Spark最具特色的RDD。CKM算法基于Spark平臺實現(xiàn)其并行化的流程步驟見下表。of57337.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.2.6基于MapReduce的聚類算法并行化1.基于MapReduce的k-means并行算法的設(shè)計k-means聚類算法進行MapReduce的基本思路：對串行算法中每1次迭代啟動對應(yīng)的1次MapReduce計算過程，完成數(shù)據(jù)記錄到聚類中心的距離計算以及新的聚類中心的計算。下圖描述了k-means聚類算法MapReduce并行化實現(xiàn)方法。of57347.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.Map函數(shù)的設(shè)計Map函數(shù)的任務(wù)是完成每個記錄到中心點距離的計算，并重新標(biāo)記其屬于的新聚類類別，其輸入為待聚類所有記錄數(shù)據(jù)和上一輪迭代（或初始聚類）的聚類中心，輸入數(shù)據(jù)記錄<Key，Value>對的形式為<行號，記錄行>。Reduce函數(shù)的任務(wù)是根據(jù)Map函數(shù)得到的中間結(jié)果計算出新的聚類中心，供下一輪MapReduce工作使用。

判斷該聚類是否已收斂：比較上一輪MapReduce工作得到的聚類中心與本輪MapReduce工作聚類中心距離，若變化小于給定閾值，則算法結(jié)束；反之，則用本輪的聚類中心文件替換上一輪的中心文件，并啟動新一輪的MapReduce工作。of57357.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.2.7譜聚類算法并行化方法1.譜聚類并行化設(shè)計下圖是譜聚類算法并行化的流程圖，從圖中可以看出第一部分是數(shù)據(jù)的輸入，輸入數(shù)據(jù)作為一個整體上傳至HDFS時進行分塊，將分好塊的數(shù)據(jù)交給Map進行處理，圖中第二部分是中間部分的處理。譜聚類并行化的MapReduce過程分為兩個階段，一部分是Map階段，另一個是Reduce階段。of57367.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進2.譜聚類并行化過程

1）構(gòu)建相似矩陣

首先要對原始數(shù)據(jù)進行處理、構(gòu)建文本向量，在構(gòu)建文本向量時要計算每個詞在文本中出現(xiàn)的次數(shù)，這就要利用TF-IDF算法。

2）并行計算對角矩陣

對角矩陣D計算方法很簡單，為上一步中求出的相似矩陣每一行相加，這是由對角矩陣的公式所決定的，計算得出的結(jié)果再按照相似矩陣的形式將數(shù)據(jù)放到相應(yīng)的對角位置上。

3）并行化計算Laplacian矩陣

這一步主要的工作是并行計算規(guī)范Laplacian矩陣，Laplacian矩陣有規(guī)范和非規(guī)范化之分，非規(guī)范化Laplacian矩陣表示為L=D-W，由非規(guī)范Laplacian矩陣可以推導(dǎo)出規(guī)范的Laplacian矩陣。37of57377.2聚類算法第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

4）并行計算特征向量及特征值

這一步主要計算Laplacian矩陣的最小特征值及特征向量，計算矩陣的最小特征值及特征向量有很多方法，

5）并行k-means算法

譜聚類的最后步驟是要選擇一個合適的聚類算法，對上幾步處理過的數(shù)據(jù)進行最后的聚類，在此選擇了k-means算法對數(shù)據(jù)進行最后的聚類。并行k-means算法的思想是將每個樣本分配給其選定的中心點，重復(fù)迭代，這個過程是可以在Hadoop平臺上并行執(zhí)行的，k-means算法并行化主要工作是Map階段設(shè)計、Combiner函數(shù)設(shè)計、Reduce函數(shù)設(shè)計。7.3關(guān)聯(lián)規(guī)則第七章常用大數(shù)據(jù)挖掘算法優(yōu)化改進7.1

分類算法7.2

聚類算法

習(xí)題of5738高級大數(shù)據(jù)人才培養(yǎng)叢書之一，大數(shù)據(jù)挖掘技術(shù)與應(yīng)用1.各種改進的Apriori算法7.3.1Apriori算法的一種改進方法of57397.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進(1)基于壓縮矩陣的方法是羅丹提出來的，改進的主要思路是，將數(shù)據(jù)壓縮存儲在0-1矩陣中，并用兩個額外的數(shù)組來分別記錄矩陣中各行各列中1的總數(shù)，減少了掃描矩陣的次數(shù)，并且能夠減少那些不能連接的項目集，提高了空間的利益率，增加了結(jié)果的準(zhǔn)確率。(2)基于劃分和壓縮矩陣的方法是由胡綠慧提出來的，主要是為了解決處理大規(guī)模數(shù)據(jù)時，效率比較低的問題。(3)基于Spark的方法是由牛海玲提出的，主要是為了使算法能夠并行化運行。改進的主要方面是利用Spark技術(shù)，將頻繁項集的計算引入到內(nèi)存中，并且利用矩陣存儲來減少數(shù)據(jù)庫的掃描，將局部剪枝和全局剪枝結(jié)合起來，減少候選項集的生成。

關(guān)聯(lián)規(guī)則是形如X→Y的蘊涵式,其中，X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)和后繼關(guān)聯(lián)規(guī)則XY，存在支持度和信任度。2.基于Hadoop平臺的Apriori并行化算法改進of57407.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

1）Apriori算法并行化

在生成頻繁項集的過程中，需要多次掃描事務(wù)數(shù)據(jù)庫，算法運行過程需要通過掃描數(shù)據(jù)庫得到每一個階次的候選項集合中元素的出現(xiàn)次數(shù)（即支持度計數(shù)），然后決定是要刪減還是要保留輸出。

2）算法改進方向Apriori算法總體來說思想簡單，就是通過不斷地迭代找出所有的項集，而且算法易于實現(xiàn)。在運算過程中，通過剪枝操作，在連接生成候選項集的過程中減少不必要項集的生成，從而減少了接下來工作的任務(wù)量。of57417.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

3）算法并行化分析

一般情況，每次在執(zhí)行一個MapReduce任務(wù)時，都有一個初始化的過程，這個過程所需要的時間基本上是一定的，每多一次MapReduce任務(wù)，就會多一次初始化時間消耗，所以在算法設(shè)計的過程中，應(yīng)該盡可能地減少MapReduce迭代次數(shù)。

Apriori算法的核心就是通過逐層的迭代，來生成1-k階頻繁項集。完全地將Apriori算法應(yīng)用到MapReduce之上，并不能適應(yīng)其框架特點，對于Apriori算法的并行化改進方法，提出了一種基于冪集的MapReduce改進算法，新的算法基于冪集定義，將每一個事務(wù)根據(jù)冪集思想進行拆分，將得到的所有子集追加到最初定義的集合中，通過不斷地追加計數(shù)，得到數(shù)據(jù)集中所有候選項集的支持度計數(shù)，這種算法的好處是，減少了數(shù)據(jù)集掃描次數(shù)，一次得到所有候選項集的同時也獲得了各項集對應(yīng)的支持度計數(shù)。這種改進方式在時間復(fù)雜度和空間復(fù)雜度上相對于串行算法有一定優(yōu)勢。4）POP-Apriori算法的實現(xiàn)流程見《數(shù)據(jù)挖掘》一書的第175頁。1.并行Apriori算法實現(xiàn)思路7.3.2Apriori算法基于Spark的分布式實現(xiàn)of57427.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進Apriori算法分布式實現(xiàn)使用Scala語言進行編程。結(jié)合Spark框架和其RDD算子進行綜合設(shè)計。算法的實現(xiàn)思路主要分為以下兩步：步驟1：產(chǎn)生頻繁1，項集L1。

（1）使用flatMap將事務(wù)集Ｔ以RDD<String，1>的形式分布到多個機器上。

（2）使用reduceByKey累計項目數(shù)。

（3）使用Filter過濾掉低于支持度的項集。步驟2：從頻繁k項集LK產(chǎn)生頻繁k+1項集LK+1。

（1）LK自連接，產(chǎn)生CK+1。

（2）掃描數(shù)據(jù)庫，比對CK+1（采用步驟1的方法），產(chǎn)生LK+1。右圖為分布式Apriori算法的實現(xiàn)流程圖。2.并行Apriori算法核心步驟of57437.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

步驟1：得到頻繁1項集L1并保存。

步驟2：頻繁1項集L1自連接產(chǎn)生C1，掃描數(shù)據(jù)庫比對C1，產(chǎn)生fim2，保存。

步驟3：循環(huán)產(chǎn)生3項集到8項集。mine函數(shù)主要包括L自連接和掃描DB過濾Ｃ。下圖為步驟2和步驟3的流程圖。1.并行化基本思想7.3.3并行FP-Growth關(guān)聯(lián)規(guī)則算法研究of57447.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

當(dāng)處理大規(guī)模數(shù)據(jù)集時，F(xiàn)P-Growth算法的缺點是不能構(gòu)建基于內(nèi)存的全局Fp-tree，并且算法遞歸挖掘條件Fp-tree的時間消耗較大。為了解決算法在時間和空間上的局限性，通常利用“數(shù)據(jù)分解”的思想來設(shè)計并行FP-Growth算法。

數(shù)據(jù)分解的基本思想是分而治之。對于任意的原始數(shù)據(jù)集D，當(dāng)D的大小比可用內(nèi)存容量M小時，則采用某種基于內(nèi)存的關(guān)聯(lián)規(guī)則算法來挖掘關(guān)聯(lián)規(guī)則。當(dāng)D的大小超過內(nèi)存時，則采用某種分解策略將D分解為k個子數(shù)據(jù)集D1，D2，…,Dk,然后對每一個Dk遞歸調(diào)用數(shù)據(jù)分解算法。

在上述分解算法中，最重要的是分解策略，它的目的是將大規(guī)模數(shù)據(jù)集劃分為一個個小規(guī)模的數(shù)據(jù)子集。這樣的劃分可以解決FP-Growth算法在時間和空間上的局限性。2.并行FP-Growth算法的設(shè)計of57457.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

并行化算法分為2個階段：①并行化統(tǒng)計頻繁1項集列表。②并行化挖掘局部Fp-tree上的關(guān)聯(lián)規(guī)則。

1）頻繁1項集的并行化方法

統(tǒng)計頻繁1項集的過程類似于計數(shù)統(tǒng)計，因此可以利用數(shù)據(jù)分解中的劃分策略進行數(shù)據(jù)集分解。每個處理節(jié)點需要對劃分到本地數(shù)據(jù)集中的數(shù)據(jù)項進行頻數(shù)的統(tǒng)計，得到局部的項集計數(shù)。然后各個節(jié)點之間通信得到每個項目的全局頻數(shù)，根據(jù)最小支持度閾值刪除非頻繁項集，從而得到頻繁1項集。將頻繁1項集廣播至各個子節(jié)點，保證每個子節(jié)點都保存了頻繁1項集列表。

2）關(guān)聯(lián)規(guī)則的并行化方法

從FP-Growth算法可知，在得到頻繁1項集列表之后，需要建立全局的Fp-tree才能獲得每個項目的條件模式基，當(dāng)數(shù)據(jù)集過大時全局Fp-tree無法放入內(nèi)存。因此，并行化的方法將數(shù)據(jù)集分解為子集之后，在數(shù)據(jù)子集上建立Fp-tree，這被稱為“局部Fp-tree”，然后針對局部Fp-tree調(diào)用FP-Growth方法遞歸挖掘局部的關(guān)聯(lián)規(guī)則。1.基于Spark的并行FP-Growth算法的設(shè)計思想7.3.4基于Spark的FP-Growth算法的并行化實現(xiàn)of57467.3關(guān)聯(lián)規(guī)則第7章常用大數(shù)據(jù)挖掘算法優(yōu)化改進

實現(xiàn)算法的并行化需要考慮任務(wù)的劃分與結(jié)果合并的問題。與Hadoop不同，Spark只需要對其彈性分布式數(shù)據(jù)集RDD調(diào)用相關(guān)的轉(zhuǎn)換或動作操作即可，它可以對同一數(shù)據(jù)集進行多次操作，更易于實現(xiàn)數(shù)據(jù)挖掘的并行化。因為FP-Growth算法是依靠消耗內(nèi)存來提高算法效率的，因此目前所實現(xiàn)的并行化算法大都會有內(nèi)存瓶頸，而Spark是一個基于內(nèi)存計算的分布式計算框架，采用多線程模型，更適合計算內(nèi)存密集型的任務(wù)。所以，可以結(jié)合Spark的優(yōu)勢，實現(xiàn)FP-Growth算法的并行化。

在Spark平臺上實現(xiàn)的FP-Growth算法的主要思路也分為5步。其算法步驟見《數(shù)據(jù)挖掘》一書的第180頁。2.