DIC 算法.pptxVIP

Dynamic Itemset Counting Algorithm 216 实验室 Dynamic Itemset Counting Algorithm DIC算法原理 项目集的存储结构 性能分析 DIC 算法原理 将数据划分成N块，每块中包含M个事务 1、将初始空节点状态置为“黑-方”，将所有1-itemset放入树中，将其状态置为“白圆” 2、当树中存在“白”状态的节点时，进行如下循环： 1、读入M个事务（如果到达结尾，则重头开始读），对当前树中状 态为“白”的节点进行计数 2、如果一个“白-圆”节点的计数超过了最小支持度，则将其状 态从“白-圆”置为“白-方”，此时，如果该节点的直接超集 的所有子集的状态都被置为了“方”，则将该节点的直接超集 也加入到树中 3、如果一个“白”节点已经被所有的事务所检验，则将其状态置为 “方”（白-圆-黑-圆，白-方-黑-方），并停止对该节点的计 数 TID A B C T1 1 1 0 T2 1 0 0 T3 0 1 1 T4 0 0 0 Minsup=1, M=2 [1] From http://www2.cs.uregina.ca/~dbd/cs831/notes/itemsets/DIC.html DIC 算法原理 TID A B C T1 1 1 0 T2 1 0 0 T3 0 1 1 T4 0 0 0 { } { } A B C Count: A=0 B=0 C=0 After M trans read { } C Count: A=2 B=1 C=0 AB=0 A B AB After 2M trans read { } Count: A=2 B=2 C=1 AB=0 AC=0 BC=0 A B AB C AC BC DIC 算法原理 TID A B C T1 1 1 0 T2 1 0 0 T3 0 1 1 T4 0 0 0 After 3M trans read { } Count: A=2 B=2 C=1 AB=1 AC=0 BC=0 A B C AC BC AB After 4M trans read { } Count: A=2 B=2 C=1 AB=1 AC=0 BC=1 A B C AC AB BC DIC 算法原理 数据结构 在读入M个事务时，使用Trie树存储候选项目集 Trie树具有如下优点： 1、每个项目集中的项目是排序的 2、每个项目集对应Trie树中的一个节点 3、空集为根结点，所有1项目集与根结点相连，k(k1)项目集所在节点与其k-1前缀构成的项目集所在节点相连，并由最后一个节点标识。 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD Trie Tree 数据结构 { } A|1 B|1 C|1 B|1 C|1 C|1 C|1 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD { } A|2 B|2 C|2 B|2 C|2 C|2 C|2 Trie Tree D|1 D|1 D|1 D|1 D|1 D|1 D|1 数据结构 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD { } A|2 B|2 C|2 B|2 C|2 C|2 C|2 D|1 D|1 D|1 D|1 D|1 D|1 D|1 Trie Tree 数据结构 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD { } A|2 B|3 C|3 B|2 C|2 C|3 C|2 D|1 D|1 D|1 D|1 D|1 D|1 D|1 Trie Tree 数据结构 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD { } A|2 B|3 C|3 B|2 C|2 C|3 C|2 D|1 D|1 D|1 D|1 D|1 D|1 D|1 …… Trie Tree 数据结构 TID LIST T1 ABC T2 ABCD T3 BC T4 AD T5 CD T6 ACD { } A|4 B|3 C|5 B|2 C|3 C|3 C|2 D|4 D|1 D|2 D|1 D|3 D|1 D|3 Trie Tree 数据结构 性能分析 数据块大小的选择将对DIC算法的效率产生极大的影响。数据块越大，则各个数据块中的频繁项目集的集合与整个数据集中的频繁项目集的集合越接近，因此候选项目集的数量也相对较少，但大的数据块使得扫描数据集所需时间总量增加；相反，数据块越小，则扫描各个数据集所需时间较少，但是候选项目集的数量较大。 M数的选择 Apro