數(shù)據(jù)挖掘原理與算法01

1、數(shù)據(jù)挖掘信息管理與工程學院,教材信息：《數(shù)據(jù)挖掘原理與算法》 毛國君，段立娟，王實，石云 清華大學出版社，2007,,,本課程的一些約定：,1、課程目的：拓寬與加深專業(yè)知識2、注重平時學習作業(yè)按時完成未按時為晚交一周內(nèi)未交視為放棄作業(yè)按規(guī)定要求完成教科書：不可或缺不允許抄襲但鼓勵討論3、無遲到、缺席、手機等,,什么激發(fā)了數(shù)據(jù)挖掘，為什么它是重要的？􀂄什么是數(shù)據(jù)挖掘？􀂄

2、在何種數(shù)據(jù)上進行數(shù)據(jù)挖掘？􀂄數(shù)據(jù)挖掘功能——可以挖掘什么類型的模式􀂄所有模式都是有趣的嗎？􀂄數(shù)據(jù)挖掘系統(tǒng)的分類􀂄數(shù)據(jù)挖掘的主要問題,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲

3、形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,數(shù)據(jù)挖掘技術的商業(yè)需求分析,隨著信息技術的高速發(fā)展，數(shù)據(jù)庫應用的規(guī)模、范圍和深度不斷擴大，網(wǎng)絡環(huán)境成為主流等等。產(chǎn)生“數(shù)據(jù)豐富而信息貧乏（Data Rich & Information Poor）”現(xiàn)象。在強大的商業(yè)需求的驅動下，商家們開始注意到有效地解決大容量數(shù)據(jù)的利用問題具有巨大的商機；學者們開始思考如何從大容量數(shù)據(jù)集中獲取有用信息和知識的方法

4、。隨著信息技術的高速發(fā)展，人們希望能夠提供更高層次的數(shù)據(jù)處理功能。新的需求推動新的技術的誕生。數(shù)據(jù)（Data）、信息（Information）和知識（Knowledge）是廣義數(shù)據(jù)表現(xiàn)的不同形式。,數(shù)據(jù)、信息和知識,,data,information,knowledge,,,數(shù)據(jù)挖掘產(chǎn)生的技術背景,數(shù)據(jù)挖掘是相關學科充分發(fā)展的基礎上被提出和發(fā)展的。主要的相關技術：數(shù)據(jù)庫、數(shù)據(jù)倉庫和Internet等信息技術的發(fā)展計算機性能的提

5、高和先進的體系結構的發(fā)展統(tǒng)計學和人工智能等方法在數(shù)據(jù)分析中的研究和應用,數(shù)據(jù)挖掘是一個多學科交叉技術,,Data Mining,Database Technology,Statistics,OtherDisciplines,InformationScience,AI /MachineLearning,Visualization,,,,,,,數(shù)據(jù)庫系統(tǒng)的發(fā)展,60年代：簡單文件處理系統(tǒng)向數(shù)據(jù)庫系統(tǒng)變革 。70年代：層次、網(wǎng)絡和

6、關系型數(shù)據(jù)庫普及。 80年代：RDBS及其相關工具、數(shù)據(jù)索引及數(shù)據(jù)組織技術被廣泛采用；中期開始，分布式數(shù)據(jù)庫廣發(fā)討論，關系數(shù)據(jù)庫技術和新型技術的結合。 90年代：數(shù)據(jù)庫領域中的新內(nèi)容、新應用、新技術層出不窮，形成了龐大的數(shù)據(jù)庫家族；人們期望分析預測、決策支持等高級應用， Data mining and data warehousing等出現(xiàn)。本世紀開始： Data mining 得到理論/技術深化。,統(tǒng)計學的深入應用,強大有效的數(shù)

7、理統(tǒng)計方法和工具，已成為信息咨詢業(yè)的基礎 。統(tǒng)計分析技術是基于嚴格的數(shù)學理論和高超的應用技巧的 。 數(shù)據(jù)挖掘技術是數(shù)理統(tǒng)計分析應用的延伸和發(fā)展 。 和數(shù)據(jù)庫技術的結合性研究,人工智能技術的研究和應用,人工智能是計算機科學研究中爭議最多而又仍始終保持強大生命的研究領域。專家系統(tǒng)曾經(jīng)是人工智能研究工作者的驕傲，但是諸多難題限制了專家系統(tǒng)的應用：知識獲取成為專家系統(tǒng)研究中公認的瓶頸問題。知識表示成為一大難題：知識工程師在整理表達從

8、領域專家那里獲得的知識時勉強抽象出來的規(guī)則有很強的工藝色彩。對常識和百科知識出奇地貧乏：人工智能學家Feigenbaum估計，一般人擁有的常識存入計算機大約有100萬條事實和抽象經(jīng)驗法則，離開常識的專家系統(tǒng)有時會比傻子還傻。數(shù)據(jù)挖掘繼承了專家系統(tǒng)的高度實用性特點，并且以數(shù)據(jù)為基本出發(fā)點，客觀地挖掘知識。機器學習得到了充分的研究和發(fā)展：理論和算法。數(shù)據(jù)挖掘研究在繼承已有的人工智能相關領域，特別是機器學習的研究成果的基礎上，成為新的

9、研究分支。,,,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢數(shù)據(jù)挖掘概念數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,數(shù)據(jù)挖掘處于研究和應用探索階段,經(jīng)過十幾年的研究和實踐，數(shù)據(jù)挖掘技術已經(jīng)吸收了許多學科的最新研究成果而形成獨具特色的研究

10、分支。大部分學者認為數(shù)據(jù)挖掘的研究仍然處于廣泛研究和探索階段：一方面，數(shù)據(jù)挖掘的概念已經(jīng)被廣泛接受。另一方面，數(shù)據(jù)挖掘的大面積應用還有待時日。隨著KDD在學術界和工業(yè)界的影響越來越大，數(shù)據(jù)挖掘的研究向著更深入和實用技術方向發(fā)展：大學等研究機構的大多數(shù)基礎性研究集中在數(shù)據(jù)挖掘理論、挖掘算法等的探討上。公司的研究更注重和實際商業(yè)問題結合。數(shù)據(jù)挖掘的經(jīng)濟價值已經(jīng)顯現(xiàn)出來：Gartner報告中列舉重要影響的五項關鍵技術，其中KDD

11、和人工智能排名第一。,數(shù)據(jù)挖掘研究聚焦點,數(shù)據(jù)挖掘在如下幾個方面需要重點開展工作：數(shù)據(jù)挖掘技術與特定商業(yè)邏輯的平滑集成問題：數(shù)據(jù)挖掘需要代表性的應用實例來證明（像“啤酒與尿布” ）。數(shù)據(jù)挖掘技術與特定數(shù)據(jù)存儲類型的適應問題：不同的數(shù)據(jù)存儲方式會影響數(shù)據(jù)挖掘的具體實現(xiàn)機制、目標定位、技術有效性等。大型數(shù)據(jù)的選擇與規(guī)格化問題：數(shù)據(jù)的噪音、信息丟失等問題的處理；針對特定挖掘方法進行數(shù)據(jù)規(guī)格化等問題。數(shù)據(jù)挖掘系統(tǒng)的構架與交互式挖掘技

12、術：在具體的實現(xiàn)機制、技術路線以及各階段的功能定位等方面仍需細化和深入研究。良好的交互式挖掘（Interaction Mining）也是數(shù)據(jù)挖掘系統(tǒng)成功的前提。數(shù)據(jù)挖掘語言與系統(tǒng)的可視化問題：可視化挖掘除了要和良好的交互式技術結合外，還必須在挖掘結果或過程的可視化進行探索和實踐。數(shù)據(jù)挖掘理論與算法研究一方面，在已有的理論框架下有許多面向實際應用目標的挖掘理論等待探索和創(chuàng)新。另一方面，隨著數(shù)據(jù)挖掘技術本身和相關技術的發(fā)展，新的

13、挖掘理論和算法的誕生是必然的。,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢數(shù)據(jù)挖掘概念數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,從商業(yè)角度看數(shù)據(jù)挖掘技術,數(shù)據(jù)挖掘從本質上說是一種新的商業(yè)信息處理技術：數(shù)據(jù)挖掘技術把人們對數(shù)據(jù)的應用

14、，從低層次的聯(lián)機查詢操作，提高到?jīng)Q策支持、分析預測等更高級應用上。通過對數(shù)據(jù)的統(tǒng)計、分析、綜合和推理，發(fā)現(xiàn)數(shù)據(jù)間的關聯(lián)性、未來趨勢以及一般性的概括知識等，這些知識性的信息可以用來指導高級商務活動。從決策、分析和預測等高級商業(yè)目的看，原始數(shù)據(jù)只是未被開采的礦山，需要挖掘和提煉才能獲得對商業(yè)目的有用的規(guī)律性知識。從商業(yè)角度看，數(shù)據(jù)挖掘就是按企業(yè)的既定業(yè)務目標，對大量的企業(yè)數(shù)據(jù)進行深層次分析以揭示隱藏的、未知的規(guī)律性并將其模型化，從而支

15、持商業(yè)決策活動。,數(shù)據(jù)挖掘的技術含義,數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KDD： Knowledge Discovery in Databases）是比數(shù)據(jù)挖掘出現(xiàn)更早的一個名詞。 KDD與Data Mining的關系，有不同的看法：KDD看成數(shù)據(jù)挖掘的一個特例：這是早期比較流行的觀點，這種描述強調了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。數(shù)據(jù)挖掘是KDD的一個關鍵步驟：這種觀點得到大多數(shù)學者認同，有它的合理性。KDD與Data Mining含義相同

16、：事實上，在現(xiàn)今的許多場合，如技術綜述等，這兩個術語仍然不加區(qū)分地使用著。也有其他的說法：KDD在人工智能界更流行，而Data Mining在數(shù)據(jù)庫界使用更多。在研究領域被稱作KDD，在工程領域則稱之為數(shù)據(jù)挖掘。,數(shù)據(jù)挖掘定義,數(shù)據(jù)挖掘定義有廣義和狹義之分。從廣義的觀點，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的、有噪聲的、不確定性的、各種存儲形式的）中，挖掘隱含在其中的、人們事先不知道的、對決策有用的知識的過程。從這種狹義的觀點上

17、，我們可以定義數(shù)據(jù)挖掘是從特定形式的數(shù)據(jù)集中提煉知識的過程。下列技術不是數(shù)據(jù)挖掘：OLTP Expert systems Small MLStatistical programs,數(shù)據(jù)挖掘研究的理論基礎,數(shù)據(jù)挖掘方法可以是基于數(shù)學理論的，也可以是非數(shù)學的；可以是演繹的，也可以是歸納的。從研究者可能是來自于數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、計算機科學以及其他方面的學者和工程技術人員，他們會從不同的視點進行探討性研究。有下面一些

18、重要的理論視點值得關注：模式發(fā)現(xiàn)（Pattern Discovery）架構規(guī)則發(fā)現(xiàn)（Rule Discovery）架構 基于概率和統(tǒng)計理論微觀經(jīng)濟學觀點（Microeconomic View）基于數(shù)據(jù)壓縮（Data Compression）理論基于歸納數(shù)據(jù)庫（Inductive Database）理論可視化數(shù)據(jù)挖掘（Visual Data Mining）等等,第一章 緒論

19、 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,根據(jù)挖掘任務,分類或預測模型發(fā)現(xiàn)數(shù)據(jù)總結與聚類發(fā)現(xiàn)關聯(lián)規(guī)則發(fā)現(xiàn)序列模式發(fā)現(xiàn)相似模式發(fā)現(xiàn)混沌模式發(fā)現(xiàn)依賴關系或依賴模型發(fā)現(xiàn)異常和趨勢發(fā)現(xiàn)等,根據(jù)挖掘對象,關系數(shù)據(jù)庫挖掘面向對象數(shù)據(jù)

20、庫挖掘空間數(shù)據(jù)庫挖掘時態(tài)數(shù)據(jù)庫挖掘文本數(shù)據(jù)源挖掘多媒體數(shù)據(jù)庫挖掘異質數(shù)據(jù)庫挖掘遺產(chǎn)數(shù)據(jù)庫挖掘web數(shù)據(jù)挖掘等,根據(jù)挖掘方法,機器學習方法統(tǒng)計方法聚類分析方法神經(jīng)網(wǎng)絡（Neural Network）方法遺傳算法（Genetic Algorithm）方法數(shù)據(jù)庫方法近似推理和不確定性推理方法基于證據(jù)理論和元模式的方法現(xiàn)代數(shù)學分析方法粗糙集（Rough Set）或模糊集方法集成方法等,根據(jù)知識類型,挖掘廣義型知

21、識挖掘差異型知識挖掘關聯(lián)型知識挖掘預測型知識挖掘偏離型（異常）知識挖掘不確定性知識等,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,知識表示模式分類,數(shù)據(jù)挖掘的目的是發(fā)

22、現(xiàn)知識，知識要通過一定的模式給出。通過對數(shù)據(jù)挖掘中知識表示模式及其所采用方法的分析，可以更清楚地了解數(shù)據(jù)挖掘系統(tǒng)的特點。主要知識模式類型有：廣義知識（Generalization）關聯(lián)知識（Association）類知識（Class/Cluster）預測型知識（Prediction）特異型知識（Exception）,廣義知識挖掘,廣義知識是指描述類別特征的概括性知識。這類數(shù)據(jù)挖掘系統(tǒng)是對細節(jié)數(shù)據(jù)的所蘊涵的概念特征信息的概括和

23、抽象的過程。主要方法有：概念描述（Concept Description）方法：概念描述本質上就是對某類對象的內(nèi)涵特征進行概括：特征性（Characterization）描述：描述某類對象的共同特征。區(qū)別性（Discrimination）描述：描述不同類對象之間的區(qū)別。多維數(shù)據(jù)分析可以看作是一種廣義知識挖掘的特例多層次概念描述問題：由數(shù)據(jù)歸納出的概念是有層次的，不同層次的概念是對原始數(shù)據(jù)的不同粒度上的概念抽象。例如，“北京

24、工業(yè)大學”能歸納出“北京市”、“中國”、“亞洲”等層次。銷售表SALES（ENO，ENAME，EAGE，VALUE，DEPT），它的每個屬性的定義域都可能存在蘊涵于領域知識內(nèi)的概念延伸。例如，DEPT能歸納出公司COMPANY、城市CITY或國家COUNTRY等層次概念分層（Concept Hierarchy）技術：將低層概念集映射到高層概念集的方法，是一個常用的處理多層次概念描述的方法。,主要的概念分層方法,模式分層（Schema

25、 Hierarchy）：利用屬性在特定背景知識下的語義層次形成不同層次的模式關聯(lián)。這種關聯(lián)是一種的全序或偏序關系。例如，DEPT的模式分層結構可能是：DEPT→COMPANY→CITY→COUNTRY。集合分組分層（Set-Grouping Hierarchy）：將屬性在特定背景知識下的取值范圍合理分割，形成替代的離散值或區(qū)間集合。例如，年齡EAGE可以抽象成{[20，29]，[30，39]，[40，49]，[50，59]}或者

26、{青年，中年，老年} 。操作導出分層（Operation-Drived Hierarchy）：有些屬性可能包含多類信息。例如，一個跨國公司的雇員號可能包含這個雇員的所在的部門、城市、國家和雇傭的時間等。對這類對象可以作為背景知識定義它的結構，通過編碼解析等操作完成概念的抽象?；谝?guī)則分層（Rule-Based Hierarchy）：通過定義背景知識的抽象規(guī)則，形成不同層次上的概念的抽象。,關聯(lián)知識挖掘,關聯(lián)知識挖掘的目的就是找出數(shù)

27、據(jù)庫中隱藏的關聯(lián)信息。關聯(lián)知識反映一個事件和其他事件之間的依賴或關聯(lián)。關聯(lián)可分為簡單關聯(lián)、時序（Time Series）關聯(lián)、因果關聯(lián)、數(shù)量關聯(lián)等。從廣義上講，關聯(lián)分析是數(shù)據(jù)挖掘的本質。關聯(lián)規(guī)則挖掘（Association Rule Mining）是關聯(lián)知識發(fā)現(xiàn)的最常用方法：關聯(lián)規(guī)則的研究最早的分支之一，最著名的Apriori算法。是數(shù)據(jù)挖掘研究中比較深入的分支，許多關聯(lián)規(guī)則挖掘的理論和算法已經(jīng)被提出。,類知識挖掘,類知識（

28、Class）刻畫了一類事物，這類事物具有某種意義上的共同特征，并明顯和不同類事物相區(qū)別。 有兩個基本的方法來挖掘類知識：分類：分類是數(shù)據(jù)挖掘中的一個重要的目標和任務，是目前的研究和應用最多的分支之一。分類的目的是學會一個分類模型（稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中。分類技術是一種有指導的學習（Supervised Learning），即每個訓練樣本的數(shù)據(jù)對象已經(jīng)有類標識，通過學習可以形成表達數(shù)據(jù)對象與類標識

29、間對應的知識。聚類：數(shù)據(jù)挖掘的目標之一是進行聚類分析。聚類是把一組個體按照相似性歸成若干類別，它的目的是使得屬于同一類別的個體之間的差別盡可能的小，而不同類別上的個體間的差別盡可能的大。聚類屬于無指導學習（Unsupervised Learning） ），當一組數(shù)據(jù)對象可以由一個概念（區(qū)別于其他的概念）來描述時，就形成一個簇（Cluster）?？坍嬃藬?shù)據(jù)所蘊涵的類知識。,分類中的基礎方法,決策樹方法：基本的分類技術之一，如ID3及

30、其改進算法ID4、ID5、C4.5、C5.0等；針對大訓練樣本集的SLIQ、SPRINT、雨林（Rainforest）BOAT等算法。貝葉斯分類 ：具有堅實的理論基礎，理論上具有較小的出錯率。但是，它的適應性差。神經(jīng)網(wǎng)絡：作為一個相對獨立的研究分支已經(jīng)很早被提出，具有高度的抗干擾能力和可以對未訓練數(shù)據(jù)進行分類等優(yōu)點，因此產(chǎn)生了神經(jīng)網(wǎng)絡和數(shù)據(jù)挖掘技術的結合性研究。遺傳算法：是基于進化理論的機器學習方法。類比學習 ：最典型的方法是k

31、-最臨近分類（k-Nearest Neighbor Classification）方法，它屬于懶散學習法。其他方法：如粗糙集（Rough Set）、模糊集（Fuzzy Set）方法等 。,主要聚類的技術,基于劃分的聚類方法：k-平均算法是統(tǒng)計學中的一個經(jīng)典聚類方法，它以預先定義好的簇平均值，構造劃分，評價和選擇他們?；趯哟蔚木垲惙椒ǎ和ㄟ^對源數(shù)據(jù)庫中的數(shù)據(jù)進行層次分解，達到目標簇的逐步生成。凝聚（Agglomeration）：由

32、小到大逐步合并、評價。分裂（Division）由大到小逐步分裂、評價?；诿芏鹊木垲惙椒ǎ夯诿芏鹊木垲惙椒ㄊ峭ㄟ^度量區(qū)域所包含的對象數(shù)目來形成最終目標的。如果一個區(qū)域的密度超過指定的值，那么它就需要進一步分解。基于網(wǎng)格的聚類方法：對象空間離散化成有限的網(wǎng)格單元，聚類工作在這種網(wǎng)格結構上進行?；谀Ｐ偷木垲惙椒ǎ好總€簇假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬和。,預測型知識挖掘,預測型知識（Prediction）是指由歷史的數(shù)

33、據(jù)產(chǎn)生的并能推測未來數(shù)據(jù)趨勢的知識。預測性挖掘主要是對未來數(shù)據(jù)的概念分類和趨勢輸出。分類技術可以用于產(chǎn)生預測型的類知識。統(tǒng)計學中的回歸方法等可以通過歷史數(shù)據(jù)直接產(chǎn)生對未來數(shù)據(jù)預測的連續(xù)值，因而這些預測型知識已經(jīng)蘊藏在諸如趨勢曲線等輸出形式中。預測型知識的挖掘可以結合經(jīng)典的統(tǒng)計方法、神經(jīng)網(wǎng)絡和機器學習等技術來研究。,預測型知識挖掘中的典型方法,趨勢預測模式：主要是針對那些具有時序（Time Series）屬性的數(shù)據(jù)，如股票價格等，

34、或者是序列項目（Sequence Items）的數(shù)據(jù)，如年齡和薪水對照等，發(fā)現(xiàn)長期的趨勢變化等。周期分析模式：主要是針對那些數(shù)據(jù)分布和時間的依賴性很強的數(shù)據(jù)進行周期模式的挖掘。例如，服裝在某季節(jié)或所有季節(jié)的銷售周期。序列模式：主要是針對歷史事件發(fā)生次序的分析形成預測模式來對未來行為進行預測。例如，預測“三年前購買計算機的客戶有很大概率會買數(shù)字相機”。神經(jīng)網(wǎng)絡：在預測型知識挖掘中，神經(jīng)網(wǎng)絡也是很有用的模式結構。,特異型知識挖掘,特異

35、型知識（Exception）是源數(shù)據(jù)中所蘊涵的極端特例或明顯區(qū)別于其他數(shù)據(jù)的知識描述，它揭示了事物偏離常規(guī)的異常規(guī)律。特異知識挖掘的價值：例如，在Web站點發(fā)現(xiàn)那些區(qū)別于正常登錄行為的用戶特點可以防止非法入侵。金融、電信欺詐等分類中的反常實例、不滿足普通規(guī)則的特例、觀測結果與模型預測值的偏差、數(shù)據(jù)聚類外的離群值等,特異型知識挖掘的任務和方法,許多技術可以擴展到特異型知識挖掘中,如：孤立點（Outlier）分析：孤立點是指不符合

36、數(shù)據(jù)的一般模型的數(shù)據(jù)。在類知識挖掘中，孤立點分析是不能歸入正常類知識中的零散數(shù)據(jù)的再分析。異常序列分析：在一系列行為或事件對應的序列中發(fā)現(xiàn)明顯不符合一般規(guī)律的特異型知識。特異規(guī)則發(fā)現(xiàn)：產(chǎn)生并評價雖然具有低支持度但可能很有價值的規(guī)則。,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表

37、示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,數(shù)據(jù)挖掘方法與數(shù)據(jù)存儲類型,數(shù)據(jù)挖掘技術應該應用到任何數(shù)據(jù)存儲方式的知識挖掘中，但是因為源數(shù)據(jù)的存儲類型的不同，挖掘的挑戰(zhàn)性和技術會不同。近年來的研究表明數(shù)據(jù)挖掘所涉及的數(shù)據(jù)存儲類型越來越豐富，除了一些有通用價值的模型、構架等研究外，也開展了一些針對復雜或新型數(shù)據(jù)存儲方式下的挖掘技術或算法的研究。主要的數(shù)據(jù)類型：事務數(shù)據(jù)庫（T

38、ransactional Database ）關系型數(shù)據(jù)庫 （Related Database ）數(shù)據(jù)倉庫（Data Warehouse ）在關系模型基礎上發(fā)展的新型數(shù)據(jù)庫 面向應用的新型數(shù)據(jù)源 Web數(shù)據(jù),事務數(shù)據(jù)庫中的數(shù)據(jù)挖掘,一個事務數(shù)據(jù)庫是對事務型數(shù)據(jù)的收集。1993年，當Agrawal等開始討論數(shù)據(jù)挖掘問題時，是以購物籃分析（Market Basket Analysis）作為商業(yè)應用背景的。從事務數(shù)據(jù)庫中發(fā)現(xiàn)知識是

39、數(shù)據(jù)挖掘中研究較早但至今仍然很活躍的問題。通過特定的技術對事務數(shù)據(jù)庫進行挖掘，可以獲得動態(tài)行為所蘊藏的關聯(lián)規(guī)則、分類、聚類以及預測等知識模式。第三章將詳細講解,關系型數(shù)據(jù)庫中的數(shù)據(jù)挖掘,關系型數(shù)據(jù)庫是由一系列數(shù)據(jù)表組成的，相當成熟：成熟的語義模型（像實體-關系模型）；成熟的DBMS（像Oracle）成熟的查詢語言（像SQL語言；可視化的輔助工具和優(yōu)化軟件。一些更深入和亟待解決的問題：多維知識挖掘： 傳統(tǒng)的事務數(shù)據(jù)庫挖掘所研究的

40、知識一般是單維（Single-Demension）的，但是，在關系型數(shù)據(jù)庫中，多維的知識更普遍和有應用價值。單維： “購買計算機的人也購買打印機”。多維： “什么樣購買計算機的人也購買打印機的可能性更大？” 。多表挖掘：關系型數(shù)據(jù)庫是一系列表的集合。因此，多表挖掘是必然的。數(shù)量數(shù)據(jù)挖掘： 關系型數(shù)據(jù)庫經(jīng)常包含非離散數(shù)量屬性（如工資）。多層知識挖掘：數(shù)據(jù)及其關聯(lián)總是可在多個不同的概念層上來理解它。知識評價問題：對傳統(tǒng)的數(shù)據(jù)挖掘

41、框架的知識評價問題，也是關系型數(shù)據(jù)庫中數(shù)據(jù)挖掘走向實際應用必須要解決的問題。約束數(shù)據(jù)挖掘問題：數(shù)據(jù)挖掘系統(tǒng)在用戶的約束指導下進行，可以提高挖掘效率和準確度。,數(shù)據(jù)倉庫中的數(shù)據(jù)挖掘,數(shù)據(jù)倉庫中的數(shù)據(jù)是按著主題來組織的。存儲的數(shù)據(jù)可以從歷史的觀點提供信息。雖然目前的一些數(shù)據(jù)倉庫輔助工具可以幫助完成數(shù)據(jù)分析，但是發(fā)現(xiàn)蘊藏在數(shù)據(jù)內(nèi)部的知識模式及其按知識工程方法來完成高層次的工作仍需要數(shù)據(jù)挖掘技術支持。數(shù)據(jù)挖掘不僅伴隨數(shù)據(jù)倉庫而產(chǎn)生，而且隨著

42、應用深入產(chǎn)生了許多新的課題。如果我們把數(shù)據(jù)挖掘作為高級數(shù)據(jù)分析手段來看，那么它是伴隨數(shù)據(jù)倉庫技術提出并發(fā)展起來的。OLAP盡管在許多方面和數(shù)據(jù)挖掘是有區(qū)別的，但是它們在應用目標上有很大的重合度。數(shù)據(jù)挖掘更看中數(shù)據(jù)分析后所形成的知識表示模式，而OLAP更注重利用多維等高級數(shù)據(jù)模型實現(xiàn)數(shù)據(jù)的聚合。從某種意義上講，我們可以把數(shù)據(jù)挖掘看作是OLAP的高級形式，與此更接近的名詞可能算是OLAM（聯(lián)機分析挖掘）。,新型數(shù)據(jù)庫中的數(shù)據(jù)挖掘,對象

43、—關系型數(shù)據(jù)庫（Object-Ralational Database）挖掘；面向對象數(shù)據(jù)庫的挖掘；空間數(shù)據(jù)庫的挖掘；時態(tài)數(shù)據(jù)庫的挖掘；工程數(shù)據(jù)庫（Engineering Database）的挖掘；多媒體數(shù)據(jù)庫（Multimedia Database）的挖掘；等等,Web數(shù)據(jù)源中的數(shù)據(jù)挖掘,隨著Internet的廣泛使用， Web這一巨大的海洋中蘊藏著極其豐富的有用信息。面向Web的數(shù)據(jù)挖掘比面向數(shù)據(jù)庫和數(shù)據(jù)倉庫的數(shù)據(jù)挖掘要

44、復雜得多：異構數(shù)據(jù)源環(huán)境：Web網(wǎng)站上的信息是異構: 每個站點的信息和組織都不一樣；存在大量的無結構的文本信息、復雜的多媒體信息；站點使用和安全性、私密性要求各異等等。數(shù)據(jù)的是復雜性：有些是無結構的（如Web頁），通常都是用長的句子或短語來表達文檔類信息；有些可能是半結構的（如Email，HTML頁）。當然有些具有很好的結構（如電子表格）。揭開這些復合對象蘊涵的一般性描述特征成為數(shù)據(jù)挖掘的不可推卸的責任。動態(tài)變化的應用環(huán)境：We

45、b的信息是頻繁變化的，像新聞、股票等信息是實時更新的。這種高變化也體現(xiàn)在頁面的動態(tài)鏈接和隨機存取上。Web上的用戶是難以預測的。Web上的數(shù)據(jù)環(huán)境是高噪音的。,Web挖掘的研究主要流派,Web結構挖掘：挖掘Web上的鏈接結構。通過Web頁面間的鏈接信息可以識別出權威頁面（Authoritative Page）、安全隱患（非法鏈接）等。Web使用挖掘對Web上的Log日志記錄的挖掘Web上的Log日志記錄了包括URL請求、IP

46、地址以及時間等的訪問信息。分析和發(fā)現(xiàn)Log日志中蘊藏的規(guī)律可以幫助我們識別潛在的客戶、跟蹤Web服務的質量以及偵探非法訪問的隱患等。Web內(nèi)容挖掘： Web的內(nèi)容是豐富的，而且構成成分是復雜的（無結構的、半結構的等），對內(nèi)容的分析是重要而艱巨的工作。Web的內(nèi)容主要是包含文本、聲音、圖片等的文檔信息。文本挖掘（Text Mining）和Web搜索引擎（Search Engine）等相關領域的研究。目多媒體信息挖掘技術。,第一章

47、 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,粗糙集理論簡介,粗糙集理論是一種研究不精確、不確定性知識的數(shù)學工具，由波蘭科學家Z. Pawlak在1982年首先提出的。粗糙集一經(jīng)提出

48、就立刻引起數(shù)據(jù)挖掘研究人員的注意，并被廣泛討論。粗糙集的知識形成思想可以概括為：一種類別對應于一個概念，知識由概念組成。粗糙集理論是一種刻畫不完整性和不確定性的數(shù)學工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律。,粗糙集理論簡介,在數(shù)據(jù)挖掘與知識發(fā)現(xiàn)中，粗糙集理論與方法對于處理復雜系統(tǒng)已成為一個有效的方法，它與概率論、模糊集方法和證據(jù)理論等其他處理不確定性問題理論的最顯著區(qū)別是：

49、它無需提供問題所處理的數(shù)據(jù)集合的任何先驗信息。粗糙集理論強調的是信息系統(tǒng)中知識的不完全性、不可分辨性，其處理方法是確定的，要求屬性值都是定性值，而實際應用中大量存在的是定量數(shù)據(jù)，必須設法轉換成定性數(shù)據(jù)才能運用粗糙集方法。因此與其他處理不確定性問題的理論，如模糊數(shù)學和云理論等，具有很強的互補性，可以相互促進，增強其知識發(fā)現(xiàn)的能力。,粗糙集理論簡介,粗糙集和數(shù)據(jù)挖掘關系密切，目前已經(jīng)在關聯(lián)規(guī)則、決策樹等方面得到了廣泛應用?；诖植诩年P聯(lián)規(guī)

50、則提取主要步驟包括去除不一致實例、求屬性核、求相對約簡、相同實例合并和值約簡?；诖植诩膯巫兞繘Q策樹構造方法的基本思想是具有最小邊界的屬性在構造決策樹時將首先被選擇。并且目前的研究趨向是：粗糙集和遺傳算法相結合、和模糊集相結合，以及和神經(jīng)網(wǎng)絡相結合用于數(shù)據(jù)挖掘。,粗糙集理論簡介,粗糙集為數(shù)據(jù)挖掘提供了一種新的方法和工具，并擁有廣闊的前景。首先，數(shù)據(jù)挖掘研究的實施對象多為關系型數(shù)據(jù)庫。關系表可被看作為粗糙集理論中的信息表或決策表，這給

51、粗糙集方法的應用帶來極大的方便；第二，粗糙集的約簡理論可用于高維數(shù)據(jù)的預處理上以去除冗余屬性從而達到降低維數(shù)的目的；第三，現(xiàn)實世界中的規(guī)則有確定性的，也有不確定性的。從數(shù)據(jù)庫中發(fā)現(xiàn)不確定性的知識，為粗糙集方法提供了用武之地；第四，運用粗糙集方法得到的知識發(fā)現(xiàn)算法有利于并行執(zhí)行，這可極大地提高對大規(guī)模數(shù)據(jù)庫的知識發(fā)現(xiàn)的效率。,第一章 緒論 內(nèi)容提要,數(shù)據(jù)挖掘技術的產(chǎn)生與

52、發(fā)展 數(shù)據(jù)挖掘研究的發(fā)展趨勢 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘技術的分類問題數(shù)據(jù)挖掘常用的知識表示模式與方法不同數(shù)據(jù)存儲形式下的數(shù)據(jù)挖掘問題 粗糙集方法及其在數(shù)據(jù)挖掘中的應用 數(shù)據(jù)挖掘的應用分析,數(shù)據(jù)挖掘技術應用廣泛,數(shù)據(jù)挖掘技術從一開始就是面向應用的。由于現(xiàn)在各行業(yè)的業(yè)務操作都向著流程自動化的方向發(fā)展，企業(yè)內(nèi)產(chǎn)生了大量的業(yè)務數(shù)據(jù)。數(shù)據(jù)挖掘技術應用很廣，應用較好的領域有：金融保險業(yè)：Credit Scoring； Insuran

53、ce Evaluation電信： Detecting telephone fraud零售（如超級市場）等商業(yè)領域：Marketing Analysis醫(yī)學： Detecting inappropriate medical treatment體育： IBM Advanced Scout analyzed NBA game statistics 在天文學、分子生物學等科學研究方面等等,數(shù)據(jù)挖掘與CRM,CRM（客戶關系管理）是指

54、對企業(yè)和客戶之間的交互活動或行為進行管理的過程。數(shù)據(jù)挖掘能夠幫助企業(yè)確定客戶的特點，使企業(yè)能夠為客戶提供有針對性的服務。因此，把數(shù)據(jù)挖掘和CRM結合起來進行研究和實踐，是一個有很大應用前景的工作。所能解決的典型商業(yè)問題包括：數(shù)據(jù)庫營銷（Database Marketing）客戶群體劃分（Customer Segmentation & Classification）客戶背景分析（Profile Analysis）交叉銷

55、售（Cross-selling）客戶流失性分析（Churn Analysis）客戶信用記分（Credit Scoring）欺詐發(fā)現(xiàn)（Fraud Detection）等等。,數(shù)據(jù)挖掘與信息安全,隨著網(wǎng)絡上需要進行存儲和處理的敏感信息的日益增多，安全問題逐漸成為網(wǎng)絡和系統(tǒng)中的首要問題?，F(xiàn)代信息安全的內(nèi)涵已經(jīng)不局限于信息的保護，而是對整個信息系統(tǒng)的保護和防御，包括對信息的保護、檢測、反映和恢復能力（PDRR）等。傳統(tǒng)的信息安全系統(tǒng)概

56、括性差，只能發(fā)現(xiàn)模式規(guī)定的、已知的入侵行為，難以發(fā)現(xiàn)新的入侵行為。人們希望能夠對審計數(shù)據(jù)進行自動的、更高抽象層次的分析，從中提取出具有代表性、概括性的系統(tǒng)特征模式，以便減輕人們的工作量，且能自動發(fā)現(xiàn)新的入侵行為。數(shù)據(jù)挖掘正是具有這樣功能的一種技術。數(shù)據(jù)挖掘可以對海量的數(shù)據(jù)進行智能化的處理，提取出我們感興趣的信息。利用數(shù)據(jù)挖掘、機器學習等智能方法作為入侵檢測的數(shù)據(jù)分析技術，可從海量的安全事件數(shù)據(jù)中提取出盡可能多的隱藏安全信息，抽象出有利

57、于進行判斷和比較的與安全相關的普遍特征，從而發(fā)現(xiàn)未知的入侵行為。,http://www.cs.sfu.ca/~han,Thank you !!!,CMPT-843 Course Arrangement,1st week: full instructor teaching2nd to 11th week: 1/2 graduate student + 1/2 instructor teaching12-13th week: full

58、student graduate project presentationCourse evaluation:presentation (quality of presentation slides 7% + presentation 8%) 15%midterm exam 35%project (presentation 5% + report 25%) total 30%homework (2): 20%Deadli

59、ne for the selection of your work in the semester:selection of course presentation: at the end of the 1st weekselection of the course project: at the end of the 3rd weekproject proposal due date: at the end of the 4th