摘 要： 時間序列的維數(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),。
（1）構(gòu)造鄰域圖G,。如果xj在xi的k近鄰中,，就在兩個點(diǎn)之間放一條有向邊。
?。?）計算加權(quán)矩陣W,。通過解決最小化問題得到點(diǎn)xi到xj之間邊的權(quán)重Wij；如果xi與xj之間沒邊,，則Wij=0,。
其中，
?。?）計算映射,。通過解決一般特征值問題來獲得轉(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é)果
?。?）使用PCA對數(shù)據(jù)集進(jìn)行預(yù)處理；
?。?）yi←APCATxi,，其中，APCA是PCA的轉(zhuǎn)換矩陣,；
?。?）計算加權(quán)矩陣W；
?。?）假設(shè)ANPE=[a0,，a1，…,，ad-1],，特征值排序后為0≤λ0≤…≤λd-1；
?。?）yi=ANPETxi，得到變換后的矩陣Y,；
?。?）使用K均值聚類將Y聚成M個類，進(jìn)行H次,，得到H個聚類成員,；
（7）計算每個聚類成員的權(quán)值,；
?。?）對聚類成員使用加權(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ì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.