数据挖掘中十大经典算法.pdf

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：1.00M 资料格式：pdf 举报版权申诉

d470969047h-9860858-4744302542906900612.pdf-第1页.png

第1页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第2页.png

第2页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第3页.png

第3页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第4页.png

第4页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第5页.png

第5页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第6页.png

第6页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第7页.png

第7页 / 共33页

d470969047h-9860858-4744302542906900612.pdf-第8页.png

第8页 / 共33页

文本预览

数据挖掘十大经典算法国际权威的学术组织 the IEEE International Conference on Data Mining (ICDM) 2006 年 12 月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的 18 种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5 算法是机器学习算法中的一种分类决策树算法,其核心算法是 ID3 算法. C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即 K-Means 算法 k-means algorithm 算法是一个聚类算法，把 n 的对象根据他们的属性分为 k 个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为 Support Vector Machine，简称 SV 机（论文中一般简称 SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是 C.J.C Burges 的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 5. 最大期望(EM)算法在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（ Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6. PageRank PageRank 是 Google 算法的重要内容。2001 年 9 月被授予美国专利，专利人是 Google 创始人之一拉里•佩奇（Larry Page）。因此，PageRank 里的 page 不是指网页，而是指佩奇，即这个

等级方法是以佩奇来命名的。 PageRank 根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank 背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的―链接流行度‖——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank 这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。 7. AdaBoost Adaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。 8. kNN: k-nearest neighbor classification K 最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 9. Naive Bayes 在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC 模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC 模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为 NBC 模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给 NBC 模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC 模型的分类效率比不上决策树模型。而在属性相关性较小时， NBC 模型的性能最为良好。 10. CART: 分类与回归树 CART, Classification and Regression Trees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。数据挖掘十大经典算法(1)C4.5 机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树是如何工作的？决策树一般都是自上而下的来生成的。选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径，这条路径就是一条―规则‖。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量： 1) 通过该节点的记录数 2) 如果是叶子节点的话，分类的路径 3) 对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。由于 ID3 算法在实际应用中存在一些问题，于是 Quilan 提出了 C4.5 算法，严格上说 C4.5 只能是 ID3 的一个改进算法。相信大家对 ID3 算法都很.熟悉了，这里就不做介绍。 C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。来自搜索的其他内容： C4.5 算法是机器学习算法中的一种分类决策树算法,其核心算法是 ID3 算法. 分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是: 根: 学习的事例集. 枝: 分类的判定条件. 叶: 分好的各个类. §4.3.2 ID3 算法 1.概念提取算法 CLS 1) 初始化参数 C={E},E 包括所有的例子,为根. 2) IF C 中的任一元素 e 同属于同一个决策类则创建一个叶子节点 YES 终止. ELSE 依启发式标准,选择特征 Fi={V1,V2,V3,．．．Vn}并创建判定节点划分 C 为互不相交的 N 个集合 C1,C2,C3,．．．,Cn； 3) 对任一个 Ci 递归. 2. ID3 算法 1) 随机选择 C 的一个子集 W (窗口). 2) 调用 CLS 生成 W 的分类树 DT(强调的启发式标准在后). 3) 顺序扫描 C 搜集 DT 的意外(即由 DT 无法确定的例子). 4) 组合 W 与已发现的意外,形成新的 W.

5) 重复 2)到 4),直到无例外为止. 启发式标准: 只跟本身与其子树有关,采取信息理论用熵来量度. 熵是选择事件时选择自由度的量度,其计算方法为 P = freq(Cj,S)/|S|; INFO(S)= - SUM( P*LOG(P) ) ; SUM()函数是求 j 从 1 到 n 和. Gain(X)=Info(X)-Infox(X); Infox(X)=SUM( (|Ti|/|T|)*Info(X); 为保证生成的决策树最小,ID3 算法在生成子树时,选取使生成的子树的熵(即 Gain(S))最小的的特征来生成子树. §4.3.3: ID3 算法对数据的要求 1. 所有属性必须为离散量. 2. 所有的训练例的所有属性必须有一个明确的值. 3. 相同的因素必须得到相同的结论且训练例必须唯一. §4.3.4: C4.5 对 ID3 算法的改进: 1. 熵的改进,加上了子树的信息. Split_Infox(X)= - SUM( (|T|/|Ti| ) *LOG(|Ti|/|T|) ); Gain ratio(X)= Gain(X)/Split Infox(X); 2. 在输入数据上的改进. 1) 因素属性的值可以是连续量,C4.5 对其排序并分成不同的集合后按照 ID3 算法当作离散量进行处理,但结论属性的值必须是离散值. 2) 训练例的因素属性值可以是不确定的,以 ? 表示,但结论必须是确定的 3. 对已生成的决策树进行裁剪,减小生成树的规模. 数据挖掘十大经典算法(2) k-means k-means algorithm 算法是一个聚类算法，把 n 的对象根据他们的属性分为 k 个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。假设有 k 个群组 Si, i=1,2,...,k。μi 是群组 Si 内所有元素 xj 的重心，或叫中心点。 k 平均聚类发明于 1956 年，该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm) 的迭代式改进探索法。劳埃德算法首先把输入点分成 k 个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。劳埃德算法和 k 平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决 k 平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。（上面函数中存在的不同的最优解）虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，David Arthur 和 Sergei Vassilvitskii 提出存在特定的点集使得 k 平均算法花费超多项式时间达到收敛。

近似的 k 平均算法已经被设计用于原始数据子集的计算。从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行 k 平均算法，选择最优解。 k 平均算法的一个缺点是，分组的数目 k 是一个输入参数，不合适的 k 可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。数据挖掘十大经典算法(3) Svm 支持向量机，英文为 Support Vector Machine，简称 SV 机（论文中一般简称 SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机属于一般化线性分类器 . 他们也可以认为是提克洛夫规范化（ Tikhonov Regularization）方法的一个特例.这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。 M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。 Vapnik 等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine,简称 SVM)。支持向量机的提出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法。 SVM 的主要思想可以概括为两点： (1) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。介绍支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是 C.J.C Burges 的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。动机

有很多个分类器(超平面）可以把数据分开，但是只有一个能够达到最大分割。我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点，而可以是任意(统计学符号)中或者 (计算机科学符号) 的点。我们希望能够把这些点通过一个 n-1 维的超平面分开，通常这个被称为线性分类器。有很多分类器都符合这个要求，但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。问题定义设样本属于两个类，用该样本训练 svm 得到的最大间隔超平面。在超平面上的样本点也称为支持向量. 我们考虑以下形式的样本点其中 ci 为 1 或−1 --用以表示数据点属于哪个类. 是一个 p − (统计学符号), 或 n − (计算机科学符号) 维向量，其每个元素都被缩放到[0,1]或[-1,1].缩放的目的是防止方差大的随机变量主导分类过程.我们可以把这些数据称为―训练数据‖，希望我们的支持向量机能够通过一个超平面正确的把他们分开。超平面的数学形式可以写作根据几何知识，我们知道向量垂直于分类超平面。加入位移 b 的目的是增加间隔.如果没有 b 的话，那超平面将不得不通过原点，限制了这个方法的灵活性。由于我们要求最大间隔，因此我们需要知道支持向量以及（与最佳超平面）平行的并且离支持向量最近的超平面。我们可以看到这些平行超平面可以由方程族：来表示。如果这些训练数据是线性可分的，那就可以找到这样两个超平面，在它们之间没有任何样本点并且这两个超平面之间的距离也最大.通过几何不难得到这两个超平面之间的距离是 2/|w|，因此我们需要最小化 |w|。同时为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的 i 满足其中的一个条件这两个式子可以写作：

原型现在寻找最佳超平面这个问题就变成了在(1)这个约束条件下最小化|w|.这是一个二次規劃 QP(quadratic programming)最优化中的问题。更清楚的，它可以表示如下：最小化 , 满足。 1/2 这个因子是为了数学上表达的方便加上的。对偶型(Dual Form) 把原型的分类规则写作对偶型，可以看到分类器其实是一个关于支持向量（即那些在间隔区边缘的训练样本点）的函数。支持向量机的对偶型如下：并满足 αi > = 0 软间隔 1995 年, Corinna Cortes 与 Vapnik 提出了一种改进的最大间隔区方法，这种方法可以处理标记错误的样本。如果可区分正负例的超平面不存在，则―软边界‖将选择一个超平面尽可能清晰地区分样本，同时使其与分界最清晰的样本的距离最大化。这一成果使术语―支持向量机‖ （或―SVM‖）得到推广。这种方法引入了松驰参数 ξi 以衡量对数据 xi 的误分类度。。随后，将目标函数与一个针对非 0ξi 的惩罚函数相加，在增大间距和缩小错误惩罚两大目标之间进行权衡优化。如果惩罚函数是一个线性函数，则等式(3)变形为数据挖掘十大经典算法(4)Apriori Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 Apriori 演算法所使用的前置统计量包括了：最大规则物件数：规则中物件组所包含的最大物件数量最小支援：规则中物件或是物件组必顸符合的最低案例数最小信心水准：计算规则所必须符合的最低信心水准门槛该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第 1 步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集,以及可能需要重复扫描数据库，是 Apriori 算法的两大缺点。数据挖掘十大经典算法(5) EM

在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（ Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。最大期望过程说明我们用表示能够观察到的不完整的变量值，用表示无法观察到的变量值，这样和一起组成了完整的数据。可能是实际测量丢失的数据，也可能是能够简化问题的隐藏变量，如果它的值能够知道的话。例如，在混合模型（Mixture Model）中，如果―产生‖样本的混合元素成分已知的话最大似然公式将变得更加便利（参见下面的例子）。估计无法观测的数据让代表矢量 θ: 定义的参数的全部数据的概率分布（连续情况下）或者概率集聚函数（离散情况下），那么从这个函数就可以得到全部数据的最大似然值，另外，在给定的观察到的数据条件下未知数据的条件分布可以表示为：数据挖掘十大经典算法(6) PageRank PageRank 是 Google 算法的重要内容。2001 年 9 月被授予美国专利，专利人是 Google 创始人之一拉里•佩奇（Larry Page）。因此，PageRank 里的 page 不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。 Google 的 PageRank 根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。 PageRank 背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的―链接流行度‖——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank 这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。 Google 有一套自动化方法来计算这些投票。Google 的 PageRank 分值从 0 到 10；PageRank 为 10 表示最佳，但非常少见，类似里氏震级（Richter scale），PageRank 级别也不是线性的，而是按照一种指数刻度。这是一种奇特的数学术语，意思是 PageRank4 不是比 PageRank3 好一级——而可能会好 6 到 7 倍。因此，一个 PageRank5 的网页和 PageRank8 的网页之间的差距会比你可能认为的要大的多。 PageRank 较高的页面的排名往往要比 PageRank 较低的页面高，而这导致了人们对链接的着魔。在整个 SEO 社区，人们忙于争夺、交换甚至销售链接，它是过去几年来人们关注的焦点，以至于 Google 修改了他的系统，并开始放弃某些类型的链接。比如，被人们广泛接受的一条规定，来自缺乏内容的―link farm‖（链接工厂）网站的链接将不会提供页面的 PageRank，从 PageRank 较高的页面得到链接但是内容不相关（比如说某个流行的漫画书网站链接到一个叉车规范页面），也不会提供页面的 PageRank。Google 选择降低了 PageRank 对更新频率，以便不鼓励人们不断的对其进行监测。 Google PageRank 一般一年更新四次，所以刚上线的新网站不可能获得 PR 值。你的网站很可能在相当长的时间里面看不到 PR 值的变化，特别是一些新的网站。PR 值暂时没有，这不是什么不好的事情，耐心等待就好了。为您的网站获取外部链接是一件好事，但是无视其他 SEO 领域的工作而进行急迫的链接建设

分享到：

赞收藏

资料库

数据挖掘中十大经典算法.pdf

相关推荐

人工智能

热门标签

最新资料