搜索
，北京（100876）E-mail：boeagle@163.com摘要：中国打开国门以来，市场的重要性越来越为广大人民所深知。抓住市场就是要抓住客户，如何才能利用有限的资源最多的抓住客户成为人们最想解决的问题之一。数据挖掘的出现给了人们一条能够实现抓大放小的途径。本文正是利用数据挖掘中的决策树方法在客户分类方面做了一些尝试，期望在发现忠诚客户更有效利用企业资源上可以有所帮助。关键词：数据挖掘；决策树；客户关系管理；中图分类号：TP301.61引言改革开放以来，历经二十年的经济发展，中国的经济形态正逐渐由稀缺经济向过剩经济过度，但这种过剩是低层次的过剩，产品的技术差别很小，同质化现象很严重，企业习惯的营销思维仍是以产品的推销为主，一次又一次地祭起“价格战”的大旗，结果是消费者逐渐麻木，并开始怀疑产品的品质，同时又严重削弱了企业的资本积累、科研开发及后续发展的能力。21世纪，对于任何企业而言，有两个方面昀为重要，一是企业品牌，二是客户的满意度，但客户的满意和忠诚不是通过简单的削价可以换来，也不是通过折扣、积分等暂时的经济利益可以买来的，要靠数据库和客户关系管理（CRM）系统，从与客户的交流互动中更好地了解客户需求来实现。如果能够争得所有客户的忠诚固然是昀好的，但是随着客户的增多，就出现了两个不可回避的问题。一是留住客户所需要付出的边际成本在迅速上升，使得花费了巨大精力留住的客户带给企业的可能并不是利益而是负担；二是企业在一定时期内的资源是有限的，也就使得同时完全满足所有客户的要求变得不可能。如何才能在众多客户中区分关键客户、普通客户、垃圾客户并能及时发现那些忠诚度可能发生变化的客户并及时引导他们维持在有利于企业的方向上就显得非常关键了。下面就对利用决策树模型分类客户进行些简单的探讨。2决策树模型的基本理论决策树算法是一种以决策树这种数据结构为基础的分类算法[1,2]。决策树是一个类似于流程图的树结构，其中每个内部结点表示一个属性上的测试(该属性被称为测试属性或决策属性)，每个分枝代表一个测试输出，而每个树叶结点代表一个类或类分布。在给未知的样本分类时，由树根开始对该样本中对象的属性按照顺序逐个测试其值，并且沿着符合条件的分枝向下走，直至到达某个叶结点，这个叶结点代表的类则为该对象所属的类。，给出了客户的消费情况。这个例子假定是要按照客户是否购买电脑将客户进行分类。该客户集合中用来描述客户特征的属性有年龄，性别和月收入。每个内部结点（矩形框）代表客户的属性（例如有年龄，性别，月收入）；每个叶子结点（椭圆形框）代表该客户属于的类别（有买电脑和不买电脑两类）；每个分支代表该属性向下需要满足的条件（如年龄在15到35之间）。昀左下的叶子结点即表示：如果客户年龄在15到35之间，性别为女性，而月收入大于5000的时候，认为该客户会购买电脑。图1一棵简单的决策树2.1决策树的生成决策树生成的过程中，输入为训练样本数据集，决策树为昀终输出结果。决策树的每一个决策结点对应元组进行分类的一个决策属性(测试属性)，分枝对应着元组按该属性进一步划分的取值特征，叶子代表类或类的分布。首先，根据用户的实际需要选择类别标识属性和决策树的决策属性集，决策属性集是指在候选属性(除了类别标识属性之外的所有属性)中选择的属性集，然后开始构造决策树。决策树归纳的基本算法是贪心算法，是以自顶向下递归的各个击破的方式生成决策树。算法的基本步骤如下：z树以代表训练样本的单个结点开始（步骤1）。z如果样本都在同一个类，则该结点成为树叶，并对该类标号（步骤2和3）。z否则，选择一个属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。z对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。z算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。z递归划分步骤仅当下列条件之一成立停止：z给定结点的所有样本属于同一类（步骤2和3）。z没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替，可以存放结点样本的类分布。z分枝test_attribute=ja没有样本（步骤11）。在这种情况下，以samples中的多数类创建一个树叶（步骤12）。算法：Generate_decision_tree。由给定的训练数据产生一棵决策树。输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_list。输出：一棵决策树。ja方法：步骤1创建结点N；步骤2ifsamples都在同一个类Cthen步骤3returnN作为叶结点，以类C标记；步骤4ifattribut_list为空then步骤5returnN作为叶结点，标记为samples中昀普通的类；（也就是子集合中属于某个类个数昀多，就定义为某个类，）步骤6选择attribute_list中的属性test_attribute；步骤7标记结点N为test_attribute；步骤8foreachtest_attribute中的未知值ja步骤9由结点N长出一个条件为test_attribute=ja的分枝；步骤10设jS是samples中test_attribute=ja的样本的集合；步骤11ifjS为空then步骤12加上一个树叶，标记为samples中昀普通的类；步骤13else加上一个由Generate_decision_tree(jS,attribute_list–test_attribute)返回的结点；2.2决策属性的选择划分样本的属性的选择对于构造的决策树的质量极为关键。如图1中是先用年龄做划分还是先用性别做划分得到的决策树就极为不同。一般用统计度量来选择属性对结点进行划分的方法主要有：2.2.1信息增益(InformationGain)分类的目的是提取系统信息，使系统向更加有序、有规则组织的方向发展。1948年，香农(C.E.Shannon)提出了信息论[3]，定义熵(Entropy)作为衡量系统混乱程度的统计量，熵越大，系统越混乱。由此可见，昀佳的方案是使熵减少量昀大的划分方案，划分后熵的减少就是信息增益。因此，选择属性对结点进行划分的标准应该是选择信息增益昀大的属性。经典决策树分类算法ID3,C4.5就是使用信息增益作为选择属性对结点进行划分的指标。信息论中对信息量(Information)和熵(Entropy)的定义为[4]：)(log2ipnInformatio−=∑−=)(log2iippEnrtopy数据集划分前的熵：，其中分类属性C有m个不同的离散取值mccc,...,,21（即数据样本S昀终要被分成m个类别）。分类属性值为mccc,...,,21的样本数分别msss,...,,21。那么划分之前，样本集S的总熵(期望信息)为：∑=−=miiimppsssI1221)(log),...,,(其中，ip是S集中任意一个样本属于类别iC的概率，并用ssi估计。注意，对数函数以2为底，因为信息用二进制编码。容易看出，数据集S的总熵在划分前是属于不同类别的样本的信息量的加权平均。数据集划分后的熵：设属性A有v个不同的离散属性值{vaaa,...,,21}，可使用属性A将数据集S划分为v个子集{vsss,...,,21}，对应每个子集jS中所有样本的属性A都是ja。设子集jS中的全部样本数为js，其中分类属性值为mccc,...,,21的样本数为mjjjsss,...,,21，则子集jS的熵为：∑=−=miijijmjjjppsssI1221)(log),...,,(其中jijijssp=，是jS中样本分别属于类别iC的概率。使用属性A把数据集S划分成v个子集后，S的总熵为v个子集的熵的加权平均：∑=+⋅⋅⋅++=vjmjjjmjjjsssIssssAE12121),...,,()(其中ssssmjjj+⋅⋅⋅++21为Sj子集的权重，表示s，子集在数据集S中的比重。信息增益:信息增益表示系统由于分类获得的信息量，由系统熵的减少量度，定义数据集S按属性A划分后的信息增益为S划分前后的熵差：)(),...,,()(21AEsssIAGainm−=算法计算每个属性的信息增益，然后选择具有昀高信息增益的属性作为给定数据集S的决策属性，创建一个结点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。2.2.2基尼指数(GiniIndex)[5]如果决策树是二叉树，常用基尼指数作为选择决策属性的标准。数据样本集S的分类属性有m个不同的离散值个类别，那么基尼指数就是∑=−=miipSGini121)(其中ip是类别iC出现的概率。如果用属性A将S划分成两部分s1,s2。即这个划分的基尼指数就是：)Gini(s*)ss()Gini(s*)ss(Gini(S)2211+=执行划分时，选择基尼指数昀小的属性对结点数据样本进行划分。决策树是二叉树时，设属性有v个离散型取值，则属性A可有2v种划分S集的方法，其中一个划分方法的基尼指数昀小，称之为属性A的昀佳划分。在选择结点昀佳划分时，首先找出每个属性的昀佳划分方法，再比较所有属性的昀佳划分方法，昀后确定结点的昀佳划分。2.3数据预处理在现实应用中，我们的数据都是存放在大型数据库或者数据仓库中。而这些数据存在不完整性、含噪声和不一致性[6]。我们必须对此做出处理，以期得到我们生成决策树所需要的。出现不完整数据的原因可能有多种。可能只是因为输入时认为是不重要而没有输入，可能是由于理解错误或设备故障而未完成输入，也可能由于同其它记录的数据不一致而被删除。在进行数据挖掘时，不完整的数据，特别是某些属性上缺少值的元组可能需要进行推导。数据含噪声也可能有多种原因。收集数据的设备可能出现故障，人或设备在数据输入时可能出现错误，数据传输中可能出现错误，另外，也可能是由命名或所用的数据代码不一致而导致的。在进行数据挖掘时，含噪声的数据需要先进行清理。另外，由于数据往往来自多个数据源，不一致的数据也常常出现，在进行数据挖掘时，也要针对这一问题对数据进行清理。数据预处理的方法有[7]：数据清理：用于填充空缺的值，平滑数据，找出孤立点并纠正数据的不一致性。数据集成：将来自不同数据源的数据整合成一致的数据存储格式。元数据、相关分析、数据冲突检测和语义异种性的解析都有助于数据集成。数据变换：将数据变换成适于挖掘的形式。例如，数据属性可以规范化，使得它们可以落入小区间，如0.0到1.0。另外在用决策树方法进行分类时，由于计算信息增益或者基尼指数的需要，数值型属性要离散化[8]。2.4决策树的修剪在决策树分类算法中，除了分类的正确性是要首先考虑的因素外，决策树的简洁程度也是一个需要考虑的重要因素。因此要使用剪枝策略来简化决策树，并提高所提取的规则的可靠性。主要的剪枝方法有预剪枝和后剪枝，以及其他的处理方法。预剪枝，在预剪枝算法中，并不把每个叶子结点均为同一类时作为算法停止的条件，而是在建树的过程中终止树的建立以达到对树进行剪枝的目的。在这里，终止只是将该结点变成叶子结点，该结点可能包含训练子集中经常出现的类或这些样本的可能分布。后前枝，后剪枝是在决策树建立之后，对形成的决策树的分枝进行清理的过程。后剪枝算法有两种可能的剪枝策略，一种是自上而下的，一种是自下而上的。自下而上的算法是首先在昀底层的内部结点(即所有子结点都是叶子结点的内结点)开始剪枝，剪