网站平台建设经费预算,wordpress总是404,网络广告营销的实现方式,建设壁纸网站的目的一、关联规则算法概述
关联规则挖掘是数据挖掘中的一个重要任务#xff0c;用于发现数据集中不同项之间的关联关系。
二、Apriori算法 原理 频繁项集生成#xff1a;Apriori算法基于一个先验原理#xff0c;即如果一个项集是频繁的#xff0c;那么它的所有子集也是频繁的…一、关联规则算法概述
关联规则挖掘是数据挖掘中的一个重要任务用于发现数据集中不同项之间的关联关系。
二、Apriori算法 原理 频繁项集生成Apriori算法基于一个先验原理即如果一个项集是频繁的那么它的所有子集也是频繁的反之如果一个项集是非频繁的那么它的所有超集也是非频繁的。首先扫描数据集统计每个单项1 - 项集的出现次数找出满足最小支持度阈值的频繁1 - 项集。然后通过频繁 k − 1 k - 1 k−1 - 项集来生成候选 k k k - 项集再扫描数据集计算候选 k k k - 项集的支持度筛选出频繁 k k k - 项集。这个过程不断迭代直到不能生成新的频繁项集为止。关联规则生成对于每个频繁项集 L L L生成所有可能的非空子集。对于每个非空子集 A A A计算关联规则 A ⇒ B A\Rightarrow B A⇒B其中 B L − A B L - A BL−A的置信度置信度计算公式为 C o n f i d e n c e ( A ⇒ B ) S u p p o r t ( A ∪ B ) S u p p o r t ( A ) Confidence(A\Rightarrow B)\frac{Support(A\cup B)}{Support(A)} Confidence(A⇒B)Support(A)Support(A∪B) 只保留满足最小置信度阈值的关联规则。 应用场景 超市购物篮分析。例如分析顾客购买商品的行为发现“购买牛奶和面包的顾客也经常购买鸡蛋”这样的关联规则用于商品陈列优化和促销策略制定。 优点 简单易懂是关联规则挖掘的经典算法。原理和实现相对直观容易理解和应用。能够有效地减少候选项集的数量。通过先验原理避免了对大量不可能是频繁项集的候选项集进行计算提高了效率。 缺点 在生成频繁项集时需要多次扫描数据集。当数据集很大时频繁的I/O操作会导致性能下降。可能会生成大量的候选项集尤其是当最小支持度阈值设置较低时计算和存储这些候选项集会消耗大量的资源。
三、FP - Growth算法 原理 构建FP - TreeFP - Growth频繁模式增长算法首先构建一棵FP - Tree频繁模式树。扫描数据集一次统计每个项的出现频率按照频率降序排列所有项。然后再次扫描数据集将每个事务中的项按照排好的顺序插入FP - Tree中。在插入过程中如果树中已经存在当前项的路径则更新路径上节点的计数否则创建新的分支。挖掘频繁项集从FP - Tree的头表存储每个项及其出现次数和指向树中第一个相同项的指针开始通过递归的方式挖掘频繁项集。对于每个项找到它在FP - Tree中的所有路径根据路径构建条件模式基然后从条件模式基构建条件FP - Tree在条件FP - Tree上继续挖掘频繁项集。这个过程类似于FP - Tree的构建和挖掘直到不能挖掘出新的频繁项集为止。 应用场景 同样适用于购物篮分析能够更高效地处理大规模数据集挖掘商品之间的关联关系。例如在大型连锁超市的销售数据挖掘中发现不同商品类别之间的关联。 优点 只需要扫描数据集两次相比Apriori算法大大减少了I/O开销。一次用于构建FP - Tree另一次用于挖掘频繁项集在挖掘过程中通过条件FP - Tree避免了对原始数据集的多次扫描。对于挖掘长频繁模式和密集数据集更有效。它能够利用FP - Tree的结构快速地找到频繁项集不会像Apriori算法那样生成大量的候选项集。 缺点 构建FP - Tree需要占用大量的内存空间尤其是当数据集很大或者数据项很多时内存消耗可能会成为瓶颈。算法实现相对复杂理解和实现FP - Tree的构建和挖掘过程需要一定的技术难度。
四、Eclat算法 原理 Eclat算法基于集合的交集运算来挖掘频繁项集。它使用垂直数据表示即将每个项的事务标识符TID列表存储起来。对于两个项集 A A A和 B B B它们的交集的事务标识符列表就是同时包含 A A A和 B B B的事务集合。频繁项集的支持度计算方式为 S u p p o r t ( A ) ∣ T I D ( A ) ∣ ∣ D ∣ Support(A)\frac{|TID(A)|}{|D|} Support(A)∣D∣∣TID(A)∣ 其中 T I D ( A ) TID(A) TID(A)是项集 A A A的事务标识符列表 ∣ D ∣ |D| ∣D∣是数据集 D D D的事务总数。通过递归地计算项集的交集来生成频繁项集。从单个项开始计算它们之间的交集和支持度找到频繁1 - 项集。然后通过频繁 k − 1 k - 1 k−1 - 项集之间的交集来生成候选 k k k - 项集计算支持度筛选出频繁 k k k - 项集直到不能生成新的频繁项集为止。 应用场景 在市场调查数据挖掘中用于分析消费者对不同产品属性的组合偏好。例如分析消费者对手机品牌、颜色、存储容量等属性组合的偏好找出频繁出现的属性组合关联。 优点 采用垂直数据表示和集合交集运算在某些情况下可以更高效地计算频繁项集。特别是当数据集的事务长度较短或者支持度阈值较高时能够快速地计算出频繁项集。可以方便地并行化计算。由于基于集合的交集运算不同的项集之间的计算相对独立可以利用并行计算资源来加速挖掘过程。 缺点 当数据集的事务长度较长或者支持度阈值较低时计算项集的交集会导致大量的中间结果需要大量的存储空间和计算时间。对于稀疏数据集性能可能会受到影响因为需要处理大量的事务标识符列表和交集运算。
五、举例说明
假设我们有一个小型超市的购物篮数据集如下
购物篮编号购买商品1牛奶、面包、鸡蛋2牛奶、面包3面包、鸡蛋、果汁4牛奶、鸡蛋5牛奶、面包、果汁
Apriori算法示例 频繁项集生成 首先计算1 - 项集的支持度假设最小支持度阈值为 0.4 0.4 0.4。“牛奶”出现了4次支持度为 4 5 0.8 \frac{4}{5}0.8 540.8“面包”出现了4次支持度为 0.8 0.8 0.8“鸡蛋”出现了3次支持度为 0.6 0.6 0.6“果汁”出现了2次支持度为 0.4 0.4 0.4。所以频繁1 - 项集为{牛奶、面包、鸡蛋、果汁}。然后生成候选2 - 项集{牛奶、面包}{牛奶、鸡蛋}{牛奶、果汁}{面包、鸡蛋}{面包、果汁}{鸡蛋、果汁}。计算它们的支持度例如{牛奶、面包}出现了3次支持度为 3 5 0.6 \frac{3}{5}0.6 530.6。经过筛选频繁2 - 项集为{牛奶、面包}{牛奶、鸡蛋}{面包、鸡蛋}{牛奶、果汁}。接着生成候选3 - 项集{牛奶、面包、鸡蛋}{牛奶、面包、果汁}{牛奶、鸡蛋、果汁}{面包、鸡蛋、果汁}。计算支持度后发现只有{牛奶、面包、鸡蛋}的支持度为 2 5 0.4 \frac{2}{5}0.4 520.4满足阈值是频繁3 - 项集。 关联规则生成 对于频繁3 - 项集{牛奶、面包、鸡蛋}生成非空子集{牛奶}{面包}{鸡蛋}{牛奶、面包}{牛奶、鸡蛋}{面包、鸡蛋}。计算关联规则的置信度例如对于规则{牛奶、面包} ⇒ \Rightarrow ⇒{鸡蛋}置信度为 S u p p o r t ( { 牛奶、面包、鸡蛋 } ) S u p p o r t ( { 牛奶、面包 } ) 0.4 0.6 2 3 \frac{Support(\{牛奶、面包、鸡蛋\})}{Support(\{牛奶、面包\})}\frac{0.4}{0.6}\frac{2}{3} Support({牛奶、面包})Support({牛奶、面包、鸡蛋})0.60.432。根据最小置信度阈值假设为 0.6 0.6 0.6保留满足条件的关联规则。 FP - Growth算法示例 构建FP - Tree 首先统计每个项的出现次数按照出现次数降序排列为牛奶4次、面包4次、鸡蛋3次、果汁2次。构建FP - Tree对于购物篮1牛奶、面包、鸡蛋先插入牛奶然后在牛奶节点下插入面包在面包节点下插入鸡蛋。以此类推构建完整的FP - Tree。 挖掘频繁项集 从FP - Tree的头表开始对于“果汁”找到它在树中的路径构建条件模式基然后从条件模式基构建条件FP - Tree挖掘包含“果汁”的频繁项集。同样地对其他项进行挖掘最终得到所有的频繁项集。 Eclat算法示例 垂直数据表示 牛奶的TID列表为{1,2,4,5}面包的TID列表为{1,2,3,5}鸡蛋的TID列表为{1,3,4}果汁的TID列表为{3,5}。 频繁项集生成 计算1 - 项集的支持度方法同Apriori算法。频繁1 - 项集为{牛奶、面包、鸡蛋、果汁}。计算2 - 项集的交集和支持度例如牛奶和面包的交集TID列表为{1,2,5}支持度为 3 5 0.6 \frac{3}{5}0.6 530.6。经过筛选得到频繁2 - 项集然后继续生成3 - 项集并计算支持度以此类推挖掘出所有频繁项集。
