数据挖掘中十大经典算法

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领域的工作而进行急迫的链接建设就是浪费时间，要时刻保持一个整体思路并记住以下几点： ?Google的排名算法并不是完全基于外部链接的 ?高PageRank并不能保证Google高排名

?PageRank值更新的比较慢，今天看到的PageRank值可能是三个月前的值

因此我们不鼓励刻意的去追求PageRank，因为决定排名的因素可以有上百种。尽管如此，PageRank还是一个用来了解Google对您的网站页面如何评价的相当好的指示，建议网站设计者要充分认识PageRank在Google判断网站质量中的重要作用，从设计前的考虑到后期网站更新都要给予PageRank足够的分析，很好的利用。我们要将PageRank看作是一种业余爱好而不是一种信仰。

--------------------------------------------------------------------------------------------------------------------- 通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。

此外，PageRank 还会评估每个投票网页的重要性，因为某些网页的投票被认为具有较高的价值，这样，它所链接的网页就能获得较高的价值。重要网页获得的 PageRank（网页排名）较高，从而显示在搜索结果的顶部。Google 技术使用网上反馈的综合信息来确定某个网页的重要性。搜索结果没有人工干预或操纵，这也是为什么 Google 会成为一个广受用户信赖、不受付费排名影响且公正客观的信息来源。 －－－－－－－－－－－－－－－