1.1 基於分部的空間聚類算法
k-均值算法：用戶定義 k 個聚類的質心位置--將每個數據點聚合到質心位置最近的聚類--重新計算每個聚類的質心位置--重復步驟二和步驟三，直到質心收斂。其計算復雜度為：T 為第四步的叠代次數，對用戶給出的聚類中心點和噪聲點的初始位置非常敏感。同時，在處理大量數據時，運行時間較長。
1.2 基於層次的空間聚類算法
層次聚類的目的是將數據對象分配到壹個層次結構中，它遵循兩種腳本策略：向上聚合和向下拆分。向上聚合法將每個對象視為壹個單獨的聚類，然後從整個層次結構的底層開始聚合具有相似特征的聚類，並遞歸到頂層。相反，向下拆分法將所有數據對象視為同壹個簇，然後從整個層次結構的頂層開始，逐層遞歸到底層，拆分具有不同特征的簇。其計算的事件復雜度為
1.3 基於密度的空間聚類算法
基於密度的聚類算法在發現任意形狀及其引起的數據方面具有獨特的優勢，並且不需要對聚類的數量進行初始設置。這些算法包括 DBSCAN 算法、OPTICS 算法、DENCLUE 算法、CURD 算法、增量 DBSCAN 算法、SDBDC 算法、ST-DBSCAN 算法等。DBSCAN 是第壹個被提出的基於密度的聚類算法。DBSCAN是第壹個提出的基於密度的聚類算法，它由兩個基本參數定義：空間半徑和密度閾值MinPts。
DBSCAN的基本概念：
該算法的主要缺點是計算時間復雜，因此大量空間數據的聚類過程需要經歷壹個難以忍受的耗時過程。它的另壹個缺點是無法支持多密度聚類、增量聚類和並行計算。為解決這些問題，已經開展了許多工作，這些工作可歸納為兩大類：1) 算法改進；2) 算法並行化。GirDBSCAN 被稱為最先進的 DBSCAN 算法，它基於網格劃分策略，在不損失計算精度的情況下大大降低了算法的時間復雜度。得益於網格的超規則空間結構，任何兩個網格之間的最短空間距離都可以輕松獲得。對於壹個任意點來說，它的近鄰只存在於壹個固定的網格集合內，換句話說，網格集合外的點壹定不是它的近鄰，因此這些點之間的距離計算可以省略，從而提高了 DBSCAN 算法的計算效率。基於這壹思想，Gunawan 將整個網格劃分為邊長為的正方形網格，用於基於密度的二維空間數據聚類計算，使得每個正方形網格內的最大空間距離為 因此，壹旦網格內的點數達到或超過 MinPts，則該網格內的所有點都是核心點，屬於同壹個聚類。因此，可以通過密度連接網格和密度可達網格的最大集合來計算壹個簇，從而省略了許多點到點距離的計算。Voronoi 圖技術還可用於進壹步提高 DBSCAN 算法的計算效率。然而，構建 Voronoi 圖本身需要耗費大量時間。基於這壹思想，甘和濤提出了壹種關於 p 的近似 DBSCAN 算法，以獲得近似精度的計算結果，但只需要關於 N 的線性計算時間，用於替代傳統的 DBSCAN 算法。
1.4 基於網格的聚類
基於網格的聚類算法將數據空間劃分為規則的不相交網格，然後將所有數據對象與網格映射，根據網格進行聚類。概括地說：對象空間被量化為有限數量的單元格，形成網格結構，所有聚類都在網格結構上進行。
我們將介紹 STING 算法和 CLIQUE 算法。