劉 學，翁小清

（河北經貿大學信息技術學院，河北 石家莊 050061）

聚類就是將未標記的實例對象根據(jù)它們之間的相似度進行分組，使組內實例之間的相似度最大，而組與組之間的實例相似度最小，以達到發(fā)現(xiàn)隱藏在數(shù)據(jù)中的內部結構的目的。時間序列［1］通常是一種高維且隨著時間變化而變化的數(shù)據(jù)，它的產生過程極易受環(huán)境因素的影響，并且存在一定的噪聲。時間序列聚類廣泛應用于金融、交通、醫(yī)學、手勢識別等領域。

時間序列一般維數(shù)很高，為了可以有效的進行時間序列聚類，通常需要將樣本的維數(shù)進行約簡。如今維數(shù)約簡的方法有很多，比如，小波、傅里葉變換、主成分分析［2］（Principal Component Analysis，PCA）、分段聚合近似［3，4］（Piecewise Aggregate Approximation，PAA）等。PCA是將多個關聯(lián)變量轉化為幾個非關聯(lián)的綜合變量，在現(xiàn)實中數(shù)據(jù)集往往具有非線性的特征，而PCA屬于線性維數(shù)約簡方法，由于PCA的這種線性局限性，使得它對具有非線性結構的數(shù)據(jù)集映射效果不好。PAA是通過對時間序列進行平均分割并利用分段序列的均值來表示原時間序列特征的方法，但是它沒有考慮數(shù)據(jù)集中各時間序列樣本之間的內在關系。局部線性嵌入［5］（Locally Linear Embedding，LLE）是一種非線性維數(shù)約簡方法，利用局部線性嵌入映射來逼近全局的非線性流形。LLE使得在高維空間中相鄰的點映射到低維空間之后應該也是相鄰的。

本文提出了一種基于LLE的時間序列聚類方法，首先使用LLE對時間序列樣本維數(shù)約簡，在低維空間對維數(shù)約簡后的數(shù)據(jù)進行聚類，將它的聚類性能與已有方法如PCA、PAA進行了比較，對實驗結果進行配對樣本t檢驗，實驗結果表明，本文提出的方法更能提高聚類性能。

1 局部線性嵌入

LLE是由Sam T.Roweis和Lawrence K.Saul提出的一種非線性降維方法。LLE的基本思想是：利用局部線性嵌入映射來逼近全局的非線性流形。在由高維空間向低維空間嵌入的過程中，流形上每個點的局部結構不變，LLE是通過使用它的近鄰點重構這個點來實現(xiàn)的。

對于LLE算法，我們給一個簡單的介紹［6］。已知原始數(shù)據(jù)集X＝ ｛x1，x2，…，xn｝?Rl，對每個點xi，找到它的k近鄰。計算每個點與它的近鄰點之間的權重wij，即最小化誤差函數(shù)：

其中，xj是xi的第j個鄰域，wij表示xi與xj之間的權重，N是數(shù)據(jù)集中點的個數(shù)＝1，當xj不是xi的k近鄰時，wij＝0。

使用上一步的重構權重，計算xi在低維空間的嵌入yi。最小化下面的代價函數(shù)可以得到低維空間向量：

為了使低維數(shù)據(jù)均勻分布，對y進行規(guī)范化限制。其中其中O是每一個分量都為0的列向量，I是單位矩陣。

2 基于LLE的時間序列聚類算法

提出的基于LLE的時間序列聚類算法包括三步：首先，對每個樣本點求它的k個近鄰點；其次，由每個樣本點的k個近鄰點計算出該樣本的局部重構權值矩陣W；最后，根據(jù)W和近鄰點計算出樣本在低維空間的嵌入。

LLE聚類算法描述：

輸入：數(shù)據(jù)集，Data，近鄰個數(shù)，k，嵌入維數(shù)，d，聚類個數(shù)，M

輸出：聚類結果

Step1：使用PCA對數(shù)據(jù)集進行預處理，去掉噪聲，保留原數(shù)據(jù)集的主要信息。

Step2：對每個點xi，找到它的k近鄰。

Step3：計算每個點xi的重構權重Wi，使誤差函數(shù)（1）最小。

Step4：使用上一步的重構權重Wi，計算xi在低維空間的嵌入yi，使得代價函數(shù)（2）最小，由此得到降維后的矩陣Y。

Step5：使用K均值聚類，將Y聚成M個類。

算法分析：

用N表示數(shù)據(jù)集中樣本個數(shù)，每個樣本用一維向量來表示，輸入樣本的維數(shù)為D。在第一步中，使用PCA對數(shù)據(jù)集進行預處理的時間復雜度［7］為O（ND2）。LLE的復雜度分為三部分：一是k近鄰搜索。二是計算權值wij。三是計算低維嵌入值Y。在k近鄰搜索中，復雜度為O（DN2）。在計算權值wij時，復雜度為O（DNK3），其中，K為近鄰個數(shù)。在計算低維嵌入值Y時，復雜度為O（dN2），其中，d為所嵌入的維數(shù)。因此，LLE算法的復雜度［8］為O（（D＋d）N2＋DNK3）。K均值聚類的復雜度［9］是O（hNM），其中，h為迭代次數(shù)，M為簇數(shù)，即聚類個數(shù)。所以算法的復雜度為O（（D＋d）N2＋DN（K3＋D）＋hNM）。

3 實驗

在10個時間序列數(shù)據(jù)集上，對本文提出的基于LLE的聚類算法的性能進行了測試，并與使用PCA和PAA進行K均值聚類的性能進行了比較。在實驗中，采用micro－p（micro－precision）［10，11］度量聚類的性能。使用不同參數(shù)時，聚類的micro－p值可能不同，在此只給出了各種方法的最高的micro－p值以及相應的參數(shù)。下面分別對實驗數(shù)據(jù)、比對的算法以及實驗的結果進行介紹。

3.1 數(shù)據(jù)集描述

本實驗在10個時間序列數(shù)據(jù)集［12］上進行了測試，這些數(shù)據(jù)集來自醫(yī)學、手勢識別、化學、生物信息等領域。表1列出了這10個數(shù)據(jù)集的主要特征，包括類別個數(shù)、樣本總數(shù)以及時間序列的長度。

表1 數(shù)據(jù)集描述

3.2 評價準則

聚類性能用micro－p表示，在一個已經有已知類別的數(shù)據(jù)集中，假設數(shù)據(jù)集分為c類，｛C1，C2，…，Cc｝。通過聚類實驗得到數(shù)據(jù)集中每個樣本的類別標號。ah表示被正確分到類Ch中的樣本的個數(shù)，n為數(shù)據(jù)集中樣本個數(shù)。

3.3 性能比較

表2給出了在10個數(shù)據(jù)集上，分別使用原始數(shù)據(jù)，PCA，PAA以及LLE進行K－均值聚類的micro－p值；對于每一種測試都重復10次實驗，然后記錄下平均的micro－p值；第2列給出了在原始數(shù)據(jù)上直接進行K－均值聚類的micro－p值，第3列、第4列、第5列分別給出了使用PCA、PAA以及LLE進行聚類時最高的micro－p值以及相應嵌入空間的維數(shù)。

表2 三種維數(shù)約簡算法聚類結果比較

為了對聚類結果的平均值進行顯著差異的判斷，我們采用配對樣本t檢驗［13］。

它是根據(jù)樣本數(shù)據(jù)對兩個配對樣本來自的兩個配對總體的均值是否有顯著差異進行判斷。使用matlab對原始數(shù)據(jù)與LLE、PCA與LLE、PAA與LLE進行了配對樣本t檢驗，計算出的t統(tǒng)計量值以及概率p值如表3所示。

從表2以及表3可以看到，原始數(shù)據(jù)與LLE的配對樣本t統(tǒng)計量為－4.4595，概率p值為0.0016＜0.05，說明使用LLE的聚類性能顯著地好于直接在原始數(shù)據(jù)上進行聚類的聚類性能。在10個數(shù)據(jù)集上，使用LLE的平均micro－p值為0.737136，而原始數(shù)據(jù)的平均micro－p值為0.607146。

表3 配對樣本t檢驗

PCA與LLE的配對樣本t統(tǒng)計量為－3.2883，概率p值為0.0094＜0.05，說明使用LLE的聚類性能顯著地好于使用PCA的聚類性能。在10個數(shù)據(jù)集上，使用LLE的平均micro－p值為0.737136，而使用PCA的平均micro－p值為0.637418。

PAA與LLE的配對樣本t統(tǒng)計量為－2.3952，概率p值為0.0402＜0.05，說明使用LLE的聚類性能顯著地好于使用PAA的聚類性能。在10個數(shù)據(jù)集上，使用LLE的平均micro－p值為0.737136，而使用PAA的平均micro－p值為0.672291。

3.4 參數(shù)對算法性能的影響

基于LLE的聚類算法，有兩個參數(shù)，一個是嵌入維數(shù)d，另一個是近鄰個數(shù)k。為了觀察參數(shù)對算法性能的影響，我們先將近鄰個數(shù)k固定，讓嵌入維數(shù)d從1變化50。圖1給出了在Coffee數(shù)據(jù)集上，將近鄰個數(shù)k固定為25，micro－p隨嵌入維數(shù)d的變化情況；圖2給出了在Gun Point數(shù)據(jù)集上，將近鄰個數(shù)k固定為5，micro－p隨嵌入維數(shù)d的變化情況。從圖1和圖2可以看到，當嵌入維數(shù)d比較小時，micro－p有一個快速上升和快速下降的過程，之后趨于平緩。由此可以看出本文提出的基于LLE的時間聚類方法，并不需要很高的嵌入維數(shù)就可以獲得不錯的聚類效果。

圖1 在Coffee數(shù)據(jù)集上micro－p隨嵌入維數(shù)變化情況

圖2 在Gun Point數(shù)據(jù)集上micro－p隨嵌入維數(shù)變化情況

將嵌入維數(shù)d固定，讓近鄰個數(shù)k從1變化50。圖3給出了在ECG數(shù)據(jù)集上，將嵌入維數(shù)d固定為6，micro－p隨近鄰個數(shù)k變化情況；圖4給出了在GunPoint數(shù)據(jù)集上，將嵌入維數(shù)d固定為3，micro－p隨近鄰個數(shù)k變化情況。從圖3和圖4可以看到，隨著近鄰個數(shù)k的增加，micro－p的值在一定范圍內波動，比較穩(wěn)定，近鄰個數(shù)k對聚類性能的影響較小。

圖3在ECG數(shù)據(jù)集上micro－p隨近鄰個數(shù)k變化情況

圖4 在Gun Point數(shù)據(jù)集上micro－p隨近鄰個數(shù)k變化情況

4 總結

本文提出了基于局部線性嵌入的時間序列聚類方法，使用LLE方法對時間序列樣本維數(shù)約簡，在低維空間對維數(shù)約簡后的數(shù)據(jù)進行聚類，通過將它的聚類性能與已有方法PCA、PAA進行比較，證明了這種方法更能提高聚類性能。在基于LLE的時間序列聚類中，有兩個參數(shù)，一個是嵌入維數(shù)d，另一個是近鄰個數(shù)k，如何選擇“最優(yōu)”的嵌入維數(shù)以及適當?shù)慕弬€數(shù)，值得今后進一步研究。

［1］ 李海林.時間序列數(shù)據(jù)挖掘中的特征表示與相似性度量方法研究［D］.大連：大連理工大學，2012.

［2］ Jackson J E.A User＇s Guide to Principal Components［J］.Series in Probability ＆ Mathematical Statistics Applied Probability ＆Statistics，1991，29（1）：493－494.

［3］ Keogh E，Chakrabarti K ，Pazzani M，et al.Dimensionality reduction for fast similarity search in large time series databases［J］.Journal of Knowledge and Information Systems，2000，3（3）：263－286.

［4］ Yi B K，F(xiàn)aloutsos C.Fast Time Sequence Indexing for Arbitrary Lp Norms［J］.Vldb Journal，2000：385－394.

［5］ Roweis ST，Saul LK.Nonlinear dimensionality reduction by Locally Linear Embedding［J］.Science，2000，290：2323－2326.

［6］ 翁小清，沈鈞毅.多變量時間序列的異常識別與分類研究［D］，西安，西安交通大學，2008.

［7］ 李強，裘正定，孫冬梅，等.基于改進二維主成分分析的在線掌紋識別［J］.電子學報，2005，33（10）：1886－1889.

［8］ Roweis ST，Saul LK.An Introduction to Locally Linear Embedding［J］.Science，2000，290：2323－2326.

［9］ Han JW，Kamber M.數(shù)據(jù)挖掘概念與技術［M］.第3版，北京：機械工業(yè)出版社，2001.

［10］ Zhou Z H，Tang W.Clusterer ensemble［J］.Knowledge－Based Systems，2006，19（1）：77－83.

［11］ 唐偉，周志華.基于Bagging的選擇性聚類集成［J］.軟件學報，2005，16（4）：496－502.

［12］ http：／／www.cs.ucr.edu／～eamonn／

［13］ 盛驟，謝式千.概率論與數(shù)理統(tǒng)計［M］.北京：高等教育出版社，2001.