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

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

1 引言

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

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

2 Apriori算法簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 算法流程圖

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

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

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

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

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

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

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

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

4 實驗及結(jié)果分析

4.1 實驗數(shù)據(jù)

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

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

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

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

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

表2 事務矩陣M

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

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

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

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

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

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

圖2 算法效率對比

4.4 算法性能比較

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

5 結(jié)語

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