【文章內(nèi)容簡介】 0萬 TB。但是，據(jù)估計，目前一個大型企事業(yè)單位的數(shù)據(jù)，大約只有 7％得到較好地應(yīng)用，對于數(shù)據(jù)管理來說，陷入了一個尷尬境地 ――“ 數(shù)據(jù)豐富，信息（知識）貧乏 ”。 數(shù)據(jù)管理用于決策分析的技術(shù)應(yīng)運而生：一方面數(shù)據(jù)倉庫技術(shù)的提出與發(fā)展，另一方面數(shù)據(jù)挖掘技術(shù)的產(chǎn)生。 先看一個例子：啤酒與尿布的故事 ―― 美國加州某超市連鎖店通過對存儲的銷售數(shù)據(jù)采用數(shù)據(jù)挖掘技術(shù)分析發(fā)現(xiàn)：下班前后或周末購買嬰兒尿布的顧客較多為男性，往往同時購買啤酒，兩類互不相干的商品有一定的關(guān)聯(lián)。于是，連鎖店經(jīng)理當機立斷，重新布置貨架，將男士們需要的日常生活用品就近布置，取得了有關(guān)商品銷量大增的驕人業(yè)績。 80年代以來，人們逐漸關(guān)注這方面的研究，其它數(shù)據(jù)挖掘的例子也就層出不窮 .正像數(shù)據(jù)庫技術(shù)的發(fā)展一樣，開始時是一個一個行業(yè)的建立使用，逐步鋪開。數(shù)據(jù)挖掘技術(shù)，目前雖沒有數(shù)據(jù)庫技術(shù)這樣家喻戶曉，但經(jīng)過多年的發(fā)展，應(yīng)用領(lǐng)域也已是一個熱門領(lǐng)域，應(yīng)用面已相當廣泛。 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 33 . (1)概述 2)數(shù)據(jù)挖掘的定義 較為廣泛接受的數(shù)據(jù)挖掘定義是：提取隱含于數(shù)據(jù)集合（數(shù)據(jù)庫、數(shù)據(jù)倉庫或其它數(shù)據(jù)集合）中未知的、有用的、不一般的（即不象OLAP中那樣計算總和、平均值子類的普通信息）信息或知識。數(shù)據(jù)挖掘，也有另外一種說法：數(shù)據(jù)庫中的知識發(fā)現(xiàn) KDD（Knowledge Discovery in Database）或知識提?。?Knowledge Extraction），數(shù)據(jù) /模式分析（ Data/Pattern Analysis），也有人認為數(shù)據(jù)挖掘 DM是 KDD的一個步驟，特別在討論實現(xiàn)過程時，往往認為 KDD是較廣泛的過程，而 DM是其中的一個步驟。 從數(shù)據(jù)庫技術(shù)看，在邏輯上從大量數(shù)據(jù)中提取規(guī)則，數(shù)據(jù)挖掘采用的是 歸納推理的方法 。而根據(jù)大量數(shù)據(jù)，采用歸納方法，推斷出一般化的規(guī)則、規(guī)律，也就是形成信息或知識。從更廣泛的角度來看，數(shù)據(jù)挖掘是一門跨學科的技術(shù) ，綜合采用了統(tǒng)計學、數(shù)據(jù)庫技術(shù)、機器學習、模式識別、人工智能、可視化技術(shù)，很難嚴格區(qū)分數(shù)據(jù)挖掘與這些學科之間的界限。 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 34 . (2)數(shù)據(jù)挖掘的過程 (2)數(shù)據(jù)挖掘的過程 :1)知識發(fā)現(xiàn) KDD的全過程 2)數(shù)據(jù)挖掘（ Data Mining， DM）過程 1)知識發(fā)現(xiàn) KDD的全過程 數(shù) 據(jù) 庫 其 它 數(shù) 據(jù) 源. . .模 式特 定 數(shù) 據(jù) 集數(shù) 據(jù) 倉 庫知 識選擇與轉(zhuǎn)換清理與集成數(shù)據(jù)挖掘評估與表示2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 35 . (2)數(shù)據(jù)挖掘的過程 2)數(shù)據(jù)挖掘（ Data Mining， DM）過程 數(shù)據(jù)挖掘作為整個知識發(fā)現(xiàn)（ KDD）的一個重要步驟，起著關(guān)鍵作用。有時，當單獨將數(shù)據(jù)挖掘過程抽出來闡述時，也經(jīng)常把 KDD過程與 DM過程不加區(qū)分，正像提到 KDD概念、 DM概念時也不加區(qū)分。 數(shù)據(jù)挖掘過程，可用下圖來表示。某種意義上看，也是知識發(fā)現(xiàn)的全過程，其中的模式（ Pattern）發(fā)現(xiàn) ―― 數(shù)據(jù)挖掘的關(guān)鍵步驟，相當于上面 KDD過程中的數(shù)據(jù)挖掘。 數(shù) 據(jù) 源數(shù) 據(jù) 選 擇 預(yù) 處 理 模 式 發(fā) 現(xiàn) 解 釋 評 估提 出 目 標 提 示 方 法 選 擇 模 式 選 擇決 策 樹2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 36 . (2)數(shù)據(jù)挖掘的過程 ① 數(shù)據(jù)選擇 ：數(shù)據(jù)挖掘正像采礦一樣，先要通過地質(zhì)普查找到礦藏所在源，這里就是提出挖掘的目標，也就是選擇好限定的主題，來選擇相關(guān)的數(shù)據(jù)。例如，目標是優(yōu)化銷售策略，那么，根據(jù)這樣的目標，圍繞此主題選取與銷售相關(guān)的數(shù)據(jù)記錄作為數(shù)據(jù)挖掘的對象。 ② 數(shù)據(jù)預(yù)處理 ：對于選擇好的數(shù)據(jù)，必須經(jīng)過預(yù)處理提高數(shù)據(jù)質(zhì)量，才能使得數(shù)據(jù)挖掘更加有效。因為不經(jīng)預(yù)處理的數(shù)據(jù)，往往垃圾數(shù)據(jù)比較多，數(shù)據(jù)的決策分析是一種典型的“垃圾進垃圾出”的過程，數(shù)據(jù)預(yù)處理對數(shù)據(jù)挖掘的結(jié)果有重要的影響。數(shù)據(jù)預(yù)處理技術(shù)主要包括：數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換和數(shù)據(jù)歸約。 ③ 模式（ Pattern）發(fā)現(xiàn) ：這是數(shù)據(jù)挖掘的關(guān)鍵一步。蘊涵在數(shù)據(jù)中的規(guī)律、規(guī)則或特征，也就是通常所說的知識，表現(xiàn)在數(shù)據(jù)的某種模式上，發(fā)現(xiàn)數(shù)據(jù)模式關(guān)鍵是人機交互地選擇算法，這一步是數(shù)據(jù)挖掘中的核心內(nèi)容，下面我們將單列一節(jié)介紹數(shù)據(jù)挖掘的基本內(nèi)容與方法。 ④ 解釋評估 ：通過模式發(fā)現(xiàn)算法可以得到較多的模式。對于給定的用戶，是否對所有模式都感興趣，答案是否定的。所以，數(shù)據(jù)挖掘過程的最后一步，是討論從挖掘出的模式中得到有趣模式的問題，即對用戶有用的模式，也就是對挖掘出的模式進行解釋評估。 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 37 . (2)數(shù)據(jù)挖掘的過程 有關(guān)解釋評估，需要討論以下一些問題： ① 模式興趣度的度量：一是客觀度量，例如對于形如 X→Y 的關(guān)聯(lián)規(guī)則，客觀度量通常采用支持度和置信度來定義，支持度 Support(X→Y) = P(X ∪ Y)，其中 P(X∪ Y)是項集 X和 Y并的概率。置信度 Confidence(X→Y) = P(Y|X) ，其中 P(Y|X)是包含 X的事務(wù)也包含 Y的概率。對于度量再引入閾值，由用戶來控制，用戶可以認為置信度閾值不超過 50%的模式是無趣的。對此，下面還要詳細討論的。另一種是主觀度量，實際上是用戶的一種主觀預(yù)感，認為合理的或認為出乎意料的，給出模式是否有趣的結(jié)論。 ② 數(shù)據(jù)挖掘的完全性：數(shù)據(jù)挖掘能否挖掘出所有有趣的模式，這是較難做到的。只能說，對于某些數(shù)據(jù)挖掘任務(wù)，根據(jù)用戶提出的限制和興趣度量，在一定條件下保證算法的完全性。 ③ 數(shù)據(jù)挖掘能夠僅僅產(chǎn)生有趣的模式嗎？往往數(shù)據(jù)挖掘可能會生成一些不是有趣的模式，我們希望僅僅產(chǎn)生有趣模式，這是一個數(shù)據(jù)挖掘優(yōu)化問題。如何識別真正有趣的模式，過濾掉一些不感興趣的模式，采用興趣度度量來知道數(shù)據(jù)挖掘過程，是數(shù)據(jù)挖掘中最后一步重要的工作。 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 38 . (3)數(shù)據(jù)挖掘的基本方法 (3)數(shù)據(jù)挖掘的基本方法 數(shù)據(jù)挖掘算法，針對不同的挖掘任務(wù)，有很多不同的方法，本節(jié)只闡述下面 4種基本方法： 1．分類、 2．聚類、 3．關(guān)聯(lián)分析、 4．時間序列。 1）分類 ①概述 分類是對數(shù)據(jù)的一個重要抽象，從機器學習的觀點看，分類是一種監(jiān)督學習，即根據(jù)應(yīng)用的需要確定分類的類別，通過對訓練數(shù)據(jù)的分類學習歸納出分類規(guī)則，利用測試數(shù)據(jù)對模型的準確率進行測試，再對數(shù)據(jù)進行分類操作。 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 39 .(3)數(shù)據(jù)挖掘的基本方法 分類過程分兩步完成，如圖所示。 訓 練 數(shù) 據(jù)分 類 算 法分 類 規(guī) 則（ 模 型 ）i f 年 齡 = “ 3 1 4 0 ” a n d 收 入 = “ 高 ”t h e n 信 用 評 估 = “ 優(yōu) 良 ”姓 名 年 齡 收 入 信 用 評 估李 明 = 3 0 低 中 等徐 林 = 3 0 低 優(yōu) 良馮 勇 3 1 4 0 高 優(yōu) 良鄭 敏 4 0 中 中 等. . . . . . . . . . . .測 試 數(shù) 據(jù)分 類 規(guī) 則（ 模 型 ）新 數(shù) 據(jù) ： 李 紅 ， 3 1 4 0 ， 高 ， 信 用 評 估 ？姓 名 年 齡 收 入 信 用 評 估張 偉 4 0 高 中 等李 勇 = 3 0 低 中 等王 明 3 1 4 0 高 優(yōu) 良. . . . . . . . . . . .優(yōu) 良2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 40 .(3)數(shù)據(jù)挖掘的基本方法 ② 分類算法 以決策樹算法為例，說明分類算法的思路。例如，要對顧客是否購買電腦進行測試，圖就是決策樹的示例。 年 齡 ？學 生 ？ 信 用 等 級 ？Y e sY e sN o Y e sN o否 是優(yōu) 良 中 等3 0 4 0 4 0 3 02021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 41 .(3)數(shù)據(jù)挖掘的基本方法 算法 141： Generate_Decision_Tree（由給定的訓練數(shù)據(jù)生成決策樹） 輸入：訓練樣本 Samples，由離散值屬性表示，候選屬性的集合是 Attribute_List 輸出：決策樹 算法描述： ⒈） 創(chuàng)建節(jié)點 N； ⒉） if Samples 都在同一類 C then 返回 N作為葉節(jié)點，以類 C標記； ⒊） if Attribute_List 為空 then 返回 N作為葉節(jié)點，標記為 Samples中類別個數(shù)最多的類別； //多數(shù)表決 ⒋） 從 Attribute_List中選擇一個信息增益最大的屬性 test_attribute； //屬性選擇方法的信息增益概念，需要解釋 并將此節(jié)點 N標記為 test_attribute； ⒌） for each test_attribute 中的已知取值 ai 由節(jié)點 N長出一個條件為 test_attribute=ai的分支； //劃分 Samples 設(shè) Si是 Samples中 test_attribute = ai的樣本的集合； //其中的一個劃分 ⒍） if Si為空 then 加上一個葉節(jié)點，標記為 Samples中類別最多的類； ⒎ ） else 加上一個由 Generate_Decision_Tree (Si, Attribute_List, test_attribute）返回的節(jié)點； 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 42 .(3)數(shù)據(jù)挖掘的基本方法 信息增益方法：這是上面決策樹算法中屬性選擇的基本方法。 信息增益的定義。設(shè) S識包含 s個數(shù)據(jù)樣本的集合，假定類標號屬性具有 m個不同值，即定義 m個不同的類別 Ci(i=1,2,…,m) ，設(shè) si是類 Ci中的樣本數(shù)，對一個給定的樣本分類可給出所需的期望信息： 其中 pi是任一樣本屬于類別 Ci的概率，可按 si/s估計，對數(shù)函數(shù)以 2為底，是因為信息以二進制位編碼。設(shè)屬性 A具有 v個不同值 {a1,a2,…av} ，利用屬性 A可將數(shù)據(jù)集合 S劃分為 v個子集 {S1,S2,…Sv} ，其中 Sj包含了 S集合中屬性 A取 aj值的樣本。若屬性 A被選為測試屬性，設(shè) sij為子集 sj中屬于 Ci類的樣本數(shù)，那么，利用屬性 A劃分當前樣本集所需的期望信息是： 其中當作第 j個子集的權(quán)值，而是對于給定子集 Sj的期望信息。 E(A)計算結(jié)果越小，表示其子集劃分結(jié)果越好。在 A上分支將獲得的編碼信息是：Gain(A)=I(S1,…,Sm) E(A)定義為利用屬性 A對當前分支節(jié)點進行劃分的信息增益。 111...( ) ( , .. . )v j m jj m jjssE A I s ss???? ?1 2 21( , , . . . , ) l o g ( )mm i iiI s s s p p??? ?2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 43 .(3)數(shù)據(jù)挖掘的基本方法 現(xiàn)以購買電腦相關(guān)的訓練數(shù)據(jù)樣本為例，說明信息增益方法的思路。 RID 年齡 收入 是否學生 信用評估 是否購買電腦 1 =30 高 No 中 No 2 =30 高 No 好 No 3 31..40 高 No 中 Yes 4 40 中 No 中 Yes 5 40 低 Yes 中 Yes 6 40 低 Yes 好 No 7 31..40 低 Yes 好 Yes 8 =30 中 No 中 No 9 =30 低 Yes 中 Yes 10 40 中 Yes 中 Yes 11 =30 中 Yes 好 Yes 12 31..40 中 No 好 Yes 13 31..40 高 Yes 中 Yes 14 40 中 No 好 No 2021年 6月 14日星期一 數(shù)據(jù)庫教程（沈 ） 44 .(3)數(shù)據(jù)挖掘的基本方法 對于表給出的訓練數(shù)據(jù)集合，分類的標記為 2類，類 C1對應(yīng)于買電南 yes，類C2對應(yīng)于 no，類 yes有 9個樣本，類 no有 5個樣本，計算得到： 現(xiàn)計算有關(guān)屬性的信息增益，從屬性年齡開始， 對年齡 =30 s11=2 s12=3 I(s11,s21)= 對年齡 31..40 s12=4 s22=0 I(s11,s21)=0 對年齡 40 s13=3 s23=2 I(s11,s21)= 樣本按年齡劃分，期望信息為： 2