改進的關聯規則算法在數據挖掘中的探討

楊 艷，韓衛媛，李文成

（1.濟源職業技術學院，濟源 454650；2.河南濟源鋼鐵公司 信息中心，濟源 459000）

0 引言

數據挖掘是數據庫中的知識發現，是指從存放在數據庫、數據倉庫或其他信息庫中的大量數據中自動地發現相關模式、提取有潛在價值的信息、挖掘知識的過程，從CRM 的角度，數據挖掘應用就是從大量數據中挖掘出隱含的、對決策有潛在價值的知識和規則，能夠根據已有的信息對未來發生行為做出結果預測，為企業經營決策、市場策劃提供依據。CRM中的應用中比較典型的數據挖掘方法有關聯分析、序列模式分析、分類和預測分析、聚類分析、演變分析等。

1 關聯規則挖掘的一般步驟

關聯規則挖掘的步驟為：

1）預處理與挖掘任務有關的數據。根據具體問題的要求對數據庫進行相應的操作，從而構成規格化的數據庫D。

2）根據D，通過迭代檢索出事務數據庫中的頻繁項目集L，即支持度不低于用戶設定的最小支持度的項目集，即頻繁項目集。

3）利用頻繁項目集L構造出滿足用戶最小可信度的規則，形成規則集并用可視化方法進行輸出。

2 算法改進——改進的頻繁項目集算法

在本文中，引入參數c，在舊數據集中發現頻繁項目集的過程中，保留那些支持度大于或等于minsup/c（minsup為最小支持度）的頻繁項目集，每次數據庫中增加新的數據集時，只考慮以前產生的支持度大于或等于minsup/c的頻繁項目集和當前增加的數據集，掃描支持度大于或等于minsup/c的頻繁項目集的時間比掃描整個舊數據集的時間要短得多。設原有交易數據庫中的數據集記為D，新增加的數據集記為d，則整個交易數據庫為(D+d)，它的基本思想是：

假設已經采用Apriori算法獲得數據集D的支持度大于或等于minsup/c的頻繁項目集L'(D)，L'(D)中的各個項目集的支持數count及用于計算這個項目集的交易總數countall(如有兩個交易集D1和D2，對于某個項目集L1，它在D1是頻繁項目集，而在D2不是頻繁項目集，則L.countall=D1，如果L1在D1及(D1+D2)中都是頻繁項目集，則Ll.countall=|D1|+|D2|，以下是在增加新的數據集d后的算法的基本思想：

1）根據新數據集d和L'(D)得到支持度大于或等于(minsup/c)的頻繁項目集，加入到(D+d)的支持度大于或等于(minsup/c)的頻繁項目集L'(D+d)中。對于項目集L1,Ll ? L'(D)，則Ll.support=(Ll.count(d)+Ll.count(D))/(Ll.countall(D)+|d|)，把支持度I.support≥minsup/c)的項目集Ll加入(D+d)的頻繁項目集L'(D+d)。

2）遍歷新數據集d，用Apriori算法計算新數據集d中的支持度大于或等于(minsup/c)的頻繁項目集L' (d)，這一步中項目集的支持度的計算方法不同于(1),d中的項目集L1的計算方法為Ll.support= Ll.count(d)/|d|。

3）對于項目集 Ll,Ll ? L'(d)且 Ll ? L'(D 十 d)，則把L1加入到L'(D+d)中。

4）用Apriori算法在得到的支持度大于或等于(minsup/c)的頻繁項目集L'(D十d)中找出支持度大于或等于minsup的頻繁項目集，即L(D+d)。

3 改進的關聯規則算法在數據挖掘中的實際應用

我們選取某鋼鐵公司的銷售數據作為我們的研究對象，來分析關聯規則應用于該系統的過程：

3.1 定義問題

根據CRM的具體目標來設置數據挖掘的目標。我們設置要挖掘的目標是通過對交易數據庫的分析，來發現哪些產品商品被客戶一起購買，利用該結果來制定相應的策略，從而提高廠家的銷售收入。

3.2 建立銷售數據倉庫

我們取“交易”作為主題，而對于其他的主題這里不作考慮，接下去就圍繞交易數據來建立數據倉庫。

表1 交易數據信息

3.3 數據挖掘過程

3.3.1 設置目標數據

我們用Num來表示交易的序號，具有相同的CustomerID和DateId,那么它們將屬于一個單一的購買訂單的交易，在客戶用戶購買一個項目的每條記錄都有的交易貨物productID，這對應于交易數據庫中的銷售合同ContractID。產品編號productID對應于交易數據庫中的貨物。我們根據客戶購買的時間DateID，把它分為不同的時間段，如取定某個日期，對于date小于該日期的數據作為舊數據，用Flag=1來表示，date大于該日期的數據作為新數據，用Flag=2來表示。按這樣的標準轉換后，我們就得到了可用關聯規則挖掘算法進行挖掘的數據。

3.3.2 決定最小支持度和最小可信度

這一步是為特定的數據挖掘過程決定最小支持度和可信度，這兩個因素一般由用戶決定。數據挖掘應用過程中，用戶選擇不同的最小支持度和可信度來得到的關聯規則，然后比較不同的挖掘結果，從而選擇合適的最小支持度和最小可信度。在本例支持度為0.002，可信度為0.15。

3.3.3 執行關聯規則挖掘算法

1）用Apriori算法生成舊數據集D的頻繁項目集

（1）產生支持度大于或等于(minsup/c)的頻繁項目集，

（2）產生支持度大于或等于(minsup/c)的頻繁k(k≥2)項集。在第k-1遍遍歷的過程中，Ck是所有頻繁k項集的一個超集，它是由第k-1遍的頻繁項目集Lk產生在以上過程中，完成了q的聯合和剪枝兩個步驟，例如，L3={{001,002,003),(001,002,004),{001,003,004),{001,003,005),{002,003,004))，那么聯合后得到的候選集的集合C4就是{{1,2,3,4},{1,3,4,5}}。

（3）緊接對得到的候選集的集合Ck進行剪枝，如果有任何一個Ck中元素的(k-I)項子集不在Lk-1中，那么我們就必須從Ck中刪除這個元素。在以上的例子中，雖然{1,3,4,5}是C4的一個元素，但因為它的一個3項子集{3,4,5}不在L3，所以必須把{1,3,4,5}從C4刪除。

通過以上步驟后，我們得到了支持度大于或等于(minsup/c)的頻繁項目集L'(D)，如果我們要獲得支持度大于或等于minsup，那么就可以在以上得到的支持度大于或等于(minsup/c)的頻繁項H集基礎上，再次利用Apriori算法就可獲得支持度大于或等于minsup的頻繁項目集L(D)。

2）根據L(D)遍歷新數據集d生成頻繁項目集

在我們得到舊數據集的支持度大于或等于(minsup/c)的頻繁項目集后，我們以它和新數據集d作為新的挖掘對象，采用Apriori算法進行挖掘，這個過程我們也分成頻繁1項集和頻繁k(k≥2)項集的生成兩個部分：

（1）支持度大于或等于(minsup/c)頻繁1項集的生成。

計算新數據集d的各個1項集的在d中的出現次數和支持度，放在表中，如下所示：

（2）支持度大于或等于(minsup/c)頻繁k(k≥2)項集的生成。

用Apriori中產生候選集的方法，根據頻繁(k-1)項集產生Ck，然后采用頻繁1項集的產生方法生成頻繁k項集。

3）新數據集d的頻繁項目集的生成

新數據集d的支持度大于或等于(minsuplc)的頻繁項目集L'(d)的生成過程和舊數據集D的一樣，這里就不再介紹。

4）把d中不同于頻繁項目集加入L'(D+d)

在得到d的頻繁項目集L'(d)之后，把項目集1,1EL'(d)且1eL'(D+d)插入到L'(D+d)中，這一步實現比較簡單，這里也不作介紹。

5）根據L'(D+d)求出L(D+d)

通過以上幾個步驟我們就得到了支持度大于等于(minsup(c)的頻繁項目集，在這個頻繁項目集的基礎上我們再次采用Apriori算法得到支持度大于或等于minsup的頻繁項目集。

對于每個頻繁項目集，我們要找到所有的關聯規則，如對于頻繁項目集{004，005,006}，可能 的 關 聯 規 則 為 {004}=:＞{005,006}，{005}=＞{005,006},{006}=＞{004,005},{004,005}=＞{006},{004,006}=＞{005},{005,006}=＞{004},并 且 刪 除 可信度小于最小可信度的關聯規則，如關聯規則{004,005}=＞{006}的可信度為confidence({004,00 5}=＞{006})=support({004,005,007})/support({004,0 05})=0.002/0.028=0.071。在這個例子中，我們取最小可信度minconf=0.15，則我們就得到關聯規則存儲表如表2所示。

表2 關聯規則存儲表

將產品代號用產品名稱替換后得到表3。

我們可得到規則：

表3 替換產品名稱

高速線材8.0（35#）=＞光圓鋼筋18(Q235B)可信度為：0.1513，支持度為：0.024

盤螺5.5（HRB335）=＞光圓鋼筋20(Q235B)可信度為：0.3118，支持度為：0.032

4 關聯規則的表示和評價

關聯規則可以用關聯表來表示，也可以用形象的二維或三維的圖來表示。如其中的一條關聯規則表示如下：

規則1：鋼錠15噸(m45錳鋼)=＞鋼錠30噸((ti13鈦鋼)，可信度為0.1513，支持度為0.024。該規則可以這樣理解:在交易數據庫中，每1000筆交易中有24筆的交易，客戶同時訂購了鋼錠15噸(m45錳鋼)和鋼錠30噸((ti13鈦鋼)，并且每1000筆訂購鋼錠15噸(m45錳鋼)的交易中，有151筆交易同時訂購了鋼錠30噸((ti13鈦鋼)。

以上的改進的關聯規則算法能夠在實際中建議生產部門，銷售部門相應改變政策，進行合理的客戶決策，以增加產品收入。能夠留住老客戶，從客戶賺取更多的利潤，并且對客戶的反饋數據進行跟蹤，從而產生具有競爭性的市場策略。

[1]AlexBerson構建面向CRM的數據挖掘應用[M].北京: 人民郵電出版社,2001.

[2]蔣斌.數據挖掘技術在客戶關系管理中的運用[J].云南大學學報(自然科學版),2006,28.

[3]呂美,姬浩.數據挖掘技術在ERP風險防范中的應用研究[J].商場現代化,2006,12.

[4]曾玲,熊才權,胡恬.關聯規則在空間數據挖掘中的研究[J].計算機與數字工程,2005,33(6).

[5]侯偉,楊炳儒.多關系關聯規則算法綜述[J].計算機工程與應用,2007,43(23).

[6]張毅馳,朱巧明.改進的關聯規則算法及其應用[J].計算機系統應用,2007,10.

[7]周艷山.數據挖掘中關聯規則界法的研究及應用[J],2005,3:28.

[8]彭儀普,熊擁軍.關聯規則挖掘Apnd算法優化研究[J].計算機工程,2006,32(05).

[9]范文建,戴齊,陳明.基于粗糙集的關聯規則算法的研究[J].福建電腦,2006,4.