智能決策理論與方法講義

決議理論與方法(4)

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

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

，i=1,2,…,k。(2)等信息量離散化方法等信息量分割首先將測量值進(jìn)行排序，然后將屬性值域分成k個區(qū)間，每個區(qū)間包含相同數(shù)量測量值。假設(shè)某個屬性最大屬性值為xmax，最小屬性值為xmin，用戶給定分割點參數(shù)為k，樣本集中對象個數(shù)為n，則需要將樣本集中對象按該屬性取值從小到大排列，然后按對象數(shù)平均劃分為k段即得到分割點集，每兩個相鄰分割點之間對象數(shù)均為n/k。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第30頁知識發(fā)覺—連續(xù)屬性離散化(3)統(tǒng)計試驗方法統(tǒng)計試驗方法依據(jù)決議屬性分析區(qū)間劃分之間獨立程度，確定分割點有效性。對于任意分割點，均可將分成2個區(qū)間和，兩區(qū)間獨立程度為：其中：r是決議類數(shù)目nij是在第l區(qū)間中屬于第j決議類對象數(shù)決議理論與方法-智能決議理論與方法智能決策理論與方法講義第31頁知識發(fā)覺—連續(xù)屬性離散化若，則取基于統(tǒng)計試驗離散化方法是將值較大分割點作為有效分割點。決議理論與方法-智能決議理論與方法智能決策理論與方法講義第32頁知識發(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頁知識發(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頁知識發(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頁知識發(fā)覺—關(guān)聯(lián)規(guī)則發(fā)覺(Apriori算法)AlgorithmJoinStepCk

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

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

表示，若xX,則

=1;若,則

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

慣用某個函數(shù)加以描述，稱為隸屬度函數(shù))高斯函數(shù)粗糙集理論(RoughSetTheory)智能決策理論與方法講義第47頁預(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商集，它組成了U一個劃分，記為U/R。概念：含有相同特征值一群對象稱為一個概念（一個等價類就是一個概念）粗糙集理論(RoughSetTheory)智能決策理論與方法講義第48頁預(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)智能決策理論與方法講義第49頁預(yù)備知識——組員集合組員：明確隸屬關(guān)系含糊組員：概念含糊(如青年)造成組員含糊粗糙組員：概念清楚(如感冒)，組員含糊(是否感冒不清楚)，含有概率特征(隸屬函數(shù))，但不是概率問題，只是因為依據(jù)可用知識無法得到準(zhǔn)確結(jié)論。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第50頁粗糙集理論經(jīng)典模型——RST提出粗糙集理論由Pawlak提出[1982,1991]。粗糙集理論反應(yīng)了人們以不完全信息或知識去處理一些不可分辨現(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頁粗糙集理論經(jīng)典模型——基本思想知識是主體對論域中客體進(jìn)行分類能力，分類能力越強(qiáng)，主體所具備知識可靠度越高

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

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

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

(值主要性：值約簡)屬性之間存在某種依賴關(guān)系(決議規(guī)則)粗糙集理論(RoughSetTheory)智能決策理論與方法講義第52頁粗糙集理論經(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)智能決策理論與方法講義第53頁粗糙集理論經(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)表示對象xa屬性值。則稱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)智能決策理論與方法講義第54頁粗糙集理論經(jīng)典模型——粗糙集與近似對于U任意子集X，若X恰能由知識R若干個初等集并組成，則稱X為R-準(zhǔn)確集，不然為R-粗糙集。每個粗糙集X都可用兩個與之相關(guān)準(zhǔn)確集近似表示即X上近似和下近似，他們是粗糙集理論兩個最基本運(yùn)算。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第55頁粗糙集理論經(jīng)典模型——粗糙集與近似下近似由全部包含于X初等集合并組成，X下近似中元素一定屬于X。上近似由與X交為非空初等集合并組成，而上近似中元素可能屬于X。上近似與下近似差為邊界域，粗糙集邊界域為非空，不然為準(zhǔn)確集。邊界域中元素依據(jù)可用知識沒有確定分類，即它既不能劃分到X中也不能劃分到X補(bǔ)集中。正域與負(fù)域粗糙集理論(RoughSetTheory)智能決策理論與方法講義第56頁粗糙集理論經(jīng)典模型——經(jīng)典粗糙集模型論域U粗糙集X粗糙集X粗糙集理論(RoughSetTheory)智能決策理論與方法講義第57頁粗糙集理論經(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}，邊界域為{p2,p5}；X2={p4,p5}也是R3粗糙集，X2R3下近似是{p4}，X2R3上近似是{p2,p4,p5}，而邊界域是{p2,p5}。T1

T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY粗糙集理論(RoughSetTheory)智能決策理論與方法講義第58頁粗糙集理論經(jīng)典模型——粗糙集數(shù)字特征精度：XR精度反應(yīng)了我們對于了解集合X知識完全程度。αR(X)=1為準(zhǔn)確集，0≤αR(X)<1為粗糙集。粗糙度：XR粗糙度反應(yīng)了我們對于了解集合X知識不完全程度。(精度與概率或隸屬度區(qū)分)隸屬度：是依據(jù)可用知識R，對象x隸屬于概念X條件概率。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第59頁粗糙集理論經(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ù)字，它反應(yīng)了兩種分類F和R之間關(guān)系。假如將R看作決議表中條件屬性集，F(xiàn)看成決議屬性集，近似質(zhì)量反應(yīng)了二者之間依賴關(guān)系。粗糙集理論(RoughSetTheory)智能決策理論與方法講義第60頁粗糙集理論經(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粗糙集，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頁粗糙集理論經(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粗糙集，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頁粗糙集理論經(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，則DB正域定義為：DB正域表示利用知識B，能正確地劃分到U/D各等價類中全部對象集合粗糙集理論(RoughSetTheory)智能決策理論與方法講義第63頁粗糙集理論經(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獨立于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)智能決策理論與方法講義第64頁粗糙集理論經(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}；X2={p4,p5}也是R3粗糙集，X2R3下近似是{p4}，X2R3上近似是{p2,p4,p5}。FR3正域是{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)智能決策理論與方法講義第65頁粗糙集理論經(jīng)典模型——知識約簡為何要約簡知識？判別：依據(jù)條件屬性取值確定對象所屬類。實際：確定對象所屬類只需其中幾個屬性甚至一個屬性，而不需要知道對象全部屬性，這與人類對實體識別是一致。表明：不一樣屬性在分類時所起作用是不一樣。什么是知識約簡？將知識庫中一些無須要等價關(guān)系（知識）移去過程。設(shè)信息系統(tǒng)I=<U,C∪D,V,f>，B

C，若

C(D)=

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