数据挖掘学习笔记：分门别类、统计学习【转载】

数据挖掘学习笔记：分类、统计学习【转载】

信息增益是用来衡量样本集S下属性A分裂时的信息熵减少量：

信息增益是信息熵的有效减少量，值越高，说明目标属性在参考属性处损失的信息熵越多，也就是失去的不确定性越多，那么在决策树进行分类的时候，它就应该越早作为决策的依据属性。

但是，使用信息增益作为判断节点分裂依据的一个缺陷在于它偏向于选择具有更多取值的属性作为节点分裂属性，而实际上属性值较多的属性不一定是最优的分类属性。

C4.5算法使用信息增益率来取代信息增益，信息增益率的定义：

其中Gain(S,A)是上面提到过的信息增益，而SplitInfo(S,A)指的是分裂信息，代表了按照属性A来分裂样本集S的广度和均匀性：

公式中，从S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。

2、在树构造过程中进行剪枝；

3、能够完成对连续属性的离散化处理：

对于连续型属性进行排序，得到多个阈值，取能够产生最大信息增益的阈值作为分裂的阈值。

4、能够对不完整数据进行处理：

在数据不完整时，对于某个具有缺失值的属性计算信息增益率，有几种处理办法，例如直接忽略该类样本，选择常用值或均值填充等等。

?

?

CART

CART（Classification And Regression Tree，分类回归树）采用一种二分递归分割的技术，将当前样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。

还是举和《使用ID3算法构造决策树》一样的例子，现在我们要研究狗的智商，潜在的关联因子包括毛的长度和颜色：

在决策树的每一个节点上都可以按照任一个属性来划分，但是到底按照那种属性来划分，需要用一个数值来衡量，例如Gini指数，如果我们用k，k=1,2,3……c表示类，其中c是类别集Result的因变量数目，pk表示观测点中属于k类的概率，一个节点A的Gini指数定义为：

好，我们现在最终是要考察哪一个潜在关联因子和狗的智商关联度最高。先看毛长度，智商为高的狗有三条，毛长度一个短、两个长；智商为低的狗有一条，短毛：

k在这张图里可以理解成圆的半径，当k取值较小时，范围为图中实线的圆，圆内红色点数目多过蓝色点，因此绿色的待分类点属于红色点集的分类；当k取值较大，范围为图中虚线的圆时，蓝色点有三个，多于两个红色点，因此绿色的待分类点属于蓝色点集的分类。

当然，这只是最简单的一个例子，实际应用中，会有很多的推广情形，以及许多改进。例如，可以把二维的例子推广到N维；可以引入不同的距离计算方法（如把欧氏距离变成汉明距离）；可以引入权值，增强较近的点对结果的影响等等。

?

Naive Bayes

朴素贝叶斯分类，对部分未知的状态用主观概率估计，然后用贝叶斯公式对概率进行修正，最后再利用期望值和修正概率做出最优决策的分类方法。基本思想是：

1. 已知类条件概率密度参数表达式和先验概率；
2. 利用贝叶斯公式转换成后验概率；
3. 根据后验概率大小进行决策分类。

请参见我曾经写过的一篇文章《朴素贝叶斯分类》，已经详细介绍了。

?

SVM

SVM（Support Vector Machine，支持向量机）是一种对线性数据和非线性数据进行分类的算法。它使用非线性映射，把原训练数据映射到较高维上，并且搜索新维度的最佳分离超平面，即将一个类的元素和其他类分离的最佳决策边界。

下面两幅图来自维基百科：

从上图可见，两个维度上看，有两组数据，一组黑点表示，一组白点表示，直线H1并未做到分类；H2虽然做到分类，但是两类之间的空隙太小；H3分类了，并且使得两类之间的空隙最大。

这幅图展示分隔两个分类的“最佳分离超平面”（两个虚线之间的最短距离达到最大），而落在图中虚线之间、得以成功分隔这两个分类的的超平面，都被称为“支持向量”。

SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如前面介绍的分类方法，基于规则的分类器和人工神经网络等等）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。另外，SVM一般只能用在二类问题，对于多类问题效果不好。

在低维线性不可分的模式通过非线性映射到高维特征空间后，可能可以做到线性可分了，但是维度的增加会引发计算量指数级增长的问题。核函数就是用来解决这样的问题的，上面和下面共两张图都来自pluskid的博客，上图可见这个数据集线性不可分，现在把平面空间点映射到三维空间后，再旋转坐标轴，使得重新满足线性可分：

?

EM

EM（Expectation-maximization，期望最大）算法在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。

在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计（一种统计方法，它用来求一个样本集的相关概率密度函数的参数。）或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望经常用在机器学习和计算机视觉的数据聚类领域。

• 最大期望算法经过两个步骤交替进行计算：
  第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；
• 第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。

  M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

  

  EM的整个推导过程请参见JerryLead的这篇文章。

  ?