模式挖掘频繁(Frequent Pattern Mining)
- 基本概念 a. 频繁模式(frequent pattern)数据集中模式(如项集、子序列或子结构)频繁出现。 例如： i. 商品(如牛奶和面包)同时频繁出现在交易数据集中，是一个频繁的项 ii. 先买一个序列PC、然后是数码相机，然后是内存卡。如果它经常出现在再购物的历史数据中，它被称为频繁的序列模式(FTM)。 iii. 子结构可能涉及不同的结构形式，如子图、子树或子格，可能与项集或子序列相结合。如果经常出现子结构，则称为频繁结构模式(FSM)。 b. 项(item)、项集(itemset)、频繁项集(frequent itemset) 项(item)表示研究对象(如购物篮实例中的商品)。I={I_1,I_2,…,I_m}是项集，称为项集(itemset)。与任务相关的数据D是数据库事务的集合，每个事务T都是非空项集，以满足要求T?I。每件事都有一个标志符，叫做TID。 c. 关联规则，支持(support)、置信度(confidence) 关联规则是形如A?B其中A?I,B?I,A≠?,B≠?，并且A∩B≠?。规则A?B支持事务集Ds，其中s是D中事务包含A∪B（集合A和B)百分比。规则A?B在事务集D中有信心c，其中c是DB事务的百分比包含在A事务的前提下。同时满足最小支持度阈值(min_sup)最小置信度阈值(min_conf)规则称为强规则。 support(A?B)=P(A∪B) confidence(A?B)=P(B│A)=(support(A∪B))/(support(A))=(support_count(A∪B))/(support_count(A)) 如果项集I的支持度s满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集的集合通常记为L_k。 d. 挖掘过程 上式表明A?BA和容易获得信心A∪B推出支持度计数。挖掘相关规则的问题可以归结为频繁挖掘项集。 挖掘一般关联规则可分为两个步骤： (1)找出所有频繁的项集。根据定义，这些项集的支持度至少与预定义的最小支持度阈值相同。 (2)频繁项集产生强相关规则。根据定义，这些规则必须满足最小支持和最小信心。 *一个例子。下图显示了5个交易的数据，每行代表一个事务，每个事务包含几个项目。数据中隐含着内部关联。
事务:由事务号和项集组成。事务是购买行为。 项目：最小处理单元，即购买的物品。 项集：由一个或多个项组成。 支持计数：包括项集的事务数。 关联规则：A和B都是项集，A?B(s,c)。这里假设A={Milk,Diaper},B={Beer}。 支持：项集中事务数的比例 s=(|Milk,Diaper,Beer|)/(|T|)=2/5=0.4 信心:Y项集事务的比例包含X项集的事务中的比例 s=(|Milk,Diaper,Beer|)/(|Milk,Diaper|)=2/3=0.67 相关规则评价： {Milk,Diaper}?{Beer}(0.4,0.67) 支持度不小于指定阈值，信心度不小于指定阈值，是强相关规则。 2. 相关算法 2.1 Apriori算法(经典的频繁项集挖掘算法) a. 算法核心思想 (1)如果一个集合是频繁项集，那么它所有的子集都是频繁项集； (2)如果一个集合不是频繁项集，那么它所有的超集都不是频繁项集。 b. 算法流程 i. 找到频繁的一维项集L1； ii. 从频繁的L_k维项集生成k 1维项集C_(k 1)；(以下详细说明) iii. 找到C_(k 1)中频繁项集L_(k 1)； iv. k=k 一、循环执行i和ii，直到k 1=n，n最大项集；或者产生的项集是空的，即没有更频繁的项集； v. 输出各维度的频繁项集。
*说明如何从L_k生成 C_(k 1)的方法，k>1 i. 假设在L_k中的所有items排名好(比如alphabetical）。 ii. 连接(joining)。将L_k与自身连接(L_k?L_k)从而产生C_(k 1)具体方法如下:设置l_1和l_2是L_k中的项集，l_1 [j]表示l_1的第j项。则称l_1和l_如果〖(l〗_1 [1]=l_2 [1])∧〖(l〗_1 [2]=l_2 [2])∧…∧〖(l〗_1 [k-1]=l_2 [k-1])∧〖(l〗_1 [k]<l_2 [k])。连接的结果是产生一个k 1项集，〖{l〗1 [1],l_1 [2],…,l_1 [k],l_2 [k]}。 iii. 剪枝(pruning)。删除生成的C(k 1)在某个项集中，如果这个项集满意，它有一个k维子项集，这个子项集不在L_k(为了减少时间的复杂性，一些非频繁项集可以通过基本思想的第二点直接删除)。
*一个例子。下表示事务数据库D，每一行都是一件事T，包含TID和项集。目标是找出满足感。min_sup=频繁项集的所有维度。
三维频繁项集最终产生，L_1,L_2,L_3.我们可以根据频繁项集获得相应的相关规则。
2.2 提高Apriori算法效率 基于散列的技术/事务压缩/划分/抽样/动态项集计数等。
2.3 Apriori算法存在的问题 主要还是开销问题。 (1)需要产生大量的候选项集； (2)需要反复扫描整个数据库，通过模式匹配检查一个大的候选集合。 现有的解决方案： FP-growth，将代表频繁项集的数据库压缩到频繁模式树（FP树)。通过将事务映射到。FP树上的一条路径可能部分重叠，因为不同的事务可能有几个相同的项目。路径重叠得越多，使用就越多FP压缩效果越好。
FP增长采用分治策略将子问题分解为较小的子问题，从而发现以特定后缀结束的所有频繁项集。
2.4垂直数据格式挖掘 Apriori和FP-growth算法都是以{TID: itemset}事务集中挖掘频繁模式。这种格式是水平数据格式。也可以通过{item:TID_set}这种数据格式被称为垂直数据格式，挖掘频繁模式。 3. 模型评价方法
- 支持-可信度框架。可能的问题强相关规则可能不能很好地表示A和B关系(即A和B可能是负相关)。
- 相关分析。A?B[support,confidence,correlation]。 a. 提升度(lift)。 lift(A,B)=(P(A∪B))/(P(A)P(B)) 1代表A和B是独立的； 值小于1代表A和B负相关意味着一个可能导致另一个不出现。 值大于1代表A和B正相关性意味着一个出现包含另一个出现。
b. χ^2相关性度量 χ2=∑_(i=1)c?∑_(j=1)r?〖(o_ij-e_ij)〗2/e_ij 以上两个指标不是零不变的(测量值不受零事务的影响，零事务是指不包括任何调查项集的事务)。 c. 全置信度 all_conf(A,B)=(sup(A?B))/(max{sup(A),sup(B)})=min{P(A|B),P(B|A)} d. 最大置信度 max_conf(A,B)=max{P(A|B),P(B|A)} e. Kulc度量 Kulc(A,B)=1/2(P(A│B) P(B|A)) f. 不平衡比(Imbanlance Ratio, IR)，用于评估规则中包含的两个项集A和B不平衡程度。 IR(A,B)=(|sup(A)-sup(B)|)/(sup(A) sup(B)-sup(A?B)) 结论，采用Kulc最好使用测量和不平衡比。 4. 子图挖掘频繁(Frequent Sub-graph Mining - FSM)
Graph mining研究情况：
(1)基本概念 ? Discovery of graph structures that occur a significant number of times across a set of graphs - Support is some integer or frequency 分为单图挖掘&多图挖掘
- Frequent graphs occur more than support number of times.
? Ex.: Common occurrences of hydroxide-ion ? Other instances:
- Finding common biological pathways among species.
- Recurring patterns of humans interaction during an epidemic.
- Highlighting similar data to reveal data set as a whole. (2)主要难点 a. 图重构。 b. 子图重构。 这些问题都是NP-Complete。 (3)一些方法 a. 传统frequent pattern mining方法 可以说是Apriori算法变形。 General Process: candidate generation: which patterns will be considered? For FSM, candidate pruning: if a candidate is not a viable frequent pattern, can we exploit the pattern to prevent unnecessary work *subgraphs and subsets exponentiate as size increases! support counting: how many of a given pattern exist? DFS or BFS Joins smaller frequent sets into larger ones. Checks the frequency of larger sets.
b. gSpan
- complete frequent subgraph mining
- Apriori扩展，使用DFS和candidate pruning来提升性能。 编码方式
c. SUBDUE
- approximate frequent subgraph mining
- 使用图压缩的方法来决定频繁模式。 d. SLEUTH
- complete frequent subgraph mining
- built specifically for trees
（4）算法评价 • Apriori-based Approach (Traditional):
- Strength: Simple to implement
- Weakness: Inefficient • gSpan (and other Pattern Growth algorithms): Strength: More efficient than Apriori Weakness: Still too slow on large data sets • SUBDUE Strength: Runs very quickly Weakness: Uses a heuristic(启发式), so it may miss some frequent subgraphs • SLEUTH:
- Strength: Mines embedded trees, not just induced, much quicker than more general FSM
- Weakness: Only works on trees… not all graphs
Reference [1]. Yan, X. and Han, J.W. 2002. gSpan: Graph-based Substructure pattern mining, In Proceedings of International Conference on Data Mining, 721–724. [2]. Yan, X. and Han, J. 2003. CloseGraph: Mining Closed Frequent Graph Patterns, In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 286–295, Washington D.C., USA. [3]. C Jiang, F Coenen, M Zito - Knowledge Engineering, A Survey of Frequent Subgraph Mining Algorithms, 2013 - livrepository.liverpool.ac.uk, The Knowledge Engineering Review, Vol. 00:0, 1–31