数据挖掘算法（十大算法）

数据挖掘算法（十大算法）

概念描述

数据挖掘算法是根据数据创建数据挖掘模型的一组试探法和计算。 为了创建模型，算法将首先分析您提供的数据，并查找特定类型的模式和趋势。算法使用此分析的结果来定义用于创建挖掘模型的最佳参数。然后，这些参数应用于整个数据集，以便提取可行模式和详细统计信息。

算法根据您的数据创建的挖掘模型可以采用多种形式，这包括：

说明数据集中的事例如何相关的一组分类。

预测结果并描述不同条件是如何影响该结果的。

预测销量的数学模型。

说明在事务中如何将产品分组到一起的一组规则，以及一起购买产品的。

算法分类

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

ID3选择属性用的是子树的（这里可以用很多方法来定义信息，ID3使用的是熵（entropy）（熵是一种不纯度度量准则）），也就是熵的变化值，而C4.5用的是。也就是多了个率嘛。一般来说率就是用来取平衡用的，就像起的作用差不多，有两个跑步的人，一个起点是10m/s的人、其1s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果仅算差值那么两个差距就很大了，如果使用速度增加率（）来衡量，2个人就是一样的了。在这里，其克服了用选择属性时偏向选择取值多的属性的不足。在树构造过程中进行剪枝，我在构造的时候好讨厌那些挂着几个元素的节点。对于这种节点，干脆不考虑最好，不然很容易导致overfitting。对非都能处理，这个其实就是一个个式，看对于连续型的值在哪里分裂好。也就是把的数据转化为的值进行处理。能够对不完整数据进行处理，这个重要也重要，其实也没那么重要，缺失数据采用一些方法补上去就是了。

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

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

(朴素贝叶斯NB)

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive BayesianModel，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

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

(支持向量机SVM)

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

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

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

8：FP-Tree

(Miningfrequent patterns without candidate generation)

这个也不太清楚。算法(Frequent Pattern-growth)使用了一种紧缩的来存储查找所需要的全部信息。采用算法：将提供的数据库压缩到一棵来保留项集关联信息，然后将压缩后的数据库分成一组条件数据库（一种特殊类型的投影数据库），每个条件数据库关联一个频繁项集。

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

10：HITS

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

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

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

k-means 算法的工作过程说明如下：首先从n个数据对象任意选择k 个对象作为初始中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

12：BIRCH

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

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

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

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

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

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

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

14：GSP

GSP，全称为Generalized Sequential Pattern(广义模式)，是一种序列挖掘算法。对于序列挖掘没有仔细看过，应该是基于的吧！网上是这样说的：

GSP类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的-----哈希树来实现候选模式的快速访存。

GSP算法描述:

1）扫描，得到长度为1的L1，作为初始的种子集。

2）根据长度为i 的种子集Li ，通过连接操作和修剪操作生成长度为i+1的候选Ci+1；然后扫描，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。

3）重复第二步，直到没有新的或新的候选序列模式产生为止。

产生候选主要分两步：

连接阶段：如果去掉s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中。

修切阶段：若某候选的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。

候选的支持度计算：对于给定的候选序列模式集合C，扫描，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数。

15：PrefixSpan

又是一个类似Apriori的序列挖掘。

 

其中经典十大算法为：C4.5，K-Means，SVM，Apriori，EM，PageRank，AdaBoost，KNN，NB和CART。