数据挖掘十大经典算法.docx

1、数据挖掘十大经典算法一、 C4.5 C4.5 算法是机器学习算法中的一种分类决策树算法,其核心算法是 ID3 算法. C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。1、机器学习中，决策树是一个预测模型；他代表的是对象属性

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

3、，随机森林分类器将许多决策树结合起来 以提升分类的正确率。 决策树是如何工作的？ 1、决策树一般都是自上而下的来生成的。 2、选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。 3、从根到叶子节点都有一条路径，这条路径就是一条规则 4、决策树可以是二叉的，也可以是多叉的。 对每个节点的衡量： 1) 通过该节点的记录数 2) 如果是叶子节点的话，分类的路径 3) 对叶子节点正确分类的比例。 有些规则的效果可以比其他的一些规则要好。 由于 ID3 算法在实际应用中存在一些问题，于是 Quilan 提出了 C4.5 算法，严格上说 C4.5 只能是 ID3 的一个改进算法。相信

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

5、4.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 递归. 2. ID

6、3 算法 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); I

7、nfox(X)=SUM( (|Ti|/|T|)*Info(X); 为保证生成的决策树最小,ID3 算法在生成子树时,选取使生成的子树的熵(即Gain(S)最小的 的特征来生成子树. 3、 ID3 算法对数据的要求 1）. 所有属性必须为离散量. 2）. 所有的训练例的所有属性必须有一个明确的值. 3）. 相同的因素必须得到相同的结论且训练例必须唯一. C4.5 对 ID3 算法的改进: 1. 熵的改进,加上了子树的信息 . Split_Infox(X)= - SUM( (|T|/|Ti| ) *LOG(|Ti|/|T|) ); Gain ratio(X)= Gain(X)/Split Info

8、x(X); 2. 在输入数据上的改进 . 1) 因素属性的值可以是连续量,C4.5 对其排序并分成不同的集合后按照 ID3 算法当作离散量进 行处理,但结论属性的值必须是离散值. 2) 训练例的因素属性值可以是不确定的,以 ? 表示, 但结论必须是确定的 3. 对已生成的决策树进行裁剪,减小生成树的规模 . 二、数据挖掘十大经典算法(2) k-means 术语“k-means”最早是由 James MacQueen 在 1967 年提出的，这一观点可以追溯到 1957 年 Hugo Steinhaus 所提出的想法。1957 年，斯图亚特劳埃德最先提出这一标准算法，当初是作为一门应用于脉码调制

9、的技术,直到 1982 年，这一算法才在贝尔实验室被正式提出。1965 年， E.W.Forgy 发表了一个本质上是相同的方法，1975 年和 1979 年，Hartigan 和 Wong 分别提出了一个更高效的版本。 算法描述 输入：簇的数目 k；包含 n 个对象的数据集 D。 输出：k 个簇的集合。 方法： 从 D 中任意选择 k 个对象作为初始簇中心； repeat; 根据簇中对象的均值，将每个对象指派到最相似的簇； 更新簇均值，即计算每个簇中对象的均值； 计算准则函数； until 准则函数不再发生变化。 算法的性能分析 1）优点 （1）k- 平均算法是解决聚类问题的一种经典算法，算法

10、简单、快速。 （2）对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是 O（nkt ），其中 n 是所有对象的数目， k 是簇的数目,t 是迭代的次数。通常 kn。这个算法经常以局部最优结束。 （3）算法尝试找出使平方误差函数值最小的 k 个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。 2）缺点 （1）k- 平均方法只有在簇的平均值被定义的情况下才能使用，不适用于某些应用，如涉及有分类属性的数据不适用。 （2）要求用户必须事先给出要生成的簇的数目 k。 （3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。 （4）不适合于发现非凸面形状

11、的簇，或者大小差别很大的簇。 （5）对于“噪声“和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。 算法的改进 针对算法存在的问题，对 K-means 算法提出一些改进： 一是数据预处理， 二是初始聚类中心选择， 三是迭代过程中聚类种子的选择。 1、首先对样本数据进行正规化处理，这样就能防止某些大值属性的数据左右样本间的距离。给定一组含有 n 个数据的数据集，每个数据含有 m 个属性，分别计算每一个属性的均值、标准差对每条数据进行标准化。 3、其次，初始聚类中心的选择对最后的聚类效果有很大的影响，原 K-means算法是随机选取 k 个数据作为聚类中心，而聚类的结果要是同类间尽可能相似

12、，不同类间尽可能相异，所以初始聚类中心的选取要尽可能做到这一点。采用基于距离和的孤立点定义来进行孤立点的预先筛选，并利用两两数据之间的最大距离在剩余数据集合中寻找初始聚类中心。但对于实际数据，孤立点个数往往不可预知。在选择初始聚类中心时，先将孤立点纳入统计范围，在样本中计算对象两两之间的距离，选出距离最大的两个点作为两个不同类的聚类中心，接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心，直到选出 k 个聚类中心。这样做就降低了样本输入顺序对初始聚类中心选择的影响。 聚类中心选好以后，就要进行不断的迭代计算，在 K-means 算法中，是将聚类均值点(类中所有数

13、据的几何中心点)作为新的聚类种子进行新一轮的聚类计算，在这种情况下，新的聚类种子可能偏离真正的数据密集区，从而导致偏差，特别是在有孤立点存在的情况下，有很大的局限性。在选择初始中心点时，由于将孤立点计算在内，所以在迭代过程中要避免孤立点的影响。这里根据聚类种子的计算时，采用簇中那些与第 k-1 轮聚类种子相似度较大的数据，计算他们的均值点作为第 k 轮聚类的种子，相当于将孤立点排除在外，孤立点不参与聚类中心的计算，这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。在计算聚类中心的时候，要运用一定的算法将孤立点排除在计算均值点那些数据之外，这里主要采用类中与聚类种子相似度大于某一阈值的

14、数据组成每个类的一个子集，计算子集中的均值点作为下一轮聚类的聚类种子。为了能让更多的数据参与到聚类中心的计算种去，阈值范围要包含大多数的数据。在第 k-1 轮聚类获得的类，计算该类中所有数据与该类聚类中心的平均距离 S,选择类中与聚类种子相似度大于 2S 的数据组成每个类的一个子集，以此子集的均值点作为第 k 轮聚类的聚类种子。在数据集中无论是否有明显的孤立点存在，两倍的平均距离都能包含大多数的数据。 对孤立点的改进基于距离法 经典 k 均值算法中没有考虑孤立点。所谓孤立点都是基于距离的, 是数据 U 集中到 U 中最近邻居的距离最大的对象, 换言之, 数据集中与其最近邻居的平均距离最大的对象

15、。针对经典 k 均值算法易受孤立点的影响这一问题, 基于距离法移除孤立点, 具体过程如下: 首先扫描一次数据集, 计算每一个数据对象与其临近对象的距离 , 累加求其距离和, 并计算出距离和均值。如果某个数据对象的距离和大于距离和均值 , 则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中, 重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。 对随机选取初始聚类中心的改进 经典 k 均值算法随机选取 k 个点作为初始聚类中心进行操作。由于是随机选取, 则变化较大, 初始点选取不同, 获得聚类的结果也不同。并且聚类分析得到的聚类的准确率也不一样。对 k 均值算法的初始聚类中心选

16、择方法随机法进行改进, 其依据是聚类过程中相同聚类中的对象是相似的 , 相异聚类中的对象是不相似的。因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路, 具体过程如下: 首先整理移除孤立点后的数据集 U,记录数据个数 y,令 m=1。比较数据集中所有数据对象两两之间的距离。找出距离最近的 2 个数据对象形成集合 Am;比较Am 中每一个数据对象与数据对象集合 U 中每一个对象的距离 ,在 U 中找出与Am 中最近的数据对象,优先吸收到 Am 中,直到 Am 中的数据对象个数到达一定数值,然后令 m=m+1。再从 U 中找到对象两两间距离最近的 2 个数据对象构成 Am,重

17、复上面的过程,直到形成 k 个对象集合。这些集合内部的数据是相似的,而集合间是相异的。 可以看出,这种聚类方法同时满足以下 2 个条件:每个组至少包含一个数据对象; 每个数据对象必须属于且仅属于一个组。即数据对象Xi Ai ,且 U=A1 A2 Ak A0 ,且 Ai Aj =。最后对 k 个对象集合分别进行算术平均,形成 k 个初始聚类中心。 近似的 k 平均算法已经被设计用于原始数据子集的计算。 从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行 k 平均算法，选择最优解。 k 平均算法的一个缺点是

18、，分组的数目 k 是一个输入参数，不合适的 k 可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。三、数据挖掘十大经典算法(3) Svm 支持向量机，英文为 Support Vector Machine，简称 SV 机（论文中一般简称SVM）。它是一 种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。 支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化（Tikhonov Regularization）方法的一个特例. 这族分类器的特点是他们能够同时最小化经验误差与最大化 几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中，最大期望（EM）

19、 算法是在概率（probabilistic ）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无 法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚 （Data Clustering）领域。最大期望算法经过两个步骤交替进行计算：第一步是计算期望（E）， 也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最 大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。 M 步上找到的参数然后用于另外一个 E 步计算，这个过程不断交替进行。 Vapnik 等人在多年研究统计学习理论基础上对线性分

20、类器提出了另一种设计最佳准则。其原 理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这 种分类器被称为支持向量机(Support Vector Machine,简称 SVM)。支持向量机的提出有很深的 理论背景。支持向量机方法是在近年来提出的一种新方法。 SVM 的主要思想可以概括为两点： (1) 它是针对线性可分情况进行分析，对于线性不可分 的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使 其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可 能；(2) 它基于结构风险最小化理论之上在特征空间中建构最优

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

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

23、最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大 间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。 四、数据挖掘十大经典算法(4)Apriori Apriori 算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集(简称频集)，也常称为最大项目集。 在 Apriori 算法中，寻找最大项目集(频繁项集)的基本思想是：算法需要对数据集进行多步处理。第一步，简单统计所有含一个元素项目集出现的频数，并找出那些不小于最小

24、支持度的项目集，即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是：第 k 步中，根据第 k-1 步生成的(k-1)维最大项目集产生 k 维侯选项目集，然后对数据库进行搜索，得到侯选项目集的项集支持度，与最小支持度进行比较，从而找到 k 维最大项目集。从算法的运行过程，我们可以看出该 Apriori 算法的优点：简单、易理解、数据要求低，然而我们也可以看到 Apriori 算法的缺点：(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;(2)每次计算项集的支持度时，都对数据库 D 中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这

25、种扫描比较会大大增加计算机系统的 I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法，如 F-P 算法。 五、数据挖掘十大经典算法(5) EM 最大期望算法（Expectation-maximization algorithm，又译期望最大化算法）在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。 在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data C

26、lustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E ），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M ），最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。 M 是一个在已知部分相关变量的情况下，估计未知变量的迭代技术。 EM 的算法流程如下：1. 初始化分布参数2. 重复直到收敛：1. E 步骤：估计未知参数的期望值，给出当前的参数估计。2. M 步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。应用于缺失值最大期望过程说明 我们用 表示能

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

28、排名，又称网页级别、Google 左侧排名或佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以 Google 公司创办人拉里 佩奇（Larry Page）之姓来命名。Google 用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google 的创始人拉里 佩奇和谢尔盖 布林于 1998 年在斯坦福大学发明了这项技术。PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。Google 把从 A页面到 B 页面的链接解释为 A 页面给 B 页面投票，Google 根据投票来源（甚至来源的来源，即链接到 A 页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。