基于RFM购买树的客户分群
2017-06-15张文斌黄哲学陈小军
明 勇，张文斌，黄哲学，陈小军
深圳大学计算机与软件学院，广东深圳518060
【电子与信息科学 / Electronic and Information Science】
基于RFM购买树的客户分群
明 勇，张文斌，黄哲学，陈小军
深圳大学计算机与软件学院，广东深圳518060
针对通过零售交易数据进行客户分群时传统方法未考虑商品的价值问题，提出用RFM(recency frequency monetary)表达交易数据的方法，该方法将客户购买的商品和商品类别组成一棵RFM购买树(recency frequency monetary purchase tree，RFMPT).提出基于RFM购买树的快速聚类算法(based recency frequency monetary purchase tree clustering，BRFMPTC)，把购买树构建为CoverTree(CT)索引结构，利用CT结构快速选择k个密度最大的购买树作为中心，将其他对象划分到距它最近的类中心. 实验结果表明，在距离加权下，BRFMPTC算法较传统算法在整体上能产生质量更高的聚类结果，性能得到较大提升.
计算机感知；零售数据；客户分群；RFM购买树；聚类；覆盖树；Dunn指数
客户分群在客户关系管理中起着关键性的作用[1]，它将客户划分成许多组，同组客户有相似的喜好和购买行为．企业可根据不同客户群的购买行为，采取针对性的营销策略．聚类是客户分群常采用的技术，其目的是根据客户的属性将客户分组．常用的属性包括性别、年龄、职业、爱好和收入等客户基本信息[2-3]．但是，这些属性数据存在不准确和不完整等问题[4]，且这些静态数据不能反映客户购买行为[5]，无法按客户的购买喜好进行分群，不满足营销应用需求．
基于零售交易数据的客户分群是当前研究的热点[6]．Zalaghi等[7-8]将客户购买的商品表示成矩阵，并用k-means方法进行客户分群．Hsu等[9]提出通过层次聚类法对客户进行分群，但该方法计算复杂度高．蔡玖琳等[10]提出基于聚类的多指标客户细分方法．陈小军等[11]提出用购买树表示零售数据并用于客户分群．以上方法仅考虑客户购买的商品，并未考虑商品的价值．
在客户关系管理模式中，基于RFM(recency frequency monetary)客户细分是一种统计划分的方法，该方法用R表示每个客户在一定时期内最近一次购买的时间，用F表示购买商品的次数，用M表示购买商品的总金额，然后加权计算得到RFM得分，进而对客户按得分进行分组．但这样的划分并未考虑同组客户购买商品的差异性，在大量客户的情况下，分组非常粗糙．为此，本研究提出一种基于RFM购买树的表达方法来表达交易数据的客户分群方法．在该方法中，统计每个客户购买每种商品的RFM值，根据客户购买的商品和商品类别建成一棵RFM购买树，树的叶子节点表示商品，内部节点表示商品类别，商品节点和商品类别节点都带有RFM值，通过定义RFM购买树之间的相似度计算方法，提出基于RFM购买树的快速聚类算法(basedRFMpurchasetreeclustering，BRFMPTC)．结果表明，在距离加权下，采用BRFMPTC算法比传统算法能获得更好的聚类效果，效率有大幅提升．
1 RFM购买树表达及相似度计算
1.1 交易数据
设D={R1,R2, …,Rm}是所有交易记录的集合，Ri为数据库中一条交易记录，其中1≤i≤m．R={TID,timestamp,vipID,item}，这里，TID为交易记录在D中唯一标识；timestamp为购买商品的时间；vipID为客户唯一标识；item为商品项．在超市或商场内，商品项都超过十万种，若采用传统矩阵方法表示数据，列表示商品项，显然不可取，因为这样表示的矩阵维度超过十万维，且矩阵非常稀疏，浪费存储空间．
本研究拟用RFM购买树表达客户交易数据，设T={t1,t2, …,tn}是从D中抽取出某客户的一组交易记录，对应商品项是i1,i2, …,in， 表示成树状结构PT={vipID,
1.2 RFM购买树表达方法
统计每个客户购买每种商品中的R、F和M值后构建RFM购买树．RFM购买树是某个客户购买商品和RFM值集合的树状表达，所有客户购买商品和购买频率的集合表达称为商品树．设φ为购买树，Ψ为商品树，Fv(φ)为φ中节点v的RFM值，则φ是Ψ的子集，即节点N(φ)⊂N(Ψ)， 边E(φ)⊂E(Ψ)， 节点是一个商品名称和RFM值的结构体．从RFM购买树根节点Root(φ)到任意一个叶节点v⊂N(φ)的路径，可在商品树Ψ中找到同样一条路径．购买树由客户交易数据产生，通过遍历购买树可查找客户具体购买的商品．图1为某客户的RFM购买树，该购买树有5层，叶子层为客户具体购买的商品，内部节点表示层次类别信息，如手机属于个人数码类别，其父节点即为个人数码．每个节点中的三元组表示RFM值，如个人数码节点中(50,2,5998.00)的50为最近一次购买距离分析点的时间(单位：d)，2为购买商品次数，5998.00为购买商品的总金额(单位：元)．
图1 RFM购买树示意图Fig.1 A sample of RFM purchase tree
1.3 RFM购买树生成算法
给定某客户的m条交易记录R={r1,r2, …,rm}， 扫描R中每条交易记录，提取每条记录中的经营小类、商品种类、商品小类和商品品牌等信息，依次插入RFM购买树φ中．各节点的RFM值计算方法为：以季度为滑动窗口统计出该商品的购买次数、金额和最后一次购买距分析点的时间，并统计出φ中各叶节点的RFM值．内部节点的RFM值是其子节点RFM值的累加和，再根据商品树中记录的各节点的最大RFM值对购买树节点RFM值进行归一化处理．φ的第1层为根节点，第2层到倒数第2层分别表示商品大类、中类、小类和品牌等层次信息，叶子层表示具体的商品．从交易记录中生成购买树的算法CreateRFMPurTree()代码如图2．
图2 CreateRFMPurTree算法
Fig.2 CreateRFMPurTree algorithm
1.4 RFM购买树相似度计算
对规模为n的购买树集合Ф={φ1,φ2,…,φn}， 设H(Φ)为购买树的高度， Root(φ)为购买树的根节点，Fv(φi)为RFM购买树φi中节点v的RFM值，Nl(φi)为购买树φi中第l层的所有节点．交易数据一般维度很高，采用欧式距离计算复杂度较高，且欧式距离更多体现的是数值的绝对差异．因此，本研究采用余弦距离，则φi与φj在节点v的余弦距离为
(1)
层次间的距离指两颗购买树在相同层的距离，由该层所有节点间的余弦距离加权求和，即
(2)
其中，l为购买树的层次， 1≤l≤H(φ)；βv是节点v的权重，对于根节点，βv=1， 对于其他节点，βv的值是其父节点的值除以该父节点拥有的子节点数目δv(φi,φj)．
RFM购买树之间的距离对应购买树层次距离的累积和，为调节某层距离在购买树距离中的比例，引入权重系数ωl， 则购买树φi和φj的距离为
(3)
表示从购买树第1层到第H(Ф)层的各层距离加权．其中，ωl表示第l层的权值，权值越大的层在购买树中占的比例越大，所有层的权值之和为1．
设r为相邻层之间系数的倍数，则ωl的值可通过r来控制，即ωl=rωl-1．
根据RFM购买树的距离定义，客户i和客户j购买树的相似度为
(4)
2 基于RFM购买树表达的聚类算法
客户分群需先用层次索引树(CoverTree,CT)将所有RFM购买树构建为CT结构，用于快速近邻查找，然后在CT中找到类初始中心所在的层，计算位于该层的RFM购买树对象的密度，作为类初始化中心，最后，将其他RFM购买树划分到距离最近的中心．
2.1 CT结构
CT是由Beygelzimer提出[12]的分层次的索引树，结构如图3．
图3 CoverTree示意图[12]Fig.3 A sample of CoverTree[12]
由图3可见，CT的每层有个索引，且随着树的生长而减小，用Ci表示集合S中与CT第i层相关联的对象集合，CT的每个节点和集合S的一个对象关联，S中的每个对象可能和CT多个节点关联，但每层只出现1次．CT具有以下特性：
1)嵌套性.Ci∈Ci-1， 表示若一个对象P∈S出现在第i层，则第i层以下每层都有一个节点与P关联．
2)覆盖性.对于第i-1层中的每个对象p∈Ci-1， 在第i层都存在一个对象q∈Ci， 使d(p,q)<2i． 同时，与q关联的节点为i-1层与p关联的节点的父节点．
3)分离性.对于每层中任何两个相异节点所关联的对象p,q∈Ci， 且p≠q，d(p,q)<2i．
把购买树集合构建为一棵CT索引结构树，用于快速近邻查找．设购买树集合为Ф={φ1,φ2, …,φn}， 根据CT的性质，依次将φi(1≤i≤n)插入CT，任意两棵购买树之间的距离d(φp,φq)∈[0,1]． 根据CT分离性易知最顶层仅1个购买树Ct， 其余都是Ct的后代，对于n个购买树对象，创建CT的时间复杂度为O(nlg(n))．
2.2 密度估计
在进行聚类时，需计算CT结构中某一层节点所关联的购买树的密度，并根据计算结果找出聚类的初始中心，再将其他购买树依次分配到相应的聚类中心．设p为任意购买树，其密度为
(5)
其中，q为除p外的其他购买树．购买树p的密度就是第l层中与p的距离小于等于2l的购买树个数．计算p的密度算法EstimateDensity()如图4．
图4 EstimateDensity算法
Fig.4 EstimateDensity algorithm
2.3 聚 类
对给定的n棵RFM购买树Ф={φ1,φ2, …,φn}， 先构建CT结构．将n棵RFM购买树分成k类，从CT中找到某层对象个数大于k的层数i， 根据CT的分离性，第i层任意两个不同的RFM购买树p和q的距离d(p,q)>2i， 以2来衡量这k个初始中心的相互距离，用EstimateDensity()计算该层所有RFM购买树的密度，选择密度最大的k个RFM购买树作为初始中心，再将剩余的每个客户划分到距它最近的类初始中心，整个过程的时间复杂度为O(nlg(n))， 聚类算法BRFMPTC()如图5．
图5 BRFMPTC算法
Fig.5 BRFMPTC algorithm
3 结果与分析
为检验基于RFM购买树表达交易数据的聚类算法的有效性，采用真实数据对效果和性能进行验证．数据源自国内某大型连锁超市的实际交易记录数据，共3 073 886条交易记录，76 419个vip号(vipID数目)．该超市的商品结构分为4层，从高到低依次是经营小类、商品中类、商品小类和商品．为便于分析，将数据分成10个数据集，用平均稀疏度描述购买树不同层中节点分布情况，则第l层平均稀疏度定义为
(6)
其中，φi为第i棵RFM购买树； Ф为n棵购买树的集合；Nl(φi)为RFM购买树φi第l层的节点．由CreateRFMPurTree()生成的10个数据集D1,D2, …,D10的大小和平均稀疏度如表1．
表1 各数据集大小和平均稀疏度
实验所用计算机配置为Inter(R) Core(TM)i5-4590CPU@3.30Hz，12 G内存，Win10操作系统．为评估BRFMPTC算法效果，选择层次聚类算法(hierarchical clustering algorithm, HAC)[13]、基于密度的聚类算法(density-based spatial clustering of application with noise, DBSCAN)[14]和模型聚类算法谱聚类(spectral clustering)[15]做为比较算法(k-means算法因不能处理树形结构数据，不参与比较)，选择聚类的紧凑度评价指标和Dunn指数(Dunnindex,DI)进行对比参数．
本实验要进行不同参数的多组计算，指标评价在大小适度的数据集D5中进行，该数据集含有3 198 个vipID．紧凑度评价标准定义为
(7)
其中，P1,P2，…，Pk表示聚成的k个簇结果．
图6展示了r取1、500和1 000时，BRFMPTC算法、单连接层次聚类算法(HAC-single)、全连接层次聚类算法(HAC-complete)、DBSCAN算法和Spectral算法在不同聚类簇数下的lg(W(k))值．从每幅图内部来看，随着聚类簇数的增加，各算法计算得到的lg(W(k))不断减小， lg(W(k))值越小表示紧凑度越高，聚类效果好，因为随着划分簇数的增多，原来紧凑度不高的一个大簇会被划分几个较小的簇，而这些小簇紧凑度较高．可见，无论r取1和500还是1 000，BRFMPTC算法的lg(W(k))值普遍比其他算法低，紧凑度更高，说明BRFMPTC算法聚类效果更好．
图6 不同k下各算法lg(W(k))值Fig.6 (Color online) lg(W(k)) of each algorithm under different k
DI指用任意簇间最小距离除以任意簇内最大距离来评价聚类效果，如式(8)，其中Ci(1≤i≤k)为聚成的第i个簇．在聚类中，任意簇间最小距离越大，说明各簇有越好的分离性，任意簇内距离的最大距离越小，说明簇内越紧密，因此DI值越大越好．
(8)
图7 各算法在不同r和k下的DI值Fig.7 (Color online) The DI value of each algorithm in different r and k
图7为r分别取1、500和1 000时，各算法在不同聚类簇数k下的DI值．从图7可见，r=1 000时，DI值比较大，在各算法对比中，BRFMPTC算法得到的DI值普遍高于其他算法．
对于n个RFM购买树对象，本研究提出的BRFMPTC算法构建CoverTree结构和聚类过程，时间复杂度都是O(nlg(n))， 所以BRFMPTC算法时间为O(nlg(n))．HAC算法在进行每次迭代的时候要计算与其他所有对象的距离，时间复杂度为O(n2)．DBSCAN算法需要将若干个核心点相关联的边界点分派到最近的核心点，时间复杂度也为O(n2)．Spectral算法需要构造数据对象的相似矩阵和对应的Laplacian矩阵，Laplacian矩阵分解是立方级的复杂度．在表1的10个不同大小的数据集上运行各算法，得到各算法总运行时间如图8．从中可见，BRFMPTC算法运行时间比其他算法更短，仅用BRFMPTC算法测出了所有数据集的运行时间，spectralclustering算法在D7数据集上的运行时间已经非常大了．
图8 各算法在数据集D1到D10上的运行时间Fig.8 (Color online) The execution time of each algorithm
结 语
针对基于零售交易数据进行客户分群的传统方法存在的问题，提出将客户交易数据用RFM购买树表达，并基于该表达方法和相似度计算提出快速聚类算法BRFMPTC．实验结果表明，在距离加权下，BRFMPTC算法比传统算法聚类的效果更好．下一步，将基于该聚类方法开发一个客户分群系统，以期提高客户零售数据分析挖掘的效率，降低数据处理分析的成本．
/ References：
[1] Natchiar S U, Baulkani S. Customer relationship management classification using data mining techniques[C]// International Conference on Science Engineering and Management Research. Dubai: IEEE, 2014:e18.
[2] Chattopadhyay M, Dan P K, Mazumdar S, et al. Application of neural network in market segmentation: areview on recent trends[J]. Management Science Letters, 2012, 2(2):425-438.
[3] Chen Muchen, Chao Chuangmin, Wu Kuanting. Pattern filtering and classification for market basket analysis with profit-based measures[J]. Expert Systems, 2012, 29(2):170-182.
[4] Böttcher M,Spott M,Nauck D, et al. Mining changing customer segments in dynamic markets[J]. Expert Systems with Applications: An International Journal, 2009,36(1):155-164.
[5] Müller H, Hamm U. Stability of market segmentation with cluster analysis:a methodological approach[J]. Food Quality and Preference, 2014, 34(2):70-78.
[6] Singh A, Rumantir G, South A, et al. Clustering experiments on big transaction data for market segmentation[C]// Proceedings of the 2014 International Conference on Big Data Science and Computing. New York, USA: ACM, 2014:1-7.
[7] Zalaghi Z, Varzi Y A. Measuring customer loyalty using an extended RFM and clustering technique[J]. Management Science Letters, 2014, 4(5): 905-912.
[8] 李 刚，张 莉，李纯青．交易数据的百货商场客户细分研究[J]．西安工业大学学报, 2014(3):216-220． Li Gang, Zhang Li, Li Chunqing. Research on customer segmentation with transaction data of a department store[J]. Journal of Xi’an Technological University,2014(3):216-220.(in Chinese)
[9] Hsu F M,Lu Lipang,Lin Chunmin. Segmenting customers by transaction data with concept hierarchy[J]. Expert Systems with Applications: an International Journal,2012,39(6):6221-6228.
[10] 蔡玖琳，张 磊，张秋三．一种基于数据挖掘的零售业客户细分方法研究[J]．重庆工商大学学报自然科学版， 2015，32(2)：43-48． Cai Jiulin, Zhang Lei, Zhang Qiusan. Research on customer segmentation method in retail industry based on data mining[J]. Journal of Chongqing Technology and Business University Natural Sciences Edition, 2015, 32(2):43-48.(in Chinese)
[11] Chen Xiaojun，Huang Joshua，Luo Jun.PurTreeClust: a purchase tree clustering algorithm for large-scale customer transaction data[C]// IEEE 32nd International Conference on Data Engineering. Helsinki: IEEE, 2016:661-672.
[12] Beygelzimer A, Kakade S, Langford J. Cover trees for nearest neighbor[C]// Proceedings of the 23rd Inter-national Conference on Machine Learning.Pittsburgh, USA: ACM, 2010:97-104.
[13] Hall M, Frank E, Holmes G, et al. The WEKA data mining software: an update[J]. ACMSIGKDD Explorations Newsletter, 2009, 11(1):10-18.
[14] Sander J, Ester M, Kriegel H P, et al. Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2):169-194.
[15] Ng A Y, Jordan M I, Weiss Y. On spectral clustering: analysis and an algorithm[J]. Proceedings of Advances in Neural Information Processing Systems, 2002, 14:849-856.
【中文责编：英 子；英文责编：子 兰】
2016-11-07；Accepted：2017-02-27
Professor Huang Zhexue．E-mail:zx.huang@szu.edu.cn
Customer segmentation based on RFM purchase tree
Ming Yong, Zhang Wenbin, Huang Zhexue, and Chen Xiaojun
College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, Guangdong Province, P.R.China
In order to solve the problem that the value of goods has not been considered in traditional methods of customer segmentation, we propose a method of using the recency frequency monetary purchase tree (RFMPT) to represent transaction data, in which a RFM purchase tree is built based on the category of the goods.Based on the RFM purchase tree,we propose a fast clustering algorithm named based recency frequency monetary purchase tree clustering (BRFMPTC). This algorithm constructs the purchase tree as a CoverTree(CT) index structure. With this structure, we can quickly select thekdensestpurchasetreesasclustercenters,thendividetheotherobjectsintothenearestclasscenter.Theexperimentalresultsshowthattheperformanceoftheproposedmethodwithdistanceweightingisbetterthanthatofthetraditionalclusteringalgorithms.
computer perception; transaction data; customer segmentation; recency frequency monetary purchase tree; cluster; CoverTree; Dunn index
：Ming Yong, Zhang Wenbin, Huang Zhexue, et al. Customer segmentation based on RFM purchase tree[J]. Journal of Shenzhen University Science and Engineering, 2017, 34(3): 306-312.(in Chinese)
国家自然科学基金资助项目(61305059)；深圳大学青年教师科研启动资助项目(201432)
明 勇(1989—)，男，深圳大学硕士研究生．研究方向：数据挖掘．E-mail:13760182207@163.com
K921/927；TP
A
10.3724/SP.J.1249.2017.03306
Foundation：National Natural Science Foundation of China (61305059); Natural Science Foundation of Shenzhen University (201432)
引 文：明 勇，张文斌，黄哲学，等．基于RFM购买树的客户分群[J]. 深圳大学学报理工版，2017，34(3)：306-312.
