決策支持系統(tǒng)及其開(kāi)發(fā)主講教師：唐晶磊E-mail:Tel:87091337(O)2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘5.6數(shù)據(jù)挖掘的決策支持及應(yīng)用2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3DW的興起（1）80年在美國(guó)召開(kāi)了第一屆國(guó)際機(jī)器學(xué)習(xí)研討會(huì)；（2）89年8月,美國(guó)底特律市召開(kāi)的第一屆KDD國(guó)際學(xué)術(shù)會(huì)議；（3）95年,加拿大召開(kāi)了第一屆KDD和DM國(guó)際學(xué)術(shù)會(huì)議；（4）我國(guó)于87年召開(kāi)了第一屆全國(guó)機(jī)器學(xué)習(xí)研討會(huì)。

5.5知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.1知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概念知識(shí)發(fā)現(xiàn)（Knowledgediscoveryindatabase）：從數(shù)據(jù)中發(fā)現(xiàn)有用知識(shí)的整個(gè)過(guò)程(KDD)。KDD過(guò)程定義:從數(shù)據(jù)集中識(shí)別出有效的、新穎的、潛在有用的，以及最終可理解的模式的高級(jí)處理過(guò)程。

“模式”即是“知識(shí)”的雛形，需經(jīng)過(guò)驗(yàn)證、完善(模式評(píng)價(jià))后形成知識(shí)。KDD過(guò)程概括：數(shù)據(jù)準(zhǔn)備(datapreparation)、數(shù)據(jù)挖掘(datamining)及結(jié)果的解釋和評(píng)估(interpretation&evaluation)。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.1知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概念問(wèn)題：所有企業(yè)都面臨企業(yè)數(shù)據(jù)量巨大，而其中真正有價(jià)值的信息卻很少。解決方法：對(duì)大量的數(shù)據(jù)進(jìn)行深層分析，獲得有利于商業(yè)運(yùn)作、提高競(jìng)爭(zhēng)力的信息。數(shù)據(jù)挖掘（DM）：KDD過(guò)程中的一個(gè)特定步驟，它用專門算法從數(shù)據(jù)中抽取模式（patterns）。數(shù)據(jù)挖掘是一門交叉學(xué)科，涉及數(shù)據(jù)庫(kù)技術(shù)、人工智能技術(shù)、數(shù)理統(tǒng)計(jì)、可視化技術(shù)、并行計(jì)算等方面。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.1知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概念（1）DM（技術(shù)角度）：從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。即從數(shù)據(jù)源發(fā)現(xiàn)用戶感興趣的知識(shí)，知識(shí)要可接受、可以理解和運(yùn)用；2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.1知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概念（2）（DM）商業(yè)角度：是一種新的、商業(yè)信息處理技術(shù)。對(duì)商業(yè)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。數(shù)據(jù)挖掘是一種深層次的數(shù)據(jù)分析方法。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.1知識(shí)發(fā)現(xiàn)與數(shù)據(jù)挖掘概念（3）(DM)企業(yè)角度：按企業(yè)既定業(yè)務(wù)目標(biāo)，對(duì)大量的企業(yè)數(shù)據(jù)進(jìn)行探索和分析，揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性，并進(jìn)一步將其模型化的先進(jìn)有效方法。

2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3數(shù)據(jù)源數(shù)據(jù)數(shù)據(jù)集成目標(biāo)數(shù)據(jù)預(yù)處理數(shù)據(jù)轉(zhuǎn)換數(shù)據(jù)模式知識(shí)數(shù)據(jù)選擇預(yù)處理數(shù)據(jù)挖掘轉(zhuǎn)換結(jié)果表達(dá)和解釋KDD過(guò)程數(shù)據(jù)準(zhǔn)備數(shù)據(jù)挖掘結(jié)果解釋和評(píng)估2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3數(shù)據(jù)準(zhǔn)備：數(shù)據(jù)選擇(dataselection)、數(shù)據(jù)預(yù)處理(datapreprocessing)和數(shù)據(jù)轉(zhuǎn)換(datatransformation)。數(shù)據(jù)選擇：確定操作對(duì)象，即目標(biāo)數(shù)據(jù)(targetdata)，是根據(jù)用戶的需要，從原始DB中選取的一組數(shù)據(jù)。數(shù)據(jù)預(yù)處理：消除噪聲、處理缺值數(shù)據(jù)、消除重復(fù)記錄等。數(shù)據(jù)轉(zhuǎn)換：完成數(shù)據(jù)類型轉(zhuǎn)換，進(jìn)行屬性約簡(jiǎn)（從初始屬性中找出真正有用的屬性，刪除無(wú)用屬性，以減少數(shù)據(jù)挖掘時(shí)要考慮的屬性個(gè)數(shù)）。數(shù)據(jù)準(zhǔn)備2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3數(shù)據(jù)挖掘數(shù)據(jù)挖掘（1）首先確定挖掘的任務(wù)或目的；（2）確定使用何種挖掘算法。選擇挖掘算法需考慮2個(gè)因素：不同數(shù)據(jù)具有不同特點(diǎn)，需要用與之相關(guān)的算法來(lái)挖掘；考慮用戶或?qū)嶋H運(yùn)行系統(tǒng)的要求。如用戶可能希望獲取描述性的、容易理解的知識(shí)，或者希望獲取預(yù)測(cè)準(zhǔn)確度更可能高預(yù)測(cè)型知識(shí)。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3結(jié)果的解釋和評(píng)估結(jié)果的解釋和評(píng)估（模式評(píng)價(jià)）（1）經(jīng)過(guò)評(píng)估，剔除冗余或無(wú)關(guān)的模式；（2）不滿足用戶要求的模式，需回退到KDD過(guò)程的前面階段。（3）KDD是面向用戶的，一般需對(duì)發(fā)現(xiàn)的模式進(jìn)行可視化處理，或把結(jié)果轉(zhuǎn)換為用戶易懂的表示形式。DM質(zhì)量好壞的2個(gè)影響因素：（1）所采用的DM技術(shù)的有效性；（2）用于挖掘的數(shù)據(jù)的質(zhì)量和數(shù)量（數(shù)據(jù)量的大小）。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3數(shù)據(jù)挖掘任務(wù)DM任務(wù)有六項(xiàng)：（1）關(guān)聯(lián)分析若兩個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的取值重復(fù)出現(xiàn)，且概率很高時(shí)，它就存在某種關(guān)聯(lián)，則可建立起這些數(shù)據(jù)項(xiàng)的關(guān)聯(lián)規(guī)則。（2）時(shí)序模式通過(guò)時(shí)間序列，搜索出重復(fù)發(fā)生概率較高的模式。（3）聚類（通過(guò)聚類建立宏觀概念）有統(tǒng)計(jì)分析方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法等。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3數(shù)據(jù)挖掘任務(wù)（4）分類：以聚類為基礎(chǔ)，對(duì)已確定的類找出該類別的概念描述。它代表此類數(shù)據(jù)的整體信息（內(nèi)涵描述）。內(nèi)涵描述分為特征描述和辨別性描述。判別分類方法的3個(gè)標(biāo)準(zhǔn)：預(yù)測(cè)準(zhǔn)確度、計(jì)算復(fù)雜度、模式的簡(jiǎn)潔度。（5）偏差檢測(cè)：尋找觀察結(jié)果與DB中參照數(shù)據(jù)之間的差別。（6）預(yù)測(cè)：利用歷史數(shù)據(jù)找出變化規(guī)律，建立模型，并用此模型來(lái)預(yù)測(cè)未來(lái)數(shù)據(jù)的種類、特征等。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3屬性約簡(jiǎn)屬性約簡(jiǎn)常用于分類問(wèn)題原則：保持?jǐn)?shù)據(jù)庫(kù)中分類關(guān)系不變。一般采用粗糙集(roughset)方法，也可采用信息論方法。在DB的分類問(wèn)題中，屬性分為條件屬性(C)和決策屬性(D)。條件屬性分為可省略屬性和不可省略屬性。屬性約簡(jiǎn)是在條件屬性中，刪除不影響對(duì)決策屬性進(jìn)行分類的多余的條件屬性。不可省略屬性，實(shí)質(zhì)上是對(duì)決策屬性進(jìn)行分類的核心屬性。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3補(bǔ)充：數(shù)據(jù)挖掘與傳統(tǒng)分析方法的區(qū)別傳統(tǒng)的數(shù)據(jù)分析方法：查詢、報(bào)表和聯(lián)機(jī)分析等。采用完全不同的工具，基于的技術(shù)差別也很大。（1）查詢和報(bào)表，告訴決策者數(shù)據(jù)庫(kù)中都有什么。（2）OLAP會(huì)進(jìn)一步告訴決策者，下一步會(huì)怎么樣，（假設(shè)）如果我采用這樣的措施，又會(huì)怎么樣。OLAP通過(guò)建立一系列的假設(shè)，來(lái)證實(shí)或推翻這些假設(shè)，以得到合理的結(jié)論。因此，OLAP本質(zhì)上是演繹推理過(guò)程。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3補(bǔ)充：數(shù)據(jù)挖掘與聯(lián)機(jī)分析處理的區(qū)別DM在沒(méi)有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識(shí)。DM所得到的信息是先前未知、有效的和可實(shí)用的。數(shù)據(jù)挖掘不用于驗(yàn)證某個(gè)假定的模式，而是在數(shù)據(jù)庫(kù)中自己尋找模型。本質(zhì)是一個(gè)歸納的過(guò)程。DM和OLAP具有一定的互補(bǔ)性。在利用DM出來(lái)的結(jié)論采取行動(dòng)之前，利用OLAP驗(yàn)證一下，如果采取這樣的行動(dòng)，將會(huì)給公司帶來(lái)什么樣的影響。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.2數(shù)據(jù)挖掘方法和技術(shù)DM方法由人工智能、機(jī)器學(xué)習(xí)的方法發(fā)展而來(lái)。結(jié)合傳統(tǒng)的統(tǒng)計(jì)分析方法、模糊數(shù)學(xué)方法以及計(jì)算科學(xué)可視化技術(shù)，以數(shù)據(jù)庫(kù)為研究對(duì)象，形成了數(shù)據(jù)挖掘方法和技術(shù)。數(shù)據(jù)挖掘方法和技術(shù)可以分為六大類。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.2數(shù)據(jù)挖掘方法和技術(shù)（一）歸納學(xué)習(xí)方法按采用的技術(shù)可分為信息論方法（決策樹(shù)方法）和集合論方法。

1、信息論方法（決策樹(shù)方法）

利用信息論的原理建立決策樹(shù)或者決策規(guī)則樹(shù)。

較有特色的方法有：

（1）ID3等方法（決策樹(shù)方法）

（2）IBLE（決策規(guī)則樹(shù)）方法。

2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-32、集合論方法

（1）粗糙集（RoughSet）方法對(duì)數(shù)據(jù)庫(kù)中的條件屬性集與決策屬性集建立上下近似關(guān)系，對(duì)下近似集合建立確定性規(guī)則，對(duì)上近似集合建立不確定性規(guī)則（含可信度）。（2）關(guān)聯(lián)規(guī)則挖掘在交易事務(wù)數(shù)據(jù)庫(kù)中，挖掘出不同商品集的關(guān)聯(lián)關(guān)系，即發(fā)現(xiàn)哪些商品頻繁地被顧客同時(shí)購(gòu)買。（3）覆蓋正例排斥反例方法它是利用覆蓋所有正例，排斥所有反例的思想來(lái)尋找規(guī)則。較典型的有AQ11方法、AQ15方法及AE5方法。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3（二）仿生物技術(shù)典型的仿生物技術(shù)方法是神經(jīng)網(wǎng)絡(luò)方法和遺傳算法。

1、神經(jīng)網(wǎng)絡(luò)方法：包括：前饋式網(wǎng)絡(luò)、反饋式網(wǎng)絡(luò)、自組織網(wǎng)絡(luò)等多個(gè)神經(jīng)網(wǎng)絡(luò)方法。2、遺傳算法：模擬生物進(jìn)化過(guò)程的算法。它由三個(gè)基本算子組成：繁殖（選擇）、交叉（重組）、變異（突變）遺傳算法起到產(chǎn)生優(yōu)良后代的作用，經(jīng)過(guò)若干代的遺傳，將得到滿足要求的后代（問(wèn)題的解）。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3（三）公式發(fā)現(xiàn)

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

1．物理定律發(fā)現(xiàn)系統(tǒng)BACON

BACON發(fā)現(xiàn)系統(tǒng)完成了物理學(xué)中大量定律的重新發(fā)現(xiàn)。

2．經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng)FDD尋找由數(shù)據(jù)項(xiàng)的初等函數(shù)或復(fù)合函數(shù)組合成的經(jīng)驗(yàn)公式。

2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3（四）統(tǒng)計(jì)分析方法

利用統(tǒng)計(jì)學(xué)原理對(duì)總體中的樣本數(shù)據(jù)進(jìn)行分析，得出描述和推斷該總體信息和知識(shí)的方法。（五）模糊數(shù)學(xué)方法

利用模糊集合理論進(jìn)行數(shù)據(jù)挖掘，如模糊聚類、模糊分類等。（六）可視化技術(shù)

利用可視化技術(shù)分析數(shù)據(jù)庫(kù)，找到潛在的有用信息。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.3數(shù)據(jù)挖掘的知識(shí)表示（一）DM獲取知識(shí)表示形式主要有六種：

規(guī)則、決策樹(shù)、濃縮數(shù)據(jù)、網(wǎng)絡(luò)權(quán)值、公式和案例。1、規(guī)則規(guī)則知識(shí)由前提條件和結(jié)論兩部分組成

前提條件由字段項(xiàng)（屬性）的取值的合取（與

）和析?。ɑ?/p>

）組合而成。

結(jié)論為決策字段項(xiàng)（屬性）的取值或者類別組成。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.5.3數(shù)據(jù)挖掘的知識(shí)表示（一）2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-32、決策樹(shù)例如：上例的人群數(shù)據(jù)庫(kù)，按ID3方法得到的決策樹(shù)如下：數(shù)據(jù)挖掘的知識(shí)表示（二）2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-33、知識(shí)基（濃縮數(shù)據(jù)）例如上例的人群數(shù)據(jù)庫(kù)，通過(guò)計(jì)算可得出身高是不重要的字段，刪除它后，再合并相同數(shù)據(jù)元組，得到濃縮數(shù)據(jù)如下表：數(shù)據(jù)挖掘的知識(shí)表示（三）2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-34、網(wǎng)絡(luò)權(quán)值神經(jīng)網(wǎng)絡(luò)方法經(jīng)過(guò)對(duì)訓(xùn)練樣本的學(xué)習(xí)后，所得到的知識(shí)是網(wǎng)絡(luò)連接權(quán)值和結(jié)點(diǎn)的閾值。數(shù)據(jù)挖掘的知識(shí)表示（四）Zy2x1x2

1y1

T1T2

w12w21

w11w22

2

,φ=0.5

2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35、公式例如，太陽(yáng)系行星運(yùn)動(dòng)數(shù)據(jù)中包含行星運(yùn)動(dòng)周期（旋轉(zhuǎn)一周所需時(shí)間，天），以及它與太陽(yáng)的距離（圍繞太陽(yáng)旋轉(zhuǎn)的橢圓軌道的長(zhǎng)半軸，百萬(wàn)公里），數(shù)據(jù)如下表：通過(guò)物理定律發(fā)現(xiàn)系統(tǒng)BACON和經(jīng)驗(yàn)公式發(fā)現(xiàn)系統(tǒng)FDD，都可得到開(kāi)普勒第三定律：d3/p2=25數(shù)據(jù)挖掘的知識(shí)表示（五）2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.6數(shù)據(jù)挖掘的決策支持及應(yīng)用

5.6.1決策樹(shù)及其應(yīng)用1、決策樹(shù)概念：用樣本的屬性作為結(jié)點(diǎn)，用屬性的取值作為分支的樹(shù)結(jié)構(gòu)。利用信息論原理對(duì)大量樣本的屬性進(jìn)行分析和歸納。決策樹(shù)的根結(jié)點(diǎn)是所有樣本中信息量最大的屬性。

中間結(jié)點(diǎn)是以該結(jié)點(diǎn)為根的子樹(shù)，所包含的樣本子集中信息量最大的屬性。葉結(jié)點(diǎn)是樣本的類別值。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-35.6數(shù)據(jù)挖掘的決策支持及應(yīng)用決策樹(shù)用于對(duì)新樣本的分類：通過(guò)決策樹(shù)對(duì)新樣本屬性值的測(cè)試，從樹(shù)的根結(jié)點(diǎn)開(kāi)始，按照樣本屬性的取值，逐漸沿著決策樹(shù)向下，直到樹(shù)的葉結(jié)點(diǎn)，該葉結(jié)點(diǎn)表示的類別就是新樣本的類別。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3DM的決策樹(shù)方法的原理是信息論。信息論是C.E.Shannon為解決信息傳遞（通信）過(guò)程問(wèn)題而建立的理論，也稱為統(tǒng)計(jì)通信理論。傳遞信息的系統(tǒng)是由發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。信息論把通信過(guò)程看做在隨機(jī)干擾的環(huán)境中傳遞信息的過(guò)程。在這個(gè)通信模型中，信息源和干擾（噪聲）都被理解為某種隨機(jī)過(guò)程或隨機(jī)序列。補(bǔ)充內(nèi)容2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3在進(jìn)行實(shí)際通信之前，收信者（信宿）不可能確切了解信源究竟會(huì)發(fā)出什么樣的具體信息，不可能判斷信源會(huì)處于什么樣的狀態(tài)。此情形稱為信宿對(duì)于信源狀態(tài)具有不確定性。這種不確定性存在通信之前的，又叫做先驗(yàn)不確定性。通信之后，信宿收到了信源發(fā)來(lái)的信息，這種先驗(yàn)不確定性才會(huì)被消除或者被減少。如果干擾很小，信源發(fā)出的信息能夠被信宿全部收到。此種情況下，信宿的先驗(yàn)不確定性就會(huì)被完全消除。補(bǔ)充內(nèi)容2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3一般情況下，干擾總會(huì)對(duì)信源發(fā)出的信息造成某種破壞，使信宿收到的信息不完全。因此，先驗(yàn)不確定性不能全部被消除，只能部分地消除。通信結(jié)束之后，信宿還仍然具有一定程度的不確定性。這就是后驗(yàn)不確定性。顯然，后驗(yàn)不確定性總要小于先驗(yàn)不確定性，不可能大于先驗(yàn)不確定性。補(bǔ)充內(nèi)容2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3如果后驗(yàn)不確定性的大小正好等于先驗(yàn)不確定性的大小，表示信宿根本沒(méi)有收到信息。如果后驗(yàn)不確定性的大小等于零，表示信宿收到了全部信息。因此，信息是用來(lái)消除（隨機(jī)）不確定性的度量。信息量的大小，由所消除的不確定性的大小來(lái)計(jì)量。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-32、ID3算法當(dāng)前國(guó)際上最有影響的示例學(xué)習(xí)方法首推ID3。ID3引進(jìn)了信息論中的互信息(信息增益informationgain），作為特征(屬性)判別能力的度量，且將建樹(shù)的方法嵌在一個(gè)迭代的外殼之中。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3ID3基本思想每個(gè)實(shí)體用多個(gè)特征來(lái)描述，每個(gè)特征限于在一個(gè)離散集中取互斥的值。例如，設(shè)實(shí)體是某天早晨，分類任務(wù)是關(guān)于氣候的類型，有4各特征（屬性）為:

天氣取值為：晴，多云，雨

氣溫取值為：冷，適中，熱

濕度取值為：高，正常

風(fēng)取值為：有風(fēng)，無(wú)風(fēng)某天早晨（實(shí)體）氣候描述為:

天氣：多云

氣溫：冷

濕度：正常

風(fēng)：無(wú)風(fēng)2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3判斷此實(shí)體屬于哪類氣候類別?假定僅有兩個(gè)類別，分別為P，N。兩個(gè)類別的歸納任務(wù)中，P類和N類的實(shí)體分別稱為概念的正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。下表給出一個(gè)訓(xùn)練集，由ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹(shù)。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3NO.屬性類別天氣氣溫濕度風(fēng)1晴熱高無(wú)風(fēng)N2晴熱高有風(fēng)N3多云熱高無(wú)風(fēng)P4雨適中高無(wú)風(fēng)P5雨冷正常無(wú)風(fēng)P6雨冷正常有風(fēng)N7多云冷正常有風(fēng)P8晴適中高無(wú)風(fēng)N9晴冷正常無(wú)風(fēng)P10雨適中正常無(wú)風(fēng)P11晴適中正常有風(fēng)P12多云適中高有風(fēng)P13多云熱正常無(wú)風(fēng)P14雨適中高有風(fēng)N第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3天氣濕度風(fēng)晴雨多云高正常有風(fēng)無(wú)風(fēng)PNNPPID3決策樹(shù)2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3決策樹(shù)葉子結(jié)點(diǎn)為類別名，即P或者N。其它結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對(duì)應(yīng)一分枝。若要對(duì)一個(gè)實(shí)體分類，從樹(shù)根開(kāi)始進(jìn)行測(cè)試。按特征的取值分枝向下進(jìn)入下層結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)進(jìn)行測(cè)試，過(guò)程一直進(jìn)行到葉結(jié)點(diǎn)，實(shí)體被判為屬于該葉結(jié)點(diǎn)所標(biāo)記的類別。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3ID3算法（一）主算法1、從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集（稱為"窗口"）；2、用“建樹(shù)算法”對(duì)當(dāng)前窗口形成一棵決策樹(shù)；3、對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹(shù)進(jìn)行類別判定，找出錯(cuò)判的例子；4、若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn)2，否則結(jié)束。主算法流程用下圖表示。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3訓(xùn)練集PE、NE取子集建窗口窗口PE`、NE`生成決策樹(shù)測(cè)試PE、NE擴(kuò)展窗口PE`=PE`+PE``NE`=NE`+NE``此決策樹(shù)為最后結(jié)果存在錯(cuò)判的PE``，NE``嗎是否ID3主算法流程第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3PE、NE分別為正例集和反例集，共同組成訓(xùn)練集。PE’，PE’’和NE’，NE’’分別表示正例集和反例集的子集。主算法中每迭代循環(huán)一次，生成的決策樹(shù)將會(huì)不相同。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3（二）建樹(shù)算法

1、計(jì)算當(dāng)前例子集合各特征的互信息；

2、選擇互信息最大的特征Ak，作為樹(shù)（子樹(shù)）的根結(jié)點(diǎn)；

3、把在Ak處取值相同的例子歸于同一子集（分支），Ak取幾個(gè)值就得幾個(gè)子集（分支）；

4、對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹(shù)算法；

5、若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-33、ID3方法應(yīng)用實(shí)例

氣候分類問(wèn)題具體計(jì)算有：⒈信息熵的計(jì)算信息熵：類別ui出現(xiàn)的概率：類別－正例or反例|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3對(duì)9個(gè)正例和5個(gè)反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log2（14/9）+（5/14）log2（14/5）=0.94b2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3

條件熵：⒉計(jì)算條件熵屬性A1取值vj時(shí)，類別ui的條件概率：2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3A1=天氣取值v1=晴，v2=多云，v3=雨在A1處取值晴的例子5個(gè)，取值多云的例子4個(gè)，取值雨的例子5個(gè)，故：

P（v1）=5/14P（v2）=4/14P（v3）=5/14取值為晴的5個(gè)例子中有2個(gè)正例、3個(gè)反例，故：

P（u1/v1）=2/5，P（u2/v1）=3/5同理有：P（u1/v2）=4/4，P（u2/v2）=0

P（u1/v3）=2/5，P（u2/v3）=3/5條件熵為：H(U/V)=(5/14)((2/5)log(5/2)+(3/5)log(5/3))+(4/14)((4/4)log(4/4)+0)+(5/14)((2/5)log(5/2)+(3/5)log(5/3))=0.694bit2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3⒊計(jì)算互信息

對(duì)A1=天氣處有：

I（天氣）=信息熵－條件熵＝H（U）-H（U|V）=0.94-0.694=0.246bit

類似可得：

I（氣溫）=0.029bitI（濕度）=0.151bitI（風(fēng)）=0.048bit2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3⒋建決策樹(shù)的樹(shù)根和分枝

ID3算法將選擇互信息最大的特征天氣作為樹(shù)根，在14個(gè)例子中,對(duì)天氣的3個(gè)取值進(jìn)行分枝，3個(gè)分枝對(duì)應(yīng)3個(gè)子集，分別是:

F1={1，2，8，9，11}，F(xiàn)2={3，7，12，13}，F(xiàn)3={4，5，6，10，14}

其中F2中的例子全屬于P類，因此對(duì)應(yīng)分枝標(biāo)記為P，其余兩個(gè)子集既有正例又有反例，將遞歸調(diào)用建樹(shù)算法。2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3對(duì)F1和F3子集分別利用ID3算法，在每個(gè)子集中對(duì)各特征（仍為四個(gè)特征）求互信息。（1）F1中的天氣全取晴值，則信息熵H（U）=條件熵H（U|V），有互信息I（U|V）=0。在余下三個(gè)特征中求出濕度互信息最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。濕度取高的例子全為N類，該分枝標(biāo)記N。取值正常的例子全為P類，該分枝標(biāo)記P。⒌遞歸建樹(shù)2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-3（2）在F3中，對(duì)四個(gè)特征求互信息。得到風(fēng)特征互信息最大，則以它為該分枝根結(jié)點(diǎn)。再向下分枝，取有風(fēng)時(shí)全為N類，該分枝標(biāo)記N。取無(wú)風(fēng)時(shí)全為P類，該分枝標(biāo)記P。

這樣就得到圖的決策樹(shù)。⒌遞歸建樹(shù)2024/11/26第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持-34、C4.5算法ID3算法在DM中占有非常重要的地位。缺點(diǎn)：ID3算法不能夠處理連續(xù)屬性、計(jì)算信息增益時(shí)偏向于選擇取值較多的屬性等不足（P257）。C4.5是在ID3基礎(chǔ)上發(fā)展起來(lái)的決策樹(shù)生成算法，由J.R.Q