張文斌，明 勇，褚維偉，黃哲學(xué)

(深圳大學(xué)，廣東 深圳 518000)

0 引 言

購物籃分析對零售業(yè)是非常重要的技術(shù)分析，尤其近年來網(wǎng)絡(luò)零售的突飛猛進(jìn)，產(chǎn)生了海量的交易數(shù)據(jù)，從而對購物籃分析提出了更高的要求。購物籃分析可以為超市和網(wǎng)絡(luò)商城中的各種促銷提供參考，去庫存，商品布局優(yōu)化。購物籃分析能為決策者提供快速、準(zhǔn)確、節(jié)約、多元的信息參考。提高零售產(chǎn)業(yè)綜合效益、提高國際競爭力、建設(shè)節(jié)約型社會購物籃分析都有重要的宏觀意義[1]。

但是在傳統(tǒng)的購物籃分析中，得出的結(jié)果通常是一些常規(guī)商品的組合。這些組合的購物籃支持度很高，但是它們已經(jīng)被大家所認(rèn)知，對企業(yè)的價值和意義不大。此外，傳統(tǒng)購物籃分析一個很大的局限性在于它并不能預(yù)測，通常只對歷史數(shù)據(jù)進(jìn)行分析，而不是對購物籃按時間的序列做出演化和預(yù)測。往往精準(zhǔn)的預(yù)測能給企業(yè)帶來很大的利益，也能提高對風(fēng)險的控制。還有，傳統(tǒng)的購物籃分析只給出比較簡單的結(jié)果，沒有實現(xiàn)數(shù)據(jù)可視化。一幅圖勝過千言萬語，人類對外界過多的信息約有80%以上來自于視覺系統(tǒng)，當(dāng)大數(shù)據(jù)以直觀可視化的圖形形式展示在分析者面前時，分析者往往能夠一眼洞悉數(shù)據(jù)背后隱藏的信息并轉(zhuǎn)化為知識以及智慧。購物籃可視化結(jié)果實現(xiàn)友好人機(jī)交互界面就需要研究數(shù)據(jù)可視化，同時，大數(shù)據(jù)本身的新特點也對可視化提出了更為迫切的需求。

針對購物籃分析的現(xiàn)狀，結(jié)合企業(yè)實際應(yīng)用中的需求，在購物籃壓縮研究分析的基礎(chǔ)上,設(shè)計并建立了購物籃可視化系統(tǒng)。其中,通過購物籃壓縮來壓縮并篩選更有價值的購物籃，購物籃可視化讓購物籃分析結(jié)果實現(xiàn)友好的人機(jī)交互界面及可視化[2]。

1 購物籃重組分析

通常說的購物籃分析指的是通過購物籃中顯示出來的交易信息來分析顧客的購買行為，顧客在購買商品的過程中通常會一次購買多個商品，從而使得這些商品之間具有很強(qiáng)的關(guān)聯(lián)性。因此，可以認(rèn)為顧客的購買行為是一種整體的行為，是否購買一件商品會影響到其他商品的購買，從而影響到每個購物籃的利潤。所以，購物籃分析的目標(biāo)就是找出重要且有價值的購物籃[3]。

關(guān)聯(lián)規(guī)則挖掘是購物籃數(shù)據(jù)挖掘最經(jīng)典的應(yīng)用之一，用來從大量的數(shù)據(jù)中挖掘出一些令人感興趣的規(guī)則，分析產(chǎn)品之間的關(guān)聯(lián)性，從而指導(dǎo)人們做出一些有利的決策和安排。例如在超市中將啤酒和尿布放在一起會增加啤酒的銷量等。

關(guān)聯(lián)規(guī)則挖掘問題最早是在1993年由AGRAWAL等提出的，主要是為了幫助零售企業(yè)分析交易數(shù)據(jù)，對一些商業(yè)決策提供支持，如怎樣制定促銷方案，怎樣擺放商品來提升銷售業(yè)績，怎樣決定供貨數(shù)量來減少庫存，等等。他們認(rèn)為，關(guān)聯(lián)規(guī)則挖掘問題主要通過兩部分來解決，即先挖掘出大項集集合，再從大項集集合中挖掘出關(guān)聯(lián)規(guī)則。同時提出了語法約束和支持度約束的概念，并且提出了AIS算法來生成大項集集合[4]。

關(guān)聯(lián)規(guī)則挖掘問題可以表述為：設(shè)I=[i1,i2,…,in]是所有項目的集合，即所有商品類別的集合；D=[T1,T2,…,Tn]是所有事務(wù)的集合，即所有交易記錄的集合。事務(wù)T可以表示為：T=[TID,]，其中TID是事務(wù)T在D中的唯一標(biāo)識，i1,i2,…,in?I(1≤n≤m)是事務(wù)T的項目集合。一個關(guān)聯(lián)規(guī)則表示為：X→Y，其中X?I，Y?I且X∩Y=?。X和Y都是項目的集合，稱之為項集。設(shè)X是一個項集，那么當(dāng)且僅當(dāng)X?T時，事務(wù)T包含項目集X。支持度和置信度都是表示關(guān)聯(lián)規(guī)則強(qiáng)度的最常用的指標(biāo)[5]。

2 購物籃聚類分析

2.1 購物籃聚類的意義

購物籃分析在實際場景中應(yīng)用時往往得出的是數(shù)以千計的購物籃，企業(yè)很難從這數(shù)量繁多的購物籃中找出真正感興趣的、對自己有價值的部分。購物籃分析中最經(jīng)典的案例莫過于“啤酒和尿布”了，可是這之后就很少有類似的購物籃分析結(jié)果了。購物籃數(shù)量的問題給購物籃分析的應(yīng)用造成了很大的阻礙。為了解決這個問題，自然而然就會想到去壓縮這些數(shù)量龐大的購物籃，例如，用一種簡潔的表達(dá)來描述一類購物籃。對購物籃通過聚類進(jìn)行壓縮，再從聚類結(jié)果中找出代表性的購物籃，從而大大減少購物籃數(shù)量[5]。

2.2 購物籃聚類算法

K-Means算法是基于劃分的聚類算法，簡潔易懂且有較高的效率，因此應(yīng)用十分廣泛。用戶給定一個期望得到的聚類數(shù)k，K-Means算法就可以通過某種距離函數(shù)反復(fù)地把數(shù)據(jù)集中的點分到這k個類中，直到滿足某個終止條件。

設(shè)數(shù)據(jù)點的集合為X=[x1,x2,…,xn]，其中xi=[xi1,xi2,…,xir]為r維向量，K-Means算法將把給定的數(shù)據(jù)集劃分成r類，每個類有一個聚類中心。聚類中心為這個類中所有點的均值，通常用聚類中心來表示這個類。K-Means聚類算法描述如下：

輸入：數(shù)據(jù)集D，聚類個數(shù)k

輸出：k個類

步驟：

選擇k個數(shù)據(jù)點作為原始聚類中心

repeat

for each data pointx?Ddo

compute the distance fromxto each centroid

計算x到每個聚類中心點的距離

assignxto the closest centroid //將x分配到距離最近的類中

endfor

re-compute the centroid //重新計算每個類中的聚類中心點

until the stopping criterion is met

首先從數(shù)據(jù)集中隨機(jī)抽取k個點作為原始聚類中心，然后計算每個數(shù)據(jù)點到這k個聚類中心的距離，并根據(jù)這個距離值將每個數(shù)據(jù)點分到最近的聚類中心，當(dāng)分配完所有的數(shù)據(jù)點之后，重新計算每個類中的聚類中心。不斷重復(fù)這一過程直到滿足某個終止條件。終止條件為以下三個中的任何一個：

(1)沒有(或最小數(shù)目)數(shù)據(jù)點被重新分配給不同的類；

(2)沒有(或最小數(shù)目)聚類中心發(fā)生變化；

(3)誤差平方和局部最小。

(1)

均值為使得簇的誤差平方和最小的質(zhì)心，即：

(2)

其中，k為用戶設(shè)定的聚類簇個數(shù)；x為對象；Ci為第i個簇；ci為第i個簇的質(zhì)心；dist(x,ci)為數(shù)據(jù)點x到簇中心ci的距離；mi為第i個簇中包含的數(shù)據(jù)點個數(shù)。

證明過程如下：

對于一維數(shù)據(jù)，式(1)可以寫成：

(3)

其中，Ci表示第i個簇；x表示Ci中的點；ci表示簇Ci的均值。

然后求解第k個質(zhì)心ck，最小化式(3)，也就是對SSE求偏導(dǎo)數(shù)，令偏導(dǎo)數(shù)為0，再求解ck。

(4)

(5)

因此，簇中各點的均值是簇的最小化誤差平方和的最優(yōu)質(zhì)心。

K-Means算法雖然簡潔易懂、效率較高，但是實際應(yīng)用中也有很多不足之處。這里運用K-Means算法進(jìn)行購物籃聚類存在的問題主要為用戶需要指定聚類數(shù)目k，這個k值的選定是非常難以估計的。很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。若k值設(shè)置過大，會導(dǎo)致聚類數(shù)目過多，達(dá)不到壓縮購物籃集合的目的；若k值設(shè)置過小，會導(dǎo)致聚類結(jié)果過于粗糙，不夠準(zhǔn)確[6-7]。

3 購物籃壓縮方法

購物籃集合壓縮方法與代表模式方法類似，也是通過聚類實現(xiàn)的。不同的是，聚類的對象不再是購物籃表達(dá)式本身，而是由一系列特征屬性表示的購物籃[8]。

3.1 數(shù)據(jù)預(yù)處理及屬性構(gòu)造

在數(shù)據(jù)挖掘的整體過程中，海量的原始數(shù)據(jù)中存在著大量雜亂的、重復(fù)的、不完整的數(shù)據(jù)，嚴(yán)重影響了數(shù)據(jù)挖掘算法的執(zhí)行效率，甚至可能導(dǎo)致挖掘結(jié)果的偏差[9]。為此，在數(shù)據(jù)挖掘算法執(zhí)行之前，必須對收集的原始數(shù)據(jù)進(jìn)行預(yù)處理，以改進(jìn)數(shù)據(jù)的質(zhì)量，提高數(shù)據(jù)挖掘過程的效率、精度和性能。數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)交換與數(shù)據(jù)歸約等[10]。

數(shù)據(jù)預(yù)處理可以補(bǔ)全殘缺的數(shù)據(jù)，糾正錯誤的數(shù)據(jù)，刪除多余的數(shù)據(jù)，篩選出所需的數(shù)據(jù)并進(jìn)行數(shù)據(jù)的集成操作，轉(zhuǎn)化數(shù)據(jù)為需要的格式，從而實現(xiàn)數(shù)據(jù)類型的相同化、數(shù)據(jù)格式的一致化、數(shù)據(jù)信息的精練化以及數(shù)據(jù)存儲的集中化[11]。通過數(shù)據(jù)預(yù)處理后，可以得到數(shù)據(jù)挖掘所需要的數(shù)據(jù)集，從而使數(shù)據(jù)挖掘具有可行性；同時也可以在一定程度上減少進(jìn)行挖掘所需付出的代價，提高挖掘結(jié)果的可理解性與有效性[12]。

為了對上面得出的購物籃進(jìn)行聚類以達(dá)到壓縮購物籃集合的目的，首先對購物籃進(jìn)行屬性構(gòu)造。通過對交易數(shù)據(jù)的仔細(xì)分析與深入理解，首先對每個購物籃構(gòu)造了13個屬性。

另一方面，有的購物籃具有較強(qiáng)的時間特征，會受到季節(jié)、節(jié)假日等時間因素的影響。基于此，將用于產(chǎn)生購物籃的原始交易數(shù)據(jù)按月分割，計算每個購物籃在每個月中這13個屬性的值。這樣得到的購物籃屬性就形成了一個12個月的時間序列，其中每個月都有13個屬性，最后每個購物籃共有156個屬性。在構(gòu)造完這些屬性之后，發(fā)現(xiàn)像支持度和銷售額占比這些屬性值都非常小。而在聚類的過程中，如果屬性值太小，在計算距離時權(quán)重就很小，近似為0，對聚類結(jié)果影響較大。因此，在聚類之前還要進(jìn)行屬性值的正規(guī)化操作，將所有屬性值都映射到[0,1]區(qū)間[13]。

3.2 購物籃壓縮算法

針對K-Means算法應(yīng)用在購物籃集合壓縮中的不足之處，結(jié)合基于劃分和基于層次的聚類方法，提出一種基于K-Means的層次聚類算法。算法詳細(xì)描述如下：

(1)將原始數(shù)據(jù)集D用K-Means()算法分裂成k個子聚類；

(2)分別對上一次聚類產(chǎn)生的所有子聚類運行K-Means()算法；

(3)重復(fù)第2步，直到滿足終止條件。

算法的主要思想是自上而下的分裂聚類。聚類過程從整個數(shù)據(jù)集的聚類(根)開始，根據(jù)用戶指定的k值，運用K-Means算法將根節(jié)點聚類分裂成k個子聚類。每個子聚類再遞歸地繼續(xù)往下分裂直到滿足某個終止條件。終止條件為以下任何一個：

(1)所有的葉節(jié)點中數(shù)據(jù)點的個數(shù)都小于k；

(2)沒有葉子節(jié)點再分裂成子聚類。

圖1為聚類結(jié)果示例，聚類結(jié)果為一棵聚類樹。樹的葉子節(jié)點有5個聚類(5個數(shù)據(jù)點)，在上一層中，聚類4包含葉子節(jié)點5和6，聚類3包含葉子節(jié)點8和9。用到的結(jié)果只需要最底層的葉子節(jié)點的聚類信息，即5和6為一個聚類，7為一個聚類，8和9為一個聚類[14]。

圖1 聚類結(jié)果示例

通過上文所述的聚類方法，將購物籃集合劃分成n個聚類。接下來從每個聚類中找出一個購物籃來表示這個聚類中的所有購物籃，這樣就將原始的購物籃集合壓縮成n個購物籃。在每個聚類中，根據(jù)購物籃中商品出現(xiàn)的頻次來構(gòu)造代表購物籃。

4 實驗結(jié)果分析

為了檢驗購物籃聚類方法在實際應(yīng)用中的效果，采用購物籃集合作為輸入數(shù)據(jù)對效果和性能進(jìn)行驗證。輸入數(shù)據(jù)為500個購物籃，并按3.1的方法進(jìn)行了數(shù)據(jù)預(yù)處理和屬性構(gòu)造，這樣每個購物籃為一個聚類對象，有156個特征屬性。通過文中提出的購物籃聚類方法，將500個購物籃劃分成了50個類，在每個類中找出一個代表購物籃，從而實現(xiàn)了購物籃壓縮。下面首先對聚類效果進(jìn)行評估與分析。

圖2為聚類結(jié)果中每個聚類中的點到聚類中心的距離分布圖，用來評估聚類結(jié)果中的類內(nèi)是否緊密。

從圖中可以看出，聚類中點到聚類中心的距離主要集中分布在0.05到0.2之間，其中距離在0.1至0.15之間點的占比達(dá)到50%以上。圖1表明聚類結(jié)果中每個聚類比較緊湊，聚類效果較好，達(dá)到了使相同類中樣本盡可能相似的目的。

采用雷達(dá)圖的形式來對比購物籃聚類前后的差別。圖3為購物籃聚類之前的購物籃數(shù)據(jù)雷達(dá)圖，這里考慮到購物籃在不同月份的表現(xiàn)具有較大差異，將購物籃屬性按月劃分，由每個月的購物籃數(shù)據(jù)得到一張雷達(dá)圖。其中每個月份的雷達(dá)圖有13個頂點，代表3.1中構(gòu)造的13個基本屬性，通過觀察每個雷達(dá)圖的形狀就可以判斷購物籃的分布情況。如果雷達(dá)圖中購物籃的軌跡比較雜亂、分散，則說明購物籃集合差異性較大。反之，如果雷達(dá)圖中購物籃形成的軌跡具有明顯的相似性，則說明這些購物籃具有很強(qiáng)的共性。由圖3可以看出，購物籃聚類前較為分散，沒有什么規(guī)律性。

圖4為聚類結(jié)果中聚類中心點間距離分布直方圖，用來評估聚類結(jié)果中類間是否遠(yuǎn)離。由圖中可以看出，聚類中心點間的距離主要分布在0.2至0.4之間，占比達(dá)到60%以上。而由圖2可知，每個聚類中點到聚類中心的距離主要分布在0.05到0.2之間，對比實驗結(jié)果可表明聚類結(jié)果中不同類間較為分散。

圖4 聚類中心點間距離分布直方圖

由以上兩個實驗，可以得出所提出的購物籃聚類算法滿足類內(nèi)緊密、類間遠(yuǎn)離的聚類有效性評估標(biāo)準(zhǔn)，有較好的聚類效果。

(a)聚類1的購物籃數(shù)據(jù)雷達(dá)圖

(b)聚類2的購物籃數(shù)據(jù)雷達(dá)圖

在實驗得到的50個聚類中，選擇兩個作為購物籃聚類結(jié)果示例。由圖5可以看出，每個聚類中的12張雷達(dá)圖形狀非常相似，每張雷達(dá)圖中的購物籃軌跡也基本重疊，有明顯的相似性。通過對比可以看出，聚類后同一個類中的購物籃具有較高的相似度，說明提出的購物籃聚類方法具有較好的聚類效果。

下面對從聚類結(jié)果中選擇代表購物籃進(jìn)行評估與分析，以代表購物籃中的商品在類中出現(xiàn)的頻次占比作為評估代表購物籃的標(biāo)準(zhǔn)，顯然占比越高則說明選擇的購物籃越有代表性。圖6為代表購物籃中商品在類中出現(xiàn)的頻次占比分布直方圖。

圖6 代表購物籃中商品在類中出現(xiàn)的頻次占比

由圖6可以看出，這一占比值普遍較高，都在50%以上，主要分布在60%至80%之間，表明所采用方法具有較高的有效性與實用價值。

根據(jù)算法描述以及實驗結(jié)果，可以總結(jié)出文中提出的購物籃壓縮方法具有以下優(yōu)點：

(1)結(jié)合基于劃分和基于層次的聚類方法，提出基于K-Means的層次聚類算法。算法簡單高效，不用人工輸入k值，避免了因k值設(shè)置不當(dāng)導(dǎo)致的聚類效果不理想。

(2)根據(jù)聚類中商品出現(xiàn)的頻次來構(gòu)造代表購物籃，保留了聚類中影響最大的商品，具有較高的代表性與有效性。

5 結(jié)束語

購物籃數(shù)量過多是購物籃分析在實際應(yīng)用中不可避免的問題，而傳統(tǒng)的壓縮方法中關(guān)注的對象都是購物籃表達(dá)式本身，效果并不是很理想。文中提出的購物籃壓縮方法為每個購物籃構(gòu)造了具有時間序列特征的屬性，然后根據(jù)這些屬性值對購物籃進(jìn)行聚類，再從聚類結(jié)果中挑選出代表購物籃，從而達(dá)到了壓縮購物籃集合的效果。

[1] 余 穎.購物籃分析在網(wǎng)絡(luò)零售業(yè)中的應(yīng)用研究[D].天津:天津大學(xué),2007.

[2] 褚維偉,張文斌,陳小軍,等.一種帶約束條件的購物籃分析方法[J].計算機(jī)技術(shù)與發(fā)展,2016,26(8):69-74.

[3] DIPPOLD K,HRUSCHKA H.Variable selection for market basket analysis[J].Computational Statistics,2013,28(2):519-539.

[4] 黃 鶴.關(guān)聯(lián)規(guī)則算法綜述[J].軟件導(dǎo)刊,2009,8(3):56-57.

[5] 羅 芳.基于聚類和壓縮矩陣的加權(quán)關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用[D].上海:華東師范大學(xué),2010.

[6] 高 瀅,劉大有,齊 紅,等.一種半監(jiān)督K均值多關(guān)系數(shù)據(jù)聚類算法[J].軟件學(xué)報,2008,19(11):2814-2821.

[7] RUPALI S,SHAH T,CHAVAN T,et al.Survey on implementation of market basket analysis using Hadoop framework[J].International Journal of Computer Applications,2016,134(10):6-9.

[8] SOLNET D,BOZTUG Y, DOLNICAR S. An untapped gold mine? Exploring the potential of market basket analysis to grow hotel revenue[J].International Journal of Hospitality Management,2016,56:119-125.

[9] 張平庸,歐陽為民,萬志華.基于密度的購物籃數(shù)據(jù)聚類方法[J].計算機(jī)工程與設(shè)計,2005,26(1):180-181.

[10] CHEN Y L,TANG K,SHEN R J,et al.Market basket analysis in a multiple store environment[J].Decision Support Systems,2005,40(2):339-354.

[12] KOCSOR A,KERTéSZ-FARKAS A,KAJN L,et al.Application of compression-based distance measures to protein sequence classification:a methodological study[J].Bioinformatics,2006,22(4):407-412.

[13] 李雷定,馬鐵華,尤文斌.常用數(shù)據(jù)無損壓縮算法分析[J].電子設(shè)計工程,2009,17(1):49-50.

[14] 彭喜元,俞 洋.基于變游程編碼的測試數(shù)據(jù)壓縮算法[J].電子學(xué)報,2007,35(2):197-201.