基于融合云模型分析的時間序列概念劃分方法

李金武，王清珍

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

隨著社會經(jīng)濟和信息化技術(shù)的發(fā)展，如何從海量數(shù)據(jù)中挖掘出有價值的信息服務(wù)于國家發(fā)展，一直是研究的熱點[1-4]。時間序列應(yīng)用廣泛，是數(shù)據(jù)挖掘的重點研究對象，相較于傳統(tǒng)數(shù)據(jù)挖掘，基于時間序列的數(shù)據(jù)挖掘需要考慮時間維度上數(shù)據(jù)的變化趨勢，分析相鄰數(shù)據(jù)的關(guān)聯(lián)性。如何全面提取時間序列關(guān)鍵特征，獲取有價值的信息，進而對其進行有效評估，是基于時間序列的數(shù)據(jù)挖掘研究需要重點考慮的問題。

時間序列通常每隔一段時間采樣一次，導(dǎo)致數(shù)據(jù)具有隨機性和模糊性等特點，故對時間序列概念進行合理劃分是保證其有效評估的前提。概念劃分一般采用兩種方法[5-6]：一種是硬性劃分，通過計算數(shù)據(jù)極差，將概念論域硬性劃分為不重疊的區(qū)間，該方法提取到的規(guī)則不符合人們的思維過程，整個概念聚類過程沒有體現(xiàn)數(shù)據(jù)隨機性和模糊性特征，弱化了決策評估的實際意義；另一種是軟劃分，根據(jù)數(shù)據(jù)實際分布將概念論域劃分成有重疊的區(qū)間，把定量數(shù)據(jù)轉(zhuǎn)換成定性概念，保留數(shù)據(jù)隨機性和模糊性特征，顯然這種概念軟劃分方法對決策評估有重大實際意義。劉玉超[7]提出用云模型數(shù)字特征表示的概念含混度來度量概念共識度，利用高斯混合模型實現(xiàn)云變換算法，計算概念云數(shù)字特征，算法僅實現(xiàn)一維數(shù)據(jù)的概念提取。劉旋等[8]對文獻[7]提出的方法進行了改進，通過K均值聚類算法對概念粒度進行初始化，使用綜合云對概念粒度進行躍升，將確定度與歐氏距離相結(jié)合，對所屬概念粒度進行劃分。許凱等[9]打破啟發(fā)式云變換僅對一維數(shù)據(jù)進行處理的限制，在高斯混合模型基礎(chǔ)上，借助高斯分布擬合誤差求解云模型數(shù)字特征，實現(xiàn)了多維數(shù)據(jù)云變換及概念提取。鄧偉輝[10]提出了一種基于二維正態(tài)云的時間序列?；稻S方法，對時間序列進行二維處理，并利用云模型進行相似性度量。代勁等[11]從煤礦安全監(jiān)管需求出發(fā)，面向煤礦安全大數(shù)據(jù)，提出宏觀、微觀、時間和空間的概念表示方法，利用云模型實現(xiàn)定量與定性之間的不確定性轉(zhuǎn)換，滿足了安全監(jiān)管的變粒度需求。由于時間序列的不確定性及其自身線性特征，概念劃分需要包含隨機性和模糊性，并且應(yīng)體現(xiàn)時間序列線性變化趨勢，但上述文獻并沒有對時間序列概念進行有效劃分。為解決此問題，本研究從時間序列本身及其變化趨勢出發(fā)對時間序列進行多維處理，并利用高斯混合模型云變換算法將時間序列劃分為由多個云模型表征的定性概念，從而實現(xiàn)了時間序列從定量數(shù)據(jù)到定性概念的不確定性轉(zhuǎn)換。

1 時間序列多維處理

時間序列是按時間排序的一組變量數(shù)據(jù)，通常每隔一段時間采樣一次，本質(zhì)上反映了隨時間變化的趨勢，故對時間序列進行概念劃分時，應(yīng)對其進行多維處理，提取變化趨勢特征。在時間序列中，通常用兩個重要數(shù)據(jù)分布描述其特性，即原始序列頻率分布和差分序列頻率分布?；谝陨纤枷耄瑢⒁痪S特性原始時間序列轉(zhuǎn)換為二維序列，既保留了原始數(shù)據(jù)特征，又表征了時間序列隨時間變化趨勢。處理方法如下：

給定含有n個觀測值的時間序列T=(t1，t2，t3，…，tn)，計算其一階差分序列ΔT，即

(1)

得到n個二維數(shù)據(jù)，即處理后的時間序列，表示為(T，ΔT)=((t1，e1)，(t2，e2)，(t3，e3)，…，(tn，en))。

2 云模型理論

時間序列經(jīng)過二維處理以后，利用云模型進行概念軟劃分，最大限度提取時間序列特征值。云模型是在概率論和模糊數(shù)學(xué)的基礎(chǔ)上，對隨機性和模糊性及其關(guān)聯(lián)性進行深入研究后提出的理論模型[12-13]，定義如下：設(shè)U是一個論域空間，C是U上一個定性概念，用數(shù)字特征Ex、En、He表示。對于任意x∈U，且x是定性概念C上的一次隨機實現(xiàn)，則x對于C的確定度y=u(x)是一個具有穩(wěn)定傾向的隨機數(shù)。把(x，y)在U上的分布稱為云，x稱為云滴。

上述定義中論域空間維度可以是任意的，對應(yīng)一維云模型C(Ex，En，He)，二維云模型C(Ex，Ey，Enx，Eny，Hex，Hey)和多維云模型C(Ex，Ey，…，Enx，Eny，…，Hex，Hey，…)。當(dāng)論域空間為一維時，Ex是云模型的數(shù)學(xué)期望，代表論域空間云滴正中心，En是云模型的熵，反映論域空間云滴離散程度，He是云模型的超熵，表示熵的不確定度，反映云滴厚度。曲線y表示一維正態(tài)云模型期望曲線：

(2)

當(dāng)論域空間為二維時，期望(Ex，Ey)表示二維正態(tài)云模型在平面XOY投影的形心，是最能夠代表定性概念的點，熵(Enx，Eny)表示二維正態(tài)云模型在OX軸和OY軸方向上“亦此亦彼”的裕度，超熵(Hex，Hey)表示二維正態(tài)云模型在平面XOZ和平面YOZ投影的離散程度。曲線z1和z2表示二維正態(tài)云模型在平面XOZ和平面YOZ投影所形成的一維正態(tài)云模型期望曲線：

(3)

3 云模型概念劃分

時間序列多維處理后，服從二維正態(tài)分布。利用二維高斯混合模型劃分多個高斯分布并對其進行云變換，提取時間序列云模型定性概念。

3.1 高斯混合模型算法

以二維數(shù)據(jù)為例，假設(shè)樣本數(shù)據(jù)X=(x1，x2，…，xn)T，xi=(xi1，xi2)，1≤i≤n，為二維數(shù)據(jù)，且服從二維高斯分布，其概率密度函數(shù)

(4)

式中：μ是一個二維均值向量，由二維高斯分布樣本期望描述；∑是一個2×2協(xié)方差陣，由高斯分布樣本方差描述，|∑|是∑的行列式。

高斯混合模型由多個高斯分布線性疊加而成，假設(shè)有K個高斯分布，則高斯混合模型由這K個高斯分布按照不同概率混合，其數(shù)學(xué)表示形式如下：

(5)

對于參數(shù)Θ的估計采用最大期望值(EM)算法[14-15]。為減少迭代次數(shù)與計算量，首先使用K均值聚類算法[16-17]對高斯混合模型初始化，再運用EM算法進行參數(shù)計算。

算法1高斯混合模型算法。

輸入：n個樣本數(shù)據(jù)X=(x1，x2，…，xn)T，xi=(xi1，xi2)，1≤i≤n。

輸出：K個高斯分量。

步驟1使用K均值聚類算法對高斯分布參數(shù)進行初始化，K值利用手肘法[16]確定：

步驟2E-step，用初始化參數(shù)計算后驗概率：

步驟3M-step，用后驗概率計算新參數(shù)Θ(m+1)：

步驟4重復(fù)步驟2和步驟3，直到算法收斂。

3.2 云變換算法

云變換是依據(jù)數(shù)據(jù)頻率分布特征進行?；瑒澐侄ㄐ愿拍畹囊环N過程[18]。將數(shù)據(jù)頻率分布曲線分解成若干個正態(tài)云模型的疊加，實現(xiàn)定性概念軟劃分，每個定性概念統(tǒng)一用云模型數(shù)字特征表示。數(shù)學(xué)表示形式如下：

(6)

式中：f(x)為頻率分布函數(shù)；ai為云模型幅度系數(shù)；n為云模型個數(shù)。

本研究使用基于高斯混合模型的云變換，利用高斯混合模型對時間序列進行建模。將時間序列分解成若干個高斯分布疊加，利用高斯分布擬合誤差求解云模型數(shù)字特征，再將高斯分布函數(shù)轉(zhuǎn)換成云模型，實現(xiàn)時間序列概念劃分。此方法不僅可以實現(xiàn)一維數(shù)據(jù)概念劃分，還可實現(xiàn)多維數(shù)據(jù)概念劃分。

算法2云變換算法。

輸出：定性云模型參數(shù)C(Exk，Eyk，Enxk，Enyk，Hexk，Heyk)，1≤k≤K。

步驟1令Exk=μkx，Eyk=μky，Enxk=σkx，Enyk=σky。

步驟2計算X和Y的邊緣概率密度函數(shù)：

步驟3計算：

步驟4計算：

步驟5計算：

步驟6計算：

4 實例驗證

為有效分析時間序列概念劃分效果，本研究采用真實數(shù)據(jù)集進行實驗仿真。仿真分析選用MATLAB軟件，數(shù)據(jù)集為某交通卡口一天實際交通流量，共包含288條數(shù)據(jù)，記錄交通卡口4條車道車流量狀態(tài)，從0∶00到23∶55每隔5 min記錄一次。

4.1 數(shù)據(jù)二維處理

對于時間序列，利用原始數(shù)據(jù)提取趨勢變化數(shù)據(jù)，將單一屬性數(shù)據(jù)變?yōu)殡p屬性數(shù)據(jù)。其中，車流量原始數(shù)據(jù)如圖1所示。利用公式(1)對時間序列進行二維差分處理，一階差分數(shù)據(jù)如圖2所示。

圖1 車流量原始數(shù)據(jù)Fig.1 Original data of the traffic flow

圖2 車流量一階差分數(shù)據(jù)Fig.2 First-order difference data of the traffic flow

車流量原始數(shù)據(jù)頻率分布見圖3。當(dāng)車流量低于100輛/5 min或高于400輛/5 min時，數(shù)據(jù)分布相對比較密集，符合車流量凌晨和日間高峰時段運行狀態(tài)。車流量一階差分數(shù)據(jù)頻率分布見圖4，車流量一階差值為-25～+25時，數(shù)據(jù)分布相對比較密集，說明大部分時間段車流量變化趨勢比較穩(wěn)定。整體數(shù)據(jù)頻率分布符合車流量實際情況。

圖3 車流量原始數(shù)據(jù)頻率分布Fig.3 Frequency distribution of original data of the traffic flow

圖4 車流量一階差分數(shù)據(jù)頻率分布Fig.4 Frequency distribution of first-order difference data of the traffic flow

為了直觀展示處理后的二維數(shù)據(jù)，選用三維空間散點圖。在散點圖(圖5)中，一個點代表一個時間序列觀測值。散點圖在平面坐標(biāo)的投影如圖6所示。

圖5 三維空間散點圖Fig.5 Three-dimensional scatter plot

圖6 散點圖投影Fig.6 Projection of three-dimensional scatter plot

4.2 概念提取

綜合考慮車流量狀態(tài)和變化趨勢二維屬性，對交通卡口車流量變化進行概念提取。首先，利用算法1對高斯混合模型進行分解，得到5個高斯分布線性疊加，其中高斯分量個數(shù)利用K均值聚類手肘法確定。5個高斯分量參數(shù)值如表1所示。

表1 高斯分量參數(shù)值Tab.1 Parameter value of Gaussian component

然后，利用算法2對表1中5個高斯分量進行云變換，得到5個概念云，其云模型數(shù)字特征見表2。由云數(shù)字特征刻畫概念云標(biāo)尺及其投影，如圖7與圖8所示。

表2 云模型數(shù)字特征Tab.2 Digital features of cloud model

圖7 概念云標(biāo)尺示意圖Fig.7 Diagram of concept cloud scale

圖8 概念云標(biāo)尺投影Fig.8 Projection of concept cloud scale

概念云標(biāo)尺表征的5個概念反映了車流量大小和車流量增速不同狀態(tài)。概念云C2表征的概念說明車流量較小且變化趨勢較穩(wěn)定，概念云C1表征的概念說明車流量較大且變化趨勢明顯。僅從車流量變化趨勢分析，概念云C2趨勢穩(wěn)定，概念云C1和C3趨勢有一定波動，有效反映了凌晨時間段和日間高峰時間段車流量實際狀況。

表3 本方法與A-GCT比較結(jié)果Tab.3 Comparison results between this method and A-GCT

4.3 對比分析

本方法與文獻[7]中自適應(yīng)高斯云變換(A-GCT)相比，采用K均值聚類手肘法確定高斯分量個數(shù)，克服了A-GCT方法初始粒度選取的盲目性，減少了迭代次數(shù)，使得EM算法收斂速度更快，效率明顯提高。并且，本方法不僅適用于一維數(shù)據(jù)，而且適用于多維數(shù)據(jù)，在數(shù)據(jù)普適性、概念誤分率和時間復(fù)雜度上均有明顯改善。具體比較結(jié)果見表3。

5 結(jié)語

本研究提出的概念劃分方法，基于高斯混合模型實現(xiàn)云變換，可以有效對時間序列進行概念劃分，體現(xiàn)了數(shù)據(jù)的隨機性和模糊性，實現(xiàn)了時間序列定量數(shù)值到定性概念的不確定性轉(zhuǎn)換。實驗結(jié)果表明，本方法在原始數(shù)據(jù)屬性上增加了序列變化趨勢屬性，利用二維云變換算法進行概念提取，較僅考慮原始數(shù)據(jù)單一屬性提取的概念更符合實際。