智能決策理論與方法講義

決議理論與方法(4)

——智能決議理論與方法(1)合肥工業(yè)大學(xué)管理學(xué)院Friday,October01,智能決策理論與方法講義第1頁(yè)不確定性決議不確定性決議：指難以取得各種狀態(tài)發(fā)生概率，甚至對(duì)未來(lái)狀態(tài)都難以把握決議問(wèn)題。特點(diǎn)：狀態(tài)不確定性。不確定性：不確定性來(lái)自人類主觀認(rèn)識(shí)與客觀實(shí)際之間存在差異。事物發(fā)生隨機(jī)性、人類知識(shí)不完全、不可靠、不準(zhǔn)確和不一致以及自然語(yǔ)言中存在含糊性和歧義性，都反應(yīng)了這種差異，都會(huì)帶來(lái)不確定性。不確定性就造成了含有相同描述信息對(duì)象可能屬于不一樣概念。處理問(wèn)題主要理論方法：人工智能與不確定性理論決議理論與方法-智能決議理論與方法智能決策理論與方法講義第2頁(yè)智能決議理論與方法1、智能決議理論形成背景2、知識(shí)發(fā)覺3、粗糙集理論4、機(jī)器學(xué)習(xí)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第3頁(yè)智能決議理論與方法—形成背景人類面臨越來(lái)越復(fù)雜決議任務(wù)和決議環(huán)境：決議問(wèn)題所包括變量規(guī)模越來(lái)越大；決議所依賴信息含有不完備性、含糊性、不確定性等特點(diǎn)，使得決議問(wèn)題難以全部定量化地表示出來(lái)；一些決議問(wèn)題及其目標(biāo)可能是含糊、不確定，使得決議者對(duì)自己偏好難以明確，伴隨決議分析深入，對(duì)決議問(wèn)題認(rèn)知加深，自己原有偏好/傾向得到不停地修正，使得決議過(guò)程出現(xiàn)不停調(diào)整情況，這時(shí)，傳統(tǒng)決議數(shù)學(xué)模型已經(jīng)難以勝任求解復(fù)雜度過(guò)高決議問(wèn)題、含有不確定性決議問(wèn)題以及半結(jié)構(gòu)化、非結(jié)構(gòu)化決議問(wèn)題，因而產(chǎn)生了智能決議理論、方法及技術(shù)。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第4頁(yè)智能決議理論與方法—AI應(yīng)用模式智能決議方法是應(yīng)用人工智能(ArtificialIntelligence,AI)相關(guān)理論方法，融合傳統(tǒng)決議數(shù)學(xué)模型和方法而產(chǎn)生含有智能化推理和求解決議方法，其經(jīng)典特征是能夠在不確定、不完備、含糊信息環(huán)境下，經(jīng)過(guò)應(yīng)用符號(hào)推理、定性推理等方法，對(duì)復(fù)雜決議問(wèn)題進(jìn)行建模、推理和求解。AI應(yīng)用于決議科學(xué)主要有兩種模式：針對(duì)可建立準(zhǔn)確數(shù)學(xué)模型決議問(wèn)題，因?yàn)閱?wèn)題復(fù)雜性，如組合爆炸、參數(shù)過(guò)多等而無(wú)法取得問(wèn)題解析解，需要借助AI中智能搜索算法取得問(wèn)題數(shù)值解；針對(duì)無(wú)法建立準(zhǔn)確數(shù)學(xué)模型不確定性決議問(wèn)題、半結(jié)構(gòu)化或非結(jié)構(gòu)化決議問(wèn)題，需要借助AI方法建立對(duì)應(yīng)決議模型并取得問(wèn)題近似解。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第5頁(yè)智能決議理論與方法1、智能決議理論形成背景2、知識(shí)發(fā)覺3、粗糙集理論4、機(jī)器學(xué)習(xí)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第6頁(yè)知識(shí)發(fā)覺—?jiǎng)訖C(jī)智能決議關(guān)鍵是怎樣獲取支持決議信息和知識(shí)。問(wèn)題知識(shí)獲取是基于知識(shí)系統(tǒng)(KBS)最大瓶頸推理機(jī)知識(shí)工程師領(lǐng)域教授決議者知識(shí)庫(kù)問(wèn)題請(qǐng)求推理結(jié)果決議理論與方法-智能決議理論與方法智能決策理論與方法講義第7頁(yè)知識(shí)發(fā)覺—?jiǎng)訖C(jī)問(wèn)題推理規(guī)則獲取與KBS中知識(shí)獲取一樣難，因而基于案例推理(Case-BasedReasoning)漸漸變成基于案例檢索(Case-BasedRetrieving)。推理機(jī)決議者案例庫(kù)問(wèn)題請(qǐng)求推理結(jié)果規(guī)則庫(kù)知識(shí)工程師領(lǐng)域教授決議理論與方法-智能決議理論與方法智能決策理論與方法講義第8頁(yè)知識(shí)發(fā)覺—?jiǎng)訖C(jī)決議者數(shù)據(jù)分析師數(shù)據(jù)中心不一定滿意決議決議支持查詢查詢結(jié)果問(wèn)題數(shù)據(jù)分析師與決議者之間對(duì)問(wèn)題了解存在偏差缺乏有創(chuàng)造性決議提議技術(shù)問(wèn)題：如查詢效率(RDBMS)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第9頁(yè)知識(shí)發(fā)覺—?jiǎng)訖C(jī)推理機(jī)數(shù)據(jù)挖掘工具數(shù)據(jù)中心決議者知識(shí)庫(kù)問(wèn)題請(qǐng)求推理結(jié)果背景知識(shí)領(lǐng)域教授優(yōu)點(diǎn)知識(shí)獨(dú)立于問(wèn)題本身知識(shí)獲取主要經(jīng)過(guò)數(shù)據(jù)挖掘?qū)崿F(xiàn)有創(chuàng)造性收獲決議理論與方法-智能決議理論與方法智能決策理論與方法講義第10頁(yè)知識(shí)發(fā)覺—?jiǎng)訖C(jī)KDD帶來(lái)新問(wèn)題知識(shí)發(fā)覺問(wèn)題：怎樣從數(shù)據(jù)中將知識(shí)挖掘出來(lái)？面臨許多技術(shù)問(wèn)題：如數(shù)據(jù)異構(gòu)問(wèn)題、數(shù)據(jù)含有噪音且信息不完整、使用什么樣挖掘算法、知識(shí)怎樣表示等知識(shí)評(píng)價(jià)問(wèn)題：數(shù)據(jù)本身含有權(quán)威性、客觀性，但知識(shí)不具備。知識(shí)怎樣評(píng)價(jià)？決議理論與方法-智能決議理論與方法智能決策理論與方法講義第11頁(yè)知識(shí)發(fā)覺—基本概念知識(shí)發(fā)覺(KnowledgeDiscoveryinDatabases,KDD)：從大量數(shù)據(jù)中提取隱含(預(yù)先未知、新奇)、有潛在應(yīng)用價(jià)值(可信、有效)并最終能被人了解模式非平凡過(guò)程。也稱為數(shù)據(jù)挖掘(DataMining)。此過(guò)程主要包含三個(gè)階段：數(shù)據(jù)準(zhǔn)備階段、數(shù)據(jù)挖掘階段、解釋評(píng)價(jià)階段。抽樣預(yù)處理數(shù)據(jù)挖掘解釋/評(píng)價(jià)數(shù)據(jù)中心樣本集預(yù)處理結(jié)果變換結(jié)果挖掘結(jié)果知識(shí)任務(wù)描述變換決議理論與方法-智能決議理論與方法智能決策理論與方法講義第12頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)準(zhǔn)備階段普通包含數(shù)據(jù)選取、預(yù)處理和數(shù)據(jù)變換等任務(wù)：數(shù)據(jù)選?。阂罁?jù)用戶需要從原始數(shù)據(jù)集中抽取一組樣本數(shù)據(jù)確定挖掘任務(wù)操作對(duì)象。常見數(shù)據(jù)源：關(guān)系型數(shù)據(jù)庫(kù)數(shù)據(jù)：如營(yíng)銷數(shù)據(jù)庫(kù)文本數(shù)據(jù)：內(nèi)容挖掘(如Web內(nèi)容挖掘，尋找相同頁(yè)面)Web數(shù)據(jù)：站點(diǎn)結(jié)構(gòu)數(shù)據(jù)(如Web結(jié)構(gòu)挖掘，優(yōu)化站點(diǎn)設(shè)計(jì)，站點(diǎn)導(dǎo)航，自適應(yīng)站點(diǎn))；站點(diǎn)使用數(shù)據(jù)或點(diǎn)擊流數(shù)據(jù)(如Web使用挖掘，用戶聚類、頁(yè)面聚類，個(gè)性化推薦等)空間數(shù)據(jù)、圖像數(shù)據(jù)、視頻數(shù)據(jù)等。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第13頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)預(yù)處理：噪音數(shù)據(jù)處理、空值處理、屬性類型轉(zhuǎn)化噪音數(shù)據(jù)處理：噪音數(shù)據(jù)往往是因輸入錯(cuò)誤而造成、或受某種外界原因干擾而有意識(shí)提供錯(cuò)誤數(shù)據(jù)。怎樣剔除噪音數(shù)據(jù)？噪音數(shù)據(jù)與系統(tǒng)中一些小概率數(shù)據(jù)統(tǒng)稱為“異常數(shù)據(jù)(Outlier)”，怎樣區(qū)分噪音數(shù)據(jù)和小概率數(shù)據(jù)？空值處理：有些數(shù)據(jù)因?yàn)椤安恢饕薄⒉恢阑颉安辉敢狻倍鴽]有取得，引發(fā)一些屬性值未知，稱這類值為空值。怎樣處理這些缺失值？屬性類型轉(zhuǎn)化：連續(xù)屬性離散化或?qū)㈦x散屬性擬合成連續(xù)屬性等。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第14頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)變換(數(shù)據(jù)約簡(jiǎn))：經(jīng)過(guò)某種方法降低算法搜索空間。垂直約簡(jiǎn)(也稱特征選擇、屬性約簡(jiǎn))：使用降維或變換方法降低變量數(shù)目，是經(jīng)典組合優(yōu)化問(wèn)題。水平約簡(jiǎn)是經(jīng)過(guò)對(duì)對(duì)象分析(包含離散化、泛化等)，合并含有相同屬性值對(duì)象，降低對(duì)象數(shù)目。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第15頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)挖掘階段：應(yīng)用相關(guān)算法從準(zhǔn)備好數(shù)據(jù)中尋找數(shù)據(jù)中隱含對(duì)信息利用如預(yù)測(cè)、決議等有價(jià)值模式。需要考慮問(wèn)題：任務(wù)確實(shí)定：分類、聚類、關(guān)聯(lián)規(guī)則發(fā)覺等。方法選擇：統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)方法、不確定性方法、數(shù)據(jù)庫(kù)技術(shù)等。是知識(shí)發(fā)覺關(guān)鍵，也是被研究最廣泛內(nèi)容。數(shù)據(jù)挖掘方法很多，需要我們對(duì)它們適用條件、前提假設(shè)有充分了解。運(yùn)行效率分析：不一樣算法其效率存在很大差異。算法設(shè)計(jì)與選擇往往就是精度與效率之間權(quán)衡。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第16頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)挖掘任務(wù)及常采取方法：歸納總結(jié)：從泛化角度總結(jié)數(shù)據(jù)，即從低層次數(shù)據(jù)抽象出高層次描述過(guò)程。主要方法：歸納學(xué)習(xí)。發(fā)覺關(guān)聯(lián)規(guī)則：關(guān)聯(lián)規(guī)則形式為A→B，A為前件，B為后件。(Day=Friday)and(Product=Nappies)→(Product=Beer)為一經(jīng)典關(guān)聯(lián)規(guī)則A為滿足前件對(duì)象集，B為滿足后件對(duì)象，N為全部對(duì)象集。經(jīng)典方法：Apriori算法。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第17頁(yè)知識(shí)發(fā)覺—基本概念分類(等價(jià)關(guān)系，判別)：按類標(biāo)簽(為數(shù)據(jù)庫(kù)中某屬性集，普通僅包含一個(gè)屬性)對(duì)數(shù)據(jù)庫(kù)中對(duì)象進(jìn)行分類，含有相同標(biāo)簽值或標(biāo)簽值在指定區(qū)間內(nèi)對(duì)象屬于同類。分類規(guī)則是判斷某個(gè)對(duì)象屬于某類充分條件即對(duì)象含有某類屬性時(shí)則表示該對(duì)象屬于該類。其規(guī)則形式普通為IFLogicExpThenA類ElseB類。主要方法：邏輯回歸、判別分析、決議樹、ANN、粗糙集、SVM等。聚類(相容關(guān)系)：聚類也叫分段，就是將數(shù)據(jù)庫(kù)中實(shí)體分成若干組或簇，每簇內(nèi)實(shí)體是相同。規(guī)則形式為IFO1與O2相同ThenO1、O2在同一簇。對(duì)象相同判斷方法有各種如距離法。經(jīng)典方法：K-means決議理論與方法-智能決議理論與方法智能決策理論與方法講義第18頁(yè)知識(shí)發(fā)覺—基本概念發(fā)覺特征規(guī)則：特征規(guī)則是刻劃某個(gè)概念特征斷言，它相當(dāng)于分類規(guī)則逆命題。比如病癥是某種疾病特征。規(guī)則普通形式是：IFA類Then特征表示式。序列模式發(fā)覺：它與關(guān)聯(lián)規(guī)則相同，不一樣之處于于事件發(fā)生有前后次序，該規(guī)則普通形式為：At(i)→Bt(j)其中t(i)<t(j)。比如序貫規(guī)則JacketandTie→Shoes表示客戶在買了“夾克”和“領(lǐng)帶”之后就會(huì)買“鞋”。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第19頁(yè)知識(shí)發(fā)覺—基本概念偏離探測(cè)：探測(cè)測(cè)量值與期望值之間差異并對(duì)其進(jìn)行解釋。常有三種偏離類型：隨時(shí)間偏離(以歷史值為期望值)、與標(biāo)準(zhǔn)偏離(以標(biāo)準(zhǔn)值為期望值)、與預(yù)測(cè)偏離(以預(yù)測(cè)值為期望值)?；貧w：依據(jù)歷史數(shù)據(jù)擬合一函數(shù)將屬性集映射到對(duì)應(yīng)值集?；貧w能夠看作一個(gè)分類，區(qū)分是分類類標(biāo)簽值是離散，而回歸是連續(xù)。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第20頁(yè)知識(shí)發(fā)覺—基本概念neurallinerprofit010005000mins回歸模型m-male，f-femalemfmmmmmmmfmmmmmmmmmffmmmmmmmmmmmfmmmmmmmmmmmmmmmmmmmf16K64K32K20304050ageincome聚類模型決議理論與方法-智能決議理論與方法智能決策理論與方法講義第21頁(yè)知識(shí)發(fā)覺—基本概念數(shù)據(jù)挖掘方法DataMining統(tǒng)計(jì)方法·相關(guān)分析·線性回歸·主成份分析·聚類分析數(shù)據(jù)庫(kù)技術(shù)·面向數(shù)據(jù)集方法·面向?qū)傩詺w納·數(shù)據(jù)庫(kù)統(tǒng)計(jì)機(jī)器學(xué)習(xí)·規(guī)則歸納·基于案例推理·遺傳算法·神經(jīng)網(wǎng)絡(luò)不確定性理論·貝葉斯網(wǎng)絡(luò)·含糊邏輯·粗糙集理論·證據(jù)理論可視化技術(shù)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第22頁(yè)知識(shí)發(fā)覺—基本概念解釋與評(píng)價(jià)階段：結(jié)果篩選：過(guò)濾(移去)不感興趣或顯而易見模式。利用描述規(guī)則特征數(shù)值如信度、支持度或興趣度等，定義某個(gè)閾值，對(duì)規(guī)則進(jìn)行篩選；指定語(yǔ)義約束，規(guī)則前件或后件只包含感興趣屬性，或者指定屬性間依賴性約束；完全依靠用戶對(duì)處理結(jié)果進(jìn)行篩選。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第23頁(yè)知識(shí)發(fā)覺—基本概念結(jié)果評(píng)價(jià)：確定所發(fā)覺模式可信度?；痉椒ㄊ菍颖緮?shù)據(jù)集分成二部分，一部分是訓(xùn)練集用來(lái)發(fā)覺模式，另一部分是測(cè)試集，分析結(jié)果可信度。處理結(jié)果維護(hù)：信息處理所包括樣本數(shù)據(jù)集經(jīng)常是動(dòng)態(tài)改變，所以需要對(duì)所處理結(jié)果進(jìn)行維護(hù)以確保結(jié)果與數(shù)據(jù)改變相一致。維護(hù)能夠?qū)?shù)據(jù)改變引發(fā)特殊問(wèn)題重新應(yīng)用所建立處理方法，或者應(yīng)用某種增量處理算法。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第24頁(yè)知識(shí)發(fā)覺—空值估算空值是指屬性值未知且不可用、與其它任何值都不相同符號(hào)。在樣本數(shù)據(jù)集中，空值在全部非主碼屬性中都可能出現(xiàn)?？罩党霈F(xiàn)主要原因：在信息搜集時(shí)忽略了一些認(rèn)為不主要數(shù)據(jù)或信息提供者不愿意提供，而這些數(shù)據(jù)對(duì)以后信息處理可能是有用；一些屬性值未知；數(shù)據(jù)模型限制。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第25頁(yè)知識(shí)發(fā)覺—空值估算空值處理慣用方法：從訓(xùn)練集中移去含未知值實(shí)例；用某個(gè)最可能值進(jìn)行替換；基于樣本中其它屬性取值和分類信息，結(jié)構(gòu)規(guī)則來(lái)預(yù)測(cè)丟失數(shù)據(jù)，并用預(yù)測(cè)結(jié)果“填補(bǔ)”丟失值；應(yīng)用貝葉斯公式確定未知值概率分布，選擇一最可能值填補(bǔ)空值或依據(jù)概率分布用不一樣值填補(bǔ)空值形成多個(gè)對(duì)象；將含有未知值一個(gè)給定樣本數(shù)據(jù)集轉(zhuǎn)換成一個(gè)新、可能不相容但每個(gè)屬性值均已知數(shù)據(jù)集，方法是將某個(gè)屬性未知值用全部該屬性可能值替換形成多個(gè)數(shù)據(jù)集。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第26頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化問(wèn)題描述

設(shè)為一樣本數(shù)據(jù)集，為非空有限集合，C是條件屬性集，D是決議屬性集。假設(shè)對(duì)于任意有，R是實(shí)數(shù)集，則為連續(xù)屬性。設(shè)是上分割點(diǎn)集合，記為其中，為一整數(shù)，表示離散化程度，能夠看作按屬性將論域中對(duì)象分成類。3kiki-121……決議理論與方法-智能決議理論與方法智能決策理論與方法講義第27頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化對(duì)于需要離散化連續(xù)屬性集，其分割點(diǎn)集合記為將ci屬性連續(xù)取值映射到離散空間，即對(duì)于任意若其屬性ci取值在區(qū)間內(nèi)，則將屬性值重新標(biāo)識(shí)為j。這么就把原來(lái)含有連續(xù)屬性樣本數(shù)據(jù)集A轉(zhuǎn)換成離散化數(shù)據(jù)集。所以離散化問(wèn)題本質(zhì)上可歸結(jié)為利用選取分割點(diǎn)對(duì)屬性值域空間進(jìn)行劃分問(wèn)題。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第28頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化離散化方法經(jīng)典有等區(qū)間方法、等信息量方法、基于信息熵方法、Holte1R離散化方法、統(tǒng)計(jì)試驗(yàn)方法、超平面搜索方法以及用戶自定義區(qū)間等。應(yīng)用不一樣準(zhǔn)則可將現(xiàn)有離散化方法分為局部與全局方法(論域空間)、靜態(tài)與動(dòng)態(tài)方法(屬性空間)和有導(dǎo)師與無(wú)導(dǎo)師方法(是否依賴決議屬性)。(1)等區(qū)間離散化方法等區(qū)間分割是將連續(xù)屬性值域等分成()個(gè)區(qū)間,普通由用戶確定。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第29頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化假設(shè)某個(gè)屬性最大屬性值為xmax，最小屬性值為xmin，用戶給定分割點(diǎn)參數(shù)為k，則分割點(diǎn)間隔為δ=(xmax-xmin)/k，所得到屬性分割點(diǎn)為xmin+i

，i=1,2,…,k。(2)等信息量離散化方法等信息量分割首先將測(cè)量值進(jìn)行排序，然后將屬性值域分成k個(gè)區(qū)間，每個(gè)區(qū)間包含相同數(shù)量測(cè)量值。假設(shè)某個(gè)屬性最大屬性值為xmax，最小屬性值為xmin，用戶給定分割點(diǎn)參數(shù)為k，樣本集中對(duì)象個(gè)數(shù)為n，則需要將樣本集中對(duì)象按該屬性取值從小到大排列，然后按對(duì)象數(shù)平均劃分為k段即得到分割點(diǎn)集，每?jī)蓚€(gè)相鄰分割點(diǎn)之間對(duì)象數(shù)均為n/k。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第30頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化(3)統(tǒng)計(jì)試驗(yàn)方法統(tǒng)計(jì)試驗(yàn)方法依據(jù)決議屬性分析區(qū)間劃分之間獨(dú)立程度，確定分割點(diǎn)有效性。對(duì)于任意分割點(diǎn)，均可將分成2個(gè)區(qū)間和，兩區(qū)間獨(dú)立程度為：其中：r是決議類數(shù)目nij是在第l區(qū)間中屬于第j決議類對(duì)象數(shù)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第31頁(yè)知識(shí)發(fā)覺—連續(xù)屬性離散化若，則取基于統(tǒng)計(jì)試驗(yàn)離散化方法是將值較大分割點(diǎn)作為有效分割點(diǎn)。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第32頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)TheApriorimethod:ProposedbyAgrawal&Srikant1994Majoridea:AsubsetofafrequentitemsetmustbefrequentE.g.,if{beer,diaper,nuts}isfrequent,{beer,diaper}mustbe.Anyoneisinfrequent,itssupersetcannotbe!Apowerful,scalablecandidatesetpruningtechnique:Itreducescandidatek-itemsetsdramatically(fork>2)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第33頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)關(guān)聯(lián)規(guī)則例子ForruleA

C:support=support({A

C})=50%confidence=support({A

C})/support({A})=66.6%TheAprioriprinciple:Anysubsetofafrequentitemsetmustbefrequent.Min.support50%Min.confidence50%決議理論與方法-智能決議理論與方法智能決策理論與方法講義第34頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)ProcedureFindthefrequentitemsets:thesetsofitemsthathaveminimumsupport(Apriori)Asubsetofafrequentitemsetmustalsobeafrequentitemset,i.e.,if{A

B}is

afrequentitemset,both{A}and{B}shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok(k-itemset)Usethefrequentitemsetstogenerateassociationrules.決議理論與方法-智能決議理論與方法智能決策理論與方法講義第35頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)AlgorithmJoinStepCk

isgeneratedbyjoiningLk-1withitselfPruneStepAny(k-1)-itemsetthatisnotfrequentcannotbeasubsetofafrequentk-itemset,henceshouldberemoved.(Ck:Candidateitemsetofsizek)(Lk:frequentitemsetofsizek)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第36頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)Pseudocode（正式代碼見附件1）Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=

;k++)dobegin

Ck+1=candidatesgeneratedfromLk;

foreachtransactiontindatabasedo

incrementthecountofallcandidatesinCk+1thatarecontainedint

Lk+1=candidatesinCk+1withmin_support

endreturn

k

Lk;決議理論與方法-智能決議理論與方法智能決策理論與方法講義第37頁(yè)知識(shí)發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD決議理論與方法-智能決議理論與方法智能決策理論與方法講義第38頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)聚類分析是把研究對(duì)象按照一定規(guī)則分成若干類別，并使類之間差異盡可能地大，類內(nèi)差異盡可能地小，換句話說(shuō)，使類間相同性最小、而類內(nèi)相同性最大。聚類方法關(guān)鍵問(wèn)題是樣品間相同性度量，通慣用距離來(lái)度量。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第39頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)聚類分析中慣用距離(1)歐氏(Euclidean)距離(2)絕對(duì)距離(3)Minkowski距離顯然當(dāng)m=1時(shí)就是絕對(duì)距離，m=2時(shí)就是歐氏距離。在實(shí)際應(yīng)用時(shí)常分析兩個(gè)樣品之間相對(duì)距離，這時(shí)需要對(duì)樣品數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后用標(biāo)準(zhǔn)化數(shù)據(jù)計(jì)算距離。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第40頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)對(duì)于給定n個(gè)樣品，先粗略地形成k(k≤n)個(gè)分割，使得每個(gè)分割對(duì)應(yīng)一個(gè)類、每個(gè)類最少有一個(gè)樣品而且每個(gè)樣品準(zhǔn)確地屬于一個(gè)類，然后按照某種標(biāo)準(zhǔn)進(jìn)行修正，直至分類比較合理為止。詳細(xì)步驟以下：(1)聚點(diǎn)選擇：聚點(diǎn)是一批有代表性樣品，它選擇決定了初始分類。首先確定分類數(shù)k，然后選擇k個(gè)有代表性樣品作為每個(gè)類初始元素即聚點(diǎn)。聚點(diǎn)可由用戶依據(jù)經(jīng)驗(yàn)選擇，也可將全部樣品人為地或隨機(jī)地分成k類，以每類重心作為聚點(diǎn)。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第41頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)聚點(diǎn)最小最大標(biāo)準(zhǔn)選擇法：①設(shè)將n個(gè)樣品分成k類，先選擇全部樣品中相距最遠(yuǎn)兩個(gè)樣品為前兩個(gè)聚點(diǎn)，所以有②設(shè)已經(jīng)找到了l個(gè)(2≤l＜k)聚點(diǎn)，則第l+1個(gè)聚點(diǎn)選擇方法是使得與前l(fā)個(gè)聚點(diǎn)距離最小者等于全部其余與前l(fā)個(gè)聚點(diǎn)較小距離最大者，直至選定k個(gè)聚點(diǎn)，即將所取得k個(gè)聚點(diǎn)集合記為決議理論與方法-智能決議理論與方法智能決策理論與方法講義第42頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)(2)初始聚類有了聚點(diǎn)集合后，可依據(jù)以下最靠近標(biāo)準(zhǔn)實(shí)現(xiàn)初始分類：若對(duì)于某樣品x出現(xiàn)，則x任意歸于Gi(0)或Gj(0)類。這么就得到了樣品空間初始分類：決議理論與方法-智能決議理論與方法智能決策理論與方法講義第43頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)(3)迭代過(guò)程設(shè)聚類形成一個(gè)分類為則可從G(m)出發(fā)計(jì)算新聚點(diǎn)集合L(m+1)。普通能夠以G(m)中各類重心作為新聚點(diǎn)。其中依據(jù)新聚點(diǎn)集，對(duì)樣品空間重新聚類，形成新分類：其中決議理論與方法-智能決議理論與方法智能決策理論與方法講義第44頁(yè)知識(shí)發(fā)覺—聚類(K-means算法)(4)迭代終止伴隨m增大，分類趨于穩(wěn)定。當(dāng)G(m+1)=G(m)或在一定精度范圍內(nèi)近似有G(m+1)=G(m)，則遞推過(guò)程結(jié)束。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第45頁(yè)智能決議理論與方法1、智能決議理論形成背景2、知識(shí)發(fā)覺3、粗糙集理論4、機(jī)器學(xué)習(xí)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第46頁(yè)預(yù)備知識(shí)——相關(guān)名詞解釋論域：研究對(duì)象全體組員組成集合，普通用字母U表示；若X

U，則稱X是U子集隸屬度：描述一個(gè)對(duì)象x與某個(gè)子集X之間隸屬程度，普通用符號(hào)

表示，若xX,則

=1;若,則

=0;其它：0<<1;(

慣用某個(gè)函數(shù)加以描述，稱為隸屬度函數(shù))高斯函數(shù)粗糙集理論(RoughSetTheory)智能決策理論與方法講義第47頁(yè)預(yù)備知識(shí)——相關(guān)名詞解釋等價(jià)關(guān)系：R是U上一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng)對(duì)于任意xU，都有xRx（自反性）對(duì)于任意x,yU，xRy?yRx（對(duì)稱性）對(duì)于任意x,y,zU，xRy∧yRz→xRz（傳遞性）等價(jià)類：若R是U上一個(gè)等價(jià)關(guān)系，對(duì)于任意xU，稱集合[x]={y|yRx,yU}為U關(guān)于R一個(gè)等價(jià)類，記為[x]R。設(shè)X1,X2,…,Xn是U關(guān)于R全部等價(jià)類，則有：Xi∩Xj=φ（i≠j，i,j=1,2,…,n）X1∪X2∪…∪Xn=U劃分：全部等價(jià)類集合稱為U關(guān)于R商集，它組成了U一個(gè)劃分，記為U/R。概念：含有相同特征值一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類就是一個(gè)概念）粗糙集理論(RoughSetTheory)智能決策理論與方法講義第48頁(yè)預(yù)備知識(shí)——相關(guān)名詞解釋piT1pjiffv(pi,T1)=v(pj,T1)，則T1是U上一個(gè)等價(jià)關(guān)系（類似地能夠定義T2,T3,E）X1=[p1]=[p4]=[p6]={p1,p4,p6}為U關(guān)于T1一個(gè)等價(jià)類X2=[p2]=[p3]=[p5]={p2,p3,p5}為U關(guān)于T1另一個(gè)等價(jià)類（T1有多少種取值就有多少個(gè)等價(jià)類）顯然X1∩X2=φ;X1∪X2=U商集U/T1={X1,X2}UT1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第49頁(yè)預(yù)備知識(shí)——組員集合組員：明確隸屬關(guān)系含糊組員：概念含糊(如青年)造成組員含糊粗糙組員：概念清楚(如感冒)，組員含糊(是否感冒不清楚)，含有概率特征(隸屬函數(shù))，但不是概率問(wèn)題，只是因?yàn)橐罁?jù)可用知識(shí)無(wú)法得到準(zhǔn)確結(jié)論。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第50頁(yè)粗糙集理論經(jīng)典模型——RST提出粗糙集理論由Pawlak提出[1982,1991]。粗糙集理論反應(yīng)了人們以不完全信息或知識(shí)去處理一些不可分辨現(xiàn)象能力，或依據(jù)觀察、度量到一些不準(zhǔn)確結(jié)果而進(jìn)行分類數(shù)據(jù)能力。PawlakZ.,Roughsets.InternationalJournalofComputerandInformationSciences,1982(11):341-356PawlakZ.,Roughset—TheoreticalAspectsofReasoningaboutData,Dordrecht,Boston,London:KluwerAcademicPublishers,1991粗糙集理論(RoughSetTheory)智能決策理論與方法講義第51頁(yè)粗糙集理論經(jīng)典模型——基本思想知識(shí)是主體對(duì)論域中客體進(jìn)行分類能力，分類能力越強(qiáng)，主體所具備知識(shí)可靠度越高

分類能力受主體分辨能力影響，所以分類含有近似性

(粗糙集)影響分類能力原因(在信息系統(tǒng)中常描述為屬性)很多，不一樣原因主要程度不一樣，其中一些原因起決定性作用

(屬性主要性：屬性約簡(jiǎn))含有相同屬性實(shí)體，屬性取值不一樣對(duì)分類能力也產(chǎn)生影響

(值主要性：值約簡(jiǎn))屬性之間存在某種依賴關(guān)系(決議規(guī)則)粗糙集理論(RoughSetTheory)智能決策理論與方法講義第52頁(yè)粗糙集理論經(jīng)典模型——信息系統(tǒng)與知識(shí)信息系統(tǒng)I能夠定義為四元組<U,A,V,f>，其中有限非空集合U是論域，A為關(guān)于U屬性集，，Va表示屬性a值域，映射f:U×A→V表示對(duì)

x

U，a

A，有：f(x,a)

V。決議表：若屬性集合A可進(jìn)一步分為兩個(gè)屬性子集并：條件屬性集C和決議屬性集D，A=C∪D，C∩D=φ，則信息系統(tǒng)也被稱為決議表。UT1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第53頁(yè)粗糙集理論經(jīng)典模型——信息系統(tǒng)與知識(shí)A任何一個(gè)子集B確定一個(gè)U上二元關(guān)系IND(B)：對(duì)于任意a

B，xIND(B)y

a(x)=a(y)；x,y

U；a(x)表示對(duì)象xa屬性值。則稱IND(B)為不可分辨關(guān)系(?)。IND(B)是等價(jià)關(guān)系，IND(B)全部等價(jià)類集合記為U/B（稱為知識(shí)B），含有元素x等價(jià)類記為B(x)或[x]B，同一等價(jià)類中元素是不可分辨，稱IND(B)等價(jià)類為初等集（范圍），它是知識(shí)庫(kù)基本結(jié)構(gòu)單元即概念。設(shè)R是由屬性集A子集誘導(dǎo)論域U上等價(jià)關(guān)系族，則稱R為U上一個(gè)知識(shí)庫(kù)，記為K=(U,R)。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第54頁(yè)粗糙集理論經(jīng)典模型——粗糙集與近似對(duì)于U任意子集X，若X恰能由知識(shí)R若干個(gè)初等集并組成，則稱X為R-準(zhǔn)確集，不然為R-粗糙集。每個(gè)粗糙集X都可用兩個(gè)與之相關(guān)準(zhǔn)確集近似表示即X上近似和下近似，他們是粗糙集理論兩個(gè)最基本運(yùn)算。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第55頁(yè)粗糙集理論經(jīng)典模型——粗糙集與近似下近似由全部包含于X初等集合并組成，X下近似中元素一定屬于X。上近似由與X交為非空初等集合并組成，而上近似中元素可能屬于X。上近似與下近似差為邊界域，粗糙集邊界域?yàn)榉强眨蝗粸闇?zhǔn)確集。邊界域中元素依據(jù)可用知識(shí)沒有確定分類，即它既不能劃分到X中也不能劃分到X補(bǔ)集中。正域與負(fù)域粗糙集理論(RoughSetTheory)智能決策理論與方法講義第56頁(yè)粗糙集理論經(jīng)典模型——經(jīng)典粗糙集模型論域U粗糙集X粗糙集X粗糙集理論(RoughSetTheory)智能決策理論與方法講義第57頁(yè)粗糙集理論經(jīng)典模型——經(jīng)典粗糙集模型R1={T1}：U/R1={{p2,p3,p5}，{p1,p4,p6}}；R2={T2,T1}：U/R2={{p1,p4,p6},{p2,p5},{p3}}；R3={T1,T2,T3}：U/R3=({p1},{p3},{p6},{p2,p5},{p4}};F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R3粗糙集，X1R3下近似是{p1,p3,p6}，R3上近似是{p1,p2,p3,p5,p6}，邊界域?yàn)閧p2,p5}；X2={p4,p5}也是R3粗糙集，X2R3下近似是{p4}，X2R3上近似是{p2,p4,p5}，而邊界域是{p2,p5}。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第58頁(yè)粗糙集理論經(jīng)典模型——粗糙集數(shù)字特征精度：XR精度反應(yīng)了我們對(duì)于了解集合X知識(shí)完全程度。αR(X)=1為準(zhǔn)確集，0≤αR(X)<1為粗糙集。粗糙度：XR粗糙度反應(yīng)了我們對(duì)于了解集合X知識(shí)不完全程度。(精度與概率或隸屬度區(qū)分)隸屬度：是依據(jù)可用知識(shí)R，對(duì)象x隸屬于概念X條件概率。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第59頁(yè)粗糙集理論經(jīng)典模型——粗糙集數(shù)字特征設(shè)F={X1，X2，…，Xn}是論域U上一個(gè)劃分，那么依據(jù)知識(shí)R，F(xiàn)分類精度怎樣？F近似精度：分類近似精度給出了依據(jù)現(xiàn)有知識(shí)對(duì)對(duì)象進(jìn)行分類時(shí)可能正確決議百分?jǐn)?shù)。F近似質(zhì)量：近似質(zhì)量給出了能正確分類百分?jǐn)?shù)。這是一個(gè)非常主要特征數(shù)字，它反應(yīng)了兩種分類F和R之間關(guān)系。假如將R看作決議表中條件屬性集，F(xiàn)看成決議屬性集，近似質(zhì)量反應(yīng)了二者之間依賴關(guān)系。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第60頁(yè)粗糙集理論經(jīng)典模型——粗糙集數(shù)字特征知識(shí)R={T1,T2,T3}：U/R=({p1},{p3},{p6},{p2,p5},{p4}};分類F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R粗糙集，X1R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}，R精度為0.6；R粗糙度為0.4；

X2={p4,p5}也是R粗糙集，X2R下近似是{p4}，X2R上近似是{p2,p4,p5}，R精度為0.333；R粗糙度為0.667；p2隸屬于X1隸屬度為0.25。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第61頁(yè)粗糙集理論經(jīng)典模型——粗糙集數(shù)字特征知識(shí)R={T1,T2,T3}：U/R=({p1},{p3},{p6},{p2,p5},{p4}};分類F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R粗糙集，X1R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}；

X2={p4,p5}也是R粗糙集，X2R下近似是{p4}，X2R上近似是{p2,p4,p5}；F近似精度為0.5；F近似質(zhì)量為0.667。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第62頁(yè)粗糙集理論經(jīng)典模型——知識(shí)依賴為了尋找“IF……THEN”形式推理規(guī)則，在粗糙集理論體系中所采取方法是從一個(gè)給定知識(shí)，推導(dǎo)另一個(gè)知識(shí)。假如知識(shí)D全部初等范圍都能用知識(shí)C一些初等范圍來(lái)定義，則稱知識(shí)D可由知識(shí)C推得，也稱D完全依賴于C，記為C

D。設(shè)信息系統(tǒng)I=<U,A,V,f>，A=C∪D，B

C，則DB正域定義為：DB正域表示利用知識(shí)B，能正確地劃分到U/D各等價(jià)類中全部對(duì)象集合粗糙集理論(RoughSetTheory)智能決策理論與方法講義第63頁(yè)粗糙集理論經(jīng)典模型——知識(shí)依賴設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，①D完全依賴于C當(dāng)且僅當(dāng)②D等價(jià)于C當(dāng)且僅當(dāng)(C

D)

(D

C)；③D獨(dú)立于C當(dāng)且僅當(dāng)

(C

D)

(D

C)。假如知識(shí)D部分初等范圍能用知識(shí)C一些初等范圍來(lái)定義，稱知識(shí)D部分依賴于知識(shí)C。設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，有：則稱D是k(0

k

1)度依賴于C，記為C

kD。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第64頁(yè)粗糙集理論經(jīng)典模型——知識(shí)依賴R1={T1}：U/R1={{p2,p3,p5}，{p1,p4,p6}}；R2={T2,T1}：U/R2={{p1,p4,p6},{p2,p5},{p3}}；R3={T1,T2,T3}：U/R3=({p1},{p3},{p6},{p2,p5},{p4}};F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R3粗糙集，X1R3下近似是{p1,p3,p6}，R3上近似是{p1,p2,p3,p5,p6}；X2={p4,p5}也是R3粗糙集，X2R3下近似是{p4}，X2R3上近似是{p2,p4,p5}。FR3正域是{p1,p3,p4,p6},所以F對(duì)R3依賴度是2/3。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY條件屬性子集{T1}{T2}{T3}{T1,T2}{T1,T3}{T2,T3}{T1,T2,T3}依賴度k001/21/62/32/32/3粗糙集理論(RoughSetTheory)智能決策理論與方法講義第65頁(yè)粗糙集理論經(jīng)典模型——知識(shí)約簡(jiǎn)為何要約簡(jiǎn)知識(shí)？判別：依據(jù)條件屬性取值確定對(duì)象所屬類。實(shí)際：確定對(duì)象所屬類只需其中幾個(gè)屬性甚至一個(gè)屬性，而不需要知道對(duì)象全部屬性，這與人類對(duì)實(shí)體識(shí)別是一致。表明：不一樣屬性在分類時(shí)所起作用是不一樣。什么是知識(shí)約簡(jiǎn)？將知識(shí)庫(kù)中一些無(wú)須要等價(jià)關(guān)系（知識(shí)）移去過(guò)程。設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，B

C，若

C(D)=

B(D)且B是D獨(dú)立，則B為CD約簡(jiǎn)，記為REDD(C)。CD約簡(jiǎn)是不含任何冗余知識(shí)且與C含有相同分類能力子集（用知識(shí)C將對(duì)象劃分到