第1章緒論
　　1.1知 識(shí) 發(fā) 現(xiàn)
　　在許多領(lǐng)域中，隨著數(shù)據(jù)的不斷增多，一些大型數(shù)據(jù)庫(kù)的規(guī)模已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)人工所能分析的程度，因此數(shù)據(jù)庫(kù)和知識(shí)發(fā)現(xiàn)（knowledge discovery in database，KDD）技術(shù)應(yīng)運(yùn)而生(李嶶和李宛州，2001)。知識(shí)發(fā)現(xiàn)也是市場(chǎng)競(jìng)爭(zhēng)的需要，它為決策者提供重要的、前所未有的信息或知識(shí)，從而產(chǎn)生不可估量的效益。
　　1.1.1知識(shí)發(fā)現(xiàn)的歷程
　　隨著數(shù)據(jù)庫(kù)系統(tǒng)的廣泛開(kāi)發(fā)和數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展，數(shù)據(jù)以前所未有的速度大量聚集在計(jì)算機(jī)中，但與之相配合的數(shù)據(jù)分析和知識(shí)提取技術(shù)在相當(dāng)長(zhǎng)一段時(shí)間里沒(méi)有大的進(jìn)展，使得存儲(chǔ)的大量原始數(shù)據(jù)沒(méi)有被充分利用，沒(méi)有轉(zhuǎn)化成為指導(dǎo)生產(chǎn)的“知識(shí)”，而是出現(xiàn)了“數(shù)據(jù)的海洋，知識(shí)的荒漠”這樣一種奇怪的現(xiàn)象。于是，知識(shí)發(fā)現(xiàn)在這種背景下應(yīng)運(yùn)而生，并很快發(fā)展成為國(guó)際上數(shù)據(jù)庫(kù)和信息決策領(lǐng)域最前沿的研究方向之一。
　　知識(shí)發(fā)現(xiàn)的研究經(jīng)歷了從機(jī)器學(xué)習(xí)到機(jī)器發(fā)現(xiàn)再到知識(shí)發(fā)現(xiàn)幾個(gè)階段，從20世紀(jì)80年代末，人們開(kāi)始研究知識(shí)發(fā)現(xiàn)，1989年8月在美國(guó)底特律召開(kāi)的第11屆國(guó)際人工智能聯(lián)合會(huì)議的專題討論會(huì)上首次出現(xiàn)知識(shí)發(fā)現(xiàn)這個(gè)術(shù)語(yǔ)，法耶茲(Fayyad)首次給出了知識(shí)發(fā)現(xiàn)的定義“知識(shí)發(fā)現(xiàn)是從數(shù)據(jù)集中識(shí)別出有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過(guò)程”。隨后在1991年、1993年和1994年都舉行了知識(shí)發(fā)現(xiàn)專題討論會(huì)，集中討論海量數(shù)據(jù)分析算法、數(shù)據(jù)統(tǒng)計(jì)、知識(shí)表達(dá)、知識(shí)運(yùn)用等問(wèn)題。隨著知識(shí)發(fā)現(xiàn)在學(xué)術(shù)界和工業(yè)界的影響越來(lái)越大，知識(shí)發(fā)現(xiàn)組委會(huì)于1995年把專題討論會(huì)更名為國(guó)際會(huì)議，并改為大會(huì)代表自愿報(bào)名參加。1995年在加拿大蒙特利爾市召開(kāi)了第一次知識(shí)發(fā)現(xiàn)國(guó)際學(xué)術(shù)會(huì)議，以后每年召開(kāi)一次。
　　1.1.2知識(shí)發(fā)現(xiàn)的內(nèi)容
　　在知識(shí)發(fā)現(xiàn)′96國(guó)際會(huì)議上對(duì)知識(shí)發(fā)現(xiàn)做了如下定義：知識(shí)發(fā)現(xiàn)是識(shí)別出存在于數(shù)據(jù)庫(kù)中有效的、新穎的、具有潛在效果的乃至最終可理解的模式的非平凡過(guò)程。知識(shí)發(fā)現(xiàn)是將數(shù)據(jù)變成信息、信息變?yōu)橹�識(shí)、知識(shí)形成策略、策略構(gòu)成智能的活動(dòng)，從而指導(dǎo)人類有效地分析問(wèn)題和解決問(wèn)題。知識(shí)發(fā)現(xiàn)過(guò)程從數(shù)據(jù)礦山中找到蘊(yùn)藏的知識(shí)金塊，將為知識(shí)創(chuàng)新和知識(shí)經(jīng)濟(jì)的發(fā)展作出積極的貢獻(xiàn)。
　　知識(shí)發(fā)現(xiàn)的范圍非常廣泛，可以是經(jīng)濟(jì)、工業(yè)、農(nóng)業(yè)、軍事、社會(huì)、商業(yè)、科學(xué)、醫(yī)療衛(wèi)生等的數(shù)據(jù)或衛(wèi)星觀測(cè)得到的數(shù)據(jù)。數(shù)據(jù)的形態(tài)有數(shù)字、符號(hào)、圖形、圖像、聲音等。數(shù)據(jù)組織方式也各不相同，可以是結(jié)構(gòu)化、半結(jié)構(gòu)化、非結(jié)構(gòu)化的。知識(shí)發(fā)現(xiàn)的結(jié)果可以表示成各種形式，包括規(guī)則、法則、科學(xué)規(guī)律、方程或語(yǔ)義網(wǎng)絡(luò)等。
　　數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)的研究非�；钴S。在法耶茲的定義中，涉及幾個(gè)需要進(jìn)一步解釋的概念：“數(shù)據(jù)集”、“模式”、“過(guò)程”、“有效性”、“新穎性”、“潛在有用性”和“最終可理解性”。數(shù)據(jù)集是一組事實(shí)F（如關(guān)系數(shù)據(jù)庫(kù)中的記錄），模式是一個(gè)用語(yǔ)言L來(lái)表示的一個(gè)表達(dá)式E，它可用來(lái)描述數(shù)據(jù)集F的某個(gè)子集FE，E作為一個(gè)模式要求它比對(duì)數(shù)據(jù)子集FE的枚舉要簡(jiǎn)單（所用的描述信息量要少）。過(guò)程在知識(shí)發(fā)現(xiàn)中通常指多階段的一個(gè)過(guò)程，涉及數(shù)據(jù)準(zhǔn)備、模式搜索、知識(shí)評(píng)價(jià)，以及反復(fù)地修改求精；該過(guò)程要求是非平凡的，意思是要有一定程度的智能性、自動(dòng)性。有效性是指發(fā)現(xiàn)的模式對(duì)于新的數(shù)據(jù)仍保持有一定的可信度。新穎性要求發(fā)現(xiàn)的模式應(yīng)該是新的。潛在有用性是指發(fā)現(xiàn)的知識(shí)將來(lái)有實(shí)際效用，如用于決策支持系統(tǒng)（decision support system，DSS）中可提高經(jīng)濟(jì)效益。最終可理解性要求發(fā)現(xiàn)的模式能被用戶理解，目前它主要體現(xiàn)在簡(jiǎn)潔性上。有效性、新穎性、潛在有用性和最終可理解性綜合在一起稱為興趣性。
　　知識(shí)發(fā)現(xiàn)與智能決策第1章緒論1.1.3知識(shí)發(fā)現(xiàn)的過(guò)程
　　知識(shí)發(fā)現(xiàn)是一門受到來(lái)自各種不同領(lǐng)域的研究者關(guān)注的交叉性學(xué)科，因此它還有很多不同的術(shù)語(yǔ)名稱。除了知識(shí)發(fā)現(xiàn)外，主要還有如下若干種稱法：數(shù)據(jù)挖掘（data mining）、知識(shí)抽�。╥nformation extraction）、信息發(fā)現(xiàn)（information discovery）、智能數(shù)據(jù)分析（intelligent data analysis）、探索式數(shù)據(jù)分析（exploratory data analysis）、信息收獲（information harvesting）和數(shù)據(jù)考古（data archeology）等。其中最常用的術(shù)語(yǔ)是“知識(shí)發(fā)現(xiàn)”和“數(shù)據(jù)挖掘”。數(shù)據(jù)挖掘主要流行于統(tǒng)計(jì)界（最早出現(xiàn)于統(tǒng)計(jì)文獻(xiàn)中）、數(shù)據(jù)分析、數(shù)據(jù)庫(kù)和管理信息系統(tǒng)（management inform ation system， MIS）領(lǐng)域，而知識(shí)發(fā)現(xiàn)則主要流行于人工智能和機(jī)器學(xué)習(xí)領(lǐng)域。
　　知識(shí)發(fā)現(xiàn)過(guò)程（圖1-1）可粗略地理解為三部曲：數(shù)據(jù)準(zhǔn)備、數(shù)據(jù)挖掘和結(jié)果的解釋評(píng)估。
　　圖1-1知識(shí)發(fā)現(xiàn)過(guò)程示意圖
　　1.1.3.1數(shù)據(jù)準(zhǔn)備
　　數(shù)據(jù)準(zhǔn)備又可分為三個(gè)子步驟：數(shù)據(jù)選�。╠ata selection）、數(shù)據(jù)預(yù)處理（data preprocessing）和數(shù)據(jù)變換（data transformation）。數(shù)據(jù)選取的目的是確定發(fā)現(xiàn)任務(wù)的操作對(duì)象，即目標(biāo)數(shù)據(jù)（target data），它是根據(jù)用戶的需要從原始數(shù)據(jù)庫(kù)中抽取的一組數(shù)據(jù)。原始數(shù)據(jù)庫(kù)可以是異構(gòu)的數(shù)據(jù)庫(kù)和多源性數(shù)據(jù)文件。數(shù)據(jù)預(yù)處理一般可能包括消除噪聲、推導(dǎo)計(jì)算缺值數(shù)據(jù)、消除重復(fù)記錄、完成數(shù)據(jù)類型轉(zhuǎn)換（如把連續(xù)值數(shù)據(jù)轉(zhuǎn)換為離散型的數(shù)據(jù)，以便于符號(hào)歸納；或是把離散型的轉(zhuǎn)換為連續(xù)值型的，以便于概念性歸納）等。當(dāng)數(shù)據(jù)挖掘的對(duì)象是數(shù)據(jù)倉(cāng)庫(kù)時(shí)，數(shù)據(jù)預(yù)處理已經(jīng)在生成數(shù)據(jù)倉(cāng)庫(kù)時(shí)完成了，主要是通過(guò)在源數(shù)據(jù)中抽取數(shù)據(jù)，按數(shù)據(jù)倉(cāng)庫(kù)的邏輯數(shù)據(jù)模型的要求進(jìn)行數(shù)據(jù)轉(zhuǎn)換，再按物理數(shù)據(jù)模型的要求裝載到數(shù)據(jù)倉(cāng)庫(kù)中去，即進(jìn)行數(shù)據(jù)抽取、轉(zhuǎn)換、加載(extract、transform、load，ETL)過(guò)程。數(shù)據(jù)變換的主要目的是消減數(shù)據(jù)維數(shù)或降維（dimension reduction），即從初始特征中找出真正有用的特征以減少數(shù)據(jù)開(kāi)采時(shí)要考慮的特征或變量個(gè)數(shù)。
　　1.1.3.2數(shù)據(jù)挖掘
　　數(shù)據(jù)挖掘階段首先要確定挖掘的任務(wù)或目的是什么，如數(shù)據(jù)總結(jié)、概念描述、分類、聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)或序列模式發(fā)現(xiàn)和相關(guān)性分析等。確定了挖掘任務(wù)后，就要決定使用什么樣的挖掘算法。同樣的任務(wù)可以用不同的算法來(lái)實(shí)現(xiàn)。選擇實(shí)現(xiàn)算法有兩個(gè)考慮因素：一是不同的數(shù)據(jù)有不同的特點(diǎn)，因此需要用與之相關(guān)的算法來(lái)挖掘；二是用戶或?qū)嶋H運(yùn)行系統(tǒng)的要求，有的用戶可能希望獲取描述型的（descriptive）、容易理解的知識(shí)，而有的用戶或系統(tǒng)的目的是獲取預(yù)測(cè)準(zhǔn)確度盡可能高的預(yù)測(cè)型（predictive）知識(shí)。完成上述準(zhǔn)備工作后，就可以實(shí)施數(shù)據(jù)挖掘操作了。具體的數(shù)據(jù)挖掘方法將在后面章節(jié)中作較為詳細(xì)的論述。需要指出的是，盡管數(shù)據(jù)挖掘算法是知識(shí)發(fā)現(xiàn)的核心，也是目前研究人員主要的努力方向，但要獲得好的挖掘效果，必須對(duì)各種挖掘算法的要求或前提假設(shè)有充分的理解。
　　1.1.3.3結(jié)果解釋和評(píng)估
　　數(shù)據(jù)挖掘階段發(fā)現(xiàn)的模式，經(jīng)過(guò)用戶或機(jī)器的評(píng)估，可能存在冗余或無(wú)關(guān)的模式，這時(shí)需要將其剔除；也有可能模式不滿足用戶要求，這時(shí)則需要讓整個(gè)發(fā)現(xiàn)過(guò)程退回到發(fā)現(xiàn)階段之前，如重新選取數(shù)據(jù)、采用新的數(shù)據(jù)變換方法、設(shè)定新的數(shù)據(jù)挖掘參數(shù)值，甚至換一種挖掘算法（如當(dāng)發(fā)現(xiàn)任務(wù)是分類時(shí)，有多種分類方法，不同的方法對(duì)不同的數(shù)據(jù)有不同的效果）。另外，知識(shí)發(fā)現(xiàn)最終是面向人類用戶的，因此可能要對(duì)發(fā)現(xiàn)的模式進(jìn)行可視化，或者把結(jié)果轉(zhuǎn)換為用戶易懂的另一種表示，如把分類決策樹(shù)轉(zhuǎn)換為“if…then…”規(guī)則等。
　　知識(shí)發(fā)現(xiàn)過(guò)程中要注意以下幾點(diǎn)：
　　1）數(shù)據(jù)挖掘僅僅是整個(gè)過(guò)程中的一個(gè)步驟。數(shù)據(jù)挖掘質(zhì)量的好壞受兩個(gè)要素的影響：一是所采用的數(shù)據(jù)挖掘技術(shù)的有效性，二是用于挖掘的數(shù)據(jù)的質(zhì)量和數(shù)量（數(shù)據(jù)量的大�。�。如果選擇了錯(cuò)誤的數(shù)據(jù)或不適當(dāng)?shù)膶傩�，或�(qū)��?shù)據(jù)進(jìn)行了不適當(dāng)?shù)霓D(zhuǎn)換，則挖掘的結(jié)果是不會(huì)令人滿意的。
　　2）整個(gè)挖掘過(guò)程是一個(gè)不斷反饋的過(guò)程。比如，用戶在挖掘途中發(fā)現(xiàn)選擇的數(shù)據(jù)不太好，或使用的挖掘技術(shù)產(chǎn)生不了期望的結(jié)果，這時(shí)，用戶需要重復(fù)先前的過(guò)程，甚至重新開(kāi)始。
　　3）可視化在數(shù)據(jù)挖掘的各個(gè)階段都扮演著重要的作用。特別是在數(shù)據(jù)準(zhǔn)備階段，用戶可能要使用散點(diǎn)圖、直方圖等統(tǒng)計(jì)可視化技術(shù)來(lái)顯示有關(guān)數(shù)據(jù)，以對(duì)數(shù)據(jù)有一個(gè)初步的理解，從而為更好地選取數(shù)據(jù)打下基礎(chǔ)。在挖掘階段，用戶則要使用與領(lǐng)域問(wèn)題有關(guān)的可視化工具。在表示結(jié)果階段，則可能要用到可視化技術(shù)。
　　1.1.4知識(shí)發(fā)現(xiàn)的方法
　　知識(shí)發(fā)現(xiàn)的方法大致可分為如下幾大類。
　　1.1.4.1統(tǒng)計(jì)方法
　　統(tǒng)計(jì)方法是從事物的外在數(shù)量上的表現(xiàn)去推斷該事物可能的規(guī)律性。科學(xué)規(guī)律性的東西一般總是隱藏得比較深，最初總是通過(guò)統(tǒng)計(jì)分析從其數(shù)量表現(xiàn)上看出一些線索，然后提出一定的假說(shuō)或?qū)W說(shuō)，再作深入的理論研究。當(dāng)理論研究提出一定的結(jié)論時(shí)，往往還需要在實(shí)踐中加以驗(yàn)證。就是說(shuō)，觀測(cè)一些自然現(xiàn)象或?qū)ｉT安排的實(shí)驗(yàn)所得資料，是否與理論相符、在多大的程度上相符、可能朝哪個(gè)方向偏離等問(wèn)題，都需要用統(tǒng)計(jì)分析的方法處理。
　　近百年來(lái)，統(tǒng)計(jì)學(xué)得到了極大的發(fā)展。我們可用圖1-2的框架粗略地刻畫(huà)統(tǒng)計(jì)學(xué)發(fā)展的過(guò)程。
　　圖1-2統(tǒng)計(jì)學(xué)發(fā)現(xiàn)過(guò)程圖
　　其中，從1960~1980年，引導(dǎo)這一革命的是20世紀(jì)60年代的四項(xiàng)發(fā)現(xiàn)：①吉洪諾夫（Tikhonov）、伊萬(wàn)諾夫（Ivanov）和菲利浦（Philips）發(fā)現(xiàn)的關(guān)于解決不適定問(wèn)題的正則化原則。②帕仁（Parzen）、羅森布拉特（Rosenblatt）和陳瑟夫（Chentsov）發(fā)現(xiàn)的非參數(shù)統(tǒng)計(jì)學(xué)。③瓦普尼克（Vapnik）和車溫尼克思（Chervonenkis）發(fā)現(xiàn)的在泛函數(shù)空間的大數(shù)定律及其與學(xué)習(xí)過(guò)程的關(guān)系。④柯?tīng)柲�哥洛夫（Kolmogorov）、索洛莫諾夫（Solomonoff）和沙坦（Chaitin）發(fā)現(xiàn)的算法復(fù)雜性及其與歸納推理的關(guān)系。
　　這四項(xiàng)發(fā)現(xiàn)也成為人們對(duì)學(xué)習(xí)過(guò)程研究的重要基礎(chǔ)。下面我們列出與統(tǒng)計(jì)學(xué)有關(guān)的機(jī)器學(xué)習(xí)方法。
　�。�1）傳統(tǒng)方法
　　統(tǒng)計(jì)學(xué)在解決機(jī)器學(xué)習(xí)問(wèn)題中起著基礎(chǔ)性的作用。傳統(tǒng)的統(tǒng)計(jì)學(xué)所研究的主要是漸近理論，即當(dāng)樣本趨向于無(wú)窮多時(shí)的統(tǒng)計(jì)性質(zhì)。統(tǒng)計(jì)方法主要考慮測(cè)試預(yù)想的假設(shè)和數(shù)據(jù)模型擬合。它依賴于顯式的基本概率模型。統(tǒng)計(jì)方法處理過(guò)程可分為三個(gè)階段：①搜集數(shù)據(jù)：采樣、實(shí)驗(yàn)設(shè)計(jì)。②分析數(shù)據(jù)：建模、知識(shí)發(fā)現(xiàn)、可視化。③進(jìn)行推理：預(yù)測(cè)、分類。
　　常見(jiàn)的統(tǒng)計(jì)方法有回歸分析（多元回歸、自回歸等）、判別分析（貝葉斯判別、費(fèi)歇爾判別、非參數(shù)判別等）、聚類分析（系統(tǒng)聚類、動(dòng)態(tài)聚類等）、探索性分析（主元分析法、相關(guān)分析法等）等。
　�。�2）模糊集
　　模糊集是表示和處理不確定性數(shù)據(jù)的重要方法。模糊集不僅可以處理不完全數(shù)據(jù)、噪聲或不精確數(shù)據(jù)，而且在開(kāi)發(fā)數(shù)據(jù)的不確定性模型方面是有用的，可以提供比傳統(tǒng)方法更靈巧、更平滑的性能。
　�。�3）支持向量機(jī)
　　支持向量機(jī)（support vector machine，SVM）建立在計(jì)算學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則之上，其主要思想針對(duì)兩類分類問(wèn)題，在高維空間中尋找一個(gè)超平面作為兩類的分割，以保證最小的分類錯(cuò)誤率。而且SVM有一個(gè)重要的優(yōu)點(diǎn)就是可以處理線性不可分的情況。
　�。�4）粗糙集
　　粗糙集（rough set）理論由帕夫拉克（Z.Pawlak）在1982年提出。它是一種新的數(shù)學(xué)工具，用于處理含糊性和不確定性問(wèn)題，在數(shù)據(jù)挖掘中發(fā)揮著重要的作用。粗糙集是由集合的下近似、上近似來(lái)定義的。下近似中的每一個(gè)成員都是該集合的確定成員，而不是上近似中的成員肯定不是該集合的成員。粗糙集的上近似是下近似和邊界區(qū)的合并。邊界區(qū)的成員可能是該集合的成員，但不是確定的成員�？梢哉J(rèn)為粗糙集是具有三值隸屬函數(shù)的模糊集，即是、不是、也許。與模糊集一樣，它是一種處理數(shù)據(jù)不確定性的數(shù)學(xué)工具，常與規(guī)則歸納、分類和聚類方法結(jié)合起來(lái)使用，很少單獨(dú)使用。
　　1.1.4.2機(jī)器學(xué)習(xí)
　　西蒙（Simon）對(duì)機(jī)器學(xué)習(xí)的定義是：“如果一個(gè)系統(tǒng)能夠通過(guò)執(zhí)行某種過(guò)程而改進(jìn)它的性能，這就是學(xué)習(xí)”。這個(gè)說(shuō)法的要點(diǎn)是：第一，學(xué)習(xí)是一個(gè)過(guò)程；第二，學(xué)習(xí)是相對(duì)一個(gè)系統(tǒng)而言的；第三，學(xué)習(xí)改變系統(tǒng)性能。過(guò)程、系統(tǒng)和改變性能是學(xué)習(xí)的三個(gè)要點(diǎn)。對(duì)上述說(shuō)法，第一點(diǎn)是自然的。第二點(diǎn)中的系統(tǒng)則相當(dāng)復(fù)雜，一般是指一臺(tái)計(jì)算機(jī)，但是，也可以是計(jì)算系統(tǒng)