1、引言及问题

决策树是一种分类算法。比如判断一个人是男还是女，可以简单地看长头发是女，穿着亮丽是女，短头发是男等。很容易理解。

聚类是把类似的个体放在一起。比如短头发、喜好运动的是一类人，长头发、穿着亮丽、化妆的是一类人。

分类是通过对已知个体的学习预测另一些个体的那个未知属性。比如知道一些人的性别，从这些人归纳出规律，用得到的规律去判断其他人的性别；这个规律可能是头发长度乘以3加上衣服颜色在红色上分量乘以5，得到的结果大于100是女，小于100是男。得到的这个规律理解起来会很晕。。。

分类只能应用到特定属性上，比如上面男女推断，并不能用这个去推断喜不喜欢玩游戏。聚类可以应用得比较广，上面短头发、喜好运动的可能会玩动作类游戏，长头发、穿着亮丽、化妆的总体上可能并不是很喜欢玩游戏，但可能会玩泡泡类游戏。分类的好处是对推断的特定属性相对准确些，聚类的缺点还有聚类结果可能会变，本月数据聚类与上个月的聚类不同了。

用决策树做聚类可以很直观地理解，能够理解则对不同时期的变化就可以解释。

在网上搜到几篇关于决策树聚类的文章，但没找到能直接实施的。本主题计划逐步探索着完成这个过程。

2013-11-10

2、目标与度量

任何算法都要有目标，目标确定了，达到目标的方法就是算法。决策树分类目标是预测单一目标变量，准确率预高越好，算法过程中用熵或gini等作为衡量距离目标的远近。聚类算法没有目标变量，但算法定义了衡量好坏的标准，实际上给它定义了目标，如利用方差、离差等。

聚类没有目标变量，就只能利用自变量，自变量的个数是多个，类型可能是类别型、连续型、有序型。需要解决变量间的平衡。

1）不同变量类型度量的统一：连续型变量用方差、绝对离差比较合适，但类别型变量没有定义；类别型变量适合用熵或gini，但不太适合连续型；有序型变量可简单看作连续型变量。熵在连续型变量中需近似计算，维度大了基本不可用；方差在类别型变量中会有歧义，把本应是一维的变量扩充为多维，扭曲了度量空间；最后分析绝对离差与gini，发现他们可以说是同一度量在两种类型变量的表现，即连续型变量用绝对离差、类别型变量用gini具有可比性。聚类前计算各变量的绝对离差或gini，聚类过程中用增益比例来解决变量间尺度不同问题。

2）目标形成：多变量会形成多目标，需要形成最终一个目标，每个变量设个重要性权重（缺省取相同值），把每个变量的增益比例乘以权重再相加，可形成算法的唯一目标。

有了目标，算法就可以设计实现了。

2013-11-23

 3、公式及算法

自变量：X1,X2,...,Xm

因变量：Y1,Y2,...,Yk；如果没有，则取k=m，Y1=X1,Y2=X2...

各因变量权重：W1,W2,...,Wk；如果没有，则都取1

样本1,2,...,n，取值：

x11,x12,...,x1m;y11,y12,...,y1k

x21,x22,...,x2m;y21,y22,...,y2k

...

xn1,xn2,...,xnm;yn1,yn2,...,ynk

分类或聚类步骤：

1）把所有样本都归为分类树根节点B0里

2）计算B0节点各因变量的初始分散度（计算方法见分散度计算方法）

3）B0设为叶子节点且尚未完成划分

4）选取尚未完成划分的叶子节点B，如果没有则算法结束

5）选取每个自变量Xj

6）寻找自变量Xj对节点B的最佳分割

如果Xj是连续型变量，设分割点为xsj，Xj的分割点xsj把B分为Xj小于等于xsj的一个分支Bl、Xj大于xsj的一个分支Br，计算划分的信息增益率（计算方法见信息增益率计算方法），选信息增益率最大的xsj作为分割点（可以用黄金分割法或类似梯度下降法）；

如果Xj是类别型变量，根据决策树算法把Xj的取值分为两个取值集合Cl、Cr，取值为Cl的样本点在分支Bl，取值为Cr的样本点在Br，计算划分的信息增益率（计算方法见信息增益率计算方法），选信息增益率最大的取值集合划分

7）比较各自变量对节点B划分的信息增益率，取信息增益率最大的那个自变量进行划分

用该变量划分出的Bl、Br作为节点B的子节点，这两个自节点尚未完成划分，B节点设为非叶子节点且已完成划分

如果所有信息增益率小于一定值，则不添加自节点，直接把B节点设为已完成划分

8）如果迭代次数达到最大或节点数达到最大则结束，否则转到4

分散度计算方法：

如果Yj为连续型变量，

MYj=(y1j+y2j+...+ynj)/n

SYj=|y1j-MYj|+|y2j-MYj|+...+|ynj-MYj|

如果Yj为类别型变量，

统计Yj各取值个数，设y1j,y2j,...,ynj取值有C1,C2,...,Cc，对应个数为n1,n2,...nc（如果变量是性别，统计男多少人、女多少人）

SYj=1-(n1*n1+n2*n2+...+nc*nc)/n/n

信息增益率的计算方法：

1）选每个因变量Yj

2）计算父节点B的Yj分散度

3）计算所有子节点的Yj分散度

4）计算Yj的信息增益率Gj=(B的Yj分散度-所有子节点的Yj分散度之和)/B的Yj分散度

4）计算完所有因变量计算完父节点分散度、所有子节点分散度后，计算总的信息增益率G=(W1*G1+W2*G2+...+Wk*Gk)/(W1+W2+...+Wk)

2013-12-14