改進(jìn)Apriori算法對(duì)試車臺(tái)監(jiān)測(cè)數(shù)據(jù)的關(guān)聯(lián)挖掘

劉自然，王律強(qiáng)，李愛(ài)民，張躍春，顏丙生，甄守樂(lè)，熊 偉

（1.河南工業(yè)大學(xué)機(jī)電工程學(xué)院，河南 鄭州 450007；2.河南工業(yè)大學(xué)工程訓(xùn)練中心，河南 鄭州 450007；3.中航工業(yè)湖南南方宇航高精傳動(dòng)有限公司，湖南 株洲 412002）

0 引 言

航空發(fā)動(dòng)機(jī)傳動(dòng)附件作為航空發(fā)動(dòng)機(jī)的關(guān)鍵部件，在裝機(jī)前需采用試車監(jiān)視系統(tǒng)進(jìn)行試驗(yàn)，試車過(guò)程中得到的數(shù)據(jù)存儲(chǔ)在傳動(dòng)附件試車臺(tái)監(jiān)測(cè)軟件中。然而，這些數(shù)據(jù)只用于一般的查詢或統(tǒng)計(jì)處理，沒(méi)有進(jìn)行深刻的分析理解；如何從這些數(shù)據(jù)中找出（或發(fā)現(xiàn)）對(duì)試車工作有指導(dǎo)意義的規(guī)則（或知識(shí)）非常有工程應(yīng)用價(jià)值。將關(guān)聯(lián)規(guī)則技術(shù)應(yīng)用于航空發(fā)動(dòng)機(jī)傳動(dòng)附件的試車監(jiān)測(cè)數(shù)據(jù)挖掘[1]中，可以有效地發(fā)現(xiàn)航空發(fā)動(dòng)機(jī)傳動(dòng)附件各變量間的關(guān)聯(lián)規(guī)則，監(jiān)測(cè)試車臺(tái)狀態(tài)的變化，以便更好地管理試車臺(tái)。針對(duì)原有Apriori算法對(duì)數(shù)據(jù)集掃描次數(shù)過(guò)多，產(chǎn)生候選集多導(dǎo)致效率不高的問(wèn)題，提出了一種改進(jìn)的Apriori算法，并應(yīng)用于某試車臺(tái)監(jiān)測(cè)數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘中。

1 關(guān)聯(lián)規(guī)則技術(shù)的原理及方法

假設(shè) I={i1，i2，…，im}是 m 項(xiàng)的集合，即數(shù)據(jù)庫(kù)中屬性的集合。事務(wù) t也是項(xiàng)的集合，即 ti?I，i=1，2，3，…，m。T 為事務(wù)的集合，即 T={t1，t2，…，tm}，ti?I。設(shè) X是一個(gè)項(xiàng)集，其中含有k個(gè)項(xiàng)的項(xiàng)集稱之為k-項(xiàng)集。當(dāng)且僅當(dāng)X?Ii時(shí)，事務(wù)ti包含X。事務(wù)集T中項(xiàng)集X的支持度Sup（X）是集合T中包含X的事務(wù)的頻率，即 Sup（X）=P（X）。若 Sup（X）≥min-sup，其中min-sup是給定的最小支持度，則稱X為頻繁項(xiàng)集[2]。設(shè)Y是I中另一個(gè)項(xiàng)集，則關(guān)聯(lián)規(guī)則就是形如X?Y的表達(dá)式，其中X?I，Y?I，并且X∩Y=Φ。關(guān)聯(lián)規(guī)則X?Y在事務(wù)集T中的置信度conf（X?Y）是T中同時(shí)包括X和Y的事務(wù)的頻率，即conf（X?Y）=P（Y|X）。

因此，關(guān)聯(lián)規(guī)則挖掘可以分以下兩步完成：

1）通過(guò)事先設(shè)定的min-sup，找出所有的頻繁項(xiàng)集，即找出支持度大于或等于給定的最小支持度閾值的所有項(xiàng)集，從而遞歸查找1到k的頻繁項(xiàng)集。

2）由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，即找到滿足最小支持度（min-sup）和最小置信度（min-conf）的關(guān)聯(lián)規(guī)則。步驟2）實(shí)現(xiàn)簡(jiǎn)單，關(guān)聯(lián)規(guī)則挖掘算法的性能主要集中在步驟1）上，大多數(shù)算法都集中在怎樣高效發(fā)現(xiàn)頻繁項(xiàng)集[2-3]。

在眾多的現(xiàn)成關(guān)聯(lián)規(guī)則挖掘算法中，由R.AGRAWAL等首先提出的Apriori算法是一種有效的頻繁項(xiàng)集挖掘算法，之后的算法基本是在其基礎(chǔ)上的改進(jìn)。該算法是利用遞歸迭代方法來(lái)完成頻繁項(xiàng)集的挖掘工作，即利用k-項(xiàng)集來(lái)生成（k+l）-項(xiàng)集，用候選項(xiàng)集Ck找頻繁項(xiàng)集Lk。首先，找到頻繁1-項(xiàng)集的集合，記作L1。然后用Ll去找頻繁2-項(xiàng)集的集合L2，得到的L2用于找L3，如此遞歸，直到k足夠大以至不能找到頻繁k-項(xiàng)集。找到每個(gè)Lk需要進(jìn)行一次數(shù)據(jù)庫(kù)掃描。從事務(wù)集T中找出頻繁項(xiàng)集后，再根據(jù)最小置信度直接產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。經(jīng)典Apriori算法的缺陷[4]是：可能需要產(chǎn)生大量的候選項(xiàng)集和重復(fù)地掃描數(shù)據(jù)庫(kù)，需要檢查一個(gè)很大的候選集合。

2 Apriori算法的改進(jìn)

2.1 Apriori算法改進(jìn)思路

提高經(jīng)典Apriori算法的效率，關(guān)鍵在于減少候選集的產(chǎn)生?；谶@種思路，提出了減少事務(wù)的改進(jìn)Apriori算法，其目標(biāo)是減少用于未來(lái)掃描的事務(wù)集的大小。改進(jìn)算法的基本原理是不包含任何k-項(xiàng)集的事務(wù)不可能包含任何（k+1）-項(xiàng)集，因而在產(chǎn)生j-項(xiàng)集（j>k）時(shí)，可以不再掃描這些事務(wù)。這樣，其后在考察這種事務(wù)時(shí)，可以直接刪除。

改進(jìn)的 Apriori算法思路是：首先，對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次全面掃描，確定記錄數(shù)量并對(duì)記錄進(jìn)行排序，然后在生成候選集C1的同時(shí)，刪除事務(wù)集中不支持L1的事務(wù)以及事務(wù)中的項(xiàng)目；第3步是對(duì)數(shù)據(jù)庫(kù)中項(xiàng)目集進(jìn)行二進(jìn)制編碼，編碼的長(zhǎng)度為記錄數(shù)量，項(xiàng)目在事務(wù)集的某個(gè)記錄中出現(xiàn)時(shí)用“1”表示，沒(méi)有出現(xiàn)時(shí)則用“0”表示；第4步是將得到的編碼表進(jìn)行轉(zhuǎn)置，生成關(guān)于項(xiàng)集編碼的表格，并對(duì)關(guān)于項(xiàng)集Ii編碼中“1”的個(gè)數(shù)進(jìn)行累加計(jì)數(shù)，由給定的最小支持度與“1”的計(jì)數(shù)進(jìn)行比較，若count（1）≥min-sup，則得到的為頻繁1-項(xiàng)集；第5步是將頻繁（k-1）-項(xiàng)集中的項(xiàng)編碼進(jìn)行“與”運(yùn)算。在產(chǎn)生的新編碼中統(tǒng)計(jì)“1”的個(gè)數(shù)，如果count（1）≥min-sup，則產(chǎn)生頻繁k-項(xiàng)集。最后重復(fù)第5步，直到找到需要的頻繁項(xiàng)集L。

圖1 改進(jìn)Apriori算法舉例示意圖

2.2 改進(jìn)后的Apriori算法舉例

為更好說(shuō)明改進(jìn)算法的工作過(guò)程，以4個(gè)項(xiàng)集，4個(gè)事務(wù)為集合進(jìn)行關(guān)聯(lián)規(guī)則挖掘說(shuō)明。假定最小支持度為2，根據(jù)改進(jìn)后的Apriori算法，具體的過(guò)程如圖1所示。首先掃描數(shù)據(jù)庫(kù)，對(duì)事務(wù)集中的項(xiàng)目進(jìn)行編碼，由事務(wù)項(xiàng)目編碼表在垂直方向的項(xiàng)轉(zhuǎn)置成項(xiàng)集一個(gè)二維表，表中的編碼是項(xiàng)在事務(wù)表中每條記錄中是否出現(xiàn)的編碼序列，“1”代表出現(xiàn)，“0”代表不出現(xiàn)。根據(jù)項(xiàng)目表計(jì)算頻繁1-項(xiàng)集，統(tǒng)計(jì)編碼中“1”的個(gè)數(shù)，由于I4的編碼計(jì)數(shù)為1，小于最小支持度2，所以進(jìn)行項(xiàng)目壓縮，刪除項(xiàng)目I4，由頻繁1-項(xiàng)集的項(xiàng)目編碼進(jìn)行與運(yùn)算，最終得到頻繁2-項(xiàng)集。

從上述分析可以看出，改進(jìn)的算法在第1步掃描數(shù)據(jù)庫(kù)并對(duì)每個(gè)項(xiàng)目編碼，后續(xù)的過(guò)程都是針對(duì)編碼進(jìn)行“與”運(yùn)算，不需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行重復(fù)掃描。同時(shí)由于刪除了小于最小支持度的項(xiàng)以及含有該項(xiàng)目的事務(wù)，可以有效地減小系統(tǒng)的開(kāi)銷，從而提高挖掘效率。

3 監(jiān)測(cè)數(shù)據(jù)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘

在試車臺(tái)監(jiān)測(cè)系統(tǒng)中，考慮成本和可行性，分為兩大系統(tǒng)：以Wincc為平臺(tái)組建的監(jiān)測(cè)壓力、流量、溫度等低頻參變量的監(jiān)控系統(tǒng)和以LabVIEW為平臺(tái)搭建的測(cè)量振幅的振動(dòng)測(cè)試系統(tǒng)。兩套系統(tǒng)在物理上相互獨(dú)立，其隱藏的參量關(guān)聯(lián)必須通過(guò)關(guān)聯(lián)規(guī)則進(jìn)行挖掘。同時(shí)，因?yàn)長(zhǎng)abVIEW和Wincc自身并沒(méi)有自帶數(shù)據(jù)挖掘功能，必須將其所存儲(chǔ)的數(shù)據(jù)進(jìn)行轉(zhuǎn)換，亦即數(shù)據(jù)預(yù)處理，才能在統(tǒng)一的專業(yè)挖掘軟件進(jìn)行挖掘。圖2為用改進(jìn)的Apriori算法挖掘監(jiān)測(cè)系統(tǒng)關(guān)聯(lián)規(guī)則的技術(shù)路線圖。在某試車臺(tái)試驗(yàn)過(guò)程中采集到一周左右的壓力、流量、溫度等參量記錄，原始數(shù)據(jù)形式如表1所示。

圖2 關(guān)聯(lián)規(guī)則挖掘技術(shù)路線圖

表1 試車臺(tái)系統(tǒng)監(jiān)測(cè)記錄

3.1 數(shù)據(jù)選擇和屬性編碼

考慮到數(shù)據(jù)挖掘時(shí)樣本規(guī)模及計(jì)算機(jī)的計(jì)算能力，沒(méi)有必要將監(jiān)測(cè)得到的所有數(shù)據(jù)都用于挖掘，有些數(shù)據(jù)對(duì)象和數(shù)據(jù)屬性對(duì)建立模型的作用可能是重復(fù)的，這些數(shù)據(jù)的引入對(duì)挖掘效率會(huì)產(chǎn)生較大的影響，甚至還可能導(dǎo)致挖掘結(jié)果的偏差。因此，選擇有效的數(shù)據(jù)很有必要。數(shù)據(jù)選擇包括屬性選擇和數(shù)據(jù)抽樣。由于傳動(dòng)附件試車臺(tái)系統(tǒng)中振動(dòng)系統(tǒng)自成一體，振動(dòng)這一屬性必須予以考慮。在監(jiān)控系統(tǒng)中，齒輪箱出口壓力與油箱壓力基本一致，若將其考慮進(jìn)來(lái)，得到的關(guān)聯(lián)規(guī)則基本是與這個(gè)參量相關(guān)的強(qiáng)規(guī)則，導(dǎo)致較大偏差，應(yīng)該予以刪除。而電機(jī)功率以及輸出轉(zhuǎn)速是通過(guò)輸入轉(zhuǎn)速、傳動(dòng)比、扭矩計(jì)算出來(lái)的，本身就存在函數(shù)關(guān)系，在挖掘時(shí)，不予考慮?；诖?，最終選擇了試車數(shù)據(jù)壓力、流量等28個(gè)對(duì)挖掘有用的參數(shù)進(jìn)行挖掘。參照文獻(xiàn)[5]對(duì)各個(gè)屬性進(jìn)行編碼，如表2所示。

表2 屬性編碼表

表3 轉(zhuǎn)換后的事務(wù)數(shù)據(jù)片段表

3.2 空缺值處理

試車過(guò)程中數(shù)據(jù)也不總是完整的，有時(shí)在某些記錄的屬性上可能出現(xiàn)空缺值。在數(shù)據(jù)的采集過(guò)程中，無(wú)論傳感器還是采集系統(tǒng)某個(gè)部分的故障均有可能導(dǎo)致空缺值的出現(xiàn)。對(duì)于空缺值的處理比較簡(jiǎn)單，可以采取忽略、人工填寫(xiě)空缺值、使用屬性的平均值填充等方法[6]進(jìn)行處理。由于試車過(guò)程中，溫度是緩變的，若溫度出現(xiàn)空缺值，使用人工填寫(xiě)較為合適。對(duì)于像振幅這樣的高頻參量，可以使用振幅的平均值來(lái)補(bǔ)充空缺值。

3.3 數(shù)據(jù)離散化

挖掘關(guān)聯(lián)規(guī)則的關(guān)鍵在于將連續(xù)型數(shù)值合理離散化，然后將其轉(zhuǎn)化為布爾關(guān)聯(lián)規(guī)則進(jìn)行處理，常見(jiàn)的屬性離散化方法有等寬離散法、等頻離散法、基于距離劃分法[7]。從監(jiān)控系統(tǒng)中導(dǎo)出的如流量、壓力、溫度等由于是緩變信號(hào)，可以采用等寬離散法進(jìn)行離散。而對(duì)于從振動(dòng)系統(tǒng)中導(dǎo)出的振幅數(shù)據(jù)，則采用等頻離散法[8]更為合適。經(jīng)數(shù)據(jù)預(yù)處理后的數(shù)據(jù)，形成以振幅、溫度、流量、壓力等為項(xiàng)目集的事務(wù)數(shù)據(jù)集，如表3所示。將所得到的事務(wù)數(shù)據(jù)集項(xiàng)目根據(jù)改進(jìn)后的Apriori算法進(jìn)行編碼，分別用yes和no來(lái)表示相應(yīng)代號(hào)出現(xiàn)、不出現(xiàn)，這樣初步完成數(shù)據(jù)的預(yù)處理。

表4 監(jiān)測(cè)數(shù)據(jù)挖掘產(chǎn)生的部分關(guān)聯(lián)規(guī)則

3.4 改進(jìn)算法的關(guān)聯(lián)規(guī)則挖掘

采用Weka3.7.0分別運(yùn)行原Apriori算法及改進(jìn)的Apriori算法，選用試車臺(tái)一周左右的試車數(shù)據(jù)。經(jīng)反復(fù)試驗(yàn)并參考文獻(xiàn)[9]設(shè)置兩種算法，設(shè)置關(guān)聯(lián)規(guī)則的支持度均為0.8，置信度均為0.9，得到了按置信度排序的前30條規(guī)則，選取部分有效的關(guān)聯(lián)規(guī)則，如表4所示。

在系統(tǒng)中，增壓出口1溫度與增壓出口1流量有較高的關(guān)聯(lián)性，置信度為100%。振動(dòng)幅值與增壓出口有一定的負(fù)相關(guān)性，振動(dòng)值低的時(shí)候溫度反而高，由此可見(jiàn)增壓出口1溫度在后續(xù)的試車過(guò)程中應(yīng)予以重視。齒輪箱入口壓力與溫度關(guān)聯(lián)度很高，置信度為100%，在試車臺(tái)子系統(tǒng)齒輪箱潤(rùn)滑系統(tǒng)中，這兩個(gè)參數(shù)在再次試車時(shí)也應(yīng)重點(diǎn)關(guān)注。

用改進(jìn)的算法進(jìn)行挖掘，得到的規(guī)則支持度與置信度相同，但運(yùn)行時(shí)間減少，改進(jìn)前后所運(yùn)行的時(shí)間如表5所示。可以看出，支持度小時(shí)，兩者相差的時(shí)間較大；支持度大時(shí)，兩者相差的時(shí)間較少。這是因?yàn)橹С侄刃〉臅r(shí)候，產(chǎn)生的候選集多，而改進(jìn)的算法使候選集減少最終減少了運(yùn)行的時(shí)間。由于兩種算法的支持度和置信度均一樣，可以看出改進(jìn)后的算法降低了運(yùn)算時(shí)間，節(jié)約了系統(tǒng)開(kāi)銷。

4 結(jié)束語(yǔ)

針對(duì)某試車臺(tái)監(jiān)測(cè)系統(tǒng)監(jiān)測(cè)數(shù)據(jù)進(jìn)行了關(guān)聯(lián)規(guī)則的挖掘，引進(jìn)Apriori算法，得到具有單獨(dú)特征量監(jiān)測(cè)不到的規(guī)則，這些規(guī)則為后續(xù)的安全試車提供了重要參考。提出了Apriori改進(jìn)算法，用采集的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，采用相同的支持度和置信度，挖掘結(jié)果表明，改進(jìn)的算法可以減少候選集從而降低運(yùn)算時(shí)間。

表5 改進(jìn)算法與改進(jìn)算法運(yùn)算時(shí)間比較

[1]彭興慧.WS9發(fā)動(dòng)機(jī)試車數(shù)據(jù)庫(kù)數(shù)據(jù)挖掘技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2005.

[2]陳文慶，許棠.關(guān)聯(lián)規(guī)則挖掘Apriori算法的改進(jìn)與實(shí)現(xiàn)[J].微機(jī)發(fā)展，2005，15（8）：155-157.

[3]高海洋，沈強(qiáng)，張軒溢，等.一種基于數(shù)據(jù)壓縮的Apriori算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（14）：117-120.

[4]龍冰瑩，陳小惠.改進(jìn)Apriori算法在醫(yī)院監(jiān)護(hù)中心的研究與應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（8）：137-140.

[5]Kusiak A，Verma A.A data-mining approach to monitoring wind turbines[J].IEEE Transactions on sustainable energy，2012，3（1）：150-157.

[6]李峰，姜麗莉.關(guān)聯(lián)規(guī)則挖掘在煤礦安全監(jiān)測(cè)中應(yīng)用[J].軟件，2011，32（2）：85-86.

[7]龔舒.橋吊動(dòng)態(tài)性能參數(shù)的統(tǒng)計(jì)特征分析及關(guān)聯(lián)規(guī)則挖掘[D].上海：上海海事大學(xué)，2005.

[8]王志欣.岸橋機(jī)械動(dòng)態(tài)特征信息的數(shù)據(jù)挖掘與狀態(tài)識(shí)別[D].上海：上海交通大學(xué)，2008.

[9]李瑤，陳佳，陳羅峰.改進(jìn)的Apriori算法在服裝營(yíng)銷中的知識(shí)發(fā)現(xiàn)研究[J].信息技術(shù)，2013（3）：100-104.