一、数据挖掘算法的定义

数据挖掘算法是根据数据创建数据挖掘模型的一组试探法和计算。 为了创建模型，算法将首先分析您提供的数据，并查找特定类型的模式和趋势。
二、数据挖掘算法的分类

1.数据挖掘经典算法

表格 1数据挖掘18种算法
算法名称
类别




Classification
（分类）
C4.5
CART
K Nearest Neighbours (kNN)
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、CART、KNN(K Nearest Neighbours)、Naive Bayes、SVM、EM(期望最大化)、Apriori、PageRank、K-Means和AdaBoost是ICDM评选出来的十大经典算法。ICDM是国际顶尖的数据挖掘的会议。这十种算法在数据挖掘领域都产生了极为深远的影响。
(1)Classification（分类）
1）C4.5
C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
（a）用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。信息增益率计算公式如下：

其中分母的位置是分裂因子：
（b）在树构造过程中进行剪枝；
（c）能够完成对连续属性的离散化处理；
（d）能够对不完整数据进行处理。

2）CART：分类与回归树
CART：Classification and Regression Trees。CART算法也是一种决策树分类算法。CART分类回归树算法的本质也是对数据进行分类的，最终数据的表现形式也是以树形的模式展现的。
CART算法与C4.5算法不同的是：
（a）CART最后形成的树是一个二叉树，每个节点会分成2个节点，左孩子节点和右孩子节点。
（b）CART算法对于属性的值采用的是基于Gini系数值的方式做比较，gini某个属性的某次值的划分的gini指数的值为：

pk就是分别为正负实例的概率，gini系数越小说明分类纯度越高。
（c）CART算法在把数据进行分类之后，会对树进行一个剪枝，常用的用前剪枝和后剪枝法，而常见的后剪枝发包括代价复杂度剪枝，悲观误差剪枝等等，我写的此次算法采用的是代价复杂度剪枝法。代价复杂度剪枝的算法公式为：

α表示的是每个非叶子节点的误差增益率，可以理解为误差代价，最后选出误差代价最小的一个节点进行剪枝。
里面变量的意思为：
是子树中包含的叶子节点个数;
是节点t的误差代价，如果该节点被剪枝;

r(t)是节点t的误差率;
p(t)是节点t上的数据占所有数据的比例。

3）kNN: k-nearest neighbor classification
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
算法的主要过程为：
1、给定一个训练集数据，每个训练集数据都是已经分好类的。
2、设定一个初始的测试数据a，计算a到训练集所有数据的欧几里得距离，并排序。
3、选出训练集中离a距离最近的K个训练集数据。
4、比较k个训练集数据，选出里面出现最多的分类类型，此分类类型即为最终测试数据a的分类。
如图：

？

比如上面这个图，我们有两类数据，分别是蓝色方块和红色三角形，他们分布在一个上图的二维中间中。那么假如我们有一个绿色圆圈这个数据，需要判断这个数据是属于蓝色方块这一类，还是与红色三角形同类。怎么做呢？我们先把离这个绿色圆圈最近的几个点找到，因为我们觉得离绿色圆圈最近的才对它的类别有判断的帮助。那到底要用多少个来判断呢？这个个数就是k了。如果k=3，就表示我们选择离绿色圆圈最近的3个点来判断，由于红色三角形所占比例为2/3，所以我们认为绿色圆是和红色三角形同类。如果k=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。从这里可以看到，k的值还是很重要的。

4）Naive Bayes
在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
（2）Statistical Learning（统计学习）
（1）Support vector machines（SVM）
支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。
SVM算法的具体原理得要分成2部分，一个是线性可分的情况，一个是线性不可分的情况，下面说说线性可分的情况：
（a）线性可分的情况
下面是一个二维空间的形式：


中间的那条线就是划分的分割线，我们可以用f(X)=w*x+b，w和x在这里都是向量的形式。向这样的分割线，只要稍稍移动一下，又会有一个正确的目标线，因此我们要找的一个目标解，当然是找出分割的临界条件。
（b）线性不可分的情况
同样给出一张图:

我们只能找出这样的条曲线将ab这个条线段进行分割。这时，就用到了在开始部分介绍的4个核函数。
选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种：
⑴线性核函数K(x,y)=x·y；
⑵多项式核函数K(x,y)=[(x·y)+1]^d；
⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2）
⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）
但是在有的时候为了数据的容错性和准确性，我们会加入惩罚因子C和ε阈值(保证容错性)
限制条件为：



2）最大期望(EM)算法
在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然 估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。
（3）Association Analysis（关联分析）
1）The Apriori algorithm
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
2）FP-Tree
FP-Tree算法的基本数据结构，包含一个一棵FP树和一个项头表，每个项通过一个结点链指向它在树中出现的位置。基本结构如下所示。需要注意的是项头表需要按照支持度递减排序，在FP-Tree中高支持度的节点只能是低支持度节点的祖先节点。
（4）Link Mining（链接挖掘）
1）PageRank
PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。
PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票， 被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自 学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。
2）HITS
HITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念，HITS算法是受用户查询条件影响的，他一般用于小规模的数据链接分析，也更容易遭受到攻击
（5）Clustering（聚类）
1）The k-means algorithm即K-Means算法
k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均 方误差总和最小。
2）BIRCH
BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)是一个综合的层次聚类算法。BIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看做数据的多层压缩。
（6）Bagging and Boosting（袋装与推进）
1）AdaBoost
Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权 值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。
（7）Sequential Patterns（序列模式）
1）GSP
GSP算法是一种非常有效的序列模式挖掘算法，该算法使用一种称作为逐层搜索的迭代方法，首先找出频繁1-序列模式的集合F1，F1用于寻找频繁2-序列模式F2，F2用于寻找频繁3-序列模式、F3...，如此下去，直到不能找到频繁序列模式为止。
2）PrefixSpan
PrefixSpan算法仅仅检测称为prefix的前段序列片，将这个数据库在这个prefix上投影，挖掘其中的频繁项，然后扩充到prefix中，继续发掘，直到挖掘出所有的频繁序列。时空效率要比类Apriori算法有较大的提高。
（8）Integrated Mining（集成挖掘）
1）CBA
CBA算法全称是Classification base of Association，就是基于关联规则进行分类的算法，说到关联规则，我们就会想到Apriori和FP-Tree算法都是关联规则挖掘算法，而CBA算法正是利用了Apriori挖掘出的关联规则，然后做分类判断，所以在某种程度上说，CBA算法也可以说是一种集成挖掘算法。
（9）Rough Sets（粗糙集）
1）Finding reduct
粗糙集算法。粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。
（10）Graph Mining（图挖掘）
1）gSpan
gSpan算法属于图挖掘算法领域。，主要用于频繁子图的挖掘，相较于其他的图算法，子图挖掘算法是他们的一个前提或基础算法。gSpan算法用到了DFS编码，和Edge五元组，最右路径子图扩展等概念，算法比较的抽象和复杂。

2.其他算法

（1）GA
遗传算法。遗传算法运用了生物进化理论的知识来寻找问题最优解的算法，算法的遗传进化过程分选择，交叉和变异操作，其中选择操是非常关键的步骤，把更适应的基于组遗传给下一代。
（2）DbScan
基于空间密度聚类算法。dbScan作为一种特殊聚类算法，弥补了其他算法的一些不足，基于空间密，实现聚类效果，可以发现任意形状的聚簇。
（3）GA_Maze
遗传算法在走迷宫游戏中的应用。将走迷宫中的搜索出口路径的问题转化为遗传算法中的问题通过构造针对此特定问题的适值函数，基因移动方向的定位，巧的进行问题的求解。
（4）CABDDCC
基于连通图的分裂聚类算法。也是属于层次聚类算法主要分为2个阶段，第一阶段构造连通图。第二个阶段是分裂连通图，最终形成聚类结果。
（5）Chameleon
两阶段聚类算法。与CABDDCC算法相反，最后是通过对小簇集合的合并，形成最终的结果，在第一阶段主要是通过K近邻的思想形成小规模的连通图，第二阶段通过RI(相对互连性)和RC(相对近似性)来选一个最佳的簇进行合并。
（6）RandomForest
随机森林算法。算法思想是决策树+boosting.决策树采用的是CART分类回归数,通过组合各个决策树的弱分类器,构成一个最终的强分类器,在构造决策树的时候采取随机数量的样本数和随机的部分属性进行子决策树的构建,避免了过分拟合的现象发生。
（7）KDTree
K-Dimension Tree。多维空间划分树，数据在多维空间进行划分与查找。主要用于关键信息的搜索，类似于在空间中的二分搜索，大大提高了搜索效率，在寻找目标元素时，使用了DFS深度优先的方式和回溯进行最近点的寻找。
（8）MS-Apriori
基于多支持度的Apriori算法。是Apriori算法的升级算法，弥补了原先Apriori算法的不足，还增加了支持度差别限制以及支持度计数统计方面的优化，无须再次重新扫描整个数据集，产生关联规则的时候可以根据子集的关系避免一些置信度的计算。
（9）ACO
蚁群算法。蚁群算法又称为蚂蚁算法。同GA遗传算法类似，也是运用了大自然规律的算法，用于在图中寻找最优路径的概率型算法。灵感来源于蚂蚁在寻找食物时会散播信息素的发现路径行为。