(c) 给定频繁项集l和l的子集s，证明规则”s’ ? (l-s’)”的置信度不可能大于”s ? (l-s)”的置信度。其中，s’是s的子集。
(d) Apriori的一种变形将事务数据库D中的事务划分成n个不重叠的部分。证明在D中是频繁的任何项集至少在D的一个部分中是频繁的。
6.2 6.2.2小节介绍了由频繁项集产生关联规则的方法。提出一个更有效的方法。解释它为什么比
6.2.2小节的方法更有效。（提示：考虑将习题6.1(b)和6.1(c)的性质结合到你的设计中） 6.3 数据库有4个事务。设min_sup = 60%，min_conf = 80%。
TID T100 T200 T300 T400
date 10/15/99 10/15/99 10/19/99 10/22/99
items_bought {K,A,D,B} {D,A,C,E,B} {C,A,B,E} {B,A,D}
(a) 分别使用Apriori和FP-增长算法找出频繁项集。比较两种挖掘过程的有效性。
(b) 列出所有的强关联规则（带支持度s和置信度c），它们与下面的元规则匹配，其中，X是代表顾客的变量，itemi是表示项的变量（例如，”A”、”B’等）：
? x? transaction, buys(X, item1) ?buys(X, item2) ? buys(X, item3) [s, c]
6.4 数据库有4个事务。设min_sup = 60%，min_conf = 80%。
cust_ID 01 02 01 03
TID T100 T200 T300 T400
items_bought（以brand-item_category形式）
{King’s-Carb, Sunset-Milk, Dairyland-Cheese,best-Bread}
{Best-Cheese, Dairyland-Milk, Goldenfarm-Apple, tasty-Pie, Wonder-Bread} {Westcoast-Apple, Dairyland-Milk, Wonder-Bread, Tasty-Pie} {Wonder-Bread, Sunset-Milk, Dairyland-Cheese}
(a) 在item_category粒度（例如，itemi可以是“Milk”），对于下面规则模板
? x? transaction, buys(X, item1) ?buys(X, item2) ? buys(X, item3) [s, c] 对最大的k, 列出频繁k -项集和包含最大的k的频繁k-项集的所有强关联规则。 (b) 在brand-item_category粒度（例如，可以是“Sunset-Milk”），对于下面的规则模板
? x? customer, buys(X, item1) ?buys(X, item2) ? buys(X, item3) 对最大的k, 列出频繁k -项集。注意：不打印任何规则。
6.5 假定一个大型存储具有分布在4个站点的事务数据库。每个成员数据库中的事务具有相同的格
式Tj: {i1 ,..., im}；其中，Tj是事务标识符，而ik(1 ? k ? m)是事务中购买的商品标识符。提出一个有效的算法，挖掘全局关联规则（不考虑多层关联规则）。你可以给出你的算法的要点。你的算法不必将所有的数据移到一个站点，并且不造成过度的网络通讯开销。 6.6 假定大型事务数据库DB的频繁项集已经存储。讨论：如果新的事务集?DB（渐增地）加进，
在相同的最小支持度阈值下，如何有效地挖掘（全局）关联规则？ 6.7 假定描述Big-University大学学生的数据关系已被泛化为表6.6的泛化关系R。
设概念分层如下：
status: {freshman, sophomore, junior, senior} ? undergraduate
{M.Sc, M.A, Ph.D} ? graduate
major: {physics, chemistry, math} ? science
{CS, engineering} ? appl_science
age: {16...20, 21-25} ? young
{26...30, over_30} ? old
nationality: {Asia, Europe, Latin_America}? foreign
{Canada, U.S.A.} ?North_America
表6.6 习题6.7的泛化关系
major French CS physics engineering philosophy French chemistry CS
philosophy French philosophy philosophy French math CS
philosophy philosophy French engineering math chemistry engineering French philosophy math
status M.A junior M.S Ph.D Ph.D senior junior senior M.S junior junior M.S junior senior junior Ph.D senior Ph.D junior Ph.D junior junior M.S junior junior
age over_30 16...20 26...30 26...30 26...30 16...20 21...25 16...20 over_30 16...20 26...30 26...30 16...20 16...20 16...20 26...30 26...30 over_30 21...25 26...30 16...20 21...25 over_30 21...25 16...20
nationality Canada Europe
Latin_America Asia Europe Canada U.S.A. Canada Canada U.S.A. Canada Asia Canada U.S.A. Canada Canada Canada Canada Europe
Latin_America U.S.A. Canada
Latin_America U.S.A. Canada
gpa 2.8...3.2 3.2...36 3.2...3.6 3.6...4.0 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.6...4.0 2.8...3.2 2.8...3.2 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.6...4.0 2.8...3.2 2.8...3.2 3.2...3.6 3.2...3.6 3.6...4.0 3.2...3.6 3.2...3.6 2.8...3.2 3.6...4.0
count 3 29 18 78 5 40 25 70 15 8 9 9 52 32 76 14 19 1 71 7 46 96 4 8 59
设最小支持度阈值为2%，最小置信度阈值为50%（每一层）。
(a) 画出status, major, age, nationality的概念分层。 (b) 对所有层使用一致的支持度，对于下面的规则模板
? S ? R P(S,x) ? Q(S,y) ? gpa(S, z) [s, c]
其中，P, Q ? {status, major, age, nationality}。找出R中的多层强关联规则。
(c) 使用层交叉单项过滤，找出R中的多层强关联规则。其中，递减的支持度10%用于如下规则模板的最低抽象层：
? S ? R P(S,x) ? Q(S,y) ? gpa(S, z) [s, c] 不要挖掘交叉层规则。 6.8 提出并给出挖掘多层关联规则的层共享挖掘方法的要点。其中，每个项用它的层位置编码，一
次初始数据库扫描收集每个概念层的每个项的计数，识别频繁和子频繁项集。将用该方法挖掘多层关联规则与挖掘单层关联规则的花费进行比较。
?的项集H的支持度与项集H-h?的支持度相同。解释如何将它用于6.9 证明：包含项h和其祖先h层交叉关联规则挖掘。
6.10 在挖掘层交叉关联规则时，假定发现项集”{IBM dssktop computer, printer}”不满足最小支持
度。这一信息可以用来剪去诸如”{IBM desktop computer, b/w printer}”的“后代”项集的挖掘吗？给出一个一般规则，解释这一信息如何用于对搜索空间剪枝。 6.11 提出一种挖掘混合维关联规则（多维关联规则，有重复谓词）的方法。
6.12 给出一个短例子，表明强关联规则中的项可能实际上是负相关的。
6.13 下面的相依表汇总了超级市场的事务数据。其中，hot dog表示包含热狗的事务，hotdog表示
不包含热狗的事务，humburgers表示包含汉堡包的事务，humburgers表示不包含汉堡包的事务。
hot dog hotdog
humburgers 2,000 500
1,000 1,500 humburgers 3,000 2,000 ?col
?row 2,500
2,500 5,000
(a) 假定发现关联规则”hot dog ? humburgers”。给定最小支持度阈值25%，最小置信度阈值50%，该关联规则是强的吗？ (b) 根据给定的数据，买hot dog独立于买humburgers吗？如果不是，二者之间存在何种相关联系？ 6.14 序列模式可以用类似于关联规则挖掘的方法挖掘。设计一个有效的算法，由事务数据库挖掘
多层序列模式。这种模式的一个例子如下：“买PC的顾客在三个月内将买Microsoft软件”，在其上，可以下钻，发现该模式的更详细的版本，如“买Pentium Pro的顾客在三个月内将买Microsoft Office ”。 6.15 证明下面表中的每一项正确地刻画了它对应的关于频繁项集挖掘的规则限制。
(a) (b) (c) (d)
规则限制 v?S S ? V min(S) ? v range (S) ? v
反单调性 否 是 否 是 可变的
单调性 是 否 是 否
简洁性 是 是 是 否
(e) avg(S) ? v
可变的 否
6.16 商店里每种商品的价格是非负的。商店经理只关心如下形式的规则：“一件免费商品可能触
发在同一事务中$200的总购物”。陈述如何有效地挖掘这种规则。 6.17 商店里每种商品的价格是非负的。对于以下每种情况，识别它们提供的限制类型，并简略讨
论如何有效地挖掘这种关联规则。
(a) 至少包含一件Nintendo游戏。
(b) 包含一些商品，它们的单价和小于$150。
(c) 包含一件免费商品，并且其它商品的单价和至少是$200。 (d) 所有商品的平均价格在$100和$500之间。
文献注释
关联规则挖掘首先由Agrawal, Imielinski和Swami[AIS93b] 提出。6.2.1小节讨论的Apriori算法由Agrawal和Srikant [AS94] 提出。使用类似的剪枝方法的算法变形独立地由Mannila, Toivonen和Verkamo[MTV94]开发。结合这些工作的联合出版物稍后出现在Aga\\rawal, Mannila, Skrikant, Toivonen和Verkamo[AMS+96]。产生关联规则的方法在Agrawal和Srikant[AS94a]中介绍。6.2.3小节的Apriori的变形包括如下引文。使用hash表提高关联规则挖掘效率被Park,Chen和Yu[PCY95]研究。扫描和事务压缩技术在Agrawal和Srikant[AS94b]，Han和Fu[HF95]，以及Park, Chen和Yu[PCY95a]中介绍。划分技术由Savasere, Omiecinski和Navathe[SON95]提出。选样方法在Toivonen[Toi96]中讨论。动态项集计数在Brin, Motwani, Ullman和Tsur[BMUT97]中给出。关联
规则挖掘有许多扩充，包括序列模式挖掘（Agrawal和Srikant[AS95]），espisodes挖掘（Mannila, Toivonen和Verkamo[MTV97]），挖掘空间关联规则（Kopeski和Han[KH95]），挖掘有环的关联规则（?zden, Ramaswamy和Silberschatz[ORS98]），挖掘否定的关联规则（Savasere, Omiecinski和Navathe[SON98]），挖掘事务间关联规则（Lu, Han和Feng[LHF98]）和日历购物篮分析（Ramaswamy, Mahajan和Silberschatz[RMS98]）。最大模式的挖掘在Bayaedo[Bay98]中介绍。频繁闭合项集的挖掘由Pasquier, Bastile, Taouil和Lakhal[PBTL99]提出，而有效的挖掘算法由Pei, Han和Mao[PHM00]提出。冰山查询在Fang, Shivakumar, Garcia-Molina等[FSGM+98] 中介绍，而Beyer和Ramakrishnan[BR99]开发了冰山查询的有效计算方法。频繁项集的深度优先产生由Agrawal,Aggarwal和Prasad[AAP00]提出。挖掘频繁模式而不产生候选的方法由Han, Pie和Yin[HPY00]提出。
多层关联规则挖掘在Han和Fu[HF95]，Srikant和Agrawal[SA95]中研究。在Srikant和Agrawal [SA]中，这种挖掘以广义关联规则的形式研究，并提出R-兴趣度度量，以删除冗余规则。
6.4.3小节介绍的根据规则聚类挖掘量化关联规则的ARCS系统由Lent,Swami和Widom[LSW97]提出。基于x-单调和直线区间挖掘量化规则的技术由Fukuda, Morimoto, Morishita和Tokuyama[FMMT96]，Yoda, Fukuda, Morimoto等[YFM+97]提出。挖掘量化关联规则的非基于栅格的技术使用部分完全性度量，由Srikant和Agrawal[SA96]提出。6.4.3小节介绍的挖掘区间数据上的（基于距离的）关联规则由Miller和Yang[MY97]提出。使用量化属性的静态离散化和数据方，挖掘多维关联规则被Kamber, Han和Chiang[KHC97]研究。
在数据挖掘中规则的统计独立性被Piatetski_Shapiro[PS91]研究。强关联规则的兴趣度问题被Chen, Han和Yu[CHY96]，Brin, Motwani和Silverstein[BMS97], Aggarwal和Yu[AY99]讨论。推广关联到相关的有效方法在Brin, Motwani 和Silverstein[BMS97]，并简略总结6.5.2小节中。评估关联规则兴趣度的支持度-置信度框架的其它替代在Brin, Motwani, Ullman和Tsur[BMUT97]，Ahmed, EI-Makky和Taha[AEMT00]中提出。Silverstein, Brin, Motwani和Ullman[SBMU98]研究了挖掘事务数据库因果关系结构的问题。
使用元规则作为语法或语义过滤器，定义单维关联规则的感兴趣形式由Klemettinen, Mannila, Ronkainen等[KMR+94]提出。元规则制导的挖掘在Shen, Ong, Mitbander 和Zaniolo[SOMZ96]中提出；那里，元规则后件指定用于满足元规则前件的数据的动作（如，贝叶斯聚类）。关联规则元规则制导的挖掘基于关系的方法在Fu和Han[HF95]中研究。基于数据方的方法在Kamber, Han和Chiang[KHC97]中研究。6.4.2小节基于限制的关联规则挖掘在Ng, Lakshmanan, Han和Pang[NLHP98]，Lakshmanan, Ng, Han和Pang [LNHP99], Pei和Han[PH00]中研究。挖掘受限的相关集的有效方法在Grahne, Lakshmanan和Wang[GLW00]中给出。涉及在挖掘中使用模板或谓词限制的其它思想在[AK93, DT93, HK91, LHC97, St96, SVA97]中讨论。
本章提供的关联规则挖掘语言基于Han, Fu, Wang等[HFW+96]提出的数据挖掘查询语言DMQL的扩充，结合了由Meo,Paila和Ceri[MPC96]提出的挖掘单维关联规则的类SQL的操作。预计今后的版本将遵循Microsoft公司提出的DM OLE DB[Mic00]语法。
挖掘关联规则的有效渐增更新由CheungHan, Ng和Wong[CHNW96]提出。在Apriori框架下，并行和分布关联规则挖掘被Park,Chen和Yu[PCY95b]，Agrawal和Shafer[AS96]，Cheung, han, Ng等[CHN+96]研究。另一种并行关联规则挖掘方法使用垂直数据库设计探查项集聚类，在Zaki, Parthasarathy, Ogihara和Li[ZPOL97]中提出。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据挖掘CHAPTER6挖掘大型数据库中的关联规则(6)在线全文阅读。
相关推荐：