CRM挖掘算法应用举例.doc

关联规则应用举例
下面结合顾客购买实例提出一个可行的关联分析方法。
某公司专业生产化妆用品和沐浴用品，该公司在全国各大城市的各大商场都设点销售，公司对一定时间范围内顾客购买详细情况作了收集，情况如表1所示（限于文章篇幅，仅列出六个顾客、五种产品为例）。

表1：顾客购买情况表
顾客
购买产品
A
日霜、洗面奶、晚霜
B
洗发水、晚霜、沐浴乳
C
洗面奶、晚霜
D
洗发水、沐浴乳、洗面奶、日霜
E
洗发水
F
洗发水、沐浴乳
针对表1进行关联分析，首先构造两种商品间的关联表，如表2所示，表中每一个数值表示的是行、列代表的两种商品同时被一个用户购买的次数。

表2：两种商品间关联表
Y
X

洗面奶

日霜

晚霜

洗发水

沐浴乳
洗面奶
3
2
2
1
1
日霜
2
2
1
1
1
晚霜
2
1
3
1
1
洗发水
1
1
1
4
3
沐浴乳
1
1
1
3
3
第二步，针对设定的最小支持度阀值，计算每一个X的最小支持度，将大于最小支持度阀值的X列出（本例，设最小支持度阀值为0.5）：support(洗面奶)=0.5; support(晚霜)=0.5; support(洗发水)=0.667; support(沐浴乳)=0.5.
第三步，针对设定的最小置信度阀值和上步列出的X，计算的最小置信度表，如表3所示：

表3：的最小置信度表
Y
X

洗面奶

晚霜

洗发水

沐浴乳
洗面奶
/
0.667
0.333
0.333
晚霜
0.667
/
0.333
0.333
洗发水
0.25
0.25
/
0.75
沐浴乳
0.333
0.333
1
/
第四步，将大于最小置信度阀值的列出（本例，设最小置信度阀值为0.5），即为关联分析所得出的规则：
Rule1: 晚霜洗面奶，support=0.5, confidence=0.667
Rule2: 洗面奶晚霜，support=0.5, confidence=0.667
Rule3: 洗发水沐浴乳，support=0.667, confidence=0.75
Rule4: 沐浴乳洗发水，support=0.5, confidence=1
从上述规则可以初步得出结论：1.购买本公司产品的顾客中相当比例的人有晚上用洗面奶洗面，并用晚霜保养皮肤的习惯（估计顾客中有一定比例是白领上班族，早上匆忙，晚上空暇）。2.购买洗发水的顾客多半会同时购买沐浴乳，而购买沐浴乳的顾客则几乎肯定会购买洗发水（因多数人沐浴时同时洗发，并且洗发次数多于沐浴）。
根据上述规则，公司在营销时采取了如下措施：1.将晚霜与洗面奶、洗发水与沐浴乳放置在一起，方便顾客购买。2.营业员在顾客购买了一种商品后，适当推荐另一种商品。3、在生产与发货运输上，将关联产品配套按排。采取这些措施后，顾客的交叉消费大为提高，商场与顾客的满意度也有所提高。

聚类分析应用示例
聚类分析问题可描述为：给定m维空间中的n个向量，把每个向量归属到S个聚类中的某一个，使得每个向量与其聚类中心的“距离”最小。聚类分析问题的实质是一个全局最优问题。在这里，m可认为是样本的参与聚类的属性个数，n是样本的个数，S是由用户预先设定的分类数目。
定义 对于m维空间中的向量，，向量之间的距离为：.
以下提出的聚类算法借鉴了模糊数学中模糊分类的思想，计算的基本思路是：对于m维空间中的一组向量，首先人为地给出分类个数c和一个初始分类，由此得出各向量的初始隶属度： ，以及计算每一个初始分类的初始聚类中心，然后反复迭代直到分类结束，每一个向量都以一定的隶属度归入某一类。迭代的过程分以下几步：
⑴ 按定义1中距离计算每一个向量到所属类聚类中心的距离

其中表示迭代次数，初始时=0，是的第k个分量。
⑵ 计算每一个向量的隶属度
j=1,2,…c, i=1,2,…n .
其中是一个关系到收敛速度的经验常数(>1)。
⑶ 判断隶属度是否收敛
ε j=1,2, …c, i=1,2,…n .
如果上式成立，分类迭代结束。
⑷ 计算每类的新的聚类中心
j=1,2, …c.
由上述设计聚类算法Clustering如下：
算法输入：n×m数组item，其中n表示分类样本的个数，m表示每个样本的属性个数, 分类数c，收敛速度常数(>1)，收敛判断数ε。
n×c 数组，其中c表示分类个数。
算法输出：n×c 数组，表示收敛了的隶属度数组。

　LOOP:
⑴ for （j=1;j<=c;j++）
{}//新聚类中心
⑵ for （j=1;j<=c;j++）
{for (i =1; i <=n; i ++)
{ }} //新的距离
⑶ for （j=1;j<=c;j++）
{for (i =1; i <=n; i ++)
{ }} //新的隶属度
⑷ for （j=1;j<=c;j++）
{for (i =1; i <=n; i ++)
{if ε then ;GO LOOP}}//判断收敛
⑸ RETURN

以下结合实例讨论聚类分析方法在员工业绩考核中的应用：
某商场拟对职工进行综合考评，因以往并未对考评指标做过量化工作，因此考虑首先将职工按照几个指标分成优、一般、欠佳三类。根据有关销售业绩、出勤天数、顾客投诉次数的统计资料如表（一）所示：（限于篇幅，仅以8位职工，3个指标为例）

表（一） 职工业绩统计表
职工
销售金额（千元）
出勤天数
顾客投诉次数
A
72.50
25
2
B
80.34
25
0
C
73.00
24
1
D
65.22
23
2
E
79.20
24
0
F
72.38
23
1
G
63.11
24
2
H
74.25
24
1
利用上述Clustering聚类算法进行分类，初始分类共分三类，随意地将职工A、B、C归于一类，职工D、E、F归于一类，职工G、H归于一类，初始隶属度为：，聚类过程如表（二）所示：

表（二） 分类迭代隶属度表
职工
第１次迭代
第２次迭代
…
第6次迭代
第7次迭代
A
0.073
0.875
0.052
0.032
0.948
0.020
…
0.048
0.910
0.041
0.048
0.912
0.041
B
0.486
0.305
0.209
0.545
0.291
0.164
…
0.863
0.093
0.044
0.865
0.092
0.043
C
0.216
0.672
0.112
0.099
0.851
0.050
…
0.019
0.967
0.014
0.020
0.966
0.015
D
0.184
0.263
0.552
0.096
0.143
0.760
…
0.053
0.099
0.849
0.054
0.102
0.843
E
0.517
0.292
0.191
0.591
0.268
0.140
…
0.930
0.049
0.021
0.928
0.051
0.022
F
0.037
0.936
0.028
0.058
0.904
0.038
…
0.061
0.885
0.054
0.060
0.866
0.053
G
0.220
0.292
0.489
0.163
0.225
0.611
…
0.062
0.104
0.834
0.060
0.102
0.838
H
0.522
0.360
0.117
0.356
0.541
0.104
…
0.161
0.748
0.091
0.161
0.748
0.091
从上面迭代隶属度表中可以看出，当迭代到第七次时，隶属度已经收敛（ε＝0.05）,从上表得出分类结果为：第一类{Ｂ，Ｅ}，第二类{Ａ，Ｃ，Ｆ，Ｈ}，第三类{Ｄ，Ｇ}，于是，可以得出职工Ｂ、Ｅ属于优等，职工Ａ、Ｃ、Ｆ、Ｈ属于一般，职工Ｄ、Ｇ欠佳的结论，结论是合理的、易理解的。

ID3算法学习过程
在学习开始的时候，只有一棵空的决策树，并不知道如何根据属性将实例进行分类，我们所要做的就是根据训练实例集构造决策树来预测如何根据属性对整个实例空间进行划分。设此时训练实例集为X，目的是将训练实例分为n类。设属于第i类的训练实例个数是Ci，X中总的训练实例个数为|X|，若记一个实例属于第i类的概率为P(Ci)，则：

此时决策树对划分C的不确定程度为：

以后在无混淆的情况下将H(X，C)简记为H(X)。

决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。若选择测试属性a进行测试，在得知a＝aj的情况下属于第i类的实例个数为Cij个。记p(Ci；a＝aj)＝Cij/|X|，即p(C；a＝aj)为在测试属性a的取值为aj时它属于第i类的概率。此时决策树对分类的不确定程度就是训练实例集对属性X的条件熵。

又因为在选择测试属性a后伸出的每个a＝aj叶结点Xj对于分类信息的信息熵为
(1)
属性a对于分类提供的信息量H(X；a)为：
(2)
式(1)的值越小则式(2)的值越大，说明选择测试属性a对于分类提供的信息越大，选择a之后对分类的不确定程度越小。Quinlan的ID3算法就是选择使得H(X；a)最大的属性作为测试属性，即选择使得式(1)最小的属性a。

ID3算法应用举例
下面结合商店定位实例提出一个可行的决策树分析方法。
某公司是一家专业的西服生产厂家，在全国各大城市均设立了连锁销售商店。公司为进一步扩大销售，拟定建立一批新的连锁销售商店。为了对连锁销售商店的位置、规模等有一个理想的定位，公司收集了以前设立的商店和同行的同类商店的详细情况，并对其经营效果作了评估，如下表所示（限于文章篇幅，仅以位置、规模、档次3个属性、每个属性两种取值为例）。

已设立的商店和同行的同类商店的详细情况表
商店个数
位置
档次
规模
经营效果
20
市中心
高
大
一般
15
市中心
高
一般
成功
8
市中心
一般
大
成功
6
城乡结合部
高
一般
一般
6
城乡结合部
一般
一般
成功
10
市中心
一般
一般
一般

决策树分析首先针对上表计算各个属性的信息熵，并将属性从大到小重新排列。
计算得：
H（X/位置）=(53/65)*[(-23/53)*LOG(23/53)+(-30/53)*LOG(30/53)]
+(12/65)*[(-6/12)*log(6/12)+(-6/12)*log(6/12)]=0.298
H（X/档次）=（41/65）*[（-15/41）*log(15/41)+(-26/41)*log(26/41)]
+(24/65)*[(-14/24)*log(14/24)+(-10/24)*log(10/24)]=0.289
H（X/规模）=（28/65）*[（-8/28）*log(8/28)+(-20/28)*log(20/28)]
+(37/65)*[(-21/37)*log(21/37)+(-16/37)*log(16/37)]=0.281
本例中，以规模对分类的贡献最大，所以应首先按规模进行划分。
第二步，建立决策树：首先按规模建立决策树，得到数据的第一次分组，然后依按同样方法按位置或档次分组（对分组得到的两个子组按第一步形式进行同样的计算），得到数据的第二次分组和数据的第三次分组。三次划分后的决策树如图4.2所示：
图4.2
第三步，从决策树中得出决策规则，如下：
Rule1: 规模=“大”并且位置=“市中心”并且档次=“一般” 成功的商店
Rule2: 规模=“一般”并且位置=“市中心”并且档次=“高” 成功的商店
Rule3: 规模=“一般” 位置=“城乡结合部”成功的商店
从上述规则得出结论：公司产品在市中心的商店可以有两种选择，一是大众化、规模化超市型，另一种是精品、专卖店型。在城乡结合部则不宜过分追求大型，应以规模适度为宜。
第四步，利用决策树和导出的规则对计划新开设的商店是否合适做出评估。

PRISM算法
PRISM算法可不首先产生决策树而直接产生分类规则，并且得到的规则比从决策树中取得的规则要简练一些。
(1)信息增益(Information gain)，从上可以看出，关键在于选择—个属性进行划分，为了避免使用属性的无关值和对分类无关的属性，PRISM力图极大化已知属性取值时对某一分类所提供的信息量。
如上所述，属性值可以看成是离散信息系统中的离散信息。信息i中关于某一事件的信息量为

例如，下表表示隐形眼睛配置决策表，眼镜师列出了对四种因素不同组合的各种诊断：
隐形眼睛配置决策表
序号
属性值
决策
序号
属性值
决策
a b c d
δ
a b c d
δ
1
1 1 1 1
3
13
2 2 1 1
3
2
1 1 1 2
2
14
2 2 1 2
2
3
1 1 2 1
3
15
2 2 2 1
3
4
1 1 2 2
1
16
2 2 2 2
3
5
1 2 1 1
3
17
3 1 1 1
3
6
1 2 1 2
2
18
3 1 1 2
3
7
1 2 2 1
3
19
3 1 2 1
3
8
1 2 2 2
1
20
3 1 2 2
1
9
2 1 1 1
3
21
3 2 1 1
3
10
2 1 1 2
2
22
3 2 1 2
2
11
2 1 2 1
3
23
3 2 2 1
3
12
2 1 2 2
1
24
3 2 2 2
3

在训练例集合S中，属于δ1类的有4个例，属于δ2类的有5个例，属于δ3类的有15例。所以，一个训练例属于δ1类的概率P(δ1)是4／24。这样，如果信息i是δ1（即分类为δ1），则此信息的信息量为

类似地，信息δ2中的信息量为

信息δ3中的信息量为

可见，一个事件发生的概率越小，我们知道该事件已经发生时所收到的信息就越多。
如果收到的信息是属性d有值1，则这个信息中关于δ3久的信息量为

其中P(δ3|d1)是给定d的值为1时δ3的概率。对于集合S，P(δ3|d1)=1，所以

可知，属性d有值1对例子属于δ3这一事件所提供的信息量为O.678比特。
如果收到的信息是属性d有值2，则这个信息中关于δ3的信息量为

由此可见，知道属性d有值2与不知道d的值相比，对例子属于类的确信程度更降低了，故信息量是负值。因此，d2对于确认δ3类来讲，不是一个好的选择。
(2) 极大化信息增益 归纳算法的任务是要找到一个属性-值对ax，使其对某—分类δn贡献最大的信息量，即极大化I(δn|ax)。我们有

由于P(δn)对所有的都相同，所以只要求P(δn|ax)最大即可。
以n＝1，即δ1为例，对所有的ax，P(δn|ax)的值列于下表(a)，从表中可见，有2个最佳的候选对：c2和d2。例如选c2。则信息增益为

现在对S中属性c为2的子集重复上述过程。从下表(b)可以看出，d2可使P(δn|ax)取极大值。此时信息增益为

现在对S中属性c为2、d为2的子集重复上述过程。从下表(c)可以看出有两个侯选对a1 ,b1。例如选b1，则信息增益为

前面已经计算过，信息δ1提供的信息量为I(δ1)＝2.585比特。我们又知道
c2提供的信息为1比特。
已知c2，时d2提供的信息为1比特。
已知c2和d2时，b1提供的信息为O.585比特。
所以，由信息源c2∧d2∧b1提供的信息为1+1+0.585＝2.585比特。也就是说，信息c2∧d2∧b1与信息δ1提供同样的信息量。其它属性值对确认δ1再不会提供任何信息了，因此归纳出规则：c2∧d2∧b1→δ1
至此，归纳过程的决策树如下图所示。此算法趋于得到通向的最短路径。归纳过程的下—步是对那些不是第一条规则的例的训练例集合求出最佳规则。方法是从S中删去所有包含c2&d2&b1的例，重复应用上述算法。上述过程要重复执行，直到S中没有类的例为止。整个过程要对每个分类轮流进行，每次都从完整的训练例集合S开始。
对隐形眼镜问题的完整输出如下，

(3)PRISM的算法步骤
基本的归纳算法可叙述如下:
如果训练例集合包括多个类别，则对每个类别δn，分别完成下列步骤：
①对每个属性—值对ax，计算类别δn的发生概率P(δn|ax)。
②选择某个属性对ax，使P(δn|ax)为最大，建立包括属性对ax的所有例的训练例子集。
③对训练例子集重复步骤①和②，直到训练例子集仅包含δn的例为止。以所有选出的属性值对的合取构成一条规则。
④从训练例集合中删去上述规则覆盖的训练例。
⑤重复步骤①一④，直到所有的δn类的例都被删去为止。
在上述归纳过程中，每归纳出一个类别的规则，就把训练例集合恢复到初始状态，算法再归纳下一类别的规则。由于每个类别是分开考虑的，所以表示的顺序是无关的。

遗传算法应用示例
下面让我们通过一个使用由三个基本算子组成的简单遗传算法SGA(Simple Genetic Algorithm)进行优化的问题，来了解遗传算法的基本机制及其在优化问题中的有效性。
问题；求使函数f(x)＝x2在[0，31]上取得最大值的点x0。
(1)首先在区间[O，31]上的整数参数x可以用一个5位的二进制位串进行编码，x的值直接对应二进制位串的数值：

(2)然后用扔分币的方法产生一个由4个位申组成的初始种群，如上表所示。
(3)计算适值及选择串。
①解码种群中的各位串得相应的参数x的值；
②由参数值计算目标函数f(x)＝x2；
③由目标函数值得相应位串的适值（直接取函数值）；
计算相应的选择率Pselect=fi／∑fi 及期望值，以上结果如上表所示。
(4)繁殖(Reproduction)。如上表所示区间上进行4次随机试验，则选择的结果如上表最后一栏所示。于是，在交配池中，我们就得到了串1的一个拷贝，串2的两个拷贝及串4的一个拷贝，如下表所示。

(5)交叉
①随机选择交配对象，结果是串1和串2配对，串3和串4配对；
②随机选择交叉点，结果是第一对在位置4交叉，第二对在位置2交又。
结果如上表所示。
(6)变异。我们取变异率Pm＝0.001，则平均每1000位中才有—位变异，由4个位串组成的种群中共有4*5=20位，则变异的期望值为20*0.001＝0.02(位)。事实上在我们这个单代遗传的实验中没有变异发生。
(7)对比以上两表可以看出，虽然仅经历了一代遗产，第二代的平均值及最大值却比第—代的平均值及最大值有了很大提高，均值：293→439，最大值：576→729，说明种群正朝优化的方向前进。