智能決策理論與方法講義(-71張)

決策理論與方法(4)

——智能決策理論與方法(1)合肥工業(yè)大學(xué)管理學(xué)院2024年4月3日決策理論與方法(4)

——智能決決策理論與方法-智能決策理論與方法不確定性決策不確定性決策：指難以獲得各種狀態(tài)發(fā)生的概率，甚至對未來狀態(tài)都難以把握的決策問題。特點(diǎn)：狀態(tài)的不確定性。不確定性：不確定性來自人類的主觀認(rèn)識與客觀實(shí)際之間存在的差異。事物發(fā)生的隨機(jī)性、人類知識的不完全、不可靠、不精確和不一致以及自然語言中存在的模糊性和歧義性，都反映了這種差異，都會帶來不確定性。不確定性就造成了具有相同描述信息的對象可能屬于不同概念。解決問題的主要理論方法：人工智能與不確定性理論決策理論與方法-智能決策理論與方法不確定性決策不確定性決策：決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能決策理論的形成背景2、知識發(fā)現(xiàn)3、粗糙集理論4、機(jī)器學(xué)習(xí)決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能決策理論與方法-智能決策理論與方法智能決策理論與方法—形成背景人類面臨越來越復(fù)雜的決策任務(wù)和決策環(huán)境：決策問題所涉及的變量規(guī)模越來越大；決策所依賴的信息具有不完備性、模糊性、不確定性等特點(diǎn)，使得決策問題難以全部定量化地表示出來；某些決策問題及其目標(biāo)可能是模糊的、不確定的，使得決策者對自己的偏好難以明確，隨著決策分析的深入，對決策問題的認(rèn)知加深，自己原有的偏好/傾向得到不斷地修正，使得決策過程出現(xiàn)不斷調(diào)整的情況，這時，傳統(tǒng)的決策數(shù)學(xué)模型已經(jīng)難以勝任求解復(fù)雜度過高的決策問題、含有不確定性的決策問題以及半結(jié)構(gòu)化、非結(jié)構(gòu)化的決策問題，因而產(chǎn)生了智能決策理論、方法及技術(shù)。決策理論與方法-智能決策理論與方法智能決策理論與方法—形成背決策理論與方法-智能決策理論與方法智能決策理論與方法—AI的應(yīng)用模式智能決策方法是應(yīng)用人工智能(ArtificialIntelligence,AI)相關(guān)理論方法，融合傳統(tǒng)的決策數(shù)學(xué)模型和方法而產(chǎn)生的具有智能化推理和求解的決策方法，其典型特征是能夠在不確定、不完備、模糊的信息環(huán)境下，通過應(yīng)用符號推理、定性推理等方法，對復(fù)雜決策問題進(jìn)行建模、推理和求解。AI應(yīng)用于決策科學(xué)主要有兩種模式：針對可建立精確數(shù)學(xué)模型的決策問題，由于問題的復(fù)雜性，如組合爆炸、參數(shù)過多等而無法獲得問題的解析解，需要借助AI中的智能搜索算法獲得問題的數(shù)值解；針對無法建立精確數(shù)學(xué)模型的不確定性決策問題、半結(jié)構(gòu)化或非結(jié)構(gòu)化決策問題，需要借助AI方法建立相應(yīng)的決策模型并獲得問題的近似解。決策理論與方法-智能決策理論與方法智能決策理論與方法—AI的決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能決策理論的形成背景2、知識發(fā)現(xiàn)3、粗糙集理論4、機(jī)器學(xué)習(xí)決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)智能決策的核心是如何獲取支持決策的信息和知識。問題知識獲取是基于知識的系統(tǒng)(KBS)的最大瓶頸推理機(jī)知識工程師領(lǐng)域?qū)＜覜Q策者知識庫問題請求推理結(jié)果決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)智能決策的核決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)問題推理規(guī)則的獲取與KBS中知識獲取一樣難，因而基于案例推理(Case-BasedReasoning)漸漸變成基于案例檢索(Case-BasedRetrieving)。推理機(jī)決策者案例庫問題請求推理結(jié)果規(guī)則庫知識工程師領(lǐng)域?qū)＜覜Q策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)問題推理機(jī)決決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)決策者數(shù)據(jù)分析師數(shù)據(jù)中心不一定滿意的決策決策支持查詢查詢結(jié)果問題數(shù)據(jù)分析師與決策者之間對問題的理解存在偏差缺少有創(chuàng)造性的決策建議技術(shù)問題：如查詢效率(RDBMS)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)決策者數(shù)據(jù)分決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)推理機(jī)數(shù)據(jù)挖掘工具數(shù)據(jù)中心決策者知識庫問題請求推理結(jié)果背景知識領(lǐng)域?qū)＜覂?yōu)點(diǎn)知識獨(dú)立于問題本身知識的獲取主要通過數(shù)據(jù)挖掘?qū)崿F(xiàn)有創(chuàng)造性收獲決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)推理機(jī)數(shù)據(jù)挖決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)KDD帶來的新問題知識發(fā)現(xiàn)問題：如何從數(shù)據(jù)中將知識挖掘出來？面臨許多技術(shù)問題：如數(shù)據(jù)異構(gòu)問題、數(shù)據(jù)具有噪音且信息不完整、使用什么樣的挖掘算法、知識如何表示等知識評價問題：數(shù)據(jù)本身具有權(quán)威性、客觀性，但知識不具備。知識如何評價？決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—動機(jī)KDD帶來的決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念知識發(fā)現(xiàn)(KnowledgeDiscoveryinDatabases,KDD)：從大量數(shù)據(jù)中提取隱含的(預(yù)先未知、新穎)、有潛在應(yīng)用價值的(可信、有效)并最終能被人理解的模式的非平凡過程。也稱為數(shù)據(jù)挖掘(DataMining)。此過程主要包含三個階段：數(shù)據(jù)準(zhǔn)備階段、數(shù)據(jù)挖掘階段、解釋評價階段。抽樣預(yù)處理數(shù)據(jù)挖掘解釋/評價數(shù)據(jù)中心樣本集預(yù)處理結(jié)果變換結(jié)果挖掘結(jié)果知識任務(wù)描述變換決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念知識發(fā)現(xiàn)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)準(zhǔn)備階段一般包含數(shù)據(jù)選取、預(yù)處理和數(shù)據(jù)變換等任務(wù)：數(shù)據(jù)選?。焊鶕?jù)用戶的需要從原始數(shù)據(jù)集中抽取一組樣本數(shù)據(jù)確定挖掘任務(wù)的操作對象。常見數(shù)據(jù)源：關(guān)系型數(shù)據(jù)庫數(shù)據(jù)：如營銷數(shù)據(jù)庫文本數(shù)據(jù)：內(nèi)容挖掘(如Web內(nèi)容挖掘，尋找相似頁面)Web數(shù)據(jù)：站點(diǎn)結(jié)構(gòu)數(shù)據(jù)(如Web結(jié)構(gòu)挖掘，優(yōu)化站點(diǎn)設(shè)計，站點(diǎn)導(dǎo)航，自適應(yīng)站點(diǎn))；站點(diǎn)使用數(shù)據(jù)或點(diǎn)擊流數(shù)據(jù)(如Web使用挖掘，用戶聚類、頁面聚類，個性化推薦等)空間數(shù)據(jù)、圖像數(shù)據(jù)、視頻數(shù)據(jù)等。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)準(zhǔn)備決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)預(yù)處理：噪音數(shù)據(jù)處理、空值處理、屬性類型轉(zhuǎn)化噪音數(shù)據(jù)處理：噪音數(shù)據(jù)往往是因輸入錯誤而導(dǎo)致的、或受某種外界因素干擾而有意識提供的錯誤數(shù)據(jù)。如何剔除噪音數(shù)據(jù)？噪音數(shù)據(jù)與系統(tǒng)中的一些小概率數(shù)據(jù)統(tǒng)稱為“異常數(shù)據(jù)(Outlier)”，如何區(qū)分噪音數(shù)據(jù)和小概率數(shù)據(jù)？空值處理：有些數(shù)據(jù)由于“不重要”、不知道或“不愿意”而沒有獲得，引起某些屬性值未知，稱此類值為空值。如何處理這些缺失值？屬性類型轉(zhuǎn)化：連續(xù)屬性離散化或?qū)㈦x散屬性擬合成連續(xù)屬性等。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)預(yù)處決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)變換(數(shù)據(jù)約簡)：通過某種方法降低算法的搜索空間。垂直約簡(也稱特征選擇、屬性約簡)：使用降維或變換方法減少變量數(shù)目，是典型的組合優(yōu)化問題。水平約簡是通過對對象的分析(包括離散化、泛化等)，合并具有相同屬性值的對象，減少對象數(shù)目。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)變換決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘階段：應(yīng)用相關(guān)算法從準(zhǔn)備好的數(shù)據(jù)中尋找數(shù)據(jù)中隱含的對信息利用如預(yù)測、決策等有價值的模式。需要考慮的問題：任務(wù)的確定：分類、聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)等。方法的選擇：統(tǒng)計方法、機(jī)器學(xué)習(xí)方法、不確定性方法、數(shù)據(jù)庫技術(shù)等。是知識發(fā)現(xiàn)的核心，也是被研究最廣泛的內(nèi)容。數(shù)據(jù)挖掘方法很多，需要我們對它們的適用條件、前提假設(shè)有充分的了解。運(yùn)行效率分析：不同的算法其效率存在很大差異。算法設(shè)計與選擇往往就是精度與效率之間的權(quán)衡。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘任務(wù)及常采用的方法：歸納總結(jié)：從泛化的角度總結(jié)數(shù)據(jù)，即從低層次數(shù)據(jù)抽象出高層次的描述的過程。主要方法：歸納學(xué)習(xí)。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則：關(guān)聯(lián)規(guī)則的形式為A→B，A為前件，B為后件。(Day=Friday)and(Product=Nappies)→(Product=Beer)為一典型關(guān)聯(lián)規(guī)則

A為滿足前件的對象集，B為滿足后件的對象，N為全部對象集。典型方法：Apriori算法。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念分類(等價關(guān)系，判別)：按類標(biāo)簽(為數(shù)據(jù)庫中的某屬性集，一般僅包含一個屬性)對數(shù)據(jù)庫中的對象進(jìn)行分類，具有相同標(biāo)簽值或標(biāo)簽值在指定區(qū)間內(nèi)的對象屬于同類。分類規(guī)則是判斷某個對象屬于某類的充分條件即對象具有某類的屬性時則表示該對象屬于該類。其規(guī)則形式一般為IFLogicExpThenA類ElseB類。主要方法：邏輯回歸、判別分析、決策樹、ANN、粗糙集、SVM等。聚類(相容關(guān)系)：聚類也叫分段，就是將數(shù)據(jù)庫中的實(shí)體分成若干組或簇，每簇內(nèi)的實(shí)體是相似的。規(guī)則形式為IFO1與O2相似ThenO1、O2在同一簇。對象相似的判斷方法有多種如距離法。典型方法：K-means決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念分類(等決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念發(fā)現(xiàn)特征規(guī)則：特征規(guī)則是刻劃某個概念的特征的斷言，它相當(dāng)于分類規(guī)則的逆命題。例如病癥是某種疾病的特征。規(guī)則一般形式是：IFA類Then特征表達(dá)式。序列模式發(fā)現(xiàn)：它與關(guān)聯(lián)規(guī)則相似，不同之處在于事件的發(fā)生有前后順序，該規(guī)則一般形式為：At(i)→Bt(j)

其中t(i)<t(j)。例如序貫規(guī)則JacketandTie→Shoes表示客戶在買了“夾克”和“領(lǐng)帶”之后就會買“鞋”。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念發(fā)現(xiàn)特征決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念偏離探測：探測測量值與期望值之間的差別并對其進(jìn)行解釋。常有三種偏離類型：隨時間偏離(以歷史值為期望值)、與標(biāo)準(zhǔn)偏離(以標(biāo)準(zhǔn)值為期望值)、與預(yù)測偏離(以預(yù)測值為期望值)?；貧w：根據(jù)歷史數(shù)據(jù)擬合一函數(shù)將屬性集映射到相應(yīng)的值集?；貧w可以看作一種分類，區(qū)別是分類的類標(biāo)簽值是離散的，而回歸是連續(xù)的。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念偏離探測決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念neurallinerprofit010005000mins

回歸模型m-male，f-femalemfmmmmmmmfmmmmmmmmmffmmmmmmmmmmmfmmmmmmmmmmmmmmmmmmmf16K64K32K20304050ageincome聚類模型決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念neur決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘方法DataMining統(tǒng)計方法·相關(guān)分析·線性回歸·主成分分析·聚類分析數(shù)據(jù)庫技術(shù)·面向數(shù)據(jù)集方法·面向?qū)傩詺w納·數(shù)據(jù)庫統(tǒng)計機(jī)器學(xué)習(xí)·規(guī)則歸納·基于案例推理·遺傳算法·神經(jīng)網(wǎng)絡(luò)不確定性理論·貝葉斯網(wǎng)絡(luò)·模糊邏輯·粗糙集理論·證據(jù)理論可視化技術(shù)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念數(shù)據(jù)挖掘決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念解釋與評價階段：結(jié)果篩選：過濾(移去)不感興趣的或顯而易見的模式。利用描述規(guī)則特征的數(shù)值如信度、支持度或興趣度等，定義某個閾值，對規(guī)則進(jìn)行篩選；指定語義約束，規(guī)則的前件或后件只包含感興趣的屬性，或者指定屬性間的依賴性約束；完全依靠用戶對處理結(jié)果進(jìn)行篩選。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念解釋與評決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念結(jié)果評價：確定所發(fā)現(xiàn)模式的可信度。基本方法是將樣本數(shù)據(jù)集分成二部分，一部分是訓(xùn)練集用來發(fā)現(xiàn)模式，另一部分是測試集，分析結(jié)果的可信度。處理結(jié)果維護(hù)：信息處理所涉及的樣本數(shù)據(jù)集常常是動態(tài)變化的，因此需要對所處理的結(jié)果進(jìn)行維護(hù)以保證結(jié)果與數(shù)據(jù)的變化相一致。維護(hù)可以對數(shù)據(jù)變化引起的特殊問題重新應(yīng)用所建立的處理方法，或者應(yīng)用某種增量處理算法。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—基本概念結(jié)果評價決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—空值估算空值是指屬性值未知且不可用、與其它任何值都不相同的符號。在樣本數(shù)據(jù)集中，空值在所有非主碼屬性中都可能出現(xiàn)?？罩党霈F(xiàn)的主要原因：在信息收集時忽略了一些認(rèn)為不重要的數(shù)據(jù)或信息提供者不愿意提供，而這些數(shù)據(jù)對以后的信息處理可能是有用的；某些屬性值未知；數(shù)據(jù)模型的限制。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—空值估算空值是指決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—空值估算空值處理的常用方法：從訓(xùn)練集中移去含未知值的實(shí)例；用某個最可能的值進(jìn)行替換；基于樣本中其它屬性的取值和分類信息，構(gòu)造規(guī)則來預(yù)測丟失的數(shù)據(jù)，并用預(yù)測結(jié)果“填補(bǔ)”丟失值；應(yīng)用貝葉斯公式確定未知值的概率分布，選擇一最可能的值填補(bǔ)空值或根據(jù)概率分布用不同值填補(bǔ)空值形成多個對象；將含有未知值的一個給定樣本數(shù)據(jù)集轉(zhuǎn)換成一個新的、可能不相容的但每個屬性值均已知的數(shù)據(jù)集，方法是將某個屬性的未知值用所有該屬性的可能值替換形成多個數(shù)據(jù)集。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—空值估算空值處理決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化問題描述

設(shè)為一樣本數(shù)據(jù)集，為非空有限集合，C是條件屬性集，D是決策屬性集。假設(shè)對于任意有，R是實(shí)數(shù)集，則為連續(xù)屬性。設(shè)是上的分割點(diǎn)集合，記為其中，為一整數(shù)，表示離散化程度，可以看作按屬性將論域中的對象分成類。3kiki-121……決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化問決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化對于需要離散化的連續(xù)屬性集，其分割點(diǎn)集合記為將ci屬性的連續(xù)取值映射到離散空間，即對于任意若其屬性ci

的取值在區(qū)間內(nèi)，則將屬性值重新標(biāo)記為j。這樣就把原來含有連續(xù)屬性的樣本數(shù)據(jù)集A轉(zhuǎn)換成離散化的數(shù)據(jù)集。因此離散化問題本質(zhì)上可歸結(jié)為利用選取的分割點(diǎn)對屬性的值域空間進(jìn)行劃分的問題。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化對決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化離散化方法典型的有等區(qū)間方法、等信息量方法、基于信息熵的方法、Holte的1R離散化方法、統(tǒng)計試驗(yàn)方法、超平面搜索方法以及用戶自定義區(qū)間等。應(yīng)用不同的準(zhǔn)則可將現(xiàn)有的離散化方法分為局部與全局方法(論域空間)、靜態(tài)與動態(tài)方法(屬性空間)和有導(dǎo)師與無導(dǎo)師方法(是否依賴決策屬性)。(1)等區(qū)間離散化方法等區(qū)間分割是將連續(xù)屬性的值域等分成()個區(qū)間,一般由用戶確定。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化離決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化

假設(shè)某個屬性的最大屬性值為xmax，最小屬性值為xmin，用戶給定的分割點(diǎn)參數(shù)為k，則分割點(diǎn)間隔為δ=(xmax-xmin)/k，所得到的屬性分割點(diǎn)為xmin+i

，i=1,2,…,k。(2)等信息量離散化方法等信息量分割首先將測量值進(jìn)行排序，然后將屬性值域分成k個區(qū)間，每個區(qū)間包含相同數(shù)量的測量值。假設(shè)某個屬性的最大屬性值為xmax

，最小屬性值為xmin

，用戶給定的分割點(diǎn)參數(shù)為k，樣本集中的對象個數(shù)為n，則需要將樣本集中的對象按該屬性的取值從小到大排列，然后按對象數(shù)平均劃分為k段即得到分割點(diǎn)集，每兩個相鄰分割點(diǎn)之間的對象數(shù)均為n/k。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化(3)統(tǒng)計試驗(yàn)方法統(tǒng)計試驗(yàn)方法根據(jù)決策屬性分析區(qū)間劃分之間的獨(dú)立程度，確定分割點(diǎn)的有效性。對于任意分割點(diǎn)，均可將分成2個區(qū)間和，兩區(qū)間的獨(dú)立程度為：其中：r是決策類數(shù)目nij是在第l區(qū)間中屬于第j決策類的對象數(shù)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化(決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化

若，則取基于統(tǒng)計試驗(yàn)的離散化方法是將值較大的分割點(diǎn)作為有效分割點(diǎn)。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—連續(xù)屬性離散化決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(Apriori算法)TheApriorimethod:ProposedbyAgrawal&Srikant1994Majoridea:AsubsetofafrequentitemsetmustbefrequentE.g.,if{beer,diaper,nuts}isfrequent,{beer,diaper}mustbe.Anyoneisinfrequent,itssupersetcannotbe!Apowerful,scalablecandidatesetpruningtechnique:Itreducescandidatek-itemsetsdramatically(fork>2)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(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%決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(Apriori算法)ProcedureFindthefrequentitemsets:thesetsofitemsthathaveminimumsupport(Apriori)Asubsetofafrequentitemsetmustalsobeafrequentitemset,i.e.,if{A

B}is

afrequentitemset,both{A}and{B}shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok(k-itemset)Usethefrequentitemsetstogenerateassociationrules.決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(Apriori算法)AlgorithmJoinStepCk

isgeneratedbyjoiningLk-1withitselfPruneStepAny(k-1)-itemsetthatisnotfrequentcannotbeasubsetofafrequentk-itemset,henceshouldberemoved.(Ck:Candidateitemsetofsizek)(Lk:frequentitemsetofsizek)決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(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;決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(Apriori算法)DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—關(guān)聯(lián)規(guī)則發(fā)現(xiàn)(A決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)聚類分析是把研究對象按照一定的規(guī)則分成若干類別，并使類之間的差別盡可能地大，類內(nèi)的差別盡可能地小，換句話說，使類間的相似性最小、而類內(nèi)的相似性最大。聚類方法的核心問題是樣品間的相似性度量，通常用距離來度量。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)聚類分析中的常用距離(1)歐氏(Euclidean)距離(2)絕對距離(3)Minkowski距離顯然當(dāng)m=1時就是絕對距離，m=2時就是歐氏距離。在實(shí)際應(yīng)用時常分析兩個樣品之間的相對距離，這時需要對樣品數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后用標(biāo)準(zhǔn)化數(shù)據(jù)計算距離。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)對于給定的n個樣品，先粗略地形成k(k≤n)個分割，使得每個分割對應(yīng)一個類、每個類至少有一個樣品并且每個樣品精確地屬于一個類，然后按照某種原則進(jìn)行修正，直至分類比較合理為止。具體步驟如下：(1)聚點(diǎn)的選擇：聚點(diǎn)是一批有代表性的樣品，它的選擇決定了初始分類。首先確定分類數(shù)k，然后選擇k個有代表性的樣品作為每個類的初始元素即聚點(diǎn)。聚點(diǎn)可由用戶根據(jù)經(jīng)驗(yàn)選擇，也可將全部樣品人為地或隨機(jī)地分成k類，以每類的重心作為聚點(diǎn)。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)聚點(diǎn)的最小最大原則選擇法：①設(shè)將n個樣品分成k類，先選擇所有樣品中相距最遠(yuǎn)的兩個樣品為前兩個聚點(diǎn)，因此有②設(shè)已經(jīng)找到了l個(2≤l＜k)聚點(diǎn)，則第l+1個聚點(diǎn)的選擇方法是使得與前l(fā)個聚點(diǎn)的距離最小者等于所有其余的與前l(fā)個聚點(diǎn)的較小距離的最大者，直至選定k個聚點(diǎn)，即將所獲得的k個聚點(diǎn)的集合記為決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)(2)初始聚類有了聚點(diǎn)集合后，可根據(jù)下列最靠近原則實(shí)現(xiàn)初始分類：若對于某樣品x出現(xiàn)，則x任意歸于Gi(0)

或Gj(0)

類。這樣就得到了樣品空間的初始分類：決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)(3)迭代過程設(shè)聚類形成的一個分類為則可從G(m)出發(fā)計算新的聚點(diǎn)集合L(m+1)。一般可以以G(m)中各類的重心作為新的聚點(diǎn)。其中根據(jù)新的聚點(diǎn)集，對樣品空間重新聚類，形成新的分類：其中決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-means算法)(4)迭代終止隨著m的增大，分類趨于穩(wěn)定。當(dāng)G(m+1)=G(m)或在一定的精度范圍內(nèi)近似有G(m+1)=G(m)，則遞推過程結(jié)束。決策理論與方法-智能決策理論與方法知識發(fā)現(xiàn)—聚類(K-mea決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能決策理論的形成背景2、知識發(fā)現(xiàn)3、粗糙集理論4、機(jī)器學(xué)習(xí)決策理論與方法-智能決策理論與方法智能決策理論與方法1、智能粗糙集理論(RoughSetTheory)預(yù)備知識——相關(guān)名詞解釋論域：研究對象的全體成員構(gòu)成的集合，一般用字母U表示；若X

U，則稱X是U的子集隸屬度：描述一個對象x與某個子集X之間的隸屬程度，一般用符號

表示，若xX,則

=1;若,則

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

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

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

分類能力受主體分辨能力的影響，因此分類具有近似性

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

(屬性重要性：屬性約簡)具有相同屬性的實(shí)體，屬性取值的不同對分類能力也產(chǎn)生影響

(值重要性：值約簡)屬性之間存在某種依賴關(guān)系(決策規(guī)則)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——信息系統(tǒng)與知識信息系統(tǒng)I可以定義為四元組<U,A,V,f>，其中有限非空集合U是論域，A為關(guān)于U的屬性集，，Va表示屬性a的值域，映射f:U×A→V表示對

x

U，a

A，有：f(x,a)

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

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——信息系統(tǒng)與知識A的任何一個子集B確定一個U上的二元關(guān)系IND(B)：對于任意a

B，xIND(B)y

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

U；a(x)表示對象x的a屬性值。則稱IND(B)為不可分辨關(guān)系(?)。IND(B)是等價關(guān)系，IND(B)的所有等價類的集合記為U/B（稱為知識B），含有元素x的等價類記為B(x)或[x]B，同一等價類中的元素是不可分辨的，稱IND(B)等價類為初等集（范疇），它是知識庫的基本結(jié)構(gòu)單元即概念。設(shè)R是由屬性集A的子集誘導(dǎo)的論域U上的等價關(guān)系族，則稱R為U上的一個知識庫，記為K=(U,R)。粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集與近似對于U的任意子集X，若X恰能由知識R的若干個初等集的并構(gòu)成，則稱X為R-精確集，否則為R-粗糙集。每個粗糙集X都可用兩個與之相關(guān)的精確集近似表示即X的上近似和下近似，他們是粗糙集理論的兩個最基本運(yùn)算。粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集與近似下近似由所有包含于X的初等集合的并構(gòu)成，X的下近似中的元素一定屬于X。上近似由與X的交為非空的初等集合的并構(gòu)成，而上近似中的元素可能屬于X。上近似與下近似的差為邊界域，粗糙集的邊界域?yàn)榉强?，否則為精確集。邊界域中的元素根據(jù)可用知識沒有確定的分類，即它既不能劃分到X中也不能劃分到X的補(bǔ)集中。正域與負(fù)域粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——經(jīng)典粗糙集模型論域U粗糙集X粗糙集X粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(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粗糙集，X1的R3下近似是{p1,p3,p6}，R3上近似是{p1,p2,p3,p5,p6}，邊界域?yàn)閧p2,p5}；X2={p4,p5}也是R3粗糙集，X2的R3下近似是{p4}，X2的R3上近似是{p2,p4,p5}，而邊界域是{p2,p5}。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集數(shù)字特征精度：X的R精度反映了我們對于了解集合X的知識的完全程度。αR(X)=1為精確集，0≤αR(X)<1為粗糙集。粗糙度：X的R粗糙度反映了我們對于了解集合X的知識的不完全程度。(精度與概率或隸屬度的區(qū)別)隸屬度：是根據(jù)可用知識R，對象x隸屬于概念X的條件概率。粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集數(shù)字特征設(shè)F={X1，X2，…，Xn}是論域U上的一個劃分，那么根據(jù)知識R，F(xiàn)的分類精度如何？F的近似精度：分類的近似精度給出了根據(jù)現(xiàn)有知識對對象進(jìn)行分類時可能正確的決策的百分?jǐn)?shù)。F的近似質(zhì)量：近似質(zhì)量給出了能正確分類的百分?jǐn)?shù)。這是一個非常重要的特征數(shù)字，它反映了兩種分類F和R之間的關(guān)系。如果將R看作決策表中的條件屬性集，F(xiàn)看成決策屬性集，近似質(zhì)量反映了兩者之間的依賴關(guān)系。粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集數(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粗糙集，X1的R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}，R精度為0.6；R粗糙度為0.4；

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

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——粗糙集數(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粗糙集，X1的R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}；

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

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——知識依賴為了尋找“IF……THEN”形式的推理規(guī)則，在粗糙集理論體系中所采用的方法是從一個給定的知識，推導(dǎo)另一個知識。如果知識D的所有初等范疇都能用知識C的某些初等范疇來定義，則稱知識D可由知識C推得，也稱D完全依賴于C，記為C

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

C，則D的B正域定義為：D的B正域表示利用知識B，能正確地劃分到U/D各等價類中的所有對象的集合粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——知識依賴設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，①D完全依賴于C當(dāng)且僅當(dāng)②D等價于C當(dāng)且僅當(dāng)(C

D)

(D

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

(C

D)

(D

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

k

1)度依賴于C，記為C

kD。粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(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粗糙集，X1的R3下近似是{p1,p3,p6}，R3上近似是{p1,p2,p3,p5,p6}；X2={p4,p5}也是R3粗糙集，X2的R3下近似是{p4}，X2的R3上近似是{p2,p4,p5}。F的R3正域是{p1,p3,p4,p6},所以F對R3的依賴度是2/3。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY條件屬性子集{T1}{T2}{T3}{T1,T2}{T1,T3}{T2,T3}{T1,T2,T3}依賴度k001/21/62/32/32/3粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)粗糙集理論(RoughSetTheory)粗糙集理論的經(jīng)典模型——知識約簡為什么要約簡知識？判別：根據(jù)條件屬性取值確定對象所屬的類。實(shí)際：確定對象所屬的類只需其中幾個屬性甚至一個屬性，而不需要知道對象所有的屬性，這與人類對實(shí)體的識別是一致的。表明：不同屬性在分類時所起的作用是不同的。什么是知識約簡？將知識庫中某些不必要的等價關(guān)系（知識）移去的過程。設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，B

C，若

C(D)=

B(D)且B是D獨(dú)立的，則B為C的D約簡，記為REDD(C)。C的D約簡是不含任何冗余知識且與C具有相同分類能力的子集（用知識C將對象劃分到知識D的初等范疇中的能力