Lecture 4 Association Rules of Data Reasoning Dr.李晓瑜Xiaoyu Li Email:xiaoyuuestc@uestc.edu.cn http://blog.sciencenet.cn/u/uestc2014xiaoyu 2019-Spring SunData Group http://www.sundatagroup.org School of Information and Software Engineering,UESTC 1966 Copyright2019 by Xiaoyu Li
Dr.李晓瑜 Xiaoyu Li Email：xiaoyuuestc@uestc.edu.cn http://blog.sciencenet.cn/u/uestc2014xiaoyu 2019-Spring Lecture 4 Association Rules of Data Reasoning SunData Group http://www.sundatagroup.org/ School of Information and Software Engineering, UESTC Copyright © 2019 by Xiaoyu Li. 1
FP-growth Algorithm 2 DATA Copyright 2019 by Xiaoyu Li
Copyright © 2019 by Xiaoyu Li. 2 FP-growth Algorithm
FP-growth Algorithm Use a compressed representation of the database using an FP-tree Once an FP-tree has been constructed,it uses a recursive divide-and-conquer approach to mine the frequent itemsets DATA 3 Copyright 2019 by Xiaoyu Li
3 Copyright © 2019 by Xiaoyu Li. FP-growth Algorithm
FP-tree Construction null After reading TID=1: A:1 TID Items 1 (A,B) 2 (B,C,D) B:1○ 3 (A,C,D,E) 4 (A,D,E) After reading TID=2: 5 (A,B,C} null 6 (A,B,C,D) A:I B:l 7 {B,C} 8 (A,B,C) 9 (A,B,D) B:1 C:1 10 B.C,E) D:1 4 Copyright 2019 by Xiaoyu Li
4 Copyright © 2019 by Xiaoyu Li. FP-tree Construction
FP-tree Construction TID Items Transaction 1 (A,B) Database 2 (B.C,D) null 3 (A,C,D,E) 4 (A,D,E) 5 (A,B,C) 6 A:7 B:3 (A,B,C,D) 7 (B,C) 8 (A,B,C) 9 (A,B,D) B:5 C:I D:1 C:3 10 (B.C,E) Header table D:1 :3 E:1 Item Pointer D: A 海年际带新际带标海司 B 带新带带带带带带带带 E:1 C D: 带带标带参带新 D Pointers are used to assist E frequent itemset generation ATA 5 Copyright 2019 by Xiaoyu Li
5 Copyright © 2019 by Xiaoyu Li. FP-tree Construction