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

韓 娜，滕少華，房小兆

（廣東工業大學 計算機學院，廣東 廣州510006）

0 引 言

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

針對多元時間序列不等長、數據量大及參數間的相關性等特點，文中提出基于離散哈達瑪變換及帶權值的矩陣相似性度量的多元時間序列聚類方法并進行了實驗驗證。

1 離散哈達瑪變換的維歸約

1.1 離散哈達瑪變換

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

定義1 一個長度為N的離散時間序列x（n），且N＝2q（q為正整數），哈達瑪變換［10］為

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

哈達瑪變換用哈達碼矩陣表示更直觀，且簡單易懂。哈達瑪矩陣是由＋1和－1構成的正交矩陣，實數表示且計算簡單，用其進行序列變換具有高效的數據能量集中性。

定義2 一個長度為N的離散時間序列x（n）＝［x（0），x （1），x （2），…，x （N－1）］，其哈達瑪變換表示為：XH（K）＝ ［XH（0），XH（1），XH（2），…，XH（N－1）］；哈達瑪矩陣為

則哈達瑪變換的矩陣表示為

定理1 設XH（K）是序列x（n）經離散哈達瑪變換后的序列，則序列變換前后保持能量不變，即

證明：離散哈達瑪變換是正交變換，正交變換在歐氏空間中保持內積，得證。

1.2 數據降維

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

對預處理后的多元時間序列數據進行維歸約的方法如下：

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

（2）對x進行離散哈達瑪變換。變換后的序列為XH。

（3）利用 （1）對XH進行調序，得到X。X即是我們需要的 （DWHT）H變換后的序列。

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

2 帶權值的矩陣相似性度量

2.1 多元時間序列權值的獲取

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

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

2.2 帶權值的矩陣相似性度量方法

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

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

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

式中：wi——新的權值，表示如下

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

3 改進的K－means聚類算法

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

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

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

為了更好地實現不等長多元時間序列聚類，在數據預處理的前提下，對K－means算法進行如下改進：

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

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

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

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

改進算法的時間復雜性為o（knd），其中n為多元時間序列個數，K為聚類個數，d為多元序列參數個數，K與d遠遠小于n。

4 數據實驗驗證

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

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

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

表1 序列長度為4時的聚類結果

表2 序列長度為6時的聚類結果

表3 序列長度為8時的聚類結果

表4 序列長度為16時的聚類結果

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

5 結束語

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

圖1 股票的形態特征變換趨勢

［1］WANG Qin.Time series analysis and application ［M］.Chengdu：Southwest Jiaotong University Press，2008 （in Chinese）. ［王沁.時間序列分析及其應用 ［M］.成都：西南交通大學出版社，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）.［張賢達.矩陣分析與應用 ［M］.北京：清華大學出版社，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）. ［喬志偉，魏學業，韓焱.用快速哈達瑪變換（FHT）實現高速線性卷積 ［J］.電子測量與儀器學報，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.數據挖掘：概念與技術 （英文版）［M］.2版.北京：機械工業出版社，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）.［毛紅保，張鳳鳴.基于參數重要度的多元時間序列相似性查詢 ［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］.