【正文】 {p3}}； ? R3={T1, T2, T3}： U/R3=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ?上近似與下近似的差為 邊界域 ，粗糙集的邊界域?yàn)榉强?，否則為精確集。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 粗糙集與近似 ?下近似 ?由所有包含于 X的初等集合的并構(gòu)成， X的下近似中的元素一定屬于 X。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 粗糙集與近似 ?對(duì)于 U的任意子集 X，若 X恰能由知識(shí) R的若干個(gè)初等集的并構(gòu)成，則稱 X為 R精確集，否則為 R粗糙集 。 ? IND(B)是等價(jià)關(guān)系， IND(B)的所有等價(jià)類的集合記為 U/B（稱為 知識(shí) B），含有元素 x的等價(jià)類記為 B(x)或 [x]B，同一等價(jià)類中的元素是不可分辨的，稱 IND(B)等價(jià)類為 初等集（范疇） ，它是知識(shí)庫(kù)的基本結(jié)構(gòu)單元即 概念 。 aAa VV ?? ?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 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 信息系統(tǒng)與知識(shí) ? A的任何一個(gè)子集 B確定一個(gè) U上的二元關(guān)系 IND(B)：對(duì)于任意 a?B， xIND(B)y?a(x)=a(y)； x, y?U； a(x)表示對(duì)象 x的 a屬性值。 ?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)行分類的能力，分類能力越強(qiáng)，主體所具備知識(shí)的可靠度越高 ?分類能力受主體分辨能力的影響，因此分類具有近似性 (粗糙集 ) ?影響分類能力的因素 (在信息系統(tǒng)中常描述為屬性 )很多，不同的因素重要程度不同，其中某些因素起決定性作用 (屬性重要性：屬性約簡(jiǎn) ) ?具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類能力也產(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。 粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— RST的提出 ? 粗糙集理論由 Pawlak提出 [1982,1991]。 ? 概念 ：具有相同特征值的一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類就是一個(gè)概念） 粗糙集理論 (Rough Set Theory) 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ?pi T1 pj iff v(pi, T1)=v(pj, T1)，則 T1是 U上的一個(gè)等價(jià)關(guān)系（類似地可以定義 T2, T3, E） ?X1=[p1]=[p4]=[p6]={p1, p4, p6}為 U關(guān)于 T1的一個(gè)等價(jià)類 ?X2=[p2]=[p3]=[p5]={p2, p3, p5}為 U關(guān)于 T1的另一個(gè)等價(jià)類（ T1有多少種取值就有多少個(gè)等價(jià)類） ?顯然 X1∩X2=φ。(?常用某個(gè)函數(shù)加以描述，稱為隸屬度函數(shù) ) Xx?高斯函數(shù) 粗糙集理論 (Rough Set Theory) 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ? 等價(jià)關(guān)系 ： R是 U上的一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng) ?對(duì)于任意 x?U，均有 x R x（自反性） ?對(duì)于任意 x, y?U， x R y?y R x （對(duì)稱性） ?對(duì)于任意 x, y, z?U， x R y ∧ y R z→ x R z（傳遞性） ? 等價(jià)類 ：若 R是 U上的一個(gè)等價(jià)關(guān)系，對(duì)于任意 x?U，稱集合[x]={y| y R x, y ?U}為 U關(guān)于 R的一個(gè)等價(jià)類，記為 [x]R。 ?若 ,則 ?=0。當(dāng) G(m+1)=G(m)或在一定的精度范圍內(nèi)近似有 G(m+1)=G(m)，則遞推過程結(jié)束。其中 根據(jù)新的聚點(diǎn)集，對(duì)樣品空間重新聚類，形成新的分類： 其中 },{ )1()1(2)1(1)1( ???? ? mkmmm xxxL ?kixGca rdxmil Gxlmimi ,2,1,)(1)()()1( ??? ???0},{ )1()1(2)1(1)1( ?? ???? mGGGG mkmmm ? kiijkjxxdxxdx mjmimi ,2,1},。,2,1),(),(:{ )0()0()0( ?? ????? ),(),( )0()0( ji xxdxxd ? },{ )0()0(2)0(1)0( kGGGG ??決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) (3)迭代過程 設(shè)聚類形成的一個(gè)分類為 則可從 G(m)出發(fā)計(jì)算新的聚點(diǎn)集合 L(m+1)。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) 聚點(diǎn)的最小最大原則選擇法： ①設(shè)將 n個(gè)樣品分成 k類，先選擇所有樣品中相距最遠(yuǎn)的兩個(gè)樣品 為前兩個(gè)聚點(diǎn)，因此有 21 , ii xx )max(),( 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),(m ax(m i n(),2,1),(m in(211rijiiiiijnjlrxxdlrxxdrrl???????????1?lix1?lix },{ )0()0(2)0(1)0( kxxxL ??決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) (2)初始聚類 有了聚點(diǎn)集合后，可根據(jù)下列最靠近原則實(shí)現(xiàn)初始分類： 若對(duì)于某樣品 x出現(xiàn) ，則 x任意歸于 Gi(0) 或 Gj(0) 類。首先確定分類數(shù) k，然后選擇 k個(gè)有代表性的樣品作為每個(gè)類的初始元素即聚點(diǎn)。 2112 ])([),( ????pkjkikji xxxxd ????pkjkikji xxxxd1||),( )1(]||[),( 11??? ??mxxxxd mpkmjkikji決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) ? 對(duì)于給定的 n個(gè)樣品，先粗略地形成 k(k≤n)個(gè)分割，使得每個(gè)分割對(duì)應(yīng)一個(gè)類、每個(gè)類至少有一個(gè)樣品并且每個(gè)樣品精確地屬于一個(gè)類，然后按照某種原則進(jìn)行修正，直至分類比較合理為止。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) 聚類分析中的常用距離 (1)歐氏 (Euclidean)距離 (2)絕對(duì)距離 (3)Minkowski距離 ? 顯然當(dāng) m=1時(shí)就是絕對(duì)距離， m=2時(shí)就是歐氏距離。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(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決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) ? 聚類分析是把研究對(duì)象按照一定的規(guī)則分成若干類別，并使類之間的差別盡可能地大，類內(nèi)的差別盡可能地小，換句話說，使類間的相似性最小、而類內(nèi)的相似性最大。 k++) do begin Ck+1 = candidates generated from Lk。 for (k = 1。 對(duì)于任意分割點(diǎn)