信息爆炸式增長，企業迫切需要對海量數據進行及時、準確地處理，以獲取潛在的、有價值的信息，云計算集網格計算、分布計算、并行計算、效用計算、網絡存儲、虛擬化、負載均衡等技術于一體，具有海量的存儲能力和可彈性變化的計算能力，成為解決該問題的有效方式，自Google提出GAE(Google App Engine)后，各種云計算產品紛紛出現：Apache的FIadoop，Amazon的AWS(Amazon Web Services)，微軟的Windows Azure，IBM的Blue Cloud，SalesForce.com的SFDC等，遺憾的是以上公司并沒有將研發的云計算架構大規模應用于數據挖掘領域，而市面上各種通用數據挖掘工具，如SAS的EntERPrise Miner，IBM的SPSS Modeler等，價格昂貴，對海量數據分析的效果欠佳。
基于云計算平臺研發的數據挖掘產品，比較有名的包括：中國科學院計算所研發的PDMiner(Parallel Distributed Miner)，提供基于Hadoop的數據處理能力，但數據預處理能力有限，部分挖掘算法的并行策略還需改善；Apache軟件基金會的開源Mahout，提供分類、聚類、頻繁模式挖掘、回歸、降維等算法，但缺少數據準備和展示過程，用戶需要以編程方式調用算法；Source forge的開源Augustus，支持預測模型標記語言，可在Amazon的云計算平臺上運行，雖提供了強大的建模能力和穩定的平臺支撐，但對數據預處理工作關注太少：德國Fraunhofer在開源數據挖掘軟件WEKA和開源云平臺Hadoop之上實現了圖形化的數據挖掘工具包，雖解決了WEKA單機運行的缺陷，但WEKA無法為用戶提供完整的業務流程；Radoop以Hadoop，Hive，Mahout為基礎，對RapidMiner進行了擴展，并以拖拽方式配置海量數據分析流程，但它尚處起步階段，且依賴于底層Mahout提供的分析算法，只能完成部分常用的數據分析工作。
而學術界從2011年起，對于將MapReduce這一云計算框架應用于數據挖掘領域的研究和討論逐年增多，例如，Robson使用MapReduce實現多維度大數據的聚類；Alina實現了快速聚類算法；Herodotos通過他們的“profing and what-if engine”提升了MapReduce的效率，種種現象表明，MapReduce適合于開發并行數據挖掘算法。
總之，目前的并行數據挖掘工具在功能、處理能力、用戶體驗等方面存在一些不足，更明顯的是它們著眼點或者是科研，或者是簡單應用，并沒有以大規模企業應用為背景，適應大型企業商務智能應用需求。以電信行業為例，為了正確分析用戶數據，獲取有價值的知識，更好地提供服務，發現商機，制定營銷、資費等策略，不少電信運營商自主開發基于云計算的新型數據分析工具。例如，國外AT&T推出了Synaptic，Verizon推出了CaaS；國內，中國移動提出“大云計劃”，電信提出了“星云計劃”，聯通開發了“互聯云”。
本文介紹一款基于Hadoop的并行數據分析系統PDM(Integrated Parallel Data Mining)，它以全球最大電信運營企業——中國移動的商務智能應用需求為背景，旨在針對海量數據提供高效、準確、便捷的數據分析服務。本系統具有強大的數據預處理能力，優化了傳統算法的并行策略，既適合簡單的數據分析，也支持復雜的業務邏輯。更重要的是，系統將數理統計功能、文本分析、圖挖掘能力與傳統數據挖掘工具相結合，豐富了數據處理的方法和能力，本系統還針對電信數據，開發了一系列典型應用，并在中國移動多個省公司試點運行。
本文結構如下：第1章系統整體架構，說明各層的功能和特色；第2章并行多元回歸算法和并行多源最短路徑算法的設計與實現；第3章基于本系統開發的典型應用；第4章系統性能測試結果；第5章總結全文，說明后續研究工作。
1 系統架構
如圖1所示，本系統包含：提供云存儲和計算環境的云平臺層，提供數據分析核心能力的算法層，提供業務支撐的邏輯層和提供用戶交互功能的界面層。
圖1 系統架構
1.1 云平臺層
提供計算和存儲能力，主要由一系列第三方開源軟件組成。
云存儲框架：由分布式文件系統HDFS(Hadoop Distributed File System)、分布式數據庫HBase(Hadoop Database)和分布式數據倉庫工具Hive構成，實現數據分布式存取。
云計算框架：由Hadoop的MapReduce模型，提供并行計算、數據發送和錯誤控制等功能。MapReduce使用極為簡單，以64MB為單位自動將文件劃分成數個片段，并送入各計算節點，執行用戶定義的Map（映射）過程，輸出key/value的鍵值對；經過一次混洗和排序，把具有相同key值的鍵值對，傳送到同一個Reduce（歸納）過程；最后根據用戶定義的Reduce，完成處理，將結果保存在分布式集群上。
數據組織模塊：加載不同格式的數據；根據內容快速查詢數據；針對云計算系統常存在缺乏數據來源的問題，本系統提供數據交換功能，保證數據在本地機器、指定服務器、分布式文件系統、分布式數據庫、傳統數據庫之間，快速、無縫地轉換和傳遞，便于與現有軟硬件設施相結合。
監控采集模塊：對任務進度、計算資源、存儲資源進行監控，并收集各節點產生的日志。
1.2 算法層
算法層包含大量并行數據分析算法，能高效準確地處理各種結構化、半結構化、非結構化數據。算法層所包含的功能如下。
數據分析模塊。提供核心數據處理能力，包括4類并行算法集。
并行數據預處理算法集：實現抽取(Extract)、轉置(Transform)、加載(Load)等數據預處理操作，為后續數據分析奠定基礎，含37種算法，主要分為：對數據類型和取值進行約束、選擇的“清洗類”，進行轉換操作的“轉換類”；進行計算操作的“計算類”；對數據進行分割、采樣的“抽樣類”；進行集合運算的“集合類”；進行更新或插人數值的“更新類”。
并行數據挖掘算法集：將傳統的數據挖掘算法并行化，以滿足海量數據的處理要求，含16種算法，主要分為：有監督的“分類”學習算法；無監督的“聚類”學習算法；從數據中發現平凡相集的“關聯規則”算法。
并行數據統計算法集：針對數值型數據求解某些統計特征值，從不同角度反映數據的特性，含22種算法，主要分為：反映數據中心點位置的“集中趨勢”；反映數據變異程度的“離散趨勢”；描述數據分布形狀和對稱性的“分布趨勢”；計算不同組數據相關程度的“相關性分析”；根據一定假設條件由樣本推斷總體的“假設檢驗”。
并行文本挖掘算法集：含11種算法，通過文本預處理、聚類、分類等一系列方法，實現在海量非結構化文本數據中提煉知識的目的。
并行社會網絡分析算法集：社會學家以數學方法、圖論等為基礎，提出社會網絡分析(SNA，Social Network Analysis)，對網絡中各種關系進行精確的量化分析，建立“宏觀和微觀”之間的橋梁．本算法集含22種算法，分為：針對點、邊、網絡進行分析的“點特征”、“邊特征”、“網絡特征”算法；尋找網絡中所有的派系，并根據重疊關系產生社團網絡的“社區發現”算法；挖掘網絡中社團在不同時間段上的演化關系的“社區演化”算法。
算法模型模塊，采用W3C(World Wide Web Consortium)認定的PIVWIL(Predictive Model Markup Language)標準，描述和存儲數據挖掘模型；采用OMG(Object Management Group)制定的CWM(Conunon Warehouse Meta model)標準定義元數據，以便其它數據倉庫工具能夠理解各自的元數據含義。
接口封裝模塊．以Java API，WebService，REST(Representational State Transfer)3種方式封裝算法，以便算法的調用和二次開發。
1.3 邏輯層
邏輯層對存儲資源、計算資源進行調控和管理，并以流程驅動的方式分析數據。本系統支持分支、選擇等多種復雜結構；支持多條流程組合業務的方式；提供流程和業務兩個層次的調度功能，為用戶創建符合需要的數據處理步驟創造良好的平臺支撐。
1.4 界面層
基于富客戶端的web應用，為用戶創建數據處理流程或業務提供良好的使用體驗。
2 核心算法介紹
由于算法眾多，且篇幅有限，本章選取了數據挖掘算法集中的并行多元線性回歸算法，以及社會網絡分析算法集中的并行多源最短路徑算法進行介紹。
2.1 并行多元線性回歸算法
用于確定因變量y和自變量X1，X2，…，Xp之間的關系。
首先，假設式(1)成立，其中ε～N(O，σ)，β1，β2，…，βp以及σ為參數，如果p>2，式(1)就是線性回歸模型：
求解線性回歸模型參數的最基本方法是最小二乘法。當式(2)達到最小時，用最小二乘法計算向量β。根據式(3)得到β的估計值β：
建立線性回歸模型，先計算訓練集中自變量和因變量的平均值，然后利用這些均值計算矩陣L中每個元素。假設矩陣中的元素是l(i，j)，則式(4)成立，其中X(i，j)是原始矩陣中元素，avg(X(i))是原始矩陣中第i列的平均值，N是向量的個數，k的取值范圍是1到n。
以類似的方法計算向量B。假設l(i，y)是向量B的元素，可由式(5)求得：
根據式(6)，得到回歸參數β向量，其中L-1可由Gauss-Jordan算法求得：
綜上，算法的步驟如下：
Step1設置MapReduce任務，計算矩陣L和向量B的平均值；
Step2根據式(4)和(5)計算矩陣L和向量B的全部元素；
Step3根據式(6)計算向量p。
2.2 并行多源最短路徑算法
最短路徑問題是圖論中的經典問題，而Dijkstra算法和Floyd-Warshall算法分別求解單源和多源最短路徑。基于MapReduce的單源最短路徑算法可由Dijkstra改進而成；但Floyd-Warshall以鄰接矩陣作為輸入，而MapReduce僅適合讀入鄰接鏈表，并行多源最短路徑的求解無法基于Floyd-Warshall算法進行改進。一種解決方案是將并行單源最短路徑解法迭代多次，但系統開銷大，實用性低，本文提出了一種基于MapReduce的多源最短路徑的算法。
建立消息傳遞模型，每個節點都有一張消息表，即mesTable，用于保存到達該節點的消息。消息的內容包括消息的源節點(發送該消息的源節點，srcld)，源節點到該節點的距離(distance)和消息的狀態(state)。模型按如下方式進行消息傳遞：
Step1在各節點中的mesTable中添加第一條消息記錄，消息的源節點是節點自身，到該節點的距離為0，并將消息狀態置為active。
Step2將mesTable里的所有active狀態消息的distance和節點的鄰接邊的權值相加，并將該消息發送給該鄰接邊所對應的鄰接節點，最后將該消息狀態置為inactive。
Step3 當一個節點收到新消息后，如果mesTable中未包含與新消息來自同一個源節點的消息，則將該消息放入本節點的mesTable中；反之，如果mesTable存在與新消息來自同一個源節點的舊消息，此時，若新消息記錄中的distance小于舊消息中的distance，則用新消息更新舊消息，并置該消息狀態為active。
Step4重復步驟2，3，直到所有節點中的消息記錄狀態均為inactive。
該模型易用MapReduce實現：在Map函數中，讀入節點鄰接表及mesTable，并向鄰居節點發送消息；在Reduce函數中，接收新消息，根據Step3的內容更新節點的mesTable。
3 典型應用
本系統不僅提供通用的數據挖掘能力，還能針對不同數據集快速開發多種應用，例如用戶行為分析、用戶興趣識別、客戶流失預測、網絡質量分析、用戶的多重身份識別、家庭用戶的社團發現等等。本節將介紹利用電信數據開發的“套餐推薦”和“營銷關鍵點發現”兩種典型應用。
3.1 套餐推薦
背景：電信用戶的消費行為具有特定的模式。發現這些消費模式，能為人網新用戶推薦適合的業務，并針對新的消費需求推出新業務。
原理：利用了“客戶細分”和“客戶分類”兩種技術。客戶細分，用于發現具有相似消費行為的客戶，為發現消費群體的消費行為特征，及時制定符合消費行為的套餐業務提供可能，常采用無監督的聚類學習方法；客戶分類，是建立一套數據模型，發現客戶各屬性與客戶所選套餐之間的隱含關系，達到分類的目的。
實現：將39列、約300萬條記錄的原始通話數據，進行預處理，選出20列數據——主要包括用戶、費用、語音（主叫、被叫、本地、漫游、長途等各種情況下的通話次數和總時長）及短信等信息；采用并行k均值算法實現客戶細分，將客戶劃分為6類：高端客戶、高端通話客戶、高端增值業務客戶、中端通話客戶、終端增值業務客戶和低端客戶；利用所得客戶類標號，以套餐編號作為分類屬性，采用并行C45的決策樹分類方法，建立客戶分類模型；最后將模型用于預測新用戶的潛在行為，為新人網用戶的套餐推薦方案提供決策支持。
結果：在86個計算節點上，對29GB原始數據（含100萬數據）進行分析，共耗時37分46秒。建模準確率達到89.03%。證明本系統對傳統數據挖掘問題的處理，效果不俗。
3.2 營銷關鍵點發現
本節將介紹采用并行社會網絡算法開發的典型應用——“營銷關鍵點發現”。
背景：營銷關鍵點，是自身消費對其他客戶消費有較大影響的點。通過探索營銷關鍵點，可開拓新的營銷渠道，針對關鍵點進行業務推廣，提高營銷效率。由于營銷關鍵點對周圍客戶的消費行為影響較大，該客戶離網會加大周圍客戶離網的概率，因此需要對關鍵客戶進行消費跟蹤，及時預測消費行為。
原理：Google提出了PageRank算法，用于衡量特定網頁相對于其他網頁的重要程度，將網頁改為用戶t將鏈接改為用戶間的通信關系，可將PageRank應用于營銷關鍵點的發現上。PageRank值越大意味著該用戶影響力越大。PageRank的計算是一個迭代過程，需要獲得鄰居節點的信息，這是通過消息傳遞模型實現的。
實現：選擇原始通話數據中的主叫號碼、被叫號碼、通話時長等屬性進行建模，并去除通話時間、短信數量極小的用戶記錄，形成輸入數據；利用并行社會網絡分析算法集的PageRank方法，構建網絡拓撲結構，找出通話網絡中的PageRank值較高的點，作為營銷關鍵點。
結果：在92個計算節點上，對含有340萬個通話節點的數據進行分析，共耗時約1小時46分鐘，輸出結果按用戶的影響力降序排列，證明本系統的圖挖掘功能拓展了數據挖掘的應用范圍，具有很好的效果。
4 系統性能
本文對PDM進行了測試，測試環境：各節點CPU為Intel (R) Xeon (R) CPU E5504 @ 2.00GHz、4核，內存為8GB，硬盤1TB；節點之間傳輸速度為31.5MB/s～33.8MB/s；測試數據大小為403 GB.測試的部分結果如下：
在10個節點上，系統響應100個用戶同時登錄平均時間是3.32s；
在10個節點上，對于典型的并行數據挖掘、統計算法需要2h左右(如圖2)；
圖2 數據挖掘、數據統計算法的性能測試結果
在5個節點上，對分組計算和缺值處理算法進行擴展性測試，圖3顯示，隨數據規模的增大，算法耗時呈線性增長，具有良好的擴展性。
圖3 分組計算和缺值處理算法的性能測試結果
社會網絡分析中，如果數據量過大，串行算法消耗的資源和時間是難以接受的。表1顯示，在30個節點上，將Map個數和Reduce個數都設置為60，本系統的數據替換、度數統計、均值、最大值、邊點統計、單源最短路徑、接近度(Closeness)等算法計算復雜度為線性；聚集系數和社團發現算法容易受輸入數據的影響，如果輸入的網絡具有比較大的局部密集子圖容易造成計算的不均衡，會使某個Reduce的計算量急劇增加導致整體的計算時間較長，但它們在稀疏的網絡中的復雜度近似線性，而通話網是一般是稀疏網絡，因此適用于分析通話數據。
表1 社會網絡分析的性能測試結果
5 結論
本文從系統架構、核心算法介紹、典型應用、系統性能等多個角度，全面介紹了一款基于Hadoop的并行數據挖掘系統，本系統融合了數理統計、文本分析及圖挖掘技術，擴大了傳統數據挖掘的范圍和效果；針對傳統MapReduce的并行計算機制，優化了數據處理流程的性能；提供的數據組織功能，解決了HDFS數據來源問題，增加了類數據庫處理能力；業務引擎，能自由組合各類分析算法，滿足不同層次的要求，易于開發典型應用，因此，本系統性能優越、功能豐富、商用前景廣泛，是一個前沿且注重實用的實踐．下一步的工作有：繼續添加數據分析算法，優化算法性能；對于一些不便于用MapReduce機制處理的算法類型，可以探索新的并行計算模型，例如考慮融入圖數據存儲和計算框架，提高圖挖掘的效率。
轉載請注明出處：拓步ERP資訊網http://www.guhuozai8.cn/
相關文章
