【正文】 (item)組成。更確切的說，關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對物品乙的出現(xiàn)有多大的影響。這些關(guān)聯(lián)規(guī)則很有價(jià)值，商場管理人員可以根據(jù)這些關(guān)聯(lián)規(guī)則更好地規(guī)劃商場，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進(jìn)銷售。保單上記錄有投保人的年齡、性別、健康狀況、工作單位、工作地址、工資水平等?？梢钥闯鰜?， A 區(qū)可能污染比較嚴(yán)重，環(huán)境比較差，導(dǎo)致工作在該區(qū)的人健康狀況不好，索賠率也相對比較 高。關(guān)聯(lián)規(guī)則是如下形式的一種蘊(yùn)含 :X→ Y，其中 X?I， Y?I，且 X∩ Y= ?。 如果不考慮關(guān)聯(lián)規(guī)則的支持度和可信度，那么在事務(wù)數(shù)據(jù)庫中存在無窮多的關(guān)聯(lián)規(guī)則。前者即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小支持度，它表示了一組物品集在統(tǒng)計(jì)意義上的需滿足的最低程度 。有了層次關(guān)系后，可以幫助發(fā)現(xiàn)一些更多的有意義的規(guī)則。 另外，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的思路還可以用于序列模式發(fā)現(xiàn)。算法的思想在于：如果說 ABCD 和AB 是大項(xiàng)集，我們就可以通過計(jì)算可信度，也就是 conf = support(ABCD) / support(AB)，并通過 conf ? miniconf 來確定規(guī)則 AB→ CD 是否確立 (該規(guī)則由于ABCD 是大項(xiàng)集故肯定具有最小支持度 )。 Lk1 ? ?。 end Lk = { c ? Ck | ? minsup} end Answer = ∪ k Lk。 附圖 函數(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}}。 3) 序列模式 a.) 序列模式的概念及定義 舉例說明，比如有顧客租借錄像帶，典型的順序是先租“星球大戰(zhàn)”，然后是“帝國反擊戰(zhàn)”，再是“杰達(dá)武士歸來” (這三部影片是以故事發(fā)生的時(shí)間先后而情節(jié)連續(xù)的 )。 b.) 一些相關(guān)概念及定義 前面已經(jīng)討論過，數(shù)據(jù)源是一個(gè)給定的由 客戶交易 (customer transaction)組成的大型數(shù)據(jù)庫，每個(gè) 交易 (transaction)由 客戶號(hào) (customerid)， 交易時(shí)間 (transactiontime)以及在交易中購買的 項(xiàng) (item)組成。 兩個(gè)序列 a a1,a2… an和 b b1,b2… bm，如果存在整數(shù) i1i2… in 且 a1 包含于 bi1， a2 包含于 bi2， … ， an包含于 bin，則稱序列 a包含于序列 b。在一個(gè) 序列集 (a set of sequences)中如果序列 s不包含于任何其他序列中，則稱序列 s 為 最大的 (maximal)。通常，將一個(gè)客戶的交易按交易時(shí)間排序成 T1 ， T2 ，??， Tn。 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) 圖 如果一個(gè)序列 s 包含于一個(gè)客戶序列中，則我們稱該客戶 支持 (support)序列 s。 ? 舉例說明： 我們看圖 _1 表示的數(shù)據(jù)庫 (該數(shù)據(jù)庫已經(jīng)按客戶號(hào)和交易時(shí)間排了序 )?？蛻?4 在項(xiàng) 30 和項(xiàng) 90 之間買了項(xiàng)（ 40,70），但仍然支持模式 (30) (90) ，這是因?yàn)槲覀兯业哪Ｊ讲⒉恍枰欢ㄟB續(xù)。而序列 (30)， (40) ， (70) ， (90) ， (30) (40) ， (30) (70) 以及 (40,70) 雖然具有 最小支持度(minimum support)，但并不是答案，因?yàn)樗鼈儾皇?最大 (maximal)的。具有 k長度的序列稱為 k序列。具有 最小支持 (minimum support)的項(xiàng)集稱為 大項(xiàng)集 (large itemset or litemset)。實(shí)際上這個(gè)階段將原來的事務(wù)數(shù)據(jù)庫 (transaction database)轉(zhuǎn)換成由客戶序列組成的數(shù)據(jù)庫。 大項(xiàng)集被映射成連續(xù)的整數(shù)。 3) 轉(zhuǎn)換階段 (Transformation Phase) 在找序列模式的過程中，我們要不斷地進(jìn)行檢測一個(gè)給定的大序列集合是否包含于一個(gè)客戶序列中。而如果一個(gè)客戶序列不包含任何的大項(xiàng) 集，在轉(zhuǎn)換好的數(shù)據(jù)庫中這個(gè)序列也將不復(fù)存在。圖 的圖 。 5) 選最大階段 (Maximal Phase) 在大序列集中找出最大序列 (maximal sequences)。 k ) do foreach ksequence sk do Delete from S all subsequences of sk 附圖 ? 序列階段的算法討論 序列階段算法的基本結(jié)構(gòu)是對數(shù)據(jù)進(jìn)行多次遍歷。 這里提出兩種算法，分別稱為 countall 和 countsome。接下來是一個(gè) 回溯階段 (backward phase)，我們找出所有剩余的大序列。k++) do 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 13 begin Ck = New candidates generated from Lk1 // 見下附圖 _2. foreach customersequence c in the database do Increment the count of all candidates in Ck that are contained in c. Lk = Candidates in Ck with minimum support. end Answer = Maximal Sequences in ∪ k Lk。在遍歷的最后，候選序列的支持度用來決定大序列 (剔除不足支持度的候選序列 )。 第二步，如果存在 c 的 (k1)子序列不包含于 Lk1 之中，則刪除所有序列c?Ck。 ? 例子 {1 5}{2}{3}{4} {1}{3}{4}{3 5} {1}{2}{3}{4} {1}{3}{5} {4}{5} 圖 考察圖 ，在這里我們沒有給出源數(shù)據(jù)庫的形式。圖 1序列，第二次遍歷，第三次遍歷以及第四次遍歷最后階段所得到的大序列和它們的支持度。 // Result of litemset phase C1 = L1。 k++) do begin if (Lk1 know) then Ck = New candidates generated from Lk1。 k = 1。 next 函數(shù)以上次遍歷的序列長度作為輸入，返回下次遍歷中需要計(jì)數(shù)的序列長度。 elsif (hitk ) return k + 3。一種極端情形是 next(k) = k + 1(k是最后一次計(jì)數(shù)的候選序列的長度 )，這時(shí)所有非最大序列都被計(jì)算，而擴(kuò)展小序列都沒有被計(jì)算。 我們用 apriorigenerate 函數(shù)產(chǎn)生新的候選序列。因?yàn)槲覀冃枰氖亲畲笮蛄?，所以可以在前推階段就刪除所有包含在其他大序列中的序列，那些序列不屬于我們需要找的答案集。在第二次遍歷時(shí)，我們計(jì)算 C2得到 L2(圖 _9.)。下一步apriorigenerate函數(shù)以 C3來產(chǎn)生 C4，在經(jīng)過剪枝 (pruning)后，得到的結(jié)果和圖 列所示的 C4 相同。在前推階段 (forward phase)我們忽略了對 C3中序列的支持度的計(jì)算。同樣的道理， L1中所有的序列都被刪除了。 // 原始數(shù)據(jù)庫的記錄總數(shù) 24. extern int nTransactionNumber。 29. extern CString m_Item。 36. int i,temp。 // 生 成一個(gè) exIIset 對象，對于 Item 表進(jìn)行操作 40. LIset_1 exLIset_1。 // 生成一個(gè) exSTset 對象，對于 SourceTable 表進(jìn)行操作 45. 46. 47. float fSupp = 。 54. 55. while(!()) //對 LarItem_1 表的初始操作 56. { 57. ()。 68. m_Cust = 。 74. m_Item = 。 80. } 81. 82. while(m_Cust == ) 83. { 84. m_Cust = 。 92. } 93. } 94. 95. fSupp = fSupp/float(nCustomerNumber)。 105. return。 112. = fSupp。 116. index++。 122. } 123. 124. ///////////////////////////////////////////////////////////////////// 125. ()。 133. ()。 140. ()。 148. for(i=0。 153. ////////////////////////////////////////////////////////////////////////////// 154. while(!()) 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 21 155. { 156. m_Tran = 。 163. m_Cust = 。 170. } 171. 172. while(m_Tran == ) 173. { 174. m_Cust = 。 180. while(m_Cust == ) 181. { 182. m_Cust = 。 186. } 187. } 188. else 189. { 190. ()。 // 對數(shù)據(jù)庫的添加操作 204. = index。 208. = 1。 212. 213. ()。 218. = 0。 223. step++。 229. step = exch。 235. ()。 在程序 FindLitemSets中，我們對每一個(gè)表生成一個(gè) CRecordSet 對象對其進(jìn)行操 作。但是它并沒有給出一個(gè)通用的算法實(shí)現(xiàn)，故只有一定的實(shí)驗(yàn)意義。 【結(jié) 語】 本文給出了對于數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則和序列模式的初步討論，以及一些基本的概念和算法，并對于找大項(xiàng)集 (Large Item set)的問題進(jìn)行了程序?qū)崿F(xiàn)上的嘗試，取得了一些有用的結(jié)果。他在繁忙的工作之余抽出時(shí)間仔細(xì)審閱，并給了我們很多好的建議。 【參考文獻(xiàn)】 [1] Professor Jiawei Han and Jian Pei, Simon Fraser Sequential Pattern Mining: From Shopping History Analy