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

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

2、數(shù)目有關(guān)。目有關(guān)。2STING:統(tǒng)計(jì)信息網(wǎng)格nSTINGSTING是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為空間區(qū)域劃分為矩形單元矩形單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，矩形單元，這些單元形成了一個(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ì)

3、信息用于回答用于回答查詢查詢。3STING:統(tǒng)計(jì)信息網(wǎng)格網(wǎng)格中常用參數(shù)網(wǎng)格中常用參數(shù)ncount- -網(wǎng)格中對(duì)象數(shù)目網(wǎng)格中對(duì)象數(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)計(jì)信息網(wǎng)格5STINGS

4、TING聚類的層次結(jié)構(gòu)聚類的層次結(jié)構(gòu)STING:統(tǒng)計(jì)信息網(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)計(jì)信息網(wǎng)格7假設(shè)當(dāng)前層的屬性x的統(tǒng)計(jì)信息記為n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相對(duì)于當(dāng)前層來(lái)說(shuō)，對(duì)應(yīng)于更低一層的統(tǒng)計(jì)參數(shù)。那么n,m,s,min,max,dist可以用以下方

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

6、可以很容易的從低層單元的參數(shù)計(jì)算得到參數(shù)計(jì)算得到。9STING:統(tǒng)計(jì)信息網(wǎng)格統(tǒng)計(jì)處理思想：統(tǒng)計(jì)處理思想：n使用自頂向下的方法回答空間數(shù)據(jù)的查詢使用自頂向下的方法回答空間數(shù)據(jù)的查詢 從一個(gè)預(yù)先選擇的層次開(kāi)始通常包含少量的單從一個(gè)預(yù)先選擇的層次開(kāi)始通常包含少量的單元，為當(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è)過(guò)程直到達(dá)到底層重復(fù)這個(gè)過(guò)程直到達(dá)到底層10STING:統(tǒng)計(jì)信息網(wǎng)格算法步驟：算法步驟：1 1 從一個(gè)層次開(kāi)始從一個(gè)層次開(kāi)始2 2 對(duì)于這一層次的

7、每個(gè)單元格，我們計(jì)算查詢相關(guān)的屬性值對(duì)于這一層次的每個(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)的單元格

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

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

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

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

12、確性確性15CLIQUE :一種類似于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ù)對(duì)象的整個(gè)嵌入把每個(gè)維劃分成不重疊的區(qū)間，從而把數(shù)據(jù)對(duì)象的整個(gè)嵌入空間劃分成單元。它使用一個(gè)密度閥值識(shí)別稠密單元，一個(gè)單元是稠空間劃

13、分成單元。它使用一個(gè)密度閥值識(shí)別稠密單元，一個(gè)單元是稠密的，如果映射到它的對(duì)象超過(guò)該密度閥值密的，如果映射到它的對(duì)象超過(guò)該密度閥值16CLIQUE :一種類似于Apriori的子空間聚類方法算法算法概述概述： 算法算法需要兩個(gè)參數(shù)值，一個(gè)是網(wǎng)格的步長(zhǎng)，一具是密度閾值需要兩個(gè)參數(shù)值，一個(gè)是網(wǎng)格的步長(zhǎng)，一具是密度閾值。 網(wǎng)格步長(zhǎng)網(wǎng)格步長(zhǎng)決定了空間的劃分，而密度閾值用來(lái)定義密集網(wǎng)格決定了空間的劃分，而密度閾值用來(lái)定義密集網(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)格開(kāi)始擴(kuò)網(wǎng)格開(kāi)始擴(kuò)展，擴(kuò)展原則是若一個(gè)網(wǎng)格與已

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

15、輸入數(shù)據(jù)的大小線性地?cái)U(kuò)展，當(dāng)數(shù)據(jù)的維數(shù)增加時(shí)具有良好的可伸縮性。小線性地?cái)U(kuò)展，當(dāng)數(shù)據(jù)的維數(shù)增加時(shí)具有良好的可伸縮性。17CLIQUE :一種類似于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)-維單元維單元) )

16、至少有至少有m m個(gè)點(diǎn)。個(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)。1819Salary (10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050 = 3CLIQU

17、E :一種類似于Apriori的子空間聚類方法相關(guān)定義：相關(guān)定義：n網(wǎng)格密度：網(wǎng)格中所包含的空間對(duì)象的數(shù)目。網(wǎng)格密度：網(wǎng)格中所包含的空間對(duì)象的數(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ū)域。20CLIQUE :一種類似于Aprio

18、ri的子空間聚類方法21CLIQUE :一種類似于Apriori的子空間聚類方法以二維空間為例說(shuō)明該算法：以二維空間為例說(shuō)明該算法： =4 =422基于網(wǎng)格的聚類-總結(jié)優(yōu)點(diǎn)優(yōu)點(diǎn): :可能是非常有效的。給定每個(gè)屬性的劃分，單遍數(shù)據(jù)掃描就可以確定每可能是非常有效的。給定每個(gè)屬性的劃分，單遍數(shù)據(jù)掃描就可以確定每個(gè)對(duì)象的網(wǎng)格單元和網(wǎng)格單元的計(jì)數(shù)。此外，盡管潛在的網(wǎng)格單元數(shù)量個(gè)對(duì)象的網(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è)對(duì)象指派到一個(gè)單元并計(jì)算每個(gè)單元的密度的時(shí)間復(fù)

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

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

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

22、是一種空間統(tǒng)計(jì)量，檢驗(yàn)空間分布的變量的空間隨機(jī)性。給定數(shù)據(jù)集機(jī)性。給定數(shù)據(jù)集D D，它可以看做隨機(jī)變量，它可以看做隨機(jī)變量O O的一個(gè)樣本，我們想要的一個(gè)樣本，我們想要確定確定O O在多大程度上不同于數(shù)據(jù)空間中的均勻分布。在多大程度上不同于數(shù)據(jù)空間中的均勻分布。 25算法評(píng)估估計(jì)聚類趨勢(shì)霍普金斯統(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。也就是說(shuō)，。也就是說(shuō)，D D的空間中的每的空間中的每 個(gè)點(diǎn)都以個(gè)點(diǎn)都以 相同的概率包含在這個(gè)樣本中。對(duì)于每個(gè)點(diǎn)相同的概率包含在這個(gè)樣本中。對(duì)于每個(gè)點(diǎn)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個(gè)點(diǎn)個(gè)點(diǎn)q q1 1,q,qn n. .對(duì)于每個(gè)點(diǎn)對(duì)于每個(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 中的最近鄰之間的距離，即中

24、的最近鄰之間的距離，即 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:26算法評(píng)估估計(jì)聚類趨勢(shì)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 我們的假

25、設(shè)是同質(zhì)假設(shè)我們的假設(shè)是同質(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ì)顯著的簇。27算法評(píng)估確定簇?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ù)木垲惙治隽６?，這可以看做在聚類分析的

26、適當(dāng)?shù)木垲惙治隽６?，這可以看做在聚類分析的可壓縮性可壓縮性與與準(zhǔn)確性準(zhǔn)確性之間尋找好的平衡點(diǎn)。之間尋找好的平衡點(diǎn)。n簡(jiǎn)單的經(jīng)驗(yàn)方法：對(duì)于簡(jiǎn)單的經(jīng)驗(yàn)方法：對(duì)于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-均值這樣的算法對(duì)數(shù)據(jù)集均值這樣的算法對(duì)數(shù)據(jù)集聚類，并計(jì)算簇內(nèi)方差和聚類，并計(jì)算簇內(nèi)方差和var(k).var(k).然后，我們繪制然后，我們繪制varvar關(guān)于關(guān)于k k的曲的曲線。曲線的第一個(gè)線。曲線的第一個(gè)( (或

27、者最顯著的或者最顯著的) )拐點(diǎn)暗示拐點(diǎn)暗示”正確的正確的”簇?cái)?shù)。簇?cái)?shù)。 還有一些其他的方法，可以依情況選擇合適的方法還有一些其他的方法，可以依情況選擇合適的方法。28算法評(píng)估測(cè)定聚類質(zhì)量n對(duì)于測(cè)定聚類的質(zhì)量，我們有幾種方法可供選擇。一般而言，根據(jù)是對(duì)于測(cè)定聚類的質(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)。如果沒(méi)有基準(zhǔn)可用，則我們可以使用內(nèi)在方法，通過(guò)考慮簇的基準(zhǔn)。如果沒(méi)有基準(zhǔn)可用，則我們可以使用內(nèi)在方法，通過(guò)考慮簇的分離情況評(píng)估聚類的好壞。基準(zhǔn)可以看做一種簇標(biāo)號(hào)形式的監(jiān)督。因分離情況評(píng)估聚類的好壞?；鶞?zhǔn)可以看做一種簇標(biāo)號(hào)形式的監(jiān)督。因此，外在方法又稱為監(jiān)督方法，而內(nèi)在方法是無(wú)監(jiān)督方法。此，外在方法又稱為監(jiān)督方法，而內(nèi)在方法是無(wú)監(jiān)督方法。29算法評(píng)估外在方法外在方法核心：外在方法核心：給定基準(zhǔn)Cg，對(duì)聚類C賦予一個(gè)評(píng)分Q(C,Cg),一種外在方法是否有效很大程度上依賴于該方法使用的度量Q,度量Q應(yīng)滿足：n簇簇的的同質(zhì)性同質(zhì)性：要求聚類中的簇越純，聚類越好n簇的簇的完全性完全性：要求對(duì)