基于矩陣的多維關(guān)聯(lián)規(guī)則算法在煙葉復(fù)烤配方的應(yīng)用研究?

王蘿萍 唐興宏 錢穎穎 馬永凱 于春霞 秦玉華

（1.云南中煙工業(yè)有限責(zé)任公司技術(shù)中心 昆明 650024）（2.青島海大新星計算機(jī)工程中心 青島 266071）（3.青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院 青島 266061）

1 引言

關(guān)聯(lián)規(guī)則［2］是一種很好的挖掘煙葉間組合和搭配的方法。自從R.Agrawal等［3］于1993年提出關(guān)聯(lián)規(guī)則挖掘問題后，眾多的學(xué)者對該問題進(jìn)行了大量的研究，其中最有效和最有影響的是Apriori算法。它以遞歸統(tǒng)計為基礎(chǔ)，生成頻繁項(xiàng)集，易于實(shí)現(xiàn)，但該算法每次尋找K頻繁項(xiàng)集都要掃描一次事務(wù)數(shù)據(jù)庫來獲取候選項(xiàng)集的支持度，頻繁的I/O操作嚴(yán)重影響算法效率。同時，為了生成候選項(xiàng)集，在連接步驟需要大量的比較，非常耗時［4］。針對Apriori算法的不足，已經(jīng)有學(xué)者給出了不同的改進(jìn)方法。FP-Growth算法［5］采取增長模式的遞歸策略，避免了候選項(xiàng)目集的產(chǎn)生，但在挖掘過程中，如果大項(xiàng)集的數(shù)量很多，并且由原數(shù)據(jù)庫得到的FP-tree的分支很多，該算法需構(gòu)造出數(shù)量巨大的conditional FP-tree，不僅費(fèi)時而且要占用大量的空間，挖掘效率較低。Apriori-sort算法［6］用折半插入排序思想對Apriori算法進(jìn)行了改進(jìn)，但當(dāng)事務(wù)數(shù)據(jù)庫非常大時，查找插入點(diǎn)同樣非常耗時。目前在提高關(guān)聯(lián)規(guī)則效率的研究中，大多采用基于Hash函數(shù)技術(shù)及各種剪枝策略［7］，但當(dāng)支持度比較低時，算法效率仍不能較好的提高［8］。此外，目前大部分關(guān)聯(lián)規(guī)則算法主要是針對單維數(shù)據(jù)挖掘，僅包含多次出現(xiàn)的單個謂詞［9］，而煙葉配方組合規(guī)律的挖掘需考慮產(chǎn)地、等級、部位等多個屬性，因此需將單維關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘擴(kuò)展為多維關(guān)聯(lián)規(guī)則挖掘［10］。

針對上述問題，本文在經(jīng)典Apriori算法的基礎(chǔ)上，提出了一種基于矩陣的多維關(guān)聯(lián)規(guī)則改進(jìn)算法并將其應(yīng)用到煙草復(fù)烤模塊配方數(shù)據(jù)挖掘中，該方法通過構(gòu)造多維事務(wù)矩陣［11］，減少了掃描數(shù)據(jù)庫的次數(shù)，同時不斷通過剪枝、剔除冗余事務(wù)對矩陣進(jìn)行壓縮，提高了挖掘效率，從而有效地挖掘出歷史配方中煙葉的搭配和協(xié)同信息。

2 Apriori算法簡介

關(guān)聯(lián)規(guī)則挖掘是從大量數(shù)據(jù)中挖掘項(xiàng)集之間的相關(guān)聯(lián)系［12］。其相關(guān)定義如下：

定義1項(xiàng)與項(xiàng)集［13］：數(shù)據(jù)庫中不可分割的最小單位信息，稱為項(xiàng)目，用符號i表示。項(xiàng)的集合稱為項(xiàng)集。設(shè)集合I={i1,i2,…,ik}是項(xiàng)集，I中項(xiàng)目的個數(shù)為k，則集合I稱為k-項(xiàng)集。

定義2事務(wù)：設(shè)I={i1,i2,…,ik}是由數(shù)據(jù)庫中所有項(xiàng)目構(gòu)成的集合，一次處理所含項(xiàng)目的集合用T表示，T={t1,t2,…,tn}。每一個ti包含的項(xiàng)集都是I子集。

定義3關(guān)聯(lián)規(guī)則：形如 X?Y的蘊(yùn)含式，其中X,Y分別是I的真子集，并且X∩Y=?。X稱為規(guī)則的前提，Y稱為規(guī)則的結(jié)果。關(guān)聯(lián)規(guī)則反映X中的項(xiàng)目出現(xiàn)時，Y中的項(xiàng)目也跟著出現(xiàn)的規(guī)律。

光學(xué)透霧使用透霧鏡頭配合支持透霧的攝像機(jī)組合成的光學(xué)透霧組合，呈現(xiàn)最為明顯的效果，光學(xué)透霧能夠觀察到霧氣后方的景物，具有層次和立體感。

定義4支持度（Support）：事務(wù)集中同時包含的X和Y的事務(wù)個數(shù)與所有事務(wù)數(shù)之和之比，記為support（ X?Y ），即：support（X?Y ）=support X∪Y=P(XY)。

定義5置信度（Confidence）：事務(wù)集中包含 X和Y的事務(wù)集數(shù)與所有包含X的事務(wù)數(shù)之比，記為confidence（X?Y ），即

定義6最小支持度與最小置信度：通常用戶為了達(dá)到一定的要求，需要指定規(guī)則必須滿足的支持度和置信度閾限［14］，當(dāng)support（X?Y）、confidence（X?Y）分別大于等于各自的閾限值時，認(rèn)為X?Y是有趣的，此兩個值稱為最小支持度閾值（min_sup）和最小置信度閾值（min_conf）。其中，min_sup描述了關(guān)聯(lián)規(guī)則的最低重要程度，min_conf規(guī)定了關(guān)聯(lián)規(guī)則必須滿足的最低可靠性。

定義7頻繁項(xiàng)集：設(shè)L={l1,l2,…,ln}為項(xiàng)目的集合，且 L?I,L≠?，對于給定的最小支持度min_sup，如 果 項(xiàng) 集 L的 支 持 度support(L)≥min_sup則稱L為頻繁項(xiàng)集。

定義8強(qiáng)關(guān)聯(lián)規(guī)則：support（ X?Y）≥min_sup且confidence（X?Y ）≥ min_conf，稱關(guān)聯(lián)規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則。

Apriori算法的思想是，掃描一次數(shù)據(jù)庫，找出頻繁1-項(xiàng)集的集合。該集合記作L1。L1用于找所有可能的候選2-項(xiàng)集的集合C2，用L1和C2，找出頻繁2-項(xiàng)集集合L2，而L2用于尋找候選3-項(xiàng)集的集合C3，用 L2和C3，找出頻繁3-項(xiàng)集集合L3。如此下去，直到不能找到頻繁k-項(xiàng)集。其中找每個Lk需要一次數(shù)據(jù)庫掃描。最后用所有頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。生成候選項(xiàng)集主要有兩個步驟：連接和剪枝［15］。連接操作是一種類矩陣運(yùn)算，即Lk-1與Lk-1遵循一定的規(guī)則連接產(chǎn)生可能的候選項(xiàng)。剪枝操作是去掉無意義或者沒有必要的中間結(jié)果。

3 基于矩陣的多維關(guān)聯(lián)規(guī)則改進(jìn)算法

本文提出的基于矩陣的多維關(guān)聯(lián)規(guī)則算法流程圖如圖1所示。

圖1 算法流程圖

具體實(shí)現(xiàn)過程描述如下：

Step1：多維數(shù)據(jù)預(yù)處理。算法在處理數(shù)值型數(shù)據(jù)時，采用分區(qū)的方式將數(shù)據(jù)轉(zhuǎn)化為布爾型數(shù)據(jù)。

Step2：以事務(wù)數(shù)據(jù)庫中的事務(wù)為數(shù)據(jù)源，用Ik表示事務(wù)數(shù)據(jù)庫中的項(xiàng)，Tj表示事務(wù)數(shù)據(jù)庫的事務(wù)，以事務(wù)Tj為行，項(xiàng)Ik為列構(gòu)造矩陣。該事務(wù)中若有此項(xiàng)則填1。當(dāng)沒有此項(xiàng)時填0，掃描事務(wù)數(shù)據(jù)庫，構(gòu)造一個布爾型矩陣A。若該事務(wù)數(shù)據(jù)庫有m個事務(wù)n項(xiàng)，則構(gòu)造的布爾矩陣為一個m行，n列的布爾矩陣。

Step5：求頻繁2項(xiàng)集。當(dāng) sum（Tj）<2時則該事務(wù)不能為頻繁2項(xiàng)集做貢獻(xiàn)，則從矩陣A1中刪除該事務(wù)；將矩陣A1中的列兩兩相交，例如項(xiàng) I1，I2將該兩項(xiàng)取交集后計算支持度計數(shù)為：

當(dāng) sup_count（ I1∩I2）≥ min_sup時，將｛I1，I2｝添加到頻繁2-項(xiàng)集L2中。用篩選后的事務(wù)為行，L2中的項(xiàng)為列，得到新的矩陣A2。

Step6：求頻繁3項(xiàng)集。當(dāng) sum（Tj）<3時則該事務(wù)不能為頻繁3項(xiàng)集做貢獻(xiàn)，則從矩陣A1，A2中刪除該事務(wù)；將矩陣A1與A2中的項(xiàng)兩兩取交集，在求支持度計數(shù)之前，先檢查該項(xiàng)的所有2項(xiàng)子集是否在L2（類推為Lk-1）中。如果是則求支持度計數(shù)，如果不是，則丟棄該項(xiàng)。如I3、（I1，I2）將該兩項(xiàng)取交集后得到（I1，I2，I3），檢查（I1，I2），（I1，I3），（I2，I3）是否都在 L2中。如果是則求支持度計數(shù)：

當(dāng)sup_count（I3,(I1,I2)）≥min_sup時，將｛I1，I2，I3｝添加到頻繁3-項(xiàng)集L3中。用篩選后的事務(wù)為行，L3中的項(xiàng)為列得到新的矩陣A3。

Step7：循環(huán)判斷執(zhí)行Step5，直到求頻繁K項(xiàng)集時，當(dāng)Ak+1=?時結(jié)束循環(huán)，則得到最大頻繁項(xiàng)頻繁K項(xiàng)集。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文方法在模塊配方規(guī)則挖掘方面的有效性，選取了云南中煙技術(shù)中心不同年度120個相近復(fù)烤模塊配方數(shù)據(jù)。表1為某模塊的配方數(shù)據(jù)。可以看出，該模塊配方包含7個單料煙葉，配方人員進(jìn)行配方維護(hù)和設(shè)計時，需考慮煙葉產(chǎn)地、年度、等級、品種、比例等綜合信息。

4.2 數(shù)據(jù)處理

本研究主要考慮對2維的煙葉配方數(shù)據(jù)進(jìn)行挖掘研究。將表1煙葉數(shù)據(jù)根據(jù)產(chǎn)地、品種、等級、年度等信息進(jìn)行編號，如2015年產(chǎn)地C1、品種K326、等級CO2的煙葉編號為P15001，這樣煙葉模塊配方信息可降為2維：等級比例和煙葉編號。

等級比例根據(jù)經(jīng)驗(yàn)劃分為3個等級：<10%為低、10%-20%為中、＞20%為高，分別用數(shù)字0、1、2表示。在編號最前面添加數(shù)字表示此煙葉在復(fù)烤配方模塊中的比例，如0P15001、1P15001、2P15001分別代表編號為P15001的煙葉在配方模塊中所占比例分別為低、中、高。

表2為處理過的120個復(fù)烤模塊，共356個煙葉的事務(wù)矩陣M。其中每一個煙葉用三列表示比例的高、中、低，因此構(gòu)成的事務(wù)矩陣M為120行1068列。

表2 事務(wù)矩陣M

4.3 數(shù)據(jù)挖掘結(jié)果及分析

為減少生成的規(guī)則數(shù)，本研究定義了最小支持度閾值（Minimum Suppport Threshold）為 0.2，最小置信度閥值（Minimum Confidence Threshold）為0.5，滿足條件時才會作為一條規(guī)則。同時為提高關(guān)聯(lián)規(guī)則的準(zhǔn)確性還引入了作用度Lift。Lift計算如下：

只有Lift大于1時，該規(guī)則將被認(rèn)為有效，即規(guī)則中兩事物正相關(guān)。

表3為對120個歷史配方模塊挖掘的部分結(jié)果。其含義如下：對于規(guī)則A?B，支持度表示同時含有某兩種煙葉A、B的概率，置信度表示在包含A煙葉的情況下，同時含包含B煙葉的概率。

表3 煙葉關(guān)聯(lián)規(guī)則表

通過對挖掘出的所有煙葉搭配規(guī)則可以看出，配方模塊中同時包含編號為D15063和D15052的煙葉概率最大 Support(D15063?D15052)=31.58%，同時，它的置信度也是最高的Confidence(D15063?D15052)=83.86%，表明在實(shí)際配方模塊中，該兩個煙葉的搭配比較合理，并且D15063的比例應(yīng)在20%以上，D15052的比例在10%與20%之間。其次是D15089和D15257煙葉組合Support(D15089?D15257)=27.31%，說明該兩個煙葉搭配也比較合理，從挖掘的結(jié)果可以看出，D15089的比例應(yīng)在10%與20%之間，D15257的比例則應(yīng)小于10%。上述結(jié)果與配方人員的經(jīng)驗(yàn)完全一致，說明該挖掘結(jié)果可將歷史配方數(shù)據(jù)中隱含的諸多配方人員的經(jīng)驗(yàn)知識提取為規(guī)則表示形式，從而有效指導(dǎo)實(shí)際復(fù)烤模塊配方維護(hù)工作，減少配方研發(fā)人員的工作量。

圖2 算法效率對比

4.4 算法性能比較

圖2 為本文方法與經(jīng)典Apriori算法的運(yùn)行效率比較?？梢钥闯?，本文所提出的算法運(yùn)行效率明顯高于Apriori算法，特別在數(shù)據(jù)量增多的情況下算法效率提高較為明顯，可以更高效地進(jìn)行關(guān)聯(lián)規(guī)則的挖掘。

5 結(jié)語

本文在傳統(tǒng)Apriori算法的基礎(chǔ)上，針對煙葉復(fù)烤配方模塊多維數(shù)據(jù)挖掘的需求，提出了一種基于矩陣的多維關(guān)聯(lián)規(guī)則改進(jìn)算法，該算法只需要掃描一次事務(wù)數(shù)據(jù)庫，避免了傳統(tǒng)Apriori算法多次掃描事務(wù)數(shù)據(jù)庫的缺陷，有效提高了挖掘效率。在對煙草復(fù)烤模塊歷史配方數(shù)據(jù)挖掘中，能有效地將配方數(shù)據(jù)中隱含的配方專家的配方維護(hù)行為規(guī)律提取為規(guī)則表示形式，并且全面地考慮煙葉間的優(yōu)化組合，減少了配方研發(fā)人員的工作量，該方法可以更高效地指導(dǎo)實(shí)際配方設(shè)計和維護(hù)工作，為模塊配方的優(yōu)化和完善提供新的理論依據(jù)和方法。