【文章內(nèi)容簡(jiǎn)介】 中國(guó)圖象圖形網(wǎng) 第二 章 數(shù)據(jù)挖掘及相關(guān)技術(shù) 數(shù)據(jù)挖掘的相關(guān)概念 數(shù)據(jù)挖掘的定義和特點(diǎn) 數(shù)據(jù)挖掘 DM(Data Mining)是對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行一定的處理，從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中提取隱含的、事先未知的、但又是潛在有用的信息和知識(shí)的過程 [1]。 確切地講， DM是 KDD 過程中的一個(gè)步驟， 其處理對(duì)象是大量的日常業(yè)務(wù)數(shù)據(jù)， 它主要基于人工只能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等技術(shù)，高度自動(dòng)化地分析原有的海量數(shù)據(jù)，做出歸納的推理，從中采掘出潛在的模式，預(yù)測(cè)未知的行為， 提高信息的利用，改變“人們被數(shù)據(jù)淹沒 ，同時(shí)卻仍感到知識(shí)饑渴”的資源浪費(fèi)的局面。 KDD 是數(shù)據(jù)庫(kù)技術(shù)和機(jī)器學(xué)習(xí)兩個(gè)學(xué)科的交叉學(xué)科 ，由于 KDD 使用的數(shù)據(jù)來自于實(shí)際的數(shù)據(jù)庫(kù)，所要處理的數(shù)據(jù)量可能很大，因此DM中的學(xué)習(xí)算法的效率和可擴(kuò)充性就尤為重要；此外， KDD 所處理的數(shù)據(jù)由于來自于現(xiàn)實(shí)世界，數(shù)據(jù)的完整性、一致性和正確性都很難保證 ，因此數(shù)據(jù)預(yù)處理也是很有必要的。 數(shù)據(jù)挖掘的方法 DM 的技術(shù)基礎(chǔ)包括機(jī)器學(xué)習(xí)、人工智能和統(tǒng)計(jì)學(xué)。人工智能是以自動(dòng)機(jī)為手段，通過模擬人類宏觀外顯的思維行為，從而高效率地解決事實(shí)世界問題的科學(xué)和技術(shù)。下面介紹數(shù)據(jù)挖掘 和知識(shí)發(fā)現(xiàn)的幾種常用方法。 1. 人工神經(jīng)網(wǎng)絡(luò)（ Artificial Neural Networks） 神經(jīng)網(wǎng)絡(luò)方法是模擬人腦神經(jīng)元結(jié)構(gòu)，以 MP 模型和 Hebb 學(xué)習(xí)規(guī)則為基礎(chǔ)。它主要有三種神經(jīng)網(wǎng)絡(luò)模型： （ 1）前饋式網(wǎng)絡(luò)。它以感知機(jī)、反向傳播模型、函數(shù)型網(wǎng)絡(luò)為代表，可用于預(yù)測(cè)、模式識(shí)別等方面。 （ 2）反饋式網(wǎng)絡(luò)。它以 Hopfield 的離散模型和連續(xù)模型為代表，分別用于聯(lián)想記憶和優(yōu)化計(jì)算。 （ 3）自組織網(wǎng)絡(luò)。它以 ART 模型、 Koholon 模型為代表，用于聚類分析等 中國(guó)圖象圖形網(wǎng) 方面。 神經(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. 遺傳算法（ Geic Algorithms） 遺傳算法是模擬生物進(jìn)化過程的算法，由三個(gè)基本算子（或過程）組成： （ 1）選擇 （ selection）。即從一個(gè)舊種群（父代）選出生命力強(qiáng)的個(gè)體，產(chǎn)生新的種群（后代）的過程。 （ 2）交叉（ crossover）。即對(duì)選擇的兩個(gè)不同的個(gè)體（染色體）的部分（基因）進(jìn)行交換，形成新個(gè)體的過程。 （ 3）變異（ mutation）。即對(duì)某些個(gè)體的某些基因進(jìn)行變異（ 0變 1，或 1變 0） ，形成新個(gè)體的過程。 這種遺傳算法可起到產(chǎn)生優(yōu)良后代的作用。這些后代需滿足適應(yīng)值，經(jīng)過若干代的遺傳，將得到滿足要求的后代。遺傳算法已在優(yōu)化計(jì)算和分類機(jī)器學(xué)習(xí)方面發(fā)揮了顯著作用。 3. 決策樹方法（ Decision Trees） 決策樹方法是利用信息論中的互信息（信息增益）尋找數(shù)據(jù)庫(kù)中具有最大信息量的屬性字段，建立決策樹的一個(gè)結(jié)點(diǎn)，再根據(jù)該屬性字段的不同取值建立樹的分支。在每個(gè)分支集中重復(fù)建立樹的下層結(jié)點(diǎn)和分支的過程。國(guó)際上最早的、也是最有影響的決策樹方法是 Quiulan 研究的 ID3 方法 [3]。 決策樹方法在 現(xiàn)有的數(shù)據(jù)挖掘產(chǎn)品中有較為廣泛的應(yīng)用，如 Bussiness Object 公司在它的 OLAP 產(chǎn)品中新增加的一個(gè)數(shù)據(jù)挖掘的模塊 Business Miner，其中就采用了一種稱為 GINI 的決策數(shù)方法。 4. 覆蓋正例、排斥反例方法 該方法是利用覆蓋所有正例、排斥所有反例的思想來尋找規(guī)則。比較典型的有 Michalski 的 AQ11 方法、洪家榮改進(jìn) AQ15 方法，以及洪家榮的 AE5方法。 AQ 系列的核心算法是，在正例集中任選一個(gè)種子，到反例集中逐個(gè)比較，對(duì)字段取值構(gòu)成的選擇子相容則舍去，相斥則保留。按此思想循環(huán)所有正 例種子，將得到正例集的規(guī)則。 AE 系列方法是用擴(kuò)張矩陣來完成的。 5. 粗糙集（ Rough Sets） 它將知識(shí)理解為對(duì)數(shù)據(jù)的劃分，每一被劃分的集合稱為概念，主要思想是利用已知的知識(shí)庫(kù)，將不精確或不確定的知識(shí)用已知的知識(shí)庫(kù)中的知識(shí)來近似刻劃處理。具體做法是在數(shù)據(jù)庫(kù)中，將行元素看成對(duì)象，列元素是屬性（分為條件屬性和決策屬性）。等價(jià)關(guān)系 R定義為不同對(duì)象在某個(gè)（或幾個(gè)）屬性上取值相同，這些滿足等價(jià)關(guān)系的對(duì)象組成的集合稱為該等價(jià)關(guān)系 R的等價(jià)類。條件屬性上的 中國(guó)圖象圖形網(wǎng) 等價(jià)類 E與決策屬性上的等價(jià)類 Y 之間有三種情況：①下近似： Y包含 E；②上近似： Y 和 E的交非空；③無關(guān)： Y 和 E的交為空。對(duì)下近似建立確定性規(guī)則，對(duì)上近似建立不確定性規(guī)則（含可信度），對(duì)無關(guān)情況不存在規(guī)則。 6. 數(shù)據(jù)可視化 (DataVisualization) 對(duì)大批數(shù)據(jù)進(jìn)行展現(xiàn)也是數(shù)據(jù)挖掘的重要方面。就數(shù)據(jù)可視化系統(tǒng)本身而言，由于數(shù)據(jù)量很大，很容易使分析人員面對(duì)數(shù)據(jù)不知所措，可視化工具可以通過適當(dāng)?shù)膱D形來表示數(shù)據(jù)，并支持多維數(shù)據(jù)的可視化，為數(shù)據(jù)分析人員提供很好的幫助。有些工具甚至提供動(dòng)畫功能，使用戶可以“跨越”數(shù)據(jù)，觀看到數(shù)據(jù)的不同層次。該方法對(duì)揭示數(shù)據(jù)的狀況、內(nèi)在本質(zhì) 及規(guī)律性起到了很強(qiáng)的作用。 7. 人工免疫系統(tǒng)模型（ Artificial Immune System） 目前 ,AIS 已發(fā)展成為計(jì)算智能研究的一個(gè)嶄新的分支，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、自動(dòng)控制、故障診斷等諸多領(lǐng)域 ,顯示出 AIS 強(qiáng)大的信息處理和問題求解能力以及廣闊的研究前景。目前 ,由于認(rèn)識(shí)到 AIS 在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等領(lǐng)域潛在的應(yīng)用前景 ,AIS 的研究得到了許多大學(xué)、研究機(jī)構(gòu)和工業(yè)界的重視。英國(guó)Kent 大學(xué)的 Timmis[7]對(duì)基于 AIS 的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)進(jìn)行了系統(tǒng)性的理論研究 ,并開展了基于 AIS 的大規(guī)模數(shù)據(jù)挖 掘應(yīng)用研究。作為計(jì)算智能的一個(gè)嶄新分支 ,AIS 已成為許多國(guó)際期刊的重要議題。 在數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)中應(yīng)用的人工智能技術(shù)還有鄰近搜索方法、規(guī)則推理、模糊邏輯、公式發(fā)現(xiàn)等等。 數(shù)據(jù)挖掘的功能 數(shù)據(jù)挖掘的功能用于指定數(shù)據(jù)挖掘任務(wù)中要找的模式類型。數(shù)據(jù)挖掘的任務(wù)一般可分為兩類：描述和預(yù)測(cè)。描述性挖掘任務(wù)刻劃數(shù)據(jù)的一般特性。預(yù)測(cè)性挖掘任務(wù)是在當(dāng)前數(shù)據(jù)上進(jìn)行推斷，用以預(yù)測(cè)。 DM 所能發(fā)現(xiàn)的模式類型包括以下四種（根據(jù) IBM 的劃分方法）：關(guān)聯(lián)分析（ Associations）；序列模式分析(Sequential Patterns)；分類分析 (Classifiers)；聚類分析 (Clustering)。 1. 關(guān)聯(lián)分析（ Associations） 顧名思義，關(guān)聯(lián)分析的目的就是為了挖掘出隱藏在數(shù)據(jù)間的相互關(guān)系。關(guān)聯(lián)分析就是給定一組 Item 和一個(gè)記錄集合，通過分析記錄集合，推導(dǎo)出 Item 間的相關(guān)性。該模式側(cè)重于確定數(shù)據(jù)中不同領(lǐng)域之間的聯(lián)系，找出滿足給定支持度(support)和置信度（ confidence）閾值的多個(gè)領(lǐng)域之間的依賴關(guān)系。挖掘關(guān)聯(lián)規(guī)則是指在數(shù)據(jù)庫(kù)組中挖掘出具有這種形式的規(guī)則：由于某些事件的發(fā)生而引起另外一些 事件的發(fā)生。 例如，同時(shí)包含 A,B,C,D,E 的 Item 占總的 Item 的百分比稱為規(guī)則“由 A， B， C推出 D,E”的支持度?！?72%包含 Item A， B的記錄同時(shí)、 中國(guó)圖象圖形網(wǎng) 也包含 Item D 和 E。”其中百分比 72 稱為規(guī)則“包含 Item A， B 和 C 的記錄同時(shí)也包含 Item D 和 E”的置信度，而 A， B， C則被稱為 D， E的對(duì)立面。 2. 序列模式分析 (Sequential Patterns) 序列模式分析和關(guān)聯(lián)分析法相似，其目的也是為了挖掘出數(shù)據(jù)之間的聯(lián)系，但序列模式分析的側(cè)重點(diǎn)在于分析數(shù)據(jù)間的前后（因果）關(guān)系。 序列模式分析 在關(guān)聯(lián)分析中增加了時(shí)間屬性。序列模式分析也可稱為時(shí)序關(guān)聯(lián)分析。如第一次購(gòu)買電腦的顧客中 95％的人同時(shí)購(gòu)買電腦應(yīng)用軟件，此為簡(jiǎn)單關(guān)聯(lián)，也就是一般的關(guān)聯(lián)分析。股票“深發(fā)展”一上漲，則第二天金融股票上漲的可能性為 85％，這就是時(shí)序關(guān)聯(lián)。由于我們并不知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)是否存在精確的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此生成的規(guī)則帶有置信度，置信度級(jí)別度量了規(guī)則的強(qiáng)度。 3. 分類分析 (Classifiers) 假定有一組記錄集合和一組標(biāo)記（ TAG），所謂標(biāo)記是指一組具有不同特征的類別。分類分析時(shí)首先為每一個(gè)記錄賦 予一個(gè)標(biāo)記，即按標(biāo)記分類記錄，然后檢查這些標(biāo)定的記錄，描述出這些記錄的特征， 然后再用這些分類的描述或模型來對(duì)未知的新的數(shù)據(jù)進(jìn)行分類 。這種描述可能是顯式的，例如一組規(guī)則定義；或者是隱式的，例如一個(gè)數(shù)學(xué)模型或公式。利用它可以分類新記錄，實(shí)際上它就是一種模式。目前，已有很多種分類分析模型得到應(yīng)用，其中的幾種典型模型是線性回歸模型、決策樹模型、基于規(guī)則模型和神經(jīng)網(wǎng)絡(luò)模型，貝葉斯信念網(wǎng)絡(luò)模型。 舉一個(gè)簡(jiǎn)單的例子，信用卡公司的數(shù)據(jù)庫(kù)中保存著各持卡人的記錄，并根據(jù)信譽(yù)程度（標(biāo)記），將持卡人分作三類：優(yōu)，良，中，一般，差。 這一過成程實(shí)際就是將持卡人記錄標(biāo)定為五類。分類分析法檢查這些記錄，然后給出一個(gè)對(duì)信譽(yù)等級(jí)的顯式描述：“信譽(yù)良的用戶是指那些收入在 25000 以上，年齡在 45 到55歲之間，居住在 XYZ地區(qū)附近的人士”。 4. 聚類分析 (Clustering) 聚類 又稱為無指導(dǎo)的分類 (Unsupervised Classification)。 與分類分析法不同，聚類分析法的輸入集是一組未標(biāo)定的記錄，也就是說此時(shí)輸入的記錄還沒有進(jìn)行任何分類。其目的是根據(jù)一定的規(guī)則，合理地劃分記錄集合，并用顯式或隱式的方法描述不同的類別。而所依據(jù)的這 些規(guī)則是由聚類分析工具定義的。由于聚類分析可以采用不同的算法，所以對(duì)于相同的記錄集合可能有不同的劃分?？梢钥闯觯S多在分類分析法中適用的算法同樣適用于聚類分析。 聚類方法包括統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法和面向數(shù)據(jù)庫(kù)的方法。 上述的四種分法摘自 IBM《 Data Mining 版本 》白皮書。但基于同樣的基本技術(shù)， DATAMATION 白皮書將 DM 的方法分為以下四種： 中國(guó)圖象圖形網(wǎng) （ 1） 預(yù)測(cè)模型（ Predictive Modeling）。在 DM中是歸納推理。可以有多種算法實(shí)現(xiàn)，包括人工神經(jīng)網(wǎng)絡(luò)，規(guī)則推理等。 （ 2） 數(shù)據(jù)庫(kù)分段 （ Database Segmentation）。將數(shù)據(jù)庫(kù)中的數(shù)據(jù)自動(dòng)地分類，包括分類分析和聚類分析。 （ 3） 聯(lián)系分析（ Link Analysis）。確定數(shù)據(jù)間的相互關(guān)系，包括關(guān)聯(lián)分析和序列分析。 （ 4） 偏差檢測(cè)（ Deviation Segmentation）。檢測(cè)并解釋數(shù)據(jù)分類的偏差 為什么有些記錄不能歸入段（ Segmentation）中。 與 IBM 白皮書對(duì) DM 方法的分類相比， DATAMATION 白皮書的分類層次更高，例如數(shù)據(jù)庫(kù)分段和聯(lián)系分析涵蓋了分類分析法、聚類分析法、關(guān)聯(lián)分析和序列分析法，而預(yù)測(cè)模型在 IBM 白皮書 中所列的四種方法中都包含了，只不過在DATAMATION 白皮書中被特別提出來了。兩種分類法最大的差異在于偏差檢測(cè)，這是 IBM 白皮書中沒有列出來的。 數(shù)據(jù)挖掘結(jié)構(gòu)和步驟 數(shù)據(jù)挖掘系統(tǒng)的結(jié)構(gòu) 如上所述， DM 的核心技術(shù)是人工智能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)等，但一個(gè) DM 系統(tǒng)不是多項(xiàng)技術(shù)的簡(jiǎn)單組合，而是一個(gè)完整的整體。它還需要其他輔助技術(shù)的支持，才能完成數(shù)據(jù)采集、預(yù)處理、數(shù)據(jù)分析、結(jié)果表述這一系列任務(wù)，最后將分析結(jié)果呈現(xiàn)在用戶面前。根據(jù)功能，整個(gè) DM 系統(tǒng)可以大致劃分為三級(jí)結(jié)構(gòu) ,如下圖 數(shù)據(jù)倉(cāng)庫(kù) 數(shù)據(jù)庫(kù)文件系統(tǒng)其他數(shù)據(jù)源OD BC 或其他專用數(shù)據(jù)庫(kù)接口知識(shí)庫(kù)用戶界面 結(jié)果輸出關(guān)聯(lián)規(guī)則分析序列模式分析分類分析聚類分析 中國(guó)圖象圖形網(wǎng) 圖 DM系統(tǒng)的三層結(jié)構(gòu) 數(shù)據(jù)挖掘系統(tǒng)的步驟 1． 準(zhǔn)備（ Preparation） 本階段主要完成數(shù)據(jù)預(yù)處理，包括數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)選擇和數(shù)據(jù)變換。 2． 挖掘（ Mining） 數(shù)據(jù)挖掘器（ Data Mining Processor）綜合利用前面提到的四種數(shù)據(jù)挖掘方法分析數(shù)據(jù)庫(kù)中的數(shù)據(jù)。 3． 表述（ Presentation） 數(shù)據(jù)挖掘?qū)@取的信息以便于用戶理解和觀察的方式反映給用戶，這時(shí)可以利用可視化工具。由于用戶要求的不同， DM 分析的數(shù)據(jù)的范圍會(huì)有所不同，例如分析一年內(nèi)或三個(gè)月內(nèi)的銷售情況，再例如分析東 部地區(qū)或西部地區(qū)的銷售情況，這樣的 DM 系統(tǒng)會(huì)得出不同的結(jié)論。這些基于不同數(shù)據(jù)集合的分析結(jié)果除了通過可視化工具提供給用戶外還可以存儲(chǔ)在知識(shí)庫(kù)中，供日后進(jìn)一步分析和比較。 4． 評(píng)價(jià)（ Assess） 如果分析人員對(duì)分析結(jié)果不滿意，可以遞歸地執(zhí)行上述三個(gè)過程，直到滿意為止。 分類算法的簡(jiǎn)介和分析 數(shù)據(jù)挖掘中的分類方法是根據(jù)給出數(shù)據(jù)集的特點(diǎn)構(gòu)造分類器，利用分類器對(duì)已知類別的樣本進(jìn)行分類的一種技術(shù) [35]。按各種分類算法的技術(shù)特點(diǎn)，可將分類算法分為決策樹方法、基于統(tǒng)計(jì)概率、基于關(guān)聯(lián)規(guī)則、基于數(shù)據(jù)庫(kù)技術(shù)、基于支持向量 機(jī)等幾類來敘述。 決策樹分類 決策樹學(xué)習(xí)算法包