当前位置：文档之家 › 一个基于兴趣度的FP-Growth算法改进

一个基于兴趣度的FP-Growth算法改进

  • 格式：pdf
  • 大小：225.96 KB
  • 文档页数：3

０ 引言
率称为关联规则 ｊｌ的支持率， ｒ 记作：ｐｏ （ ￣Ｙ ， ｓ ｐｒ Ｘ ） ｕ ｔ
ｓ ｐｒ Ｘ ） ｓｐ ｒ ＸＵＹ ｕ ｏ （ ￣Ｙ ＝ ｕｐ ｔ ｐ ｔ ｏ （ ） （） １
数据挖掘是从数据库中提取隐含的、 未知的和潜在的有用信息的过
程， 是数据库及相关领域研究中的一个极其重要而又具有广阔应用前景
ｓｐ ｏ （ ｕ ｐ ｒ Ｊ ｔ
…
、
通常用户根据挖掘需要指定的最小置信度记为 Ｃ 。
支持率和置信度是描述关联规则的两个重要概念， 前者用于衡量关
后者用于衡量关联规则的可信程 自 从关联规则问题被提出后， 就不断有人提出关联规则的局限性， 为 联规则在整个数据集中的统计重要性， 只有支持率和置信度均较高的关联规则才可能是用户感 了避免生成“ 错觉” 的关联规则， 人们引入各种新的阈值以加强对关联规 度。一般来说， 兴趣、 有用的关联规则 。 则的评判。其中， 兴趣度阈值的提出是一个比较经典的观点。这些兴趣 度的定义各具特色， 在文献［］ ２ 中作者给出了感兴趣的规则的定义（ Ｒ— ｉｅ ｓｎ）在文献［ ］ ｎ ｒｔｇ ， ｔｅｉ ３ 中他们又对此作了改进， 文献［ ］ ４ 定义了否定关联
在 Ｆ —ｒ 中， Ｐ ｔｅ 有如下几个特点 ： ｅ
１１ 关联规则挖掘 的基本概念 ．
定义１ 关联规则挖掘的数据集记为 Ｄ Ｄ一般为事务数据库）Ｄ＝ （ ， ｌ ， ， ｔ， ｔ｝ｔ＝｛ ， ， ｉ － ｉ｝ ｋ ，， Ｈ 为一条事 ｔ ｆ …， …， ， ｉ …， － ｐ （ ＝１２ …， ） ｌ２ Ｉ ｌ２ ，
规 则 允许 包含 负项 规 则。
关键词 ： 度 ； 兴趣 关联 规 则 ； 支持 度 ； 置信 度 ；Ｐ— ｒｗｈ Ｉ Ｐ—Ｇｏ ｈ Ｆ Ｇｏ ， ｔ ＮＦ ｒｗ ｔ
中图分类号： Ｐ １．３ Ｔ ３ １１ １
文献标识码 ： Ａ
文章编号 ：６ １— ３ ５ ２０ ）２—０５ １７ ５ ６ （０ ８ １ ０ ４—０ ３
关联规则 ｌ的置信度记作： ｎｄｎｅＸ ） ， ｃ ｆ ｅｃ（ ￣Ｙ ， ｏｉ
ｃ ｆ ｅｅ（ ｏｉ ｎｅ ｊｙ ： ｕ ｏ （ Ｕ Ｙ ｘ１０％ ｎｄ ） ＿ ｒ Ｘ ） ０ ｓ ｔ ￣ｐ
．
的新领域， 其中关联规则技术是数据挖掘中的一个重要分支。 目 前典型
关联规则算法有先验算法、 周期关联规则、 日历关联规则、 定量关联规则、 广义关联规则和频 繁模 式增长 （ ｒ ｕｎ Ｐｔｒ Ｇｏｔ， 称 Ｆ Ｆｅ ｅｔ ａｅ ｒ ｈ 简 ｑ ｔｎ ｗ Ｐ— Ｇｗ） ｏ ｈ ｒ ｔ 算法… 等。
规则的兴趣度 。
１ 问题定义
１２ Ｆ — ｒ ｔ算法 ． Ｐ Ｇｏ ｈ ｗ
Ｊ ｗｉ ａ 等人提出了一种基于 Ｆ —ｒ 的关联规则挖掘算法 Ｆ — ｉ ｅ Ｈｒ ａ ｔ Ｐ ｔｅ ｅ Ｐ Ｇ ｗｈ 它采用分而治之的策略， ｏ ， ｒｔ 将提供频繁项目集的数据库压缩成一棵 频繁模式树（ Ｐ ｔｅ ， Ｆ —ｒ ）但是仍然保留项集关联信息 ， ｅ 然后， 将这种压缩后 的数据库分成一组条件数据库并分别挖掘每个数据库。
ｅ Ｃｕｔ 和Ｘ分别为Ｄ中的事务和项目 ， 集 如果Ｘ＿ 则称事务ｔ包含项目集 。 Ｉｍ— ａ ｅ Ｃｔ， ｔ ｎｍ 记录了该节点所代表的项的名字；ｏｎ记录了所在路径代表 ｔｎａ ｉ ） ｒ ｃｏ ｎｄ —ｉ ｎ 定义 ３ 数据集 Ｄ中包含项 目集 的事务 数称为项 目集 的支 持 的交易（ ａｓ ｔｎ 中达到此节点 的交易个数 ；ｏｅ ｌｋ指 向下一个 具 数， 记作６。项目集 的支持率， 记作： ｐｏ （ ） ｓ ｐｒ Ｘ ， ｕ ｔ 有同样的 Ｉｍ— ａ ｅ ｔ ｎｍ 域的节点， ｅ 要是没有这样一个节点， 就为 ｎｌ ｕ。 ｌ （）频繁项头表（ｅｕｎ ｉｍ ｈａｅ ｔ ｌ 的每个表项（ｌｙ 由两 ３ ｆｑｅｔ ｅ ｅｄｒａ ｅ ｒ ቤተ መጻሕፍቲ ባይዱｔ ｂ ） ｅｔ ） ｌ ｒ
（ ）它有一个标记为“ｕ” １ ｎｌ 的根节点 ， ｌ 它的子节点为一个项前缀子树 （ｅ ｒ ｘ ｕｔｅ 的集合， Ｉｍｐ ｆ ｂｅ） ｔ ｅ ｓ ｒ ｉ 还有一个频繁项（ ｒ ｕｎ ｉｍ） Ｆｅ ｅｔｔ 组成的头表 ｑ ｅ
（ ｅｄｒ 。 Ｈ ａｅ ）
（） ２ 每个项前缀子树 的节点有三个域 ：ｅ ｎｍ ， ｕｔ ｏｅ ｌｋ Ｉｍ— ａ ｅｃ ｎ， ｄ —ｉ 。 ｔ ｏ ｎ ｎ
摘要 ： 人们 已经提 出了许多用于高效地发现 大规模数据库 中关联规则的算法， 但它们大多会产生大量 的关联规则， 这些规则 中包含很 多用户不 感兴 趣的垃圾规则 ， 只能发现正项 的关联规则。因此 ， 且 引入兴趣度的概念。 Ｆ 对 Ｐ—Ｇｏ ｔ ｒ ｈ算法进行改造， ｗ 发现一些用户真正 感兴趣 的有 用关联规 则， 些 这
务 ， 中的元素 （： ，， ，） ｔ ， １２… ｐ 称为项 目（ｅ ） Ｉｍ 。 ｔ 定义 ２ 设 ， ｉ， ， ｝ Ｄ中全体项 目组成 的集合 ， 的任何 ＝｛ ｉ …， 是 ，： ， 子集 称 为 Ｄ中的项 目 （ｅ ｓ ） Ｉ ＿ 称集合 为 ｋ 目集。设 ｔ 集 Ｉｍｅ ， ｔ ｔ Ｉ ｋ 项
个域组成 （ｅ ｎｍ ，ｏｅ ｌｋ 。Ｎ ｄ —ｉ 指 向 Ｆ ｔｅ ｉｍ— ａｅｎｄ — ｉ ） ｏｅ ｌｋ ｔ ｎ ｎ Ｐ—ｒ 中具有与 ｅ
５ ４
第１ ２期
Ｎ １ Ｏ．２
宜宾学院学报
Ｊｕｎｌ ｆ ｉｉ Ｕ ｉ ｒｔ ｏ ｒａ ｏ ｂｎ ｎｖ ｓｙ Ｙ ｅ ｉ
Ｄ ｃｍｂｒ２０ ｅｅ ｅ．０８
一
个基于兴趣度 的 Ｆ Ｇｏ ｔ 算法改进 Ｐ— ｒ ｈ ｗ
曾安 平 ， 永乎２， 黄 阳万安 ， 李广 军 唐远 翔 ，
（． １ 宜宾学院 计算机与信息科学系 ， 四川 宜宾 ６４ ０ ；． ４ ０ ０ ２ 宜宾学院 物理与电子工程系 ， 四川 宜宾 ６４０ ） ４ ００

合集下载

机器学习-FPGROWTH算法

机器学习-FPGROWTH算法

47
代码实现-抽取条件模式基
48
代码实现-抽取条件模式基（验证）
49
代码实现-创建条件FP树
50
代码实现-创建条件FP树
51
代码实现-运行
52
示例：从新闻网站点击流中挖掘新闻报道-数据格式
53
示例：从新闻网站点击流中挖掘新闻报道-代码
• 在源数据集合中，包含将近100w条记录，该文件中的每一行代表某个用户浏览过的 新闻报道。一些用户只看过一篇报道，而有些用户看过2498篇报道，用户和报道被 编码成整数。
得到I5频繁项集：{{I2,I5},{I1,I5},{I2,I1,I5}}
32
FP-GROWTH算法原理-实例2-挖掘频繁项集 • 接着考虑I4，得到条件模式基：
<(I2,I1:1)>、<I2:1> • 构造条件FP-Tree
得到I4频繁项集：{{I2,I4}}
33
FP-GROWTH算法原理-实例2-挖掘频繁项集 • 然后考虑I3，得到条件模式基：
值，则该项集是频繁项集。 • 强关联规则:满足给定支持度和置信度阈值的关联规则 • 支持度：support(A->B) = P(AB) • 置信度：confidence(A->B) = P(A|B)
3
回忆Apriori算法
4
回忆Apriori算法
5
Apriori算法的挑战
挑战
多次数据库扫描 巨大数量的候补项集 繁琐的支持度计算
3 面包,牛奶,啤酒
4 薯片,鸡蛋,面包,牛奶,啤酒
5 薯片,鸡蛋,面包
6 鸡蛋,面包,啤酒
7 薯片,面包,牛奶
8 薯片,鸡蛋,面包,牛奶
9 薯片,鸡蛋,牛奶
个性化推荐系统中的一种基于FP—growth的改进算法

个性化推荐系统中的一种基于FP—growth的改进算法


互联 网使得 人们在 任 何 时间 ，任 何 地点 可 以 自由的访 问信 息 资源 ，给 用户 带 来极 大的便 利 ，然 而也 产生 了难 以准 确获 得所 需
要信 息 的 问题 ，即所 谓 的 “ 息爆 炸 ，但 知识 贫乏 ” ｅ 信 。Ｗｂ数据 挖
从而 提 高 了推 荐系 统 的运行 效率 。 根据 最大 频繁 项 目集定 义 ，推导 出任 何一 个频 繁项 目集 都是 某个 最大 频繁 项 目集 的子集 ， 利用 这一性 质 找 出最 大频 繁项 目集 。 算法 步骤 如下 ： 步骤 １ ：生成 卜频 繁项 目集 扫描 事务 数据 库 Ｄ ， 生 卜项 目 合 ， 据 其支 持数递 减列 产 集 根 出 卜项 目集 ， 并删 除其 中小于最 小支 持度 的项 目， 生成 卜频 繁项
＿
ｓ
ａｇ ｒｔ ． ｉ ｌｏｒｔ ｌｏ ｉｈ Ｔｈ ｓ ａｇ ｉ ｍ ｈｍ ａ ｏｄ ｃ ｔｅ ａｇ ｓ ｅ ｕ ｎ ｉ ｍ ｓｔ ａ ｉｉ ｇ ｔ ｅ ｅ ｕ ｄ ｎ ｅ ｅ ｉ ｍｓ ｔ ’ｇ ｎｅａ ｉｎ ａ ｃ ｎ ｐｒ ｕ ｅ ｈ ｌｒｅ ｔ ｆ ｑ ｅ ｔ ｔ ｒ ｅ ｅｓ ｖｏｄ ｎ ｈ ｒ ｄ ｎ ａ ｔ ｆ ｑｕ ｎｔ ｔ ｒ ｅ ｅｓ ｅ ｒ ｔｏ ｎｄ ｒ ｄ ｉ ｇ ｔｅｎ ｅ ｕｃｎ ｈ ｕｍｂｅ ｆｇｅ ｅ ａｉ ｓ ｏ ｉｔｏ ｕ ｅ ，ｆｅ ｔｖ ｌ ｏｕ ｅ ｈ ｏｓｉ ｅｔ ａ ｒ ｄ ｃｎ ｕ ｉａｅｒ ｃ ｍｍ ｅ ｄ ｔｏ ， ｒｏ ｎ ｒ ｔ ａ ｓ ｃａｉ ｎｒ ｌ ｓｅ ｃｉ ｅｙｓ ｌｔ ｄｔ ｅｐ ｓｂｌ ｈ ｔ ｏ ｕ ｉｇ ｄ ｐｌ ｔ ｅ ｏ ｎｇ ｐ ｃ ｎ ａｉ ｎｗｈｅ ｎ ｕｓｎｇｉ ｔｅｒ ｃ ｍｍ ｅ ｄ ｄ ｓ ｓｅ ａ ｐ ｏ ｅｔ ｅｓ ｓｅ ｅ ｃｅ ｃ ． ｉ ｈ ｅ ｏ ｎ ｎ ｅ ｙ ｔｍ ｉ ｃ ｎｉ ｒ ｖ ｈ ｙ ｔ ｍ ｆ ｉｎ ｙ ｔ ｍ ｉ
数据挖掘考试题目——关联分析

数据挖掘考试题目——关联分析

数据挖掘考试题目——关联分析一、10个选择1.以下属于关联分析的是（）A．CPU性能预测B．购物篮分析C．自动判断鸢尾花类别D．股票趋势建模2.维克托▪迈尔-舍恩伯格在《大数据时代：生活、工作与思维的大变革》一书中，持续强调了一个观点：大数据时代的到来，使我们无法人为地去发现数据中的奥妙，与此同时，我们更应该注重数据中的相关关系，而不是因果关系。

其中，数据之间的相关关系可以通过以下哪个算法直接挖掘（）A．K-means B．Bayes NetworkC．C4.5 D．Apriori3.置信度(confidence)是衡量兴趣度度量（）的指标。

A．简洁性B．确定性C．实用性D．新颖性4.Apriori算法的加速过程依赖于以下哪个策略（）A．抽样B．剪枝C．缓冲D．并行5.以下哪个会降低Apriori算法的挖掘效率（）A．支持度阈值增大B．项数减少C．事务数减少D．减小硬盘读写速率6.Apriori算法使用到以下哪些东东（）A．格结构、有向无环图B．二叉树、哈希树C．格结构、哈希树D．多叉树、有向无环图7.非频繁模式（）A．其置信度小于阈值B．令人不感兴趣C．包含负模式和负相关模式D．对异常数据项敏感8.对频繁项集、频繁闭项集、极大频繁项集的关系描述正确的是（）[注：分别以1、2、3代表之]A．3可以还原出无损的1 B．2可以还原出无损的1C．3与2是完全等价的D．2与1是完全等价的9.Hash tree在Apriori算法中所起的作用是（）A．存储数据B．查找C．加速查找D．剪枝10.以下不属于数据挖掘软件的是（）A．SPSS Modeler B．WekaC．Apache Spark D．Knime二、10个填空1.关联分析中表示关联关系的方法主要有：和。

2.关联规则的评价度量主要有：和。

3.关联规则挖掘的算法主要有：和。

4.购物篮分析中，数据是以的形式呈现。

5.一个项集满足最小支持度，我们称之为。

FP—Growth关联规则挖掘的改进算法

FP—Growth关联规则挖掘的改进算法

降低 了时问开销 。实验表 明： 算法能明显地提 高挖掘效率 。 改进
关键 词 ： 关联规 则；Ｐ—Ｇｏｔ 法；Ｐ— ｒ ； Ｆ ｒ ｈ算 ｗ Ｆ Ｔｅ 数据挖掘 ｅ 中图分类号 ： Ｔ ３ １ Ｐ０ １ 关联规则概述 关联 规则 （ ｓｏｉ ｉ ｕ ｓ Ａ ｓｃ ｔ ｎＲ ｌ ）挖掘是数据挖掘研究 领域的一个 重要研究 方 向， 由美 国 ＩＭ 灿叮 Ｉ ｅｅｗ ｅｔ ａｏ ｅ 它 Ｂ 出 ｓａ． Ｃｎｅ Ｒ ｈ ｒ 文献标识码 ： Ａ
掘 出事务 数据库 Ｄ中所有 的强规则 。 关联规则 的挖掘是一个两步的过程 ： （） １ 找出所 有的频繁项集 ： 根据定义 ， 这些项集 出现的频繁性至少等于预定义的最小支 持度 计数 。 （） ２ 由频 繁项集产生强关联规则 ： 根据定义 ， 这些规则必须满足最小支持度和最小置信 度。 在以上两个步骤 中， 第二步较容易 。 挖掘关联规则 的总体 性能由第 一步决定。 项 的集合称为项集 ， 包含 个项 的项集称为 Ｊ一项集 。 ｝
维普资讯
第 ｌ 卷第 １ ７ 期 ２０ 年 １ ０８ 月
平 顶 山 工 学 院 学 报
Ｖ １ １ ． ０ ． ７ Ｎｏ １
Ｊ ｒ ｌ ｆ ｉ８ｉ ８ ￣ ｔｔ０ Ｔ ｅ ｌ ｙ ｏ ｎ Ｉ ｄｌ Ｉ ｕ ａ ｏ Ｐ ｌ Ｉ ｌ ｕｅ ｆ ｅｔ ｏ ｛ ｍｏ ｇ
０４ ０
０５ ０
Ｂ， Ｋ， ， Ｃ， Ｓ Ｎ
Ａ， Ｃ， Ｌ Ｐ， Ｎ Ｆ， Ｅ， ， Ｍ，
０６ ０ Ｏｆ ０ ７
Ａ， Ｃ， Ｍ ， Ｂ， Ｆ， Ｐ ０。 Ｎ
（） １ 频繁 １ 项集排 序 ： 一 首先扫描一遍数据库 ， 得到频繁 １ 项集 和每 个频繁项集 一 的支持度 ， 根据 １ 项集的频繁支持度对频繁 １ 项集进行降序排列 ， 一 一 设最小支持度为 ２结果集用 Ｌ ， 表示 ； 对表 １ 的数据 集有 ： ＝ ［ ５ Ｆ ５Ａ： ， ４Ｌ： ， ： ， ４０： ， ３。 Ｌ Ｃ： ， ： ， ４Ｂ： ， ４Ｍ ４Ｐ： ， ３Ｎ： 】 （） ２ 生成 Ｆ Ｐ—Ｔ ｅ创建树的根节点， ｎｌ 标记 ， ｒ： ｅ 用“ｕ” ｌ 第二次扫描数据库， 对每个事务 中的频繁项按 Ｌ 中的次序排列，