【正文】 , Normal) THEN (E, Yes) 3. IF (T3, High) THEN (E, Yes) 4. IF (T3, Low) THEN (E, No) 5. IF (T2, No) AND (T3, Normal) THEN (E, No) 6. IF (T3, High) THEN (E, Yes) T2 T3 E p1 Y Normal Y p2 N Normal Y p3 High Y p4 Low N p5 N Normal N p6 High Y 粗糙集：約簡示例 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 歸納學(xué)習(xí)：決策樹 A0根 A1內(nèi)結(jié)點(diǎn) A1 A2 1 1 1 1 1 1 0 0 1 0 1 1 0 葉結(jié)點(diǎn) A0 A1 A2 A3 類 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 A0 A1 A2 A3 類 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 決策樹：概念 ? 決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。但若體重屬性值為 60Kg時(shí)，此人的體形要結(jié)合其身高、性別才能確定，但若體重屬性值為 150Kg時(shí)，我們幾乎肯定他是個(gè)胖子，這時(shí)身高、性別已不重要，也就是說身高、性別的屬性值是冗余的。 /( ( ) )()()X U DBC ard B XkDC ard U? ???粗糙集：知識(shí)約簡算法 ? 為什么要約簡屬性值？ ? 在判斷某個(gè)對象屬于某類時(shí)，某個(gè)屬性的取值不同，對分類產(chǎn)生的影響也不相同。 )()(1)()()()(),( DDDDDBCBCCBCCDC ?????? ?? ????粗糙集：屬性重要性與屬性核 ? 基于屬性依賴度的屬性約簡 ： 設(shè)決策表 T=U,CUD,V, f，C,D分別為條件屬性和決策屬性， B是 C的任一非空子集，對于經(jīng)典粗糙集模型， D對 B的依賴度為： ? 則在 B中增加某個(gè)屬性 p?CB所引起的 k的變化大小為： γp(D|B)= γB∪ {p}(D)γB(D) ? γp(D|B)越大，說明在已知屬性 B的條件下， p對決策 D越重要。重要度可理解為移去 B時(shí)所產(chǎn)生的分類誤差。處理方法是將該屬性從信息表中移去，分析其對分類能力的影響，影響越大，屬性越重要。 粗糙集：知識(shí)約簡 ? 在確定某個(gè)決策目標(biāo)時(shí)，不同屬性的重要性是不同的，在一般分析中常用事先假設(shè)的權(quán)重來描述。 ? 設(shè)信息系統(tǒng) I=U,C∪ D,V,f， B?C，若 ?C(D)=?B(D)且 B是 D獨(dú)立的，則 B為 C的 D約簡，記為 REDD(C)。 ? 表明：不同屬性在分類時(shí)所起的作用是不同的。 條件屬性子集 {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 粗糙集：知識(shí)依賴 ? 為什么要約簡知識(shí)？ ? 判別：根據(jù)條件屬性取值確定對象所屬的類。 ? 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} 。 ? 設(shè)信息系統(tǒng) I=U, C∪ D, V, f，有： 則稱 D是 k(0?k?1)度依賴于 C，記為 C?kD。 ? 設(shè)信息系統(tǒng) I=U, A, V, f， A=C∪ D， B?C，則 D的 B正域定義為： ? D的 B正域表示：利用知識(shí) B，能正確地劃分到 U/D各等價(jià)類中的所有對象的集合 XBDPOSDUXB /)(?? ?粗糙集：知識(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)。 粗糙集：數(shù)字特征 ? 為了尋找“ IF…… THEN”形式的推理規(guī)則，在粗糙集理論體系中所采用的方法是從一個(gè)給定的知識(shí)，推導(dǎo)另一個(gè)知識(shí)。 粗糙集：數(shù)字特征 ? 知識(shí) R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。這是一個(gè)非常重要的特征數(shù)字，它反映了兩種分類 F和 R之間的關(guān)系。 粗糙集：數(shù)字特征 ? 設(shè) F={X1， X2， … ， Xn}是論域 U上的一個(gè)劃分，那么根據(jù)知識(shí) R， F的分類精度如何？ ? F的近似精度 ：分類的近似精度給出了根據(jù)現(xiàn)有知識(shí)對對象進(jìn)行分類時(shí)可能正確的決策的百分?jǐn)?shù)。 (精度與概率或隸屬度的區(qū)別 ) 粗糙集：數(shù)字特征 ? 知識(shí) R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。αR(X)=1為 精確集， 0≤αR(X)1為粗糙集。 ? 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}。邊界域中的元素根據(jù)可用知識(shí)沒有確定的分類，即它既不能劃分到 X也不能劃分到 X的補(bǔ)集。 ? 上近似 ? 由與 X的交為非空的初等集合的并構(gòu)成，而上近似中的元素可能屬于 X。 ? 每個(gè)粗糙集 X都可用兩個(gè)與之相關(guān)的精確集近似表示即 X的 上近似 和 下近似 ，他們是粗糙集理論的兩個(gè)最基本運(yùn)算。 ? 設(shè) R是由屬性集 A的子集誘導(dǎo)的論域 U上的等價(jià)關(guān)系族，則稱R為 U上的一個(gè) 知識(shí)庫 ，記為 K=(U, R)。則稱 IND(B)為 不可分辨關(guān)系 。 ? 決策表 ：若屬性集合 A可進(jìn) 一步分為兩個(gè)屬性子集的并： 條件屬性集 C和決策屬性集 D， A=C∪ D， C∩D=?，則信息 系統(tǒng)也被稱為決策表。粗糙集理論反映了人們以不完全信息或知識(shí)去處理一些不可分辨現(xiàn)象的能力，或依據(jù)觀察、度量到某些不精確的結(jié)果而進(jìn)行分類數(shù)據(jù)的能力。 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ù)備知識(shí) ? 集合成員 ：明確的隸屬關(guān)系 ? 模糊成員 ：概念模糊 (如青年 )導(dǎo)致成員模糊 ? 粗糙成員 ：概念清晰 (如感冒 )，成員模糊 (是否感冒不清楚 )，具有概率特征 (隸屬函數(shù) )，但不是概率問題，只是由于根據(jù)可用知識(shí)無法得到準(zhǔn)確結(jié)論。設(shè) X1, X2, …, X n是 U關(guān)于 R的所有等價(jià)類，則有： ? Xi∩Xj=φ（ i≠j， i, j=1,2,…,n ） ? X1∪ X2∪ … ∪ Xn=U ? 劃分 ： 所有等價(jià)類的集合稱為 U關(guān)于 R的商集，它構(gòu)成了 U的一個(gè)劃分，記為 U/R。 ? 若 ,則 ?=0。 ? 這樣就可以計(jì)算出所有頁面的重要性。d的經(jīng)驗(yàn)值約為 。 11( ) / ( )ddij ijl ijl ijlllSS ????? ??聚類：相似性度量 ? 相似性度量的鄰近矩陣 ? 對于 N個(gè)輸入數(shù)據(jù)對象，兩兩之間的相似性可以表示成一個(gè) NN階對稱矩陣，稱為鄰近矩陣。相似性一般采用特征值匹配的辦法衡量。對于任意兩個(gè)對象 xi, xj， n1 n00、n n01分別表示兩者都有、兩者都無、 xi有 xj無、 xi無 xj有的特征數(shù)，則： 或 根據(jù)不同的情境， w可以取 1(Jaccard), 2(Sokal), 1/2(Gower)。 x2=(2,2,2) x3=(1,1,2)。計(jì)算量較大。 n→∞ 時(shí)，稱為上確界距離， Dij=max|xilxjl|, l={1...d}。 n=1時(shí)，稱為絕對距離 (超矩形聚類 )。 特征類型決定著相似性測度機(jī)制。 ,KNj i j i i jijx u C u N??? ? ? ???聚類：相似性度量 ? 數(shù)據(jù)對象與特征： 數(shù)據(jù)對象都是由一些特征來描述的，常表示為多維向量。 (解釋：如果兩個(gè)簇不在同一層，那么，這兩個(gè)簇要么是包含關(guān)系，要么不相交 ) * 決策理論與方法 智能決策理論與方法 聚類 ? 聚類的定義 ? 軟聚類 (基于相容的聚類 )：試圖將 X分割成 K個(gè)簇C={C1,...,Ck,...,CK}(K≤N)。滿足① Ci≠?， i?{1,...,k}；②∪ i?{1,...,k}Ci=X； ③ Ci∩Cj=?， i, j∈ {1,...,k}, i≠j。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對象 xj對應(yīng)的第 i個(gè)特征 (維度、屬性、變量 )的值。 ? 聚類是一個(gè)主觀過程，其相似性度量都是根據(jù)發(fā)現(xiàn)感興趣的“簇”的能力主觀選擇的，不存在一個(gè)絕對的準(zhǔn)則適用所有情境。 NBASupp ort || ??||||ABACon fide nce ??* 決策理論與方法 智能決策理論與方法 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Apriori算法由 Agrawal Srikant在 1994年提出 ? 主要思想 : ? 一個(gè)頻繁項(xiàng)集（支持度超過給定值的項(xiàng)集）的子集一定是頻繁的 ?例如， 若 {beer, diaper, nuts}是頻繁的 , 那么 {beer, diaper} 一定是頻繁的 . ? 任一項(xiàng)是非頻繁的，則包含該項(xiàng)的超集一定是不頻繁的。 (Day=Friday) and (Product= Diaper) → (Product=Beer) 為一典型關(guān)聯(lián)規(guī)則 A為滿足前件的對象集， B為滿足后件的對象， N為全部對象集。 ? 無監(jiān)督預(yù)測學(xué)習(xí) (如關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、鏈接分析等 )：具有預(yù)測能力的無監(jiān)督學(xué)習(xí)。 Taxonomy of Data Mining Methods ? 無監(jiān)督學(xué)習(xí) ? 無監(jiān)督分類 (聚類 )：應(yīng)用于無標(biāo)簽數(shù)據(jù)的分類，稱為聚類分析或探究性分析，其目標(biāo)是將無標(biāo)簽數(shù)據(jù)分類到有限、離散的“自然狀態(tài)”。 W是可調(diào)整的參數(shù)向量。 Ck表示類標(biāo)簽。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對象 xj對應(yīng)的第 i個(gè)特征 (維度、屬性、變量 )的值。 人類認(rèn)識(shí)新生事物。 挑戰(zhàn) : 動(dòng)態(tài)與增量挖掘問題。 KDD過程 （ 1）缺失值處理 （ 2）剔除噪聲或異常數(shù)據(jù) KDD過程 （ 1）維數(shù)約簡 (特征選擇與抽取，數(shù)據(jù)采樣 ) （ 2）屬性轉(zhuǎn)換 (離散化和泛化 ) （ 3）數(shù)據(jù)編碼 KDD過程 (1)確定數(shù)據(jù)挖掘類型，如分類、聚類、回歸； (2) 選擇特定的方法； (3) 執(zhí)行數(shù)據(jù)挖掘算法。 KDD過程 理解、定義用戶的目標(biāo)和KDD運(yùn)行的環(huán)境。知識(shí)如何評價(jià)？ 參考書推薦 KDD DM ? 知識(shí)發(fā)現(xiàn) (Knowledge Discovery in Databases ,KDD) 是指從大量數(shù)據(jù)中提取有用的 (useful)、新穎的 (novel)、有效的 (valid)并最終能被人理解 (understandable)的模式(patterns)的處理過程 (process)。 ? 問題 ? 知識(shí)獲取是基于知識(shí)的系統(tǒng) (KBS)的最大瓶頸 推理機(jī) 知識(shí)工程師 領(lǐng)域?qū)＜? 決策者 知識(shí)庫 問題請求 推理結(jié)果 知識(shí)發(fā)現(xiàn) —