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