购物篮模型.pptx

第六章第六章频繁繁项集集 6.1 购物物篮模型模型2024/5/21 周二1 1购物物篮模型（模型（market-basket model）本质：描述“项”(item)和“购物篮”(basket /transaction)两类元素之间的多对多关系。通常我们假设一个购物篮中项的总数目较小，相对于所有项的总数目而言要小的多。而购物篮的数目通常假设很大，导致在内存中无法存放。整个数据假定由一个购物篮序列构成的文件来表示。2024/5/21 周二2 2频繁项集与相似项发现的区别频繁项集问题主要关注包含某个特定项集的购物篮的绝对数目。相似项发现主要目标是寻找购物篮之间具有较高重合度的项集，不管购物篮数目的绝对数量是否很低。2024/5/21 周二3 3一、一、频繁繁项集（集（frequent item）的定）的定义直观上：一个在多个购物篮中出现的项集成为频繁项集。形式化：如果I的支持度不小于s，则称I是频繁项集。s：支持度阈值（support threshold）I的支持度(support)：包含I（即I是购物篮中项集的子集）的购物篮数目。2024/5/21 周二4 4例6.1 购物篮：每个集合项：词语这些集合是通过在谷歌搜索“cat dog”然后从排名较高的网页摘要中生成。由于购物篮是集合，所以一个词语在某个购物篮中出现两次不会被考虑。即项在购物篮中只能出现一次。这些词语中的大写被忽略。2024/5/21 周二5 52024/5/21 周二6 6单元素集合空集：空集是任何集合的子集，支持度为8。但通常情况下不关注空集。“cat”：6（出现在除（4）和（8）的购物篮中）“dog”：7（在除（5）之外的购物篮中都出现）“and”：5“a”、“training”：3“for”、“is”：2其他：不多于1假定给出的支持度阈值s为3，频繁项集为dog、cat、and、a、training2024/5/21 周二7 7双元素集合一个双元素集合中的两个元素本身都必须是频繁的，这样该集合才有可能是频繁的。所有可能的双元素频繁集合只有10个。2024/5/21 周二8 8三元素集合三个元素组成的项集要成为频繁项集，必须要求其中任意两个元素组成的集合都是频繁的。频繁的双元素项集：dog,a dog,and dog,cat cat,andeg.集合dog,a,and不可能是频繁项集，因为如果它是的话，那么必定有a,and是频繁项集，但是这个集合并不频繁。eg.集合dog,cat,and有可能频繁，因为dog,cat cat,and为频繁项集，但是集合中的三个词只在购物篮（1）和（2）中出现，因此实际上并不频繁。如果不存在三元素频繁项集，肯定不会存在四元素或更多元素的频繁项集。2024/5/21 周二9 9二、二、频繁繁项集的集的应用用最早应用：真实的购物篮分析项：商店出售的不同商品购物篮：单个购物车中所装的商品 通过发现频繁项集，零售商可以知道哪些商品通常会被顾客一起购买。那些共同购买的频度远高于各自独立购买所预期的频度的项对或项集。2024/5/21 周二10102024/5/21 周二1111其他应用1.关联概念(related concepts)项：词购物篮：文档文档中所有词构成对应购物篮中的所有项如果忽略所有停用词，我们希望在高频词对中发现某些能够代表联合概念的一部分词对。2024/5/21 周二12122.文档抄袭(plagiarism)项：文档购物篮：句子一篇文档中如果包含某个句子，则认为该句子对应的购物篮中包含文档对应的项。我们寻找那些在多个购物篮中共同出现的项对。如果发现这样的项对，就是两篇文档有很多相同的句子。实际中，一到两个句子相同都是抄袭发生的有力证据。2024/5/21 周二13133.生物标志物(biomarker)项：诸如基金或血蛋白之类的生物标志物 疾病购物篮：某个病人的数据集（基因组、血生化分析数据、病史信息）频繁项集：由某个疾病和一个或多个生物标志物构成，它们组合在一起给出的是疾病的一个检测建议。2024/5/21 周二1414三、关三、关联规则(association rule)关联规则：从数据中抽取到的频繁项集结果往往采用if-then形式的规则集合来表示，这些规则称为关联规则。形式：Ij(I为项集，j为项)如果I中所有项出现在某个购物篮的话，那么j“有可能”也出现在这一购物篮。2024/5/21 周二1515可信度（confidence）Ij的支持度/I的支持度 即所有包含I的购物篮中同时包含j的购物篮的比例。2024/5/21 周二1616例6.2cat,dogand的可信度：3/5dogcat的可信度：5/72024/5/21 周二1717兴趣度(interest)其可信度与包含j的购物篮比率之间的差值。一条规则的兴趣度很高：某个购物篮中I的存在在某种程度上会促进j的存在；兴趣度为绝对值很大的负值：I的存在会抑制j的存在。2024/5/21 周二1818eg.dogcat的兴趣度计算 dogcat的可信度：5/7 cat出现在所有8个购物篮中的6个 5/76/8=0.036该关联规则并不十分“有趣”2024/5/21 周二1919例6.3diapersbeer的兴趣度很高：购买尿布的人中购买啤酒的比率显著高于所有顾客中购买啤酒的比率。cokepepsi的兴趣度为负值：购买可口可乐的顾客一般不会同时购买百事可乐。2024/5/21 周二2020四、高可信度关四、高可信度关联规则的的发现可以找到可以找到频繁繁项集集关关联规则应用用于很多于很多购物物篮,则I的支持度要的支持度要相当高相当高集合集合Ij的支的支持度也相当高持度也相当高可找到高支持度可找到高支持度和高可信度的关和高可信度的关联规则假定假定频繁集繁集项不不会太多，会太多，则高支高支持度高可信度的持度高可信度的关关联规则也不会也不会太多太多实际当中要当中要调节支持度支持度阈值来限制来限制频繁繁项集集2024/5/21 周二21212024/5/21 周二2222