【正文】 ,70 3 June 25’99 30,50,70 4 4 4 June 25’99 June 30’99 July 25’99 30 40,70 90 5 June 12’99 90 圖 (Cust_id)及交易時間 (Tran_time) 排序的源數(shù)據(jù)庫 圖 2) 關聯(lián)規(guī)則 a.) 關聯(lián)規(guī)則的概念及定義 考察一些涉及許多物品的事務：事務 1 中出現(xiàn)了物品甲，事務 2 中出現(xiàn)了物品乙，事務 3 中則同時出現(xiàn)了物品甲和乙。那么，物品甲和乙在事務中的出現(xiàn)相互之間是否有規(guī)律可循呢？在數(shù)據(jù)庫的數(shù)據(jù)挖掘中， 關聯(lián)規(guī)則 就是描述這種在一個事務中物品之間同時出現(xiàn)的規(guī)律的知識模式。更確切的說，關聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對物品乙的出現(xiàn)有多大的影響。 現(xiàn)實中，這樣的例子很多。例如超級市場利用前端收 款機收集存儲了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購買事務記錄，每條記錄存儲了事務處理時間，顧客購買的物品、物品的數(shù)量及金額等。這些數(shù)據(jù)中常常隱含形式如下的關聯(lián)規(guī)則：在購買鐵錘的顧客當中，有70 ％的人同時購買了鐵釘 。這些關聯(lián)規(guī)則很有價值，商場管理人員可以根據(jù)這些關聯(lián)規(guī)則更好地規(guī)劃商場，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進銷售。 有些數(shù)據(jù)不像售貨數(shù)據(jù)那樣很容易就能看出一個事務是許多物品的集合，但稍微轉(zhuǎn)換一下思考角度，仍然可以像售貨數(shù)據(jù)一樣處理。比如人壽保險，一份保單就是一個事務。保險公司在接受保 險前，往往需要記錄投保人詳盡的信息，有時還要到醫(yī)院做身體檢查。保單上記錄有投保人的年齡、性別、健康狀況、工作單位、工作地址、工資水平等。這些投保人的個人信息就可以看作事務中的物品。通過分析這些數(shù)據(jù)，可以得到類似以下這樣的關聯(lián)規(guī)則：年齡在 40 歲以上，工作在 A 區(qū)的投保人當中，有 45 ％的人曾經(jīng)向保險公司索賠過。在這條規(guī)則中，“年齡在 40 歲以上”是物品甲，“工作在 A 區(qū)”是物品乙，“向保險公司索賠過”則是物品丙?？梢钥闯鰜恚?A 區(qū)可能污染比較嚴重，環(huán)境比較差，導致工作在該區(qū)的人健康狀況不好，索賠率也相對比較 高。 b.) 關聯(lián)規(guī)則的形式 設 I = {i1， i2， ...， im}是一組物品集 (一個商場的物品可能有上萬種 )， D是一組事務集 (稱數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 7 之為事務數(shù)據(jù)庫 )。 D中的每個事務 T 是一組物品，顯然滿足 T?I。稱事務 T 支持物品集 X，如果 X?T。關聯(lián)規(guī)則是如下形式的一種蘊含 :X→ Y，其中 X?I， Y?I，且 X∩ Y= ?。 (1) 稱物品集 X 具有大小為 s 的支持度，如果 D 中有 s%的事務支持物品集 X。 (2) 稱關聯(lián)規(guī)則 X→ Y 在事務數(shù)據(jù)庫 D 中具有大小為 s的支持度，如果物品集 X∪ Y 的支持度為 s。 (3) 稱規(guī)則 X→ Y 在事務數(shù)據(jù)庫 D 中具有大小為 c 的可信度，如果 D 中支持物品 集 X 的事務中有 c%的事務同時也支持物品集 Y。 如果不考慮關聯(lián)規(guī)則的支持度和可信度，那么在事務數(shù)據(jù)庫中存在無窮多的關聯(lián)規(guī)則。事實上，人們一般只對滿足一定的支持度和可信度的關聯(lián)規(guī)則感興趣。在文獻中，一般稱滿足一定要求的 (如較大的支持度和可信度 )的規(guī)則為強規(guī)則。因此，為了發(fā)現(xiàn)出有意義的關聯(lián)規(guī)則，需要給定兩個閾值 :最小支持度和最小可信度。前者即用戶規(guī)定的關聯(lián)規(guī)則必須滿足的最小支持度，它表示了一組物品集在統(tǒng)計意義上的需滿足的最低程度 。后者即用戶規(guī)定的關聯(lián)規(guī)則必須 滿足的最小可信度，它反應了關聯(lián)規(guī)則的最低可靠度。 在實際情況下，一種更有用的關聯(lián)規(guī)則是泛化關聯(lián)規(guī)則。因為物品概念間存在一種層次關系，如夾克衫、滑雪衫屬于外套類，外套、襯衣又屬于衣服類。有了層次關系后，可以幫助發(fā)現(xiàn)一些更多的有意義的規(guī)則。例如 ”買外套 → 買鞋子 (此處，外套和鞋子是較高層次上的物品或概念，因而該規(guī)則是一種泛化的關聯(lián)規(guī)則 )。由于商店或超市中有成千上萬種物品，平均來講，每種物品 (如滑雪衫 )的支持度很低，因此有時難以發(fā)現(xiàn)有用規(guī)則 。但如果考慮到較高層次的物品 (如外套 )，則其支持度就較高，從而可能發(fā) 現(xiàn)有用的規(guī)則。 另外，關聯(lián)規(guī)則發(fā)現(xiàn)的思路還可以用于序列模式發(fā)現(xiàn)。用戶在購買物品時，除了具有上述關聯(lián)規(guī)律，還有時間上或序列上的規(guī)律，因為，很多時候顧客會這次買這些東西，下次買同上次有關的一些東西，接著又買有關的某些東西。 c.) 有關算法的討論 (1) 找出所有具有超出最小支持度的支持度的項集 (itemsets)，由 Apriori 算法實現(xiàn)。 (2) 利用大項集 (litemsets)產(chǎn)生所需的規(guī)則 (rules)。算法的思想在于：如果說 ABCD 和AB 是大項集，我們就可以通過計算可信度，也就是 conf = support(ABCD) / support(AB)，并通過 conf ? miniconf 來確定規(guī)則 AB→ CD 是否確立 (該規(guī)則由于ABCD 是大項集故肯定具有最小支持度 )。 這里我們討論 (1)中的 Apriori 算法，因為根據(jù)此算法得到的大項集，在序列模式階段是有實際用處的。 L1 = {large 1itemsets}。 for ( k = 2。 Lk1 ? ?。 k++) do begin Ck = apriorigen ( Lk1)。 // New candidates,見附圖 _a. 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 8 forall transactions t ? D do begin Ct = subset ( Ck, t )。 // Candidates contained in t forall candidates c ? Ct do ++。 end Lk = { c ? Ck | ? minsup} end Answer = ∪ k Lk。 圖 算法 apriorigen 函數(shù)以 Lk1(所有大 (k1)項集 )作為輸入?yún)?shù)，返回所有大 k項集的集合Lk，以以下兩步實現(xiàn)： 第一步，聯(lián)合 insert into Ck select , ,… , from Lk1p,Lk1q where = ,… , = , 。 第二步，剪枝 (pruning)，如果存在 c 的 (k1)子序列不包含于 Lk1之中，則刪除所有項集 c?Ck。 forall itemsets c?Ck do forall (k1)subsets s of c do if ( s ? Lk1 ) then delete c from Ck。 附圖 函數(shù) ? 舉例 令 L3為 {{1 2 3},{1 2 4},{1 3 4},{1 3 5},{2 3 4}}，聯(lián)合階段后， C4將為 {{1 2 3 4},{1 3 4 5}}。在剪枝階段 {1 3 4 5}將被刪除，因為它的一個子集 {1 4 5}不在 L3之中。這樣我們得到的 C4 中只剩下 {1 2 3 4}。 注：在以 上算法中，支持度是對交易 (transaction)而言的，但在序列模式的計算中，大項集的支持度是對客戶 (customer)數(shù)而言的，故程序需做相應的部分改動。 3) 序列模式 a.) 序列模式的概念及定義 舉例說明，比如有顧客租借錄像帶，典型的順序是先租“星球大戰(zhàn)”，然后是“帝國反擊戰(zhàn)”，再是“杰達武士歸來” (這三部影片是以故事發(fā)生的時間先后而情節(jié)連續(xù)的 )。值得數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 9 注意的是租借這三部電影的行為并不一定需要是連續(xù)的。在任意兩部之間隨便插租了什么電影，仍然還是滿足了這個 序列模式 ，并且擴展一下，序列模式的元素也可 以不只是一個元素(如一部電影 )，它也可以是一個 項集 (item set)。所謂項集，指的是多個物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作是由兩個 項 (item)組成的項集，它也可以作為某一個序列模式的元素。 b.) 一些相關概念及定義 前面已經(jīng)討論過，數(shù)據(jù)源是一個給定的由 客戶交易 (customer transaction)組成的大型數(shù)據(jù)庫，每個 交易 (transaction)由 客戶號 (customerid)， 交易時間 (transactiontime)以及在交易中購買的 項 (item)組成。 (1) 項集 (itemset)是由 項 (item)組成的一個非空集合。 (2) 序列 (sequence)是一列排好序的 項集 不失一般性我們假定項集中的項由一些連續(xù)整數(shù)代替，這樣一個 項集 i 可以表示為(i1,i2… im)，而這里的 ij 代表了一個項。一個 序列 s 可以表示為 s1,s2… sn，這里的 sj代表的是一個項集。 兩個序列 a a1,a2… an和 b b1,b2… bm，如果存在整數(shù) i1i2… in 且 a1 包含于 bi1， a2 包含于 bi2， … ， an包含于 bin，則稱序列 a包含于序列 b。比如 序列 (3) (4,5) (8) 包含于序列 (7) (3,8) (9) (4,5,6) (8) ，因為 (3)包含于 (3,8)， (4,5)包含于 (4,5,6)以及 (8)包含于 (8)。但是序列 (3) (5) 不包含于 (3,5) ，反之亦然。前者表示項 3 和項 5是先后購買的，而后者則表示項 3 和項 5 是同時購買的，這就是區(qū)別所在。在一個 序列集 (a set of sequences)中如果序列 s不包含于任何其他序列中，則稱序列 s 為 最大的 (maximal)。 一個客戶所有的 事務 (transactions)可以綜合的看成是一個序列，每一個事務都由相應的一個項集來表示。事務按交易時間序排列就成了一個序列。我們稱這樣的序列為 客戶序列(customersequence)。通常，將一個客戶的交易按交易時間排序成 T1 ， T2 ，??， Tn。 Ti中的項集定義成 itemset(Ti)。這樣，這個客戶的客戶序列就成了這樣的一個序列： 〈 itemset(T1) itemset(T2) … itemset(Tn)〉 。見圖 _2。 Customer Id Customer Sequence 1 2 3 4 5 (30) (90) (10,20) (30) (40,60,70) (30,50,70) (30) (40,70) (90) (90) 圖 如果一個序列 s 包含于一個客戶序列中，則我們稱該客戶 支持 (support)序列 s。一個具體序列的 支持 (support)定義為那一部分 支持 該序列的客戶總數(shù)。 給定一個由客戶交易組成的數(shù)據(jù)庫 D，挖掘序列模式的問題就是在那些具有客戶指定 最小支持度 (minimum support)的序列中找出 最大序列 (maximal sequence)。而每個這樣的 最大序數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 10 列 就代表了一個 序列模式 (sequential pattern)。 ? 舉例說明： 我們看圖 _1 表示的數(shù)據(jù)庫 (該數(shù)據(jù)庫已經(jīng)按客戶號和交易時間排了序 )。圖 _2 則以客戶序列集的形式表示了該數(shù)據(jù)庫。 對于最小支持為 25%的情況，也就是最小支持 2 個客戶 (因為一共有 5 個客戶 )，有兩個序列： (30) (90) 和 (30) (40,70) 在那些滿足 支持度約束 (the support constraint)的序列中是 最大 (maximal)的，也是我們所需的 序列模式 。序列模式 (30) (90) 被客戶 1 和客戶 4 所支持 (support)?？蛻?4 在項 30 和項 90 之間買了項（ 40,70），但仍然支持模式 (30) (90) ，這是因為我們所找的模式并不需要一定連續(xù)。序列模式 (30) (40,70) 被客戶 2 和客戶 4 所支持。客戶 2 在買項 60 的同時也買了項 40 和項