陳　珂，柯文德，許　波

（廣東石油化工學(xué)院 計算機科學(xué)與技術(shù)系，廣東 茂名　525000）

一種基于增量式時間序列和最佳任務(wù)調(diào)度的Web數(shù)據(jù)聚類算法

陳珂，柯文德，許波

（廣東石油化工學(xué)院 計算機科學(xué)與技術(shù)系，廣東 茂名525000）

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

Web數(shù)據(jù)聚類；增量式時間序列；數(shù)據(jù)壓縮；最佳任務(wù)調(diào)度

0　引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，Web服務(wù)數(shù)量的增長速度不斷加快，對于越來越多的Web服務(wù)請求，如何保障用戶所需要響應(yīng)速度以及查詢準確度來說是個巨大的挑戰(zhàn)［1?2］。網(wǎng)絡(luò)系統(tǒng)在保障用戶的Web服務(wù)請求時，通常采用數(shù)據(jù)挖掘的方法處理大規(guī)模的Web服務(wù)請求數(shù)據(jù)［3］。

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

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

圖1　算法系統(tǒng)框圖

1　基于時間序列的Web數(shù)據(jù)聚類定義

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

定義1時間序列。文中時間序列K=｛k1，k2，…，kt｝表示在Web服務(wù)的總的壽命軌跡中，任何時間t內(nèi)表示樣本數(shù)據(jù)時間特性的數(shù)字有序集合。

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

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

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

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

式中：Xij表示ki與kj之間的相似度；|GCi|表示時間序列數(shù)據(jù)的數(shù)目；A（ki）是用來區(qū)別具有低緊密度的時間序列數(shù)據(jù)，并把它們放到一個新的子集群中。

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

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

2.1數(shù)據(jù)壓縮

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

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

式中：ai表示數(shù)據(jù)點的算術(shù)平均值；λ是在給定的時間序列內(nèi)所有數(shù)據(jù)點的標準偏差。

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

當(dāng)給定一個相似度矩陣XN×N，其閾值范圍為（0，1）的緊密度，算法通過從一個子集群移除時間序列數(shù)據(jù)來實現(xiàn)數(shù)據(jù)壓縮。

2.2時間序列數(shù)據(jù)聚類

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

式中：n（G Ci），n（GCj）分別表示子集群GCi和GCj的數(shù)據(jù)點數(shù)量。

3　最佳任務(wù)調(diào)度

在進行Web的集群服務(wù)時，服務(wù)器的裝載量平衡可以被描述為：N個任務(wù)需要分配到M個節(jié)點服務(wù)器，并且用不同的裝載量和處理量進行處理，為了找到一個優(yōu)化調(diào)度，以最小化總完工時間。 該系統(tǒng)的數(shù)學(xué)模型表示如下［12?13］：

假設(shè)有M個服務(wù)器（或節(jié)點）和N個任務(wù)，并且每個任務(wù)必須被分配給一個服務(wù)器。在此采用F=｛f1，f2，…，fM｝代表服務(wù)器，并用L=｛l1，l2，…，lM｝表示當(dāng)前的負載，N個任務(wù)表示為Y=｛y1，y2，…，yN｝，建立一個M×N的矩陣來表示任務(wù)和服務(wù)器，用 gij表示任務(wù) yi在服務(wù)器 fj的兩種狀態(tài)：

假設(shè)任務(wù) yi在服務(wù)器 fj執(zhí)行所需要的時間為tij，定義進行任務(wù)調(diào)度時最佳的系統(tǒng)狀態(tài)具有以下條件：

（1）整個系統(tǒng)具有相對短的處理時間；

（2）整個系統(tǒng)的吞吐量在任務(wù)執(zhí)行時是較大的。

采用一個函數(shù)W（yi，li，fi），它可以反映整個系統(tǒng)處理任務(wù)的能力：

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

步驟1：在進行Web的集群服務(wù)時，對于M個服務(wù)器F=｛f1，f2，…，fM｝，根據(jù)式（8）計算其當(dāng)前的執(zhí)行能力。

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

σij=W（yi，li，fj）ζ（fj）（n（fj）（loadj））（9）式中：ζ（fj）表示服務(wù)器 fj的最大吞吐量；loadj表示服務(wù)器 fj當(dāng)前的負載量；n（fj）表示當(dāng)前服務(wù)器 fj所接收的任務(wù)數(shù)量。

4　實驗仿真及分析

4.1仿真環(huán)境及場景設(shè)置

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

4.2聚類時間

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

圖2　聚類時間性能比較圖

4.3聚類精確度

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

圖3　聚類精確度性能比較圖

4.4服務(wù)執(zhí)行成功率

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

圖4　服務(wù)執(zhí)行成功率性能比較圖

4.5聚類失真度

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

圖5　聚類失真度性能比較圖

從圖5中可以看出，隨著聚類數(shù)量的增多，聚類算法的失真程度會逐漸降低，這是因為在整體數(shù)據(jù)量不變的情況下，根據(jù)數(shù)據(jù)的特性劃分的聚類數(shù)更多，則每個聚類所包含的范圍越小，在某一個聚類中的數(shù)據(jù)就越接近所屬聚類的代表點。圖5中本文算法的聚類失真度最低達到了5.4%，而文獻［14］算法達到了8.3%，文獻［15］達到了7.1%，相比較這兩個對比算法，本文算法的失真度更小，聚類的效果就越好。

5　結(jié)論

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

［1］俞忻峰.社交網(wǎng)絡(luò)挖掘方案研究［J］.現(xiàn)代電子技術(shù)，2015，38 （4）：25?29.

［2］羅鳳娥，張成偉.基于時序數(shù)據(jù)挖掘的航班延誤預(yù)測分析［J］.現(xiàn)代電子技術(shù)，2014，37（24）：52?55.

［3］李靜.基于數(shù)據(jù)挖掘技術(shù)的電子商務(wù)CRM研究［J］.現(xiàn)代電子技術(shù)，2015，38（11）：126?128.

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

［5］劉銘，劉秉權(quán)，劉遠超.面向信息檢索的快速聚類算法［J］.計算機研究與發(fā)展，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 adap?tive particle swarm optimization for data clustering［J］.Interna?tional 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服務(wù)聚類方法［J］.計算機研究與發(fā)展，2013，50（z1）：205?210.

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

［11］HATAMLOU A.Black hole：A new heuristic optimization ap?proach 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 technolo?gies，2014，42（14）：82?98.

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

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

［15］MAULIK Saha Indrajit.Incremental learning based multiob?jective fuzzy clustering for categorical data［J］.Information sciences，2014，267：35?57.

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）

In order to achieve fast clustering of Web service request data and improve accuracy of the clustering，a Web da?ta 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 com?plexity of Web data is reduced first in data compression form，and then the time series data clustering based on service time sim?ilarity 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?dimen?sional data grid?based hierarchical clustering algorithm and multi?objective fuzzy clustering algorithm based on incremental learn?ing，the algorithm proposed in this paper has obtained better results in the aspects of time clustering，clustering accuracy，suc?cess rate of all service execution and distortion degree.

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

10.16652/j.issn.1004?373x.2016.14.002

TN911?34；TP393

A

1004?373X（2016）14?0004?05

2015?11?17

國家自然科學(xué)基金（61272382）；廣東省科技計劃項目（2012B0101100037）；廣東省高等學(xué)校科技創(chuàng)新資助項目（2013kjcx0132）

陳珂（1964—），男，廣東韶關(guān)人，副教授。主要研究領(lǐng)域為Web數(shù)據(jù)挖掘、計算智能、計算機網(wǎng)絡(luò)。

柯文德（1976—），男，廣東興化人，教授，博士。主要研究領(lǐng)域為人工智能、智能機器人。

許波（1986—），男，講師，博士。主要研究領(lǐng)域為計算智能、機器學(xué)習(xí)。