数据挖掘学习笔记：分类、统计学习

ICDM（国际数据挖掘大会）2006 年从 18 种提名的数据挖掘算法中投票选出了十大算法。这 18 中提名数据挖掘算法分属 10 大数据挖掘主题，蓝色部分即为最终选出的十大算法：

分类（Classification）
- C4.5
- CART
- K Nearest Neighbours
- Naive Bayes
统计学习（Statistical Learning）
- SVM
- EM
关联分析（Association Analysis）
- Apriori
- FP-Tree
链接挖掘（Link Mining）
- PageRank
- HITS
聚类（Clustering）
- K-Means
- BIRCH
袋装与推进（Bagging and Boosting）
- AdaBoost
序列模式（Sequential Patterns）
- GSP
- PrefixSpan
集成挖掘（Integrated Mining）
- CBA
粗糙集（Rough Sets）
- Finding Reduct
图挖掘（Graph Mining）
- gSpan

以下是其中关于分类和统计学习主题的笔记。

C4.5

C4.5 算法源于 ID3 算法，也是一种分类决策树算法，但是做了如下的改进：

1、用 “信息增益率” 代替 “信息增益” 来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足：

关于 “信息增益率”，先要理解 “信息增益（Information Gain）”，请参见《使用 ID3 算法构造决策树》这篇文章，里面既介绍了 C4.5 的前身 ID3 算法，同时，也以一个实际例子提到了 “信息熵” 和 “信息增益” 的含义，这个例子理解以后，下面对于信息熵和信息增益的公式就清楚了。

信息熵（Entropy）：

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

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

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

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

Gain Ratio

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

Split Info

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

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

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

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

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

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

CART

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

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

颜色（color）	毛长度（length）	智商（IQ）
black	长	高
white	长	高
white	短	高
white	短	低

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

GINI

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

Gini(length) = (3/4) * ( 1-( (1/3)² + (2/3)² ) ) + (1/4) * ( 1-( (1/1)² ) )

再看颜色，智商高的狗有三条，颜色两白一黑；智商低的狗有一条，颜色白：

Gini(color) = (3/4) * ( 1-( (1/3)² + (2/3)² ) ) + (1/4) * ( 1-( (1/1)² ) )

最后比较两者的 Gini 系数，如果 Gini(length) 更小，那么使用毛长度的划分要更好（但是这个例子里面可以看出二者的 Gini 系数相同）。

关于终止条件：最简单的情况是，如果只剩下一个元素了，或者包含元素都属于同一个类别了，那么分类就可以停止了，但是我们也可以设定一个阈值，低于这个阈值时就没有必要继续划分了。

关于剪枝：使用验证数据进行剪枝是 CART 的一个重要思想。最常见的有两种剪枝方式，预剪枝和后剪枝。预剪枝就是满足剪枝条件时树停止生长，后剪枝就是在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。

关于分类后的回归：现实中会有些数据很复杂，肉眼几乎看不出符合那种模型，因此构建全局的模型就有点不合适。“回归” 就是为了解决这类问题，在构建决策节点把数据数据切分成区域之后，局部区域可以进行回归拟合，例如最后取值为叶节点目标变量的加权值。

KNN

KNN（K Nearest Neighbours）属于比较简单的一种用来归类的算法，给定一个表示范围的 k 值，从而确定了一定的范围，然后根据范围内的点的分布来确定待分类目标点属于哪个范围。下面这张图来自维基百科。

knn

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

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

Naive Bayes

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

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

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

SVM

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

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

svm

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

svm2

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

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

two_circles

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

rotate