一種基于云計算的高效數據挖掘框架研究

劉猛

一種基于云計算的高效數據挖掘框架研究

劉猛

云計算可按軟件即服務（SaaS）的形式提供數據挖掘的結果。數據挖掘的性能和質量是云計算環境下數據挖掘應用的重要使用標準。文中提出一種基于云計算的數據挖掘應用及其數據集的分布和調度框架，該框架實現了基于云計算的K均值聚類方法，并將其作為云軟件即服務（SaaS）來提供給用戶，其主要目標是降低應用的總體運行時間，將挖掘質量的損失最小化。仿真結果表明，相比于已有方案，其方案在速度獲得顯著提升的同時，挖掘質量損失最小。另外，當聚類數量和數據集的規模上升時，挖掘質量也具有良好的擴展性，可促進本文方案在云服務提供商中的應用。

云計算；數據挖掘；K均值聚類；總體運行時間

0 引言

云計算[1]作為一種新興技術，使得人們對可配置的共享計算資源能隨心所欲的訪問，只需極少量的管理或服務提供商的交互，即可迅速供應和發布這些可配置共享資源。云計算包括3種服務模型：云軟件即服務（SaaS），云平臺即服務（PaaS），基礎設施即服務（IaaS）。SaaS提供商為用戶提供可以運行的應用，方便用戶快速獲得相關結果。PaaS提供商為用戶應用的云部署提供條件。IaaS提供商為用戶提供運行應用所需要的處理、存儲和網絡能力。

云計算是許多科學和工程應用的潛在高性能方案[2]。許多研究人員試圖利用Hadoop[3]等分布式數據挖掘工具來提升數據挖掘應用的性能。然而，使用該工具來處理大數據中的數據挖掘應用的復雜度較高。一般而言，數據挖掘應用的用戶只對數據的挖掘結果感興趣，無需知道數據的挖掘地點和挖掘方式。此外，他們還關注應用的實時性和結果的準確性，即關注結果的質量。云計算通過服務水平協議（SLA)[4]可以提高服務的性能和水平。為此，本文提出一種基于云計算的分布式數據挖掘應用方案，并將其集成為云計算環境下的SaaS來提供給用戶。

1 相關工作

云計算因其高靈活性和性價比，被廣泛應用于分布式數據挖掘的基礎設施，相繼有眾多研究者提出了一系列卓有成效的數據挖掘方法。如文獻[5]提出并實現了一種基于Hadoop云計算平臺的頻繁閉項集的并行挖掘算法。該算法主要包括并行計數、構造全局頻繁項表、并行挖掘局部頻繁閉項集和并行篩選全局頻繁閉項集四個步驟。在多個數據集上的實驗表明，該方法能大幅提高數據挖掘的效率，具有較好的加速比。文獻[6]針對目前搜索數據量大、搜索延遲的特點，提出了基于云計算Web挖掘的搜索模型。采用提出的基于Map/Reduce模型的改進型算法，在一定程度上減少了搜索的代價，提高了搜索效率。文獻[7]提出了一種基于云計算的Web數據挖掘方法，該方法將海量數據和挖掘任務分解到多臺服務器上并行處理。采用Hadoop開源平臺，建立一個基于Apriori算法的并行關聯規則挖掘算法來驗證了該系統的高效性。

另外，隨著分布式數據庫的出現，分布式數據挖掘(DDM)在近年吸引了人們的眼球。文獻[8]提出一種基于高性能云的分布式數據并行處理方法。使用一個專用的網絡服務分層結構，適用于高性能廣域網絡連接的計算機集群所產生的大型分布式數據集的數據挖掘。實驗結果表明，與Hadoop方法相比，該方法的性能有顯著提高。文獻[9]在基于不可信節點的云計算架構基礎之上提出了一種新型的分布式數據挖掘模式，實現分布式數據挖掘無縫接入云計算系統，以滿足物聯網的需求。總的來說，上述方案大多還存在著以下不足：1）不能實現對云基礎設施的實時監測，不能根據系統負載自適應地分配數據挖掘任務到云端，使得系統的負載失衡，在造成資源浪費的同時，也降低了數據挖掘的質量；2）可擴展性差，當對大數據進行挖掘時，挖掘質量較差、且延遲高。針對這些不足，本文主要研究基于云計算的聚類策略用于數據挖掘任務。目前有多種聚類技術，比如K均值聚類、分層聚類和基于密度的聚類等[10]。這些方法各有優缺點。鑒于K均值法的普及性，本文以K均值聚類為基礎，提出一種基于云計算的K均值算法作為SaaS模式，并通過仿真實驗驗證了本文方案的有效性。

2 K均值聚類

為了便于描述，下面先對K均值聚類進行闡述。K均值聚類只根據可用信息（數據點的相似度/離散度）生成數據點的K個分區。目標是使每個數據點與其對應聚類質心間離散度之和最小化（即類內離散度）。設有m個未標識數據點χ=｛x1,x2,...,xm｝，K均值法生成χ的K個分區，且使如下目標函數最小，如公式（1）：

其中ui表示聚類i的質心，表示x和ui間的歐氏距離。K均值聚類主要包括如下3個步驟：

1）初始化：采取某種啟發式策略或隨機選擇K個初始質心（即聚類中心）。

2）聚類分配：每個數據點分配給與其最近質心相對應的聚類。

3）質心再計算：利用第2步中分配的數據點再次計算每個聚類的質心。然后，回到第2步。

上述迭代過程一直持續至滿足某個終止條件為止（比如兩次迭代期間均無數據點的聚類發生變更，或者達到最大迭代次數）。

3 基于云計算的數據挖掘總體框架

云計算環境下的數據挖掘總體框架如圖所示：

圖1 云計算環境的數據挖掘總體框架

在圖1中，一個云包括可被本文框架使用的多個物理聚類。為了分發大數據，需要一個主工作站、多個與主工作站相連的計算工作站。主工作站和計算工作站間的鏈路速度表示數據傳輸時的通信處理速度。總體框架由如下組件構成：

1）主工作站：可以處理云中集中式數據的節點，調度決策也發生于該節點中。主工作站是主節點上負責分發數據的計算實體。

2）計算工作站：可進行本地數據挖掘的數據單元稱為計算工作站。本文假設每個計算工作站可以訪問足夠多的存儲空間以便存儲分配給它的數據量。

3）資源管理器：通過與資源記錄器的數據庫進行溝通來檢查資源可用性的實體。為K均值應用選擇一組資源以便與存儲于SLA記錄器數據庫中的SLA相匹配。它將所選擇的資源發送到主工作站做進一步處理。有多種啟發性資源選擇策略可滿足SLA要求。然而，這不在本文研究范圍內。

在云環境下為K均值應用選擇的每個計算工作站i,i∈｛1,...,N｝，其計算容量為μi。大數據包括共Wtotal個可分割計算負載。計算工作站i處理所有負載中的一部分，即chunki≤Wtotal。本文將一個計算工作站處理chunki個單位的負載所需時間TPi建模如公式（2）：

其中θi表示啟動節點i計算過程的固定延時，單位為秒，μi表示節點的計算速度，單位為單位負載/秒。將發送chunki個單位負載給計算工作站i所需時間TCi建模如公式（3）：

其中iλ表示主工作站往計算工作站i傳輸數據的啟動延時，單位為秒。Ci表示主工作站和計算工作站i間通信鏈路的數據傳輸速率，單位為單位計算負載/秒。當運行SSH或訪問工作站i而使用各種云軟件時，啟動主工作站到計算工作站i的數據傳輸過程，即會導致iλ延時。

為了便于主工作站確定應該往每個計算工作站分配多少負載，本文使用文獻[11]中的調度算法。每個計算工作站i將被分配大小為chunki的處理負載。本文算法考慮了網絡和計算能力，且基于如下公式確定負載規模：

首個計算工作站完成分配任務chunk1所需時間，由下式給出如公式（4）：

對第二個工作站如公式（5）：

依次地，chunkN值由下式給出如公式（6）：

以式（7）為基礎，通過替代相應等式中的chunk1，即可確定剩余負載chunki,i=2,...,N。

4 基于云計算的K均值聚類

本文基于云計算的K均值聚類方法架構如圖2所示：

圖2 本文K均值法的架構

設D表示存儲于主工作站控制的中央存儲器處的數據點集。首先利用第5節中的部署計算數據塊大小，其中chunki表示將傳遞給computing-workeri的分區的尺寸。設di表示分區，即：將會分配給computing-workeri的數據點集合。因此，數據分區分配完畢后，computing-workeri通過K均值聚類方法對數據塊di進行聚類，生成具有K個代表點（即：質心）的K個聚類。設Si表示computing-workeri計算出的K個質心所組成的集合。下一步驟是從所有計算工作站收集所有質心，在主工作站處存儲Kn個質心。然后，主工作站對Kn個質心進行K均值聚類，計算出K個聚類。最后，使用這些聚類的質心，并結合D中每個數據點到質心的距離，計算聚類的全局集合。綜上所述，基于云計算的K均值聚類偽代碼如下所示：

假設已經按照第3節中SLA的要求選擇了計算工作站。主工作站在部署時使用第3節中描述的公式來計算必須要分配給工作站的數據塊：每個計算工作站采用μ和θ值作為輸入；主節點和每個計算工作站間的通信鏈路采用C和λ值作為輸入。主工作站將規模上升的樣本數據集發送給計算工作站，測量每個計算工作站上的計算時間及從主工作站到每個計算工作站的傳輸時間，并對這些數據進行線性擬合。然后，利用線性回歸來計算大規模數據擬合時的計算能力（μ）和網絡帶寬（C）。在數據規模幾乎為0時進行擬合，并計算出傳輸延時（λ）和計算延時（θ）。所有系統參數計算5次然后取均值。由于主工作站需要計算C,λ,μ,θ，減少運行次數將能避免較大開銷。

下面偽代碼描述的調度程序根據本文獲得的公式計算數據塊。本文部署了3種調度策略：（1）基于CPU的調度策略，調度器根據計算工作站的計算能力（μ）對計算工作站降序排序；（2）基于網絡的調度策略，根據主工作站和計算工作站間的網絡容量（C）對計算工作站降序排序；（3）無選擇策略，采取隨機次序。

然后，應用中的主節點利用計算出來的數據塊相應地分割應用，按照C的升序次序將應用的數據塊分配給計算工作站，也就是說，首先將相應數據塊分配給通信鏈路C最大（即最快）的計算工作站。這可以降低剩余計算工作站對相應數據塊的等待時間。在將計算數據塊發送給相應的計算工作站后，主工作站通過使用ssh命令，觸發計算工作站遠程運行。本文在主節點和每個計算工作站間配置無密碼通信，每個計算工作站在完成任務后會向主節點發送一個信號。

5 框架的部署

6 仿真實驗

本節評估主工作站中K均值分布式應用的數據挖掘性能。比較本文框架與應用的理想makespan和理論makespan的效率。理想makespan計算方法是大數據集的總體規模除以被選計算工作站計算能力之和。

理論makespan是本文框架根據計算應用和系統參數獲得的值。另外，本文使用聚類純度指標（Purity）來衡量聚類挖掘的質量。常用的有兩種聚類純度指標：基于多數派的總純度指標（GP）[12]和基尼系數指標（GI）[13]。總純度指標表示每個聚類中多數派類別的正規化頻率，定義如下：

其中，K表示生成的聚類總量，W=｛W1,...,WK｝表示利用K均值法生成的K個聚類組成的集合，C表示類別標簽數量，表示聚類i中屬于類別j的數據點數量，D表示整個數據集。

其中pj∩i）表示類別j和聚類i的聯合概率，即：

6.1 實驗環境

本文實驗環境包含3個節點構成的一個異質聚類：1個主工作站和2個計算工作站。主工作站也可向自己分配任務，扮演計算工作站的角色。主工作站配置1個Intel Xeon 2.8 GHz CPU，運行CentOS 6.3 Linux操作系統。其中1個計算工作站配置AMD Opteron 252 CPU，openSUSE 12.1(i586),版本12.1，另一個為Intel Xeon 3.6 GHz CPU，運行CentOS 6.3 Linux操作系統。聚類通過一個思科交換機相連。

本文采用UCI數據庫中的森林覆蓋數據集。該數據集包括不同類型森林的地理空間描述，有7種類別，54種屬性及581,000個左右的實例（約130MB）。對數據集正規化，為相同屬性賦予相同權重。同時，在聚類期間去除類別標簽，以避免無意之中產生監督。為了進行大規模數據的實驗仿真，本文通過隨機選擇并復制部分實例，生成了具有500,000-1000,000個實例的多個森林覆蓋數據集。

本文測量了分布式K均值應用的總makespan。應用的makespan表示從主工作站開始向計算工作站分配數據集至主工作站上生成最終挖掘結果所經歷的時間。計算了應用相對于理想makespan的效率，同時還計算了實際makespan相對于理論值的退化情況（（actual-theoretical）/theoretical）*100。通過計算數據規模上升時的總運行時間及聚類純度來評估工作負載上升對分布式K均值的性能和挖掘質量的影響。通過計算聚類規模增加時的聚類純度評估聚類規模的影響，即聚類數量與聚類純度的關系。進行100次實驗取均值。

6.2 實驗結果分析

當部署本文框架并調整K均值應用的尺寸時，本文的主要目的是研究經過尺寸調整后的K均值makespan與理想的makespan的接近程度，如圖3所示：

圖3 真實makespan相對于理論makespan的退化比

圖3表明，實際makespan與理想makespan之比達到最大值3.18。在本文實驗環境中，當數據規模較大時，比率降到2.38如圖4所示：

圖4 正規化后的實際makespan與理想makespan

退化比例表明理論性能和實際性能間存在差異。本文框架假設數據集及運行時間之間具有線性關系。對基于聚類的應用來說，這一假設未必始終成立，因為收斂時間還依賴于被選擇的數據集。然而，從總的趨勢可以看出，隨著數據集規模的增加，退化比例會呈現下降趨勢，這表明本文方法在真實環境下確實能夠降低數據挖掘應用的總體運行時間。

聚類純度與聚類數量(K)和工作站數量(N)間的關系如圖5所示：

圖5 純度與聚類數量(K)和工作站數量(N)之間的關系

X軸對應于聚類數量(K)(7-49)，Y軸對應于純度。從圖中可明顯看出，不論N取何值，聚類純度均會隨著K的上升而上升。以K=14和K=50為例。當K=14時，工作站為集中式(N=1)、2個工作站和3個工作站時的聚類純度分別為0.58,0.61和0.58。當K=50時，工作站為集中式(N=1)、2個工作站和3個工作站時的聚類純度分別為0.65,0.64和0.65。這一結果表明，當K增加時，基于云的數據聚類與集中式版本一樣，均可提高聚類純度。換句話說，基于云的聚類方法與集中式方法同樣有效。這是因為對工作站獲得的質心集合專門進行了一次聚類，于是每個位置本地生成的聚類模型在主節點處被有效融合。

數據規模增加對純度的影響如圖6所示：

圖6 純度與數據集規模

此時固定設置K=15。X軸表示數據集規模（單位為千個實例），Y軸表示純度。該圖表明，增加數據集規模對集中式和基于云的方法具有類似的影響。以X=500和X=1000為例。當X=500時（即：數據集有500K個實例），集中式方法和帶有3個工作站的基于云的方法的純度分別為0.58和0.60。當X=1000時（即：數據集有1百萬個實例），集中式方法和帶有3個工作站的基于云的方法的純度分別為0.59和0.60。可以看出數據集對集中式和基于云方法的聚類純度沒有顯著影響。根據這些結果得出結論：基于云的方法的聚類精度與集中式方法相同。

最后，為了進一步體現本文方案的優越性，采用UCI數據庫中的森林覆蓋數據集作為測試數據集，將本文方案與文獻[6,7]中的方案在數據挖掘質量方面進行比較，實驗結果如圖7所示：

圖7 不同方案的聚類質量比較

從圖7中可以看到，隨著數據集規模的增加，不同方案的聚類純度都在下降。其中，文獻[6]中方案的聚類純度最低，而本文方案性能最好。仔細分析其原因可知，這是由于文獻[6]的方案旨在應對實時性要求較強的以犧牲部分挖掘質量來達到提升挖掘效果的目的。而文獻[7]的方案能夠對數據挖掘任務進行優化分解，并通過定制并行挖掘規則來處理海量數據，較好的性能。而本文方案則更進一步，通過對云基礎設施的實時監測、在考慮了所選資源的網絡和計算延時基礎上，能夠自適應地從可用的云硬件網絡中選擇可用的硬件資源（計算和網絡資源）分配給分布式數據挖掘應用，因此數據挖掘質量最優。總的來說，本文方案是有效的，能夠滿足目前大多數數據挖掘應用的需求。

7 總結

本文提出一種基于云計算的K均值聚類法以便對應用進行擴展。該方法的主要目標是把K均值應用作為一種SaaS云提供給云終端用戶。用戶只對K均值應用的性能和挖掘質量感興趣，無需知道具體實現方法。本文的目標是通過提出一種基于云的大數據挖掘方法，向終端用戶隱藏云技術的復雜性。其主要作用在于使K均值具有伸縮性并將其作為SaaS提供，同時將挖掘質量的損失降到最低。在下一步工作中將研究在本文框架中集成實時服務水平協議，以滿足用戶對挖掘/聚類的性能和質量要求。此外，還將提出數據的動態自主式再分配策略，以便本文框架能夠實時監測基于云的應用的性能和質量指標，在必要情況下可以采取糾正措施。

[1]李德毅,張天雷,黃立威.位置服務:接地氣的云計算[J].電子學報,2014,42(4):786-790.

[2]Ismail L,Barua R.Implementation and performance evaluation of a distributed conjugate gradient method in a cloud computing environment[J].Software:Practice and Experience,2013,43(3):281-304.

[3]Lai Y,ZhongZhi S.An efficient data mining framework on Hadoop using Java persistence API[C].Computer and Information Technology(CIT),2010IEEE10th International Conference on.IEEE,2010:203-209.

[4]Wu L,Garg S K,Buyya R.SLA-based resource allocation for software as a service provider(SaaS)in cloud computing environments[C].Cluster,Cloud and Grid Computing(CCGrid),201111thIEEE/ACM International Symposium on.IEEE,2011:195-204.

[5]陳光鵬,楊育彬,高陽,等.一種基于MapReduce的頻繁閉項集挖掘算法水[J].模式識別與人工智能,2012,25(2):220-224.

[6]方少卿,周劍,張明新.基于Map/Reduce的改進選擇算法在云計算的Web數據挖掘中的研究[J].計算機應用研究,2013,30(2):377-380.

[7]程苗.基于云計算的Web數據挖掘[J].計算機科學,2011,38(10):146-149.

[8]桂兵祥,何 健.基于高性能云的分布式數據挖掘方法[J].計算機工程,2010,36(5):76-78.

[9]陳磊,王鵬,董靜宜,等.基于云計算架構的分布式數據挖掘研究[J].成都信息工程學院學報,2010,25(6): 577-579.

[10]Kantardzic M.Data mining:concepts,models,methods,and algorithms[M].John Wiley&Sons,2011.

[11]Ismail L,Khan L.Implementation and performance evaluation of a scheduling algorithm for divisible load parallel applications in a cloud computing environment [J].Software:Practice and Experience,2014,11(4):158-167.

[12]Osei-Bryson K M.Towards supporting expert evaluation of clustering results using a data mining process model[J]. Information Sciences,2010,180(3):414-431.

[13]Kavulya S,Tan J,Gandhi R,et al.An analysis of traces from a production mapreduce cluster[C].Cluster,Cloud and Grid Computing(CCGrid),2010 10th IEEE/ACM International Conference on.IEEE,2010:94-103.

Research on an Efficient Data Ming Framework Based on Cloud Computing

Liu Meng
(Dongguan Science and Technology School,Dongguan 523000,China)

Cloud computing can provide data mining results in the form of Software as a Service(SaaS).Both performance and quality of data mining are the fundamental criteria of data mining application in the cloud computing environment.This paper proposes a data mining application based on cloud computing and the framework for its distribution and scheduling of data sets. The framework implements the K mean clustering method based on cloud computing,and provides itself with the users as the cloud SaaS.Its main purpose is to reduce the whole execution time of the application and to minimize the loss of quality of mining. The simulation results show that,compared with the existing scheme,the scheme proposed in this paper can minimize the loss of quality of mining while the speed is significantly improved.In addition,it has good scalability of quality of mining when the amounts of cluster and scale of data sets both increase.It can promote this paper's program application in cloud service provider.

Cloud Computing;Data Ming;K Mean Clustering;Overall Execution Time

TP393

A

1007-757X(2015)06-0015-05

2015.03.16）

劉猛（1981-），男，江蘇邳州人，東莞理工學校，講師，研究方向：網絡安全、云計算，東莞，523000