基于簇中心群的時(shí)間序列數(shù)據(jù)分類(lèi)方法

李海林，萬(wàn)?；?/p>

(1. 華僑大學(xué)信息管理系 福建 泉州 362021；2. 華僑大學(xué)現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心 福建 廈門(mén) 361021)

基于簇中心群的時(shí)間序列數(shù)據(jù)分類(lèi)方法

李海林，萬(wàn)?；?/p>

(1. 華僑大學(xué)信息管理系 福建 泉州 362021；2. 華僑大學(xué)現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心 福建 廈門(mén) 361021)

分類(lèi)算法是時(shí)間序列數(shù)據(jù)挖掘中極為重要的任務(wù)和技術(shù)，該文提出一種基于簇中心群的時(shí)間序列數(shù)據(jù)分類(lèi)方法。該方法根據(jù)時(shí)間序列訓(xùn)練數(shù)據(jù)集中的類(lèi)別標(biāo)簽進(jìn)行簇劃分，利用近鄰傳播算法分別對(duì)每個(gè)簇進(jìn)行中心代表點(diǎn)選擇，構(gòu)造出各代表點(diǎn)的代表對(duì)象集；然后借助基于動(dòng)態(tài)時(shí)間彎曲的均值中心方法對(duì)各代表對(duì)象集實(shí)現(xiàn)中心群計(jì)算，結(jié)合改進(jìn)后的K近鄰算法實(shí)現(xiàn)時(shí)間序列數(shù)據(jù)的分類(lèi)。數(shù)值實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)方法相比，新方法具有更好的分類(lèi)效果和計(jì)算性能。

近鄰傳播; 分類(lèi)算法; 數(shù)據(jù)挖掘; 動(dòng)態(tài)時(shí)間彎曲; 時(shí)間序列

時(shí)間序列是一種與時(shí)間相關(guān)的數(shù)值型數(shù)據(jù)，基于時(shí)間序列的數(shù)據(jù)挖掘與分析成為目前數(shù)據(jù)研究領(lǐng)域中最具有挑戰(zhàn)性的十大問(wèn)題之一[1]。在時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域中，特別是金融時(shí)間序列數(shù)據(jù)存在時(shí)間高維性，使得傳統(tǒng)分類(lèi)算法不能直接有效地對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行分類(lèi)，有礙于金融數(shù)據(jù)市場(chǎng)分析。部分學(xué)者通過(guò)數(shù)據(jù)降維與特征表示方法將高維時(shí)間序列數(shù)據(jù)挖掘進(jìn)行特征提取，再結(jié)合傳統(tǒng)聚類(lèi)或分類(lèi)算法實(shí)現(xiàn)特征對(duì)象的數(shù)據(jù)分類(lèi)[2-3]。然而，由于數(shù)據(jù)降維和特征表示在一定程度上會(huì)丟失部分重要數(shù)據(jù)信息，傳統(tǒng)方法不能很好地對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行有效分類(lèi)。有成果研究表明[4]，最近鄰分類(lèi)算法是時(shí)間序列數(shù)據(jù)分類(lèi)最為有效的方法，它能較好地實(shí)現(xiàn)時(shí)間序列數(shù)據(jù)分類(lèi)和預(yù)測(cè)。傳統(tǒng)分類(lèi)算法的分類(lèi)質(zhì)量和計(jì)算效率在一定程度上取決于前期數(shù)據(jù)處理中特征表示和相似性度量等方法的性能[5-6]?；趧?dòng)態(tài)時(shí)間彎曲的最近鄰分類(lèi)方法是一種通過(guò)匹配異步形態(tài)相似性來(lái)對(duì)具有共同波動(dòng)特征的時(shí)間序列數(shù)據(jù)進(jìn)行聚類(lèi)或分類(lèi)，它能夠提高最近鄰方法的分類(lèi)質(zhì)量，但其平方階的時(shí)間復(fù)雜度在一定程度上影響了其在高維時(shí)間序列數(shù)據(jù)挖掘中的應(yīng)用效果[7]。

鑒于基于動(dòng)態(tài)時(shí)間彎曲距離的最近鄰算法在時(shí)間序列數(shù)據(jù)分類(lèi)中重要性和有效性[8]，本文從分類(lèi)質(zhì)量和效率兩個(gè)角度出發(fā)，提出一種基于簇中心群的時(shí)間序列分類(lèi)算法。該方法利用近鄰傳播聚類(lèi)算法對(duì)訓(xùn)練集中的每個(gè)簇進(jìn)行代表點(diǎn)計(jì)算，并找到各代表點(diǎn)所對(duì)應(yīng)的被代表對(duì)象集，利用基于動(dòng)態(tài)時(shí)間彎曲的均值中心來(lái)描述每個(gè)被代表對(duì)象集，最后結(jié)合改進(jìn)后的K近鄰算法來(lái)討論在不同K值下的分類(lèi)情況。數(shù)值實(shí)驗(yàn)結(jié)果與分析表明，新方法具有更好的時(shí)間序列數(shù)據(jù)分類(lèi)質(zhì)量和計(jì)算性能。

1 相關(guān)理論基礎(chǔ)

1.1 動(dòng)態(tài)時(shí)間彎曲

動(dòng)態(tài)時(shí)間彎曲(dynamic time warping, DTW)是時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域中用來(lái)進(jìn)行相似性度量的一種經(jīng)典方法，其能較好地對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行形態(tài)匹配，進(jìn)而得到反映時(shí)間序列相似性的最小距離[8]。

定義 1 DTW是按一定的規(guī)則從兩條時(shí)間序列數(shù)據(jù)中尋找一條最優(yōu)彎曲路徑,使得該彎曲路徑對(duì)應(yīng)元素之間的距離總和最小，即：

式中，d(pw)=D(i, j)=d(xi, yj)，表示最優(yōu)彎曲路徑P中來(lái)自不同時(shí)間序列數(shù)據(jù)對(duì)應(yīng)元素之間的距離,通常使用歐氏距離來(lái)度量元素之間的距離，即。基于動(dòng)態(tài)規(guī)劃方法和距離矩陣可以求解獲得一條滿(mǎn)足最優(yōu)情況的路徑，使得該路徑中最后一個(gè)元素的累積距離最小，即DTW(X, Y)= R(n, m)，且有：

DTW能夠有效地匹配兩條時(shí)間序列中具有相似性形態(tài)的數(shù)據(jù)點(diǎn)，且代價(jià)矩陣R記錄了最優(yōu)彎曲路徑的方向和反映兩條時(shí)間序列之間相似性的最小距離R(n, m)。由于需要通過(guò)累積代價(jià)矩陣R獲得最優(yōu)彎曲路徑P，使得其計(jì)算時(shí)間復(fù)雜度為O(nm)，不利于較長(zhǎng)時(shí)間序列之間的距離度量。

1.2 近鄰傳播聚類(lèi)

近鄰傳播(affinity propagation, AP)聚類(lèi)[9]是一種基于近鄰信息傳播的聚類(lèi)算法，與其他無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法一樣[10-11]，具有較高效率的分類(lèi)效果。AP聚類(lèi)目的是找出若干個(gè)最優(yōu)代表點(diǎn)，使得其與所代表對(duì)象相似性之和最大。

AP聚類(lèi)算法將所有數(shù)據(jù)對(duì)象視為聚類(lèi)中心，為每個(gè)樣本點(diǎn)建立與其他樣本點(diǎn)的吸引程度信息，即相似性矩陣S，其中任意i和j，相似性矩陣中元素。另外，AP聚類(lèi)算法涉及3個(gè)重要參數(shù)：偏向參數(shù)、代表程度及合適程度。

定義 2 偏向參數(shù)p(i)表示數(shù)據(jù)點(diǎn)i被選作聚類(lèi)中心的傾向程度，初始可以被賦予一個(gè)先驗(yàn)值，由樣本i與其他樣本之間的相似性的中位值來(lái)確定。

定義 3 代表程度r(i, k)是指由樣本點(diǎn)xi指向樣本點(diǎn)xk，表示代表點(diǎn)xk積累的信息，用來(lái)說(shuō)明xk作為xi的類(lèi)代表點(diǎn)的程度。

定義 4 合適程度a(i, k)是從樣本點(diǎn)xk指向樣本點(diǎn)xi, 表示代表點(diǎn)xi積累的信息，用來(lái)表示xi選擇xk作為代表點(diǎn)的合適程度。

在AP聚類(lèi)算法中，通過(guò)代表程度和合適程度兩個(gè)信息量的交替更新，計(jì)算所有數(shù)據(jù)點(diǎn)的代表程度r(i, k)和合適程度a(i, k)之和，取和值最大的xk0作為xi的代表點(diǎn)，。

AP聚類(lèi)算法每次需要重復(fù)交替更新a(i, k)和r(i, k)，使其在不同替代次數(shù)下，數(shù)據(jù)集中被聚類(lèi)所構(gòu)成的代表點(diǎn)不同，直到達(dá)到指定又迭代次數(shù)或最終代表點(diǎn)被確定不變?yōu)橹埂?/p>

1.3 均值中心序列

均值中心序列(DTW barycenter averaging, DBA)[12]是一種基于DTW的時(shí)間序列中心序列，利用啟發(fā)式規(guī)則來(lái)計(jì)算時(shí)間序列數(shù)據(jù)集的中心。其基本思想是，在數(shù)據(jù)集X={X1,X2,…,XN}中，首先通過(guò)初始化中心序列C=[c1, c2,…,cT], 再利用DTW相匹配的數(shù)據(jù)點(diǎn)集合Xi(jai:jbi)；最后計(jì)算所有數(shù)據(jù)點(diǎn)Xi(jai:jbi)(i=1,2,…,N)的平均值作為更新后算法計(jì)算Xi與中心序列C的彎曲路徑iP；對(duì)于每個(gè)i值，根據(jù)iP值從Xi中選取與中心序列中數(shù)據(jù)點(diǎn)cj中心序列cj的值，即：

通過(guò)C′更新C，即C←C′，重新獲得描述時(shí)間序列數(shù)據(jù)集X的均值中心序列C，直到連續(xù)兩次替代中均值中心序列收斂不變?yōu)橹?。基于DTW的均值中心序列能夠反映原始時(shí)間序列數(shù)據(jù)的形態(tài)變化。另外，DBA能夠用不同長(zhǎng)度的中心序列來(lái)描述數(shù)據(jù)集中不等長(zhǎng)時(shí)間序列的形態(tài)變化關(guān)系。

2 新分類(lèi)方法

新分類(lèi)方法首先通過(guò)構(gòu)建訓(xùn)練簇中心群來(lái)描述每個(gè)簇中的對(duì)象特征，結(jié)合基于最近距離的近鄰算法實(shí)現(xiàn)對(duì)象特征集的近鄰分類(lèi)，使其具有較好的分類(lèi)質(zhì)量和計(jì)算性能。

2.1 簇中心群

大數(shù)據(jù)時(shí)代，數(shù)據(jù)量呈現(xiàn)出爆炸式增長(zhǎng)，若用單一中心代表點(diǎn)或均值中心(univariate center object, UCO)來(lái)描述超大型數(shù)據(jù)對(duì)象集，其對(duì)所有數(shù)據(jù)對(duì)象的特征描述力顯得不足。因此，隨著同類(lèi)數(shù)據(jù)量的增長(zhǎng)和數(shù)據(jù)特征的頻繁演化，需要提出一種能夠動(dòng)態(tài)描述同類(lèi)數(shù)據(jù)特征的代表對(duì)象群，使其能夠更好地表達(dá)同類(lèi)數(shù)據(jù)的特征。

定義 5 對(duì)于數(shù)據(jù)集A，若 a0=Rep(A)，則a0為數(shù)據(jù)集A的代表對(duì)象，Rep是一個(gè)求解代表對(duì)象的函數(shù)，它可以是均值、中位數(shù)或眾數(shù)等函數(shù)。

定義 6 簇中心群是對(duì)同類(lèi)數(shù)據(jù)集中的若干個(gè)代表對(duì)象的集合，使得被代表對(duì)象離代表對(duì)象的距離之和最小。形式化講，對(duì)于同一簇中的數(shù)據(jù)對(duì)象集A=[a1, a2,…,aM]，該數(shù)據(jù)集被劃分成K個(gè)子集，B={B1, B2,… ,BK}，簇中心群C=[c1, c2,…,cK]，使得ck=Rep(Bk)，其中 Bi∈A,Bi∩Bj=?且。

簇中心群是對(duì)同一簇中具有較小差異的數(shù)據(jù)子集的代表對(duì)象的集合，與傳統(tǒng)單一代表對(duì)象相比，其具有更好的數(shù)據(jù)特征表現(xiàn)力，可以減小代表對(duì)象與被代表對(duì)象的距離誤差，即：

式中，|Bk|是數(shù)據(jù)子集Bk的模，表示Bk中具有數(shù)據(jù)對(duì)象的個(gè)數(shù)；bki表示Bk數(shù)據(jù)子集中的第i個(gè)數(shù)據(jù)對(duì)象，即有。

為了更好地挑選簇中心群，本文提出一種基于近鄰傳播聚類(lèi)的中心群選擇方法(AP based center group, APCG)。其基本思想為，對(duì)同一類(lèi)簇中所有對(duì)象集使用近鄰傳播聚類(lèi)算法進(jìn)行自動(dòng)聚類(lèi)，生成K個(gè)子簇，獲得每個(gè)子簇的代表對(duì)象，再結(jié)合DBA算法以對(duì)應(yīng)的代表對(duì)象為初始中心序列計(jì)算每個(gè)子簇的均值中心序列，所有子簇產(chǎn)生的均值中心序列集合被視為簇中心群。其算法過(guò)程如下：

基于AP聚類(lèi)的時(shí)序簇中心群方法：C=APCG (A)。

輸入：同簇中時(shí)序數(shù)據(jù)集A=[a1, a2,…,aM], 其中ai表示某一條時(shí)間序列。

輸出：簇中心群C=[c1, c2,…,cK]，ck表示簇中的第k個(gè)中心代表對(duì)象。

1) 根據(jù)AP聚類(lèi)算法，將同一簇劃分成K個(gè)子簇和相應(yīng)的代表對(duì)象，即[B, C′]=AP(A)，B和C'分別表示被劃分的子簇集合和代表對(duì)象集，即應(yīng)子簇Bk的中心序列，即ck=DBA(Bk,)。

3) 重復(fù)步驟2)，計(jì)算所有子簇B的均值中心序列，最終獲得簇中心群C=[c1, c2,…,cK]。 B={B1, B2,…,BK}和C′=[c1′, c2′,…,cK′]，c′K表示第K個(gè)子簇的中心代表對(duì)象。

2) 以cK′為初始中心序列，利用DBA算法計(jì)算對(duì)

通過(guò)AP聚類(lèi)能夠?qū)⑼財(cái)?shù)據(jù)集進(jìn)行自適應(yīng)地劃分成若干子類(lèi)(記為K類(lèi))，每個(gè)子類(lèi)用DBA來(lái)表示對(duì)應(yīng)時(shí)間序列子集的特征。

圖1 基于單一均值和簇中心群的代表對(duì)象

如圖1所示，方塊和星號(hào)組合代表均值中心，子圖b中圓圈和星號(hào)組合代表AP聚類(lèi)算法產(chǎn)生的代表對(duì)象，箭頭起始端表示被代表對(duì)象。若用單一均值代表點(diǎn)表示同一簇中的所有數(shù)據(jù)，其離差較大，代表中心對(duì)數(shù)據(jù)的代表能力較弱；相反，利用簇中心群中的對(duì)象對(duì)更相似的數(shù)據(jù)子集進(jìn)行描述，將會(huì)產(chǎn)生具有較小的離差，說(shuō)明具有較強(qiáng)的代表能力。

2.2 新K近鄰分類(lèi)

在傳統(tǒng)K近鄰分類(lèi)算法中[13]，通過(guò)查找與被分類(lèi)對(duì)象最相似或距離最近的前K個(gè)數(shù)據(jù)對(duì)象，把被分類(lèi)對(duì)象的類(lèi)別歸為這K個(gè)對(duì)象中類(lèi)別眾數(shù)所對(duì)應(yīng)的數(shù)據(jù)類(lèi)標(biāo)簽。如圖2所示，當(dāng)近鄰數(shù)為5時(shí)，被分類(lèi)數(shù)據(jù)點(diǎn)(0,0)將被歸為星號(hào)類(lèi)。然而，從數(shù)據(jù)點(diǎn)之間的距離易知，被分類(lèi)數(shù)據(jù)點(diǎn)與十字類(lèi)2個(gè)數(shù)據(jù)點(diǎn)平均距離要小于與星號(hào)類(lèi)3個(gè)數(shù)據(jù)點(diǎn)的平均距離，說(shuō)明被分類(lèi)數(shù)據(jù)點(diǎn)與十字類(lèi)更相似。因此，傳統(tǒng)最近鄰算法不能很好地處理類(lèi)似情況。特別地，當(dāng)K值較小時(shí)，這種情況更容易發(fā)生。

圖2 K近鄰分類(lèi)算法分析

為了更好地使傳統(tǒng)KNN算法適用于K值較小的時(shí)序分類(lèi)，提出一種基于平均距離的K近鄰分類(lèi)方法(distance based KNN, DKNN)，其具體算法如下。

基于平均距離的K近鄰方法：l=DKNN (o,A,K)。

輸入：時(shí)序o、訓(xùn)練集A和近鄰數(shù)目K。

輸出：時(shí)序o的類(lèi)標(biāo)簽l。

1) 利用DTW計(jì)算時(shí)序o與A中所有時(shí)間序列aj的距離dj∈D，即dj=DTW(o, aj)。

2) 根據(jù)距離向量D找出前K個(gè)距離最小的數(shù)據(jù)對(duì)象集合S，根據(jù)它們的類(lèi)別標(biāo)簽進(jìn)行分組S={S1, S2,… ,Sw}, 且標(biāo)簽記為L(zhǎng)=[l1, l2,…,lw],其中w為K個(gè)近鄰對(duì)象的類(lèi)數(shù)。

3) 計(jì)算每組Si中數(shù)據(jù)對(duì)象與o的平均距離，記=averDist(Si, D )。

2.3 基于簇中心群的K近鄰分類(lèi)方法

提出的基于簇中心群的K近鄰分類(lèi)方法(KNN based on cluster center group, KNN2CG)利用APCG算法在訓(xùn)練集中對(duì)每個(gè)簇進(jìn)行中心群計(jì)算，使得每個(gè)簇利用一個(gè)中心群來(lái)表示其總體特征。與此同時(shí)，將所有中心群成員對(duì)象視為新構(gòu)建的訓(xùn)練數(shù)據(jù)集，對(duì)于測(cè)試集中的每個(gè)數(shù)據(jù)對(duì)象利用DKNN在新構(gòu)建的訓(xùn)練集中實(shí)現(xiàn)分類(lèi)。其具體算法如下。

基于簇中心群的 K近鄰分類(lèi)方法： L= KNN2CG(A, B,K)

輸入：訓(xùn)練集A、測(cè)試集B和近鄰數(shù)目K。

輸出：測(cè)試集B中成員類(lèi)標(biāo)簽集合L。

1) 根據(jù)訓(xùn)練集A=[a1, a2,…,aN]中成員類(lèi)標(biāo)簽劃分成相應(yīng)的簇，即A={A1, A2,… ,Aw}, 且有，其中w為A中的類(lèi)別數(shù)目。

2) 利用APCG對(duì)每個(gè)簇iA計(jì)算其中心序列群，即Ci=APCG(Ai), 進(jìn)而獲得簇中心群集合C且有。

3) 對(duì)于測(cè)試集中的每個(gè)數(shù)據(jù)對(duì)象bj利用KNN2CG在簇中心群集合C中進(jìn)行類(lèi)標(biāo)簽預(yù)測(cè)，則有l(wèi)j=KNN2CG(bj,C,K)。

4) 重復(fù)執(zhí)行步驟3)，獲得所有測(cè)試集中數(shù)據(jù)成員的預(yù)測(cè)類(lèi)標(biāo)簽，即L=[l1, l2,…,lM]，其中M表示測(cè)試集B中的成員數(shù)目。

新構(gòu)建的特征訓(xùn)練集大小遠(yuǎn)小于原始訓(xùn)練集，使得DKNN能夠快速有效地對(duì)時(shí)間序列進(jìn)行分類(lèi)。從時(shí)間效率角度來(lái)分析，KNN2CG方法的時(shí)間復(fù)雜度由訓(xùn)練集學(xué)習(xí)時(shí)間T1和測(cè)試集預(yù)測(cè)時(shí)間T2所決定，即：

由于新構(gòu)建的訓(xùn)練集成員數(shù)量N′遠(yuǎn)小于原始訓(xùn)練集成員數(shù)目N，新方法預(yù)測(cè)時(shí)間將會(huì)遠(yuǎn)小于傳統(tǒng)K最近鄰算法的時(shí)間，即KMm2N′＜KMm2N 。因此，從時(shí)間復(fù)雜度分析可知，新方法具有更好的預(yù)測(cè)時(shí)間效率。

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)例分析

實(shí)例分析通過(guò)計(jì)算每個(gè)簇的中心群，用于驗(yàn)證簇中心群對(duì)相應(yīng)簇成員的代表程度。從數(shù)據(jù)集Synthetic Control中隨機(jī)選取30條時(shí)間序列數(shù)據(jù)，其也是金融市場(chǎng)中較為常見(jiàn)的股票波動(dòng)現(xiàn)象，即存在6類(lèi)趨勢(shì)，分別為正常隨機(jī)波動(dòng)(No.: 1～5)、周期性波動(dòng)(No.: 6～9)、上升波動(dòng)趨勢(shì)(No.: 10～13)、下降波動(dòng)趨勢(shì)(No.: 14～18)、向上跳躍勢(shì)波動(dòng)(No.: 19～23)和向下跳躍勢(shì)波動(dòng)(No.: 24～30)6種形態(tài)。

通過(guò)APCG方法，對(duì)6組時(shí)間序列數(shù)據(jù)中每組數(shù)據(jù)進(jìn)行AP聚類(lèi)劃分，利用劃分后的數(shù)據(jù)對(duì)象集進(jìn)行均值中心序列計(jì)算，使得每組時(shí)間序列數(shù)據(jù)用中心群C來(lái)反映每組時(shí)間序列數(shù)據(jù)的總體形態(tài)特征或者金融股票每個(gè)時(shí)間段所反映的群體波動(dòng)趨勢(shì)。如圖3所示，每組數(shù)據(jù)被轉(zhuǎn)化為若干個(gè)均值中心序列，均值中心序列的形態(tài)變化反映了原始時(shí)間序列數(shù)據(jù)的形態(tài)波動(dòng)趨勢(shì)。與此同時(shí)，根據(jù)每組數(shù)據(jù)的形態(tài)分布情況，APCG對(duì)每組時(shí)間序列數(shù)據(jù)產(chǎn)生不同數(shù)量的均值中心序列。例如，APCG在前5組分別產(chǎn)生了2條均值中心序列，第6組卻產(chǎn)生了3條均值序列。這說(shuō)明APCG在訓(xùn)練數(shù)據(jù)集的學(xué)習(xí)過(guò)程中具有自適應(yīng)性，同時(shí)也從體現(xiàn)了基于APCG的新方法的可靠性。

圖3 訓(xùn)練集中各簇的中心群

3.2 分類(lèi)實(shí)驗(yàn)

利用兩種方法對(duì)15組UCI時(shí)間序列數(shù)據(jù)集[14]進(jìn)行分類(lèi)試驗(yàn)，具體實(shí)驗(yàn)數(shù)據(jù)信息如表1所示。通過(guò)統(tǒng)計(jì)測(cè)試集中數(shù)據(jù)成員對(duì)象預(yù)測(cè)標(biāo)簽的平均錯(cuò)誤率來(lái)反映算法在對(duì)應(yīng)時(shí)間序列數(shù)據(jù)集的分類(lèi)質(zhì)量，實(shí)驗(yàn)結(jié)果如表2和表3所示。

表1 UCI時(shí)間序列數(shù)據(jù)集信息

表2 KNN2CG方法的時(shí)間序列分類(lèi)結(jié)果

表3 傳統(tǒng)KNN方法的時(shí)間序列分類(lèi)結(jié)果

Aver列表示不同K值下兩種方法在對(duì)應(yīng)時(shí)間序列數(shù)據(jù)集中的平均分類(lèi)錯(cuò)誤率，可以發(fā)現(xiàn)，本文提出的方法在大部分?jǐn)?shù)據(jù)集中具有較小的平均錯(cuò)誤率，說(shuō)明新方法具有更好的分類(lèi)質(zhì)量。Aver行表示兩種方法在不同數(shù)據(jù)集中對(duì)應(yīng)同一個(gè)近鄰數(shù)K的平均分類(lèi)錯(cuò)誤率，對(duì)于大部分近鄰數(shù)K，本文提出的KNN2CG方法也具有較低的平均錯(cuò)誤率。特別地，當(dāng)K=1時(shí)，兩種方法成為了最近鄰分類(lèi)方法，而新方法KNN2CG具有比傳統(tǒng)最近鄰算法更好的分類(lèi)質(zhì)量。

針對(duì)每個(gè)數(shù)據(jù)集中的分類(lèi)實(shí)驗(yàn)，記錄在不同近鄰數(shù)K值的情況下兩種方法所花費(fèi)的時(shí)間，從不同近鄰數(shù)和不同數(shù)據(jù)集的兩個(gè)角度來(lái)觀察兩種方法的時(shí)間效率，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 兩種方法在不同數(shù)據(jù)集和K的平均消耗時(shí)間

圖4a顯示了兩種方法的時(shí)間消耗量會(huì)隨著近鄰數(shù)K值的增大而稍微變大，同時(shí)也說(shuō)明了新方法KNN2CG在不同K值下的時(shí)間效率明顯要優(yōu)于傳統(tǒng)KNN分類(lèi)方法。圖4b中的結(jié)果說(shuō)明，在大部分?jǐn)?shù)據(jù)集中，新方法的時(shí)間效率要優(yōu)于KNN。相對(duì)于測(cè)試集來(lái)說(shuō)，較小的訓(xùn)練集且較長(zhǎng)的時(shí)間序列數(shù)據(jù)對(duì)象容易使KNN2CG獲得較好的時(shí)間效率。

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

鑒于最近鄰算法在時(shí)間序列分類(lèi)研究中的重要性和優(yōu)越性，提出了一種基于簇中心群的時(shí)間序列數(shù)據(jù)分類(lèi)方法(KNN2CG)。通過(guò)近鄰傳播AP聚類(lèi)對(duì)訓(xùn)練數(shù)據(jù)集中的每個(gè)簇進(jìn)行子簇劃分和代表對(duì)象選擇，再以代表對(duì)象為初始化中心對(duì)象，利用DBA對(duì)每個(gè)子簇進(jìn)行中心序列計(jì)算，進(jìn)而構(gòu)建訓(xùn)練簇中心群。同時(shí)，結(jié)合改進(jìn)的K最近鄰方法，使得基于簇中心群的分類(lèi)算法獲得更好的分類(lèi)效果和計(jì)算性能。新方法具有以下幾點(diǎn)優(yōu)勢(shì)：1) 通過(guò)AP和DBA使得具有極為相似形態(tài)的時(shí)間序列數(shù)據(jù)子集被均值中心序列所描述，減少了新訓(xùn)練集中成員數(shù)量，提高了分類(lèi)算法的計(jì)算性能。2) 中心群為每個(gè)簇提供了更為詳細(xì)的總體特征描述，結(jié)合DTW使得均值中心序列能夠更好地表達(dá)被描述對(duì)象的形態(tài)特征，有利于提高最近鄰算法的分類(lèi)質(zhì)量。3) 利用平均距離來(lái)選取K個(gè)近鄰對(duì)象，克服了傳統(tǒng)K近鄰方法限入局最優(yōu)的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)方法相比，新方法具有更好的分類(lèi)質(zhì)量和較高的計(jì)算效率。

本文研究工作還得到福建省高等學(xué)校新世紀(jì)優(yōu)秀人才支持計(jì)劃(Z1625112)和華僑大學(xué)中青年教師科研提升資助計(jì)劃(ZQN-PY220)的資助，在此表示感謝。

[1] WU X D, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37.

[2] 李海林, 楊麗彬. 時(shí)間序列數(shù)據(jù)降維及特征表示新方法[J]. 控制與決策, 2013, 28(11): 1718-1722.

LI Hai-lin, YANG Li-bin. Method of dimensionality reduction and feature representation for time series[J]. Control and Decision, 2013, 28(11): 1718-1722.

[3] 李正欣, 郭建勝, 惠曉濱, 等. 基于共同主成分的多元時(shí)間序列降維方法[J]. 控制與決策, 2013, 28(4): 531-536.

LI Zheng-xin, GUO Jian-sheng, HUI Xiao-bin, etal. Dimension reduction method for multivariate time series based on common principal component[J]. Control and Decision, 2013, 28(4): 531-536.

[4] PETITJEAN F, FORESTIER G, NICHOLSON A, et al. Dynamic time warping averaging of time series allows faster and more accurate classification[C]//IEEE International Conference on Data Mining. Piscataway: IEEE, 2014: 470-479.

[5] 郭興明, 袁志會(huì), 丁曉蓉. 經(jīng)驗(yàn)?zāi)Ｊ椒纸饧瓣P(guān)聯(lián)維數(shù)在心音信號(hào)分類(lèi)識(shí)別中的應(yīng)用[J]. 電子科技大學(xué)學(xué)報(bào), 2013, 42(6): 954-960.

GUO Xing-ming, YUAN Zhi-hui, DING Xiao-rong. Application of EMD and correlation dimension in classification and recognition of heart sound[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(6): 954-960.

[6] KAYA H, GüNDüZ-??üDüCü. A distance based time series classification framework[J]. Information Systems, 2015, 51: 27-42.

[7] LI Hai-lin. Asynchronism-based principal component analysis for time series data mining[J]. Expert Systems with Applications, 2014, 41(6): 2842-2850.

[8] KEOGH E. Exact indexing of dynamic time warping[J]. Knowledge and Information Systems, 2005, 7(3): 358-386.

[9] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[10] 楊燕, 馮晨菲, 賈真. 基于鏈接的模糊聚類(lèi)集成方法[J].電子科技大學(xué)學(xué)報(bào), 2014, 43(6): 887-892.

YANG Yan, FENG Chen-fei, JIA Zhen. A link-based fuzzy clustering ensemble[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(6): 887-892.

[11] LIAO T W. Clustering of time series data survey[J]. Pattern Recognition, 2005, 38(11): 1857-1874.

[12] PETITJEAN F, KETTERLIN A , GANCARSKI P. A global averaging method for dynamic time warping, with applications to clustering[J]. Pattern Recognition, 2011, 44: 678-693.

[13] LEE Y, WEI C, CHENG T. Nearest-neighbor-based approach to time-series classification[J]. Decision Support Systems, 2012, 53(1): 207-217.

[14] KEOGH E, ZHU Q, HU B, et al. The UCR time series classification/clustering homepage[EB/OL]. [2015-06-08]. http://www.cs.ucr.edu/～eamonn/time_series_ data/.

編 輯 蔣 曉

Classification for Time Series Data Based on Center Sequences of Clusters

LI Hai-lin and WAN Xiao-ji

(1. Department of Information Management, Huaqiao University Quanzhou Fujian 362021; 2. Research Center of Applied Statistics and Big Data, Huaqiao University Xiamen Fujian 361021)

Classification algorithm is one of the important tasks and techniques in the field of time series data mining. A classification method for time series data based on center sequences of clusters is proposed in this paper. Time series in the training set are divided into several clusters according to their labels, and every cluster picks out the representation objects using affinity propagation clustering and constructs the representation subset. The barycenter averaging method based on dynamic time warping is used to calculate the center group in which the improved K nearest neighbors method is executed for time series classification. The experimental results demonstrated that the new method, compared to the traditional method, has better classification quality and calculation performance.

affinity propagation; classification algorithm; data mining; dynamic time warping; time series

TP273

A

10.3969/j.issn.1001-0548.2017.03.024

2015 ? 11 ? 21；

2016 ? 06 ? 18

國(guó)家自然科學(xué)基金(61300139); 福建省社會(huì)科學(xué)規(guī)劃項(xiàng)目(FJ2016B076); 福建省自然科學(xué)基金(2015J01581)

李海林(1982 ? ), 男, 副教授, 博士, 主要從事數(shù)據(jù)挖掘與人工智能等方面的研究.