【正文】 nimum 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ī)則發(fā)現 (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ī)則發(fā)現 聚類分析 連接分析 粗糙集分析 決策樹 神經網絡 支持向量機 聚類 ? 聚類 (Clustering)的定義 ? 聚類算法將數據分割成若干個簇，被大多數人接受的定義是：簇內的相似性盡可能大 (簇內同質性 )，簇間的相似性盡可能小 (簇間異質性 )。 ? 聚類是一個主觀過程，其相似性度量都是根據發(fā)現感興趣的“簇”的能力主觀選擇的，不存在一個絕對的準則適用所有情境。 ? 輸入： X={x1,...,xj,...,xN}。 xj={xj1,...,xji,...,xjd}T?Rd， xji表示對象 xj對應的第 i個特征 (維度、屬性、變量 )的值。 聚類 ? 聚類的定義 ? 硬聚類 (基于劃分的聚類 )：試圖將 X分割成 K個簇C={C1,...,Ck,...,CK}(K≤N)。滿足① Ci≠?， i?{1,...,k}；②∪ i?{1,...,k}Ci=X； ③ Ci∩Cj=?， i, j∈ {1,...,k}, i≠j。 ? 層次聚類 ：試圖構造一個 X的樹狀嵌套結構H={H1,...,HQ}(QN)，對于 Ci?Hm， Cj?Hl，若 ml，則要么 Ci?Cj，要么 Ci∩Cj=?。 (解釋：如果兩個簇不在同一層，那么，這兩個簇要么是包含關系，要么不相交 ) * 決策理論與方法 智能決策理論與方法 聚類 ? 聚類的定義 ? 軟聚類 (基于相容的聚類 )：試圖將 X分割成 K個簇C={C1,...,Ck,...,CK}(K≤N)。滿足① Ci≠?， i?{1,...,k}；②∪ i?{1,...,k}Ci=X； ③對象 xj屬于 Ci簇的隸屬度為 ui,j， ui,j滿足： ,11, 1 。 ,KNj i j i i jijx u C u N??? ? ? ???聚類：相似性度量 ? 數據對象與特征： 數據對象都是由一些特征來描述的，常表示為多維向量。特征類型包括定量與定性、連續(xù)與離散、名詞與序數等。 特征類型決定著相似性測度機制。 聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數型 )特征 ① Minkowski(閔氏 )距離： 值較大和波動較大的特征主導著相似性。 n=1時，稱為絕對距離 (超矩形聚類 )。 n=2時，稱為歐幾里德距離 (超球面聚類 )。 n→∞ 時，稱為上確界距離， Dij=max|xilxjl|, l={1...d}。 1/1||ndnij il jllD x x??????????xi xj 聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數型 )特征 ② 余弦相似性： ③ Mahalanobis(馬氏 )距離： S為協方差矩陣，當各個特征是線性無關的時候， Dij就是歐氏距離。計算量較大。 c os || || || ||TijijijxxSxx??? ?xi xj O ? 1( ) ( )Tij i j i jD x x S x x?? ? ?聚類：相似性度量 ? 相似性度量方法 ? 連續(xù)型 (包括序數型 )特征 ④ Pearson相關系數： Dij=1rij (不能度量兩個對象的差異幅度 )，例如： x1=(1,1,1)。 x2=(2,2,2) x3=(1,1,2)。 x4=(2,2,3) ⑤ 點對稱距離 (不能度量兩個對象的差異幅度 )： 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) 設每個對象都可用 d個特征表示，如果對象有此特征則標記為 1，否則標記為 0。對于任意兩個對象 xi, xj， n1 n00、n n01分別表示兩者都有、兩者都無、 xi有 xj無、 xi無 xj有的特征數，則： 或 根據不同的情境， w可以取 1(Jaccard), 2(Sokal), 1/2(Gower)。 11 0011 00 10 01()ijnnSn n w n n??? ? ?1111 10 01()ijnSn w n n??聚類：相似性度量 ? 相似性度量方法 ? 名詞型 (多元 )特征 名詞性特征是指取值超過 2個狀態(tài)的離散型特征，如性別、顏色等。相似性一般采用特征值匹配的辦法衡量。 11 dij ijllSSd?? ? 0,1ijl ijS ij?? ??與 不 匹 配， 與 匹 配聚類：相似性度量 ? 相似性度量方法 ? 混合情形 實際上，我們遇到的大多數數據對象所包含的特征可能各種類型都有，這時怎么辦？ ① 將所有特征映射到 [0,1]實數域； ② 將所有特征都映射成二元特征； ③ 通用測度： Sijl表示第 l個特征的相似度， ?ijl表示是否使用該特征參與測度。 11( ) / ( )ddij ijl ijl ijlllSS ????? ??聚類：相似性度量 ? 相似性度量的鄰近矩陣 ? 對于 N個輸入數據對象，兩兩之間的相似性可以表示成一個 NN階對稱矩陣，稱為鄰近矩陣。 11 1 111jNi ij iNN N j N NS S SS S SSS S S???????????聚類：主要方法 ? 層次聚類方法 ? kmeans ? 概率混合模型 ? 圖模型與譜聚類 ? 組合搜索技術 ? 模糊聚類 ? 基于神經網絡 ? 基于核的方法 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ī)則發(fā)現 聚類分析 連接分析 粗糙集分析 決策樹 神經網絡 支持向量機 連接分析 (LinkAnalysis) ? 事物之間是普遍聯系的 ? 網站與網站之間 ? 網頁與網頁之間 ? 社交網絡中的結點之間 ? ...... ? 需要回答的一個問題：這些連接點誰重要？ 連接分析 — PageRank算法 ? Google采用的基本算法 (Lary Page, 拉里 .佩奇，google創(chuàng)始人 ),節(jié)點代表頁面 ,有向邊代表超鏈接 ? 假設： ? 沖浪者隨機選擇起始頁面 ? 在以后的每一步，沖浪者以概率 d直接進入目標頁面或以1d的概率通過其它指向目標頁面的超鏈接進入目標頁面。d的經驗值約為 。 ? 一個頁面的重要性取決于指向該頁面的頁面的重要性 隨機選擇的起始頁面 d= 連接分析 — PageRank算法 ? 則頁面 p的重要性為： xp(k+1)=(1d)/n+d?q,p?P,q→p (xq(k)/Nq) ? P為站點的頁面集， n為所有頁面數， Nq為頁面 q的出度， xq(k)為頁面 q的重要性。 ? 這樣就可以計算出所有頁面的重要性。記X={xp|p?P}， D={1/n,1/n,…,1/n} ， M={mpq} ={1/Nq}， Nq表示可直接鏈接到頁面 p的頁面 q的出度，則 X(k+1)=(1d)D+dMX(k) 隨機選擇的起始頁面 q d= 連接分析 — PageRank算法 連接分析 — PageRank算法 ? 算例： 0 連接分析 — PageRank算法 不確定性決策理論與方法 不確定性決策概述 關聯規(guī)則發(fā)現 聚類分析 連接分析 粗糙集分析 決策樹 神經網絡 支持向量機 粗糙集：預備知識 ? 論域 ：研究對象的全體成員構成的集合，一般用字母 U表示；若 X?U，則稱 X是 U的 子集 ? 隸屬度 ：描述一個對象 x與某個子集 X之間的隸屬程度，一般用符號 ??表示， ? 若 x?X, 則 ?=1。 ? 若 ,則 ?=0。 ? 其他： 0?1(?常用某個函數加以描述，稱為隸屬度函數 ) ?