一.聚類的基本概念
聚類是針對給定的樣本，依據它們特征的 相似度或距離，将其歸并到若千個“類”或“簇”的資料分析問題。一個類是樣本的一個子集。直覺上，相似的樣本聚集在相同的類,不相似的樣本分散在不同的類。這裡，樣本之間的相似度或距離起着重要作用。
1.1 相似度或距離
聚類的對象是觀測資料，或樣本集合。假設有 n 個樣本，每個樣本由 m 個屬性的特征向量組成。樣本集合可以用矩陣 X 表示矩陣的第 j 清單示第 j 個樣本， j=1,2,..,n; 第 i 行表示第 i 個屬性, i=1,2,...,m; 矩陣元素 xij 表示第 j 個樣本的第 i 個屬性值， i=1,2,...,m; j=1,2,..,n。
聚類的核心概念是相似度(similarity) 或距離(distance) ，有多種相似度或距離的定義。因為相似度直接影響聚類的結果，是以其選擇是聚類的根本問題。具體哪種相似度更合适取決于應用問題的特性。
1.闵可夫斯基距離
在聚類中，可以将樣本集合看作是向量空間中點的集合，以該空間的距離表示樣本之間的相似度。常用的距離有 闵可夫斯基距離，特别是 歐氏距離。闵可夫斯基距離越大相似度越小，距離越小相似度越大。
定義7.1 給定樣本集合 X, X 是 m維實數向量空間 Rm中點的集合,其中 x i , x j ∈ X , xi=(x1i,x2i,...,xmi)T, xj=(x1j,x2j,...,xmj)T，樣本 xi 與樣本xj 的 **闵可夫斯基距離( Minkowski distance)**定義為
這裡 p≥1。當 p=2 時稱為 歐氏距離( Euclidean distance)，即
當 p = 1 p=1 p=1 時稱為曼哈頓距離( Manhattan distance )，即
當p=∞時稱為 切比雪夫距離( Chebyshev distance),取各個坐标數值差的絕對值的最大值，即
- 相關系數
樣本之間的相似度也可以用 相關系數(correlation cofficient) 來表示。相關系數的絕對值越接近于1,表示樣本越相似；越接近于0，表示樣本越不相似。
1.2 類或簇
通過聚類得到的類或簇，本質是樣本的子集。如果一個聚類方法假定一個樣本隻能屬于一個類，或類的交集為空集，那麼該方法稱為 硬聚類(hard clustering) 方法。否則，如果一個樣本可以屬于多個類，或類的交集不為空集，那麼該方法稱為軟聚類(soft clustering) 方法。本章隻考慮硬聚類方法。
用 G 表示類或簇(cluster) ，用xi,xj表示類中的樣本，用 nG表示G 中樣本的個數，用 dij 表示樣本 xi 與樣本 xj 之間的距離。下面給出 類的定義：
設 T 為給定的正數，若集合 G 中任意兩個樣本 xi,xj，有
則稱 G 為一個類或簇。
類的特征可以通過不同角度來刻畫，常用的特征有下面幾種:
(1)類的均值
，又稱為類的中心
(2)類的直徑(diameter) DG
類的直徑 DG是類中任意兩個樣本之間的最大距離，即
1.3 類與類之間的距離
下面考慮類 Gp與類 Gq之間的距離 D(p,q), 也稱為連接配接(linkage)。類與類之間的距離也有多種定義。
(1)最短距離或單連接配接(single linkage)
定義類 Gp 的樣本與 Gq 的樣本之間的最短距離為兩類之間的距離
(2)最長距離或完全連接配接(complete linkage)
定義類 Gp 的樣本與 Gq 的樣本之間的最長距離為兩類之間的距離
(3)中心距離
定義類Gp 與類 Gq 的中心
之間的距離為兩類之間的距離
(4)平均距離
定義類 Gp 與類 Gq 任意兩個樣本之間距離的平均值為兩類之間的距離
二.層次聚類
層次聚類假設類别之間存在層次結構，将樣本聚到階層化的類中。層次聚類又有 聚(agglomerative) 或自下而上(ottom-up)聚類、分裂(divisive) 或自上而下(top-down)聚類兩種方法。因為每個樣本隻屬于一個類，是以層次聚類屬于硬聚類。
2.1 基本概念
聚合聚類開始将 每個樣本各自分到一個類；之後将相距 最近的兩類合并，建立一個新的類，重複此操作直到滿足停止條件；得到階層化的類别。分裂聚類開始将 所有樣本分到一個類;之後将已有類中相距 最遠的樣本分到兩個新的類，重複此操作直到滿足停止條件;得到階層化的類别。本書隻介紹聚合聚類。
聚合聚類的具體過程如下：對于給定的樣本集合，開始将每個樣本分到一個類；然後按照一定規則，例如類間距離最小，将最滿足規則條件的兩個類進行合并；如此反複進行，每次減少一個類，直到滿足停止條件,如所有樣本聚為一類。
由此可知，聚合聚類需要預先确定下面三個要素:
- 距離或相似度;
- 合并規則;
- 停止條件。
根據這些要素的不同組合，就可以構成不同的聚類方法。距離或相似度可以是闵可夫斯基距離、馬哈拉諾比斯距離、相關系數、夾角餘弦。合并規則一般是類間距離最小，類間距離可以是最短距離、最長距離、中心距離、平均距離。停止條件可以是類的個數達到門檻值(極端情況類的個數是1)、類的直徑超過門檻值。
如果采用 歐氏距離為樣本之間距離；類間距離最小為合并規則，其中最短距離為類間距離；類的個數是1，即所有樣本聚為一類，為停止條件，那麼聚合聚類的算法如下。
2.2 算法描述
算法14.1 (聚合聚類算法)
輸入： n n n 個樣本組成的樣本集合及樣本之間的距離;
輸出：對樣本集合的一個階層化聚類。
2.3 例題
例： 給定5個樣本的集合，樣本之間的歐氏距離由如下矩陣 D D D 表示:
其中dj表示第 i 個樣本與第 j 個樣本之間的 歐氏距離。顯然 D 為對稱矩陣。應用聚合層次聚類法對這5個樣本進行聚類。
三.K均值聚類
k均值聚類是基于 樣本集合劃分 的聚類算法。k 均值聚類将樣本集合劃分為 k 個子集，構成 k個類，将 n 個樣本分到 k 個類中，每個樣本到其所屬類的中心的距離最小。每個樣本隻能屬于一個類，是以 k 均值聚類是硬聚類。下面分别介紹 k 均值聚類的模型、政策、算法，讨論算法的特性及相關問題。
3.1 模型
給定 n 個樣本的集合 X=x1,x2,...,xn 每個樣本由一個特征向量表示，特征向量的維數是 m。 k 均值聚類的目标是将 n 個樣本分到 k 個不同的類或簇中，這裡假設k < n。 k 個類 G1,G2,...,Gk形成對樣本集合 X的劃分，其中
用 C 表示劃分，一個劃分對應着一個聚類結果。
劃分 C 是一個多對一的函數。事實上，如果把每個樣本用一個整數 i∈{1,2,..,n} 表示，每個類也用一個整數 l∈{1,2,..,k} 表示，那麼劃分或者聚類可以用函數 l=C(i) 表示，其中 i∈{1,2,...,n},l∈{1,2，..,k}。是以 k 均值聚類的模型是一個從樣本到類的函數。
3.2 政策
k均值聚類歸結為樣本集合X的劃分，或者從樣本到類的函數的選擇問題。k均值聚類的政策是通過 損失函數的最小化選取最優的劃分或函數C*。
首先，采用 歐氏距離平方(squared Euclidean distance) 作為樣本之間的距離d(xi,xj) .
然後，定義樣本與其所屬類的中心之間的距離的總和為損失函數，即
式中
是第 l 個類的均值或中心，
是訓示函數，取值為 1或 0。函數 W(C) 也稱為能量，表示相同類中的樣本相似的程度。
k均值聚類就是求解最優化問題:
3.3 算法
聚類中心的初始化
樣本集 D劃分之前，先選擇代表點作為初始聚類核心，再将其餘樣本初始分類。疊代結果與初始代表點選擇有關
3.3.1 K-Means ++ 中的聚類中心初始化算法：
3.3.2 聚類數 K 的确定
通常要求事先給定聚類數K，若類别數目未知，可按如下方法确定
- 一般根據領域先驗知識确定
-
實驗确定:
令k = 1,2，3…分别進行聚類，得 Je(k)，繪制 Je(k)−k曲線圖；找出拐點，對應聚類數目為最終類别數。
3.3.3 K均值聚類算法描述
3.4.例題
例： 給定含有5 個樣本的集合
試用k均值聚類算法将樣本聚到2個類中。
解：
四.密度聚類(DBSCAN)
DBSCAN 算法是一種基于 高密度連通區域的、基于密度的聚類算法。能夠将具有足夠高密度的區域劃分為簇。
4.1 相關概念
給定樣本集 D={x1,⋯,xm}
4.2 算法描述
結語
喜歡人工智能的小夥伴記得點贊關注哦~