『数据挖掘十大算法』笔记一：决策树

数据挖掘Top 10算法

C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART

决策树模型与学习

决策树是一种基本的分类与回归方法。误以为决策树就只是分类，它是一种树形结构，有结点和有向边构成，结点有内部结点和叶节点，内部结点代表一个特征或者属性，叶节点代表一个类。

决策树算法包含特征选择、决策树生成、决策树剪枝过程。

特征选择

即选取对训练数据具有分类能力的特征。如何选取特征呢，可以通过信息增益，信息增益率，Gini指数等。

信息增益

熵(entropy)

熵表示随机变量不确定性度量，对于X它为有限取值的离散随机变量

P(X = x_i) = p_i, i = 1,2,3,...,n

则其熵定义为:

H(X) = - sum_{i=1}^{n}p_ilog{p_i}

其中若

p_i

=0，则定义

0log0=0

，其中熵与X的值无关，只和X的分布有关。

熵越大，随机变量的不确定性越大,

0leq H(p) leq log{n}

条件熵

条件熵定义为X给定条件下Y的条件概率分布对X的期望：

H(Y|X) = sum_{i=1}^{n}p_i H(Y|X=x_i)

其中

p_i=P(X=x_i)

H(Y|X=x_i)= - sum_{ j=1}^{n}P(X=x_i, Y=y_j)log{P(X=x_i, Y=y_j)}

信息增益

信息增益表示得知特征A的信息而使得类Y的信息的不确定性减少的程度。信息增益定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g(D,A)=H(D)-H(D|A)

信息增益算法

计算数据集D的经验熵：

H(D) = - sum_{k=1}^{K}{frac{|C_k|}{|D|} logfrac{|C_k|}{|D|} }

计算特征A对数据集D的经验条件熵：

H(D|A) = sum_{i=1}^{n}frac{|D_i|}{|D|}H(D_i) = - sum_{i=1}^{n}frac{|D_i|}{|D|} sum_{k=1}^{K}{frac{|D_{ik}|}{|D_i|} log _{2} frac{|D_{ik}|}{|D_i|}}

计算信息增益：

g(D,A) = H(D) - H(D|A)

信息增益比

信息增益作为划分数据集的特征，存在偏向与选择取值较多的特征的问题。信息增益比可以改进改问题。

特征A对训练数据集D的信息增益比

g_R(D,A)

定义为其信息增益g(D,A)与训练数据集D关于特征A的值得熵

H_A(D)

之比，即：

g_R(D,A) = frac{g(D,A)}{H_A(D)}

其中

H_A(D) = - sum_{i=1}^{n} frac{|D_i|}{|D|} log_2{frac{|D_i|}{|D|} }

, n为特征A的取值个数。

决策树生成

ID3算法

ID3算法核心是在决策树各个节点上应用信息增益准则选择特征，递归构建决策树。

输入：给定训练数据集D, 特征集A, 阈值

epsilon

。

输出：决策树.

若D中所有实例属于同一类

C_k

，则T为单结点树，并将类

C_k

作为该结点的类标记，返回T.

若A=

emptyset

，则T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T；

否则，计算A中各特征对D的信息增益，选择信息增益最大的特征

A_g

；

如果

A_g

的信息增益小于阈值

epsilon

，则置T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T；

否则，对

A_g

的每一个可能值

a_i

，将D分割为若干个非空子集

D_i

，将

D_i

中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T.

对第i个子节点，以

D_i

为训练集，以

A-A_g

为特征集，递归调用步（1）-（5），得到字数

T_i

，返回

T_i

。

C4.5算法

C4.5是ID3的改进算法，只是它用信息增益比准则选择特征，递归构建决策树。

输入：给定训练数据集D, 特征集A, 阈值

epsilon

。

输出：决策树.

若D中所有实例属于同一类

C_k

，则T为单结点树，并将类

C_k

作为该结点的类标记，返回T.

若A=

emptyset

，则T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T；

否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征

A_g

；

如果

A_g

的信息增益比小于阈值

epsilon

，则置T为单结点树，并将D中实例数最大的类

C_k

作为该结点的类标记，返回T；

否则，对

A_g

的每一个可能值

a_i

，将D分割为若干个非空子集

D_i

，将

D_i

中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T.

对第i个子节点，以

D_i

为训练集，以

A-A_g

为特征集，递归调用步（1）-（5），得到字数

T_i

，返回

T_i

。

决策树剪枝

决策树生成算法可能产生过于复杂的树结构，发生过拟合的现象，解决此问题的方法就是对其简化，即剪枝。

先验设定控制复杂度

设置树的最大深度，防止过深。
设置节点的熵的最小阈值。
设置每个节点所包含的最小样本数量。

决策树剪枝一种方法是通过极小化决策树整体损失函数或代价函数实现。

损失函数

设数T的叶节点个数为

|T|

，对于叶节点t，其有

N_t

个样本点，其中k类有样本点

N_{tk}

个，

H_t(T)

为叶节点t上的经验熵，

alpha geq 0

为参数，损失函数定义为：

C_alpha(T) = sum_{t=1}^{|T|} N_t H_t(T) alpha|T|

经验熵为：

H_t(T) = -sum_k frac{N_{tk}}{N_t}

记

C(T) = sum_{t=1}^{|T|} N_t H_t(T) = - sum_{t=1}^{|T|} sum_{k=1}^{|K|} N_{tk}log{frac{N_{tk}}{N_t}}

得到：

C_alpha(T) = C(T) alpha|T|

其中，

C(T)

表示模型对训练数据的误差，即拟合度。|T|表示模型复杂度，参数

alpha geq 0

控制两者之间的影响。

剪枝算法

剪枝，就是在确定α情况下，选择损失函数最小的模型。

输入：生成算法产生的整个数T，参数α

输出：修剪之后的子树

T_alpha

计算每个节点的经验熵
递归的从树的叶节点向上回缩。对比回缩到其父节点前后的树

T_B, T_A

，比较其损失函数，若

C_alpha(T_A) leq C_alpha(T_B)

，则进行剪枝，父节点变为新的节点。

返回2，直到不能继续为止，获得损失函数最小的子树

T_alpha

CART算法

分类与回归树（CART）同样由特征选择、树的生成和剪枝组成。但CART还在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。

CART假设决策树是二叉树，递归地二分每个特征，将输入空间划分为有限个单元，并在这些单元上预测概率分布。 CART由两步组成： 1. 树生成：基于训练集生成决策树，生成决策树尽量地大。 2. 树的剪枝：用验证集对已生成的树进行剪枝并选择最优子树。

CART生成

CART生成就是递归地构建二叉决策树过程，特征选择有两种标准：回归树用平方误差最小、分类树用Gini指数最小化准则。

最小二乘回归树生成算法

输入：训练数据集；

输出：回归树f(x);

在训练数据集所在输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

选择最优切分变量j与切分点s，求解

minlimits_{j,s} [ minlimits_{c_1} sumlimits_{x_i in R_1(j,s)} (y_i-c_1)^2 minlimits_{c_2} sumlimits_{x_i in R_2(j,s)} (y_i - c_2)^2]

其中，

R_1(j,s) = {x|x^{(j)} le s}, R_2(j,s) = {x|x^{(j)} ge s}

，遍历变量j，对固定切分变量j扫描切分点s，选择是上式达到最小值的对(j,s)。

用选定的对(j,s)划分区域并决定相应的输出值。

R_1(j,s) = {x|x^{(j)} le s}, R_2(j,s) = {x|x^{(j)} ge s}

hat{c} = frac{1}{N_m} sumlimits_{x_i in R_m(j,s)} y_i,x in R_m, m =1,2

继续对两个子区域调用步骤1,2，直到满足停止条件。
将输入空间划分为M个区域，

R_1,R_2,···R_m

，生成决策树。

f(x) = sumlimits_{m=1}^{M} hat{c} I(x in R_m)

分类树的生成

Gini指数

分类问题中，假设K个类，样本点属于第k类的概率为

p_k

，则概率分布的基尼指数为:

Gini(p) = sumlimits_{k=1}^K p_k(1-p_k) = 1- sumlimits_{k=1}^K p_k^2

对于二分类问题，K=2,

Gini(p) = 2p(1-p)

实际情况中，对于给定样本集合D，并没有

p_k

值，令

p_k = frac{|C_k|}{|D|}

，其基尼指数为：

Gini(D) = 1-sumlimits_{k=1}^K (frac{|C_k|}{|D|})^2

其中

C_k

是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一可能值a被分割成

D_1,D_2

两部分，即

D_1 = { (x,y) in D|A(x) =a},D_2 = D-D_1

则在特征A的条件下，集合D的基尼指数定义为：

Gini(D,A)= frac{|D_1|}{|D|}Gini(D_1) frac{|D_2|}{|D|}Gini(D_2)

CART生成算法

输入：数据集D，停止计算的条件；

输出：CART决策树。

根据训练数据集合，从根节点开始，递归地对每个结点进行如下步骤：

设结点的悬链数据集为D，计算现有特征对该数据集的Gini指数，对于每一个特征A，对其每个取值a，将其分割为“是”和“不是”两部分，计算A=a时的Gini指数。
在所有可能的特征A以及他们所有可能的切分点a中，选择Gini指数最小的特征及其对应的切分点作为最优特征与最优切分点。然后依最优特征和切分点切分结点为两个子结点，将其对应的数据集依特征分配到两个子节点中取。
对两个子结点递归地调用1,2，直到满足停止条件。
生成CART决策树。

算法停止条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或没有更多的特征。

CART剪枝

定义损失函数：

C_alpha(T) = C(T) alpha|T|

其中C(T)为对训练数据的预测误差（可以是Gini指数，或者平方差），|T|为树的叶结点个数，

alpha

为参数，参数

alpha

权衡训练数据的拟合程度与模型的复杂度。

CART剪枝算法

输入：CART算法生成的决策树

T_0

；

输出：最优决策树

T_alpha

;

k = 0 , T = T_0

，设

alpha = infty

。

自上而下地对各内部结点t计算

C(T_t),|T|

以及

g(t) = frac{C(t)-C(T_t)}{|T_t|-1}

alpha = min(alpha, g(t))

其中

T_t

表示以t为根节点的子树，

C(T_t)

是对训练数据的预测误差，

|T_t|

是

T_t

的叶结点个数。

g(t) = alpha

的内部结点t进行剪枝，并对叶结点t以多数表决法决定其分类，得到树T。

k = k 1,alpha_k = alpha, T_k=T

。

如果

T_k

不是由根节点及两个叶结点构成的树，则回到步骤2，否则

T_k = T_n

。

采用交叉验证法在子树序列

T_0,T_1,···T_n

中选取最优子树

T_alpha

。

附录

算法分类

机器学习算法按照学习方式分为监督学习、非监督学习、半监督学习、强化学习

监督学习：从给定的训练数据集中学习出一个函数，当新的数据到来时，可以根据这个函数预测结果。训练集中的目标是由人标注的。

非监督式学习：与监督学习相比，训练集没有人为标注的结果。常见的非监督式学习算法有聚类。

半监督式学习：输入数据部分被标识，部分没有被标识，介于监督式学习与非监督式学习之间。常见的半监督式学习算法有支持向量机。

强化学习：在这种学习模式下，输入数据作为对模型的反馈，不像监督模型那样，输入数据仅仅是作为一个检查模型对错的方式，在强化学习下，输入数据直接反馈到模型，模型必须对此立刻作出调整。常见的强化学习算法有时间差学习。

按照算法类似性分为决策树学习、回归、聚类、人工神经网络

决策树：根据数据的属性采用树状结构建立决策模型。决策树模型常常用来解决分类和回归问题。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5、随机森林 (Random Forest) 等。

回归算法：试图采用对误差的衡量来探索变量之间的关系的一类算法。常见的回归算法包括最小二乘法 (Least Square)、逻辑回归 (Logistic Regression)、逐步式回归 (Stepwise Regression) 等。

聚类算法：通常按照中心点或者分层的方式对输入数据进行归并。所有的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类。常见的聚类算法包括 K-Means 算法以及期望最大化算法 (Expectation Maximization) 等。

人工神经网络：模拟生物神经网络，是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络算法包括感知器神经网络 (Perceptron Neural Network) 、反向传递 (Back Propagation) 和深度学习等。

CSDN博客：http://blog.csdn.net/shine19930820/article/details/62233166

参考资料

《统计学习方法》《The Elements of Statistical Learning 》《Machine Learning A Probabilistic Perspective》 Top 10 algorithms in data mining

相似算法：

『数据挖掘十大算法』笔记一：决策树
『数据挖掘十大算法』笔记二：SVM-支持向量机
『数据挖掘十大算法』笔记三：K-means

决策树机器学习神经网络深度学习人工智能

0 人点赞

『数据挖掘十大算法 』笔记一：决策树

数据挖掘Top 10算法

决策树模型与学习

特征选择

信息增益

熵(entropy)

条件熵

信息增益

信息增益算法

信息增益比

决策树生成

ID3算法

C4.5算法

决策树剪枝

先验设定控制复杂度

损失函数

剪枝算法

CART算法

CART生成

最小二乘回归树生成算法

分类树的生成

Gini指数

CART生成算法

CART剪枝

CART剪枝算法

附录

算法分类

参考资料

相似算法：

『数据挖掘十大算法』笔记一：决策树