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