郭小芳， 張絳麗， 宋曉寧， 王衛(wèi)東

(江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 江蘇 鎮(zhèn)江 212003)

基于加權(quán)(擴(kuò)展)歐幾里德范數(shù)(Extended Euclid Norm,Eros)[1]的主元分析(principal component analysis, PCA)[2]是一種處理高維數(shù)據(jù)的有效方法．這種方法通過原始數(shù)據(jù)的適當(dāng)線性組合,把多元時(shí)間序列數(shù)據(jù)集分解為若干個(gè)簇,在每個(gè)簇中任選一代表元素,根據(jù)簇的代表元素與剩余MTS元素的前若干個(gè)主元與之間的Eros范數(shù),將剩余元素劃分給最近的一個(gè)簇,再用剩余元素替換代表元素,再次進(jìn)行操作,當(dāng)各元素所在的簇不再改變?yōu)橹?或超過限定迭代次數(shù))[3-4]．這種方法在計(jì)算范數(shù)時(shí)對(duì)原有的復(fù)雜數(shù)據(jù)進(jìn)行降維,可以給出數(shù)據(jù)的主要成分和有用信息,去除數(shù)據(jù)中的噪音和冗余．文中采用一種基于主元的K-近鄰的MTS數(shù)據(jù)聚類算法,根據(jù)多元時(shí)間序列數(shù)據(jù)的主元及其范數(shù)進(jìn)行K近鄰聚類分析．理論分析和實(shí)驗(yàn)結(jié)果表明該算法聚類結(jié)果質(zhì)量和運(yùn)行時(shí)間明顯優(yōu)于直接利用k-均值法的聚類結(jié)果．

1 PCA原理分析

在以原始變量X1和X2為坐標(biāo)的平面上(圖1),數(shù)據(jù)點(diǎn)分布在一個(gè)傾斜的橢圓內(nèi),表明原始變量X1和X2之間相關(guān)性很強(qiáng)．如果在平面上作一個(gè)坐標(biāo)變換：

(1)

在Z1Z2坐標(biāo)下,數(shù)據(jù)點(diǎn)主要沿著Z1方向的分布,Z2方向上數(shù)據(jù)的變化不大,在一定條件下可以忽略,從而將原來的二維問題看做一維問題來處理,達(dá)到降維的目的[5]．主元分析技術(shù)[6]通過對(duì)原有數(shù)據(jù)進(jìn)行適當(dāng)操作,將原有的復(fù)雜數(shù)據(jù)降維,揭示隱藏在復(fù)雜數(shù)據(jù)背后的簡(jiǎn)單關(guān)系．這種方法首先獲得每個(gè)矩陣的主元,然后試探性選擇z個(gè)主元,這前z個(gè)主元素之間的相似性通過下式計(jì)算:

(2)

圖1 主元分析的幾何意義

這里要求MTS項(xiàng)A和B具有相同列數(shù),可以有不同的行數(shù)．式(2)中,L和M各自包含矩陣A和B的前z個(gè)主元,θi j為A的第i個(gè)主元與B的第j個(gè)主元之間的夾角．即從0到z,通過計(jì)算兩矩陣的前z個(gè)主元兩兩之間的余弦平方值來測(cè)量其相似性．方法簡(jiǎn)單,無參數(shù)限制,可以方便的應(yīng)用于各種場(chǎng)合．

2 擴(kuò)展歐幾里德范數(shù)(Eros)

設(shè)A=[a1, …,an],B=[b1, …,bn],ai和bi為單位正交向量,其夾角為θi,則矩陣C=A-B=[a1-b1,…,an-bn,]的F-加權(quán)范數(shù)的平方可用如下公式計(jì)算：

(3)

對(duì)于MTS項(xiàng)A和B,其擴(kuò)展歐幾里得范數(shù)(Eros) 定義為

(4)

式中：ai和bi為協(xié)方差矩陣為MA和MB的右特征向量(列正交向量,長(zhǎng)度為n)；w為基于MTS數(shù)據(jù)集特征值的加權(quán)向量；θi是ai和bi之間的夾角．Eros從0到1變化,反映了A和B之間的相似程度,1表示最相似．定義A和B之間的Eros距離:

(5)

即利用包含主元及相關(guān)特征值的右特征向量矩陣測(cè)量?jī)蓚€(gè)MTS主成份間距離．

根據(jù)式(5),若Eros(A,B,w)>Eros(B,C,w),則有

(6)

即DEros(A,B)小于DEros(B,C),可見DEros也保存了Eros的距離．

3 多元時(shí)間序列的聚類分析

K-means算法將類的均值作為聚類中心,較好地體現(xiàn)了聚類的統(tǒng)計(jì)意義[7-8],是當(dāng)前普遍應(yīng)用的聚類方法之一．正是這個(gè)原因,也導(dǎo)致其無法用于具有類別屬性的數(shù)據(jù)．

基于主元的聚類分析的思路是:對(duì)于n個(gè)數(shù)據(jù)元素的MTS數(shù)據(jù)集,分為k(k≤n)個(gè)目標(biāo)簇,簇內(nèi)的元素相似,不同簇元素相異[9]．任選某簇內(nèi)元素作為代表,取簇外剩余元素的前z個(gè)主元計(jì)算其與代表元組的范數(shù),以此為依據(jù)來決定將剩余元素分配給最近一簇,同時(shí)用剩余元素替換代表元素,反復(fù)操作,當(dāng)各簇元素不再變化為止[10-11]．這種方法的算法描述如下:

輸入:MTS數(shù)據(jù)的主成分序列

輸出:k個(gè)聚類

流程：

① 選取參考點(diǎn),取元素(C1,C2,…,Ck)作為初始聚類的中心;

② 對(duì)于新序列點(diǎn)a,根據(jù)上述范數(shù)將其劃入與其最近的類,合并后類的半徑為r1;

③ 用相同的方法找出原有類中最相近的兩類,合并后的類半徑為r2;

④ 比較r1和r2,若r1

⑤ 對(duì)所有MTS主成分重復(fù)步驟②～④,直到整個(gè)MTS主成分序列掃描結(jié)束;

⑥ 輸出k個(gè)聚類．

如有m個(gè)參考點(diǎn),則每個(gè)數(shù)據(jù)對(duì)象就會(huì)有m個(gè)距離,p是最佳參考點(diǎn),查詢點(diǎn)為q,查詢半徑為rq．建立索引結(jié)構(gòu),當(dāng)某聚類c與查尋區(qū)域相交時(shí),利用前述三角不等式進(jìn)行過濾,查詢聚類c中以p為圓心,內(nèi)外半徑為r1,r2的圓環(huán)與聚類c相交的區(qū)域中的點(diǎn)．中類被分解為核心聚類環(huán)與邊緣聚類環(huán),對(duì)這些聚類環(huán)分別進(jìn)行索引,可以進(jìn)一步提高數(shù)據(jù)過濾效率．

算法： 主元聚類分析算法；

輸入: MTS數(shù)據(jù)集,聚類數(shù)k,主元數(shù)z;

輸出:k個(gè)MTS主元序列的聚類中心.

①[A,w]←PCA(MTS);

② C←select(A,k);//選擇初始類中心

③num←0;

④ whilenum

⑤ for eachainA

⑥ for eachcinC

⑦ d←dist(a,c,w,z);//計(jì)算到各個(gè)類中心點(diǎn)距離

⑧ end

⑨i←min(d,a);//距離A 最近的類.

⑩end

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

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

取某股市300家上市公司的交易數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集,股票長(zhǎng)度為300個(gè)交易日的觀測(cè)值,選取開盤、收盤價(jià)、最高、最低價(jià)、交易量和交易金額等6個(gè)變量．利用Matlab7.9a 檢驗(yàn)實(shí)驗(yàn)算法．雖然MTS項(xiàng)經(jīng)過PCA處理,但還不是單變量序列,不能用傳統(tǒng)的相似性方法進(jìn)行相似性度量．由于各主成分對(duì)整體數(shù)據(jù)的貢獻(xiàn)率不同[12],其方差反映了原變量在主成分上的集中程度,因而將方差作為貢獻(xiàn)率權(quán)值．設(shè)方差貢獻(xiàn)率為SYi/∑SYi,各成分對(duì)應(yīng)的權(quán)值為ωi=SYi/∑SYi．

實(shí)驗(yàn)過程中,主元z的選取也會(huì)對(duì)算法結(jié)果產(chǎn)生一定的影響．當(dāng)股票樣本數(shù)為300時(shí),主元數(shù)z及其的貢獻(xiàn)率見表1．可以看出當(dāng)z=2時(shí),它們的累積貢獻(xiàn)率就高達(dá)99%,這說明取前2個(gè)主元就可以很好地代表原始數(shù)據(jù),所以一般在驗(yàn)證算法時(shí)取z=2即可．

表1 主元z的貢獻(xiàn)率

為了估算聚類結(jié)果的質(zhì)量,定義聚類算法的聚類質(zhì)量:

(7)

式中：E表示數(shù)據(jù)集所有元素的平方誤差的總和；p代表任意元素；mi表示簇Ci的中心點(diǎn)．E值越小聚類質(zhì)量越好．

4.2 實(shí)驗(yàn)結(jié)果

1) 主元聚類分析和K-means的聚類質(zhì)量比較

為比較主元聚類算法和K-means算法的聚類質(zhì)量值E,表2給出了k值從6到20變化情況下主元聚類算法與K-means算法的聚類質(zhì)量．從表中可以看出主元聚類算法在聚類質(zhì)量上明顯優(yōu)于K-means算法,且隨著近鄰數(shù)k值的增加聚類質(zhì)量值E值減小的比例更大,聚類效果更好．

表2 兩種算法的聚類結(jié)果值E比較

2) 主元聚類分析和K-means的執(zhí)行效率比較

針對(duì)上述股票數(shù)據(jù)集,比較了在不同的近鄰數(shù)k值條件下,主元聚類算法與K-means算法耗費(fèi)CPU時(shí)間見圖2,其中，近鄰數(shù)k值分別取6～20．可見PCA-cluster的執(zhí)行效率優(yōu)于K-means算法,特別是當(dāng)近鄰數(shù)k在10～12時(shí)算法執(zhí)行速度最快．

圖2 兩種算法耗費(fèi)CPU時(shí)間比較

從以上結(jié)果容易看出基于主元聚類的多元時(shí)間序列聚類算法的聚類質(zhì)量結(jié)果明顯優(yōu)于直接利用K-means法時(shí)的聚類結(jié)果,運(yùn)行時(shí)間也少于直接利用K-means法的運(yùn)行時(shí)間,而且重復(fù)次數(shù)越多,運(yùn)行時(shí)間越少．表明基于PCA的MTS聚類方法是一個(gè)簡(jiǎn)單有效的聚類方法．

5 結(jié)論

為提高M(jìn)TS聚類分析的效率,采用基于主元的聚類分析方法．將多元MTS數(shù)據(jù)集分為k個(gè)簇(k小于數(shù)據(jù)元組個(gè)數(shù)n),在每個(gè)簇中任選一代表元組,根據(jù)代表元組與剩余元組的前z個(gè)主元的Eros距離對(duì)MTS數(shù)據(jù)進(jìn)行聚類．實(shí)驗(yàn)結(jié)果表明該方法聚類質(zhì)量和運(yùn)行時(shí)間明顯優(yōu)于直接的K-means方法．

[1] Sambasivam S, Theodosopoulos N.Advanced data clustering methods of mining Web documents [J].IssuesinInformingScienceandInformationTechnology, 2006(3):563-579.

[2] Yang K, Shahabi C. An efficient k nearest neighbor search for multivariate time series [J].InformationComputation, 2007, 205(1): 65-98.

[3] Wang Xiaozhe, Smith K A, Hyndman R J. Dimension reduction for clustering time series using global characteristics[J].LectureNotesinComputerScience, 2005, 3516:792-795.

[4] Zhao F, Jiao L C, Liu H Q.Spectral clustering with eigenvector selection based on entropy ranking [J].Neurocomputing, 2010, 73(10/11/12): 1704-1717.

[5] Filippone M, Camastra F, Masulli F. A survey of kerne land spectral methods for clustering[J].PatternRecognition, 2008, 41:176-190.

[6] 郭小芳, 張絳麗. 基于加權(quán)范數(shù)的多維時(shí)間序列相似性主元分析[J]. 江蘇科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 2011, 25(5): 466-469.

Guo Xiaofang, Zhang Jiangli. Similarity PCA of multivariate time series based on extended Frobemus norm[J].JiangsuUniversityofScienceandTechnology:NaturalScienceEdition,2011,25(5):466-469.(in Chinese)

[7] Gelbard R,Goldman O,Spiegler I.Investigating diversity of clustering methods:An empirical comparison [J].Data&KnowledgeEngineering, 2007, 63(1):155-166.

[8] Birant D,Kut A.ST-DBSCAN: An algorithm for clustering spatial-temporal data [J].DataKnowledgeEngineering, 2007, 60(1):208-221.

[9] Pilevar A H,Sukumar M.GCHL: A grid-clustering algorithm for high-dimensional very large spatial data bases [J].PatternRecognitionLetters,2005,26(7):999-1010.

[10] Naseimento M, Carvalho A.Spectral methods for clustering-a survey [J].EuropeanJournalofOperationalResearch, 2011, 211(2):221-231.

[11]Zhang Z, Jordan M. multiway spectral clustering: a margin-based perspective [J].StatisticalScience, 2008,23(3):353-403.

[12]Climescu-Hauliea A.How to choose the number of clusters: the cramer multiplicity solution[C]∥AdvancesinDataAnalysis.Berlin Heidelberg:Springer,2007:15-22.