基于自適應(yīng)分段聚合的云模型序列相似度評(píng)價(jià)方法

李 金 武

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

0 引 言

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

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

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

1 云模型及分段聚合理論

1.1 云模型理論

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

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

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

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

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

(1)

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

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

1.2 分段聚合理論

(2)

2 云模型分段聚合及評(píng)價(jià)方法

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

2.1 云模型自適應(yīng)分段聚合

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

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

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

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

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

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

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

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

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

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

循環(huán)遍歷t0，通過計(jì)算使得Δ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í)間序列評(píng)價(jià)方法

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

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

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

(3)

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

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

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

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

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

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

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

(a) Ex1≠Ex2,En1=En2

(b) Ex1=Ex2,En1≠En2

(c) Ex1≠Ex2,En1≠En2

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

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

(1) 存在雙交點(diǎn)p1、p2，不妨設(shè)p1

代入云期望曲線：

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

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

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

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

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

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

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

綜合云[12]是兩個(gè)基礎(chǔ)云在更高層面的不確定性表示，它包含低層次概念的全部信息，由此可以利用基礎(chǔ)云的截?cái)囔赜?jì)算綜合云。把截?cái)囔刈鳛闄?quán)重，通過加權(quán)求和計(jì)算綜合云的期望和超熵，而綜合云的熵為兩個(gè)基礎(chǔ)云截?cái)囔刂汀ＴO(shè)基礎(chǔ)云Ci(Exi,Eni,Hei),i=1,2，yi(x)為云期望曲線，Li(x)代表論域上兩期望曲線最大值，反映交點(diǎn)對(duì)期望曲線的分段表示。

把基礎(chǔ)云的截?cái)囔刈鳛闄?quán)值，利用式(4)計(jì)算綜合云的數(shù)字特征，即綜合云Cz(Exz,Enz,Hez)。

(4)

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

圖2 基礎(chǔ)云與綜合云位置關(guān)系

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

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

綜合考慮基礎(chǔ)云對(duì)綜合云的貢獻(xiàn)程度，定義兩個(gè)基礎(chǔ)云的相似度為：

(5)

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

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

(6)

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

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

(7)

3 實(shí)驗(yàn)仿真

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

圖3 車流量變化

3.1 分段聚合效果分析

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

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

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

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

圖4 分段聚合效果-10維

圖5 分段聚合效果- 6維

3.2 云模型序列相似度分析

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

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

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

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

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

(a) Lane 1

(b) Lane 2

(c) Lane 3

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

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

表7 TDS算法計(jì)算相似度

4 結(jié) 語(yǔ)

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