基于編輯距離的序列聚類算法的優(yōu)化

孫啟航，楊鶴標(biāo)

(江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

1 概 述

序列聚類的基礎(chǔ)問(wèn)題就是序列的相似性度量[1]。直觀看來(lái)，當(dāng)序列中對(duì)應(yīng)位置的對(duì)象的值相似時(shí)，才被認(rèn)為是相似的。在現(xiàn)有的研究中，根據(jù)度量范圍的不同，序列相似性度量算法可分為如下兩類：

(1)局部序列相似性度量。在生物信息學(xué)研究中，DNA序列或蛋白質(zhì)序列中往往存在著最能體現(xiàn)序列整體特征的關(guān)鍵片段，這些關(guān)鍵片段在刻畫(huà)序列特點(diǎn)時(shí)占有相當(dāng)高的比重，因此可以用來(lái)度量序列的相似性[2]?；诰植啃蛄械南嗨菩远攘克惴ǎ诵木褪且崛〕瞿鼙碚鞑煌蛄械木植啃蛄?，從而在局部序列的基礎(chǔ)上度量全序列的整體相似性。

(2)全序列相似性度量。序列的特征通過(guò)整個(gè)序列來(lái)體現(xiàn)，這時(shí)度量序列的相似性必須從序列的全局考慮。例如有5個(gè)患者P1、P2、P3、P4、P5在不同時(shí)間點(diǎn)的臨床行為序列如圖1所示。

PatientP1’sclinicalsequence:14 21 30 34 26 67 90 45 70 29PatientP2’sclinicalsequence:33 21 62 92 17 76 19 43 70 29PatientP3’sclinicalsequence:33 95 62 34 17 67 19 45 57 56PatientP4’sclinicalsequence:72 72 54 54 46 68 53 70 57 56PatientP5’sclinicalsequence:11 38 59 80 22 22 16 65 57 56

圖1 患者的臨床行為序列

盡管患者P3與患者P4、P5的臨床行為序列有一致的頻繁子模式57、56，但是患者P3與P2、P3與P1、P1與P2在對(duì)應(yīng)時(shí)刻的相同醫(yī)療行為數(shù)量分別為4,3,3，因此P1、P2、P3整體上的臨床行為更相似。編輯距離的相似性度量算法能夠準(zhǔn)確反映序列全局相似度[3]，但其時(shí)間復(fù)雜度相對(duì)較高。

2 相關(guān)技術(shù)

K均值是基于劃分的聚類方法[4-6]，該算法首先指定K值，并在數(shù)據(jù)集中選擇K個(gè)點(diǎn)作為簇的初始質(zhì)心。然后將每條序列都分配到距離它最近的質(zhì)心，當(dāng)完成一遍劃分后，更新每個(gè)簇的質(zhì)心。重復(fù)分配序列的過(guò)程，直到質(zhì)心不再變化，聚類結(jié)果才是穩(wěn)定的，最終所有數(shù)據(jù)都被劃分到K個(gè)簇中。

相比于K均值聚類，二分K均值[7]避免了兩個(gè)序列之間距離的直接計(jì)算，時(shí)間復(fù)雜度是線性增長(zhǎng)的。序列的二分K均值聚類算法可作如下描述[8]：把所有序列初始化為一個(gè)簇加入簇表；從簇表中選取一個(gè)總體相似度水平最低的簇C；利用K-means方法將簇C二分為C1和C2；將C1和C2加入簇表中；重復(fù)以上步驟，直到產(chǎn)生K個(gè)簇時(shí)停止。

編輯距離[9]是計(jì)算兩個(gè)序列之間相似度的算法。求解的常用思路是動(dòng)態(tài)規(guī)劃法[10]，即對(duì)于兩個(gè)序列A={a1,a2,…,am}和B={b1,b2,…,bn},用dis(i,j)表示序列A的前i(0≤i≤m)個(gè)項(xiàng)通過(guò)編輯轉(zhuǎn)化為序列B的前j(0≤j≤n)個(gè)項(xiàng)所需的最小代價(jià)。序列A和B的相似度計(jì)算方法具有子結(jié)構(gòu)和子問(wèn)題重疊性質(zhì)，可以通過(guò)不斷地遞歸求解dis(i,j)最優(yōu)解得到。具體的相似度計(jì)算步驟如下：

(1)參數(shù)初始化。

distance(A，B)=dis(m,n)；dis(0,0)=0；

dis(0,j)=j；dis(i,0)=i

(2)遞歸計(jì)算序列相似度。

1≤i≤m,1≤j≤n

(1)

其中，當(dāng)ai=bi時(shí)，k(i,j)=0,否則k(i,j)=1。

通過(guò)在動(dòng)態(tài)規(guī)劃矩陣中對(duì)式(1)的計(jì)算，矩陣最右下角的dis(m,n)可以通過(guò)不斷得到子問(wèn)題的最優(yōu)解來(lái)迭代解決，最終解得兩個(gè)序列的編輯距離。

3 帶剪枝策略的序列聚類算法

3.1 基于全序列比對(duì)的編輯距離上下界

定義1：序列是由項(xiàng)表中的項(xiàng)目組成的有序項(xiàng)目集合，記為S={a1,a2,…,an},其中ak∈E(1≤k≤n)，ak稱為序列中的項(xiàng)。T為臨床行為項(xiàng)目表中項(xiàng)目的個(gè)數(shù)，T=|E|。序列S的長(zhǎng)度為n，n=|S|。

(2)

標(biāo)簽距離和編輯距離的關(guān)系如定理1所示，這給后文聚類算法的剪枝策略提供了理論基礎(chǔ)。

定理1：對(duì)于給定的兩個(gè)臨床行為序列S1和S2，標(biāo)簽距離TD(S1,S2)與兩條序列的長(zhǎng)度之和|S1|+|S2|分別是編輯距離ED(S1,S2)的下限和上限，即TD(S1,S2)≤ED(S1,S2)≤|S1|+|S2|。

TD(S1,S2)≤ED(S1,S2)的證明見(jiàn)文獻(xiàn)[11]。下面證明ED(S1,S2)≤|S1|+|S2|。

在S1和S2的求解矩陣中，通過(guò)動(dòng)態(tài)規(guī)劃將S1編輯為S2時(shí)，從矩陣最右下角的(m,n)位置開(kāi)始回溯，直到(0,0)時(shí)終止。每一次回溯或者是縱坐標(biāo)減1，或者是橫坐標(biāo)減1，或者是橫坐標(biāo)和縱坐標(biāo)均減1，最多經(jīng)過(guò)m+n步可以走到(0,0)坐標(biāo)，所以ED(S1,S2)≤|S1|+|S2|。故可推出定理1,TD(S1,S2)≤ED(S1,S2)≤|S1|+|S2|。

由定理1可以推出下列結(jié)論：

推論1：給定三個(gè)臨床行為序列S1、S2、S3，若TD(S1,S2)≥|S1|+|S3|,則有ED(S1,S2)≥ED(S1,S3)。由定理1得：ED(S1,S2)≥TD(S1,S2)≥|S1|+|S3|≥ED(S1,S3)，故可得推論1。

定理2：給定三條臨床序列S1、S2、S3，S1與S2的編輯距離ED(S1,S2)已知，若ED(S1,S2)≥2×(|S1|+|S3|)，則ED(S1,S3)≤ED(S2,S3)。

證明：由于|S1|+|S3|≥ED(S1,S3)，所以ED(S1,S2)≥2(|S1|+|S3|)≥2ED(S1,S3)，通過(guò)移項(xiàng)得到ED(S1,S2)-ED(S1,S3)≥ED(S1,S3)。由編輯距離的定義可知其滿足三角不等式兩邊之差小于第三邊[12]，因而有ED(S2,S3)≥ED(S1,S2)-ED(S1,S3)，所以ED(S2,S3)≥ED(S1,S3)。

計(jì)算序列編輯距離的時(shí)間復(fù)雜度為O(m×n)[13]，計(jì)算標(biāo)簽距離的時(shí)間復(fù)雜度同為O(m×n)。對(duì)于待劃分的序列和兩個(gè)簇的質(zhì)心，如果符合推論1和定理2中的條件，則可以僅通過(guò)計(jì)算標(biāo)簽距離來(lái)劃分?jǐn)?shù)據(jù)點(diǎn),從而有效降低序列之間編輯距離的計(jì)算量。

3.2 基于前綴子序列的相似度比較

若推論1和定理2中的兩個(gè)前提條件都不能滿足，也有可能不需要進(jìn)行兩條序列的全序列比較，轉(zhuǎn)而通過(guò)計(jì)算序列的部分編輯距離來(lái)衡量它們的臨近度。對(duì)于給定的兩個(gè)序列A={a1,a2,…,am}和B={b1,b2,…,bn}，假設(shè)其動(dòng)態(tài)規(guī)劃矩陣為T(mén)(T為一個(gè)m+1行、n+1列的矩陣)，則可以推導(dǎo)出下面的性質(zhì)：

性質(zhì)1：|dis(i,j)-dis(i-Δi,j-Δj)|≤1。

其中，dis(i,j)表示動(dòng)態(tài)規(guī)劃矩陣中第i行第j列的值，0≤i≤m,0≤j≤n，Δi,Δj∈(0,1),并且i-Δi≥0,j-Δj≥0。

證明：計(jì)算兩條序列編輯距離的動(dòng)態(tài)規(guī)劃矩陣是由m+n-1個(gè)初始狀態(tài)dis(i,j)=0、dis(0,j)=j,dis(i,0)=i(0≤i≤m,0≤j≤n)和式(1)生成的，若ai=bj，則k(i,j)=0，否則k(i,j)=1。由歸納法證明dis(i,j)-dis(i-Δi,j-Δj)不會(huì)超過(guò)1，性質(zhì)1得證。

由性質(zhì)1表明，在反映編輯距離的動(dòng)態(tài)規(guī)劃矩陣中，任何一個(gè)坐標(biāo)對(duì)應(yīng)的值減去緊鄰其左邊、上邊或者左上角的值，只會(huì)有0和1兩種結(jié)果，不會(huì)超過(guò)1。圖2所示的動(dòng)態(tài)規(guī)劃矩陣揭示了性質(zhì)1，且由性質(zhì)1可以證明定理3。

圖2 序列animals與bicycle的動(dòng)態(tài)規(guī)劃矩陣

定理3：對(duì)于給定的兩條序列A={a1,a2,…,am}和B={b1,b2,…,bn}(m>n)，其最小編輯代價(jià)的動(dòng)態(tài)規(guī)劃矩陣為T(mén)，則當(dāng)i≤j≤n時(shí)，存在dis(i,i)≤dis(j,j)。

證明定理3只要證明dis(i,i)≤dis(i+1,i+1)即可。根據(jù)動(dòng)態(tài)規(guī)劃矩陣T的生成過(guò)程，可以對(duì)以下三種情況進(jìn)行分析：

(1)若dis(i+1,i+1)=dis(i,i)+k(i+1,i+1)，因?yàn)閗(i+1,i+1)的取值為0或1，所以dis(i+1,i+1)≥dis(i,i)。

(2)若dis(i+1,i+1)=dis(i+1,i)+1，根據(jù)性質(zhì)1可得|dis(i+1,i)-dis(i,i)|≤1。分三種情況討論：

①dis(i+1,i)-dis(i,i)=1，此時(shí)dis(i+1,i+1)=dis(i,i)+2，dis(i,i)

②dis(i+1,i)-dis(i,i)=0，此時(shí)dis(i+1,i+1)=dis(i,i)+1，dis(i,i)

③dis(i+1,i)-dis(i,i)=-1，此時(shí)dis(i+1,i+1)=dis(i,i)。

(3)若dis(i+1,i+1)=dis(i+1,i)+1，參考情況(2)中的證明過(guò)程，仍可證得dis(i+1,i+1)≥dis(i,i)。

綜上所述，有dis(i,i)≤dis(i+1,i+1)。故定理3得證。

定理3表明，在對(duì)兩個(gè)序列進(jìn)行全序列編輯距離的計(jì)算時(shí)，其長(zhǎng)度相等的前綴子序列具有隨著子序列中項(xiàng)的增加而編輯距離非遞減的特性。例如圖2中兩種不同灰度的陰影部分所顯示的，有ED(an,bi)≤ED(ani,bic)。

在臨床行為異常檢測(cè)中，需要將待檢序列S和兩個(gè)簇的質(zhì)心C1、C2進(jìn)行編輯距離的比較，若已知S和C1的編輯距離ED(S,C1)，又知道S和C2某個(gè)等長(zhǎng)前綴子序列的編輯距離比ED(S,C1)大，那么不用計(jì)算S和C2的全序列編輯距離就可以將S劃入C1所代表的簇中。對(duì)于長(zhǎng)度不同的臨床序列，通過(guò)定理4，當(dāng)在聚類過(guò)程中的編輯距離比較時(shí)，其中一個(gè)編輯距離只需求出等長(zhǎng)前綴子序列的部分即可。

定理4：設(shè)有三條序列S、P、Q，其中S={s1,s2,…,sm}，P={p1,p2,…,pn}(m>n)，S作為待分配序列需要比較它與P、Q的編輯距離的大小。若S、Q的編輯距離ED(S,Q)已知,且存在一個(gè)k≤n使得不等式ED(s1,s2,…,sk,p1,p2,…,pk)-(m-n)≥ED(S,Q)成立，則不等式ED(S,P)≥ED(S,Q)成立。

證明：設(shè)S和P的最優(yōu)動(dòng)態(tài)規(guī)劃矩陣為T(mén)，將性質(zhì)1中的絕對(duì)值符號(hào)去掉可以得到-1≤dis(i,j)-dis(i-Δi,j-Δj)≤1，故可以推得dis(m,n)+1≥dis(m-1,n)，dis(m-1,n)+1≥dis(m-2,n)，…，dis(n+1,n)+1≥dis(n,n)，將這m-n個(gè)不等式合并可得dis(m,n)≥dis(n,n)-(m-n)。根據(jù)定理3，若存在一個(gè)k≤n，則有dis(k,k)≤dis(n,n)。因此，若k≤n且ED(s1,s2,…,sk,p1,p2,…,pk)-(m-n)≥ED(S,Q)成立，可得ED(S,P)=dis(m,n)≥dis(n,n)-(m-n)≥dis(k,k)-(m-n)≥ED(S,Q)。

定理4的推導(dǎo)表明，在比較待檢序列到簇的距離時(shí)，有時(shí)并不需要計(jì)算S和Q的全序列編輯距離就可以與ED(S,Q)進(jìn)行比較，這大大降低了二分K均值算法在計(jì)算臨床序列在計(jì)算編輯距離上的開(kāi)銷。

3.3 序列聚類算法的實(shí)現(xiàn)過(guò)程

對(duì)于數(shù)據(jù)集中的t條序列，其平均長(zhǎng)度為L(zhǎng)，在以編輯距離為臨近度度量的前提下，如果采用兩兩比較的方式來(lái)計(jì)算序列的編輯距離，算法的時(shí)間復(fù)雜度為O(t2L2)，這嚴(yán)重影響了算法的聚類效率。為降低算法的復(fù)雜度，減少聚類時(shí)間，從以下幾個(gè)方面來(lái)考慮：

(1)在聚類算法的選取上，選取二分K均值的方法。相比于K均值聚類，二分K均值避免了兩個(gè)序列之間距離的直接計(jì)算，時(shí)間復(fù)雜度與數(shù)據(jù)集大小不是呈指數(shù)增長(zhǎng)，而是線性增長(zhǎng)的。

(2)在處理簇間數(shù)據(jù)點(diǎn)的移動(dòng)時(shí)，采取計(jì)算序列和簇的標(biāo)簽距離的方式避免不必要的計(jì)算。假設(shè)在應(yīng)用二分K均值算法時(shí)，當(dāng)前的兩個(gè)質(zhì)心是C1和C2，S表示序列數(shù)據(jù)集中的任意一條序列，且兩個(gè)質(zhì)心之間的編輯距離ED(C1，C2)已知。在尋找離S點(diǎn)最近的簇時(shí)，需要計(jì)算ED(S,C1)和ED(S,C2)并比較這兩者的大小。由推論1和定理2可知，當(dāng)Max{TD(S,C1)，ED(C1,C2)/2}≥|C2|+|S|時(shí)，ED(S,C2)≤ED(S,C1)，序列S放入C2所代表的簇；當(dāng)Max{TD(S,C2)，ED(C1,C2)/2}≥|C1|+|S|時(shí)，有ED(S,C1)≤ED(S,C2)，序列S放入C1所代表的簇。

若上述條件都不滿足，才需要計(jì)算ED(S,C1)和ED(S,C2)的值。但是，也有可能只需計(jì)算S與其中一個(gè)質(zhì)心的等長(zhǎng)前綴子序列的編輯距離而不必計(jì)算全部就可以比較它們的大小。步驟(3)的剪枝策略描述了S到兩個(gè)質(zhì)心的編輯距離比較方法。

(3)對(duì)于臨床行為序列數(shù)據(jù)集中的每一個(gè)序列S，創(chuàng)建一個(gè)維數(shù)為2T的概貌向量Vs={n1,n2,…,nT,d1,d2,…,dT}，其中ni(1≤i≤T)是S的標(biāo)簽向量中的值，表示臨床行為項(xiàng)表中第i個(gè)項(xiàng)在S中出現(xiàn)的次數(shù)，di表示序列S中的項(xiàng)ei到序列第一個(gè)項(xiàng)的距離之和。概貌向量在序列標(biāo)簽的基礎(chǔ)上增加了反映序列中項(xiàng)的位置信息的維度，如果兩條臨床序列差異很大，它們所對(duì)應(yīng)的概貌向量的曼哈頓距離也會(huì)很大[14]。

分析定理4可以發(fā)現(xiàn)，若想通過(guò)該定理減少編輯距離的計(jì)算復(fù)雜度，需要事先知道待檢序列與哪一個(gè)簇的質(zhì)心的編輯距離較小，通過(guò)計(jì)算三個(gè)序列概貌向量的曼哈頓距離來(lái)幫助判斷。序列概貌向量的曼哈頓距離在很大概率上能幫助確定編輯距離的大小，從而有效決定待檢臨床序列與簇的質(zhì)心編輯距離的計(jì)算順序，最終達(dá)到簡(jiǎn)化計(jì)算序列臨近度時(shí)間開(kāi)銷的目的。

3.4 帶剪枝策略的二分K均值序列聚類算法

綜合上一節(jié)的三點(diǎn)陳述，帶剪枝策略的二分K均值臨床序列聚類算法PSClu(clustering algorithm based on similarity of prefix sequence)描述如下：

算法1：帶剪枝策略的臨床序列聚類算法PSClu。

輸入：含有t條臨床行為數(shù)據(jù)序列的數(shù)據(jù)集SequenceSet={S1,S2,…,St},參數(shù)k

輸出：序列的k個(gè)集合

/*起始狀態(tài)下，將原始序列數(shù)據(jù)集SequenceSet初始化為一個(gè)簇并放入簇表ClusterList中，此時(shí)簇的個(gè)數(shù)ClusterCount=1*/

ClusterList←SequenceSet；ClusterCount=1；

for(i=1;i≤t;i++)

將序列數(shù)據(jù)集SequenceSet掃描一趟，生成Si的標(biāo)簽T(Si)以及概貌向量VSi;

end for;

while(ClusterCount

從簇表ClusterList中選一個(gè)內(nèi)部相似程度最差的簇C；

分別將簇C中的最長(zhǎng)序列和最短序列作為兩個(gè)簇的質(zhì)心CO1和CO2；

計(jì)算兩個(gè)質(zhì)心的編輯距離ED(CO1,CO2)以及概貌向量VCO1和VCO2；

while(簇C中所有序列不會(huì)在CO1和CO2兩個(gè)質(zhì)心代表的簇之間發(fā)生移動(dòng))

for(屬于簇C的每一條序列S’)

if(Max{TD(S’,CO1),ED(CO1,CO2)/2}≥|CO2|+|S’|)

將序列S’放到以CO2為質(zhì)心的簇C2中；

else if(Max{TD(S’,CO2),ED(CO1,CO2)/2}≥|CO1|+|S’|)

將序列S’放到以CO1為質(zhì)心的簇C1中；

else if(L1(VS',VCO1)≤L1(VS',VCO2))

計(jì)算ED(S’,CO1);

if(S’和CO2的等長(zhǎng)前綴子序列滿足定理4前提條件中的不等式)

終止S’與CO2編輯距離的計(jì)算，并將序列S’放到以CO1為質(zhì)心的簇C1中；

else

繼續(xù)利用動(dòng)態(tài)規(guī)劃矩陣算完ED(S’,CO2),然后確定將S’放到哪個(gè)簇；

else

計(jì)算ED(S’,CO2);

if(S’和CO1的等長(zhǎng)前綴子序列滿足定理4前提條件中的不等式)

終止S’與CO1編輯距離的計(jì)算，并將序列S’放到以CO2為質(zhì)心的簇C2中；

else

繼續(xù)利用動(dòng)態(tài)規(guī)劃矩陣算完ED(S’,CO1),然后確定將S’放到哪個(gè)簇；

end for;

更新兩個(gè)簇的質(zhì)心CO1和CO2；

end while;

ClusterCount=ClusterCount+1；

將C1和C2添加到簇表ClusterList中；

end while;

4 實(shí)驗(yàn)結(jié)果分析與驗(yàn)證

為了驗(yàn)證PSClu算法在對(duì)序列進(jìn)行聚類分析時(shí)的性能，使用Java語(yǔ)言編碼，并在人工合成的序列數(shù)據(jù)集上與其他算法進(jìn)行對(duì)比實(shí)驗(yàn)。所有實(shí)驗(yàn)均在主頻為2.8 GHz，操作系統(tǒng)為Windows7，可用內(nèi)存為3.24 G的PC機(jī)上實(shí)現(xiàn)。

4.1 實(shí)驗(yàn)數(shù)據(jù)集的生成

類似文獻(xiàn)[15]中實(shí)驗(yàn)所使用的方法，該課題合成數(shù)據(jù)集的方法如下：給定項(xiàng)表E(表中項(xiàng)的個(gè)數(shù)設(shè)定為10，用a到j(luò)十個(gè)英文字母表示)，先隨機(jī)生成k條長(zhǎng)度不同的根序列，并以這k條根序列代表k個(gè)簇，然后在每條根序列的基礎(chǔ)上，通過(guò)隨機(jī)變換序列長(zhǎng)度和其中的項(xiàng)來(lái)合成其他全部序列。合成序列的特征通過(guò)如下的標(biāo)識(shí)符進(jìn)行描述：K表示合成的數(shù)據(jù)集中簇的個(gè)數(shù)，C表示數(shù)據(jù)集中序列的個(gè)數(shù)，L表示最短根序列的長(zhǎng)度，△表示其他根序列長(zhǎng)度在最短根序列長(zhǎng)度的基礎(chǔ)上的遞增度，VL表示根序列所代表的簇中的其他序列長(zhǎng)度相對(duì)于根序列變化的百分率約束，VP表示根序列所代表的簇中的各序列變化的元素相對(duì)于根序列變化百分率的約束。例如，對(duì)于數(shù)據(jù)集K6C6000 L50△50VL5VP10的解釋就是，該數(shù)據(jù)集中有6個(gè)簇，一共6 000條序列分布在這6個(gè)簇中，因?yàn)樽疃谈蛄械拈L(zhǎng)度為50，所以其他根序列的長(zhǎng)度在其基礎(chǔ)上以50位單位遞增，所以6條根序列的長(zhǎng)度分別為50,100,150,200,250,300。每個(gè)根序列S所代表的簇中，其他序列都是通過(guò)變化S長(zhǎng)度(隨機(jī)在任意位置上添加或刪除項(xiàng))的至多5%以及改變項(xiàng)(隨機(jī)將序列中的任意項(xiàng)替換成其他項(xiàng))的至多10%而合成的。

4.2 聚類效率的比較

對(duì)這兩種算法進(jìn)行測(cè)試的四組合成數(shù)據(jù)集特征如表1所示。對(duì)于這四組數(shù)據(jù)集，控制住其他特征不變，將參數(shù)C由1 000增長(zhǎng)到10 000。

表1 合成的四組序列數(shù)據(jù)集

PSClu與EDClu算法執(zhí)行的時(shí)間對(duì)比見(jiàn)圖3。

圖3 EDCluster與PSClu聚類時(shí)間對(duì)比

從圖中可以看出，帶剪枝策略、使用序列局部相似性來(lái)代替全局相似性的PSClu算法的運(yùn)行時(shí)間比不帶剪枝策略的EDClu要少。

5 結(jié)束語(yǔ)

針對(duì)序列聚類算法中序列相似性度量算法的不足，提出了PSClu序列聚類算法。通過(guò)編輯距離的上下界以及前綴子序列的相似性計(jì)算減少序列之間兩兩編輯距離的計(jì)算。實(shí)驗(yàn)表明，PSClu算法在時(shí)間效率上明顯優(yōu)于EDClu算法。由于在最差的情況下，PSClu的時(shí)間復(fù)雜度仍然是與序列均長(zhǎng)L呈平方項(xiàng)時(shí)間復(fù)雜度的，今后的研究目標(biāo)將采用隨機(jī)近似的方法進(jìn)一步降低PSClu算法的時(shí)間復(fù)雜度。

[1] 戴東波,湯春蕾,熊 赟.基于整體和局部相似性的序列聚類算法[J].軟件學(xué)報(bào),2010,21(4):702-717.

[2] 唐東明,朱清新,楊 凡,等.一種有效的蛋白質(zhì)序列聚類分析方法[J].軟件學(xué)報(bào),2011,22(8):1827-1837.

[3] WAGNER R A,FISCHER M J.The string-to-string correction problem[J].Journal of the ACM,1974,21(1):168-173.

[4] 袁 方,周志勇,宋 鑫.初始聚類中心優(yōu)化的k-means算法[J].計(jì)算機(jī)工程,2007,33(3):65-66.

[5] 王 勇,唐 靖,饒勤菲,等.高效率的K-means最佳聚類數(shù)確定算法[J].計(jì)算機(jī)應(yīng)用,2014,34(5):1331-1335.

[6] CELEBI M E,KINGRAVI H A,VELA P A.A comparative study of efficient initialization methods for the k-means clustering algorithm[J].Expert Systems with Applications,2013,40(1):200-210.

[7] HAMERLY G,ELKAN C.Alternatives to the k-means algorithm that find better clusterings[C]//Proceedings of the eleventh international conference on information and knowledge management.New York,NY,USA:ACM,2002:600-607.

[8] 戴 紅,常子冠,于 寧.數(shù)據(jù)挖掘?qū)д揫M].北京:清華大學(xué)出版社,2015.

[9] ILIOPOULOS C S,RAHMAN M S.New efficient algori-thms for the LCS and constrained LCS problems[J].Information Processing Letters,2008,106(1):13-18.

[10] SAKOE H,CHIBA S.Dynamic programming algorithm optimization for spoken word recognition[M].[s.l.]:Morgan Kaufmann Publishers Inc.,1990.

[11] BANG K S,LU H,SIAU K.An efficient index structure for spatial databases[J].Journal of Database Management,1996,7(3):3-16.

[12] RISTAD E S,YIANILOS P N.Learning string-edit distance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1998,20(5):522-532.

[13] 姜 華,韓安琪,王美佳,等.基于改進(jìn)編輯距離的字符串相似度求解算法[J].計(jì)算機(jī)工程,2014,40(1):222-227.

[14] 劉瑩霞.鏈碼技術(shù)和聚類分析在基因序列中的應(yīng)用[D].廣州:華南理工大學(xué),2012.

[15] AGRAWAL R, SRIKANT R. Mining sequential patterns[C]//Eleventh international conference on data engineering.Washington,DC,USA:IEEE Computer Society,1995:3-14.