數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)方法研究

摘要:歸納了最新的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)方法的理論和應(yīng)用進(jìn)展，詳細(xì)總結(jié)了研究和應(yīng)用的一些關(guān)鍵技術(shù)，最后對(duì)數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)將來的理論發(fā)展趨勢(shì)和應(yīng)用趨勢(shì)做出了展望。

關(guān)鍵詞:數(shù)據(jù)挖掘;知識(shí)發(fā)現(xiàn)

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)02-281-03

The Studay of Date Mining and Knowledge Discovery in Database

SHI Feng-fei， HU Fei， LU Chao

(Department of Physics， Shaanxi University of Technology， Hanzhong 723000， China)

Abstract: This article tries to draw a general picture of the newest development progress of Data Mining and Knowledge Discovery in Database within both theory and application of it. Summarized the general approaches of research and application in DM/KDD fields. At the end， forecasted the DM/KDD foreseeable future.

Key words: data mining; knowledge discovery in database

隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展和數(shù)據(jù)庫系統(tǒng)的廣泛應(yīng)用，數(shù)據(jù)庫中存儲(chǔ)的數(shù)據(jù)量急劇增大。但目前數(shù)據(jù)庫系統(tǒng)所能做到的只是對(duì)數(shù)據(jù)庫中已有的數(shù)據(jù)進(jìn)行存取，人們只能看到這些數(shù)據(jù)的一些表面的東西，而不能看到隱藏在這些數(shù)據(jù)之后的更重要的信息，即關(guān)于這些數(shù)據(jù)的整體特征的描述和發(fā)展趨勢(shì)的預(yù)測(cè)等等。而后一種信息對(duì)決策過程具有重要的意義。這就要求我們將研究重點(diǎn)從數(shù)據(jù)的生產(chǎn)和傳輸能力轉(zhuǎn)移到數(shù)據(jù)的分析能力上來。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)是人工智能、機(jī)器學(xué)習(xí)與數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物。數(shù)據(jù)挖掘是知識(shí)發(fā)現(xiàn)最關(guān)鍵的步驟，也是技術(shù)難點(diǎn)所在。知識(shí)發(fā)現(xiàn)的研究是信息技術(shù)的匯總，它融數(shù)據(jù)庫技術(shù)、人工智能技術(shù)、數(shù)理統(tǒng)計(jì)技術(shù)和可視化技術(shù)為一體，是一個(gè)多學(xué)科相互交叉融合所形成的一個(gè)新興的具有廣泛應(yīng)用前景的研究領(lǐng)域。

1 知識(shí)發(fā)現(xiàn)的核心——數(shù)據(jù)挖掘

數(shù)據(jù)挖掘是知識(shí)發(fā)現(xiàn)的最核心的部分，是采用機(jī)器學(xué)習(xí)、統(tǒng)計(jì)等方法進(jìn)行知識(shí)學(xué)習(xí)的階段。數(shù)據(jù)挖掘算法的好壞將直接影響到所發(fā)現(xiàn)知識(shí)的好壞。目前大多數(shù)的研究都集中在數(shù)據(jù)挖掘算法和應(yīng)用上。人們往往不嚴(yán)格區(qū)分?jǐn)?shù)據(jù)挖掘和數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)，把兩者混淆使用。數(shù)據(jù)挖掘的任務(wù)是從數(shù)據(jù)中發(fā)現(xiàn)模式。模式有很多種，按功能可分有兩大類:預(yù)測(cè)型(Predictive)模式和描述型(Descriptive)模式。預(yù)測(cè)型模式是可以根據(jù)數(shù)據(jù)項(xiàng)的值精確確定某種結(jié)果的模式。挖掘預(yù)測(cè)型模式所使用的數(shù)據(jù)也都是可以明確知道結(jié)果的。描述型模式是對(duì)數(shù)據(jù)中存在的規(guī)則做一種描述，或者根據(jù)數(shù)據(jù)的相似性把數(shù)據(jù)分組。描述型模式不能直接用于預(yù)測(cè)在實(shí)際應(yīng)用中，往往根據(jù)模式的實(shí)際作用細(xì)分為以下幾種:

1.1 分類模式

分類模式是一個(gè)分類函數(shù)(分類器)，能夠把數(shù)據(jù)集中的數(shù)據(jù)項(xiàng)映射到某個(gè)給定的類上。分類模式往往表現(xiàn)為一棵分類樹，根據(jù)數(shù)據(jù)的值從樹根開始搜索，沿著數(shù)據(jù)滿足的分支往上走，走到樹葉就能確定類別。

1.2 回歸模式

回歸模式的函數(shù)定義與分類模式相似，它們的差別在于分類模式的預(yù)測(cè)值是離散的，回歸模式的預(yù)測(cè)值是連續(xù)的。

1.3 時(shí)間序列模式

時(shí)間序列模式根據(jù)數(shù)據(jù)隨時(shí)間變化的趨勢(shì)預(yù)測(cè)將來的值。這里要考慮到時(shí)間的特殊性質(zhì)，像一些周期性的時(shí)間定義如星期、月、季節(jié)、年等，不同的日子如節(jié)假日可能造成的影響，日期本身的計(jì)算方法，還有一些需要特殊考慮的地方如時(shí)間前后的相關(guān)性(過去的事情對(duì)將來有多大的影響力)等。只有充分考慮時(shí)間因素，利用現(xiàn)有數(shù)據(jù)隨時(shí)間變化的一系列的值，才能更好地預(yù)測(cè)將來的值。

1.4 聚類模式

聚類模式把數(shù)據(jù)劃分到不同的組中，組之間的差別盡可能大，組內(nèi)的差別盡可能小。與分類模式不同，進(jìn)行聚類前并不知道將要?jiǎng)澐殖蓭讉€(gè)組和什么樣的組，也不知道根據(jù)哪一(幾)個(gè)數(shù)據(jù)項(xiàng)來定義組。一般來說，業(yè)務(wù)知識(shí)豐富的人應(yīng)該可以理解這些組的含義，如果產(chǎn)生的模式無法理解或不可用，則該模式可能是無意義的，需要回到上階段重新組織數(shù)據(jù)。

1.5 關(guān)聯(lián)模式和序列模式

關(guān)聯(lián)模式是數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則。序列模式與關(guān)聯(lián)模式相仿，而把數(shù)據(jù)之間的關(guān)聯(lián)性與時(shí)間聯(lián)系起來。為了發(fā)現(xiàn)序列模式，不僅需要知道事件是否發(fā)生，而且需要確定事件發(fā)生的時(shí)間。

在解決實(shí)際問題時(shí)，經(jīng)常要同時(shí)使用多種模式。分類模式和回歸模式是使用最普遍的模式。分類模式、回歸模式、時(shí)間序列模式也被認(rèn)為是受監(jiān)督知識(shí)，因?yàn)樵诮⒛Ｊ角皵?shù)據(jù)的結(jié)果是已知的，可以直接用來檢測(cè)模式的準(zhǔn)確性，模式的產(chǎn)生是在受監(jiān)督的情況下進(jìn)行的。一般在建立這些模式時(shí)，使用一部分?jǐn)?shù)據(jù)作為樣本，用另一部分?jǐn)?shù)據(jù)來檢驗(yàn)、校正模式。聚類模式、關(guān)聯(lián)模式、序列模式則是非監(jiān)督知識(shí)，因?yàn)樵谀Ｊ浇⑶敖Y(jié)果是未知的，模式的產(chǎn)生不受任何監(jiān)督。

2 數(shù)據(jù)挖掘的方法

2.1 決策樹方法

利用信息論中的互信息(信息增益)尋找數(shù)據(jù)庫中具有最大信息量的字段，建立決策樹的一個(gè)結(jié)點(diǎn)，再根據(jù)字段的不同取值建立樹的分枝;在每個(gè)分枝子集中重復(fù)建樹的下層結(jié)點(diǎn)和分枝的過程，即可建立決策樹。流行的IBLE方法是，利用信息論中的信道容量，尋找數(shù)據(jù)庫中信息量從大到小的多個(gè)字段的取值，建立決策規(guī)則樹的一個(gè)結(jié)點(diǎn)，再根據(jù)所有字段取值的權(quán)值之和與兩個(gè)閾值比較，建立左、中、右三個(gè)分枝;在各分枝子集中重復(fù)建樹結(jié)點(diǎn)和分枝的過程，即可建立決策規(guī)則樹。

2.2 神經(jīng)網(wǎng)絡(luò)方法

它是模擬人腦神經(jīng)元結(jié)構(gòu)，以MP模型和Hebb學(xué)習(xí)規(guī)則為基礎(chǔ)，建立三大類多種神經(jīng)網(wǎng)絡(luò)模型。前饋式網(wǎng)絡(luò):它以感知機(jī)、反向傳播模型、函數(shù)型網(wǎng)絡(luò)為代表，可用于預(yù)測(cè)、模式識(shí)別等方面。反饋式網(wǎng)絡(luò):它以Hopfield的離散模型和連續(xù)模型為代表，分別用于聯(lián)想記憶和優(yōu)化計(jì)算。自組織網(wǎng)絡(luò):它以ART模型、Koholon模型為代表，用于聚類。神經(jīng)網(wǎng)絡(luò)的知識(shí)體現(xiàn)在網(wǎng)絡(luò)連接的權(quán)值上，是一個(gè)分布式矩陣結(jié)構(gòu)，神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)體現(xiàn)在神經(jīng)網(wǎng)絡(luò)權(quán)值的逐步計(jì)算上(包括反復(fù)迭代或累加計(jì)算)。

2.3 覆蓋正例、排斥反例方法

利用覆蓋所有正例、排斥所有反例的思想來尋找規(guī)則。比較典型的有Michalski的AQ11方法、洪家榮改進(jìn)的AQ15方法，以及洪家榮的AE5方法。AQ系列的核心算法是，在正例集中任選一個(gè)種子，到反例集中逐個(gè)比較，對(duì)字段取值構(gòu)成的選擇子相容則舍去，相斥則保留。按此思想循環(huán)所有正例種子，將得到正例集的規(guī)則(選擇子的合取式)。AE系列方法是用擴(kuò)張矩陣來完成的。

2.4 粗集(Rough Set)方法

在數(shù)據(jù)庫中，將行元素看成對(duì)象，列元素是屬性(分為條件屬性和決策屬性)。等價(jià)關(guān)系R定義為不同對(duì)象在某個(gè)(或幾個(gè))屬性上取值相同，這些滿足等價(jià)關(guān)系的對(duì)象組成的集合稱為該等價(jià)關(guān)系R的等價(jià)類。條件屬性上的等價(jià)類E與決策屬性上的等價(jià)類Y之間有三種情況:1) 下近似:Y包含E;2) 上近似:Y和E的交非空;3) 無關(guān):Y和E的交為空。對(duì)下近似建立確定性規(guī)則，對(duì)上近似建立不確定性規(guī)則(含可信度)，對(duì)無關(guān)情況不存在規(guī)則。

2.5 概念樹方法

數(shù)據(jù)庫中記錄的屬性字段按歸類方式進(jìn)行抽象，建立起來的層次結(jié)構(gòu)稱為概念樹。利用概念樹提升的方法可以大大濃縮數(shù)據(jù)庫中的記錄。對(duì)多個(gè)屬性字段的概念樹提升，將得到高度概括的知識(shí)基表，然后再將它轉(zhuǎn)換成規(guī)則。

2.6 遺傳算法

模擬生物進(jìn)化過程的算法，由三個(gè)基本算子組成:繁殖(選擇)是從一個(gè)舊種群(父代)選出生命力強(qiáng)的個(gè)體，產(chǎn)生新種群(后代)的過程;交叉(重組)選擇兩個(gè)不同個(gè)體(染色體)的部分(基因)進(jìn)行交換，形成新個(gè)體;變異(突變)對(duì)某些個(gè)體的某些基因進(jìn)行變異(1變0、0變1)。遺傳算法可起到產(chǎn)生優(yōu)良后代的作用。這些后代需滿足適應(yīng)值，經(jīng)過若干代的遺傳，將得到滿足要求的后代(問題的解)。遺傳算法已在優(yōu)化計(jì)算和分類機(jī)器學(xué)習(xí)方面發(fā)揮了顯著作用。

2.7 公式發(fā)現(xiàn)

是在工程和科學(xué)數(shù)據(jù)庫(由試驗(yàn)數(shù)據(jù)組成)中，對(duì)若干數(shù)據(jù)項(xiàng)(變量)進(jìn)行一定的數(shù)學(xué)運(yùn)算，求得相應(yīng)的數(shù)學(xué)公式。

2.8 統(tǒng)計(jì)分析方法

在數(shù)據(jù)庫字段項(xiàng)之間存在兩種關(guān)系:函數(shù)關(guān)系(能用函數(shù)公式表示的確定性關(guān)系)和相關(guān)關(guān)系(不能用函數(shù)公式表示，但仍是相關(guān)確定關(guān)系)

2.9 模糊論方法

利用模糊集合理論對(duì)實(shí)際問題進(jìn)行模糊評(píng)判、模糊決策、模糊模式識(shí)別和模糊聚類分析。模糊性是客觀存在的，系統(tǒng)的復(fù)雜性越高，精確化能力就越低，也就意味著模糊性越強(qiáng)。

2.10 可視化技術(shù)

可視化數(shù)據(jù)分析技術(shù)拓寬了傳統(tǒng)的圖表功能，使用戶對(duì)數(shù)據(jù)的剖析更清楚。例如，把數(shù)據(jù)庫中的多維數(shù)據(jù)變成多種圖形，這對(duì)揭示數(shù)據(jù)的狀況、內(nèi)在本質(zhì)及規(guī)律性起到了很強(qiáng)的作用。

3 知識(shí)發(fā)現(xiàn)的處理過程

對(duì)知識(shí)發(fā)現(xiàn)的一個(gè)比較公認(rèn)的定義是:知識(shí)發(fā)現(xiàn)是識(shí)別出存在于數(shù)據(jù)庫中的可信的、新穎的、有效的并能被人理解的模式的非平凡的過程。從定義中可以看出，知識(shí)發(fā)現(xiàn)是一個(gè)高級(jí)的處理過程，它從數(shù)據(jù)集中識(shí)別出以模式來表示的知識(shí)。高級(jí)的處理過程是指一個(gè)多步驟的處理過程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式上升過程，如圖1所示。處理步驟如下:

準(zhǔn)備:熟悉應(yīng)用領(lǐng)域的數(shù)據(jù)和背景知識(shí)。

確定KDD的目標(biāo):根據(jù)用戶要求，確定所要完成的KDD是發(fā)現(xiàn)何種類型的知識(shí)，確定知識(shí)模式。一般認(rèn)為最常發(fā)現(xiàn)的4類知識(shí)模式是:廣義型知識(shí)、分類型知識(shí)、關(guān)聯(lián)型知識(shí)和預(yù)測(cè)型知識(shí)。

數(shù)據(jù)收集和選擇:根據(jù)發(fā)現(xiàn)任務(wù)從數(shù)據(jù)庫中提取相關(guān)的數(shù)據(jù)集合。

數(shù)據(jù)預(yù)處理:對(duì)與發(fā)現(xiàn)任務(wù)相關(guān)的數(shù)據(jù)集合進(jìn)行再加工，檢查數(shù)據(jù)的完整性和一致性，并消除數(shù)據(jù)中的噪音。

確定知識(shí)發(fā)現(xiàn)方法:根據(jù)發(fā)現(xiàn)任務(wù)的目標(biāo)和發(fā)現(xiàn)知識(shí)的模式，設(shè)計(jì)或選擇合適的知識(shí)發(fā)現(xiàn)算法。

發(fā)現(xiàn)模式:調(diào)用相應(yīng)的算法發(fā)現(xiàn)所需的知識(shí)。

模式解釋和知識(shí)評(píng)價(jià):對(duì)發(fā)現(xiàn)的模式進(jìn)行解釋，將發(fā)現(xiàn)的知識(shí)以一種適當(dāng)?shù)男问匠尸F(xiàn)給用戶。其中包括對(duì)知識(shí)一致性、新穎性和有效性的評(píng)價(jià)。

4 知識(shí)發(fā)現(xiàn)的的主要技術(shù)與發(fā)展

4.1 知識(shí)發(fā)現(xiàn)的具體過程

需要采用的主要技術(shù)有:

1) 特征提取:從與學(xué)習(xí)任務(wù)相關(guān)的一組數(shù)據(jù)中提取出關(guān)于這些數(shù)據(jù)的特征式。這些特征式表達(dá)了該數(shù)據(jù)集的總體特征。

2) 分類:根據(jù)數(shù)據(jù)的不同特征式，將其劃分為不同的數(shù)據(jù)類。目前已有許多數(shù)據(jù)分類方法，如歸納法、決策樹方法、神經(jīng)網(wǎng)絡(luò)方法和簇集方法等。

3) 聚類:根據(jù)所處理的數(shù)據(jù)的一些屬性(特征)，對(duì)一些數(shù)據(jù)進(jìn)行分類，經(jīng)過分類以后的數(shù)據(jù)，在各類之間其相似程度很小，而在某一類內(nèi)部，其數(shù)據(jù)之間的相似度則很大。分類結(jié)束后，每類中的數(shù)據(jù)由惟一的標(biāo)志進(jìn)行標(biāo)識(shí)，類中的數(shù)據(jù)的共同特征也被提取出來用于對(duì)該類的特征描述。

4) 相關(guān)性分析:發(fā)現(xiàn)特征之間或數(shù)據(jù)之間的相互依賴關(guān)系，常用技術(shù)有回歸分析、信念網(wǎng)絡(luò)等。

5) 偏差分析:如分類中的反常實(shí)例、例外模式、觀測(cè)結(jié)果對(duì)期望值的偏離以及量值隨時(shí)間的變化等等。其基本思想是尋找觀察結(jié)果與參照量之間的有意義的差別。

4.2 知識(shí)發(fā)現(xiàn)離不開數(shù)據(jù)庫和數(shù)據(jù)倉庫技術(shù)的發(fā)展

可以從下面的幾個(gè)方面來考慮它們之間的關(guān)系。

1) 知識(shí)發(fā)現(xiàn)與演繹數(shù)據(jù)庫

演繹數(shù)據(jù)庫就是在傳統(tǒng)關(guān)系型數(shù)據(jù)庫中引入演繹規(guī)則，提供邏輯推理能力。演繹數(shù)據(jù)庫中的KDD包括以下兩種情形;在演繹規(guī)則所定義的數(shù)據(jù)上發(fā)現(xiàn)知識(shí)(規(guī)則);在已開采的知識(shí)(規(guī)則)上進(jìn)一步發(fā)現(xiàn)新的知識(shí)(規(guī)則)，逐步求精。這一點(diǎn)可能是KDD與演繹數(shù)據(jù)庫相結(jié)合更具有潛在意義的地方。

2) 知識(shí)發(fā)現(xiàn)與面向?qū)ο髷?shù)據(jù)庫

面向?qū)ο髷?shù)據(jù)庫在傳統(tǒng)數(shù)據(jù)庫上引入面向?qū)ο蟾拍睿鐚?duì)象標(biāo)識(shí)、封裝、繼承、多態(tài)性等，支持復(fù)雜應(yīng)用領(lǐng)域中的數(shù)據(jù)建模要求。KDD可用于發(fā)現(xiàn)基于對(duì)象層次的關(guān)聯(lián)規(guī)則。事實(shí)上，面向?qū)ο髷?shù)據(jù)庫的類層次結(jié)構(gòu)對(duì)描述知識(shí)發(fā)現(xiàn)的背景知識(shí)提供了極其自然的支持。同時(shí)，其繼承和封裝機(jī)制也能支持KDD的模塊化、可重用性和多態(tài)性。

3) 知識(shí)發(fā)現(xiàn)與多媒體數(shù)據(jù)庫

多媒體數(shù)據(jù)庫極大地?cái)U(kuò)充了數(shù)據(jù)的類型，一些原來不能用簡(jiǎn)單的結(jié)構(gòu)化數(shù)據(jù)表達(dá)的信息，可以直接通過圖像、聲音、動(dòng)畫等信息來存儲(chǔ)和檢索，這樣就擴(kuò)展了KDD的研究領(lǐng)域，而且國外已經(jīng)出現(xiàn)了這樣的商品化產(chǎn)品。

5 結(jié)束語

目前對(duì)知識(shí)發(fā)現(xiàn)的研究圍繞理論、技術(shù)和應(yīng)用等方面展開。理論方面的研究包括:數(shù)據(jù)和知識(shí)的表示;結(jié)構(gòu)化、文本和多媒體數(shù)據(jù)的模型構(gòu)造;不確定性管理;知識(shí)的實(shí)用性評(píng)測(cè);數(shù)據(jù)挖掘的算法復(fù)雜性和效率分析;海量數(shù)據(jù)集的統(tǒng)計(jì)學(xué)等。技術(shù)方面的研究主要包括數(shù)據(jù)挖掘方法、數(shù)據(jù)挖掘算法和知識(shí)發(fā)現(xiàn)過程。數(shù)據(jù)挖掘方法包括分類、聚類、預(yù)測(cè)和評(píng)估、相關(guān)性分析、搜索和優(yōu)化等。數(shù)據(jù)挖掘算法包括空間數(shù)據(jù)、文本數(shù)據(jù)和多媒體數(shù)據(jù)的數(shù)據(jù)挖掘算法、并行和分布式數(shù)據(jù)挖掘技術(shù)等。知識(shí)發(fā)現(xiàn)過程包括數(shù)據(jù)預(yù)處理技術(shù)，如數(shù)據(jù)去噪、有效樣本選取、數(shù)據(jù)縮減等，此外還有知識(shí)的評(píng)估、統(tǒng)一和解釋、數(shù)據(jù)和知識(shí)的可視化。應(yīng)用研究包括開發(fā)各種KDD系統(tǒng)和工具及其在各個(gè)行業(yè)中的應(yīng)用，另外還包括一些有關(guān)數(shù)據(jù)保密的問題。

參考文獻(xiàn):

[1] 胡斌.基于網(wǎng)格技術(shù)的分布式空間數(shù)據(jù)挖掘算法研究[D].長(zhǎng)沙:中南大學(xué)，2008.

[2] 孔忠勇.基于地域因素的分布式?jīng)Q策樹算法與其網(wǎng)格模型研究[D].杭州:浙江工商大學(xué)，2008.

[3] 魏定國，彭宏.基于知識(shí)網(wǎng)格的數(shù)據(jù)挖掘[J].計(jì)算機(jī)科學(xué)，2006，33(6).

[4] 盧超.談軟件項(xiàng)目管理[J].中小企業(yè)管理與科技，2008(29).

[5] 呂品，陳年生，董武世.一種網(wǎng)格數(shù)據(jù)挖掘應(yīng)用系統(tǒng)的設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(1).

[6] 盧超.基于熵的多點(diǎn)脈搏傳感器信息融合方法[J].佳木斯大學(xué)學(xué)報(bào):自然科學(xué)版，2009(5).

[7] 魏大慶，應(yīng)宏.基于知識(shí)網(wǎng)格服務(wù)的分布式數(shù)據(jù)挖掘研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(15).

[8] 胡蓉，肖基毅.基于知識(shí)網(wǎng)格的分布式數(shù)據(jù)挖掘[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007(10).