数据挖掘实验（六）Matlab实现Apriori算法【关联规则挖掘】.pdfVIP

数据挖掘实验 （六）Matlab实现Apriori算法 【关联规则挖掘】 本⽂代码均已在 MATLAB 20 19b 测试通过，如有错误，欢迎指正。 ⽂章 ⽬录 （⼀）关联规则挖掘 关联规则挖掘 （Association rule mining）是数据挖掘中最活跃的研究⽅法之⼀，可以⽤来发现不同事物之间的联系，最早是为了发现超 市交易数据库中不同的商品之间的关系。 例如⼀个超市的经理想要更多的了解顾客的购物习惯，⽐如 “哪组商品可能会在⼀次购物中同时被购买？”或者 “某顾客购买了个⼈电脑， 那该顾客三个⽉后购买数码相机的概率有多⼤？”。利⽤关联规则挖掘，他可能会发现在⾯包和⽜奶间存在较强的关联性，顾客在购买⾯包 的同时⼤都会同时购买⽜奶。这样的关联规则对超市进⾏促销销售是很有帮助的，如 ：如果需要对⾯包进⾏促销，可通过将其与⽜奶捆绑销 售的⽅式来进⾏，从⽽提⾼⼆者共同的销量。 ⽀持度(support) ： ⽀持度是模式为真的任务相关的元组 （或事务）所 占的百分⽐。对于形如 “A⇒B”的关联规则，⽀持度定义为 ： 包含A和B 的元组数 ⽀持度(A ⇒ B) = 元组总数 ，其中A、B是项 ⽬的集合。 置信度(certainty) ： 每个发现的模式都有⼀个表⽰其有效性或值得信赖性的度量。对于形如 “A⇒B”的关联规则，其有效性度量为置 信度，定义为 ： 包含A和B 的元组数 置信度(A ⇒ B) = 包含A 的元组数 ，其中A、B是项 ⽬的集合。 强关联规则 （合格的关联规则） ： 同时满⾜⽤户定义的最⼩置信度和最⼩⽀持度阈值的关联规则，称为强关联规则 （strong association rule），并被认为是有趣的。 （⼆）Apriori关联规则挖掘算法的基本思想 Apriori算法的主要思想是找出存在于事务数据集中最⼤的频繁项集，利⽤得到的最⼤频繁项集与预先设定的最⼩置信度阈值⽣成强关联规 则。 （1）Apriori 算法原理 任何⼀个频繁项集的⼦集必定是频繁项集。 任何⼀个⾮频繁项集的超集必定是⾮频繁项集。 （2）Apriori算法实现的两个过程 a）找出所有的频繁项集 （⽀持度必须⼤于等于给定的最⼩⽀持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最⼤的频繁项 集L 。 k 连接步 ： 连接步的⽬的是找到K项集。 对给定的最⼩⽀持度阈值，分别对候选 1项集C ，剔除⼩于该阈值的项集得到频繁 1项集L ； 1 1 下⼀步由L ⾃⾝连接 （L ∗ L ）产⽣候选2项集C ，保留C 中满⾜约束条件的项集得到频繁2项集，记为L ； 1 1 1 2 2 2 再下⼀步由L ⾃⾝连接 （L ∗ L ）产⽣候选3项集C ，保留C 中满⾜约束条件的项集得到频繁3项集，记为L ，等等。 2 2 2 3 3 3 这样循环下去，得到最⼤频繁项集L 。 k 剪枝步 ： 剪枝步紧接着连接步，在产⽣候选k项集C 的过程中起到减⼩搜索空间的⽬的。由于C 是Lk−1与Lk−1连接产⽣的，根据Apriori k k 的性质，频繁项集的所有⾮空⼦集也必须是频繁项集，所以不满⾜该性质的项集将不会存在于C 中，该过程就是剪枝。 k b）由频繁项集产⽣强关联规则 ：在过程a）可知未超过预定的最⼩⽀持度阈值的项集已被剔除，如果剩下这些规则⼜满⾜了预定的最⼩置信 度阈值，那么就挖掘出了强关联规则。 （三）问题描述 下表给出了某超市的交易记录。该记录中共包含7次交易，7次交易共涉及5种不同的商品。如果某次交易过程中购买了某商品，则在该次