数据挖掘算法:创建数据挖掘模型的算法-中文百科频道

简介

国际权威的学术组织the IEEE International Conference on Data Mining(ICDM)评选出了数据挖掘领域的十大经典算法：C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,Naive Bayes,and CART.

算法分类

C4.5

C4.5就是一个决策树算法，它是决策树（决策树也就是做决策的节点间像一棵树一样的组织方式，其实是一个倒树）核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。C4.5比ID3改进的地方时：

CART

CART也是一种决策树算法！相对于上着有条件实现一个节点下面有多个子树的多元分类，CART只是分类两个子树，这样实现起来稍稍简便些。所以说CART算法生成的决策树是结构简洁的二叉树。

KNN(KNearestNeighbours)

这个很简单，就是看你周围的K个人（样本）中哪个类别的人占的多，哪个多，那我就是多的那个。实现起来就是对每个训练样本都计算与其相似度，是Top-K个训练样本出来，看这K个样本中哪个类别的多些，谁多跟谁。

NaiveBayes

(朴素贝叶斯NB)

NB认为各个特征是独立的，谁也不关谁的事。所以一个样本（特征值的集合，比如“数据结构”出现2词，“文件”出现1词），可以通过对其所有出现特征在给定类别的概率相乘。比如“数据结构”出现在类1的概率为0.5，“文件”出现在类1的概率为0.3，则可认为其属于类1的概率为0.5*0.5*0.3。

SupportVectorMachine

(支持向量机SVM)

SVM就是想找一个分类得最”好”的分类线/分类面（最近的一些两类样本到这个”线”的距离最远）。这个没具体实现过，上次听课，那位老师自称自己实现了SVM，敬佩其钻研精神。常用的工具包是LibSVM、SVMLight、MySVM。

EM(期望最大化)

这个我认为就是假设数据时由几个高斯分布组成的，所以最后就是要求几个高斯分布的参数。通过先假设几个值，然后通过反复迭代，以期望得到最好的拟合。

Apriori

这个是做关联规则用的。不知道为什么，一提高关联规则我就想到购物篮数据。这个没实现过，不过也还要理解，它就是通过支持度和置信度两个量来工作，不过对于Apriori，它通过频繁项集的一些规律（频繁项集的子集必定是频繁项集等等啦）来减少计算复杂度。

FP-Tree

(Mining frequent patterns without candidate generation)

PageRank

大名鼎鼎的PageRank大家应该都知道（Google靠此专利发家，其实也不能说发家啦!）。对于这个算法我的理解就是：如果我指向你（网页间的连接）则表示我承认你，则在计算你的重要性的时候可以加上我的一部分重要性（到底多少，要看我自己有多少和我共承认多少个人）。通过反复这样来，可以求的一个稳定的衡量各个人（网页）重要性的值。不过这里必须要做些限制（一个人的开始默认重要性都是1），不然那些值会越来越大越来越大。

HITS

HITS也是一个连接分析算法，它是由IBM首先提出的。在HITS，每个节点（网页）都有一个重要度和权威度（Hubs and authorities,我也忘了具体的翻译是什么了）。通过反复通过权威度来求重要度，通过重要度来求权威度得到最后的权威度和重要度。

K-Means

K-Means是一种最经典也是使用最广泛的聚类方法，时至今日任然有很多基于其的改进模型提出。K-Means的思想很简单，对于一个聚类任务（你需要指明聚成几个类，当然按照自然想法来说不应该需要指明类数，这个问题也是当前聚类任务的一个值得研究的课题），首先随机选择K个簇中心，然后反复计算下面的过程直到所有簇中心不改变（簇集合不改变）为止：步骤1：对于每个对象，计算其与每个簇中心的相似度，把其归入与其最相似的那个簇中。

步骤2：更新簇中心，新的簇中心通过计算所有属于该簇的对象的平均值得到。

BIRCH

BIRCH也是一种聚类算法，其全称是Balanced Iterative Reducing and Clustering using Hierarchies。BIRCH也是只是看了理论没具体实现过。是一个综合的层次聚类特征(Clustering Feature,CF)和聚类特征树(CF Tree)两个概念，用于概括聚类描述。聚类特征树概括了聚类的有用信息，并且占用空间较元数据集合小得多，可以存放在内存中，从而可以提高算法在大型数据集合上的聚类速度及可伸缩性。

BIRCH算法包括以下两个阶段：

1）扫描数据库，建立动态的一棵存放在内存的CF Tree。如果内存不够，则增大阈值，在原树基础上构造一棵较小的树。

2）对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。

由于CF Tree的叶节点代表的聚类可能不是自然的聚类结果，原因是给定的阈值限制了簇的大小，并且数据的输入顺序也会影响到聚类结果。因此需要对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。

daBoost

AdaBoost做分类的一般知道，它是一种boosting方法。这个不能说是一种算法，应该是一种方法，因为它可以建立在任何一种分类算法上，可以是决策树，NB，SVM等。

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据，并将关键放在关键的训练数据上面。