博文
算法学习（八）：关联分析
||
一：关联分析的基本概念
1：购物篮事务
如图。表中每一行对应一个事务，包含一个唯一标示TID和给定顾客购买的商品集合。
2：关联分析
（1）：关联分析：用于发现隐藏在大型数据集中的有意义的联系。所发现的联系一般用关联规则或频繁项集的形式表示。
如下：
{尿布}->{啤酒}：表明两者的销售之间存在很强的联系。
（2）：二元表示
如图。每行对应一个事务，每一列对应一个项。项用二元变量表示，若项在事务出现则值为1，否则为0
（3）：项集
令$I = {i_1,i_2,...,i_d}$是购物篮数据中所有项的集合,$T={t_1,t_2,...,t_N}$是所有事务的集合。包含0个多多个项的集合被称为项集。如果一个项集包含k个项，则称为k-项集。
例如：{啤酒，尿布，牛奶}称为3-项集。
（4）：支持度计数
1：如果项集X是事务$t_j$的子集，则称事务$t_j$包含项集X；
2：支持度计数：包含特定项集的事务个数，即：
$\sigma(X) = \left|{t_i|X\subseteq t_i,t_i \in T}\right|$
例如：在上图中项集{啤酒，尿布，牛奶}的支持度计数为2，有两个事务同时包含这3个项。
（5）：关联规则：形如X->Y的蕴含表达式。X与Y不相交。
1：支持度
$s(X -> Y) = \frac{\sigma (X \cup Y)}{N}$：规定数据集的频繁程度
2：置信度
$c(X -> Y) = \frac{\sigma (X \cup Y)}{\sigma (X)}$:确定Y在包含X的事务中出现的频繁程度
（6）：关联规则的发现
给定事务的集合T，找出支持度大于等于某个支持度并且置信度大于等于某个置信度的所有规则。分为两个子问题
1：频繁项集产生：发现满足最小支持度阈值的所有项集
2：规则的产生：从上步发现的频繁项集中提取所有高置信度的规则
二：相关算法
1：频繁项集的产生
Apriori算法
（1）：先验原理：如果一个项集是频繁的，则它的所有子集一定也是频繁的。
（2）：Apriori算法大致过程
令$C_k$为候选k-项集的集合，$F_k$为频繁k-项集的集合
1：初始单遍扫描数据集，确定每个项的支持度，得到所有频繁1-项集的集合$F_1$
2：使用上一次迭代得到的频繁(k-1)-项集，产生新的候选k-项集
3：重新扫描数据集得到候选项的支持度计数。删除支持度小于阈值的所有候选项集
4：跳转到2
5：没有新的项集产生，算法结束
2：规则的产生
将频繁项集Y划分为两个非空的子集X和Y-X，使得X->Y-X满足置信度的阈值
Apriori算法：
初始，提取规则后件只含有一个项的所有高置信度规则，然后，使用这些规则来产生新的候选规则。
例如：如果{acd}->{b}和{abd}->{c}是两个高置信度的规则，则通过合并这两个规则的后件产生候选规则{ad}->{bc}
https://blog.sciencenet.cn/blog-796597-653103.html
上一篇：算法学习（七）：高斯混合模型GMM
下一篇：算法学习（九）：聚类
扫一扫，分享此博文