【正文】 決策理論與方法 —— 不確定性決策理論與方法 合肥工業(yè)大學(xué)管理學(xué)院 2023年 3月 4日 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 不確定性決策 ? 不確定性決策 ： 指難以獲得各種狀態(tài)發(fā)生的概率，甚至對(duì)未來狀態(tài)都難以把握的決策問題。 ? 特點(diǎn) ：狀態(tài)的不確定性。 ? 不確定性 ： 不確定性來自人類的主觀認(rèn)識(shí)與客觀實(shí)際之間存在的差異。事物發(fā)生的隨機(jī)性、人類知識(shí)的不完全、不可靠、不精確和不一致以及自然語言中存在的模糊性和歧義性，都反映了這種差異，都會(huì)帶來不確定性。不確定性就造成了具有相同描述信息的對(duì)象可能屬于不同概念。 ? 解決問題的主要理論方法 ：人工智能與不確定性理論 不確定性決策準(zhǔn)則 ? 在決策者無法獲取狀態(tài)的概率時(shí)，貝葉斯決策準(zhǔn)則就難以湊效。下面介紹幾種常用的不確定性決策準(zhǔn)則。 ? 悲觀準(zhǔn)則或極小化極大準(zhǔn)則 【 Wald,1950】 ? 考察采取行動(dòng) ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最壞后果，即最大損失 si或 最小效用 ui； ? 選擇行動(dòng) ak，使得 sk(uk)在所有行動(dòng)中最小 (最大 )。 ? 樂觀準(zhǔn)則 ? 考察采取行動(dòng) ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最好后果，即最小損失 oi或 最大效用 vi； ? 選擇行動(dòng) ak，使得 ok(vk)在所有行動(dòng)中最小 (最大 )。 不確定性決策準(zhǔn)則 ? 樂觀系數(shù)法 【 Hurwicz,1951】 ? 考察采取行動(dòng) ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最壞后果和最好后果，即最大損失 si和最小損失 oi或 最小效用 ui和 最大效用 vi ； ? 設(shè)決策人的樂觀系數(shù)為 ?，則 選擇行動(dòng) ak，使得 (1 ?)sk+ ?ok((1 ?)uk+ ?vk)在所有行動(dòng)中最小 (最大 )。 不確定性決策準(zhǔn)則 ? 后悔值極小化極大法 【 Savage,1951】 ? 在狀態(tài) θj下考察采取行動(dòng) ai的損失 lji或 效用 uji和，并將其與在此狀態(tài)下采取不同行動(dòng)時(shí)的最小損失 sj或 最大效用 uj進(jìn)行比較，其差值的大小定義為后悔值 rji，從而形成一個(gè)后悔值表； ? 針對(duì)后悔值表，應(yīng)用悲觀準(zhǔn)則求解：找出不同狀態(tài)下采取行動(dòng) ai的最大后悔值 pi，然后再使所有行動(dòng)的最大后悔值極小，其所對(duì)應(yīng)的行動(dòng)記為決策結(jié)果。 不確定性決策準(zhǔn)則 ? 等概率法 【 Laplace,1825】 ? Laplace認(rèn)為，對(duì)真實(shí)的自然狀態(tài)一無所知 等價(jià)于 所有自然狀態(tài)具有相同的概率。 ? 然后借助于貝葉斯準(zhǔn)則進(jìn)行決策。 不確定性決策準(zhǔn)則 ? 不確定性決策問題舉例 【 Milnor,1954】 a1 a2 a3 a4 θ1 2 3 4 3 θ2 2 3 0 1 θ3 4 3 4 4 θ4 3 3 4 4 不確定性決策準(zhǔn)則 ? 不確定性決策問題舉例 【 Milnor,1954】 a1 a2 a3 a4 最小損失 后悔值 a1 a2 a3 a4 θ1 2 3 4 3 2 0 1 2 1 θ2 2 3 0 1 0 2 3 0 1 θ3 4 3 4 4 3 1 0 1 1 θ4 3 3 4 4 3 0 0 1 1 最大損失 （悲觀） 4 3 4 4 a2 最大后悔值 pi 2 3 2 1 最小損失 （樂觀） 2 3 0 1 a3 a4 樂觀系數(shù) 42? 3 44? 43? ?， a2； ?， a3 等 概 率 a1 不確定性決策準(zhǔn)則 公理 悲觀準(zhǔn)則 樂觀系數(shù) 后悔值 等概率 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 智能決策理論與方法 — 形成背景 ? 人類面臨越來越復(fù)雜的決策任務(wù)和決策環(huán)境 ： ? 決策問題所涉及的變量規(guī)模越來越大； ? 決策所依賴的信息具有不完備性、模糊性、不確定性等特點(diǎn)，使得決策問題難以準(zhǔn)確地量化表示； ? 某些決策問題及其目標(biāo)可能是模糊的、不確定的，使得決策者對(duì)自己的偏好難以明確，隨著決策分析的深入，對(duì)決策問題的認(rèn)知加深，自己原有的偏好 /傾向得到不斷地修正，使得決策過程出現(xiàn)不斷調(diào)整的情況。 ? 這時(shí)，傳統(tǒng)的決策數(shù)學(xué)模型已經(jīng)難以勝任求解復(fù)雜度過高的決策問題、含有不確定性的決策問題以及半結(jié)構(gòu)化、非結(jié)構(gòu)化的決策問題，因而產(chǎn)生了智能決策理論、方法及技術(shù)。 智能決策理論與方法 — AI的應(yīng)用模式 ? 智能決策方法 是應(yīng)用人工智能 (Artificial Intelligence, AI)相關(guān)理論方法，融合傳統(tǒng)的決策數(shù)學(xué)模型和方法而產(chǎn)生的具有智能化推理和求解的決策方法，其典型特征是能夠在不確定、不完備、模糊的信息環(huán)境下，通過應(yīng)用符號(hào)推理、定性推理等方法，對(duì)復(fù)雜決策問題進(jìn)行建模、推理和求解。 AI應(yīng)用于決策科學(xué)主要有兩種模式 ： ? 針對(duì)可建立精確數(shù)學(xué)模型的決策問題，由于問題的復(fù)雜性，如組合爆炸、參數(shù)過多等而無法獲得問題的解析解，需要借助 AI中的智能搜索算法獲得問題的數(shù)值解； ? 針對(duì)無法建立精確數(shù)學(xué)模型的不確定性決策問題、半結(jié)構(gòu)化或非結(jié)構(gòu)化決策問題，需要借助 AI方法建立相應(yīng)的決策模型并獲得問題的近似解。 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) ? 智能決策的核心是如何獲取支持決策的信息和知識(shí)。 ? 問題 ? 知識(shí)獲取是基于知識(shí)的系統(tǒng) (KBS)的最大瓶頸 推理機(jī) 知識(shí)工程師 領(lǐng)域?qū)＜? 決策者 知識(shí)庫(kù) 問題請(qǐng)求 推理結(jié)果 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) ? 問題 ? 推理規(guī)則的獲取與 KBS中知識(shí)獲取一樣難，因而基于案例推理 (CaseBased Reasoning)漸漸變成基于案例檢索 (CaseBased Retrieving)。 推理機(jī) 決策者 案例庫(kù) 問題請(qǐng)求 推理結(jié)果 規(guī)則庫(kù) 知識(shí)工程師 領(lǐng)域?qū)＜? 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) 決策者 數(shù)據(jù)分析師 數(shù)據(jù)中心 不一定滿意的決策 決策支持查詢 查詢結(jié)果 ? 問題 ? 數(shù)據(jù)分析師與決策者之間對(duì)問題的理解存在偏差 ? 缺少有創(chuàng)造性的決策建議 ? 技術(shù)問題：如查詢效率 (RDBMS) 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) 推理機(jī) 數(shù)據(jù)挖掘工具 數(shù)據(jù)中心 決策者 知識(shí)庫(kù) 問題請(qǐng)求 推理結(jié)果 背景知識(shí) 領(lǐng)域?qū)＜? ? 優(yōu)點(diǎn) ? 知識(shí)獨(dú)立于問題本身 ? 知識(shí)的獲取主要通過數(shù)據(jù)挖掘?qū)崿F(xiàn) ? 有創(chuàng)造性收獲 Data Mining within the DSS 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) ? KDD帶來的新問題 ?知識(shí)發(fā)現(xiàn)問題：如何從數(shù)據(jù)中將知識(shí)挖掘出來？面臨許多技術(shù)問題： 如 數(shù)據(jù)異構(gòu)問題 、 數(shù)據(jù)具有噪音且信息不完整、使用什么樣的挖掘算法、知識(shí)如何表示等 ?知識(shí)評(píng)價(jià)問題： 數(shù)據(jù)本身具有權(quán)威性、客觀性，但知識(shí)不具備。知識(shí)如何評(píng)價(jià)？ 參考書推薦 KDD DM ? 知識(shí)發(fā)現(xiàn) (Knowledge Discovery in Databases ,KDD) 是指從大量數(shù)據(jù)中提取有用的 (useful)、新穎的 (novel)、有效的 (valid)并最終能被人理解 (understandable)的模式(patterns)的處理過程 (process)。 ? 數(shù)據(jù)挖掘 (Data Mining， DM) 是 KDD的核心階段 , 通過實(shí)施相關(guān)算法獲得期望的模式。 KDD過程 理解、定義用戶的目標(biāo)和KDD運(yùn)行的環(huán)境。 KDD過程 （ 1）選取可用的數(shù)據(jù)； （ 2）定義附加的、必須的數(shù)據(jù)，如領(lǐng)域知識(shí)； （ 3）數(shù)據(jù)集成為一個(gè)數(shù)據(jù)集，供 KDD使用。 KDD過程 （ 1）缺失值處理 （ 2）剔除噪聲或異常數(shù)據(jù) KDD過程 （ 1）維數(shù)約簡(jiǎn) (特征選擇與抽取，數(shù)據(jù)采樣 ) （ 2）屬性轉(zhuǎn)換 (離散化和泛化 ) （ 3）數(shù)據(jù)編碼 KDD過程 (1)確定數(shù)據(jù)挖掘類型，如分類、聚類、回歸； (2) 選擇特定的方法； (3) 執(zhí)行數(shù)據(jù)挖掘算法。 KDD過程 評(píng)估和解釋所挖掘的模式，重點(diǎn)是可理解性、有用性 . KDD過程 與原有知識(shí)系統(tǒng)合并。 挑戰(zhàn) : 動(dòng)態(tài)與增量挖掘問題。 Taxonomy of Data Mining Methods Taxonomy of Data Mining Methods ? Verificationoriented (the system verifies the user‘s hypothesis): including the most mon methods of traditional statistics, like goodness of fit(擬合優(yōu)度 ) test, tests of hypotheses (假設(shè)檢驗(yàn) ， ., ttest of means), and analysis of variance (ANOVA， 方差分析或 F檢驗(yàn) ). ? Discoveryoriented (the system finds new rules and patterns autonomously): prediction methods VS description methods； supervised learning（ 有導(dǎo)師學(xué)習(xí) ） VS unsupervised learning Taxonomy of Data Mining Methods 分類 有監(jiān)督學(xué)習(xí) 無監(jiān)督學(xué)習(xí) 父母、老師教我們認(rèn)識(shí)世界的萬事萬物。 人類認(rèn)識(shí)新生事物。 標(biāo)簽化 Taxonomy of Data Mining Methods ? 有監(jiān)督學(xué)習(xí) ? 輸入： X={x1,...,xj,...,xN}。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對(duì)象 xj對(duì)應(yīng)的第 i個(gè)特征 (維度、屬性、變量 )的值。 ? 輸出： Y={C1,...,Ck,...,CK}。 Ck表示類標(biāo)簽。 ? 模型： Y=f(X,W)或 P(Y|X)=f(X,W)，將輸入 X映射成類標(biāo)簽 Y或 Y的概率分布。 W是可調(diào)整的參數(shù)向量。 ? 模型訓(xùn)練： 使用歸納學(xué)習(xí)方法 (經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 )確定模型的結(jié)構(gòu) f和參數(shù) W，訓(xùn)練樣本集為 (xi,yi)。 Taxonomy of Data Mining Methods ? 無監(jiān)督學(xué)習(xí) ? 無監(jiān)督分類 (聚類 )：應(yīng)用于無標(biāo)簽數(shù)據(jù)的分類，稱為聚類分析或探究性分析，其目標(biāo)是將無標(biāo)簽數(shù)據(jù)分類到有限、離散的“自然狀態(tài)”?！白匀粻顟B(tài)”隱藏了數(shù)據(jù)的結(jié)構(gòu)，而不是為未觀測(cè)的樣本提供一個(gè)精確刻畫 (描述而非預(yù)測(cè) )。 ? 無監(jiān)督預(yù)測(cè)學(xué)習(xí) (如關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、鏈接分析等 )：具有預(yù)測(cè)能力的無監(jiān)督學(xué)習(xí)。 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) ? 關(guān)聯(lián)規(guī)則 (Association Rules)：關(guān)聯(lián)規(guī)則的形式為A→B ， A為前件， B為后件。 (Day=Friday) and (Product= Diaper) → (Product=Beer) 為一典型關(guān)聯(lián)規(guī)則 A為滿足前件的對(duì)象集， B為滿足后件的對(duì)象， N為全部對(duì)象集。 典型方法： Apriori算法。 NBASupp ort || ??||||ABACon fide nce ??* 決策理論與方法 智能決策理論與方法 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Apriori算法由 Agrawal Srikant在 1994年提出 ? 主要思想 : ? 一個(gè)頻繁項(xiàng)集（支持度超過給定值的項(xiàng)集）的子集一定是頻繁的 ?例如， 若 {beer, diaper, nuts}是頻繁的 , 那么 {beer, diaper} 一定是頻繁的 . ? 任一項(xiàng)是非頻繁的，則包含該項(xiàng)的超集一定是不頻繁的。 ?例如， 若 {beer, diaper}是不頻繁的 , 那么 {beer, diaper, nuts}一定是不頻繁的 . 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Procedure ?Find the frequent itemsets: the sets of items that have mi