购物篮模型(完整版).pptxVIP

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