摘 要： 時間序列的維數(shù)比較大，直接對時間序列進(jìn)行聚類性能不理想。如何提高時間序列的聚類性能，是主要研究點(diǎn)。首先使用鄰域保持嵌入對時間序列樣本維數(shù)約簡，然后對維數(shù)約簡后的數(shù)據(jù)進(jìn)行聚類融合，最后將它的聚類性能與已有方法如主成分分析、分段聚合近似進(jìn)行比較。實(shí)驗(yàn)表明，所提出的算法更能提高聚類性能。
關(guān)鍵詞： 時間序列；聚類融合；維數(shù)約簡；鄰域保持嵌入
0 引言
時間序列是一種高維且隨著時間變化而變化的數(shù)據(jù)。時間序列聚類在風(fēng)險管理、車輛檢測[1]、隧道通風(fēng)控制、交通流等領(lǐng)域廣泛應(yīng)用。
蘇木亞等人[2]提出了基于主成分分析（Principal Component Analysis，PCA）的時間序列聚類方法，但是PCA是線性方法，現(xiàn)實(shí)數(shù)據(jù)集往往具有非線性特征；李海林等人[3]先用分段聚合近似（Piecewise Aggregate Approximation，PAA）對時間序列降維，然后進(jìn)行聚類，但是PAA沒有考慮樣本之間的內(nèi)在關(guān)系。鄰域保持嵌入（Neighborhood Preserving Embedding，NPE）[4]是局部線性嵌入（Locally Linear Embedding，LLE）[5]的線性近似，它清晰地考慮了數(shù)據(jù)的流形結(jié)構(gòu)，約簡后的數(shù)據(jù)可以最優(yōu)地保持原數(shù)據(jù)集的局部鄰域信息，并考慮了樣本之間的內(nèi)在關(guān)系。
針對單一聚類算法存在結(jié)果不穩(wěn)定的問題，現(xiàn)在趨向于融合多個聚類的結(jié)果，即聚類融合。本文提出了一種基于NPE的時間序列聚類融合算法，實(shí)驗(yàn)結(jié)果表明，本文提出的算法與已有方法相比，更能提高聚類性能。
1 背景
1.1 鄰域保持嵌入
設(shè)原始數(shù)據(jù)集X={x1，x2，…，xn}?奐Rl，NPE[4]找到變換矩陣A。使用A將X映射到Y(jié)={y1，y2，…，yn}Rd，（d<<l），能夠保持X的局部結(jié)構(gòu)。
?。?）構(gòu)造鄰域圖G。如果xj在xi的k近鄰中，就在兩個點(diǎn)之間放一條有向邊。
?。?）計(jì)算加權(quán)矩陣W。通過解決最小化問題得到點(diǎn)xi到xj之間邊的權(quán)重Wij；如果xi與xj之間沒邊，則Wij=0。
其中，
?。?）計(jì)算映射。通過解決一般特征值問題來獲得轉(zhuǎn)換向量a：
XMXTa=λXXTa（2）
其中，X=（x1，…，xn），M=（I-W）T（I-W），I=diag（1，…，1）。假設(shè)A=[a0，a1，…，ad-1]，特征值排序后為0≤λ0≤…≤λd-1。得到y(tǒng)：yi=ATxi，其中yi是d維向量，A是l×d矩陣。
1.2 基于互信息的聚類成員的權(quán)值
聚類成員Pa、Pb類標(biāo)記用{P1a，P2a，…，Pka}和{P1b，P2b，…，Pkb}表示。設(shè)Pia中有ni個元素，Pjb中有nj個元素，Pia和Pjb中相同元素有nij個?；バ畔ⅶ禡I為[6]：
每個聚類成員的平均互信息為：
βm越大，聚類成員Pm所包含的特有信息就越少，其權(quán)值[6]可定義為：
其中，Z是對權(quán)值標(biāo)準(zhǔn)化，wm>0且
2 時間序列聚類融合算法
算法包括三步：首先，使用NPE對數(shù)據(jù)集進(jìn)行維數(shù)約簡；其次，對降維后的數(shù)據(jù)進(jìn)行聚類，產(chǎn)生聚類成員；最后，使用加權(quán)投票法進(jìn)行聚類融合。
聚類融合算法如下：
輸入：數(shù)據(jù)集Data，近鄰個數(shù)k，嵌入維數(shù)d，聚類個數(shù)M，聚類成員個數(shù)H
輸出：聚類結(jié)果
（1）使用PCA對數(shù)據(jù)集進(jìn)行預(yù)處理；
?。?）yi←APCATxi，其中，APCA是PCA的轉(zhuǎn)換矩陣；
（3）計(jì)算加權(quán)矩陣W；
?。?）假設(shè)ANPE=[a0，a1，…，ad-1]，特征值排序后為0≤λ0≤…≤λd-1；
?。?）yi=ANPETxi，得到變換后的矩陣Y；
?。?）使用K均值聚類將Y聚成M個類，進(jìn)行H次，得到H個聚類成員；
（7）計(jì)算每個聚類成員的權(quán)值；
（8）對聚類成員使用加權(quán)投票進(jìn)行聚類融合。
3 實(shí)驗(yàn)
3.1 數(shù)據(jù)集描述
表1列出了來自不同領(lǐng)域的10個時間序列數(shù)據(jù)集[7]的主要特征。
3.2 評價準(zhǔn)則
聚類性能用micro-p[6]表示，如式（6）所示。設(shè)數(shù)據(jù)集分為c類{C1，C2，…，Cc}，n為樣本個數(shù)，ah表示實(shí)驗(yàn)正確分到Ch中的樣本個數(shù)，micro-p越大，聚類效果越好。
3.3 性能比較
每一種測試重復(fù)10次，記錄平均的micro-p，結(jié)果如表2所示。第2列是在原始數(shù)據(jù)上進(jìn)行K均值聚類的micro-p，第3、4、5列分別是對PCA、PAA以及NPE降維后的數(shù)據(jù)進(jìn)行K均值聚類時最高的micro-p以及相應(yīng)嵌入空間的維數(shù)；第6列給出了對NPE降維后的數(shù)據(jù)進(jìn)行聚類融合最高的micro-p以及相應(yīng)聚類成員個數(shù)，用NPEC表示聚類融合算法。
對表2中實(shí)驗(yàn)結(jié)果進(jìn)行配對樣本t檢驗(yàn)，結(jié)果如表3所示。
從表2、表3可以看到，NPEC的平均micro-p為 0.8，高于其他方法。另外，原始數(shù)據(jù)、PCA、PAA分別與NPEC配對樣本t檢驗(yàn)的概率p值都小于0.05，說明NPEC的聚類性能顯著地好于這三種方法。
3.4 參數(shù)對算法性能的影響
圖1為在Coffee上，將k固定為10，micro-p隨d的變化情況。當(dāng)d較小時，micro-p較低，聚類性能較差。產(chǎn)生這種情況，一種可能的解釋為數(shù)據(jù)集中不同的樣本經(jīng)過NPE映射以后，在低維空間重疊在了一起。隨著d增加，micro-p快速上升，說明本文提出的算法并不需要很高的嵌入維數(shù)就可以獲得不錯的聚類效果。
圖2為在Synthetic Control上，將d固定為43， micro-p隨k的變化情況。隨著k的增加，micro-p在一定范圍內(nèi)波動，說明k對聚類性能的影響較小。
圖3給出在Face Four上，micro-p隨H的變化情況。當(dāng)H從5增長到100時，micro-p逐漸提高，當(dāng)H繼續(xù)增大時，micro-p保持穩(wěn)定并在一定范圍內(nèi)波動。
4 結(jié)論
本文提出了一種基于NPE的時間序列聚類融合算法，與已有方法PCA、PAA相比，這種方法更能提高聚類性能。在算法中，如何選擇最優(yōu)的嵌入維數(shù)以及共識函數(shù)的設(shè)計(jì)，值得今后進(jìn)一步研究。
參考文獻(xiàn)
[1] 陳龍威，孫旭飛.一種基于時間序列分層匹配的騎線車輛檢測方法[J].微型機(jī)與應(yīng)用，2014，33（21）：88-91.
[2] 蘇木亞，郭崇慧.基于主成分分析的單變量時間序列聚類方法[J].運(yùn)籌與管理，2011（6）：66-72.
[3] 李海林，郭崇慧，楊麗彬.基于分段聚合時間彎曲距離的時間序列挖掘[J].山東大學(xué)學(xué)報，2011，41（5）：57-62.
[4] He Xiaofei， Cai Deng， Yan Shuicheng， et al. Neighborhood preserving embedding[C]. IEEE International Conference on Computer Vision， 2005：1208-1213.
[5] ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science， 2000， 290（5500）：2323-2326.
[6] 唐偉，周志華.基于Bagging的選擇性聚類集成[J].軟件學(xué)報，2005，16（4）：496-502.
[7] Chen Yanping， KEOGH E， et al. The UCR Time Series Classification Archive. www.cs.ucr.edu/~eamonn/time_series_data/.2015.