數(shù)據(jù)挖掘考試復習大綱

1、數(shù)據(jù)挖掘期末復習第一章、數(shù)據(jù)挖掘概論數(shù)據(jù)挖掘: 數(shù)據(jù)庫中的知識挖掘(KDD)q數(shù)據(jù)挖掘知識挖掘的核心數(shù)據(jù)清理數(shù)據(jù)清理數(shù)據(jù)集成數(shù)據(jù)集成數(shù)據(jù)庫數(shù)據(jù)庫數(shù)據(jù)倉庫數(shù)據(jù)倉庫任務相關(guān)數(shù)據(jù)任務相關(guān)數(shù)據(jù)選擇選擇數(shù)據(jù)挖掘數(shù)據(jù)挖掘模式評估模式評估知識挖掘的步驟n了解應用領域q了解相關(guān)的知識和應用的目標n創(chuàng)建目標數(shù)據(jù)集: 選擇數(shù)據(jù)n數(shù)據(jù)清理和預處理: (這個可能要占全過程60的工作量)n數(shù)據(jù)縮減和變換q找到有用的特征，維數(shù)縮減/變量縮減，不變量的表示。n選擇數(shù)據(jù)挖掘的功能 q數(shù)據(jù)總結(jié), 分類模型數(shù)據(jù)挖掘, 回歸分析, 關(guān)聯(lián)規(guī)則挖掘, 聚類分析等.n選擇挖掘算法n數(shù)據(jù)挖掘: 尋找感興趣的模式n模式評估和知識表示q可視化

2、，轉(zhuǎn)換，消除冗余模式等等n運用發(fā)現(xiàn)的知識體系結(jié)構(gòu):典型數(shù)據(jù)挖掘系統(tǒng)數(shù)據(jù)倉庫數(shù)據(jù)倉庫數(shù)據(jù)清洗數(shù)據(jù)清洗過濾過濾數(shù)據(jù)庫數(shù)據(jù)庫數(shù)據(jù)庫或數(shù)據(jù)倉庫服務器數(shù)據(jù)挖掘引擎模式評估圖形用戶界面知識庫數(shù)據(jù)集成數(shù)據(jù)集成數(shù)據(jù)挖掘的主要功能n概念/類描述: 特性化和區(qū)分q歸納，總結(jié)和對比數(shù)據(jù)的特性。n關(guān)聯(lián)分析q發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則，這些規(guī)則展示屬性值頻繁的在給定的數(shù)據(jù)中所一起出現(xiàn)的條件。n分類和預測 q通過構(gòu)造模型 (或函數(shù))用來描述和區(qū)別類或概念，用來預測類型標志未知的對象類。n聚類分析q將類似的數(shù)據(jù)歸類到一起，形成一個新的類別進行分析。n孤立點分析q通常孤立點被作為“噪音”或異常被丟棄，但在欺騙檢測中卻可以通過對罕

3、見事件進行孤立點分析而得到結(jié)論。n趨勢和演變分析q描述行為隨時間變化的對象的發(fā)展規(guī)律或趨勢數(shù)據(jù)挖掘:多個學科的融合數(shù)據(jù)挖掘數(shù)據(jù)庫系統(tǒng)統(tǒng)計學其他學科算法機器學習可視化數(shù)據(jù)挖掘的主要問題n挖掘方法 q在不同的數(shù)據(jù)類型中挖掘不同類型的知識, e.g., 生物數(shù)據(jù), 流式數(shù)據(jù), Web數(shù)據(jù)q性能性能: 算法的有效性、可伸縮性和并行處理算法的有效性、可伸縮性和并行處理q模式評估: 興趣度問題q背景知識的合并q處理噪聲何不完全數(shù)據(jù)q并行, 分布式和增量挖掘算法q新發(fā)現(xiàn)知識與已有知識的集成: 知識融合 n用戶交互q數(shù)據(jù)挖掘查詢語言和特定的數(shù)據(jù)挖掘q數(shù)據(jù)挖掘結(jié)果的表示和顯示q多個抽象層的交互知識挖掘n應用和社

4、會因素q特定域的數(shù)據(jù)挖掘 & 不可視的數(shù)據(jù)挖掘q數(shù)據(jù)安全,完整和保密的保護第二章、數(shù)據(jù)倉庫和OLAP技術(shù)什么是數(shù)據(jù)倉庫? p67n數(shù)據(jù)倉庫的定義很多，但卻很難有一種嚴格的定義q它是一個提供決策支持功能的數(shù)據(jù)庫，它與公司的操作數(shù)據(jù)庫分開維護。 q為統(tǒng)一的歷史數(shù)據(jù)分析提供堅實的平臺，對信息處理提供支持n“數(shù)據(jù)倉庫是一個面向主題的、集成的、隨時間而變化的、不容易丟失的數(shù)據(jù)集合，支持管理部門的決策過程.”W. H. Inmon（數(shù)據(jù)倉庫構(gòu)造方面的領頭設計師）n建立數(shù)據(jù)倉庫(data warehousing):q構(gòu)造和使用數(shù)據(jù)倉庫的過程。數(shù)據(jù)倉庫與異種數(shù)據(jù)庫集成 p68n傳統(tǒng)的異種數(shù)據(jù)庫集成:

5、q在多個異種數(shù)據(jù)庫上建立包裝程序（wrappers）和中介程序（mediators ）q查詢驅(qū)動方法當從客戶端傳過來一個查詢時，首先使用元數(shù)據(jù)字典將查詢轉(zhuǎn)換成相應異種數(shù)據(jù)庫上的查詢；然后，將這些查詢映射和發(fā)送到局部查詢處理器q缺點：復雜的信息過慮和集成處理，競爭資源n數(shù)據(jù)倉庫: 更新驅(qū)動q將來自多個異種源的信息預先集成，并存儲在數(shù)據(jù)倉庫中，供直接查詢和分析q高性能OLTP系統(tǒng)和OLAP系統(tǒng)的比較 p69特征特征OLTPOLAP任務特點任務特點操作處理信息處理面向面向事務分析用戶用戶辦事員、DBA、數(shù)據(jù)庫專業(yè)人員經(jīng)理、主管、數(shù)據(jù)分析員功能功能日常操作長期信息分析、決策支持DB設計設計基于E-R，

6、面向應用星型/雪花，面向主體數(shù)據(jù)數(shù)據(jù)最新的、詳細的歷史的、匯總的視圖視圖詳細的、二維關(guān)系型匯總的、多維的任務單位任務單位簡短的事務復雜的查詢訪問數(shù)據(jù)量訪問數(shù)據(jù)量數(shù)十個數(shù)百萬個用戶數(shù)用戶數(shù)數(shù)千個數(shù)百個DB規(guī)模規(guī)模100M-數(shù)GB100GB-數(shù)TB優(yōu)先性優(yōu)先性高性能、高可用性高靈活性、端點用戶自治度量度量事務吞吐量查詢吞吐量、響應時間從關(guān)系表和電子表格到數(shù)據(jù)立方體 p70n數(shù)據(jù)倉庫和數(shù)據(jù)倉庫技術(shù)基于多維數(shù)據(jù)模型多維數(shù)據(jù)模型。這個模型把數(shù)據(jù)看作是數(shù)據(jù)立方體數(shù)據(jù)立方體形式。多維數(shù)據(jù)模型圍繞中心主題組織，該主題用事實表事實表表示。事實事實是數(shù)值度量的。n數(shù)據(jù)立方體數(shù)據(jù)立方體允許以多維數(shù)據(jù)建模和觀察。它由

7、維維和事實事實定義。n維維是關(guān)于一個組織想要記錄的視角或觀點。每個維都有一個表與之相關(guān)聯(lián)，稱為維表維表。n事實表事實表包括事實的名稱或度量以及每個相關(guān)維表的關(guān)鍵字n在數(shù)據(jù)倉庫的研究文獻中，一個n維的數(shù)據(jù)的立方體叫做基本方體基本方體。給定一個維的集合，我們可以構(gòu)造一個方體的格方體的格，每個都在不同的匯總級或不同的數(shù)據(jù)子集顯示數(shù)據(jù)，方體的格稱為數(shù)據(jù)立方體數(shù)據(jù)立方體。0維方體存放最高層的匯總，稱作頂點方體頂點方體；而存放最底層匯總的方體則稱為基本方體基本方體。度量的分類 p76n一個數(shù)據(jù)立方體的度量是一個數(shù)值函數(shù)，該函數(shù)可以對數(shù)據(jù)立方體的每一個點求值。度量可以根據(jù)其所用的聚集函數(shù)分為三類：q分布的(

8、distributive)：將函數(shù)用于n個聚集值得到的結(jié)果和將函數(shù)用于所有數(shù)據(jù)得到的結(jié)果一樣。n比如：count()，sum()，min()，max()等q代數(shù)的(algebraic)：函數(shù)可以由一個帶M個參數(shù)的代數(shù)函數(shù)計算（M為有界整數(shù)），而每個參數(shù)值都可以有一個分布的聚集函數(shù)求得。n比如：avg()，min_N()，standard_deviation()q整體的(holistic)：描述函數(shù)的子聚集所需的存儲沒有一個常數(shù)界。n比如：median()，mode()，rank()概念分層：location維的一個概念分層 p77allEuropeNorth_AmericaMexicoCana

9、daSpainGermanyVancouverM. WindL. Chan.allregionofficecountryTorontoFrankfurtcity多維數(shù)據(jù)模型上的OLAP操作 79n上卷(roll-up):匯總數(shù)據(jù)q通過一個維的概念分層向上攀升或者通過維規(guī)約n下鉆(drill-down)：上卷的逆操作q由不太詳細的數(shù)據(jù)到更詳細的數(shù)據(jù)，可以通過沿維的概念分層向下或引入新的維來實現(xiàn)n切片和切塊(slice and dice)q投影和選擇操作n轉(zhuǎn)軸(pivot)q立方體的重定位，可視化，或?qū)⒁粋€3維立方體轉(zhuǎn)化維一個2維平面序列n其他OLAP操作q鉆過(drill_across)：執(zhí)行涉

10、及多個事實表的查詢q鉆透(drill_through)：使用關(guān)系SQL機制，鉆到數(shù)據(jù)立方體的底層，到后端關(guān)系表數(shù)據(jù)倉庫設計的四種視圖 82n數(shù)據(jù)倉庫設計的四種視圖q自頂向下視圖n允許我們選擇數(shù)據(jù)倉庫所需的相關(guān)信息q數(shù)據(jù)源視圖n揭示被操作數(shù)據(jù)庫系統(tǒng)所捕獲、存儲和管理的信息q數(shù)據(jù)倉庫視圖n有事實表和維表所組成q商務查詢視圖n從最終用戶的角度透視數(shù)據(jù)倉庫中的數(shù)據(jù)三種數(shù)據(jù)倉庫模型 84n企業(yè)倉庫q搜集關(guān)于跨越整個組織的主題的所有信息n數(shù)據(jù)集市q企業(yè)范圍數(shù)據(jù)的一個子集，對于特定的客戶是有用的。其范圍限于選定的主題，比如一個商場的數(shù)據(jù)集市n獨立的數(shù)據(jù)集市 VS. 非獨立的數(shù)據(jù)集市（數(shù)據(jù)來自于企業(yè)數(shù)據(jù)倉庫）

11、n虛擬倉庫q操作數(shù)據(jù)庫上的一系列視圖q只有一些可能的匯總視圖被物化OLAP服務器類型 86n邏輯上，OLAP服務器從數(shù)據(jù)倉庫或數(shù)據(jù)集市中給商業(yè)用戶提供多維數(shù)據(jù)n物理上，OLAP的底層數(shù)據(jù)存儲實現(xiàn)可以有多種不同的方式q關(guān)系OLAP服務器(ROLAP)n使用關(guān)系數(shù)據(jù)庫或擴展的關(guān)系數(shù)據(jù)庫存放并管理數(shù)據(jù)倉庫的數(shù)據(jù)，而用OLAP中間件支持其余部分n包括每個DBMS后端優(yōu)化，聚集導航邏輯的實現(xiàn)，附加的工具和服務n較大的可擴展性q多維OLAP服務器(MOLAP)n基于數(shù)組的多維存儲引擎（稀疏矩陣技術(shù)）n能對預計算的匯總數(shù)據(jù)快速索引q混合OLAP服務器(HOLAP)n結(jié)合上述兩種技術(shù)，更大的使用靈活性q特殊的

12、SQL服務器n在星型和雪花模型上支持SQL查詢方體計算的多路數(shù)組聚集方法(1)n將數(shù)組分成塊（chunk,一個可以裝入內(nèi)存的小子方）n壓縮的稀疏數(shù)組尋址：(chunk_id, offset)n通過訪問立方體單元，計算聚集?？梢詢?yōu)化訪問單元組的次序，使得每個單元被訪問的次數(shù)最小化，從而減少內(nèi)存訪問和磁盤I/O的開銷。A(month)B29303132123459131415166463626148474645a1a0c3c2c1c 0b3b2b1b0a2a3C(item)B(city)442856402452362060哪個是多路數(shù)組哪個是多路數(shù)組聚集的最佳遍歷聚集的最佳遍歷次序？次序？第三章、

13、數(shù)據(jù)預處理為什么要預處理數(shù)據(jù)？n現(xiàn)實世界的數(shù)據(jù)是“骯臟的”q不完整的：有些感興趣的屬性缺少屬性值，或僅包含聚集數(shù)據(jù)q含噪聲的：包含錯誤或者“孤立點”q不一致的：在編碼或者命名上存在差異n沒有高質(zhì)量的數(shù)據(jù)，就沒有高質(zhì)量的挖掘結(jié)果q高質(zhì)量的決策必須依賴高質(zhì)量的數(shù)據(jù)q數(shù)據(jù)倉庫需要對高質(zhì)量的數(shù)據(jù)進行一致地集成數(shù)據(jù)預處理的主要任務 p31n數(shù)據(jù)清理q填寫空缺的值，平滑噪聲數(shù)據(jù)，識別、刪除孤立點，解決不一致性n數(shù)據(jù)集成q集成多個數(shù)據(jù)庫、數(shù)據(jù)立方體或文件n數(shù)據(jù)變換q規(guī)范化和聚集n數(shù)據(jù)歸約q得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果q數(shù)據(jù)離散化n數(shù)據(jù)歸約的一部分，通過概念分層和數(shù)據(jù)的離散化來規(guī)

14、約數(shù)據(jù)，對數(shù)字型數(shù)據(jù)特別重要如何處理空缺值 39n忽略元組：當類標號缺少時通常這么做（假定挖掘任務設計分類或描述），當每個屬性缺少值的百分比變化很大時，它的效果非常差。n人工填寫空缺值：工作量大，可行性低n使用一個全局變量填充空缺值：比如使用unknown或-n使用屬性的平均值填充空缺值n使用與給定元組屬同一類的所有樣本的平均值n使用最可能的值填充空缺值：使用像Bayesian公式或判定樹這樣的基于推斷的方法噪聲數(shù)據(jù) p40n噪聲：一個測量變量中的隨機錯誤或偏差n引起不正確屬性值的原因q數(shù)據(jù)收集工具的問題q數(shù)據(jù)輸入錯誤q數(shù)據(jù)傳輸錯誤q技術(shù)限制q命名規(guī)則的不一致n其它需要數(shù)據(jù)清理的數(shù)據(jù)問題q重復

15、記錄q不完整的數(shù)據(jù)q不一致的數(shù)據(jù)如何處理噪聲數(shù)據(jù) p40 n分箱(binning):q首先排序數(shù)據(jù)，并將他們分到等深的箱中q然后可以按箱的平均值平滑、按箱中值平滑、按箱的邊界平滑等等n聚類：q監(jiān)測并且去除孤立點n計算機和人工檢查結(jié)合q計算機檢測可疑數(shù)據(jù)，然后對它們進行人工判斷n回歸q通過讓數(shù)據(jù)適應回歸函數(shù)來平滑數(shù)據(jù)數(shù)據(jù)變換 45n平滑：去除數(shù)據(jù)中的噪聲 （分箱、聚類、回歸）n聚集：匯總，數(shù)據(jù)立方體的構(gòu)建n數(shù)據(jù)概化：沿概念分層向上匯總n規(guī)范化：將數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間q最小最大規(guī)范化qz-score規(guī)范化q小數(shù)定標規(guī)范化n屬性構(gòu)造q通過現(xiàn)有屬性構(gòu)造新的屬性，并添加到屬性集中；以

16、增加對高維數(shù)據(jù)的結(jié)構(gòu)的理解和精確度數(shù)據(jù)歸約策略 47n數(shù)據(jù)倉庫中往往存有海量數(shù)據(jù)，在其上進行復雜的數(shù)據(jù)分析與挖掘需要很長的時間n數(shù)據(jù)歸約q數(shù)據(jù)歸約可以用來得到數(shù)據(jù)集的歸約表示，它小得多，但可以產(chǎn)生相同的（或幾乎相同的）分析結(jié)果n數(shù)據(jù)歸約策略q數(shù)據(jù)立方體聚集q維歸約q數(shù)據(jù)壓縮q數(shù)值歸約q離散化和概念分層產(chǎn)生n用于數(shù)據(jù)歸約的時間不應當超過或“抵消”在歸約后的數(shù)據(jù)上挖掘節(jié)省的時間。分類數(shù)據(jù)的概念分層生成 p56n分類數(shù)據(jù)是指無序的離散數(shù)據(jù)，它有有限個值（可能很多個）。n分類數(shù)據(jù)的概念分層生成方法：q由用戶或?qū)＜以谀Ｊ郊夛@式的說明屬性的部分序。q通過顯示數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分。q說明屬性集，但不

17、說明它們的偏序，然后系統(tǒng)根據(jù)算法自動產(chǎn)生屬性的序，構(gòu)造有意義的概念分層。q對只說明部分屬性集的情況，則可根據(jù)數(shù)據(jù)庫模式中的數(shù)據(jù)語義定義對屬性的捆綁信息，來恢復相關(guān)的屬性。第四章、數(shù)據(jù)挖掘原語和DMQL數(shù)據(jù)挖掘原語的組成部分n數(shù)據(jù)挖掘原語應該包括以下部分：q說明數(shù)據(jù)庫的部分或用戶感興趣的數(shù)據(jù)集q要挖掘的知識類型q用于指導挖掘的背景知識q模式評估、興趣度量q如何顯示發(fā)現(xiàn)的知識n數(shù)據(jù)挖掘原語用于用戶和數(shù)據(jù)挖掘系統(tǒng)通信，讓用戶能從不同的角度和深度審查和發(fā)現(xiàn)結(jié)果，并指導挖掘過程。說明數(shù)據(jù)挖掘任務的原語n任務相關(guān)的數(shù)據(jù)q數(shù)據(jù)庫（倉庫）名、數(shù)據(jù)立方體、選擇條件、相關(guān)屬性、分組條件n挖掘的知識類型q特征化、區(qū)

18、分、關(guān)聯(lián)、分類/預測、聚類n背景知識q概念分層，關(guān)聯(lián)的確信度n模式興趣度度量q簡單性、確定性、實用性、新穎性n發(fā)現(xiàn)模式的可視化q規(guī)則、表、圖表、圖、判定樹興趣度度量n沒有興趣度度量，挖掘出來的有用模式，很可能會給淹沒在用戶不感興趣的模式中。q簡單性q確定性q實用性q新穎性n興趣度的客觀度量方法：根據(jù)模式的結(jié)構(gòu)和統(tǒng)計，用一個臨界值來判斷某個模式是不是用戶感興趣的。第五章、特征化和比較兩種不同類別的數(shù)據(jù)挖掘n從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描述性挖掘和預測性挖掘q描述性挖掘：以簡潔概要的方式描述數(shù)據(jù)，并提供數(shù)據(jù)的有趣的一般性質(zhì)。q預測性數(shù)據(jù)挖掘：通過分析數(shù)據(jù)建立一個或一組模型，并試圖預測新數(shù)據(jù)

19、集的行為。什么是概念描述？n描述性挖掘 VS. 預測性挖掘q描述性挖掘：以簡潔概要的方式描述數(shù)據(jù)，并提供數(shù)據(jù)的有趣的一般性質(zhì)。q預測性數(shù)據(jù)挖掘：通過分析數(shù)據(jù)建立一個或一組模型，并試圖預測新數(shù)據(jù)集的行為。n概念描述：為數(shù)據(jù)的特征化和比較產(chǎn)生描述（當所描述的概念所指的是一類對象時，也稱為類描述類描述）q特征化：提供給定數(shù)據(jù)集的簡潔匯總。q區(qū)分：提供兩個或多個數(shù)據(jù)集的比較描述。數(shù)據(jù)概化n數(shù)據(jù)概化q數(shù)據(jù)庫中的數(shù)據(jù)和對象通常包含原始概念層的細節(jié)信息，數(shù)據(jù)概化就是將數(shù)據(jù)庫中的跟任務相關(guān)的數(shù)據(jù)集從較低的概念層抽象到較高的概念層的過程。n主要方法：q數(shù)據(jù)立方體（OLAP使用的方法）q面向?qū)傩缘臍w納方法1234

20、5概念層面向?qū)傩缘臍w納nAttribute-oriented induction, AOI (KDD 89 Workshop)n受數(shù)據(jù)類型和度量類型的約束比較少n面向?qū)傩詺w納的基本思想：q使用關(guān)系數(shù)據(jù)庫查詢收集任務相關(guān)的數(shù)據(jù)q通過考察任務相關(guān)數(shù)據(jù)中每個屬性的不同值的個數(shù)進行概化，方法是屬性刪除或者是屬性概化q通過合并相等的，概化的廣義元組，并累計他們對應的計數(shù)值進行聚集操作q通過與用戶交互，將廣義關(guān)系以圖表或規(guī)則等形式，提交給用戶面向?qū)傩缘臍w納的基本步驟n數(shù)據(jù)聚焦，獲得初始工作關(guān)系n進行面向?qū)傩缘臍w納q基本操作是數(shù)據(jù)概化，對有大量不同值的屬性大量不同值的屬性，進行進一步概化n屬性刪除n屬性概化

21、q屬性概化控制：控制概化過程，確定有多少不同的值才算是有大量不同值的屬性大量不同值的屬性n屬性概化臨界值控制n概化關(guān)系臨界值控制概念描述的屬性相關(guān)分析步驟 (1)n數(shù)據(jù)收集q通過查詢處理，收集目標類和對比類數(shù)據(jù)n使用保守的AOI進行預相關(guān)分析q識別屬性和維的集合，它們是所選擇的相關(guān)性分析度量的應用對象q因為不同的概念層對某個類描述的相關(guān)性可能很不同，因此在這個過程中同時要包含概念分層q對有大量不同值的屬性進行刪除或概化q在這一級進行概化時，臨界值要相應比較高，以便在后續(xù)步驟的分析中包含更多屬性（保守的）q產(chǎn)生候選關(guān)系概念描述的屬性相關(guān)分析步驟 (2)n使用選定的相關(guān)分析度量刪除不相關(guān)和弱相關(guān)的

22、屬性q使用選定的相關(guān)分析度量（e.g.信息增益），評估候選關(guān)系中的每個屬性q根據(jù)所計算的相關(guān)性對屬性進行排序q低于臨界值的不相關(guān)和弱相關(guān)的屬性被刪除q產(chǎn)生初始目標類工作關(guān)系（或初始對比類工作關(guān)系）n使用AOI產(chǎn)生概念描述q使用一組不太保守的屬性概化臨界值進行AOI挖掘類比較：區(qū)分不同的類n類比較挖掘的目標是得到將目標類與對比類相區(qū)分的描述。q目標類和對比類間必須具有可比性，即兩者間要有相似的屬性或維。n本科生 VS. 研究生；student VS. addressn很多應用于概念描述的技巧可以應用于類比較，比如屬性概化。q屬性概化必須在所有比較類上同步進行，將屬性概化到同一抽象層后進行比較。n

23、City VS country類比較的過程 136n數(shù)據(jù)收集q通過查詢處理收集數(shù)據(jù)庫中相關(guān)的數(shù)據(jù)，并將其劃分為一個目標類和一個或多個對比類n維相關(guān)分析q使用屬性相關(guān)分析方法，使我們的任務中僅包含強相關(guān)的維n同步概化q同步的在目標類和對比類上進行概化，得到主目標類關(guān)系主目標類關(guān)系/方體方體 和 主對比類關(guān)系主對比類關(guān)系/方體方體n導出比較的表示q用可視化技術(shù)表達類比較描述，通常會包含“對比”度量，反映目標類與對比類間的比較 (e.g count%)在大型數(shù)據(jù)庫中挖掘描述統(tǒng)計計量n對于數(shù)據(jù)挖掘任務，用戶經(jīng)常關(guān)心的數(shù)據(jù)特征包括數(shù)據(jù)的中心趨勢和離散特征q中心趨勢的度量包括：mean, median,

24、mode 和 midrangeq數(shù)據(jù)離散度量包括：quartiles, 五數(shù)概括和標準差等q關(guān)系數(shù)據(jù)庫中，系統(tǒng)提供了以下聚集函數(shù)：count(), sum(), avg(), max(), min()q在大型數(shù)據(jù)庫中挖掘用戶感興趣的描述統(tǒng)計計量涉及到如何利用關(guān)系數(shù)據(jù)庫現(xiàn)有的函數(shù)來計算上述兩類用戶感興趣的度量值第六章、關(guān)聯(lián)規(guī)則挖掘什么是關(guān)聯(lián)規(guī)則挖掘？n關(guān)聯(lián)規(guī)則挖掘：q從事務數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。n應用：q購物籃分析、分類設計、捆綁銷售和虧本銷售分析關(guān)聯(lián)規(guī)則：基本概念n給定：q項的集合：I=i1,i2,.,inq任務相關(guān)數(shù)據(jù)

25、D是數(shù)據(jù)庫事務的集合，每個事務T則是項的集合，使得q每個事務由事務標識符TID標識；qA,B為兩個項集，事務T包含A當且僅當n則關(guān)聯(lián)規(guī)則是如下蘊涵式：q其中 并且 ，規(guī)則 在事務集D中成立，并且具有支持度s和置信度cIT TA , csBA IBIA , BABA Apriori算法nApriori算法利用頻繁項集性質(zhì)的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。q先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。nA

26、priori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。（ 模式不可能比A更頻繁的出現(xiàn)）qApriori算法是反單調(diào)的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。BAApriori算法步驟nApriori算法由連接連接和剪枝剪枝兩個步驟組成。n連接：連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選候選k項集項集記為Ck。qLk-1中的兩個元素L1和L2可以執(zhí)行連接操作 的條件是n剪枝：剪枝： Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度來得到Lk 。

27、q為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsup

28、A, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2使用Apiori性質(zhì)由L2產(chǎn)生C3n1 連接：qC3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,En2使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：qA,B,C的2項子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以刪除這個選項；qA,C,E的2項子集是A,C,A,E,C,E

29、，其中A,E 不是L2的元素，所以刪除這個選項；qB,C,E的2項子集是B,C,B,E,C,E，它的所有2項子集都是L2的元素，因此保留這個選項。n3這樣，剪枝后得到C3=B,C,E多層關(guān)聯(lián)一致支持度 VS. 遞減支持度n一致支持度：對所有層都使用一致的最小支持度q優(yōu)點：搜索時容易采用優(yōu)化策略，即一個項如果不滿足最小支持度，它的所有子項都可以不用搜索q缺點：最小支持度值設置困難n太高：將丟掉出現(xiàn)在較低抽象層中有意義的關(guān)聯(lián)規(guī)則n太低：會在較高層產(chǎn)生太多的無興趣的規(guī)則n遞減支持度：在較低層使用遞減的最小支持度q抽象層越低，對應的最小支持度越小Computer support=10%Laptopsu

30、pport=6%Desktopsupport=4%min_sup = 5%min_sup = 5%min_sup = 3%多層關(guān)聯(lián)搜索策略n具有遞減支持度的多層關(guān)聯(lián)規(guī)則的搜索策略q逐層獨立：完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝q層交叉單項過濾：一個第i層的項被考察，當且僅當它在第（i-1）層的父節(jié)點是頻繁的（圖6-14）q層交叉k項集過濾：一個第i層的k項集被考察，當且僅當它在第(i-1)層的對應父節(jié)點k-項集是頻繁的（圖6-15）n搜索策略比較q逐層獨立策略條件松，可能導致底層考察大量非頻繁項q層交叉k項集過濾策略限制太強，僅允許考察頻繁k-項集的子女q層交叉單項過濾策略是上述兩者

31、的折中，但仍可能丟失低層頻繁項（圖6-14)關(guān)聯(lián)規(guī)則的興趣度度量n客觀度量q兩個流行的度量指標n支持度n置信度n主觀度量q最終，只有用戶才能確定一個規(guī)則是否有趣的，而且這種判斷是主觀的，因不同的用戶而異；通常認為一個規(guī)則（模式）是有趣的，如果：n它是出人意料的n可行動的（用戶可以使用該規(guī)則做某些事情）n挖掘了關(guān)聯(lián)規(guī)則后，哪些規(guī)則是用戶感興趣的？強關(guān)聯(lián)規(guī)則是否就是有趣的？第七章、分類和預測分類 VS. 預測n分類：q預測分類標號（或離散值）q根據(jù)訓練數(shù)據(jù)集和類標號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)n預測：q建立連續(xù)函數(shù)值模型，比如預測空缺值n典型應用q信譽證實q目標市場q醫(yī)療診斷q性

32、能預測數(shù)據(jù)分類一個兩步過程n第一步，建立一個模型，描述預定數(shù)據(jù)類集和概念集q假定每個元組屬于一個預定義的類，由一個類標號屬性確定q基本概念n訓練數(shù)據(jù)集訓練數(shù)據(jù)集：由為建立模型而被分析的數(shù)據(jù)元組形成n訓練樣本訓練樣本：訓練數(shù)據(jù)集中的單個樣本（元組）q學習模型可以用分類規(guī)則、判定樹或數(shù)學公式的形式提供n第二步，使用模型，對將來的或未知的對象進行分類q首先評估模型的預測準確率n對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較n模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比n測試集要獨立于訓練樣本集，否則會出現(xiàn)“過分適應數(shù)據(jù)”的情況有指導的學習 VS. 無指導的學習n有指導的學

33、習（用于分類）q模型的學習在被告知每個訓練樣本屬于哪個類的“指導”下進行q新數(shù)據(jù)使用訓練數(shù)據(jù)集中得到的規(guī)則進行分類n無指導的學習（用于聚類）q每個訓練樣本的類編號是未知的，要學習的類集合或數(shù)量也可能是事先未知的q通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類比較分類方法n使用下列標準比較分類和預測方法q預測的準確率：模型正確預測新數(shù)據(jù)的類編號的能力q速度：產(chǎn)生和使用模型的計算花銷q健壯性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預測的能力q可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建模型的能力可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建模型的能力q可解釋性：學習模型提供的理解和洞察的層次用判定樹歸納分類n什么是判

34、定樹？q類似于流程圖的樹結(jié)構(gòu)q每個內(nèi)部節(jié)點表示在一個屬性上的測試q每個分枝代表一個測試輸出q每個樹葉節(jié)點代表類或類分布n判定樹的生成由兩個階段組成q判定樹構(gòu)建n開始時，所有的訓練樣本都在根節(jié)點n遞歸的通過選定的屬性，來劃分樣本 （必須是離散值）q樹剪枝n許多分枝反映的是訓練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝n判定樹的使用：對未知樣本進行分類q通過將樣本的屬性值與判定樹相比較貝葉斯分類n貝葉斯分類利用統(tǒng)計學中的貝葉斯定理，來預測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。n樸素貝葉斯分類：假設每個屬性之間都是相互獨立的，并且每個屬性對非類問題產(chǎn)生的影響都是一樣

35、的。)()()|()|(DPhPhDPDhP后向傳播分類n后向傳播是一種神經(jīng)網(wǎng)絡學習算法；神經(jīng)網(wǎng)絡是一組連接的輸入/輸出單元，每個連接都與一個權(quán)相連。在學習階段，通過調(diào)整神經(jīng)網(wǎng)絡的權(quán)，使得能夠預測輸入樣本的正確標號來學習。n優(yōu)點q預測精度總的來說較高q健壯性好，訓練樣本中包含錯誤時也可正常工作q輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值q對目標進行分類較快n缺點q訓練（學習）時間長q蘊涵在學習的權(quán)中的符號含義很難理解q很難根專業(yè)領域知識相整合什么是預測？n預測是構(gòu)造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。n預測和分類的異同n相同點q兩者都需要構(gòu)建模型q都用模型來估計未知值n預測當中主要的估計方法是回歸分析q線性回歸和多元回歸q非線性回歸n不同點q分類法主要是用來預測類標號（分類屬性值）q預測法主要是用來估計連續(xù)值（量化屬性值）第八章、聚類分析什么是聚類分析？n聚類（簇）：數(shù)據(jù)對象的集合q在同一個聚類（簇）中的對象彼此相似q不同簇中的對象則相異n聚類分析q將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程n聚類是一種無指導的學習：沒有預定義的類編號n聚類分析的數(shù)據(jù)挖掘功能q作為一個獨立的工具來獲得數(shù)據(jù)分布的情況q作為其他算法（如：特征和分類）的預處理步驟聚類分