企业CRM系统中决策树算法的应用

企业CRM系统中决策树算法的应用河北金融学院郭佳许明保定市科技局《基于数据挖掘的客户关系管理系统应用研究》09ZG009摘要：客户资源决定企业的核心竞争力，更多的关心自己的销售群体，并与之建立良好的、长期的客户关系，提升客户价值，对全面提升企业竞争能力和盈利能力具有重要作用。本文以某企业销售业绩为对象，利用决策树分类算法，得到支持决策，从而挖掘出理想客户。关键字：客户关系管理；数据挖掘；分类算法决策树分类是一种从无规则、无序的训练样本集合中推理出决策树表示形式的分类规则的方法。该方法采用自顶向下的比较方式，在决策树的内部结点进行属性值的比较，然后根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。本文主要研究决策树分类算法中ID3算法在企业CRM系统中的应用情况。1.ID3算法原理ID3算法是一种自顶向下的决策树生成算法，是一种根据熵减理论选择最优的描述属性的方法。该算法从树的根节点处的训练样本开始，选择一个属性来区分样本。对属性的每一个值产生一个分支。分支属性的样本子集被移到新生成的子节点上。这个算法递归地应用于每个子节点，直到一个节点上的所有样本都分区到某个类中。2.用于分类的训练数据源组数据挖掘的成功在很大程度上取决于数据的数量和质量。我们应从大量的企业客户数据中找到与分析问题有关的，具有代表性的样本数据子集。然后，进行数据预处理、分析，按问题要求对数据进行组合或增删生成新的变量，从而对问题状态进行有效描述。在本文研究的企业数据中，是将客户的年龄概化为“小于等于30”、“30到50之间”和“大于50”三个年龄段，分别代表青年、中年和老年客户，将产品价格分为高、中、低三档等，详见表1，将企业CRM系统数据库中销售及客户信息汇总为4个属性2个类别。4个属性是客户年龄段、文化程度、销售地区、产品档次，类别是销售业绩，分为好和差两类。表1训练样本集合attributeageeducationarealevelclass1=30HⅠlowbad2=30HⅠhighgood3=30HⅡmediumbad4=30HⅡhighgood5=30LⅠhighgood6=30LⅠlowgood7=30LⅡlowgood8=30MⅠhighgood9=30MⅠmediumgood10=30MⅡmediumgood11=30MⅠlowgood1231-51MⅠmediumgood1331-51MⅡmediumgood1431-51MⅠlowbad1531-51HⅠhighgood1631-51HⅠmediumgood1731-51HⅠlowgood1831-51HⅡhighbad1931-51HⅡlowbad2031-51LⅠhighgood2131-51LⅠlowgood2231-51MⅡhighbad2331-51MⅠhighgood2450MⅠhighbad2550MⅡhighbad2650MⅠmediumgood表2训练数据中各属性的说明属性说明age客户的年龄段education文化程度area业务销售地区（Ⅰ本地区，Ⅱ外地）level产品档次class销售状况3.ID3算法分类模型的建立由表1可知：类标号属性有两个不同的值，因此有两个不同的类（即m=2）设类C1对应于good，类C2对应于bad。类good有18个样本，类bad有8个样本。为了计算每个属性的信息增益，先使用miiimppsssI1221log,,,，所以初始信息熵为：I(s1,s2)=I(18,8)=268log2682618log2618227.1*26853.0*26181826log2681826log2618220.8905然后计算客户年龄、文化程度、产品档次和销售区域4个属性的熵。首先观察age属性的每个样本值的good、bad分布，分别计算每个分布的信息熵：当age=30：s11=9s21=2时，I(s11,s21)=-112log112119log11922当age在31-50间：s12=8s22=4时，I(s12,s22)=-124log124128log12822当age=50：s13=1s23=2时，I(s13,s23)=-32log3231log3122若按age划分样本，所需的信息熵为：E(age)=),(263),(2612),(2611231322122111ssIssIssI=0.8192类似的，可以得到：E(education)=)50log5055log55(265)124log124128log128(2612)94log9495log95(269222222=0.7669E(production)=)83log8385log85(268)71log7176log76(267)114log114117log117(2611222222=0.853E(area)=783.0)95log9594log94(269)173log1731714log1714(26172222通过以上属性，对当前分支节点进行相应样本集合划分，从而获得的信息增益分别为：Gain(age)=I(s1,s2)-E(age)=0.8905-0.8192=0.0713Gain(education)=I(s1,s2)-E(education)=0.8905-0.7769=0.1236Gain(production)=I(s1,s2)-E(production)=0.8905-0.853=0.0375Gain(area)=I(s1,s2)-E(area)=0.8905-0.783=0.1075Gain(equipment)=1.576-0.873=0.703从计算结果得到education属性具有最高信息增益，因此education属性成为决策树根节点的测试属性。如下图所示：图1决策树根节点的测试属性在样本集合中对education属性的3个取值进行分支，3个分支对应3个子集，分别为：P1＝{1,2,3,4,15,16,17,18,19}；P2＝{8,9,10,11,12,13,14,22,23,24,25,26}；P3={5,6,7,20,21}其中P3的样本都为good类，因此对应分支标记为good，P1、P2样本类别未定，所以需要对P1、P2子集分别递归调用ID3算法。在P1中可以求出剩下的age、production、area三个属性的信息增益。1I=30lowbad2I=30highgood3Ⅱ=30mediumbad4Ⅱ=30highgood15I31-50highgood16I31-50mediumgood17I31-50lowgood18Ⅱ31-50highbad19Ⅱ31-50lowbad8I=30highgood9I=30mediumgood10Ⅱ=30mediumgood11I=30lowgood12I31-50mediumgood13Ⅱ31-50mediumgood14I31-50lowbad22Ⅱ31-50highbad23I31-50highgood24I=50highbad25Ⅱ=50highbad26I=50mediumgood5I=30highgood6I=30lowgood7Ⅱ=30lowgood20Ⅱ=30highgood21I31-50lowgoodeducationHML992.094log9495log95),(2221ssI985.0)52log5253log53(95)42log4242log42(94)(2222ageE007.0)(),()(21ageEssIageGain889.0)41log4143log43(94)21log2121log21(92)32log3231log31(93)(222222productionE103.0)(),()(21productionEssIproductionGain762.0)43log4341log41(94)51log5154log54(95)(2222areaE23.0)(),()(21areaEssIareaGain因为area属性的信息增益最大，所以把属性area作为该分支的节点，再向下分支，P2处理类似，最后得到的决策树如下图所示：图2经数据分类生成的决策树因此，对于样本X=(age=“31-50”,education=“low”,level=“medium”,area=“I”)，ID3算法分类预测其class为good。4.决策树的生成productionhighlowgoodbad=3031-50goodageareaIⅡ31-50=30badageproductionmediumhighbadgoodeducationHMLgood=3050badagegood31-50areaIⅡgoodbadgoodproductionmediumhighlow=3031-50badagegood决策树的建立是决策树分类的基础，以ID3算法为例说明建立决策树的过程。在决策树的递归构造过程中，在树的节点上利用特征的信息增益大小作为分支属性选择的依据，选择信息增益最大的特征作为分支属性。ID3算法描述简单，分类速度快，适合于大规模数据的处理，具体算法描述如下所示。输入：训练样本samples,候选属性集合attribute_list输出：一棵决策树首先创建节点N，ifsamples都在同一个类Cthen返回N作为叶节点，以类C标记；ifattribute_list为空then返回N作为叶节点，标记为samples中最普遍的类，选择attribute_list中具有最高信息增益的属性branch_attribute，标记节点N为branch_attribute；遍历foreachbranch_attribute中已知的值ai，由节点N长出一个条件为branch_attribute=ai的分支，设si是samples中branch_attribute=ai的样本集合，若si为空then加上一个树叶，标记为samples中最普遍的类，否则else加上一个由generate_decision(si,attribute_list-branch_attribute)返回的节点该算法中属性的度量标准是在树的每个节点上使用信息增益度量选择分支属性。这种度量选择具有最高信息增益的属性作为当前节点的分支属性。该属性使得对结果划分的样本分类所需的信息量最小。算法的伪代码描述如下所示。Generate_Decision_Tree(Samples,usable-attribute-list,C){createanewnodeN；if(allSamplesinNareintheclassC){returnNasaleafNodelabledwith1astheprobabilityofclassC;}selecttest-attribute,theattributeamongattribute-listwiththehighestinformationgain;labelnodeNwithtest-attributeandprobabilityofsamplesinclassC;foreachknownvalueaioftest-attribute{letsibethesetofsamplesinsamplesforwhichtest-attribute=ai;if(!(siisempty)){growabranchfromnodeNfortheconditiontest-attribute=ai;attachthenodeN-newreturnedbyGenerate_Decision_Tree(Si,attribute-list-test-a