【正文】 2) 關(guān)聯(lián)規(guī)則 a.) 關(guān)聯(lián)規(guī)則的概念及定義 考察一些涉及許多物品的事務(wù)：事務(wù) 1 中出現(xiàn)了物品甲，事務(wù) 2 中出現(xiàn)了物品乙，事務(wù) 3 中則同時(shí)出現(xiàn)了物品甲和乙。一條記錄通 常是由 交易 (transaction)數(shù)據(jù)和交易中所買的 項(xiàng) (item)—— 即物品組成。 B. 我們所要討論的問題 如前所述，數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則成為關(guān)聯(lián)模式?！? 6. 序列模式 序列模式與關(guān)聯(lián)模式相仿，而把數(shù)據(jù)之間的關(guān)聯(lián)性與時(shí)間聯(lián)系起來。 3. 時(shí)間序列模式 時(shí)間序列模式根據(jù)數(shù)據(jù)隨時(shí)間變化的趨勢預(yù)測將來的值。當(dāng)有新的動(dòng)物資料時(shí)，就可以根據(jù)這個(gè)模式判別此動(dòng)物是否是哺乳動(dòng)物。 【問題陳述】 A. 數(shù)據(jù)挖掘的任務(wù)及其六種模式 數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。隨后在 1991年、 1993年和 1994 年都舉行 KDD 專題討論會(huì)，匯集來自各個(gè)領(lǐng)域的研究人員和應(yīng)用開發(fā)者，集中討論數(shù)據(jù)統(tǒng)計(jì)、海量數(shù)據(jù)分析算法、知識(shí)表示、知識(shí)運(yùn)用等問題。缺乏挖掘數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 3 數(shù)據(jù)背后隱藏的知識(shí)的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識(shí)貧乏”的現(xiàn)象。數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 1 主題：數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則 (Association Rules)和序列模式 (Sequential Patterns) 指導(dǎo)老師：朱揚(yáng)勇 復(fù)旦大學(xué)計(jì)算機(jī)系 97 級(jí)軟件 楊 靖 9724016 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 2 數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則 (Association Rules)和序列模式 (Sequential Patterns) 【 Abstract】 Database mining is motivated by the decision support problem faced by most large retail anizations. Progress in barcode technology has made it possible for retail anizations to collect and store massive amounts of sales data, referred to as the basket data. We can get some information useful for sale or produce procedure through mining in the data while these information usually reflected by a certain pattern. We discussed two patterns in this theme: association rules and sequential patterns. Also we presented a program for resolving the problem “ to find large item set”, and pared some algorithms about these subjects. 【摘 要】 數(shù)據(jù)挖掘由一些大型零售機(jī)構(gòu)所面臨的“ 決策 支持”問題 (decision support problem)所激發(fā)。 計(jì)算機(jī)技術(shù)的另一領(lǐng)域 —— 人工智能自 1956 年誕生之后取得了重大進(jìn)展。隨著參與人員的不斷增多， KDD 國際會(huì)議發(fā)展成為年會(huì)。模式是一個(gè)用語言 L 來表示的一個(gè)表達(dá)式 E，它可用來描述數(shù)據(jù)集 F 中數(shù)據(jù)的特性， E 所描述的數(shù)據(jù)是集合 F 的一個(gè)子集 FE。 描述型模式 是對(duì)數(shù)據(jù)中存在的規(guī)則做一種描述，或者 根據(jù)數(shù)據(jù)的相似性把數(shù)據(jù)分組。這里要考慮到時(shí)間的特殊性質(zhì)，像一些周期性的時(shí)間定義如星期、月、季節(jié)、年等，不同的日子如節(jié)假日可能造成的影響，日期本身的計(jì)算方法，還有一些需要特殊考慮的地方如時(shí)間前后的相關(guān)性 (過去的事情對(duì)將來有多大的影響力 )等。為了發(fā)現(xiàn)序列模式，不僅需要知道事件是否發(fā)生，而且需要確定事件發(fā)生的時(shí)間。我們所要討論的問題集中在 數(shù)據(jù)挖掘中的 關(guān)聯(lián)規(guī)則 (Mining Association Rules)和 序列模式 (Mining Sequential Patterns)上， 也就是上述六個(gè)模式中的第五和第六個(gè)。更通常的是，數(shù)據(jù)記錄也包含了 客戶號(hào) (customerid)，特別當(dāng)買主是持有信用卡或商店優(yōu)惠卡的顧客時(shí)。那么，物品甲和乙在事務(wù)中的出現(xiàn)相互之間是否有規(guī)律可循呢？在數(shù)據(jù)庫的數(shù)據(jù)挖掘中， 關(guān)聯(lián)規(guī)則 就是描述這種在一個(gè)事務(wù)中物品之間同時(shí)出現(xiàn)的規(guī)律的知識(shí)模式。保險(xiǎn)公司在接受保 險(xiǎn)前，往往需要記錄投保人詳盡的信息，有時(shí)還要到醫(yī)院做身體檢查。稱事務(wù) T 支持物品集 X，如果 X?T。因此，為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，需要給定兩個(gè)閾值 :最小支持度和最小可信度。但如果考慮到較高層次的物品 (如外套 )，則其支持度就較高，從而可能發(fā) 現(xiàn)有用的規(guī)則。 for ( k = 2。 forall itemsets c?Ck do forall (k1)subsets s of c do if ( s ? Lk1 ) then delete c from Ck。所謂項(xiàng)集，指的是多個(gè)物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作是由兩個(gè) 項(xiàng) (item)組成的項(xiàng)集，它也可以作為某一個(gè)序列模式的元素。前者表示項(xiàng) 3 和項(xiàng) 5是先后購買的，而后者則表示項(xiàng) 3 和項(xiàng) 5 是同時(shí)購買的，這就是區(qū)別所在。見圖 _2。序列模式 (30) (90) 被客戶 1 和客戶 4 所支持 (support)。分別是 ⅰ ）排序階段， ⅱ ）大項(xiàng)集階段 ⅲ ）轉(zhuǎn)換階段， ⅳ ）序列階段，以及 ⅴ ）選最大階段 ? 涉及的術(shù)語 一個(gè)序列的 長度 (length)是它所包含的 項(xiàng)集 (itemset)的總數(shù)。 ? 步驟 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 11 1) 排序階段 (Sort Phase) 數(shù)據(jù)庫（ D）以客戶號(hào) (customerid)為主鍵 (major key)，交易時(shí)間 (transactiontime)為次鍵 (minor key)進(jìn)行排序。 Large Itemsets Mapped To (30) (40) (70) (40,70) (90) 1 2 3 4 5 圖 這樣映射的好處在于，將大項(xiàng)集按一個(gè)實(shí)體 (entity)的形式進(jìn)行處理，可以帶來比較和處理上的方便和高效，提供了一個(gè)統(tǒng)一的格式。 這樣的一個(gè)轉(zhuǎn)換好的數(shù)據(jù)庫被稱為 D?。 k 1 。 countsome 算法有一個(gè) 前推階段 (forward phase)，這個(gè)階段中我們找出具有一定長度的所有的大序列。在每一次遍歷 (pass)中，我們利用上一次遍歷產(chǎn)生的大序列來產(chǎn)生候選序列，并在一次遍歷中計(jì)算它們的支持度 (support)。比如，序列 1 2 4 3 由于它有一個(gè)子序列 2 4 3 不在 L3 中，所以被剔除了。 // Forward Phase — 前推階段 L1 = {large 1sequences}。 end end // Backward Phase — 回溯階段 for (k 。 elsif (hitk ) return k + 2。 hitk 被定義為大 k序列 (large ksequence)和候選 k序列 (candidate ksequence)的比率（ ratio），即 |Lk| / |Ck|。為了舉例方便，取 f(k) = 2k。 L4中的序列不被刪除，因?yàn)闆]有更長的序列了 (也就是說它不會(huì)再是別的序列的子序列了 )。 // 最小支持度，由用戶輸入 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 18 23. extern int nRecordNumber。 // 記錄向前移動(dòng)步數(shù) 35. int exch = 1。 43. 44. STset exSTset。 64. 65. while(!()) 66. { 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 19 67. m_Tran = 。 77. if(()) 78. { 79. break。 104. ()。 115. ()。 128. 129. // 以下找 L(2),即有兩個(gè)項(xiàng)的大項(xiàng)集 130. //////////////////////////////////////////////////////////////////////// 131. 132. ()。 147. ()。 159. 160. if(m_Itemid == ) 161. { 162. m_Tran = 。 177. if(m_Itemidv==m_Item) 178. { 179. fSupp = fSupp + 。 201. if(fSupp = fMiniSupport) 202. { 203. ()。 211. index++。 222. ()。 234. ()。 B. 應(yīng)用 該程序可以找出大項(xiàng)集 L(1)和 L(2)，以備在序列模式階段使用。 【感 謝】 在此我要真誠地感謝我的指導(dǎo)老師朱揚(yáng)勇教授，在他的指導(dǎo)和幫助下，這篇文章得以完成。他嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度使他成為我們年輕人學(xué)習(xí)的榜樣。在這個(gè)程序中數(shù) 據(jù)結(jié)構(gòu)的定義是比較簡單的，程序的流程也比較清晰和單一。 236. } 237. FindLitemsets::~FindLitemsets() // 析構(gòu)函數(shù) 238. { 239. 240. } 數(shù)據(jù)源采用了 MS access產(chǎn)生的 .mdb 文件，見 。 224. fSupp = 。 214. = 0。 205. = m_Itemid。 183. m_Tran = 。 164. m_Item = 。istep。 134. ()。 117. } 118. 119. ()。 106. } 107. if(fSupp = fMiniSupport) 108. { 109. ()。 85. m_Item = 。 69. m_Item = 。 // 用于存放支持度的臨時(shí)變量 48. 49. // 以 下找 L(1),即只有一個(gè)項(xiàng)的所有大項(xiàng)組成的大項(xiàng) 50. //////////////////////////////////////////////////////////////////////// 51. ()。 // 臨時(shí)變量 37. CString m_Itemid。 // 總的交易數(shù) 25. extern int nCustomerNumber。刪除 C3中那些是 L4(1 2 3 4)的子序列的序列之后，我們得到剩下的兩個(gè)序列 1 3 5和 3 4 5。第三次遍歷后， apriorigenerate