韓 娜，滕少華，房小兆

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州510006）

0 引 言

時(shí)間序列分析是數(shù)理統(tǒng)計(jì)這一學(xué)科中應(yīng)用性較強(qiáng)的一個(gè)分支，在金融經(jīng)濟(jì)、氣象天文、信號(hào)處理、機(jī)械振動(dòng)等眾多領(lǐng)域有著廣泛的應(yīng)用［1］。聚類問題是時(shí)間序列模式發(fā)現(xiàn)的一個(gè)重要問題［2］。目前大部分研究主要針對(duì)一元時(shí)間序列的降維和相似性度量方法，多元時(shí)間序列聚類的研究還很少見。但是，現(xiàn)實(shí)世界中反映某一客觀事物僅靠一個(gè)參數(shù)是不夠的，大多數(shù)事物需要多個(gè)參數(shù)進(jìn)行度量，如股票一般具有開盤價(jià)、收盤價(jià)、最高價(jià)、最低價(jià)等，多元時(shí)間序列是普遍存在的。當(dāng)前對(duì)多元時(shí)間序列聚類方面的研究及存在的問題如下：Huang等采用主成分分析 （principal component analysis，PCA）方法聚類多變量時(shí)間序列［3］。這種方法當(dāng)整個(gè)數(shù)據(jù)集的方差無法事先確定時(shí)有很大的局限性，而且在特定情況下，各對(duì)象確定的主成分?jǐn)?shù)量不能一致，必須經(jīng)過統(tǒng)一協(xié)調(diào)才能進(jìn)行主成分分析且其不適合小規(guī)模數(shù)據(jù)集；Wang和McGreavy將每個(gè)多變量時(shí)間序列表示成m×n矩陣，然后將矩陣的每個(gè)元素展開成行向量來進(jìn)行聚類［4］。這種方法只能聚類具有相同參數(shù)個(gè)數(shù)和序列長(zhǎng)度的多元時(shí)間序列且計(jì)算復(fù)雜度會(huì)隨著序列維數(shù)的增多而劇增；Kiyoung Yang［5］把多元時(shí)間序列看成矩陣，應(yīng)用矩陣的Frobenius范數(shù)［6］度量多元時(shí)間序列的相似性，但它直接對(duì)原始時(shí)間序列進(jìn)行處理，對(duì)于大規(guī)模數(shù)據(jù)集時(shí)間開銷較大。文獻(xiàn) ［7－9］中利用傅立葉變換進(jìn)行時(shí)間序列數(shù)據(jù)降維。傅立葉變換使我們可以從信號(hào)的時(shí)域和頻域兩個(gè)角度觀察和分析信號(hào)，但是二者卻是絕對(duì)分離的。對(duì)于傅立葉頻譜中的某一頻率，不知道這一頻率是何時(shí)產(chǎn)生的，只能從全局上分析信號(hào)。這樣在信號(hào)分析中就面臨一對(duì)最基本的矛盾：時(shí)域和頻域的局部化矛盾。

針對(duì)多元時(shí)間序列不等長(zhǎng)、數(shù)據(jù)量大及參數(shù)間的相關(guān)性等特點(diǎn)，文中提出基于離散哈達(dá)瑪變換及帶權(quán)值的矩陣相似性度量的多元時(shí)間序列聚類方法并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1 離散哈達(dá)瑪變換的維歸約

1.1 離散哈達(dá)瑪變換

離散哈達(dá)瑪變換 （Descrete Hadamard Transform（DHT）h）的本質(zhì)是將離散序列x（n）的各項(xiàng)值的符號(hào)按一定規(guī)律改變后，進(jìn)行加減運(yùn)算，它是一種線性運(yùn)算，比采用復(fù)數(shù)運(yùn)算的離散傅立葉變換 （DFT）和采用余弦運(yùn)算的離散余弦變換 （DCT）計(jì)算相對(duì)簡(jiǎn)單。

定義1 一個(gè)長(zhǎng)度為N的離散時(shí)間序列x（n），且N＝2q（q為正整數(shù)），哈達(dá)瑪變換［10］為

式中：bi（x）——非負(fù)整數(shù)的二進(jìn)制形式的第i位，例如6的二進(jìn)制表示為110，則b0（6）＝0；b1（6）＝1；b2（6）＝1。

哈達(dá)瑪變換用哈達(dá)碼矩陣表示更直觀，且簡(jiǎn)單易懂。哈達(dá)瑪矩陣是由＋1和－1構(gòu)成的正交矩陣，實(shí)數(shù)表示且計(jì)算簡(jiǎn)單，用其進(jìn)行序列變換具有高效的數(shù)據(jù)能量集中性。

定義2 一個(gè)長(zhǎng)度為N的離散時(shí)間序列x（n）＝［x（0），x （1），x （2），…，x （N－1）］，其哈達(dá)瑪變換表示為：XH（K）＝ ［XH（0），XH（1），XH（2），…，XH（N－1）］；哈達(dá)瑪矩陣為

則哈達(dá)瑪變換的矩陣表示為

定理1 設(shè)XH（K）是序列x（n）經(jīng)離散哈達(dá)瑪變換后的序列，則序列變換前后保持能量不變，即

證明：離散哈達(dá)瑪變換是正交變換，正交變換在歐氏空間中保持內(nèi)積，得證。

1.2 數(shù)據(jù)降維

多元時(shí)間序列數(shù)據(jù)進(jìn)行離散哈達(dá)瑪變換，是在對(duì)多元時(shí)間序列數(shù)據(jù)進(jìn)行能量集中的情況下，抽取多元時(shí)間序列前K個(gè)系數(shù)作為特征維，將不等長(zhǎng)多元時(shí)間序列映射到K維特征空間，降不等長(zhǎng)的多元時(shí)間序列轉(zhuǎn)換成長(zhǎng)度為K的多元時(shí)間序列。首先應(yīng)對(duì)原始多元時(shí)間序列數(shù)據(jù)進(jìn)行預(yù)處理，為了解決基線和刻度問題，最好的方法是使用序列數(shù)據(jù)規(guī)范化變換［11］。對(duì)多元時(shí)間序列的每一元時(shí)間序列利用公式進(jìn)行規(guī)范化變換，其中，μ為原時(shí)間序列x的平均值，σ為原時(shí)間序列x的標(biāo)準(zhǔn)差，X為規(guī)范化變換后的序列。

對(duì)預(yù)處理后的多元時(shí)間序列數(shù)據(jù)進(jìn)行維歸約的方法如下：

（1）用二進(jìn)制反碼的格雷碼建立按哈達(dá)瑪編號(hào)的離散沃爾什－哈達(dá)瑪變換后序列和按沃爾什編號(hào)的離散沃爾什－哈達(dá)瑪變換后序列的映射關(guān)系。

（2）對(duì)x進(jìn)行離散哈達(dá)瑪變換。變換后的序列為XH。

（3）利用 （1）對(duì)XH進(jìn)行調(diào)序，得到X。X即是我們需要的 （DWHT）H變換后的序列。

多元時(shí)間序列經(jīng)過哈達(dá)瑪變換后，取前K維，則不等長(zhǎng)的多元時(shí)間序列都映射到K維的特征空間。由定理1可知，變換后的長(zhǎng)度為K的多元序列能很好的保持原多元時(shí)間序列數(shù)據(jù)的趨勢(shì)特征，這是實(shí)現(xiàn)多元時(shí)間序列快速有效聚類的必要前提。

2 帶權(quán)值的矩陣相似性度量

2.1 多元時(shí)間序列權(quán)值的獲取

多元時(shí)間序列并不是簡(jiǎn)單的一元時(shí)間序列的組合，通常多元時(shí)間序列的多個(gè)參數(shù)之間存在一定的關(guān)聯(lián)，這些參數(shù)應(yīng)該作為一個(gè)整體看待而不應(yīng)該割裂開來［12］。為了更好的進(jìn)行多元時(shí)間序列的相似性度量，這里考慮多元時(shí)間序列各個(gè)參數(shù)之間的相關(guān)系數(shù)。

多元時(shí)間序列A （M×N）經(jīng)過離散哈達(dá)瑪變換進(jìn)行能量集中后，抽取前K個(gè)系數(shù)作為特征維，得到矩陣A（K×N）表示原多元時(shí)間序列，其能很好的保持原多元時(shí)間序列數(shù)據(jù)的趨勢(shì)特征。首先，求變換后矩陣A （K×N）的相關(guān)系數(shù)矩陣A （N×N），然后，求相關(guān)系數(shù)方陣的特征根σA＝ ［σA1，σA2，…，σAN］，最后，σA與矩陣 A （K×N）的各列向量一一對(duì)應(yīng)，作為矩陣相似性度量的權(quán)值。

2.2 帶權(quán)值的矩陣相似性度量方法

目前，一元時(shí)間序列的相似性度量一般是基于距離，但這種方法顯然已經(jīng)不再適合多元時(shí)間序列的相似性度量。多元時(shí)間序列數(shù)據(jù)的相似性度量大都致力于其形態(tài)特征變換趨勢(shì)的相似性，比如，對(duì)于股票，人們更關(guān)注的是股票價(jià)格序列的漲跌情況，而不是股票的具體價(jià)格。多元時(shí)間序列基于帶權(quán)值的矩陣相似性度量，文獻(xiàn) ［13］中的相似性度量公式，能很好的表現(xiàn)多元時(shí)間序列數(shù)據(jù)的形態(tài)特征變換趨勢(shì)。

兩個(gè)不等長(zhǎng)的多元時(shí)間序列A （M×N）和B（Q×N），利用離散哈達(dá)瑪變換數(shù)據(jù)能量集中并進(jìn)行K維歸約后，能保持原多元時(shí)間序列數(shù)據(jù)的變換趨勢(shì)特征且長(zhǎng)度相同，其相應(yīng)的變換后矩陣為

式中：K——矩陣A和B的行，即多元時(shí)間序列維歸約后的序列長(zhǎng)度，N——兩多元時(shí)間序列的參數(shù)個(gè)數(shù)。σ＝［σA1，σA2，…，σAN］和τ＝ ［τB1，τB2，…，τBN］分別為矩陣A和B各列相對(duì)應(yīng)的權(quán)值。則帶權(quán)值的矩陣相似性度量定義如下

式中：wi——新的權(quán)值，表示如下

式中：｜＜ai，bi＞｜——矩陣A和B內(nèi)積的絕對(duì)值。當(dāng)sim （A，B）的值越大時(shí)表示矩陣A和B越相似，即表示多元時(shí)間序列A （M×N）和B（Q×N）的趨勢(shì)形態(tài)特征變化越一致。

3 改進(jìn)的K－means聚類算法

提出的基于哈達(dá)瑪變換和帶權(quán)值矩陣相似的聚類方法，首先用離散哈達(dá)瑪變換對(duì)多元數(shù)據(jù)進(jìn)行降維。然后求出多元變量相關(guān)系數(shù)矩陣的特征值作為權(quán)值。最后采用帶權(quán)值的矩陣相似性度量方法，利用改進(jìn)的K－means算法對(duì)多元時(shí)間序列進(jìn)行聚類分析。

（1）K－means聚類是目前應(yīng)用最為廣泛的聚類算法之一。K均值聚類算法的具體步驟如下：1.初始化k個(gè)聚類中心c1，c2，…ck（可隨機(jī)選取k個(gè)觀測(cè)點(diǎn)作為聚類中心）；2.循環(huán)執(zhí)行如下操作步驟：①將數(shù)據(jù)集中的觀測(cè)點(diǎn)根據(jù)它與聚類中心相似度的大小，把它分配到距離最近的類；②重新計(jì)算聚類中心，重復(fù)步驟2直到將聚類中心不再發(fā)生變換或者聚類次數(shù)達(dá)到了算法設(shè)定的最大循環(huán)次數(shù)。

根據(jù)以上對(duì)K－means算法的分析，它具有算法簡(jiǎn)單且收斂速度快的特點(diǎn)［15］，該算法也適合于研究多元時(shí)間序列的聚類分析。

為了更好地實(shí)現(xiàn)不等長(zhǎng)多元時(shí)間序列聚類，在數(shù)據(jù)預(yù)處理的前提下，對(duì)K－means算法進(jìn)行如下改進(jìn)：

（2）利用層次聚類算法，采用式 （3），找到K個(gè)變換后的矩陣及其相應(yīng)的權(quán)值向量作為聚類中心；

（3）將D中所有的元素 （D為n個(gè)變換后矩陣的集合），根據(jù)相似性大小，分配到相似性最大的簇中；

（4）重復(fù)計(jì)算每個(gè)新簇的中心 （每個(gè)簇中各個(gè)變換后矩陣的平均值及權(quán)值向量的平均值）；

（5）重復(fù) （2）、 （3）直至簇中心不再發(fā)生變化或迭代次數(shù)超過設(shè)定的最大迭代次數(shù)。

改進(jìn)算法的時(shí)間復(fù)雜性為o（knd），其中n為多元時(shí)間序列個(gè)數(shù)，K為聚類個(gè)數(shù)，d為多元序列參數(shù)個(gè)數(shù)，K與d遠(yuǎn)遠(yuǎn)小于n。

4 數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證

本文選取2009年30支長(zhǎng)度為239的股票數(shù)據(jù)，均取自sohu網(wǎng)的財(cái)經(jīng)板塊16。它們有開盤價(jià)、最高價(jià)、收盤價(jià)、最低價(jià)4個(gè)參數(shù)，具體如下：1包鋼稀土、2寶鋼股份、3波導(dǎo)股份、4東風(fēng)汽車、5歌華有線、6哈飛股份、7航天機(jī)電、8華夏銀行、9建發(fā)銀行、10金地集團(tuán)、11馬鋼股份、12民生銀行、13上港集團(tuán)、14上海能源、15四川長(zhǎng)虹、16鐵龍物流、17銅陵有色、18維科精華、19武漢控股、20新疆城建、21鄭州煤電、22中國船舶、23中國石化、24中國石油、25中國銀行、26中青旅、27中信證劵、28中原高速、29重慶啤酒、30紫金礦業(yè)。對(duì)以上股票數(shù)據(jù)進(jìn)行聚類分析，30支股票分為4類。

經(jīng)查文獻(xiàn)了解，目前國內(nèi)對(duì)于多元時(shí)間序列的研究大多致力于相似性研究，對(duì)多元時(shí)間序列聚類的算法研究才剛剛起步。下面用實(shí)驗(yàn)來驗(yàn)證本文方法在實(shí)現(xiàn)多元時(shí)間序列高效降維的基礎(chǔ)上，聚類的準(zhǔn)確性也有所提高，本文采用兩種實(shí)驗(yàn)方法。方法1：用哈達(dá)瑪變換進(jìn)行維歸約，用式（3）的相似性度量進(jìn)行聚類分析；方法2：用4層小波變換進(jìn)行維歸約，用式 （3）的相似性度量進(jìn)行聚類分析。維歸約后多元時(shí)間序列長(zhǎng)度為K，聚類結(jié)果只給出股票代號(hào)。

由實(shí)驗(yàn)結(jié)果表1～表4觀察可知，兩種方法的聚類準(zhǔn)確性都隨著選取序列長(zhǎng)度的增長(zhǎng)而提高，但是，當(dāng)選取的序列長(zhǎng)度繼續(xù)增長(zhǎng)時(shí)聚類準(zhǔn)確性會(huì)成降低趨勢(shì)。實(shí)驗(yàn)結(jié)果表明多元時(shí)間序列利用離散哈達(dá)瑪變化比離散小波變換具有更好的能量集中性即維歸約性能。

表1 序列長(zhǎng)度為4時(shí)的聚類結(jié)果

表2 序列長(zhǎng)度為6時(shí)的聚類結(jié)果

表3 序列長(zhǎng)度為8時(shí)的聚類結(jié)果

表4 序列長(zhǎng)度為16時(shí)的聚類結(jié)果

由以上聚類結(jié)果及其趨勢(shì)特征變換圖分析，最終準(zhǔn)確性高的聚類結(jié)果應(yīng)如表3所示，兩種方法中第一類和第三類中包含的股票代號(hào)相同。第二類和第四類包含的股票代號(hào)不同，主要差別是代號(hào)為12、16、19三支股票的歸屬。3種股票的立體三維趨勢(shì)形態(tài)特征用matlab7.1中的surf（X，Y，Z）函數(shù)繪制而成，其中，3個(gè)參數(shù)坐標(biāo)為X－維度（多元時(shí)間序列中參數(shù)的個(gè)數(shù)），Y－時(shí)間 （時(shí)間序列的時(shí)間間隔），Z－股票價(jià)格。股票趨勢(shì)形態(tài)如圖1所示，5、15號(hào)股票的趨勢(shì)形態(tài)特征是第二類股票形態(tài)特征的代表，9號(hào)股票的趨勢(shì)形態(tài)特征是第四類股票形態(tài)特征的代表。由圖1可以看出12號(hào)股票和第四類股票形態(tài)相似，16、19號(hào)股票與第二類相似。由以上分析可知，序列長(zhǎng)度取8時(shí)聚類效果較好，能有效地把不同趨勢(shì)變化形態(tài)的股票分配到不同的類中，即同一類中的股票趨勢(shì)形態(tài)特征盡可能的相似，不同類中的股票趨勢(shì)形態(tài)特征盡可能的不相似。實(shí)驗(yàn)聚類結(jié)果說明文中帶權(quán)值的相似性度量方法能很好的度量多元時(shí)間序列間的相似程度，同時(shí)，由圖1可以看出方法1比方法2的聚類準(zhǔn)確性要高，說明離散哈達(dá)瑪變換方法比離散小波變換方法進(jìn)行維歸約，前者數(shù)據(jù)能量集中性要高于后者。實(shí)驗(yàn)結(jié)果證明，基于離散哈達(dá)瑪變化進(jìn)行維歸約和帶權(quán)值的矩陣相似性度量的方法，能有效的實(shí)現(xiàn)多元時(shí)間序列有效聚類分析。

5 結(jié)束語

多元時(shí)間序列聚類的研究仍處于發(fā)展中，利用單元時(shí)間序列哈達(dá)瑪變換降維方法，其數(shù)據(jù)能量集中性相對(duì)較高。基于加權(quán)矩陣相似性原理，本文提出了基于哈達(dá)瑪變換的多元時(shí)間序列聚類研究方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠很好的實(shí)現(xiàn)多元時(shí)間序列聚類分析，把具有相同趨勢(shì)變化的多元時(shí)間序列分配到同一類中.當(dāng)然，多元時(shí)間序列權(quán)值的選擇不同對(duì)結(jié)果有一定的影響，在以后的研究中，還需考慮如何更科學(xué)的考慮權(quán)值的確定問題。

圖1 股票的形態(tài)特征變換趨勢(shì)

［1］WANG Qin.Time series analysis and application ［M］.Chengdu：Southwest Jiaotong University Press，2008 （in Chinese）. ［王沁.時(shí)間序列分析及其應(yīng)用 ［M］.成都：西南交通大學(xué)出版社，2008.］

［2］LAST M，Klein Y，Kandel A.Knowledge discovery in time series databases ［J］.IEEE Trans on Systems，Man and Cybernetics，2001，31 （1）：160－169.

［3］HUANGY，McAvoy T J，Gertler J.Fault isolation in nonlinear systems with structured partial principal component analysis and clustering analysis［J］.Can J Chem Engr，2000，78 （2）：569－577.

［4］WANG X Z，McGreavy C.Automatic clalssification for mining process operational data ［J］.Eng Chem Res，1998，37 （6）：2215－2222.

［5］YANG Kiyoung，Cyrus Shahabi.A PCA based similary multivariate time series［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17 （9）：65－74.

［6］ZHANG Xianda.Matrix analysis and application ［M］.Beijing：Tsinghua University Press，2004 （in Chinese）.［張賢達(dá).矩陣分析與應(yīng)用 ［M］.北京：清華大學(xué)出版社，2004.］

［7］Moon Y S，Kim J.Efficient moving average transform－based subsequence matching algorithms intime－series database ［J］.Information Sciences an Inter－National Journal，2007，177（23）：5415－5431.

［8］Kim S W，Park D H，Lee H G.Efficient processing of Subsequenee matching with the Euclidean metric in time－series databases［J］.Information Processing Letters，2004，90 （5）：253－260.

［9］Kontaki M，Papadopoulos A N， Manolopoulos Y.Adaptive similarity search in streaming time series with sliding Windows ［J］.Data ＆Knowledge Engineering，2007，63 （2）：478－502.

［10］QIAO Zhiwei，WEI Xueye，HAN Yan.Implement high speed linear convolution using fast Hadamard transform ［J］.Journal of Electronic Measurement and Instrument，2010，24 （3）：263－267（in Chinese）. ［喬志偉，魏學(xué)業(yè)，韓焱.用快速哈達(dá)瑪變換（FHT）實(shí)現(xiàn)高速線性卷積 ［J］.電子測(cè)量與儀器學(xué)報(bào)，2010，24 （3）：263－267.］

［11］HAN Jiawei.Data mining：Concept and technology ［M］.2nd ed.Beijing：Mechanical Industy Press，2006 （in Chinese）. ［HAN Jiawei.數(shù)據(jù)挖掘：概念與技術(shù) （英文版）［M］.2版.北京：機(jī)械工業(yè)出版社，2006.］

［12］YANG K，Shahabi C.A PCA－based similarity measure for multivariate time series［C］.Proceedings of the 2nd ACM International Workshop on Multimedia Databases.Washington，DC，USA：ACM Press，2004.

［13］MAO Hongbao，ZHANG Fengming.Similarity query in multivariate time series based on parameter importance degree［J］.Computer Engineering，2009，35 （24）：54－56 （in Chinese）.［毛紅保，張鳳鳴.基于參數(shù)重要度的多元時(shí)間序列相似性查詢 ［J］.計(jì)算機(jī)工程，2009，35 （24）：54－56.］

［14］ZHANG Jianpei，YANG Yue，YANG Jing，et al.Algorithm for initialization of K－means clustering center based on optimized－division［J］.Journal of System Simulation，2009，21（9）：2586－2590.

［15］Ordonez C，Omiecinski E.Efficient disk based K－means clustering for relational databases［J］.IEEE Trans on Knowledge and Data Engineering，2004，16 （8）：909－921.

［16］http：//business.sohu.com/ ［OL］.