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