【正文】 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 10 列 就代表了一個(gè) 序列模式 (sequential pattern)。序列模式 (30) (90) 被客戶 1 和客戶 4 所支持 (support)。 序列 (10,20) (30) 是一個(gè)不具備最小支持的 例子，它只被客戶 2所支持。分別是 ⅰ ）排序階段， ⅱ ）大項(xiàng)集階段 ⅲ ）轉(zhuǎn)換階段， ⅳ ）序列階段，以及 ⅴ ）選最大階段 ? 涉及的術(shù)語(yǔ) 一個(gè)序列的 長(zhǎng)度 (length)是它所包含的 項(xiàng)集 (itemset)的總數(shù)。于是項(xiàng)集 i 和 1序列 i具有相同的 支持 。 ? 步驟 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 11 1) 排序階段 (Sort Phase) 數(shù)據(jù)庫(kù)（ D）以客戶號(hào) (customerid)為主鍵 (major key)，交易時(shí)間 (transactiontime)為次鍵 (minor key)進(jìn)行排序。因?yàn)檫@個(gè)集合就是 {l | l ?L}。 Large Itemsets Mapped To (30) (40) (70) (40,70) (90) 1 2 3 4 5 圖 這樣映射的好處在于，將大項(xiàng)集按一個(gè)實(shí)體 (entity)的形式進(jìn)行處理，可以帶來(lái)比較和處理上的方便和高效，提供了一個(gè)統(tǒng)一的格式。如果一條交易不包含任何大項(xiàng)集，在轉(zhuǎn)換完成的序列中它將不被保留。 這樣的一個(gè)轉(zhuǎn)換好的數(shù)據(jù)庫(kù)被稱為 D?。在下一部分我們將討論這個(gè)階段的算法。 k 1 。在第一次遍歷前，所有在大項(xiàng)集階段得到的具有最小支持度 (minimum support)的大 1序列 (large 1sequence)組成了種子集。 countsome 算法有一個(gè) 前推階段 (forward phase)，這個(gè)階段中我們找出具有一定長(zhǎng)度的所有的大序列。Lk1 ? ?。在每一次遍歷 (pass)中，我們利用上一次遍歷產(chǎn)生的大序列來(lái)產(chǎn)生候選序列，并在一次遍歷中計(jì)算它們的支持度 (support)。該函數(shù)實(shí)現(xiàn)步驟如下： 第一步，聯(lián)合 insert into Ck select ,… , from Lk1p,Lk1q where = ,… , = 。比如，序列 1 2 4 3 由于它有一個(gè)子序列 2 4 3 不在 L3 中，所以被剔除了。對(duì)于數(shù)據(jù)的第一次遍歷是在大項(xiàng)集階段進(jìn)行的。 // Forward Phase — 前推階段 L1 = {large 1sequences}。 Ck1 ? ? and Llast ? ?。 end end // Backward Phase — 回溯階段 for (k 。比如，前推階段我們對(duì)長(zhǎng)度為 1， 2， 4，和 6 的序列計(jì)數(shù) (計(jì)算支持度 )，而長(zhǎng)度為 3 和 5 的序列則在回溯階段中計(jì)數(shù)。 elsif (hitk ) return k + 2。 end 附圖 函數(shù) 這個(gè)函數(shù)的功能是確定對(duì)哪些序列進(jìn)行計(jì)數(shù)，在對(duì)非最大序列 (nonmaximal sequence)計(jì)數(shù)時(shí)間的浪費(fèi)和計(jì)算擴(kuò)展小候選序列 (extensions of small candidate sequences)之間作出權(quán)衡。 hitk 被定義為大 k序列 (large ksequence)和候選 k序列 (candidate ksequence)的比率（ ratio），即 |Lk| / |Ck|。 在回溯階段 (backward phase)，我們對(duì)那些在前推階段 (forward phase)忽略的長(zhǎng)度的序列進(jìn)行計(jì)算。為了舉例方便，取 f(k) = 2k。我們不計(jì)算 C3，因此也不產(chǎn)生 L3。 L4中的序列不被刪除，因?yàn)闆](méi)有更長(zhǎng)的序列了 (也就是說(shuō)它不會(huì)再是別的序列的子序列了 )。下一步，除了 4 5以外 L2 中所有序列都被刪除，因?yàn)樗鼈兌及谀骋粋€(gè)更長(zhǎng)的序列中。 // 最小支持度，由用戶輸入 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 18 23. extern int nRecordNumber。 // 用以保存 SourceTable 中的三個(gè)記錄字段 28. extern CString m_Cust。 // 記錄向前移動(dòng)步數(shù) 35. int exch = 1。 39. IIset exIIset。 43. 44. STset exSTset。 53. ()。 64. 65. while(!()) 66. { 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 19 67. m_Tran = 。 73. m_Cust = 。 77. if(()) 78. { 79. break。 87. } 88. } 89. else 90. { 91. ()。 104. ()。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 20 111. = m_Itemid。 115. ()。 121. fSupp = 。 128. 129. // 以下找 L(2),即有兩個(gè)項(xiàng)的大項(xiàng)集 130. //////////////////////////////////////////////////////////////////////// 131. 132. ()。 136. 137. while(!()) //對(duì) LarItem_2 表的初始操作 138. { 139. ()。 147. ()。 151. } 152. m_Itemidv = 。 159. 160. if(m_Itemid == ) 161. { 162. m_Tran = 。 167. if(()) 168. { 169. break。 177. if(m_Itemidv==m_Item) 178. { 179. fSupp = fSupp + 。 185. ()。 201. if(fSupp = fMiniSupport) 202. { 203. ()。 207. = fSupp。 211. index++。 216. 217. ()。 222. ()。 228. exch++。 234. ()。程 序 與數(shù)據(jù)源之間的連接以調(diào)用 ODBC 實(shí)現(xiàn)。 B. 應(yīng)用 該程序可以找出大項(xiàng)集 L(1)和 L(2)，以備在序列模式階段使用。本設(shè)計(jì)是一個(gè)國(guó)家 863 項(xiàng)目的一部分內(nèi)容，對(duì)這些方面的問(wèn)題進(jìn)行了初步的探討。 【感 謝】 在此我要真誠(chéng)地感謝我的指導(dǎo)老師朱揚(yáng)勇教授，在他的指導(dǎo)和幫助下，這篇文章得以完成。謝謝你們。他嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度使他成為我們年輕人學(xué)習(xí)的榜樣。 數(shù)據(jù)挖掘是一個(gè)嶄新的計(jì)算機(jī)應(yīng)用領(lǐng)域，它將極大地促進(jìn)信息對(duì)于人類社會(huì)進(jìn)步所起的作用。在這個(gè)程序中數(shù) 據(jù)結(jié)構(gòu)的定義是比較簡(jiǎn)單的，程序的流程也比較清晰和單一。第一次遍歷從 Item 表中取出每一項(xiàng)與 SourceTable 表中的項(xiàng)進(jìn)行比較，對(duì)同一個(gè)客戶的同一次交易，如果該交易包含了此項(xiàng)集 (第一次只是一個(gè)項(xiàng) )，那么對(duì)此項(xiàng)集的支持度加 1，跳過(guò)所有該客戶的交易，繼續(xù)對(duì)下一個(gè)客戶進(jìn)行比較和匹配。 236. } 237. FindLitemsets::~FindLitemsets() // 析構(gòu)函數(shù) 238. { 239. 240. } 數(shù)據(jù)源采用了 MS access產(chǎn)生的 .mdb 文件，見(jiàn) 。 230. } 231. } 232. ()。 224. fSupp = 。 219. ()。 214. = 0。 209. ()。 205. = m_Itemid。 191. } 192. } 193. } 194. else 195. { 196. ()。 183. m_Tran = 。 175. m_Tran = 。 164. m_Item = 。 157. m_Cust = 。istep。 141. } 142. 143. temp = index 1。 134. ()。 126. ()。 117. } 118. 119. ()。 113. = 1。 106. } 107. if(fSupp = fMiniSupport) 108. { 109. ()。 96. 97. if(()) 98. { 99. coutexLIset_1 is opened.。 85. m_Item = 。 75. fSupp = fSupp + 。 69. m_Item = 。 58. ()。 // 用于存放支持度的臨時(shí)變量 48. 49. // 以 下找 L(1),即只有一個(gè)項(xiàng)的所有大項(xiàng)組成的大項(xiàng) 50. //////////////////////////////////////////////////////////////////////// 51. ()。 41. LIset_1 exLIset_1v。 // 臨時(shí)變量 37. CString m_Itemid。 30. 31. FindLitemsets::FindLitemsets() 32. { 33. int index = 1。 // 總的交易數(shù) 25. extern int nCustomerNumber。 【實(shí)踐部分 】 A. 程序說(shuō)明 程序 找出大項(xiàng)集，代碼段如下： 1. include // 包含一些預(yù)定義的頭文件 2. include 3. include 4. include 5. include 6. include 7. include 8. include 9. include 10. include 11. 12. ifdef _DEBUG 13. undef THIS_FILE 14. static char THIS_FILE[]=__FILE__。刪除 C3中那些是 L4(1 2 3 4)的子序列的序列之后，我們得到剩下的兩個(gè)序列 1 3 5和 3 4 5。在以 C4計(jì)算 L4(圖 )之