基于動態(tài)編程匹配的聚類序列數(shù)據(jù)挖掘算法

曾 錚

(信陽職業(yè)技術(shù)學院 河南 信陽 464000)(中國農(nóng)業(yè)大學 北京 100083)

0 引 言

隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)挖掘技術(shù)已經(jīng)在金融、工業(yè)和運輸?shù)雀鱾€領(lǐng)域得到了廣泛的應(yīng)用與發(fā)展[1-2]。時空數(shù)據(jù)表示同時具備時間空間屬性的數(shù)據(jù)，步入“互聯(lián)網(wǎng)+”時代后，從巨大體量的時空數(shù)據(jù)中提取隱藏的巨大價值信息對于進一步充分挖掘數(shù)據(jù)潛力具有重大意義[3-4]。

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

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

1 聚類序列挖掘

1.1 相關(guān)定義

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

針對事件序列數(shù)據(jù)挖掘必須滿足以下要求：

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

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

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

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

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

(2)

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

ψ(θ):tAB～ψ(θ)

(3)

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

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

(4)

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

1.2 一對一匹配

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

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

圖1 發(fā)生時間間隔的示意圖

1.3 動態(tài)編程匹配的多重對應(yīng)

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

步驟1初始化計數(shù)器k=1并設(shè)置TAB=?。

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

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

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

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

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

1.4 時間間隔推斷概率密度函數(shù)

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

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

(6)

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

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

(7)

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

αpost=αprior+n

(8)

1.5 評估函數(shù)與計算步驟

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

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

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

CSDM算法的運行步驟如下：

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

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

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

2 合成數(shù)據(jù)驗證

合成數(shù)據(jù)是根據(jù)以下過程生成的：

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

圖3 合成數(shù)據(jù)分布

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

圖4 合成數(shù)據(jù)的示意圖

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

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

式中：Ctrue∈{Atrue,Btrue}是真實的聚類；而CCSM/CCM∈{ACSM/CCM,BCSM/CCM}是使用CSDM或CCM提取的聚類。當λtrue=0.05時，聚類結(jié)果如圖5所示。數(shù)值越接近1，性能越好。由于此實驗中只有一個真實模式，因此僅對CSDM衍生的具有最高L值的模式執(zhí)行此評估。應(yīng)用CSDM參數(shù)τ=100.0和σ=1.0，并將單鏈接方法用于層次聚類。由于合成數(shù)據(jù)是使用隨機變量從正態(tài)分布和指數(shù)分布生成的，因此該圖顯示了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成功地在噪聲的情況下穩(wěn)定地提取了聚類。另外，在真實數(shù)據(jù)的情況下，即不知道真實的聚類和對，CCM無法區(qū)分先驗聚類和后驗聚類。

(a) 聚類準確率

(b) 聚類召回率

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

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

(a) CSM方法提取結(jié)果

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

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

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

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

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

表3 更改時間間隔參數(shù)λtrue時，F(xiàn)1度量的平均值和標準差以及時間間隔分布的估計參數(shù)

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

(a) 參數(shù)τ的影響

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

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

3 應(yīng)用實例與分析

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

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

溫度以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的猝發(fā)提取方法從連續(xù)測量的AE信號中提取AE事件，并獲得1 429個AE事件。使用猝發(fā)提取方法，可以在不設(shè)置時間窗或幅度閾值的情況下提取任何長度的AE事件。接下來，通過應(yīng)用傅里葉變換將每個獲得的AE事件轉(zhuǎn)換為頻域，從而產(chǎn)生大約5 000個離散的功率譜點。

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

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

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

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

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

(a) 損傷模式1

(b) 損傷模式2

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

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

(a) CSM提取結(jié)果

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

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

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

4 結(jié) 語

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