基于動態編程匹配的聚類序列數據挖掘算法

曾 錚

(信陽職業技術學院 河南 信陽 464000)(中國農業大學 北京 100083)

0 引 言

隨著大數據時代的來臨，數據挖掘技術已經在金融、工業和運輸等各個領域得到了廣泛的應用與發展[1-2]。時空數據表示同時具備時間空間屬性的數據，步入“互聯網+”時代后，從巨大體量的時空數據中提取隱藏的巨大價值信息對于進一步充分挖掘數據潛力具有重大意義[3-4]。

時空數據挖掘方法主要包括時空頻繁模式、時空共現模式和時空關聯模式等，每種模式都有其各自的優缺點[5-7]。針對有兩種或者多種同類型數據出現在間隔較短的時間或空間中的數據，比如天氣數據、交通數據以及醫療數據等，時空共現模式由于其較強的時空關聯性成為了該類數據挖掘研究的熱點，但是絕大多數的研究無法直接從時、空兩者出發進行數據挖掘[8]。針對該問題，李小紅等[9]提出了一種共現聚類挖掘(Co-occurring cluster mining,CCM)算法，該算法包含兩個評估函數，一個表示單個聚類在特征空間中的空間接近性，另一個表示聚類對之間的時間接近性。然而，由于模型簡單性以及固定的標準，從而將序列分解成區間，忽略了共現事件的發生順序和時間間隔。另外，該算法沒有考慮多個事件發生內在聯系，即未能充分挖掘事件相關性，從而限制了推理精度。

針對上述問題，提出了一種基于動態編程匹配(Dynamic programming matching,DPM)的聚類序列數據挖掘算法(Clustering sequence data mining algorithm,CSDM)。通過合成數據及燃料電池損傷分析實驗證明了該方法在不確定情況下良好的推理精度。

1 聚類序列挖掘

1.1 相關定義

事件序列數據：將具有v維特征的N個數據點xk=(xk,1,xk,2,…,xk,v)∈D,k=1,2，…,N作為事件序列數據，其中數據點順序為x1x2…xN，它們出現的時間表示為t(xk)，則相應的定義式為：

針對事件序列數據挖掘必須滿足以下要求：

(1) 時間接近性要求：給定兩個簇A,B?D(A∩B=?)，在事件x(A)∈A發生后，事件x(B)∈B幾乎同時發生。即當存在實數Θ滿足0

(2) 頻率要求：如果x(A)∈A及其對應的事件對x(B)∈B出現的頻率越高，則說明簇之間的相關關系就越強。因此，為了提供最小支持Suppmin，要求滿足#{tAB}≥Suppmin，其中#{·}表示集合中元素數。

(3) 空間接近性要求：簇A(或簇B)中的事件在特征空間內緊密相鄰。例如要求數據分布的簇內平方和(SSW)較小。其中，簇A和簇B可以獨立評估。

(4) 聚類序列模式：假設事件x(A)和x(B)之間的所有對應的發生時間間隔的集合為：

TAB={tAB|x(A)∈A,x(B)∈B}

(2)

假定發生時間間隔概率密度函數(PDF)為：

ψ(θ):tAB～ψ(θ)

(3)

式中：θ為參數。事件發生時間間隔PDF滿足上述三個要求的簇對A和B的集合可定義為:

PA→B=〈A,B,ψ(θ)〉

(4)

PA→B稱為聚類序列模式，其中A可以稱為先驗聚類，B可以稱為后驗聚類。

1.2 一對一匹配

CSDM算法包括生成和評估候選聚類序列模式的過程。有必要針對候選模式簇對A和B計算發生時間間隔集TAB。考慮兩種事件的計算類型，分別為簡單的一對一匹配和通過彈性匹配的多重匹配。

在此，以圖1所示的事件序列為例，說明計算發生時間間隔的方法。事件x2、x8和x9屬于簇A，x3、x5、x10和x11屬于簇B，其余事件不屬于任何簇。這是通過在特征空間中聚類來預先確定的。當事件以圖1所示的順序發生時，計算與任何A事件和B事件相對應的時間間隔。

圖1 發生時間間隔的示意圖

1.3 動態編程匹配的多重對應

一對一匹配的計算算法如下，該過程在k=N的點完成[10]。

步驟1初始化計數器k=1并設置TAB=?。

步驟4將時間間隔tAB=t(xpost)-t(xpre)添加到TAB。以k←k+1返回步驟2。

進一步考慮事件之間存在多重對應關系，為此設置了如下條件：(1) 一個事件可以配對多次；(2) 每個事件至少應配對一次；(3) 時間間隔的總和應最小化[11]。

其中，條件(1)和(2)用于盡可能多地增加生成的事件對的數量，以確保模式的可靠性。同時，在條件(3)中應將所有時間間隔的總時間最小化，因為根據本文中使用的時間接近的定義，較短的時間間隔表示它們之間的關系更強。

圖2 計算時間間隔的多重匹配示意圖

將上述條件公式化為多重匹配問題，如式(5)所示。

1.4 時間間隔推斷概率密度函數

通常，事件發生的時間是隨機的，具有極強的不確定性。假設時間間隔是根據以下指數分布發生的：

ψ(tAB;λ)=λe-λtAB

(6)

式中：λ>0是縮放參數；π(λ)表示參數λ的先驗分布；ψ(tAB|λ)表示tAB的似然函數；并且π(λ|tAB)表示觀察tAB時與λ相關的后驗分布。根據貝葉斯定理得出：

π(λ|tAB)∝ψ(tAB|λ)×π(λ)

(7)

似然函數采用指數分布，因此先驗分布獲得伽馬分布Γ(λ;α,β)，其中α和β分別是形狀和比例參數。先驗分布參數αprior和βprior在沒有特定目標的情況下，經常使用Γ(1,1)。后驗分布參數可根據貝葉斯更新規則計算如下[12]：

αpost=αprior+n

(8)

1.5 評估函數與計算步驟

定義候選聚類序列模式PA→B的評估函數為：

相反，函數G(A,B)是根據空間接近性要求評估函數。同樣，G(A,B)值越大，空間接近度越高。SSW表示相對于簇中心的簇內數據點的分布。在此，使用σ>0的高斯函數作為用于調整候選模式之間的G值的相對分辨率的超參數，將值的范圍歸一化為[0,1]。用CCM的評估函數替換了F，而G與CCM中的相同[13]。

此外，L的評估函數定義為函數F和G的乘積；其中γ=0.5。提取模式時滿足頻率要求，其中相應的時間間隔數{tAB}大于或等于預先指定的最小支持Suppmin。

CSDM算法的運行步驟如下：

步驟1生成候選模式。首先，在數據空間中使用分層聚類生成候選聚類，而不使用時間信息。在排除包含關系之后，將所有可能的簇對都設置為候選模式集。

步驟2評估候選模式。根據函數L計算每個候選模式的評估值。當候選模式大于或等于預定義的最小閾值Lmin和Suppmin時，該模式將添加到輸出模式集P。

步驟3排除重疊模式。最后，去除輸出模式集P中的重疊模式，并使用其余的模式集，P(l)∩P(m)指Al∩Am和Bl∩Bm，P(l)∩P(m)≠?表示兩個模式都是具有包含關系的先驗聚類或后驗聚類時的情況。在這種情況下，采用具有較高L值的模式，而排除具有較低L值的模式。

2 合成數據驗證

合成數據是根據以下過程生成的：

(1) 從分別以m1=(5,5)和m2=(9,5)為中心的兩個不同的二維正態分布生成N個數據點，方差為1，協方差為0；每個數據點都表示為x～N(m,Σ)，如圖3所示。

圖3 合成數據分布

(2) 從最接近各自正態分布中心的數據點創建了T個數據點對；每對包括先驗聚類Atrue和后驗聚類Btrue。其余數據點是代表噪聲的錯誤數據，如圖3所示。

圖4 合成數據的示意圖

在此實驗中，總共生成了N=1 000個數據點，每個正態分布中有500個點。真實數據點的對數T是用于確定真實簇的大小和數據空間中周圍噪聲的比率的參數，而λtrue是用于確定時間接近的強度的參數，通過改變這些參數來評估CSDM。

當真實對數T發生變化時，對于簇C∈{A,B}，根據式(13)-式(15)評估提取的模式PA→B的精度、召回率和F1度量三個參數來評估兩種方法的聚類性能。

式中：Ctrue∈{Atrue,Btrue}是真實的聚類；而CCSM/CCM∈{ACSM/CCM,BCSM/CCM}是使用CSDM或CCM提取的聚類。當λtrue=0.05時，聚類結果如圖5所示。數值越接近1，性能越好。由于此實驗中只有一個真實模式，因此僅對CSDM衍生的具有最高L值的模式執行此評估。應用CSDM參數τ=100.0和σ=1.0，并將單鏈接方法用于層次聚類。由于合成數據是使用隨機變量從正態分布和指數分布生成的，因此該圖顯示了30個實驗的平均值。

P(A,B)),F1-measure(P(B,A))}，則采用更好的F1度量。

圖5(a)顯示，對于先驗聚類A，CSDM成功地以0.8或更高的準確率提取了聚類。圖5(b)顯示對于后驗聚類B，無論噪聲水平如何，CSDM的召回率均達到0.95或更高。當噪聲較少時，即當存在更多真實對時，CSDM和CCM的F1度量之間沒有主要差異。但是，圖5(c)顯示了CSDM成功地在噪聲的情況下穩定地提取了聚類。另外，在真實數據的情況下，即不知道真實的聚類和對，CCM無法區分先驗聚類和后驗聚類。

(a) 聚類準確率

(b) 聚類召回率

(c) 聚類F1-度量圖5 聚類結果

由CSDM和CCM提取的聚類的示例如圖6所示。CSDM能夠提取更接近真實聚類的聚類，而CCM提取的聚類包含比在真實聚類中可以觀察到的更多的噪聲數據。

(a) CSM方法提取結果

(b) CCM方法提取結果圖6 從合成數據中提取的聚類

根據發生時間間隔估算指數分布的準確性是基于真實值的絕對誤差：

表1 時間間隔分布的平均估計參數和誤差Eλ以及標準偏差

此外，還比較了當改變合成數據的間隙參數gp時，CSDM在應用一對一匹配和DPM時的性能。平均值和標準偏差示于表2。一對一匹配對于較小的間隙(gp=1.0)更可能具有不正確的匹配順序，從而導致較高的誤差值，而DPM顯示出較低的誤差且不受間隙長度的影響。

表2 更改間隙參數gp時，CSDM中的一對一匹配和DPM的比較

表3 更改時間間隔參數λtrue時，F1度量的平均值和標準差以及時間間隔分布的估計參數

接下來，改變函數F和G的參數，并計算出聚類提取和指數分布參數的精度，如圖7所示。在這種情況下，只有一個真實的模式具有相對較大的簇。因此，只要將預先指定的Lmin和Suppmin設置為合理的較低值，同一模式將始終具有最佳評估值。在實驗中，這些值設置為Lmin=0.5和Suppmin=20。從圖7可以看出，就簇F度量而言，τ和σ都有一個穩定的區域，一旦超過某個值，這兩個參數的值就會突然變差。這說明聚類提取對τ和σ的變化不是很敏感。因此，可以將這些參數設置為穩定區域中的任何值。

(a) 參數τ的影響

(b) 參數σ的影響圖7 超參數的影響(T=400，λtrue=0.05)

相反，時間間隔分布的誤差Eλ對時間接近度F中的參數τ敏感，因此可以通過調整τ來顯著改善。然而，實際上，應基于候選模式集中評估值的分布，從值的相對分辨率的角度進行調整，因為在使用實際數據集時不可能調整誤差，因此真實值未知。另一方面，對于空間接近度函數G，參數τ在可接受的簇提取精度(F度量)的穩定范圍內實際上是恒定的，并且對Eλ幾乎沒有影響。

3 應用實例與分析

由于燃料電池通過化學反應直接發電，因此已經開發了將其用作高效、低污染的下一代能量轉換器的實際應用。在這些應用中，固態氧化物燃料電池(SOFCs)被認為是有效的大規模實現高效發電的手段。但是，由于SOFCs完全由固態陶瓷材料組成，因熱和氧化還原膨脹而產生應力，這會導致電極或電解質中的裂紋和分層，并導致物理性能下降。為了描述這個問題，使用聲頻發射(AE)事件序列生成的內核自組織映射(SOM)對損傷過程進行可視化處理。另外，應用了CCM成功提取了材料之間的損傷共現關系。

SOFC中用于評估損傷的設備是在單電池中使用的標準材料組合物，其三氧化二鈰基氧化物作為電解質，電極的橫截面中央為三層結構，電解質夾在電極之間。單電池上方和下方是帶有同心Al2O3管的氣體環境(內徑為8毫米，外徑為13毫米)。在Al2O3管道之間放置一個屏蔽層，因此也使用熔化溫度為800 ℃的蘇打氣環。

溫度以200 ℃/h的速度升高到800 ℃，并在玻璃封口融化后保持1 h。然后以100 ℃/h的速度降低到550 ℃并在添加H2和O2氣體的同時保持1.5 h。然后，溫度以100 ℃/h的速率一次升高10 ℃，直到800 ℃，并保持1.5 h。然后以100 ℃/h的速度將溫度降至20 ℃，并保持60 h。在此項實驗中，損傷是由于突然降低溫度而故意造成的。

使用寬帶壓電換能器(PAC UT-1000)以1 MHz的采樣頻率進行AE測量。換能器與電爐外部的Al2O3管道接觸。來自換能器的電信號用40 dB的前置放大器放大，再用40 dB的主放大器放大。

首先，采用Kleinberg的猝發提取方法從連續測量的AE信號中提取AE事件，并獲得1 429個AE事件。使用猝發提取方法，可以在不設置時間窗或幅度閾值的情況下提取任何長度的AE事件。接下來，通過應用傅里葉變換將每個獲得的AE事件轉換為頻域，從而產生大約5 000個離散的功率譜點。

帶有基于Kullback-Leibler散度的內核函數的內核自組織映射(Self organizing maps,SOM)將每個AE事件的離散功率譜用作輸入數據x，以可視化二維平面上AE事件之間的相似性。SOM是一種無監督算法，主要用于聚類和可視化。根據先前的研究[18]，可以通過直觀地解釋內核SOM結果來發現AE事件與損傷類型(例如電解質裂紋和電極分層)之間的大致對應關系。在這項研究中，CSDM被應用于內核SOM產生的可視化空間來解釋事件。

由于內核SOM無法顯式定義每個神經元節點的參考向量，因此它無法直接定義時間鄰近函數G的集群內分散SSW。因此，根據以下公式代替式(12)重新定義G：

內核SOM中的神經元拓撲是2D方格，有15×15個神經元。如前所述，使用了基于完全鏈接方法的層次聚類。CSDM評估函數的兩個超參數如第2節所述，τ=2.0和σ=0.5。此外，最小評價函數值Lmin被設定為0.7，最小支持閾值Suppmin=10。這些閾值影響提取的模式的總數和每個模式的置信度。結果從總共29個模式中獲得了聚類序列模式。

考慮到物理現象以及與CCM提取結果的相似性，對CSDM提取的聚類序列模式進行了合理性評估。圖8顯示了CSDM提取的損傷模式的示例。在2D平面上以一種方式配置了內核SOM來說明各種模式，以便盡可能保留AE事件之間的相似性。每個單元格對應一個SOM神經元節點，相同顏色的相鄰單元格表示由CSDM提取的單個聚類。圖中箭頭的方向指示先驗和后驗聚類的方向。此外，圖8中(A)至(E)顯示了先前描述的估計損害類型。圖9顯示了由CSDM估計的時間間隔的指數分布以及對于每種損傷模式的觀察值。根據實際觀察值，可以確認該趨勢遵循在特定值處沒有峰值的指數分布。

圖8 CSDM提取的損傷模式的示例

(a) 損傷模式1

(b) 損傷模式2

(c) 損傷模式3圖9 每種損傷模式的時間間隔

另外，圖10描繪了其中將所有29個提取的模式分析為損傷類型之間的關系圖，其中箭頭邊緣的寬度與模式出現的次數成正比。CSDM的提取結果如圖10(a)所示，顯示出與圖10(b)所示的CCM相似的趨勢。(B)和(C)以及(B)和(D)之間的順序可以確定；相反，可以提取諸如(B)和(E)之間以及(E)和(F)之間的雙向關系。

(a) CSM提取結果

(b) CCM提取結果圖10 比較CSDM和CCM提取的模式

在圖8所示的損傷模式1中，由于材料中的初始缺陷和不均勻而產生的裂紋(B)的發展導致產生電解質裂紋(D)的損傷模式。特別是，在圖的上部中心區域中發生的AE事件表示損傷，尤其是在后期，由于材料的初始缺陷和不均勻性，裂紋頻繁出現。可以認為當這些裂紋發展到一定程度時，在電解質中開始形成裂紋。

另外，損傷模式3是由玻璃密封損傷(E)和電極材料分層(F)引起的雙向損傷模式。玻璃密封和電極材料在結構上沒有連接，但是可以推測：當玻璃密封由于溫度下降和電解質收縮而凝固時，在電解質和電極材料之間產生剪切應力，導致觀察到的分層。相比之下，雖然玻璃中發生的塑性變形很小，但達到了突然出現裂紋的極限。綜上，圖10(a)表明了初始缺陷和玻璃密封材料具有顯著影響。因此，通過解決這些問題，可以提高損傷分析的可靠性，并且分析得到的結論是符合先驗知識的，進一步驗證了方法的有效性。

4 結 語

針對共現聚類挖掘算法存在的局限性，本文提出了一種基于動態編程匹配的聚類序列數據挖掘算法。通過使用合成數據進行的實驗，以及燃料電池損傷分析，可以得到如下結論：聚類序列挖掘算法即使在噪聲不確定性相對較高的情況下，也可用于穩定地提取聚類序列模式。此外，動態編程匹配的引入可以有效地提高發生時間間隔概率密度函數估計的準確性以及推理精度。CSDM成功地確定了損傷模式的方向性，進一步證明了該算法能夠應用于損傷模式判別。