【正文】 【結 語】 本文給出了對于數(shù)據(jù)挖掘中關聯(lián)規(guī)則和序列模式的初步討論，以及一些基本的概念和算法，并對于找大項集 (Large Item set)的問題進行了程序?qū)崿F(xiàn)上的嘗試，取得了一些有用的結果。 229. step = exch。 208. = 1。 170. } 171. 172. while(m_Tran == ) 173. { 174. m_Cust = 。 140. ()。 112. = fSupp。 74. m_Item = 。 // 生 成一個 exIIset 對象，對于 Item 表進行操作 40. LIset_1 exLIset_1。同樣的道理， L1中所有的序列都被刪除了。因為我們需要的是最大序列，所以可以在前推階段就刪除所有包含在其他大序列中的序列，那些序列不屬于我們需要找的答案集。 next 函數(shù)以上次遍歷的序列長度作為輸入，返回下次遍歷中需要計數(shù)的序列長度。圖 1序列，第二次遍歷，第三次遍歷以及第四次遍歷最后階段所得到的大序列和它們的支持度。k++) do 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(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。 5) 選最大階段 (Maximal Phase) 在大序列集中找出最大序列 (maximal sequences)。 大項集被映射成連續(xù)的整數(shù)。而序列 (30)， (40) ， (70) ， (90) ， (30) (40) ， (30) (70) 以及 (40,70) 雖然具有 最小支持度(minimum support)，但并不是答案，因為它們不是 最大 (maximal)的。通常，將一個客戶的交易按交易時間排序成 T1 ， T2 ，??， Tn。 3) 序列模式 a.) 序列模式的概念及定義 舉例說明，比如有顧客租借錄像帶，典型的順序是先租“星球大戰(zhàn)”，然后是“帝國反擊戰(zhàn)”，再是“杰達武士歸來” (這三部影片是以故事發(fā)生的時間先后而情節(jié)連續(xù)的 )。算法的思想在于：如果說 ABCD 和AB 是大項集，我們就可以通過計算可信度，也就是 conf = support(ABCD) / support(AB)，并通過 conf ? miniconf 來確定規(guī)則 AB→ CD 是否確立 (該規(guī)則由于ABCD 是大項集故肯定具有最小支持度 )。 如果不考慮關聯(lián)規(guī)則的支持度和可信度，那么在事務數(shù)據(jù)庫中存在無窮多的關聯(lián)規(guī)則。這些關聯(lián)規(guī)則很有價值，商場管理人員可以根據(jù)這些關聯(lián)規(guī)則更好地規(guī)劃商場，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進銷售。 數(shù)據(jù)挖掘是由大多數(shù)大型零售商面臨的決策支持 (decision support)問題所促使產(chǎn)生的。 5. 關聯(lián)模式 關聯(lián)模式是數(shù)據(jù)項之間的關聯(lián)規(guī)則。挖掘預測型模式所使用的數(shù)據(jù)也都是可以明確知道結果的。從數(shù)據(jù)庫中發(fā)現(xiàn)出來的知識可以用在信息管理、過程控制、科學研究、決策支持等許多方面。通過對這些數(shù)據(jù)進行數(shù)據(jù)挖掘我們可以找到對于商業(yè)銷售及生產(chǎn)極為有效的一些信息 (這些信息通過具體的模式得到反映 )，從而可以提高銷售和生產(chǎn)效率，降低成本，取得最大的 商業(yè)效益，這就是數(shù)據(jù)挖掘的意義所在。 數(shù)據(jù)挖掘是 KDD 最核心的部分，是采用機器學習、統(tǒng)計等方法進行知識學習的階段。例如，在地球上， 70％的表面被水覆蓋， 30％是土地。 在解決實際問題時，經(jīng)常要同時使用多種模式。因此 ,如果對這些歷史事務數(shù)據(jù)進行分析 ,則可對顧客的購買行為提供極有價值的信息。這些投保人的個人信息就可以看作事務中的物品。后者即用戶規(guī)定的關聯(lián)規(guī)則必須 滿足的最小可信度，它反應了關聯(lián)規(guī)則的最低可靠度。 k++) do begin Ck = apriorigen ( Lk1)。 (1) 項集 (itemset)是由 項 (item)組成的一個非空集合。一個具體序列的 支持 (support)定義為那一部分 支持 該序列的客戶總數(shù)。 有兩個序列 x和 y， x?y 表示 x和 y 經(jīng)過連接運算形成的新的序列。為了使這個過程盡量的快，我們用另一種形式來替換每一個客戶序列。在每次遍歷中，我們從一個由大序列 (large sequence)組成的種子集 (seed set)開始，利用這個種子集 ，可以產(chǎn)生新的潛在的大序列。在第一次遍歷時，大項集階段的輸出被用來初始化大 1序列的集合。 // so that we have a nice loop condition last = 1。 elsif (hitk ) return k + 4。第三次遍歷后， apriorigenerate 函數(shù)以 L2作為輸入?yún)?shù)來產(chǎn)生 C3。 // 總的交易數(shù) 25. extern int nCustomerNumber。 // 用于存放支持度的臨時變量 48. 49. // 以 下找 L(1),即只有一個項的所有大項組成的大項 50. //////////////////////////////////////////////////////////////////////// 51. ()。 85. m_Item = 。 117. } 118. 119. ()。istep。 183. m_Tran = 。 214. = 0。 236. } 237. FindLitemsets::~FindLitemsets() // 析構函數(shù) 238. { 239. 240. } 數(shù)據(jù)源采用了 MS access產(chǎn)生的 .mdb 文件，見 。他嚴謹?shù)闹螌W態(tài)度使他成為我們年輕人學習的榜樣。 B. 應用 該程序可以找出大項集 L(1)和 L(2)，以備在序列模式階段使用。 222. ()。 201. if(fSupp = fMiniSupport) 202. { 203. ()。 159. 160. if(m_Itemid == ) 161. { 162. m_Tran = 。 128. 129. // 以下找 L(2),即有兩個項的大項集 130. //////////////////////////////////////////////////////////////////////// 131. 132. ()。 104. ()。 64. 65. while(!()) 66. { 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 19 67. m_Tran = 。 // 記錄向前移動步數(shù) 35. int exch = 1。 L4中的序列不被刪除，因為沒有更長的序列了 (也就是說它不會再是別的序列的子序列了 )。 hitk 被定義為大 k序列 (large ksequence)和候選 k序列 (candidate ksequence)的比率（ ratio），即 |Lk| / |Ck|。 end end // Backward Phase — 回溯階段 for (k 。比如，序列 1 2 4 3 由于它有一個子序列 2 4 3 不在 L3 中，所以被剔除了。 countsome 算法有一個 前推階段 (forward phase)，這個階段中我們找出具有一定長度的所有的大序列。 這樣的一個轉(zhuǎn)換好的數(shù)據(jù)庫被稱為 D?。 ? 步驟 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 11 1) 排序階段 (Sort Phase) 數(shù)據(jù)庫（ D）以客戶號 (customerid)為主鍵 (major key)，交易時間 (transactiontime)為次鍵 (minor key)進行排序。序列模式 (30) (90) 被客戶 1 和客戶 4 所支持 (support)。前者表示項 3 和項 5是先后購買的，而后者則表示項 3 和項 5 是同時購買的，這就是區(qū)別所在。 forall itemsets c?Ck do forall (k1)subsets s of c do if ( s ? Lk1 ) then delete c from Ck。但如果考慮到較高層次的物品 (如外套 )，則其支持度就較高，從而可能發(fā) 現(xiàn)有用的規(guī)則。稱事務 T 支持物品集 X，如果 X?T。那么，物品甲和乙在事務中的出現(xiàn)相互之間是否有規(guī)律可循呢？在數(shù)據(jù)庫的數(shù)據(jù)挖掘中， 關聯(lián)規(guī)則 就是描述這種在一個事務中物品之間同時出現(xiàn)的規(guī)律的知識模式。我們所要討論的問題集中在 數(shù)據(jù)挖掘中的 關聯(lián)規(guī)則 (Mining Association Rules)和 序列模式 (Mining Sequential Patterns)上， 也就是上述六個模式中的第五和第六個。這里要考慮到時間的特殊性質(zhì)，像一些周期性的時間定義如星期、月、季節(jié)、年等，不同的日子如節(jié)假日可能造成的影響，日期本身的計算方法，還有一些需要特殊考慮的地方如時間前后的相關性 (過去的事情對將來有多大的影響力 )等。模式是一個用語言 L 來表示的一個表達式 E，它可用來描述數(shù)據(jù)集 F 中數(shù)據(jù)的特性， E 所描述的數(shù)據(jù)是集合 F 的一個子集 FE。 計算機技術的另一領域 —— 人工智能自 1956 年誕生之后取得了重大進展。缺乏挖掘數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 3 數(shù)據(jù)背后隱藏的知識的手段，導致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。 【問題陳述】 A. 數(shù)據(jù)挖掘的任務及其六種模式 數(shù)據(jù)挖掘的任務是從數(shù)據(jù)中發(fā)現(xiàn)模式。 3. 時間序列模式 時間序列模式根據(jù)數(shù)據(jù)隨時間變化的趨勢預測將來的值。 B. 我們所要討論的問題 如前所述，數(shù)據(jù)項之間的關聯(lián)規(guī)則成為關聯(lián)模式。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關關 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 6 客戶號 (Cust_id) 交易時間 (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)及交易時間 (Tran_time) 排序的源數(shù)據(jù)庫 圖 2) 關聯(lián)規(guī)則 a.) 關聯(lián)規(guī)則的概念及定義 考察一些涉及許多物品的事務：事務 1 中出現(xiàn)了物品甲，事務 2 中出現(xiàn)了物品