知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概述

1、知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概述摘要：數(shù)據(jù)挖掘(data mining),就是從存放在數(shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的人量 的數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過(guò)程。 關(guān)鍵字：知識(shí)發(fā)現(xiàn) 數(shù)據(jù)挖掘 神經(jīng)網(wǎng)絡(luò) 決策樹(shù) 引言知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘是人工智能，機(jī)器學(xué)習(xí)與數(shù)據(jù)庫(kù)技術(shù)相結(jié)合的產(chǎn)物。隨著數(shù)據(jù) 庫(kù)技術(shù)的成熟和數(shù)據(jù)應(yīng)用的普及，人類積累的數(shù)據(jù)量正在以指數(shù)速度迅速增長(zhǎng)。進(jìn)入九 十年代，伴隨著互聯(lián)網(wǎng)的出現(xiàn)和發(fā)展，以及各種局域網(wǎng)的產(chǎn)生和應(yīng)用，將整個(gè)枇界聯(lián)成 一個(gè)小小的地球村，人們可以跨越時(shí)空地在網(wǎng)上交換數(shù)據(jù)信息和協(xié)同工作。由于計(jì)算機(jī) 數(shù)據(jù)采集工具以及關(guān)系數(shù)據(jù)庫(kù)技術(shù)的發(fā)展，各行業(yè)存儲(chǔ)了大量的

2、數(shù)據(jù)，而關(guān)系數(shù)據(jù)庫(kù)提 供的簡(jiǎn)單查詢及報(bào)表生成功能，只能獲得數(shù)據(jù)的表層信息，而不能獲得數(shù)據(jù)屬性的內(nèi)在 關(guān)系和隱含的信息，這樣既淹沒(méi)了包含的知識(shí)又造成了資源的浪費(fèi)。傳統(tǒng)的數(shù)據(jù)分析手 段更是難以應(yīng)付，導(dǎo)致越來(lái)越嚴(yán)重的數(shù)據(jù)災(zāi)難，使決策者出現(xiàn)或是窮于應(yīng)付，或是置z 不理的事實(shí)。為了使消耗大量財(cái)力與物力所收集與整理的寶貴數(shù)據(jù)資源得以利用，有效 解決數(shù)據(jù)豐富性及知識(shí)貧乏性的矛盾，需要新技術(shù)智能、自動(dòng)地分析處理原始數(shù)據(jù)，促 使了數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(kdd, knowledge discovery in database),也有人稱為數(shù) 據(jù)挖掘(data mining)技術(shù)的出現(xiàn)。從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)(knowl

3、edge discovery in database-kdd) 一詞是于1989年8月在美國(guó)底特律召開(kāi)的第一屆kdd國(guó)際學(xué)術(shù)會(huì)議上 正式形成的。1995年在加拿大召開(kāi)了第一屆知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘(data mining一dm,有 人翻譯為數(shù)據(jù)挖掘、數(shù)據(jù)發(fā)掘、數(shù)據(jù)采掘)國(guó)際學(xué)術(shù)會(huì)議。1、數(shù)據(jù)挖掘技術(shù)的概念1. 1知識(shí)發(fā)現(xiàn)的概念kdd (知識(shí)發(fā)現(xiàn))是一個(gè)綜合的過(guò)程，它包括數(shù)據(jù)錄入、迭代求解、用戶交互以及許 多定制要求和決策設(shè)計(jì)等，這一研究領(lǐng)域興起于八十年代初，它是一個(gè)眾多學(xué)科諸如人 工智能、機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫(kù)和知識(shí)庫(kù)、數(shù)據(jù)可視化等相互交叉、融 合所形成的一個(gè)新興的且具有廣闊前景的領(lǐng)域

4、。在 kdd-96 國(guó)際會(huì)議上,fayyad, piatetsky-shapi ro 和 smyth 對(duì) kdd 作了如下描述： 指從數(shù)據(jù)庫(kù)中識(shí)別并獲取獲取止確、新穎、有潛在應(yīng)用價(jià)值和最終可理解的模式的非平 凡過(guò)程。在這個(gè)描述屮，數(shù)據(jù)庫(kù)是一系列數(shù)據(jù)事實(shí)的集合。模式即知識(shí)，它給出了數(shù)據(jù)特性或數(shù)據(jù)之間的關(guān)系，是對(duì)數(shù)據(jù)所包含的信息更抽象的描述。按功能可以分為預(yù)測(cè) 型模式和描述型模式。在實(shí)際應(yīng)用屮，可以細(xì)分為關(guān)聯(lián)模式、分類模式、聚類模式和序 列模式等。過(guò)程是在kdd中包含的多階段的處理，如數(shù)據(jù)的預(yù)處理、模式搜索、知識(shí)表 示及知識(shí)評(píng)價(jià)等。最終可理解性則要求發(fā)現(xiàn)的模式能被用戶理解，目前它主要體現(xiàn)在簡(jiǎn) 潔性

5、上。非平凡是指它已經(jīng)超越了一般封閉形式的數(shù)量計(jì)算，而將包括對(duì)結(jié)構(gòu)、模式和 參數(shù)的搜索。1.2數(shù)據(jù)挖掘的對(duì)象數(shù)據(jù)挖掘的對(duì)象主要是關(guān)系數(shù)據(jù)庫(kù)。隨著數(shù)據(jù)開(kāi)采技術(shù)的發(fā)展，逐步進(jìn)入到空間數(shù) 據(jù)庫(kù)，吋態(tài)數(shù)據(jù)庫(kù)，文本數(shù)據(jù)庫(kù)，多媒體數(shù)據(jù)庫(kù)，環(huán)球互聯(lián)網(wǎng)等。文字、咅頻、圖象、 視頻等多媒體數(shù)據(jù)己逐漸成為信息領(lǐng)域的重要表現(xiàn)形式。音頻、視頻的數(shù)拯量很大，要 從千萬(wàn)計(jì)的多媒體數(shù)據(jù)屮找出需要的數(shù)據(jù)和信息是很困難的。目前，對(duì)多媒體數(shù)據(jù)的處 理只能在存取，編輯，集成，快進(jìn)快退等基木操作上，對(duì)多媒體信息的檢索僅靠文件標(biāo) 識(shí)、關(guān)鍵字等進(jìn)行檢索，局限性很大。目前，基于內(nèi)容的多媒體檢索，通過(guò)實(shí)例的查詢 方式，檢索相似圖象，咅頻，視頻

6、信息的應(yīng)用已經(jīng)相當(dāng)成熟。基于內(nèi)容的音頻、視頻信 息的聚類、分類、相似查詢等數(shù)據(jù)挖掘技術(shù)，己成為研究的熱點(diǎn)。1.3 kdd過(guò)程的一般步驟kdd過(guò)程由多個(gè)階段的處理相互連接起來(lái)，反復(fù)進(jìn)行人機(jī)交互過(guò)程，一般有數(shù)據(jù)的 預(yù)處理、模式搜索、知識(shí)表示及知識(shí)評(píng)價(jià)等。kdd過(guò)程一般如圖2. 1可視化't數(shù)據(jù)集-£f目標(biāo)數(shù)據(jù)預(yù)處理數(shù)據(jù)抽樣選取預(yù)處理轉(zhuǎn)換解釋與評(píng)價(jià)轉(zhuǎn)換后的數(shù)據(jù)抽取的信息耐-_有用知識(shí)圖2. 1由上圖知，知識(shí)發(fā)現(xiàn)的過(guò)程可粗略的理解為三部曲：數(shù)據(jù)準(zhǔn)備(data preparation)階段、數(shù)拯挖掘(data mining)階段以及模型的解釋評(píng)估(interpreparation an

7、d evaluation)階段。1.4數(shù)據(jù)發(fā)掘與知識(shí)發(fā)現(xiàn)的關(guān)系從知識(shí)發(fā)現(xiàn)的概念及步驟中，我們可以看出，其實(shí)知識(shí)發(fā)現(xiàn)的核心就是數(shù)據(jù)發(fā)掘， 而數(shù)據(jù)發(fā)掘的目的就是冇效地從海量數(shù)據(jù)屮捉取出需要的知識(shí)，實(shí)現(xiàn)從數(shù)據(jù)到信息再到 知識(shí)轉(zhuǎn)變?yōu)閮r(jià)值的過(guò)程。并非所冇的知識(shí)發(fā)現(xiàn)任務(wù)都被視為數(shù)據(jù)挖掘。例如，使用數(shù)據(jù)庫(kù)管理系統(tǒng)查找個(gè)別的記 錄，或通過(guò)因特網(wǎng)的搜索引擎查找特定的互聯(lián)網(wǎng)頁(yè)面，則是信息檢索領(lǐng)域的任務(wù)。雖然 這些任務(wù)是重要的，可能涉及使用復(fù)雜的算法和數(shù)據(jù)結(jié)構(gòu)，但是它們主要依賴傳統(tǒng)的計(jì) 算機(jī)科學(xué)技術(shù)和數(shù)據(jù)的明顯特征來(lái)創(chuàng)建索引結(jié)構(gòu)，從而有效地組織和檢索信息。盡管如 此，數(shù)據(jù)挖掘技術(shù)也具冇増強(qiáng)信息檢索系統(tǒng)的能力，這樣一

8、來(lái)，就把人們對(duì)數(shù)據(jù)的應(yīng)用, 從低層次的末端查詢操作，提高到為各級(jí)決策者提供決策支持的高級(jí)層面。2、知識(shí)發(fā)現(xiàn)的主要階段2. 1 數(shù)據(jù)準(zhǔn)備(data preparation)kdd的處理對(duì)象是大量的數(shù)據(jù)，往往并不直接在這些數(shù)據(jù)上進(jìn)行知識(shí)發(fā)現(xiàn)，需耍做 些準(zhǔn)備工作。數(shù)據(jù)準(zhǔn)備一方面是從多種數(shù)據(jù)源去綜合所需要的數(shù)據(jù)，保證數(shù)據(jù)的綜合性、 易用性以及數(shù)據(jù)的質(zhì)量和數(shù)據(jù)的吋效性；另一方面就是如何從現(xiàn)有的數(shù)據(jù)屮衍生出所需 要數(shù)據(jù)的指標(biāo)。如果kdd的對(duì)象是數(shù)據(jù)庫(kù)，呢么這些工作往往在生成數(shù)據(jù)庫(kù)時(shí)已經(jīng)準(zhǔn)備 就緒。數(shù)據(jù)準(zhǔn)備是kdd的第一個(gè)階段，也是比較重要的一個(gè)階段，因?yàn)閿?shù)據(jù)準(zhǔn)備得好壞 將直接影響到數(shù)據(jù)挖掘的效率、準(zhǔn)確度以

9、及最終模型的有效性。2. 2 數(shù)據(jù)挖掘(data mining)數(shù)據(jù)挖掘的任務(wù)就是從數(shù)據(jù)屮發(fā)現(xiàn)模式和規(guī)律。根據(jù)kdd的口標(biāo)，數(shù)據(jù)挖掘階段需 要分析數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)搜索策略、選取相應(yīng)的參數(shù)、評(píng)價(jià)各搜索階段的假設(shè)和結(jié)果，得 到可能形成知識(shí)的模型。數(shù)據(jù)挖掘是kdd的關(guān)鍵階段，也是最困難的階段。在構(gòu)造具體的算法時(shí)往往涉及統(tǒng)計(jì)學(xué)、 機(jī)器學(xué)習(xí)、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、演化計(jì)算等多個(gè)領(lǐng)域，涉及這些領(lǐng)域的技術(shù)融合與創(chuàng) 新。事實(shí)上，數(shù)據(jù)挖掘就是一個(gè)利用各種分析工具在海量數(shù)據(jù)屮發(fā)現(xiàn)模型和數(shù)據(jù)間關(guān)系 的過(guò)程。2. 3 模型的解釋評(píng)估(interpreparation and evaluation)上述階段所獲得的模型，有

10、可能沒(méi)有實(shí)際意義或沒(méi)有使用價(jià)值，因此需要評(píng)估哪些 是冇效模型。評(píng)估工作可以根據(jù)用戶的要求來(lái)做，也可以通過(guò)數(shù)據(jù)檢驗(yàn)。這個(gè)階段還包 括把符合實(shí)際并有價(jià)值的模型以易于理解的方式呈現(xiàn)給用戶，這些呈現(xiàn)方式可以是語(yǔ)言 文字報(bào)告、函數(shù)解析表達(dá)式，也可以是圖表、圖形、決策樹(shù)等。3、數(shù)據(jù)挖掘的方法和技術(shù)數(shù)據(jù)開(kāi)采方法是由人工智能、機(jī)器學(xué)習(xí)的方法發(fā)展而來(lái)，結(jié)合傳統(tǒng)的統(tǒng)計(jì)分析方法、 模糊數(shù)學(xué)方法以及科學(xué)計(jì)算可視化技術(shù)，以數(shù)據(jù)庫(kù)為研究對(duì)彖，形成了數(shù)據(jù)開(kāi)采方法和 技術(shù)。3. 1神經(jīng)網(wǎng)絡(luò)方法神經(jīng)網(wǎng)絡(luò)（nerual net）指由大量神經(jīng)元互連而成的網(wǎng)絡(luò)，是模擬人腦的一類系統(tǒng)，有點(diǎn) 象服務(wù)器互連而成的互連網(wǎng)。人腦大約冇1000

11、億個(gè)神經(jīng)元，每個(gè)神經(jīng)元平均與10000 個(gè)其他神經(jīng)元互連，這就構(gòu)成了人類智慧的直接物質(zhì)基礎(chǔ)。神經(jīng)元由細(xì)胞體，樹(shù)突（輸 入端），軸突（輸出端）組成，冇興奮和抑制兩種工作狀態(tài)。每個(gè)神經(jīng)元到另一個(gè)神經(jīng) 元的連接權(quán)（后者對(duì)前者輸出的反應(yīng)程度）可以接受外界刺激而改變，這構(gòu)成了學(xué)習(xí)機(jī) 能的基礎(chǔ)。圖3. 1人工模擬了神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)：人工神經(jīng)網(wǎng)絡(luò)首先耍以一定的學(xué)習(xí)準(zhǔn)則進(jìn)行學(xué)習(xí)，然后才能工作?，F(xiàn)以人工神經(jīng)網(wǎng) 絡(luò)對(duì)手寫(xiě)“a”、兩個(gè)字母的識(shí)別為例進(jìn)行說(shuō)明，規(guī)定當(dāng)輸入網(wǎng)絡(luò)時(shí)，應(yīng)該輸 出“1”，而當(dāng)輸入為“甘 吋，輸出為“0”。所以網(wǎng)絡(luò)學(xué)習(xí)的準(zhǔn)則應(yīng)該是：如果網(wǎng)絡(luò)作 出錯(cuò)誤的的判決，則通過(guò)網(wǎng)絡(luò)的學(xué)習(xí)，應(yīng)使得網(wǎng)絡(luò)減少下次犯同

12、樣錯(cuò)誤的可能性。首先, 給網(wǎng)絡(luò)的各連接權(quán)值賦予（0, 1）區(qū)間內(nèi)的隨機(jī)值，將“a”所對(duì)應(yīng)的圖彖模式輸入給網(wǎng) 絡(luò)，網(wǎng)絡(luò)將輸入模式加權(quán)求和、與門(mén)限比較、再進(jìn)行非線性運(yùn)算，得到網(wǎng)絡(luò)的輸出。在 此情況下，網(wǎng)絡(luò)輸出為“1”和“0”的概率各為50%,也就是說(shuō)是完全隨機(jī)的。這時(shí)如 果輸出為“1”（結(jié)果正確），則使連接權(quán)值增大，以便使網(wǎng)絡(luò)再次遇到“a”模式輸入?yún)? 仍然能作出正確的判斷。如果輸出為“0”（結(jié)果錯(cuò)誤），則把網(wǎng)絡(luò)連接權(quán)值朝著減小綜 合輸入加權(quán)值的方向調(diào)整，其目的在于使網(wǎng)絡(luò)下次再遇到“a”模式輸入時(shí)，減小犯同 樣錯(cuò)誤的可能性。如此操作調(diào)整，當(dāng)給網(wǎng)絡(luò)輪番輸入若干個(gè)手寫(xiě)字母“a”、后，經(jīng) 過(guò)網(wǎng)絡(luò)按以上學(xué)

13、習(xí)方法進(jìn)行若干次學(xué)習(xí)后，網(wǎng)絡(luò)判斷的正確率將大犬提高。這說(shuō)明網(wǎng)絡(luò) 對(duì)這兩個(gè)模式的學(xué)習(xí)已經(jīng)獲得了成功，它已將這兩個(gè)模式分布地記憶在網(wǎng)絡(luò)的各個(gè)連接 權(quán)值上。當(dāng)網(wǎng)絡(luò)再次遇到其屮任何一個(gè)模式時(shí)，能夠作出迅速、準(zhǔn)確的判斷和識(shí)別。一 般來(lái)說(shuō)，網(wǎng)絡(luò)中所含的神經(jīng)元個(gè)數(shù)越多，則它能記憶、識(shí)別的模式也就越多。神經(jīng)網(wǎng) 絡(luò)模型利用大量的簡(jiǎn)單計(jì)算單元（神經(jīng)元）連成網(wǎng)絡(luò)，從而可以實(shí)現(xiàn)人規(guī)模并行計(jì)算； 其分布式的存儲(chǔ)結(jié)構(gòu)，將信息存在整個(gè)網(wǎng)屮，用權(quán)值體現(xiàn)出來(lái)，因而具有聯(lián)想能力，可 以從一個(gè)不完整的信息恢復(fù)出完整信息。其工作機(jī)理是通過(guò)學(xué)習(xí)來(lái)改變神經(jīng)元之間的連 接強(qiáng)度。常用神經(jīng)網(wǎng)絡(luò)模型冇：hopfield net harmming net> carpenter/grossberg 分 類器、單層感知網(wǎng)、多層感知網(wǎng)、kohonen的門(mén)組織特性圖和反向傳播（bp）網(wǎng)絡(luò)。3.2決策樹(shù)方法決策樹(shù)方法是應(yīng)用最廣泛的歸納學(xué)習(xí)。所謂決策樹(shù)就是一棵樹(shù)，樹(shù)的根節(jié)點(diǎn)是整個(gè) 數(shù)據(jù)集合空間，每個(gè)分節(jié)點(diǎn)是對(duì)一個(gè)單一變量的測(cè)試，該測(cè)試將數(shù)據(jù)集合空間分割成兩