人工智能數(shù)據(jù)挖掘(46張)課件

1、章數(shù)據(jù)挖掘第1頁，共47頁。第八章 數(shù)據(jù)挖掘 數(shù)據(jù)挖掘（Data Mining）是一個多學科交叉研究領域，它融合了數(shù)據(jù)庫技術(shù)、人工智能、機器學習、統(tǒng)計學、知識工程、面向?qū)ο蠓椒?、信息檢索、高性能計算以及數(shù)據(jù)可視化等最新技術(shù)的研究成果。經(jīng)過十幾年的研究，產(chǎn)生了許多新概念和方法。特別是最近幾年來，一些基本概念和方法趨于清晰，它的研究正向著更深入的方向發(fā)展。數(shù)據(jù)挖掘技術(shù)正在以一種全新的概念改變著人類利用數(shù)據(jù)的方式，它被認為是未來信息處理的骨干技術(shù)之一，網(wǎng)絡之后的下一個技術(shù)熱點。第2頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.1數(shù)據(jù)挖掘的定義 數(shù)據(jù)挖掘（Data Mining）是一門受到來自各種不同領域

2、的研究者關(guān)注的交叉性學科，有很多不同的術(shù)語名稱，除了常用的“數(shù)據(jù)挖掘”和“知識發(fā)現(xiàn)”之外，與數(shù)據(jù)挖掘相近的同義詞有數(shù)據(jù)融合、數(shù)據(jù)分析、知識抽取、信息發(fā)現(xiàn)、數(shù)據(jù)采掘、知識獲取、數(shù)據(jù)考古、信息收獲和決策支持等。 從技術(shù)的角度講，數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。這個定義包括好幾層含義：數(shù)據(jù)源必須是真實的、大量的、含噪聲的；發(fā)現(xiàn)的是用戶感興趣的知識；發(fā)現(xiàn)的知識要可接受、可理解、可運用；并不要求發(fā)現(xiàn)放之四海皆準的知識，也不是要去發(fā)現(xiàn)嶄新的自然科學定理和純數(shù)學公式，更不是什么機器定理證明，只要能支

3、持特定的發(fā)現(xiàn)問題即可。實際上，利用數(shù)據(jù)挖掘從數(shù)據(jù)集中所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件，面向特定領域的，同時還要能夠易于被用戶理解。最好能用自然語言表達所發(fā)現(xiàn)的結(jié)果。 第3頁，共47頁。8.1 數(shù)據(jù)挖掘概述 從商業(yè)的角度講，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要特點是對商業(yè)數(shù)據(jù)庫中的大量業(yè)務數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。簡而言之，數(shù)據(jù)挖掘其實是一類深層次的數(shù)據(jù)分析方法。數(shù)據(jù)分析本身已經(jīng)有很多年的歷史，只不過在過去數(shù)據(jù)收集和分析的目的是用于科學研究，另外，由于當時計算能力的限制，對大數(shù)據(jù)量進行分析的復雜數(shù)據(jù)分析方法受到很大限制?，F(xiàn)在

4、，由于各行業(yè)業(yè)務自動化的實現(xiàn)，商業(yè)領域產(chǎn)生了大量的業(yè)務數(shù)據(jù)，這些數(shù)據(jù)不再是為了分析的目的而收集的，而是由于純機會的商業(yè)運作而產(chǎn)生。分析這些數(shù)據(jù)也不再是單純?yōu)榱搜芯康男枰饕菫樯虡I(yè)決策提供真正有價值的信息，進而獲得利潤。 第4頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.2數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)（1）KDD看成數(shù)據(jù)挖掘的一個特例 數(shù)據(jù)挖掘系統(tǒng)可以在關(guān)系數(shù)據(jù)庫、事務數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫（Spatial Database）、文本數(shù)據(jù)（Text Data）以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識，既然如此，那么可以說數(shù)據(jù)庫中的知識發(fā)現(xiàn)只是數(shù)據(jù)挖掘的一個方面，這是早期比較流行的觀點。因

5、此，從這個意義說，數(shù)據(jù)挖掘就是從數(shù)據(jù)庫、數(shù)據(jù)倉庫以及其它數(shù)據(jù)存儲方式中挖掘有用知識的過程。這種描述強調(diào)了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。(2) 數(shù)據(jù)挖掘是KDD過程的一個步驟 在“知識發(fā)現(xiàn)96國際會議” 上，許多學者建議對這兩個名詞加以區(qū)分。核心思想是：KDD是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而Data Mining則是此全部過程的一個特定的、關(guān)鍵步驟，這種觀點有它的合理性。雖然我們可以從數(shù)據(jù)倉庫、WEB等源數(shù)據(jù)中挖掘知識，但是這些數(shù)據(jù)源都是和數(shù)據(jù)庫技術(shù)相關(guān)的。數(shù)據(jù)倉庫是由源數(shù)據(jù)庫集成而來的，即使是像WEB這樣的數(shù)據(jù)源恐怕也離不開數(shù)據(jù)庫技術(shù)來組織和存儲抽取的信息。因此KDD是一個更廣義的范疇，它

6、包括數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、模式生成及評估等一系列步驟。這樣，我們可以把KDD看作是一些基本功能構(gòu)件的系統(tǒng)化協(xié)同工作系統(tǒng)，而數(shù)據(jù)挖掘則是這個系統(tǒng)中的一個關(guān)鍵的部分。 第5頁，共47頁。8.1 數(shù)據(jù)挖掘概述（3）KDD與Data Mining含義相同 也有些人認為，KDD與Data Mining只是叫法不一樣，它們的含義基本相同。事實上，在現(xiàn)今的文獻中，許多場合，如技術(shù)綜述等，這兩個術(shù)語仍然不加區(qū)分地使用著。也有人說，KDD在人工智能界更流行；Data Mining在數(shù)據(jù)庫界使用更多。所以，從廣義的觀點，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的、有噪聲的、不確定性的、各種

7、存儲形式的）中，挖掘隱含在其中的、人們事先不知道的、對決策有用的知識的過程。 從上面的描述中可以看出，數(shù)據(jù)挖掘概念可以在不同的技術(shù)層面上來理解，但是其核心仍然是從數(shù)據(jù)中挖掘知識。從本質(zhì)來講，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)是有區(qū)別的，但是在很多場合人們往往不嚴格區(qū)分數(shù)據(jù)挖掘和數(shù)據(jù)庫中的知識發(fā)現(xiàn)，兩者互為使用。一般在科研領域中稱為KDD，而在工程領域則多稱為數(shù)據(jù)挖掘。 第6頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.3數(shù)據(jù)挖掘研究的理論基礎 數(shù)據(jù)挖掘方法可以是基于數(shù)學理論的，也可以是非數(shù)學的；可以是演繹的，也可以是歸納的。從研究的歷史看，它們可能是數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、計算機科學以及其它方面的學者和工程技

8、術(shù)人員，在數(shù)據(jù)挖掘的探討性研究過程中創(chuàng)立的理論體系。1997年，Mannila對當時流行的數(shù)據(jù)挖掘的理論框架給出了綜述。結(jié)合最新的研究成果，有下面一些重要的理論框架可以幫助我們準確地理解數(shù)據(jù)挖掘的概念與技術(shù)特點。 模式發(fā)現(xiàn)架 規(guī)則發(fā)現(xiàn)架構(gòu) 基于概率和統(tǒng)計理論 微觀經(jīng)濟學觀點 基于數(shù)據(jù)壓縮理論 基于歸納數(shù)據(jù)庫理論 第7頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.4數(shù)據(jù)挖掘與其它數(shù)據(jù)處理方法的區(qū)別及聯(lián)系1數(shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別 數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析(如查詢、報表、聯(lián)機應用分析)的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設的前提下去挖掘信息、發(fā)現(xiàn)知識。數(shù)據(jù)挖掘所得到的信息應具有先未知，有效和可實用三

9、個特征。 先前未知的信息是指該信息是預先未曾預料到的，既數(shù)據(jù)挖掘是要發(fā)現(xiàn)那些不能靠直覺發(fā)現(xiàn)的信息或知識，甚至是違背直覺的信息或知識，挖掘出的信息越是出乎意料，就可能越有價值，在商業(yè)應用中最典型的例子就是一家連鎖店通過數(shù)據(jù)挖掘發(fā)現(xiàn)了小孩尿布和啤酒之間有著驚人的聯(lián)系。2. 數(shù)據(jù)挖掘和數(shù)據(jù)倉庫 大部分情況下，數(shù)據(jù)挖掘都要先把數(shù)據(jù)從數(shù)據(jù)倉庫中拿到數(shù)據(jù)挖掘庫或數(shù)據(jù)集市中（見圖8.1）。從數(shù)據(jù)倉庫中直接得到進行數(shù)據(jù)挖掘的數(shù)據(jù)有許多好處。第8頁，共47頁。8.1 數(shù)據(jù)挖掘概述數(shù)據(jù)倉庫的數(shù)據(jù)清理和數(shù)據(jù)挖掘的數(shù)據(jù)清理差不多，如果數(shù)據(jù)在導入數(shù)據(jù)倉庫時已經(jīng)清理過，那很可能在做數(shù)據(jù)挖掘時就沒必要在清理一次了，而且所有

10、的數(shù)據(jù)不一致的問題都已經(jīng)被解決了。數(shù)據(jù)挖掘庫可能是數(shù)據(jù)倉庫的一個邏輯上的子集，而不一定非得是物理上單獨的數(shù)據(jù)庫。但如果數(shù)據(jù)倉庫的計算資源已經(jīng)很緊張，那最好還是建立一個單獨的數(shù)據(jù)挖掘庫 圖8.1 數(shù)據(jù)挖掘苦聰數(shù)據(jù)倉庫中得出第9頁，共47頁。8.1 數(shù)據(jù)挖掘概述 3. 數(shù)據(jù)挖掘和在線分析處理（OLAP） 數(shù)據(jù)挖掘和OLAP是完全不同的工具，基于的技術(shù)也大相徑庭。OLAP是決策支持領域的一部分。傳統(tǒng)的查詢和報表工具是告訴人們數(shù)據(jù)庫中都有什么，OLAP則更進一步告訴人們下一步會怎么樣和如果人們采取這樣的措施又會怎么樣。用戶首先建立一個假設，然后用OLAP檢索數(shù)據(jù)庫來驗證這個假設是否正確。 數(shù)據(jù)挖掘與O

11、LAP不同的地方是，數(shù)據(jù)挖掘不是用于驗證某個假定的模式（模型）的正確性，而是在數(shù)據(jù)庫中自己尋找模型。它在本質(zhì)上是一個歸納的過程。 數(shù)據(jù)挖掘和OLAP具有一定的互補性。在利用數(shù)據(jù)挖掘出來的結(jié)論采取行動之前，也許要驗證一下如果采取這樣的行動會帶來什么樣的影響，那么OLAP工具能回答這些問題。 第10頁，共47頁。8.1 數(shù)據(jù)挖掘概述4. 數(shù)據(jù)挖掘與機器學習和統(tǒng)計分析方法 數(shù)據(jù)挖掘利用了人工智能（AI）和統(tǒng)計分析的進步所帶來的好處。這兩門學科都致力于模式發(fā)現(xiàn)和預測。數(shù)據(jù)挖掘不是為了替代傳統(tǒng)的統(tǒng)計分析技術(shù)。相反，它是統(tǒng)計分析方法學的延伸和擴展。大多數(shù)的統(tǒng)計分析技術(shù)都基于完善的數(shù)學理論和高超的技巧，預測

12、的準確度還是令人滿意的，但對使用者的要求很高。而隨著計算機計算能力的不斷增強，我們有可能利用計算機強大的計算能力只通過相對簡單和固定的方法完成同樣的功能。 一些新興的技術(shù)同樣在知識發(fā)現(xiàn)領域取得了很好的效果，如神經(jīng)元網(wǎng)絡和決策樹，在足夠多的數(shù)據(jù)和計算能力下，它們幾乎不用人的關(guān)照自動就能完成許多有價值的功能。第11頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.5數(shù)據(jù)挖掘的內(nèi)容 隨著DM和KDD研究逐步走向深入，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究已經(jīng)形成了三根強大的技術(shù)支柱：數(shù)據(jù)庫、人工智能和數(shù)理統(tǒng)計。因此，KDD大會程序委員會曾經(jīng)由這三個學科的權(quán)威人物同時來任主席。目前DMKD的主要研究內(nèi)容包括基礎理論、發(fā)現(xiàn)算

13、法、數(shù)據(jù)倉庫、可視化技術(shù)、定性定量互換模型、知識表示方法、發(fā)現(xiàn)知識的維護和再利用、半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)中的知識發(fā)現(xiàn)以及網(wǎng)上數(shù)據(jù)挖掘等。數(shù)據(jù)挖掘所發(fā)現(xiàn)的知識最常見的有以下四類。 廣義知識 關(guān)聯(lián)知識 分類知識 預測型知識 第12頁，共47頁。8.1 數(shù)據(jù)挖掘概述8.1.6數(shù)據(jù)挖掘的研究歷史和現(xiàn)狀 數(shù)據(jù)庫中發(fā)現(xiàn)知識（KDD）是在 1989 年召開的第 11 屆國際人工智能聯(lián)合學術(shù)會議 (IJCAI) 上首次提出的。在這屆學術(shù)會議上舉行了以 KDD 為主題的學術(shù)研討會，在 1991 年、 1993 年和 1994 年相繼舉行了 KDD 專題研討會。隨著 KDD 的深入研究以及 KDD 在許多領域的成

14、功應用，于 1995 年在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學術(shù)會議，此后每年都召開大規(guī)模的國際會議，其研究重點也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應用，注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學科之間的相互滲透。第一本關(guān)于 DM和KDD 的國際學術(shù)雜志 Data Mining and Knowledge Discovery 也于 97 年 3 月創(chuàng)刊發(fā)行。亞太地區(qū)于 1997 年在新加坡召開了首次 KDD 研討會，其后又在澳大利亞的墨爾本召開了第二屆，在中國北京召開了第三屆。目前，在 IJCAI 、 AAAI 、 VLDB 、 ACM-SIGMOD 等代表人工智能與數(shù)據(jù)庫技術(shù)研究最高水平的國際學術(shù)會

15、議上，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究都占有較大的比例，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究已經(jīng)成為當今計算機科學與技術(shù)研究、應用的熱點領域之一。第13頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 根據(jù)挖掘的任務可以分為：分類和預測模型發(fā)現(xiàn)、數(shù)據(jù)總結(jié)和聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、序列模式發(fā)現(xiàn)、相似模式發(fā)現(xiàn)和混沌模式發(fā)現(xiàn)等。根據(jù)挖掘?qū)ο髞矸?，?shù)據(jù)挖掘方法有面向關(guān)系數(shù)據(jù)庫、空間數(shù)據(jù)庫、時態(tài)數(shù)據(jù)庫、文本數(shù)據(jù)源、多媒體數(shù)據(jù)庫、面向?qū)ο髷?shù)據(jù)庫、異質(zhì)數(shù)據(jù)庫以及WEB信息等。根據(jù)挖掘方法來分，數(shù)據(jù)挖掘方法可分為機器學習方法、統(tǒng)計方法、神經(jīng)網(wǎng)絡方法和數(shù)據(jù)庫方法。其中機器學習可細分為歸納學習方法、基于范例學習、遺傳算法等；統(tǒng)計方法可細分為回歸分

16、析、判別分析、聚類分析、探索性分析等；神經(jīng)網(wǎng)絡方法可細分為前向神經(jīng)網(wǎng)絡、自組織神經(jīng)網(wǎng)絡等；數(shù)據(jù)庫方法主要是多維數(shù)據(jù)分析或聯(lián)機分析方法，另外還有面向?qū)傩缘臍w納方法。 第14頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 8.2.1分類和預測 分類是數(shù)據(jù)挖掘中一項非常重要的任務，目前在商業(yè)上的應用最多。分類的目的是提出一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。分類和回歸都可用于預測，預測的目的是從歷史數(shù)據(jù)記錄中自動推導出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進行預測。 分類的效果一般和數(shù)據(jù)的特點有關(guān)，有的數(shù)據(jù)噪聲大，有的有缺省值，有的分布稀疏，有的字段

17、或?qū)傩蚤g相關(guān)性強，有的屬性是離散的而有的是連續(xù)值或混合式的。目前普遍認為不存在某種方法能適合各種特點的數(shù)據(jù)。下面介紹幾種常用的分類算法。第15頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 1決策樹 構(gòu)造一個決策樹分類器通常分為兩步：樹的生成和剪枝。樹的生成采用自上而下的遞歸分治法。如果當前訓練例子集合中的所有實例是同類的, 構(gòu)造一個葉節(jié)點, 節(jié)點內(nèi)容即是該類別。否則, 根據(jù)某種策略選擇一個屬性, 按照該屬性的不同取值, 把當前實例集合劃分為若干子集合。對每個子集合重復此過程, 直到當前集中的實例是同類的為止。剪枝就是剪去那些不會增大樹的錯誤預測率的分枝。 經(jīng)過剪枝, 不僅能有效的克服噪聲, 還使樹變

18、得簡單, 容易理解。生成最優(yōu)的決策樹同樣是NP問題。 目前的決策樹算法通過啟發(fā)式屬性選擇策略來解決問題。 第16頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 2AQ算法 存在大量的基于規(guī)則的分類方法，以及對規(guī)則進行后處理如剪枝等工作。AQ是一種典型的基于規(guī)則的方法。 AQ是一種覆蓋算法，由Micalski和洪家榮提出。算法的核心是所謂的”星”。 一個正例集合在反例集合背景下的星是覆蓋所有正例而排斥所有反例的極大復合的集合。算法就是要求得這樣的最大復合。算法從正例中的一個種子的一個選擇子(屬性值對)出發(fā)，逐漸地增加選擇子，直到找到覆蓋所有正例的最大復合。在最初的AQ11基礎上，AQ15增加了漸近學習，

19、構(gòu)造學習和近似推理等功能，成為比較成熟的覆蓋算法。第17頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 3Bayes方法 貝葉斯統(tǒng)計分析起源于英國學者Bayes T.R.的一篇論文An essay towards solving a problem in the doctrine of chances(1763年), 給出了著名的貝葉斯公式和一種歸納推理方法。 其后一些統(tǒng)計學家將其發(fā)展成一種系統(tǒng)的統(tǒng)計推斷方法，到本世紀30年代形成了貝葉斯學派，5060年代發(fā)展成了一個有影響的統(tǒng)計學派。 貝葉斯方法的學習機制是利用貝葉斯公式將先驗信息與樣本信息綜合得到后驗信息。 在數(shù)據(jù)挖掘中，主要有兩種bayes方法，

20、即Nave-bayes方法和bayes網(wǎng)絡。前者直接利用bayes公式進行預測，把從訓練樣本中計算出的各個屬性值和類別頻率比作為先驗概率， 并假定各個屬性之間是獨立的，就可以用 bayes公式和相應的概率公司計算出要預測實例的對各類別的條件概率值。選取概率值最大的類別作為預測值。此方法簡單易行并且具有較好的精度。第18頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 4神經(jīng)網(wǎng)絡 神經(jīng)網(wǎng)絡是一種很好的函數(shù)逼近工具，在過去十幾年里取得了飛速的發(fā)展，發(fā)展出了很多的模型及其改進，例如BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。雖然試驗表明，神經(jīng)網(wǎng)絡在某些分類問題上具有比符號方

21、法更好的表現(xiàn)，但是神經(jīng)網(wǎng)絡用于數(shù)據(jù)挖掘主要不利之處在于無法獲取顯式的規(guī)則。近年來許多學者提出了從神經(jīng)網(wǎng)絡中提取規(guī)則的方法，典型的如KBANN等。主要可以分為三類方法：分解法、學習法以及這兩種的折衷方法 第19頁，共47頁。5粗糙集 粗糙集(Rougn Set,RS)理論是一種刻劃不完整性和不確定性的數(shù)學工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，是由波蘭科學家Z. Pawlak在1982年首先提出。粗糙集理論的研究對象是由一個多值屬性（特征、癥狀、特性等）級和描述的一個對象集合，對于每個對象及其屬性都有一個值作為其描述符號，對象、屬性和

22、描述符號是表達決策問題的3個基本要素。通常關(guān)于對象的可得到的信息不一定足以劃分其成員類別，換句話說，這種不精確性導致了對象的不可分辨性。給定對象間的一種等價關(guān)系，即導致由等價類構(gòu)成的近似空間的不分明關(guān)系，Rough集就用不分明對象類形成的上近似和下近似來描述。前者指的是所有對象都一定被包含，后者指的是所有對象可能被包含。8.2 數(shù)據(jù)挖掘技術(shù)簡介 第20頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 8.2.2聚類分析 聚類和數(shù)據(jù)挖掘中的分類不同，聚類是在預先不知道目標數(shù)據(jù)庫到底有多少類的情況下，希望將所有的記錄組成不同的類或者說聚類，并且使得在這種分類情況下，以某種度量為標準的相似性，在同一聚類之間最

23、小化，而在不同聚類之間最大化。換句話說，聚類（clustering）是一個將數(shù)據(jù)集劃分為若干組或類的過程，并使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度；而不同組中的數(shù)據(jù)對象是不相似的。相似或不相似的描述是基于數(shù)據(jù)描述屬性的取值來確定的。通常就是利用（各對象間）距離來進行表示的。許多領域，包括數(shù)據(jù)挖掘、統(tǒng)計學和機器學習都有聚類研究和應用。 第21頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 1.聚類分析概念 將一組物理的或抽象的對象，根據(jù)它們之間的相似程度，分為若干組；其中相似的對象構(gòu)成一組，這一過程就稱為聚類過程（clustering）。一個聚類就是由彼此相似的一組對象所構(gòu)成的集合；不同聚類中對象是不

24、相似的。就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)項（items）之間所存在的有價值聯(lián)系。在許多應用，一個聚類中所有對象常常被當作一個對象來進行處理或分析等操作。第22頁，共47頁。8.2 數(shù)據(jù)挖掘技術(shù)簡介 2.聚類分析的主要方法 在聚類分析中有大量的算法可供選擇。需要根據(jù)應用所涉及的數(shù)據(jù)類型、聚類的目的以及具體應用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具，那么就可以使用若干聚類算法對同一個數(shù)據(jù)集進行處理以觀察可能獲得的有關(guān)（數(shù)據(jù)特征）描述。通常聚類分析算法可以劃分為以下幾大類： （1）劃分方法（2）層次方法（3）基于密度方法（4）基于網(wǎng)格方法（5）基于模型方法第23頁，共47頁。

25、8.3 關(guān)聯(lián)規(guī)則挖掘 關(guān)聯(lián)規(guī)則的概念是由.grawal、Imieelinski和Swami提出來的。在數(shù)據(jù)挖掘領域,關(guān)聯(lián)規(guī)則的挖掘有著廣泛的應用背景。關(guān)聯(lián)規(guī)則挖掘目的就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識。隨著收集和存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，人們對從這些數(shù)據(jù)中挖掘相應的關(guān)聯(lián)知識越來越有興趣。例如：從大量的商業(yè)交易記錄中發(fā)現(xiàn)有價值的關(guān)聯(lián)知識就可幫助進行商品目錄的設計、交叉營銷或幫助進行其它有關(guān)的商業(yè)決策。第24頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘8.3.1關(guān)聯(lián)規(guī)則概述 關(guān)聯(lián)規(guī)則是描述在一個事件中不同的項之間同時出現(xiàn)的規(guī)律的知識模式，具體地針對一個事物數(shù)據(jù)庫來說，關(guān)聯(lián)

26、規(guī)則就是通過量化的數(shù)據(jù)描述某種物品的出現(xiàn)對另一種物品的出現(xiàn)有多大的影響。 關(guān)聯(lián)規(guī)則的挖掘研究具有以下發(fā)展趨勢：一是從單一的概念層次關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)發(fā)展到多概念層次的關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)。也就是說在很多應用中，挖掘規(guī)則可以作用到數(shù)據(jù)庫的不同層面上。例如，在分析超市銷售事務數(shù)據(jù)庫過程中，若單單從數(shù)據(jù)庫的原始字段，如面包、牛奶等等進行規(guī)則挖掘，可能很難發(fā)現(xiàn)令人感興趣的規(guī)則。這時如果把一些抽象層次的概念也考慮進去，比如面包、牛奶更抽象的概念食品，則有可能新的更為抽象的規(guī)則。所以研究在數(shù)據(jù)庫中的不同的抽象層次上發(fā)掘規(guī)則是數(shù)據(jù)挖掘新的研究內(nèi)容。 第25頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘 二是提高算法效率。顯然在挖

27、掘規(guī)則過程中，需要處理大量的數(shù)據(jù)庫記錄，并且可能對數(shù)據(jù)庫記錄進行多次掃描，所以如何提高算法的效率是非常重要的。目前共有三種提高效率的思路，一種技術(shù)是減少數(shù)據(jù)庫掃描次數(shù)；另一種是利用采樣技術(shù)，對要挖掘的數(shù)據(jù)集合進行選擇；最后是采用并行數(shù)據(jù)挖掘技術(shù)。 此外，對獲取的關(guān)聯(lián)規(guī)則總規(guī)模的控制，即如何選擇和進一步處理所獲得的關(guān)聯(lián)規(guī)則；模糊關(guān)聯(lián)規(guī)則的獲取和發(fā)現(xiàn)；高效的關(guān)聯(lián)規(guī)則挖掘算法等也是關(guān)聯(lián)規(guī)則要研究的關(guān)鍵性課題。從采掘的對象上看，由僅在關(guān)系數(shù)據(jù)庫中進行挖掘擴充到在文本和web數(shù)據(jù)中進行關(guān)聯(lián)的發(fā)現(xiàn)等課題也是未來關(guān)聯(lián)規(guī)則挖掘要深入研究和解決的問題。第26頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘下面介紹關(guān)聯(lián)規(guī)則挖掘

28、過程中所涉及到的有關(guān)概念和術(shù)語。(1)數(shù)據(jù)項和數(shù)據(jù)項集設I =i1，i2，.，im是n個不同項目的集合,則每一個項目ik(=1,2,n)稱為數(shù)據(jù)項(item)。為數(shù)據(jù)項集(itemset),n為數(shù)據(jù)項集的長度。長度為的數(shù)據(jù)項集稱為-項集(k-itemsets)。(2)事務一個事務(Transaction)是數(shù)據(jù)項集中的一組項目的集合,即TI。每一個事務賦予一個唯一的標識符TID。所有事務的全體就構(gòu)成一個事務數(shù)據(jù)庫。(3)數(shù)據(jù)項集的支持度數(shù)據(jù)項集的支持度(Support)就是數(shù)據(jù)項集出現(xiàn)的概率。設是中的一個子集,稱一個事務包含,當且僅當。的支持度為: Support ()=()第27頁，共47頁

29、。8.3 關(guān)聯(lián)規(guī)則挖掘(4)關(guān)聯(lián)規(guī)則及其支持度和置信度 一個關(guān)聯(lián)規(guī)則就是具有“ XY ”形式的蘊含式，其中有X I， Y I且XY= 。稱作規(guī)則的前提,是結(jié)果。規(guī)則XY的支持度為,是指在中有%的事務,既包含同時又包含,即同時出現(xiàn)數(shù)據(jù)項集和的概率。其表達式為Support(XY)=P(XY)。規(guī)則XY的置信度(Confidence)為,是指在中包含的事務有%的事務同時又包含, 即出現(xiàn)數(shù)據(jù)項集的前提下,出現(xiàn)數(shù)據(jù)項集的概率,其表達式為confidence(XY)=P(YX)。支持度體現(xiàn)了項目集在交易集中出現(xiàn)的頻度,置信度體現(xiàn)了項目集和之間的關(guān)聯(lián)程度。（5）頻繁項集一個項集的出現(xiàn)頻度就是整個交易數(shù)據(jù)集

30、D中包含該項集的交易記錄數(shù), 若一個項集的出現(xiàn)頻度大于最小支持度閾值乘以交易記錄集D中記錄數(shù)，那么就稱該項集滿足最小支持度閾值；而滿足最小支持度閾值所對應的交易記錄數(shù)就稱為最小支持頻度。 第28頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘滿足最小支持閾值的項集就稱為頻繁項集(或稱大項集)。所有頻繁k-項集的集合就記為Lk。挖掘關(guān)聯(lián)規(guī)則的問題就是找出這樣一些規(guī)則,它們的Support和confidence分別大于用戶指定的最小支持度(minisupport)和最小置信度(miniconfidence)的限度,稱這些規(guī)則為強規(guī)則。通常為方便起見，都將最小支持度閾值簡寫為min_sup；最小信任度閾值簡寫為m

31、in_conf。這兩個閾值均在0%到100%之間，而不是0到1之間。 如果不考慮關(guān)聯(lián)規(guī)則的支持度和可信度，那么在事務數(shù)據(jù)庫中存在無窮多的關(guān)聯(lián)規(guī)則。事實上，人們一般只對滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。因此，為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，需要給定兩個閾值:最小支持度和最小可信度。前者即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小支持度，它表示了一個項集在統(tǒng)計意義上的需滿足的最低程度;后者即用戶規(guī)定的關(guān)聯(lián)規(guī)則必須滿足的最小可信度，它反應了關(guān)聯(lián)規(guī)則的最低可靠度。第29頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘挖掘關(guān)聯(lián)規(guī)則主要包含以下二個步驟：步驟一：發(fā)現(xiàn)所有的頻繁項集，根據(jù)定義，這些項集的頻度至少應等于（預先設置

32、的）最小支持頻度；步驟二：根據(jù)所獲得的頻繁項集，產(chǎn)生相應的強關(guān)聯(lián)規(guī)則。根據(jù)定義這些規(guī)則必須滿足最小信任度閾值。 此外還可利用有趣性度量標準來幫助挖掘有價值的關(guān)聯(lián)規(guī)則知識。由于步驟二中的相應操作極為簡單，因此挖掘關(guān)聯(lián)規(guī)則的整個性能就是由步驟一中的操作處理所決定。第30頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘8.3.2關(guān)聯(lián)規(guī)則的分類 （1）根據(jù)關(guān)聯(lián)規(guī)則所處理的變量的類別來劃分，關(guān)聯(lián)規(guī)則可分為布爾型和數(shù)值型（2）根據(jù)規(guī)則中數(shù)據(jù)的維數(shù)來劃分，關(guān)聯(lián)規(guī)則可分為單維的和多維的（3）根據(jù)規(guī)則中數(shù)據(jù)挖掘的抽象層次來劃分，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則（4）根據(jù)關(guān)聯(lián)規(guī)則所涉及的關(guān)聯(lián)特性來進行分類劃分 關(guān)聯(lián)挖掘可擴展

33、到其它數(shù)據(jù)挖掘應用領域，如進行分類學習，或進行相關(guān)分析（即可以通過相關(guān)數(shù)據(jù)項出現(xiàn)或不出現(xiàn)來進行相關(guān)屬性識別與分析）第31頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘8.3.3經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法 1Apriori算法 Apriori算法是挖掘產(chǎn)生布爾關(guān)聯(lián)規(guī)則所需頻繁項集的基本算法；它也是一個很有影響的關(guān)聯(lián)規(guī)則挖掘算法。Apriori算法就是根據(jù)有關(guān)頻繁項集特性的先驗知識而命名的。該算法利用了一個層次順序搜索的循環(huán)方法來完成頻繁項集的挖掘工作。這一循環(huán)方法就是利用k-項集來產(chǎn)生(k+1)-項集。具體做法就是：首先找出頻繁1-項集，記為L1；然后利用L1來挖掘L2 ，即頻繁2-項集；不斷如此循環(huán)下去直到無法

34、發(fā)現(xiàn)更多的頻繁k-項集為止。每挖掘一層Lk就需要掃描整個數(shù)據(jù)庫一遍。 第32頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘算法8.1：（Apriori）利用層次循環(huán)發(fā)現(xiàn)頻繁項集。輸入：交易數(shù)據(jù)庫D最小支持閾值min_sup輸出：Li，D中的頻繁項集；處理流程：(1) L1=find_frequent_1_itemset(D)；/發(fā)現(xiàn)1-項集(2) for(k=2;Lk-1;k+) (3) Ck = apriori-gen ( Lk-1, min_sup); / 根據(jù)頻繁(k-1)-項集產(chǎn)生候選k-項集(4) for each t D /掃描數(shù)據(jù)庫，以確定每個候選項集的支持頻度(5) Ct = subset

35、( Ck, t ); /獲得t所包含的候選項集(6) for each c Ct c.count + ; (7) Lk = c Ck | c.count min_sup(8) Return L=k Lk ;第33頁，共47頁。8.3 關(guān)聯(lián)規(guī)則挖掘2. Apriori算法的改進 雖然Apriori算法自身已經(jīng)進行了一定的優(yōu)化，但是在實際應用中，還是存在不令人滿意的地方，于是人們相繼提出了一個改進的方法。下面介紹三種改進方法。(1)基于劃分的方法(2)基于HASH技術(shù)的方法(3)基于采樣技術(shù)的方法第34頁，共47頁。8.3.4多層關(guān)聯(lián)規(guī)則挖掘 對于很多應用來說，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)

36、最細節(jié)的層次上發(fā)現(xiàn)一些強關(guān)聯(lián)規(guī)則。但我們引入概念層次后，就可以在就高的層次上進行挖掘。雖然較高層次得到的規(guī)則可能是跟普通的信息，但是對于一個用戶來說是普通的信息，對于另一個用戶卻未必如此。所以數(shù)據(jù)挖掘應該提供一種在多個層次上進行挖掘的功能。 多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度-可信度”的框架。一般地，可以采用自頂向下策略，由概念層1開始向下，到較低的更特定的概念層，對每個概念層分別計算頻繁項集，直到不能再找到頻繁項集。也就是說一旦找到概念層1的所有頻繁項集，開始在第2層找頻繁項集，找出第2層所有頻繁項集后，在開始找第3層，如此下去。對于每一層可以是用發(fā)現(xiàn)頻繁項集的任何算法，如前面介紹的A

37、priori算法及其任意變形。不過，在支持度的設置問題上有一些又考慮的東西。通常，根據(jù)規(guī)則中涉及到的層次，多層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則。8.3 關(guān)聯(lián)規(guī)則挖掘第35頁，共47頁。8.4 序列模式挖掘 序列模式挖掘是基于時間或者其它序列的經(jīng)常發(fā)生的模式。序列模式挖掘與關(guān)聯(lián)規(guī)則挖掘相似, 其目的也是為了挖掘數(shù)據(jù)之間的關(guān)系。但序列模式挖掘側(cè)重點在于分析數(shù)據(jù)間的前后序列關(guān)系。它能發(fā)現(xiàn)數(shù)據(jù)庫中形如“在某一段時間內(nèi), 顧客購買商品A , 接著購買商品B , 而后購買商品C , 即序列A B C 出現(xiàn)的頻度較高”之類的知識。第36頁，共47頁。8.4 序列模式挖掘8.4.1序列模式的概念及定

38、義 1數(shù)據(jù)源的形式 假設我們給定一個由客戶交易(customer transaction)組成的大型數(shù)據(jù)庫D，每個交易(transaction)由客戶號(customer-id)、交易時間(transaction-time)及在交易中購買的項(item)組成。同一個顧客在一個交易時間只能進行一次交易，我們不考慮顧客在一次交易中所購買物品的數(shù)量，每種物品都由一個二進制變量代替，只關(guān)心一個項目在交易中被購買與否。2基本定義 序列模式的元素也可以不只是一個元素(如一本書)，它也可以是一個項集(item set)。所謂項集，指的是多個物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作

39、是由兩個項(item)組成的項集，它也可以作為某一個序列模式的元素。 第37頁，共47頁。8.4 序列模式挖掘 一個序列(sequence)是一列排好序的項集。不失一般性我們假定項集中的項由一些連續(xù)整數(shù)代替，這樣一個項集i可以表示為(i1,i2im)，而這里的ij代表了一個項。一個序列s可以表示為，這里的sj代表的是一個項集。 設有兩個序列a 和b ，如果存在整數(shù)i1i2in且a1包含于bi1，a2包含于bi2，an包含于bin，則稱序列a包含于序列b。比如序列包含于序列，因為(3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。但是序列不包含于，反之亦然。前者表示項3

40、和項5是先后購買的，而后者則表示項3和項5是同時購買的，這就是區(qū)別所在。在一個序列集(a set of sequences)中如果序列s不包含于任何其他序列中，則稱序列s為最大的(maximal)。第38頁，共47頁。8.4 序列模式挖掘 一個客戶所有的事務(transactions)可以綜合的看成是一個序列，每一個事務都由相應的一個項集來表示。事務按交易時間序排列就成了一個序列。我們稱這樣的序列為客戶序列(customer-sequence)。通常，將一個客戶的交易按交易時間排序成T1 ，T2 ，Tn。Ti中的項集定義成itemset(Ti)。這樣，這個客戶的客戶序列就成了這樣的一個序列：i

41、temset(T1) itemset(T2) itemset(Tn)。如圖8.6所示。 如果一個序列s包含于一個客戶序列中，則我們稱該客戶支持(support)序列s。一個具體序列的支持(support)定義為那一部分支持該序列的客戶總數(shù)。 給定一個由客戶交易組成的數(shù)據(jù)庫D，挖掘序列模式的問題就是在那些具有客戶指定最小支持度(minimum support)的序列中找出最大序列(maximal sequence)。而每個這樣的最大序列就代表了一個序列模式(sequential pattern)。第39頁，共47頁。8.4 序列模式挖掘8.4.2序列模式的發(fā)現(xiàn) 一個序列的長度(length)是它

42、所包含的項集(itemset)的總數(shù)。具有k長度的序列稱為k-序列。有兩個序列x和y，x，y表示x和y經(jīng)過連接運算形成的新的序列。 一個項集i的支持是指那一部分在單次交易中買了項集i中的項的那一部分客戶。于是項集i和1-序列具有相同的支持。具有最小支持(minimum support)的項集稱為大項集(large itemset or litemset)。需要注意的是，大序列中的每一個項集都必須具有最小支持。因此，任何大序列都是大項集的列表所組成。 分5個具體階段來找出所有的序列模式。其找出過程分為: 排序階段、大項集階段、轉(zhuǎn)換階段、序列階段和選最大階段。第40頁，共47頁。8.4 序列模式挖

43、掘8.4.3序列階段的算法 序列階段算法的基本結(jié)構(gòu)是對數(shù)據(jù)進行多次遍歷。在每次遍歷中，我們從一個由大序列(large sequence)組成的種子集(seed set)開始，利用這個種子集，可以產(chǎn)生新的潛在的大序列。在遍歷數(shù)據(jù)的過程中，我們計算出這些候選序列的支持度，這樣在一次遍歷的最后，我們就可以決定哪些候選序列是真正的大序列，這些序列構(gòu)成下一次遍歷的種子集。在第一次遍歷前，所有在大項集階段得到的具有最小支持度(minimum support)的大1-序列組成了種子集。 這里給出兩種算法，分別稱為count-all和count-some。count-all 累計所有大序 列，包括非最大序列(

44、non-maximal sequence)，在找最大階段(maximal phase)，這些非最大序列必須被刪除。給出一個count-all算法，稱為AprioriAll，給出一個count-some算法，稱為AprioriSome。第41頁，共47頁。8.5 WEB挖掘8.5.1概述 隨著Internet的日益普及，人們通過Web接觸到了比以前多得多的數(shù)據(jù)和信息。然而，盡管Web上有海量的數(shù)據(jù)，但由于Web頁面過于復雜、而且是無結(jié)構(gòu)的、動態(tài)的，導致人們難以迅速、方便地在Web上找到所需要的數(shù)據(jù)和信息。在面臨如此龐大的信息空間以及Web組織無序化的情況下，搜索是解決網(wǎng)絡信息無序和混亂的一個基本

45、方法，現(xiàn)代社會的競爭趨勢要求能夠?qū)@些信息進行實時和深層次的分析，因此，如何利用數(shù)據(jù)挖掘知識，進一步提高Web信息搜索的性能成為眾多學者研究的熱點。 Web挖掘就是從Web文檔和Web活動中抽取感興趣的、潛在的有用模式和隱藏的信息。Web挖掘可以在確定權(quán)威頁面、Web文檔分類、Web Log挖掘、智能查詢等在很多方面發(fā)揮作用。 與傳統(tǒng)數(shù)據(jù)挖掘技術(shù)所面對的數(shù)據(jù)相比，Web挖掘的數(shù)據(jù)源具有以下特點： 第42頁，共47頁。8.5 WEB挖掘（1）對有效的數(shù)據(jù)倉庫和數(shù)據(jù)挖掘而言，Web似乎太龐大了。Web的數(shù)據(jù)量目前以Terabytes計算，而且仍然在迅速地增長。這使得幾乎不可能去構(gòu)造一個數(shù)據(jù)倉庫來復

46、制、存儲或集成Web上的所有數(shù)據(jù)。 （2）Web頁面的復雜性高于任何傳統(tǒng)的文本文檔。Web頁面缺乏統(tǒng)一的結(jié)構(gòu)，它包含了遠比任何一組書籍或文本文檔多得多的風格和內(nèi)容。（3）Web是一個動態(tài)性極強的信息源。Web不僅以極快的速度增長，而且其信息還在不斷地發(fā)生著更新。新聞、股票市場、公司廣告和Web服務中心都在不斷地更新著各自的頁面。鏈接信息和訪問記錄也在頻繁地更新之中。（4）Web面對的是一個廣泛的形形色色的用戶群體。目前因特網(wǎng)用戶在不斷的快速增加，各個用戶可以有不同的背景、興趣和使用目的。大部分的用戶并不了解信息網(wǎng)絡結(jié)構(gòu)，不清楚搜索的高昂代價，極易在網(wǎng)絡中迷失方向，也極易在跳躍式的訪問中煩亂不已

47、和在等待中失去耐心。因此web挖掘應能根據(jù)不同的用戶提供個性化的服務。第43頁，共47頁。8.5 WEB挖掘（5）web上的信息只有很小的一部分是相關(guān)的或有用的。因為每個用戶可能只關(guān)心很小的對自己有用的一部分信息，其余的信息對這個用戶來說就是不感興趣的，而且會淹沒所希望搜索的結(jié)果。 Web 是一個巨大的、廣泛分布的、異構(gòu)的、半結(jié)構(gòu)的、超文本P超媒體的、相互聯(lián)系并且不斷變化的信息倉庫, 其中包括鏈接信息、訪問使用信息等。這大量的非結(jié)構(gòu)化數(shù)據(jù)是無法使用現(xiàn)有數(shù)據(jù)庫管理系統(tǒng)來處理和管理的, 這就對Web 進行有效的信息抽取和知識發(fā)現(xiàn)帶來了極大的挑戰(zhàn), 也使得Web 數(shù)據(jù)挖掘更加復雜。 web上的信息的多樣性決定了web數(shù)據(jù)挖掘的多樣性。按照處理對象的不同我們將web數(shù)據(jù)挖掘分為三大類：Web內(nèi)容挖掘、Web結(jié)構(gòu)挖掘和Web使用記錄挖掘。第44頁，共47頁。8.6 數(shù)據(jù)挖掘的研究熱點與發(fā)展趨勢 8.6.1研究熱點 隨著網(wǎng)絡技術(shù)