【正文】 forall transactions t ? D do begin Ct = subset ( Ck, t )。 L1 = {large 1itemsets}。 c.) 有關(guān)算法的討論 (1) 找出所有具有超出最小支持度的支持度的項集 (itemsets)，由 Apriori 算法實現(xiàn)。由于商店或超市中有成千上萬種物品，平均來講，每種物品 (如滑雪衫 )的支持度很低，因此有時難以發(fā)現(xiàn)有用規(guī)則 。 在實際情況下，一種更有用的關(guān)聯(lián)規(guī)則是泛化關(guān)聯(lián)規(guī)則。在文獻中，一般稱滿足一定要求的 (如較大的支持度和可信度 )的規(guī)則為強規(guī)則。 (2) 稱關(guān)聯(lián)規(guī)則 X→ Y 在事務(wù)數(shù)據(jù)庫 D 中具有大小為 s的支持度，如果物品集 X∪ Y 的支持度為 s。 D中的每個事務(wù) T 是一組物品，顯然滿足 T?I。通過分析這些數(shù)據(jù)，可以得到類似以下這樣的關(guān)聯(lián)規(guī)則：年齡在 40 歲以上，工作在 A 區(qū)的投保人當(dāng)中，有 45 ％的人曾經(jīng)向保險公司索賠過。比如人壽保險，一份保單就是一個事務(wù)。例如超級市場利用前端收 款機收集存儲了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購買事務(wù)記錄，每條記錄存儲了事務(wù)處理時間，顧客購買的物品、物品的數(shù)量及金額等。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(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) 關(guān)聯(lián)規(guī)則 a.) 關(guān)聯(lián)規(guī)則的概念及定義 考察一些涉及許多物品的事務(wù)：事務(wù) 1 中出現(xiàn)了物品甲，事務(wù) 2 中出現(xiàn)了物品乙，事務(wù) 3 中則同時出現(xiàn)了物品甲和乙。例如 ,可以幫助如何擺放貨架上的商品 (如把顧客經(jīng)常同時買的商品放在一起 ),幫助如何規(guī)劃市場 (怎樣相互搭配進貨 )。一條記錄通 常是由 交易 (transaction)數(shù)據(jù)和交易中所買的 項 (item)—— 即物品組成。 C. 具體任務(wù)及其應(yīng)用 挖掘的序列模式，也就是從序列組成的數(shù)據(jù)庫 (sequence database)中找出出現(xiàn)頻繁的子序列 (subsequences)，它是一項重要的數(shù)據(jù)挖掘任務(wù)。 B. 我們所要討論的問題 如前所述，數(shù)據(jù)項之間的關(guān)聯(lián)規(guī)則成為關(guān)聯(lián)模式。分類模式和回歸模式是使用最普遍的模式。” 6. 序列模式 序列模式與關(guān)聯(lián)模式相仿，而把數(shù)據(jù)之間的關(guān)聯(lián)性與時間聯(lián)系起來。與分類模式不同，進行聚類前并不知道將要劃分成幾個組和什么樣的組，也不知道根據(jù)哪一 (幾 )個數(shù)據(jù)項來定義組。 3. 時間序列模式 時間序列模式根據(jù)數(shù)據(jù)隨時間變化的趨勢預(yù)測將來的值。 數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 4 在實際應(yīng)用中，往往根據(jù)模式的實際作用細分為以下 6 種： 1. 分類模式 分類模式是一個分類函數(shù) (分類器 )，能夠把數(shù)據(jù)集中的數(shù)據(jù)項映射到某個給定的類上。當(dāng)有新的動物資料時，就可以根據(jù)這個模式判別此動物是否是哺乳動物。 模式有很多種，按功能可分有兩大類：預(yù)測型 (Predictive)模式和描述型 (Descriptive)模式。 【問題陳述】 A. 數(shù)據(jù)挖掘的任務(wù)及其六種模式 數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。數(shù)據(jù)挖掘算法的好壞將直接影響到所發(fā)現(xiàn) 知識的好壞。隨后在 1991年、 1993年和 1994 年都舉行 KDD 專題討論會，匯集來自各個領(lǐng)域的研究人員和應(yīng)用開發(fā)者，集中討論數(shù)據(jù)統(tǒng)計、海量數(shù)據(jù)分析算法、知識表示、知識運用等問題。 用數(shù)據(jù)庫 管理系統(tǒng)來存儲數(shù)據(jù)，用機器學(xué)習(xí)的方法來分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后的知識，這兩者的結(jié)合促成了數(shù)據(jù)庫中的知識發(fā)現(xiàn) (KDD： Knowledge Discovery in Databases)的產(chǎn)生。缺乏挖掘數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 3 數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。本文就數(shù)據(jù)挖掘 中的兩種 模式 ： 關(guān)聯(lián)規(guī)則 (Association Rules)和 序列模式(Sequential Patterns)的概念和作用進行了探討，對關(guān)聯(lián)規(guī)則中尋找大項集 (Large Item Set)的部分用程序加以實現(xiàn)，并對此兩個模式的實現(xiàn)過程用程序流程的方式加以說明，討論了幾種不同的實現(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)老師：朱揚勇 復(fù)旦大學(xué)計算機系 97 級軟件 楊 靖 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ù)挖掘由一些大型零售機構(gòu)所面臨的“ 決策 支持”問題 (decision support problem)所激發(fā)。 【術(shù) 語】 1. 知識發(fā)現(xiàn) —— KDD(Knowledge Discovery in Databases)用數(shù)據(jù)庫管理系統(tǒng)來存儲 數(shù) 據(jù)，用機器學(xué)習(xí)的方法來分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后的知識， 稱 為數(shù)據(jù)庫中的知識發(fā)現(xiàn) 2. 數(shù)據(jù)挖掘 —— 數(shù)據(jù)挖掘 (Data Mining)就是從大量的、不完全的、有噪聲的、模 糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但 又是潛在有用的信息和知識的過程 【背景概述】 隨著數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們積累的數(shù)據(jù)越來越多。 計算機技術(shù)的另一領(lǐng)域 —— 人工智能自 1956 年誕生之后取得了重大進展。實際上，數(shù)據(jù)庫中的知識發(fā)現(xiàn)是一門交叉性學(xué)科，涉及到機器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、智能數(shù)據(jù)庫、知識獲取、數(shù)據(jù)可視化、高性能計算、專家系統(tǒng)等多個領(lǐng)域。隨著參與人員的不斷增多， KDD 國際會議發(fā)展成為年會。目前大多數(shù)的研究都集中在數(shù)據(jù)挖掘算法和應(yīng)用上。模式是一個用語言 L 來表示的一個表達式 E，它可用來描述數(shù)據(jù)集 F 中數(shù)據(jù)的特性， E 所描述的數(shù)據(jù)是集合 F 的一個子集 FE。 預(yù)測型模式 是可以根據(jù)數(shù)據(jù)項的值精確確定某種結(jié)果的模式。 描述型模式 是對數(shù)據(jù)中存在的規(guī)則做一種描述，或者 根據(jù)數(shù)據(jù)的相似性把數(shù)據(jù)分組。分類模式往往表現(xiàn)為一棵分類樹，根據(jù)數(shù)據(jù)的值從樹根開始搜索，沿著數(shù)據(jù)滿足的分支往上走，走到樹葉就能確定類別。這里要考慮到時間的特殊性質(zhì)，像一些周期性的時間定義如星期、月、季節(jié)、年等，不同的日子如節(jié)假日可能造成的影響，日期本身的計算方法，還有一些需要特殊考慮的地方如時間前后的相關(guān)性 (過去的事情對將來有多大的影響力 )等。一般來說，業(yè)務(wù)知識豐富的人應(yīng)該可以理解這些組的含義，如果產(chǎn)生的模式無法理解或不可用，則該模式可能是無意義的，需要回到上階段重新組織數(shù)據(jù)。為了發(fā)現(xiàn)序列模式，不僅需要知道事件是否發(fā)生，而且需要確定事件發(fā)生的時間。分類模式、回歸模式、時間序列模式也被認為是受監(jiān)督知識，因為在建立模式前數(shù)據(jù)的數(shù)數(shù) 據(jù)據(jù) 挖挖 掘掘 中中 的的 關(guān)關(guān) 聯(lián)聯(lián) 規(guī)規(guī) 則則 和和 序序 列列 模模 式式 5 結(jié)果是已知的，可以直接用來檢測模式的準(zhǔn)確性，模式的產(chǎn)生是在受監(jiān)督的情況下進行的。我們所要討論的問題集中在 數(shù)據(jù)挖掘中的 關(guān)聯(lián)規(guī)則 (Mining Association Rules)和 序列模式 (Mining Sequential Patterns)上， 也就是上述六個模式中的第五和第六個。以下對其總體概念作一些說明并討論其應(yīng)用方向。更通常的是，數(shù)據(jù)記錄也包含了 客戶號 (customerid)，特別當(dāng)買主是持有信用卡或商店優(yōu)惠卡的顧客時。由此可見 ,從事務(wù)數(shù)據(jù)中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則并以此為基礎(chǔ)挖掘 出序列模式 ,對于改進零售業(yè)等商業(yè)活動的決策非常重要。那么，物品甲和乙在事務(wù)中的出現(xiàn)相互之間是否有規(guī)律可循呢？在數(shù)據(jù)庫的數(shù)據(jù)挖掘中， 關(guān)聯(lián)規(guī)則 就是描述這種在一個事務(wù)中物品之間同時出現(xiàn)的規(guī)律的知識模式。這些數(shù)據(jù)中常常隱含形式如下的關(guān)聯(lián)規(guī)則：在購買鐵錘的顧客當(dāng)中，有70 ％的人同時購買了鐵釘 。保險公司在接受保 險前，往往需要記錄投保人詳盡的信息，有時還要到醫(yī)院做身體檢查。在這條規(guī)則中，“年齡在 40 歲以上”是物品甲，“工作在 A 區(qū)”是物品乙，“向保險公司索賠過”則是物品丙。稱事務(wù) T 支持物品集 X，如果 X?T。 (3) 稱規(guī)則 X→ Y 在事務(wù)數(shù)據(jù)庫 D 中具有大小為 c 的可信度，如果 D 中支持物品 集 X 的事務(wù)中有 c%的事務(wù)同時也支持物品集 Y。因此，為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，需要給定兩個閾值 :最小支持度和最小可信度。因為物品概念間存在一種層次關(guān)系，如夾克衫、滑雪衫屬于外套類，外套、襯衣又屬于衣服類。但如果考慮到較高層次的物品 (如外套 )，則其支持度就較高，從而可能發(fā) 現(xiàn)有用的規(guī)則。 (2) 利用大項集 (litemsets)產(chǎn)生所需的規(guī)則 (rules)。 for ( k = 2。 // Candidates contained in t forall candidates c ? Ct do ++。 forall itemsets c?Ck do forall (k1)subsets s of c do if ( s ? Lk1 ) then delete c from Ck。 注：在以 上算法中，支持度是對交易 (transaction)而言的，但在序列模式的計算中，大項集的支持度是對客戶 (customer)數(shù)而言的，故程序需做相應(yīng)的部分改動。所謂項集，指的是多個物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作是由兩個 項 (item)組成的項集，它也可以作為某一個序列模式的元素。一個 序列 s 可以表示為 s1,s2… sn，這里的 sj代表的是一個項集。前者表示項 3 和項 5是先后購買的，而后者則表示項 3 和項 5 是同時購買的，這就是區(qū)別所在。我們稱這樣的序列為 客戶序列(customersequence)。見圖 _2。而每個這樣的 最大序