一種基于增量式時間序列和最佳任務調度的Web數據聚類算法

摘 要： 為了實現Web服務請求數據的快速聚類，并提高聚類的準確率，提出一種基于增量式時間序列和最佳任務調度的Web數據聚類算法。該算法進行了Web數據在時間序列上的聚類定義，并采用增量式時間序列聚類方法。先通過數據壓縮形式降低Web數據的復雜性，再進行基于服務時間相似性的時間序列數據聚類； 最后針對Web集群服務的最佳服務任務調度問題，通過以服務器執行能力為標準來分配服務任務。仿真實驗結果表明，相比基于網格的高維數據層次聚類算法和基于增量學習的多目標模糊聚類算法，該文的算法在聚類時間、聚類精度、服務執行成功率、聚類失真度上均獲得了更好的性能。

關鍵詞： Web數據聚類； 增量式時間序列； 數據壓縮； 最佳任務調度

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2016）14?0004?05

A Web data clustering algorithm based on incremental time series and

optimal task scheduling

CHEN Ke， KE Wende， XU bo

（Department of Computer Science and Technology， Guangdong University of Petrochemical Technology， Maoming 525000， China）

Abstract： In order to achieve fast clustering of Web service request data and improve accuracy of the clustering， a Web data clustering algorithm based on incremental time series and optimal task scheduling is proposed in this paper. The Web data clustering definition in the time sequence and time series incremental clustering method are adopted in the algorithm. The complexity of Web data is reduced first in data compression form， and then the time series data clustering based on service time similarity is conducted. Finally， for the problem of the best service task scheduling in Web cluster services， the executive capacity of the server is taken as a standard to dispatch the service tasks. The simulation results show that in comparison with high?dimensional data grid?based hierarchical clustering algorithm and multi?objective fuzzy clustering algorithm based on incremental learning， the algorithm proposed in this paper has obtained better results in the aspects of time clustering， clustering accuracy， success rate of all service execution and distortion degree.

Keywords： Web data clustering； incremental time series； data compression； optimal task scheduling

0 引 言

隨著互聯網技術的發展，Web服務數量的增長速度不斷加快，對于越來越多的Web服務請求，如何保障用戶所需要響應速度以及查詢準確度來說是個巨大的挑戰[1?2]。網絡系統在保障用戶的Web服務請求時，通常采用數據挖掘的方法處理大規模的Web服務請求數據[3]。

聚類算法是數據挖掘領域的一個重要研究內容，通過多個作為聚類中心的數據樣本與其他數據樣本之間的相似性程度，使數據樣本向聚類中心靠攏，從而形成多個簇結構[4]?，F有的經典聚類算法有K?means，QIDBSCAN，PAM，AP等聚類算法[5?8]。以上一些方法沒有利用本體等技術從語義層次進行匹配計算來實現服務聚類，影響了服務聚類的準確性；另外一些方法在利用傳統的聚類方法實施服務聚類時，計算服務間的相似度所耗時間比較長，影響了服務聚類的效率。綜上，這些算法應用為搜索引擎時，存在著精確度不高、召回率低、信息過載和淹沒的問題。文獻[9]提出一種基于RDB中自身連接的Web服務聚類方法，該方法利用本體概念間的語義推理關系，并設計一種基于關系數據庫，快速準確實施Web服務聚類，但也存在著服務種類設定單一固定，沒有考慮服務特性信息，實際應用性不高的問題。

針對上述聚類算法在應用中的問題，本文提出一種新的Web數據聚類算法，首先對于Web數據在Web服務的時間序列上的聚類過程進行了定義和分析，接著提出了增量式時間序列聚類方法，該部分包括了數據壓縮和數據聚類，確保在數據挖掘前期處理掉重復的數據，利用時間相似度矩陣，對聚類任務進行分組，進一步確保所設計算法的準確度。然后依據最佳任務調度策略實現Web集群服務中的最佳負載運算狀態，進一步保證本文所設計方法的快速高效。整個系統算法系統框圖見圖1。

1 基于時間序列的Web數據聚類定義

對于Web數據在Web服務的時間序列上的聚類過程，定義如下：

定義1 時間序列。文中時間序列[K=k1，k2，…，kt]表示在Web服務的總的壽命軌跡中，任何時間[t]內表示樣本數據時間特性的數字有序集合。

定義2 時間序列聚類。給定[N]個對象的數據集，則[N=K1，K2，…，KN]，表示一個時間集。以作為一個聚類中心，基于相似信息均勻的時間序列數據被集中在一起，這就是時間序列聚類。

定義3 相似信息。兩個時間序列之間的相似性是基于它們的子序列之間的相似性。

定義4 子集群。一個子集群GCi是一組單獨的在時間上具有相似性的時間序列數據，并表示為一個單一的原型。時間序列數據根據與它們的子集群緊密度被附加到新的子集群。

定義5 聚類能力。時間序列[ki]與一個子集群GCi的緊密度被定義為：

式中：[Xij]表示[ki]與[kj]之間的相似度；[GCi]表示時間序列數據的數目；[Aki]是用來區別具有低緊密度的時間序列數據，并把它們放到一個新的子集群中。

2 增量式時間序列聚類算法

時間序列分析（Time Series Analysis）是一種動態數據處理的統計方法，而本文采用的增量式時間序列聚類是采用聚類的方法先對總的數據進行時間序列的分析，從而根據時間相似性將數據分成多個子集群，再對各個子集群數據進行相似性分析。而且本文的增量式時間序列聚類方法還加入了數據壓縮技術，有效減少算法運算的復雜性，減少聚類時間。該算法的流程包括數據壓縮和時間序列數據聚類2個步驟。

2.1 數據壓縮

對于非常相似的時間序列數據，基于增量式時間序列聚類方法首先計算出時間序列數據之間的相似度矩陣，以一個緊密度閾值為標準，通過比較閾值的大小來確定時間序列數據是否達到一定的相似程度，當數據達到一定的相似度時，通過移除這部分相似數據，從而盡可能地減少重復的無用數據，實現Web數據的壓縮。

先采用數據壓縮的方法可以有效地減少Web數據的復雜性[10?11]。時間序列數據首先通過歸一化法而被標準化，防止時間序列數據在壓縮時發生比例變化和偏移。假如[K=k1，k2，…，kt]是一個時間序列，則時間序列數據通過歸一化定義為：

式中：[ai]表示數據點的算術平均值；[λ]是在給定的時間序列內所有數據點的標準偏差。

時間序列數據之間的相似性被計算出來并存儲在一個[N×N]的相似度矩陣[XN×N]中，假設[DN×N]為一個距離矩陣，由于[Xij]表示[ki]與[kj]之間的相似度，則[Dij]用來表示[ki]與[kj]之間的歐幾里得距離，[Dij]的計算公式為：

[Dij=i=1nki2-kj2] （5）

當給定一個相似度矩陣[XN×N]，其閾值范圍為（0，1）的緊密度，算法通過從一個子集群移除時間序列數據來實現數據壓縮。

2.2 時間序列數據聚類

在步驟1中，時間序列數據是基于時間的相似性進行分組。當兩個時間序列數據在結構信息上是相似時，在時間上并不一定相似，而只有考慮到時間序列上的相似性，才更加符合實際的Web數據聚類情況。因此，子集群之間的相似性被計算出來，并且存儲在一個[M×M]的相似性矩陣中，用[YM×M]表示。[Yij]代表著子集群[GCi]與[GCj]之間的相似度。子集群之間的歐幾里得距離是被計算出來構建相似性矩陣[YM×M]的。為了計算子集群[GCi]與[GCj]之間的距離，需要計算子集群[GCi]中所有數據點與子集群[GCj]中所有數據的歐幾里得距離的平均值。得到距離方程：

式中：[nGCi]，[nGCj]分別表示子集群[GCi]和[GCj]的數據點數量。

3 最佳任務調度

在進行Web的集群服務時，服務器的裝載量平衡可以被描述為：[N]個任務需要分配到[M]個節點服務器，并且用不同的裝載量和處理量進行處理，為了找到一個優化調度，以最小化總完工時間。 該系統的數學模型表示如下[12?13]：

假設有[M]個服務器（或節點）和[N]個任務，并且每個任務必須被分配給一個服務器。在此采用[F=f1，f2，…，fM]代表服務器，并用[L=l1，l2，…，lM]表示當前的負載，[N]個任務表示為[Y=y1，y2，…，yN]，建立一個[M×N]的矩陣來表示任務和服務器，用[gij]表示任務[yi]在服務器[fj]的兩種狀態：

假設任務[yi]在服務器[fj]執行所需要的時間為[tij]，定義進行任務調度時最佳的系統狀態具有以下條件：

（1） 整個系統具有相對短的處理時間；

（2） 整個系統的吞吐量在任務執行時是較大的。

采用一個函數[Wyi，li，fi]，它可以反映整個系統處理任務的能力：[Wyi，li，fi=μ1i=1Mj=1Ntij+i=1Mfiti-μ2i=1Mli2i=1Nyi] （8）

式中：[μ1]和[μ2]分別表示一個常數；[li]反映當前服務器[fj]的負載能力；[i=1Mli]表示系統當前所有服務器的負載能力；[i=1Mfiti]中的[fiti]表示對應服務器[fj]處理每個任務的時間間隔；[i=1Mfiti]則表示系統在處理任務過程中的總間隔時間；[i=1Mj=1Ntij+i=1Mfiti]的值越大，說明該系統在完成任務上花費的時間越多，則說明該系統的運算能力越差。[i=1Mli]越大，則說明系統的負載能力越強。因此這里的[Wyi，li，fi]反映的是在處理每一個任務時系統在運算及負載上的綜合能力，并用它來反映整個系統處理任務的能力，[Wyi，li，fi]越小，則系統處理任務的能力越好。當處于任務執行狀態且服務器的負載能力達到最大時，該系統處在最佳的運行狀態。假設每個服務器作為一個聚類中心，任務以服務器的執行能力作為衡量緊密度的一個標準，緊密度越高的服務器，任務就會向其聚攏，但服務器每增加一個任務時，根據式（8）可知其執行能力會逐漸下降。在本文的Web數據聚類算法中，實現任務的最佳調度的步驟如下：

步驟1：在進行Web的集群服務時，對于[M]個服務器[F=f1，f2，…，fM]，根據式（8）計算其當前的執行能力。

步驟2：對于[N]個任務[Y=y1，y2，…，yN]，任務[yi]根據緊密度的大小[σij]而選擇是否需要向服務器[fj]聚攏，[σij]的計算公式為：

[σij=Wyi，li，fjζfjnfjloadj] （9）

式中：[ζfj]表示服務器[fj]的最大吞吐量；[loadj]表示服務器[fj]當前的負載量；[nfj]表示當前服務器[fj]所接收的任務數量。

4 實驗仿真及分析

4.1 仿真環境及場景設置

為了驗證本文提出的基于增量式時間序列和最佳任務調度的Web數據聚類算法，在CPU為Intel Core i5，主頻3.3 GHz，內存為4 GB的PC機上對算法進行了Matlab編程仿真，采用了OWLS?TC數據庫的數據資源，本文所進行的仿真實驗的Web服務總數最大為300，服務器數量為60，仿真數據取20次運行的平均結果。文獻[14]提出了GACH：基于網格的高維數據的層次聚類算法；文獻[15]提出了基于多目標模糊聚類的增量學習數據分類算法，本文的算法與這兩篇文獻中的算法進行了性能比較。

4.2 聚類時間

聚類算法完成每一次數據聚類的時間是衡量該聚類算法聚類性能的一個重要指標，為了測試本文算法的聚類性能，在仿真實驗中對系統提供的數據進行了聚類，并得出算法所需的聚類時間，得到圖2的結果。從圖2的曲線可以看出，在服務總數增大的情況下，本文算法的聚類時間保持著較小的增長趨勢，最大的聚類時間不超過200 s，而文獻[14]算法和文獻[15]算法的聚類時間隨服務總數的增加有明顯的增長趨勢，且最大的聚類時間均超過500 s。可以看出，本文算法所需的聚類時間相對較少，在這方面的性能相比文獻[14?15]算法具有一定的優勢。因為文獻[14]是一種基于網格的方法來對高維數據進行劃分，網格方法雖然在數據分類上復雜度較低，但計算量較大。文獻[15]采用的是模糊聚類的方法，并結合學習的方法實現數據分類，因此數據分類的迭代次數較多，運算量大。而本文的方法先對數據進行了壓縮，減少了運算量，縮短了聚類時間。

4.3 聚類精確度

聚類精確度是衡量聚類算法有效性的關鍵，聚類精度越高說明該聚類算法能夠更加有效地對樣本進行分類。為了驗證算法的聚類精確度，在服務總數逐漸增多的情況下，統計了三種算法的聚類精度，并得到了圖3的結果。從圖3中可以看出，服務總數的增加使得算法的聚類精度有下降的趨勢，其中本文算法的下降幅度相對較小，從60的服務總數增多至240的服務總數時，本文算法的聚類精度下降了9%，最終處在86.7%。文獻[14]的算法和文獻[15]的算法則分別下降了20.3%和21.4%，最終分別處在66.4%和68.5%。從對比數據可以看出，本文算法的聚類精確度較高。文獻[14]的方法只采用基于網格的方法，單一地考慮了數據的結構性特征，因此聚類精度最低。文獻[15]結合聚類和機器學習的方法，在一定程度上提高了聚類精度，但相比本文的方法，缺少了對數據在時間相似度上的考慮，因此聚類精度相比本文的方法不占優勢。

4.4 服務執行成功率

服務執行成功率表示對服務任務進行調度時，給服務器所分配的服務任務能夠執行成功的數量與總分配的服務任務的比值，從服務執行成功率可以說明該任務調度方法是否有效。為了對這一問題進行驗證，在服務總數增多的情況下，對三種算法就服務執行成功率問題進行了仿真實驗。從得到的圖4的結果可以看出，在服務總數增多的情況下，算法的服務成功率會出現波動的趨勢，并且會有一定的下降幅度，圖4中本文的算法在服務總數為30時服務執行成功率高于85%，之后下降到78%，而文獻[14]和文獻[15]的方法在服務總數為30時服務執行成功率均低于75%，之后分別下降到59%和53%。因此本文算法的服務執行成功率相對來說較高。

4.5 聚類失真度

聚類失真度是反映聚類算法性能的一個重要指標，失真度越小說明相似點聚在一個類中程度越高，聚類的效果就越好。在實驗中失真度定義為每個點和它所屬聚類的代表點之間距離的平方和，在改變數據聚類的個數的情況下，記錄聚類算法的失真度，并得到了圖5的結果。

5 結 論

本文提出一種基于增量式時間序列和最佳任務調度的Web數據聚類算法。該算法首先對Web數據聚類進行了基于時間序列的聚類分析，其次采用了增量式時間序列聚類，對數據進行壓縮和基于時間序列的數據聚類，最后Web的集群服務的任務調度問題采用了最佳調度策略。實驗中對聚類時間、聚類精度、服務執行成功率、聚類失真度四個方面進行了算法驗證，從得到的實驗結果來看，本文算法的聚類時間相對于兩種對比算法來說在服務總數為240時縮減了300 s，而聚類精度則至少提高了10%，服務執行成功率在服務總數為240時相比兩種對比算法則至少提高了18%。

參考文獻

[1] 俞忻峰.社交網絡挖掘方案研究[J].現代電子技術，2015，38（4）：25?29.

[2] 羅鳳娥，張成偉.基于時序數據挖掘的航班延誤預測分析[J].現代電子技術，2014，37（24）：52?55.

[3] 李靜.基于數據挖掘技術的電子商務CRM研究[J].現代電子技術，2015，38（11）：126?128.

[4] 周開樂，楊善林，丁帥，等.聚類有效性研究綜述[J].系統工程理論與實踐，2014，34（9）：2417?2431.

[5] 劉銘，劉秉權，劉遠超.面向信息檢索的快速聚類算法[J].計算機研究與發展，2013，50（7）：1452?1463.

[6] FAN W， BOUGUILA N， ZIOU D. Unsupervised hybrid feature extraction selection for high?dimensional non?Gaussian data clustering with variational inference [J]. IEEE Transactions on knowledge and data engineering， 2013， 25（7）： 1670?1685.

[7] RANA S， JASOLA S， KUMAR R. A boundary restricted adaptive particle swarm optimization for data clustering [J]. International journal of machine learning and cybernetics， 2013， 4（4）： 391?400.

[8] KRISHNASAMY Ganesh， KULKARNI A J. A hybrid approach for data clustering based on modified cohort intelligence and K?means [J]. Expert systems with applications， 2011， 41（13）： 6009?6016.

[9] 劉建曉，王健，張秀偉，等.一種基于RDB中自身連接的Web服務聚類方法[J].計算機研究與發展，2013，50（z1）：205?210.

[10] 黃德才，李曉暢.基于相對密度的混合屬性數據增量聚類算法[J].控制與決策，2013，28（6）：815?822.

[11] HATAMLOU A. Black hole： A new heuristic optimization approach for data clustering [J]. Information sciences， 2013， 222（12）： 175?184.

[12] ELHENAWY M， CHEN H， RAKHA H A. Dynamic travel time prediction using data clustering and genetic programming [J]. Transportations on research Part C： Emerging technologies， 2014， 42（14）： 82?98.

[13] KIM Younghoon. DBCURE?MR： An efficient density?based clustering algorithm for large data using MapReduce [J]. Information systems， 2014， 41（7）： 3351?3366.

[14] MANSOORI E G. GACH： A grid?based algorithm for hierarchical clustering of high?dimensional data [J]. Soft computing， 2014， 18（5）： 905?922.

[15] MAULIK Saha Indrajit. Incremental learning based multiobjective fuzzy clustering for categorical data [J]. Information sciences， 2014， 267： 35?57.