搜索
第二次作业1.Apriori算法使用子集支持性质的先验知识。(a)证明频繁项集的所有非空的子集也必须是频繁的。答：设s是一个频繁项集，min_sup是最小支持度阀值，任务相关的数据D是数据库事务的集合，|D|是D有事务量，则有Support_count(s)=min_sup×|D|；再设s’是s的非空子集，则任何包含项集s的事务将同样包含项集s’,即：support_count(s')supportcount(s)=min_sup×|D|.所以，s’也是一个频繁项集。(b)证明项集s的任意非空子集s’的支持至少和s的支持度一样大。答：设任务相关的数据D是数据库事务的集合，|D|是D的事务量，由定义得：设s’是s的非空子集，由定义得：由（a）可知：support(s’)support(s)由此证明，项集s的任意非空子集s’的支持至少和s的支持度一样大。（c）给定频繁项集l和l的子集s,证明规则的置信度不可能大于答：设s是l的子集,则设s’是s的非空子集，则由（b）可知：support_count(s')supportcount(s)，此外，confidence(s’)(l-s’))confidence(s)(l-s))所以，规则的置信度不可能大于。(d)Apriori算法的一种变形将事务数据库D中的事务划分成n个不重叠的分区。证明在D中频繁的项集至少在D的一个分区中是频繁的。答：假设频繁项集在D的任何部分中都不频繁。设F为D的任何频繁项集。令D是相关事务数据集。令C是D中事务的总数量。令A是D中包含F的事务数量。令min_sup是最小支持度阈值。因为F是频繁项集，所以A=C*min_sup.令D分成n个不重叠的部分，d1,d2„dn。那么D=d1d2„dn.令c1c2„cn分别是各部分d1„dn的事务数量。则C=c1+c2+„+cn令a1a2„an分别是各部分d1„dn中包含F的事务数量，则A=a1+a2+„+anA=C*min_sup即a1+a2+„+an=(c1+c2+„+cn)*min_sup①由假设知F在各部分d1„dn中都不是频繁的，所以aici*min_sup(i=1,2,3,„,n)把式子加起来得a1+a2+„+an(c1+c2+„+cn)*min_sup,②可得①②矛盾，所以原假设不成立2．6.2.2节介绍了由频繁项集产生关联规则的方法。提出一个更有效的方法。解释它为什么比6.2.2节的方法更有效。（提示：考虑将习题6.3（b）和6.3（c）的性质结合到你的设计中。）方法1：基于hash表的项集计数将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。方法2：事务压缩（压缩进一步迭代的事务数）不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。方法3：划分挖掘频繁项集只需要两次数据扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集3.设数据库有5个事务。设min_sup=60%,min_conf=80%(a)分别使用Apriori和FP增长算法找出所有频繁项集。比较两种挖掘过程的效率。效率比较：Apriori需多次扫描数据库而FP增长建立FP树只需一次的扫描。在Apriori算法中产生候选是昂贵的（由于联接），而FP增长不产生任何候选。(b)列举所有与下面的元规则匹配的强关联规则（给出支持度S和置信度C）,其中，X是代表顾客的变量，itemi是表示项的变量（如：“A”、“B”等）：答：k,oe[0.6,1]e,ok[0.6,1]4．下面的相依表汇总了超级市场的事务数据。其中，hotdogs表示包含热狗的事务，hotdogs表示不包含热狗的事务，hamburgers表示包含汉堡包的事务，hamburgers表示不包含汉堡包的事务。a.假定挖掘出了关联规则“hotdogshumburgers”。给定最小支持度阀值25%，最小置信度阀值50%，该关联规则是强规则吗？答：根据规则，support=2000/5000=40%，confidence=2000/3000=66.7%.该关联规则是强规则.b.根据给定的数据，买hotdogs独立于买humburgers吗？如果不是，二者之间存在何种相关联系？答：corr{hotdog;hamburger}=P({hotdog,hamburger})/(P({hotdog})P({hamburger})=0.4/(0.5×0.6)=1.331.所以，买hotdogs不是独立于买humburgers。两者存在正相关关系c.在给定的数据上，将全置信度、最大置信度、Kulczynski和余弦的使用与提升度和相关度进行比较。P(hotdogs|humburgers)=0.8P(humburgers|hotdogs)=0.67全置信度：0.67最大置信度：0.8Kulczynski：0.74余弦：0.73提升度：1.3相关度：2.33