面向大數據的數據處理與分析算法綜述

周 宇，曹英楠，王永超

（南京航空航天大學計算機科學與技術學院/人工智能學院，南京 211106）

隨著多核CPU 性能、存儲設備性價比的迅速提升、網絡帶寬的不斷增加，以及移動互聯網、物聯網、云計算等新一代信息技術的迅速發展和快速普及，人類生產生活已和信息技術相互交融，全球數據量出現爆發式增長。海量集聚的數據中蘊含著前所未有的社會價值和商業價值，政府和企業可通過分析處理大規模的用戶數據得到傳統數據分析方式無法獲知的隱藏價值和模式，從而為公眾和客戶提供更加迅速、準確的公共服務及產品，大數據研究領域也因此吸引了社會各界的廣泛關注。

大數據［1］指的是利用傳統的數據處理分析技術或軟硬件工具無法在可容忍的時間范圍內對數據進行采集、處理和分析的數據集。其相較于傳統的數據集，擁有4V 特點［1］：規模性（Volume）、多樣性（Variety）、價值（Value）和實效性（Velocity）。根據挖掘任務的不同，數據挖掘處理方法可分為分類分析、聚類分析、關聯規則挖掘和序列分析等多種不同的方法。Blackett 將各處理方法進一步地按數據分析的程度劃分為3 類［2］：使用歷史數據進行總結的描述性分析、利用相關技術預測未來概率或趨勢的預測性分析、發現隱藏數據相關性以幫助用戶制定決策的規則性分析。聚類分析被用于描述數據，其通過衡量數據之間的相似性對數據進行分類；分類分析根據訓練數據獲得分類規則，故而常被用于預測分析；關聯規則挖掘目的在于從數據庫中發現并提取有價值的隱藏模式，且其思路同樣適用于序列模式發現。其中，分類屬于監督學習，聚類和關聯規則挖掘屬于無監督學習，這3 類方法作為常用機器學習算法，在學術界受到較多關注和研究，發展出了許多方法和理論，本文將按照分類、聚類和關聯規則挖掘依次對相關內容進行展開。

大數據的4V 特征及其影響意味著數據的高復雜度和高計算成本，故難以使用傳統數據挖掘方法來分析處理數據。在分類問題中，傳統的對靜態數據處理的方法已比較完善，但流式數據作為大數據的一個重要來源，傳統算法難以對流式數據處理中出現的概念漂移現象進行應對，故針對大數據中流式數據的分類算法比較關鍵。聚類和關聯規則挖掘方法最初便用于從各種應用的數據庫中發現隱藏的有價值信息，因此在大數據時代，相關算法也受到越來越多的關注，面對大數據處理的挑戰，關鍵在于如何通過并行傳統算法或是提出新的算法來應對。

1 面向大數據的流式數據分類算法

本文按照圖1 的思維框架圖，首先介紹流式數據的分類算法，分類作為一種監督學習方法［3］，其目的是通過訓練數據集中的實例以及實例所屬的類標簽發現分類規則，并使用該分類規則來預測未知實例所屬類標簽。分類過程有兩個階段：（1）分類規則學習階段，該階段通過分析、歸納訓練集中各實例類標簽情況，發現分類規則，創建合適的分類器模型；（2）測試集的分類階段，該階段需在驗證集上評估分類器模型的分類準確率，若準確度較好，則使用該分類器對測試集中實例進行預先分類，否則需重新訓練分類器模型。

1.1 流式數據特點

在大數據時代，流式數據作為大數據的一個重要來源［4?5］，大多源自日常生活中的簡單操作，例如網上購物數據、網絡社交信息以及web 應用程序生成的日志信息等。 其具有如下主要特性［6］：

（1）無限性。流式數據作為真實世界中的記錄，數據量是連續不斷、無限的。

（2）實時性。各類數據源產生的數據是實時的，不可預知的。

（3）時序性。數據按產生的時間先后順序按序到達。

（4）一次處理。因流式數據是實時且數據量無限，故流式數據中的數據通常只處理一次，在沒有特別保存的情況下，流式數據不能被再次處理。

（5）富含變化。流式數據隨時間不斷產生的過程中，其數據分布動態改變，即會出現概念漂移的現象［7］。

1.2 概念漂移及其處理技術

概念漂移指流式數據中數據分布隨時間發生變化，導致實例和實例所屬類標簽之間的分類規則發生改變。如圖2 所示，常見的概念漂移有如下幾種類型［8］：

圖2 概念漂移分布類型Fig.2 Conceptual drift distribution type

（1）突變漂移。概念在短時間發生巨大的變化且不可逆。

（2）漸變漂移。概念隨著時間逐漸的變化，且中間可能發生往復。

（3）增量漂移。概念隨著時間緩慢的不可逆的演變。

（4）重復漂移。是一種臨時性的改變，在短時間內會恢復成之前的狀態。

（5）罕見漂移。概念的異常改變。

（6）噪聲漂移。概念會由于數據中的噪聲隨機改變，但不是真正的概念漂移。

流式數據分類關注的是實例和所屬類標簽之間最新的分類規則，故相關算法應具備一定的遺忘能力，使得所學習的分類器模型與最新的概念相一致。當概念漂移發生時，常用的幾種概念漂移處理技術如下［7］：

（1）滑動窗口技術?；瑒哟翱谧鳛橐粋€緩沖區，在緩沖區內的數據實例能反映當前最新的數據分布狀況，且該窗口可以實時地對舊實例進行遺棄。當算法檢測到概念漂移時，縮小窗口范圍，否則適當地增加窗口大小，確保當前訓練數據與最新數據分布保持一致，從而確保分類模型的準確性。

（2）概念漂移檢測技術。通過統計量比如誤差、分錯率等來監視數據分布的變化，是與給定分類器相合作的外部算法。如漂移檢測法（Drift de?tection method，DDM）［9］使用統計量分類錯誤率和誤差標準差，設置警告和漂移閾值，該算法一旦檢測到數據分布開始變化并達到警告閾值，便向分類器模型發送警告信號，當達到漂移閾值時，表示概念漂移已經發生，需丟棄當前分類器重新學習，DDM 算法能有效檢測到突變漂移，但不擅長漸變漂移?；贖offding 邊界的在線漂移檢測方法［10］對DDM 算法進行了改進，其通過監控一系列性能指標的平均值，使用移動平均線和加權移動平均線，使得算法具備突變漂移和漸變漂移的檢測能力。

（3）集成學習技術［11］。將多個訓練好的基分類器通過某種規則（投票、加權等）組合成一個新的分類器，從而得到比基分類器更好的分類效果。每個基分類器的訓練數據不同，新的基分類器訓練最近到達的數據，并淘汰掉性能最差的基分類器，使得集成分類器能適應數據分布的變化。

由于流式數據自身的5 個特點，流式數據分類算法要求具備在資源受限的環境中實時地分析處理數據能力以及遇到概念漂移現象時具備快速恢復性和適應性能力。存在的流式數據分類算法按所含分類器個數主要分類兩大類［11］：單模型算法和集成分類算法。

1.3 單模型算法

單模型算法，也稱為單分類器方法，通過對傳統批量分類算法的改進和擴展，并配備特定的概念漂移處理機制，使之能夠適應流中數據的變化。根據傳統分類算法，單模型算法可以分為基于決策樹、支持向量機和貝葉斯模型等幾種類型。由于分類問題基本都是線性不可分問題，決策樹作為經典的非線性分類器，已發展出許多基于決策樹的流式數據分類算法，同時支持向量機作為一個線性分類器，可以通過利用核函數將非線性數據映射到高維空間使其轉變為線性可分問題。兩類方法各有優勢，且呈現出平行發展的趨勢，因此本文主要介紹基于決策樹和基于支持向量機的兩類單模型算法。

1.3.1 基于決策樹的單模型算法

決策樹算法的主要思想［12］：從包含待分類樣本全集的根節點開始，遞歸地將根節點或者葉子節點替換為內部節點（決策節點）進行樣本屬性的測試來生長樹，直到當前葉子節點沒有屬性可以劃分或屬于一個類時，算法完成對決策樹的構造。

Domingos 等提出了快速決策樹（Very fast de?cision tree，VFDT）［13］，該算法在決策節點的屬性劃分上采用信息熵增益和基尼指數作為評判標準，僅掃描流式數據一次且不保存，能對大量數據流進行分類，但其沒有考慮發生概念漂移的情況。針對VFDT 的該缺點，Hulten 等［14］提出了概念自適應的快速決策樹（Concept adaptive VFDT，CVFDT），該算法在VFDT 基礎上，引入了處理概念漂移的滑動窗口技術，其通過當前窗口的流式數據建立臨時子樹，并在每次窗口滑動時對決策樹進行優化更新。為了進一步解決不確定數據流中概念漂移問題，劉志軍等［15］提出了自適應快速決策樹（Adaptive fast decision tree，AFDT），該算法將數據流中的特征屬性分為不確定數值屬性和不確定分類屬性，并與概念漂移問題緊密聯系，通過不斷將不確定數值屬性轉化為不確定分類屬性來構建決策樹。極速決策樹（Extremely fast de?cision tree，EFDT）［16］與VFDT 類似，不同之處是在對決策節點進行屬性劃分時，使用Hoeffding 邊界來確定最佳屬性劃分帶來的增益，且最佳屬性劃分具有一定的置信度，使得其所需時間比VFDT 要長，但分類準確率有明顯提高。Pecori等［17］提出的流式模糊決策樹（Streaming fuzzy de?cision tree，SFDT）將模糊邏輯和模糊集理論中的一些元素與VFDT 相結合，利用均勻模糊劃分對每個輸入屬性進行離散化，每個節點在分裂時以模糊信息增益作為度量指標選擇最佳的輸入屬性，該算法相比于VFDT 較為復雜，但其能高效處理模糊數據和噪聲數據，有效提高分類的精度。

1.3.2 基于支持向量機的單模型算法

支持向量機的主要思想是［18］：針對線性不可分的情況，通過使用一個預先定義的核函數導出的非線性映射，將原始線性不可分的樣本映射到較高維的線性可分的特征空間中，在新的特征空間采用線性算法對樣本的非線性特征進行線性分析。

Wang 等［19］提出了一種用于大規模內核在線訓練的預算隨機梯度下降算法（Budgeted stochas?tic gradient descent，BSGD），該算法通過迭代地接收標記的流式數據，利用隨機梯度下降（Stochastic gradient descent，SGD）在相應的目標函數上更新模型權重以及動態更新支持向量的數目來解決概念漂移問題，當支持向量數目超出預定于上界時，使用刪除、合并以及投影3 種主要的預算維護策略來控制支持向量的數量。該算法能有效地處理大規模流式數據分類，而且擁有較高的分類準確率。Le 等［20］提出了用于大規模在線學習的近似向量機算法。算法首先將整個輸入空間域用足夠小的單元重疊分區覆蓋，并構造出相應的覆蓋核心集，當有新的流式數據實例到來時，找到包含該實例的單元并用相應的核心點來近似這個實例，最后在近似表示該實例的核心點以及實例本身中通過伯努利隨機采樣選擇一個加入支持向量集中，實現對模型的增量更新。該算法利用當前數據不斷增量更新模型，從而能靈活地處理概念漂移問題，并增加分類的準確性。

上述基于決策樹的分類模型，易構建且可解釋性強，可以結合概念漂移檢測技術處理應對概念漂移問題。由于現實數據的高維性及不平衡特性，未來可以在決策節點分裂時的屬性劃分上做進一步研究，以提高分類的準確性?；谙蛄繖C的分類模型能學習特征空間的維數，利用在線學習技術增量的更新模型來解決概念漂移問題，但隨著數據量的增加，其支持向量的數目也會不斷增長，進而導致模型的可擴展性差，未來可以在動態更新支持向量數目、核心集覆蓋等問題上進行研究，從而提高模型的準確性及擴展性。表1 概述了基于決策樹和基于SVM 的單模型算法優缺點。

表1 基于決策樹和基于SVM 的單模型算法優缺點Table 1 Merits and demerits of single model algorithms based on DT and SVM

1.4 集成分類算法

集成學習算法，也稱為多模型算法，根據不同時間段的數據訓練N個基分類器，通過某種組合方式將各分類模型組合成集成分類器，并將各基分類器的結果按某種機制進行綜合得到集成模型的結果，使得集成模型的魯棒性更強，并能夠靈活地處理概念漂移問題。根據模型每次處理數據的數據量，可分為基于數據塊的集成分類算法和基于單個實例的在線集成分類算法［21］。

1.4.1 基于數據塊的集成分類算法

基于數據塊集成的主要思想是［22］：數據以塊的形式進行傳輸，每個塊包含固定數目的訓練實例，根據訓練生成N個基分類器，淘汰準確率低的分類模型，在線更新集成模型，最后綜合各分類器的分類結果，達到快速適應數據分布變化的目的。

文獻［23］中提出了一種準確率更新集成算法（Accuracy updated ensemble，AUE），該算法采用大小為n的窗口和增量的基學習器，使得集成模型中基分類器都可根據當前塊的訓練實例增量式更新，從而能更快速地適應突變漂移。文獻［24］提出的CVFDT 更新集成算法（CVFDT update en?semble，CUE）使用VFDT 訓練基分類器，用最新數據塊更新準確率低于隨機猜測準確率的基分類器，并對訓練數據采用bagging 操作增加基分類器間相異度，其分類準確率和概念漂移適應度都較高?；谛畔㈧氐募煞诸愃惴ǎ‥nsemble classi?fication algorithm based on information entropy，ECBE）［25］根據分類前后熵值差異檢測概念漂移并決定各基分類器的權值，通過相鄰概念漂移周期內各基分類器權值信息得出概念穩定時的權值下界，移除權值低于該下界的基分類器，既提高了分類準確率又能快速適應新概念。Sarnovsky 等［26］提出了多樣化動態類加權集成算法。該算法維護可變數量的異構的基分類器，根據基分類器的性能動態調整其權重，一旦權重低于給定閾值，即將該分類器從集成模型中移除。通過多樣性調整投票的組合規則以及各基分類器預測的聚合最終獲得集成模型結果，若結果不正確，則向集成模型中添加新的隨機基分類器。由于基分類器的自適應機制和多樣化，使得該集成模型能有效處理各類型的概念漂移。

1.4.2 基于單個實例的在線集成分類算法

基于單個實例的在線集成主要思想是［27］：數據流中的實例單獨到達，一次僅處理一個訓練實例并對其進行增量學習，不斷地修正集成分類模型，從而可以在有限的時間和內存下對數據流分類做出快速反應。

Zhai 等［28］提出的EBPegasos 集成算法以在線核SVM 作為基分類器，檢測到概念漂移時，首先判斷漂移對各基分類器的影響，若影響較大，則需移除性能最差的基分類器，并創建新的基分類器，若影響不大，則對各基分類器進行增量更新，使得集成模型在遺忘和利用舊概念之間達成良好的平衡。Shan 等［29］提出的在線主動學習集成模型（On?line active learning ensemble，OALEnsemble）由一個穩定分類器和一定數目的動態分類器構成，穩定分類器根據數據流分布變化的長期趨勢，捕捉漸變漂移，動態分類器根據數據流最新的變化，及時更新基分類器，捕捉突變漂移，使得該算法對概念漂移有較強的處理應對能力。Canzian 等［30］提出了一種感知器加權多數投票算法，該算法采用一組分布式的學習器，每個學習器可以采用不同類型的局部分類器生成局部預測，收集并使用加權多數投票規則聚合其余學習器的局部預測以生成最終預測，最后根據學習器的預測結果，通過感知器學習規則來動態更新其聚合權值，使其能靈活應該概念漂移問題。該算法能對分布式、異構以及動態的數據進行分類且性能較高。

集成學習和在線集成學習都是通過聚合策略將多個學習器進行聚合從而得到集成結果，通過在學習過程中結合概念漂移檢測技術監測流式數據分布的變化來快速適應各類型的概念漂移，但這使得算法性能在一定程度上受到漂移檢測技術的限制。為了進一步提高和改善集成模型的準確率和性能，未來可以向基分類器的多樣化和高魯棒性的漂移檢測算法發展研究。

2 大數據聚類

大數據聚類是一種無監督學習方法［31］，即不需要預先定義類別和訓練樣本，其目的是將未知的數據集分成若干簇，使得同一簇中的數據點具有盡可能大的相似度，而不同簇中的數據點具有盡可能大的相異性。聚類過程主要有兩個階段：（1）定義相似函數，將其作為判斷數據之間是否相似的依據；（2）選擇合適的聚類算法將數據對象劃分到不同的簇中。大數據聚類分析方法可分為單機聚類方法以及多機器集群聚類方法［32］。單機聚類方法的實現主要是通過對經典聚類算法進行優化、擴展以及對數據集進行降維或采樣等處理，而主流的多機聚類方法則主要體現在體系結構等方面，其底層聚類算法與經典聚類算法無本質差別。

2.1 單機聚類

為解決處理大規模數據聚類的需求，單機聚類算法也一直在演進，現在的單機聚類主要有2 個研究方向：通過改進、優化經典的聚類算法，使算法本身即具備精確的聚類效果又有良好的可擴展性，或是在不改變數據分布特征的前提下，直接對待處理的數據集進行采樣或降維等處理，即通過減少數據量或縮小整個數據集的形式來處理大規模數據。

在經典聚類算法基礎上進行改進、優化的可擴展單機聚類算法，如Monath 等［33］提出的子聚類組件算法（Sub?cluster component algorithm，SCC），是一種凝聚型層次聚類，算法使用鏈接函數來衡量兩組點的相似性，以最佳優先方式進行迭代，即迭代從最易決定相似性高低的簇開始，并延長相似度衡量困難的決定，直至其易判斷，且算法的每次迭代都會以不同的粒度生成簇。該算法能生成高質量的聚類結果，且可以擴展到數十億數據點而不犧牲質量。Kobren 等［34］提出了一種純度增強旋轉的層級聚類算法（Purity enhancing rotations for clus?ter hierarchies，PERCH），算法將新數據點路由到葉子上，以增量的方式進行樹結構的構建，通過樹的旋轉糾正貪婪增量聚類過程中的錯誤，提高了子樹的純度、聚類的質量以及算法執行速度，并引入促進平衡的旋轉，使得算法可擴展到大量數據點N和集群K的極端聚類上。

對待處理數據集進行采樣或降維等處理的單機聚類算法，如Zhao 等［35］提出了分層抽樣加擴展的模糊C?means 聚類算法。該算法首先通過局部敏感哈希技術將相似數據劃分到一起，粗略地將大規模數據劃分成若干層，并從各層中隨機抽取數據對象形成代表性樣本；其次在采樣的樣本上使用模糊C?means 聚類算法生成局部聚類結果；最后使用最近鄰近標記實現樣本外擴展，即將樣本外對象分配到距它們最近的、已確定的簇中。該算法通過對數據進行分層采樣，保持了原始大規模數據集中的數據分布特征，提高了聚類質量和計算效率。Chen 等［36］提出了一種基于深度學習的深度流形聚類方法（Deep multi?manifold clustering，DMC），由于位于流形局部的點具有相似的表示，算法首先通過迭代最小化局部保持目標函數使得學習到的表示有意義，其次通過直接對表示執行K?means 聚類算法確定聚類中心，并使用面向聚類的目標函數，即根據表示到各質心的接近程度來懲罰表示，來指導模型提取特定于聚類的表示，最后將兩個目標函數集合為一個聯合損失函數，使用反向傳播不斷地對其優化，使得算法具有更精確的聚類效果以及更強大的性能。Mautz 等［37］提出了一種在高維空間中具有輕量級參數的非冗余K?means 聚類算法（Non?redundant K?means，Nr?K?means），該算法尋找數據集中相互正交的子空間，確保發現的聚類代表數據的不同視圖，并在所有子空間中優K?means的目標函數，從而識別不同子空間中的多個非冗余簇，即數據對象在不同子空間中屬于不同簇，可進一步分析各個非冗余簇之間的關系。算法引入的噪音空間能過濾不能在所有子空間中表示良好的數據特性，使得算法具備同時降維的能力以及高效地執行速度。

2.2 多機聚類

多機聚類首先將待處理數據劃分成若干塊，分別加載到不同機器上執行分組聚類，其次綜合分組聚類結果并根據分析結果自動改進聚類過程，最后再重新進行分組聚類，直到綜合聚類結果符合一定的終止條件。多機聚類具有較高的處理速度和可擴展性，但增加了機器間的通信成本，因此優秀的多機聚類算法需在盡可能少的通信成本下，獲得較好的聚類效果。多機聚類可以分為并行聚類和分布式聚類［38］。

2.2.1 并行聚類

并行聚類主要是通過縱向擴展平臺實現單機聚類算法的并行，常見的縱向擴展平臺如多核CPU，圖形處理單元（Graphics processing unit，GPU）等。

基于多核CPU 的聚類算法，如Hadian 等［39］提出了基于多核CPU 的并行K?means 算法，該算法有兩個線程集組成：主線程和塊聚類線程。主線程負責在讀取數據集時按預定義的大小劃分塊，并使用隊列概念將塊發送給塊聚類線程。塊聚類線程接受塊后使用K?means 算法進行聚類，得到當前塊的質心并存儲入全局質心列表中。所有塊聚類完成時，主線程加載全局質心列表，通過K?means 算法對質心進行聚類，形成最終聚類，在12 核機器上的評估結果顯示，該算法在產生的聚類質量上與K?means、K?means++相同但運行速度快得多。Er?dem 等［40］提出了一種多核具有噪聲的基于密度的空間聚類算法（Multicore fast density?based spatial clusteringofapplicationswithnoise，M?FDBSCAN），該算法首先將二維模糊數據對象集按核數進行劃分，其次對每個子集并行使用FD?BSCAN 算法進行聚類，獲得部分確定聚類區域，最后合并成最終聚類區域，該算法性能隨著核數的增加呈線性增長，處理速度明顯增加。

基于GPU 的聚類算法，如Melo 等［41］提出了基于GPU 并行化的點排序識別聚類結構（Ordering points to identify the clustering structure，OPTICS）實現方式，OPTICS 并行化有兩個階段，即圖形構造和執行OPTICS 算法，其中執行OPTICS 時間較短，重點在于圖形構造的并行化。算法使用3 個向量分別存儲頂點、鄰接列表節點以及邊的權值。在構造成圖時，并行地對這3 個向量進行頂點度計算、鄰接索引計算、鄰接表組裝和排序操作，實驗結果表明，該方法不僅降低了OPTICS 算法的復雜度，而且執行速度比基于CPU 的版本快得多。

前文的幾種基于多核CPU 以及基于GPU 的聚類算法中，多核CPU 適用于復雜程度高的算法，GPU 適用于低復雜度、高計算量的算法。為進一步優化算法的性能，未來可以探索和設計將多核CPU 與GPU 并行計算相結合，同時利用兩者優勢的算法。

2.2.2 分布式聚類

分布式聚類使用分布式計算框架自動對數據集進行劃分和分配，并在集群上實現聚類算法的并行，更適合處理大數據聚類，常見的分布式計算框架有MapReduce、Spark 等。

Li 等［42］提出的Multiplex K?means 算法，使用MapReduce 并行執行多個具有不同質心組的K?means 進程，Map 函數負責計算當前點與所有質心間的距離，Reduce 函數負責質心的更新，每一次迭代根據聚類內總變異值對其進行評估，對聚類質量差的K?means 過程進行剪枝，避免無用計算，對保留的高質量質心群采用啟發式方法生成新的質心群，擴大聚類結果的搜索范圍，避免陷入局部最優解，重復此過程獲得最終聚類結果，該算法相比于串行的K?means 算法有更好的效果，也適用于大數據集聚類。He 等［43］提出了一種MR?DBSCAN 算法，該算法根據空間鄰近度對數據進行分區，并在各分區獨立執行DB?SCAN 聚類算法，全局聚類結果由局部聚類結果聚合而成，該算法子程序完全并行且可擴展性良好。胡健等［44］提出的一種基于改進的果蠅算法（Improved fruit fly optimization algorithm，IFOA）的并行密度聚類算法（The density?based cluster?ing algorithm by using IFOA based on MapRe?duce，MR?DBIFOA），使用K?維樹和貪心算法對數據進行劃分，使得各分區內數據對象數量相近，并通過基于自適應搜索策略和聚類判定函數IFOA 對局部聚類的參數進行態尋優，提升局部聚類效果，并結合MapReduce 實現局部聚類的并行計算，合并得到全局聚類結果。該算法在大數據集下的聚類效果、尋優能力和魯棒性方面效果良好并具有較強的并行性能。

基于Spark 的聚類算法，如王博文等［45］提出利用Spark 設計的并行K?means 算法，首先隨機選取多個數據點作為質心，其次在一個彈性分布式數據集（Resilient distributed dataset，RDD）變換中，并行計算當前數據實例與各質心的距離，將其劃分到距離最近質心的所屬類簇，接著將各類簇的均值點更新為新質心，若相鄰兩次質心的誤差小于給定閾值，則得到最終聚類結果，反之，再次計算距離進行迭代。該算法有不錯的聚類效果和并行能力。Liu等［46］提出了一種基于Spark RDD 模型的分布式密度峰值聚類算法。該算法首先預定義局部密度閾值P和密度較高點的距離閾值D，其次通過調用Spark 的圖形計算API（GraphX）生成圖并計算截斷距離，然后計算每個數據點的局部密度p和與密度高點的距離閾值d，最后選擇p>P且d>D的數據點作為聚類中心，選擇pD的數據點作為隔離點，將剩余點分配到與其最近的聚類中心，從而完成聚類，該算法比使用MapReduce 實現的密度峰值聚類算法快10 倍，能更高效地處理大數據聚類。

基于分布式計算框架的算法能有效處理大數據聚類且擴展性好，但其消耗的軟硬件資源較多，未來可以向著在消耗軟硬件資較少的前提下實現高效、精確及可擴展的大數據聚類算法的方向進行研究。

3 大數據關聯規則挖掘

大數據關聯規則挖掘指從大量數據中發現隱藏的信息關聯性，并通過分析該關聯性幫助決策者制定正確的決策。關聯規則的強度可用支持度和置信度來衡量［47］：若有規則X→Y，則支持度為事務X和Y在事務數據庫中出現的頻率，用于判斷該規則是否有利用價值；置信度為當事務X出現時事務Y出現的頻率，用于判斷該規則的正確度。關聯規則挖掘主要有兩個步驟：（1）從數據中找出支持度不小于最小支持度的規則，稱為頻繁模式或頻繁項集；（2）從頻繁模式中找出置信度不小于最小置信度閾值的強關聯規則，其中重點在于頻繁模式的挖掘。關聯規則挖掘可分為基本的單機關聯規則挖掘和基于分布式計算框架的多機并行關聯規則挖掘［48］。

3.1 單機關聯規則挖掘

單機挖掘的基本方法有3 種：基于多候選產生的Apriori 算法［49］、基于模式增長的頻繁模式增長算法（Frequent?pattern growth，FP?growth）［50］和基于垂直格式的Eclat 算法［51］，其余的單機算法大都是在基本方法的基礎上，通過改善存儲結構快速高效地對候選集剪枝以及快速獲取候選集支持度而提出來的。

Apriori 算法依據兩個先驗性質，即非頻繁項集的超集一定是非頻繁項集以及頻繁項集的子集必為頻繁項集，對事務數據庫進行一遍掃描，并根據MinSup 剪枝得到頻繁1 項集，然后連接頻繁1項集得到候選2 項集，再次掃描數據庫剪枝獲得頻繁2 項集，以此類推進行迭代，直到無候選項集產生為止，最后根據MinCon 篩選頻繁項集得到強關聯規則。該算法的優點在于對每次迭代進行剪枝，在一定程度上減少了計算量，但每次剪枝需訪問數據庫且算法執行過程中產生了大量候選項集，其導致算法的執行效率低下。

FP?growth 算法主要包含兩個階段：（1）構造FP?Tree，掃描一次數據庫得到頻繁1 項集，再次掃描去除事務中非頻繁項目并將剩余項目按支持度遞減的順序進行排列，初始根節點為空，將事務依次插入到FP?Tree 中，每條事務在插入時，事務的第1 項作為根節點的子節點插入，若已含該節點，則只需將該節點的節點計數加1，否則將該項新生為根節點的子節點插入，在插入事務的第2 項時，將其作為已插入節點的子節點并按相同方法進行插入，直至該事務的所有項目插入完畢。（2）自底向上地對FP?Tree 進行遞歸挖掘，從頻繁1 項集中支持度最低的項目作為初始后綴開始，在FP?Tree中查找該后綴的條件模式基并構造其條件FP?Tree，遞歸地挖掘該條件FP?Tree 的頻繁模式并將其與初始后綴連接實現模式增長。該算法相較于Apriori 有兩個優勢，即不產生候選項集以及只訪問數據庫2 次，其不足之處在于壓縮原始數據的FP?Tree 需全部裝載入內存，當數據量大時，會導致計算能力受限。

Apriori 和FP?growth 算法都以水平數據格式{TID:itemset}挖掘頻繁項集,而Eclat 算法采用的是垂直數據格式{item:TIDSET}。在支持度計算上，水平數據格式需訪問一次數據庫得到而垂直數據格式中支持度即為該項目的TID 集長度。Eclat算法通過遍歷1 次事務數據庫，將數據格式轉換為垂直格式，并通過支持度計算和剪枝得到頻繁1 項集，將頻繁1 項集求交集、剪枝得到頻繁2 項集，迭代此過程直至無候選項集產生。該算法與Apriori算法都是通過頻繁k項集生成頻繁k+1 項集，但其只需訪問數據庫1 次，加快了候選項集的產生，且優化了支持度的計算方式，3 種基本方法的優缺點對比見表2。

吳磊［48］提出的基于事務映射區間求交算法（Interval interaction and transaction mapping，IITM）在FP?Tree 基礎上，采用深度優先遍歷為每個節點生成區間，獲得壓縮程度更強的頻繁1 項集區間列表，并使用哈希結構進行存儲。IITM 使用頻繁1 項集和頻繁k項集來生成候選k+1 項集，并使用由頻繁k項集生成的布隆過濾器對候選項集進行高效地剪枝，在支持度計算上，由兩個區間列表求交得到候選k+1 項集的區間列表，從區間列表中即可獲得支持度，并篩選出頻繁k+1 項集。該算法使用區間進一步壓縮數據，引入布隆過濾器降低候選項集的數目，通過區間求交快速獲取候選項集的支持度，使得算法具有較高的效率。

3.2 多機并行關聯規則挖掘

多機并行關聯規則挖掘指將數據進行劃分并分配到各節點當中，每個節點運用單機上的挖掘方法獨立地完成頻繁模式的挖掘，最后將各節點結果進行匯總得到最終結果，適合于大數據上的關聯規則挖掘。常見的多機并行挖掘方式按照大數據處理平臺的不同大致可分為基于GPU 的并行關聯規則挖掘、基于MapReduce 的并行關聯規則挖掘以及基于Spark 的并行關聯規則挖掘。

3.2.1 基于GPU 的并行關聯規則挖掘

張旭［52］提出了基于GPU 的并行關聯規則挖掘算法，該算法利用統一計算框架（Compute unified device architecture，CUDA）編程模型，在CPU 主機端完成邏輯復雜的候選項集生成，在GPU 設備端并行計算邏輯簡單但計算量大的候選項集的支持度。算法依此主要分為兩個階段：（1）在CPU 中進行，在深度為k的前綴樹中，找到前k-1 項相同的兩個頻繁k項集，將它們的第k項按字典順序進行連接，得到候選k+1 項集，并將存儲結構由前綴樹轉換為位表結構，以便在GPU 中進行計算；（2）在GPU 中進行，將兩個頻繁k項集的位表進行按位與運算得到候選k+1 項集的位表，使用多個并行線程計算其位表中“1”的數目，得出候選項集的支持度并判斷其是否為頻繁項集。該算法通過GPU 加速了支持度計算速率，且算法的性能隨著測試數據集規模的增長逐步擴大。

Chon 等［53］提出了基于GPU 的GMiner 算法，該算法采用第1 層遍歷策略（Travesal from the first level，TEL）和中間層跳轉策略（Hopping from the intermediate level，HIL）充分發揮GPU 的計算能力。TEL 將頻繁1 項集映射到事務數據塊內并劃分得到若干分區，將分區和事務數據塊傳送至GPU 中，在GPU 中通過按位與得到候選項集的部分支持度，并傳送入主存進行匯總。TEL 僅對頻繁1 項集進行大量計算來挖掘全部頻繁項集，在挖掘較長的頻繁項集時性能較低，而HIL 策略通過使用更多GPU 顯存來提高此性能。該算法充分利用GPU 的計算能力，且其性能隨著GPU 數量的增加呈線性增長，適用于大規模數據集的挖掘。

Djenouri 等［54］提出的CGSS（Single scan on multiple cluster nodes equipped with GPUs）算法結合了集群和GPU 的能力，將挖掘過程進一步加速。在CGSS 中，集群采用主從模式且每臺機器都配有GPU 設備端，該算法主要分為5 個過程：（1）簡單分區。主節點將事務數據庫等分成p個分區分配工作節點。（2）智能分區。根據工作節點GPU 中線程塊數量r，各分區通過迭代將相鄰事務依次分配給不同的線程塊，劃分成r個子分區。（3）各線程塊生成所有可能的候選項集，并存入線程塊的本地哈希表中。（4）合并。每個GPU 工作節點合并其線程塊的本地哈希表創建GPU 本地哈希表，主節點在GPU 本地哈希表的基礎上創建1 個全局哈希表。（5）生成頻繁項集。該算法利用分區策略解決了集群負載的不均衡以及減少了線程發散，在面向大數據的關聯規則挖掘上具有更高的性能和并行能力。

3.2.2 基于MapReduce 的并行關聯規則挖掘

（1）并行Apriori 算法

Huang 等［55］提出的基于MapReduce 的Smart?Cache 算法，由兩個MapReduce 作業組成：第1 個是在Map 函數中，降低MinSup 得到局部支持度，根據局部支持度執行局部挖掘算法，將支持度在兩者之間的項集存入Cache 中，通過簡單的線性回歸分析出Cache 容量呈非線性增長的轉折點，即最佳局部支持度閾值，將根據局部支持度篩選得到的局部頻繁項集以及支持度信息寫入Hadoop 分布式文件系統（Hadoop distributed filesystem，HDFS）的Cache 文件中，Reduce 將Map 的結果進行匯總；第2 個是Map 任務在HDFS 的Cache 文件中查找支持度信息，Reduce 任務通過合并各個候選項集的支持度得到全局頻繁項集。該算法使用局部支持度提高了結果的準確性，通過存儲第1 個MapRe?duce 產生的支持度信息，大大減少了第2 階段的計算量，提高了執行效率和算法性能。

Chon 等［56］提出的BIGMiner（BIG data pat?tern miner）算法，包括預計算和挖掘頻繁k 項集2個階段。預計算階段根據預定義集合長度將頻繁1 項集劃分成互不相交的集合，枚舉出所有子集，生成垂直數據格式的事物塊。挖掘階段中Map 任務根據頻繁k項集和事務塊生成候選k+1 項集及局部支持度，Reduce 任務合并局部支持度獲取頻繁k+1 項集，并將其廣播到所有機器，用于下次迭代時Map 任務中。該算法在執行過程中不產生中間數據，且只需廣播頻繁k項集的網絡開銷，使得算法伸縮性好，在大規模數據上具有較高性能。

（2）并行FP?growth 算法

Xun 等［57］提出了基于頻繁完全樹（Frequent items ultrametric tree，FUI?Tree）的FiDoop 算法，FUI?Tree 相較于FP?Tree 最大的優勢在于避免了遞歸遍歷。FiDoop 算法首先通過2 次掃描事物數據庫，將各條事務中非頻繁項目丟棄，得到含有k個頻繁項目的k項集；其次將k項集分解成2～（k-1）個項集，使用長度相同的項集構造FUI?Tree；最后通過FUI?Tree 的葉節點計數便可獲得所有頻繁項集。該算法實現了自動并行化，能夠在大型集群上并行地進行數據挖掘，進一步加快了數據挖掘速度，面對高維數據集時，Xun 等［57］還提出了通過維度減少的方法來提高挖掘效率的FiDoop?HD算法。

Wang 等［58］提出了一種基于多項目支持的頻繁模式挖掘算法（Multiple item support frequent patterns，MISFP?growth）。該算法首先在數據預處理階段引入預定義的多項目支持度；其次用1 個MapReduce 作業完成對各項目實際支持度的計算，得到多項支持的最小值，刪去事務中低于最小多項支持的項目，并將剩余各項目按實際支持度大小降序排序；最后根據多項支持劃分成子事務塊，與FP?growth 算法類似，通過構建MISFP?Tree 的后綴條件模式基以及條件模式樹來遞歸地挖掘頻繁模式。實驗結果證明，該算法在多項支持的數據集上實現了高效的挖掘，且通過并行計算減少了執行時間，適合于大數據分析應用。

（3）并行Eclat 算法

Gole 等［59］提出的ClustBigFIM 是一種將聚類和頻繁模式挖掘混合的算法。算法利用MapRe?duce 計算模型首先對待處理大型數據集進行K?means 聚類生成多個簇；其次對每一個簇并行執行Apriori 算法挖掘頻繁k模式，使用生成的前綴樹得到TID 列表，并將其合并成一個全局TID 列表，以便于將水平格式轉換為垂直格式；最后通過對前綴樹執行Eclat 算法挖掘頻繁k+1 項集。該算法使用K?means 算法對數據進行預處理，并對簇進行頻繁項集挖掘，從而使得算法的執行效率更加地高效，能更快地處理大數據集。

張春等［60］提出了一種基于MapReduce 的MREclatK 算法。該算法的思路比較簡單，整個并行計算過程由一個MapReduce 作業迭代完成。具體地，首先執行一次MapReduce 作業得到頻繁1 項集，接著在每次迭代過程中在Map 端將數據格式轉換為垂直格式，將剪枝后的頻繁1 項集和頻繁k項集求并集獲得候選k+1 項集，求交集獲得相應的支持度，在Reduce 端合并候選k+1 項集得到全局支持度，通過比較MinSup 篩選得到頻繁k+1 項集。該算法將傳統Eclat 算法向MapReduce 計算模型上進行了遷移，使得該算法能處理海量數據。

3.2.3 基于Spark 的并行關聯規則挖掘

（1）并行Apriori 算法

Rathee 等［61］提出的無需生成候選項集的算法R?Apriori 包含3 個步驟：第1 步獲取頻繁1 項集，Map 函數完成flatMap（）和map（）的轉換操作，Re?duce 函數調用reduceByKey（）計算每個項目的支持度并修剪出頻繁1 項集，存入布隆過濾器中；第2步Map 函數將事務中不包含在布隆過濾器的項目進行修剪，利用修剪后的事務快速生成所有可能的項集對，再使用Reduce 函數來計算支持度并得到頻繁2 項集；第3 步由頻繁k項集迭代生成頻繁k+1 項集。該算法通過步驟2 消除了候選項集的生成，降低了計算復雜度，有效地提高了效率和性能。

Rathee 等［62］提出的動態關聯規則挖掘算法Adaptive?Miner，改進了R?Apriori 算法的頻繁模式挖掘過程，該算法根據上一次迭代中生成的頻繁項集數量分別計算R?Apriori 方法和常規Apriori 方法的時間消耗成本，動態選擇當下最優的方法執行此次迭代，使得其具有更高的挖掘速度和性能。

（2）并行FP?Growth 算法

Shi 等［63］提出了一種基于Spark 的分布式FP?Growth 算法（Distributed FP?growth algorithm based on Spark，DFPS）。該算法首先將全局頻繁1項集廣播到各節點；其次分配條件模式庫，將頻繁1 項集中各項目按支持度降序排列，除首個項目外為剩余各項目分配一個分區存放條件模式基，并將事物中的項目分發到相應的分區；最后進行并行挖掘，各分區間數據相互獨立，無需傳遞消息，獨立地使用傳統FP?growth 算法來挖掘頻繁項集。該算法在并行挖掘階段消除了節點間的通信負載，且無多余的候選項目集生成，使得DFPS 在大數據環境下的執行速度、并行能力以及可擴展性都得到了顯著提升。

吳磊［48］提出了PIITM 算法，該算法將IITM 算法遷移到Spark 平臺上對大規模數據進行分布式并行挖掘。算法中各節點根據頻繁1 項集生成局部FP?Tree，并將生成的條件模式基根據后綴發送至相應的節點上，數據相互獨立的各節點獨立地執行IITM 算法挖掘局部頻繁項集，最后由Reduce 作業匯總各結果并篩選出頻繁項集。該算法充分考慮了節點間的負載均衡，且擴展性強，適應大規模集群。

（3）并行Eclat 算法

馮興杰等［64］提出了一種基于Spark 的Eclat 算法SPEclat，算法首先以（Item，BitSet）的形式獲取并存儲頻繁1 項集，其次將具有相同前綴的頻繁k項集劃分到同一節點上，最后在各節點上將頻繁k項集進行自連接得到候選k+1 項集，并根據Min?Sup 得到頻繁k+1 項集。該算法優化了支持度的計算，減少了候選項集的數量，在處理大規模數據方面具有較高的性能，但其沒有對節點進行負載均衡處理。

Huang 等［65］提出了一種優化的Eclat 算法（Bal?anced parallel eclat，BPEclat），該算法在SPEclat 算法基礎上，使用范圍劃分思想平衡計算節點負載，根據Apriori 算法的先驗性質刪除不滿足MinSup的非頻繁項集，對候選項集的生成采取了進一步優化。實驗結果表明該算法通過減少候選項集的數量，提高了時間效率，在處理大數據時更為可靠，并具有較好的可擴展性。

上述基于GPU、基于MapReduce 以及基于Spark 的并行關聯規則挖掘算法的主要思想是將經典算法遷移至分布式計算平臺，但隨著數據量的不斷更新增加，將會產生海量的關聯規則，故如何壓縮關聯規則數量以及如何利用已有的結果來增量地進行關聯規則的挖掘，都值得在未來深入探索。

4 結論

本文從數據挖掘角度介紹了大數據處理算法，分別從流式大數據分類算法、大數據聚類算法和大數據關聯規則挖掘3 方面梳理總結了近年來國內外專家學者取得的進展。隨著CUDA、MapRe?duce 和Spark 等分布式并行計算平臺的普遍應用，面向大數據的數據挖掘算法的研究取得了巨大的進步，但針對大數據真實性、高維和高噪聲等特點，仍需在如下方面開展進一步研究：

（1）增量式更新算法。對于當前大多面向大數據的數據挖掘算法都根據固定大小的數據集進行分析和評估算法性能，但在信息時代新數據無時無刻不在增加，要求算法能對結果進行動態更新，因此需進一步研究處理新舊數據變化的增量式更新算法。

（2）適用于高維數據的算法設計。目前大多面向大數據的數據挖掘算法都屬于低維度算法，而大數據普遍具有超高維度、高稀疏特性，其意味著數據的高復雜性和高計算成本，因此設計適用于處理高維數據的高性能算法值得在未來深入探索。

（3）分布式并行算法的設計和實現。現有面向大數據的分布式并行算法大多是經典算法向分布式計算平臺的遷移，并通過改進數據劃分方法達到負載均衡和降低通信開銷的目的。鑒于這一問題，未來可以考慮根據大數據的特點并結合分布式計算平臺自身優勢，設計并實現高性能、高并行性以及低復雜度的分布式并行算法。