聚類算法的停止準則主要有兩種：根據距離來停止合併與根據集群數量來停止合併。這兩種準則的具體實施細節可以如下說明：

### 根據距離停止合併

當聚類過程中，兩個集群之間的距離達到一個預設的閾值，則可以停止合併。這意味著，如果現有的集群之間的距離超過了所設置的限度，則不再合併新集群，認為這些集群之間的差異過大，無需被合併。

**例子**：
例如，在處理相同類型的客戶數據時，若以顧客行為特徵進行聚類，如果某兩組顧客的行為模式差異很大（例如，購物頻率和消費額），而其之間的距離計算結果超過了特定閾值（例如 10），則可以認為這兩組顧客不應被歸為同一類。這時可以根據距離來停止合併。

### 根據集群數量停止合併

根據集群數量來停止合併則是在形成足夠少的集群之後停止。這通常在有明確需求或業務目的的時候會使用，特別是在希望將數據分組為特定數量的集群時。

**例子**：
如果一個市場調查企劃的目的是將消費者劃分為 4 類，那麼在聚類過程中，一旦形成了 4 個集群，則可以提前停止合併，即使目前的兩個集群之間的距離可能是較小的。在這種情況下，根據集群數量來停止比距離更符合業務需求。

### 總結

在進行聚類時，如果對於所生成的集群數量有明確的預期或需求，則根據集群數量來停止合併會是首選。而如針對數據之間的相似度和差異性想進行更嚴謹的分析，則根據距離來停止合併會更有效。各種情況下可根據具體的數據特性和實際需求來選擇合適的停止準則。
聚類算法的停止準則有哪些具體的實施細節？能否舉例說明在何種情況下應根據距離來停止合併，而何時又應根據集群數量來決定？
在數據挖掘和統計學中，**層次聚類**（英語：Hierarchical clustering）是一種旨在建立聚類的層次結構的聚類分析方法。層次聚類的策略通常有兩種：

* 凝聚（Agglomerative clustering）：一種自底向上方法，從小集群開始，逐漸將其合併，形成更大的集群；
* 分裂（Divisive clustering）：一種自頂向下方法，從單個集群開始，遞歸地將其拆分成更小的集群。

凝聚和分離的操作通常用貪心算法實現，結果通常用樹狀圖展示。

標準的凝聚層次聚類（Hierarchical agglomerative clustering，HAC）算法的時間複雜度為 ${\mathcal {O}}(n^{3})$ ，空間複雜度為 $\Omega (n^{2})$ ，這使它甚至難以應用於中等規模的數據集中。對於一些特殊情況，效率最優的算法（複雜度為 ${\mathcal {O}}(n^{2})$ ）包括 SLINK（用於單連接聚類，Single-linkage clustering）和 CLINK（用於全連接聚類，Complete-linkage clustering）。當使用堆（Heap）時，一般情況下的時間複雜度降至 ${\mathcal {O}}(n^{2}\log n)$ ，該改進以更多的內存需求為代價。這種改進方法的內存開銷很多時候大到難以實際使用。

除了單連接聚類的特殊情況，除了窮舉算法（複雜度 ${\mathcal {O}}(2^{n})$ ）外，沒有算法可以保證找到最優解。

使用窮舉算法的分裂方法的複雜度為 ${\mathcal {O}}(2^{n})$ ，不過可以通過更快的啟發式方法（例如 k - 均值算法）進行分裂。

層次聚類的優點是可以採用任何有效的距離測量。當給定距離矩陣時，觀測本身是沒有必要的。

## 聚集層次聚類

本節將對上圖所示的原始數據進行聚集層次聚類（Agglomerative clustering），採取歐幾里得距離度量距離。

下圖展示了聚類結果的樹狀圖：

在給定高度切割樹，會得到一個特定精度的聚類結果。例如，在從上往下數的第二行切割會得到四個集群：{a}、{b, c}、{d, e} 和 {f}；在第三行切割會得到 {a}、{b, c}、{d, e, f}，相比之前，這是一個更粗糙（coarser）的聚類結果，集群的數量更少但集群更大。

該方法合併單獨的元素形成集群並得到層次（Hierarchy）。本例有六個元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步確定哪些元素合併到一個集群，判定標準通常是元素間的距離，選取兩個最近的形成集群。

也可以在該步構建距離矩陣（矩陣的第 i 行第 j 列的數值為 i-j 元素之間的距離）。在聚類過程中，行、列被合併並形成新的距離。該方法為實現聚集層次聚類的通用方法，同時對緩存集群之間的距離有益。單連接聚類是一個簡單的聚集層次聚類方法。

在完成對距離最短元素 _b_ 和 _c_ 的合併後，形成的集群為：{_a_}、{_b_, _c_}、{_d_}、{_e_} 、{_f_}，對其進行進一步的合併需要度量集群 {a} 和 {b, c} 之間的距離（即兩個集群間的距離）。通常將集群 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 之間的距離定義為：

* 兩個集群的元素間的最大距離（又稱全連接聚類）：

　
: : $\max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.$

* 兩個集群的元素間的最小距離（又稱單連接聚類）：

　
: : $\min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.$

* 兩個集群的元素間的平均距離（又稱平均連接聚類（Average linkage clustering），在 UPGMA 方法中有應用）：

　
: : ${1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).$

* 所有聚類內方差的總和
* 被合併的集群方差的增加量 （Ward 法）
* 候選聚類從同一分布函數生成的概率（V-linkage）

當若干對組合具有同樣的距離且為最小時，可以隨機選取一對形成集群（生成不同的樹狀圖）；也可以同時形成不同的集群（生成唯一的樹狀圖）。

聚類算法的停止準則可以取決於數量（當形成足夠少的集群時停止）；也可以取決於距離（當兩個集群之間的距離足夠遠，以至於不能形成新集群時停止）。

## 分裂層次聚類

DIANA（DIvisive ANAlysis Clustering）是分裂層次聚類的基礎算法。 首先，所有元素歸屬同一個集群，然後分裂集群，直到所有元素都獨立成群。由於存在 $O(2^{n})$ 種方法進行分裂，因此需要啟發式（Heuristics）算法實現。DIANA 選擇平均異同度（Average dissimilarity）最大的元素，然後將所有與新集群相似度高於其餘集群的元素劃分到該集群。

## 軟體

### 開源軟體

* ALGLIB 用 C++ 和 C# 實現了多種層次聚類算法
* ELKI 實現了多種層次聚類算法
* Julia 在 Clustering.jl 包中實現了層次聚類
* Octave（GNU 對 MATLAB 的兼容實現）實現了層次聚類（函數 linkage）
* Orange（一個數據挖掘軟體套件）實現了帶有交互式樹狀圖可視層次聚類
* R 有內置的函數和包，提供層次聚類的函數
* SciPy 在 Python 中實現了層次聚類
* Scikit-learn 也在 Python 中實現了層次聚類
* Weka 實現了層次聚類

### 商業軟體

* MATLAB 中有層次聚類分析
* SAS 在 PROC CLUSTER 中包含層次聚類分析
* Mathematica 有一個層次聚類包
* NCSS 中實現了層次聚類分析
* SPSS 中包括層次聚類分析
* Qlucore Omics Explorer 中包括分層聚類分析
* Stata 中包括層次聚類分析
* CrimeStat 中實現了近鄰層次聚類算法
## 聚集層次聚類

本節將對上圖所示的原始數據進行聚集層次聚類（Agglomerative clustering），採取歐幾里得距離度量距離。

下圖展示了聚類結果的樹狀圖：

在給定高度切割樹，會得到一個特定精度的聚類結果。例如，在從上往下數的第二行切割會得到四個集群：{a}、{b, c}、{d, e} 和 {f}；在第三行切割會得到 {a}、{b, c}、{d, e, f}，相比之前，這是一個更粗糙（coarser）的聚類結果，集群的數量更少但集群更大。

該方法合併單獨的元素形成集群並得到層次（Hierarchy）。本例有六個元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步確定哪些元素合併到一個集群，判定標準通常是元素間的距離，選取兩個最近的形成集群。

也可以在該步構建距離矩陣（矩陣的第 i 行第 j 列的數值為 i-j 元素之間的距離）。在聚類過程中，行、列被合併並形成新的距離。該方法為實現聚集層次聚類的通用方法，同時對緩存集群之間的距離有益。單連接聚類是一個簡單的聚集層次聚類方法。

在完成對距離最短元素 _b_ 和 _c_ 的合併後，形成的集群為：{_a_}、{_b_, _c_}、{_d_}、{_e_} 、{_f_}，對其進行進一步的合併需要度量集群 {a} 和 {b, c} 之間的距離（即兩個集群間的距離）。通常將集群 ${\mathcal {A}}$ 和 ${\mathcal {B}}$ 之間的距離定義為：

* 兩個集群的元素間的最大距離（又稱全連接聚類）： 注意這個算法可以以下方式簡化：其一，"has been visited" 和 "belongs to cluster C" 可被結合起來，另外 "expandCluster" 副程式不必被抽出來，因為它只在一個位置被調用。以上算法沒有以簡化方式呈現，以反映原本出版的版本。另外，regionQuery 是否包含 P 並不重要，它等價於改變 MinPts 的值。

## 複雜度

DBSCAN 對資料庫裡的每一點進行訪問，可能多於一次（例如作為不同聚類的候選者），但在現實的考慮中，時間複雜度主要受 regionQuery 的調用次數影響，DBSCAN 對每點都進行剛好一次調用，且如果使用了特別的編號結構，則總平均時間複雜度為 $O(n\log {n})$ ，最差時間複雜度則為 $O(n^{2})$ 。可以使用 $O(n^{2})$ 空間複雜度的距離矩陣以避免重複計算距離，但若不使用距離矩陣，DBSCAN 的空間複雜度為 $O(n)$ 。

## 優點

1. 相比 K - 平均算法，DBSCAN 不需要預先聲明聚類數量。
2. DBSCAN 可以找出任何形狀的聚類，甚至能找出一個聚類，它包圍但不連接另一個聚類，另外，由於 MinPts 參數，single-link effect （不同聚類以一點或極幼的線相連而被當成一個聚類）能有效地被避免。
3. DBSCAN 能分辨噪音（局外點）。
4. DBSCAN 只需兩個參數，且對資料庫內的點的次序幾乎不敏感（兩個聚類之間邊緣的點有機會受次序的影響被分到不同的聚類，另外聚類的次序會受點的次序的影響）。
5. DBSCAN 被設計成能配合可加速範圍訪問的資料庫結構，例如 R\* 樹。
6. ## 基礎知識

考慮在某空間裡將被聚類的點集合，為了進行 DBSCAN 聚類，所有的點被分為_核心點_、_(密度) 可達點_及_局外點_，詳請如下：

* 如果一個點 _p_ 在距離 _ε_ 範圍內有至少 minPts 個點 (包括自己)，則這個點被稱為_核心點_，那些 _ε_ 範圍內的則被稱為_由 p 直接可達的。_根據定義，沒有任何點是由非核心點直接可達的。
* 如果存在一條道路 _p_1, ..., _pn_ ，有 _p_1 = _p_ 和 _pn_ = _q_， 且每個 _p_i+1 都是由 pi 直接可達的 (道路上除了 q 以外所有點都一定是核心點)，則稱 q 是_由 p 可達的_。
* 所有不由任何點可達的點都被稱為局外點。

如果 p 是核心點，則它與所有由它可達的點 (包括核心點和非核心點) 形成一個聚類，每個聚類擁有最少一個核心點，非核心點也可以是聚類的一部分，但它是在聚類的「邊緣」位置，因為它不能達至更多的點。

「可達性」（英文：Reachability ）不是一個對稱關係，因為根據定義，沒有點是由非核心點可達的，但非核心點可以是由其他點可達的。所以為了正式地界定 DBSCAN 找出的聚類，進一步定義兩點之間的「連結性」（英文：Connectedness） ：如果存在一個點 _o_ 使得點 _p_ 和點 _q_ 都是由 _o_ 可達的，則點 _p_ 和點 _q_ 被稱為 (密度) 連結的，而連結性是一個對稱關係。

定義了連結性之後，每個聚類都符合兩個性質： 在數據挖掘和統計學中，**層次聚類**（英語：Hierarchical clustering）是一種旨在建立聚類的層次結構的聚類分析方法。層次聚類的策略通常有兩種：

* 凝聚（Agglomerative clustering）：一種自底向上方法，從小集群開始，逐漸將其合併，形成更大的集群；
* 分裂（Divisive clustering）：一種自頂向下方法，從單個集群開始，遞歸地將其拆分成更小的集群。

凝聚和分離的操作通常用貪心算法實現，結果通常用樹狀圖展示。

標準的凝聚層次聚類（Hierarchical agglomerative clustering，HAC）算法的時間複雜度為 ${\mathcal {O}}(n^{3})$ ，空間複雜度為 $\Omega (n^{2})$ ，這使它甚至難以應用於中等規模的數據集中。對於一些特殊情況，效率最優的算法（複雜度為 ${\mathcal {O}}(n^{2})$ ）包括 SLINK（用於單連接聚類，Single-linkage clustering）和 CLINK（用於全連接聚類，Complete-linkage clustering）。當使用堆（Heap）時，一般情況下的時間複雜度降至 ${\mathcal {O}}(n^{2}\log n)$ ，該改進以更多的內存需求為代價。這種改進方法的內存開銷很多時候大到難以實際使用。

除了單連接聚類的特殊情況，除了窮舉算法（複雜度 ${\mathcal {O}}(2^{n})$ ）外，沒有算法可以保證找到最優解。

使用窮舉算法的分裂方法的複雜度為 ${\mathcal {O}}(2^{n})$ ，不過可以通過更快的啟發式方法（例如 k - 均值算法）進行分裂。

層次聚類的優點是可以採用任何有效的距離測量。當給定距離矩陣時，觀測本身是沒有必要的。