改進的FP-growth算法及其在TE過程故障診斷中的應用

李宏光， 夏麗君

(北京化工大學信息科學與技術(shù)學院， 北京　100029)

?

改進的FP-growth算法及其在TE過程故障診斷中的應用

李宏光， 夏麗君

(北京化工大學信息科學與技術(shù)學院， 北京100029)

為了解決頻繁模式增長(frequent pattern growth，F(xiàn)P-growth)算法因多次遍歷頻繁集列表而產(chǎn)生龐大頻繁模式樹需占用大量內(nèi)存降低了運行效率的問題，提出一種改進的FP-growth(upgraded FP-growth，UFP)算法. 首先，構(gòu)造支持度函數(shù)實現(xiàn)各項與其支持度的映射，使算法的運行效率得到提高；其次，利用關(guān)鍵字篩選技術(shù)，把頻繁項分成關(guān)鍵項表、非關(guān)鍵項表兩部分，保證了最終獲取的每條關(guān)聯(lián)規(guī)則都是人們關(guān)注的有效信息；最后，根據(jù)頻繁1-項集劃分數(shù)據(jù)庫子集并直接構(gòu)造每一項的條件模式樹，節(jié)省了內(nèi)存空間. 將UFP算法應用于Tenessee Eastman(TE)過程的故障診斷，通過與主成分分析(principal component analysis,PCA)、核主成分分析(kernel principal component analysis，KPCA)算法在多種故障下的診斷結(jié)果對比實驗驗證了算法的優(yōu)越性.

頻繁模式增長(FP-growth)算法； 關(guān)聯(lián)規(guī)則； Tenessee Eastman (TE)過程； 故障診斷

數(shù)據(jù)挖掘(data mining)的目的是從海量、不完整、有噪聲、模糊、隨機的大型數(shù)據(jù)中挖掘那些隱含的、有用的、令人感興趣的和前所未知的模式或知識. 而關(guān)聯(lián)規(guī)則挖掘(association rules mining)則是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)中的一個重要研究課題，主要是為了發(fā)現(xiàn)大量數(shù)據(jù)中各個項集之間的相關(guān)聯(lián)系，以揭示事物間隱含的本質(zhì)關(guān)系.

Agrawal等在1993年首次提出關(guān)聯(lián)規(guī)則挖掘這一概念[1]，其核心思想是基于頻繁項集理論的遞推算法，用于探索超市交易數(shù)據(jù)庫中商品間的關(guān)聯(lián)信息，并于1996年提出了并行挖掘算法[2]，引起了諸多學者的注意. 各個領(lǐng)域的研究人員從多個方面對此經(jīng)典算法進行了改進，關(guān)聯(lián)規(guī)則挖掘進入了蓬勃發(fā)展的時期. Han 等[3]深入研究可擴展聯(lián)機分析處理(on-line analytical processing，OLAP)，在信息網(wǎng)絡的挖掘方面創(chuàng)造了里程碑式的成就. Tohidi等[4]提出了一種基于因式分解的頻繁模式挖掘(frequent patlern processing based on factorization，F(xiàn)PPF)，避免了頻繁模式樹的生成. Silva等[5]針對星型模式，首先建立每個維度的FP-tree，然后進行結(jié)合形成一棵超級FP-tree，再用FP-growth算法進行挖掘. Wang等[6]采用B-事務聚類的方法，很大程度上降低了FP-tree的規(guī)模，提高了算法的時空效率. Chen等[7]利用數(shù)據(jù)庫解析和FP-tree劃分的并行算法思想，實現(xiàn)了高效的任務分配和很好的負載穩(wěn)定性. Wang等[8]通過考慮項集的不同權(quán)重，采用AHP方法挖掘報警記錄，結(jié)合主從網(wǎng)站的分布式結(jié)構(gòu)有效地降低了算法復雜度. Totad等[9]提出批量增量挖掘算法(batch incremental technology FP-growth，BIT-FPgrowth)，通過重組2個連續(xù)的階段FP-tree來獲取算法的新樹. Wang等[10]采用網(wǎng)格劃分方法決定每個事務項的隸屬函數(shù)數(shù)值，并提出一種模糊FP-growth算法來處理數(shù)據(jù)挖掘過程. Sun等[11]結(jié)合FP-growth算法和映射規(guī)約(map reduce)計算模型，提高了處理大數(shù)據(jù)的能力. 這些專家學者在關(guān)聯(lián)模式挖掘領(lǐng)域從不同的角度進行了開拓創(chuàng)新，然而FP-growth算法需多次遍歷頻繁項列表產(chǎn)生龐大頻繁模式樹的不足仍需要進一步改善，從而提高算法的時空效率. 此外，F(xiàn)P-growth在工業(yè)故障診斷領(lǐng)域的應用研究相對較少，如何改進算法，使其能夠僅產(chǎn)生有價值的故障診斷信息，摒棄無用的頻繁模式也是有待研究的課題.

針對上述不足，本文提出了一種改進的FP-growth(upgraded FP-growsth，UFP)算法. 首先，此算法利用函數(shù)使每一項的關(guān)鍵字與其支持度計數(shù)實現(xiàn)映射，避免了需要多次遍歷頻繁項列表F-list的缺點，時間效率大大提高；其次，借鑒關(guān)鍵字篩選[12]的思路，把頻繁項分成兩部分：關(guān)鍵項表、非關(guān)鍵項表，將人們關(guān)注的項存儲于關(guān)鍵項表，其他項存儲于非關(guān)鍵項表，保證了最終獲取的每條關(guān)聯(lián)規(guī)則都是人們需要的有效信息；最后，UFP采取基于頻繁1-項集進行劃分的思想，根據(jù)關(guān)鍵項表中頻繁1-項集劃分數(shù)據(jù)庫子集，直接構(gòu)造每一項的條件樹，極大節(jié)省了內(nèi)存空間. 為證明UFP算法的優(yōu)越性，本文將其應用于TE過程故障的數(shù)據(jù)挖掘，仿真實驗驗證了UFP算法運行效率較PCA算法有較大提高，并且最終獲得的每一條關(guān)聯(lián)規(guī)則均以狀態(tài)信息為前項，故障信息為后項，有效避免了信息冗余.

1　FP-growth算法

當今工業(yè)過程中產(chǎn)生的大量數(shù)據(jù)中隱藏著豐富而珍貴的監(jiān)控信息，為了獲得并利用這些信息輔助生產(chǎn)，數(shù)據(jù)挖掘技術(shù)應運而生. 關(guān)聯(lián)規(guī)則挖掘在20世紀90年代被提出之后迅速成為數(shù)據(jù)庫研究的一個熱點，而FP-growth算法作為挖掘頻繁項集的經(jīng)典算法之一受到了相關(guān)學者的廣泛關(guān)注.

所謂關(guān)聯(lián)規(guī)則即形如Ix→Iy的蘊涵式，其中，關(guān)聯(lián)規(guī)則前項Ix和關(guān)聯(lián)規(guī)則后項Iy都是項集I中的項.

支持度(support)是獲取的規(guī)則有用性的確定性度量：

support (Ix→Iy)=P(Ix∪Iy)

(1)

置信度(confidence)代表挖掘的關(guān)聯(lián)規(guī)則的可信度大小：

confidence (Ix→Iy)=P(Ix|Iy)

(2)

若包含某項集的事務數(shù)占數(shù)據(jù)庫總事務數(shù)的百分比高于最小支持度，則稱該項集為頻繁項集. 而強關(guān)聯(lián)規(guī)則指的是既滿足最小支持度閾值又滿足最小置信度閾值的規(guī)則.

一般來講，關(guān)聯(lián)規(guī)則挖掘過程主要包括2個步驟：

1) 從事務數(shù)據(jù)庫D中挖掘滿足條件的頻繁項集；

2) 在獲取頻繁項集的基礎(chǔ)上，產(chǎn)生關(guān)聯(lián)規(guī)則.

而FP-growth算法就是針對第1個步驟——挖掘頻繁項集的經(jīng)典算法.

FP-growth算法的實現(xiàn)步驟主要包括產(chǎn)生頻繁項列表，構(gòu)造FP-tree，根據(jù)尾項構(gòu)造各頻繁項的條件FP-tree并分別挖掘，最終求并集來獲取頻繁模式.

假設項集I={A,B,C,D,E}，如表1所示，事務編號TID為101～110的事務數(shù)據(jù)庫D，每個事務T都是項集I的非空子集. 現(xiàn)在用FP-growth算法對此事務數(shù)據(jù)庫進行挖掘.

表1　事務數(shù)據(jù)庫

1) 產(chǎn)生頻繁項列表

首先遍歷整個事務數(shù)據(jù)庫，記錄每個項的支持度計數(shù)，然后分別與最小支持度閾值進行比較(本例中假設最小支持度為2)，刪除支持度小于此閾值的項，即不頻繁項，剩余的所有項按其支持度降序排列，由此得到頻繁項列表(F-list).

本例中，各個項的支持度計數(shù)分別為{E:7;D:6; C:6;B:5;A:3}，均大于最小支持度閾值2，因此不需要刪除任何項.F-list為E-D-C-B-A.

2) 構(gòu)造FP-tree

刪除事務數(shù)據(jù)庫中的不頻繁項后(本例中無不頻繁項，因此沒有需要刪除的項)，把每條事務中剩余的頻繁項按F-list中各項的先后順序(即E—D—C—B—A)重新排列.

重新排序后的事務數(shù)據(jù)庫列表見表2.

表2　重新排序的事務數(shù)據(jù)庫

在創(chuàng)建根節(jié)點“null”的基礎(chǔ)上，遍歷表2中的每條事務，通過合并共同前綴的方式把數(shù)據(jù)壓縮并映射到FP-tree結(jié)構(gòu)中，與此同時保持數(shù)據(jù)之間的關(guān)聯(lián)聯(lián)系不變. 經(jīng)處理，最終得到的FP-tree如圖1所示.

然后按自下而上的順序挖掘FP-tree，從而得出頻繁項集. 具體操作是，以樹的尾項為劃分基準分別進行挖掘，依次得出有關(guān)項的頻繁項集，最后取并集，即可得到事務數(shù)據(jù)庫的所有頻繁項集.

步驟1在FP-tree中保留以A結(jié)尾的路徑，刪除其余路徑，如圖2所示.

步驟2更新每個項的支持度計數(shù). 為詳細闡明更新支持度的過程，首先將獲得圖1時合并的共同前綴分解開. 圖2從表面上看有3條分枝，實際上，第1條分枝可以分解為{E:1—C:1—A:1}，而第2條分枝則可以分解獲得4條子分枝，它們是{E:1—D:1—C:1—A:1}{E:2—D:2—C:2}{E:1}和{E：2—D:2}，第3條分枝可分解為2條子分枝{C:1—B:1—A:1}和{C:1}. 由此可見，以A結(jié)尾的路徑有{E:1—C:1—A:1}{E:1—D:1—C:1—A:1}和{C:1—B:1—A:1}，重新合并共同前綴，得圖3.

步驟3刪除A及其他不頻繁項. 由圖3可知，更新計數(shù)后各項的支持度分別為{E:2;D:1;C:3;B:1;A:3}，已確定A:3>2為頻繁項，于是得到頻繁項集{A}. 為簡化圖形刪除A，再刪除不頻繁項D:1和B:1，最后合并共同前綴(即合并E:2下面的2個C:1)，如圖4所示.

步驟4查找以B-A結(jié)尾的路徑，發(fā)現(xiàn)無符合要求的路徑.

步驟5查找以C-A結(jié)尾的路徑，結(jié)果與圖4一致.

步驟6更新支持度計數(shù)并刪除C后，如圖5所示.

由此，得到頻繁項集{ECA}.

步驟7查找以D-A結(jié)尾的路徑，發(fā)現(xiàn)無符合要求的路徑.

步驟8查找以E-A結(jié)尾的路徑，結(jié)果與圖5一致.

步驟9更新支持度計數(shù)并刪除E后，如圖6所示.

mull

圖6刪除冗余項后以E-A結(jié)尾的FP-tree

Fig.6FP-tree ended withE-Aafter removing

redundant entries

由此，得到頻繁項集{EA}.

至此，已經(jīng)得到以A結(jié)尾的所有頻繁項集：{A}{ECA}{EA}.

以此類推，挖掘有關(guān)其他尾項的頻繁項集. 本例中只剩以B結(jié)尾的路徑，挖掘后得到以B結(jié)尾的頻繁項集為{B}{EDB}{EB}，所以本例最終的挖掘結(jié)果為：頻繁項集{A}{B}{EA}{EB}{ECA}{EDB}.

綜上可見，傳統(tǒng)FP-growth算法采用深度優(yōu)先的處理方法，先后2次遍歷事務數(shù)據(jù)庫，把信息壓縮到一棵FP-tree，遞歸地挖掘頻繁項集. 由于此算法不產(chǎn)生候選項集，因此，相對Apriory算法而言效率有所提高；但是在處理大型數(shù)據(jù)庫時，F(xiàn)P-growth算法需要多次遍歷項表，構(gòu)造數(shù)據(jù)庫的整體FP-tree，而且會無選擇性地輸出挖掘結(jié)果，導致運行時間過長，存在內(nèi)存溢出的可能性.

2　改進算法

2.1UFP算法改進策略

UFP算法相對傳統(tǒng)FP-growth算法的改進主要體現(xiàn)在以下3個方面.

首先，根據(jù)上述FP-growth算法工作原理可知：傳統(tǒng)算法如果要判定某項是否為頻繁項，或是要找出某個頻繁項的支持度計數(shù)，均需從頻繁項列表F-list的第一項開始遍歷，查找到與之匹配的項名稱，返回查找成功和相應的支持度計數(shù)，否則返回查找失敗. 無論頻繁項列表F-list的存儲結(jié)構(gòu)是什么形式，只能進行順序查找. 當頻繁項列表F-list的數(shù)據(jù)集增大時，查找某項的遍歷時間會隨之增加，嚴重影響算法執(zhí)行效率.

而UFP算法通過設定一個散列函數(shù)f(In)，將項名稱In與存儲地址f(In)對應起來，并將其支持度計數(shù)存儲于該地址，最終得到一個散列表，實現(xiàn)了項名稱到存儲地址的映射，進而實現(xiàn)了項名稱到其支持度計數(shù)的映射. 在查找某項的支持度計數(shù)時，只需給出項名稱In，通過散列函數(shù)f(In)可直接計算出其存儲地址，直接獲得其支持度計數(shù)，而無需從第1項遍歷頻繁項列表F-list，時間復雜度由n(頻繁項個數(shù))提高到1.

例如，對表1的事物數(shù)據(jù)庫，其傳統(tǒng)FP-growth算法和UFP算法的存儲結(jié)構(gòu)分別如表3、4所示.

表3　FP-growth算法散列表

表4　UFP算法散列表

對比頻繁項列表F-list的存儲結(jié)構(gòu)表3、4可知，UFP算法效率的提高主要體現(xiàn)在：第2次掃描事物數(shù)據(jù)庫時，刪除了非頻繁項，并且對于含非頻繁項的每條事務，數(shù)據(jù)庫按F-list中順序降序排列. 當對2個支持度計數(shù)相等的項排序時， UFP算法中只需比較其散列函數(shù)值的大小，便可判定項的順序. 例如，表1中TID編號為101的事務中，C和D的支持度都是6，為確定其先后順序，F(xiàn)P-growth算法需在表3中遍歷到第4項，分別記錄下其邏輯地址2和3才能確定項C在項D前面，而UFP算法中只需比較其散列函數(shù)值f(C)和f(D)的大小，即可判定項C在項D前面.

其次，F(xiàn)P-growth算法無選擇性地挖掘事務數(shù)據(jù)庫會輸出大量實際生產(chǎn)過程中操作員不感興趣的無效頻繁項集，這會大大影響算法的運行效率. 而UFP算法是基于知識的智能數(shù)據(jù)挖掘算法，在產(chǎn)生頻繁1-項集后對其進行劃分，將人們關(guān)注的重要信息存儲于關(guān)鍵項表L1，其他信息存儲于非關(guān)鍵項表L2，后續(xù)步驟基于L1進行運算，只會輸出包含L1中的項的頻繁項集，實現(xiàn)了使用關(guān)鍵項約束輸出的目的. 而對于頻繁項集中關(guān)鍵項與非關(guān)鍵項的劃分標準，需要具體情況具體分析. 例如IBM顧額購物籃(IBM quest market-basket)案例中是針對購物籃模型進行數(shù)據(jù)挖掘，目的是找出食品部關(guān)心的關(guān)聯(lián)規(guī)則，所以這里運用UFP算法時，將9個食品大類劃分為關(guān)鍵項，其他類(鞋帽服飾、家電、日用品等)劃分為非關(guān)鍵項. 而TE模型中，將15個已知的典型故障設定為關(guān)鍵項，52個狀態(tài)變量設定為非關(guān)鍵項，最終達到了故障診斷的目的. 可見，項表的劃分原則各個案例不一而同，在工業(yè)故障診斷領(lǐng)域，一般將工業(yè)過程中常見的或可預見的嚴重故障劃分為關(guān)鍵項，把監(jiān)測的控制變量或操作變量劃分為非關(guān)鍵項，最終挖掘出有價值的關(guān)聯(lián)規(guī)則.

采用IBM顧客購物籃人工數(shù)據(jù)合成工具(IBM quest market-basket synthetic data generator)生成20 000條事務，事務數(shù)據(jù)庫涉及60個項，對比FP-growth算法和UFP算法，實驗結(jié)果如表5所示.

表5　FP-growth與UFP算法運行結(jié)果對比表

由此可見，UFP算法采用關(guān)鍵項約束的方法，有效避免了冗余輸出，降低了內(nèi)存的消耗，同時有效地提高了算法的運行效率.

最后，在內(nèi)存問題上，傳統(tǒng)FP-growth算法還存在一個弊端：FP-growth算法使用原始數(shù)據(jù)直接構(gòu)造整體FP-tree，然后從FP-tree中選擇以各個頻繁項結(jié)尾的前綴路徑，從而構(gòu)造各項的條件FP-tree. 而UFP算法基于頻繁項集劃分的思想，分別得到每個頻繁1-項集的數(shù)據(jù)庫子集，直接根據(jù)子集構(gòu)造各項的條件FP-tree，避免了構(gòu)造整體FP-tree占用大量內(nèi)存的缺陷，實現(xiàn)了傳統(tǒng)算法在空間復雜度上的突破.

綜上所述，UFP算法在FP-growth算法流程中利用支持度函數(shù)及劃分思想等輔助手段優(yōu)化了算法，提高了運行效率，節(jié)省了內(nèi)存，并且劃分關(guān)鍵項表和非關(guān)鍵項表，采用關(guān)鍵字篩選的技術(shù)，保證了輸出結(jié)果的價值性.

2.2UFP算法流程

UFP算法具體描述如下.

輸入：事務數(shù)據(jù)庫，最小支持度閾值minsup；

輸出：事務數(shù)據(jù)庫中挖掘出的頻繁項集F.

1) 遍歷數(shù)據(jù)庫，確定每個項的支持度計數(shù).

2) 構(gòu)造支持度函數(shù)f(In). 其中，數(shù)據(jù)庫涉及的項名稱In是自變量，每項In的存儲地址f(In)是因變量，在存儲地址f(In)中寫入該項In的支持度計數(shù)，從而實現(xiàn)項名稱In與其支持度的一一映射關(guān)系.

3) 再次掃描數(shù)據(jù)庫，利用支持度函數(shù)迅速查找事務中每項的支持度并與支持度閾值做比較，把小于支持度閾值的非頻繁1-項集刪除，然后比較剩余的頻繁1-項集的支持度，按計數(shù)由高到低重新排列事務中的項，得到新數(shù)據(jù)庫Dnew.

4) 對頻繁1-項集進行劃分，將人們關(guān)注的信息存儲于關(guān)鍵項表L1={I1,I2,I3, …,Ip}，其他信息存儲于非關(guān)鍵項表L2={Ip+1, …,Im}，每個表中的項都按支持度計數(shù)由大到小的次序排列.

5) 對L1中的項In(n={p,p-1, …, 1})，依次選取數(shù)據(jù)庫Dnew中包含此項的事務. 利用支持度函數(shù)計算包含In的事務中其余項的支持度大小. 從每條事務中刪除支持度計數(shù)小于In的L1中的項、In項本身以及支持度函數(shù)中支持度小于閾值的項，刪除過后的事務便組合成了In的子數(shù)據(jù)集Dn，其中n={p,p-1, …, 1}.

6) 在獲得子數(shù)據(jù)集Dn的基礎(chǔ)上，構(gòu)造In的條件FP-tree，并挖掘以In結(jié)尾的頻繁項集.

7) 將各個子數(shù)據(jù)集Dn挖掘出的頻繁項集求并集，就得出了所有包含關(guān)鍵信息的頻繁項集F.

2.3在故障診斷領(lǐng)域的優(yōu)勢

目前，復雜工業(yè)過程(連續(xù)過程或是間歇過程) 已有大量成熟的故障診斷方法，其中PCA及其改進算法KPCA作為經(jīng)典的多變量統(tǒng)計方法，在監(jiān)控工業(yè)系統(tǒng)中被廣泛使用. 下面將PCA、KPCA與UFP算法進行對比，從而證明UFP算法在故障診斷中的優(yōu)勢.

PCA算法的基本思想是數(shù)據(jù)降維，使用PCA首先要滿足4個前提條件：

1) 數(shù)據(jù)結(jié)構(gòu)是線性的；

2) 數(shù)據(jù)的概率分布滿足指數(shù)型分布；

3) 向量的方差大小與變量的重要性正相關(guān)；

4) 主元相互正交.

而實際生產(chǎn)過程中這些假設的前提條件很難滿足，大大限制了算法的適用性. 例如將TE過程作為研究對象時，實驗結(jié)果[13]表明，PCA算法對溫度等劇烈變化的強非線性變量所引起的故障進行檢測時，會出現(xiàn)明顯的誤報和漏報現(xiàn)象，即PCA在非線性過程中的故障檢測會失效. 而KPCA方法雖然很好地彌補了PCA無法解決非線性問題的弊端，但它只能用于檢測是否發(fā)生了故障，而無法直接沿用線性PCA貢獻圖的方法對引發(fā)故障的原因進行診斷. 為達到故障診斷的目的，KPCA必須先計算核函數(shù)的偏導數(shù)來獲得每個監(jiān)控變量的T2和SPE貢獻率，再由此診斷出故障源，存在計算耗時、仿真速度慢的缺點.

相比之下，UFP算法具有明顯優(yōu)勢. 第4節(jié)中，對TE仿真模型的15種已知的故障進行診斷，對比實驗結(jié)果證明了UFP算法進行非線性模型故障診斷更準確. 而針對其中6種故障算法運行時間的實驗，驗證了UFP算法在運行速度上，相對PCA而言效率有大幅度的提高.

3　TE過程故障診斷

3.1過程描述

TE過程[14]作為一個典型的化工生產(chǎn)模型，具有復雜多變、非線性的特點. 它主要涉及的操作對象有5個：化學反應器、氣液分離器、汽提塔、冷凝器和壓縮機，具體流程如圖7所示.

TE過程的反應器內(nèi)有8種組分共存：A、B、C、D、E、F、G和H，發(fā)生以下4個化學反應：

(3)

其中：A、C、D、E 是生產(chǎn)原料；B是惰性氣體，不參與反應；生產(chǎn)目的是獲取G、H兩種所需產(chǎn)品，而F是副產(chǎn)品，需要及時排除.

TE過程涉及41個測量變量(其中包括22個連續(xù)變量、19個成分變量) 和12個操縱變量，其中第12個操縱變量(攪拌速度) 為恒定值，所以共有52個可控的過程變量. 本文將這52個變量[15]作為狀態(tài)信息，分別對應編號1～52，如表6所示，存放于非關(guān)鍵項表中，最終作為關(guān)聯(lián)規(guī)則前項輸出.

TE仿真模型包括20個典型故障[16]，其中15個是已知的，5個是未知的. 為驗證UFP算法的有效性，本文利用15個已知故障進行實驗，如表7所示，它們在事務數(shù)據(jù)庫中的TID分別為101～115，有關(guān)數(shù)據(jù)存放于關(guān)鍵項表中，最終作為所挖掘關(guān)聯(lián)規(guī)則后項輸出.

在TE過程仿真平臺上，通過改變過程的設定點，分別引發(fā)上述15個故障，運用UFP算法進行故障診斷，從而證明該算法的有效性和優(yōu)越性.

3.2故障診斷

將TE過程仿真產(chǎn)生的事務數(shù)據(jù)庫作為測試數(shù)據(jù)，共包含6 391條故障事務，每條事務中的關(guān)鍵項是101～115中的某個故障變量，非關(guān)鍵項由52個狀態(tài)變量的非空真子集構(gòu)成. 在Microsoft Visual Studio 2005開發(fā)平臺上用C++語言實現(xiàn)UFP算法后，挖掘數(shù)據(jù)庫，產(chǎn)生頻繁項集. 圖8為數(shù)據(jù)挖掘時間的可視化界面.

表6　TE過程中的狀態(tài)變量

續(xù)表

表7　TE過程中的故障變量

在圖8的“閾值”文本框中可任意設置最小支持度，在“keyValues”文本框中可設定關(guān)鍵項，點擊“getdata”按鈕可方便地選擇需要挖掘的數(shù)據(jù)庫，這3項設置完畢后自動開始調(diào)用UFP算法進行挖掘，結(jié)束時算法運行時間自動顯示. 在最小支持度為10%，最小置信度為60%的情況下，共輸出2 207個頻繁項集，最終挖掘出的關(guān)聯(lián)規(guī)則如表8所示.

表8　UFP挖掘結(jié)果

觀察發(fā)現(xiàn)，表8中TID為105(冷凝器冷卻水入口溫度發(fā)生變化) 和TID為109(物料D的溫度發(fā)生變化) 的故障所挖掘出的關(guān)聯(lián)規(guī)則前項相同，而置信度不同. 針對這一情況，可通過增加實驗數(shù)據(jù)和調(diào)節(jié)支持度、置信度的方法，對2種故障加以區(qū)分，而實際工業(yè)生產(chǎn)中工程師應根據(jù)置信度的高低，依次對2種故障進行檢查最終確定故障類型.

表8中，輸出的每條關(guān)聯(lián)規(guī)則都以狀態(tài)信息為規(guī)則前項，故障信息為后項，表明了故障發(fā)生的因果關(guān)系. 為證明UFP算法在故障診斷準確度上的優(yōu)勢，將此實驗結(jié)果與采用PCA和KPCA算法進行故障診斷的結(jié)果進行對比，結(jié)果如表9所示.

表9　PCA與KPCA故障診斷結(jié)果

經(jīng)過仿真證明，遞歸特征消除算法[17](recursive feature elimination，RFE)結(jié)合支持向量機(support vector machines，SVM)進行TE過程故障診斷所得結(jié)果具有較高可信度，其結(jié)果與UFP算法所挖掘出的關(guān)聯(lián)規(guī)則具有高度一致性，而PCA和KPCA的診斷結(jié)果卻出現(xiàn)了較高的誤報率和漏報率，且故障診斷出的原因與實際情況有較大出入，不能正確識別故障. 由此可見，UFP算法在TE過程這類大型非線性系統(tǒng)故障診斷中，與PCA和KPCA算法相比，準確度有較大優(yōu)勢.

為證明UFP算法在運行時間上的優(yōu)越性，對101、102、104、105、107、111這6個故障用PCA算法和UFP算法分別進行故障診斷，運行時間對比如圖9所示.

實驗中，TID為101、102、104、105和107的故障都是變量發(fā)生了階躍變化，而TID為111的故障類型是隨機變化. 實驗結(jié)果表明：在TE過程故障診斷中， UFP算法運行時間較短，尤其是在診斷隨機變化的故障類型時，相對PCA算法運行速度明顯提高. 這是因為PCA是針對線性模型的故障診斷算法，在監(jiān)測溫度這一類非線性變量時，PCA存在準確度和時效性兩方面的明顯弊端，這種缺陷在變量發(fā)生隨機性變化時表現(xiàn)得尤為明顯. 而UFP算法是基于知識的挖掘關(guān)聯(lián)規(guī)則算法，對于TE過程中出現(xiàn)的各類典型故障都能夠快速地實現(xiàn)準確診斷. 綜上所述，UFP算法在故障診斷的準確度和運行效率上相對PCA算法而言都具有明顯的優(yōu)越性.

4　結(jié)論

本文在傳統(tǒng)FP-growth算法的基礎(chǔ)上，提出了UFP改進算法. 此算法與傳統(tǒng)算法的不同之處主要在于：

1) UFP通過構(gòu)造支持度函數(shù)實現(xiàn)了頻繁項名稱與其支持度計數(shù)之間的映射，提高了算法的效率；

2) UFP采用劃分的思想直接生成有關(guān)各關(guān)鍵項的條件FP-tree，節(jié)省了內(nèi)存；

3) UFP劃分關(guān)鍵項表與非關(guān)鍵項表，保證了算法可有效地挖掘出有價值的重要信息.

實驗結(jié)果表明：在TE過程仿真模型上，UFP算法能夠準確地診斷出引發(fā)故障的原因. 在6種不同故障下的對比實驗驗證了UFP算法相對于PCA算法在運行效率上的優(yōu)越性. 盡管如此，UFP算法在挖掘過程中獲得關(guān)聯(lián)規(guī)則后項時，仍存在搜索范圍大、測試點多的缺點，后續(xù)的研究工作將嘗試利用模式識別技術(shù)，對頻繁項集進行分類，縮小搜索范圍，減少測試點個數(shù)，進一步提高獲取關(guān)聯(lián)規(guī)則的速度，最終實現(xiàn)高效穩(wěn)定地挖掘大數(shù)據(jù)的目的.

[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases [J]. Proceedings of the ACM SIGMOD Conference on Management of Data, 1993(12): 207-216.

[2] AGRAWAL R, SHAFER J. Parallel mining of association rules: design, implementation, and experience [R]. San Jose: IBM Almaden Research Center, 1996.

[3] HAN J W, YAN X F. Scalable OLAP and mining of information networks [C]∥Proceedings of the 12th International Conference. Saint Petersburg: ASNT, 2009.

[4] TOHIDI H, IBRAHIM H. A frequent pattern mining algorithm based on FP-growth without generating tree [J]. Proceedings of Knowledge Management 5th International Conference, 2010(34): 723-728.

[5] SILVA A, ANTUNES C. Pattern mining on stars with FP-growth [J]. Lecture Notes in Artificial Intelligence, 2010(5): 175-186.

[6] WANG H, YUNGYEON B. Advanced FP-growth using bit clustering in data mining [J]. Journal of KIISE: Databases, 2011, 38(5): 280-288.

[7] CHEN K, ZHANG L J, LI S K, et al. Research on association rules parallel algorithm based on FP-growth [J]. Communications in Computer and Information Science, 2011, 244(2): 249-256.

[8] WANG H B, LIU YC, WANG C D. Research on association rule algorithm based on distributed and weighted FP-growth [J]. Advances in Intelligent and Soft Computing, 2011, 128(1): 133-138.

[9] TOTAD S G, GEETA R B, REDDY, et al. Batch incremental processing for FP-tree construction using FP-growth algorithm [J]. Knowledge and Information Systems, 2012, 33(2): 475-490.

[10] WANG C H, LEE W H, PANG C T. Fuzzy data mining for quantitative transaction with FP-growth [J]. Journal of Nonlinear and Convex Analysis, 2013, 14(1): 193-207.

[11] SUN H, ZHANG H X, CHEN S P, et al. The study of improved FP-growth algorithm in map reduce [J]. Advances in Intelligent Systems Research, 2013, 52(6): 250-253.

[12] 程丹. 關(guān)聯(lián)分析在中醫(yī)數(shù)據(jù)挖掘中的應用[D]. 北京： 北京交通大學, 2007.

CHENG D. Application of association analysis in TCM data mining [D]. Beijing: Beijing Jiaotong University, 2007. (in Chinese)

[13] 王新明. 基于TE過程的化工過程故障診斷方法研究[D]. 蘭州： 蘭州科技大學, 2010.

WANG X M. Research on fault diagnosis algorithms of chemical process based on TE [D]. Lanzhou: Lanzhou University of Technology, 2010. (in Chinese)

[14] 王婷. 面向TE過程的實時優(yōu)化技術(shù)研究[D]. 北京： 北京化工大學， 2010.

WANG T. Studies on real-time optimization of the Tennessee Eastman problem [D]. Beijing: Beijing University of Chemical Technology, 2010. (in Chiense)

[15] 閆寧， 勞倫斯. 田納西- 伊斯曼過程的在線優(yōu)化[D]. 北京： 北京化工大學， 1996.

YAN N, LAWRENCE R. On-line optimization of the Tennessee Eastman challenge process [D]. Beijing: Beijing University of Chemical Technology, 1996. (in Chiense)

[16] MAURICIO S C. Tennessee Eastman plant-wide industrial process challenge problem [D]. Department of Chemical Engineering Technical University of Denmark, 2004.

[17] 邊雙微. 田納西- 伊斯曼化工過程的故障診斷[D]. 上海： 華中科技大學， 2011.

BIAN S W. Fault diagnosis of Tennessee Eastman chemical process [D]. Shanghai: Huazhong University of Science and Technology, 2011. (in Chinese)

(責任編輯呂小紅)

Improved FP-growth Algorithm With Applications in TE Process Fault Diagnosis

LI Hongguang, XIA Lijun

(College of Information Science & Technology, Beijing University of Chemical Technology, Beijing 100029, China)

FP-growth algorithm is very effective for mining frequent itemsets. However, the huge frequent pattern trees generated due to repeatF-list searching consume a large amount of memory and lead to low efficiency. In response to these drawbacks, this paper presented an improved algorithm, termed as UFP algorithm (upgraded FP-growth). First, it used support function to map the support rate with each item in order to improve the operating efficiency. Second, it took advantage of keyword filtering technology to devide theF-list into two parts, key-item list and non-critical list, ensuring the association rules which ultimately were obtained, were all valid information. Finally, it divided the whole database into subsets according to the first frequent itemsets and constructed condition pattern trees directly which saved lots of memory space. This paper applied UFP algorithm into TE process for fault diagnosis. The comparative experiments with PCA and KPCA algorithm under different process faults improve its superiority.

FP-growth algorithm; association rule; Tenessee Eastman (TE) process; fault diagnosis

2015- 09- 18

中央高?；究蒲袠I(yè)務費資助項目(YS1404)

李宏光(1963—)， 男， 教授, 博士生導師， 主要從事工業(yè)過程控制領(lǐng)域的計算機集成化智能系統(tǒng)方面的研究， E-mail：lihg@mail.buct.edu.cn

TP 273

A

0254-0037(2016)05-0697-10

10.11936/bjutxb2015090050