数据挖掘--挖掘频繁模式、关联和相关(1)

60 阅读 0 评论 40 点赞

我是靠谱客的博主怡然西装，最近开发中收集的这篇文章主要介绍数据挖掘--挖掘频繁模式、关联和相关(1)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

学习是一件很苦的事情，但是有时却是一件很神奇的事情，神奇到原本很抽象枯燥的知识点你却可以取其精华的理解，这时效率最高

此时务必将心得写下

以下读书笔记来自我在阅读《数据挖掘－概念与技术》的一点感受

所谓挖掘频繁模式，关联和相关，即指在出现的数据集中找到一个经常出现的序列模式或者是一个经常出现的数据结构。就像搞CPU设计的人知道，Cache的预取机制有流预取和指针预取，前者就是发现流模式，即发现在地址上顺序出现的序列模式，后者即发现指针链接模式，即链式数据结构。

比如一个人逛超市，她的购物篮里可能装有各种商品的组合。我们设想所有的商品构成全集，每种商品用0-1表示是否出现，那么每个购物篮就可以用一个布尔向量表示，如(0,1,...,1,0)可能表示:(没有买酸奶，买了冰激凌...买了批萨，没有买牛排)，分析大量顾客的购物篮就可以得到一个用购物模式，这个模式我们用关联规则表示，如 :

冰激凌=>批萨 [支持度 = 2%, 置信度 = 60%]

这个就表示所有顾客中有2%的人同时购买了冰激凌和批萨，而买了冰激凌的人中有60%的购买了批萨。一般来说，如果某个模式的支持度和置信度都大于各自的一个阈值，那么这个模式就是一个我们感兴趣的模式(这个就称为强关联规则)。

结合数学语言来说，就是I ＝ {I1,I2,...Im}是所有物品的集合，而事务集D表示所有购物篮里可能的物品组合，事务T是D中的一种可能，也是I中许多物品的一个组合，这个事务用TID标识。假设A,B都是一个元素集合，并且事务T包含A,B。定义关联规则是形如A=>B的蕴含式。

若D中出现AUB的百分比为s，则称A=>B在事务集D中成立的支持度为s。所以support(A=>B) = P(AUB) // 注意，这里的U表示事务集包含A和B的并集，而不是A or B的意思

若出现A的情况下出现B的百分比为c，则称A=>B在事务集D中具有置信度c。所以confidence(A=>B) = P(B|A)

{冰激凌，批萨}是一个2项集。一个项集的出现频率是包含项集的事务数，即包含该物品组合的篮子数量，这个称为该项集的绝对支持度或计数:support_count，若这个值大于某个阈值，那么这个项集就称为频繁项集。

由条件概率公式可以得出：confidence(A=>B) = P(B|A) = support(AUB)/support(A) ＝ support_count(AUB)/support_count(A)

那么只要知道有多少篮子里出现了批萨，以及有多少篮子里同时出现冰激凌和批萨，就可以求得出现冰激凌的条件下出现批萨的概率。

关联规则的挖掘就可以归结为挖掘频繁项集：

(1)找出所有的频繁项集。

(2)由频繁项集产生强关联规则

也就是说找出所有篮子里常出现的组合，然后在这些组合中发现规律。

显然第一步的复杂度远高于第二步，因而总体性能由第一步决定。

显然一个项集是频繁的，其子集也是频繁的，因为包含了该项集的事务必然也包含该项集的子集。换句话说只要冰激凌和批萨的组合是频繁出现的，那么冰激凌和批萨本身必然也是频繁出现的。所以往往频繁项集的数据量是非常大的。为了克服这个困难，引入了闭频繁项集和极大频繁项集的概念。

若项集X是闭的，那么只要X是Y的子集，则Y的计数一与X的计数不同。

若项集X是极大频繁的，那么只要X是频繁的，并且X是Y的子集，那么Y一定不是频繁的。

这里，“极大”很好理解，只要再多一个物品，那么这个组合就不符合频繁了。“闭”这个字不好理解，我们可以认为只要多一个元素，一定就会发生改变，就像临界点一样。

比如数据库里只有两个事务，或者说我们只调查了两个顾客的篮子。第一个是{柴，米，油，盐，酱，醋，茶}，第二个是{柴，米，油，盐}。加入最小阈值为1，也就是说出现次数多于1次的组合就是频繁的。那么显然柴，米，油，盐，酱，醋，茶都是频繁的，而柴，米，油，盐的计数为2，酱，醋，茶的计数为1。这时如果把在集合{柴，米，油，盐}中再增加一个元素，那么新集合的计数必然变化为2，因而第二个集合是闭频繁的，同理一也是闭频繁的，另外若在一中再增加一个元素，那么新集合计数就变为0了，因而一还是极大频繁的。

以上购物篮分析只是频繁挖掘的一种形式。事实上，形式有很多种，不同类型的形式对应了不同的计算和优化方法。我们主要研究挖掘频繁项集的完全集，闭频繁项集，和被约束的频繁项集(即满足用户指定的一组约束的频繁项集)，我们的研究针对最基本的情况(单层、单维、布尔)。

单层：表示每个物品只有一个抽象层(如冰激凌和DQ就是两个抽象层的东西)

单维：表示每个物品只涉及一个维(如30－40年龄段的人、收入5000到8000的人的购物篮)

布尔：即只考虑每个元素是否出现。