李 金 武

(鄭州科技學院信息工程學院 河南 鄭州 450064)

0 引 言

時間序列是一種具有高維特性，且與時間相關的連續(xù)型指標數(shù)據(jù)，廣泛存在于金融、氣象、交通和網(wǎng)絡安全等領域。如何從時間序列數(shù)據(jù)中挖據(jù)有價值的信息和知識為決策者提供有效的決策支持，是數(shù)據(jù)挖掘技術研究的方向之一[1-2]。如何對時間序列數(shù)據(jù)進行有效的約簡和降維，是數(shù)據(jù)挖掘的首要任務。

目前常用的數(shù)據(jù)降維技術有離散傅里葉變換(DFT)、離散小波變換(DWT)、分段線性表示(PLR)和分段聚合近似(PAA)等[3]。DFT能夠保留數(shù)據(jù)的全局特性，但是忽略了數(shù)據(jù)的局部特征，且只能應用于平穩(wěn)序列；DWT雖然可以提取和分析數(shù)據(jù)的局部特征，但只能應用于長度為2的整次冪的時間序列；PLR是用直線段來近似表示時間序列的局部波動，是一種較好的數(shù)據(jù)壓縮方法，但轉折點的提取是關鍵；PAA將時間序列平均分割成多段，每段用段內平均值表示，但子段寬度的確定并不具有普適性，且對于波動劇烈的時間序列，會嚴重丟失數(shù)據(jù)局部細節(jié)。

依據(jù)時間序列連續(xù)型指標數(shù)據(jù)的自身特性，提出一種自適應分段聚合云模型評價方法，利用云模型的熵評價分段序列穩(wěn)定性，動態(tài)識別時間序列數(shù)據(jù)特征并用云模型表示，同時基于云模型的距離和形狀，給出云模型相似度評價方法，對聚合后的時間序列關系進行評價度量。

1 云模型及分段聚合理論

1.1 云模型理論

云模型是處理定性概念與定量描述的不確定性轉換模型，反映了知識表達中模糊性與隨機性之間的關聯(lián)性，自李德毅院士1995年提出至今，云模型已經在數(shù)據(jù)挖掘[4]、自然語言處理[5]、安全評估[6]和決策分析[7-8]等領域得到應用，并取得良好效果。下面給出云模型相關概念。

定義1設U是用精確數(shù)值表示的定量論域，C是論域上的定性描述，對于x∈U，且x是C上的一次隨機實現(xiàn)，則x對于C的確定度y=yc(x)∈[0,1]是一個具有穩(wěn)定傾向的隨機數(shù)，把(x,y)在論域U上的分布稱為云[9]。

定義2用3個參量(Ex,En,He)表示云的數(shù)字特征的過程，稱為云模型，記作C(Ex,En,He)。Ex表示云模型的期望，是最能夠代表定性概念的點；En表示云模型的熵，反映了定性概念的模糊性和隨機性；He表示云模型的超熵，是云模型熵的不確定性度量，直接反映了云模型的厚度。

定義3對于任意云滴變量x，x滿足x～N(Ex,En′2)，且En′～N(En,He2)，存在一條曲線貫穿整個云滴集合，描述了云的整體幾何形態(tài)，這條曲線稱為云期望曲線，記作y(x)，y(x)解析式如下：

y(x)=exp[-(x-Ex)2/2En2]

(1)

定義4通過云的數(shù)字特征(Ex,En,He)產生n個云滴，實現(xiàn)定性概念到定量數(shù)據(jù)轉換的過程，稱為正向云發(fā)生器，記作cloud(Ex,En,He,n)。

定義5將一定數(shù)量的云滴x，且x∈X，轉換為某一定性概念，即實現(xiàn)定量數(shù)據(jù)到定性概念轉換的過程，稱為逆向云發(fā)生器，記作back_cloud(X)。

1.2 分段聚合理論

(2)

2 云模型分段聚合及評價方法

為了更好地對時間序列連續(xù)型指標進行評價，考慮連續(xù)型指標數(shù)據(jù)的局部特性，提出一種自適應分段聚合云模型評價方法。首先依據(jù)云模型的熵判斷分段聚合數(shù)據(jù)的穩(wěn)定性，自適應地形成穩(wěn)定性較好的云模型數(shù)據(jù)序列，其次給出云模型數(shù)據(jù)序列的相似度計算方法，對兩個時間段內同一連續(xù)型指標進行近似評價。

2.1 云模型自適應分段聚合

云模型自適應分段聚合是依據(jù)云模型的熵對數(shù)據(jù)進行可變長度的分段處理，打破傳統(tǒng)平均分割數(shù)據(jù)的處理方法，從而最大限度提取數(shù)據(jù)特征值，實現(xiàn)數(shù)據(jù)從高維到低維的不確定性轉換。首先利用逆向云發(fā)生器依次對當前分段數(shù)據(jù)進行云模型描述，得到各分段數(shù)據(jù)云模型數(shù)字特征，然后比較各分段數(shù)據(jù)云模型的熵，找到熵值最大的云模型所對應的原始分段數(shù)據(jù)，對這個原始分段數(shù)據(jù)再次進行云模型劃分。

在進行云模型劃分時，為了盡可能保留原始分段數(shù)據(jù)局部特征，需對其進行遍歷，找到關鍵點，對關鍵點前后兩段數(shù)據(jù)分別進行云模型描述，從而把熵值最大的云模型劃分為兩個新的云模型，確保被劃分云模型熵與新劃分的兩個云模型熵之和差值最大。

根據(jù)云模型分段聚合思想，設計云模型分段聚合算法，如算法1所示。

算法1云模型分段聚合算法

輸入：n維時間序列數(shù)據(jù)TD={td1,td2,…,tdn}，聚合后的維度m。

輸出：m維云模型數(shù)據(jù)序列CD={cd1,cd2,…，cdm}，cdi=[Exi,Eni,Hei]。

Step1利用逆向云發(fā)生器，對分段聚合數(shù)據(jù)進行預處理，提取數(shù)據(jù)特征值，用矩陣Vm×5記錄這些信息。其中:V(i,1∶3)表示第i個子序列云模型特征值[Exi,Eni,Hei];V(i,4∶5)表示第i個子序列在原時間序列中的始末位置[tf,tb]。初始設置i=1，V(i,1∶3)=back_cloud(TD)，V(i,4∶5)=[1,n]。

Step2若i>m，則程序結束，輸出CD，否則執(zhí)行Step 3。

Step3對當前矩陣Vi×5第二列V(1∶i,2)進行檢索，查找最大熵值，表示為V(i0,2),1≤i0≤i。其中最大熵值的索引號為i0，即第i0個子序列的云模型熵值最大。

Step4對當前第i0個子序列進行分段，分為兩段。提取第i0個子序列的始末位置信息，令t1=V(i0,4),t2=V(i0,5)，記第i0個子序列為TD(t1∶t2)。從子序列TD(t1∶t2)中搜索t0，t1

循環(huán)遍歷t0，通過計算使得ΔEn最大。

L(1∶5)=[back_cloud(TD(t1∶t0)),t1,t0]

R(1∶5)=[back_cloud(TD(t0∶t2)),t0,t2]

ΔEn=V(i0,2)(t2-t1)-[L(2)(t0-t1)+R(2)(t2-t0)]

Step5記V(i0,1∶5)=L,V(i0+1,1∶5)=R,i=i+1，返回Step 2。

2.2 云模型時間序列評價方法

對于降維后的云模型數(shù)據(jù)序列，需要利用云相似度評價方法來衡量兩個云模型之間的近似程度。由于正態(tài)云的期望曲線能夠較好地反映云模型的數(shù)字特征，綜合考慮云模型的形狀和距離，可以使用云模型期望曲線相交面積來計算相似度，在此特意把兩個云相交的面積提升至更高層面進行間接計算，充分體現(xiàn)云模型亦此亦彼的特性。

2.2.1云交點判定規(guī)則及“與”區(qū)域面積計算

兩個云相交的面積稱之為“與”區(qū)域面積，要計算其面積，首先要判定云期望曲線交點，云模型特征值直接影響交點個數(shù)和位置。設云模型Ci(Exi,Eni,Hei),i=1,2，yi(x)為云期望曲線，根據(jù)定義3，聯(lián)立云期望曲線組成的方程組，可求兩個云的交點。

(3)

在此可以不考慮云模型“3En”規(guī)則[11]，依據(jù)式(3)求得交點主要表現(xiàn)為以下幾種情況：

(1)Ex1≠Ex2,En1=En2，求得單交點p，如圖1(a)所示。

p=(Ex1En2+Ex2En1)/(En1+En2)

(2)Ex1=Ex2,En1≠En2，求得單交點p，如圖1(b)所示。

p=(Ex1En2+Ex2En1)/(En1+En2)=Ex1=Ex2

(3)Ex1En2，求得雙交點p1、p2，如圖1(c)所示。

(4)Ex1=Ex2,En1=En2，兩條云期望曲線重合，在此不考慮云交點，如圖1(d)所示。

(a) Ex1≠Ex2,En1=En2

(b) Ex1=Ex2,En1≠En2

(c) Ex1≠Ex2,En1≠En2

(d) Ex1=Ex2,En1=En2圖1 云交點及”與”區(qū)域面積圖

令“與”區(qū)域面積為S∩，其計算方法可以通過積分求得，云的位置關系不同，S∩的求法也不盡相同，在此先根據(jù)云交點判定規(guī)則確定交點，S∩主要有以下幾種不同的情況:

(1) 存在雙交點p1、p2，不妨設p1

代入云期望曲線：

考慮到被積函數(shù)不可積，對其變形為標準正態(tài)分布函數(shù)求積分，進行變量換元代換，令u=(x-Ex1)/En1，v=(x-Ex2)/En2，dx=En1·du=En2·dv。

令Φ(·)為標準正態(tài)分布概率分布函數(shù)，其值可以通過查表求得，則S∩變形為：

(2) 存在單交點p，如圖1(a)所示，S∩由兩部分組成。

進行變量換元代換，令u=(x-Ex2)/En2，v=(x-Ex1)/En1，dx=En2·du=En1·dv，Φ(·)為標準正態(tài)分布概率分布函數(shù)，S∩變形為：

(3) 存在云重合或包含關系，如圖1(b)和圖1(d)所示，S∩只有一部分，且由較小云(若云重合，選其中任何一個)進行積分求得。

進行變量換元代換，令u=(x-Ex2)/En2，dx=En2·du，S∩變形為：

2.2.2綜合云生成規(guī)則及云相似度評價方法

綜合云[12]是兩個基礎云在更高層面的不確定性表示，它包含低層次概念的全部信息，由此可以利用基礎云的截斷熵計算綜合云。把截斷熵作為權重，通過加權求和計算綜合云的期望和超熵，而綜合云的熵為兩個基礎云截斷熵之和。設基礎云Ci(Exi,Eni,Hei),i=1,2，yi(x)為云期望曲線，Li(x)代表論域上兩期望曲線最大值，反映交點對期望曲線的分段表示。

把基礎云的截斷熵作為權值，利用式(4)計算綜合云的數(shù)字特征，即綜合云Cz(Exz,Enz,Hez)。

(4)

基礎云與綜合云“與”區(qū)域面積大小決定了基礎云概念對綜合云概念的貢獻程度，“與”區(qū)域面積越大，則對綜合云概念的貢獻程度越大，此時兩個基礎云越接近。將基礎云和綜合云放到同一云圖中，如圖2所示，y1(x)、y2(x)為基礎云期望曲線，yz(x)為綜合云期望曲線，p1、p2是y1(x)與yz(x)的交點，p3、p4是y2(x)與yz(x)的交點，設待評價基礎云Ci與綜合云Cz“與”區(qū)域面積分別為S∩1和S∩2，綜合云與橫軸所圍面積為Sz。

圖2 基礎云與綜合云位置關系

S∩1和S∩2可以通過2.2.1節(jié)方法求得，Sz通過積分求得。

進行變量換元代換，令u=(x-Exz)/Enz，dx=Enz·du，S2變形為：

綜合考慮基礎云對綜合云的貢獻程度，定義兩個基礎云的相似度為：

(5)

式(5)是基于云期望曲線“與”面積確定的云相似度，僅從距離上考慮云模型的相似性，忽略云模型形狀，在此提出一種通過云模型超熵進行修正的相似性度量方法，兼顧云模型的距離和形狀，對式(5)進行修正，修正后的相似度為：

s(C1,C2)sxz(C1,C2)∈[0,1]

(6)

如果給定兩個n維時間序列數(shù)據(jù)S和R，通過2.1節(jié)方法進行云模型分段聚合，降維以后得到兩個m維云模型數(shù)據(jù)序列SC和RC，定義兩個云模型數(shù)據(jù)序列的相似度TDS。

TDS(SC,RC)∈[0,1]

(7)

3 實驗仿真

為了更好地驗證評價方法的有效性，采用實際的交通流調查數(shù)據(jù)，對2018年9月10號某條道路一天的交通流進行分析，本條道路分為4車道，主要從兩個方面進行分析，即道路交通流的分段聚合效果和車道交通流的相似度。數(shù)據(jù)集含有5個交通流時間序列，即Lane 1(1車道)、Lane 2(2車道)、Lane 3(3車道)、Lane 4(4車道)和Lane #(#道路)，其中Lane #為全部4車道的車流量之和，從0:00到23:55每隔5分鐘記錄一次車流量變化情況，即每個交通流時間序列有288個車流量狀態(tài)數(shù)據(jù)，車流量如圖3所示。

圖3 車流量變化

3.1 分段聚合效果分析

利用云模型分段聚合方法，可以自適應地對交通流數(shù)據(jù)進行特征識別和表示，把具有相同特征的交通流數(shù)據(jù)劃分為一段，并用云模型表示。通過Lane#交通流分析分段聚合效果，對交通流數(shù)據(jù)進行10維和6維的云模型分段聚合處理，處理結果如表1和表2所示，其中(t0,t1)表示t0到t1的數(shù)據(jù)聚合為一段。

表1 Lane #分段聚合及云模型特征-10維

表2 Lane #分段聚合及云模型特征- 6維

依據(jù)表1和表2的分段序列，對Lane#交通流數(shù)據(jù)進行分段，分段效果如圖4和圖5所示，時間維度波動較小的數(shù)據(jù)，即數(shù)據(jù)特征近似的會被自動劃分為一段，有利于下一步從時間維度上進行數(shù)據(jù)相似度的評價。從6維到10維的分段聚合過程來看，隨著分段維度的增大，能夠根據(jù)數(shù)據(jù)特征的近似性自動進行分段，最大限度保持時間維度上數(shù)據(jù)的局部特征。

圖4 分段聚合效果-10維

圖5 分段聚合效果- 6維

3.2 云模型序列相似度分析

在時間維度上對云模型序列進行相似度分析，首先需對原始數(shù)據(jù)進行分段聚合并用云模型表示。在此，對4個車道交通流數(shù)據(jù)依次進行分段聚合，得到4個10維的云模型序列，聚合后的云模型特征見表3-表6。

表4 Lane 2交通流云模型特征

表5 Lane 3交通流云模型特征

表6 Lane 4交通流云模型特征

依據(jù)表3-表6的云模型數(shù)字特征，得到云模型曲線如圖6所示，(a)-(d)依次為4個車道交通流云模型曲線，在時間維度上表現(xiàn)為10個云，用ti表示第i個時間片的云模型描述，1≤i≤10。

(a) Lane 1

(b) Lane 2

(c) Lane 3

(d) Lane 4圖6 交通流聚合云模型曲線-10維

利用TDS算法，在時間維度上計算云模型序列相似度，如表7所示。Lane 2與Lane 4全天車流量相似度為0.715 6，相似度最高；Lane 1與Lane 3全天車流量相似度為0.608 9，相似度最低，即交通流變化特性較之其他車道差異性較大。

表7 TDS算法計算相似度

4 結 語

本文提出時間序列云模型相似度評價方法，利用云模型的熵來判斷分段子序列的穩(wěn)定性，自適應地對時間序列進行分段聚合。同時給出TDS相似度評價算法，該算法把云模型相似度評價提升至更高層面，基于云期望曲線的相交面積進行評價，并且通過云模型的超熵對相似度進行修正，充分體現(xiàn)云模型亦此亦彼的特性，是對不確定性問題的一種新探索。實驗結果表明，該方法較之經典聚合近似PAA，具有更好的聚合效果，同時在時間維度上進行的相似度評價更符合現(xiàn)實情況，特別是對于隨機性和突發(fā)性較強的數(shù)據(jù)序列，效果會更加明顯。然而如何降低算法復雜度，如何確定分段聚合的維度，是今后研究需要進一步探討的問題。