基于聚類算法的購物籃壓縮研究

張文斌，明 勇，褚維偉，黃哲學

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

0 引 言

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

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

針對購物籃分析的現狀，結合企業實際應用中的需求，在購物籃壓縮研究分析的基礎上,設計并建立了購物籃可視化系統。其中,通過購物籃壓縮來壓縮并篩選更有價值的購物籃，購物籃可視化讓購物籃分析結果實現友好的人機交互界面及可視化[2]。

1 購物籃重組分析

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

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

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

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

2 購物籃聚類分析

2.1 購物籃聚類的意義

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

2.2 購物籃聚類算法

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

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

輸入：數據集D，聚類個數k

輸出：k個類

步驟：

選擇k個數據點作為原始聚類中心

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

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

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

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

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

(1)

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

(2)

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

證明過程如下：

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

(3)

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

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

(4)

(5)

因此，簇中各點的均值是簇的最小化誤差平方和的最優質心。

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

3 購物籃壓縮方法

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

3.1 數據預處理及屬性構造

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

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

為了對上面得出的購物籃進行聚類以達到壓縮購物籃集合的目的，首先對購物籃進行屬性構造。通過對交易數據的仔細分析與深入理解，首先對每個購物籃構造了13個屬性。

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

3.2 購物籃壓縮算法

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

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

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

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

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

(1)所有的葉節點中數據點的個數都小于k；

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

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

圖1 聚類結果示例

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

4 實驗結果分析

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

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

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

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

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

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

由以上兩個實驗，可以得出所提出的購物籃聚類算法滿足類內緊密、類間遠離的聚類有效性評估標準，有較好的聚類效果。

(a)聚類1的購物籃數據雷達圖

(b)聚類2的購物籃數據雷達圖

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

下面對從聚類結果中選擇代表購物籃進行評估與分析，以代表購物籃中的商品在類中出現的頻次占比作為評估代表購物籃的標準，顯然占比越高則說明選擇的購物籃越有代表性。圖6為代表購物籃中商品在類中出現的頻次占比分布直方圖。

圖6 代表購物籃中商品在類中出現的頻次占比

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

根據算法描述以及實驗結果，可以總結出文中提出的購物籃壓縮方法具有以下優點：

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

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

5 結束語

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

[1] 余 穎.購物籃分析在網絡零售業中的應用研究[D].天津:天津大學,2007.

[2] 褚維偉,張文斌,陳小軍,等.一種帶約束條件的購物籃分析方法[J].計算機技術與發展,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] 黃 鶴.關聯規則算法綜述[J].軟件導刊,2009,8(3):56-57.

[5] 羅 芳.基于聚類和壓縮矩陣的加權關聯規則算法的研究與應用[D].上海:華東師范大學,2010.

[6] 高 瀅,劉大有,齊 紅,等.一種半監督K均值多關系數據聚類算法[J].軟件學報,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] 張平庸,歐陽為民,萬志華.基于密度的購物籃數據聚類方法[J].計算機工程與設計,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] 李雷定,馬鐵華,尤文斌.常用數據無損壓縮算法分析[J].電子設計工程,2009,17(1):49-50.

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