数据挖掘基于约束的挖掘(编辑修改稿)

数据挖掘基于约束的挖掘(编辑修改稿)内容摘要：

挖掘：路线图  布尔 vs. 定量 关联 (基于规则中所处理数据的值类型 )  buys(x, ―SQLServer‖) ^ buys(x, ―DMBook‖) buys(x, ―DBMiner‖) [%, 60%]  age(x, ―30..39‖) ^ ine(x, ―42..48K‖) buys(x, ―PC‖) [1%, 75%]  单维 vs. 多维 关联 (基于规则中涉及的数据维 )(例子同上 )  单层 vs. 多层 分析 (基于规则集所涉及的抽象层 )  那个品种牌子的啤酒与那个牌子的尿布有关系 ?  各种扩展  相关性、因果分析 关联并不一定意味着相关或因果  最大模式和闭合项集 第 6章：从大数据库中挖掘关联规则  关联规则挖掘    联规则    关联规则挖掘 —一个例子 对于 A  C： support = support({A 、 C}) = 50% confidence = support({A 、 C})/support({A}) = % Apriori的基本思想 : 频繁项集的任何子集也一定是频繁的 交易 ID 购买商品2020 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F频繁项集 支持度{ A } 75%{ B } 50%{ C} 50%{ A ,C} 50%最小值尺度 50% 最小可信度 50% 关键步骤：挖掘频繁集  频繁集 :是指满足最小支持度的项目集合  频繁集的子集也一定是频繁的  如 , 如果 {AB} 是频繁集，则 {A} {B} 也一定是频繁集  从 1到 k（ k频繁集）递归查找频繁集  用得到的频繁集生成关联规则 Apriori算法  连接 : 用 Lk1自连接得到候选 k项集 Ck  修剪 : 一个 k项集，如果他的一个 k1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。  伪代码 : Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = { frequent items}。 for (k = 2。 Lk1 !=。 k++) do begin Ck = candidates generated from Lk1。 for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support end return k Lk。 Apriori算法 — 例子 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3扫描 D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 扫描 D C3 L3 item set{2 3 5}扫描 D ite m s e t s u p{ 2 3 5 } 2如何生成候选集  假定 Lk1 中的项按顺序排列  第一步 : 自连接 Lk1 insert into Ck select , , …, k1, from Lk1 p, Lk1 q where =, …, k2=,  第二步 : 修剪 For all itemsets c in Ck do For all (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck  计算支持度为什么会成为一个问题。  候选集的个数非常巨大  一笔交易可能包含多个候选集 生成候选集的例子  L3={abc, abd, acd, ace, bcd}  自连接 : L3*L3  abc 和 abd 得到 abcd  acd 和 ace 得到 acde  修剪 :  ade 不在 L3中，删除 acde  C4={abcd} 提高 Apriori效率的方法 Hash的项集计数 : 若 k项集在 hashtree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。 (157页图 66) : 不包含任何频繁 k项集的交易也不可能包含任何大于 k的频繁集，下一步计算时删除这些记录。 : 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。 两次扫描数据。 (157页图 56) : 使用小的支持度 +完整性验证方法。 在小的抽样集上找到局部频繁项集，然后在全部数据集找频繁项集。 : 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。 Apriori 够快了吗 ? — 性能瓶颈  Apriori算法的核心 :  用频繁的 (k – 1)项集生成 候选 的频繁 k项集  用数据库扫描和模式匹配计算候选集的支持度  Apriori 的瓶颈 : 候选集生成  巨大的候选集 :  104 个频繁 1项集要生成 107 个候选 2项集  要找尺寸为 100的频繁模式，如 {a1, a2, …, a 100}, 你必须先产生 2100  1030 个候选集  多次扫描数据库：  如果最长的模式是 n的话，则需要 (n +1 ) 次数据库扫描 挖掘频繁集 不用生成候选集  频繁模式增长 (FP增长 )用 FrequentPattern tree (FPtree) 结构压缩数据库 ,  高度浓缩，同时对频繁集的挖掘又完备的  避免代价较高的数据库扫描 开发一种高效的基于 FPtree的频繁集挖掘算法  采用分而治之的方法学：分解数据挖掘任务为小任务  避免生成关联规则 : 分别挖掘条件数据库 用 FPtree挖掘频繁集  基本思想 (分而治之 )  用 FPtree地归增长频繁集  方法  对每个项，生成它的 条件模式库 , 然后是它的 条件 FPtree  对每个新生成的条件 FPtree，重复这个步骤  直到结果 FPtree为 空 , 或只含。