一种面向商业智能兴趣度的顾客目录分割算法

1、一种面向商业智能兴趣度的顾客目录分割算法摘要：从商业智能角度出发，研究面向顾客的目录分割问题，发挥商品及顾客聚簇在交易数量中所起的作用。为平衡评分函数各部分的地位，引入了顾客对商品的兴趣度加权值，并对满足商品兴趣度的顾客数量进行评估。为优化这一评估，提出了基于顾客兴趣度的加权商品目录分割IW-BPF算法，并给出了详细的SQL算法描述和实验分析结果，验证了本算法能够获得更好的商业目标。关键词：数据挖掘；目录分割；兴趣度权值；BPF算法1引言 目前，商业领域汇集了大量客户信息和业务数据，商业智能是数据挖掘技术的一个重要应用领域。分割问题是一类经典的商业智能优化问题，它包括市场分割和目录分割。本文研

2、究的目录分割问题是基于微观经济理论的数据挖掘在商业营销中的一个具体应用，用于解决商业决策的数据聚合度问题。它采集大量的点销售数据，其中零售企业（包括单体百货、超市、连锁和便利店等多种业态）这方面尤为突出，其信息量具有代表性。本文中所指的顾客是广义的，包括狭义顾客、供应商、员工和其他影响企业效用的外部因素。MIS系统、POS系统和CRM系统的集成应用，以及形形色色的会员卡、贵宾卡、金卡、银卡及优惠卡、打折卡等识别顾客身份的忠诚度卡片的使用，使得收集每一单独顾客的消费数据成为可能。 在目录分割问题中，企业想要定制目录发送给顾客，使得顾客能够了解企业的产品从而达到促销的效果。企业针对所有的顾客只制定

3、一个目录是不明智的，并非所有的顾客都关心同样的商品。企业出于成本的考虑也不能为每个顾客都制定一个目录。因此，企业通常将顾客划分为k个簇，针对每个簇制定相应的目录，使得企业能够获得最优的促销效果这样的问题是NP（Non-deterministic Polynomial）完全问题【1】。 从市场营销来说，从前的促销都是面向产品的促销，企业生产很少从顾客角度考虑。现在企业销售产品都是面向顾客的促销，即生产产品都是经过严格调研和顾客需要的产品。这种观念的转变使得企业在制定目录时也应该从顾客的角度出发，将顾客分成不同的顾客簇，制定面向不同顾客群的目录，使得目录在顾客簇上产生的效用最大。为了使得顾客能够对

4、接收的目录感兴趣，要求每个顾客对接收的目录至少有兴趣度t。这样使得目录分割问题变成了加入了兴趣度约束的目录分割问题，也称这样的问题是面向顾客的目录分割问题。 但是，面向顾客的目录分割数学模型具体应用到商业领域挖掘过程中还存在着一些不足，特别是大型商业企业要以承担风险和调节风险为代价，其本身具有高风险特征。因此，商业企业不仅仅会考虑顾客对产品的兴趣度，还会考虑其自身的风险系数，如果企业的风险系数过高，势必会影响其利润。对于商业企业来说，目录分割问题不仅仅是顾客的需求决定产品的促销，也应该是顾客与产品相互影响的过程。如何依据市场风险系数以及顾客兴趣度，给予客户适中、合理的目录是本文研究的重点。 本

5、文提出的基于兴趣度加权的BPF算法应用于实际案例中，希望能为这一领域提供有价值的研究成果，通过目录分割和商品搭配的结合应用于市场定位，为顾客群提供个性化的交互方式，向顾客簇散发具有最大效用的商品目录清单，进而满足最大化顾客的效用。将成为商业智能的重要组成部分。 2商品目录分割问题 商业智能的目录分割问题是基于单个企业效用的问题。假设一个企业对其顾客有充分的了解，即存在顾客数据库(customers DB)，使用双向图G表示，G=(P, C, E)，使用 表示集合的基数，且P=m，J=n。P是所有产品的集合，C是所有顾客的集合；E是边集，当且仅当存在顾客Ci对产品pj感兴趣时，存在对应边eij，

6、记做eij=(ci, pj)。 2.1 目录分割问题定义 定义1 分割问题【2】。设决策域D，n个顾客收益函数f1,fn和一个整数k，求D的k个子集S1,Sk，使得 （1） 容易证明，基本分割问题是NP完全问题【3】。 定义2 顾客覆盖。如果顾客Customeri对目录Catalogj中至少有一个产品感兴趣，称该目录覆盖了该顾客。 下面给出目录分割问题的定义。首先给出符号【2】，使用表示至少有一条边连接到P中的顶点C的顾客集合，即定义为： 定义3k目录分割问题【2】。给出使用二分图G=(P, C, E)表示的顾客数据库，且P=m，J=n，求P的k个子集P1,Pk，和其对应C的k个子集C1,Ck

7、，使得 （2） 对于任意i,j，当时不必为空 此时将顾客分成k个簇，每个顾客最多只能属于一个簇，每个簇对应的目录包含r个产品；而同一产品允许在多个产品簇中同时出现。 2.2 兴趣度约束的目录分割问题 上面提到的目录分割问题以最大化覆盖顾客数量为目的。但是实际上一旦顾客被目录所吸引，就会购买很多目录以外的产品。Ester等人【3】引入了最小兴趣度t，即在目录分割问题中加入兴趣度约束，使发送到顾客的产品目录至少有兴趣度t的顾客数量来测量顾客的整体效用。为形式化描述此问题，首先给出【3】的定义，表示至少有t条边连接到P中的顶点C的顾客集合，表示为 定义4 面向顾客的目录分割问题。 设存在顾客数据库G

8、:(P,C,E)，P=m，J=n，企业希望制定k个目录，每个目录包含r个商品，顾客对发送的目录中至少有t个感兴趣的产品，使得满足如下函数： （3） 3加权BPF目录分割算法 3.1 k-MECWT组合问题 Martin Estert针对商品目录分割引入了吸引顾客的最小兴趣度t概念，提出对商品感兴趣的商品目录至少达到一个指定兴趣度t的顾客数量，以此来衡量顾客整体的效用。为此文献【4】提出了多个面向顾客的商品目录分割方法，它们是：经典的组合问题MEC(Maximum Element Cover)、k-MEC和k-MECWT(k-Maximum Element Cover With t)。可以证明，

9、MEC方法是NP（Non-deterministic Polynomial）完全问题。k-MECWT方法是找到k个顾客簇，每个顾客簇用一组商品来描述，并且每个顾客被分配到具有最相似簇描述的那个簇，其前提是他们对于簇的描述要满足对簇的最小兴趣度t。经过简单的图灵转换，k-MECWT对于任意的k，t1时，同样是NP完全问题。 文献【4】提出的这些算法以客户数据库DB表示为基础，采用邻接表作为主要的数据结构：对于每种商品，相应的邻接表包括对这种商品感兴趣的所有顾客，表头记录列表中顾客的数量，扫描DB一次，在内存中将它转换为邻接表；每个顾客需要一个记数器表示需要被当前的商品目录吸引的额外的感兴趣的商品

10、的数量。算法的空间复杂度为o(E+C)=o(E)。 3.2爬山算法Naive 文献【5】提出了解决商品目录分割问题的简单爬山算法Naive，其基本思想是：首先依次选择支持度最高的前t个产品进入第1个目录；然后计算此时覆盖的顾客；然后每次在目录中添加一个产品，要求是在未选产品中选择一个能够使得覆盖增加的顾客最多的产品；直到第1个目录含有r个产品结束然后依次填充剩下的目录爬山算法虽然简单容易实现，但是实验效果很差。 3.3 朴素贪婪算法 文献【6】提出了用于面向顾客的商品目录分割问题的朴素贪婪算法，其基本思想是：每次通过为当前的商品目录选择最佳的下一个商品来构造商品目录，不考虑兴趣度阀值t，从剩余

11、的商品中选择对其感兴趣的顾客数量最多的商品作为下一个商品。由于面向顾客的商品目录分割问题的目标是最大化对商品目录中的至少一种商品有足够兴趣度t的全部顾客的数量，朴素的贪婪算法会产生资源的浪费：没有考虑兴趣度阀值t，会选择不能为当前商品目录带来新顾客的下一个商品。没有考虑兴趣度阀值t，会选择那些对商品目录中的商品的兴趣度永远达不到t的顾客所感兴趣的商品作为下一个商品。 3.4 改进的目录分割算法IW-BPF 3.4.1 BFP算法的提出 针对上述算法中的空间复杂度、实验效果以及资源问题，文献【7】提出了有效解决顾客商品目录分割的BPF（Best Product Fit）算法，其基本思想是：为了提

12、高顾客对目录中商品所感兴趣的商品优先权，根据对商品感兴趣的剩余顾客的数量和这些顾客需要感兴趣的当前商品目录中其它商品的数量，为每个商品赋予一个权值。 BPF算法： G=P,C,E； CustomersCovered=已经对一个商品目录的兴趣度达到t的所有顾客； :=C-CustomersCovered； Counter(c)=顾客c的计数器，初始化为t； 商品p的评分函数： （4） 评分函数包括两部分。第一部分代表所有对P感兴趣的剩余顾客的权值(顾客的权值是顾客计数器的倒数，权值越大、顾客对当前商品目录已经有的兴趣越大)。第二部分仅关注已经对当前商品目录中的至少一个商品P，感兴趣的顾客，并测量

13、这些顾客中有多少顾客对P感兴趣。为了优化性能，可以不考虑那些需要多于r-cat个商品才能被完全覆盖的顾客。选取评分函数值最大的商品P加入商品簇。 BPF算法的关键是确定商品P的评分函数，但它忽略了两个问题：评分函数的两部分在函数中所起的作用不均衡。第二部分没有考虑到对P的兴趣度。实际应用中，由于忽略了这两个问题可使一部分的作用淹没另一部分的作用，而只考虑了商品种类的差异而忽视了数量或利润的效用，由此导致聚簇的性能下降及不能最大化全部顾客的效用f(x)。 3.4.2 BPF算法的改进 为了发挥购买数量在商品及顾客聚簇中所起的作用，同时平衡评分函数各部分的地位，引入了顾客对商品的兴趣度加权值。要求

14、考虑人选商品时，在重视对此商品感兴趣的不同顾客量时要同时关注这些顾客对此类商品的交易量占总交易量的比重。 设顾客兴趣度为t，为商品P的交易集合，其中Cij代表一顾客，代表Cij对P的交易数量。顾客c对商品p的兴趣度为fc(p)，则评价函数修改为： 3.4.3IW-BPF算法描述 输入：客户关系数据库DB G=(P, C, E)。 k：商品目录分割个数。 r：每个商品目录区隔P的尺寸。 t：兴趣度阀值。 输出：k个商品目录和k个相应的顾客聚簇。 FOR i=1 to kDO FOR each pPDO Calculate Score(p); FOR j=l to rDO Add the Prod

15、uct p with largest Score(p) to Catalog i; For each c with(p, c)EDO Counter(c) := Counter(c)-1; Remove customers whose counter is 0 and recalculate Score(p) for all products P interesting to those customers; FOR each cCDO IF Counter(c)0 THEN Counter(c):=t; Return k clusters of customers with k catalo

16、gs 该算法每计算一次评分函数，只需遍历一次数据库，提高了算法的运算速度。其关键函数score(p)的 SQL代码如下： 输入：t_product(p)，t_customer(c)，t_c(e)，顾客簇编码(jc)，商品编码(sp)，商品簇(t_spjc) 输出：score(p) create or replace FUNCTION score_P(r number，jc numbersp varchar) RETURN number IS; v_countc number; v_gxd number; BEGIN select sum(1/b.countc) into v_conntc fr

17、om t_e a, t_customer b where a.gkbm = b.gkbm and b.countc 0 and spbm=sp; select sum(gxd) into v_gxd from t_e a where spbm=sp and exists(select gxd from t_e b where gkbm=a.gkbm and exists(select 1 from t_spjc where jcbm=jc and spbm=b.spbm); return(nvl(v_countc, 0)+nvl(v_gxd, 0); END； 3.4.4实验及结果分析 本文将

18、这一算法应用于某超市顾客交易数据（商品、数量）进行仿真实验，对比分析BPF和WBPF算法结果。假设该超市销售商品有Gl, G2, G3, G44种，会员顾客C1, C2, C3, C4, C5, C66个，表1列出了详细的顾客交易情况。 表1顾客交易数据 商品顾客C1C2C3C4C5C6G11111G21111G31111G41111如果采用BPF算法，簇长度取值3，顾客兴趣度取值2，生成的商品簇为G1, G2, G3。如采用IW-BPF算法，则生成的商品簇为Gl, G2, G4，顾客簇为C1, C2, C3, C4。IW-BPF算法生成的商品簇中商品G4替换了商品G3，其原因是IW-BPF中

19、引进了商品数量兴趣度权值，商品G4被顾客簇中的顾客总购买量要远大于商品G3，从而导致G4被选人到簇中来，这个结果正是我们所期望的。 4 结语 基于兴趣度加权的顾客商品目录分割问题作为商业智能的重要组成部分，有助于企业在激烈的市场竞争中做出有效、迅速的市场决策。应用IW-BFT算法实现商品目录分割问题，大大提高了市场定位的准确率，降低了促销成本。提高了商品销售量和顾客满意度。但是IW-BFT算法也有一定的局限性，如商品目录簇数目k能否动态定义，这是下一步要研究的内容。 参考文献： 【1】 Heikki MannilaTheoretical Frameworks for Data MiningAC

20、MSIGKDD Explorations Newsletter，2000,32(3):168-171 【2】 Jon Kleinberg, Chirstos Papadimitriou, Prabhakar Raghavan. Segmentation problems. Journal of the ACM, 2004,51(2)：263-280 【3】 M.Ester, R.Ge, W.Jin, eta1. A micro-economic data mining problem: Customer oriented catalog segmentation. The 10th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining, Seattie, WA, United States, 2004 【4】 Martin Ester，Rong Ge，Wen Jin et a1A Microeconomic Data Mining Problem：Customer Oriented Cata