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

客戶導(dǎo)向目錄分割問(wèn)題的改進(jìn)算法①

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

客戶導(dǎo)向目錄分割問(wèn)題假設(shè)顧客至少對(duì)目錄中一定數(shù)量的商品感興趣, 計(jì)算目錄覆蓋的顧客數(shù)量, 據(jù)此評(píng)估目錄分割結(jié)果. 現(xiàn)有的分割算法為了保證目錄盡可能多的覆蓋顧客, 而忽略了目錄分割結(jié)果的效用. 針對(duì)該問(wèn)題, 本文構(gòu)建一種新的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)CFP-Tree用于存儲(chǔ)顧客交易數(shù)據(jù), 并提出一種新的算法Effective-Cover解決目錄分割問(wèn)題. 該算法使用樹(shù)深度遍歷法選擇目錄產(chǎn)品. 實(shí)驗(yàn)結(jié)果表明, 該算法能夠獲得更好的目錄分割結(jié)果.

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

客戶分類問(wèn)題[1,2]是一類經(jīng)典的商業(yè)智能優(yōu)化問(wèn)題, 客戶分類問(wèn)題實(shí)際也屬于分割問(wèn)題的一種. 以此為切入點(diǎn), 近年來(lái), 多種商業(yè)智能理論相繼被提出,其中基于微觀經(jīng)濟(jì)學(xué)的觀點(diǎn)尤其引人注目[3-5]. 該理論將商業(yè)智能視為大量非聚集數(shù)據(jù)在商業(yè)目標(biāo)驅(qū)動(dòng)下的優(yōu)化問(wèn)題, 當(dāng)企業(yè)使用某個(gè)模式使得企業(yè)效益增加時(shí),該模式被認(rèn)為有效[5].

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

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

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

1 符號(hào)定義與問(wèn)題描述

1.1 相關(guān)符號(hào)定義

本文使用二部圖G代表顧客數(shù)據(jù)庫(kù). 有兩類頂點(diǎn)集合, 一類為顧客集合, 另一類為產(chǎn)品集合, 邊代表相應(yīng)的顧客對(duì)相應(yīng)的產(chǎn)品感興趣的事實(shí). 假設(shè)收集到的顧客數(shù)據(jù)存儲(chǔ)在顧客數(shù)據(jù)庫(kù)(Customers DB)中. 相關(guān)的符號(hào)定義包括:

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

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

P={p1, p2,...,pj,...,pm}, 表示所有的產(chǎn)品;

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

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

1.2 客戶導(dǎo)向目錄分割問(wèn)題定義

定義2. 覆蓋. 如果顧客Customeri對(duì)目錄Catalogj中至少有一個(gè)產(chǎn)品感興趣, 稱該目錄覆蓋了該顧客.

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

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

大.

將顧客分成k個(gè)群體, 每個(gè)顧客最多只能屬于其中一個(gè)群體, 每個(gè)群體所對(duì)應(yīng)的目錄包含r個(gè)產(chǎn)品,而同一產(chǎn)品允許在多個(gè)產(chǎn)品目中中同時(shí)出現(xiàn).

定義1至定義4中的目錄分割問(wèn)題以最大化的覆蓋顧客數(shù)量為目的. Ester引入最小興趣度t[6], 即在目錄分割問(wèn)題中加入興趣度約束, 使發(fā)送到顧客的產(chǎn)品目錄至少有興趣度t的顧客數(shù)量來(lái)評(píng)價(jià)目錄的整體效用.

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

1.3 CFP-Tree結(jié)構(gòu)定義

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

圖1 CFP-Tree結(jié)構(gòu)圖

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

若將短交易插入樹(shù)中, 則葉節(jié)點(diǎn)到根的路徑長(zhǎng)度小于t, 故沒(méi)有必要將此交易插入樹(shù)中. 因此, 在數(shù)據(jù)預(yù)處理中, 可刪除所有短交易和其對(duì)應(yīng)的顧客信息.

定義7. 錨節(jié)點(diǎn). 距CFP-Tree根節(jié)點(diǎn)t層的節(jié)點(diǎn).

若選擇從錨節(jié)點(diǎn)到根上所有節(jié)點(diǎn), 則可覆蓋全部顧客. CFP-Tree需維護(hù)2個(gè)表: 頻繁項(xiàng)列表按頻繁計(jì)數(shù)降序排列; 樹(shù)下面的顧客表記錄每個(gè)顧客對(duì)應(yīng)的葉節(jié)點(diǎn).

定義8. CFP-Tree. 設(shè)使用樹(shù)結(jié)構(gòu)表示顧客數(shù)據(jù)庫(kù). CFP-Tree是一種高度為t的樹(shù)結(jié)構(gòu), 包括三部分,定義如下:

1) 包含一個(gè)標(biāo)記為null的根節(jié)點(diǎn)、一個(gè)項(xiàng)前綴子樹(shù)作為根的孩子、一個(gè)頻繁項(xiàng)表、一個(gè)顧客項(xiàng)表;

2) 在項(xiàng)前綴子樹(shù)上的每個(gè)節(jié)點(diǎn)包含四個(gè)域, 項(xiàng)名稱、頻繁項(xiàng)、節(jié)點(diǎn)鏈和標(biāo)記標(biāo)簽, 其中, 項(xiàng)名稱記錄當(dāng)前項(xiàng)代表哪個(gè)節(jié)點(diǎn); 頻繁項(xiàng)表示到此節(jié)點(diǎn)的頻繁度;節(jié)點(diǎn)鏈鏈接到CFP-Tree上有相同名稱的下一項(xiàng), 若無(wú)則為null; 標(biāo)記標(biāo)簽用來(lái)標(biāo)記該節(jié)點(diǎn)是否被選中, 被選中為1, 未被選擇則為0;

3) 在頻繁項(xiàng)列表的每個(gè)入口包含項(xiàng)名稱和節(jié)點(diǎn)鏈頭2個(gè)域．其中, 節(jié)點(diǎn)鏈頭指向CFP-Tree上有相同項(xiàng)名稱的第一個(gè)節(jié)點(diǎn);

4) 顧客項(xiàng)表頭的每個(gè)入口包含顧客名稱和節(jié)點(diǎn)鏈頭2個(gè)域. 其中, 節(jié)點(diǎn)鏈頭指向CFP-Tree上的后1個(gè)節(jié)點(diǎn).

為構(gòu)建CFP-Tree, 需掃描數(shù)據(jù)庫(kù)兩次, 第一次讀取全部的項(xiàng), 并將單個(gè)項(xiàng)按照頻繁度降序排序, 構(gòu)建CFP-Tree根節(jié)點(diǎn)和左側(cè)鏈表; 第2次掃描數(shù)據(jù)庫(kù), 將事務(wù)數(shù)據(jù)庫(kù)中的每個(gè)交易都插入到CFP-Tree樹(shù)結(jié)構(gòu)中.

2 Effective-Cover算法

客戶導(dǎo)向的目錄分割問(wèn)題已被證明是一個(gè)NP完全問(wèn)題, 徐秀娟在研究這類問(wèn)題時(shí); 提出一種新的數(shù)據(jù)結(jié)構(gòu)TFP-Tree, 基于此數(shù)據(jù)結(jié)構(gòu)提出一種新的算法Max-Cover, 獲得了比較好的目錄分割結(jié)果[10].

但是該算法在樹(shù)的遍歷中, 是將樹(shù)的葉子節(jié)點(diǎn)按照支持度進(jìn)行降序排序, 在遍歷樹(shù)的過(guò)程中優(yōu)先選擇支持?jǐn)?shù)大的葉子點(diǎn), 再?gòu)倪x中的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上選擇產(chǎn)品加入到目錄. 這樣做只考慮葉子節(jié)點(diǎn)的支持度, 而忽視了節(jié)點(diǎn)之間的關(guān)聯(lián)性, 可能會(huì)導(dǎo)致生成的目錄內(nèi)部產(chǎn)品耦合性不高,顧客與顧客之間的關(guān)聯(lián)性也不大.

本文在此基礎(chǔ)上改進(jìn)了數(shù)據(jù)存儲(chǔ)結(jié)構(gòu), 構(gòu)建了一種新的數(shù)據(jù)結(jié)構(gòu)CFP-Tree, 并改進(jìn)了樹(shù)的遍歷方法,設(shè)計(jì)出相應(yīng)的最大顧客覆蓋的目錄分割算法Effective-Cover, 結(jié)合本文提出的基于興趣度約束的目錄分割算法, 可將商品目錄分割問(wèn)題變成樹(shù)深度搜索問(wèn)題.

2.1 構(gòu)造CFP-Tree

構(gòu)建CFP-Tree算法描述如算法1.

?

表1給出顧客交易數(shù)據(jù)的一個(gè)例子. 設(shè)此時(shí)興趣度t為3, 其中每條交易中的項(xiàng)按照支持度降序排序,將修剪后的每條數(shù)據(jù)寫(xiě)在表的第三列.

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

表1 示例數(shù)據(jù)庫(kù)

2.2 算法過(guò)程

本文使用CFP-Tree樹(shù)形結(jié)構(gòu)存儲(chǔ)顧客數(shù)據(jù), 客戶導(dǎo)向的目錄分割問(wèn)題變成了在剪枝后的樹(shù)上尋找某些產(chǎn)品的組合問(wèn)題, 并使該組合可最大程度覆蓋感興趣的顧客. 下面給出了本文提出的Effective-Cover算法的具體過(guò)程.

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

在沒(méi)有被覆蓋的葉子節(jié)點(diǎn)當(dāng)中選中支持度最大的節(jié)點(diǎn)′p,將OrderLeaf ［］′p到root路徑上的未選中節(jié)點(diǎn)加入cat; } }將cat覆蓋的顧客標(biāo)記為已覆蓋顧客; }

2.3 算法分析

根據(jù)整個(gè)算法運(yùn)行過(guò)程, 我們觀察到對(duì)算法效率影響最大的是反復(fù)掃描數(shù)據(jù)庫(kù)讀取數(shù)據(jù)的時(shí)間. 與原有的算法相比較, 本算法通過(guò)增加節(jié)點(diǎn)標(biāo)記的方法大大減少了數(shù)據(jù)庫(kù)的掃描次數(shù), 提高了算法的運(yùn)行效率.雖然在算法復(fù)雜方面較原有算法沒(méi)有明顯降低, 但在目錄產(chǎn)品選擇上降低了算法的隨機(jī)性, 一定程度上提高了目錄分割結(jié)果的準(zhǔn)確性.

3 實(shí)驗(yàn)及討論

3.1 實(shí)驗(yàn)設(shè)置

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

表2 示例數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

根據(jù)算法1構(gòu)建CFP-Tree, 我們首先將數(shù)據(jù)庫(kù)的每條交易信息存儲(chǔ)到樹(shù)結(jié)構(gòu)中, 如圖2所示. 再根據(jù)算法2, 從樹(shù)中遍歷選擇節(jié)點(diǎn)依次加入到目錄中, 得出目錄分割結(jié)果, 如表3所示.

表3 實(shí)驗(yàn)結(jié)果

圖2 CFP-Tree

3.3 實(shí)驗(yàn)結(jié)果分析與討論

從實(shí)驗(yàn)結(jié)果可以看出, 與文獻(xiàn)[10]的算法相比,本算法在遍歷樹(shù)的過(guò)程中, 在選擇節(jié)點(diǎn)時(shí), 優(yōu)先選擇父親節(jié)點(diǎn)被覆蓋的子節(jié)點(diǎn), 否則, 優(yōu)先選擇支持?jǐn)?shù)最大的葉子節(jié)點(diǎn). 這樣做既保證了同一目錄中, 客戶之間興趣盡可能相似, 同時(shí)保證了目錄覆蓋客戶數(shù)盡可能多,提高了目錄分割結(jié)果的效用.

本算法構(gòu)建一棵CFP-Tree樹(shù)只需要掃描數(shù)據(jù)庫(kù)2次. 其中, 第1次獲得所有顧客交易中對(duì)應(yīng)商品的支持度, 第2次將所有顧客的交易插入樹(shù)中, 每個(gè)顧客對(duì)應(yīng)1條交易, 完成了數(shù)據(jù)預(yù)處理. 構(gòu)建CFP-Tree樹(shù)結(jié)構(gòu)后, 按照算法Effective-Cover中樹(shù)的遍歷方法從樹(shù)上選擇r個(gè)節(jié)點(diǎn)加入. 每個(gè)目錄構(gòu)建成功后, 都需要掃描數(shù)據(jù)庫(kù)1次以便標(biāo)記所有被當(dāng)前目錄覆蓋的產(chǎn)品和顧客. 因此, 構(gòu)建k個(gè)錄只需掃描2k+次數(shù)據(jù)庫(kù).

在示例數(shù)據(jù)集上, 本文所提出的Effective-Cover算法的客戶覆蓋數(shù)比文獻(xiàn)[10]提出的Max-Cover算法多. 為了測(cè)試本文所提出的算法在大規(guī)模數(shù)據(jù)集上的運(yùn)行效果, 本文使用IBM數(shù)據(jù)生成器產(chǎn)生合成數(shù)據(jù)集,并在該數(shù)據(jù)集上比較兩種算法. 實(shí)驗(yàn)結(jié)果顯示, 本文所提出的算法在算法運(yùn)行效率和客戶覆蓋結(jié)果上, 具有更好的表現(xiàn).

4 總結(jié)與展望

商業(yè)活動(dòng)的最終目的是獲得盡可能大的利潤(rùn). 近年來(lái), 微觀經(jīng)濟(jì)觀點(diǎn)指導(dǎo)下的數(shù)據(jù)挖掘得到了快速的發(fā)展, 本文將微觀經(jīng)濟(jì)觀點(diǎn)引入到數(shù)據(jù)挖掘中, 討論了目錄分割問(wèn)題. 在未來(lái)的工作中, 我們將從以下角度繼續(xù)深入討論本文研究的問(wèn)題:

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

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

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 徐秀娟,王喆,常曉宇,等.一種新的面向顧客的目錄分割算法.計(jì)算機(jī)研究與發(fā)展,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

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

2016-07-21;收到修改稿時(shí)間:2016-08-22

10.15888/j.cnki.csa.005690