文章目錄

• • • • I . 聚類主要算法
      • II . 基于劃分的聚類方法
      • III . 基于層次的聚類方法
      • IV . 聚合層次聚類 圖示
      • V . 劃分層次聚類 圖示
      • VI . 基于層次的聚類方法 切割點(diǎn)選取
      • VII . 基于密度的方法
      • VIII . 基于方格的方法
      • IX . 基于模型的方法

I . 聚類主要算法

---

聚類主要算法 :

① 基于劃分的聚類方法 : K-Means 方法 ;

② 基于層次的聚類方法 : Birch ;

③ 基于密度的聚類方法 : DBSCAN ( Density-Based Spatial Clustering of Applications with Noise ) ;

④ 基于方格的方法 ;

⑤ 基于模型的方法 : GMM 高斯混合模型 ;

II . 基于劃分的聚類方法

---

基于劃分的方法 簡(jiǎn)介 : 基于劃分的方法 , 又叫基于距離的方法 , 基于相似度的方法 ;

① 概念 : 給定 $n$ 個(gè)數(shù)據(jù)樣本 , 使用劃分方法 , 將數(shù)據(jù)構(gòu)建成 $k$ 個(gè)劃分 $(k\le n)$ , 每個(gè)劃分代表一個(gè)聚類 ;

② 分組 : 將數(shù)據(jù)集 分成 $k$ 組 , 每個(gè)分組至少要有一個(gè)樣本 ;

③ 分組與樣本 對(duì)應(yīng)關(guān)系 : 每個(gè)分組有 $1$ 個(gè)或多個(gè)樣本對(duì)象 ( $1$ 對(duì)多 ) , 每個(gè)對(duì)象同時(shí)只能在 $1$ 個(gè)分組中 ( $1$ 對(duì) $1$ ) ;

④ 硬聚類 與 軟聚類 : 每個(gè)數(shù)據(jù)對(duì)象只能屬于一個(gè)組 , 這種分組稱為硬聚類 ; 軟聚類每個(gè)對(duì)象可以屬于不同的組 ;

III . 基于層次的聚類方法

---

1 . 基于層次的聚類方法 概念 : 將數(shù) 據(jù)集樣本對(duì)象 排列成 樹結(jié)構(gòu) , 稱為 聚類樹 , 在指定的層次 ( 步驟 ) 上切割數(shù)據(jù)集樣本 , 切割后時(shí)刻的 聚類分組 就是 聚類算法的 聚類結(jié)果 ;

2 . 基于層次的聚類方法 : 一棵樹可以從葉子節(jié)點(diǎn)到根節(jié)點(diǎn) , 也可以從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) , 基于這兩種順序 , 衍生出兩種方法分支 , 分別是 : 聚合層次聚類 , 劃分層次聚類 ;

3 . 聚合層次聚類 ( 葉子節(jié)點(diǎn)到根節(jié)點(diǎn) ) : 開始時(shí) , 每個(gè)樣本對(duì)象自己就是一個(gè)聚類 , 稱為 原子聚類 , 然后根據(jù)這些樣本之間的 相似性 , 將這些樣本對(duì)象 ( 原子聚類 ) 進(jìn)行 合并 ;

常用的聚類算法 : 大多數(shù)的基于層次聚類的方法 , 都是 聚合層次聚類 類型的 ; 這些方法從葉子節(jié)點(diǎn)到根節(jié)點(diǎn) , 逐步合并的原理相同 ; 區(qū)別只是聚類間的相似性計(jì)算方式不同 ;

4 . 劃分層次聚類 ( 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) ) : 開始時(shí) , 整個(gè)數(shù)據(jù)集的樣本在一個(gè)總的聚類中 , 然后根據(jù)樣本之間的相似性 , 不停的切割 , 直到完成要求的聚類操作 ;

5 . 算法性能 : 基于層次的聚類方法的時(shí)間復(fù)雜度為 $O(N^2)$ , 如果處理的樣本數(shù)量較大 , 性能存在瓶頸 ;

IV . 聚合層次聚類 圖示

---

1 . 聚合層次聚類 圖示 :

① 初始狀態(tài) : 最左側(cè) 五個(gè) 數(shù)據(jù)對(duì)象 , 每個(gè)都是一個(gè)聚類 ;

② 第一步 : 分析相似度 , 發(fā)現(xiàn) $a,b$ 相似度很高 , 將 $\{a,b\}$ 分到一個(gè)聚類中 ;

③ 第二步 : 分析相似度 , 發(fā)現(xiàn) $d,e$ 相似度很高 , 將 $\{d,e\}$ 分到一個(gè)聚類中 ;

④ 第三步 : 分析相似度 , 發(fā)現(xiàn) $c$ 與 $d,e$ 相似度很高 , 將 $c$ 數(shù)據(jù)放入 $\{d,e\}$ 聚類中 , 組成 $\{c,d,e\}$ 聚類 ;

⑤ 第四步 : 分析相似度 , 此時(shí)要求的相似度很低就可以將不同的樣本進(jìn)行聚類 , 將前幾步生成的兩個(gè)聚類 , 合并成一個(gè)聚類 $\{a,b,c,d,e\}$ ;

2 . 切割點(diǎn)說明 : 實(shí)際進(jìn)行聚類分析時(shí) , 不會(huì)將所有的步驟走完 , 這里提供四個(gè)切割點(diǎn) , 聚類算法進(jìn)行聚類時(shí) , 可以在任何一個(gè)切割點(diǎn)停止 , 使用當(dāng)前的聚類分組當(dāng)做聚類結(jié)果 ;

① 切割點(diǎn) $1$ : 在切割點(diǎn) $1$ 停止 , 會(huì)得到 $5$ 個(gè)聚類分組 , $\{a\}$ , $\{b\}$, $\{c\}$, $\{d\}$ , $\{e\}$ ;

② 切割點(diǎn) $2$ : 在切割點(diǎn) $2$ 停止 , 會(huì)得到 $4$ 個(gè)聚類分組 , $\{a,b\}$ , $\{c\}$, $\{d\}$ , $\{e\}$ ;

③ 切割點(diǎn) $3$ : 在切割點(diǎn) $3$ 停止 , 會(huì)得到 $3$ 個(gè)聚類分組 , $\{a,b\}$ , $\{c\}$, $\{d,e\}$ ;

④ 切割點(diǎn) $4$ : 在切割點(diǎn) $4$ 停止 , 會(huì)得到 $2$ 個(gè)聚類分組 ; $\{a,b\}$ , $\{c,d,e\}$ ;

⑤ 走完整個(gè)流程 : 會(huì)得到 $1$ 個(gè)聚類分組 , $\{a,b,c,d,e\}$ ;

V . 劃分層次聚類 圖示

---

1 . 劃分層次聚類 圖示 :

① 初始狀態(tài) : 最左側(cè) 五個(gè) 數(shù)據(jù)對(duì)象 , 屬于一個(gè)聚類 ;

② 第一步 : 分析相似度 , 切割聚類 , 將 $\{c,d,e\}$ 與 $\{a,b\}$ 劃分成兩個(gè)聚類 ;

③ 第二步 : 分析相似度 , 將 $\{c,d,e\}$ 中的 $\{c\}$ 與 $\{d,e\}$ 劃分成兩個(gè)聚類 ;

④ 第三步 : 分析相似度 , 將 $\{d,e\}$ 拆分成 $\{d\}$ 和 $\{e\}$ 兩個(gè)聚類 ;

⑤ 第四步 : 分析相似度 , 將 $\{a,b\}$ 拆分成 $\{a\}$ 和 $\{b\}$ 兩個(gè)聚類 , 至此所有的數(shù)據(jù)對(duì)象都劃分成了單獨(dú)的聚類 ;

2 . 切割點(diǎn)說明 : 實(shí)際進(jìn)行聚類分析時(shí) , 不會(huì)將所有的步驟走完 , 這里提供四個(gè)切割點(diǎn) , 聚類算法進(jìn)行聚類時(shí) , 可以在任何一個(gè)切割點(diǎn)停止 , 使用當(dāng)前的聚類分組當(dāng)做聚類結(jié)果 ;

① 切割點(diǎn) $1$ : 在切割點(diǎn) $1$ 停止 , 會(huì)得到 $1$ 個(gè)聚類分組 , $\{a,b,c,d,e\}$ ;

② 切割點(diǎn) $2$ : 在切割點(diǎn) $2$ 停止 , 會(huì)得到 $2$ 個(gè)聚類分組 ; $\{a,b\}$ , $\{c,d,e\}$ ;

③ 切割點(diǎn) $3$ : 在切割點(diǎn) $3$ 停止 , 會(huì)得到 $3$ 個(gè)聚類分組 , $\{a,b\}$ , $\{c\}$, $\{d,e\}$$ ;

④ 切割點(diǎn) $4$ : 在切割點(diǎn) $4$ 停止 , 會(huì)得到 $4$ 個(gè)聚類分組 , $\{a,b\}$ , $\{c\}$, $\{d\}$ , $\{e\}$ ;

⑤ 走完整個(gè)流程 : 會(huì)得到 $5$ 個(gè)聚類分組 , $\{a\}$ , $\{b\}$, $\{c\}$, $\{d\}$ , $\{e\}$ ;

VI . 基于層次的聚類方法 切割點(diǎn)選取

---

1 . 算法終止條件 ( 切割點(diǎn) ) : 用戶可以指定聚類操作的算法終止條件 , 即上面圖示中的切割點(diǎn) , 如 :

① 聚類的最低個(gè)數(shù) : 聚合層次聚類中 , $n$ 個(gè)樣本 , 開始有 $n$ 個(gè)聚類 , 逐步合并 , 聚類個(gè)數(shù)逐漸減少 , 當(dāng)聚類個(gè)數(shù)達(dá)到最低值 $min$ , 停止聚類算法 ;

② 聚類最高個(gè)數(shù) : 劃分層次聚類中 , $n$ 個(gè)樣本 , 開始有 $1$ 個(gè)聚類 , 逐步劃分 , 聚類個(gè)數(shù)逐漸增加 , 當(dāng)聚類個(gè)數(shù)達(dá)到最大值 $max$ , 停止聚類算法 ;

③ 聚類樣本的最低半徑 : 聚類的數(shù)據(jù)樣本范圍不能無限擴(kuò)大 , 指定一個(gè)閾值 , 只有將該閾值內(nèi)的樣本放入一組 ; 半徑指的是所有對(duì)象距離其平均點(diǎn)的距離 ;

2 . 切割點(diǎn)回退問題 : 切割點(diǎn)一旦確定 , 便無法回退 ; 這里以聚合層次聚類為例 :

① 處于切割點(diǎn) $4$ : 如已經(jīng)執(zhí)行到了步驟三 , 此時(shí)處于切割點(diǎn) $4$ , 聚類分組為 $\{a,b\}$ , $\{c,d,e\}$ ;

② 試圖回退到 切割點(diǎn) $3$ : 想要會(huì)回退到切割點(diǎn) $3$ 的狀態(tài) , 視圖將聚類分組恢復(fù)成 $\{a,b\}$ , $\{c\}$, $\{d,e\}$ ;

③ 無法回退 : 該操作是無法實(shí)現(xiàn)的 , 聚類分組一旦 合并 或 分裂 , 此時(shí)就無法回退 ;

VII . 基于密度的方法

---

1 . 基于距離聚類的缺陷 : 很多的聚類方法 , 都是 基于樣本對(duì)象之間的距離 ( 相似度 ) 進(jìn)行的 , 這種方法對(duì)于任意形狀的分組 , 就無法識(shí)別了 , 如下圖左側(cè)的聚類模式 ; 這種情況下可以使用基于密度的方法進(jìn)行聚類操作 ;

基于距離的方法 , 是基于歐幾里得距離函數(shù)得來 , 其基本的形狀都是球狀 , 或凸形狀 , 如下圖右側(cè)的形狀 ; 無法計(jì)算出凹形狀 , 如下圖左側(cè)的形狀 ;

2 . 基于密度的聚類方法 : 相鄰的區(qū)域內(nèi) 樣本對(duì)象 的密度超過某個(gè)閾值 , 聚類算法就繼續(xù)執(zhí)行 , 如果周圍區(qū)域密度都很小 , 那么停止聚類方法 ;

① 密度 : 某 單位大小 區(qū)域內(nèi)的樣本對(duì)象個(gè)數(shù) ;

② 聚類分組要求 : 在聚類分組中 , 每個(gè)分組的數(shù)據(jù)樣本密度都 必須達(dá)到密度要求的最低閾值 ;

3 . 基于密度的聚類方法 算法優(yōu)點(diǎn) :

① 排除干擾 : 過濾噪音數(shù)據(jù) , 即密度很小 , 樣本分布稀疏的數(shù)據(jù) ;

② 增加聚類模式復(fù)雜度 : 聚類算法可以識(shí)別任意形狀的分布模式 , 如上圖左側(cè)的聚類分組模式 ;

VIII . 基于方格的方法

---

1 . 基于方格的方法 : 將數(shù)據(jù)空間劃分成 一個(gè)個(gè)方格 , 在這些方格數(shù)據(jù)結(jié)構(gòu)上 , 將每個(gè)方格中的數(shù)據(jù)樣本 , 當(dāng)做一個(gè)數(shù)據(jù)處理 , 進(jìn)行聚類操作 ;

2 . 基于方格的方法優(yōu)點(diǎn) : 處理速度很快 , 將每個(gè)方格都作為一個(gè)數(shù)據(jù) , 如果分成 少數(shù)的幾個(gè)方格進(jìn)行聚類操作 , 聚類瞬間完成 ; 其速度與數(shù)據(jù)集樣本個(gè)數(shù)無關(guān) , 與劃分的數(shù)據(jù)方格個(gè)數(shù)有關(guān) ;

3 . 局限性 : 該方法的錯(cuò)誤率很高 ;

IX . 基于模型的方法

---

基于模型的方法

① 基于統(tǒng)計(jì)的方法 : GMM 高斯混合模型 ;

② 神經(jīng)網(wǎng)絡(luò)方法 ;

總結(jié)

以上是生活随笔為你收集整理的【数据挖掘】聚类算法 简介 ( 基于划分的聚类方法 | 基于层次的聚类方法 | 基于密度的聚类方法 | 基于方格的聚类方法 | 基于模型的聚类方法 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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