7.3模式增长方法FP-Growth_第1页
7.3模式增长方法FP-Growth_第2页
7.3模式增长方法FP-Growth_第3页
7.3模式增长方法FP-Growth_第4页
7.3模式增长方法FP-Growth_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

7.3模式增长方法

FP-Growth模

式

增

长

方

法从Apriori到FP-Tree产生大量的候选项集需要多遍扫描数据库Apriori不会产生候选项集直接从FP-Tree中提取频繁项集采用分治策略FP-TreeFP-Tree的构建输入：D事务数据库；

最小支持度阈值Minsupport。输出：FP-Tree树。算法过程：扫描事务数据库D一次，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列成L，L是频繁项列表。创建FP-Tree的根结点,标注其为NULL。对D中的每个事务T，进行以下操作：选择T中的频繁项，根据

L中的次序进行降序排列模

式

增

长

方

法例题7-6构建FP-tree示例。对于一个给定的事务数据库，扫描一次数据库，确定每个1-项集的支持度计数，去掉非频繁项集（本例中假设最小支持度阈值为20%，支持度计数为2）。并将频繁1-项集按照支持度计数降序排列。初始，FP-tree仅包含一个根结点，用符号null标记。随后，用如下方法扩充FP-tree。去掉非频繁1-项集TIDItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3按支持度降序排列模

式

增

长

方

法例题7-6第二次扫描数据库，按支持度递减的顺序，为每个事务创建一个分枝。TIDItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3T1={I2,I1,I5}T2={I2,I4}所有事务模

式

增

长

方

法FP-Growth算法举例项条件模式基I5{(I2,I1:1),(I2,I1,I3:1)}I4{(I2,I1:1),(I2:1)}I3{(I2,I1:2),(I2:2),(I1:2)}I1{(I2:4)}筛选合并项条件FP-treeI5<I2:2,I1:2>I4<I2:2>I3<I2:4,I1:2>,<I1:2>I1<I2:4>条件模式基：前缀路径：当前计数裁剪模

式

增

长

方

法FP-Growth算法举例项条件FP-treeI5<I2:2,I1:2>I4<I2:2>I3<I2:4,I1:2>,<I1:2>I1<I2:4>组合生成的频繁模式(I2,I5:2),(I1,I5:2),(I2,I1,I5:2)(I2,I4:2)(I2,I3:4),(I1,I3:4),(I2,I1,I3:2)(I2,I1:4)频繁项集：条件FP-tree的所有非空真子集+当前项模

式

增

长

方

法FP-Growth算法优点没有生成候选项集；对数据库扫描次数少；FP-Tree是一个高度压缩的结构，存储量用于挖掘频繁项集的所有信息；对于某些事务数据集，FP-Growth算法比Apriori算法要快几个数量级。模

式

增

长

方

法FP-Growth算法缺点如果生成的条件FP

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论