基于密度的聚類和基于網(wǎng)格的兩大聚類算法

1、數(shù)據(jù)挖掘Data Mining肖婷112090501 第十章第十章 聚類聚類 2基于密度的聚類方法n劃分和層次方法旨在發(fā)現(xiàn)球狀簇。他們很難發(fā)現(xiàn)劃分和層次方法旨在發(fā)現(xiàn)球狀簇。他們很難發(fā)現(xiàn)任意形狀的簇。任意形狀的簇。n改進(jìn)思想，將改進(jìn)思想，將簇簇看作數(shù)據(jù)空間中由低密度區(qū)域分看作數(shù)據(jù)空間中由低密度區(qū)域分隔開的高密度對象區(qū)域。這是基于密度的聚類方隔開的高密度對象區(qū)域。這是基于密度的聚類方法的主要策略。法的主要策略。n基于密度的聚類方法可以用來過濾噪聲孤立點(diǎn)數(shù)基于密度的聚類方法可以用來過濾噪聲孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。據(jù)，發(fā)現(xiàn)任意形狀的簇。DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類

2、 OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)DENCLUE:基于密度分布函數(shù)的聚類基于密度分布函數(shù)的聚類 3DBSCANn基于密度的簇基于密度的簇是是密度相連密度相連的點(diǎn)的集合的點(diǎn)的集合n主要思想主要思想尋找被尋找被低密度區(qū)低密度區(qū)域分離的域分離的高密度高密度區(qū)域區(qū)域只要臨近區(qū)域的密度（單位大小上對象或數(shù)據(jù)點(diǎn)的數(shù)只要臨近區(qū)域的密度（單位大小上對象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)閾值，就繼續(xù)聚類目）超過某個(gè)閾值，就繼續(xù)聚類 4DBSCANn兩個(gè)參數(shù)：兩個(gè)參數(shù)：EpsEps: : 鄰域的最大半徑鄰域的最大半徑MinPtsMinPts: : 一個(gè)一個(gè)核心對象核心對象以以 EpsEps為半徑

3、的鄰域內(nèi)的最小為半徑的鄰域內(nèi)的最小頂點(diǎn)數(shù)頂點(diǎn)數(shù)MinPts = 5Eps = 1 cmpq5DBSCANn密度密度 = = 制定半徑制定半徑 ( (Eps) )內(nèi)點(diǎn)的個(gè)數(shù)內(nèi)點(diǎn)的個(gè)數(shù)n如果一個(gè)對象的如果一個(gè)對象的 EpsEps 鄰域至少包含最小數(shù)目鄰域至少包含最小數(shù)目MinPts 個(gè)對象，則稱該對象為個(gè)對象，則稱該對象為核心對象核心對象（Core point）n如果一個(gè)對象是非核心對象如果一個(gè)對象是非核心對象, , 但它的鄰域中有核但它的鄰域中有核心對象，則稱該對象為心對象，則稱該對象為邊界點(diǎn)邊界點(diǎn)（ Border point ）n除核心對象和邊界點(diǎn)之外的點(diǎn)是除核心對象和邊界點(diǎn)之外的點(diǎn)是噪聲點(diǎn)噪

4、聲點(diǎn)（ Noise point ）6DBSCAN7DBSCAN密度可達(dá)的密度可達(dá)的（Density-reachable）對于對于對象對象p p和和核心對象核心對象q q( (關(guān)于關(guān)于E E和和MinPtsMinPts),),我們稱我們稱p p是從是從q(q(關(guān)關(guān)于于E E和和MinPtsMinPts) )直接密度可達(dá)直接密度可達(dá)，若對象，若對象p p在對象在對象q q的的E E鄰域內(nèi)。鄰域內(nèi)。如果存在一個(gè)對象鏈如果存在一個(gè)對象鏈 p p1 1, , , , p pn n, , p p1 1 = = q q, , p pn n = = p p ，p pi+1 i+1 是從是從p pi i關(guān)于關(guān)于

5、EpsEps和和MinPtsMinPts 直接密度可達(dá)的，則對象直接密度可達(dá)的，則對象p p是從對象是從對象q q關(guān)于關(guān)于EpsEps和和MinPtsMinPts 密度可達(dá)的。密度可達(dá)的。密度可達(dá)性是直接密度可達(dá)性的密度可達(dá)性是直接密度可達(dá)性的傳遞閉包傳遞閉包，這種關(guān)系是，這種關(guān)系是非非對稱對稱的。的。 只有核心對象之間是只有核心對象之間是相互可達(dá)相互可達(dá)的。的。pqp18DBSCANn密度相連的密度相連的（Density-connected）如果對象集合如果對象集合D D中存在一個(gè)對象中存在一個(gè)對象o o，使得對象，使得對象p p和和q q是從是從o o關(guān)于關(guān)于EpsEps 和和 MinPt

6、sMinPts密度可達(dá)的，那么對象密度可達(dá)的，那么對象p p和和q q是關(guān)于是關(guān)于EpsEps 和和 MinPtsMinPts 密度相連的。密度相連的。密度相連性是一個(gè)密度相連性是一個(gè)對稱對稱的關(guān)系。的關(guān)系。pqo9DBSCAN: 算法算法：算法：DBSCAN輸入：輸入：D-數(shù)據(jù)對象集合數(shù)據(jù)對象集合 ；Eps-鄰域或稱為半徑鄰域或稱為半徑 ； MinPts-密度閾值密度閾值輸出：基于密度的簇的集合輸出：基于密度的簇的集合方法：方法：Step1 讀取讀取D中任意一個(gè)未分類的對象中任意一個(gè)未分類的對象p；Step2 檢索出與檢索出與p的距離不大于的距離不大于Eps的所有對象的所有對象Neps(p)

7、； Step3 如果如果 |Neps(p)|MinPts，則剔除已經(jīng)打上標(biāo)記的，則剔除已經(jīng)打上標(biāo)記的對象，將余下的未分類對象打上類標(biāo)簽對象，將余下的未分類對象打上類標(biāo)簽newid，然后壓入堆棧；，然后壓入堆棧；Step6 Seeds.pop，判斷，判斷Seeds是否為空，是，則執(zhí)行是否為空，是，則執(zhí)行Step1 ，否則執(zhí)行，否則執(zhí)行Step5。10DBSCANOriginal PointsClusters特點(diǎn)：特點(diǎn)： 抗噪聲 能處理任意形狀聚類11OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)n對于真實(shí)的，高維的數(shù)據(jù)集合而言，參數(shù)的設(shè)置對于真實(shí)的，高維的數(shù)據(jù)集合而言，參數(shù)的設(shè)置通常是依靠經(jīng)驗(yàn)，難以確定。

8、通常是依靠經(jīng)驗(yàn)，難以確定。n絕大多數(shù)算法對參數(shù)值是非常敏感的：設(shè)置的細(xì)絕大多數(shù)算法對參數(shù)值是非常敏感的：設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。微不同可能導(dǎo)致差別很大的聚類結(jié)果。nOPTICSOPTICS算法通過對象排序識(shí)別聚類結(jié)構(gòu)。算法通過對象排序識(shí)別聚類結(jié)構(gòu)。nOPTICSOPTICS沒有顯式地產(chǎn)生一個(gè)數(shù)據(jù)集合簇，它為自沒有顯式地產(chǎn)生一個(gè)數(shù)據(jù)集合簇，它為自動(dòng)和交互的聚類分析計(jì)算一個(gè)動(dòng)和交互的聚類分析計(jì)算一個(gè)簇排序簇排序。n這個(gè)次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。較這個(gè)次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。較稠密中的對象在簇排序中相互靠近。稠密中的對象在簇排序中相互靠近。12OPTICS簇簇

9、排序選擇這樣的對象：即關(guān)于最小的排序選擇這樣的對象：即關(guān)于最小的E E值，它是密度可值，它是密度可達(dá)的，以便較高密度（較低達(dá)的，以便較高密度（較低E E值）的簇先完成。值）的簇先完成。n對象對象p p的核心距離：的核心距離：使使p p成為核心對象的最小成為核心對象的最小。如果。如果p p不不是核心對象，那么是核心對象，那么p p的核心距離沒有任何意義。的核心距離沒有任何意義。n可達(dá)距離：可達(dá)距離：對象對象q q到到對象對象p p的可達(dá)距離是指的可達(dá)距離是指p p的核心距離的核心距離和和p p與與q q之間歐幾里得距離之間歐幾里得距離之間的之間的較大值較大值。如果。如果p p不是核心對象，不是核

10、心對象，p p和和q q之間的可達(dá)距離沒有意義。之間的可達(dá)距離沒有意義。13OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)算法思路算法思路n首先檢查數(shù)據(jù)對象集合首先檢查數(shù)據(jù)對象集合D D中任一個(gè)對象的中任一個(gè)對象的E E鄰域。設(shè)定其鄰域。設(shè)定其可達(dá)距離為可達(dá)距離為“未定義未定義”，并確定其核心距離，然后將對象及，并確定其核心距離，然后將對象及其核心距離和可達(dá)距離寫入文件。其核心距離和可達(dá)距離寫入文件。n如果如果P P是核心對象，則將對象是核心對象，則將對象P P的的E E鄰域內(nèi)的對象鄰域內(nèi)的對象N (P)N (P)插插入到一個(gè)種子隊(duì)列中，包含在種子隊(duì)列中的對象入到一個(gè)種子隊(duì)列中，包含在種子隊(duì)列中的對象p

11、p按按到到其直其直接密度可達(dá)的最近的核心對象接密度可達(dá)的最近的核心對象q q的的可達(dá)距離可達(dá)距離排序。排序。n種子隊(duì)列中具有最小可達(dá)距離的對象被首先挑選出來，確種子隊(duì)列中具有最小可達(dá)距離的對象被首先挑選出來，確定該對象的定該對象的E E一鄰域和核心距離，一鄰域和核心距離，n然后將其該對象及其核心距離和可達(dá)距離寫入文件中，如然后將其該對象及其核心距離和可達(dá)距離寫入文件中，如果當(dāng)前對象是核心對象，則更多的用于擴(kuò)展的后選對象被插果當(dāng)前對象是核心對象，則更多的用于擴(kuò)展的后選對象被插入到種子隊(duì)列中。入到種子隊(duì)列中。n這個(gè)處理一直重復(fù)到再?zèng)]有一個(gè)新的對象被加入到當(dāng)前的這個(gè)處理一直重復(fù)到再?zèng)]有一個(gè)新的對象被

12、加入到當(dāng)前的種子隊(duì)列種子隊(duì)列 中。中。OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)n數(shù)據(jù)集的排序可以用圖形描述，有助于可視化和理解數(shù)據(jù)集數(shù)據(jù)集的排序可以用圖形描述，有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)，例如下圖是一個(gè)簡單的二維數(shù)據(jù)集的可達(dá)圖。中聚類結(jié)構(gòu)，例如下圖是一個(gè)簡單的二維數(shù)據(jù)集的可達(dá)圖。其中三個(gè)高斯其中三個(gè)高斯“凸起凸起”反映數(shù)據(jù)集中比較稠密的部分。反映數(shù)據(jù)集中比較稠密的部分。1415OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)nStep 1Step 1：有序種子隊(duì)列初始為空結(jié)果隊(duì)列初始為空：有序種子隊(duì)列初始為空結(jié)果隊(duì)列初始為空 ； nStep 2Step 2：如果所有點(diǎn)處理完畢：如果所有點(diǎn)處理完畢算法結(jié)

13、束算法結(jié)束；否則選擇一個(gè)未處理對象；否則選擇一個(gè)未處理對象（即不在結(jié)果隊(duì)列中）即不在結(jié)果隊(duì)列中）放人有序種子隊(duì)列：放人有序種子隊(duì)列： nStep 3Step 3：如果有序種子隊(duì)列為空，返回：如果有序種子隊(duì)列為空，返回Step 2Step 2，否則選擇種子隊(duì)列中的，否則選擇種子隊(duì)列中的第一個(gè)對象第一個(gè)對象P P進(jìn)行擴(kuò)張：進(jìn)行擴(kuò)張： nStep 3.1Step 3.1：如果：如果P P不是核心節(jié)點(diǎn)轉(zhuǎn)不是核心節(jié)點(diǎn)轉(zhuǎn)Step 4Step 4；否則，對；否則，對P P 的的E E鄰域內(nèi)任一鄰域內(nèi)任一未擴(kuò)張的鄰居未擴(kuò)張的鄰居q q 進(jìn)行如下處理進(jìn)行如下處理nStep 3.1.1Step 3.1.1：如果：

14、如果q q已在有序種子隊(duì)列中且從已在有序種子隊(duì)列中且從P P到到 q q的可達(dá)距離小的可達(dá)距離小于于舊值舊值，則更新，則更新q q的可達(dá)距離，并調(diào)整的可達(dá)距離，并調(diào)整q q到相應(yīng)位置以保證隊(duì)列的有序性；到相應(yīng)位置以保證隊(duì)列的有序性； nStep 3.1.2Step 3.1.2：如果：如果q q不在有序種不在有序種f f隊(duì)列中，則根據(jù)隊(duì)列中，則根據(jù)P P 到到q q的可達(dá)距離將其插的可達(dá)距離將其插入有序隊(duì)列；入有序隊(duì)列； nStep 4Step 4：從有序種子隊(duì)列中刪除：從有序種子隊(duì)列中刪除P P并將并將P P寫入結(jié)果隊(duì)列中，返回寫入結(jié)果隊(duì)列中，返回Step 3Step 3DENCLUE基于密度

15、分布函數(shù)的聚類DENCLUE是是一種一種基于基于一一組密度分布組密度分布函數(shù)的聚類算法函數(shù)的聚類算法。該。該算法的原理算法的原理是：是：p每個(gè)每個(gè)數(shù)據(jù)點(diǎn)的影響可以用一個(gè)數(shù)學(xué)函數(shù)來形式化地模擬，它描述了一個(gè)數(shù)據(jù)數(shù)據(jù)點(diǎn)的影響可以用一個(gè)數(shù)學(xué)函數(shù)來形式化地模擬，它描述了一個(gè)數(shù)據(jù)點(diǎn)在鄰域內(nèi)的影響，被稱為點(diǎn)在鄰域內(nèi)的影響，被稱為影響函數(shù)影響函數(shù)。p數(shù)據(jù)數(shù)據(jù)空間的空間的整體整體密度密度(全局密度函數(shù)全局密度函數(shù))可以可以被模擬為所有數(shù)據(jù)點(diǎn)的影響函數(shù)被模擬為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的的 總和；總和；p聚類聚類可以通過確定密度吸引點(diǎn)可以通過確定密度吸引點(diǎn)(density attractor)來得到，這里的來得到，這

16、里的密度吸引點(diǎn)密度吸引點(diǎn)是全局密度函數(shù)的局部最大值是全局密度函數(shù)的局部最大值。p一一個(gè)點(diǎn)個(gè)點(diǎn) x 是被一個(gè)密度吸引點(diǎn)是被一個(gè)密度吸引點(diǎn) x*密度吸引的，如果存在一組點(diǎn)密度吸引的，如果存在一組點(diǎn) x0，x1，,xk，使得，使得x0=x，xk=x*，對，對 0ik，xi-1 的梯度是在的梯度是在 xi的的方向方向上，也就上，也就是說是說xi-1在在xi的方向上變化最快。的方向上變化最快。 p使用一個(gè)使用一個(gè)步進(jìn)式爬山步進(jìn)式爬山過程，把待分析的數(shù)據(jù)分配到密度吸引點(diǎn)過程，把待分析的數(shù)據(jù)分配到密度吸引點(diǎn) x*所代表的所代表的簇中。簇中。16DENCLUE基于密度分布函數(shù)的聚類17DENCLUE基于密度分

17、布函數(shù)的聚類算法步驟：算法步驟：（1）對數(shù)據(jù)點(diǎn)占據(jù)的空間推導(dǎo)密度函數(shù)；）對數(shù)據(jù)點(diǎn)占據(jù)的空間推導(dǎo)密度函數(shù)；（2）通過沿密度增長最大的方向）通過沿密度增長最大的方向(即梯度方向即梯度方向)移動(dòng)，識(shí)別移動(dòng)，識(shí)別密度函數(shù)的密度函數(shù)的局局 部最大點(diǎn)（這是局部吸引點(diǎn)）部最大點(diǎn)（這是局部吸引點(diǎn)），將每個(gè)點(diǎn)關(guān)聯(lián)到一個(gè)密度吸引點(diǎn)；將每個(gè)點(diǎn)關(guān)聯(lián)到一個(gè)密度吸引點(diǎn)；（3）定義與特定的密度吸引點(diǎn)相關(guān)聯(lián)的點(diǎn)構(gòu)成的簇；）定義與特定的密度吸引點(diǎn)相關(guān)聯(lián)的點(diǎn)構(gòu)成的簇；（4）丟棄）丟棄與非平凡與非平凡密度吸引點(diǎn)密度吸引點(diǎn)相關(guān)聯(lián)的簇（密度吸引點(diǎn)相關(guān)聯(lián)的簇（密度吸引點(diǎn) x稱為非平凡密稱為非平凡密 度吸引點(diǎn)，如果度吸引點(diǎn)，如果f*(x)

18、(其其中中f*是密度函數(shù)是密度函數(shù),是指定的閥值是指定的閥值) )；（5）若兩個(gè)密度吸引點(diǎn)之間存在若兩個(gè)密度吸引點(diǎn)之間存在密度大于或等于密度大于或等于的路徑的路徑，則合并他們，則合并他們 所代表的所代表的簇。簇。對所有的密度吸引點(diǎn)重復(fù)此過程，直到不再改變時(shí)對所有的密度吸引點(diǎn)重復(fù)此過程，直到不再改變時(shí) 算法中止算法中止。1819基于密度的聚類方法n主要特征：主要特征：發(fā)現(xiàn)任意形狀的聚類發(fā)現(xiàn)任意形狀的聚類處理噪聲（孤立點(diǎn)數(shù)據(jù)）處理噪聲（孤立點(diǎn)數(shù)據(jù)）一次掃描一次掃描需要密度參數(shù)作為終止條件需要密度參數(shù)作為終止條件基于網(wǎng)格的聚類n聚類分析的算法有很多，其中一大類的傳統(tǒng)算法聚類分析的算法有很多，其中一大

19、類的傳統(tǒng)算法是是基于距離的基于距離的，這種基于距離的缺點(diǎn)在于只能發(fā)，這種基于距離的缺點(diǎn)在于只能發(fā)現(xiàn)球狀的簇、處理大數(shù)據(jù)集和高維數(shù)據(jù)集時(shí)不夠現(xiàn)球狀的簇、處理大數(shù)據(jù)集和高維數(shù)據(jù)集時(shí)不夠有效，另一方面它能發(fā)現(xiàn)的聚類個(gè)數(shù)常常依賴于有效，另一方面它能發(fā)現(xiàn)的聚類個(gè)數(shù)常常依賴于用戶參數(shù)的指定，這對用戶來說經(jīng)常是很困難的。用戶參數(shù)的指定，這對用戶來說經(jīng)常是很困難的。n基于網(wǎng)格基于網(wǎng)格( (ddingdding-based)-based)指將對象空間量化為有限指將對象空間量化為有限數(shù)目的數(shù)目的單元單元，形成一個(gè)，形成一個(gè)網(wǎng)格結(jié)構(gòu)網(wǎng)格結(jié)構(gòu)，所有聚類都在，所有聚類都在這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。20基于

20、網(wǎng)格的聚類n基本思想基本思想是將每個(gè)屬性的可能值分割成許多相鄰是將每個(gè)屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合（對于的討論我們的區(qū)間，創(chuàng)建網(wǎng)格單元的集合（對于的討論我們假設(shè)屬性值是序數(shù)的、區(qū)間的或者連續(xù)的）。假設(shè)屬性值是序數(shù)的、區(qū)間的或者連續(xù)的）。n每個(gè)對象落入一個(gè)網(wǎng)格單元，網(wǎng)格單元對應(yīng)的屬每個(gè)對象落入一個(gè)網(wǎng)格單元，網(wǎng)格單元對應(yīng)的屬性區(qū)間包含該對象的值。性區(qū)間包含該對象的值。n優(yōu)點(diǎn)優(yōu)點(diǎn)是它的處理速度很快，其處理時(shí)間獨(dú)立于數(shù)是它的處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。目有關(guān)。21STING:統(tǒng)計(jì)信息

21、網(wǎng)格nSTINGSTING是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為空間區(qū)域劃分為矩形單元矩形單元。針對不同級別的分辨率，通常存在多個(gè)級別的針對不同級別的分辨率，通常存在多個(gè)級別的矩形單元，矩形單元，這些單元形成了一個(gè)這些單元形成了一個(gè)層次結(jié)構(gòu)層次結(jié)構(gòu)：高層的每個(gè)單：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。元被劃分為多個(gè)低一層的單元。關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息（例如平均關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息（例如平均值、最大值和最小值）被預(yù)先計(jì)算和存儲(chǔ)。這值、最大值和最小值）被預(yù)先計(jì)算和存儲(chǔ)。這些些統(tǒng)計(jì)信息統(tǒng)計(jì)信息用于回答用于回答查詢查詢。22STI

22、NG:統(tǒng)計(jì)信息網(wǎng)格網(wǎng)格中常用參數(shù)網(wǎng)格中常用參數(shù)ncount- -網(wǎng)格中對象數(shù)目網(wǎng)格中對象數(shù)目nmean- -網(wǎng)格中所有值的平均值網(wǎng)格中所有值的平均值nstdev- -網(wǎng)格中屬性值的標(biāo)準(zhǔn)偏差網(wǎng)格中屬性值的標(biāo)準(zhǔn)偏差nmin- -網(wǎng)格中屬性值的最小值網(wǎng)格中屬性值的最小值nmax- -網(wǎng)格中屬性值的最大值網(wǎng)格中屬性值的最大值ndistribution- -網(wǎng)格中屬性值符合的網(wǎng)格中屬性值符合的分布類型。分布類型。如正如正態(tài)分布、均勻分布、指數(shù)分布或者態(tài)分布、均勻分布、指數(shù)分布或者nonenone（分布類（分布類型未知）型未知）23STING:統(tǒng)計(jì)信息網(wǎng)格24STINGSTING聚類的層次結(jié)構(gòu)聚類的層次結(jié)

23、構(gòu)STING:統(tǒng)計(jì)信息網(wǎng)格25 level i level i+1 level i+2 a cell of (i-1)th level corresponds to 4 cells of (a cell of (i-1)th level corresponds to 4 cells of (i)thi)th level level STING:統(tǒng)計(jì)信息網(wǎng)格26假設(shè)當(dāng)前層的屬性x的統(tǒng)計(jì)信息記為n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相對于當(dāng)前層來說，對應(yīng)于更低一層的統(tǒng)計(jì)參數(shù)。那么n,m,s,min,max,dist可以用以下方法計(jì)算: dist dist S

24、TING:統(tǒng)計(jì)信息網(wǎng)格27STING: 統(tǒng)計(jì)信息網(wǎng)格n當(dāng)數(shù)據(jù)加載到數(shù)據(jù)庫時(shí)。最底層的單元參數(shù)直接當(dāng)數(shù)據(jù)加載到數(shù)據(jù)庫時(shí)。最底層的單元參數(shù)直接由數(shù)據(jù)計(jì)算，若分布類型事先知道，可以用戶直由數(shù)據(jù)計(jì)算，若分布類型事先知道，可以用戶直接指定，而較高層的分布類型可以基于它對應(yīng)的接指定，而較高層的分布類型可以基于它對應(yīng)的低層單元多數(shù)的分布類型，用一個(gè)閾值過濾過程低層單元多數(shù)的分布類型，用一個(gè)閾值過濾過程的合取來計(jì)算，若低層分布彼此不同，則高層分的合取來計(jì)算，若低層分布彼此不同，則高層分布設(shè)置為布設(shè)置為nonenone。n高層單元的統(tǒng)計(jì)參數(shù)可以很容易的從低層單元的高層單元的統(tǒng)計(jì)參數(shù)可以很容易的從低層單元的參數(shù)計(jì)

25、算得到參數(shù)計(jì)算得到。28STING:統(tǒng)計(jì)信息網(wǎng)格統(tǒng)計(jì)處理思想：統(tǒng)計(jì)處理思想：n使用自頂向下的方法回答空間數(shù)據(jù)的查詢使用自頂向下的方法回答空間數(shù)據(jù)的查詢 從一個(gè)預(yù)先選擇的層次開始通常包含少量的單從一個(gè)預(yù)先選擇的層次開始通常包含少量的單元，為當(dāng)前層的每個(gè)單元計(jì)算置信區(qū)間元，為當(dāng)前層的每個(gè)單元計(jì)算置信區(qū)間n不相關(guān)的單元不再考慮不相關(guān)的單元不再考慮n當(dāng)檢查完當(dāng)前層，接著檢查下一個(gè)低層次當(dāng)檢查完當(dāng)前層，接著檢查下一個(gè)低層次n重復(fù)這個(gè)過程直到達(dá)到底層重復(fù)這個(gè)過程直到達(dá)到底層29STING:統(tǒng)計(jì)信息網(wǎng)格算法步驟：算法步驟：1 1 從一個(gè)層次開始從一個(gè)層次開始2 2 對于這一層次的每個(gè)單元格，我們計(jì)算查詢相關(guān)

26、的屬性值對于這一層次的每個(gè)單元格，我們計(jì)算查詢相關(guān)的屬性值3 3 從計(jì)算的屬性值及其約束條件中，我們將每一個(gè)單元格標(biāo)從計(jì)算的屬性值及其約束條件中，我們將每一個(gè)單元格標(biāo)注成相關(guān)或者不相關(guān)注成相關(guān)或者不相關(guān)4 4 如果這一層是底層，則轉(zhuǎn)到步驟如果這一層是底層，則轉(zhuǎn)到步驟6 6，否則就行步驟，否則就行步驟5 55 5 我們由層次結(jié)構(gòu)轉(zhuǎn)到下一層依照步驟我們由層次結(jié)構(gòu)轉(zhuǎn)到下一層依照步驟2 2進(jìn)行計(jì)算進(jìn)行計(jì)算6 6 查詢結(jié)果滿足，轉(zhuǎn)到步驟查詢結(jié)果滿足，轉(zhuǎn)到步驟8 8，否則轉(zhuǎn)到步驟，否則轉(zhuǎn)到步驟7 77 7 恢復(fù)數(shù)據(jù)到相關(guān)的單元格進(jìn)一步處理以得到滿意結(jié)果，轉(zhuǎn)恢復(fù)數(shù)據(jù)到相關(guān)的單元格進(jìn)一步處理以得到滿意結(jié)果，轉(zhuǎn)

27、到步驟到步驟8 88 8 停止停止30STING:統(tǒng)計(jì)信息網(wǎng)格應(yīng)用nSTING STING 能夠用來幫助各種不同的空間查詢。這最常見的請求查詢是區(qū)域能夠用來幫助各種不同的空間查詢。這最常見的請求查詢是區(qū)域查詢。查詢。n例如例如查詢滿足一定條件的查詢滿足一定條件的區(qū)域區(qū)域。查找加利福尼亞州地區(qū)的房屋以得到房屋所查找加利福尼亞州地區(qū)的房屋以得到房屋所在區(qū)域相關(guān)方面數(shù)據(jù)。查詢的對象是房屋，價(jià)格是其中的一個(gè)屬性。區(qū)域須在區(qū)域相關(guān)方面數(shù)據(jù)。查詢的對象是房屋，價(jià)格是其中的一個(gè)屬性。區(qū)域須滿足約束條件：哪些區(qū)域面積至少是滿足約束條件：哪些區(qū)域面積至少是A,A,單元地區(qū)至少有單元地區(qū)至少有c c棟房屋棟房屋,

28、 ,至少至少d%d%的房的房屋其價(jià)格在屋其價(jià)格在a a到到b b之間的置信之間的置信度為度為1-t.1-t.且且mn,.mAnA* *C C* *d%成立成立?) )，若相關(guān)，則標(biāo)記該網(wǎng)格為，若相關(guān)，則標(biāo)記該網(wǎng)格為relevantrelevant否則標(biāo)記為否則標(biāo)記為 not-relevant not-relevant . .處理層次結(jié)構(gòu)中的下一層。這個(gè)處理過程反復(fù)進(jìn)行。直處理層次結(jié)構(gòu)中的下一層。這個(gè)處理過程反復(fù)進(jìn)行。直 到到達(dá)最底層到到達(dá)最底層 。最后返回滿足查詢要求的相關(guān)單元的區(qū)域。最后返回滿足查詢要求的相關(guān)單元的區(qū)域。 查找結(jié)束查找結(jié)束 。 32STING:統(tǒng)計(jì)信息網(wǎng)格優(yōu)點(diǎn)如下：優(yōu)點(diǎn)如下：

29、n計(jì)算是獨(dú)立于查詢的；計(jì)算是獨(dú)立于查詢的；n有利于并行處理和增量更新；有利于并行處理和增量更新；n效率很高效率很高。STINGSTING算法掃描數(shù)據(jù)庫一次來計(jì)算單元的統(tǒng)計(jì)信息，因算法掃描數(shù)據(jù)庫一次來計(jì)算單元的統(tǒng)計(jì)信息，因此產(chǎn)生聚類的時(shí)間復(fù)雜度是此產(chǎn)生聚類的時(shí)間復(fù)雜度是o(no(n) )，其中，其中n n是對象的數(shù)目。是對象的數(shù)目。在層次結(jié)構(gòu)建立后，查詢處理時(shí)間是，這里在層次結(jié)構(gòu)建立后，查詢處理時(shí)間是，這里g g是最低層是最低層網(wǎng)格單元的數(shù)目網(wǎng)格單元的數(shù)目o(go(g) )，通常遠(yuǎn)小于，通常遠(yuǎn)小于n n。33STING:統(tǒng)計(jì)信息網(wǎng)格缺點(diǎn)如下：缺點(diǎn)如下：n如果粒度比較細(xì)，處理的代價(jià)會(huì)顯著增加；但是

30、，如果網(wǎng)如果粒度比較細(xì)，處理的代價(jià)會(huì)顯著增加；但是，如果網(wǎng)格結(jié)構(gòu)最低層的粒度太粗，將會(huì)降低聚類分析的質(zhì)量；格結(jié)構(gòu)最低層的粒度太粗，將會(huì)降低聚類分析的質(zhì)量；n在構(gòu)建一個(gè)父親單元時(shí)沒有考慮孩子單元和其相鄰單元之在構(gòu)建一個(gè)父親單元時(shí)沒有考慮孩子單元和其相鄰單元之間的關(guān)系，因此，結(jié)果簇的形狀是間的關(guān)系，因此，結(jié)果簇的形狀是isotheticisothetic，即所有的，即所有的聚類邊界或者是水平的，或者是豎直的，沒有斜的分界線聚類邊界或者是水平的，或者是豎直的，沒有斜的分界線。n盡管該技術(shù)有快速的處理速度，但可能降低簇的質(zhì)量和精盡管該技術(shù)有快速的處理速度，但可能降低簇的質(zhì)量和精確性確性34CLIQUE

31、 :一種類似于Apriori的子空間聚類方法n CLICQUE算法是基于網(wǎng)格的空間聚類算法，但它同時(shí)非常好地算法是基于網(wǎng)格的空間聚類算法，但它同時(shí)非常好地結(jié)結(jié) 合了基于合了基于密度的聚類算法思想，因此既可以像基于密度的方法發(fā)現(xiàn)任密度的聚類算法思想，因此既可以像基于密度的方法發(fā)現(xiàn)任意形狀的簇，又意形狀的簇，又可以像可以像基于網(wǎng)格的方法處理較大的多維數(shù)據(jù)集基于網(wǎng)格的方法處理較大的多維數(shù)據(jù)集。n CLIQUE把每個(gè)維劃分成不重疊的區(qū)間，從而把數(shù)據(jù)對象的整個(gè)嵌入把每個(gè)維劃分成不重疊的區(qū)間，從而把數(shù)據(jù)對象的整個(gè)嵌入空間劃分成單元。它使用一個(gè)密度閥值識(shí)別稠密單元，一個(gè)單元是稠空間劃分成單元。它使用一個(gè)密度

32、閥值識(shí)別稠密單元，一個(gè)單元是稠密的，如果映射到它的對象超過該密度閥值密的，如果映射到它的對象超過該密度閥值35CLIQUE :一種類似于Apriori的子空間聚類方法算法算法概述概述： 算法算法需要兩個(gè)參數(shù)值，一個(gè)是網(wǎng)格的步長，一具是密度閾值需要兩個(gè)參數(shù)值，一個(gè)是網(wǎng)格的步長，一具是密度閾值。 網(wǎng)格步長網(wǎng)格步長決定了空間的劃分，而密度閾值用來定義密集網(wǎng)格決定了空間的劃分，而密度閾值用來定義密集網(wǎng)格。 聚類思想：聚類思想：n算法算法首先掃描所有網(wǎng)格，當(dāng)發(fā)現(xiàn)第一個(gè)密集網(wǎng)格時(shí)，首先掃描所有網(wǎng)格，當(dāng)發(fā)現(xiàn)第一個(gè)密集網(wǎng)格時(shí)，便以該便以該網(wǎng)格開始擴(kuò)網(wǎng)格開始擴(kuò)展，擴(kuò)展原則是若一個(gè)網(wǎng)格與已知密集區(qū)域內(nèi)的網(wǎng)格鄰接并

33、且其自身也展，擴(kuò)展原則是若一個(gè)網(wǎng)格與已知密集區(qū)域內(nèi)的網(wǎng)格鄰接并且其自身也是密集的，則將該網(wǎng)格加入到該密集區(qū)域中、直到不再有這樣的網(wǎng)格被是密集的，則將該網(wǎng)格加入到該密集區(qū)域中、直到不再有這樣的網(wǎng)格被發(fā)現(xiàn)為止發(fā)現(xiàn)為止。n算法算法再繼續(xù)掃描網(wǎng)格并重復(fù)上述過程，直至所有網(wǎng)格被遍歷。以自動(dòng)地再繼續(xù)掃描網(wǎng)格并重復(fù)上述過程，直至所有網(wǎng)格被遍歷。以自動(dòng)地發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中，并且它對元組發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中，并且它對元組的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。它隨輸入數(shù)據(jù)的大的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。它隨輸入數(shù)據(jù)的大小線性地?cái)U(kuò)展

34、，當(dāng)數(shù)據(jù)的維數(shù)增加時(shí)具有良好的可伸縮性。小線性地?cái)U(kuò)展，當(dāng)數(shù)據(jù)的維數(shù)增加時(shí)具有良好的可伸縮性。36CLIQUE :一種類似于Apriori的子空間聚類方法nCLIQUECLIQUE識(shí)別候選搜索空間的主要策略是使用稠密單元關(guān)于維度的單識(shí)別候選搜索空間的主要策略是使用稠密單元關(guān)于維度的單調(diào)性。調(diào)性。n在子空間聚類的背景下，單調(diào)性陳述如下：在子空間聚類的背景下，單調(diào)性陳述如下： 一個(gè)一個(gè)k- k-維維(k1)(k1)單元單元c c至少有至少有m m個(gè)點(diǎn)，僅當(dāng)個(gè)點(diǎn)，僅當(dāng)c c的每個(gè)的每個(gè)(k-1)-(k-1)-維投影維投影 ( (它是它是(k-1)-(k-1)-維單元維單元) )至少有至少有m m個(gè)點(diǎn)。

35、個(gè)點(diǎn)。 如下圖嵌入數(shù)據(jù)空間包括如下圖嵌入數(shù)據(jù)空間包括3 3個(gè)維：個(gè)維： age,salaryage,salary和和vacationvacation。例如，子空間。例如，子空間ageage和和salarysalary中的一個(gè)二維中的一個(gè)二維 單元包含單元包含m m個(gè)點(diǎn)，僅當(dāng)該單元在每個(gè)維上的投影都至少包含個(gè)點(diǎn)，僅當(dāng)該單元在每個(gè)維上的投影都至少包含m m個(gè)點(diǎn)。個(gè)點(diǎn)。3738Salary (10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050 = 3CLIQUE :一種類似于Apri

36、ori的子空間聚類方法相關(guān)定義：相關(guān)定義：n網(wǎng)格密度：網(wǎng)格中所包含的空間對象的數(shù)目。網(wǎng)格密度：網(wǎng)格中所包含的空間對象的數(shù)目。n密集網(wǎng)格：給定刻度閾值密集網(wǎng)格：給定刻度閾值, ,當(dāng)網(wǎng)格當(dāng)網(wǎng)格g g的密度的密度 時(shí)，網(wǎng)格時(shí)，網(wǎng)格g g是是 密集網(wǎng)格，否則是非密集網(wǎng)格。密集網(wǎng)格，否則是非密集網(wǎng)格。n網(wǎng)格刻度連通區(qū)域：設(shè)網(wǎng)格刻度連通區(qū)域：設(shè)GridsGrids為一個(gè)網(wǎng)格集合，若集合中的為一個(gè)網(wǎng)格集合，若集合中的所有網(wǎng)格相互鄰接且均是密集網(wǎng)格，則稱所有網(wǎng)格相互鄰接且均是密集網(wǎng)格，則稱GridGrid是網(wǎng)格是網(wǎng)格 密度連通區(qū)域。密度連通區(qū)域。39CLIQUE :一種類似于Apriori的子空間聚類方法40

37、CLIQUE :一種類似于Apriori的子空間聚類方法以二維空間為例說明該算法：以二維空間為例說明該算法： =4 =441基于網(wǎng)格的聚類-總結(jié)優(yōu)點(diǎn)優(yōu)點(diǎn): :可能是非常有效的。給定每個(gè)屬性的劃分，單遍數(shù)據(jù)掃描就可以確定每可能是非常有效的。給定每個(gè)屬性的劃分，單遍數(shù)據(jù)掃描就可以確定每個(gè)對象的網(wǎng)格單元和網(wǎng)格單元的計(jì)數(shù)。此外，盡管潛在的網(wǎng)格單元數(shù)量個(gè)對象的網(wǎng)格單元和網(wǎng)格單元的計(jì)數(shù)。此外，盡管潛在的網(wǎng)格單元數(shù)量可能很高，但是只需要為非空單元?jiǎng)?chuàng)建網(wǎng)格。這樣，定義網(wǎng)格、將每個(gè)可能很高，但是只需要為非空單元?jiǎng)?chuàng)建網(wǎng)格。這樣，定義網(wǎng)格、將每個(gè)對象指派到一個(gè)單元并計(jì)算每個(gè)單元的密度的時(shí)間復(fù)雜度和空間復(fù)雜度對象指派

38、到一個(gè)單元并計(jì)算每個(gè)單元的密度的時(shí)間復(fù)雜度和空間復(fù)雜度為為O(m)O(m)，其中，其中，m m是點(diǎn)的個(gè)數(shù)。如果鄰接的、已占據(jù)的單元可以有效的是點(diǎn)的個(gè)數(shù)。如果鄰接的、已占據(jù)的單元可以有效的訪問（例如，通過使用搜索樹）則整個(gè)聚類過程將非常高效，例如具有訪問（例如，通過使用搜索樹）則整個(gè)聚類過程將非常高效，例如具有O(O(mlogmmlogm) )的時(shí)間復(fù)雜度的時(shí)間復(fù)雜度。缺點(diǎn)缺點(diǎn)：（：（1 1）像大多數(shù)基于密度的聚類算法一樣、基于網(wǎng)格的聚類非常依賴）像大多數(shù)基于密度的聚類算法一樣、基于網(wǎng)格的聚類非常依賴于密度閾值的選擇。（太高，簇可能或丟失；太低，本應(yīng)分開的簇可能于密度閾值的選擇。（太高，簇可能或

39、丟失；太低，本應(yīng)分開的簇可能被合并）；（被合并）；（2 2）如果存在不同密度的簇和噪聲，則也許不可能找到適合）如果存在不同密度的簇和噪聲，則也許不可能找到適合于數(shù)據(jù)空間所有部分的值；（于數(shù)據(jù)空間所有部分的值；（3 3）隨著維度的增加，網(wǎng)格單元個(gè)數(shù)迅速增）隨著維度的增加，網(wǎng)格單元個(gè)數(shù)迅速增加（指數(shù)增長）。即對于高維數(shù)據(jù)，基于網(wǎng)格的聚類傾向于效果很差。加（指數(shù)增長）。即對于高維數(shù)據(jù)，基于網(wǎng)格的聚類傾向于效果很差。42算法評估聚類評估主要包括如下任務(wù)聚類評估主要包括如下任務(wù)：n估計(jì)聚類趨勢n確定數(shù)據(jù)集中的簇?cái)?shù)n測定聚類質(zhì)量43算法評估估計(jì)聚類趨勢n聚類趨勢評估聚類趨勢評估確定給定的數(shù)據(jù)集是否具有可以

40、導(dǎo)致有意義的聚類的確定給定的數(shù)據(jù)集是否具有可以導(dǎo)致有意義的聚類的非隨機(jī)結(jié)構(gòu)。非隨機(jī)結(jié)構(gòu)。聚類要求數(shù)據(jù)的非均勻分布。聚類要求數(shù)據(jù)的非均勻分布。n“如何評估數(shù)據(jù)集的聚類趨勢如何評估數(shù)據(jù)集的聚類趨勢? ?”直觀地看，我們可以評估直觀地看，我們可以評估數(shù)據(jù)集數(shù)據(jù)集被均勻分布產(chǎn)生的概率被均勻分布產(chǎn)生的概率。這可以通過。這可以通過空間隨機(jī)性的統(tǒng)計(jì)檢驗(yàn)空間隨機(jī)性的統(tǒng)計(jì)檢驗(yàn)來實(shí)現(xiàn)。來實(shí)現(xiàn)。為了解釋這一思想，我們考慮一種簡單但有效的統(tǒng)計(jì)量為了解釋這一思想，我們考慮一種簡單但有效的統(tǒng)計(jì)量霍普金斯霍普金斯統(tǒng)計(jì)量統(tǒng)計(jì)量。n霍普金斯統(tǒng)計(jì)量霍普金斯統(tǒng)計(jì)量是一種空間統(tǒng)計(jì)量，檢驗(yàn)空間分布的變量的空間隨是一種空間統(tǒng)計(jì)量，檢驗(yàn)空

41、間分布的變量的空間隨機(jī)性。給定數(shù)據(jù)集機(jī)性。給定數(shù)據(jù)集D D，它可以看做隨機(jī)變量，它可以看做隨機(jī)變量O O的一個(gè)樣本，我們想要的一個(gè)樣本，我們想要確定確定O O在多大程度上不同于數(shù)據(jù)空間中的均勻分布。在多大程度上不同于數(shù)據(jù)空間中的均勻分布。 44算法評估估計(jì)聚類趨勢霍普金斯統(tǒng)計(jì)量霍普金斯統(tǒng)計(jì)量- -計(jì)算計(jì)算（1 1）均勻地從）均勻地從D D的空間中抽取的空間中抽取n n個(gè)點(diǎn)個(gè)點(diǎn)p p1 1,p,pn n。也就是說，。也就是說，D D的空間中的每的空間中的每 個(gè)點(diǎn)都以個(gè)點(diǎn)都以 相同的概率包含在這個(gè)樣本中。對于每個(gè)點(diǎn)相同的概率包含在這個(gè)樣本中。對于每個(gè)點(diǎn)p pi i(1(1i in),),我們找出我

42、們找出 p pi i在在D D中的最鄰近，并令中的最鄰近，并令x xi i為為p pi i與它在與它在D D中的最近鄰之間的距離，即中的最近鄰之間的距離，即 x xi i=min=mindistdist( (p pi i,v,v)()(其中其中v vD) )（2 2）均勻地從）均勻地從D D中抽取中抽取n n個(gè)點(diǎn)個(gè)點(diǎn)q q1 1,q,qn n. .對于每個(gè)點(diǎn)對于每個(gè)點(diǎn)q qi i(1(1i in),),我們找出我們找出q qi i在在 D-q D-qi i 中的最鄰近，并令中的最鄰近，并令y yi i為為q qi i它在它在D-qD-qi i 中的最近鄰之間的距離，即中的最近鄰之間的距離，即

43、y yi i=min=mindistdist( (q qi i,v,v)()(其中其中v vD,vq qi i) )（3 3）計(jì)算霍普金斯統(tǒng)計(jì)量）計(jì)算霍普金斯統(tǒng)計(jì)量H:H:45算法評估估計(jì)聚類趨勢n“霍普金斯統(tǒng)計(jì)量告訴我們數(shù)據(jù)集霍普金斯統(tǒng)計(jì)量告訴我們數(shù)據(jù)集D D有多大可能遵循數(shù)據(jù)空間的均勻有多大可能遵循數(shù)據(jù)空間的均勻分布分布?”?”如果如果D D是均勻分布的，則是均勻分布的，則yi和和xi將會(huì)很接近，因而將會(huì)很接近，因而H大約為大約為0.5。然而，如果。然而，如果D是高度傾斜的，則是高度傾斜的，則yi將顯著地小于將顯著地小于xi，因而，因而H將接將接近近0。n 我們的假設(shè)是同質(zhì)假設(shè)我們的假設(shè)是

44、同質(zhì)假設(shè)D是均勻分布的，因而不包含有意義的簇。是均勻分布的，因而不包含有意義的簇。非均勻假設(shè)非均勻假設(shè)(即即D不是均勻分布，因而包含簇不是均勻分布，因而包含簇)是備擇假設(shè)。我們可以迭是備擇假設(shè)。我們可以迭代地進(jìn)行霍普金斯統(tǒng)計(jì)量檢驗(yàn)，使用代地進(jìn)行霍普金斯統(tǒng)計(jì)量檢驗(yàn)，使用0.5作為拒絕備擇假設(shè)閾值，即如作為拒絕備擇假設(shè)閾值，即如果果H0.5，則，則D不大可能具有統(tǒng)計(jì)顯著的簇。不大可能具有統(tǒng)計(jì)顯著的簇。46算法評估確定簇?cái)?shù)l確定數(shù)據(jù)集中確定數(shù)據(jù)集中”正確的正確的”簇?cái)?shù)是重要的，因?yàn)楹线m的簇?cái)?shù)可以控制簇?cái)?shù)是重要的，因?yàn)楹线m的簇?cái)?shù)可以控制適當(dāng)?shù)木垲惙治隽６?，這可以看做在聚類分析的適當(dāng)?shù)木垲惙治隽６龋@可

45、以看做在聚類分析的可壓縮性可壓縮性與與準(zhǔn)確性準(zhǔn)確性之間尋找好的平衡點(diǎn)。之間尋找好的平衡點(diǎn)。n簡單的經(jīng)驗(yàn)方法：對于簡單的經(jīng)驗(yàn)方法：對于n n個(gè)點(diǎn)的數(shù)據(jù)集，設(shè)置簇?cái)?shù)個(gè)點(diǎn)的數(shù)據(jù)集，設(shè)置簇?cái)?shù)p p大約為大約為n/2.在期在期望情況下，每個(gè)簇大約有望情況下，每個(gè)簇大約有2n個(gè)點(diǎn)。個(gè)點(diǎn)。n肘方法：給點(diǎn)肘方法：給點(diǎn)k0,k0,我們可以使用一種像我們可以使用一種像k-k-均值這樣的算法對數(shù)據(jù)集均值這樣的算法對數(shù)據(jù)集聚類，并計(jì)算簇內(nèi)方差和聚類，并計(jì)算簇內(nèi)方差和var(kvar(k).).然后，我們繪制然后，我們繪制varvar關(guān)于關(guān)于k k的曲的曲線。曲線的第一個(gè)線。曲線的第一個(gè)( (或者最顯著的或者最顯著的) )拐點(diǎn)暗示拐點(diǎn)暗示”正確的正確的”