数据挖掘算法

《数据挖掘算法》由会员分享，可在线阅读，更多相关《数据挖掘算法（5页珍藏版）》请在装配图网上搜索。

1、数据挖掘的10大经典算法国际权威的学术组织theIEEEInternationalConferenceonDataMining(ICDM)2006年12月评选出了数据挖掘领域的十大经典算法：C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,NaiveBayes,andCART.不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。C4.5C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法.C4.5算法继承了ID3算法的优点，并在以下几方面对I

2、D3算法进行了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。Thek-meansalgorithm即K-Means算法k-meansalgorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，kn。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性

3、来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。Supportvectormachines支持向量机，英文为SupportVectorMachine,简称SV机(论文中一般简称SVM。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.CBurges的模式识别支持向量机指南。vanderWalt和Barnard将支持向量机和其

4、他分类器进行了比较。TheApriorialgorithmApriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。最大期望(EM)算法在统计计算中，最大期望(EMExpectation-Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量(LatentVariabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(DataClustering)领域。P

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

6、性就越高。AdaBoostAdaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。kNN:k-nearestneighborclassificationK最近邻(k-NearestNeighbor，KNN分类算法，是一个理论上比较成熟的方法，也是最简单的机器学

7、习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。NaiveBayes在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel)和朴素贝叶斯模型(NaiveBayesianModel，NBC)。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC莫型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC莫型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC莫型假设属性之间相互独立，这个假设在实

8、际应用中往往是不成立的，这给NBC莫型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC莫型的分类效率比不上决策树模型。而在属性相关性较小时，nbC莫型的性能最为良好。CART:分类与回归树CART,ClassificationandRegressionTrees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。数据挖掘十大经典算法(1)C4.5ID3机器学习中，决策树是一个预测莫型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根

9、节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习,通俗说就是决策树。决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加

10、理想的效果。决策树是如何工作的决策树一般都是自上而下的来生成的。选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量：1) 通过该节点的记录数如果是叶子节点的话，分类的路径对叶子节点正确分类的比例。有些规则的效果可以比其他的一些规则要好。由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了，这里就不做介绍。C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行

11、了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。来自搜索的其他内容：C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法.分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树.决策树的各部分是

12、:根:学习的事例集.枝:分类的判定条件.叶:分好的各个类.1) 4.3.2ID3算法概念提取算法CLS初始化参数C=E,E包括所有的例子,为根.IFC中的任一元素e同属于同一个决策类则创建一个叶子节点YES终止.2) ELSE依启发式标准,选择特征Fi=V1,V2,V3,Vn并创建判定节点划分C为互不相交的N个集合C1,C2,C3,.,Cn;对任一个Ci递归.1) ID3算法随机选择C的一个子集W(窗口).2) 调用CLS生成W的分类树DT(强调的启发式标准在后).3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子).4) 组合W与已发现的意外，形成新的W.5) 重复2)到4),直到无例外

13、为止.启发式标准:只跟本身与其子树有关,采取信息理论用熵来量度.熵是选择事件时选择自由度的量度,其计算方法为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)最小的的特征来生成子树.1. 4.3.3:ID3算法对数据的要求所有属性必须为离散量.2. 所有的训练例的所有属性必须有一个明确的值.3. 相同的因素必须得到相同的结论且训练例必须唯一

14、.4.3.4:C4.5对ID3算法的改进:1.熵的改进,加上了子树的信息.Split_Infox(X)=-SUM(|T|/|Ti|)*LOG(|Ti|/|T|);Gainratio(X)=Gain(X)/SplitInfox(X);2.在输入数据上的改进.1)因素属性的值可以是连续量,C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理,但结论属性的值必须是离散值.2)训练例的因素属性值可以是不确定的,以?表示,但结论必须是确定的1. 对已生成的决策树进行裁剪,减小生成树的规模.数据挖掘十大经典算法(2)Thek-meansalgorithmk-meansalgorithm算法是

15、一个聚类算法，把n的对象根据他们的属性分为k个分割，kn。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。假设有k个群组Si,i=1,2,.,k。卩i是群组Si内所有元素xj的重心，或叫中心点。k平均聚类发明于1956年，该算法最常见的形式是采用被称为劳埃德算法(Lloydalgorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心

16、并重新分组，直到收敛，即对象不再改变分组(中心点位置不再改变)。劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。(上面函数中存在的不同的最优解)虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，DavidArthur和SergeiVassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。近似的k平均算法已经被设计用于原始数据子集的计算。从算法的表现上来说，它并不保证一定得到全局最优解，最终

17、解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。数据挖掘十大经典算法(3)Supportvectormachines支持向量机，英文为SupportVectorMachine，简称SV机(论文中一般简称SVM。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化(TikhonovRegularization)方法的一个特例.这

18、族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中，最大期望(EM算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量(LatentVariabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(DataClustering)领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望(E,也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化(M，也就是最大化在E步上找到的最大似然的期望值从而计算参数的最大似然估计。M步上找到的参数然后用

19、于另外一个E步计算，这个过程不断交替进行。Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(SupportVectorMachine,简称SVM)。支持向量机的提出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法。SVM的主要思想可以概括为两点：(1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分

20、析成为可能；(2)它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。介绍支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超

21、平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.CBurges的模式识别支持向量机指南。vanderWalt和Barnard将支持向量机和其他分类器进行了比较。动机有很多个分类器(超平面)可以把数据分开，但是只有一个能够达到最大分割。我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点，而可以是任意(统计学符号)中或者(计算机科学符号)的点。我们希望能够把这些点通过一个n-1维的超平面分开，通常这个被称为线性分类器。有很多分类器都符合这个要求，但是我们

22、还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。问题定义设样本属于两个类，用该样本训练svm得到的最大间隔超平面。在超平面上的样本点也称为支持向量我们考虑以下形式的样本点(mathbfx_1,c_1),(mathbf(x)_2,c_2),ldots,(mathbf(x)_n,c_n)其中c为1或-1-用以表示数据点属于哪个类是一个p-(统计学符号),或n-(计算机科学符号)维向量，其每个元素都被缩放到0,1或-1,1.缩放的目的是防止方差大的随机变量主导分类过程我们可以把这些数据称为训练数据”，希望我们的支持向量机能够通过一个超平面正确的把他们分开。超平面的数学形式可以写作mathbfxcdotmathbfx-b=0.