[工学]2 frequent pattern -c.ppt

关联规则 Write-based、DFS算法 VIPER Implement DFS with bitmap compression of data in vertical format FP-Growth算法 Implement DFS using a tree structure in horizontal format FP-Growth based sub-graph mining Comparison of Data Layouts Vertical format for write-based FPM Vertical format Vertical format for write-based FPM 关联规则 Write-based、DFS算法 VIPER Implement DFS with bitmap compression of data in vertical format FP-Growth算法 Implement DFS using a tree structure in horizontal format FP-Growth based sub-graph mining FP-Growth算法 第一次扫描数据库： 类似于Apriori算法，找出频繁的1-itemset和他们的计 数值， 将频繁项目按频度降序排列 2. 第二次扫描数据库： 构造fp-tree （频度从大到小） 挖掘该树（频度从小到大） ? 注意：数据库大时，fp-tree可能在内存中装不下，需要 采取partition方法。 Construct FP-tree from a Transaction Database Find Patterns Having P From P-conditional Database Starting at the frequent item header table in the FP-tree Traverse the FP-tree by following the link of each frequent item p Accumulate all of transformed prefix paths of item p to form p’s conditional pattern base From Conditional Pattern-bases to Conditional FP-trees For each pattern-base Accumulate the count for each item in the base Construct the FP-tree for the frequent items of the pattern base Benefits of the FP-tree Structure Completeness Preserve complete information for frequent pattern mining Never break a long pattern of any transaction Compactness Reduce irrelevant info—infrequent items are gone Items in frequency descending order: the more frequently occurring, the more likely to be shared Never be larger than the original database (not count node-links and the count field) For Connect-4 DB, compression ratio could be over 100 Partition Patterns and Databases Frequent patterns can be partitioned into subsets according to f-list F-list=f-c-a-b-m-p Patterns containing p Patterns having m but no p … Patterns having c but no a nor b, m, p Pattern f Completeness and non-redundency FP-Growth vs. Apriori: Scalability With the Support Threshold VIPER vs. FP-Growth: Comparision VIPER vs. F