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

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

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

1 PCA原理分析

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

(1)

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

(2)

圖1 主元分析的幾何意義

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

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

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

(3)

對于MTS項A和B,其擴展歐幾里得范數(shù)(Eros) 定義為

(4)

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

(5)

即利用包含主元及相關特征值的右特征向量矩陣測量兩個MTS主成份間距離．

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

(6)

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

3 多元時間序列的聚類分析

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

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

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

輸出:k個聚類

流程：

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

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

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

④ 比較r1和r2,若r1

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

⑥ 輸出k個聚類．

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

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

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

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

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

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

③num←0;

④ whilenum

⑤ for eachainA

⑥ for eachcinC

⑦ d←dist(a,c,w,z);//計算到各個類中心點距離

⑧ end

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

⑩end

4 實驗及結(jié)果分析

4.1 實驗數(shù)據(jù)集

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

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

表1 主元z的貢獻率

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

(7)

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

4.2 實驗結(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í)行效率比較

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

圖2 兩種算法耗費CPU時間比較

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

5 結(jié)論

為提高MTS聚類分析的效率,采用基于主元的聚類分析方法．將多元MTS數(shù)據(jù)集分為k個簇(k小于數(shù)據(jù)元組個數(shù)n),在每個簇中任選一代表元組,根據(jù)代表元組與剩余元組的前z個主元的Eros距離對MTS數(shù)據(jù)進行聚類．實驗結(jié)果表明該方法聚類質(zhì)量和運行時間明顯優(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] 郭小芳, 張絳麗. 基于加權范數(shù)的多維時間序列相似性主元分析[J]. 江蘇科技大學學報：自然科學版, 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.