數(shù)據(jù)挖掘精品講義

數(shù) 據(jù) 挖 掘 主講教師：王燦 E-mail: 教科書和參考書 教科書 數(shù)據(jù)挖掘：概念與技術(shù)， Jiawei Han和 Micheline Kamber 著，機(jī)械工業(yè)出版社 (2001) 參考書 數(shù)據(jù)挖掘原理 , David Hand, Heikki Mannila和 Padhraic Smyth著，機(jī)械工業(yè)出版社 (2003) 中文版 英文影 印版 數(shù)據(jù)挖掘的發(fā)展動力 -需要是發(fā)明之母 數(shù)據(jù)爆炸問題 自動數(shù)據(jù)收集工具和成熟的數(shù)據(jù)庫技術(shù)使得大量的數(shù)據(jù)被收集，存儲在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中以待分析。 我們擁有豐富的數(shù)據(jù)，但卻缺乏有用的信息 解決方法：數(shù)據(jù)倉庫技術(shù)和數(shù)據(jù)挖掘技術(shù) 數(shù)據(jù)倉庫 (Data Warehouse)和在線分析處理 (OLAP) 數(shù)據(jù)挖掘：在大量的數(shù)據(jù)中挖掘感興趣的知識（規(guī)則，規(guī)律，模式，約束） 數(shù)據(jù)庫技術(shù)的演化 (1) 1960s和以前 : 文件系統(tǒng) 1970s: 層次數(shù)據(jù)庫和網(wǎng)狀數(shù)據(jù)庫 1980s早期 : 關(guān)系數(shù)據(jù)模型 , 關(guān)系數(shù)據(jù)庫管理系統(tǒng) (RDBMS)的實現(xiàn) 數(shù)據(jù)庫技術(shù)的演化 (2) 1980s晚期 : 各種高級數(shù)據(jù)庫系統(tǒng) (擴(kuò)展的關(guān)系數(shù)據(jù)庫 ,面向?qū)ο髷?shù)據(jù)庫等等 .) 面向應(yīng)用的數(shù)據(jù)庫系統(tǒng) (空間數(shù)據(jù)庫，時序數(shù)據(jù)庫，多媒體數(shù)據(jù)庫等等） 1990s: 數(shù)據(jù)挖掘 , 數(shù)據(jù)倉庫 , 多媒體數(shù)據(jù)庫和網(wǎng)絡(luò)數(shù)據(jù)庫 2000s 流數(shù)據(jù)管理和挖掘 基于各種應(yīng)用的數(shù)據(jù)挖掘 XML數(shù)據(jù)庫和整合的信息系統(tǒng) 什么是數(shù)據(jù)挖掘？ 數(shù)據(jù)挖掘 (從數(shù)據(jù)中發(fā)現(xiàn)知識 ) 從 大量的數(shù)據(jù) 中挖掘哪些令人感興趣的、有用的、隱含的、先前未知的和可能有用的模式或知識 挖掘的不僅僅是數(shù)據(jù)（所以“數(shù)據(jù)挖掘”并非一個精確的用詞） 數(shù)據(jù)挖掘的替換詞 數(shù)據(jù)庫中的知識挖掘（ KDD） 知識提煉、 數(shù)據(jù) /模式分析 數(shù)據(jù)考古 數(shù)據(jù)捕撈、信息收獲等等。 數(shù)據(jù)挖掘 : 數(shù)據(jù)庫中的知識挖掘 (KDD) 數(shù)據(jù)挖掘 知識挖掘的核心 數(shù)據(jù)清理 數(shù)據(jù)集成 數(shù)據(jù)庫 數(shù)據(jù)倉庫 任務(wù)相關(guān)數(shù)據(jù) 選擇 數(shù)據(jù)挖掘 模式評估 KDD的步驟 從 KDD對數(shù)據(jù)挖掘的定義中可以看到當(dāng)前研究領(lǐng)域?qū)?shù)據(jù)挖掘的狹義和廣義認(rèn)識 1. 數(shù)據(jù)清理 : (這個可能要占全過程 60的工作量 ) 2. 數(shù)據(jù)集成 3. 數(shù)據(jù)選擇 4. 數(shù)據(jù)變換 5. 數(shù)據(jù)挖掘（選擇適當(dāng)?shù)乃惴▉碚业礁信d趣的模式） 6. 模式評估 7. 知識表示 典型數(shù)據(jù)挖掘系統(tǒng)的體系結(jié)構(gòu) 數(shù)據(jù)倉庫 數(shù)據(jù)清洗 過濾 數(shù)據(jù)庫 數(shù)據(jù)庫或數(shù)據(jù)倉庫服務(wù)器 數(shù)據(jù)挖掘引擎 模式評估 圖形用戶界面 知識庫 數(shù)據(jù)集成 并非所有的東西都是數(shù)據(jù)挖掘 基于數(shù)據(jù)倉庫的 OLAP系統(tǒng) OLAP系統(tǒng)專注于數(shù)據(jù)的匯總，而數(shù)據(jù)挖掘系統(tǒng)可以對數(shù)據(jù)進(jìn)行多種復(fù)雜的處理。 機(jī)器學(xué)習(xí)系統(tǒng)，數(shù)據(jù)統(tǒng)計分析系統(tǒng) 這些系統(tǒng)所處理的數(shù)據(jù)容量往往很有限。 信息系統(tǒng) 專注于數(shù)據(jù)的查詢處理。 相比于上述系統(tǒng)，數(shù)據(jù)挖掘系統(tǒng)關(guān)注更廣的范圍，是一個多學(xué)科的融合 在何種數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘 關(guān)系數(shù)據(jù)庫 數(shù)據(jù)倉庫 事務(wù)數(shù)據(jù)庫 高級數(shù)據(jù)庫系統(tǒng)和信息庫 空間數(shù)據(jù)庫 時間數(shù)據(jù)庫和時間序列數(shù)據(jù)庫 流數(shù)據(jù) 多媒體數(shù)據(jù)庫 面向?qū)ο髷?shù)據(jù)庫和對象 -關(guān)系數(shù)據(jù)庫 異種數(shù)據(jù)庫和歷史 (legacy)數(shù)據(jù)庫 文本數(shù)據(jù)庫和萬維網(wǎng) (WWW) 空間數(shù)據(jù)庫 空間數(shù)據(jù)庫是指在關(guān)系型數(shù)據(jù)庫（ DBMS）內(nèi)部對地理信息進(jìn)行物理存儲?？臻g數(shù)據(jù)庫中存儲的海量數(shù)據(jù)包括對象的空間拓?fù)涮卣?、非空間屬性特征以及對象在時間上的狀態(tài)變化。 常見的空間數(shù)據(jù)庫數(shù)據(jù)類型 地理信息系統(tǒng) (GIS) 遙感圖像數(shù)據(jù) 醫(yī)學(xué)圖像數(shù)據(jù) 數(shù)據(jù)挖掘技術(shù)的應(yīng)用：通過空間分類和空間趨勢分析，引入機(jī)器學(xué)習(xí)算法，對有用模式進(jìn)行智能檢索 時間數(shù)據(jù)庫和時序數(shù)據(jù)庫 時間數(shù)據(jù)庫和時序數(shù)據(jù)庫都存放與時間有關(guān)的數(shù)據(jù)。時間數(shù)據(jù)庫通常存放包含時間相關(guān)屬性的數(shù)據(jù)。時序數(shù)據(jù)庫存放隨時間變化的值序列。 對時間數(shù)據(jù)庫和時序數(shù)據(jù)庫的數(shù)據(jù)挖掘 ,可以通過研究事物發(fā)生發(fā)展的過程，有助于揭示事物發(fā)展的本質(zhì)規(guī)律，可以發(fā)現(xiàn)數(shù)據(jù)對象的演變特征或?qū)ο笞兓厔荨?流數(shù)據(jù) 與傳統(tǒng)的數(shù)據(jù)庫技術(shù)中的靜態(tài)數(shù)據(jù)不同，流數(shù)據(jù)是連續(xù)的、有序的、變化的、快速的、大量的數(shù)據(jù)輸入的數(shù)據(jù)。 主要應(yīng)用場合 網(wǎng)絡(luò)監(jiān)控 網(wǎng)頁點擊流 股票市場 流媒體 等等 與傳統(tǒng)數(shù)據(jù)庫技術(shù)相比，流數(shù)據(jù)在存儲、查詢、訪問、實時性的要求等方面都有很大區(qū)別。 多媒體數(shù)據(jù)庫 多媒體數(shù)據(jù)庫實現(xiàn)用計算機(jī)管理龐大復(fù)雜的多媒體數(shù)據(jù)，主要包括包括圖形 (graphics)、圖象 (image)、聲音 (audio)、視頻 (video)等等，現(xiàn)代數(shù)據(jù)庫技術(shù)一般將這些多媒體數(shù)據(jù)以二進(jìn)制大對象的形式進(jìn)行存儲。 對于多媒體數(shù)據(jù)庫的數(shù)據(jù)挖掘，需要將存儲和檢索技術(shù)相結(jié)合。目前的主要方法包括構(gòu)造多媒體數(shù)據(jù)立方體、多媒體數(shù)據(jù)庫的多特征提取和基于相似性的模式匹配。 面向?qū)ο髷?shù)據(jù)庫和對象 -關(guān)系數(shù)據(jù)庫 面向?qū)ο髷?shù)據(jù)庫是面向?qū)ο蠹夹g(shù)和數(shù)據(jù)庫技術(shù)結(jié)合的產(chǎn)物，該技術(shù)對數(shù)據(jù)以對象的形式進(jìn)行存儲，并在這個基礎(chǔ)上實現(xiàn)了傳統(tǒng)數(shù)據(jù)庫的功能，包括持久性、并發(fā)控制、可恢復(fù)性、一致性和查詢數(shù)據(jù)庫的能力等。 對象關(guān)系數(shù)據(jù)庫基于對象關(guān)系模型構(gòu)造，該模型通過處理復(fù)雜對象的豐富數(shù)據(jù)類型和對象定位等功能，擴(kuò)充關(guān)系模型。 面向?qū)ο髷?shù)據(jù)庫和對象關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)挖掘會涉及一些新的技術(shù)，比如處理復(fù)雜對象結(jié)構(gòu)、復(fù)雜數(shù)據(jù)類型、類和子類層次結(jié)構(gòu)、構(gòu)造繼承以及方法和過程等等。 異構(gòu)數(shù)據(jù)庫和歷史 (legacy)數(shù)據(jù)庫 歷史數(shù)據(jù)庫是一系列的異構(gòu)數(shù)據(jù)庫系統(tǒng)的集合，包括不同種類的數(shù)據(jù)庫系統(tǒng)，像關(guān)系數(shù)據(jù)庫、網(wǎng)絡(luò)數(shù)據(jù)庫、文件系統(tǒng)等等。 有效利用歷史數(shù)據(jù)庫的關(guān)鍵在于實現(xiàn)不同數(shù)據(jù)庫之間的數(shù)據(jù)信息資源、硬件設(shè)備資源和人力資源的合并和共享。 對于異構(gòu)數(shù)據(jù)庫系統(tǒng)，實現(xiàn)數(shù)據(jù)共享應(yīng)當(dāng)達(dá)到兩點：一是實現(xiàn)數(shù)據(jù)庫轉(zhuǎn)換；二是實現(xiàn)數(shù)據(jù)的透明訪問。 WEB SERVICE技術(shù)的出現(xiàn)有利于歷史數(shù)據(jù)庫數(shù)據(jù)的重新利用。 文本數(shù)據(jù)庫和萬維網(wǎng) (WWW) 文本數(shù)據(jù)庫存儲的是對對象的文字性描述。 文本數(shù)據(jù)庫的分類 無結(jié)構(gòu)類型（大部分的文本資料和網(wǎng)頁） 半結(jié)構(gòu)類型（ XML數(shù)據(jù)） 結(jié)構(gòu)類型（圖書館數(shù)據(jù)） 萬維網(wǎng) (WWW)可以被看成最大的文本數(shù)據(jù)庫 數(shù)據(jù)挖掘內(nèi)容 內(nèi)容檢索 WEB訪問模式檢索 數(shù)據(jù)挖掘應(yīng)用 市場分析和管理 (1) 數(shù)據(jù)從那里來 ? 信用卡交易 , 會員卡 , 商家的優(yōu)惠卷 , 消費者投訴電話 , 公眾生活方式研究 目標(biāo)市場 構(gòu)建一系列的“客戶群模型”，這些顧客具有相同特征 : 興趣愛好 , 收入水平 , 消費習(xí)慣 ,等等 確定顧客的購買模式 交叉市場分析 貨物銷售之間的相互聯(lián)系和相關(guān)性，以及基于這種聯(lián)系上的預(yù)測 數(shù)據(jù)挖掘應(yīng)用 市場分析和管理 (2) 顧客分析 哪類顧客購買那種商品 (聚類分析或分類預(yù)測 ) 客戶需求分析 確定適合不同顧客的最佳商品 預(yù)測何種因素能夠吸引新顧客 提供概要信息 多維度的綜合報告 統(tǒng)計概要信息 (數(shù)據(jù)的集中趨勢和變化 ) 數(shù)據(jù)挖掘應(yīng)用 公司分析和風(fēng)險管理 財務(wù)計劃 現(xiàn)金流轉(zhuǎn)分析和預(yù)測 交叉區(qū)域分析和時間序列分析（財務(wù)資金比率，趨勢分析等等） 資源計劃 總結(jié)和比較資源和花費 競爭 對競爭者和市場趨勢的監(jiān)控 將顧客按等級分組和基于等級的定價過程 將定價策略應(yīng)用于競爭更激烈的市場中 數(shù)據(jù)挖掘應(yīng)用 欺詐行為檢測和異常模式的發(fā)現(xiàn) 方法 : 對欺騙行為進(jìn)行聚類和建模，并進(jìn)行孤立點分析 應(yīng)用 : 衛(wèi)生保健、零售業(yè)、信用卡服務(wù)、電信等 汽車保險 : 相撞事件的分析 洗錢 : 發(fā)現(xiàn)可疑的貨幣交易行為 醫(yī)療保險 職業(yè)病人 , 醫(yī)生以及相關(guān)數(shù)據(jù)分析 不必要的或相關(guān)的測試 電信 : 電話呼叫欺騙行為 電話呼叫模型 : 呼叫目的地，持續(xù)時間，日或周呼叫次數(shù) . 分析該模型發(fā)現(xiàn)與期待標(biāo)準(zhǔn)的偏差 零售產(chǎn)業(yè) 分析師估計有 38的零售額下降是由于雇員的不誠實行為造成的 反恐怖主義 數(shù)據(jù)挖掘的主要功能 可以挖掘哪些模式？ 一般功能 描述性的數(shù)據(jù)挖掘 預(yù)測性的數(shù)據(jù)挖掘 通常，用戶并不知道在數(shù)據(jù)中能挖掘出什么東西，對此我們會在數(shù)據(jù)挖掘中應(yīng)用一些常用的數(shù)據(jù)挖掘功能，挖掘出一些常用的模式，包括： 概念 /類描述 : 特性化和區(qū)分 關(guān)聯(lián)分析 分類和預(yù)測 聚類分析 孤立點分析 趨勢和演變分析 概念 /類描述 : 特性化和區(qū)分 概念描述：為數(shù)據(jù)的特征化和比較產(chǎn)生描述（當(dāng)所描述的概念所指的是一類對象時，也稱為類描述） 特征化：提供給定數(shù)據(jù)集的簡潔匯總。 例：對 AllElectronic公司的“大客戶”（年消費額 $1000以上）的特征化描述： 40 50歲，有固定職業(yè)，信譽良好，等等 區(qū)分：提供兩個或多個數(shù)據(jù)集的比較描述。 例： S t a t u s B i r t h _ c o u n t r y A g e _ r a n g e G p a C o u n tG r a d u a t e C a n a d a 2 5 - 3 0 G o o d 90U n d e r g r a d u a t e C a n a d a 2 5 - 3 0 G o o d 2 1 0關(guān)聯(lián)分析 關(guān)聯(lián)規(guī)則挖掘： 從事務(wù)數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。 廣泛的用于購物籃或事務(wù)數(shù)據(jù)分析。 例： %70%,20 s u p) ,( )48.42 ,( )39.30 ,( c on f i d e n c ep o r tc omp u t e rXb u y skkXi n c omeXage分類和預(yù)測 根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)（分類），用來預(yù)測類型標(biāo)志未知的對象類（預(yù)測）。 比如：按氣候?qū)曳诸?，按汽油消耗定額將汽車分類 導(dǎo)出模型的表示 : 判定樹、分類規(guī)則、神經(jīng)網(wǎng)絡(luò) 可以用來預(yù)報某些未知的或丟失的數(shù)字值 例： IF age = 40 AND credit_rating = excellent THEN buys_computer = yes IF age = 40 AND credit_rating = fair THEN buys_computer = no 聚類分析 聚類分析： 將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程。 最大化類內(nèi)的相似性和最小化類間的相似性 例：對 WEB日志的數(shù)據(jù)進(jìn)行聚類，以發(fā)現(xiàn)相同的用戶訪問模式 孤立點分析 孤立點分析 孤立點 :一些與數(shù)據(jù)的一般行為或模型不一致的孤立數(shù)據(jù) 通常孤立點被作為“噪音”或異常被丟棄，但在欺騙檢測中卻可以通過對罕見事件進(jìn)行孤立點分析而得到結(jié)論。 應(yīng)用 信用卡欺詐檢測 移動電話欺詐檢測 客戶劃分 醫(yī)療分析（異常） 趨勢和演變分析 描述行為隨時間變化的對象的發(fā)展規(guī)律或趨勢（時序數(shù)據(jù)庫） 趨勢和偏差 : 回歸分析 序列模式匹配：周期性分析 基于類似性的分析 所有模式都是有趣的嗎？ 數(shù)據(jù)挖掘可能產(chǎn)生數(shù)以千計的模式或規(guī)則，但并不是所有的模式或規(guī)則都是令人感興趣的。 模式興趣度的度量 一個模式是有趣的，如果 (1) 它易于被人理解 ；（ 2）在某種程度上，對于新的或測試數(shù)據(jù)是有效的；（ 3）具有潛在效用；（ 4）新穎的；（ 5）符合用戶確信的某種假設(shè) 模式興趣度的客觀和主觀度量 客觀度量 : 基于所發(fā)現(xiàn)模式的結(jié)構(gòu)和關(guān)于它們的統(tǒng)計， 比如： 支持度、置信度等等 主觀度量 : 基于用戶對數(shù)據(jù)的判斷。比如：出乎意料的、新穎的、可行動的等等 5-6 王 燦 數(shù)據(jù)挖掘 0703004 能夠產(chǎn)生所有有趣模式并且僅產(chǎn)生有趣模式嗎？ 找出所有有趣的模式 : 數(shù)據(jù)挖掘算法的完全性問題 數(shù)據(jù)挖掘系統(tǒng)能夠產(chǎn)生所有有趣的模式嗎 ? 試探搜索 vs.窮舉搜索 關(guān)聯(lián) vs. 分類 vs. 聚類 只搜索有趣的模式 : 數(shù)據(jù)挖掘算法的最優(yōu)化問題 數(shù)據(jù)挖掘系統(tǒng)可以僅僅發(fā)現(xiàn)有趣的模式嗎？ 方法 首先生成所有模式然后過濾那些無趣的 . 僅僅生成有趣的模式 挖掘查詢優(yōu)化 數(shù)據(jù)挖掘 :多個學(xué)科的融合 數(shù)據(jù)挖掘 數(shù)據(jù)庫系統(tǒng) 統(tǒng)計學(xué) 其他學(xué)科 算法 機(jī)器學(xué)習(xí) 可視化 數(shù)據(jù)挖掘系統(tǒng)的分類 (1) 數(shù)據(jù)挖掘的多學(xué)科融合的特性，決定了數(shù)據(jù)挖掘的研究將產(chǎn)生種類繁多的數(shù)據(jù)挖掘系統(tǒng)。 根據(jù)所挖掘的數(shù)據(jù)庫分類 關(guān)系數(shù)據(jù)庫，事務(wù)數(shù)據(jù)庫，流式數(shù)據(jù)，面向?qū)ο髷?shù)據(jù)庫，對象關(guān)系數(shù)據(jù)庫，數(shù)據(jù)倉庫，空間數(shù)據(jù)庫，時序數(shù)據(jù)庫，文本數(shù)據(jù)庫，多媒體數(shù)據(jù)庫，異構(gòu)數(shù)據(jù)庫，歷史數(shù)據(jù)庫， WWW 數(shù)據(jù)挖掘系統(tǒng)的分類 (2) 根據(jù)挖掘的知識類型 特征分析 , 區(qū)分 , 關(guān)聯(lián)分析 , 分類聚類 , 孤立點分析 /演變分析 , 偏差分析等等 . 多種方法的集成和多層機(jī)挖掘 根據(jù)挖掘所用的技術(shù) 面向數(shù)據(jù)庫的挖掘、數(shù)據(jù)倉庫 、 OLAP、機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)、可視化等等 . 根據(jù)挖掘所用的應(yīng)用 金融 ,電信 ,銀行 , 欺詐分析 , DNA分析 ,股票市場 , Web挖掘等等 . 數(shù)據(jù)挖掘的主要問題 (1) 數(shù)據(jù)挖掘是多個學(xué)科融合，但本課程所關(guān)注的是： 海量數(shù)據(jù)的挖掘的效率和可擴(kuò)展性 本課程中所要涵蓋的主要數(shù)據(jù)挖掘問題包括： 挖掘方法問題和用戶交互問題 在數(shù)據(jù)庫中挖掘不同類型的知識 在不同抽象層上的交互式知識挖掘 背景知識的合并 數(shù)據(jù)挖掘查詢語言和特定的數(shù)據(jù)挖掘 數(shù)據(jù)挖掘結(jié)果的表示和可視化 處理噪聲何不完全數(shù)據(jù) 模式評估 : 興趣度問題 數(shù)據(jù)挖掘的主要問題 (2) 性能問題 數(shù)據(jù)挖掘算法的效率和可擴(kuò)展性 (scalability) （什么是可擴(kuò)展性？） 并行，分布式和增量挖掘算法 （數(shù)據(jù)的分塊挖掘） 其他和多樣化的數(shù)據(jù)庫類型相關(guān)的問題 關(guān)系型和復(fù)雜數(shù)據(jù)類型的處理 為特定的數(shù)據(jù)類型構(gòu)建特定的數(shù)據(jù)挖掘系統(tǒng) 從異構(gòu)數(shù)據(jù)庫中挖掘 WEB數(shù)據(jù)挖掘 數(shù)據(jù)倉庫和數(shù)據(jù)挖掘的OLAP技術(shù) 數(shù)據(jù)倉庫數(shù)據(jù)挖掘的有效平臺 數(shù)據(jù)倉庫中的數(shù)據(jù)清理和數(shù)據(jù)集成，是數(shù)據(jù)挖掘的重要數(shù)據(jù)預(yù)處理步驟 數(shù)據(jù)倉庫提供 OLAP工具，可用于不同粒度的數(shù)據(jù)分析 很多數(shù)據(jù)挖掘功能都可以和 OLAP操作集成，以提供不同概念層上的知識發(fā)現(xiàn) 分類 預(yù)測 關(guān)聯(lián) 聚集 什么是數(shù)據(jù)倉庫 ? 數(shù)據(jù)倉庫的定義很多，但卻很難有一種嚴(yán)格的定義 它是一個提供決策支持功能的數(shù)據(jù)庫，它與公司的操作數(shù)據(jù)庫分開維護(hù)。 為統(tǒng)一的歷史數(shù)據(jù)分析提供堅實的平臺，對信息處理提供支持 數(shù)據(jù)倉庫區(qū)別于其他數(shù)據(jù)存儲系統(tǒng) “數(shù)據(jù)倉庫是一個面向主題的、集成的、隨時間而變化的、不容易丟失的數(shù)據(jù)集合，支持管理部門的決策過程 .W. H. Inmon 數(shù)據(jù)倉庫關(guān)鍵特征一 面向主題 面向主題，是數(shù)據(jù)倉庫顯著區(qū)別于關(guān)系數(shù)據(jù)庫系統(tǒng)的一個特征 圍繞一些主題，如顧客、供應(yīng)商、產(chǎn)品等 關(guān)注決策者的數(shù)據(jù)建模與分析，而不是集中于組織機(jī)構(gòu)的日常操作和事務(wù)處理。 排除對于決策無用的數(shù)據(jù)，提供特定主題的簡明視圖。 數(shù)據(jù)倉庫關(guān)鍵特征二 數(shù)據(jù)集成 一個數(shù)據(jù)倉庫是通過集成多個異種數(shù)據(jù)源來構(gòu)造的。 關(guān)系數(shù)據(jù)庫，一般文件， 聯(lián)機(jī)事務(wù)處理記錄 使用數(shù)據(jù)清理和數(shù)據(jù)集成技術(shù)。 確保命名約定、編碼結(jié)構(gòu)、屬性度量等的一致性。 當(dāng)數(shù)據(jù)被移到數(shù)據(jù)倉庫時，它們要經(jīng)過轉(zhuǎn)化。 數(shù)據(jù)倉庫關(guān)鍵特征三 隨時間而變化 數(shù)據(jù)倉庫是從歷史的角度提供信息 數(shù)據(jù)倉庫的時間范圍比操作數(shù)據(jù)庫系統(tǒng)要長的多。 操作數(shù)據(jù)庫系統(tǒng) : 主要保存當(dāng)前數(shù)據(jù)。 數(shù)據(jù)倉庫 :從歷史的角度提供信息（比如過去 5-10 年） 數(shù)據(jù)倉庫中的每一個關(guān)鍵結(jié)構(gòu)都隱式或顯式地包含時間元素，而操作數(shù)據(jù)庫中的關(guān)鍵結(jié)構(gòu)可能就不包括時間元素。 數(shù)據(jù)倉庫關(guān)鍵特征四 數(shù)據(jù)不易丟失 盡管數(shù)據(jù)倉庫中的數(shù)據(jù)來自于操作數(shù)據(jù)庫，但他們卻是在物理上分離保存的。 操作數(shù)據(jù)庫的更新操作不會出現(xiàn)在數(shù)據(jù)倉庫環(huán)境下。 不需要事務(wù)處理，恢復(fù)，和并發(fā)控制等機(jī)制 只需要兩種數(shù)據(jù)訪問 : 數(shù)據(jù)的初始轉(zhuǎn)載和數(shù)據(jù)訪問（讀操作） 數(shù)據(jù)倉庫的構(gòu)建與使用 數(shù)據(jù)倉庫的構(gòu)建包括一系列的數(shù)據(jù)預(yù)處理過程 數(shù)據(jù)清理 數(shù)據(jù)集成 數(shù)據(jù)變換 數(shù)據(jù)倉庫的使用熱點是商業(yè)決策行為，例如： 增加客戶聚焦 產(chǎn)品重定位 尋找獲利點 客戶關(guān)系管理 數(shù)據(jù)倉庫與異種數(shù)據(jù)庫集成 異種數(shù)據(jù)庫的集成方法 傳統(tǒng)的異種數(shù)據(jù)庫集成 :（ 查詢驅(qū)動 ） 在多個異種數(shù)據(jù)庫上建立包裝程序（ wrappers）和中介程序（ mediators ） 查詢驅(qū)動方法 當(dāng)從客戶端傳過來一個查詢時，首先使用元數(shù)據(jù)字典將查詢轉(zhuǎn)換成相應(yīng)異種數(shù)據(jù)庫上的查詢；然后，將這些查詢映射和發(fā)送到局部查詢處理器 數(shù)據(jù)倉庫 : （ 更新驅(qū)動 ） 將來自多個異種源的信息預(yù)先集成，并存儲在數(shù)據(jù)倉庫中，供直接查詢和分析 查詢驅(qū)動方法和更新驅(qū)動方法的比較 查詢驅(qū)動的方法 需要負(fù)責(zé)的信息過濾和集成處理 與局部數(shù)據(jù)源上的處理競爭資源 對于頻繁的查詢，尤其是涉及聚集（匯總）操作的查詢，開銷很大（決策支持中常見的查詢形式） 更新驅(qū)動的方法（帶來高性能） 數(shù)據(jù)經(jīng)預(yù)處理后單獨存儲，對聚集操作提供良好支持 不影響局部數(shù)據(jù)源上的處理 集成歷史信息，支持負(fù)責(zé)的多維查詢 數(shù)據(jù)倉庫與操作數(shù)據(jù)庫系統(tǒng) 操作數(shù)據(jù)庫系統(tǒng)的主要任務(wù)是聯(lián)機(jī)事務(wù)處理OLTP 日常操作 : 購買，庫存，銀行，制造，工資，注冊，記帳等 數(shù)據(jù)倉庫的主要任務(wù)是聯(lián)機(jī)分析處理 OLAP 數(shù)據(jù)分析和決策支持，支持以不同的形式顯示數(shù)據(jù)以滿足不同的用戶需要 OLAP VS. OLTP (1) 用戶和系統(tǒng)的面向性 面向顧客（事務(wù)） VS. 面向市場（分析） 數(shù)據(jù)內(nèi)容 當(dāng)前的、詳細(xì)的數(shù)據(jù) VS. 歷史的、匯總的數(shù)據(jù) 數(shù)據(jù)庫設(shè)計 實體聯(lián)系模型 (ER)和面向應(yīng)用的數(shù)據(jù)庫設(shè)計 VS. 星型 /雪花模型和面向主題的數(shù)據(jù)庫設(shè)計 OLAP VS. OLTP (2) 數(shù)據(jù)視圖 當(dāng)前的、企業(yè)內(nèi)部的數(shù)據(jù) VS. 經(jīng)過演化的、集成的數(shù)據(jù) 訪問模式 事務(wù)操作 VS. 只讀查詢（但很多是復(fù)雜的查詢） 任務(wù)單位 簡短的事務(wù) VS. 復(fù)雜的查詢 訪問數(shù)據(jù)量 數(shù)十個 VS. 數(shù)百萬個 OLAP VS. OLTP (3) 用戶數(shù) 數(shù)千個 VS. 數(shù)百個 數(shù)據(jù)庫規(guī)模 100M-數(shù) GB VS. 100GB-數(shù) TB 設(shè)計優(yōu)先性 高性能、高可用性 VS. 高靈活性、端點用戶自治 度量 事務(wù)吞吐量 VS. 查詢吞吐量、響應(yīng)時間 為什么需要一個分離的數(shù)據(jù)倉庫 ? 提高兩個系統(tǒng)的性能 DBMS是為 OLTP而設(shè)計的：存儲方式 ,索引 , 并發(fā)控制 , 恢復(fù) 數(shù)據(jù)倉庫是為 OLAP而設(shè)計：復(fù)雜的 OLAP查詢 , 多維視圖，匯總 不同的功能和不同的數(shù)據(jù) : 歷史數(shù)據(jù) : 決策支持需要歷史數(shù)據(jù)，而這些數(shù)據(jù)在操作數(shù)據(jù)庫中一般不會去維護(hù) 數(shù)據(jù)匯總：決策支持需要將來自異種源的數(shù)據(jù)統(tǒng)一（如聚集和匯總） 數(shù)據(jù)質(zhì)量 : 不同的源使用不一致的數(shù)據(jù)表示、編碼和格式，對這些數(shù)據(jù)進(jìn)行有效的分析需要將他們轉(zhuǎn)化后進(jìn)行集成 多維數(shù)據(jù)模型 (1) 數(shù)據(jù)倉庫和 OLAP工具基于多維數(shù)據(jù)模型 在多維數(shù)據(jù)模型中，數(shù)據(jù)以數(shù)據(jù)立方體 (data cube)的形式存在 數(shù)據(jù)立方體 允許以多維數(shù)據(jù)建模和觀察。它由 維 和 事實 定義 維 是關(guān)于一個組織想要記錄的視角或觀點。每個維都有一個表與之相關(guān)聯(lián)，稱為 維表 。 多維數(shù)據(jù)模型圍繞中心主題組織，該主題用 事實表 表示 事實表 包括事實的名稱或度量以及每個相關(guān)維表的關(guān)鍵字 事實 指的是一些數(shù)字度量 多維數(shù)據(jù)模型 (2) 示例 time_key day day_of_the_week month quarter year time 維表 location_key street city state_or_province country location 事實表 Sales 事實表 time_key item_key branch_key location_key units_sold dollars_sold avg_sales 度量 item_key item_name brand type supplier_type item 維表 branch_key branch_name branch_type branch 維表 多維數(shù)據(jù)模型 (3) 在數(shù)據(jù)倉庫中，數(shù)據(jù)立方體是 n-D的 (n維） （關(guān)系表和電子表格是幾維的？） 示例 AllElectronics的銷售數(shù)據(jù)按維 time, item的 2-D視圖 (P30, 表2-2) AllElectronics的銷售數(shù)據(jù)按維 time, item和 location的 3-D視圖 (P30, 表 2-3) AllElectronics的銷售數(shù)據(jù)按維 time, item和 location的 3-D視圖的 3-D數(shù)據(jù)立方體表示 (P31, 圖 2-1) 銷售數(shù)據(jù)的 4-D立方體表示 (P31, 圖 2-2) 多維數(shù)據(jù)模型為不同角度上的數(shù)據(jù)建模和觀察提供了一個良好的基礎(chǔ) 多維數(shù)據(jù)模型 (4) 在數(shù)據(jù)倉庫的研究文獻(xiàn)中，一個 n維的數(shù)據(jù)的立方體叫做 基本方體 。給定一個維的集合，我們可以構(gòu)造一個 方體的格 ，每個都在不同的匯總級或不同的數(shù)據(jù)子集顯示數(shù)據(jù)，方體的格稱為數(shù)據(jù)立方體 。 0維方體存放最高層的匯總，稱作頂點方體 ；而存放最底層匯總的方體則稱為 基本方體 。 數(shù)據(jù)立方體 一個方體的格 all time item location supplier time,item time,location time,supplier item,location item,supplier location,supplier time,item,location time,item,supplier time,location,supplier item,location,supplier time, item, location, supplier 0-D(頂點 ) 方體 1-D方體 2-D 方體 3-D 方體 4-D(基本 ) 方體 數(shù)據(jù)倉庫的概念模型 最流行的數(shù)據(jù)倉庫概念模型是多維數(shù)據(jù)模型。這種模型可以以星型模式、雪花模式、或事實星座模式的形式存在。 星型模式（ Star schema） : 事實表在中心，周圍圍繞地連接著維表（每維一個），事實表含有大量數(shù)據(jù)，沒有冗余。 雪花模式（ Snowflake schema） : 是星型模式的變種，其中某些維表是規(guī)范化的，因而把數(shù)據(jù)進(jìn)一步分解到附加表中。結(jié)果，模式圖形成類似于雪花的形狀。 事實星座（ Fact constellations） : 多個事實表共享維表 , 這種模式可以看作星型模式集，因此稱為星系模式（ galaxy schema），或者事實星座（ fact constellation） 星型模式實例 time_key day day_of_the_week month quarter year time location_key street city state_or_province country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch 雪花模式實例 time_key day day_of_the_week month quarter year time location_key street city_key location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_key item branch_key branch_name branch_type branch supplier_key supplier_type supplier city_key city state_or_province country city 事實星座模式實例 time_key day day_of_the_week month quarter year time location_key street city province_or_state country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch Shipping Fact Table time_key item_key shipper_key from_location to_location dollars_cost units_shipped shipper_key shipper_name location_key shipper_type shipper 一種數(shù)據(jù)挖掘查詢語言 : DMQL DMQL首先包括定義數(shù)據(jù)倉庫和數(shù)據(jù)集市的語言原語，這包括兩種原語定義：一種是立方體定義，一種是維定義 立方體定義 (事實表 ) define cube : 維定義 (維表 ) define dimension as () 特殊案例 (共享維表的定義 ) 第一次作為維表定義 “ cube definition” 然后： define dimension as in cube 實例：使用 DMQL定義星型模式 define cube sales_star time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city, province_or_state, country) 實例：使用 DMQL定義雪花模式 define cube sales_snowflake time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier(supplier_key, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city(city_key, province_or_state, country) 實例：使用 DMQL定義事實星座模式 define cube sales time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city, province_or_state, country) define cube shipping time, item, shipper, from_location, to_location: dollar_cost = sum(cost_in_dollars), unit_shipped = count(*) define dimension time as time in cube sales define dimension item as item in cube sales define dimension shipper as (shipper_key, shipper_name, location as location in cube sales, shipper_type) define dimension from_location as location in cube sales define dimension to_location as location in cube sales 度量的分類 一個數(shù)據(jù)立方體的度量是一個 數(shù)值 函數(shù)，該函數(shù)可以對數(shù)據(jù)立方體的每一個點求值。 (剛才的示例中用的是什么函數(shù)？ ) 度量可以根據(jù)其所用的聚集函數(shù)分為三類： 分布的 (distributive)：將函數(shù)用于 n個聚集值得到的結(jié)果和將函數(shù)用于所有數(shù)據(jù)得到的結(jié)果一樣。 比如： count()， sum()， min()， max()等 代數(shù)的 (algebraic)：函數(shù)可以由一個帶 M個參數(shù)的代數(shù)函數(shù)計算（ M為有界整數(shù)），而每個參數(shù)值都可以有一個分布的聚集函數(shù)求得。 比如： avg()， min_N()， standard_deviation() 整體的 (holistic)：描述函數(shù)的子聚集所需的存儲沒有一個常數(shù)界。 比如： median()， mode()， rank() 5-6 王 燦 數(shù)據(jù)挖掘 0703004 概念分層 (1) 一個概念分層（ concept hierarchy）定義一個映射序列，將低層概念映射到更一般的高層概念 E.g. 表示 location的概念：杭州 浙江 中國 亞洲 概念分層允許我們在各種抽象級審查和處理數(shù)據(jù) 概念分層可以由系統(tǒng)用戶、領(lǐng)域?qū)＜?、知識工程師人工的提供，也可以根據(jù)數(shù)據(jù)分布的統(tǒng)計分析自動的產(chǎn)生 概念分層 (2): location維的一個概念分層 all Europe North_America Mexico Canada Spain Germany Vancouver M. Wind L. Chan . . . . . . all region office country Toronto Frankfurt city 許多概念分層的定義隱含在數(shù)據(jù)庫的模式中。比如： location維的定義，officebuys(X, Z) X-customer表的關(guān)鍵字 P,Q-謂詞變量 W, Y, Z-對象變量 模板具體化 age(X, 3039) income(X, 40k49k)=buys(X, VCR) 2.2%, 60% occupation(x, student) age(X, 2029)=buys(X, computer) 1.4%, 70% 背景知識：概念分層 背景知識是關(guān)于挖掘領(lǐng)域的知識 概念分層是背景知識的一種，它允許在多個抽象層上發(fā)現(xiàn)知識。 概念分層以樹形結(jié)構(gòu)的節(jié)點集來表示，其中每個節(jié)點本身代表一個概念，根節(jié)點稱為 all，而葉節(jié)點則對應(yīng)于維的原始數(shù)據(jù)值。 概念分層中，自頂向底進(jìn)行層的標(biāo)識，即 all為 0層，向下依次為 1， 2， 3等層 概念分層 上卷和下鉆 在概念分層中應(yīng)用上卷操作（概化），使得用戶可以使用較高層次概念替代較低層次概念 可以在更有意義，更高、更抽象的層次觀察數(shù)據(jù)，從而使發(fā)現(xiàn)的模式更加容易理解。 上卷操作使得數(shù)據(jù)得到壓縮，在這個壓縮的數(shù)據(jù)集上進(jìn)行挖掘可以減少 I/O操作，使得挖掘的效率提高。 概念分層的下鉆操作使用較低層概念代替較高層概念，從而使用戶能夠?qū)^于一般化的數(shù)據(jù)做更詳細(xì)分析。 上卷和下鉆操作讓用戶以不同視圖觀察數(shù)據(jù)，洞察隱藏的數(shù)據(jù)聯(lián)系。 概念分層的自動生成。 在同一個維上，可能根據(jù)用戶的觀點不同，存在多個概念分層。 概念分層的類型 四種常用的概念分層類型 模式分層 E.g., street $250 興趣度度量 沒有興趣度度量，挖掘出來的有用模式，很可能會給淹沒在用戶不感興趣的模式中。 興趣度的客觀度量方法：根據(jù)模式的結(jié)構(gòu)和統(tǒng)計，用一個臨界值來判斷某個模式是不是用戶感興趣的。 常用的四種興趣度的客觀度量： 簡單性 確定性 實用性 新穎性 簡單性和確定性 簡單性 (simplicity) 模式是否容易被人所理解 模式結(jié)構(gòu)的函數(shù)（模式的長度、屬性的個數(shù)、操作符個數(shù)）。e.g. 規(guī)則長度或者判定樹的節(jié)點個數(shù)。 確定性 (certainty) 表示一個模式在多少概率下是有效的。 置信度 (A=B)=(包含 A和 B的元組值 )/(包含 A的元組值 )， e.g. buys(X, computer)=buys(X, software) 30%, 80% 100%置信度：準(zhǔn)確的。 實用性和新穎性 實用性 可以用支持度來進(jìn)行度量：支持度 (A=b) = (包含 A和 B的元組數(shù) )/(元組總數(shù) ) e.g. buys(X, computer)=buys(X, software)30%, 80% 同時滿足最小置信度臨界值和最小支持度臨界值的關(guān)聯(lián)規(guī)則稱為 強關(guān)聯(lián)規(guī)則 。 新穎性 提供新信息或提高給定模式集性能的模式 通過刪除冗余模式來檢測新穎性（一個模式已經(jīng)為另外一個模式所蘊涵） Location(X, Canada)=buys(X, Sony_TV) 8%, 70% Location(X, Vancouver)=buys(X, Sony_TV) 2%, 70% 發(fā)現(xiàn)模式的表示和可視化 以多種形式顯示挖掘出來的模式：表、圖、判定樹、數(shù)據(jù)立方體等等，以適合不同背景的用戶的需要。 使用概念分層，用更有意義，更容易理解的高層概念來替代低層概念；并通過上卷、下鉆等操作從不同的抽象級審視所發(fā)現(xiàn)的模式。 特定知識類型的表示。 一種數(shù)據(jù)挖掘查詢語言 DMQL DMQL的設(shè)計目的 支持特別的和交互的數(shù)據(jù)查詢，以便利于靈活和有效的知識發(fā)現(xiàn) 提供一種類似于 SQL的標(biāo)準(zhǔn)化查詢語言 希望達(dá)到 SQL在關(guān)系數(shù)據(jù)庫中的地位 系統(tǒng)開發(fā)和演化的基礎(chǔ) 方便的信息交互，廣泛的技術(shù)支持，商業(yè)化，廣為認(rèn)可 設(shè)計挑戰(zhàn) 數(shù)據(jù)挖掘任務(wù)涉及面寬 數(shù)據(jù)特征、關(guān)聯(lián)規(guī)則、分類、演變分析 每種任務(wù)都有不同的需求 DMQL的語法 采用與 SQL相類似的語法，便于與 SQL的集成。 允許在多個抽象層上，由關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫進(jìn)行多類型知識的特殊挖掘 DMQL的設(shè)計基于數(shù)據(jù)挖掘原語，相應(yīng)的，其語法中應(yīng)該包括對以下任務(wù)的指定： 說明數(shù)據(jù)庫的部分或用戶感興趣的數(shù)據(jù)集 要挖掘的知識類型 用于指導(dǎo)挖掘的背景知識 模式評估、興趣度量 如何顯示發(fā)現(xiàn)的知識 任務(wù)相關(guān)數(shù)據(jù)說明的語法 任務(wù)相關(guān)數(shù)據(jù)說明應(yīng)包括的內(nèi)容： 包含相關(guān)數(shù)據(jù)的數(shù)據(jù)庫或數(shù)據(jù)倉庫 相關(guān)的表名或數(shù)據(jù)立方體的名字 選擇相關(guān)數(shù)據(jù)的條件 探察的相關(guān)屬性或維 關(guān)于檢索數(shù)據(jù)的排序和分組指令 任務(wù)相關(guān)數(shù)據(jù)說明子句 說明相關(guān)的數(shù)據(jù)庫或數(shù)據(jù)倉庫 use database 或 use data warehouse 指定涉及的表或數(shù)據(jù)立方體，定義檢索條件 From where 列出要探察的屬性或維 In relevance to 相關(guān)數(shù)據(jù)的排序 order by 相關(guān)數(shù)據(jù)的分組 group by 相關(guān)數(shù)據(jù)的分組條件： having 任務(wù)相關(guān)數(shù)據(jù)說明 示例 挖掘加拿大顧客與在 AllElectronics經(jīng)常購買的商品之間的關(guān)聯(lián)規(guī)則 use database AllElectronics_db in relevance to I.name, I.price, C.income, C.age from customer C, item I, purchases P, items_sold S where I.item_ID=S. item_ID and S.trans_ID=P.trans_ID and P.cust_ID=C.cust_ID and C.country=“Canada” group by P.date 指定挖掘知識類型 要挖掘的知識類型將決定所使用的數(shù)據(jù)挖掘功能。 幾種主要的數(shù)據(jù)挖掘功能 特征化 目標(biāo)數(shù)據(jù)的一般特征或特性匯總 數(shù)據(jù)區(qū)分 將目標(biāo)對象的一般特性與一個或多個對比類對象的特性相 比較 關(guān)聯(lián)分析 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，這些規(guī)則展示屬性值頻繁的在給定數(shù)據(jù)中集中一起出現(xiàn)的條件 分類 找出區(qū)分?jǐn)?shù)據(jù)類或概念的模型（或函數(shù)），以便用之標(biāo)志未知的對象類。 聚類分析、孤立點分析、演變分析 指定挖掘知識類型 特征化 目標(biāo)數(shù)據(jù)的一般特征或特性匯總 語法 Mine_Knowledge_Specification := mine characteristics as pattern_name analyze measure(s) analyze子句指定聚集度量（ count, sum, count%），通過這些度量對每個找到的數(shù)據(jù)特征進(jìn)行計算 示例：顧客購買習(xí)慣的特征描述，對于每一特征，顯示滿足特征的任務(wù)相關(guān)元組的百分比 mine characteristics as custPurchasing analyze count