基于哈達(dá)瑪變換的多元時間序列聚類研究

韓 娜，滕少華，房小兆

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

0 引 言

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

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

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

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

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

定義1 一個長度為N的離散時間序列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á)碼矩陣表示更直觀，且簡單易懂。哈達(dá)瑪矩陣是由＋1和－1構(gòu)成的正交矩陣，實(shí)數(shù)表示且計算簡單，用其進(jìn)行序列變換具有高效的數(shù)據(jù)能量集中性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文選取2009年30支長度為239的股票數(shù)據(jù)，均取自sohu網(wǎng)的財經(jīng)板塊16。它們有開盤價、最高價、收盤價、最低價4個參數(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四川長虹、16鐵龍物流、17銅陵有色、18維科精華、19武漢控股、20新疆城建、21鄭州煤電、22中國船舶、23中國石化、24中國石油、25中國銀行、26中青旅、27中信證劵、28中原高速、29重慶啤酒、30紫金礦業(yè)。對以上股票數(shù)據(jù)進(jìn)行聚類分析，30支股票分為4類。

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

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

表1 序列長度為4時的聚類結(jié)果

表2 序列長度為6時的聚類結(jié)果

表3 序列長度為8時的聚類結(jié)果

表4 序列長度為16時的聚類結(jié)果

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

5 結(jié)束語

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

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

［1］WANG Qin.Time series analysis and application ［M］.Chengdu：Southwest Jiaotong University Press，2008 （in Chinese）. ［王沁.時間序列分析及其應(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］.電子測量與儀器學(xué)報，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ù)重要度的多元時間序列相似性查詢 ［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］.