数据挖掘十大经典算法.docx
- 文档编号:15442466
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:19
- 大小:82.32KB
数据挖掘十大经典算法.docx
《数据挖掘十大经典算法.docx》由会员分享,可在线阅读,更多相关《数据挖掘十大经典算法.docx(19页珍藏版)》请在冰点文库上搜索。
数据挖掘十大经典算法
数据挖掘十大经典算法
数据挖掘十大经典算法
一、C4.5
C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:
1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
2)在树构造过程中进行剪枝;
3)能够完成对连续属性的离散化处理;
4)能够对不完整数据进行处理。
C4.5算法有如下优点:
产生的分类规则易于理解,准确率较高。
其缺点是:
在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。
1、机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。
树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则
对应从根节点到该叶节点所经历的路径所表示的对象的值。
决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。
2、从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
3、决策树学习也是数据挖掘中一个普通的方法。
在这里,每个决策树都表述了一种树型结构,他由他的分支来对该类型的对象依靠属性进行分类。
每个决策树可以依靠对源数据库的分割
进行数据测试。
这个过程可以递归式的对树进行修剪。
当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。
另外,随机森林分类器将许多决策树结合起来
以提升分类的正确率。
决策树是如何工作的?
1、决策树一般都是自上而下的来生成的。
2、选择分割的方法有好几种,但是目的都是一致的:
对目标类尝试进行最佳的分割。
3、从根到叶子节点都有一条路径,这条路径就是一条―规则
4、决策树可以是二叉的,也可以是多叉的。
1)
因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进 行处理,但结论属性的值必须是离散值.
2) 训练例的因素属性值可以是不确定的,以 ?
表示,但结论必须是确定的
3. 对已生成的决策树进行裁剪,减小生成树的规模.
二、数据挖掘十大经典算法
(2)k-means
术语“k-means”最早是由JamesMacQueen在1967年提出的,这一观点可以追溯到1957年HugoSteinhaus所提出的想法。
1957年,斯图亚特·劳埃德最先提出这一标准算法,当初是作为一门应用于脉码调制的技术,直到1982年,这一算法才在贝尔实验室被正式提出。
1965年,E.W.Forgy发表了一个本质上是相同的方法,1975年和1979年,Hartigan和Wong分别提出了一个更高效的版本。
算法描述
输入:
簇的数目k;包含n个对象的数据集D。
输出:
k个簇的集合。
方法:
从D中任意选择k个对象作为初始簇中心;
repeat;
根据簇中对象的均值,将每个对象指派到最相似的簇;
更新簇均值,即计算每个簇中对象的均值;
计算准则函数;
until准则函数不再发生变化。
算法的性能分析
1)优点
(1)k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。
(2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。
通常k< 这个算法经常以局部最优结束。 (3)算法尝试找出使平方误差函数值最小的k个划分。 当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。 2)缺点 (1)k-平均方法只有在簇的平均值被定义的情况下才能使用,不适用于某些应用,如涉及有分类属性的数据不适用。 (2)要求用户必须事先给出要生成的簇的数目k。 (3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。 (4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。 (5)对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。 算法的改进 针对算法存在的问题,对K-means算法提出一些改进: 一是数据预处理, 二是初始聚类中心选择, 三是迭代过程中聚类种子的选择。 1、首先对样本数据进行正规化处理,这样就能防止某些大值属性的数据左右样本间的距离。 给定一组含有n个数据的数据集,每个数据含有m个属性,分别计算每一个属性的均值、标准差对每条数据进行标准化。 3、其次,初始聚类中心的选择对最后的聚类效果有很大的影响,原K-means算法是随机选取k个数据作为聚类中心,而聚类的结果要是同类间尽可能相似,不同类间尽可能相异,所以初始聚类中心的选取要尽可能做到这一点。 采用基于距离和的孤立点定义来进行孤立点的预先筛选,并利用两两数据之间的最大距离在剩余数据集合中寻找初始聚类中心。 但对于实际数据,孤立点个数往往不可预知。 在选择初始聚类中心时,先将孤立点纳入统计范围,在样本中计算对象两两之间的距离,选出距离最大的两个点作为两个不同类的聚类中心,接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心,直到选出k个聚类中心。 这样做就降低了样本输入顺序对初始聚类中心选择的影响。 聚类中心选好以后,就要进行不断的迭代计算,在K-means算法中,是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮的聚类计算,在这种情况下,新的聚类种子可能偏离真正的数据密集区,从而导致偏差,特别是在有孤立点存在的情况下,有很大的局限性。 在选择初始中心点时,由于将孤立点计算在内,所以在迭代过程中要避免孤立点的影响。 这里根据聚类种子的计算时,采用簇中那些与第k-1轮聚类种子相似度较大的数据,计算他们的均值点作为第k轮聚类的种子,相当于将孤立点排除在外,孤立点不参与聚类中心的计算,这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。 在计算聚类中心的时候,要运用一定的算法将孤立点排除在计算均值点那些数据之外,这里主要采用类中与聚类种子相似度大于某一阈值的数据组成每个类的一个子集,计算子集中的均值点作为下一轮聚类的聚类种子。 为了能让更多的数据参与到聚类中心的计算种去,阈值范围要包含大多数的数据。 在第k-1轮聚类获得的类,计算该类中所有数据与该类聚类中心的平均距离S,选择类中与聚类种子相似度大于2S的数据组成每个类的一个子集,以此子集的均值点作为第k轮聚类的聚类种子。 在数据集中无论是否有明显的孤立点存在,两倍的平均距离都能包含大多数的数据。 对孤立点的改进—基于距离法 经典k均值算法中没有考虑孤立点。 所谓孤立点都是基于距离的,是数据U集中到U中最近邻居的距离最大的对象,换言之,数据集中与其最近邻居的平均距离最大的对象。 针对经典k均值算法易受孤立点的影响这一问题,基于距离法移除孤立点,具体过程如下: 首先扫描一次数据集,计算每一个数据对象与其临近对象的距离,累加求其距离和,并计算出距离和均值。 如果某个数据对象的距离和大于距离和均值,则视该点为孤立点。 把这个对象从数据集中移除到孤立点集合中,重复直到所有孤立点都找到。 最后得到新的数据集就是聚类的初始集合。 对随机选取初始聚类中心的改进 经典k均值算法随机选取k个点作为初始聚类中心进行操作。 由于是随机选取,则变化较大,初始点选取不同,获得聚类的结果也不同。 并且聚类分析得到的聚类的准确率也不一样。 对k均值算法的初始聚类中心选择方法—随机法进行改进,其依据是聚类过程中相同聚类中的对象是相似的,相异聚类中的对象是不相似的。 因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路,具体过程如下: 首先整理移除孤立点后的数据集U,记录数据个数y,令m=1。 比较数据集中所有数据对象两两之间的距离。 找出距离最近的2个数据对象形成集合Am;比较Am中每一个数据对象与数据对象集合U中每一个对象的距离,在U中找出与Am中最近的数据对象,优先吸收到Am中,直到Am中的数据对象个数到达一定数值,然后令m=m+1。 再从U中找到对象两两间距离最近的2个数据对象构成Am,重复上面的过程,直到形成k个对象集合。 这些集合内部的数据是相似的,而集合间是相异的。 可以看出,这种聚类方法同时满足以下2个条件: ①每个组至少包含一个数据对象;②每个数据对象必须属于且仅属于一个组。 即数据对象Xi∈Ai,且U={{A1∪A2∪…∪Ak}∪A0},且Ai∩Aj=Φ。 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。 近似的k平均算法已经被设计用于原始数据子集的计算。 从算法的表现上来说,它并不保证一定得到全局最优解,最终解的质量很大程度上取决于初始化的分组。 由于该算法的速度很快,因此常用的一种方法是多次运行k平均算法,选择最优解。 k平均算法的一个缺点是,分组的数目k是一个输入参数,不合适的k可能返回较差的结果。 另外,算法还假设均方误差是计算群组分散度的最佳参数。 三、数据挖掘十大经典算法(3)Svm 支持向量机,英文为Support Vector Machine,简称SV机(论文中一般简称SVM)。 它是一 种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。 支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化(Tikhonov Regularization)方法的一个特例.这族分类器的特点是他们能够同时最小化经验误差与最大化 几何边缘区.因此支持向量机也被称为最大边缘区分类器。 在统计计算中,最大期望(EM) 算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无 法观测的隐藏变量(Latent Variabl)。 最大期望经常用在机器学习和计算机视觉的数据集聚 (DataClustering)领域。 最大期望算法经过两个步骤交替进行计算: 第一步是计算期望(E), 也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值; 另外一步是最 大化(M),也就是最大化在 E步上找到的最大似然的期望值从而计算参数的最大似然估计。 M步上找到的参数然后用于另外一个 E步计算,这个过程不断交替进行。 Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。 其原 理也从线性可分说起,然后扩展到线性不可分的情况。 甚至扩展到使用非线性函数中去,这 种分类器被称为支持向量机(SupportVectorMachine,简称SVM)。 支持向量机的提出有很深的 理论背景。 支持向量机方法是在近年来提出的一种新方法。 SVM的主要思想可以概括为两点: (1)它是针对线性可分情况进行分析,对于线性不可分 的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使 其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可 能; (2)它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得 到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。 在学习这种方法时,首先要弄清楚这种方法考虑问题的特点,这就要从线性可分的最简单情 况讨论起,在没有弄懂其原理之前,不要急于学习线性不可分等较复杂的情况,支持向量机 在设计时,需要用到条件极值问题的求解,因此需用拉格朗日乘子理论,但对多数人来说, 以前学到的或常用的是约束条件为等式表示的方式,但在此要用到以不等式作为必须满足的 条件,此时只要了解拉格朗日理论的有关结论就行。 介绍 支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。 在分开数据的超平面的两边建有两个互相平行的超平面。 分隔超平面使两个平行超平面的距 离最大化。 假定平行超平面间的距离或差距越大,分类器的总误差越小。 一个极好的指南是 C.J.CBurges的《模式识别支持向量机指南》。 vanderWalt和 Barnard将支持向量机和其他 分类器进行了比较。 动机 有很多个分类器(超平面)可以把数据分开,但是只有一个能够达到最大分割。 我们通常希望分类的过程是一个机器学习的过程。 这些数据点并不需要是中的点,而可以是 任意(统计学符号)中或者 (计算机科学符号)的点。 我们希望能够把这些点通过一个n-1维的 超平面分开,通常这个被称为线性分类器。 有很多分类器都符合这个要求,但是我们还希望 找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大 间隔超平面。 如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。 四、数据挖掘十大经典算法(4)Apriori Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。 它的核心是基于两阶段频集思想的递推算法。 该关联规则在分类上属于单维、单层、布尔关联规则。 在这里,所有支持度大于最小支持度的项集称为频繁项集(简称频集),也常称为最大项目集。 在Apriori算法中,寻找最大项目集(频繁项集)的基本思想是: 算法需要对数据集进行多步处理。 第一步,简单统计所有含一个元素项目集出现的频数,并找出那些不小于最小支持度的项目集,即一维最大项目集。 从第二步开始循环处理直到再没有最大项目集生成。 循环过程是: 第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度进行比较,从而找到k维最大项目集。 从算法的运行过程,我们可以看出该Apriori算法的优点: 简单、易理解、数据要求低,然而我们也可以看到Apriori算法的缺点: (1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素; (2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。 而这种代价是随着数据库的记录的增加呈现出几何级数的增加。 因此人们开始寻求更好性能的算法,如F-P算法。 五、数据挖掘十大经典算法(5)EM 最大期望算法(Expectation-maximizationalgorithm,又译期望最大化算法)在统计中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。 在统计计算中,最大期望(EM)算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量(LatentVariable)。 最大期望经常用在机器学习和计算机视觉的数据聚类(DataClustering)领域。 最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大化在E步上求得的最大似然值来计算参数的值。 M步上找到的参数估计值被用于下一个E步计算中,这个过程不断交替进行。 M是一个在已知部分相关变量的情况下,估计未知变量的迭代技术。 EM的算法流程如下: 1.初始化分布参数 2.重复直到收敛: 1.E步骤: 估计未知参数的期望值,给出当前的参数估计。 2.M步骤: 重新估计分布参数,以使得数据的似然性最大,给出未知变量的期望估计。 应用于缺失值 最大期望过程说明 我们用 表示能够观察到的不完整的变量值,用 表示无法观察到的变量值,这样 和 一起组成了完整的数据。 可能是实际测量丢失的数据,也可能是能够简化问题的隐藏变量,如果它的值能够知道的话。 例如,在混合模型(MixtureModel)中,如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利(参见下面的例子)。 估计无法观测的数据 让 代表矢量: 定义的参数的全部数据的概率分布(连续情况下)或者概率聚类函数(离散情况下),那么从这个函数就可以得到全部数据的最大似然值,另外,在给定的观察到的数据条件下未知数据的条件分布可以表示为: 六、数据挖掘十大经典算法(6)PageRank PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(LarryPage)之姓来命名。 Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。 Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。 PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。 Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。 简单的说,一个高等级的页面可以使其他低等级页面的等级提升。 PageRank让链接来"投票" 一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。 一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。 一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。 2005年初,Google为网页链接推出一项新属性nofollow,使得网站管理员和网志作者可以做出一些Google不计票的链接,也就是说这些链接不算作"投票"。 nofollow的设置可以抵制垃圾评论。 Google工具条上的PageRank指标从0到10。 它似乎是一个对数标度算法,细节未知。 PageRank是Google的商标,其技术亦已经申请专利。 PageRank算法中的点击算法是由JonKleinberg提出的。 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向量集合的计算和在线查询时主题的确定。 优点: 根据用户的查询请求和相关上下文判断用户查询相关的主题(用户的兴趣)返回查询结果准确性高。 不足: 没有利用主题的相关性来提高链接得分的准确性。 3.Hilltop 基本思想: 与PageRank的不同之处: 仅考虑专家页面的链接。 主要包括两个步骤: 专家页面搜索和目标页面排序。 优点: 相关性强,结果准确。 不足: 专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性,而 专家页面的质量和公平性难以保证;忽略了大量非专家页面的影响,不能反应整个Internet的民意;当没有足够的专家页面存在时,返回空,所以Hilltop适合对于查询排序进行求精。 那么影响googlePageRank的因素有哪些呢? 1与pr高的网站做链接: 2内容质量高的网站链接 3加入搜索引擎分类目录 4加入免费开源目录 5你的链接出现在流量大、知名度高、频繁更新的重要网站上 6google对DPF格式的文件比较看重。 7安装Google工具条 8域名和tilte标题出现关键词与meta标签等 9反向连接数量和反向连接的等级 10Google抓取您网站的页面数量 11导出链接数量 七、数据挖掘十大经典算法(7)AdaBoost AdaBoost,是英文"AdaptiveBoosting"(自适应增强)的缩写,是一种机器学习方法,由YoavFreund和RobertSchapire提出。 AdaBoost方法的自适应在于: 前一个分类器分错的样本会被用来训练下一个分类器。 AdaBoost方法对于噪声数据和异常数据很敏感。 但在一些问题中,AdaBoost方法相对于大多数其它学习算法而言,不会很容易出现过拟合现象。 AdaBoost方法中使用的分类器可能很弱(比如出现很大错误率),但只要它的分类效果比随机好一点(比如两类问题分类错误率略小于0.5),就能够改善最终得到的模型。 而错误率高于随机分类器的弱分类器也是有用的,因为在最终得到的多个分类器的线性组合中,可以给它们赋予负系数,同样也能提升分类效果。 如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低; 相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。 通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上。 在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类器Ck。 然后就根据这个分类器,来提高被它分错的的样本的权重,并降低被正确分类的样本权重。 然后,权重更新过的样本集被用于训练下一个分类器Ck[2]。 整个训练过程如此迭代地进行下去。 Adaboost算法的具体步骤如下: 1.给定训练样本集 ,其中 分别对应于正例样本和负例样本; 为训练的最大循环次数; 2.初始化样本权重 ,即为训练样本的初始概率分布; 3.第一次迭代: (1) 训练样本的概率分布 下,训练弱分类器: (2)计算弱分类器的错误率: (3)选取 ,使得 最小 (4)更新样本权重: (5)最终得到的强分类器: Adaboost算法是经过调整的Boosting算法,其能够对弱学习得到的弱分类器的错误进行适应 性调整。 上述算法中迭代了次的主循环,每一次循环根据当前的权重分布对样本x定一个分 布P,然后对这个分布下的样本使用若学习算法得到一个错误率为的弱分类器 ,对于这个算 法定义的弱学习算法,对所有的 ,都有,而这个错误率的上限并不需要事先知道,实际上。 每一次迭代,都要对权重进行更新。 更新的规则是: 减小弱分类器分类效果较好的数据的概 率,增大弱分类器分类效果较差的数据的概率。 最终的分类器是个弱分类器的加权平均。 八、数据挖掘十大经典算法(8)kNN 1、K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。 该方法的思路是: 如果一个样本在特征空间中的k个最相似(即特征空 间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。 2、K
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 挖掘 经典 算法