数据挖掘十大算法.docx

数据挖掘十大算法.docx

《数据挖掘十大算法.docx》由会员分享，可在线阅读，更多相关《数据挖掘十大算法.docx（18页珍藏版）》请在冰点文库上搜索。

数据挖掘十大算法

一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.  对已生成的决策树进行裁剪,减小生成树的规模.

二Thek-meansalgorithm

k-meansalgorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k

它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。

它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。

　　假设有k个群组Si,i=1,2,...,k。

μi是群组Si内所有元素xj的重心，或叫中心点。

　　k平均聚类发明于1956年，该算法最常见的形式是采用被称为劳埃德算法（Lloydalgorithm）的迭代式改进探索法。

劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。

然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。

继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。

　　劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。

（上面函数中存在的不同的最优解）

　　虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。

实际上，观察发现迭代次数远远少于点的数量。

然而最近，DavidArthur和SergeiVassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。

　　近似的k平均算法已经被设计用于原始数据子集的计算。

　　从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。

由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。

　　k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。

另外，算法还假设均方误差是计算群组分散度的最佳参数。

三支持向量机

支持向量机，英文为SupportVectorMachine，简称SV机（论文中一般简称SVM）。

它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。

支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化（TikhonovRegularization）方法的一个特例.这种分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区.因此支持向量机也被称为最大边缘区分类器。

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（LatentVariabl）。

最大期望经常用在机器学习和计算机视觉的数据集聚（DataClustering）领域。

最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在E步上找到的最大似然的期望值从而计算参数的最大似然估计。

M步上找到的参数然后用于另外一个E步计算，这个过程不断交替进行。

Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。

其原理也从线性可分说起，然后扩展到线性不可分的情况。

甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机（SupportVectorMachine,简称SVM）。

支持向量机的提出有很深的理论背景。

支持向量机方法是在近年来提出的一种新方法。

　　SVM的主要思想可以概括为两点：

（1）它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；

（2）它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。

　　在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。

介绍

支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。

在分开数据的超平面的两边建有两个互相平行的超平面。

分隔超平面使两个平行超平面的距离最大化。

假定平行超平面间的距离或差距越大，分类器的总误差越小。

一个极好的指南是C.J.CBurges的《模式识别支持向量机指南》。

vanderWalt和Barnard将支持向量机和其他分类器进行了比较。

动机

有很多个分类器（超平面）可以把数据分开，但是只有一个能够达到最大分割。

我们通常希望分类的过程是一个机器学习的过程。

这些数据点并不需要是

中的点，而可以是任意

（统计学符号）中或者

（计算机科学符号）的点。

我们希望能够把这些点通过一个n-1维的超平面分开，通常这个被称为线性分类器。

有很多分类器都符合这个要求，但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。

如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。

问题定义

设样本属于两个类，用该样本训练svm得到的最大间隔超平面。

在超平面上的样本点也称为支持向量.

我们考虑以下形式的样本点

其中ci为1或−1--用以表示数据点属于哪个类.

是一个p−（统计学符号）,或n−（计算机科学符号）维向量，其每个元素都被缩放到[0,1]或[-1,1].缩放的目的是防止方差大的随机变量主导分类过程.我们可以把这些数据称为“训练数据”，希望我们的支持向量机能够通过一个超平面正确的把他们分开。

超平面的数学形式可以写作

根据几何知识，我们知道

向量垂直于分类超平面。

加入位移b的目的是增加间隔.如果没有b的话，那超平面将不得不通过原点，限制了这个方法的灵活性。

由于我们要求最大间隔，因此我们需要知道支持向量以及（与最佳超平面）平行的并且离支持向量最近的超平面。

我们可以看到这些平行超平面可以由方程族：

来表示。

如果这些训练数据是线性可分的，那就可以找到这样两个超平面，在它们之间没有任何样本点并且这两个超平面之间的距离也最大.通过几何不难得到这两个超平面之间的距离是2/|w|，因此我们需要最小化|w|。

同时为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的i满足其中的一个条件

这两个式子可以写作：

原型

现在寻找最佳超平面这个问题就变成了在

（1）这个约束条件下最小化|w|.这是一个二次規劃QP（quadraticprogramming）最优化中的问题。

更清楚的，它可以表示如下：

最小化

满足

。

1/2这个因子是为了数学上表达的方便加上的。

对偶型（DualForm）

把原型的分类规则写作对偶型，可以看到分类器其实是一个关于支持向量（即那些在间隔区边缘的训练样本点）的函数。

支持向量机的对偶型如下：

并满足αi>=0

软间隔

1995年,CorinnaCortes与Vapnik提出了一种改进的最大间隔区方法，这种方法可以处理标记错误的样本。

如果可区分正负例的超平面不存在，则“软边界”将选择一个超平面尽可能清晰地区分样本，同时使其与分界最清晰的样本的距离最大化。

这一成果使术语“支持向量机”（或“SVM”）得到推广。

这种方法引入了松驰参数ξi以衡量对数据xi的误分类度。

。

随后，将目标函数与一个针对非0ξi的惩罚函数相加，在增大间距和缩小错误惩罚两大目标之间进行权衡优化。

如果惩罚函数是一个线性函数，则等式（3）变形为

四APRIORI算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。

其核心是基于两阶段频集思想的递推算法。

该关联规则在分类上属于单维、单层、布尔关联规则。

在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

Apriori演算法所使用的前置统计量包括了：

∙最大规则物件数：

规则中物件组所包含的最大物件数量

∙最小支援：

规则中物件或是物件组必顸符合的最低案例数

∙最小信心水准：

计算规则所必须符合的最低信心水准门槛

　　该算法的基本思想是：

首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。

然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。

然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。

一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。

为了生成所有频集，使用了递推的方法。

　　可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。

五最大期望（EM）算法

在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（LatentVariabl）。

最大期望经常用在机器学习和计算机视觉的数据集聚（DataClustering）领域。

最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在E步上找到的最大似然的期望值从而计算参数的最大似然估计。

M步上找到的参数然后用于另外一个E步计算，这个过程不断交替进行。

最大期望过程说明

我们用

表示能够观察到的不完整的变量值，用

表示无法观察到的变量值，这样

和

一起组成了完整的数据。

可能是实际测量丢失的数据，也可能是能够简化问题的隐藏变量，如果它的值能够知道的话。

例如，在混合模型（MixtureModel）中，如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利（参见下面的例子）。

估计无法观测的数据

让

代表矢量θ:

定义的参数的全部数据的概率分布（连续情况下）或者概率集聚函数（离散情况下），那么从这个函数就可以得到全部数据的最大似然值，另外，在给定的观察到的数据条件下未知数据的条件分布可以表示为：

六PageRank

 PageRank是Google算法的重要内容。

2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（LarryPage）。

因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。

　　Google的PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。

PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。

这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。

PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。

　　Google有一套自动化方法来计算这些投票。

Google的PageRank分值从0到10；PageRank为10表示最佳，但非常少见，类似里氏震级（Richterscale），PageRank级别也不是线性的，而是按照一种指数刻度。

这是一种奇特的数学术语，意思是PageRank4不是比PageRank3好一级——而可能会好6到7倍。

因此，一个PageRank5的网页和PageRank8的网页之间的差距会比你可能认为的要大的多。

　　PageRank较高的页面的排名往往要比PageRank较低的页面高，而这导致了人们对链接的着魔。

在整个SEO社区，人们忙于争夺、交换甚至销售链接，它是过去几年来人们关注的焦点，以至于Google修改了他的系统，并开始放弃某些类型的链接。

比如，被人们广泛接受的一条规定，来自缺乏内容的“linkfarm”（链接工厂）网站的链接将不会提供页面的PageRank，从PageRank较高的页面得到链接但是内容不相关（比如说某个流行的漫画书网站链接到一个叉车规范页面），也不会提供页面的PageRank。

Google选择降低了PageRank对更新频率，以便不鼓励人们不断的对其进行监测。

　　GooglePageRank一般一年更新四次，所以刚上线的新网站不可能获得PR值。

你的网站很可能在相当长的时间里面看不到PR值的变化，特别是一些新的网站。

PR值暂时没有，这不是什么不好的事情，耐心等待就好了。

　　　在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。

这就是PageRank的核心思想。

当然Google的PageRank算法实际上要复杂得多。

比如说，对来自不同网页的链接对待不同，本身网页排名高的链接更可靠，于是给这些链接予较大的权重。

PageRank考虑了这个因素，可是现在问题又来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了先有鸡还是先有蛋的问题了吗？

　　Google的两个创始人拉里·佩奇（LarryPage）和谢尔盖·布林（SergeyBrin）把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。

他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。

他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。

值得一提的事，这种算法是完全没有任何人工干预的。

　　理论问题解决了，又遇到实际问题。

因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。

如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。

这样大的矩阵相乘，计算量是非常大的。

拉里和谢尔盖两人利用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。

今天Google的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多。

　　我来Google后，拉里（Larry）在和我们几个新员工座谈时，讲起他当年和谢尔盖（Sergey）是怎么想到网页排名算法的。

他说：

"当时我们觉得整个互联网就像一张大的图（Graph），每个网站就像一个节点，而每个网页的链接就像一个弧。

我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做个博士论文。

"他和谢尔盖就这样发明了PageRank的算法。

　　网页排名的高明之处在于它把整个互联网当作了一个整体对待。

它无意识中符合了系统论的观点。

相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。

　　1.PageRank

　　基本思想：

如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。

这个重要性得分值为：

PR（T）/C（T）

　　其中PR（T）为T的PageRank值，C（T）为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

　　优点：

是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。

　　不足：

人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低；另外，PageRank有很严重的对新网页的歧视。

　　2.Topic-SensitivePageRank（主题敏感的PageRank）

　　基本思想：

针对PageRank对主题的忽略而提出。

核心思想：

通过离线计算出一个PageRank向量集合，该集合中的每一个向量与某一主题相关，即计算某个页面关于不同主题的得分。

主要分为两个阶段：

主题相关的PageRank向量集合的计算和在线查询时主题的确定。

　　优点：

根据用户的查询请求和相关上下文判断用户查询相关的主题（用户的兴趣）返回查询结果准确性高。

　　不足：

没有利用主题的相关性来提高链接得分的准确性。

七AdaBoost

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。

其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。

将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。

使用adaboost分类器可以排除一些不必要的训练数据特徵，并将关键放在关键的训练数据上面。

　　目前，对adaboost算法的研究以及应用大多集中于分类问题，同时近年也出现了一些在回归问题上的应用。

就其应用adaboost系列主要解决了:

两类问题、多类单标签问题、多类多标签问题、大类单标签问题，回归问题。

它用全部的训练样本进行学习。

　　该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。

整个过程如下所示：

　　1.先通过对N个训练样本的学习得到第一个弱分类器；

　　2.将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器；

　　3.将和都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器；

　　4.