改進(jìn)的關(guān)聯(lián)規(guī)則算法在數(shù)據(jù)挖掘中的探討

楊 艷，韓衛(wèi)媛，李文成

（1.濟(jì)源職業(yè)技術(shù)學(xué)院，濟(jì)源 454650；2.河南濟(jì)源鋼鐵公司 信息中心，濟(jì)源 459000）

0 引言

數(shù)據(jù)挖掘是數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)，是指從存放在數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的大量數(shù)據(jù)中自動(dòng)地發(fā)現(xiàn)相關(guān)模式、提取有潛在價(jià)值的信息、挖掘知識(shí)的過程，從CRM 的角度，數(shù)據(jù)挖掘應(yīng)用就是從大量數(shù)據(jù)中挖掘出隱含的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則，能夠根據(jù)已有的信息對(duì)未來發(fā)生行為做出結(jié)果預(yù)測(cè)，為企業(yè)經(jīng)營(yíng)決策、市場(chǎng)策劃提供依據(jù)。CRM中的應(yīng)用中比較典型的數(shù)據(jù)挖掘方法有關(guān)聯(lián)分析、序列模式分析、分類和預(yù)測(cè)分析、聚類分析、演變分析等。

1 關(guān)聯(lián)規(guī)則挖掘的一般步驟

關(guān)聯(lián)規(guī)則挖掘的步驟為：

1）預(yù)處理與挖掘任務(wù)有關(guān)的數(shù)據(jù)。根據(jù)具體問題的要求對(duì)數(shù)據(jù)庫(kù)進(jìn)行相應(yīng)的操作，從而構(gòu)成規(guī)格化的數(shù)據(jù)庫(kù)D。

2）根據(jù)D，通過迭代檢索出事務(wù)數(shù)據(jù)庫(kù)中的頻繁項(xiàng)目集L，即支持度不低于用戶設(shè)定的最小支持度的項(xiàng)目集，即頻繁項(xiàng)目集。

3）利用頻繁項(xiàng)目集L構(gòu)造出滿足用戶最小可信度的規(guī)則，形成規(guī)則集并用可視化方法進(jìn)行輸出。

2 算法改進(jìn)——改進(jìn)的頻繁項(xiàng)目集算法

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

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

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

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

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

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

3 改進(jìn)的關(guān)聯(lián)規(guī)則算法在數(shù)據(jù)挖掘中的實(shí)際應(yīng)用

我們選取某鋼鐵公司的銷售數(shù)據(jù)作為我們的研究對(duì)象，來分析關(guān)聯(lián)規(guī)則應(yīng)用于該系統(tǒng)的過程：

3.1 定義問題

根據(jù)CRM的具體目標(biāo)來設(shè)置數(shù)據(jù)挖掘的目標(biāo)。我們?cè)O(shè)置要挖掘的目標(biāo)是通過對(duì)交易數(shù)據(jù)庫(kù)的分析，來發(fā)現(xiàn)哪些產(chǎn)品商品被客戶一起購(gòu)買，利用該結(jié)果來制定相應(yīng)的策略，從而提高廠家的銷售收入。

3.2 建立銷售數(shù)據(jù)倉(cāng)庫(kù)

我們?nèi)　敖灰住弊鳛橹黝}，而對(duì)于其他的主題這里不作考慮，接下去就圍繞交易數(shù)據(jù)來建立數(shù)據(jù)倉(cāng)庫(kù)。

表1 交易數(shù)據(jù)信息

3.3 數(shù)據(jù)挖掘過程

3.3.1 設(shè)置目標(biāo)數(shù)據(jù)

我們用Num來表示交易的序號(hào)，具有相同的CustomerID和DateId,那么它們將屬于一個(gè)單一的購(gòu)買訂單的交易，在客戶用戶購(gòu)買一個(gè)項(xiàng)目的每條記錄都有的交易貨物productID，這對(duì)應(yīng)于交易數(shù)據(jù)庫(kù)中的銷售合同ContractID。產(chǎn)品編號(hào)productID對(duì)應(yīng)于交易數(shù)據(jù)庫(kù)中的貨物。我們根據(jù)客戶購(gòu)買的時(shí)間DateID，把它分為不同的時(shí)間段，如取定某個(gè)日期，對(duì)于date小于該日期的數(shù)據(jù)作為舊數(shù)據(jù)，用Flag=1來表示，date大于該日期的數(shù)據(jù)作為新數(shù)據(jù)，用Flag=2來表示。按這樣的標(biāo)準(zhǔn)轉(zhuǎn)換后，我們就得到了可用關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行挖掘的數(shù)據(jù)。

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

這一步是為特定的數(shù)據(jù)挖掘過程決定最小支持度和可信度，這兩個(gè)因素一般由用戶決定。數(shù)據(jù)挖掘應(yīng)用過程中，用戶選擇不同的最小支持度和可信度來得到的關(guān)聯(lián)規(guī)則，然后比較不同的挖掘結(jié)果，從而選擇合適的最小支持度和最小可信度。在本例支持度為0.002，可信度為0.15。

3.3.3 執(zhí)行關(guān)聯(lián)規(guī)則挖掘算法

1）用Apriori算法生成舊數(shù)據(jù)集D的頻繁項(xiàng)目集

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

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

（3）緊接對(duì)得到的候選集的集合Ck進(jìn)行剪枝，如果有任何一個(gè)Ck中元素的(k-I)項(xiàng)子集不在Lk-1中，那么我們就必須從Ck中刪除這個(gè)元素。在以上的例子中，雖然{1,3,4,5}是C4的一個(gè)元素，但因?yàn)樗囊粋€(gè)3項(xiàng)子集{3,4,5}不在L3，所以必須把{1,3,4,5}從C4刪除。

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

2）根據(jù)L(D)遍歷新數(shù)據(jù)集d生成頻繁項(xiàng)目集

在我們得到舊數(shù)據(jù)集的支持度大于或等于(minsup/c)的頻繁項(xiàng)目集后，我們以它和新數(shù)據(jù)集d作為新的挖掘?qū)ο?，采用Apriori算法進(jìn)行挖掘，這個(gè)過程我們也分成頻繁1項(xiàng)集和頻繁k(k≥2)項(xiàng)集的生成兩個(gè)部分：

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

計(jì)算新數(shù)據(jù)集d的各個(gè)1項(xiàng)集的在d中的出現(xiàn)次數(shù)和支持度，放在表中，如下所示：

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

用Apriori中產(chǎn)生候選集的方法，根據(jù)頻繁(k-1)項(xiàng)集產(chǎn)生Ck，然后采用頻繁1項(xiàng)集的產(chǎn)生方法生成頻繁k項(xiàng)集。

3）新數(shù)據(jù)集d的頻繁項(xiàng)目集的生成

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

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

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

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

通過以上幾個(gè)步驟我們就得到了支持度大于等于(minsup(c)的頻繁項(xiàng)目集，在這個(gè)頻繁項(xiàng)目集的基礎(chǔ)上我們?cè)俅尾捎肁priori算法得到支持度大于或等于minsup的頻繁項(xiàng)目集。

對(duì)于每個(gè)頻繁項(xiàng)目集，我們要找到所有的關(guān)聯(lián)規(guī)則，如對(duì)于頻繁項(xiàng)目集{004，005,006}，可能 的 關(guān) 聯(lián) 規(guī) 則 為 {004}=:＞{005,006}，{005}=＞{005,006},{006}=＞{004,005},{004,005}=＞{006},{004,006}=＞{005},{005,006}=＞{004},并 且 刪 除 可信度小于最小可信度的關(guān)聯(lián)規(guī)則，如關(guān)聯(lián)規(guī)則{004,005}=＞{006}的可信度為confidence({004,00 5}=＞{006})=support({004,005,007})/support({004,0 05})=0.002/0.028=0.071。在這個(gè)例子中，我們?nèi)∽钚】尚哦萴inconf=0.15，則我們就得到關(guān)聯(lián)規(guī)則存儲(chǔ)表如表2所示。

表2 關(guān)聯(lián)規(guī)則存儲(chǔ)表

將產(chǎn)品代號(hào)用產(chǎn)品名稱替換后得到表3。

我們可得到規(guī)則：

表3 替換產(chǎn)品名稱

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

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

4 關(guān)聯(lián)規(guī)則的表示和評(píng)價(jià)

關(guān)聯(lián)規(guī)則可以用關(guān)聯(lián)表來表示，也可以用形象的二維或三維的圖來表示。如其中的一條關(guān)聯(lián)規(guī)則表示如下：

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

以上的改進(jìn)的關(guān)聯(lián)規(guī)則算法能夠在實(shí)際中建議生產(chǎn)部門，銷售部門相應(yīng)改變政策，進(jìn)行合理的客戶決策，以增加產(chǎn)品收入。能夠留住老客戶，從客戶賺取更多的利潤(rùn)，并且對(duì)客戶的反饋數(shù)據(jù)進(jìn)行跟蹤，從而產(chǎn)生具有競(jìng)爭(zhēng)性的市場(chǎng)策略。

[1]AlexBerson構(gòu)建面向CRM的數(shù)據(jù)挖掘應(yīng)用[M].北京: 人民郵電出版社,2001.

[2]蔣斌.數(shù)據(jù)挖掘技術(shù)在客戶關(guān)系管理中的運(yùn)用[J].云南大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,28.

[3]呂美,姬浩.數(shù)據(jù)挖掘技術(shù)在ERP風(fēng)險(xiǎn)防范中的應(yīng)用研究[J].商場(chǎng)現(xiàn)代化,2006,12.

[4]曾玲,熊才權(quán),胡恬.關(guān)聯(lián)規(guī)則在空間數(shù)據(jù)挖掘中的研究[J].計(jì)算機(jī)與數(shù)字工程,2005,33(6).

[5]侯偉,楊炳儒.多關(guān)系關(guān)聯(lián)規(guī)則算法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(23).

[6]張毅馳,朱巧明.改進(jìn)的關(guān)聯(lián)規(guī)則算法及其應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2007,10.

[7]周艷山.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則界法的研究及應(yīng)用[J],2005,3:28.

[8]彭儀普,熊擁軍.關(guān)聯(lián)規(guī)則挖掘Apnd算法優(yōu)化研究[J].計(jì)算機(jī)工程,2006,32(05).

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