1、數 據 挖 掘概念與技術數據庫與信息系統研究室Tel: Email: Cell Phone: 引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容大批成熟的業務信息系統投入運行信息系統多年運行，積累了海量的數據各類信息系統大多屬于面向事務處理的OLTP系統數據是一種寶貴的資源，但沒有充分發揮作用企業信息化發展現狀我在數據中獲取知識（有益的模式）發展趨勢數據集中化業務綜合化管理“扁平化”決策科學化特點以客戶為中心以服務求發展企業信息化發展趨勢數據處理的發展趨勢（需求與產品）Data MiningDatabase

2、TechnologyStatisticsOtherDisciplinesInformationScienceMachineLearningVisualization數據挖掘多學科交叉的領域引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容什么是數據挖掘？數據挖掘是從大量的數據中抽取出潛在的、不為人知的有用信息、模式和趨勢Jiawei Han(University of Illinois at Urbana-Champaign )數據挖掘不同的術語和定義：data mining, knowledge disco

3、very, pattern discovery數據挖掘知識發現過程（KDD）的核心數據清理：消除噪音或不一致數據數據集成：多種數據源可以組合在一起 數據選擇：從數據庫中提取與分析任務相關的數據數據變換：數據變換或統一成適合挖掘的形式 數據挖掘：基本步驟，使用智能方法提取數據模式模式評估：根據某種興趣度度量，識別提供知識的真正有用的模式知識表示：使用可視化和知識表示技術，向用戶提供挖掘的知識數據挖掘系統分類根據挖掘的數據類型分類根據挖掘的知識類型分類根據所用的挖掘技術分類根據系統的應用領域分類關系數據庫面向對象數據庫文本數據多媒體數據異構數據WWW數據數據挖掘分類數據類型Data Warehou

4、se數據挖掘分類知識類型關聯挖掘序列模式挖掘聚類挖掘分類挖掘孤立點挖掘概化挖掘預測挖掘數據庫技術機器學習技術統計技術神經網絡技術可視化技術數據挖掘分類挖掘技術引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容關聯挖掘序列模式挖掘分類挖掘聚類挖掘孤立點挖掘數據挖掘原理與方法關聯（Association）反映一個事件和其他事件之間依賴或關聯的知識如果兩項或多項屬性之間存在關聯，那么其中一項的屬性值就可以依據其他屬性值進行預測可以用關聯規則的形式表示規則形式： “Body Head support, confide

5、nce”.舉例： contains(T, “computer”) contains(T, “software”) support = 1%, confidence = 75%age(X, “20.29”) income(X, “20.29K”) buys(X, “PC”) 2%, 60%應用：業務相關性分析、交叉銷售、產品目錄設計等關聯規則（一）X Y滿足X中條件的數據庫元組也滿足Y中條件規則興趣度度量支持度置信度強規則同時滿足最小支持度閾值和最小置信度閾值的規則給定: (1)交易數據庫 (2)每筆交易是：一個項目列表 (消費者一次購買活動中購買的商品)查找: 所有描述一個項目集合與其他項目集

6、合相關性的規則E.g., 98% of people who purchase tires and auto accessories also get automotive services done應用* 護理用品 (商店應該怎樣提高護理用品的銷售？)家用電器 * (其他商品的庫存有什么影響?)在產品直銷中使用附加郵寄關聯規則（二）規則度量：支持度與置信度查找所有的規則 X & Y Z 具有最小支持度和可信度支持度 s, 一次交易中包含X 、 Y 、 Z的可能性置信度 c, 包含X 、 Y的交易中也包含Z的條件概率設最小支持度為50%, 最小置信度為 50%, 則可得到A C (50%, 6

7、6.6%)C A (50%, 100%)買尿布的客戶二者都買的客戶買啤酒的客戶關聯規則挖掘方法對于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%最小支持度50%最小置信度 50%找出所有的頻繁項集由頻繁項集產生強關聯規則關鍵步驟：挖掘頻繁集頻繁集:是指滿足最小支持度的項目集合頻繁集的子集也一定是頻繁的如, 如果AB 是頻繁集，則 A B 也一定是頻繁集從1到k（k-頻繁集）遞歸查找頻繁集用得到的頻繁集生成關聯規則Apriori算法連接: 用 Lk-1自連接得到Ck修剪: 一個k-項集

8、，如果他的一個k-1項集（他的子集 ）不是頻繁的，那他本身也不可能是頻繁的。偽代碼:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t

9、 Lk+1 = candidates in Ck+1 with min_support endreturn k Lk;Apriori算法 例子數據庫 D掃描 DC1L1L2C2C2掃描 DC3L3掃描 D（最小支持度為2）如何生成候選集假定 Lk-1 中的項按順序排列第一步: 自連接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 6THEN tenured =

10、yes 模型分類過程 : 使用模型模型測試集未知數據(Jeff, Professor, 4)Tenured?一 個訓 練 集一棵關于“買計算機”的決策樹實例age?overcaststudent?credit rating?noyesfairexcellent40yes31.40nonoyesyes根內部節點葉子分枝分類結果分類比例非空間分類屬性類標號決策樹空間分類屬性分類挖掘實例全國縣經濟狀況空間分類關聯挖掘序列模式挖掘分類挖掘聚類挖掘孤立點挖掘數據挖掘原理與方法聚類（Clustering）最大化類內的相似性、最小化類間相似性的原則進行聚類或者分組，使得在一個類中的對象具有很高的相似性，而與

11、其他類中的對象很不相似簇（Cluster）:一個數據對象的集合在同一個類中，對象之間具有相似性不同類的對象之間是相異的聚類分析：把一個給定的數據對象集合分成不同的簇特點：一種無監督分類法，沒有預先指定的類別有監督和無監督學習有監督學習 (分類)訓練集是帶有類標簽的新的數據是基于訓練集進行分類的無監督學習 (聚集)訓練集是沒有類標簽的提供一組屬性，然后尋找出訓練集中存在類別或者聚集應用聚類分析的例子客戶劃分與市場銷售: 幫助市場人員發現客戶中的不同群體，然后用這些知識來開展一個目標明確的市場計劃；土地使用: 在一個陸地觀察數據庫中標識那些土地使用相似的地區；保險: 對購買了汽車保險的客戶，標識那

12、些有較高平均賠償成本的客戶；城市規劃: 根據類型、價格、地理位置等來劃分不同類型的住宅；什么是一個好的聚類方法?一個好的聚類方法要能產生高質量的聚類結果簇，這些簇要具備以下兩個特點：高的簇內相似性低的簇間相似性 聚類結果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現；聚類方法的好壞還取決與該方法是能發現某些還是所有的隱含模式；聚類實現的一個方法：劃分劃分方法: 將一個包含n個數據對象的數據庫組織成k個劃分（k=n），其中每個劃分代表一個簇（Cluster）。給定一個k，要構造出k個簇，并滿足采用的劃分準則：全局最優:盡可能的列舉所有的劃分；啟發式方法: k-平均和k-中心點算法

13、k-平均 (MacQueen67):由簇的中心來代表簇；k-中心點或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每個簇由簇中的某個數據對象來代表。 K-平均算法012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the clus

14、ter meansreassignreassign聚類數據挖掘實例（1） 關聯挖掘序列模式挖掘分類挖掘聚類挖掘孤立點挖掘數據挖掘原理與方法數據庫中可能包含一些數據對象，它們與數據的一般行為或模型很不一致，這些對象稱作孤立點孤立點包括很多潛在的知識，如分類中的反常實例、不滿足規則的特例、觀測結果與模型預測值的偏差、量值隨時間的變化等孤立點（Outlier）挖掘引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容數據挖掘標準化簡介模型級別XML PMML應用級別XML（JAVA） SOAP數據挖掘與標準化進程CRI

15、SPDM過程標準化（CRoss-Industry Standard Process for Data Mining）XML與數據預處理相結合SOAP（Simple Object Access Protocol ）數據庫與系統互操作的標準PMML預言模型交換標準PMML:預言模型標記語言PMML 標準的由來什么是PMML?PMML的主要目的PMML的內容PMML 標準的由來PMML 最初由NCDM開發 National Center for Data Mining (NCDM) at the University of Illinois at Chicago (UIC) Robert Gross

16、man 1997Grossman,etc: The Management and Mining of Multiple Predictive Models Using the Predictive Modeling Markup Language (PMML), 1999DMG（Data Mining Group）修正和擴充DMG最初成員包括：Angoss, Magnify, NCDM,SPSSPMML1.0在1999年7月由DMG組織發布DMG目的是開發數據挖掘標準目前由9個成員組成：Angoss，IBM，Magnify，NCR，Oracle，SPSS，NCDM，Xchange,MINEit

17、當前PMML最新版本是2.0什么是PMML?（一）定義PMML稱為預言模型標記語言（Predictive Model Markup Language），利用XML描述和存儲數據挖掘模型， 是一個已經被W3C所接受的標準。PMML2.0Tree ModelNaive BayesGeneral RegressionRegression ModelSequencesGeneral StructureAsscocation Rules什么是PMML?（二）PMML的主要目的允許應用程序和聯機分析處理（OLAP）工具能從數據挖掘系統獲得模型，而不用獨自開發數據挖掘模塊 能夠收集使用大量潛在的模型，并且統

18、一管理各種模型的集合 解決目前各數據挖掘系統之間封閉性的問題可以在其它應用系統中間嵌入數據挖掘模型，解決孤立的知識發現問題 引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容數據庫、數據倉庫、或其它信息庫：數據挖掘的數據源，需要在其上進行數據清理和集成數據庫或數據倉庫服務器：根據用戶的數據挖掘請求，數據庫或數據倉庫服務器負責提取相關數據知識庫：存儲面向領域的知識，用于指導搜索，或評估結果模式的興趣度數據挖掘引擎：數據挖掘系統核心部分，由一組功能模塊組成，用于特征、關聯、分類、聚類分析、演變和偏差分析等數據挖掘

19、系統體系結構模式評估模塊：使用興趣度度量，與挖掘模塊交互，以便將搜索聚焦在有趣的模式上可能使用興趣度閾值過濾發現的模式模式評估模塊也可以與挖掘模塊集成在一起，這依賴于所用的數據挖掘方法的實現對于有效的數據挖掘，建議盡可能地將模式評估推進到挖掘過程之中，以便將搜索限制在有興趣的模式上數據挖掘系統體系結構（續一）圖形用戶界面：該模塊在用戶和挖掘系統之間通訊允許用戶與系統交互，指定數據挖掘查詢或任務，提供信息、幫助搜索聚焦，根據數據挖掘的中間結果進行探索式數據挖掘。允許用戶瀏覽數據庫和數據倉庫模式或數據結構，評估挖掘的模式，以不同的形式對模式可視化數據挖掘系統體系結構（續二）引言數據挖掘的概念與分類

20、體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容數據挖掘系統設計中的若干問題挖掘方法與用戶交互問題如何設計覆蓋廣譜的數據分析和知識發現任務多個抽象層的交互知識挖掘如何納入領域知識數據挖掘系統的性能問題算法的有效性和可伸縮性并行、分布和增量挖掘算法與體系挖掘方法與用戶交互問題不同的用戶可能對不同類型的知識感興趣數據挖掘系統應當覆蓋廣譜的數據分析和知識發現任務，包括數據特征、區分、關聯、聚類、趨勢、偏差分析和類似性分析等這些任務可能以不同的方式使用相同的數據庫避免開發單一的挖掘應用，需設計良好的系統可擴展性多個抽象層的交互知識挖掘問題

21、由于很難準確地知道能夠在數據庫中發現什么，數據挖掘過程應當是交互的對于包含大量數據的數據庫，應當使用適當的選樣技術，進行交互式數據探查交互式挖掘允許用戶聚焦搜索模式，根據返回的結果提出和精煉數據挖掘請求特殊地，類似于立方體上的OLAP操作，應當通過交互地在數據空間和知識空間下鉆、上卷和轉軸，挖掘知識。用這種方法，用戶可以與數據挖掘系統交互，以不同的粒度和從不同的角度觀察數據和發現模式納入領域知識的問題結合背景知識：可以使用背景知識或關于所研究領域的信息來指導發現過程，并使得發現的模式以簡潔的形式，在不同的抽象層表示關于數據庫的領域知識，如完整性限制和演繹規則，可以幫助聚焦和加快數據挖掘過程，或

22、評估發現的模式的興趣度挖掘結果的表示問題發現的知識應當用高級語言、可視化表示形式、或其它表示形式表示，使得知識易于理解，能夠直接被人使用如果數據挖掘系統是交互的，這一點尤為重要要求系統采用有表達能力的知識表示技術，如樹、表、圖、圖表、交叉表、矩陣或曲線處理噪音和不完全數據問題存放在數據庫中數據可能反映噪音、例外情況、或不完全的數據對象這些對象可能搞亂分析過程，導致數據與所構造的知識模型過分適應其結果是，所發現的模式的精確性可能很差。需要處理數據噪音的數據清理方法和數據分析方法，以及發現和分析例外情況的孤立點挖掘方法模式評估興趣度問題數據挖掘系統可能發現數以千計的模式對于給定的用戶，許多模式不是

23、有益的，它們表示平凡知識或缺乏新穎性使用興趣度度量，指導發現過程和壓縮搜索空間，是有效篩選有益模式的方法算法的有效性和可伸縮性問題為了有效地從數據庫中大量數據提取信息，數據挖掘算法必須是有效的和可伸縮的對于大型數據庫，數據挖掘算法的運行時間必須是可預計的和可接受的從數據庫角度，有效性和可伸縮性是數據挖掘系統實現的關鍵問題上面討論的挖掘技術和用戶交互的大多數問題，也必須考慮有效性和可伸縮性引言數據挖掘的概念與分類體系數據挖掘的原理與方法數據挖掘的相關國際標準數據挖掘系統結構數據挖掘系統設計中的若干問題數據挖掘新技術主要內容數據挖掘新技術數據流挖掘技術基于數據立方體的挖掘時空數據挖掘技術移動對象挖

24、掘技術Web挖掘技術數據流問題的提出電信領域：電話呼叫記錄分析、網絡管理數據分析金融領域：信用卡交易分析、證券交易分析網絡監測和流量控制Web日志與點擊流分析能源供給部門的能源供給分析天氣預報、地震預測傳感網絡監控 數據流的定義與特點數據流：以順序(ordered)、快速、隨時間變化、可能無法預測并且數量巨大的流的形式連續到達的數據序列： 特點大量、連續到達的數據，可能無限快速變化，需要快速、實時響應單次線性掃描算法，隨機訪問代價太高只能存儲數據的匯總或提綱（synopsis）低層次、多維數據，需要多層次、多維處理數據流研究中的主要問題數據流查詢技術當前焦點，主要是連續查詢（continuou

25、s query）查詢語言、查詢計劃、近似查詢回答技術等 數據流分析技術傳統的統計分析，已比較成熟結合數據倉庫與OLAP技術的多維多層次分析數據流挖掘數據流管理系統查詢處理、資源管理、存儲實現等DBMS與DSMS的比較DBMS DSMS 持久關系 臨時數據流 一次查詢（one-time query） 連續查詢（continuous query） 隨機訪問 順序訪問（sequential access） “極大的”（unbounded）磁盤存儲 有限的（bounded）主存 僅是當前狀態事務 歷史數據是重要的 沒有實時服務 實時服務需求 相當低的更新率 可能多GB的到達率 任何粒度層次的數據 精粒

26、度層次的數據 采取精確數據形式 數據是不精確的 準確的查詢回答 近似回答 通過查詢處理器、物理數據庫設計決定訪問計劃 不可預測的、易變的數據到達情況和特征 數據流處理的挑戰多個、連續、快速、時變、有序的數據流主存計算查詢經常是連續的數據到來時的連續估計隨時間更新的查詢結果查詢經常是復雜的超越了“一次一成員”（element-at-a-time）的處理方式超越了“一次個流”（stream-at-a-time）的處理方式超越了關系查詢（科學數據庫、數據挖掘、OLAP）多層次/多維處理和數據挖掘絕大多數流數據是相當低層的、多維的數據挖掘新技術數據流挖掘技術基于數據立方體的挖掘時空數據挖掘技術移動對象

27、挖掘技術Web挖掘技術根據用戶的交互，系統自動完成用戶的OLAP分析需求根據用戶的交互，系統自動調整挖掘角度和策略基于數據立方體的挖掘用戶期望什么？如何使分析更簡單、更高效？DSS的分析工具OLAPDataMining既有用戶的參與又有系統的自動發現兩者的無縫聯接與融合提供功能更強、操作更方便的分析分析更簡單更高效假定驅動與發現驅動假定驅動的探查(hypothesis-driven exploration)用戶通過使用下鉆、上卷、切片、切塊等OLAP操作，檢索方中感興趣的模式盡管這些工具可以用于幫助用戶探查數據，但這一過程不是自動的用戶根據他的直觀和假定，試圖去識別數據中的例外和異常缺點：搜索空間非常大，容易忽略有益的模式發現驅動的探查(discovery-driven exploration)將挖掘引入立方體集成的OLAM和OLAP結構數據挖掘新技術數據流挖掘技術基于數據立方體的挖掘時空數據挖掘技術移動對象挖掘技術Web挖掘技術時空數據挖掘時空數據挖掘是一種非平凡的從大型時空數據庫中進行隱