基于粗糙集的决策树在电子商务中的应用

2014-12-28吴学辉张月琴

重庆科技学院学报（自然科学版） 2014年1期

吴学辉张月琴

(1.运城学院计算机科学与技术系，山西运城 044000;2.太原理工大学计算机与软件学院，太原 030012)

随着互联网技术的发展，电子商务逐渐改变着传统经营模式，特别是企业与客户之间的关系。企业最关心的是:谁是最有价值的客户，如何实现这些客户价值最大化等，这些都需要进行客户价值分析。通过分析可以为客户提供个性化的服务，使企业以最小化的投入获得最大的回报。当前许多企业的网站服务器端记录着大量的客户特征信息和行为信息，但是对这些信息缺乏深层次的分析。决策树是数据挖掘中的一种重要的数据分析方法，它主要用来进行数据的分类和预测，其主要优点是分类速度快，效率高［1-2］。缺点是当属性比较多时，分类能力较差，难以发现有用的规则。粗糙集也是一种处理不完备信息的有效工具，因为它不需要先验知识，所以适合处理不确定性问题。粗糙集已经广泛应用在数据预处理、消除冗余信息等方面［3-4］。

本文以数据挖掘中的决策树和粗糙集理论为基础，将二者有机结合，提出了一种基于粗糙集属性依赖度的决策树算法，并将此算法应用于电子商务客户价值分析，提取相关规则，为企业决策提供实质性的建议和指导。

1 基本概念

1.1 决策树算法

决策树是数据挖掘中的一种分类方法，决策树算法的主要思想是:以信息论为基础，找出具有最大信息增益的属性字段，以该属性字段的不同取值构造决策树分支，然后在每个分支中递归构建决策树。在最终构建的决策树中，每一条从根节点到叶节点的路径对应着一条规则。因此，它在数据挖掘中应用非常广泛。

决策树算法中，最经典的是ID3算法，该算法以信息论中的信息熵和信息增益度为标准，实现对数据的归纳分类。由于ID3算法只能处理离散型属性，所以它的应用受到一些限制，在它之后的C4.5、CART、SLIQ、SPRINT都是对ID3算法进行了相关改进［5］。

1.2 粗糙集理论

1982年，波兰教授 Pawlak Z提出了粗糙集(Rough Set)的概念。粗糙集的基本思想是利用已存在的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻画。它是一种处理不确定信息的方法［6-8］。本文研究中所涉及的粗糙集相关理论如下:

定义1 粗糙集S= ＜U，R，V，F ＞，X⊆U为U上的一个概念，∪{［x］R∈U/R|［x］R∩X≠∅}也是一个概念，当X是属性子集R所确定的U上的不分明集的并时，即X是R可定义的，R的可定义集即为R的精确集，否则X是R不可定义的，R的不可定义集即为R的非精确集或粗糙集。

定义2 (不可分辨关系)S= ＜ U，R，V，F ＞，设P⊆R，P≠∅，P上的不可分辨关系定义为P中所有等价关系的交集。也记为IND(P):

定义3 (上近似、下近似)令X⊆U，则RX和RX称为X关于R的上近似和下近似。

定义4 (边界、正域、负域)集合BNG(X)=RX-RX称为X的R边界;POSR(X)=RX称为X的R正域;BNG(X)=U-RX称为X的R负域。

定义5 (关系独立、关系依赖)设S=＜U，R，V，F ＞，属性 P ∈ R，IND(R)=IND(R-{P}}，则称P在R中是可缺的，否则称P在R中是不可缺的，如果R中的每个知识都是不可缺的，则称R是独立的，否则就是依赖的。

定义6 (属性核)P和Q是论域U上的2个等价关系簇，若 Q⊆ P是独立的，且 IND(P)=IND(Q)，则称Q是P的约简，在每个约简中都不可缺的关系集合称为核，记为 COREQ(P)。其中COREQ(P)=∩REDQ(P)，P的所有Q约简关系簇为REDQ(P)。

定义7 (Q的P正域)设论域U上的2个等价关系簇为P和Q，则Q的P正域记为POSP(Q)，定义为

2 一种基于粗糙集属性依赖度的决策树算法

传统的决策树算法如ID3存在一些不足，它偏向选择取值较多的属性，但该属性并不一定就是最优的属性，还有它只能处理离散属性，另外该算法假设训练集中的正例与反例的比例与实例相一致［9］。针对ID3算法的不足，结合粗糙集相关理论，本文提出一种基于粗糙集属性依赖度的分类算法。

定义8(属性依赖度)设K=(U，R)为一知识库，且P，Q⊆R，当ind(P)⊆ind(Q)，知识Q依赖于知识P，Q对P的依赖度的定义为:

式中:PosP(Q)—Q的P正域;Card—集合的基数，当k=0时称Q完全独立于P，当0＜k＜1时称Q粗糙依赖于P，当k=1时称Q完全依赖于P。

依据2个属性集合P，Q⊆R之间的相互依赖程度，当属性α加入Q后，对于分类U/P的重要程度可以定义为:SGF(α，Q，P)=rQ(P)-rQ-{α}(P)。

基于以上理论，算法描述如下:

(1)首先选择条件属性集中属性重要性最大的那个属性作为分支节点，如果所有条件属性的属性重要性相同，则选择条件属性中信息增益最大的属性作为分支节点，如果属性增益也相同，则选择序号小的属性作为分支节点。

(2)依据第一步选择的属性进行分类，接着重复以上操作，直到分类中的决策属性一致或条件属性选择后不能继续分类或决策属性为空，产生叶节点，条件属性选择后，在属性集中要将其删除，保证以后分支不再选择该条件属性。

(3)读树。从根节点到叶节点对应一条规则。

通过该算法可以得到一个相对简单的规则集，且效率很高。

3 实验结果与分析

本文以某企业在客户管理中积累的客户数据进行研究。为了方便说明，这里从大量客户数据中抽取10组专家评价数据，具体数据见表1。

表1 电子商务客户价值指标统计决策表

3.1 决策表离散化

粗糙集处理的数据必须是离散的，由于表1中的数据本身就是离散的，为了处理方便，只需将字符型属性的取值变换为数字型，将条件属性中的好(或高)用1来表示，差(或低)用0来表示。将决策属性中的高用1来表示，低用0来表示。同时将条件属性分别用1—8来代替，决策属性用d代替，最后得到的离散化后的统计数据见表2。

表2 离散化后的统计数据表

3.2 属性约简

属性约简就是在保持知识库分类能力不变的条件下，删除不重要或不相关的属性。目前属性约简方法主要有盲目法和启发式约简算法。由于盲目法所需时间和空间代价较高，实际约简中主要采用的是启发式约简算法。对表2采用启发式约简算法，约简后的统计数据见表3。

表3 约简后的统计数据表

从约简结果可以看出，属性4，6，7，8是冗余属性，而属性1，2，3，5 是核属性。

3.3 构建决策树

针对表3，用前面介绍的基于属性依赖度的决策树算法进行处理，过程如下:

首先计算各条件属性的依赖度。

PosC(D)={1，2，3，4，5，6，7，8}

对于条件属性1:U/ind(C-1)={{1，5}，{2}，{3}，{4}，{6}，{7，8}}

PosC-1(D)={2，3，4，6}

rC-1(D)=card((PosC-1(D))/card(U)=1/2

SGF(1，C，D)=rC(D)-rC-1(D)=1-1/2=1/2

同理，对于条件属性 2，SGF(2，C，D)=1/4;条件属性 3，SGF(3，C，D)=1/4;条件属性 5，SGF(5，C，D)=1/4。因此，条件属性1将作为决策树的根节点，分类属性1为0时，它的分类集合为{1，3，7}，其决策属性为一类，就停止选择属性。分类属性1为1 时，它的分类集合为{2，4，5，6，8}，由于它的决策属性不为一类，继续选择属性分类，此时条件属性集合中有2，3，5。采用上面的方法，分别计算属性2，3，5 的重要性，结果为:SGF(2，C-1，D)=SGF(3，C-1，D)=SGF(5，C-1，D)=2/5。依据上面提出的基于粗糙集属性依赖度的决策树算法，则选择条件属性中信息增益最大的属性作为分支节点。经过计算，属性2的信息增益为:Gain(2)=0.02。属性3的信息增益为:Gain(3)=0.42。属性5的信息增益为:Gain(5)=0.32。属性3的信息增益最大，选择属性3作为分类节点，以此类推，最终构造出的决策树如图1所示。