第三节 描述型数据探勘模式
一、关联法则
关联法则可以说是数据探勘中最有名的一项应用，又称为购物篮分析(Market Basket Analysis)，最早是由Agrawal et al.(1993)所提出的，并随后于1994提出Apriori算法(Agrawal and Srikant, 1994)。是一套探索变量间关联的数据探勘技术，常应用于商业营销与客户关系管理(CRM – Customer Relationship Management)上。其原始构想是用来分析顾客的消费行为，也就是说当顾客走进卖场推着推车购物时，购物车上总是放着多样不同的商品，交易结账后，数据库内会纪录着每一顾客交易的明细，关联法则企图从消费者的交易纪录中，找出那些产品总是被顾客同时购买，如此，便可以进行货架的安排或是营销策略的制定。最有名的例子，就是美国Walmart卖场发现了尿布与啤酒之间的关联性。另外日常生活中常见的例子，还有亚马逊电子书局之在线购物，比如当我们挑选了A书后，网站会建议顾客，通常购买A书的顾客也会购买B、C或D书，藉以吸引顾客以获得额外的商机。另外，银行也可以借着由探勘消费事务数据库中的关联法则来分析消费者的行为，做为未来一对一客制化营销上的参考。
1. 关联法则之定义：
我们先为它做一简单的描述，并以购物交易作例子来说明(Agrawal et al., 1993; Agrawal and Srikant, 1994; Chen et al., 1996)：假设I = {i1, i2, i3,….im}表示商场内所有商品，即项目(items)的集合，称作项目集(itemsets)，而其中每一笔交易T为部份项目的集合，即T ? I。假设X是一个项目集合，若 X ? T，我们可以说T包含X。而关联法则「购买X商品也会同时购买Y商品」的形式如下：
X ? Y [Support, Confidence] 其中，
X ? I, Y ? I 及 X ∩ Y = ? (空集合) Support = Probability(X∪Y)
Confidence = Probability(X∪Y)/ Probability(X)
X和Y都是购物项目(items)的集合，不限单一商品或项目，另外还
包含两个最重要的指标，信赖度(confidence)与支持度(support)。
信赖度(confidence)：代表条件机率，即此一规则的准确度有多少，为购
买X产品项目的顾客中有也会同时购买Y产品项目的比率，即(the number of transactions containing X and Y)/(the number of transactions containing X)。信赖度越高，则此一法则越有参考价值。
支持度(support)：是事务数据库中，同时包含有X与Y商品项目，占全
部交易数的百分比，即(the number of transactions containing X and Y)/(the number of transactions)的值。信赖度高固然表示规则具有很高的准确度，但是前提是该种交易型态出现的次数够多，该法则才具有代表性。
进行关联法则数据探勘前，通常必须先订出最小的信赖度门坎与最小的支持度，来剔除不合格的规则，才能从大量的候选规则中筛选出合格或有用的法则。它的计算程序很简单，可以分为两个阶段：
(1) 找出大项目集合(Large Itemsets)：首先计算各单一项目在数据库中出现的次数，判断其是否大于等于使用者所定义的最小支持度(minimum support)，以决定出大项目集Li(Large I-itemsets)。其做法是在每个回合中进行合并及删除的阶段，产生候选项目集合(candidate itemsets)，接着对每个候选项目集合计算其支持度，将满足最小支持度的候选项目成为大项目集合，如此反复上述步骤，值到无法产生新的候选项目集合为止(如图3-6)。 (2)产生关联法则：将每个大项目集(即X∪Y的支持度达到最小持度的集合)，以X∪Y的支持度除以X的支持度，以计算出X ? Y的信赖度。若信赖度达到使用者定义之最小信赖度(minimum confidence)，则X ? Y这样的关联法则成立。
本研究以Apriori算法做为关联法则探勘上的方法,做法如以下说明； Lk – 当数据的support大于minimum support则称该资料为large
k-itemset，k为数据内的项目数(number of item)，Lk为资料项数
k且support又大于minimum support数据的集合。 Ck – 有k个数据项数且具有large潜力之数据的集合。 C’k – 每一个transaction 中包含有Candidate元素的集合。
对于每一transaction中每一数据项，以其项目码以排序方式来表达(例如根据货品编号顺序有小而大排列)
Apriori算法： Apriori() {
L1 = {large 1-itemset}; for (k=2; Lk-1??;k++) {
Ck = CandidateGenerate(Lk-1); for all transactions t?D {
Ct = Subset(Ck,t); for all candidate t? Ct
c.count++;
}//end for
Lk = { c?Ck? c.count > Minimum Support}; }//end for
Answer = ?k Lk; }//end of function
有关候选large k-itemset集合的产生，是程序中较耗时的部份，但藉由程序语言以及其数据库管理功能，我们可以很方便的SQL语言来产生，方法如下：
CandidateGenerate() {
RunSQL(“insert into Ck
Select p.item1, p.item2,…p.itemk-1, q.itemk-1
from Lk-1 p, Lk-1 q
where p.item1 = q.item1, p.item2 = q.item2,… p.itemk-1 < q.itemk-1”) ; //去掉不符合的项目 for all candidate c? Ck for all (k-1)-subset s of c if (s?Lk-1) then delete c from Ck; }//end of function
另外，我们可以注意到在Apriori算法中Ct = Subset(Ck,t)，是为了找出每笔transaction到底有那些itemset是属于候选large k-itemset，由于必须针对所有transaction做比对，颇为耗时，为了增进执行效率，我们以数据结构中哈希表(hash table)的观念来解决(Jones 1997)，为了使内存做更有效率的运用，我们将哈希表改为易失存储器配置的哈希表，并且藉由指标串连建成哈希树(hash tree)，其做法如图3-7说明，将所有候选itemset集合 Ck建成一株哈希树，其内部节点为哈希表，叶节点则为各个itemset，根节点为树高1，若为k-itemset表示树高为k(不含叶节点)，第d层的内部节点指向第d+1层的内部节点，当我们加入一个itemset c时，由根节点开始针对每个item做哈希函数计算以做为分枝的依据，不停的做递归调用直到叶节点为止﹐并且将所有的itemset建立起来。而寻找的方式则是透过建好的哈希树，对每一笔transaction将其导入哈希树中，找出该笔transaction有那些次集合属于在候选集合Ck中，对于每一笔transaction的每一个item均由根节点起始，然后使用哈希函数做为分枝的计算，当使用哈希函数分枝至第i项item时，再以第i+1项item做为哈希计算，如此不断递归调用向下找，当碰到叶节点时该叶节点为部份子集合，将其加入集合中。
TID Itemset Database TID 100 200 300 400 Itemset C’1 { {1}, {3}, {4} } { {2}, {3}, {5} } { {1}, {2}, {3}, {5} } { {2}, {5} } Itemset L1 {1} {2} {3} {5} Support 2 3 3 3 100 200 300 400 1 3 4 2 3 5 1 2 3 5 2 5 C2
C’2 TID 100 200 300 Itemset C3
{1 2} {1 3} {1 5} {2 3} {2 5} Itemset { {1 3} } { {2 3}, {2 5}, {3 5} } { {1 2}, {1 3}, {1 5}, {2 3},{2 5},{3 5}} L2
Itemset {1 3} {2 3} {2 5} {3 5} Support 2 2 3 2
C’3 TID 200 300 L3 Itemset {2 3 5} Itemset
{2 3 5} Itemset { {2 3 5} } { {2 3 5} } Support 2 图3-6 关连法则范例说明(Agrawal and Srikant 1994)
2 3 5 3 5 內部節點 5 根節點 1 2 3
图3-7 哈希树
1,2 1,3 1,5 2,3 2,5 葉節點 3,5