机器学习10大经典算法综述.docx

1、机器学习10大经典算法综述1、C4.5机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当

2、不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树一般都是自上而下的来生成的。选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量：1)通过该节点的记录数2)如果是叶子节点的话，分类的路径3)对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。由于ID3算法在实际应用中存在一些问题

3、，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了，这里就不做介绍。 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练

4、集大得无法在内存容纳时程序无法运行。来自搜索的其他内容：C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. 分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是: 根: 学习的事例集. 枝: 分类的判定条件. 叶: 分好的各个类. 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递归.

5、 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|/|

6、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. 在输入数据上的改进.

7、 1) 因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理,但结论属性的值必须是离散值. 2) 训练例的因素属性值可以是不确定的,以 ? 表示,但结论必须是确定的 3. 对已生成的决策树进行裁剪,减小生成树的规模.2、The k-means algorithm k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k = 0软间隔1995年, Corinna Cortes 与Vapnik 提出了一种改进的最大间隔区方法，这种方法可以处理标记错误的样本。如果可区分正负例的超平面不存在，则“软边界”将选择一个超平面尽可

8、能清晰地区分样本，同时使其与分界最清晰的样本的距离最大化。这一成果使术语“支持向量机”（或“SVM”）得到推广。这种方法引入了松驰参数i以衡量对数据xi的误分类度。随后，将目标函数与一个针对非0i的惩罚函数相加，在增大间距和缩小错误惩罚两大目标之间进行权衡优化。如果惩罚函数是一个线性函数，则等式(3)变形为4、Apriori算法Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。Apriori演算法所使用的前置统计量包括了：最大规则物

9、件数：规则中物件组所包含的最大物件数量最小支援：规则中物件或是物件组必顸符合的最低案例数最小信心水准：计算规则所必须符合的最低信心水准门槛该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法

10、的两大缺点。5、最大期望(EM)算法在统计计算中，最大期望（EM，ExpectationMaximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于

11、另外一个 E 步计算，这个过程不断交替进行。最大期望过程说明我们用 表示能够观察到的不完整的变量值，用 表示无法观察到的变量值，这样 和 一起组成了完整的数据。 可能是实际测量丢失的数据，也可能是能够简化问题的隐藏变量，如果它的值能够知道的话。例如，在混合模型（Mixture Model）中，如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利（参见下面的例子）。估计无法观测的数据让 代表矢量 : 定义的参数的全部数据的概率分布（连续情况下）或者概率集聚函数（离散情况下），那么从这个函数就可以得到全部数据的最大似然值，另外，在给定的观察到的数据条件下未知数据的条件分布可以表示为：6

12、、PageRankPageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。Google的 PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度即被别人引述的次数越多，

13、一般判断这篇论文的权威性就越高。Google有一套自动化方法来计算这些投票。Google的PageRank分值从0到 10；PageRank为10表示最佳，但非常少见，类似里氏震级（Richter scale），PageRank级别也不是线性的，而是按照一种指数刻度。这是一种奇特的数学术语，意思是PageRank4不是比PageRank3好一级而可能会好6到7倍。因此，一个PageRank5的网页和PageRank8的网页之间的差距会比你可能认为的要大的多。PageRank较高的页面的排名往往要比PageRank较低的页面高，而这导致了人们对链接的着魔。在整个SEO社区，人们忙于争夺、交换甚至

14、销售链接，它是过去几年来人们关注的焦点，以至于Google修改了他的系统，并开始放弃某些类型的链接。比如，被人们广泛接受的一条规定，来自缺乏内容的“link farm”（链接工厂）网站的链接将不会提供页面的PageRank，从PageRank较高的页面得到链接但是内容不相关（比如说某个流行的漫画书网站链接到一个叉车规范页面），也不会提供页面的PageRank。Google选择降低了PageRank对更新频率，以便不鼓励人们不断的对其进行监测。Google PageRank一般一年更新四次，所以刚上线的新网站不可能获得PR值。你的网站很可能在相当长的时间里面看不到PR值的变化，特别是一些新的网站

15、。PR值暂时没有，这不是什么不好的事情，耐心等待就好了。为您的网站获取外部链接是一件好事，但是无视其他SEO领域的工作而进行急迫的链接建设就是浪费时间，要时刻保持一个整体思路并记住以下几点：Google的排名算法并不是完全基于外部链接的高PageRank并不能保证Google高排名PageRank值更新的比较慢，今天看到的PageRank值可能是三个月前的值因此我们不鼓励刻意的去追求PageRank，因为决定排名的因素可以有上百种。尽管如此，PageRank还是一个用来了解Google对您的网站页面如何评价的相当好的指示，建议网站设计者要充分认识PageRank在Google判断网站质量中的重

16、要作用，从设计前的考虑到后期网站更新都要给予PageRank足够的分析，很好的利用。我们要将PageRank看作是一种业余爱好而不是一种信仰。-通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。此外，PageRank 还会评估每个投票网页的重要性，因为某些网页的投票被认为具有较高的价值，这样，它所链接的网页就能获得较高的价值

17、。重要网页获得的 PageRank（网页排名）较高，从而显示在搜索结果的顶部。Google 技术使用网上反馈的综合信息来确定某个网页的重要性。搜索结果没有人工干预或操纵，这也是为什么 Google 会成为一个广受用户信赖、不受付费排名影响且公正客观的信息来源。其实简单说就是民主表决。打个比方，假如我们要找李开复博士，有一百个人举手说自己是李开复。那么谁是真的呢？也许有好几个真的，但即使如此谁又是大家真正想找的呢？:-) 如果大家都说在 Google 公司的那个是真的，那么他就是真的。在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是 Page R

18、ank 的核心思想。 当然 Google 的 Page Rank 算法实际上要复杂得多。比如说，对来自不同网页的链接对待不同，本身网页排名高的链接更可靠，于是给这些链接予较大的权重。Page Rank 考虑了这个因素，可是现在问题又来了，计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了先有鸡还是先有蛋的问题了吗？Google 的两个创始人拉里佩奇 （Larry Page ）和谢尔盖布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一

19、次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。值得一提的事，这种算法是完全没有任何人工干预的。理论问题解决了，又遇到实际问题。因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多。我来 Googl

20、e 后，拉里 (Larry) 在和我们几个新员工座谈时，讲起他当年和谢尔盖(Sergey) 是怎么想到网页排名算法的。他说：当时我们觉得整个互联网就像一张大的图（Graph)，每个网站就像一个节点，而每个网页的链接就像一个弧。我想，互联网可以用一个图或者矩阵描述，我也许可以用这个发现做个博士论文。 他和谢尔盖就这样发明了 Page Rank 的算法。网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下，以前的信息检索大多把每一个网页当作独立的个体对待，很多人当初只注意了网页内容和查询语句的相关性，忽略了网页之间的关系。 今天，Google 搜索引擎比最

21、初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界, 这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程 (Information Retrieval) 的教程。 如何提高你网页的 PR 值？什么是PR值呢? PR值全称为PageRank，PR是英文Pagerank 的缩写形式，Pagerank取自Google的创始人LarryPage，它是Google排名运算法则（排名公式）的一部分，Pagerank是 Google对网页重要性的评估，是Google用来衡量一个网站的好坏的唯一标准。PageRank(网页级别)是Google用于评测一个网页“重要性”的一种方法。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。 PR值的级别从1到10级，10级为满分。PR值越高说明该网页越受欢迎。Google把自己的网站的PR值定到10，这说明Google这个网站是非常受欢迎的，也可以说这个网站非常重要。Google大受青睐的另一个原因就是它的网站索引速度。向Google提交你的网站直到为Google收录，一般只需两个星期。如果你的网站已