【正文】 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決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類(lèi) (Kmeans算法 ) ? 聚類(lèi)分析是把研究對(duì)象按照一定的規(guī)則分成若干類(lèi)別，并使類(lèi)之間的差別盡可能地大，類(lèi)內(nèi)的差別盡可能地小，換句話說(shuō)，使類(lèi)間的相似性最小、而類(lèi)內(nèi)的相似性最大。 2112 ])([),( ????pkjkikji xxxxd ????pkjkikji xxxxd1||),( )1(]||[),( 11??? ??mxxxxd mpkmjkikji決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類(lèi) (Kmeans算法 ) ? 對(duì)于給定的 n個(gè)樣品，先粗略地形成 k(k≤n)個(gè)分割，使得每個(gè)分割對(duì)應(yīng)一個(gè)類(lèi)、每個(gè)類(lèi)至少有一個(gè)樣品并且每個(gè)樣品精確地屬于一個(gè)類(lèi)，然后按照某種原則進(jìn)行修正，直至分類(lèi)比較合理為止。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類(lèi) (Kmeans算法 ) 聚點(diǎn)的最小最大原則選擇法： ①設(shè)將 n個(gè)樣品分成 k類(lèi)，先選擇所有樣品中相距最遠(yuǎn)的兩個(gè)樣品 為前兩個(gè)聚點(diǎn)，因此有 21 , ii xx )m ax(),( 21 ijii dxxd ?②設(shè)已經(jīng)找到了 l個(gè) (2≤ l＜ k)聚點(diǎn)，則第 l+1個(gè)聚點(diǎn) 的選擇方法是使得 與前 l個(gè)聚點(diǎn)的距離最小者等于所有其余的與前 l個(gè)聚點(diǎn)的較小距離的最大者，直至選定 k個(gè)聚點(diǎn)，即 將所獲得的 k個(gè)聚點(diǎn)的集合記為 ),2,1),2,1),(ma x( mi n(),2,1),(mi n(211rijiiiiijnjlrxxdlrxxdrrl???????????1?lix1?lix },{ )0()0(2)0(1)0( kxxxL ??決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類(lèi) (Kmeans算法 ) (2)初始聚類(lèi) 有了聚點(diǎn)集合后，可根據(jù)下列最靠近原則實(shí)現(xiàn)初始分類(lèi)： 若對(duì)于某樣品 x出現(xiàn) ，則 x任意歸于 Gi(0) 或 Gj(0) 類(lèi)。其中 根據(jù)新的聚點(diǎn)集，對(duì)樣品空間重新聚類(lèi)，形成新的分類(lèi)： 其中 },{ )1()1(2)1(1)1( ???? ? mkmmm xxxL ?kixGcardxmil Gxlmimi ,2,1,)(1)()()1( ??? ???0},{ )1()1(2)1(1)1( ?? ???? mGGGG mkmmm ? kiijkjxxdxxdx mjmimi ,2,1},。 ?若 ,則 ?=0。 ? 概念 ：具有相同特征值的一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類(lèi)就是一個(gè)概念） 粗糙集理論 (Rough Set Theory) 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ?pi T1 pj iff v(pi, T1)=v(pj, T1)，則 T1是 U上的一個(gè)等價(jià)關(guān)系（類(lèi)似地可以定義 T2, T3, E） ?X1=[p1]=[p4]=[p6]={p1, p4, p6}為 U關(guān)于 T1的一個(gè)等價(jià)類(lèi) ?X2=[p2]=[p3]=[p5]={p2, p3, p5}為 U關(guān)于 T1的另一個(gè)等價(jià)類(lèi)（ T1有多少種取值就有多少個(gè)等價(jià)類(lèi)） ?顯然 X1∩X2=φ。 ?Pawlak Z., Rough sets. International Journal of Computer and Information Sciences, 1982(11): 341356 ?Pawlak Z., Rough set— Theoretical Aspects of Reasoning about Data, Dordrecht, Boston, London: Kluwer Academic Publishers,1991 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 基本思想 ?知識(shí)是主體對(duì)論域中的客體進(jìn)行分類(lèi)的能力，分類(lèi)能力越強(qiáng)，主體所具備知識(shí)的可靠度越高 ?分類(lèi)能力受主體分辨能力的影響，因此分類(lèi)具有近似性 (粗糙集 ) ?影響分類(lèi)能力的因素 (在信息系統(tǒng)中常描述為屬性 )很多，不同的因素重要程度不同，其中某些因素起決定性作用 (屬性重要性：屬性約簡(jiǎn) ) ?具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類(lèi)能力也產(chǎn)生影響 (值重要性：值約簡(jiǎn) ) ?屬性之間存在某種依賴關(guān)系 (決策規(guī)則 ) 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 信息系統(tǒng)與知識(shí) ?信息系統(tǒng) I可以定義為四元組 U, A, V, f，其中有限非空集合 U是論域， A為關(guān)于 U的屬性集， ， Va表示屬性 a的值域，映射 f: U A→ V表示對(duì) ?x?U， a?A，有： f(x, a)?V。 ? IND(B)是等價(jià)關(guān)系， IND(B)的所有等價(jià)類(lèi)的集合記為 U/B（稱為 知識(shí) B），含有元素 x的等價(jià)類(lèi)記為 B(x)或 [x]B，同一等價(jià)類(lèi)中的元素是不可分辨的，稱 IND(B)等價(jià)類(lèi)為 初等集（范疇） ，它是知識(shí)庫(kù)的基本結(jié)構(gòu)單元即 概念 。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 粗糙集與近似 ?下近似 ?由所有包含于 X的初等集合的并構(gòu)成， X的下近似中的元素一定屬于 X。 ?正域與負(fù)域 YXxUxXR XYRUYR )()/(}][:{ ??????? ? YXxUxXRXYRUYR )()/(}][:{ ????????? ???XRXPO SR ?)( XRUXNeg R ??)(粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 經(jīng)典粗糙集模型 論域 U 粗糙集 X 粗糙集粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(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}}。 ?粗糙度 ： X的 R粗糙度反映了我們對(duì)于了解集合 X的知識(shí)的不完全程度。這是一個(gè)非常重要的特征數(shù)字，它反映了兩種分類(lèi) F和 R之間的關(guān)系。 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 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 粗糙集數(shù)字特征 ? 知識(shí) R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ? 設(shè)信息系統(tǒng) I=U, A, V, f， A=C∪ D， B?C，則 D的 B正域定義為： ? D的 B正域表示利用知識(shí) B，能正確地劃分到 U/D各等價(jià)類(lèi)中的所有對(duì)象的集合 XBDPOSDUXB /)(?? ?粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 知識(shí)依賴 ? 設(shè)信息系統(tǒng) I=U, C∪ D, V, f， ① D完全依賴于 C當(dāng)且僅當(dāng) ② D等價(jià)于 C當(dāng)且僅當(dāng) (C?D) ?(D?C)； ③ D獨(dú)立于 C當(dāng)且僅當(dāng) ?(C?D) ??(D?C)。 ? 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} 。 ?表明：不同屬性在分類(lèi)時(shí)所起的作用是不同的。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 屬性重要性與屬性核 ? 在確定某個(gè)決策目標(biāo)時(shí)，不同屬性的重要性是不同的，在一般分析中常用事先假設(shè)的權(quán)重來(lái)描述。重要度可理解為移去 B時(shí)所產(chǎn)生的分類(lèi)誤差。 )())(()( /, 0UCar dXBCar dDk DUXB???????粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 值約簡(jiǎn) ? 為什么要約簡(jiǎn)屬性值？ ?在判斷某個(gè)對(duì)象屬于某類(lèi)時(shí)，某個(gè)屬性的取值不同，對(duì)分類(lèi)產(chǎn)生的影響也不相同。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 約簡(jiǎn)示例 1. IF (T1, No) AND (T3, Normal) THEN (E, Yes) 2. IF (T1, Yes) AND (T3, No