• / 66
  • 下载费用:25 金币  

计算机软件及应用数据挖掘算法报告五条算法PPT课件

关 键 词:
计算机软件及应用 数据挖掘算法 数据挖掘课件 数据挖掘与应用
资源描述:
数据挖掘经典算法概述 数据挖掘十大算法 N 关联分析 PrefixSpan 2004 韩家炜 聚类 • 为了更加方便直观的理解算法,每一个算 法都不会只是空洞的讲述原理及步骤,都 会有一个实例进行讲解展示,从而可以更 直观的了解算法是如何应用的。 算法一:C4.5 • 挖掘主题:分类挖掘 • C4.5,是机器学习算法中的一个分类决 策树算法,它是决策树(决策树也就是做 决策的节点间的组织方式像一棵树,其实 是一个倒树)核心算法ID3的改进算法,所 以基本上了解了一半决策树构造方法就能 构造它。决策树构造方法其实就是每次选 择一个好的特征以及分裂点作为当前节点 的分类条件。 什么是分类? • 分类是用于识别什么样的事务属于哪一类 的方法 什么是信息熵 • 信息熵:信息的基本作用就是消除人们对 事物的不确定性。所谓信息熵,是一个数 学上颇为抽象的概念,在这里不妨把信息 熵理解成某种特定信息的出现概率。 • 香农指出,它的准确信息量应该是 -(p1*log(2,p1) + p2 * log(2,p2) + .. . +p32 *log(2,p32)), • 熵的概念源自热物理学.假定有两种气体a、b, 当两种气体完全混合时,可以达到热物理学中 的稳定状态,此时熵最高。如果要实现反向过 程,即将a、b完全分离,在封闭的系统中是没 有可能的。只有外部干预(信息),也即系统 外部加入某种有序化的东西(能量),使得a、 b分离。这时,系统进入另一种稳定状态,此时 ,信息熵最低。热物理学证明,在一个封闭的 系统中,熵总是增大,直至最大。若使系统的 熵减少(使系统更加有序化),必须有外部能 量的干预。 • 也就是说,熵是描述系统混乱的量,熵越 大说明系统越混乱,携带的信息就越少, 熵越小说明系统越有序,携带的信息越多 。 C4.5具体算法步骤 1、创建节点N 2、如果训练集为空,在返回节点N标记为Failure 3、如果训练集中的所有记录都属于同一个类别,则以该类别标记节点N 4、如果候选属性为空,则返回N作为叶节点,标记为训练集中最普通的类; 5、for each 候选属性 attribute_list 6、if 候选属性是连续的then 7、对该属性进行离散化 8、选择候选属性attribute_list中具有最高信息增益的属性D 9、标记节点N为属性D 10、for each 属性D的一致值d 11、由节点N长出一个条件为D=d的分支 12、设s是训练集中D=d的训练样本的集合 13、if s为空 14、加上一个树叶,标记为训练集中最普通的类 15、else加上一个有C4.5(R - {D},C,s)返回的点 C4.5定义 C4.5定义 实例 • 假设有一个信息 系统,关于的是 几种天气的不同 变化对是否进行 比赛的影响.根 据这些信息,给 定一个决策表如 右图: NO.OutlookTemperatureWindyHumidityPlay? 1sunnyhotfalsehighNo 2sunnyhottruehighNo 3overcasthotfalsehighYes 4rain Mild(温暖 ) falsehighYes 5raincoolfalsenormalYes 6raincooltruenormalNo 7overcastcooltruenormalYes 8sunnymildfalsehighNo 9sunnycoolfalsenormalYes 10rainmildfalsenormalYes 11sunnymildtruenormalYes 12overcastmildtruehighYes 13overcasthotfalsenormalYes 14rainmildtruehighNo “Outlook”的信息增益最大,可知应该选择“Outlook”作为分裂点. 接下来,继续上述过程.比如选择“Outlook=sunny”这个分支.现在要考虑计算剩 下的三个属性对应的信息增益. NO. Temperat ure Windy Humid ity Play ? 1hotfalsehighNo 2hottruehighNo 8mildfalsehighNo 9coolfalsenormalYes 11mildtruenormalYes 上述只是完成了ID3 • 以上是ID3计算信息增益的方法,C4.5算 法对此进行了改进。C4.5算法采用信息增 益率作为选择分支属性的标准,克服了 ID3算法中信息增益选择属性时偏向选择 取值多的属性的不足。 树的终止 • 树的建立实际上是一个递归过程,那么这 个递归什么时候到达终止条件退出递归呢 ?有两种方式,第一种方式是如果某一节 点的分支所覆盖的样本都属于同一类的时 候,那么递归就可以终止,该分支就会产 生一个叶子节点。还有一种方式就是,如 果某一分支覆盖的样本的个数如果小于一 个阈值,那么也可产生叶子节点,从而终 止建立树。我们只考虑二叉分割的情况, 因为这样生成的树的准确度更高。 树的修剪 •树一旦生成后,便进入第二阶段——修剪阶段。决策树为什么要剪 枝?原因就是避免决策树“过拟合”样本。前面的算法生成的决策树 非常的详细而庞大,每个属性都被详细地加以考虑,决策树的树叶 节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样 本进行分类的话,你会发现对于训练样本而言,这个树表现堪称完 美,它可以100%完美正确得对训练样本集中的样本进行分类(因 为决策树本身就是100%完美拟合训练样本的产物)。但是,这会 带来一个问题,如果训练样本中包含了一些错误,按照前面的算法 ,这些错误也会100%一点不留得被决策树学习了,这就是“过拟合” 。C4.5的缔造者昆兰教授很早就发现了这个问题,他做过一个试验 ,在某一个数据集中,过拟合的决策树的错误率比一个经过简化了 的决策树的错误率要高。 •目前决策树的修剪的策略有三种:基于代价复杂度的修剪(Cost- Complexity Pruning)、悲观修剪(Pessimistic Pruning)和MDL (Minimum Description Length)修剪。对于树的修剪,相对树的 生成要简单一些 ,时间关系, 具体就不讲了,有兴趣下来讨论。 • C4.5算法继承了ID3算法的优点,并在以下几方面对ID3 算法进行了改进: • 1) 用信息增益率来选择属性,克服了用信息增益选择属 性时偏向选择取值多的属性的不足; • 2) 在树构造过程中进行剪枝; • 3) 能够完成对连续属性的离散化处理; • 4) 能够对不完整数据进行处理。 • C4.5算法有如下优点:产生的分类规则易于理解,准确 率较高。其缺点是:在构造树的过程中,需要对数据集 进行多次的顺序扫描和排序,因而导致算法的低效。此 外,C4.5只适合于能够驻留于内存的数据集,当训练集 大得无法在内存容纳时程序无法运行。 C4.5总结 算法二:K-Means • 挖掘主题:聚类 • k-means算法是一个聚类算法,把n个对 象根据他们的属性分为k个分割(k (在这里每 一个e都和在S中给定的连续的元素相一致)和一 个序列β=(m≤n).只有如果:1) ei’=ei(i≤m-1),2)em’∈em ,3)所有在(em —em’)的连续项在em’中都是按照字母表顺序排 列的,那么我们就说β是α的一个前缀。 例如,,,和都是序列 s=的前缀 后缀定义 • 序列关于子序列 = 的投影 为’ = (n = m),则序列关于子 序列的后缀为, 其中em” = (em - em’)。 • 例如,对于序列s=, 就被认识为是关于前缀的 后缀,就被认为是关于前缀 的后缀, 就被被认为是关于前缀的 后缀。 投影数据库定义 • 令α是在序列数据库S中的一个序列模式, 这个α-投影数据库表示为:S|α。 • 简单来说,它是在S中关于前缀α的序列的 后缀的集合 • PrefixSpan算法是一种深度优先搜索算法 ,其基本思想是使用频繁前缀划分搜索空 间和投影序列数据库,并搜索相关的序列 。首先检查前缀子序列,只将其相应的后 缀子序列投影到数据库中。该算法同时采 用分治(divide and conquer)的策略,不断 产生序列数据库的多个更小的投影数据库 ,然后在各个投影数据库上进行序列模式 挖掘。 算法描述 输入:序列数据库S和最小支持阈值min_support 输出:完整的一组序列模式 方法:调用PrefixSpan(,S|α是α的投影数据库,否则他就是 序列数据库S。 算法步骤 • 1)对投影数据库S|α进行一次扫描,找到 一组连续的项b,其中b可以集合成为α的 最后一个元素或者可以被追加到α上, 形成一个序列模式。 • 2)对于每一个连续的项b,把他添加到α 上形成一个序列α’,并且输出α’。 • 3)对于每一个α’,创建一个α’-投影数据 库S|α’,并调用PrefixSpan(α’,l+1,S|α’). 实例 表 中 的 序 列 数 据 库 , 最 小 支 持 数 为 2 ,P r e f i x S p a n 算法过程如下: • 步骤 1 : 对交易数据库扫描一次得到全 部频繁项目,它们同时也是频繁1-序列 。 它们分别是 • :4 • :2 • :3 • :4 • 步骤 2 :基于以上发现的四个频繁项目, 序列模式的完整的集合可被分为四个具有 不同前缀的序列模式的子集 : ( 1 ) 为前 缀的 ; …( 4 ) 以 为 前缀的 。 • 步 骤 3 : 发现序列模式的子集 。通过构 造相应的投影数据库并在其中递归地挖掘 可得到序列模式的子集。直到不能继续为 止。 prefixspan算法特点 • ①无需产生候选频繁序列模式 ,这是与类 A p r i o r i算法的根本区别 ; • ②相对于原始数据库而言 ,投影数据库的 规模不断减小 ; • ③该算法的工作量主要集中在投影数据库 的构造上。 END
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:计算机软件及应用数据挖掘算法报告五条算法PPT课件
链接地址:https://www.maidoc.com/p-15698539.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开