朱龍

（四川信息職業(yè)技術(shù)學(xué)院 信息工程系，四川 廣元628040）

購(gòu)物籃分析是大數(shù)據(jù)在零售業(yè)的一個(gè)嶄新應(yīng)用方向，就是商家希望通過(guò)分析每個(gè)購(gòu)物籃子中都裝了什么商品，進(jìn)而通過(guò)這些信息來(lái)研究顧客們的購(gòu)買(mǎi)喜好，找出其中暗含的規(guī)則，其最終目標(biāo)就是讓超市和生產(chǎn)企業(yè)通過(guò)大數(shù)據(jù)挖掘，建立自己產(chǎn)品的競(jìng)爭(zhēng)優(yōu)勢(shì).購(gòu)物籃分析中常用的是Apriori算法，它成功彌補(bǔ)了零售業(yè)數(shù)據(jù)分析不足、有價(jià)知識(shí)提取匱乏的問(wèn)題，在商家積累的海量數(shù)據(jù)中，例如零售業(yè)數(shù)據(jù)，其中的知識(shí)若經(jīng)Apriori算法有效分析提煉，可以充分提升商家銷(xiāo)售業(yè)績(jī).本文對(duì)于Apriori算法原有的支持度和置信度的運(yùn)算進(jìn)行了相關(guān)調(diào)整，設(shè)計(jì)了新的基于利潤(rùn)加權(quán)約束的加權(quán)支持度和加權(quán)置信度求取方法，并以此為基礎(chǔ)對(duì)Apriori算法進(jìn)行改進(jìn).

1 Apriori算法

Apriori作為一種有特色的傳統(tǒng)算法，根據(jù)循序漸進(jìn)的方式，利用數(shù)據(jù)庫(kù)找尋各項(xiàng)之間的聯(lián)系，并組成關(guān)聯(lián)規(guī)則.它的核心是挖掘穎繁項(xiàng)集，輸入minsupport，指導(dǎo)頻率的閾值，如minsupport＝5%表示用戶(hù)（超市商家）是對(duì)數(shù)據(jù)庫(kù)中事務(wù)數(shù)據(jù)概率大于5%的子集感興趣.

Apriori算法輸入最小支持度minsupport后，利用數(shù)據(jù)庫(kù)提取出所有產(chǎn)品交易信息，并獲得Candidate 1－itemset.隨后就可以找到Large 1－itemset，此時(shí)將各個(gè)Large 1－itemset連接形成Candidate 2－itemset.當(dāng)候選2項(xiàng)集中的某一項(xiàng)的支持度≥minsupport，則這個(gè)候選項(xiàng)就劃入到高頻項(xiàng)集.

以此類(lèi)推，已建立的2項(xiàng)集為基礎(chǔ)，再找出所有的高頻2項(xiàng)集.然后，進(jìn)一步利用提取出的高頻2項(xiàng)集，三三組合，生成候選3項(xiàng)集.重復(fù)高頻2項(xiàng)集的搜索方法，與minsupport作比較，提取大于minsupport的3項(xiàng)集構(gòu)成高頻3項(xiàng)集.以此類(lèi)推，直到達(dá)到用戶(hù)的目標(biāo)為止.

2 利潤(rùn)的約束關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘

Apriori算法是一種比較有效的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法，但它以數(shù)據(jù)庫(kù)中所有項(xiàng)在挖掘時(shí)都是等價(jià)的為前提，即權(quán)值都為1、所有項(xiàng)的重要程度都一樣.但在現(xiàn)實(shí)世界中，數(shù)據(jù)庫(kù)中的每一項(xiàng)都是一種商品，它們的重要形式不同的.最直接的就是不同的商品帶給超市的利潤(rùn)是不同的.若Apriori算法直接進(jìn)行數(shù)據(jù)挖掘，則價(jià)值高的大件商品會(huì)因?yàn)槌霈F(xiàn)頻率?。ㄙ?gòu)買(mǎi)數(shù)量少）被算法認(rèn)為不重要而丟掉，對(duì)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘結(jié)果造成不利影響.

2.1 利潤(rùn)加權(quán)閾值的設(shè)計(jì)

利潤(rùn)是超市經(jīng)營(yíng)決策者所關(guān)心的最重要的問(wèn)題.利潤(rùn)＝商品銷(xiāo)售數(shù)量×商品利潤(rùn)率，記為P，利潤(rùn)P越大，越受到超市的重視.因?yàn)槌兄猩唐蜂N(xiāo)售利潤(rùn)率大多數(shù)情況下是比較固定的，不會(huì)隨著客戶(hù)購(gòu)買(mǎi)商品的多少而變化，所以一種商品的銷(xiāo)售數(shù)量也可通過(guò)利潤(rùn)P的值反映出來(lái).

令項(xiàng)目權(quán)重集為

式中：W為商品的權(quán)重，由一段時(shí)間內(nèi)的商品利潤(rùn)計(jì)算得到.商品利潤(rùn)建立的權(quán)重，如表1所示.

表1 權(quán)重對(duì)照表Tab.1 Weight comparison table

2.2 歸一化處理項(xiàng)目權(quán)重集

對(duì)于MINWAL（O）算法可能存在加權(quán)支持度大于1的情況，對(duì)權(quán)重集合W＝｛W1，W2，…，Wj，…，Wm｝實(shí)施歸一化處理.

原來(lái)的權(quán)重集W可以用歸一化權(quán)重集代替.為了表示方便，歸一化的項(xiàng)目權(quán)重集依舊用W表示，即

式中：W1＋W2＋…＋Wj＋…＋Wm＝1.

2.3 布爾向量的獲取

重新統(tǒng)一統(tǒng)計(jì)超市信息庫(kù)的原始交易記錄，交易記錄如表2所示.在購(gòu)物籃分析的傳統(tǒng)方法中，僅是根據(jù)購(gòu)買(mǎi)與否進(jìn)行“1”和“0”狀態(tài)的歸一化處理.即對(duì)于在超市記錄的某種商品銷(xiāo)售數(shù)據(jù)中，若客戶(hù)購(gòu)買(mǎi)，記為“1”；若無(wú)購(gòu)買(mǎi)，則記為“0”.原始記錄依照此方法獲得的布爾向量，如表3所示.

表2 超市商品的交易記錄Tab.2 Trading recordings of supermarket goods

表3 傳統(tǒng)的布爾向量Tab.3 Traditional boolean vector

上述處理過(guò)程的缺點(diǎn)是沒(méi)有考慮每件商品的購(gòu)買(mǎi)數(shù)量，認(rèn)為大批量銷(xiāo)售和單件銷(xiāo)售的影響是一樣的，將銷(xiāo)售100件和1件等同處理.依照這種方式獲得的布爾類(lèi)型數(shù)據(jù)，準(zhǔn)確度值得商榷，獲得的知識(shí)有可能存在大量失真.首先，將某樣產(chǎn)品每一次的交易量除以在銷(xiāo)售中最多賣(mài)出的數(shù)量，如表2中商品1，4次交易中最大的銷(xiāo)售數(shù)量是93件，則商品1的各條記錄中在銷(xiāo)售數(shù)量的字段都除以數(shù)值93，可得到新的4次交易數(shù)值為0.88，0，0.16，1.00.按照此方式，對(duì)表1中的權(quán)重?cái)?shù)據(jù)利用式（1）實(shí)施處理，數(shù)據(jù)統(tǒng)計(jì)后的結(jié)果，如表4所示.表4中：最后一行數(shù)據(jù)是新得出的.

當(dāng)某項(xiàng)目（某種商品）歸一化后，若其數(shù)值大于或等于該商品的利潤(rùn)加權(quán)閾值，布爾值轉(zhuǎn)換表中的對(duì)應(yīng)位置結(jié)果記為“1”，以次標(biāo)識(shí)用戶(hù)對(duì)該商品感興趣，以此作為后續(xù)挖掘關(guān)聯(lián)規(guī)則數(shù)據(jù)的屬性；若數(shù)值小于利潤(rùn)加權(quán)閾值時(shí)，布爾值轉(zhuǎn)換結(jié)果記為“0”，作為后續(xù)挖掘關(guān)聯(lián)規(guī)則數(shù)據(jù)的屬性.根據(jù)這種規(guī)則，以商品1為例，它的權(quán)重W1等于0.4.因此，表4中商品1的交易號(hào)1的第1行記錄是0.881 7（＞0.400 0），布爾變量取值為1；而交易號(hào)2，3記錄的值分別為0和0.161 3，它們都小于0.400 0，對(duì)應(yīng)的布爾變量都取值為0；交易號(hào)4的記錄大于權(quán)重，以此布爾變量取值為1.依此類(lèi)推，對(duì)表4中的數(shù)據(jù)實(shí)施布爾向量化，可以得到通過(guò)利潤(rùn)加權(quán)閾值處理后的布爾記錄表，如表5所示.相比較于表3，可見(jiàn)表5的記錄更加簡(jiǎn)化.

表4 歸一化后的商品交易記錄Tab.4 Commodity trading records after normalization

表5 利潤(rùn)加權(quán)處理后的布爾向量Tab.5 Weight processing of Boolean vector

2.4 加權(quán)支持度和加權(quán)置信度

由于每個(gè)領(lǐng)域工程都已經(jīng)有權(quán)重?cái)?shù)據(jù)，Apriori算法中的運(yùn)算需要進(jìn)行改進(jìn)，通過(guò)重新定義來(lái)滿(mǎn)足需要.以利潤(rùn)加權(quán)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘中的加權(quán)支持度和加權(quán)置信度為基礎(chǔ).令數(shù)據(jù)庫(kù)中項(xiàng)目集X的交易記錄中的數(shù)量集合為S（X），交易總數(shù)取值為n.

對(duì)于項(xiàng)目集X｛x1，…，xp｝，其加權(quán)支持度定義為

將最小加權(quán)支持度（Wminsupport）設(shè)定成用戶(hù)設(shè)定的原始最小加權(quán)支持度，假設(shè)計(jì)算出的加權(quán)支持度Wsup（X）≥Wminsupport，則算法稱(chēng)X是“加權(quán)大項(xiàng)集”.

3 算法設(shè)計(jì)

對(duì)于Apriori算法，若求取高頻項(xiàng)集時(shí)，它的全部子集都屬于高頻項(xiàng)集；但是若項(xiàng)目添加了權(quán)重信息，上述的性質(zhì)不再有效，大項(xiàng)集的某些子集可能并不屬于大項(xiàng)集.

3.1 算法描述

算法的輸入：數(shù)據(jù)庫(kù)D，每個(gè)商品項(xiàng)目的權(quán)重Wm，用戶(hù)設(shè)定的Wminsupport，用戶(hù)設(shè)定的最小加權(quán)置信度（Wminconf）.

步驟1將各項(xiàng)目權(quán)重排除在外，基于布爾型關(guān)聯(lián)規(guī)則挖掘技術(shù)確定高頻項(xiàng)集，當(dāng)項(xiàng)集的支持度大于或等于Wminsupport時(shí)，提取出該項(xiàng)集.如果一種商品十分受歡迎，數(shù)據(jù)挖掘過(guò)程中，加權(quán)的作用是突出更加它的受歡迎程度，即加權(quán)高頻項(xiàng)集是包含在這些未加權(quán)處理的項(xiàng)集的子集中，該項(xiàng)集就是加權(quán)高頻項(xiàng)集的超集.

步驟2對(duì)超集中包含的所有項(xiàng)集實(shí)施挖掘，求出每個(gè)超集中每個(gè)項(xiàng)集的加權(quán)支持度，把大于或等于（Wminconf）的項(xiàng)集取出作為加權(quán)大項(xiàng)集；對(duì)去除項(xiàng)集后的超集繼續(xù)掃描，直至找出超集中的所有的加權(quán)大項(xiàng)集.在第二步數(shù)據(jù)挖掘中，因?yàn)榧訖?quán)高頻項(xiàng)集包含在這些未加權(quán)項(xiàng)集的子集中，因此，無(wú)需再次掃描超市的商品交易數(shù)據(jù)庫(kù)，只需超集乘上每項(xiàng)所對(duì)應(yīng)的項(xiàng)集權(quán)重即可.

步驟3基于加權(quán)大項(xiàng)集改良形成加權(quán)關(guān)聯(lián)規(guī)則.最大的改良之處在于經(jīng)過(guò)加權(quán)處理后提取出的加權(quán)大項(xiàng)集形式未發(fā)生改變，因此，可以使用布爾型關(guān)聯(lián)規(guī)則產(chǎn)生加權(quán)大項(xiàng)集的關(guān)聯(lián)規(guī)則.

輸出：超市商品的加權(quán)關(guān)聯(lián)規(guī)則.

3.2 算法的數(shù)據(jù)挖掘流程

B為數(shù)據(jù)庫(kù)，Lk是高頻k的項(xiàng)集，Ck是候選k項(xiàng)集，T臨時(shí)項(xiàng)集，項(xiàng)目的權(quán)值屬性定義為W＝｛W1，W2，…，Wj，…，Wm｝.算法的運(yùn)行過(guò)程為

定理1 設(shè)X為項(xiàng)集，C1和C2分別為單調(diào)性約束和非單調(diào)性約束.

1）如果C1（X）＝不正確，那么?Y?X，C1（Y）∧C2（Y）＝不正確，即X的任何子集都不同時(shí)滿(mǎn)足C1和C2；

2）如果C1（X）＝正確，C2（X）＝正確，則存在Y?X，使得C1（Y）∧C2（Y）＝正確；

3）如果C1（X）＝正確，C2（X）＝不正確，則存在Y?X，使得C1（Y）∧C2（Y）＝正確.

證明 如果C1（X）＝不正確，很顯然有?Y?X.根據(jù)單調(diào)約束的性質(zhì)，C1（Y）＝不正確，于是不管C2（Y）的值如何，C1（Y）∧C2（Y）＝不正確.

4 試驗(yàn)結(jié)果分析

關(guān)聯(lián)規(guī)則挖掘的目標(biāo)是挖掘出暗含在數(shù)據(jù)庫(kù)中的知識(shí)，為了測(cè)試基于利潤(rùn)的約束的關(guān)聯(lián)規(guī)則挖掘算法的特性，選用了將其他算法與Apriori算法進(jìn)行比較，如圖1所示.圖1中：縱坐標(biāo)是數(shù)據(jù)挖掘獲取的高頻項(xiàng)集；橫坐標(biāo)是不同的最小支持度的取值.對(duì)于各個(gè)不同的最下支持度，每個(gè)橫坐標(biāo)點(diǎn)左邊柱體是Apriori算法數(shù)據(jù)挖掘所算出的最有意義的項(xiàng)目，右邊柱體是算法在該的最小支持度下挖掘出的有效項(xiàng)集數(shù)量.由圖1可知：其他算法（右邊柱體）和Apriori算法（左邊柱體）直接按對(duì)比明顯，提取出的有價(jià)值項(xiàng)集數(shù)目精簡(jiǎn)明顯.

假設(shè)非單調(diào)性約束C1：max（S.cost）≤min（S.price）；單調(diào)性約束C2：total（S.price）≥100；最小支持度為20%（表1）.

1）求出數(shù)據(jù)庫(kù)頻繁1項(xiàng)集（按支持度由大到小排列）：D，E，B，A，C.

2）C2（DEBAC）＝不正確，得出N值至少大于等于2.

3）C1（D）＝正確，C1（E）＝正確，C1（B）＝正確，C1（A）＝正確，C1（C）＝正確.

以A為例，D的支持度最大，沒(méi)有必要生成D的條件數(shù)據(jù)庫(kù)，因?yàn)樗闹С侄茸畲?，已?jīng)沒(méi)有前綴項(xiàng)了.

4）求出A的條件數(shù)據(jù)庫(kù)，其投影事務(wù)在原數(shù)據(jù)庫(kù)中分別為（項(xiàng)按支持度由大到小排列）：｛DEB，DB，E，DE，DEB｝.

5）求出頻繁1項(xiàng)集：D，E，B.由于DEBA為4項(xiàng)，大于N的值，因此，后面考慮繼續(xù)生成各項(xiàng)的條件數(shù)據(jù)庫(kù).

6）C1（DEBA）＝不正確；C1（DA）＝正確；C1（EA）＝正確；C1（BA）＝不正確.

7）由于DEA的子集除了DEA是3項(xiàng)外，其余為≤2，經(jīng)檢查，均不滿(mǎn)足C2，最后輸出滿(mǎn)足C1∧C2的A的條件數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集為DEA.

圖1 算法比較Fig.1 Algorithm comparison

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

針對(duì)Apriori算法在實(shí)際應(yīng)用中的不足，設(shè)計(jì)了基于利潤(rùn)的約束關(guān)聯(lián)規(guī)則挖掘算法，對(duì)數(shù)據(jù)庫(kù)的原始數(shù)據(jù)實(shí)施了利潤(rùn)約束修正，增加了利潤(rùn)加權(quán)閾值，有效提升數(shù)據(jù)挖掘算法的知識(shí)挖掘性能.到目前為止，大部分算法還只是一種挖掘，所以其算法還是不夠完善，而新算法不但能進(jìn)行約束的挖掘，還能進(jìn)行另一種算法，分別是單調(diào)性和非單調(diào)性.

［1］HAN Jia－wei，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機(jī)械工業(yè)出版社，2001：132－156.

［2］陳奇，俞瑞釗.關(guān)聯(lián)規(guī)則采掘綜述［J］.計(jì)算機(jī)應(yīng)用研究，2000，17（1）：1－5.

［3］李興良，陳湘濤.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究［J］.計(jì)算機(jī)工程與科學(xué)，2007（12）：111－116.

［4］MICHAEL J A B，GORDON S L.數(shù)據(jù)挖掘：客戶(hù)關(guān)系管理科學(xué)與藝術(shù)［M］.北京：中國(guó)財(cái)政經(jīng)濟(jì)出版社，2004：10－52.

［5］黃健斌.基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測(cè)技術(shù)研究［D］.重慶：重慶大學(xué)，2007：13－19.

［6］王德興，胡剛，劉小平.基于概念和Apriori的關(guān)聯(lián)規(guī)則挖掘算法分析［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，29（6）：69－702.

［7］杜海濤，陳定方，張波.基于關(guān)聯(lián)規(guī)則的超市購(gòu)物籃分析方［J］.湖北工業(yè)大學(xué)學(xué)報(bào)，2008，23（4）：15－18.

［8］薛紅，聶桂華.基于關(guān)聯(lián)規(guī)則分析的購(gòu)物籃分析模型研究［J］.北京工商大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，23（4）：15－18.

［9］黃嘉滿(mǎn).面向零售業(yè)的關(guān)聯(lián)規(guī)則挖掘的研究與實(shí)現(xiàn)［D］.上海：上海交通大學(xué)，2007：4－45.

［10］馮瑤.基于零售業(yè)的數(shù)據(jù)挖掘技術(shù)和關(guān)聯(lián)規(guī)則算法的改進(jìn)研究［D］.天津：河北工業(yè)大學(xué)，2006：31－43.

［11］謝小蘭.應(yīng)用數(shù)據(jù)挖掘技術(shù)提高決策能力的研究［J］.商情，2011（47）：139－142.

［12］張文獻(xiàn)，陸建江.加權(quán)布爾關(guān)聯(lián)規(guī)則的研究［J］.計(jì)算機(jī)工程，2003，29（9）：55－57.