【正文】 為 U關(guān)于 R的商集，它構(gòu)成了 U的一個(gè)劃分，記為 U/R。 11( ) / ( )ddij ijl ijl ijlllSS ????? ??聚類：相似性度量 ? 相似性度量的鄰近矩陣 ? 對(duì)于 N個(gè)輸入數(shù)據(jù)對(duì)象，兩兩之間的相似性可以表示成一個(gè) NN階對(duì)稱矩陣，稱為鄰近矩陣。計(jì)算量較大。 ,KNj i j i i jijx u C u N??? ? ? ???聚類：相似性度量 ? 數(shù)據(jù)對(duì)象與特征： 數(shù)據(jù)對(duì)象都是由一些特征來(lái)描述的，常表示為多維向量。 ? 聚類是一個(gè)主觀過(guò)程，其相似性度量都是根據(jù)發(fā)現(xiàn)感興趣的“簇”的能力主觀選擇的，不存在一個(gè)絕對(duì)的準(zhǔn)則適用所有情境。 Taxonomy of Data Mining Methods ? 無(wú)監(jiān)督學(xué)習(xí) ? 無(wú)監(jiān)督分類 (聚類 )：應(yīng)用于無(wú)標(biāo)簽數(shù)據(jù)的分類，稱為聚類分析或探究性分析，其目標(biāo)是將無(wú)標(biāo)簽數(shù)據(jù)分類到有限、離散的“自然狀態(tài)”。 人類認(rèn)識(shí)新生事物。知識(shí)如何評(píng)價(jià)？ 參考書推薦 KDD DM ? 知識(shí)發(fā)現(xiàn) (Knowledge Discovery in Databases ,KDD) 是指從大量數(shù)據(jù)中提取有用的 (useful)、新穎的 (novel)、有效的 (valid)并最終能被人理解 (understandable)的模式(patterns)的處理過(guò)程 (process)。 ? 然后借助于貝葉斯準(zhǔn)則進(jìn)行決策。不確定性就造成了具有相同描述信息的對(duì)象可能屬于不同概念。事物發(fā)生的隨機(jī)性、人類知識(shí)的不完全、不可靠、不精確和不一致以及自然語(yǔ)言中存在的模糊性和歧義性，都反映了這種差異，都會(huì)帶來(lái)不確定性。 不確定性決策準(zhǔn)則 ? 等概率法 【 Laplace,1825】 ? Laplace認(rèn)為，對(duì)真實(shí)的自然狀態(tài)一無(wú)所知 等價(jià)于 所有自然狀態(tài)具有相同的概率。 推理機(jī) 決策者 案例庫(kù) 問(wèn)題請(qǐng)求 推理結(jié)果 規(guī)則庫(kù) 知識(shí)工程師 領(lǐng)域?qū)＜? 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) 決策者 數(shù)據(jù)分析師 數(shù)據(jù)中心 不一定滿意的決策 決策支持查詢 查詢結(jié)果 ? 問(wèn)題 ? 數(shù)據(jù)分析師與決策者之間對(duì)問(wèn)題的理解存在偏差 ? 缺少有創(chuàng)造性的決策建議 ? 技術(shù)問(wèn)題：如查詢效率 (RDBMS) 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) 推理機(jī) 數(shù)據(jù)挖掘工具 數(shù)據(jù)中心 決策者 知識(shí)庫(kù) 問(wèn)題請(qǐng)求 推理結(jié)果 背景知識(shí) 領(lǐng)域?qū)＜? ? 優(yōu)點(diǎn) ? 知識(shí)獨(dú)立于問(wèn)題本身 ? 知識(shí)的獲取主要通過(guò)數(shù)據(jù)挖掘?qū)崿F(xiàn) ? 有創(chuàng)造性收獲 Data Mining within the DSS 知識(shí)發(fā)現(xiàn) — 動(dòng)機(jī) ? KDD帶來(lái)的新問(wèn)題 ?知識(shí)發(fā)現(xiàn)問(wèn)題：如何從數(shù)據(jù)中將知識(shí)挖掘出來(lái)？面臨許多技術(shù)問(wèn)題： 如 數(shù)據(jù)異構(gòu)問(wèn)題 、 數(shù)據(jù)具有噪音且信息不完整、使用什么樣的挖掘算法、知識(shí)如何表示等 ?知識(shí)評(píng)價(jià)問(wèn)題： 數(shù)據(jù)本身具有權(quán)威性、客觀性，但知識(shí)不具備。 Taxonomy of Data Mining Methods Taxonomy of Data Mining Methods ? Verificationoriented (the system verifies the user‘s hypothesis): including the most mon methods of traditional statistics, like goodness of fit(擬合優(yōu)度 ) test, tests of hypotheses (假設(shè)檢驗(yàn) ， ., ttest of means), and analysis of variance (ANOVA， 方差分析或 F檢驗(yàn) ). ? Discoveryoriented (the system finds new rules and patterns autonomously): prediction methods VS description methods； supervised learning（ 有導(dǎo)師學(xué)習(xí) ） VS unsupervised learning Taxonomy of Data Mining Methods 分類 有監(jiān)督學(xué)習(xí) 無(wú)監(jiān)督學(xué)習(xí) 父母、老師教我們認(rèn)識(shí)世界的萬(wàn)事萬(wàn)物。 ? 模型訓(xùn)練： 使用歸納學(xué)習(xí)方法 (經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化 )確定模型的結(jié)構(gòu) f和參數(shù) W，訓(xùn)練樣本集為 (xi,yi)。 ?例如， 若 {beer, diaper}是不頻繁的 , 那么 {beer, diaper, nuts}一定是不頻繁的 . 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Procedure ?Find the frequent itemsets: the sets of items that have minimum support (Apriori) ?A subset of a frequent itemset must also be a frequent itemset, ., if {A ? B} is a frequent itemset, both {A} and {B} should be a frequent itemset ?Iteratively find frequent itemsets with cardinality from 1 to k (kitemset) ?Use the frequent itemsets to generate association rules. 關(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不確定性決策理論與方法 不確定性決策概述 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) 聚類分析 連接分析 粗糙集分析 決策樹(shù) 神經(jīng)網(wǎng)絡(luò) 支持向量機(jī) 聚類 ? 聚類 (Clustering)的定義 ? 聚類算法將數(shù)據(jù)分割成若干個(gè)簇，被大多數(shù)人接受的定義是：簇內(nèi)的相似性盡可能大 (簇內(nèi)同質(zhì)性 )，簇間的相似性盡可能小 (簇間異質(zhì)性 )。滿足① Ci≠?， i?{1,...,k}；②∪ i?{1,...,k}Ci=X； ③對(duì)象 xj屬于 Ci簇的隸屬度為 ui,j， ui,j滿足： ,11, 1 。 1/1||ndnij il jllD x x??????????xi xj 聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數(shù)型 )特征 ② 余弦相似性： ③ Mahalanobis(馬氏 )距離： S為協(xié)方差矩陣，當(dāng)各個(gè)特征是線性無(wú)關(guān)的時(shí)候， Dij就是歐氏距離。 11 dij ijllSSd?? ? 0,1ijl ijS ij?? ??與 不 匹 配， 與 匹 配聚類：相似性度量 ? 相似性度量方法 ? 混合情形 實(shí)際上，我們遇到的大多數(shù)數(shù)據(jù)對(duì)象所包含的特征可能各種類型都有，這時(shí)怎么辦？ ① 將所有特征映射到 [0,1]實(shí)數(shù)域； ② 將所有特征都映射成二元特征； ③ 通用測(cè)度： Sijl表示第 l個(gè)特征的相似度， ?ijl表示是否使用該特征參與測(cè)度。 ? 其他： 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。 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屬性值。 ? 上近似與下近似的差為 邊界域 ，粗糙集的邊界域?yàn)榉强?，否則為精確集。 ? 分類 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}， R精度為 ； R粗糙度為 ； ? X2={p4, p5}也是 R粗糙集， X2的 R下近似是 {p4}， X2的 R上近似是 {p2, p4, p5}， R精度為 ； R粗糙度為 。如果知識(shí) D的所有初等范疇都能用知識(shí) C的某些初等范疇來(lái)定義，則稱知識(shí) D可由知識(shí) C推得，也稱 D完全依賴于 C，記為 C?D。 ? 實(shí)際：確定對(duì)象所屬的類只需其中幾個(gè)屬性甚至一個(gè)屬性，而不需要知道對(duì)象所有的屬性，這與人類對(duì)實(shí)體的識(shí)別是一致的。 ? 設(shè)信息系統(tǒng) I=U,C∪ D,V,f，對(duì)于 C的非空子集 B，其重要度為 ? 若 B的重要度為０，則表示 B可以從 C中移去，也即 B是冗余的。 ? 什么是值約簡(jiǎn)？ ? 值約簡(jiǎn)就是移去對(duì)分類沒(méi)有實(shí)際價(jià)值的冗余的屬性值。 決策樹(shù)：學(xué)習(xí)結(jié)果 A0 A1 A1 A2 1 1 1 1 1 1 0 0 1 0 1 1 0 T2 T1 T11 T12 T111 T112 T21 T22 T 決策樹(shù)： ID3學(xué)習(xí)算法 ? ID3算法 (Quinlan)：以信息熵的下降速度 (信息增益 )作為測(cè)試屬性選擇標(biāo)準(zhǔn)。 決策樹(shù)：算例 A1 1 0 1 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 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 確定子樹(shù)根結(jié)點(diǎn) I(P,N)=6/8log6/82/8log2/8= E(A0)=E(A2)=1/2= E(A3)=23/4log3= A0， A2具有相同的分類能力，任取一個(gè)均可。 神經(jīng)網(wǎng)絡(luò) ? 多層前向神經(jīng)網(wǎng)絡(luò) ：包括一個(gè)輸入層、一個(gè)輸出層以及多層隱單元。輸入 ? T = [0 1 2 3 4 3 2 1 2 3 4]。 ? Y = sim(,P)。 分類的任務(wù)就是尋找分類器 f： U→Y 且使期望風(fēng)險(xiǎn)最小。這是小樣本統(tǒng)計(jì)理論與經(jīng)典統(tǒng)計(jì)理論的本質(zhì)區(qū)別，也是將 Vapnik統(tǒng)計(jì)方法稱之為小樣本統(tǒng)計(jì)理論 的原因。 從線性可分情況下的 最優(yōu)分類超平面 發(fā)展而來(lái)的 ， 其本質(zhì)是在訓(xùn)練樣本中找出具有最優(yōu)分類超平面的 支持向量 。 ? 分類模型 ：尋求最優(yōu)超平面 H，使得 margin最大。流形學(xué)習(xí)（ Manifold Learning， 2023年， Joshua Tenenbaum（ Isomap）； Sam T. Roweis and Lawrence K. Saul（ LLE）， 《 Science》 ）是結(jié)構(gòu)學(xué)習(xí)的