【正文】 動機(jī) ? 問題 ? 推理規(guī)則的獲取與 KBS中知識獲取一樣難，因而基于案例推理 (CaseBased Reasoning)漸漸變成基于案例檢索 (CaseBased Retrieving)。 AI應(yīng)用于決策科學(xué)主要有兩種模式 ： ? 針對可建立精確數(shù)學(xué)模型的決策問題，由于問題的復(fù)雜性，如組合爆炸、參數(shù)過多等而無法獲得問題的解析解，需要借助 AI中的智能搜索算法獲得問題的數(shù)值解； ? 針對無法建立精確數(shù)學(xué)模型的不確定性決策問題、半結(jié)構(gòu)化或非結(jié)構(gòu)化決策問題，需要借助 AI方法建立相應(yīng)的決策模型并獲得問題的近似解。 ? 這時(shí)，傳統(tǒng)的決策數(shù)學(xué)模型已經(jīng)難以勝任求解復(fù)雜度過高的決策問題、含有不確定性的決策問題以及半結(jié)構(gòu)化、非結(jié)構(gòu)化的決策問題，因而產(chǎn)生了智能決策理論、方法及技術(shù)。 ? 然后借助于貝葉斯準(zhǔn)則進(jìn)行決策。 不確定性決策準(zhǔn)則 ? 后悔值極小化極大法 【 Savage,1951】 ? 在狀態(tài) θj下考察采取行動 ai的損失 lji或 效用 uji和，并將其與在此狀態(tài)下采取不同行動時(shí)的最小損失 sj或 最大效用 uj進(jìn)行比較，其差值的大小定義為后悔值 rji，從而形成一個(gè)后悔值表； ? 針對后悔值表，應(yīng)用悲觀準(zhǔn)則求解：找出不同狀態(tài)下采取行動 ai的最大后悔值 pi，然后再使所有行動的最大后悔值極小，其所對應(yīng)的行動記為決策結(jié)果。 ? 樂觀準(zhǔn)則 ? 考察采取行動 ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最好后果，即最小損失 oi或 最大效用 vi； ? 選擇行動 ak，使得 ok(vk)在所有行動中最小 (最大 )。下面介紹幾種常用的不確定性決策準(zhǔn)則。不確定性就造成了具有相同描述信息的對象可能屬于不同概念。 ? 不確定性 ： 不確定性來自人類的主觀認(rèn)識與客觀實(shí)際之間存在的差異。決策理論與方法 —— 不確定性決策理論與方法 合肥工業(yè)大學(xué)管理學(xué)院 2023年 3月 4日 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 不確定性決策 ? 不確定性決策 ： 指難以獲得各種狀態(tài)發(fā)生的概率，甚至對未來狀態(tài)都難以把握的決策問題。 ? 特點(diǎn) ：狀態(tài)的不確定性。事物發(fā)生的隨機(jī)性、人類知識的不完全、不可靠、不精確和不一致以及自然語言中存在的模糊性和歧義性，都反映了這種差異，都會帶來不確定性。 ? 解決問題的主要理論方法 ：人工智能與不確定性理論 不確定性決策準(zhǔn)則 ? 在決策者無法獲取狀態(tài)的概率時(shí)，貝葉斯決策準(zhǔn)則就難以湊效。 ? 悲觀準(zhǔn)則或極小化極大準(zhǔn)則 【 Wald,1950】 ? 考察采取行動 ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最壞后果，即最大損失 si或 最小效用 ui； ? 選擇行動 ak，使得 sk(uk)在所有行動中最小 (最大 )。 不確定性決策準(zhǔn)則 ? 樂觀系數(shù)法 【 Hurwicz,1951】 ? 考察采取行動 ai， i=1,2,…,m 時(shí)可能出現(xiàn)的最壞后果和最好后果，即最大損失 si和最小損失 oi或 最小效用 ui和 最大效用 vi ； ? 設(shè)決策人的樂觀系數(shù)為 ?，則 選擇行動 ak，使得 (1 ?)sk+ ?ok((1 ?)uk+ ?vk)在所有行動中最小 (最大 )。 不確定性決策準(zhǔn)則 ? 等概率法 【 Laplace,1825】 ? Laplace認(rèn)為，對真實(shí)的自然狀態(tài)一無所知 等價(jià)于 所有自然狀態(tài)具有相同的概率。 不確定性決策準(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)可能是模糊的、不確定的，使得決策者對自己的偏好難以明確，隨著決策分析的深入，對決策問題的認(rèn)知加深，自己原有的偏好 /傾向得到不斷地修正，使得決策過程出現(xiàn)不斷調(diào)整的情況。 智能決策理論與方法 — AI的應(yīng)用模式 ? 智能決策方法 是應(yīng)用人工智能 (Artificial Intelligence, AI)相關(guān)理論方法，融合傳統(tǒng)的決策數(shù)學(xué)模型和方法而產(chǎn)生的具有智能化推理和求解的決策方法，其典型特征是能夠在不確定、不完備、模糊的信息環(huán)境下，通過應(yīng)用符號推理、定性推理等方法，對復(fù)雜決策問題進(jìn)行建模、推理和求解。 知識發(fā)現(xiàn) — 動機(jī) ? 智能決策的核心是如何獲取支持決策的信息和知識。 推理機(jī) 決策者 案例庫 問題請求 推理結(jié)果 規(guī)則庫 知識工程師 領(lǐng)域?qū)＜? 知識發(fā)現(xiàn) — 動機(jī) 決策者 數(shù)據(jù)分析師 數(shù)據(jù)中心 不一定滿意的決策 決策支持查詢 查詢結(jié)果 ? 問題 ? 數(shù)據(jù)分析師與決策者之間對問題的理解存在偏差 ? 缺少有創(chuàng)造性的決策建議 ? 技術(shù)問題：如查詢效率 (RDBMS) 知識發(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)造性收獲 Data Mining within the DSS 知識發(fā)現(xiàn) — 動機(jī) ? KDD帶來的新問題 ?知識發(fā)現(xiàn)問題：如何從數(shù)據(jù)中將知識挖掘出來？面臨許多技術(shù)問題： 如 數(shù)據(jù)異構(gòu)問題 、 數(shù)據(jù)具有噪音且信息不完整、使用什么樣的挖掘算法、知識如何表示等 ?知識評價(jià)問題： 數(shù)據(jù)本身具有權(quán)威性、客觀性，但知識不具備。 ? 數(shù)據(jù)挖掘 (Data Mining， DM) 是 KDD的核心階段 , 通過實(shí)施相關(guān)算法獲得期望的模式。 KDD過程 （ 1）選取可用的數(shù)據(jù)； （ 2）定義附加的、必須的數(shù)據(jù)，如領(lǐng)域知識； （ 3）數(shù)據(jù)集成為一個(gè)數(shù)據(jù)集，供 KDD使用。 KDD過程 評估和解釋所挖掘的模式，重點(diǎn)是可理解性、有用性 . KDD過程 與原有知識系統(tǒng)合并。 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)識世界的萬事萬物。 標(biāo)簽化 Taxonomy of Data Mining Methods ? 有監(jiān)督學(xué)習(xí) ? 輸入： X={x1,...,xj,...,xN}。 ? 輸出： Y={C1,...,Ck,...,CK}。 ? 模型： Y=f(X,W)或 P(Y|X)=f(X,W)，將輸入 X映射成類標(biāo)簽 Y或 Y的概率分布。 ? 模型訓(xùn)練： 使用歸納學(xué)習(xí)方法 (經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 )確定模型的結(jié)構(gòu) f和參數(shù) W，訓(xùn)練樣本集為 (xi,yi)?！白匀粻顟B(tài)”隱藏了數(shù)據(jù)的結(jié)構(gòu)，而不是為未觀測的樣本提供一個(gè)精確刻畫 (描述而非預(yù)測 )。 不確定性決策理論與方法 不確定性決策概述 關(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為后件。 典型方法： Apriori算法。 ?例如， 若 {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 minimum support (Apriori) ?A subset of a frequent itemset must also be a frequent itemset, ., if {A ? B} is a frequent itemset, both {A} and {B} should be a frequent itemset ?Iteratively find frequent itemsets with cardinality from 1 to k (kitemset) ?Use the frequent itemsets to generate association rules. 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3Scan D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 Scan D C3 L3 item set{2 3 5}Scan D ite m s e t s u p{ 2 3 5 } 2不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 聚類 ? 聚類 (Clustering)的定義 ? 聚類算法將數(shù)據(jù)分割成若干個(gè)簇，被大多數(shù)人接受的定義是：簇內(nèi)的相似性盡可能大 (簇內(nèi)同質(zhì)性 )，簇間的相似性盡可能小 (簇間異質(zhì)性 )。 ? 輸入： X={x1,...,xj,...,xN}。 聚類 ? 聚類的定義 ? 硬聚類 (基于劃分的聚類 )：試圖將 X分割成 K個(gè)簇C={C1,...,Ck,...,CK}(K≤N)。 ? 層次聚類 ：試圖構(gòu)造一個(gè) X的樹狀嵌套結(jié)構(gòu)H={H1,...,HQ}(QN)，對于 C