高級大數據人才培養叢書之一，大數據挖掘技術與應用DATAMINING數據挖掘第七章常用大數據挖掘算法優化改進of572高級大數據人才培養叢書之一，大數據挖掘技術與應用

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

習題of573高級大數據人才培養叢書之一，大數據挖掘技術與應用1.并行算法簡介7.1.1分類算法的并行化of5747.1分類算法第7章常用大數據挖掘算法優化改進

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

所謂分類，簡單來說，就是根據數據的特征或屬性，劃分到已有的類別中。2.并行算法的常規研究內容1）并行計算模型

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

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

2）并行算法的設計技術

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

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

1）并行計算

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

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

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

2）并行算法

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

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

4.共享內存of5787.1分類算法第7章常用大數據挖掘算法優化改進

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

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

關于決策樹算法的并行訓練策略主要有以下兩種實現方式。根據數據劃分方式的不同可以分為動態數據劃分和靜態數據劃分；根據程序設計模式的不同可以分為主從模式和對等模式。

1）數據劃分方式

（1）動態數據劃分法。

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

（2）靜態數據劃分法。

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

①橫向劃分方式。

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

②縱向劃分方式。

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

（1）主從模式。

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

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

（2）對等模式。

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

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

對于經典的C4.5算法，基于MapReduce的并行算法，在構造決策樹時，分裂指標的計算方法相同，所以邏輯上若數據集相同，它們構造的決策樹應該相同，只是MapReduce是一并行計算框架，數據集較大時，執行效率高，而經典的決策樹算法對大數據卻無能為力。

基于Hadoop平臺的C4.5算法是為了解決傳統的C4.5算法不能處理大規模數據的問題。

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

針對樸素貝葉斯分類方法要求數據集獨立性假設的問題，應用統計量分布的方法給出一種

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

2.算法設計

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

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

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

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

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

2）級聯式并行支持向量機（CascadePSVM）

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

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

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

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

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

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

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

分類算法7.3關聯規則

習題of5718高級大數據人才培養叢書之一，大數據挖掘技術與應用1.目前聚類分析研究的主要內容7.2.1聚類分析研究的主要內容及算法應用of57197.2聚類算法第7章常用大數據挖掘算法優化改進

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

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

聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小。20of57207.2聚類算法第7章常用大數據挖掘算法優化改進

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

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

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

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

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

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

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

并行計算體系結構主要有以下四種：

1）集群（Cluster）

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

2）對稱多處理（SMP）

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

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

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

4）大規模并行處理（MPP）

它是目前并行計算機發展過程的主要方向，大規模并行處理可在上萬臺機器上進行并行處理，并可應用多種并行計算框架和文件存儲系統等。of57247.2聚類算法第7章常用大數據挖掘算法優化改進2.并行聚類算法體系結構和模型

1）并行算法的基本體系結構

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

2）并行計算模型

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

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

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

4.改進算法的基本流程

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

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

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

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

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

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

1）構建相似矩陣

首先要對原始數據進行處理、構建文本向量，在構建文本向量時要計算每個詞在文本中出現的次數，這就要利用TF-IDF算法。

2）并行計算對角矩陣

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

3）并行化計算Laplacian矩陣

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

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

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

5）并行k-means算法

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

分類算法7.2

聚類算法

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

關聯規則是形如X→Y的蘊涵式,其中，X和Y分別稱為關聯規則的先導和后繼關聯規則XY，存在支持度和信任度。2.基于Hadoop平臺的Apriori并行化算法改進of57407.3關聯規則第7章常用大數據挖掘算法優化改進

1）Apriori算法并行化

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

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

3）算法并行化分析

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

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

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

（2）使用reduceByKey累計項目數。

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

（1）LK自連接，產生CK+1。

（2）掃描數據庫，比對CK+1（采用步驟1的方法），產生LK+1。右圖為分布式Apriori算法的實現流程圖。2.并行Apriori算法核心步驟of57437.3關聯規則第7章常用大數據挖掘算法優化改進

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

步驟2：頻繁1項集L1自連接產生C1，掃描數據庫比對C1，產生fim2，保存。

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

當處理大規模數據集時，FP-Growth算法的缺點是不能構建基于內存的全局Fp-tree，并且算法遞歸挖掘條件Fp-tree的時間消耗較大。為了解決算法在時間和空間上的局限性，通常利用“數據分解”的思想來設計并行FP-Growth算法。

數據分解的基本思想是分而治之。對于任意的原始數據集D，當D的大小比可用內存容量M小時，則采用某種基于內存的關聯規則算法來挖掘關聯規則。當D的大小超過內存時，則采用某種分解策略將D分解為k個子數據集D1，D2，…,Dk,然后對每一個Dk遞歸調用數據分解算法。

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

并行化算法分為2個階段：①并行化統計頻繁1項集列表。②并行化挖掘局部Fp-tree上的關聯規則。

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

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

2）關聯規則的并行化方法

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

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

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