客戶導向目錄分割問題的改進算法①

杜萍萍, 陸 可, 吳金南(安徽工業大學 管理科學與工程學院, 馬鞍山4300)(安徽工業大學 商學院, 馬鞍山4300)

客戶導向目錄分割問題的改進算法①

杜萍萍1, 陸 可1, 吳金南21(安徽工業大學 管理科學與工程學院, 馬鞍山243002)2(安徽工業大學 商學院, 馬鞍山243002)

客戶導向目錄分割問題假設顧客至少對目錄中一定數量的商品感興趣, 計算目錄覆蓋的顧客數量, 據此評估目錄分割結果. 現有的分割算法為了保證目錄盡可能多的覆蓋顧客, 而忽略了目錄分割結果的效用. 針對該問題, 本文構建一種新的數據存儲結構CFP-Tree用于存儲顧客交易數據, 并提出一種新的算法Effective-Cover解決目錄分割問題. 該算法使用樹深度遍歷法選擇目錄產品. 實驗結果表明, 該算法能夠獲得更好的目錄分割結果.

目錄分割; CFP-Tree; Effective-Cover算法; 客戶; 商業智能

客戶分類問題[1,2]是一類經典的商業智能優化問題, 客戶分類問題實際也屬于分割問題的一種. 以此為切入點, 近年來, 多種商業智能理論相繼被提出,其中基于微觀經濟學的觀點尤其引人注目[3-5]. 該理論將商業智能視為大量非聚集數據在商業目標驅動下的優化問題, 當企業使用某個模式使得企業效益增加時,該模式被認為有效[5].

簡單地為所有顧客采取同一商業決策不利于利潤最大化. 一個有效的方法是形成k個決策, 使每個決策覆蓋的顧客數量最大化, 從而使企業獲得更多的利潤. Ester研究了微觀經濟學視角下數據挖掘問題的另一個問題[6]: 客戶導向的目錄分割問題. 將顧客劃分成不同的群體, 并制定針對不同顧客群體的商品目錄,使得商品目錄在顧客群體上產生盡可能大的效用. 整體的效用, 由所有目錄所覆蓋的滿足最小興趣度的顧客數量來度量. 在這樣的假設下, 目錄分割問題就演化成加入興趣度約束的目錄分割問題, 也稱為客戶導向目錄分割問題[6].

由于現實生活中數據信息量大, 為了提高算法效率, 需要一個有效的數據結構來存儲數據. Han在研究關聯規則時, 提出了一種新的存儲結構--頻繁模式樹FP-Tree(frequent pattern tree), 取得了顯著的效果[7,8]. Xu構建了一種新的數據結構頻繁模式樹TFP-Tree (frequent pattern tree with T-layer interest constraint)來存儲顧客交易數據, 并在此基礎上提出一種有效的客戶導向目錄分割算法Max-Cover (maximal customer cover catalog segmentation algorithm), 獲得了更好的目錄分割效用[9,10]. Amiri提出了兩種解決客戶導向目錄分割問題的算法[11]. 第一種是貪婪算法, 并利用算法的隨機性避免了局部最優; 第二種是基于關聯規則挖掘的啟發式算法. Iraj將客戶導向目錄分割問題轉化成一種可供替代的方法問題, 提出了一種自適應的遺傳算法解決該問題, 并且有效地避免了局部最優[12].也有一些關于目錄分割問題的算法相繼被提出, 比如最大二等分和不相交的目錄分割問題的改進算法[13].

針對客戶導向目錄分割問題, 本文基于樹結構改進了客戶交易數據的存儲方式, 構建一種新的數據結構CFP-Tree(frequent pattern tree of customer database),改進了樹的遍歷方法, 設計出Effective-Cover(effective customer cover catalog segmentation algorithm)目錄分割算法, 旨在提高生成目錄的整體效用.

1 符號定義與問題描述

1.1 相關符號定義

本文使用二部圖G代表顧客數據庫. 有兩類頂點集合, 一類為顧客集合, 另一類為產品集合, 邊代表相應的顧客對相應的產品感興趣的事實. 假設收集到的顧客數據存儲在顧客數據庫(Customers DB)中. 相關的符號定義包括:

二部圖G=｛P, C, E｝: 有兩個頂點集合P, C和一個邊集E, 使用||表示集合的基數,P=m，C=n，其中:

C={c1, c2,...,ci,...,cn}, 表示所有的顧客;

P={p1, p2,...,pj,...,pm}, 表示所有的產品;

E={eij=(ci, pj)|ci對pj感興趣, ci∈C,pj∈P}對于?P′?P, w( P′)={至少有一條邊連接到p′中的頂點C的顧客集合}.

對于P′?P, t≥1, φ（P′, t）表示至少有t條邊連接到產品集P′中的顧客集C′, 即: φ(P′, t)={C′?C|?ci∈C′,?eij=(ci, pj),eij∈E ′, pj∈P′, P′?P}.

1.2 客戶導向目錄分割問題定義

定義2. 覆蓋. 如果顧客Customeri對目錄Catalogj中至少有一個產品感興趣, 稱該目錄覆蓋了該顧客.

定義3. 最多顧客覆蓋問題. 給出任意的二部圖G=(P, C, E)和一個正整數r, 尋找一個大小為r的子集P′?P使顧客集合w( p′)盡可能大.

定義4. k目錄分割問題. 給出使用二部圖G=(P, C, E)表示的顧客數據庫, 并且|p|=m,| C|=n,求商品集合P的k個子集p1,...,pk,其中|Pi|=r,和對應顧客集合C的k個子集C1,...Ck,使得盡可能

大.

將顧客分成k個群體, 每個顧客最多只能屬于其中一個群體, 每個群體所對應的目錄包含r個產品,而同一產品允許在多個產品目中中同時出現.

定義1至定義4中的目錄分割問題以最大化的覆蓋顧客數量為目的. Ester引入最小興趣度t[6], 即在目錄分割問題中加入興趣度約束, 使發送到顧客的產品目錄至少有興趣度t的顧客數量來評價目錄的整體效用.

定義5. 客戶導向的目錄分割問題. 給出使用二部圖G=(P, C, E)表示的顧客數據庫, |p|=m,| C|=n,制定k個目錄p1,...,pk,其中|Pi|=r,和對應的C的k個子集以C1,...Ck,并且顧客在對應的目錄中至少有t個感興趣的產品, 使得最大.

1.3 CFP-Tree結構定義

考慮到顧客數據庫數據量龐大的問題, 為了提高算法的運行效率, 我們需要建立一個有效的數據結構,同時存儲事務和其對應的顧客信息. 本研究使用樹結構存儲數據, 即興趣度t的約束. 在構建樹時僅構建頂上t層, 假設顧客感興趣的產品中支持度最高的t個產品就可覆蓋其基本需求. 將顧客對應的感興趣產品按支持度降序排列, 并取前t個插入樹中. 使用本文提出的CFP-Tree結構存儲數據, 將每條交易對應的顧客信息存入表中. CFP-Tree每個樹枝末尾加入顧客信息, 如圖1所示.

圖1 CFP-Tree結構圖

定義6. 短交易. 若顧客感興趣的產品量小于t,則稱該顧客交易為短交易.

若將短交易插入樹中, 則葉節點到根的路徑長度小于t, 故沒有必要將此交易插入樹中. 因此, 在數據預處理中, 可刪除所有短交易和其對應的顧客信息.

定義7. 錨節點. 距CFP-Tree根節點t層的節點.

若選擇從錨節點到根上所有節點, 則可覆蓋全部顧客. CFP-Tree需維護2個表: 頻繁項列表按頻繁計數降序排列; 樹下面的顧客表記錄每個顧客對應的葉節點.

定義8. CFP-Tree. 設使用樹結構表示顧客數據庫. CFP-Tree是一種高度為t的樹結構, 包括三部分,定義如下:

1) 包含一個標記為null的根節點、一個項前綴子樹作為根的孩子、一個頻繁項表、一個顧客項表;

2) 在項前綴子樹上的每個節點包含四個域, 項名稱、頻繁項、節點鏈和標記標簽, 其中, 項名稱記錄當前項代表哪個節點; 頻繁項表示到此節點的頻繁度;節點鏈鏈接到CFP-Tree上有相同名稱的下一項, 若無則為null; 標記標簽用來標記該節點是否被選中, 被選中為1, 未被選擇則為0;

3) 在頻繁項列表的每個入口包含項名稱和節點鏈頭2個域．其中, 節點鏈頭指向CFP-Tree上有相同項名稱的第一個節點;

4) 顧客項表頭的每個入口包含顧客名稱和節點鏈頭2個域. 其中, 節點鏈頭指向CFP-Tree上的后1個節點.

為構建CFP-Tree, 需掃描數據庫兩次, 第一次讀取全部的項, 并將單個項按照頻繁度降序排序, 構建CFP-Tree根節點和左側鏈表; 第2次掃描數據庫, 將事務數據庫中的每個交易都插入到CFP-Tree樹結構中.

2 Effective-Cover算法

客戶導向的目錄分割問題已被證明是一個NP完全問題, 徐秀娟在研究這類問題時; 提出一種新的數據結構TFP-Tree, 基于此數據結構提出一種新的算法Max-Cover, 獲得了比較好的目錄分割結果[10].

但是該算法在樹的遍歷中, 是將樹的葉子節點按照支持度進行降序排序, 在遍歷樹的過程中優先選擇支持數大的葉子點, 再從選中的葉子節點到根節點的路徑上選擇產品加入到目錄. 這樣做只考慮葉子節點的支持度, 而忽視了節點之間的關聯性, 可能會導致生成的目錄內部產品耦合性不高,顧客與顧客之間的關聯性也不大.

本文在此基礎上改進了數據存儲結構, 構建了一種新的數據結構CFP-Tree, 并改進了樹的遍歷方法,設計出相應的最大顧客覆蓋的目錄分割算法Effective-Cover, 結合本文提出的基于興趣度約束的目錄分割算法, 可將商品目錄分割問題變成樹深度搜索問題.

2.1 構造CFP-Tree

構建CFP-Tree算法描述如算法1.

?

表1給出顧客交易數據的一個例子. 設此時興趣度t為3, 其中每條交易中的項按照支持度降序排序,將修剪后的每條數據寫在表的第三列.

掃描表1所示的顧客數據集, 刪除短交易; 并對所有頻繁項按照降序排序, 然后對每條交易中的項按照頻繁度從高到低的順序進行排序, 取出前t個產品.首先得到圖1(a)的項列表. 然后掃描數據庫構建相應的CFP-Tree, 如圖1(b)所示. 例如對于顧客c1其對應的交易為,將其排序為由于t為3, 則將其剪枝, 僅保留前t個產品, 即再將其插入CFP-Tree上, 成為最左邊的樹枝. 對于剩余的顧客交易數據, 也使用類似方法插入.

表1 示例數據庫

2.2 算法過程

本文使用CFP-Tree樹形結構存儲顧客數據, 客戶導向的目錄分割問題變成了在剪枝后的樹上尋找某些產品的組合問題, 并使該組合可最大程度覆蓋感興趣的顧客. 下面給出了本文提出的Effective-Cover算法的具體過程.

算法2: Effective-Cover輸入: 歷史交易記錄Customer DB, 目錄數量k, 每個目錄包含的產品數量r, 顧客興趣度t.輸出: k個目錄和對應的k個顧客簇. Step1: 將一個顧客的所有交易合并為一個交易, 并刪除所有短交易; Step2: 標記所有顧客為未覆蓋顧客; 1 For catto k=（）{ (第一次)掃描數據庫中所有未覆蓋的顧客交易得到相應的頻繁項并計算支持度, 按照頻繁項的支持度進行降序排序, 將頻繁項對應的產品標記為未選狀態; (第二次)掃描預處理過的數據中所有未覆蓋的顧客交易, 構建CFP-Tree;掃描CFP-Tree, 將當前的所有葉子節點加入數組Leaf中, 將數組Leaf按照節點計數從高到低排序后得到新數組OrderLeaf; while catr＜{（）（）{從數組OrderLeaf選擇支持度最大的葉子節點p, 將OrderLeaf []p到root路徑上的未選中節點加入cat; } else {從trcat if rcatt -≥--（）層中尋找父節點已經被覆蓋的子樹; if (從父節點到葉子節點上的存在未選中節點){將未選中節點加入到cat; } else{

在沒有被覆蓋的葉子節點當中選中支持度最大的節點′p,將OrderLeaf ［］′p到root路徑上的未選中節點加入cat; } }將cat覆蓋的顧客標記為已覆蓋顧客; }

2.3 算法分析

根據整個算法運行過程, 我們觀察到對算法效率影響最大的是反復掃描數據庫讀取數據的時間. 與原有的算法相比較, 本算法通過增加節點標記的方法大大減少了數據庫的掃描次數, 提高了算法的運行效率.雖然在算法復雜方面較原有算法沒有明顯降低, 但在目錄產品選擇上降低了算法的隨機性, 一定程度上提高了目錄分割結果的準確性.

3 實驗及討論

3.1 實驗設置

為了演示算法運行效果, 本文首先給出一個包含20條顧客交易數據的示例數據集. 在本次實驗中, 相應的參數設置如下: t=3, r=5, k=3. 其中每條交易中的項按照支持度降序排序, 并得到了數據預處理后的剪枝結果, 如表2所示.

表2 示例數據集

3.2 實驗結果

根據算法1構建CFP-Tree, 我們首先將數據庫的每條交易信息存儲到樹結構中, 如圖2所示. 再根據算法2, 從樹中遍歷選擇節點依次加入到目錄中, 得出目錄分割結果, 如表3所示.

表3 實驗結果

圖2 CFP-Tree

3.3 實驗結果分析與討論

從實驗結果可以看出, 與文獻[10]的算法相比,本算法在遍歷樹的過程中, 在選擇節點時, 優先選擇父親節點被覆蓋的子節點, 否則, 優先選擇支持數最大的葉子節點. 這樣做既保證了同一目錄中, 客戶之間興趣盡可能相似, 同時保證了目錄覆蓋客戶數盡可能多,提高了目錄分割結果的效用.

本算法構建一棵CFP-Tree樹只需要掃描數據庫2次. 其中, 第1次獲得所有顧客交易中對應商品的支持度, 第2次將所有顧客的交易插入樹中, 每個顧客對應1條交易, 完成了數據預處理. 構建CFP-Tree樹結構后, 按照算法Effective-Cover中樹的遍歷方法從樹上選擇r個節點加入. 每個目錄構建成功后, 都需要掃描數據庫1次以便標記所有被當前目錄覆蓋的產品和顧客. 因此, 構建k個錄只需掃描2k+次數據庫.

在示例數據集上, 本文所提出的Effective-Cover算法的客戶覆蓋數比文獻[10]提出的Max-Cover算法多. 為了測試本文所提出的算法在大規模數據集上的運行效果, 本文使用IBM數據生成器產生合成數據集,并在該數據集上比較兩種算法. 實驗結果顯示, 本文所提出的算法在算法運行效率和客戶覆蓋結果上, 具有更好的表現.

4 總結與展望

商業活動的最終目的是獲得盡可能大的利潤. 近年來, 微觀經濟觀點指導下的數據挖掘得到了快速的發展, 本文將微觀經濟觀點引入到數據挖掘中, 討論了目錄分割問題. 在未來的工作中, 我們將從以下角度繼續深入討論本文研究的問題:

1) 在商品選擇的過程中, 不僅考慮顧客的交易歷史, 還考慮現實情境中能反映顧客興趣度的其他信息,如商品瀏覽記錄等.

2) 在商品選擇的過程中, 考慮單個商品對企業總體利潤的貢獻度. 譬如現有商品選擇算法都不允許負利潤商品存在. 然而現實情況下, 為了吸引顧客, 捆綁銷售的商品集合中可能包含企業虧本售賣的商品.

1 Rezaeinia SM, Rahmani R. Recommender system based on customer segmentation(RSCS). Kybernetes, 2016, 45(6): 946–961.

2 Gü?demir H, Selim H. Integrating multi-criteria decision making and clustering for business customer segmentation. Industrial Management & Data Systems, 2015, 115(6): 1022–1040.

3 Kleinberg J, Papadimitriou C, Raghavan P. Segmentation problems. Journal of the ACM (JACM), 2004, 51(2): 263–280.

4 Kleinberg J, Papadimitriou C, Raghavan P. Segmentation problems. Proc. of the Thirtieth Annual ACM Symposium on Theory of Computing. 1998. 473–482.

5 Kleinberg J, Papadimitriou C, Raghavan P. A microeconomic view of data mining. Data Mining and Knowledge Discovery, 1998, 2(4): 311–324.

6 Ester M, Ge R, Jin W, et al. A microeconomic data mining problem:customer-oriented catalog segmentation. Proc. of the Tenth ACM SIGKDD Int’l Conference on Knowledge Discovery and Data Mining. 2004. 557–562.

7 Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation. ACM Sigmod Record, 2000, 29(2): 1–12.

8 Han J, Wang J, Lu Y. Mining top-k frequent closed patterns without minimum support. IEEE Int’l Conference on Data Mining, ICDM 2002. 2002. 211–218.

9 Xu X, Liu Y, Wang Z, et al. Catalog segmentation withdouble constraints in business. Pattern Recognition Letters, 2009, 30(4): 440–448.

10 徐秀娟,王喆,常曉宇,等.一種新的面向顧客的目錄分割算法.計算機研究與發展,2008,(z1):310–315.

11 Amiri A. Customer-oriented catalog segmentation: Effective solution approaches. Decision Support Systems, 2006, 42(3): 1860–1871.

12 Mahdavi I, Movahednejad M, Adbesh F. Designing customer-oriented catalogs in e-CRM using an effective self-adaptive genetic algorithm. Expert Systems with Applications, 2011, 38(1): 631–639.

13 Xu Z, Du D, Xu D. Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems. Journal of Combinatorial Optimization, 2014, 27(2): 315–327.

14 Kianfar K, Fathi M, Hasanzadeh A, et al. Catalog segmentation with the objective of satisfying customer requirements in minimum number of catalog. 2009 IEEE International Conference on Industrial Engineering and Engineering Management. IEEE. 2009. 1253–1257.

Improved Algorithm of Customer Oriented Catalog Segmentation Problem

DU Ping-Ping1, LU Ke1, WU Jin-Nan21(School of Management Science and Engineering, Anhui University of Technology, Maanshan 243002, China)2(School of Business, Anhui University of Technology, Maanshan 243002, China)

The customer oriented catalog segmentation problem assumes that one customer is interested in at least a certain number of items in the catalog, and then calculates the number of customers that are covered by the catalog. Hence, the result of catalog segmentation is assessed according to it. In order to ensure that the catalog covers customers as many as possible, the existing segmentation algorithm ignores the effect of the results of the catalog segmentation. Aiming at this problem, this paper constructs a new data storage structure CFP-Tree for storing customer transaction data, and presents a new algorithm Effective-Cover to solve the problem of catalog segmentation. The algorithm uses tree depth traversal method to select catalog products. The experimental results show that the algorithm can obtain better catalog segmentation results.

catalog segmentation; CFP-Tree; Effective-Cover algorithm; customer; business intelligence

國家自然科學基金(7371013);安徽工業大學校青年教師科研基金(QZ201420);安徽省教育廳自然科學基金(KJ2016A087)

2016-07-21;收到修改稿時間:2016-08-22

10.15888/j.cnki.csa.005690