数据挖掘领域十大经典算法之—Apriori算法

谁践踏了优雅 2022-05-30 08:41 197阅读 0赞

> **相关文章：**
> 
>  *  **[数据挖掘领域十大经典算法之—C4.5算法（超详细附代码）][C4.5]**
>  *  **[数据挖掘领域十大经典算法之—K-Means算法（超详细附代码）][K-Means]**
>  *  **[数据挖掘领域十大经典算法之—SVM算法（超详细附代码）][SVM]**
>  *  **[数据挖掘领域十大经典算法之—EM算法][EM]**
>  *  **[数据挖掘领域十大经典算法之—PageRank算法][PageRank]**
>  *  **[数据挖掘领域十大经典算法之—AdaBoost算法（超详细附代码）][AdaBoost]**
>  *  **[数据挖掘领域十大经典算法之—K-邻近算法/kNN（超详细附代码）][K-_kNN]**
>  *  **[数据挖掘领域十大经典算法之—朴素贝叶斯算法（超详细附代码）][Link 1]**
>  *  **[数据挖掘领域十大经典算法之—CART算法（超详细附代码）][CART]**

### 简介 ###

先验算法（Apriori Algorithm）是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库（例如,顾客购买的商品清单，或者网页常访清单。）而其他的算法则是设计用来寻找无交易信息（如Winepi算法和Minepi算法）或无时间标记（如DNA测序）的数据之间的联系规则。

在关联式规则中,一般对于给定的项目集合（例如，零售交易集合，每个集合都列出的单个商品的购买信息），算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法，即频繁子集每次只扩展一个对象（该步骤被称为候选集产生），并且候选集由数据进行检验。当不再产生匹配条件的扩展对象时，算法终止。

### 算法流程 ###

算法：Apriori 算法的频繁项集的产生
    输入：数据集D；最小支持度阈值min_sup
    输出：D 中的频繁项集L
    (1) L1 = find_frequent_1-itemset( D );
    (2) for( k=2; Lk−1≠Φ; k++)
    (3) { (4)　　Ck = apriori_gen(Lk−1);　　　　　　// 产生候选项集 (5)　　for all transactions t ∈D (6)　　{ (7)　　　　Ct = subset(Ck, t);　　　　　　// 识别 t 包含的所有候选 (8)　　　　for all candidates c∈Ct (9)　　　　{ (10)　　　　　　c.count++;　　　　　　// 支持度计数增值 (11)　　　 }
    (12)　　}
    (13)　　Lk = { c∈Ck | c.count≥min_sup}　　　　　　// 提取频繁k-项集
    (14) }
    (15) return L=∪kLk
    
    ;
    
    
    procedure apriori_gen(Lk−1 ) (1) for each itemset l1∈Lk−1 (2)　　for each itemset l2∈Lk−1 (3)　　　　if( l1[1]=l2[1] ∧…∧ ( l1[k-2]=l2[k-2] ) ∧ ( l1[k-1]<l2[k-2] ) then (4)　　　　｛ (5)　　　　　　c = join( l1, l2 );　　　　　　// 连接：产生候选
    (6)　　　　　　if has_infrequent_subset( c, Lk−1) then
    (7)　　　　　　　　delete c;　　　　　　// 减枝：移除非频繁的候选
    (8)　　　　　　else
    (9)　　　　　　　　add c to Ck
    (10)　　　　｝
    (11) return Ck
    
    ;
    
    
    procedure has_infrequent_subset( c, Lk−1 ) // 使用先验知识判断候选项集是否频繁 (1) for each ( k-1 )-subset s of c (2)　　if s ∉Lk−1 then (3)　　　　return TRUE;
    (4) return FALSE;

[C4.5]: http://blog.csdn.net/fuqiuai/article/details/79456971
[K-Means]: http://blog.csdn.net/fuqiuai/article/details/79458331
[SVM]: http://blog.csdn.net/fuqiuai/article/details/79483057
[EM]: http://blog.csdn.net/fuqiuai/article/details/79484421
[PageRank]: http://blog.csdn.net/fuqiuai/article/details/79484929
[AdaBoost]: http://blog.csdn.net/fuqiuai/article/details/79482487
[K-_kNN]: http://blog.csdn.net/fuqiuai/article/details/79458648
[Link 1]: http://blog.csdn.net/fuqiuai/article/details/79458943
[CART]: http://blog.csdn.net/fuqiuai/article/details/79469412