【正文】 Original Customer Sequence Transformed Customer Sequence After Mapping 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 12 1 2 3 4 5 (30)(90) (10,20)(30)(40,60,70) (30,50,70) (30)(40,70)(90) (90) {(30)}{(90)} {(30)}{(40),(70),(40,70)} {(30),(70)} {(30)}{(40),(70),(40,70)}{(90)} {(90)} {1}{5} {1}{2,3,4} {1,3} {1}{2,3,4}{5} {5} 圖 4) 序列階段 (Sequence Phase) 利用已知的大項(xiàng)集的集合來找到所需的序列。在遍歷數(shù)據(jù)的過程中，我們計(jì)算出這些候選序列的支持度 (support)，這樣在一次遍歷的最后，我們就可以決定哪些候選序列是真正的大序列，這些序列構(gòu)成下一次遍歷的種子集。 // 大項(xiàng)集階段得到的結(jié)果 for(k = 2。 ? Apriori Candidate Generation(候選的產(chǎn)生 ) 函數(shù) apriorigenerate 以 Lk1，所 有大 (k1)序列的集合為 輸入?yún)?shù)。最小支持度定義為 40%(也就是至少兩個(gè)客戶序列 )。 // we last counted Clast for(k = 2。 foreach customersequence c in DT do Increment the count of all candidates in Ck that are contained in c. Lk = Candidates in Ck with minimum support. end else // Lk already known Delete all sequences in Lk contained in Some Li, i k. Answer = ∪ k Lk 圖 算法 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 16 在前推階段 (forward phase)中，我們只對(duì)特定長度的序列進(jìn)行計(jì)數(shù)。 else return k + 5。這種情形下，我們利用 k1 候選集 Ck1 來產(chǎn)生 Ck。圖 C3中的候選序列。這兩個(gè)序列分別計(jì)算后得到 1 3 5是一個(gè)最大 3序列。 // 總的顧客數(shù) 26. // 一些臨時(shí)標(biāo)志變量 27. extern CString m_Tran。 38. CString m_Itemidv。 52. ()。 70. if(m_Itemid == ) 71. { 72. m_Tran = 。 86. ()。 // 向數(shù)據(jù)庫添加記錄 110. = index。 120. ()。 135. ()。i++) 149. { 150. ()。 165. 166. ()。 184. m_Item = 。 206. = m_Itemidv。 215. ()。 225. if(()) 226. { 227. ()。其中的 Item 表存儲(chǔ)所有數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 23 的項(xiàng)，并以整數(shù)對(duì)其進(jìn)行了編號(hào)； SourceTable 表存儲(chǔ)了以客戶號(hào) (customerid)以及交易時(shí)間(transactiontime)排好序的數(shù)據(jù)庫； LarItem_1 存儲(chǔ)大項(xiàng)集 L(1)； LarItem_2 存儲(chǔ)大項(xiàng)集 L(2)。作為數(shù)據(jù)挖掘中的一個(gè)模塊，關(guān)聯(lián)規(guī)則的算法在序列模式中也有著重要的作用，極為相似。同時(shí)，在此我也要感謝朱建秋，張曉輝和蔡偉杰三位師兄，在他們的關(guān)心和熱情幫助之下，我得到了多方面的學(xué)習(xí)能力以及專業(yè)知識(shí)的提高。在對(duì)大量的已 知信息進(jìn)行知識(shí)發(fā)現(xiàn)和整理的過程中，我們可以提供一定程度的決策支持，在生產(chǎn)，銷售，保險(xiǎn)，事故分析等等領(lǐng)域發(fā)揮巨大的經(jīng)濟(jì)和社會(huì)效益。 遍歷的最后，我們通過對(duì)所得到的支持度和用戶輸入的最小支持度的比較確定該項(xiàng)集是否是大項(xiàng)集，如果是則將它寫入特定的表中，以備以后使用。 233. ()。 220. } 221. ()。 210. ()。 197. } 198. } 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 22 199. ////////////////////////////////////////////////////////////////////////////// 200. fSupp = fSupp/float(nCustomerNumber)。 176. m_Item = 。 158. m_Item = 。 144. while(steptemp) 145. { 146. m_Itemid = 。 127. ()。 114. ()。 100. } 101. if(!()) 102. { 103. coutCan not append.。 76. ()。 59. } 60. 61. while(!()) 62. { 63. m_Itemid = 。 // 輔助對(duì)象 42. LIset_2 exLIset_2。 // 大項(xiàng)集的索引號(hào) index 34. int step = 1。 15. define new DEBUG_NEW 16. endif 17. 18. ////////////////////////////////////////////////////////////////////// 19. // 找大項(xiàng)集 20. ////////////////////////////////////////////////////////////////////// 21. // 引用外部變量 22. extern float fMiniSupport。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 17 1 2 3 1 2 4 1 3 4 1 3 5 2 3 4 3 4 5 圖 接下來我們進(jìn)行回溯階段 (backward phase)。 ? 例子 仍然采用 AprioriAll 算法用過的數(shù)據(jù)庫例子，在大項(xiàng)集階段 (對(duì)數(shù)據(jù)庫的第一次遍歷中 )我們找出 (L1)如圖 。另一種極端的情形比如 next (k) = 100*k，這時(shí)幾乎沒有非最大序列被計(jì)算，但有許多擴(kuò)展小序列被計(jì)算。 function next ( k: integer) begin if (hitk ) return k + 1。 if (k = = next (last) ) then begin 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. last = k。 ? AprioriSome 算法 圖 。當(dāng)它最為輸入?yún)?shù)進(jìn)入到 apriorigenerate 函數(shù)，在聯(lián)合結(jié)束后，我們得到了第二列所示的結(jié)果，數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 14 進(jìn)一步剔除那些子序列不在 L3 中的序列，第三列顯示的序列將被保留。 圖 。給出一個(gè) countall 算法，稱為 AprioriAll，給出一個(gè) countsome 算法，稱為 AprioriSome。定義最長序列的長度為 n，則： for ( k = n ?，F(xiàn)在，一個(gè)客戶序列被一列由大項(xiàng)集組成的集合所取代，每個(gè)大項(xiàng)集的集合表示為 {l 1,l 2,… ,l n}， l i表示一個(gè)大項(xiàng)集。圖 。由此，任何大序列都是大項(xiàng)集的列表所組成。 Sequential Pattern with support 25% (30) (90) (30) (40,70) 圖 c.) 實(shí)現(xiàn)算法的討論 我們分五 個(gè)具體階段來找出所有的序列模式。 對(duì)于最小支持為 25%的情況，也就是最小支持 2 個(gè)客戶 (因?yàn)橐还灿?5 個(gè)客戶 )，有兩個(gè)序列： (30) (90) 和 (30) (40,70) 在那些滿足 支持度約束 (the support constraint)的序列中是 最大 (maximal)的，也是我們所需的 序列模式 。這樣，這個(gè)客戶的客戶序列就成了這樣的一個(gè)序列： 〈 itemset(T1) itemset(T2) … itemset(Tn)〉 。但是序列 (3) (5) 不包含于 (3,5) ，反之亦然。在任意兩部之間隨便插租了什么電影，仍然還是滿足了這個(gè) 序列模式 ，并且擴(kuò)展一下，序列模式的元素也可 以不只是一個(gè)元素(如一部電影 )，它也可以是一個(gè) 項(xiàng)集 (item set)。 第二步，剪枝 (pruning)，如果存在 c 的 (k1)子序列不包含于 Lk1之中，則刪除所有項(xiàng)集 c?Ck。 L1 = {large 1itemsets}。由于商店或超市中有成千上萬種物品，平均來講，每種物品 (如滑雪衫 )的支持度很低，因此有時(shí)難以發(fā)現(xiàn)有用規(guī)則 。在文獻(xiàn)中，一般稱滿足一定要求的 (如較大的支持度和可信度 )的規(guī)則為強(qiáng)規(guī)則。 D中的每個(gè)事務(wù) T 是一組物品，顯然滿足 T?I。比如人壽保險(xiǎn)，一份保單就是一個(gè)事務(wù)。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 6 客戶號(hào) (Cust_id) 交易時(shí)間 (Tran_time) 物品 (Item) 1 1 June 25’99 June 30’99 30 90 2 2 2 June 10’99 June 15’99 June 20’99 10,20 30 40,60,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)及交易時(shí)間 (Tran_time) 排序的源數(shù)據(jù)庫 圖