一种基于决策树改进算法的客户关系管理

严 熙

摘 要:针对决策树的经典算法(ID3)计算比较复杂的问题,提出利用条件概率等知识来改进决策树的构造。分别利用这两种方法建立客户关系管理模型,并根据结果发现,改进后的方法在计算效率方面有所提高。

关键词:CRM;ID3;条件概率;数据描述

中图分类号:TP311.5文献标识码:A

文章编号:1004-373X(2009)20-134-03

Advanced Algorithm Based on Calculation of ID3 in CRM

YAN Xi

(Jiangsu University of Science and Technology,Zhenjiang,212003,China)

Abstract:For the reason of that the calculation of ID3 is complex,an advanced way referring condition probability and other knowledge to improve the structure of the decision tree is proposed.These two methods are used to build two CRM models,the results show that advanced way really improved the efficiency of calculation.

Keywords:CRM;ID3;condition probability;data description

0 引 言

客户关系管理(Customer Relationship Management,CRM)起源于西方的市场营销理论。近年来,信息技术的长足发展为市场营销管理理念的普及和应用开辟了广阔的空间。以客户为中心,视客户为资源,通过客户关怀实现客户满意度。客户对企业的好感和忠诚不仅来自于企业提供的商品,更来自于服务和经验等非实体因素。企业要了解客户的喜好,管理每一个客户的关系,从每个客户身上获取最大利润,降低市场营销费用,并减少由于客户离去和无效的营销策略产生的浪费。用客户关系管理的方法,即CRM方法可以使这些希望成为现实[1-4]。而数据挖掘方法可以从客户数据库中挖掘出有价值的信息,并且这些信息可以处理已有的和潜在的客户关系,企业可以不断改善适合每个客户的个性化服务。

数据挖掘是一门广义的交叉学科[5],融合了数据库、数理统计、机器学习、人工智能、高性能计算、可视化等多个领域的理论和技术,是一个利用各种分析工具在海量数据中发现模型和数据之间关系的过程。使用这种模型和关系可以进行预测,它帮助决策者寻找数据之间潜在的关联,发现被忽略的因素,因而被认为是解决当前数据爆炸时代所面临信息贫乏问题的一种有效方法。

1 数据的描述与分析

客户关系管理主要的目标是将客户分成两类:只签订一张订单的客户和签订多张订单的客户。二值变量(用Y表示)可以用变量Total Number of Orders推导出。设定当Total Number of Orders等于1时,Y=0,表示客户不忠诚;当Total Number of Orders大于1时,Y=1,表示客户忠诚。根据经验,探索性变量的选取如下:

Instalment:表示第一次购买是否是分期付款的二值变量,使用分期付款为1,未使用分期付款为0。它表示客户和企业保持联系的时间长短。如果一个人使用分期付款,与企业的合同就会延长一些时间;

First Amount Spent:表示客户第一次购物所花费的金额是否是可观的二值变量,如果第一次购物的金额大于或等于300 000美元,则令其为1,否则为0;

Number of Products at first Order(Numb):表示客户第一次购物的数量是否是可观的二值变量,如果第一次购物的数量大于或等于6件,则令其为1,否则为0;

Age:如果客户的年龄小于或等于50岁,则Age取值为1,否则为0;

Area of Residence:客户所在地域位于北部到中部,则Area of Residence取值为0,客户所在地域位于中部到南部,则Area of Residence取值为1。

2 建立客户关系管理模型

管户关系是一个分类问题,响应变量是二值变量,目标是将客户分成不忠诚和忠诚两类。分别应用ID3方法和改进的方法建立客户分类模型。

2.1 ID 3算法

设训练实例集为X,将其分为n类,记为C={X1,X2,…,Xn},设第i类训练实例的个数是|Xi|,实例集X中的训练实例个数为|X|。若记一个实例属于第i类的概率为P(Xi),则决策树划分C的不确定程度为H(X,C),可简记为H(X),且:

H(X)=-∑P(Xi)log2[P(Xi)](1)

选择测试属性A进行测试。设A具有性质a1,a2,…,al,在A=aj的情况下,属于第i类的实例个数为|Xij|,A=aj的实例个数为|Xj|。记P(Xi|A=aj)为A取aj时属于第i类的概率,则有P(Xi|A=aj)=|Xij|/|Xj|,设Yi为A=aj时的实例集,此时决策树对划分类的不确定程度就是实例集对属性A的条件熵为:

H(X|A)=∑jP(A=aj)H(Yj)=

-∑i∑jP(A=aj)P(Xi|A=aj)•

log2[P(Xi|A=aj)](2)

属性A对于分类提供的信息量,即属性A的信息增益I(A)为:

I(A)=H(X)-H(X|A)(3)

ID3算法就是以I(A)作为测试属性的选取标准,分割训练实例集最终生成的决策树。样本各节点处的最大信息增益熵见表1,生成的决策树见图1。

表1 ID3算法结点处的最大信息增益熵

结点名称 最大信息增益熵结点名称 最大信息增益熵

结点1-10.731 0结点1-50.111 5

结点1-20.263 1结点1-60.001 7

结点1-30.800 1结点1-70.271 9

结点1-40.659 7

2.2 改进的算法

ID3算法是把信息熵作为选择测试属性的标准,即树结点的选择策略,但在计算基于属性的信息熵时,公式比较复杂,计算量较大,相应的复杂度也高。在对于实例集中的每一个属性,所提供的信息量是具有一定规律的,特别是当某个属性发生时,其某例别结果发生的条件概率提供给属性对某例的信息量,基于这个原因,可以考虑采用属性对某例的条件概率提供的分类信息量构造决策树。

ID3算法是通过最大信息增益值选择测试属性,改进的算法是通过最大条件概率值选择测试属性。

图1 ID3生成的决策树

根据概率统计知识,设事件为A,B,称P(B|A)为事件A发生时事件B会发生的概率,并称这个条件概率P(B|A)为训练实例集A发生后,事件B对训练集中某例别的影响度。

P(B|A)=P(AB)/P(A)(4)

对于实例集中的各个属性,首先计算所有属性值的影响度,然后进行比较可知影响度越大的属性值对应的属性所提供分类的信息量越大。依次比较,就可以确定属性对分类的影响程度的大小,因此可以根据此大小来构造决策树的生成算法。

具体算法如下:

Advanced Tree

Input:Attributes and Data

Output:A Tree

Start

W=An example

if W belong to a class X then

return N as a leave X

if attribute =NULL then

return N as a leave

for W do

for each attribute of class X do

利用公式(3)计算出attribute中具有最大条件概率值的属性max attribute

V= max attribute//具有最大条件概率值的样本集合

end for

end for

for each ai of max attribute do

grow a branch

end for

if V=Null then

add a leave

else 递归执行算法Advanced Tree

End

该实验中所使用的样本数据集按类别可分为不忠诚和忠诚两类,分别记为C1和C2。P(1|Instalment)表示第一次购买使用分期付款的事件发生的概率;P(C1,1|Instalment)表示为第一次购买使用分期付款,且类别为C1的事件发生的概率;PC11|Instalment为第一次购买使用分期付款,且类别为C1的条件概率,其余类推。根据式(4)可以得到每个属性对分类为C1的影响度,根据计算可得样本各结点处最大条件的概率见表2。

表2 改进算法结点处划分的最大条件概率值

结点名称最大条件概率值

结点2-10.457 1

结点2-20.046 0

结点2-30.142 9

结点2-40.714 3

生成的树如图2所示。

图2 改进算法生成的决策树

3 比较模型与分析

使用ID3算法生成的决策树有7个结点和8片叶子,使用改进后的算法生成的决策树有4个结点和5片叶子,减少了Area of Residence这一属性,简化了决策过程,直接把属性值和类别结果相联系,降低了计算的复杂性,提高了计算效率。

4 结 语

这里分别使用ID3算法和改进算法对客户关系管理进行研究。实验结果表明,改进的算法可以提高决策效率。利用这种方法对客户关系进行管理,可全面掌握客户偏好和客户信息,了解客户的需求和信用风险,可以更有针对性地开发和选择金融产品,制定正确的营销服务策略,将信息流的控制能力和快速反应能力转化成竞争力,提高客户满意度,从而形成企业的核心竞争力。

参考文献

[1]Alex Berson,Stephen Smith,Kurt Thearling.构建面向CRM的数据挖掘应用[M].贺奇,郑岩,魏藜,等译.北京:人民邮电出版社,2001.

[2]戴艳红,贺红燕.数据挖掘技术在客户关系管理中的应用研究[J].商场现代化,2006(34):350-351.

[3]何祖银,李静,马宏伟.面向CRM的数据挖掘应用[J].物流科技,2006(9):73-75.

[4]张新香.决策树挖掘在CRM中的应用[J].电脑开发与应用,2007(4):52-54.

[5]黄晓芳.数据挖掘中决策树算法及其应用[J].兵工自动化,2005(2):35-36.

[6]Wang X Z,Chen B,Qian G L,et al.On the Optimization of Fuzzy Decision Trees[J].Fuzzy Sets and Systems,2000,112:117-125.

[7]张桂杰,王帅.决策树分类ID3算法研究[J].吉林师范大学学报:自然科学版,2008(3):136-137.

[8]郭玉滨.决策树算法研究综述[J].电脑知识与技术,2006(2):155-156.

[9]庞哈利,高政威,左军伟,等.基于变精度粗糙集的分类决策树构造方法[J].系统工程与电子技术,2008(11):2 160-2 163.

[10]白雪,段富.决策树分类算法的研究及其在教学评估中的应用[J].电脑开发与应用,2007(2):24-26.