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

第八章

數(shù)據(jù)挖掘人工智能華中師范大學(xué)計算機科學(xué)系第八章人工智能華中師范大學(xué)計算機科學(xué)系1第八章數(shù)據(jù)挖掘數(shù)據(jù)挖掘（DataMining）是一個多學(xué)科交叉研究領(lǐng)域，它融合了數(shù)據(jù)庫技術(shù)、人工智能、機器學(xué)習(xí)、統(tǒng)計學(xué)、知識工程、面向?qū)ο蠓椒?、信息檢索、高性能計算以及數(shù)據(jù)可視化等最新技術(shù)的研究成果。經(jīng)過十幾年的研究，產(chǎn)生了許多新概念和方法。特別是最近幾年來，一些基本概念和方法趨于清晰，它的研究正向著更深入的方向發(fā)展。數(shù)據(jù)挖掘技術(shù)正在以一種全新的概念改變著人類利用數(shù)據(jù)的方式，它被認為是未來信息處理的骨干技術(shù)之一，網(wǎng)絡(luò)之后的下一個技術(shù)熱點。第八章數(shù)據(jù)挖掘數(shù)據(jù)挖掘（DataMining）是28.1數(shù)據(jù)挖掘概述8.1.1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘（DataMining）是一門受到來自各種不同領(lǐng)域的研究者關(guān)注的交叉性學(xué)科，有很多不同的術(shù)語名稱，除了常用的“數(shù)據(jù)挖掘”和“知識發(fā)現(xiàn)”之外，與數(shù)據(jù)挖掘相近的同義詞有數(shù)據(jù)融合、數(shù)據(jù)分析、知識抽取、信息發(fā)現(xiàn)、數(shù)據(jù)采掘、知識獲取、數(shù)據(jù)考古、信息收獲和決策支持等。從技術(shù)的角度講，數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。這個定義包括好幾層含義：數(shù)據(jù)源必須是真實的、大量的、含噪聲的；發(fā)現(xiàn)的是用戶感興趣的知識；發(fā)現(xiàn)的知識要可接受、可理解、可運用；并不要求發(fā)現(xiàn)放之四海皆準(zhǔn)的知識，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機器定理證明，只要能支持特定的發(fā)現(xiàn)問題即可。實際上，利用數(shù)據(jù)挖掘從數(shù)據(jù)集中所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件，面向特定領(lǐng)域的，同時還要能夠易于被用戶理解。最好能用自然語言表達所發(fā)現(xiàn)的結(jié)果。8.1數(shù)據(jù)挖掘概述8.1.1數(shù)據(jù)挖掘的定義38.1數(shù)據(jù)挖掘概述從商業(yè)的角度講，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要特點是對商業(yè)數(shù)據(jù)庫中的大量業(yè)務(wù)數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。簡而言之，數(shù)據(jù)挖掘其實是一類深層次的數(shù)據(jù)分析方法。數(shù)據(jù)分析本身已經(jīng)有很多年的歷史，只不過在過去數(shù)據(jù)收集和分析的目的是用于科學(xué)研究，另外，由于當(dāng)時計算能力的限制，對大數(shù)據(jù)量進行分析的復(fù)雜數(shù)據(jù)分析方法受到很大限制?，F(xiàn)在，由于各行業(yè)業(yè)務(wù)自動化的實現(xiàn)，商業(yè)領(lǐng)域產(chǎn)生了大量的業(yè)務(wù)數(shù)據(jù)，這些數(shù)據(jù)不再是為了分析的目的而收集的，而是由于純機會的商業(yè)運作而產(chǎn)生。分析這些數(shù)據(jù)也不再是單純?yōu)榱搜芯康男枰饕菫樯虡I(yè)決策提供真正有價值的信息，進而獲得利潤。8.1數(shù)據(jù)挖掘概述從商業(yè)的角度講，數(shù)據(jù)挖掘是一種新48.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ù)庫、事務(wù)數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫（SpatialDatabase）、文本數(shù)據(jù)（TextData）以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識，既然如此，那么可以說數(shù)據(jù)庫中的知識發(fā)現(xiàn)只是數(shù)據(jù)挖掘的一個方面，這是早期比較流行的觀點。因此，從這個意義說，數(shù)據(jù)挖掘就是從數(shù)據(jù)庫、數(shù)據(jù)倉庫以及其它數(shù)據(jù)存儲方式中挖掘有用知識的過程。這種描述強調(diào)了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。(2)數(shù)據(jù)挖掘是KDD過程的一個步驟在“知識發(fā)現(xiàn)96國際會議”上，許多學(xué)者建議對這兩個名詞加以區(qū)分。核心思想是：KDD是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而DataMining則是此全部過程的一個特定的、關(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是一個更廣義的范疇，它包括數(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)鍵的部分。8.1數(shù)據(jù)挖掘概述8.1.2數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)58.1數(shù)據(jù)挖掘概述（3）KDD與DataMining含義相同

也有些人認為，KDD與DataMining只是叫法不一樣，它們的含義基本相同。事實上，在現(xiàn)今的文獻中，許多場合，如技術(shù)綜述等，這兩個術(shù)語仍然不加區(qū)分地使用著。也有人說，KDD在人工智能界更流行；DataMining在數(shù)據(jù)庫界使用更多。所以，從廣義的觀點，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的、有噪聲的、不確定性的、各種存儲形式的）中，挖掘隱含在其中的、人們事先不知道的、對決策有用的知識的過程。

從上面的描述中可以看出，數(shù)據(jù)挖掘概念可以在不同的技術(shù)層面上來理解，但是其核心仍然是從數(shù)據(jù)中挖掘知識。從本質(zhì)來講，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)是有區(qū)別的，但是在很多場合人們往往不嚴格區(qū)分數(shù)據(jù)挖掘和數(shù)據(jù)庫中的知識發(fā)現(xiàn)，兩者互為使用。一般在科研領(lǐng)域中稱為KDD，而在工程領(lǐng)域則多稱為數(shù)據(jù)挖掘。8.1數(shù)據(jù)挖掘概述（3）KDD與DataMining含義68.1數(shù)據(jù)挖掘概述8.1.3數(shù)據(jù)挖掘研究的理論基礎(chǔ)數(shù)據(jù)挖掘方法可以是基于數(shù)學(xué)理論的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。從研究的歷史看，它們可能是數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、計算機科學(xué)以及其它方面的學(xué)者和工程技術(shù)人員，在數(shù)據(jù)挖掘的探討性研究過程中創(chuàng)立的理論體系。1997年，Mannila對當(dāng)時流行的數(shù)據(jù)挖掘的理論框架給出了綜述。結(jié)合最新的研究成果，有下面一些重要的理論框架可以幫助我們準(zhǔn)確地理解數(shù)據(jù)挖掘的概念與技術(shù)特點。模式發(fā)現(xiàn)架規(guī)則發(fā)現(xiàn)架構(gòu)基于概率和統(tǒng)計理論微觀經(jīng)濟學(xué)觀點基于數(shù)據(jù)壓縮理論基于歸納數(shù)據(jù)庫理論8.1數(shù)據(jù)挖掘概述8.1.3數(shù)據(jù)挖掘研究的理論基礎(chǔ)78.1數(shù)據(jù)挖掘概述8.1.4數(shù)據(jù)挖掘與其它數(shù)據(jù)處理方法的區(qū)別及聯(lián)系1．?dāng)?shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析(如查詢、報表、聯(lián)機應(yīng)用分析)的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識。數(shù)據(jù)挖掘所得到的信息應(yīng)具有先未知，有效和可實用三個特征。先前未知的信息是指該信息是預(yù)先未曾預(yù)料到的，既數(shù)據(jù)挖掘是要發(fā)現(xiàn)那些不能靠直覺發(fā)現(xiàn)的信息或知識，甚至是違背直覺的信息或知識，挖掘出的信息越是出乎意料，就可能越有價值，在商業(yè)應(yīng)用中最典型的例子就是一家連鎖店通過數(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.1數(shù)據(jù)挖掘概述8.1.4數(shù)據(jù)挖掘與其它數(shù)據(jù)處理方法的區(qū)88.1數(shù)據(jù)挖掘概述數(shù)據(jù)倉庫的數(shù)據(jù)清理和數(shù)據(jù)挖掘的數(shù)據(jù)清理差不多，如果數(shù)據(jù)在導(dǎo)入數(shù)據(jù)倉庫時已經(jīng)清理過，那很可能在做數(shù)據(jù)挖掘時就沒必要在清理一次了，而且所有的數(shù)據(jù)不一致的問題都已經(jīng)被解決了。數(shù)據(jù)挖掘庫可能是數(shù)據(jù)倉庫的一個邏輯上的子集，而不一定非得是物理上單獨的數(shù)據(jù)庫。但如果數(shù)據(jù)倉庫的計算資源已經(jīng)很緊張，那最好還是建立一個單獨的數(shù)據(jù)挖掘庫圖8.1數(shù)據(jù)挖掘苦聰數(shù)據(jù)倉庫中得出8.1數(shù)據(jù)挖掘概述數(shù)據(jù)倉庫的數(shù)據(jù)清理和數(shù)據(jù)挖掘的數(shù)據(jù)清理差98.1數(shù)據(jù)挖掘概述3.數(shù)據(jù)挖掘和在線分析處理（OLAP）數(shù)據(jù)挖掘和OLAP是完全不同的工具，基于的技術(shù)也大相徑庭。OLAP是決策支持領(lǐng)域的一部分。傳統(tǒng)的查詢和報表工具是告訴人們數(shù)據(jù)庫中都有什么，OLAP則更進一步告訴人們下一步會怎么樣和如果人們采取這樣的措施又會怎么樣。用戶首先建立一個假設(shè)，然后用OLAP檢索數(shù)據(jù)庫來驗證這個假設(shè)是否正確。數(shù)據(jù)挖掘與OLAP不同的地方是，數(shù)據(jù)挖掘不是用于驗證某個假定的模式（模型）的正確性，而是在數(shù)據(jù)庫中自己尋找模型。它在本質(zhì)上是一個歸納的過程。數(shù)據(jù)挖掘和OLAP具有一定的互補性。在利用數(shù)據(jù)挖掘出來的結(jié)論采取行動之前，也許要驗證一下如果采取這樣的行動會帶來什么樣的影響，那么OLAP工具能回答這些問題。

8.1數(shù)據(jù)挖掘概述3.數(shù)據(jù)挖掘和在線分析處理（OLAP108.1數(shù)據(jù)挖掘概述4.數(shù)據(jù)挖掘與機器學(xué)習(xí)和統(tǒng)計分析方法數(shù)據(jù)挖掘利用了人工智能（AI）和統(tǒng)計分析的進步所帶來的好處。這兩門學(xué)科都致力于模式發(fā)現(xiàn)和預(yù)測。數(shù)據(jù)挖掘不是為了替代傳統(tǒng)的統(tǒng)計分析技術(shù)。相反，它是統(tǒng)計分析方法學(xué)的延伸和擴展。大多數(shù)的統(tǒng)計分析技術(shù)都基于完善的數(shù)學(xué)理論和高超的技巧，預(yù)測的準(zhǔn)確度還是令人滿意的，但對使用者的要求很高。而隨著計算機計算能力的不斷增強，我們有可能利用計算機強大的計算能力只通過相對簡單和固定的方法完成同樣的功能。一些新興的技術(shù)同樣在知識發(fā)現(xiàn)領(lǐng)域取得了很好的效果，如神經(jīng)元網(wǎng)絡(luò)和決策樹，在足夠多的數(shù)據(jù)和計算能力下，它們幾乎不用人的關(guān)照自動就能完成許多有價值的功能。8.1數(shù)據(jù)挖掘概述4.數(shù)據(jù)挖掘與機器學(xué)習(xí)和統(tǒng)計分析方法118.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)由這三個學(xué)科的權(quán)威人物同時來任主席。目前DMKD的主要研究內(nèi)容包括基礎(chǔ)理論、發(fā)現(xiàn)算法、數(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)知識分類知識預(yù)測型知識8.1數(shù)據(jù)挖掘概述8.1.5數(shù)據(jù)挖掘的內(nèi)容128.1數(shù)據(jù)挖掘概述8.1.6數(shù)據(jù)挖掘的研究歷史和現(xiàn)狀

數(shù)據(jù)庫中發(fā)現(xiàn)知識（KDD）是在1989年召開的第11屆國際人工智能聯(lián)合學(xué)術(shù)會議(IJCAI)上首次提出的。在這屆學(xué)術(shù)會議上舉行了以KDD為主題的學(xué)術(shù)研討會，在1991年、1993年和1994年相繼舉行了KDD專題研討會。隨著KDD的深入研究以及KDD在許多領(lǐng)域的成功應(yīng)用，于1995年在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學(xué)術(shù)會議，此后每年都召開大規(guī)模的國際會議，其研究重點也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應(yīng)用，注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之間的相互滲透。第一本關(guān)于DM和KDD的國際學(xué)術(shù)雜志《DataMiningandKnowledgeDiscovery》也于97年3月創(chuàng)刊發(fā)行。亞太地區(qū)于1997年在新加坡召開了首次KDD研討會，其后又在澳大利亞的墨爾本召開了第二屆，在中國北京召開了第三屆。目前，在IJCAI、AAAI、VLDB、ACM-SIGMOD等代表人工智能與數(shù)據(jù)庫技術(shù)研究最高水平的國際學(xué)術(shù)會議上，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究都占有較大的比例，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究已經(jīng)成為當(dāng)今計算機科學(xué)與技術(shù)研究、應(yīng)用的熱點領(lǐng)域之一。8.1數(shù)據(jù)挖掘概述8.1.6數(shù)據(jù)挖掘的研究歷史和現(xiàn)狀138.2數(shù)據(jù)挖掘技術(shù)簡介

根據(jù)挖掘的任務(wù)可以分為：分類和預(yù)測模型發(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ù)挖掘方法可分為機器學(xué)習(xí)方法、統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)方法和數(shù)據(jù)庫方法。其中機器學(xué)習(xí)可細分為歸納學(xué)習(xí)方法、基于范例學(xué)習(xí)、遺傳算法等；統(tǒng)計方法可細分為回歸分析、判別分析、聚類分析、探索性分析等；神經(jīng)網(wǎng)絡(luò)方法可細分為前向神經(jīng)網(wǎng)絡(luò)、自組織神經(jīng)網(wǎng)絡(luò)等；數(shù)據(jù)庫方法主要是多維數(shù)據(jù)分析或聯(lián)機分析方法，另外還有面向?qū)傩缘臍w納方法。8.2數(shù)據(jù)挖掘技術(shù)簡介根據(jù)挖掘的任務(wù)可以分為：分148.2數(shù)據(jù)挖掘技術(shù)簡介

8.2.1分類和預(yù)測分類是數(shù)據(jù)挖掘中一項非常重要的任務(wù)，目前在商業(yè)上的應(yīng)用最多。分類的目的是提出一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。分類和回歸都可用于預(yù)測，預(yù)測的目的是從歷史數(shù)據(jù)記錄中自動推導(dǎo)出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進行預(yù)測。分類的效果一般和數(shù)據(jù)的特點有關(guān)，有的數(shù)據(jù)噪聲大，有的有缺省值，有的分布稀疏，有的字段或?qū)傩蚤g相關(guān)性強，有的屬性是離散的而有的是連續(xù)值或混合式的。目前普遍認為不存在某種方法能適合各種特點的數(shù)據(jù)。下面介紹幾種常用的分類算法。8.2數(shù)據(jù)挖掘技術(shù)簡介8.2.1分類和預(yù)測158.2數(shù)據(jù)挖掘技術(shù)簡介

1．決策樹構(gòu)造一個決策樹分類器通常分為兩步：樹的生成和剪枝。樹的生成采用自上而下的遞歸分治法。如果當(dāng)前訓(xùn)練例子集合中的所有實例是同類的,構(gòu)造一個葉節(jié)點,節(jié)點內(nèi)容即是該類別。否則,根據(jù)某種策略選擇一個屬性,按照該屬性的不同取值,把當(dāng)前實例集合劃分為若干子集合。對每個子集合重復(fù)此過程,直到當(dāng)前集中的實例是同類的為止。剪枝就是剪去那些不會增大樹的錯誤預(yù)測率的分枝。經(jīng)過剪枝,不僅能有效的克服噪聲,還使樹變得簡單,容易理解。生成最優(yōu)的決策樹同樣是NP問題。目前的決策樹算法通過啟發(fā)式屬性選擇策略來解決問題。8.2數(shù)據(jù)挖掘技術(shù)簡介1．決策樹168.2數(shù)據(jù)挖掘技術(shù)簡介

2．AQ算法存在大量的基于規(guī)則的分類方法，以及對規(guī)則進行后處理如剪枝等工作。AQ是一種典型的基于規(guī)則的方法。AQ是一種覆蓋算法，由Micalski和洪家榮提出。算法的核心是所謂的”星”。一個正例集合在反例集合背景下的星是覆蓋所有正例而排斥所有反例的極大復(fù)合的集合。算法就是要求得這樣的最大復(fù)合。算法從正例中的一個種子的一個選擇子(屬性值對)出發(fā)，逐漸地增加選擇子，直到找到覆蓋所有正例的最大復(fù)合。在最初的AQ11基礎(chǔ)上，AQ15增加了漸近學(xué)習(xí)，構(gòu)造學(xué)習(xí)和近似推理等功能，成為比較成熟的覆蓋算法。8.2數(shù)據(jù)挖掘技術(shù)簡介2．AQ算法178.2數(shù)據(jù)挖掘技術(shù)簡介

3．Bayes方法貝葉斯統(tǒng)計分析起源于英國學(xué)者BayesT.R.的一篇論文＂Anessaytowardssolvingaprobleminthedoctrineofchances＂(1763年),給出了著名的貝葉斯公式和一種歸納推理方法。其后一些統(tǒng)計學(xué)家將其發(fā)展成一種系統(tǒng)的統(tǒng)計推斷方法，到本世紀30年代形成了貝葉斯學(xué)派，50~60年代發(fā)展成了一個有影響的統(tǒng)計學(xué)派。貝葉斯方法的學(xué)習(xí)機制是利用貝葉斯公式將先驗信息與樣本信息綜合得到后驗信息。在數(shù)據(jù)挖掘中，主要有兩種bayes方法，即Na?ve-bayes方法和bayes網(wǎng)絡(luò)。前者直接利用bayes公式進行預(yù)測，把從訓(xùn)練樣本中計算出的各個屬性值和類別頻率比作為先驗概率，并假定各個屬性之間是獨立的，就可以用bayes公式和相應(yīng)的概率公司計算出要預(yù)測實例的對各類別的條件概率值。選取概率值最大的類別作為預(yù)測值。此方法簡單易行并且具有較好的精度。8.2數(shù)據(jù)挖掘技術(shù)簡介3．Bayes方法188.2數(shù)據(jù)挖掘技術(shù)簡介

4．神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是一種很好的函數(shù)逼近工具，在過去十幾年里取得了飛速的發(fā)展，發(fā)展出了很多的模型及其改進，例如BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。雖然試驗表明，神經(jīng)網(wǎng)絡(luò)在某些分類問題上具有比符號方法更好的表現(xiàn)，但是神經(jīng)網(wǎng)絡(luò)用于數(shù)據(jù)挖掘主要不利之處在于無法獲取顯式的規(guī)則。近年來許多學(xué)者提出了從神經(jīng)網(wǎng)絡(luò)中提取規(guī)則的方法，典型的如KBANN等。主要可以分為三類方法：分解法、學(xué)習(xí)法以及這兩種的折衷方法8.2數(shù)據(jù)挖掘技術(shù)簡介4．神經(jīng)網(wǎng)絡(luò)195．粗糙集粗糙集(RougnSet,RS)理論是一種刻劃不完整性和不確定性的數(shù)學(xué)工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，是由波蘭科學(xué)家Z.Pawlak在1982年首先提出。粗糙集理論的研究對象是由一個多值屬性（特征、癥狀、特性等）級和描述的一個對象集合，對于每個對象及其屬性都有一個值作為其描述符號，對象、屬性和描述符號是表達決策問題的3個基本要素。通常關(guān)于對象的可得到的信息不一定足以劃分其成員類別，換句話說，這種不精確性導(dǎo)致了對象的不可分辨性。給定對象間的一種等價關(guān)系，即導(dǎo)致由等價類構(gòu)成的近似空間的不分明關(guān)系，Rough集就用不分明對象類形成的上近似和下近似來描述。前者指的是所有對象都一定被包含，后者指的是所有對象可能被包含。8.2數(shù)據(jù)挖掘技術(shù)簡介

5．粗糙集8.2數(shù)據(jù)挖掘技術(shù)簡介208.2數(shù)據(jù)挖掘技術(shù)簡介

8.2.2聚類分析

聚類和數(shù)據(jù)挖掘中的分類不同，聚類是在預(yù)先不知道目標(biāo)數(shù)據(jù)庫到底有多少類的情況下，希望將所有的記錄組成不同的類或者說聚類，并且使得在這種分類情況下，以某種度量為標(biāo)準(zhǔn)的相似性，在同一聚類之間最小化，而在不同聚類之間最大化。換句話說，聚類（clustering）是一個將數(shù)據(jù)集劃分為若干組或類的過程，并使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度；而不同組中的數(shù)據(jù)對象是不相似的。相似或不相似的描述是基于數(shù)據(jù)描述屬性的取值來確定的。通常就是利用（各對象間）距離來進行表示的。許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計學(xué)和機器學(xué)習(xí)都有聚類研究和應(yīng)用。8.2數(shù)據(jù)挖掘技術(shù)簡介8.2.2聚類分析218.2數(shù)據(jù)挖掘技術(shù)簡介

1.聚類分析概念

將一組物理的或抽象的對象，根據(jù)它們之間的相似程度，分為若干組；其中相似的對象構(gòu)成一組，這一過程就稱為聚類過程（clustering）。一個聚類就是由彼此相似的一組對象所構(gòu)成的集合；不同聚類中對象是不相似的。就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)項（items）之間所存在的有價值聯(lián)系。在許多應(yīng)用，一個聚類中所有對象常常被當(dāng)作一個對象來進行處理或分析等操作。8.2數(shù)據(jù)挖掘技術(shù)簡介1.聚類分析概念228.2數(shù)據(jù)挖掘技術(shù)簡介

2.聚類分析的主要方法

在聚類分析中有大量的算法可供選擇。需要根據(jù)應(yīng)用所涉及的數(shù)據(jù)類型、聚類的目的以及具體應(yīng)用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具，那么就可以使用若干聚類算法對同一個數(shù)據(jù)集進行處理以觀察可能獲得的有關(guān)（數(shù)據(jù)特征）描述。通常聚類分析算法可以劃分為以下幾大類：（1）劃分方法（2）層次方法（3）基于密度方法（4）基于網(wǎng)格方法（5）基于模型方法8.2數(shù)據(jù)挖掘技術(shù)簡介2.聚類分析的主要方法238.3關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則的概念是由Ｒ.Ａgrawal、Imieelinski和Swami提出來的。在數(shù)據(jù)挖掘領(lǐng)域,關(guān)聯(lián)規(guī)則的挖掘有著廣泛的應(yīng)用背景。關(guān)聯(lián)規(guī)則挖掘目的就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識。隨著收集和存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，人們對從這些數(shù)據(jù)中挖掘相應(yīng)的關(guān)聯(lián)知識越來越有興趣。例如：從大量的商業(yè)交易記錄中發(fā)現(xiàn)有價值的關(guān)聯(lián)知識就可幫助進行商品目錄的設(shè)計、交叉營銷或幫助進行其它有關(guān)的商業(yè)決策。8.3關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則的概念是由Ｒ.Ａgraw248.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)規(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)。也就是說在很多應(yīng)用中，挖掘規(guī)則可以作用到數(shù)據(jù)庫的不同層面上。例如，在分析超市銷售事務(wù)數(shù)據(jù)庫過程中，若單單從數(shù)據(jù)庫的原始字段，如面包、牛奶等等進行規(guī)則挖掘，可能很難發(fā)現(xiàn)令人感興趣的規(guī)則。這時如果把一些抽象層次的概念也考慮進去，比如面包、牛奶更抽象的概念——食品，則有可能新的更為抽象的規(guī)則。所以研究在數(shù)據(jù)庫中的不同的抽象層次上發(fā)掘規(guī)則是數(shù)據(jù)挖掘新的研究內(nèi)容。8.3關(guān)聯(lián)規(guī)則挖掘8.3.1關(guān)聯(lián)規(guī)則概述258.3關(guān)聯(lián)規(guī)則挖掘二是提高算法效率。顯然在挖掘規(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ī)則挖掘要深入研究和解決的問題。8.3關(guān)聯(lián)規(guī)則挖掘二是提高算法效率。顯然在挖掘規(guī)則268.3關(guān)聯(lián)規(guī)則挖掘下面介紹關(guān)聯(lián)規(guī)則挖掘過程中所涉及到的有關(guān)概念和術(shù)語。(1)數(shù)據(jù)項和數(shù)據(jù)項集設(shè)I={i1，i2，...，im}是n個不同項目的集合,則每一個項目ik(ｋ=1,2,…,n)稱為數(shù)據(jù)項(item)。Ｉ為數(shù)據(jù)項集(itemset),n為數(shù)據(jù)項集的長度。長度為ｋ的數(shù)據(jù)項集稱為ｋ-項集(k-itemsets)。(2)事務(wù)一個事務(wù)Ｔ(Transaction)是數(shù)據(jù)項集Ｉ中的一組項目的集合,即TI。每一個事務(wù)賦予一個唯一的標(biāo)識符TID。所有事務(wù)的全體就構(gòu)成一個事務(wù)數(shù)據(jù)庫Ｄ。(3)數(shù)據(jù)項集的支持度數(shù)據(jù)項集的支持度(Support)就是數(shù)據(jù)項集出現(xiàn)的概率。設(shè)Ｘ是Ｉ中的一個子集,稱一個事務(wù)Ｔ包含Ｘ,當(dāng)且僅當(dāng)ＸＴ。Ｘ的支持度為:Support(Ｘ)=Ｐ(Ｘ)8.3關(guān)聯(lián)規(guī)則挖掘下面介紹關(guān)聯(lián)規(guī)則挖掘過程中所涉及到的有關(guān)278.3關(guān)聯(lián)規(guī)則挖掘(4)關(guān)聯(lián)規(guī)則及其支持度和置信度一個關(guān)聯(lián)規(guī)則就是具有“X→Y”形式的蘊含式，其中有XI，YI且X∩Y=

。Ｘ稱作規(guī)則的前提,Ｙ是結(jié)果。規(guī)則X→Y的支持度為ｓ,是指在Ｄ中有ｓ%的事務(wù),既包含Ｘ同時又包含Ｙ,即同時出現(xiàn)數(shù)據(jù)項集Ｘ和Ｙ的概率。其表達式為Support(X→Y)=P(X∩Y)。規(guī)則X→Y的置信度(Confidence)為ｃ,是指在Ｄ中包含Ｘ的事務(wù)有ｃ%的事務(wù)同時又包含Ｙ,即出現(xiàn)數(shù)據(jù)項集Ｘ的前提下,出現(xiàn)數(shù)據(jù)項集Ｙ的概率,其表達式為confidence(X→Y)=P(Y∣X)。支持度體現(xiàn)了項目集Ｘ在交易集中出現(xiàn)的頻度,置信度體現(xiàn)了項目集Ｘ和Ｙ之間的關(guān)聯(lián)程度。（5）頻繁項集一個項集的出現(xiàn)頻度就是整個交易數(shù)據(jù)集D中包含該項集的交易記錄數(shù),若一個項集的出現(xiàn)頻度大于最小支持度閾值乘以交易記錄集D中記錄數(shù)，那么就稱該項集滿足最小支持度閾值；而滿足最小支持度閾值所對應(yīng)的交易記錄數(shù)就稱為最小支持頻度。8.3關(guān)聯(lián)規(guī)則挖掘(4)關(guān)聯(lián)規(guī)則及其支持度和置信度288.3關(guān)聯(lián)規(guī)則挖掘滿足最小支持閾值的項集就稱為頻繁項集(或稱大項集)。所有頻繁k-項集的集合就記為Lk。挖掘關(guān)聯(lián)規(guī)則的問題就是找出這樣一些規(guī)則,它們的Support和confidence分別大于用戶指定的最小支持度(minisupport)和最小置信度(miniconfidence)的限度,稱這些規(guī)則為強規(guī)則。通常為方便起見，都將最小支持度閾值簡寫為min_sup；最小信任度閾值簡寫為min_conf。這兩個閾值均在0%到100%之間，而不是0到1之間。如果不考慮關(guān)聯(lián)規(guī)則的支持度和可信度，那么在事務(wù)數(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ī)則必須滿足的最小可信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠度。8.3關(guān)聯(lián)規(guī)則挖掘滿足最小支持閾值的項集就稱為頻繁項集(或298.3關(guān)聯(lián)規(guī)則挖掘挖掘關(guān)聯(lián)規(guī)則主要包含以下二個步驟：步驟一：發(fā)現(xiàn)所有的頻繁項集，根據(jù)定義，這些項集的頻度至少應(yīng)等于（預(yù)先設(shè)置的）最小支持頻度；步驟二：根據(jù)所獲得的頻繁項集，產(chǎn)生相應(yīng)的強關(guān)聯(lián)規(guī)則。根據(jù)定義這些規(guī)則必須滿足最小信任度閾值。此外還可利用有趣性度量標(biāo)準(zhǔn)來幫助挖掘有價值的關(guān)聯(lián)規(guī)則知識。由于步驟二中的相應(yīng)操作極為簡單，因此挖掘關(guān)聯(lián)規(guī)則的整個性能就是由步驟一中的操作處理所決定。8.3關(guān)聯(lián)規(guī)則挖掘挖掘關(guān)聯(lián)規(guī)則主要包含以下二個步驟：308.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)挖掘可擴展到其它數(shù)據(jù)挖掘應(yīng)用領(lǐng)域，如進行分類學(xué)習(xí)，或進行相關(guān)分析（即可以通過相關(guān)數(shù)據(jù)項出現(xiàn)或不出現(xiàn)來進行相關(guān)屬性識別與分析）8.3關(guān)聯(lián)規(guī)則挖掘8.3.2關(guān)聯(lián)規(guī)則的分類318.3關(guān)聯(lián)規(guī)則挖掘8.3.3經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法

1．Apriori算法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)下去直到無法發(fā)現(xiàn)更多的頻繁k-項集為止。每挖掘一層Lk就需要掃描整個數(shù)據(jù)庫一遍。8.3關(guān)聯(lián)規(guī)則挖掘8.3.3經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法328.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)foreachtD{//掃描數(shù)據(jù)庫，以確定每個候選項集的支持頻度(5)Ct=subset(Ck,t);//獲得t所包含的候選項集(6)foreachcCtc.count++;}(7)Lk={cCk|c.countmin_sup}(8)ReturnL=∪kLk;8.3關(guān)聯(lián)規(guī)則挖掘算法8.1：（Apriori）利用層次循338.3關(guān)聯(lián)規(guī)則挖掘2.Apriori算法的改進雖然Apriori算法自身已經(jīng)進行了一定的優(yōu)化，但是在實際應(yīng)用中，還是存在不令人滿意的地方，于是人們相繼提出了一個改進的方法。下面介紹三種改進方法。(1)基于劃分的方法(2)基于HASH技術(shù)的方法(3)基于采樣技術(shù)的方法8.3關(guān)聯(lián)規(guī)則挖掘2.Apriori算法的改進348.3.4多層關(guān)聯(lián)規(guī)則挖掘?qū)τ诤芏鄳?yīng)用來說，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)最細節(jié)的層次上發(fā)現(xiàn)一些強關(guān)聯(lián)規(guī)則。但我們引入概念層次后，就可以在就高的層次上進行挖掘。雖然較高層次得到的規(guī)則可能是跟普通的信息，但是對于一個用戶來說是普通的信息，對于另一個用戶卻未必如此。所以數(shù)據(jù)挖掘應(yīng)該提供一種在多個層次上進行挖掘的功能。多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度-可信度”的框架。一般地，可以采用自頂向下策略，由概念層1開始向下，到較低的更特定的概念層，對每個概念層分別計算頻繁項集，直到不能再找到頻繁項集。也就是說一旦找到概念層1的所有頻繁項集，開始在第2層找頻繁項集，找出第2層所有頻繁項集后，在開始找第3層，如此下去。對于每一層可以是用發(fā)現(xiàn)頻繁項集的任何算法，如前面介紹的Apriori算法及其任意變形。不過，在支持度的設(shè)置問題上有一些又考慮的東西。通常，根據(jù)規(guī)則中涉及到的層次，多層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則。8.3關(guān)聯(lián)規(guī)則挖掘8.3.4多層關(guān)聯(lián)規(guī)則挖掘8.3關(guān)聯(lián)規(guī)則挖掘358.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)的頻度較高”之類的知識。8.4序列模式挖掘序列模式挖掘是基于時間或者其它序368.4序列模式挖掘8.4.1序列模式的概念及定義

1．?dāng)?shù)據(jù)源的形式假設(shè)我們給定一個由客戶交易(customertransaction)組成的大型數(shù)據(jù)庫D，每個交易(transaction)由客戶號(customer-id)、交易時間(transaction-time)及在交易中購買的項(item)組成。同一個顧客在一個交易時間只能進行一次交易，我們不考慮顧客在一次交易中所購買物品的數(shù)量，每種物品都由一個二進制變量代替，只關(guān)心一個項目在交易中被購買與否。2．基本定義序列模式的元素也可以不只是一個元素(如一本書)，它也可以是一個項集(itemset)。所謂項集，指的是多個物品組成的集合，內(nèi)部元素不分排列順序，比如“枕頭和枕頭套”就可以看作是由兩個項(item)組成的項集，它也可以作為某一個序列模式的元素。8.4序列模式挖掘8.4.1序列模式的概念及定義378.4序列模式挖掘一個序列(sequence)是一列排好序的項集。不失一般性我們假定項集中的項由一些連續(xù)整數(shù)代替，這樣一個項集i可以表示為(i1,i2…im)，而這里的ij代表了一個項。一個序列s可以表示為<s1,s2…sn>，這里的sj代表的是一個項集。設(shè)有兩個序列a<a1,a2…an>和b<b1,b2…bm>，如果存在整數(shù)i1<i2<…<in且a1包含于bi1，a2包含于bi2，…，an包含于bin，則稱序列a包含于序列b。比如序列<(3)(4,5)(8)>包含于序列<(7)(3,8)(9)(4,5,6)(8)>，因為(3)包含于(3,8)，(4,5)包含于(4,5,6)以及(8)包含于(8)。但是序列<(3)(5)>不包含于<(3,5)>，反之亦然。前者表示項3和項5是先后購買的，而后者則表示項3和項5是同時購買的，這就是區(qū)別所在。在一個序列集(asetofsequences)中如果序列s不包含于任何其他序列中，則稱序列s為最大的(maximal)。8.4序列模式挖掘一個序列(sequence)388.4序列模式挖掘一個客戶所有的事務(wù)(transactions)可以綜合的看成是一個序列，每一個事務(wù)都由相應(yīng)的一個項集來表示。事務(wù)按交易時間序排列就成了一個序列。我們稱這樣的序列為客戶序列(customer-sequence)。通常，將一個客戶的交易按交易時間排序成T1，T2，……，Tn。Ti中的項集定義成itemset(Ti)。這樣，這個客戶的客戶序列就成了這樣的一個序列：〈itemset(T1)itemset(T2)…itemset(Tn)〉。如圖8.6所示。如果一個序列s包含于一個客戶序列中，則我們稱該客戶支持(support)序列s。一個具體序列的支持(support)定義為那一部分支持該序列的客戶總數(shù)。給定一個由客戶交易組成的數(shù)據(jù)庫D，挖掘序列模式的問題就是在那些具有客戶指定最小支持度(minimumsupport)的序列中找出最大序列(maximalsequence)。而每個這樣的最大序列就代表了一個序列模式(sequentialpattern)。8.4序列模式挖掘一個客戶所有的事務(wù)(transa398.4序列模式挖掘8.4.2序列模式的發(fā)現(xiàn)

一個序列的長度(length)是它所包含的項集(itemset)的總數(shù)。具有k長度的序列稱為k-序列。有兩個序列x和y，x，y表示x和y經(jīng)過連接運算形成的新的序列。一個項集i的支持是指那一部分在單次交易中買了項集i中的項的那一部分客戶。于是項集i和1-序列<i>具有相同的支持。具有最小支持(minimumsupport)的項集稱為大項集(largeitemsetorlitemset)。需要注意的是，大序列中的每一個項集都必須具有最小支持。因此，任何大序列都是大項集的列表所組成。分5個具體階段來找出所有的序列模式。其找出過程分為:排序階段、大項集階段、轉(zhuǎn)換階段、序列階段和選最大階段。8.4序列模式挖掘8.4.2序列模式的發(fā)現(xiàn)408.4序列模式挖掘8.4.3序列階段的算法序列階段算法的基本結(jié)構(gòu)是對數(shù)據(jù)進行多次遍歷。在每次遍歷中，我們從一個由大序列(largesequence)組成的種子集(seedset)開始，利用這個種子集，可以產(chǎn)生新的潛在的大序列。在遍歷數(shù)據(jù)的過程中，我們計算出這些候選序列的支持度，這樣在一次遍歷的最后，我們就可以決定哪些候選序列是真正的大序列，這些序列構(gòu)成下一次遍歷的種子集。在第一次遍歷前，所有在大項集階段得到的具有最小支持度(minimumsupport)的大1-序列組成了種子集。這里給出兩種算法，分別稱為count-all和count-some。count-all累計所有大序列，包括非最大序列(non-maximalsequence)，在找最大階段(maximalphase)，這些非最大序列必須被刪除。給出一個count-all算法，稱為AprioriAll，給出一個count-some算法，稱為AprioriSome。8.4序列模式挖掘8.4.3序列階段的算法418.5WEB挖掘8.5.1概述隨著Internet的日益普及，人們通過Web接觸到了比以前多得多的數(shù)據(jù)和信息。然而，盡管Web上有海量的數(shù)據(jù)，但由于Web頁面過于復(fù)雜、而且是無結(jié)構(gòu)的、動態(tài)的，導(dǎo)致人們難以迅速、方便地在Web上找到所需要的數(shù)據(jù)和信息。在面臨如此龐大的信息空間以及Web組織無序化的情況下，搜索是解決網(wǎng)絡(luò)信息無序和混亂的一個基本方法，現(xiàn)代社會的競爭趨勢要求能夠?qū)@些信息進行實時和深層次的分析，因此，如何利用數(shù)據(jù)挖掘知識，進一步提高Web信息搜索的性能成為眾多學(xué)者研究的熱點。Web挖掘就是從Web文檔和Web活動中抽取感興趣的、潛在的有用模式和隱藏的信息。Web挖掘可以在確定權(quán)威頁面、Web文檔分類、WebLog挖掘、智能查詢等在很多方面發(fā)揮作用。

與傳統(tǒng)數(shù)據(jù)挖掘技術(shù)所面對的數(shù)據(jù)相比，Web挖掘的數(shù)據(jù)源具有以下特點：8.5WEB挖掘8.5.1概述428.5WEB挖掘（1）對有效的數(shù)據(jù)倉庫和數(shù)據(jù)挖掘而言，Web似乎太龐大了。Web的數(shù)據(jù)量目前以Terabytes計算，而且仍然在迅速地增長。這使得幾乎不可能去構(gòu)造一個數(shù)據(jù)倉庫來復(fù)制、存儲或集成Web上的所有數(shù)據(jù)。（2）Web頁面的復(fù)雜性高于任何傳統(tǒng)的文本文檔。Web頁面缺乏統(tǒng)一的結(jié)構(gòu)，它包含了遠比任何一組書籍或文本文檔多得多的風(fēng)格和內(nèi)容。（3）Web是一個動態(tài)性極強的信息源。Web不僅以極快的速度增長，而且其信息還在不斷地發(fā)生著更新。新聞、股票市場、公司廣告和Web服務(wù)中心都在不斷地更新著各自的頁面。鏈接信息和訪問記錄也在頻繁地更新之中。（4）Web面對的是一個廣泛的形形色色的用戶群體。目前因特網(wǎng)用戶在不斷的快速增加，各個用戶可以有不同的背景、興趣和使用目的。大部分的用戶并不了解信息網(wǎng)絡(luò)結(jié)構(gòu)，不清楚搜索的高昂代價，極易在網(wǎng)絡(luò)中迷失方向，也極易在跳躍式的訪問中煩亂不已和在等待中失去耐心。因此web挖掘應(yīng)能根據(jù)不同的用戶提供個性化的服務(wù)。8.5WEB挖掘（1）對有效的數(shù)據(jù)倉庫和數(shù)據(jù)挖掘而言，We438.5WEB挖掘（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ù)挖掘更加復(fù)雜。web上的信息的多樣性決定了web數(shù)據(jù)挖掘的多樣性。按照處理對象的不同我們將web數(shù)據(jù)挖掘分為三大類：Web內(nèi)容挖掘、Web結(jié)構(gòu)挖掘和Web使用記錄挖掘。8.5WEB挖掘（5）web上的信息只有很小的一部分是相關(guān)448.6數(shù)據(jù)挖掘的研究熱點與發(fā)展趨勢

8.6.1研究熱點隨著網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)挖掘技術(shù)的發(fā)展，從應(yīng)用的角度來看，目前有這樣一些研究熱點：網(wǎng)站的數(shù)據(jù)挖掘、生物信息和DNA數(shù)據(jù)分析的數(shù)據(jù)挖掘、文本數(shù)據(jù)挖掘等幾個方面。1．電子商務(wù)網(wǎng)站的數(shù)據(jù)挖掘2．生物信息和DNA數(shù)據(jù)分析的數(shù)據(jù)挖掘3．文本數(shù)據(jù)挖掘8.6數(shù)據(jù)挖掘的研究熱點與發(fā)展趨勢8.6.1研究熱點458.6數(shù)據(jù)挖掘的研究熱點與發(fā)展趨勢

8.6.2發(fā)展趨勢研究焦點可能會集中到以下幾個方面。（1）數(shù)據(jù)挖掘語言的標(biāo)準(zhǔn)化（2）可視化數(shù)據(jù)挖掘（3）Web挖掘（4）復(fù)雜數(shù)據(jù)類型挖掘的新方法（5）交互式發(fā)現(xiàn)（6）可伸縮的數(shù)據(jù)挖掘方法（7）數(shù)據(jù)挖掘與數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)倉庫系統(tǒng)和Web數(shù)據(jù)庫系統(tǒng)的集成（8）數(shù)據(jù)挖掘中的隱私保護與信息安全（9）應(yīng)用的探索8.6數(shù)據(jù)挖掘的研究熱點與發(fā)展趨勢8.6.2發(fā)展趨勢46第八章

數(shù)據(jù)挖掘人工智能華中師范大學(xué)計算機科學(xué)系第八章人工智能華中師范大學(xué)計算機科學(xué)系47第八章數(shù)據(jù)挖掘數(shù)據(jù)挖掘（DataMining）是一個多學(xué)科交叉研究領(lǐng)域，它融合了數(shù)據(jù)庫技術(shù)、人工智能、機器學(xué)習(xí)、統(tǒng)計學(xué)、知識工程、面向?qū)ο蠓椒?、信息檢索、高性能計算以及數(shù)據(jù)可視化等最新技術(shù)的研究成果。經(jīng)過十幾年的研究，產(chǎn)生了許多新概念和方法。特別是最近幾年來，一些基本概念和方法趨于清晰，它的研究正向著更深入的方向發(fā)展。數(shù)據(jù)挖掘技術(shù)正在以一種全新的概念改變著人類利用數(shù)據(jù)的方式，它被認為是未來信息處理的骨干技術(shù)之一，網(wǎng)絡(luò)之后的下一個技術(shù)熱點。第八章數(shù)據(jù)挖掘數(shù)據(jù)挖掘（DataMining）是488.1數(shù)據(jù)挖掘概述8.1.1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘（DataMining）是一門受到來自各種不同領(lǐng)域的研究者關(guān)注的交叉性學(xué)科，有很多不同的術(shù)語名稱，除了常用的“數(shù)據(jù)挖掘”和“知識發(fā)現(xiàn)”之外，與數(shù)據(jù)挖掘相近的同義詞有數(shù)據(jù)融合、數(shù)據(jù)分析、知識抽取、信息發(fā)現(xiàn)、數(shù)據(jù)采掘、知識獲取、數(shù)據(jù)考古、信息收獲和決策支持等。從技術(shù)的角度講，數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。這個定義包括好幾層含義：數(shù)據(jù)源必須是真實的、大量的、含噪聲的；發(fā)現(xiàn)的是用戶感興趣的知識；發(fā)現(xiàn)的知識要可接受、可理解、可運用；并不要求發(fā)現(xiàn)放之四海皆準(zhǔn)的知識，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機器定理證明，只要能支持特定的發(fā)現(xiàn)問題即可。實際上，利用數(shù)據(jù)挖掘從數(shù)據(jù)集中所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件，面向特定領(lǐng)域的，同時還要能夠易于被用戶理解。最好能用自然語言表達所發(fā)現(xiàn)的結(jié)果。8.1數(shù)據(jù)挖掘概述8.1.1數(shù)據(jù)挖掘的定義498.1數(shù)據(jù)挖掘概述從商業(yè)的角度講，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要特點是對商業(yè)數(shù)據(jù)庫中的大量業(yè)務(wù)數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。簡而言之，數(shù)據(jù)挖掘其實是一類深層次的數(shù)據(jù)分析方法。數(shù)據(jù)分析本身已經(jīng)有很多年的歷史，只不過在過去數(shù)據(jù)收集和分析的目的是用于科學(xué)研究，另外，由于當(dāng)時計算能力的限制，對大數(shù)據(jù)量進行分析的復(fù)雜數(shù)據(jù)分析方法受到很大限制?，F(xiàn)在，由于各行業(yè)業(yè)務(wù)自動化的實現(xiàn)，商業(yè)領(lǐng)域產(chǎn)生了大量的業(yè)務(wù)數(shù)據(jù)，這些數(shù)據(jù)不再是為了分析的目的而收集的，而是由于純機會的商業(yè)運作而產(chǎn)生。分析這些數(shù)據(jù)也不再是單純?yōu)榱搜芯康男枰饕菫樯虡I(yè)決策提供真正有價值的信息，進而獲得利潤。8.1數(shù)據(jù)挖掘概述從商業(yè)的角度講，數(shù)據(jù)挖掘是一種新508.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ù)庫、事務(wù)數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫（SpatialDatabase）、文本數(shù)據(jù)（TextData）以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識，既然如此，那么可以說數(shù)據(jù)庫中的知識發(fā)現(xiàn)只是數(shù)據(jù)挖掘的一個方面，這是早期比較流行的觀點。因此，從這個意義說，數(shù)據(jù)挖掘就是從數(shù)據(jù)庫、數(shù)據(jù)倉庫以及其它數(shù)據(jù)存儲方式中挖掘有用知識的過程。這種描述強調(diào)了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。(2)數(shù)據(jù)挖掘是KDD過程的一個步驟在“知識發(fā)現(xiàn)96國際會議”上，許多學(xué)者建議對這兩個名詞加以區(qū)分。核心思想是：KDD是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而DataMining則是此全部過程的一個特定的、關(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是一個更廣義的范疇，它包括數(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)鍵的部分。8.1數(shù)據(jù)挖掘概述8.1.2數(shù)據(jù)挖掘與數(shù)據(jù)庫中的知識發(fā)現(xiàn)518.1數(shù)據(jù)挖掘概述（3）KDD與DataMining含義相同

也有些人認為，KDD與DataMining只是叫法不一樣，它們的含義基本相同。事實上，在現(xiàn)今的文獻中，許多場合，如技術(shù)綜述等，這兩個術(shù)語仍然不加區(qū)分地使用著。也有人說，KDD在人工智能界更流行；DataMining在數(shù)據(jù)庫界使用更多。所以，從廣義的觀點，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的、有噪聲的、不確定性的、各種存儲形式的）中，挖掘隱含在其中的、人們事先不知道的、對決策有用的知識的過程。

從上面的描述中可以看出，數(shù)據(jù)挖掘概念可以在不同的技術(shù)層面上來理解，但是其核心仍然是從數(shù)據(jù)中挖掘知識。從本質(zhì)來講，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)是有區(qū)別的，但是在很多場合人們往往不嚴格區(qū)分數(shù)據(jù)挖掘和數(shù)據(jù)庫中的知識發(fā)現(xiàn)，兩者互為使用。一般在科研領(lǐng)域中稱為KDD，而在工程領(lǐng)域則多稱為數(shù)據(jù)挖掘。8.1數(shù)據(jù)挖掘概述（3）KDD與DataMining含義528.1數(shù)據(jù)挖掘概述8.1.3數(shù)據(jù)挖掘研究的理論基礎(chǔ)數(shù)據(jù)挖掘方法可以是基于數(shù)學(xué)理論的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。從研究的歷史看，它們可能是數(shù)據(jù)庫、人工智能、數(shù)理統(tǒng)計、計算機科學(xué)以及其它方面的學(xué)者和工程技術(shù)人員，在數(shù)據(jù)挖掘的探討性研究過程中創(chuàng)立的理論體系。1997年，Mannila對當(dāng)時流行的數(shù)據(jù)挖掘的理論框架給出了綜述。結(jié)合最新的研究成果，有下面一些重要的理論框架可以幫助我們準(zhǔn)確地理解數(shù)據(jù)挖掘的概念與技術(shù)特點。模式發(fā)現(xiàn)架規(guī)則發(fā)現(xiàn)架構(gòu)基于概率和統(tǒng)計理論微觀經(jīng)濟學(xué)觀點基于數(shù)據(jù)壓縮理論基于歸納數(shù)據(jù)庫理論8.1數(shù)據(jù)挖掘概述8.1.3數(shù)據(jù)挖掘研究的理論基礎(chǔ)538.1數(shù)據(jù)挖掘概述8.1.4數(shù)據(jù)挖掘與其它數(shù)據(jù)處理方法的區(qū)別及聯(lián)系1．?dāng)?shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析(如查詢、報表、聯(lián)機應(yīng)用分析)的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識。數(shù)據(jù)挖掘所得到的信息應(yīng)具有先未知，有效和可實用三個特征。先前未知的信息是指該信息是預(yù)先未曾預(yù)料到的，既數(shù)據(jù)挖掘是要發(fā)現(xiàn)那些不能靠直覺發(fā)現(xiàn)的信息或知識，甚至是違背直覺的信息或知識，挖掘出的信息越是出乎意料，就可能越有價值，在商業(yè)應(yīng)用中最典型的例子就是一家連鎖店通過數(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.1數(shù)據(jù)挖掘概述8.1.4數(shù)據(jù)挖掘與其它數(shù)據(jù)處理方法的區(qū)548.1數(shù)據(jù)挖掘概述數(shù)據(jù)倉庫的數(shù)據(jù)清理和數(shù)據(jù)挖掘的數(shù)據(jù)清理差不多，如果數(shù)據(jù)在導(dǎo)入數(shù)據(jù)倉庫時已經(jīng)清理過，那很可能在做數(shù)據(jù)挖掘時就沒必要在清理一次了，而且所有的數(shù)據(jù)不一致的問題都已經(jīng)被解決了。數(shù)據(jù)挖掘庫可能是數(shù)據(jù)倉庫的一個邏輯上的子集，而不一定非得是物理上單獨的數(shù)據(jù)庫。但如果數(shù)據(jù)倉庫的計算資源已經(jīng)很緊張，那最好還是建立一個單獨的數(shù)據(jù)挖掘庫圖8.1數(shù)據(jù)挖掘苦聰數(shù)據(jù)倉庫中得出8.1數(shù)據(jù)挖掘概述數(shù)據(jù)倉庫的數(shù)據(jù)清理和數(shù)據(jù)挖掘的數(shù)據(jù)清理差558.1數(shù)據(jù)挖掘概述3.數(shù)據(jù)挖掘和在線分析處理（OLAP）數(shù)據(jù)挖掘和OLAP是完全不同的工具，基于的技術(shù)也大相徑庭。OLAP是決策支持領(lǐng)域的一部分。傳統(tǒng)的查詢和報表工具是告訴人們數(shù)據(jù)庫中都有什么，OLAP則更進一步告訴人們下一步會怎么樣和如果人們采取這樣的措施又會怎么樣。用戶首先建立一個假設(shè)，然后用OLAP檢索數(shù)據(jù)庫來驗證這個假設(shè)是否正確。數(shù)據(jù)挖掘與OLAP不同的地方是，數(shù)據(jù)挖掘不是用于驗證某個假定的模式（模型）的正確性，而是在數(shù)據(jù)庫中自己尋找模型。它在本質(zhì)上是一個歸納的過程。數(shù)據(jù)挖掘和OLAP具有一定的互補性。在利用數(shù)據(jù)挖掘出來的結(jié)論采取行動之前，也許要驗證一下如果采取這樣的行動會帶來什么樣的影響，那么OLAP工具能回答這些問題。

8.1數(shù)據(jù)挖掘概述3.數(shù)據(jù)挖掘和在線分析處理（OLAP568.1數(shù)據(jù)挖掘概述4.數(shù)據(jù)挖掘與機器學(xué)習(xí)和統(tǒng)計分析方法數(shù)據(jù)挖掘利用了人工智能（AI）和統(tǒng)計分析的進步所帶來的好處。這兩門學(xué)科都致力于模式發(fā)現(xiàn)和預(yù)測。數(shù)據(jù)挖掘不是為了替代傳統(tǒng)的統(tǒng)計分析技術(shù)。相反，它是統(tǒng)計分析方法學(xué)的延伸和擴展。大多數(shù)的統(tǒng)計分析技術(shù)都基于完善的數(shù)學(xué)理論和高超的技巧，預(yù)測的準(zhǔn)確度還是令人滿意的，但對使用者的要求很高。而隨著計算機計算能力的不斷增強，我們有可能利用計算機強大的計算能力只通過相對簡單和固定的方法完成同樣的功能。一些新興的技術(shù)同樣在知識發(fā)現(xiàn)領(lǐng)域取得了很好的效果，如神經(jīng)元網(wǎng)絡(luò)和決策樹，在足夠多的數(shù)據(jù)和計算能力下，它們幾乎不用人的關(guān)照自動就能完成許多有價值的功能。8.1數(shù)據(jù)挖掘概述4.數(shù)據(jù)挖掘與機器學(xué)習(xí)和統(tǒng)計分析方法578.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)由這三個學(xué)科的權(quán)威人物同時來任主席。目前DMKD的主要研究內(nèi)容包括基礎(chǔ)理論、發(fā)現(xiàn)算法、數(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)知識分類知識預(yù)測型知識8.1數(shù)據(jù)挖掘概述8.1.5數(shù)據(jù)挖掘的內(nèi)容588.1數(shù)據(jù)挖掘概述8.1.6數(shù)據(jù)挖掘的研究歷史和現(xiàn)狀

數(shù)據(jù)庫中發(fā)現(xiàn)知識（KDD）是在1989年召開的第11屆國際人工智能聯(lián)合學(xué)術(shù)會議(IJCAI)上首次提出的。在這屆學(xué)術(shù)會議上舉行了以KDD為主題的學(xué)術(shù)研討會，在1991年、1993年和1994年相繼舉行了KDD專題研討會。隨著KDD的深入研究以及KDD在許多領(lǐng)域的成功應(yīng)用，于1995年在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學(xué)術(shù)會議，此后每年都召開大規(guī)模的國際會議，其研究重點也逐漸從發(fā)現(xiàn)方法轉(zhuǎn)向系統(tǒng)應(yīng)用，注重多種發(fā)現(xiàn)策略和技術(shù)的集成，以及多種學(xué)科之間的相互滲透。第一本關(guān)于DM和KDD的國際學(xué)術(shù)雜志《DataMiningandKnowledgeDiscovery》也于97年3月創(chuàng)刊發(fā)行。亞太地區(qū)于1997年在新加坡召開了首次KDD研討會，其后又在澳大利亞的墨爾本召開了第二屆，在中國北京召開了第三屆。目前，在IJCAI、AAAI、VLDB、ACM-SIGMOD等代表人工智能與數(shù)據(jù)庫技術(shù)研究最高水平的國際學(xué)術(shù)會議上，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究都占有較大的比例，數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究已經(jīng)成為當(dāng)今計算機科學(xué)與技術(shù)研究、應(yīng)用的熱點領(lǐng)域之一。8.1數(shù)據(jù)挖掘概述8.1.6數(shù)據(jù)挖掘的研究歷史和現(xiàn)狀598.2數(shù)據(jù)挖掘技術(shù)簡介

根據(jù)挖掘的任務(wù)可以分為：分類和預(yù)測模型發(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ù)挖掘方法可分為機器學(xué)習(xí)方法、統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)方法和數(shù)據(jù)庫方法。其中機器學(xué)習(xí)可細分為歸納學(xué)習(xí)方法、基于范例學(xué)習(xí)、遺傳算法等；統(tǒng)計方法可細分為回歸分析、判別分析、聚類分析、探索性分析等；神經(jīng)網(wǎng)絡(luò)方法可細分為前向神經(jīng)網(wǎng)絡(luò)、自組織神經(jīng)網(wǎng)絡(luò)等；數(shù)據(jù)庫方法主要是多維數(shù)據(jù)分析或聯(lián)機分析方法，另外還有面向?qū)傩缘臍w納方法。8.2數(shù)據(jù)挖掘技術(shù)簡介根據(jù)挖掘的任務(wù)可以分為：分608.2數(shù)據(jù)挖掘技術(shù)簡介

8.2.1分類和預(yù)測分類是數(shù)據(jù)挖掘中一項非常重要的任務(wù)，目前在商業(yè)上的應(yīng)用最多。分類的目的是提出一個分類函數(shù)或分類模型（也常常稱作分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。分類和回歸都可用于預(yù)測，預(yù)測的目的是從歷史數(shù)據(jù)記錄中自動推導(dǎo)出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進行預(yù)測。分類的效果一般和數(shù)據(jù)的特點有關(guān)，有的數(shù)據(jù)噪聲大，有的有缺省值，有的分布稀疏，有的字段或?qū)傩蚤g相關(guān)性強，有的屬性是離散的而有的是連續(xù)值或混合式的。目前普遍認為不存在某種方法能適合各種特點的數(shù)據(jù)。下面介紹幾種常用的分類算法。8.2數(shù)據(jù)挖掘技術(shù)簡介8.2.1分類和預(yù)測618.2數(shù)據(jù)挖掘技術(shù)簡介

1．決策樹構(gòu)造一個決策樹分類器通常分為兩步：樹的生成和剪枝。樹的生成采用自上而下的遞歸分治法。如果當(dāng)前訓(xùn)練例子集合中的所有實例是同類的,構(gòu)造一個葉節(jié)點,節(jié)點內(nèi)容即是該類別。否則,根據(jù)某種策略選擇一個屬性,按照該屬性的不同取值,把當(dāng)前實例集合劃分為若干子集合。對每個子集合重復(fù)此過程,直到當(dāng)前集中的實例是同類的為止。剪枝就是剪去那些不會增大樹的錯誤預(yù)測率的分枝。經(jīng)過剪枝,不僅能有效的克服噪聲,還使樹變得簡單,容易理解。生成最優(yōu)的決策樹同樣是NP問題。目前的決策樹算法通過啟發(fā)式屬性選擇策略來解決問題。8.2數(shù)據(jù)挖掘技術(shù)簡介1．決策樹628.2數(shù)據(jù)挖掘技術(shù)簡介

2．AQ算法存在大量的基于規(guī)則的分類方法，以及對規(guī)則進行后處理如剪枝等工作。AQ是一種典型的基于規(guī)則的方法。AQ是一種覆蓋算法，由Micalski和洪家榮提出。算法的核心是所謂的”星”。一個正例集合在反例集合背景下的星是覆蓋所有正例而排斥所有反例的極大復(fù)合的集合。算法就是要求得這樣的最大復(fù)合。算法從正例中的一個種子的一個選擇子(屬性值對)出發(fā)，逐漸地增加選擇子，直到找到覆蓋所有正例的最大復(fù)合。在最初的AQ11基礎(chǔ)上，AQ15增加了漸近學(xué)習(xí)，構(gòu)造學(xué)習(xí)和近似推理等功能，成為比較成熟的覆蓋算法。8.2數(shù)據(jù)挖掘技術(shù)簡介2．AQ算法638.2數(shù)據(jù)挖掘技術(shù)簡介

3．Bayes方法貝葉斯統(tǒng)計分析起源于英國學(xué)者BayesT.R.的一篇論文＂Anessaytowardssolvingaprobleminthedoctrineofchances＂(1763年),給出了著名的貝葉斯公式和一種歸納推理方法。其后一些統(tǒng)計學(xué)家將其發(fā)展成一種系統(tǒng)的統(tǒng)計推斷方法，到本世紀30年代形成了貝葉斯學(xué)派，50~60年代發(fā)展成了一個有影響的統(tǒng)計學(xué)派。貝葉斯方法的學(xué)習(xí)機制是利用貝葉斯公式將先驗信息與樣本信息綜合得到后驗信息。在數(shù)據(jù)挖掘中，主要有兩種bayes方法，即Na?ve-bayes方法和bayes網(wǎng)絡(luò)。前者直接利用bayes公式進行預(yù)測，把從訓(xùn)練樣本中計算出的各個屬性值和類別頻率比作為先驗概率，并假定各個屬性之間是獨立的，就可以用bayes公式和相應(yīng)的概率公司計算出要預(yù)測實例的對各類別的條件概率值。選取概率值最大的類別作為預(yù)測值。此方法簡單易行并且具有較好的精度。8.2數(shù)據(jù)挖掘技術(shù)簡介3．Bayes方法648.2數(shù)據(jù)挖掘技術(shù)簡介

4．神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)是一種很好的函數(shù)逼近工具，在過去十幾年里取得了飛速的發(fā)展，發(fā)展出了很多的模型及其改進，例如BP、Hopfield、Kohonen、ART、RNN、KBANN、RBF等等。雖然試驗表明，神經(jīng)網(wǎng)絡(luò)在某些分類問題上具有比符號方法更好的表現(xiàn)，但是神經(jīng)網(wǎng)絡(luò)用于數(shù)據(jù)挖掘主要不利之處在于無法獲取顯式的規(guī)則。近年來許多學(xué)者提出了從神經(jīng)網(wǎng)絡(luò)中提取規(guī)則的方法，典型的如KBANN等。主要可以分為三類方法：分解法、學(xué)習(xí)法以及這兩種的折衷方法8.2數(shù)據(jù)挖掘技術(shù)簡介4．神經(jīng)網(wǎng)絡(luò)655．粗糙集粗糙集(RougnSet,RS)理論是一種刻劃不完整性和不確定性的數(shù)學(xué)工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律，是由波蘭科學(xué)家Z.Pawlak在1982年首先提出。粗糙集理論的研究對象是由一個多值屬性（特征、癥狀、特性等）級和描述的一個對象集合，對于每個對象及其屬性都有一個值作為其描述符號，對象、屬性和描述符號是表達決策問題的3個基本要素。通常關(guān)于對象的可得到的信息不一定足以劃分其成員類別，換句話說，這種不精確性導(dǎo)致了對象的不可分辨性。給定對象間的一種等價關(guān)系，即導(dǎo)致由等價類構(gòu)成的近似空間的不分明關(guān)系，Rough集就用不分明對象類形成的上近似和下近似來描述。前者指的是所有對象都一定被包含，后者指的是所有對象可能被包含。8.2數(shù)據(jù)挖掘技術(shù)簡介

5．粗糙集8.2數(shù)據(jù)挖掘技術(shù)簡介668.2數(shù)據(jù)挖掘技術(shù)簡介

8.2.2聚類分析

聚類和數(shù)據(jù)挖掘中的分類不同，聚類是在預(yù)先不知道目標(biāo)數(shù)據(jù)庫到底有多少類的情況下，希望將所有的記錄組成不同的類或者說聚類，并且使得在這種分類情況下，以某種度量為標(biāo)準(zhǔn)的相似性，在同一聚類之間最小化，而在不同聚類之間最大化。換句話說，聚類（clustering）是一個將數(shù)據(jù)集劃分為若干組或類的過程，并使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度；而不同組中的數(shù)據(jù)對象是不相似的。相似或不相似的描述是基于數(shù)據(jù)描述屬性的取值來確定的。通常就是利用（各對象間）距離來進行表示的。許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計學(xué)和機器學(xué)習(xí)都有聚類研究和應(yīng)用。8.2數(shù)據(jù)挖掘技術(shù)簡介8.2.2聚類分析678.2數(shù)據(jù)挖掘技術(shù)簡介

1.聚類分析概念

將一組物理的或抽象的對象，根據(jù)它們之間的相似程度，分為若干組；其中相似的對象構(gòu)成一組，這一過程就稱為聚類過程（clustering）。一個聚類就是由彼此相似的一組對象所構(gòu)成的集合；不同聚類中對象是不相似的。就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)項（items）之間所存在的有價值聯(lián)系。在許多應(yīng)用，一個聚類中所有對象常常被當(dāng)作一個對象來進行處理或分析等操作。8.2數(shù)據(jù)挖掘技術(shù)簡介1.聚類分析概念688.2數(shù)據(jù)挖掘技術(shù)簡介

2.聚類分析的主要方法

在聚類分析中有大量的算法可供選擇。需要根據(jù)應(yīng)用所涉及的數(shù)據(jù)類型、聚類的目的以及具體應(yīng)用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具，那么就可以使用若干聚類算法對同一個數(shù)據(jù)集進行處理以觀察可能獲得的有關(guān)（數(shù)據(jù)特征）描述。通常聚類分析算法可以劃分為以下幾大類：（1）劃分方法（2）層次方法（3）基于密度方法（4）基于網(wǎng)格方法（5）基于模型方法8.2數(shù)據(jù)挖掘技術(shù)簡介2.聚類分析的主要方法698.3關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則的概念是由Ｒ.Ａgrawal、Imieelinski和Swami提出來的。在數(shù)據(jù)挖掘領(lǐng)域,關(guān)聯(lián)規(guī)則的挖掘有著廣泛的應(yīng)用背景。關(guān)聯(lián)規(guī)則挖掘目的就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識。隨著收集和存儲在數(shù)據(jù)庫中的數(shù)據(jù)規(guī)模越來越大，人們對從這些數(shù)據(jù)中挖掘相應(yīng)的關(guān)聯(lián)知識越來越有興趣。例如：從大量的商業(yè)交易記錄中發(fā)現(xiàn)有價值的關(guān)聯(lián)知識就可幫助進行商品目錄的設(shè)計、交叉營銷或幫助進行其它有關(guān)的商業(yè)決策。8.3關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則的概念是由Ｒ.Ａgraw708.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)規(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)。也就是說在很多應(yīng)用中，挖掘規(guī)則可以作用到數(shù)據(jù)庫的不同層面上。例如，在分析超市銷售事務(wù)數(shù)據(jù)庫過程中，若單單從數(shù)據(jù)庫的原始字段，如面包、牛奶等等進行規(guī)則挖掘，可能很難發(fā)現(xiàn)令人感興趣的規(guī)則。這時如果把一些抽象層次的概念也考慮進去，比如面包、牛奶更抽象的概念——食品，則有可能新的更為抽象的規(guī)則。所以研究在數(shù)據(jù)庫中的不同的抽象層次上發(fā)掘規(guī)則是數(shù)據(jù)挖掘新的研究內(nèi)容。8.3關(guān)聯(lián)規(guī)則挖掘8.3.1關(guān)聯(lián)規(guī)則概述718.3關(guān)聯(lián)規(guī)則挖掘二是提高算法效率。顯然在挖掘規(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ī)則挖掘要深入研究和解決的問題。8.3關(guān)聯(lián)規(guī)則挖掘二是提高算法效率。顯然在挖掘規(guī)則728.3關(guān)聯(lián)規(guī)則挖掘下面介紹關(guān)聯(lián)規(guī)則挖掘過程中所涉及到的有關(guān)概念和術(shù)語。(1)數(shù)據(jù)項和數(shù)據(jù)項集設(shè)I={i1，i2，...，im}是n個不同項目的集合,則每一個項目ik(ｋ=1,2,…,n)稱為數(shù)據(jù)項(item)。Ｉ為數(shù)據(jù)項集(itemset),n為數(shù)據(jù)項集的長度。長度為ｋ的數(shù)據(jù)項集稱為ｋ-項集(k-itemsets)。(2)事務(wù)一個事務(wù)Ｔ(Transaction)是數(shù)據(jù)項集Ｉ中的一組項目的集合,即TI。每一個事務(wù)賦予一個唯一的標(biāo)識符TID。所有事務(wù)的全體就構(gòu)成一個事務(wù)數(shù)據(jù)庫Ｄ。(3)數(shù)據(jù)項集的支持度數(shù)據(jù)項集的支持度(Support)就是數(shù)據(jù)項集出現(xiàn)的概率。設(shè)Ｘ是Ｉ中的一個子集,稱一個事務(wù)Ｔ包含Ｘ,當(dāng)且僅當(dāng)ＸＴ。Ｘ的支持度為:Support(Ｘ)=Ｐ(Ｘ)8.3關(guān)聯(lián)規(guī)則挖掘下面介紹關(guān)聯(lián)規(guī)則挖掘過程中所涉及到的有關(guān)738.3關(guān)聯(lián)規(guī)則挖掘(4)關(guān)聯(lián)規(guī)則及其支持度和置信度一個關(guān)聯(lián)規(guī)則就是具有“X→Y”形式的蘊含式，其中有XI，YI且X∩Y=

。Ｘ稱作規(guī)則的前提,Ｙ是結(jié)果。規(guī)則X→Y的支持度為ｓ,是指在Ｄ中有ｓ%的事務(wù),既包含Ｘ同時又包含Ｙ,即同時出現(xiàn)數(shù)據(jù)項集Ｘ和Ｙ的概率。其表達式為Support(X→Y)=P(X∩Y)。規(guī)則X→Y的置信度(Confidence)為ｃ,是指在Ｄ中包含Ｘ的事務(wù)有ｃ%的事務(wù)同時又包含Ｙ,即出現(xiàn)數(shù)據(jù)項集Ｘ的前提下,出現(xiàn)數(shù)據(jù)項集Ｙ的概率,其表達式為confidence(X→Y)=P(Y∣X)。支持度體現(xiàn)了項目集Ｘ在交易集中出現(xiàn)的頻度,置信度體現(xiàn)了項目集Ｘ和Ｙ之間的關(guān)聯(lián)程度。（5）頻繁項集一個項集的出現(xiàn)頻度就是整個交易數(shù)據(jù)集D中包含該項集的交易記錄數(shù),若一個項集的出現(xiàn)頻度大于最小支持度閾值乘以交易記錄集D中記錄數(shù)，那么就稱該項集滿足最小支持度閾值；而滿足最小支持度閾值所對應(yīng)的交易記錄數(shù)就稱為最小支持頻度。8.3關(guān)聯(lián)規(guī)則挖掘(4)關(guān)聯(lián)規(guī)則及其支持度和置信度748.3關(guān)聯(lián)規(guī)則挖掘滿足最小支持閾值的項集就稱為頻繁項集(或稱大項集)。所有頻繁k-項集的集合就記為Lk。挖掘關(guān)聯(lián)規(guī)則的問題就是找出這樣一些規(guī)則,它們的Support和confidence分別大于用戶指定的最小支持度(minisupport)和最小置信度(miniconfidence)的限度,稱這些規(guī)則為強規(guī)則。通常為方便起見，都將最小支持度閾值簡寫為min_sup；最小信任度閾值簡寫為min_conf。這兩個閾值均在0%到100%之間，而不是0到1之間。如果不考慮關(guān)聯(lián)規(guī)則的支持度和可信度，那么在事務(wù)數(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ī)則必須滿足的最小可信度，它反應(yīng)了關(guān)聯(lián)規(guī)則的最低可靠度。8.3關(guān)聯(lián)規(guī)則挖掘滿足最小支持閾值的項集就稱為頻繁項集(或758.3關(guān)聯(lián)規(guī)則挖掘挖掘關(guān)聯(lián)規(guī)則主要包含以下二個步驟：步驟一：發(fā)現(xiàn)所有的頻繁項集，根據(jù)定義，這些項集的頻度至少應(yīng)等于（預(yù)先設(shè)置的）最小支持頻度；步驟二：根據(jù)所獲得的頻繁項集，產(chǎn)生相應(yīng)的強關(guān)聯(lián)規(guī)則。根據(jù)定義這些規(guī)則必須滿足最小信任度閾值。此外還可利用有趣性度量標(biāo)準(zhǔn)來幫助挖掘有價值的關(guān)聯(lián)規(guī)則知識。由于步驟二中的相應(yīng)操作極為簡單，因此挖掘關(guān)聯(lián)規(guī)則的整個性能就是由步驟一中的操作處理所決定。8.3關(guān)聯(lián)規(guī)則挖掘挖掘關(guān)聯(lián)規(guī)則主要包含以下二個步驟：768.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ī)則可分為單維的