基于聚类提取训练集的预测分析

杨怀珍，李玲华

（桂林电子科技大学 管理学院，广西 桂林 541004）

0 引言

在决策树研究应用中，有学者侧重于研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系，即着重于产生决策树的数据。众所周知，数据挖掘中的原始数据集通常存在以下问题：属性值不完整；多数据源集合造成的数据定义、内涵不一致；异常、错误、孤立值造成的噪声数据；数据记录或属性的重复造成的数据冗余等。这类数据的增加并没有都带来决策树准确性的提高，一些专家认为，在产生决策树前尽量减少训练数据量比在决策树产生后再简化决策树更能够提高决策树的性能，实际上，这就是经常提起的数据预处理技术，与决策树修剪技术相对应，也称为数据减少技术。聚类技术可以将同一个聚类“簇”中的物理或抽象对像尽可能地彼此相似，不同聚类“簇”中的对象彼此相异，基于原始数据的缺陷及聚类的特性，将聚类应用于分类预测前的数据预处理中，可以删除冗余、相似、噪声数据，从而减少训练数据并提高训练数据的质量，进而改进单个决策树的性能。

本文以某区有线电视用户数据作为研究对象，根据K-means聚类分析结果抽取训练样本，在训练样本的支持下，建立基于C5.0的决策树模型，对用户订制交互服务的意愿进行预测，探索一种新的预测思路。

1 研究方法

1.1 K-means聚类算法

K-means聚类算法又称为K均值聚类算法，其优点是原理简单、算法速度快，伸缩性好。

K-means聚类算法的工作流程是：首先随机选取K个样本作为初始聚类中心，然后计算各个样本到聚类中心的距离，把样本归到离它最近的聚类中心所在的类中，重新计算调整后的新类的聚类中心，重复这个过程，直到相邻2次的聚类中心没有任何变化，这时样本调整结束，算法已经收敛。该算法的描述如下：

(1)给定大小为N的数据集，令I=1，选取k个初始聚类中心 zj(I),j=1,2,3,…，k。

(2)计算每个数据对象与聚类中心的距离D(Xi，Zj(I))。其中 i=1,2,3,…，k，j=1,2,3,…，k 如果满足(1)式：

(4)判断：若 Zi(I+1)≠Zj(I)，j=1,2,3,…，k，则 I=I+1。 返回（2）。否则该算法结束。

从上面的算法思想和算法框架，不难看出，K个初始聚类中心点的选取对聚类结果具有较大的影响，因为在该算法中是随机地选取任意K个点作为初始聚类中心。如果有先验知识，可以选取具有代表性的点作为初始中心点。

1.2 决策树及C5.0算法

决策树算法的起源是概念学习系统，是应用较广的归纳推理算法之一，它对噪声数据有很好的健壮性。决策树通过把实例从根节点排列到某个叶子节点来分类，叶子节点即为实例所属的分类。一般情况下，树越小则树的预测能力越强。具体来说，决策树是对一组数据进行分类的树形结构，要求这组数据存在于一个二维的表形结构中，表中每行数据对应一个训练样本并包括若干个属性值，这些值中包含一个表征数据类别的属性，称类别属性，其它属性称非类别属性。根据二维表数据生成的决策树的每个非叶子节点都对应一个非类别属性，其分支对应于该属性的可能取值。叶子节点则代表某记录对应的类别属性值。对一个新的待预测数据，生成的决策树在每个非叶子节点上都对其属性进行提问，确定进入哪一个分支，最后到达决定其类别属性的叶子节点，从而获得预测值。

C5.0决策树算法由C4.5算法改进而成，根据提供最大信息增益的字段分割样本数据，并对决策树各叶子进行裁剪或合并来提高分类精度，最后确定各叶子的最佳阈值。通常不需花费大量的训练时间即可建立决策树，且生成的决策树容易进行解释。C5.0增加了强大的Boosting算法以提高分类精度，Boosting算法依次建立一系列决策树，后建立的决策树重点考虑以前被错分和漏分的数据，最后生成更准确的决策树。下面以计算评价属性A为例计算信息增益率GainRatio(A)，S表示一组样本，Pi是任意样本属于Bi的概率，用Si/s表示。假定类别属性具有n个不同的值，定义n个不同类Bi(i=1,…，n)。设Si是类B中的样本数。lnfo(s)表示当前样本中的信息熵，计算如下：

设属性A具有n个不同值{A1,A2,…，An}，利用A将S划分为 n个子集{S1,S2,…，Sn}，其中 Sj为 S中在 A中具有 Aj的样本，sij是子集sj中类Bi样本数。ijfo(S,A)表示利用属性A划分S中所需要信息熵，计算如下：

分裂信息Splitlnfo(A)是S关于属性A的各值的熵，用以消除具有大量属性值属性的偏差，计算如下：

1.3 研究方法

基于以上分析，本文的研究方法具体如图1所示：

抽取主要过程描述如下：

样本数据组织与预处理：数据预处理包括数据的过滤筛选和数据的规范化、离散化处理等。

建模前导处理：基于K-means聚类技术对客户样本进行分群，抽取各个簇中心附近的一个样本组合成为K个训练样本集。

利用训练样本训练决策分类器。

构建预测模型。

利用测试样本检验模型。

2 实例：某区有线电视服务交互服务订制预测建模与应用

有线电视服务交互服务是指有线电视台可利用现有的宽带网络和卫星传输系统，将海量的数据信息加密后广播出去，用户可按照自己的需要，通过无线遥控器、机顶盒、IC卡等设备，在电视上自由地点播远程节目库中的视频节目和信息，以及股票信息接收、交互式娱乐、电子商务、电视购物、远程教育等增值业务服务，令人们的生活将更加快捷、丰富多彩。随着人们消费观念的转变，“有偿服务”也将成为未来信息服务产业的核心，付费电视业务将成为电视发展的动力和结构变化的方向，基于此的交互服务订制与否的用户预测具有广阔的市场前景。

图1 基于K-means聚类与决策树的有线电视交互服务订制预测建模框架与应用方法

2.1 数据准备与预处理

本文数据来源于某区有线电视网络的442名用户一定历史时期市场研究资料，文中将K-means聚类分析与C5.0算法应用于有线电视交互服务的订制预测分析中，从中找出订制响应率较高的客户群，分析工具采用SPSS Clementine 11.1。影响目标变量交互服务订制与否的因素很多，根据实际操作经验来看，通常包括：①教育程度；②性别；③年龄；④每天看电视时长；⑤所属行业；⑥子女数目；⑦月收入等级等。预处理过程中包含对收入缺失值的补充，对月收入等级、所属行业进行离散化处理等。

2.2 抽取学习样本与建立决策树模型

决策树算法是从样本中学习规则，属于监督分类方法，因此学习样本的好坏对决策树模型的性能影响较大。本文依据渐进抽样原则，采用聚类分析中K-means算法对原始数据进行聚类抽样。将采集的某区的442个样本记录在Clementine11.1软件中进行数据抽样。为了保证评价模型的学习精度，学习样本的确定采用试验的方法，即根据建立的模型评价精度高低来选择合适规模的学习样本。本次试验开始聚50个类，分别从每个聚类中心附近抽取一条记录，得到50个训练样本。通过建立评价模型来检验评价模型的精度，若满足实际情况的要求，表示该模型建立合理；如果所建立的评价模型精度不高，需要重新增加学习样本对模型进行训练，直至满足实际工作需要为止。抽样流程中，C5.0节点采用专家模式，修剪严重性设为20，修剪严重性高低的不同会影响生成的决策树或规则集的修剪程度，增加该值可获得一个更简洁的小型树，减小该值可获得一个更精确的树。经多次训练，在设为20时精确度与树的复杂度得到较好的平衡。为了能体现评价的模型的实用性，检验模型的泛化能力，采用测试样本是全部的样本记录，即442个测试样本。

在聚50个类的数据集来看，得到模型的预测精度为76.39%，预测结果误差较大，不能完全反映接受交互服务订制的用户分布情况，故50个学习样本建立模型试验失败。主要原因是50个聚类中各个聚类的数据之间距离过大，样本分布不太合理，决策树模型没有得到充分学习，因此50个样本不能有效地代表用户群分布情况。为了实现评价目的，需要增大学习样本的范围，重新建立决策树评价模型。依据试验设计的路线，结合孙微微等研究成果，本次采用递增的方式来抽取学习样本。当采用聚80类来抽取学习样本，重新训练决策树评价模型，并检验得到此时的模型预测精度为81.76%。从80个学习样本建立模型的效果看出，随着学习样本的增加，评价模型精度有所提高，但精度依然不是很理想，需要再增大学习样本规模，以下操作与之前相同。当选择200个学习样本时，与150个样本建立的模型精度差别不明显，停止继续扩大样本规模。图2表示在六种不同的学习样本支持下所表现出评价模型预测精度的变化曲线。

从图2可以看出，150个样本比120个样本评价模型准确率提高了4.16个百分点，而200个和180个学习样本模型的准确率只比120个样本模型提高了0.56个百分点和0.38个百分点。从这些数据可以看出在150个样本基础上每增加30左右的样本，模型精度提高的很少，表明在150个样本点模型准确率趋于稳定。因此确定150个学习样本建立的决策树模型作为有线电视交互服务订制预测模型，该样本所建立的模型预测精度为87.35%。

表1 基于K-means与决策树预测的误分类损失

表2 基于决策树预测的误分类损失

2.3 试验结果与分析

(1)基于K-means与决策树C5.0预测的误分类损失

最后，用442个样本替代流程图中的数据源，检验用150个训练样本建立的决策树评价模型，其模型测试的准确率为84.84%，表明该模型的泛化能力较好，能有效地用典型性样本推理出大量未知样本的类别。误分类损失如表1所示，字段NEWSCHAN表示实际的订制意愿，字段$CNEWSCHAN则表示预测的订制意愿，0表示不愿意接受订制，1表示愿意接受订制。

表1表明，442名用户中，共预测有204名用户会订制有线电视交互服务，其中准确预测176名，即愿意接受订制的预测准确率达86.27%。预测有234名用户将不愿意订制有线电视交互服务，其中准确预测199名，即不愿意订制有线电视交互服务的预测准确率为83.61%。

(2)本文研究方法与基于决策树预测的误分类损失比较

同样的样本不经过聚类抽取学习样本而直接用决策树C5.0进行预测，误分类损失如表2所示，该模型的预测准确率仅达70.14%，其中愿意接受订制的预测准确率为77.48%，该精度与基于K-means与决策树进行预测所得的同类精度86.27%低了8.79个百分点。

(3)基于K-means与决策树C5.0预测所产生的部分决策规则描述

在生成决策树之后，可以方便地提取决策树描述的知识，沿着根结点到叶结点的每一条对应一条决策规则。

抽取部分响应率较高的节点列如表3所示。

指数值大于 1的节点表示，通过从这些节点中选择记录而不是从整个样本中随机选择记录，能够有更多的机会找到愿意接受订制的用户。抽取表3第三条规则描述如下：

该用户群为40岁以上的女性，每天看电视3小时以内，这类用户在442名样本用户中共存在63位，占总体样本的14.25%（14.25%=63*100%/442），63位用户中有44位用户愿意接受交互服务的订制，即响应率为69.84%（69.84%=44*100%/63），这44位用户数目占总体愿意接受订制数目（如图 3， 39+176=215名）的 20.47%(20.47%=44*100%/215)，从这些记录中获得积级响应的可能性是随机选择用户的1.43倍 (总体响应率=215*100%/442=48.64%，1.43=69.84%/48.64%)。故可对响应指数＞1的用户群进行有针对性的营销。

实验结果表明，决策树建模前的样本抽样采用聚类抽样方法，以渐进抽样的原则，有效地减少了学习样本数量，降低了评价模型的复杂度，并提高了模型的精度。

3 结论

本文运用聚类方法抽取决策树模型的学习样本，有效地减少了学习样本空间，在试验精度不高时增加选择样本，所获得的模型的预测精度相对于仅运用决策树进行处理有所增高，并且该模型的可解释性较好，提取的规则能有效地识别高响应率的客户群。进一步的工作包括对该方法进行完善和改进，以及进行深入的理论上的分析和严格论证，在回归任务、神经网络、粗集等其他一些学习方法和其他集成学习方法的基础上进行评测。

[1]Sebbanm,Nock R,Chauchat J H,et al.Impact of Learning Set Quality and Size on Decision Tree Performances[J].IJCSS,2000,1(1).

[2]饶秀琪,张国基.基于KPCA的决策树方法及其应用[J].计算机工程与设计,2007,28(7).

[3]Durkin J,蔡竞峰,蔡自兴.决策树技术及其当前研究方向[J].控制工程,2005,12(1).

[4]Brodley C E,Friedlm A.Identifying and Eliminating Mislabeled Training Instances[C].Proceeding of the 13th National Conference on Artificial Intelligence，,1996.

[5]Uinlan J R.C4.5:Programs for Machine Learning[M].San Mateo,CA:Morgan Kaufmann,1993.

[6]葛宏伟,杨镜非.决策树在短期电力负荷预测中的应用[J].华中电力,2009,(1).

[7]孙微微,刘才兴,田绪红.训练集容量对决策树分类错误率的影响研究[J].计算机工程与应用,2005,(10).