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