文章目錄

• • • • I . DBSCAN 簡介
      • II . DBSCAN 算法流程
      • III . DBSCAN 算法 優(yōu)缺點(diǎn)
      • IV . 可變密度問題
      • V . 鏈條現(xiàn)象
      • VI . OPTICS 算法原理
      • VII . 聚類分組包含關(guān)系
      • VIII . 根據(jù)層次進(jìn)行聚類
      • IX . 族序 ( Cluster Ordering ) 概念

I . DBSCAN 簡介

---

1 . DBSCAN 算法原理 :

① 聚類條件 : 如果 樣本對象 $p$ 與 $q$ 有密度連接關(guān)系 , 那么 $p$ 和 $q$ 樣本就會(huì)被分到同一個(gè)聚類中 ;

② 噪音識別 : 如果 樣本對象 與 其它的樣本對象 沒有密度連接關(guān)系 , 那么該樣本就是噪音 ;

2 . DBSCAN 總結(jié) : 一個(gè) 聚類 就是 所有 密度相連 的 的 數(shù)據(jù)樣本 的最大集合 , 密度連接所有可以連接的樣本 , 組成一個(gè)聚類 ;

II . DBSCAN 算法流程

---

1 . 輸入算法參數(shù) : 算法開始時(shí) , 需要輸入兩個(gè)參數(shù) ;

① 參數(shù)一 : $\epsilon$ 參數(shù) , 是 $\epsilon$-鄰域 的 半徑 ;

② 參數(shù)二 : MinPts 參數(shù) , 是 $\epsilon$-鄰域中要求的含有的最低樣本個(gè)數(shù) , 即閾值 ;

2 . 選擇樣本 : 隨機(jī)選擇一個(gè)數(shù)據(jù)樣本 $p$ ;

3 . 判定核心對象 : 判定數(shù)據(jù)樣本 $p$ 是否是核心對象 , 通過判定其 $\epsilon$-鄰域 中分布的樣本數(shù)量是否大于等于 MinPts 閾值 個(gè)數(shù) , 也就是其中的樣本分布達(dá)到一定的密度 ;

4 . 如果 $p$ 是核心對象 :

① 標(biāo)記聚類分組 : 當(dāng)前以 $p$ 為中心的 $\epsilon$-鄰域 中的所有樣本 , 與 $p$ 都是直接密度可達(dá)的 , 也是密度可達(dá) , 密度連接的 , 因此 $\epsilon$-鄰域 中的所有點(diǎn) , 包括 $p$ 點(diǎn) , 可以劃分到同一個(gè)聚類分組中 ;

② 搜索所有密度可達(dá)樣本 : 在上面的聚類分組基礎(chǔ)上 , 通過廣度優(yōu)先搜索 , 找到所有的密度可達(dá)的樣本 , 劃分到該聚類分組中 ;

5 . 如果 $p$ 是邊界對象 ( 非核心對象 ) : 將 $p$ 樣本標(biāo)記成噪音 , 再隨機(jī)地選取另外一個(gè)數(shù)據(jù)樣本進(jìn)行處理 ;

6 . 迭代要求及算法終止條件 : 繼續(xù)選擇樣本 , 執(zhí)行 $2.3.4.5.6$ 操作 進(jìn)行迭代 , 直到所有的樣本全部被標(biāo)記完成 ;

III . DBSCAN 算法 優(yōu)缺點(diǎn)

---

1 . DBSCAN 算法優(yōu)點(diǎn) :

① 算法復(fù)雜度 : DBSCAN 算法復(fù)雜度是 $O(n)$ , $n$ 代表 數(shù)據(jù)集樣本個(gè)數(shù) ;

② 識別模式多 : DBSCAN 算法可以得到任意形狀的聚類分組 , 如凹形 , 馬蹄形 等 ;

③ 魯棒性好 : DBSCAN 算法魯棒性好 , 可以屏蔽異常點(diǎn) , 噪音 的干擾 ;

④ 不需要設(shè)定聚類分組參數(shù) : DBSCAN 算法不需要參數(shù) $k$ , 不需要提前指定其聚類分組個(gè)數(shù) , 這個(gè)參數(shù)設(shè)置不好 會(huì)影響聚類效果 ;

2 . DBSCAN 算法缺點(diǎn) :

① 需要設(shè)置額外參數(shù) : DBSCAN 算法需要設(shè)置 $\epsilon$-鄰域半徑參數(shù) 和 MinPts 鄰域最小樣本閾值 參數(shù) , 這兩個(gè)參數(shù)只是會(huì)影響 ;

② 密度可變 : DBSCAN 算法 對于密度可變的數(shù)據(jù)集進(jìn)行聚類分析效果很差 , 這里的密度可變指的是 聚類分組 中的樣本密度不同 ; 數(shù)據(jù)集樣本中一部分密度大 , 一部分密度小 ;

③ 鏈條現(xiàn)象 : DBSCAN 算法 存在鏈條現(xiàn)象 ;

IV . 可變密度問題

---

1 . 樣本描述 : 針對密度可變的數(shù)據(jù)集樣本 , 不同的聚類分組中 , 樣本的密度不同 ; 一部分樣本密度大 , 一部分樣本密度小 ;

示例 : 如 , 聚類 $1$ 中單位面積內(nèi)樣本有 20個(gè) , 聚類 $2$ 中單位面積內(nèi)有樣本 4 個(gè) ;

2 . 參數(shù)值設(shè)定問題 :

① 問題描述 : 這樣為其設(shè)置 $\epsilon$-鄰域半徑參數(shù) 和 MinPts 鄰域最小樣本閾值 參數(shù) 時(shí) , 就不太好設(shè)置 ;

② 半徑設(shè)置小 : 如果半徑設(shè)置的小了 , 密度低的聚類 , 可能全部給打散成噪音值 ;

③ 半徑設(shè)置大 : 如果半徑設(shè)置的大了 可能整個(gè)數(shù)據(jù)集只有一個(gè)聚類 ;

3 . 圖示 : 紫色的樣本密度很大 , 綠色的樣本密度很小 , 此時(shí)如果設(shè)置 $\epsilon$-鄰域半徑參數(shù) 比較大 , 那么只有一個(gè)聚類分組 , 如果設(shè)置 $\epsilon$-鄰域半徑參數(shù)比較小 , 綠色的樣本就會(huì)被標(biāo)記成異常點(diǎn) , 當(dāng)做噪音處理 ;

V . 鏈條現(xiàn)象

---

兩個(gè)聚類分組中 , 出現(xiàn)一個(gè)鏈條 , 少數(shù)個(gè)別的樣本 , 將兩個(gè)本應(yīng)該分開的聚類分組 進(jìn)行了 密度連接 , 導(dǎo)致 兩個(gè)聚類分組 變成了一個(gè)聚類分組 ;

VI . OPTICS 算法原理

---

OPTICS 算法 原理 :

① 排序索引 : 給所有的 數(shù)據(jù)樣本對象 進(jìn)行排序 , 并為每個(gè)樣本對象設(shè)置對應(yīng)的順序 索引值 ;

② 索引值意義 : 表示樣本 基于 密度 的聚類分組 的結(jié)構(gòu) , 同一個(gè)聚類分組的 樣本 , 順序相近 ;

③ 根據(jù)索引排列 : 將全體數(shù)據(jù)集樣本數(shù)據(jù) , 根據(jù)該索引值 , 排列在坐標(biāo)系中 , 索引值就是 $x$ 軸的坐標(biāo)值 , 排列的結(jié)果就是不同層次的聚類分組 ;

VII . 聚類分組包含關(guān)系

---

1 . 聚類分組包含關(guān)系 :

① 前提 : 為 數(shù)據(jù)集樣本 進(jìn)行 聚類分組時(shí) , MinPts 鄰域最小樣本閾值 參數(shù)不變時(shí) ;

② 密度大的聚類 : 當(dāng)設(shè)置的 $\epsilon$-鄰域 的 $\epsilon$ 半徑比較小的時(shí)候 , 其聚類的結(jié)果為 $C_0$ ;

③ 密度小的聚類 : 當(dāng)設(shè)置的 $\epsilon$-鄰域 的 $\epsilon$ 半徑比較大的時(shí)候 , 其聚類的結(jié)果為 $C_1$ ;

④ 包含關(guān)系 : $C_0$ 肯定完全包含在 $C_1$ 中 ; 密度小的聚類 , 肯定被密度大的聚類包含 ;

2 . 聚類分組示例 :

當(dāng)設(shè)置比較小的 $\epsilon$ 參數(shù)時(shí) , 得到的聚類結(jié)果是 $C_1$ 和 $C_2$ ;

當(dāng)設(shè)置比較大的 $\epsilon$ 參數(shù)時(shí) , 得到的聚類結(jié)果是 $C_3$ ;

由圖中可以看出 , $C_3$ 包含 $C_1$ 和 $C_2$ , 它們之間具有層次關(guān)系 , $C_3$ 可以看做 $C_1$ 和 $C_2$ 的父容器 ;

VIII . 根據(jù)層次進(jìn)行聚類

---

根據(jù)層次進(jìn)行聚類 :

進(jìn)行聚類分析時(shí) , 將不同層次的 聚類分組 都劃分出來 , 也就是使用不同的 $\epsilon$ 參數(shù) , 進(jìn)行聚類分析 , 最終得出不同的聚類分組結(jié)果 , 這些結(jié)果之間有層次關(guān)系 ;

只針對一個(gè) $\epsilon$ 參數(shù) 進(jìn)行聚類分組 , 聚類結(jié)果很片面 , 效果不佳 ;

IX . 族序 ( Cluster Ordering ) 概念

---

1 . 族序 ( Cluster Ordering ) 概念 :

① 多層次同時(shí)聚類 : 不同層次的聚類分組 , 可以同時(shí)進(jìn)行構(gòu)建 ;

② 順序處理樣本 : 處理數(shù)據(jù)集樣本對象時(shí) , 使用特定的順序進(jìn)行處理 ;

③ 順序擴(kuò)展 : 數(shù)據(jù)集樣本對外擴(kuò)展時(shí) , 按照該順序進(jìn)行擴(kuò)展 ,

④ 族序概念 : 該特定順序就是 族序 ( Cluster Ordering ) ;

2 . 聚類順序 : 從 低層 到 高層 ; 從 稠密 到 稀疏 ;

聚類時(shí) , 低層 的聚類分組 要首先構(gòu)建完成 , 也就是 $\epsilon$ 參數(shù) 較小的聚類分組 ;

3 . 密度可達(dá)的兩種情況情況 : 兩個(gè)樣本 密度可達(dá) , 有兩種情況 :

① $\epsilon$ 參數(shù)小 : 一種情況是 $\epsilon$ 參數(shù) 較小的時(shí)候 , 這兩個(gè)樣本就可以密度可達(dá) ;

② $\epsilon$ 參數(shù)大 : 另一種情況是 $\epsilon$ 參數(shù) 取值很大時(shí) , 才可以密度可達(dá) ;

4 . 擴(kuò)展樣本優(yōu)先級 : 擴(kuò)展樣本對象時(shí) , 優(yōu)先選擇第一種情況 , $\epsilon$ 參數(shù) 較小的時(shí)候 就可以密度可達(dá)的樣本 ;

5 . 每個(gè)樣本對象需要存儲(chǔ)兩個(gè)值 : 核心距離 與 可達(dá)距離 ;

總結(jié)

以上是生活随笔為你收集整理的【数据挖掘】基于密度的聚类方法 - DBSCAN 方法 ( DBSCAN 原理 | DBSCAN 流程 | 可变密度问题 | 链条现象 | OPTICS 算法引入 | 聚类层次 | 族序概念 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。