陸 楠，杜文峰，梁正平

深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，深圳 518060

基于FP-tree目錄分割自適應(yīng)算法

陸 楠，杜文峰，梁正平

深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，深圳 518060

研究面向顧客的商業(yè)智能目錄分割問(wèn)題，要求顧客對(duì)收到的目錄至少有興趣度t，并評(píng)估滿(mǎn)足最小興趣度的顧客數(shù)量.為優(yōu)化評(píng)估效果，構(gòu)建頻繁模式樹(shù)結(jié)構(gòu)FP-tree存儲(chǔ)顧客數(shù)據(jù)庫(kù)，給出MCC-CS算法解決目錄分割問(wèn)題，該算法使用樹(shù)深度遍歷法選擇目錄產(chǎn)品.經(jīng)驗(yàn)證，該算法能夠獲得更好的商業(yè)目標(biāo).

數(shù)據(jù)挖掘;目錄分割;顧客覆蓋;頻繁模式樹(shù);自適應(yīng)算法

分割問(wèn)題［3-4］是一類(lèi)基于微觀經(jīng)濟(jì)觀點(diǎn)的經(jīng)典商業(yè)智能優(yōu)化問(wèn)題，包括市場(chǎng)分割和目錄分割［3］.本研究討論的目錄分割問(wèn)題可描述為:企業(yè)將定制目錄發(fā)送給顧客，使顧客了解企業(yè)產(chǎn)品達(dá)到促銷(xiāo)效果.該問(wèn)題有3個(gè)要求［3-4］:① 目錄需大小適中.對(duì)傳統(tǒng)企業(yè)來(lái)說(shuō)，若目錄太大則設(shè)計(jì)、印刷和郵寄等成本加大，對(duì)于電子商務(wù)公司來(lái)說(shuō)，目錄太大會(huì)分散顧客注意力，使顧客產(chǎn)生厭倦情緒.反之，若目錄太小，則不足以產(chǎn)生促銷(xiāo)效果;② 目錄中包含的商品需具有代表性，使顧客能夠?qū)ζ涓信d趣，從而促進(jìn)非目錄商品的銷(xiāo)售.一旦顧客通過(guò)目錄被吸引到實(shí)體店，就有可能購(gòu)買(mǎi)非目錄中的產(chǎn)品;③企業(yè)應(yīng)針對(duì)不同顧客制定不同目錄.僅對(duì)所有顧客制定1個(gè)目錄是不明智的，并非所有顧客都關(guān)心同樣的商品.然而限于成本也不能為每個(gè)顧客都制定一個(gè)特定目錄.因此，企業(yè)通常將顧客劃分為k個(gè)簇，再針對(duì)每個(gè)簇制定相應(yīng)的目錄，使促銷(xiāo)效果最佳.由此可見(jiàn)，顧客目錄分割問(wèn)題也是一個(gè)NP(non-deterministic polynomial)完全問(wèn)題［3］.

作為商業(yè)智能目錄分割問(wèn)題，從市場(chǎng)營(yíng)銷(xiāo)來(lái)說(shuō)，以往的促銷(xiāo)都是面向產(chǎn)品的促銷(xiāo)，企業(yè)生產(chǎn)者很少?gòu)念櫩徒嵌瓤紤].現(xiàn)在企業(yè)銷(xiāo)售產(chǎn)品都是面向顧客的促銷(xiāo)，即生產(chǎn)的產(chǎn)品都經(jīng)過(guò)嚴(yán)格調(diào)研且顧客需要的產(chǎn)品.這種觀念的轉(zhuǎn)變使得企業(yè)在制定目錄時(shí)也應(yīng)從顧客的角度出發(fā)，將顧客分成不同的顧客簇，并制定面向不同顧客群的目錄，從而使目錄對(duì)顧客簇產(chǎn)生最大效用.為使顧客對(duì)接收的目錄感興趣，要求每個(gè)顧客對(duì)接收的目錄至少有興趣度t.如此，目錄分割問(wèn)題變成了加入興趣度約束的目錄分割問(wèn)題，也稱(chēng)面向顧客的目錄分割問(wèn)題.

1 目錄分割問(wèn)題

商業(yè)智能目錄分割是基于單個(gè)企業(yè)效用的問(wèn)題.設(shè)企業(yè)已對(duì)其顧客有充分了解，則可建立顧客數(shù)據(jù)庫(kù) (customers database)，用雙向圖G表示，G=(P，C，E)，P={p1，p2，…，pm}，C={c1，c2，…，cn}使用‖表示集合的基數(shù)，且其中，P是所有產(chǎn)品的集合;C是所有顧客的集合;E是邊集，當(dāng)且僅當(dāng)顧客ci對(duì)產(chǎn)品pj感興趣時(shí)，存在對(duì)應(yīng)邊eij，記做eij=(ci，pj).

1.1 目錄分割定義

文獻(xiàn)［3］已證明，基本分割問(wèn)題是NP完全問(wèn)題［3］.

定義2 顧客覆蓋.若顧客對(duì)目錄中至少1個(gè)產(chǎn)品感興趣，則稱(chēng)該目錄覆蓋了此顧客.

下面給出目錄分割問(wèn)題的定義.用ω(P')［2］表示至少有1條邊連接到產(chǎn)品集P'中的頂點(diǎn)c的顧客集合，即

定義3k目錄分割問(wèn)題［4］.用二分圖G=(P，C，E)表示顧客數(shù)據(jù)庫(kù)，且求P的k個(gè)子集P1，P2，…，Pk，和其對(duì)應(yīng)C的k個(gè)子集C1，C2，…，Ck，使它們滿(mǎn)足目標(biāo)函數(shù)

對(duì)于任意i和j，當(dāng)i≠j時(shí)，Pi∩Pj可不必為空.

在定義3中，若將顧客分成k簇，每個(gè)顧客最多只能屬于1個(gè)簇，每個(gè)簇對(duì)應(yīng)的目錄包含r個(gè)產(chǎn)品;而同一產(chǎn)品允許在多個(gè)產(chǎn)品簇中同時(shí)出現(xiàn).

1.2 具有興趣度約束的目錄分割問(wèn)題

定義1至定義3中的目錄分割問(wèn)題是以最大化覆蓋顧客數(shù)量為目的.但實(shí)際上若顧客被目錄所吸引，就會(huì)購(gòu)買(mǎi)很多非目錄產(chǎn)品.Ester等［2］引入最小興趣度t，即在目錄分割問(wèn)題中加入興趣度約束，使發(fā)送到顧客的產(chǎn)品目錄至少有興趣度t的顧客數(shù)量來(lái)測(cè)量顧客的整體效用.為形式化描述此問(wèn)題，設(shè) φ(P'，t)［2］表示至少有t條邊連接到產(chǎn)品集P'中的頂點(diǎn)c的顧客集中，表達(dá)式為

2 最大顧客覆蓋的目錄分割算法

2.1 Naive算法

該算法提出解決目錄分割問(wèn)題的簡(jiǎn)單爬山算法［5］.首先依次選擇支持度最高的前t個(gè)產(chǎn)品進(jìn)入第1個(gè)目錄;再計(jì)算此時(shí)覆蓋的顧客;然后每次在目錄中添加1個(gè)產(chǎn)品，要求是在未選產(chǎn)品中選擇1個(gè)可覆蓋增加顧客最多的產(chǎn)品，直到第1個(gè)目錄含有r個(gè)產(chǎn)品結(jié)束;最后依次填充剩余目錄.Naive算法雖然簡(jiǎn)單且易于實(shí)現(xiàn)，但實(shí)驗(yàn)效果差.

2.2 BPF算法

文獻(xiàn)［6］提出解決顧客商品目錄分割問(wèn)題的BPF(best product fit)算法.根據(jù)對(duì)商品感興趣的剩余顧客數(shù)量，和這些顧客需要感興趣的當(dāng)前商品目錄中其他商品的數(shù)量，為每個(gè)商品賦予1個(gè)分值，從而提高已對(duì)目錄中其他商品感興趣的顧客所關(guān)注商品的優(yōu)先權(quán).圖1給出了BPF算法描述.

圖1 BPF算法描述 Fig.1 BPF algorithm

BPF算法的關(guān)鍵是確定商品P的評(píng)分函數(shù)，但它忽略了兩個(gè)問(wèn)題:①評(píng)分函數(shù)的兩部分在函數(shù)中所起的作用不均衡;②第2部分未考慮對(duì)P的興趣度，只考慮商品種類(lèi)差異而忽視數(shù)量或利潤(rùn)的效用，導(dǎo)致聚簇性能下降，不能最大化全部顧客的效用f(x).

2.3 最大顧客覆蓋目錄分割算法的提出

為避免資源浪費(fèi)，使用頻繁模式樹(shù) (frequent-pattern tree，F(xiàn)P-tree)結(jié)構(gòu)存儲(chǔ)顧客數(shù)據(jù)庫(kù)，即將顧客數(shù)據(jù)庫(kù)映射到1棵樹(shù)上，然后基于FP-tree設(shè)計(jì)相應(yīng)的最大顧客覆蓋的目錄分割算法 (maximal customers cover for catalog segmentation，MCC-CS)，利用我們提出的基于興趣度約束的目錄分割算法，可將商品目錄分割問(wèn)題變成樹(shù)深度搜索問(wèn)題.

2.3.1 頻繁模式樹(shù)FP-tree結(jié)構(gòu)定義

為找到能覆蓋最多顧客的k個(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層，顧客感興趣的產(chǎn)品中支持度最高的t個(gè)產(chǎn)品就可覆蓋其需求.將顧客對(duì)應(yīng)的感興趣產(chǎn)品按支持度降序排列，并取前t個(gè)插入樹(shù)中.本研究使用改進(jìn)后的FP-tree［6］結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，將每條交易對(duì)應(yīng)的顧客信息存入對(duì)應(yīng)的表中，稱(chēng)此樹(shù)為t層興趣度約束樹(shù) (frequent pattern tree witht-layer interest constraint).FP-tree每個(gè)樹(shù)枝末尾加入顧客信息，如圖2.

圖2 頻繁模式樹(shù)示意Fig.2 FP-tree and its items lists

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

定義6 錨節(jié)點(diǎn)［7］.它是距離FP-tree根節(jié)點(diǎn)t層的節(jié)點(diǎn).若選擇從錨節(jié)點(diǎn)到根上所有節(jié)點(diǎn)，則可覆蓋全部顧客.FP-tree需維護(hù)2個(gè)表:頻繁項(xiàng)列表按頻繁計(jì)數(shù)降序排列;樹(shù)下面的顧客表記錄每個(gè)顧客對(duì)應(yīng)的葉節(jié)點(diǎn).

定義7 FP-tree.FP-tree是一種最高為t層的樹(shù)結(jié)構(gòu)，包含:①1個(gè)標(biāo)記為null的根節(jié)點(diǎn)、1個(gè)項(xiàng)前綴子樹(shù)作為根的孩子、1個(gè)頻繁項(xiàng)表和1個(gè)顧客項(xiàng)表;②在項(xiàng)前綴子樹(shù)上的每個(gè)節(jié)點(diǎn)包含項(xiàng)名稱(chēng)、頻繁項(xiàng)和節(jié)點(diǎn)鏈3個(gè)域.其中，項(xiàng)名稱(chēng)記錄當(dāng)前項(xiàng)代表哪個(gè)節(jié)點(diǎn);頻繁項(xiàng)表示到此節(jié)點(diǎn)的頻繁度，節(jié)點(diǎn)鏈鏈接到FP-tree上有相同名稱(chēng)的下一項(xiàng)，若無(wú)則為null;③在頻繁項(xiàng)列表的每個(gè)入口包含項(xiàng)名稱(chēng)和節(jié)點(diǎn)鏈頭2個(gè)域.其中，節(jié)點(diǎn)鏈頭指向FP-tree上有相同項(xiàng)名稱(chēng)的第1個(gè)節(jié)點(diǎn);④在顧客項(xiàng)表頭的每個(gè)人包含顧客名稱(chēng)和節(jié)點(diǎn)鏈頭2個(gè)域.其中，節(jié)點(diǎn)鏈頭指向FP-tree上相應(yīng)顧客交易的最后1個(gè)節(jié)點(diǎn).

為構(gòu)建FP-tree，需掃描數(shù)據(jù)庫(kù)2次.第1次讀取全部單個(gè)項(xiàng)，并將單個(gè)項(xiàng)按頻繁度降序排列，構(gòu)建FP-tree的根節(jié)點(diǎn)和鏈表;第2次掃描數(shù)據(jù)庫(kù)，將事務(wù)數(shù)據(jù)庫(kù)中的每個(gè)交易都插入FP-tree.

2.3.2 構(gòu)建 FP-tree結(jié)構(gòu)

基于上述定義構(gòu)建FP-tree算法如下.

算法1.構(gòu)建 FP-tree.算法輸入為顧客數(shù)據(jù)庫(kù);輸出為FP-tree.

①掃描數(shù)據(jù)庫(kù)，找到所有頻繁項(xiàng)集合和其對(duì)應(yīng)的頻繁度.將所有項(xiàng)按頻繁度降序排列，所得鏈表記做Lf.

insert-tree(，T)操作.若T有同名項(xiàng)N，則將N計(jì)數(shù)加1;否則，創(chuàng)建新節(jié)點(diǎn)N，并將計(jì)數(shù)置1，將N的父節(jié)點(diǎn)鏈接到T，并將在頻繁項(xiàng)表中對(duì)應(yīng)的節(jié)點(diǎn)鏈頭引出鏈接到此節(jié)點(diǎn).若P?Φ，則繼續(xù)遞歸調(diào)用insert-tree(，T).

當(dāng)插入操作完成后，在顧客項(xiàng)表中找到當(dāng)前交易對(duì)應(yīng)的顧客，并將其鏈接到p'上.

表1給出每個(gè)顧客感興趣的產(chǎn)品示例數(shù)據(jù)庫(kù).設(shè)此時(shí)興趣度t=3，修剪后的每條數(shù)據(jù)排在末列.

掃描表1數(shù)據(jù)庫(kù)，刪除短交易;按頻繁度降序排列所有交易，并取前t個(gè)交易，得到項(xiàng)列表.然后掃描數(shù)據(jù)庫(kù)構(gòu)建相應(yīng)的FP-tree，如圖2(此處為清晰，將樹(shù)上的節(jié)點(diǎn)到圖2(a)相關(guān)的項(xiàng)上的鏈接省去).例如，對(duì)顧客C1，其對(duì)應(yīng)的交易為I0，I1，I2，I4，將其排序?yàn)镮0，I1，I2，由于t=3，則將其剪枝，僅保留前t個(gè)產(chǎn)品，即I0，I1，I2，然后將其插入FP-tree，成為最左邊的樹(shù)枝.對(duì)剩余的顧客交易，也使用類(lèi)似方法插入.

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

2.3.3 MCC-CS 算法

用FP-tree結(jié)構(gòu)表示數(shù)據(jù)庫(kù)，商品目錄分割問(wèn)題變成了在剪枝后的樹(shù)上尋找某些節(jié)點(diǎn)的組合，并使該組合可最大限度地覆蓋感興趣的顧客.

算法2.MCC-CS算法.算法輸入為歷史交易記錄Customer DB、目錄數(shù)量k、每個(gè)目錄包含的產(chǎn)品數(shù)量r及顧客興趣度t;輸出為k個(gè)目錄和其對(duì)應(yīng)的k個(gè)顧客簇.算法執(zhí)行前需將每個(gè)顧客的所有交易合并為1條交易，刪除所有短交易.按圖3給出的MCC-CS算法描述，標(biāo)記所有顧客為未覆蓋顧客.

圖3MCC-CS算法描述Fig.3 MCC-CS algorithm

MCC-CS算法在每次構(gòu)建目錄時(shí)需用未覆蓋的顧客交易來(lái)構(gòu)建1棵FP-tree，從而使構(gòu)建的樹(shù)能最大程度地覆蓋尚未覆蓋的顧客.

2.3.4 算法分析

MCC-CS算法為每個(gè)目錄構(gòu)建1棵FP-tree，共構(gòu)建k棵樹(shù).構(gòu)建1棵樹(shù)，需掃描數(shù)據(jù)庫(kù)2次.第1次獲得所有未覆蓋顧客對(duì)應(yīng)商品的支持度，第2次將所有未覆蓋顧客的交易插入樹(shù)中，數(shù)據(jù)預(yù)處理完畢后，每個(gè)顧客僅對(duì)應(yīng)1條交易.構(gòu)建好樹(shù)后，從樹(shù)上選擇節(jié)點(diǎn)進(jìn)入當(dāng)前目錄需支持度最大的節(jié)點(diǎn)遍歷當(dāng)前樹(shù)的r個(gè)節(jié)點(diǎn).每個(gè)目錄構(gòu)建成功后，還要掃描數(shù)據(jù)庫(kù)1次以便標(biāo)記所有被當(dāng)前目錄覆蓋的產(chǎn)品.因此，構(gòu)建k個(gè)目錄共需掃描3k次數(shù)據(jù)庫(kù).

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證算法的有效性，我們?cè)谥黝l為2.66 GHz，內(nèi)存為1 GB的PC上采用C++編程語(yǔ)言，對(duì)MCC-CS算法與BPF算法［6］性能進(jìn)行比較.實(shí)驗(yàn)數(shù)據(jù)采集自CSDN-IT技術(shù)社區(qū)提供的IBM數(shù)據(jù)生產(chǎn)器［9］產(chǎn)生的合成數(shù)據(jù)庫(kù)，含10×103個(gè)顧客，8×103個(gè)商品及50×103個(gè)交易.在數(shù)據(jù)預(yù)處理時(shí)合并了顧客交易，使得1個(gè)顧客僅對(duì)應(yīng)1條交易，因此交易數(shù)量大減.為觀測(cè)算法效果，同時(shí)采用BPF算法和Naive算法進(jìn)行仿真對(duì)比.BPF算法是目前解決面向顧客的目錄分割問(wèn)題最佳算法.Naive算法指的是使用簡(jiǎn)單爬山算法得到的結(jié)果.

圖4比較了最小興趣度t變化時(shí)獲得的目錄覆蓋的顧客數(shù)量.由圖4可見(jiàn)，目錄覆蓋的顧客隨著t的增加而減少.MCC-CS算法比BPF算法覆蓋了更多的顧客.圖5表示目錄數(shù)量k變化影響的結(jié)果.目錄覆蓋的顧客量隨著目錄數(shù)量k增加而增加，符合市場(chǎng)規(guī)律.目錄數(shù)量的增多表示對(duì)顧客進(jìn)行了更多的細(xì)化，因而成本也要提高，獲得的收益亦高.圖6表示目錄中產(chǎn)品數(shù)量r變化對(duì)結(jié)果的影響.當(dāng)t=2，k=3時(shí)，目錄所覆蓋的顧客數(shù)量隨產(chǎn)品量增加而增加.由圖4至圖6可見(jiàn)，MCC-CS算法獲得了比其他算法更好的結(jié)果.這表明，MCC-CS算法能有效解決面向顧客的目錄分割問(wèn)題.

圖4 顧客覆蓋數(shù)隨興趣度的變化Fig.4 The number of customer cover by changes of interesting

圖7是當(dāng)k=3，r=80時(shí)目錄覆蓋的額外產(chǎn)品比較.額外產(chǎn)品指當(dāng)前目錄覆蓋的顧客所購(gòu)買(mǎi)的非目錄產(chǎn)品.此時(shí)，BPF算法比MCC-CS算法覆蓋了更多的額外產(chǎn)品，這是因?yàn)镸CC-CS算法沒(méi)有考慮此目標(biāo).BPF算法能覆蓋較多額外產(chǎn)品，說(shuō)明算法是松散的.MCC-CS算法所覆蓋的額外產(chǎn)品更少，說(shuō)明該算法產(chǎn)生的目錄是緊密的.

圖5 顧客覆蓋數(shù)隨目錄數(shù)量的變化Fig.5 The number of customer cover by changes of catalog number

圖6 顧客覆蓋數(shù)隨目錄大小的變化Fig.6 The number of customer cover by changes of catalog size

圖7 產(chǎn)品結(jié)果隨興趣度的變化Fig.7 The result of products by changes of interesting

結(jié) 語(yǔ)

本研究面向顧客的目錄分割問(wèn)題，提出基于FP-tree數(shù)據(jù)結(jié)構(gòu)的MCC-CS算法.模擬測(cè)試結(jié)果表明.該算法使目錄分割問(wèn)題更具實(shí)用價(jià)值.下一步我們將加入利潤(rùn)約束，在為企業(yè)構(gòu)建目錄時(shí)兼顧利潤(rùn)條件，從而使構(gòu)建的目錄針對(duì)性更強(qiáng)，功效更好.

［1］Kleinberg J，Papadimitriou C，Raghavan P.數(shù)據(jù)挖掘微觀經(jīng)濟(jì)思想 ［J］.數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)期刊，1998，2(4):311-324.(英文版)

［2］Ester M，GE Rong，JIN Wen，等.一種面向顧客目錄分割的微觀經(jīng)濟(jì)數(shù)據(jù)挖掘問(wèn)題 ［C］//第10屆ACM SIGKDD數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)國(guó)際會(huì)議論文集.西雅圖:計(jì)算機(jī)協(xié)會(huì)，2004:557-562.(英文版)

［3］Kleinberg J，Papadimitriou C，Raghavan P.目錄分割問(wèn)題的近似算法［C］//第13屆計(jì)算理論學(xué)術(shù)會(huì)議論文集.紐約:計(jì)算機(jī)協(xié)會(huì)，1998:321-219.(英文版)

［4］Kleinberg J，Papadimitriou C，Raghavan P.目錄分割問(wèn)題研究 ［J］.ACM 期刊，2004，51(2):263-280.(英文版)

［5］Charu C A.基于分割的流模型應(yīng)用 ［C］//第9屆SIAM數(shù)據(jù)挖掘國(guó)際會(huì)議論文集.斯帕克斯 (美國(guó)):工業(yè)和應(yīng)用數(shù)學(xué)學(xué)會(huì)，2009:721-732.(英文版)

［6］HAN Jia-wei，PEI Jian，YIN Yi-wen.產(chǎn)生候選集頻繁模式的數(shù)據(jù)挖掘［C］//ACM SIGMOD數(shù)據(jù)管理國(guó)際會(huì)議論文集.達(dá)拉斯(美國(guó)):計(jì)算機(jī)協(xié)會(huì)，2005，8(1):53-87.(英文版)

［7］HAN Jia-wei，WANG Jiang-yong，LU Ying，等.具有最小支持度的k層閉合頻繁模式的數(shù)據(jù)挖掘 ［C］//第2屆IEEE數(shù)據(jù)挖掘國(guó)際會(huì)議論文集.前橋 (日本):IEEE出版社.2002:211-218.(英文版)

［8］徐秀娟，王 喆，常曉宇，等.一種新的面向顧客的目錄分割算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2008，45(增刊1):310-315.

［9］Agrawal R.IBM同步數(shù)據(jù)發(fā)生器［M/OL］.［2004-09-23］ http://www.almaden.ibm.com/edquest/syndata.html.(英文版)

［10］Kleinberg J，Tardos E.算法設(shè)計(jì) ［CP/DK］.閱讀，新澤西 (美國(guó)):安德森·威斯利出版社，2005.(英文版)

［1］Kleinberg J，Papadimitriou C，Raghavan P.A microeconomie view of data mining［J］.Journal of Data Mining and Knowledge Discovery，1998，2(4):311-324.

［2］Ester M，GE Rong，JIN Wen，et a1.A microeconomic data mining problem:customer-oriented catalog segmentation［C］//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Seattle:Association for Computing Machinery，2004:557-562.

［3］Kleinberg J，Papadimitriou C，Raghavan P.Approximation algorithm for segmentation problems［C］//Proceedings of the 13th Annual ACM Symp on Theory of Computing.New York:Association for Computing Machinery，1998:321-219.

［4］Kleinberg J，Papadimitriou C，Raghavan P.Segmentation problems［J］.Journal of the ACM，2004，51(2):263-280.

［5］Charu C A.On seginent-based stream modeling and its application［C］//Proceedings of the 9th SIAM International Conference on Data Mining.Sparks(USA):Society for Industrial and Applied Mathematrs，2009:721-732.

［6］HAN Jia-wei，PEI Jian，YIN Yi-wen，et al.Mining frequent patterns without candidate generation:a frequent-Patterm tree approach［C］//Proceedings of the ACM SIGMOD Intemational Conference on Management of Data.Dallas(USA):Association for Computing Machinery，2000，8(1):53-87.

［7］HAN Jia-wei，WANG Jiang-yong，LU Ying，et al.Mining top-kfrequent closed patterns without minimum support［C］//Proceedings of the IEEE International Conference on DataMining. Maebashi(Japan):IEEE Press，2002:211-218.

［8］XU Xiu-juan，WANG Zhe，CHANG Xiao-yu，et al.A novel algorithm for the customer-oriented catalog segmentation problem ［J］.Journal of Computer Research and Development，2008，45(S1):310-315.(in Chinese)

［9］Agrawal R.IBM Synthetic Data Generator［M/OL］.［2004-09-23］ http://www.almaden/ibm.com/edquest/syndata.html.

［10］Kleinberg J，Tardos E.Algorithm Design ［CP/DK］.Reading.New Jersey:Addison-Wesley，2005.

A self-adaptive algorithm for the problem of catalog segmentation based on FP-tree?

LU Nan，DU Wen-feng，and LIANG Zheng-ping

College of Computer Science and Software Engineering Shenzhen University Shenzhen 518060 P.R.China

The customer-oriented catalog segmentation problem in the context of business intelligence was studied.Particularly，the catalog segmentation problem was casted as an optimization for maximizing the satisfaction of all customers subject to the requirement of at least t interestingness for each customer.To solve this problem，we introduced an improved frequent pattern tree to store the customer database and proposed a novel MCC-CS algorithm to optimize the selection of catalog products based on depth-first search strategy.Experimental results show that MCC-CS is capable of obtaining better performance than other state-of-the-art methods.

data mining;catalog segmentation;customer cover;frequent pattern tree;adaptive algorithm

TP 311

A

1000-2618(2011)04-0341-06

2010-12-14;

2011-04-10

廣東省自然科學(xué)基金資助項(xiàng)目 (1015180600100)

陸 楠 (1959-)男 (漢族)，上海市人，深圳大學(xué)教授、博士.E-mail:lunan@szu.edu.cn

Abstract:1000-2618(2011)04-0346-EA

? This work was supported by the Natural Science Foundation of Guangdong Province(1015180600100).

【中文責(zé)編:英 子;英文責(zé)編:雨 辰】