【正文】 into k groups Update the cluster centroids Update the cluster centroids Reassign objects Loop if needed The initial data set ? Partition objects into k nonempty subsets ? Repeat ? Compute centroid (., mean point) for each partition ? Assign each object to the cluster of its nearest centroid ? Until no change 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 連接分析 (LinkAnalysis) ? 事物之間是普遍聯(lián)系的 ? 網(wǎng)站與網(wǎng)站之間 ? 網(wǎng)頁與網(wǎng)頁之間 ? 社交網(wǎng)絡(luò)中的結(jié)點(diǎn)之間 ? ...... ? 需要回答的一個問題：這些連接點(diǎn)誰重要？ 連接分析 — PageRank算法 ? Google采用的基本算法 (Lary Page, 拉里 .佩奇，google創(chuàng)始人 ),節(jié)點(diǎn)代表頁面 ,有向邊代表超鏈接 ? 假設(shè)： ? 沖浪者隨機(jī)選擇起始頁面 ? 在以后的每一步，沖浪者以概率 d直接進(jìn)入目標(biāo)頁面或以1d的概率通過其它指向目標(biāo)頁面的超鏈接進(jìn)入目標(biāo)頁面。 11 0011 00 10 01()ijnnSn n w n n??? ? ?1111 10 01()ijnSn w n n??聚類：相似性度量 ? 相似性度量方法 ? 名詞型 (多元 )特征 名詞性特征是指取值超過 2個狀態(tài)的離散型特征，如性別、顏色等。 c os || || || ||TijijijxxSxx??? ?xi xj O ? 1( ) ( )Tij i j i jD x x S x x?? ? ?聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數(shù)型 )特征 ④ Pearson相關(guān)系數(shù)： Dij=1rij (不能度量兩個對象的差異幅度 )，例如： x1=(1,1,1)。 n=2時，稱為歐幾里德距離 (超球面聚類 )。特征類型包括定量與定性、連續(xù)與離散、名詞與序數(shù)等。 ? 層次聚類 ：試圖構(gòu)造一個 X的樹狀嵌套結(jié)構(gòu)H={H1,...,HQ}(QN)，對于 Ci?Hm， Cj?Hl，若 ml，則要么 Ci?Cj，要么 Ci∩Cj=?。 ? 輸入： X={x1,...,xj,...,xN}。 典型方法： Apriori算法?！白匀粻顟B(tài)”隱藏了數(shù)據(jù)的結(jié)構(gòu)，而不是為未觀測的樣本提供一個精確刻畫 (描述而非預(yù)測 )。 ? 模型： Y=f(X,W)或 P(Y|X)=f(X,W)，將輸入 X映射成類標(biāo)簽 Y或 Y的概率分布。 標(biāo)簽化 Taxonomy of Data Mining Methods ? 有監(jiān)督學(xué)習(xí) ? 輸入： X={x1,...,xj,...,xN}。 KDD過程 評估和解釋所挖掘的模式，重點(diǎn)是可理解性、有用性 . KDD過程 與原有知識系統(tǒng)合并。 ? 數(shù)據(jù)挖掘 (Data Mining， DM) 是 KDD的核心階段 , 通過實(shí)施相關(guān)算法獲得期望的模式。 知識發(fā)現(xiàn) — 動機(jī) ? 智能決策的核心是如何獲取支持決策的信息和知識。 不確定性決策準(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)整的情況。 不確定性決策準(zhǔn)則 ? 樂觀系數(shù)法 【 Hurwicz,1951】 ? 考察采取行動 ai， i=1,2,…,m 時可能出現(xiàn)的最壞后果和最好后果，即最大損失 si和最小損失 oi或 最小效用 ui和 最大效用 vi ； ? 設(shè)決策人的樂觀系數(shù)為 ?，則 選擇行動 ak，使得 (1 ?)sk+ ?ok((1 ?)uk+ ?vk)在所有行動中最小 (最大 )。 ? 解決問題的主要理論方法 ：人工智能與不確定性理論 不確定性決策準(zhǔn)則 ? 在決策者無法獲取狀態(tài)的概率時，貝葉斯決策準(zhǔn)則就難以湊效。 ? 特點(diǎn) ：狀態(tài)的不確定性。 ? 不確定性 ： 不確定性來自人類的主觀認(rèn)識與客觀實(shí)際之間存在的差異。下面介紹幾種常用的不確定性決策準(zhǔn)則。 不確定性決策準(zhǔn)則 ? 后悔值極小化極大法 【 Savage,1951】 ? 在狀態(tài) θj下考察采取行動 ai的損失 lji或 效用 uji和，并將其與在此狀態(tài)下采取不同行動時的最小損失 sj或 最大效用 uj進(jìn)行比較，其差值的大小定義為后悔值 rji，從而形成一個后悔值表； ? 針對后悔值表，應(yīng)用悲觀準(zhǔn)則求解：找出不同狀態(tài)下采取行動 ai的最大后悔值 pi，然后再使所有行動的最大后悔值極小，其所對應(yīng)的行動記為決策結(jié)果。 ? 這時，傳統(tǒng)的決策數(shù)學(xué)模型已經(jīng)難以勝任求解復(fù)雜度過高的決策問題、含有不確定性的決策問題以及半結(jié)構(gòu)化、非結(jié)構(gòu)化的決策問題，因而產(chǎn)生了智能決策理論、方法及技術(shù)。 ? 問題 ? 知識獲取是基于知識的系統(tǒng) (KBS)的最大瓶頸 推理機(jī) 知識工程師 領(lǐng)域?qū)＜? 決策者 知識庫 問題請求 推理結(jié)果 知識發(fā)現(xiàn) — 動機(jī) ? 問題 ? 推理規(guī)則的獲取與 KBS中知識獲取一樣難，因而基于案例推理 (CaseBased Reasoning)漸漸變成基于案例檢索 (CaseBased Retrieving)。 KDD過程 理解、定義用戶的目標(biāo)和KDD運(yùn)行的環(huán)境。 挑戰(zhàn) : 動態(tài)與增量挖掘問題。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對象 xj對應(yīng)的第 i個特征 (維度、屬性、變量 )的值。 W是可調(diào)整的參數(shù)向量。 ? 無監(jiān)督預(yù)測學(xué)習(xí) (如關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、鏈接分析等 )：具有預(yù)測能力的無監(jiān)督學(xué)習(xí)。 NBASupp ort || ??||||ABACon fide nce ??* 決策理論與方法 智能決策理論與方法 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Apriori算法由 Agrawal Srikant在 1994年提出 ? 主要思想 : ? 一個頻繁項(xiàng)集（支持度超過給定值的項(xiàng)集）的子集一定是頻繁的 ?例如， 若 {beer, diaper, nuts}是頻繁的 , 那么 {beer, diaper} 一定是頻繁的 . ? 任一項(xiàng)是非頻繁的，則包含該項(xiàng)的超集一定是不頻繁的。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對象 xj對應(yīng)的第 i個特征 (維度、屬性、變量 )的值。 (解釋：如果兩個簇不在同一層，那么，這兩個簇要么是包含關(guān)系，要么不相交 ) * 決策理論與方法 智能決策理論與方法 聚類 ? 聚類的定義 ? 軟聚類 (基于相容的聚類 )：試圖將 X分割成 K個簇C={C1,...,Ck,...,CK}(K≤N)。 特征類型決定著相似性測度機(jī)制。 n→∞ 時，稱為上確界距離， Dij=max|xilxjl|, l={1...d}。 x2=(2,2,2) x3=(1,1,2)。相似性一般采用特征值匹配的辦法衡量。d的經(jīng)驗(yàn)值約為 。 ? 若 ,則 ?=0。 X1∪ X2=U ? 商集 U/T1={X1, X2} U T1 T2 T3 E p1 N Y Normal Y p2 Y N Normal Y p3 Y Y High Y p4 N Y Low N p5 Y N Normal N p6 N Y High Y 粗糙集：預(yù)備知識 ? 集合成員 ：明確的隸屬關(guān)系 ? 模糊成員 ：概念模糊 (如青年 )導(dǎo)致成員模糊 ? 粗糙成員 ：概念清晰 (如感冒 )，成員模糊 (是否感冒不清楚 )，具有概率特征 (隸屬函數(shù) )，但不是概率問題，只是由于根據(jù)可用知識無法得到準(zhǔn)確結(jié)論。 ? 決策表 ：若屬性集合 A可進(jìn) 一步分為兩個屬性子集的并： 條件屬性集 C和決策屬性集 D， A=C∪ D， C∩D=?，則信息 系統(tǒng)也被稱為決策表。 ? 設(shè) R是由屬性集 A的子集誘導(dǎo)的論域 U上的等價關(guān)系族，則稱R為 U上的一個 知識庫 ，記為 K=(U, R)。 ? 上近似 ? 由與 X的交為非空的初等集合的并構(gòu)成，而上近似中的元素可能屬于 X。 ? 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}，邊界域?yàn)?{p2, p5}； ? X2={p4, p5}也是 R粗糙集， X2的 R下近似是 {p4}，X2的 R上近似是 {p2, p4, p5}，而邊界域是 {p2, p5}。 (精度與概率或隸屬度的區(qū)別 ) 粗糙集：數(shù)字特征 ? 知識 R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。這是一個非常重要的特征數(shù)字，它反映了兩種分類 F和 R之間的關(guān)系。 粗糙集：數(shù)字特征 ? 為了尋找“ IF…… THEN”形式的推理規(guī)則，在粗糙集理論體系中所采用的方法是從一個給定的知識，推導(dǎo)另一個知識。 ? 設(shè)信息系統(tǒng) I=U, C∪ D, V, f，有： 則稱 D是 k(0?k?1)度依賴于 C，記為 C?kD。 條件屬性子集 {T1} {T2} {T3} {T1,T2} {T1,T3} {T2,T3} {T1,T2,T3} 依賴度 k 0 0 1/2 1/6 2/3 2/3 2/3 粗糙集：知識依賴 ? 為什么要約簡知識？ ? 判別：根據(jù)條件屬性取值確定對象所屬的類。 ? 設(shè)信息系統(tǒng) I=U,C∪ D,V,f， B?C，若 ?C(D)=?B(D)且 B是 D獨(dú)立的，則 B為 C的 D約簡，記為 REDD(C)。處理方法是將該屬性從信息表中移去，分析其對分類能力的影響，影響越大，屬性越重要。 )()(1)()()()(),( DDDDDBCBCCBCCDC ?????? ?? ????粗糙集：屬性重要性與屬性核 ? 基于屬性依賴度的屬性約簡 ： 設(shè)決策表 T=U,CUD,V, f，C,D分別為條件屬性和決策屬性， B是 C的任一非空子集，對于經(jīng)典粗糙集模型， D對 B的依賴度為： ? 則在 B中增加某個屬性 p?CB所引起的 k的變化大小為： γp(D|B)= γB∪ {p}(D)γB(D) ? γp(D|B)越大，說明在已知屬性 B的條件下， p對決策 D越重要。但若體重屬性值為 60Kg時，此人的體形要結(jié)合其身高、性別才能確定，但若體重屬性值為