基于鄰域保持嵌入的時間序列聚類融合算法*

劉 學(xué)，翁小清（河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061）

基于鄰域保持嵌入的時間序列聚類融合算法*

劉 學(xué)，翁小清
（河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061）

時間序列的維數(shù)比較大，直接對時間序列進(jìn)行聚類性能不理想。如何提高時間序列的聚類性能，是主要研究點。首先使用鄰域保持嵌入對時間序列樣本維數(shù)約簡，然后對維數(shù)約簡后的數(shù)據(jù)進(jìn)行聚類融合，最后將它的聚類性能與已有方法如主成分分析、分段聚合近似進(jìn)行比較。實驗表明，所提出的算法更能提高聚類性能。

時間序列；聚類融合；維數(shù)約簡；鄰域保持嵌入

0 引言

時間序列是一種高維且隨著時間變化而變化的數(shù)據(jù)。時間序列聚類在風(fēng)險管理、車輛檢測［1］、隧道通風(fēng)控制、交通流等領(lǐng)域廣泛應(yīng)用。

蘇木亞等人［2］提出了基于主成分分析（Principal Component Analysis，PCA）的時間序列聚類方法，但是PCA是線性方法，現(xiàn)實數(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的時間序列聚類融合算法，實驗結(jié)果表明，本文提出的算法與已有方法相比，更能提高聚類性能。

1 背景

1.1 鄰域保持嵌入

（1）構(gòu)造鄰域圖G。如果xj在xi的k近鄰中，就在兩個點之間放一條有向邊。

（2）計算加權(quán)矩陣W。通過解決最小化問題得到點xi到xj之間邊的權(quán)重Wij；如果xi與xj之間沒邊，則Wij=0。

（3）計算映射。通過解決一般特征值問題來獲得轉(zhuǎn)換向量a：其中，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)值

每個聚類成員的平均互信息為：

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ù)處理；

（3）計算加權(quán)矩陣W；

（6）使用K均值聚類將Y聚成M個類，進(jìn)行H次，得到H個聚類成員；

（7）計算每個聚類成員的權(quán)值；

（8）對聚類成員使用加權(quán)投票進(jìn)行聚類融合。

3 實驗

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

表1列出了來自不同領(lǐng)域的10個時間序列數(shù)據(jù)集［7］的主要特征。

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

3.2 評價準(zhǔn)則

聚類性能用 micro-p［6］表示，如式（6）所示。設(shè)數(shù)據(jù)集分為 c類 ｛C1，C2，…，Cc｝，n為樣本個數(shù)，ah表示實驗正確分到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 聚類結(jié)果比較

對表2中實驗結(jié)果進(jìn)行配對樣本t檢驗，結(jié)果如表3所示。

表3 配對樣本t檢驗

從表2、表 3可以看到，NPEC的平均 micro-p為0.8，高于其他方法。另外，原始數(shù)據(jù)、PCA、PAA分別與NPEC配對樣本t檢驗的概率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ù)就可以獲得不錯的聚類效果。

圖1 在Coffee數(shù)據(jù)集上micro-p隨d的變化情況

圖2為在Synthetic Control上，將d固定為43，micro-p隨k的變化情況。隨著k的增加，micro-p在一定范圍內(nèi)波動，說明k對聚類性能的影響較小。

圖2 在Synthetic Control數(shù)據(jù)集上micro-p隨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)一步研究。

圖3 在Face Four數(shù)據(jù)集上micro-p隨H的變化情況

［1］陳龍威，孫旭飛.一種基于時間序列分層匹配的騎線車輛檢測方法［J］.微型機與應(yīng)用，2014，33（21）：88-91.

［2］蘇木亞，郭崇慧.基于主成分分析的單變量時間序列聚類方法［J］.運籌與管理，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.

Time series clustering fusion algorithm based on neighborhood preserving embedding

Liu Xue，Weng Xiaoqing
（Information Technology College，Hebei University of Economics＆Business，Shijiazhuang 050061，China）

The dimension of time series is relatively large，and the clustering performance which clusters directly to the time series data is not ideal.How to improve the clustering performance of time series is the main research point of this paper.Firstly，it uses neighborhood preserving embedding to time series sample for dimensionality reduction.Then clustering fusion of data after dimension reduction is carried out.Finally，the clustering performance is compared with the existing methods，such as principal component analysis and piecewise aggregate approximation.Experiment shows that the proposed algorithm can improve the clustering performance.

time series；clustering fusion；dimension reduction；neighborhood preserving embedding

TP311.13

A

1674-7720（2015）20-0048-03

劉學(xué)，翁小清.基于鄰域保持嵌入的時間序列聚類融合算法［J］.微型機與應(yīng)用，2015，34（20）：48-50.

2015-07-29）

國家社會科學(xué)基金（ 13BTJ007 ）