聚類分析提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法孤立點(diǎn)分析聚類（Clustering）聚類:是一個(gè)數(shù)據(jù)集聚類（Clustering）是對(duì)物理的或抽象的對(duì)象集合分組的過程；將數(shù)據(jù)集劃分為若干組（class）或簇（cluster）的過程，并使得同一個(gè)組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度；而不同組中的數(shù)據(jù)對(duì)象是不相似的。聚類生成的組稱為簇（Cluster）簇是數(shù)據(jù)對(duì)象的集合。簇內(nèi)部的任意兩個(gè)對(duì)象之間具有較高的相似度，而屬于不同簇的兩個(gè)對(duì)象間具有較高的相異度。相異度可以根據(jù)描述對(duì)象的屬性值計(jì)算，對(duì)象間的距離是最常采用的度量指標(biāo)。聚類分析：機(jī)器學(xué)習(xí)觀點(diǎn)從機(jī)器學(xué)習(xí)的角度講，簇相當(dāng)于隱藏模式。聚類是搜索簇的無監(jiān)督學(xué)習(xí)過程。與分類不同，無監(jiān)督學(xué)習(xí)不依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例，需要由聚類學(xué)習(xí)算法自動(dòng)確定標(biāo)記，而分類學(xué)習(xí)的實(shí)例或數(shù)據(jù)對(duì)象有類別標(biāo)記。聚類是觀察式學(xué)習(xí)，而不是示例式的學(xué)習(xí)。聚類分析：其它觀點(diǎn)從實(shí)際應(yīng)用的角度看，聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。就數(shù)據(jù)挖掘功能而言，聚類能夠作為一個(gè)獨(dú)立的工具獲得數(shù)據(jù)的分布狀況，觀察每一簇?cái)?shù)據(jù)的特征，集中對(duì)特定的聚簇集合作進(jìn)一步地分析。聚類分析還可以作為其他數(shù)據(jù)挖掘任務(wù)（如分類、關(guān)聯(lián)規(guī)則）的預(yù)處理步驟。數(shù)據(jù)挖掘領(lǐng)域主要研究面向大型數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)的高效實(shí)用的聚類分析算法。聚類分析的一些典型要求可擴(kuò)展性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類需要（由用戶）決定的輸入?yún)?shù)最少處理噪聲數(shù)據(jù)的能力對(duì)輸入記錄順序不敏感高維問題基于約束的聚類可解釋性和可用什么是好的聚類方法?一個(gè)好的聚類方法可以產(chǎn)生高質(zhì)量的聚類：類的內(nèi)部具有較高的相似度類間具有較低的相似度聚類結(jié)果的質(zhì)量依賴于相似度評(píng)價(jià)方法以及它們的應(yīng)用；聚類結(jié)果的質(zhì)量也取決于它發(fā)現(xiàn)隱藏模式的能力。提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法相異度矩陣（DissimilarityMatrix）

按n個(gè)對(duì)象兩兩間的相異度構(gòu)建n階矩陣（因?yàn)橄喈惗染仃囀菍?duì)稱的，只需寫出上三角或下三角即可）：

其中d(i,j)表示對(duì)象i與j的相異度，它是一個(gè)非負(fù)的數(shù)值。當(dāng)對(duì)象i和j越相似或“接近”時(shí)，d(i,j)值越接近0；而對(duì)象i和j越不相同或相距“越遠(yuǎn)”時(shí)，d(i,j)值越大。顯然，d(i,j)=d(j,i)，d(i,i)=0。相異度矩陣是對(duì)象-對(duì)象結(jié)構(gòu)的一種數(shù)據(jù)表達(dá)方式。

區(qū)間標(biāo)度變量數(shù)據(jù)標(biāo)準(zhǔn)化（數(shù)據(jù)預(yù)處理）計(jì)算平均的絕對(duì)偏差:

計(jì)算標(biāo)準(zhǔn)化的度量值(z-score)使用平均的絕對(duì)偏差比使用標(biāo)準(zhǔn)差更加健壯：異常數(shù)據(jù)的Z－分值不會(huì)變得太小，從而使得異常數(shù)據(jù)仍是可識(shí)別的。區(qū)間標(biāo)度的相似度(1)由間隔數(shù)值所描述對(duì)象之間的差異（或相似）程度可以通過計(jì)算相應(yīng)兩個(gè)對(duì)象之間距離來確定；

Minkowski舉例:i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是兩個(gè)n維的數(shù)據(jù),其中q為一個(gè)正整數(shù)；如果q=1,d

是Manhattan距離區(qū)間標(biāo)度的相似度(2)如果q=2,d是

Euclidean距離:屬性d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)可以使用權(quán)重函數(shù)二元變量二元屬性的可能性表簡(jiǎn)單匹配相關(guān)系數(shù)(不變相似性，如果二元變量是對(duì)稱的):Jaccard相關(guān)系數(shù)(非變相似性，如果二元變量是非對(duì)稱的):ObjectiObjectj二元變量的相似度示例gender是對(duì)稱屬性其余屬性是非對(duì)稱屬性可將其Y和P設(shè)為1；N設(shè)為0。標(biāo)稱變量（2）方法2:通過為標(biāo)稱變量的每個(gè)狀態(tài)創(chuàng)建一個(gè)新二元變量，能夠?qū)?biāo)稱變量表示為非對(duì)稱的二元變量。對(duì)于具有給定狀態(tài)的一個(gè)對(duì)象，代表一個(gè)狀態(tài)的二元變量置為1；而其它的二元變量置為0。序數(shù)型變量一個(gè)序數(shù)型變量可以是離散的也可以是連續(xù)的;序號(hào)是重要的,例如.,rank處理方法與間隔數(shù)值變量的處理方法類似-scaled用xif的序數(shù)值替換xif，由于每個(gè)順序變量的狀態(tài)個(gè)數(shù)可能不同。因此有必要將每個(gè)順序變量的取值范圍映射到[0,1]

區(qū)間，以便使每個(gè)變量的權(quán)值相同。用有關(guān)間隔數(shù)值變量的任一個(gè)距離計(jì)算公式，來計(jì)算用順序變量描述的對(duì)象間距離；混合類型變量一個(gè)數(shù)據(jù)庫(kù)經(jīng)常包含上述六種數(shù)據(jù)類型一種將每種類型的變量分別組織在一起，并根據(jù)每種類型的變量完成相應(yīng)的聚類分析。f

是二元變量或標(biāo)稱標(biāo)量:dij(f)=0如果xif=xjf,否則dij(f)=1f

是間隔數(shù)值變量使用:間隔數(shù)值變量距離計(jì)算f

是序數(shù)型變量和比例標(biāo)度型變量則計(jì)算順序rif

并且并將zif當(dāng)作間隔數(shù)值變量來進(jìn)行計(jì)算處理。24

相似系數(shù)的算法（1）相似系數(shù)設(shè)和是第和個(gè)樣品的觀測(cè)值，則二者之間的相似測(cè)度為:其中26(1)所選擇的親疏測(cè)度指標(biāo)在實(shí)際應(yīng)用中應(yīng)有明確的意義。如在經(jīng)濟(jì)變量分析中，(2)親疏測(cè)度指標(biāo)的選擇要綜合考慮已對(duì)樣本觀測(cè)數(shù)據(jù)實(shí)施了的變換方法和將要采用的聚類分析方法。(3)如在標(biāo)準(zhǔn)化變換之下，夾角余弦實(shí)際上就是相關(guān)系數(shù)；又如若在進(jìn)行聚類分析之前已經(jīng)對(duì)變量的相關(guān)性作了處理，則通常就可采用歐氏距離，而不必選用斜交空間距離。(4)所選擇的親疏測(cè)度指標(biāo)，還須和所選用的聚類分析方法一致。如聚類方法若選用離差平方和法，則距離只能選用歐氏距離。選擇原則提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法劃分方法給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)行，劃分方法將數(shù)據(jù)集劃分為k個(gè)子集（劃分）。其中每個(gè)子集均代表一個(gè)聚類（k≤n）。也就是說將數(shù)據(jù)分為k組，這些組滿足以下要求：每組至少應(yīng)包含一個(gè)對(duì)象；每個(gè)對(duì)象必須只能屬于某一組。需要注意的是后一個(gè)要求在一些模糊劃分方法中可以放寬。給定需要?jiǎng)澐值膫€(gè)數(shù)，一個(gè)劃分方法創(chuàng)建一個(gè)初始劃分；然后利用循環(huán)再定位技術(shù)，即通過移動(dòng)不同劃分（組）中的對(duì)象來改變劃分內(nèi)容。為獲得基于劃分聚類分析的全局最優(yōu)結(jié)果就需要窮舉所有可能的對(duì)象劃分。在分析中小規(guī)模數(shù)據(jù)集以發(fā)現(xiàn)圓形或球狀聚類時(shí)工作的很好。但為了使劃分算法能夠分析處理大規(guī)模數(shù)據(jù)集或復(fù)雜數(shù)據(jù)類型，就需要對(duì)其進(jìn)行擴(kuò)展。k-Means算法

輸入期望得到的簇的數(shù)目k，n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出使得平方誤差準(zhǔn)則函數(shù)最小化的k個(gè)簇。方法

選擇k個(gè)對(duì)象作為初始的簇的質(zhì)心；

repeat計(jì)算對(duì)象與各個(gè)簇的質(zhì)心的距離，將對(duì)象劃分到距離其最近的簇；

重新計(jì)算每個(gè)新簇的均值；

until簇的質(zhì)心不再變化。K-Means算法示例K-Means方法的變化(1)K－Means算法還有一些變化在初始k個(gè)聚類中心的選擇；差異程度計(jì)算；聚類均值的計(jì)算方法。一個(gè)常常有助于獲得好的結(jié)果的策略就是首先應(yīng)用自下而上層次算法來獲得聚類數(shù)目，并發(fā)現(xiàn)初始分類；然后再應(yīng)用循環(huán)再定位（聚類方法）來幫助改進(jìn)分類結(jié)果。K－Modes算法：該算法通過用模來替換聚類均值、采用新差異性計(jì)算方法來處理符號(hào)量，以及利用基于頻率對(duì)各聚類模進(jìn)行更新方法，從而將K－Means

算法的應(yīng)用范圍從數(shù)值量擴(kuò)展到符號(hào)量。K－Means

算法和K－Modes

算法結(jié)合到一起，就可以對(duì)采用數(shù)值量和符號(hào)量描述對(duì)象進(jìn)行聚類分析，從而構(gòu)成了K－Prototype算法。K-Means方法的變化(2)而EM（期望最大化）算法又從多個(gè)方面對(duì)K－Means

算法進(jìn)行了擴(kuò)展。其中包括：它根據(jù)描述聚類所屬程度的概率權(quán)值，將每個(gè)對(duì)象歸類為一個(gè)聚類，不是將一個(gè)對(duì)象僅歸類為一個(gè)聚類（所擁有）；也就是說在各聚類之間的邊界并不是非常嚴(yán)格。因此可以根據(jù)概率權(quán)值計(jì)算相應(yīng)的聚類均值。k-中心點(diǎn)算法

k-均值算法采用簇的質(zhì)心來代表一個(gè)簇，質(zhì)心是簇中其他對(duì)象的參照點(diǎn)。因此，k-均值算法對(duì)孤立點(diǎn)是敏感的，如果具有極大值，就可能大幅度地扭曲數(shù)據(jù)的分布。

k-中心點(diǎn)算法是為消除這種敏感性提出的，它選擇簇中位置最接近簇中心的對(duì)象（稱為中心點(diǎn)）作為簇的代表點(diǎn)，目標(biāo)函數(shù)仍然可以采用平方誤差準(zhǔn)則。

采用k-中心點(diǎn)算法有兩個(gè)好處：對(duì)屬性類型沒有局限性；通過簇內(nèi)主要點(diǎn)的位置來確定選擇中心點(diǎn)，對(duì)孤立點(diǎn)的敏感性小。

k-中心點(diǎn)算法的處理過程

首先，隨機(jī)選擇k個(gè)對(duì)象作為初始的k個(gè)簇的代表點(diǎn)，將其余對(duì)象根據(jù)其與代表點(diǎn)對(duì)象的距離分配到最近的簇；

然后，反復(fù)用非代表點(diǎn)來代替代表點(diǎn)，以改進(jìn)聚類質(zhì)量，聚類質(zhì)量用一個(gè)代價(jià)函數(shù)來估計(jì)，該函數(shù)度量對(duì)象與代表點(diǎn)對(duì)象之間的平均相異度。

k-中心點(diǎn)算法

輸入n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，期望得到的簇的數(shù)目k

輸出使得所有對(duì)象與其最近中心點(diǎn)的偏差總和最小化的k個(gè)簇

方法

選擇k個(gè)對(duì)象作為初始的簇中心

repeat對(duì)每個(gè)對(duì)象，計(jì)算離其最近的簇中心點(diǎn)，并將對(duì)象分配到該中心點(diǎn)代表的簇

隨機(jī)選取非中心點(diǎn)Orandom

計(jì)算用Orandom代替Oj形成新集合的總代價(jià)S

如果S<0，用Orandom代替Oj，形成新的k個(gè)中心點(diǎn)的集合

until不再發(fā)生變化

k-中心點(diǎn)算法的四種情況k-中心點(diǎn)算法的改進(jìn)PAM仍然采用迭代優(yōu)化策略，在開始時(shí)隨機(jī)選擇k個(gè)中心點(diǎn)，然后通過迭代找到更好的中心點(diǎn)。

CLARA算法是一個(gè)基于抽樣的方法，其主要思想是先從數(shù)據(jù)集中抽取若干樣本，在每份樣本上使用PAM算法，求得抽樣數(shù)據(jù)的中心點(diǎn)。

PAM算法直接尋找給定數(shù)據(jù)集中最佳的k個(gè)中心點(diǎn)，而CLARA算法在抽樣數(shù)據(jù)中尋找中心點(diǎn)，因此，CLARA算法的有效性取決于抽樣的合理性。如果樣本偏斜，產(chǎn)生的聚類結(jié)果也不會(huì)很好。

對(duì)k-中心點(diǎn)算法更進(jìn)一步的改進(jìn)是CLARANS算法。該算法是較早提出的面向空間數(shù)據(jù)庫(kù)聚類問題的方法，它克服了傳統(tǒng)聚類算法在大數(shù)據(jù)集上的主要缺點(diǎn)。

提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法層次方法層次方法就是通過分解所給定的數(shù)據(jù)對(duì)象集來創(chuàng)建一個(gè)層次。根據(jù)層次分解形成的方式，可以將層次方法分為自下而上和自上而下兩種類型。自下而上的層次方法從每個(gè)對(duì)象均為一個(gè)（單獨(dú)的）組開始；逐步將這些（對(duì)象）組進(jìn)行合并，直到組合并在層次頂端或滿足終止條件為止。自上而下層次方法從所有均屬于一個(gè)組開始；每一次循環(huán)將其（組）分解為更小的組；直到每個(gè)對(duì)象構(gòu)成一組或滿足終止條件為止。層次方法存在缺陷就是在進(jìn)行（組）分解或合并之后，無法回溯。凝聚的和分裂的層次聚類

廣泛采用的類間距離：最小距離法（singlelinkagemethod）廣泛采用的類間距離：最大距離法（completelinkagemethod）廣泛采用的類間距離：類平均距離法（averagelinkagemethod）類間所有樣本點(diǎn)的平均距離該法利用了所有樣本的信息，被認(rèn)為是較好的系統(tǒng)聚類法廣泛采用的類間距離：重心法（centroidhierarchicalmethod）類的重心之間的距離對(duì)異常值不敏感，結(jié)果更穩(wěn)定廣泛采用的類間距離離差平方和法（wardmethod）D2=WM－WK－WL即對(duì)異常值很敏感；對(duì)較大的類傾向產(chǎn)生較大的距離，從而不易合并，較符合實(shí)際需要。ClusterKClusterLClusterM02January2023DataMining:ConceptsandTechniques47層次方法的主要缺點(diǎn)：沒有良好的伸縮性:時(shí)間復(fù)雜度至少是O(n2)一旦一個(gè)合并或分裂被執(zhí)行，就不能修復(fù)；綜合層次聚類和其它的聚類技術(shù)：BIRCH(1996):usesCF-treeandincrementallyadjuststhequalityofsub-clustersCURE(1998):selectswell-scatteredpointsfromtheclusterandthenshrinksthemtowardsthecenteroftheclusterbyaspecifiedfractionCHAMELEON(1999):hierarchicalclusteringusingdynamicmodeling層次聚類方法的優(yōu)缺點(diǎn)層次聚類方法的優(yōu)點(diǎn)在于可以在不同粒度水平上對(duì)數(shù)據(jù)進(jìn)行探測(cè)，而且容易實(shí)現(xiàn)相似度量或距離度量。

單純的層次聚類算法終止條件含糊，而且執(zhí)行合并或分裂簇的操作后不可修正，這很可能導(dǎo)致聚類結(jié)果質(zhì)量很低。由于需要檢查和估算大量的對(duì)象或簇才能決定簇的合并或分裂，所以這種方法的可擴(kuò)展性較差。通常考慮把層次聚類方法與其他方法相結(jié)合來解決實(shí)際聚類問題。

層次聚類和其他聚類方法的有效集成可以形成多階段聚類，能夠改善聚類質(zhì)量。這類方法包括BIRCH、CURE、ROCK、Chameleon等。

提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法基于密度方法大多數(shù)劃分方法是基于對(duì)象間距離進(jìn)行聚類的。這類方法僅能發(fā)現(xiàn)圓形或球狀的聚類而在較難發(fā)現(xiàn)具有任何形狀的聚類?；诿芏确椒ň褪遣粩嘣鲩L(zhǎng)所獲得的聚類直到“鄰近”（數(shù)據(jù)對(duì)象或點(diǎn)）密度超過一定閾值（如：一個(gè)聚類中的點(diǎn)數(shù)，或一個(gè)給定半徑內(nèi)必須包含至少的點(diǎn)數(shù)）為止。這種方法可以用于消除數(shù)據(jù)中的噪聲（異常數(shù)據(jù)），以及幫助發(fā)現(xiàn)任意形狀的聚類。DBSCAN方法：根據(jù)密度閾值不斷增長(zhǎng)聚類；OPTICS方法：法提供聚類增長(zhǎng)順序以便進(jìn)行自動(dòng)或交互式數(shù)據(jù)分析。DBSCAN算法

DBSCAN（DensityBasedSpatialClusteringofApplicationswithNoise）算法是一種基于密度的聚類算法，它將足夠高密度的區(qū)域劃分為簇，能夠在含有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇。

直接密度可達(dá)點(diǎn)p的ε-鄰域記為Nε(p)，定義如下：

Nε(p)={qD|dist(p,q)≤ε}如果p，q滿足下列條件：（1）pNε(p)，（2）∣Nε(q)∣≥MinPts，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts直接密度可達(dá)的。

密度可達(dá)

如果存在一個(gè)點(diǎn)的序列p1,p2,…,pn，p1=q，pn=p，pi+1是從pi直接密度可達(dá)的，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts密度可達(dá)的。

密度相連如果存在一個(gè)點(diǎn)o，p和q都是從點(diǎn)o關(guān)于ε和MinPts密度可達(dá)的，則稱點(diǎn)p是從點(diǎn)q關(guān)于ε和MinPts密度相連的。

簇的發(fā)現(xiàn)給定參數(shù)ε和MinPts，可以分兩步發(fā)現(xiàn)簇。第一步，從數(shù)據(jù)庫(kù)中任意選取一個(gè)滿足核心點(diǎn)條件的點(diǎn)作為種子；第二步，檢索從種子點(diǎn)密度可達(dá)的所有點(diǎn)，獲得包括種子點(diǎn)在內(nèi)的簇。

DBSCAN算法DBSCAN算法可以發(fā)現(xiàn)空間數(shù)據(jù)庫(kù)中的簇和“噪聲”。但必須為每個(gè)簇指定恰當(dāng)?shù)膮?shù)ε和MinPts，及至少每個(gè)簇中的一個(gè)點(diǎn)。

為發(fā)現(xiàn)簇，DBSCAN算法從任意點(diǎn)p開始，檢索所有從點(diǎn)p關(guān)于ε和MinPts密度可達(dá)的點(diǎn)。如果p是核心點(diǎn)，就生成一個(gè)關(guān)于ε和MinPts的簇；如果p是邊界點(diǎn)，且沒有從p密度可達(dá)的點(diǎn)，DBSCAN算法就訪問數(shù)據(jù)庫(kù)中下一個(gè)點(diǎn)。由于ε和MinPts是全局參數(shù)值，如果兩個(gè)不同密度的簇彼此接近，DBSCAN可能會(huì)合并這兩個(gè)簇。當(dāng)沒有新的點(diǎn)添加到任何簇時(shí)，過程結(jié)束。

02January2023DataMining:ConceptsandTechniques57DBSCAN基本思想簇：基于密度可達(dá)性的最大的密度相連對(duì)象的集合噪音：不在任何簇中的對(duì)象邊界對(duì)象：不是核心對(duì)象，但在簇中，即至少?gòu)囊粋€(gè)核心對(duì)象直接可達(dá)核心對(duì)象邊界點(diǎn)噪音=1cmMinPts=502January2023DataMining:ConceptsandTechniques58DBSCAN算法1）任意選擇一點(diǎn)p2）如果點(diǎn)p未被歸類，那么檢查核心點(diǎn)條件3）如果該點(diǎn)為核心點(diǎn)，找到所有由p關(guān)于和MinPts密度可達(dá)的點(diǎn)4）用這些點(diǎn)形成一個(gè)新簇，給每個(gè)點(diǎn)分配一個(gè)簇ID5）如果點(diǎn)p為邊界點(diǎn)（沒有從p密度可達(dá)的點(diǎn)），則繼續(xù)訪問數(shù)據(jù)中的下一個(gè)點(diǎn)6）重復(fù)上述過程，直到所有的點(diǎn)處理完畢=1cmMinPts=502January2023DataMining:ConceptsandTechniques59不足和改進(jìn)只能發(fā)現(xiàn)密度相仿的簇對(duì)用戶定義的參數(shù)（

andMinPts）敏感計(jì)算復(fù)雜度為O(n2)采用R-樹等空間索引技術(shù)，計(jì)算復(fù)雜度為o(nlogn)02January2023DataMining:ConceptsandTechniques60圖示A和B被認(rèn)為是噪音C1和C2兩個(gè)簇合并了DBSCAN算法的優(yōu)缺點(diǎn)DBSCAN算法的優(yōu)點(diǎn)是可以在帶有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，但把確定參數(shù)的任務(wù)留給用戶，而且算法對(duì)參數(shù)是敏感的，所以在具體實(shí)施時(shí)困難很大。

提綱聚類分析簡(jiǎn)介聚類分析中的數(shù)據(jù)類型劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的聚類方法基于網(wǎng)格方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。所有聚類操作均是在這一網(wǎng)格結(jié)構(gòu)上進(jìn)行的。這種方法主要優(yōu)點(diǎn)就是處理時(shí)間由于與數(shù)據(jù)對(duì)象個(gè)數(shù)無關(guān)而僅與劃分對(duì)象空間的網(wǎng)格數(shù)相關(guān)，從而顯得相對(duì)較快。STING就是一個(gè)典型的基于網(wǎng)格的方法。CLIQUE和WAVE－Cluster是兩個(gè)基于網(wǎng)格和基于密度的聚類方法。STING算法STING（StatisticalInforationGrid-basedMethod，基于統(tǒng)計(jì)信息網(wǎng)格的方法）是針對(duì)空間數(shù)據(jù)挖掘的算法，它利用層次結(jié)構(gòu)將空間區(qū)域劃分為矩形單元，在每個(gè)單元中存儲(chǔ)對(duì)象的統(tǒng)計(jì)參數(shù)（如均值、方差、最小值、最大值、分布的類型等），用以描述有關(guān)數(shù)據(jù)特征。STING通過對(duì)數(shù)據(jù)集進(jìn)行一次掃描，計(jì)算單元中的統(tǒng)計(jì)參數(shù)。因此，若n表示對(duì)象的個(gè)數(shù)，則生成簇的時(shí)間復(fù)雜度為O(n)。

EachCellat(i-1)thlevelhas4childrenatithlevel(canbechanged)ParameterGenerationi1234ni100506010mi20.119.72120.5si2.32.22.42.1mini4.55.53.87maxi36343740distiNormalNormalNormalNoneTheparametersofthecurrentce