廖洪一，王 欣

(中國民用航空飛行學院計算機學院，四川 廣漢 618300)

0 引言

時間序列(Time Series)是和時間變化相關(guān)聯(lián)的數(shù)據(jù)，在每個時間點都會有與之相對應(yīng)的一系列觀察值。在現(xiàn)代社會，時間序列廣泛地存在于各個領(lǐng)域中，如生物信息的RNA 序列、心電圖變化、商場銷售額和傳感器網(wǎng)絡(luò)收到的數(shù)據(jù)等。時間序列數(shù)據(jù)的挖掘是通過對這些數(shù)據(jù)觀察值的分析歸類來提取決策者關(guān)心的有效信息［1］。相較于一般靜態(tài)數(shù)據(jù)而言，時間序列數(shù)據(jù)呈現(xiàn)了待分析數(shù)據(jù)集一段時期內(nèi)的狀態(tài)，并且數(shù)據(jù)集內(nèi)的數(shù)據(jù)之間存在時間上的聯(lián)系。金融時間序列是在人類的金融活動中伴隨產(chǎn)生的，由于人類活動具有周期性，因此在一定歷史時期內(nèi)金融時間序列總是會與歷史數(shù)據(jù)表現(xiàn)出驚人的相似性，如何合理地利用這些歷史數(shù)據(jù)，并通過以往的金融時間序列進行分析，挖掘出潛在的、有價值的信息是學者們急需解決的問題。

目前使用得比較廣泛的金融時間序列聚類方法有k-均值聚類算法［2］、基于RBF 神經(jīng)網(wǎng)絡(luò)算法、基于ICA 的時間序列聚類方法［3］、基于AP-NN 的混合模型聚類算法、基于譜聚類的時間序列聚類算法［4］和基于蟻群的時間序列算法［5］等，由于時間序列數(shù)據(jù)的多維性和高噪聲性，傳統(tǒng)的聚類算法往往在聚類過程中會增大時間和空間上的復雜度。本文提出一種基于擴展范式(Extended Frobenius Norm，Eros)的近鄰傳播聚類算法(Affinity Propagation，AP)，并結(jié)合主成分分析方法(Principal Component Analysis，PCA)先對多維多變量時間序列數(shù)據(jù)進行降維處理，再選取多變量時間序列數(shù)據(jù)的主成分進行聚類，可以有效地提高聚類的準確性、穩(wěn)定性以及魯棒性。

1 基于Eros 的近鄰傳播聚類算法

1.1 近鄰傳播算法

聚類分析是建立一個分類模型，首先通過特征的形式來表示數(shù)據(jù)集中的數(shù)據(jù)，再按照特征的相似性來進行分類的過程，是人工智能和機器學習的一個重要研究領(lǐng)域［6］。聚類分析使得同一個類中的數(shù)據(jù)相似性最大，不同類中的數(shù)據(jù)相似性最小。而時間序列聚類是將時間序列數(shù)據(jù)集中的數(shù)據(jù)分組成多個類的過程，是時間序列數(shù)據(jù)分析中最主要的任務(wù)之一?，F(xiàn)代研究通過不同的距離和聚類方法的選擇，可以得到令人滿意的時間序列分類結(jié)果。

近鄰傳播聚類算法［7］是由Frey 等人在2007 年提出的一種新型聚類算法，該算法把樣本集中所有數(shù)據(jù)點都當作潛在的聚類中心，然后通過各個數(shù)據(jù)點之間的實時信息傳遞來迭代競爭從而發(fā)現(xiàn)聚類，與傳統(tǒng)的聚類算法相比，該算法不需要事先確定聚類的個數(shù)，更加快速有效。

對于有N 個樣本的樣本空間X={x1，x2，…，xN}，每一個樣本點xi有k 個影響因素，任意2 個樣本點xi和xj之間的相似度度量sij選取Eros 距離作為計算方法，數(shù)據(jù)點之間的Eros 距離越小說明數(shù)據(jù)點的相似性越大。

根據(jù)sij構(gòu)造相似性矩陣:

矩陣對角線上的元素p 為偏向參數(shù)，表示在迭代過程中各個樣本點成為聚類中心的可能性大小，不同的p 會影響聚類中心的數(shù)目從而產(chǎn)生不同的聚類結(jié)果，一般來說，p 值越大，在聚類中心迭代過程中樣本點的競爭就會越大。

在近鄰傳播聚類算法的計算過程中，選擇通過矩陣形式的吸引度R 和歸屬度A 來傳遞消息。其中吸引度表示樣本點作為聚類中心的可能性大小，歸屬度表示樣本點選擇對應(yīng)樣本點為聚類中心的可能性大小。數(shù)據(jù)集的所有樣本點通過算法迭代計算所有樣本點的吸引度和歸屬度，直到迭代滿足終止條件產(chǎn)生聚類中心，并且所有的樣本點都找到對應(yīng)的聚類中心為止。吸引度和歸屬度的迭代計算公式為:

更新公式為:

其中，λ(0 ＜λ ＜1，一般設(shè)置為0.9)為阻尼系數(shù)，用來控制迭代過程中的收斂，不同的阻尼系數(shù)迭代過程的收斂和振蕩過程不同。

近鄰傳播聚類算法的計算過程可描述如下:

1)初始化:求解相似度矩陣S，設(shè)置參考度p 值，令R0(i，k)=0，A0(i，k)=0。

2)更新吸引度矩陣R 和歸屬度矩陣A，每更新一次迭代次數(shù)加1，直至達到終止條件。

3)判斷聚類結(jié)果是否達到要求，否則重新設(shè)置p值，再重復步驟1)，2)，直到輸出的聚類結(jié)果滿足要求。

1.2 矩陣的Frobenius 范數(shù)

設(shè)矩陣A 為p×n 的矩陣，并且A=［a1，a2，…，an］，則矩陣A 的F-范數(shù)的平方公式如下:

其中tr(A)表示矩陣A 的跡，〈xi，xj〉表示向量xi與向量xj的內(nèi)積。

設(shè)矩陣A 和矩陣B 都是n ×n 的矩陣，并且A=［a1，a2，…，an］，B=［b1，b2，…，bn］，則A -B 的F-范數(shù)的計算公式為:

其中，θi是向量ai和向量bi的夾角，W=［wij］是對角半正定矩陣，并且wij=0(i≠j)，=1 且wii≥0。

1.3 矩陣的擴展范式

設(shè)A 是pA×n 矩陣，B 是pB×n 矩陣，分別對其協(xié)方差矩陣進行奇異值分解，可以得到矩陣A、B的右特征值矩陣VA=[a1，a2，…，an]和 VB=[b1，b2，…，bn]，其中ai，bi是長度為n 的正交向量，則可以將A 和B 的Eros［8］定義為:

其中，w 是特征值的權(quán)重向量，Eros 的變化從0 到1，即相似度在0 時最小，在1 時最大。A 和B 之間的Eros 距離定義為:

至此，2 個縱向數(shù)據(jù)之間的相似度就可以通過包含主元以及相關(guān)特征值的右特征向量來度量。假設(shè)式子:Eros(A，B，w)＞Eros(B，C，w)成立，這意味著成立［9］。因此

這表明，DEros也相對保留了Eros 的距離，即DEros也表現(xiàn)出Eros 的相似性。

2 主成分分析法優(yōu)化的近鄰傳播算法模型

由于多元時間序列的數(shù)據(jù)集龐大，并且當數(shù)據(jù)信息冗余時會導致近鄰傳播聚類算法的計算時間過長。因此如果在多元時間序列中查找出與原序列相似等價的子序列，并確定其相似度就可以對多元時間序列進行降維，以此來降低計算難度，提高聚類的質(zhì)量。也就是說，將Eros 距離的相似性度量用于去掉冗長信息構(gòu)造出來的方陣，將會得到更好的效果。

主成分分析方法是通過去掉次要的基本因素，用較少的具有代表性的基本因素表示原始數(shù)據(jù)的一種多元統(tǒng)計分析方法［10］。它通過將數(shù)據(jù)集投影到特征空間，再根據(jù)數(shù)據(jù)集在各個特征方向的方差大小排序，再去掉方差較小的特征方向，其實質(zhì)是數(shù)據(jù)在多因素影響的情況下如何使用較少的指標表示，或者給多個影響因素進行重要程度的排序。主成分分析方法理論簡單，實踐性強，結(jié)果客觀有效，因此是金融、經(jīng)濟、社會科學等領(lǐng)域被使用最為廣泛的評價排序方法之一［11］。

傳統(tǒng)的主成分分析方法通過搜索較少的幾個具有代表性的影響因素來實現(xiàn)對各個樣本向量的降維［12］?，F(xiàn)使用主成分分析方法對基于Eros 的近鄰傳播聚類算法進行優(yōu)化，步驟如下:

1)原始數(shù)據(jù)集中的樣本點向量e1，e2，…，e300都是由6 個隨機變量組成，則原始數(shù)據(jù)集X 可以用一個300 ×6 維的矩陣表示。

2)對矩陣中元素作標準化處理:yij=，其中xij表示第i 個樣本點的第j 個影響因素，xj表示第j 個影響因素的樣本均值，Sij表示表示第j 個影響因素的樣本標準差。得到標準化矩陣:

3)求解標準化矩陣的相關(guān)矩陣R 的特征值λ 以及特征向量u，并令λ1≥λ2≥λ3≥…≥λ6≥0。

4)確定p(p≤6)個變量主成分，在實際應(yīng)用中，一般只找到前p0個主成分即可，其中前p0個主成分方差之和在所有方差中占有較大的比例，并且p0?p。按照主成分方差λj占所有方差的比例求權(quán)系數(shù)，j=1，2，…，6。

5)根據(jù)主成分的方差貢獻率計算樣本綜合評價值Z=(Z1，Z2，…，Zn)T［13］，其中Z=，由Zi(i=1，2，…，n)值的大小來對樣本進行評價排隊。

3 實驗與分析

3.1 實驗數(shù)據(jù)選取

為了驗證算法在金融數(shù)據(jù)領(lǐng)域的有效性，選取通信達金融數(shù)據(jù)庫系統(tǒng)中300 只股票的相關(guān)交易數(shù)據(jù)進行仿真實驗，共覆蓋5 個行業(yè)，構(gòu)成原始數(shù)據(jù)集。只列舉前12 只股票分別是:1)古井貢酒;2)國電電力;3)中航飛機;4)濰柴動力;5)中航動控;6)燕京啤酒;7)華能國際;8)華電國際;9)航天科技;10)一汽轎車;11)瀘州老窖;12)海馬汽車。選取2013 年1 月30 日到2014 年11 月4 日時間跨度為420 個交易日的數(shù)據(jù)，每只股票的交易情況用每日上證指數(shù)的開盤指數(shù)最高值、指數(shù)最低值、收盤指數(shù)、當日交易量、當日交易額、當日開盤指數(shù)6 個變量的時間序列來描述［14］。聚類算法通過工具軟件Matlab7.1 實現(xiàn)，根據(jù)先驗知識調(diào)節(jié)偏向參數(shù)的p 值，并在累積貢獻率達到95%時確定主元數(shù)。

3.2 算法對比實驗

為驗證基于Eros 的近鄰傳播聚類算法的有效性，現(xiàn)選取K 均值和凝聚層次2 種同樣基于距離的聚類算法作為對比實驗。其中K 均值聚類是一種可以把數(shù)據(jù)集自動劃分為K 類的聚類方法，也是當下應(yīng)用最為廣泛的一種聚類方法。凝聚層次聚類［15］則是通過自下而上的方式，通過合成子簇從而達到最終聚類結(jié)果。本文將從聚類的準確率和聚類質(zhì)量2 方面來比較3 種聚類算法的優(yōu)劣。

3.3 聚類結(jié)果評價

為了對聚類結(jié)果做出評價，現(xiàn)引入評價指標ASW(Average Silhouette Width)、F-Measure 和熵。

Kaufman 和Rousseeuw 在1990 年提出一種可以對聚類結(jié)果進行評價的驗證統(tǒng)計量ASW:對于類中的一個對象i，i 的ASW［16］定義為:

F-Measure 是基于準確率和召回率的的一個綜合評價。對于任何一個預(yù)定類，尋找聚類結(jié)果中與之最相似的簇，并根據(jù)這個簇計算該類的準確率(precision(i，j)=)，召回率(recall(i，j)=)以及FMeasure。定義類i，j之間的F值為F(i，j)=。至此，整體聚類結(jié)果的F 值可以通過加權(quán)獲得:F=max {F(i，j)}，F(xiàn)值越大說明聚類的準確率越高。

熵用來衡量聚類結(jié)果的純度，熵的值越小說明聚類結(jié)果的純度越大，聚類的效果越好。現(xiàn)將聚類結(jié)果的整體熵值定義為:

3.4 實驗結(jié)果

將股票原始數(shù)據(jù)集中的數(shù)據(jù)進行歸一化處理后引入主成分分析法模型，計算主元累積率，結(jié)果如表1 所示。

表1 列舉前12 只股票主元累積貢獻率

由表1 可以看出當主成分z=3 時，主元的累積貢獻率已經(jīng)達到95%［17］，包含了原始數(shù)據(jù)集的絕大部分信息，因此選取前3 個主成分代表原始數(shù)據(jù)，然后分別用基于Eros 的近鄰傳播聚類(AP)算法和K均值算法、凝聚層次算法進行聚類比較。

圖1 3 種聚類算法的ASW 值

從圖1 可以看出基于Eros 的近鄰傳播聚類算法的ASW 在聚類數(shù)目為5 時出現(xiàn)了一個明顯的峰值，達到最大值。K 均值算法的ASW 隨著聚類數(shù)目的增加而緩慢增大，在K=5 時取得最大值，然后ASW 值減小。凝聚層次算法的ASW 先增加后減小K=4 處取得最大值。

圖2 3 種聚類算法的F 值

3 種聚類算法在數(shù)據(jù)集上的F 值如圖2 所示。從圖中可以看出改進的近鄰傳播算法結(jié)合了主成分分析方法，在準確率幾乎不受影響的情況下，提高了召回率，使得該方法的F 值明顯大于K 均值算法和凝聚層次算法。

表2 數(shù)據(jù)集的聚類結(jié)果熵值

改進的AP 算法取得了較低的熵值，而K 均值算法和凝聚層次算法的熵值較高。這是因為K 均值算法初始參數(shù)的選擇會大大影響聚類結(jié)果的平衡，凝聚層次算法對于多元時間序列的處理沒有優(yōu)勢，而改進的AP 算法聚類純度高，性能穩(wěn)定。

綜合考慮3 種聚類算法，可以看出與K 均值算法、凝聚層次算法相比，基于Eros 的近鄰傳播聚類算法的聚類結(jié)果具有更高的聚類精度，性能也更加穩(wěn)定。同時，從聚類結(jié)果也可以看出，同一個行業(yè)內(nèi)的股票相似度遠遠大于不同行業(yè)內(nèi)的股票相似度，同行業(yè)之間的股票趨勢具有很高的借鑒。

4 結(jié)束語

時間序列的聚類問題是時間序列數(shù)據(jù)挖掘的重要任務(wù)之一，針對時間序列的高維性和高噪聲性使得一般的聚類算法不能直接應(yīng)用的問題，本文引入了一種基于主成分分析法和Eros 的近鄰傳播聚類算法。通過建立多變量的股票時間序列聚類模型，評估該算法在股票時間序列聚類的可行性，并與傳統(tǒng)的聚類算法進行對比。近鄰傳播算法可以自動確定聚類中心和聚類的數(shù)目，不需要人工設(shè)置初始值，這種通過競爭迭代確定出聚類中心的算法要明顯優(yōu)于傳統(tǒng)的給定模型優(yōu)化的算法。最后通過實驗證明了基于Eros的近鄰傳播算法的有效性，且在聚類精度和算法速度方面要優(yōu)于傳統(tǒng)的聚類算法。

［1］Buyya R，Abramson D，Venugopal S.The grid economy［J］.Proceedings of the IEEE，2005，93(3):698-714.

［2］謝娟英，蔣帥，王春霞，等.一種改進的全局K-均值聚類算法［J］.陜西師范大學學報(自然科學版)，2010，38(2):18-22.

［3］郭崇慧，賈宏峰，張娜.基于ICA 的時間序列聚類方法及其在股票數(shù)據(jù)分析中的應(yīng)用［J］.運籌與管理，2008，17(5):120-124.

［4］Maharaj E A，D'Urso P.A coherence-based approach for the pattern recognition of time series［J］.Physica A:Statistical Mechanics and its Applications，2010，389(17):3516-3537.

［5］Caiado J，Crato N，Pe?ad D.A periodogram-based metric for time series classification［J］.Computational Statist ＆Data Analysis，2006，50(10):2668-2684.

［6］王駿，王士同，鄧趙紅.聚類分析研究中的若干問題［J］.控制與決策，2012，27(3):321-328.

［7］Frey B J，Dueck D.Clustering by passing messages between data points［J］.Science，2007，315(5814):972-976.

［8］Sambasivam S，Theodosopoulos N.Advanced data clustering methods of mining Web documents［J］.Issues in Informing Science and Information Technology，2006(3):563-579.

［9］Bohm C，Berchtold S，Keim D A.Searching in high-dimensional spaces-index structures for improving the performance of multimedia databases［J］.ACM Computing Surveys，2001，33(3):322-373.

［10］Fang S H，Lin T N.Principal component localization in indoor WLAN environments［J］.IEEE Transactions on Mobile Computing，2012，11(1):100-110.

［11］王德青，朱建平，謝邦昌.主成分聚類分析有效性的思考［J］.統(tǒng)計研究，2012，29(11)84-87.

［12］Climescu-Hauliea A.How to choose the number of clusters:The cramer multiplicity solution［C］// Advances in Data Analysis.2007:15-22.

［13］廖東，杜瑞卿，王驍力.變量線性相關(guān)對主成分方差貢獻率的影響［J］.河南師范大學學報(自然科學版)，2010，38(6):23-26.

［14］高玉明，張仁津.基于改進QPSO 算法優(yōu)化SVR 的上證指數(shù)預(yù)測［J］.計算機仿真，2013，30(12):208-213.

［15］李春忠，徐忠本，喬琛.帶信息反饋的凝聚層次聚類算法［J］.中國科學:信息科學，2012，42(6):730-742.

［16］Kaufman L，Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis［M］.John Wiley and Sons，1990.

［17］杜敏.基于主成分分析法的環(huán)境質(zhì)量綜合指數(shù)研究［D］.成都:四川大學，2006.