数据挖掘十大经典算法个人总结

数据挖掘十大经典算法个人总结
这两年对数据挖掘相关知识研究运用的已经很多了，最近看了关于数据挖掘十大经典算法的文章。想对其进行一个总结，强化下自己对这些算法的理解。
1. C4.5

C4.5 是基于ID3算法改进的决策树算法。相对于ID3，其伪代码：

它具有的特点：
1) 用信息增益率来选择属性
信息增益会偏向选择取值多的属性，而信息增益率除以H（v）来削弱这种偏向。

信息增益率：IG-ratio

　　　　

2) 在树构造过程中进行剪枝；
C4.5采用悲观剪枝法，它使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集。

悲观剪枝法的基本思路是：设训练集生成的决策树是T，用T来分类训练集中的N的元组，设K为到达某个叶子节点的元组个数，其中分类错误地个数为J。由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树，其叶节点个数为L(s)， 为到达此子树的叶节点的元组个数总和， 为此子树中被错误分类的元组个数之和。在分类新的元组时，则其错误分类个数为 ，其标准错误表示为：  。当用此树分类训练集时，设E为分类错误个数，当下面的式子成立时，则删掉子树S，用叶节点代替，且S的子树不必再计算。

         。

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

C4.5是如何处理连续属性的呢？实际上它先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：<=vj的分到左子树，>vj的分到右子树。计算这N-1种情况下最大的信息增益率。对于连续属性，这样计算量是相当大的。可以进行排序，只有在决策属性发生改变的地方才需要切开。

4) 能够对不完整数据进行处理。

2. K-means

K-means算法是很典型的基于距离的硬聚类算法。

算法过程图所示： 

从上图中，我们可以看到，A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。

然后，K-Means的算法如下：

1. 随机在图中取K（这里K=2）个种子点。
2. 然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）
3. 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
4. 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。

3. SVM

SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高纬特征空间使其线性可分，从而 使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；

SVM应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难”．

4. Apriori 关联规则挖掘

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。
5. EM

最大期望算法（Expectation Maximization Algorithm，又译期望最大化算法），是一种迭代算法，用于含有隐变量（hidden variable）的概率参数模型的最大似然估计或极大后验概率估计。

最大期望算法经过两个步骤交替进行计算：

第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。

循环重复直到收敛 {

      （E步）对于每一个i，计算

                  

      （M步）计算

                  

6. Pagerank

PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票，Google根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

假设一个由4个页面组成的小团体：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的Pagerank总和。

实际中

如果网页A有链接到网页B，则存在一条有向边A->B，下面是一个简单的示例：

上网者的概率分布V的计算过程：

 

最终V=[3/9,2/9,2/9,2/9]：

7. Adaboost

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。

类似思想的算法有 Boosting和Bagging。Bagging方法通过重新随机选取训练集增加了神经网络集成的差异度，从而提高了泛化能力。Bagging能提高不稳定学习算法的预测精度，而对稳定的学习算法效果不明显。而boosting重采样的不是样本，而是样本的分布，对于分类正确的样本权值低，分类错误的样本权值高（通常是边界附近的样本），最后的分类器是很多弱分类器的线性叠加（加权组合），分类器相当简单。

adaBoost算法对boosting进行了调整：

1. 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；

2. 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。

8. K-NN 最近邻分类回归

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

算法步骤：

step.1---初始化距离为最大值

step.2---计算未知样本和每个训练样本的距离dist

step.3---得到目前K个最临近样本中的最大距离maxdist

step.4---如果dist小于maxdist，则将该训练样本作为K-最近邻样本

step.5---重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完

step.6---统计K-最近邻样本中每个类标号出现的次数

step.7---选择出现频率最大的类标号作为未知样本的类标号

其中距离算法根据不同数据来选择，如欧式距离。

我的KNN/WAkNN根据不同k值，不同输入变量，匹配效果分析代码：

https://github.com/fengyejack/kNN-analysis/

9. Naive Bayes 朴素贝叶斯算法

首先，贝叶斯分类的基础：

贝叶斯定理：

      

  朴素贝叶斯分类的正式定义如下：

      1、设为一个待分类项，而每个a为x的一个特征属性。

      2、有类别集合。

      3、计算。

      4、如果，则。

通过

      

可以计算。

10. CART 分类和回归树

分类回归树算法：CART(Classification And Regression Tree)算法

  分类树两个基本思想：第一个是将训练样本进行递归地划分自变量空间进行建树的想法，第二个想法是用验证数据进行剪枝。

CART 首先进行建树。对所有可能分类计算器Gini值（Gini越小，数据越纯）

根据Gini值进行划分，选择分类后Gini增益最小的划分。

CART算法采用后剪枝方法，用独立的验证数据集。