知识发现与关联规则挖掘二(编辑修改稿)

知识发现与关联规则挖掘二(编辑修改稿)内容摘要：

)}；相应关闭项目集为 Cl (A)={ABC,3}， Cl (B)={B,5}， Cl (C)={BC,4}， Cl (D)={BD,3}，Cl(E)={BE,3} ；  L2={(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)}；相应关闭集为 C2 (AB)={ABC,3}；  L3， L4， L5不用测，于是频繁大项集为 {ABC }。 样本数据库 TID Itemset 1 A， B， C， D 2 B， C， E 3 A， B， C， E 4 B， D， E 5 A， B， C， D 2020年 10月 5日星期一 29 FPtree算法的基本原理  进行 2次数据库扫描：一次对所有 1项目的频度排序；一次将数据库信息转变成紧缩内存结构。  不使用侯选集，直接压缩数据库成一个频繁模式树，通过频繁模式树可以直接得到频集。  基本步骤是：  两次扫描数据库，生成频繁模式树 FPTree：  扫描数据库一次，得到所有 1项目的频度排序表 T；  依照 T，再扫描数据库，得到 FPTree。  使用 FPTree，生成频集：  为 FPtree中的每个节点生成条件模式库；  用条件模式库构造对应的条件 FPtree；  递归挖掘条件 FPtrees同时增长其包含的频繁集：  如果条件 FPtree只包含一个路径，则直接生成所包含的频繁集。 2020年 10月 5日星期一 30 生成频繁模式树 FPTree {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 min_support = TID Original Items (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 2020年 10月 5日星期一 31 挖掘频集步骤 1：生成条件模式库  为每个节点， 寻找它的所有前缀路径并记录其频度，形成 CPB条件模式库 CPB item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020年 10月 5日星期一 32 挖掘频集步骤 2：构造 CFPtree  为每一个节点，通过 FPtree构造一个 CFPtree  例如， m节点的 CFPtree为： mCPB: fca:2, fcab:1 {} f:3 c:3 a:3 mconditional FPtree  {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020年 10月 5日星期一 33 挖掘频集步骤 3：递归构造 CFPtree {} f:3 c:3 a:3 mconditional FPtree {} f:3 c:3 amconditional FPtree {} f:3 cmconditional FPtree f:3 {} camconditional FPtree 所有频集： m, fm, cm, am, fcm, fam, cam, fcam 单路径可以形成频集 2020年 10月 5日星期一 34  定理：令 α 是 DB的一个频繁集， B为 α 的条件模式库， β 是 B中一个项，要使 α∪ β 是 DB中的频繁集，当且仅当 β 是 B的频繁集  例子： abcde是频繁集，且 f在包含 abcde的事物中是频繁的，则 abcdef是频繁集，依据上述定理，我们可以实现频繁集的增长。 2020年 10月 5日星期一 35 第 3章 知识发现与关联规则挖掘（ 二 ） 内容提要  基本概念与解决方法  经典的频繁项目集生成算法分析  Apriori算法的性能瓶颈问题  Apriori的改进算法  对项目集格空间理论的发展  基于项目序列集操作的关联规则挖掘算法（可选）  改善关联规则挖掘质量问题  约束数据挖掘问题  关联规则挖掘中的一些更深入的问题  数量关联规则挖掘方法 2020年 10月 5日星期一 36 项目序列集概念  “ 项目序列（ Itemsequence） ” 来替代大多数文献中出现的 “ 项目集（ Itemset） ” 可以简化挖掘的过程。  所谓 项目序列 是指项目集中的元素按着某种标准进行有序排列。 例如，我们可以按项目名称的字典顺序排列，也可以象 FPTree算法那样，按它们在数据库中出现次数的多少降序排列。  为了重复利用对数据库的扫描信息，把来自数据库的信息组织成项目序列集（ Set of itemsequences）形式，并且对项目序列集格及其操作代数化。 在这样的代数系统下研究适应关联规则挖掘问题的操作算子 . 2020年 10月 5日星期一 37 项目序列集格  定义 35 一个项目序列集格空间可以用三元组（ I，S， p）来刻画，其中含义如下：  项目定义域 I： I={ i1， i2， „ ， im }为所有项目集；  项目序列集变量集 S： S中的每个项目序列集变量形式为ISS={IS1， IS2， „ ， ISn}，其中 ISi（ i=1， 2， „ ， n）是定义在 I上项目序列；  操作 p ：关于 S中的项目序列集变量的操作集。  定义 36（项目序列集间（上）的属于（ ）、包含（ ）、并（ ∪ ）、交（ ∩ ）、差（－）等操作和普通的集合操作相同。  例子： 设 ISS1={AB， CD}和 ISS2={ABCD， AD}是定义在 I ={A， B， C， D}上的项目序列集，则 ABISS1； ABISS2；{AB}ISS1； {AB}ISS2； ISS1∪ISS 2={AB， CD， ABCD，AD}； ISS1∩ISS 2= 216。 2020年 10月 5日星期一 38 项目序列集格上的亚操作  定义 37 设 ISS1和 ISS2是定义在 I上的两个项目序列集， IS是定义在 I上的一个项目序列，定义如下操作：  亚属于（ sub）： ISsub ISS1当且仅当  IS1ISS1使得 ISIS1；  亚包含（ sub）： ISS1subISS2当且仅当  IS1ISS1 IS1subISS2；  亚交（ ∩ sub）： ISS1∩ subISS2={IS | ISsubISS1且ISsubISS2}；  亚并（ ∪ sub）： ISS1∪ subISS2={IS | ISsubISS1或ISsubISS2}。  例如，对上面的例子，虽然 {AB} ISS2中，但是 AB sub ISS2。 2020年 10月 5日星期一 39 基于项目序列集操作的关联规则挖掘算法 算法 314 ISSDM Algorithm 输入：数据库 D 输出：最大频繁项目序列集 ISS* （ 1） Input（ minsup_count）； （ 2） ISS  216。 ISS*  216。 ； （ 3） FOR all ISD DO BEGIN //取 D的一个项目序列 IS （ 4） join（ IS， ISS）； （ 5） make_fre（ IS， ISS， ISS*）； （ 6） END （ 7） AnswerISS*  join（ IS， ISS）完成数据库中一个项目序列（元组）加入项目序列集后，它及它的子项目序列的频度维护。  make_fre（ IS， ISS， ISS*）从 ISS挑选频繁的并加入到 ISS*。 2020年 10月 5日星期一 40 ISSDM例子 操作 IS ISS 频繁 ISS* 说明 初始 216。 216。 1 ABCD {（ ABCD， 1） } 216。 2 BCE {（ ABCD， 1），（ BCE， 1） } {BC} 3 ABCE {（ ABCD， 1） ， （ BCE， 1） ， （ ABCE， 1） } {ABC， BCE} 裁 *BC。 BCE 4 BDE {（ ABCD， 1），（ ABCE， 1），（ BDE， 1） } {ABC， BCE， BD} 5 ABCD {（ ABCD， 2） ， （ ABCE， 1） ， （ BDE， 1） } { ABCD， BCE } 裁 *ABC。 BD。 ABCD Answ {（ ABCE， 1），（ BDE， 1） } { ABCD， BCE } 2020年 10月 5日星期一 41 第 3章 知识发现与关联规则挖掘（ 二 ） 内容提要  基本概念与解决方法  经典的频繁项目集生成算法分析  Apriori算法的性能瓶颈问题  Apriori的改进算法  对项目集格空间理论的发展  基于项目序列集操作的关联规则挖掘算法  改善关联规则挖掘质量问题  约束数据挖掘问题  关联规则挖掘中的一些更深入的问题  数量关联规则挖掘方法 2020年 10月 5日星期一 42 衡量关联规则挖掘结果的有效性  应该从多种综合角度来考虑：  准确性：挖掘出的规则必须反映数据的实际情况。  实用性：挖掘出的规则必须是简洁可用的。  新颖性：挖掘出的关联规则可以为用户提供新的有价值信息。  改善关联规则挖掘 质量 是一件很困难的工作。 必须采用 事先预防、过程控制 以及 事后评估 等多种方法，其中使用合适的机制（如约束），让用户主动参与挖掘工作是解决问题的关键。 粗略地说，可以在 用户主观和系统客观 两个层面上考虑关联。