【正文】 ?2 將余 下的對象分到各個(gè)類中去（根據(jù)與medoid最相近的原則） 。 ?3 對于每個(gè)類 （ Oi）中，順序選取一個(gè) Or，計(jì)算用 Or代替 Oi后的消耗 —E（ Or）。選擇 E最小的那個(gè) Or來代替 Oi。 ?4 重復(fù) 23直到 medoids不變 。 ?O（ n2dt） 聚類方法性能評價(jià) ?一個(gè)好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果 ——簇，這些簇要具備以下兩個(gè)特點(diǎn)： ?高的 簇內(nèi) 相似性 ?低的 簇間 相似性 ?聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實(shí)現(xiàn)； ?聚類方法的好壞還取決于該方法是能發(fā)現(xiàn)某些還是所有的 隱含模式 ； 聚類方法性能評價(jià) ? 可伸縮性 ? 能夠處理不同類型的屬性 ? 能發(fā)現(xiàn)任意形狀的簇 ? 在決定輸入?yún)?shù)的時(shí)候，盡量不需要特定的領(lǐng)域知識； ? 能夠處理噪聲和異常 ? 對輸入數(shù)據(jù)對象的順序不敏感 ? 能處理高維數(shù)據(jù) ? 能產(chǎn)生一個(gè)好的、能滿足用戶指定約束的聚類結(jié)果 ? 結(jié)果是可解釋的、可理解的和可用的 聚類評價(jià) ?準(zhǔn)備率：找到正確的結(jié)果數(shù) /找到結(jié)果數(shù) ?召回率：找到正確的結(jié)果數(shù) /正確結(jié)果數(shù) ? 最小誤差 :衡量不同類別 的數(shù)據(jù)與類別 中心的誤差和 。 ? 最小方差 :衡量同一類別內(nèi)數(shù)據(jù)的平均誤差和 。 21 | | | | ||iiiicxCi e i ei i x Cc x m Cxm J x m JC???? ? ????個(gè) 類 別 ， 待 聚 類 數(shù) 據(jù) ， 為 類 別 的 中 心 ，越 小 聚 類 結(jié) 果 越 好39。39。221 || ||i iixC xCS x xn? ?????常用的相似性度量方法 ?余弦夾角： Dice系數(shù)： Jaccard系數(shù)： ? ??? ????nknkjkiknkjkikjiWWWWddC o s1 1221))((),(? ??? ????? nknkjkiknkjkikjiWWWWddD i c e1 1221)(),(? ???? ???????? nknkjkiknkjkiknkjkikjiWWWWWWddJ a c c a r d1 11221),(相似性度量方法 ?Euclidean Distance ?交叉熵 ?Cosine 12211s( , )rim jmmrrim jmmmAACoAA???????ijAA1( , ) ( )rim jmmE uc l i de an A A??? ?ijAA2 2 21 1 1( ) 1( , ) l o g ( ) ( * l o g ) ( * l o g )22r n nim jmim jm im im jm jmi i iAAH A A A A A A? ? ?? ??? ? ? ?????? ? ?ijAA數(shù)據(jù)表示為向量，向量中某一維對應(yīng)數(shù)據(jù)某一特征或?qū)傩? 僅計(jì)算了數(shù)據(jù)向量中屬于同一維度特征的權(quán)值差距 。 聚類 分析（續(xù) ） ?基于層次的方法： 層次的方法對給定數(shù)據(jù)集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以被分為凝聚或分裂方法。 （Chameleon ， CURE， BIRCH） ?基于密度的方法： 只要臨近區(qū)域的密度超過某個(gè)閾值，就繼續(xù)聚類。避免僅生成球狀聚類。（DBSCAN， OPTICS， DENCLUE） ?基于網(wǎng)格的方法： 基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，所有的聚類操作都在這個(gè)量化的空間上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度很快。（ STING， CLIQUE，WaveCluster） ?基于模型的方法： 為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對模型的最好匹配。（ COBWEB， CLASSIT， AutoClass） DBSCAN ?基于密度的簇 是 密度相連 的點(diǎn)的集合 ?主要思想 ?尋找被 低密度區(qū)域 分離的 高密度區(qū)域 ?只要臨近區(qū)域的密度（單位大小上對象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)閾值，就繼續(xù)聚類 DBSCAN ?兩個(gè)參數(shù)： ?Eps: 鄰域的最大半徑 ?MinPts: 一個(gè) 核心對象 以 Eps為半徑的鄰域內(nèi)的最小頂點(diǎn)數(shù) MinPts = 5 Eps = 1 cm p q DBSCAN ?密度 = 制定半徑 (Eps)內(nèi)點(diǎn)的個(gè)數(shù) ?如果一個(gè)對象的 Eps 鄰域至少包含最小數(shù)目MinPts 個(gè)對象，則稱該對象為 核心對象 （ Core point） ?如果一個(gè)對象是非核心對象 , 但它的鄰域中有核心對象，則稱該對象為 邊界點(diǎn) （ Border point ） ?除核心對象和邊界點(diǎn)之外的點(diǎn)是 噪聲點(diǎn) （ Noise point ） DBSCAN DBSCAN ?密度可達(dá)的 （ Densityreachable） ?對于 對象 p和 核心對象 q(關(guān)于 E和 MinPts),我們稱 p是從 q(關(guān)于 E和 MinPts)直接密度可達(dá) ，若對象 p在對象 q的 E鄰域內(nèi)。 ?如果存在一個(gè)對象鏈 p1, ?, pn, p1 = q, pn = p ， pi+1 是從 pi關(guān)于 Eps和 MinPts 直接密度可達(dá)的，則對象 p是從對象q關(guān)于 Eps和 MinPts 密度可達(dá)的 。 ?密度可達(dá)性是直接密度可達(dá)性的 傳遞閉包 ，這種關(guān)系是 非對稱 的。 只有核心對象之間是 相互可達(dá) 的。 p q p1 DBSCAN ?密度相連的 （ Densityconnected） ?如果對象集合 D中存在一個(gè)對象 o，使得對象 p和 q是從 o關(guān)于 Eps 和 MinPts密度可達(dá)的，那么對象 p和 q是關(guān)于Eps 和 MinPts 密度相連的 。 ?密度相連性是一個(gè) 對稱 的關(guān)系。 p q o DBSCAN DBSCAN算法描述： ? 輸入：包含 n個(gè)對象的數(shù)據(jù)庫，半徑 ε ，最少數(shù)目 MinPts。 ? 輸出：所有生成的簇，達(dá)到密度要求。 ? 1. REPEAT ? 2. 從數(shù)據(jù)庫中抽取一個(gè)未處理過的點(diǎn)； ? 3. IF 抽出的點(diǎn)是核心點(diǎn) THEN找出所有從該點(diǎn)密度可達(dá)的對象，形成一個(gè)簇 ? 4. ELSE 抽出的點(diǎn)是邊緣點(diǎn) (非核心對象 )，跳出本次循環(huán)，尋找下一點(diǎn)； ? 5. UNTIL 所有點(diǎn)都被處理； 基于密度方法的聚類 DBSCAN 下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫（見下表），對它實(shí)施 DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對其進(jìn)行 DBSCAN算法，以下為算法的步驟（設(shè) n=12，用戶輸入 ε =1， MinPts=4） 序號 屬性 1 屬性 2 1 2 1 2 5 1 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 1 3 10 2 3 11 5 3 12 2 4 樣本事務(wù)數(shù)據(jù)庫 DBSCAN聚類過程 ? 第 1步，在數(shù)據(jù)庫中選擇一點(diǎn) 1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含 2個(gè)點(diǎn)（小于 4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 ? 第 2步，在數(shù)據(jù)庫中選擇一點(diǎn) 2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含 2個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 ? 第 3步，在數(shù)據(jù)庫中選擇一點(diǎn) 3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含 3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 4步，在數(shù)據(jù)庫中選擇一點(diǎn) 4，由于在以它為圓心的，以 1為半徑的圓內(nèi)包含 5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)（直接可達(dá) 4個(gè)，間接可達(dá) 3個(gè)），聚出的新類 {1， 3， 4， 5， 9， 10， 12}，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 5步，在數(shù)據(jù)庫中選擇一點(diǎn) 5，已經(jīng)在簇 1中，選擇下一個(gè)點(diǎn)。 ? 第 6步，在數(shù)據(jù)庫中選擇一點(diǎn) 6，由于在以它為圓心的，以 1為半徑的圓內(nèi)包含 3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 7步，在數(shù)據(jù)庫中選擇一點(diǎn) 7，由于在以它為圓心的，以 1為半徑的圓內(nèi)包含 5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)，聚出的新類 {2， 6， 7， 8， 11}，選擇下一個(gè)點(diǎn)。 DBSCAN聚類過程 ? 第 8步，在數(shù)據(jù)庫中選擇一點(diǎn) 8，已經(jīng)在簇 2中，選擇下一個(gè)點(diǎn)。 ? 第 9步，在數(shù)據(jù)庫中選擇一點(diǎn) 9，已經(jīng)在簇 1中，選擇下一個(gè)點(diǎn)。 ? 第 10步，在數(shù)據(jù)庫中選擇一點(diǎn) 10，已經(jīng)在簇 1中，選擇下一個(gè)點(diǎn)。 ? 第 11步，在數(shù)據(jù)庫中選擇一點(diǎn) 11，已經(jīng)在簇 2中，選擇下一個(gè)點(diǎn)。 ? 第 12步，選擇 12點(diǎn)，已經(jīng)在簇 1中，由于這已經(jīng)是最后一點(diǎn)所有點(diǎn)都以處理，程序終止。 序號 屬性 1 屬性 2 1 2 1 2 5 1 3 1 2 4 2 2 5 3 2 6 4 2 7 5 2 8 6 2 9 1 3 10 2 3 11 5 3 12 2 4 基于密度方法的聚類 DBSCAN 步驟 選擇的點(diǎn) 在 ε中點(diǎn)的個(gè)數(shù) 通過計(jì)算可達(dá)點(diǎn)而找到的新簇 1 1 2 無 2 2 2 無 3 3 3 無 4 4 5 簇 C1： {1， 3， 4， 5， 9， 10，12} 5 5 3 已在一個(gè)簇 C1中 6 6 3 無 7 7 5 簇 C2： {2， 6， 7， 8， 11} 8 8 2 已在一個(gè)簇 C2中 9 9 3 已在一個(gè)簇 C1中 10 10 4 已在一個(gè)簇 C1中， 11 11 2 已在一個(gè)簇 C2中 12 12 2 已在一個(gè)簇 C1中 算法執(zhí)行過程： DBSCAN Original Points Clusters 特點(diǎn)： ?抗噪聲 ? 能處理 任意形狀聚類 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則： Association Rule ? 關(guān)聯(lián)規(guī)則挖掘： ?在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 ? 應(yīng)用： ?購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)等。 ? 舉例： ?規(guī)則形式 :“ Body = Head [support, confidence]” ? buys(x, “ diapers” ) = buys(x, “ beers” ) [%, 60%] ? major(x, “ CS” ) ^ takes(x, “ DB” ) = grade(x, “ A” ) [1%, 75%] 規(guī)則度量：支持度與可信度 ?查找所有的規(guī)則 X Y = Z 具有最小支持度和可信度 ?支持度 , s, 一次交易中包含 {X 、 Y 、 Z}的 可能性 ?可信度 , c, 包含 {X 、 Y}的交易中也包含 Z的 條件概率 交易 ID 購買的商品2023 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F設(shè)最小支持度為 50%, 最小可信度為 50%, 則可得到 ? A = C (50%, %) ? C = A (50%, 100%) 買尿布的客戶 二者都買的客戶 買啤酒的客戶 ?關(guān)聯(lián)規(guī)則挖掘問題就是根據(jù)用戶指定的 最小支持度和最小可信度來尋找強(qiáng)關(guān)聯(lián)規(guī)則。 ?關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)子問題： :通過用戶給定 最小支持度 ，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。 :通過用戶給定 最小可信度 ，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。 第 1個(gè)子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。 關(guān)聯(lián)規(guī)則挖掘 基本過 程 經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集 算法 Apriori算法是通過項(xiàng)目集元素?cái)?shù)目不斷增長來完成頻繁項(xiàng)目集發(fā)現(xiàn)的。首先產(chǎn)生 1_頻繁項(xiàng)目集 L1，然后產(chǎn)生 2_頻繁項(xiàng)目集 L2，直到不能再擴(kuò)展頻繁項(xiàng)目集的元素?cái)?shù)目為止。 TID Itemset 100 1， 3， 4 200 2， 3， 5 300 1， 2， 3， 5 400 2， 5 ? 1994年， Agrawal 等人提出了著名的 Apriori 算法。 it e m s e t s u p{ 1 2 3 5 } 25%Apriori算法例子 ite m s e t s u p{ 1 2 3 } 25%