【正文】 i?Hm， Cj?Hl，若 ml，則要么 Ci?Cj，要么 Ci∩Cj=?。滿足① Ci≠?， i?{1,...,k}；②∪ i?{1,...,k}Ci=X； ③對(duì)象 xj屬于 Ci簇的隸屬度為 ui,j， ui,j滿足： ,11, 1 。特征類型包括定量與定性、連續(xù)與離散、名詞與序數(shù)等。 聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數(shù)型 )特征 ① Minkowski(閔氏 )距離： 值較大和波動(dòng)較大的特征主導(dǎo)著相似性。 n=2時(shí)，稱為歐幾里德距離 (超球面聚類 )。 1/1||ndnij il jllD x x??????????xi xj 聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數(shù)型 )特征 ② 余弦相似性： ③ Mahalanobis(馬氏 )距離： S為協(xié)方差矩陣，當(dāng)各個(gè)特征是線性無(wú)關(guān)的時(shí)候， Dij就是歐氏距離。 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 (不能度量?jī)蓚€(gè)對(duì)象的差異幅度 )，例如： x1=(1,1,1)。 x4=(2,2,3) ⑤ 點(diǎn)對(duì)稱距離 (不能度量?jī)蓚€(gè)對(duì)象的差異幅度 )： 12211( ) ( )( ) ( )dil i jl jlij ddil i jl jllx x x xrx x x x???????????1 , .. .,|| ( ) ( ) ||m in|| ( ) || || ( ) ||i r j rir jNi r j rjix x x xDx x x x? ?? ? ??? ? ?xi xj xr 聚類：相似性度量 ? 相似性度量方法 ? 二元型特征 (特征取值僅為 0,1) 設(shè)每個(gè)對(duì)象都可用 d個(gè)特征表示，如果對(duì)象有此特征則標(biāo)記為 1，否則標(biāo)記為 0。 11 0011 00 10 01()ijnnSn n w n n??? ? ?1111 10 01()ijnSn w n n??聚類：相似性度量 ? 相似性度量方法 ? 名詞型 (多元 )特征 名詞性特征是指取值超過 2個(gè)狀態(tài)的離散型特征，如性別、顏色等。 11 dij ijllSSd?? ? 0,1ijl ijS ij?? ??與 不 匹 配， 與 匹 配聚類：相似性度量 ? 相似性度量方法 ? 混合情形 實(shí)際上，我們遇到的大多數(shù)數(shù)據(jù)對(duì)象所包含的特征可能各種類型都有，這時(shí)怎么辦？ ① 將所有特征映射到 [0,1]實(shí)數(shù)域； ② 將所有特征都映射成二元特征； ③ 通用測(cè)度： Sijl表示第 l個(gè)特征的相似度， ?ijl表示是否使用該特征參與測(cè)度。 11 1 111jNi ij iNN N j N NS S SS S SSS S S???????????聚類：主要方法 ? 層次聚類方法 ? kmeans ? 概率混合模型 ? 圖模型與譜聚類 ? 組合搜索技術(shù) ? 模糊聚類 ? 基于神經(jīng)網(wǎng)絡(luò) ? 基于核的方法 Kmeans算法：基于幾何中心 ? Given k, the kmeans algorithm is implemented in four steps: 1. Partition objects into k nonempty subsets 2. Compute seed points as the centroids of the clusters of the current partitioning (the centroid is the center, ., mean point, of the cluster) 3. Assign each object to the cluster with the nearest seed point 4. Go back to Step 2, stop when the assignment does not change kixGca rdxmil Gx lmimi ,2,1,)(1)()()1( ??? ??? Kmeans算法示例 K=2 Arbitrarily partition objects 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)頁(yè)與網(wǎng)頁(yè)之間 ? 社交網(wǎng)絡(luò)中的結(jié)點(diǎn)之間 ? ...... ? 需要回答的一個(gè)問題：這些連接點(diǎn)誰(shuí)重要？ 連接分析 — PageRank算法 ? Google采用的基本算法 (Lary Page, 拉里 .佩奇，google創(chuàng)始人 ),節(jié)點(diǎn)代表頁(yè)面 ,有向邊代表超鏈接 ? 假設(shè)： ? 沖浪者隨機(jī)選擇起始頁(yè)面 ? 在以后的每一步，沖浪者以概率 d直接進(jìn)入目標(biāo)頁(yè)面或以1d的概率通過其它指向目標(biāo)頁(yè)面的超鏈接進(jìn)入目標(biāo)頁(yè)面。 ? 一個(gè)頁(yè)面的重要性取決于指向該頁(yè)面的頁(yè)面的重要性 隨機(jī)選擇的起始頁(yè)面 d= 連接分析 — PageRank算法 ? 則頁(yè)面 p的重要性為： xp(k+1)=(1d)/n+d?q,p?P,q→p (xq(k)/Nq) ? P為站點(diǎn)的頁(yè)面集， n為所有頁(yè)面數(shù)， Nq為頁(yè)面 q的出度， xq(k)為頁(yè)面 q的重要性。記X={xp|p?P}， D={1/n,1/n,…,1/n} ， M={mpq} ={1/Nq}， Nq表示可直接鏈接到頁(yè)面 p的頁(yè)面 q的出度，則 X(k+1)=(1d)D+dMX(k) 隨機(jī)選擇的起始頁(yè)面 q d= 連接分析 — PageRank算法 連接分析 — PageRank算法 ? 算例： 0 連接分析 — PageRank算法 不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 粗糙集：預(yù)備知識(shí) ? 論域 ：研究對(duì)象的全體成員構(gòu)成的集合，一般用字母 U表示；若 X?U，則稱 X是 U的 子集 ? 隸屬度 ：描述一個(gè)對(duì)象 x與某個(gè)子集 X之間的隸屬程度，一般用符號(hào) ??表示， ? 若 x?X, 則 ?=1。 ? 其他： 0?1(?常用某個(gè)函數(shù)加以描述，稱為隸屬度函數(shù) ) ? 等價(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。 ? 概念 ：具有相同特征值的一群對(duì)象稱為一個(gè)概念（一個(gè)等價(jià)類就是一個(gè)概念） 粗糙集：預(yù)備知識(shí) ? 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=φ。 粗糙集：預(yù)備知識(shí) ? 粗糙集理論由 Pawlak提出 [1982,1991]。 ? 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 粗糙集：理論的提出 ? 知識(shí)是主體對(duì)論域中的客體進(jìn)行分類的能力，分類能力越強(qiáng)，主體所具備知識(shí)的可靠度越高 ? 分類能力受主體分辨能力的影響，因此分類具有近似性 (粗糙集 ) ? 影響分類能力的因素 (在信息系統(tǒng)中常描述為屬性 )很多，不同的因素重要程度不同，其中某些因素起決定性作用 (屬性重要性：屬性約簡(jiǎn) ) ? 具有相同屬性的實(shí)體，屬性取值的不同對(duì)分類能力也產(chǎn)生影響 (值重要性：值約簡(jiǎn) ) ? 屬性之間存在某種依賴關(guān)系 (決策規(guī)則 ) 粗糙集：基本思想 ? 信息系統(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。 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 粗糙集：信息系統(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屬性值。 ? 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)單元即 概念 。 粗糙集：信息系統(tǒng)與知識(shí) ? 對(duì)于 U的任意子集 X，若 X恰能由知識(shí) R的若干個(gè)初等集的并構(gòu)成，則稱 X為 R精確集，否則為 R粗糙集 。 粗糙集：粗糙集與近似 ? 下近似 ? 由所有包含于 X的初等集合的并構(gòu)成， X的下近似中的元素一定屬于 X。 ? 上近似與下近似的差為 邊界域 ，粗糙集的邊界域?yàn)榉强?，否則為精確集。 ? 正域與負(fù)域 XRXPO S R ?)(XRUXNeg R ??)(粗糙集：粗糙集與近似 論域 U 粗糙集 X 粗糙集粗糙集：經(jīng)典粗糙集模型 ? R1={T1}： U/R1={{p2, p3, p5}， {p1, p4, p6}}； ? R2={T2,T1}： U/R2={{p1, p4, p6}, {p2, p5}, {p3}}； ? R={T1, T2, T3}： U/R=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 粗糙集：經(jīng)典粗糙集模型 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