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

陳　珂，柯文德，許　波

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

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

陳珂，柯文德，許波

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

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

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

0　引言

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

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

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

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

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

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

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

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

定義3相似信息。兩個(gè)時(shí)間序列之間的相似性是基于它們的子序列之間的相似性。

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

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

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

2　增量式時(shí)間序列聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）整個(gè)系統(tǒng)具有相對(duì)短的處理時(shí)間；

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

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

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

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

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

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

4　實(shí)驗(yàn)仿真及分析

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

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

4.2聚類時(shí)間

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

圖2　聚類時(shí)間性能比較圖

4.3聚類精確度

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

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

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

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

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

4.5聚類失真度

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

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

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

5　結(jié)論

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

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

［2］羅鳳娥，張成偉.基于時(shí)序數(shù)據(jù)挖掘的航班延誤預(yù)測(cè)分析［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)工程理論與實(shí)踐，2014，34（9）：2417?2431.

［5］劉銘，劉秉權(quán)，劉遠(yuǎn)超.面向信息檢索的快速聚類算法［J］.計(jì)算機(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］.計(jì)算機(jī)研究與發(fā)展，2013，50（z1）：205?210.

［10］黃德才，李曉暢.基于相對(duì)密度的混合屬性數(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

國(guó)家自然科學(xué)基金（61272382）；廣東省科技計(jì)劃項(xiàng)目（2012B0101100037）；廣東省高等學(xué)?？萍紕?chuàng)新資助項(xiàng)目（2013kjcx0132）

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

柯文德（1976—），男，廣東興化人，教授，博士。主要研究領(lǐng)域?yàn)槿斯ぶ悄堋⒅悄軝C(jī)器人。

許波（1986—），男，講師，博士。主要研究領(lǐng)域?yàn)橛?jì)算智能、機(jī)器學(xué)習(xí)。