數(shù)據(jù)挖掘2015最新精品課程完整課件(第15講)---基于網(wǎng)格的聚類算法

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

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

3、信息用于回答用于回答查詢查詢。3STING:統(tǒng)計信息網(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（分布類（分布類型未知）型未知）4STING:統(tǒng)計信息網(wǎng)格5STINGS

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

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

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

7、每個單元格，我們計算查詢相關(guān)的屬性值對于這一層次的每個單元格，我們計算查詢相關(guān)的屬性值3 3 從計算的屬性值及其約束條件中，我們將每一個單元格標(biāo)從計算的屬性值及其約束條件中，我們將每一個單元格標(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ìn)行計算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)的單元格

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

9、區(qū)至少有c c棟房屋棟房屋, ,至少至少d%d%的房的房屋其價格在屋其價格在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)中的下一層。這個處理過程反復(fù)進(jìn)行。直處理層次結(jié)構(gòu)中的下一層。這個處理過程反復(fù)進(jìn)行。直 到到達(dá)最底層到到達(dá)最底層 。最后返回滿足查詢要求的相關(guān)單元的區(qū)域。最后返回滿足查詢要求的相關(guān)單元的區(qū)域。 查找結(jié)束查找結(jié)束 。 13STING:統(tǒng)計

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

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

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

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

14、知密集區(qū)域內(nèi)的網(wǎng)格鄰接并且其自身也展，擴(kuò)展原則是若一個網(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)格被遍歷。以自動地再繼續(xù)掃描網(wǎng)格并重復(fù)上述過程，直至所有網(wǎng)格被遍歷。以自動地發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中，并且它對元組發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中，并且它對元組的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。它隨輸入數(shù)據(jù)的大的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。它隨

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

16、至少有至少有m m個點。個點。 如下圖嵌入數(shù)據(jù)空間包括如下圖嵌入數(shù)據(jù)空間包括3 3個維：個維： age,salaryage,salary和和vacationvacation。例如，子空間。例如，子空間ageage和和salarysalary中的一個二維中的一個二維 單元包含單元包含m m個點，僅當(dāng)該單元在每個維上的投影都至少包含個點，僅當(dāng)該單元在每個維上的投影都至少包含m m個點。個點。1819Salary (10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050 = 3CLIQU

17、E :一種類似于Apriori的子空間聚類方法相關(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的密度的密度 時，網(wǎng)格時，網(wǎng)格g g是是 密集網(wǎng)格，否則是非密集網(wǎng)格。密集網(wǎng)格，否則是非密集網(wǎng)格。n網(wǎng)格刻度連通區(qū)域：設(shè)網(wǎng)格刻度連通區(qū)域：設(shè)GridsGrids為一個網(wǎng)格集合，若集合中的為一個網(wǎng)格集合，若集合中的所有網(wǎng)格相互鄰接且均是密集網(wǎng)格，則稱所有網(wǎng)格相互鄰接且均是密集網(wǎng)格，則稱GridGrid是網(wǎng)格是網(wǎng)格 密度連通區(qū)域。密度連通區(qū)域。20CLIQUE :一種類似于Aprio

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

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

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

21、給定的數(shù)據(jù)集是否具有可以導(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ī)性的統(tǒng)計檢驗來實現(xiàn)。來實現(xiàn)。為了解釋這一思想，我們考慮一種簡單但有效的統(tǒng)計量為了解釋這一思想，我們考慮一種簡單但有效的統(tǒng)計量霍普金斯霍普金斯統(tǒng)計量統(tǒng)計量。n霍普金斯統(tǒng)計量霍普金斯統(tǒng)計量是一種空間統(tǒng)計量，檢驗空間分布的變量的空間隨

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

23、 in),),我們找出我們找出 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個點個點q q1 1,q,qn 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 中的最近鄰之間的距離，即中

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

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

26、適當(dāng)?shù)木垲惙治隽６龋@可以看做在聚類分析的可壓縮性可壓縮性與與準(zhǔn)確性準(zhǔn)確性之間尋找好的平衡點。之間尋找好的平衡點。n簡單的經(jīng)驗方法：對于簡單的經(jīng)驗方法：對于n n個點的數(shù)據(jù)集，設(shè)置簇數(shù)個點的數(shù)據(jù)集，設(shè)置簇數(shù)p p大約為大約為n/2.在期在期望情況下，每個簇大約有望情況下，每個簇大約有2n個點。個點。n肘方法：給點肘方法：給點k0,k0,我們可以使用一種像我們可以使用一種像k-k-均值這樣的算法對數(shù)據(jù)集均值這樣的算法對數(shù)據(jù)集聚類，并計算簇內(nèi)方差和聚類，并計算簇內(nèi)方差和var(k).var(k).然后，我們繪制然后，我們繪制varvar關(guān)于關(guān)于k k的曲的曲線。曲線的第一個線。曲線的第一個( (或

27、者最顯著的或者最顯著的) )拐點暗示拐點暗示”正確的正確的”簇數(shù)。簇數(shù)。 還有一些其他的方法，可以依情況選擇合適的方法還有一些其他的方法，可以依情況選擇合適的方法。28算法評估測定聚類質(zhì)量n對于測定聚類的質(zhì)量，我們有幾種方法可供選擇。一般而言，根據(jù)是對于測定聚類的質(zhì)量，我們有幾種方法可供選擇。一般而言，根據(jù)是否有基準(zhǔn)可用，這些方法可以可以分成兩類。這里，基準(zhǔn)是一種理想否有基準(zhǔn)可用，這些方法可以可以分成兩類。這里，基準(zhǔn)是一種理想的聚類，通常由專家構(gòu)建。的聚類，通常由專家構(gòu)建。n如果有基準(zhǔn)可用，則外在方法可以使用它。外在方法比較聚類結(jié)構(gòu)和如果有基準(zhǔn)可用，則外在方法可以使用它。外在方法比較聚類結(jié)構(gòu)和基準(zhǔn)。如果沒有基準(zhǔn)可用，則我們可以使用內(nèi)在方法，通過考慮簇的基準(zhǔn)。如果沒有基準(zhǔn)可用，則我們可以使用內(nèi)在方法，通過考慮簇的分離情況評估聚類的好壞?；鶞?zhǔn)可以看做一種簇標(biāo)號形式的監(jiān)督。因分離情況評估聚類的好壞。基準(zhǔn)可以看做一種簇標(biāo)號形式的監(jiān)督。因此，外在方法又稱為監(jiān)督方法，而內(nèi)在方法是無監(jiān)督方法。此，外在方法又稱為監(jiān)督方法，而內(nèi)在方法是無監(jiān)督方法。29算法評估外在方法外在方法核心：外在方法核心：給定基準(zhǔn)Cg，對聚類C賦予一個評分Q(C,Cg),一種外在方法是否有效很大程度上依賴于該方法使用的度量Q,度量Q應(yīng)滿足：n簇簇的的同質(zhì)性同質(zhì)性：要求聚類中的簇越純，聚類越好n簇的簇的完全性完全性：要求對