R 資料探勘演算法/聚類/基於密度的聚類

聚類技術在資料庫中記錄類別識別方面起著重要作用，因此它已成為資料探勘研究的主要主題之一。空間聚類技術是聚類技術的一個子集，它應用於記錄具有與某些空間語義內在相關的屬性的資料庫。前幾章介紹的大多數傳統聚類技術都適用於空間資料庫。但是，當應用於空間上下文中的類別識別等任務時，傳統技術可能無法取得良好的結果，例如，同一聚類中的元素可能沒有足夠的相似性，或者效能可能很差。

由空間聚類演算法輔助的類別識別任務具有廣泛的應用，因為在日益龐大的空間資料庫中查詢相關資訊最近已成為一項高度需求的任務。示例包括來自衛星影像的地理資料、醫學 X 射線影像處理或機器學習樣本中的模式識別。

雖然已經提出了大量用於聚類空間相關資料的技術，但其中指定的大多數傳統聚類演算法都存在一些缺點。首先，基於 k 分割槽（如基於 k 均值的）的技術僅限於以凸形方式構建的聚類。許多資料庫的聚類具有多種形狀（圖 1），因此傳統的 k 分割槽演算法將無法產生令人滿意的結果。其次，大多數技術需要資料庫的先驗知識（領域知識）來確定最佳輸入引數。例如，k 均值將預期聚類數量 k 作為輸入，而 k 必須先驗地已知才能應用於任何資料庫。在許多現實生活中的資料庫中，沒有先驗的領域知識，因此根據猜測選擇引數值可能會導致不完整和不希望的結果。最後，大多數技術不可擴充套件，這意味著它們不能用於大型資料庫，例如由數十萬個元素組成的資料庫。雖然大多數技術派生出屬於多項式執行時間複雜度類的演算法，但當它們應用於大型資料庫（例如數百萬或數十億個元素）時，成本可能會變得過高。

上述限制可以透過使用一種新方法來克服，該方法基於密度來決定每個元素將位於哪個聚類中。下一節將介紹這種新方法 DBSCAN，它代表用於在具有噪聲的大型空間資料庫中發現聚類的基於密度的演算法。

DBSCAN：基於密度的空間聚類應用於噪聲

基於資料庫密度屬性構建聚類的想法源於人類自然聚類方法。透過檢視圖 1 中顯示的二維資料庫，人們幾乎可以立即識別出三個聚類以及幾個噪聲點。聚類以及由此產生的類別很容易識別，因為它們相對於它們擁有的點具有更高的密度。另一方面，散佈在資料庫周圍的單個點是離群值，這意味著由於它們位於濃度相對較低的區域，因此不屬於任何聚類。

檔案：具有三個聚類的二維資料庫.PNG

圖 1：具有三個非凸形聚類和幾個離群值的二維空間資料庫。

此外，正如將在以下部分中解釋的那樣，DBSCAN 演算法最多需要兩個引數：密度度量和聚類的最小大小。因此，與其他技術（即 k 均值）不同，不需要先驗地估計聚類數量。最後，正如將在後面證明的那樣，即使應用於大型資料庫，DBSCAN 也是有效的。

重要概念

在描述 DBSCAN 演算法之前，必須解釋一些概念以使其完全理解。資料庫的元素可以分為兩種不同型別：邊界點，位於聚類邊緣的點，以及核心點，位於聚類內部區域。點 p 的鄰域是所有距離度量小於預定值的點的集合，稱為 Eps。因此，核心點的鄰域大小通常大於邊界點的鄰域大小。如果點 p 屬於 q 的鄰域，並且 q 的鄰域大小大於給定的常數 MinPts，則點 p 直接密度可達點 q。透過從先前的概念中規範地派生，可以定義一個通用的密度可達性：如果存在一個點鏈 p₁,..., p_n，其中 p₁ = q，p_n = p，並且 p_i+1 直接密度可達 p_i，則點 p 從 q 密度可達。然後將前述概念組合到聚類 D 的定義中

$\forall$ q,p : 如果 q $\in$ D 並且如果 q 從 p 密度可達，並且 p 的鄰域大於 MinPts 閾值，則 p 屬於 D。
$\forall$ q,p : 如果 q $\in$ D 並且 p $\in$ D，那麼一定存在一個點 t 使得 q 和 p 直接可達 t。

根據上述定義，可能存在一些點不屬於任何生成的聚類，這些點是離群值（噪聲）。換句話說，聚類 D 由一組點組成，這些點滿足一定程度的集中度，該集中度由 MinPts 和 Eps 約束設定。透過調整這些值，可以找到形狀和密度不同的聚類。

換句話說，一個簇 D 是由一組點組成的，這些點滿足一定的濃度，該濃度由 MinPts 和 Eps 約束設定。透過調整這些值，可以建立形狀和密度不同的簇。

演算法

DBSCAN 演算法（演算法 1）從隨機選擇資料庫中的一個元素 P 開始。如果 P 不是核心點，即 P 的鄰居少於 MinPts，則將其標記為噪聲。否則，它將被標記為當前簇的一部分，並將呼叫 ExpandCluster（演算法 2）函式。它的目的是找到所有從 P 密度可達的點，並且目前被標記為未分類或噪聲。儘管是一個遞迴函式，但 ExpandCluster 在沒有明確使用遞迴的情況下實現。遞迴行為是透過使用一個集合來實現的，該集合的大小隨著新密度可達點的發現而變化。當所有點都被正確分類時，演算法結束。

檔案：DBSCAN 演算法.png

最後，在識別完所有簇之後，人們可能會想知道一個邊界點是否可以同時屬於兩個簇。對於這個問題，當前實現的演算法會將模糊的點視為首先聚合它們的簇的一部分。

檔案：DBSCAN ExpandCluster 演算法.PNG

R 中的 DBSCAN

R 是一種用於統計計算的程式語言和軟體環境。除了是廣泛使用的統計分析工具外，R 還集成了多種資料探勘技術。因此，它已成為用於發現數據庫知識的簡單任務的主要工具。R 的原始碼在 GNU 通用公共許可證下免費提供，並且已移植到除 Unix 變體之外的多個平臺，例如 Windows 和 MacOS。雖然 R 主要使用命令列介面，但有幾個 GUI 可用，這提高了它的使用者友好性。DBSCAN 技術在 R 的 fpc 包中可用，由 Christian Hennig 開發，該包實現了針對固定點簇的聚類任務。DBSCAN 實現提供了高可配置性，因為它允許選擇多個引數和選項值。此外，fpc 的 DBSCAN 具有視覺化介面，可以迭代地視覺化聚類過程。

不幸的是，fpc 包相當慢，因為它主要是用 R 編寫的。DBSCAN 的一個更快版本存在於 dbscan 包中。

安裝

可以使用 R 命令列上的以下命令安裝 fpc 包

install.packages("fpc", dependencies = TRUE)

上述命令將遞迴地下載和安裝 fpc 依賴的所有包，以及 fpc 本身。

使用

要開始使用 fpc 包，必須呼叫以下命令

library('fpc')

DBSCAN 過程

fpc 包允許使用者使用以下過程直接應用 dbscan 技術

dbscan(data, eps, MinPts, scale, method, seeds, showplot, countmode)

引數

DBSCAN 過程接受以下引數

data：將被聚類的資料。它可以是資料矩陣、data.frame、差異矩陣或 dist 物件。
eps：可達距離（前面討論過）。
MinPts：可達點的最小數量（前面討論過）。
scale：用於對資料進行縮放。
method：透過約束效能配置記憶體使用情況，有三個選項
- "raw"：將資料視為原始資料並避免計算距離矩陣（節省記憶體，但可能很慢）。
- "dist"：將資料視為距離矩陣（相對較快，但記憶體消耗大）。
- "hybrid"：也需要原始資料，但會計算部分距離矩陣（速度非常快，記憶體需求適中）。
seeds：關於在 dbscan 物件中包含 isseed 向量配置，可以是 TRUE 或 FALSE。
showplot：繪圖配置
- 0：不繪圖
- 1：每次迭代繪圖
- 2：每次子迭代繪圖
countmode：NULL 或點號向量以報告進度。

前三個引數是迄今為止最重要的引數：data 是用於聚類的輸入資料；eps 和 MinPts 變數保留與之前相同的含義，即它們分別是元素之間的最小距離和形成簇所需的點數。showplot 引數與結果視覺化相關。method 引數直接影響演算法的效率，可用於在記憶體受限的環境中校準記憶體效能權衡。

例子

本節中的示例將說明 fpc 的 DBSCAN 在圖 1 所示的資料庫上的使用情況。它還將展示聚類機制作為一個迭代視覺化過程。首先，必須建立要聚類的資料

x <- matrix(scan("file.dat",1926), nrow=1926, ncol=2, byrow=TRUE); # Read 1926 points on file "file.dat".
par(bg="grey40");                                                   # Set background to gray.
plot(x);                                                           # Plot original database.
d <- dbscan(x,10,showplot = 2);                                    # Calls DBSCAN routine (eps = 10 and MinPts is set to its default, which is 5).
d;                                                                 # Shows DBSCAN result.
# Notice that setting showplot to 2 will make dbscan show the result iteratively by its sub-iterations.

輸出

DBSCAN 的輸出顯示了有關剛剛建立的簇的資訊

dbscan Pts=1926 MinPts=5 eps=20
       0 1 2  3 4   5 6   7 8   9 10 11 12 13 14 15 16 17 18 19
seed   0 8 8 12 8 844 8 312 8 616  8 18  8  8 10 10  8  8 12  8
border 4 0 0  0 0   0 0   0 0   0  0  0  0  0  0  0  0  0  0  0
total  4 8 8 12 8 844 8 312 8 616  8 18  8  8 10 10  8  8 12  8

每個簇用一列表示，行顯示它有多少個種子（核心）、邊界和總點。請注意，散佈在整個資料庫中的微小簇實際上是由多個點組成的。因此，它們被認為是有效的簇，因為 MinPts 引數沒有設定，並且它的預設值太低。

視覺化

屬於某個簇的點用不同顏色的三角形分隔。屬於同一個簇的所有點都用相同顏色的三角形分隔。不屬於任何簇的點保留與之前相同的顏色，並且如將要顯示的那樣，通常用黑色圓圈表示。此外，將 showplot 引數設定為 2 意味著在 DBSCAN 演算法的每個子迭代中，例程都會在螢幕上顯示部分簇。以下是其中的五個時刻

File:DBSCAN Iteration1.PNG File:DBSCAN Iteration2.PNG File:DBSCAN Iteration3.PNG

File:DBSCAN Iteration4.PNG File:DBSCAN Iteration5.PNG

第一張影像顯示了在呼叫 DBSCAN 例程之前（命令 plot(x)）的點。第二張影像顯示了聚類演算法的開始，第一個主要簇正在資料庫的頂部中心形成。第五張影像顯示了演算法結束時獲得的 19 個簇。

案例研究：識別天體

以下部分將討論由 DBSCAN 輔助並在空間資料庫上應用的常見類識別任務：天文學中的天體識別。

場景

透過捕捉天體發射的輻射來識別天體是天文學中一項反覆出現的工作。一個天體實體可能是電磁輻射的來源本身（例如，恆星），也可能是從其他來源反射的（例如，行星）。通常，一個實體會在不同的波長上發射輻射，這些輻射加起來可以幫助識別它的類別：它可能是一顆行星、任何型別或年齡的恆星，甚至是一個星系或其他以前未識別的奇異實體。從電磁頻譜的每個範圍內收集到的強度儲存在單獨的二維網格中（例如，一個用於紫外線，另一個用於伽馬射線）。現代天文學研究小組能夠收集和儲存數千個大維網格，每個網格代表天空中的不同視角（或影像），並使用多達幾 TB 的儲存空間。

除了捕捉實體在特定頻譜範圍內發射的電磁強度外，感測器還可能捕捉到感測器產生的噪聲，以及來自大氣和太空本身的漫射發射。傳統上，消除漫射發射和部分噪聲的方法是透過已知閾值約束相關強度。例如，只有當強度超過 5 $\rho$ rms 時才會被認為是相關的。一個更大的問題是，電磁波在不同的頻譜範圍內穿過介質時會產生不同的干涉。這種現象被稱為瑞利散射，最終會導致波在被感測器捕捉時偏轉。因此，當考慮從空間同一區域但來自不同頻譜範圍的多個影像時，必須完成以下步驟才能正確識別天體。

方法和執行

例如，考慮圖 2，它顯示了從星系中心拍攝的影像。該影像包含一個天體影像上的噪聲病理例子。以下是提取該影像上的天體物件的步驟。

步驟 1：預處理

首先，必須應用一個預處理步驟來去除噪聲和漫射發射。如前所述，這可以透過使用閾值來實現。此步驟在圖 3 中顯示，而原始影像可以在圖 2 中檢視，它代表了描繪星系中心的原始影像。閾值設定為 50，這意味著只有強度小於 50（因此更暗）的畫素才被考慮。

步驟 2：DBSCAN 聚類

其次，DBSCAN 演算法可以應用於單個畫素，將電磁頻譜每個通道的影像上的完整發射區域連結在一起。這是透過將 eps 引數設定為某個值來完成的，該值將定義源被認為所需的最小面積。eps 引數將定義以畫素為單位的距離度量。每個生成的簇將定義一個天體實體。圖 4 顯示了此步驟的結果，其中 eps 和 MinPts 引數設定為 5。

x <- matrix(scan("file.dat",1214), nrow=1214, ncol=2, byrow=TRUE);
dbscan(x,5,showplot = 2);

結果

dbscan Pts=1214 MinPts=5 eps=5
         0  1  2  3  4 5 6  7 8  9 10 11 12 13 14 15 16
seed     0 28 26 26 26 6 6 18 2 10 18  8 16 16  8 28 20
border 226  0  0  0  0 0 0  0 4  0  0  0  0  0  0  0  0
total  226 28 26 26 26 6 6 18 6 10 18  8 16 16  8 28 20
        17 18 19 20 21 22 23 24 25 26 27 28 29  30 31 32
seed    14 14  8 18  6  6  6 14  6  6  6 14  8 112  6 18
border   0  0  0  0  0  0  0  0  0  0  0  0  0   0  0  0
total   14 14  8 18  6  6  6 14  6  6  6 14  8 112  6 18
        33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
seed     6 20 20 20 16 10  6  6  8 14  8 10 14 10  6 36
border   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  2
total    6 20 20 20 16 10  6  6  8 14  8 10 14 10  6 38
       49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
seed   24  6  6 14  6 24 18  6 16  6 14 28 26 26 10 10  8
border  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
total  24  6  6 14  6 24 18  6 16  6 14 28 26 26 10 10  8

步驟 3：多光譜相關

識別完所有簇後，可以應用多光譜相關過程來考慮來自每個電磁波長的結果（生成的簇）。這裡不會詳細說明，但一種常見的方法是隻考慮與電磁頻譜的其他通道上的某些閾值足夠接近的簇，這些簇有一個或多個對應物。

分析

圖 4 顯示了 DBSCAN 演算法在 MinPts 和 eps 設定為 5 後執行聚類後的結果。從結果來看，我們可以看到許多孤立點沒有被聚類，因為 MinPts 引數透過元素的最小值限制了簇的大小。此限制將刪除被認為是不相關的發射源的太小的簇，因此被歸類為噪聲。透過限制 MinPts 引數，強度較弱的天體（例如，它們可能太遠或沒有發出強輻射）將從結果中排除。這通常是可取的，但當必須分析由較小區域定義的發射源時，可能會成為問題。因此，必須仔細選擇 MinPts 值，因為它可能會極大地改變結果。

儘管如此，還是發現了 64 個簇和 224 個離群值。大多數簇沒有大量的點，有一些例外，例如位於資料庫中心的巨大簇，它代表著星系核心，這是一個強發射區域。eps 引數起著重要的作用，因為它將定義代表相同發射源的畫素的最小半徑。設定為 5 意味著歐幾里得距離大於 5 的點不屬於同一個發射源。雖然 5 對 eps 引數來說相對較大，但一些簇（如 (300,0) 上的簇）沒有聚類在一起。這是因為儘管彼此接近，但根據 eps 值，它們不代表同一個天體。因此，設定 eps 的作用類似於 MinPts，因為它將根據距離度量來定義噪聲物件，與 MinPts 的計數度量相同。

結論

隨著天文學和天體物理學成為研究的突出領域，自動識別天體實體類別的需求變得越來越重要。隨著技術的發展，以及越來越多的資料樣本需要分析，對這項任務的需求不斷增長。在沒有計算輔助的情況下，這項任務是不可能的，而 DBSCAN 技術的出現讓這項任務變得更加容易，它允許分析更大的樣本，同時獲得更精確的結果。

參考資料

Martin Ester, Hans-Peter Kriegel, Joerg Sander, Xiaowei Xu (1996)。用於在大型空間資料庫中發現帶有噪聲的簇的基於密度的演算法。慕尼黑大學計算機科學研究所。第二屆知識發現與資料探勘國際會議（KDD-96）論文集。
CRAN 上的 FPC 包：http://cran.r-project.org/web/packages/fpc/index.html
FPC 中實現的 DBSCAN 演算法手冊位於 http://bm2.genes.nig.ac.jp/RGM2/R_current/library/fpc/man/dbscan.html
Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu (1998)。空間資料庫中的基於密度的聚類：GDBSCAN 演算法及其應用