https://www.toutiao.com/article/7244781043902251577/?log_from=c30de435e10df_1694408244494

(相似度或距離)

一.聚類的基本概念

聚類是針對(duì)給定的樣本，依據(jù)它們特征的 相似度或距離，將其歸并到若千個(gè)“類”或“簇”的數(shù)據(jù)分析問題。一個(gè)類是樣本的一個(gè)子集。直觀上，相似的樣本聚集在相同的類,不相似的樣本分散在不同的類。這里，樣本之間的相似度或距離起著重要作用。

1.1 相似度或距離

聚類的對(duì)象是觀測數(shù)據(jù)，或樣本集合。假設(shè)有 n 個(gè)樣本，每個(gè)樣本由 m 個(gè)屬性的特征向量組成。樣本集合可以用矩陣 X 表示矩陣的第 j 列表示第 j 個(gè)樣本， j=1,2,..,n; 第 i 行表示第 i 個(gè)屬性, i=1,2,...,m; 矩陣元素 xij 表示第 j 個(gè)樣本的第 i 個(gè)屬性值， i=1,2,...,m; j=1,2,..,n。

聚類的核心概念是相似度(similarity) 或距離(distance) ，有多種相似度或距離的定義。因?yàn)橄嗨贫戎苯佑绊懢垲惖慕Y(jié)果，所以其選擇是聚類的根本問題。具體哪種相似度更合適取決于應(yīng)用問題的特性。

1.閔可夫斯基距離

在聚類中，可以將樣本集合看作是向量空間中點(diǎn)的集合，以該空間的距離表示樣本之間的相似度。常用的距離有 閔可夫斯基距離，特別是 歐氏距離。閔可夫斯基距離越大相似度越小，距離越小相似度越大。

定義7.1 給定樣本集合 X, X 是 m維實(shí)數(shù)向量空間 Rm中點(diǎn)的集合,其中 x i , x j ∈ X , xi=(x1i,x2i,...,xmi)T, xj=(x1j,x2j,...,xmj)T，樣本 xi 與樣本xj 的 **閔可夫斯基距離( Minkowski distance)**定義為

這里 p≥1。當(dāng) p=2 時(shí)稱為 歐氏距離( Euclidean distance)，即

當(dāng) p = 1 p=1 p=1 時(shí)稱為曼哈頓距離( Manhattan distance )，即

當(dāng)p=∞時(shí)稱為 切比雪夫距離( Chebyshev distance),取各個(gè)坐標(biāo)數(shù)值差的絕對(duì)值的最大值，即

1. 相關(guān)系數(shù)

樣本之間的相似度也可以用 相關(guān)系數(shù)(correlation cofficient) 來表示。相關(guān)系數(shù)的絕對(duì)值越接近于1,表示樣本越相似；越接近于0，表示樣本越不相似。

1.2 類或簇

通過聚類得到的類或簇，本質(zhì)是樣本的子集。如果一個(gè)聚類方法假定一個(gè)樣本只能屬于一個(gè)類，或類的交集為空集，那么該方法稱為 硬聚類(hard clustering) 方法。否則，如果一個(gè)樣本可以屬于多個(gè)類，或類的交集不為空集，那么該方法稱為軟聚類(soft clustering) 方法。本章只考慮硬聚類方法。

用 G 表示類或簇(cluster) ，用xi,xj表示類中的樣本，用 nG表示G 中樣本的個(gè)數(shù)，用 dij 表示樣本 xi 與樣本 xj 之間的距離。下面給出 類的定義：

設(shè) T 為給定的正數(shù)，若集合 G 中任意兩個(gè)樣本 xi,xj，有

則稱 G 為一個(gè)類或簇。

類的特征可以通過不同角度來刻畫，常用的特征有下面幾種:

(1)類的均值

，又稱為類的中心

(2)類的直徑(diameter) DG
類的直徑 DG是類中任意兩個(gè)樣本之間的最大距離，即

1.3 類與類之間的距離

下面考慮類 Gp與類 Gq之間的距離 D(p,q), 也稱為連接(linkage)。類與類之間的距離也有多種定義。

(1)最短距離或單連接(single linkage)

定義類 Gp 的樣本與 Gq 的樣本之間的最短距離為兩類之間的距離

(2)最長距離或完全連接(complete linkage)

定義類 Gp 的樣本與 Gq 的樣本之間的最長距離為兩類之間的距離

(3)中心距離
定義類Gp 與類 Gq 的中心

之間的距離為兩類之間的距離

(4)平均距離
定義類 Gp 與類 Gq 任意兩個(gè)樣本之間距離的平均值為兩類之間的距離

二.層次聚類

層次聚類假設(shè)類別之間存在層次結(jié)構(gòu)，將樣本聚到層次化的類中。層次聚類又有 聚(agglomerative) 或自下而上(ottom-up)聚類、分裂(divisive) 或自上而下(top-down)聚類兩種方法。因?yàn)槊總€(gè)樣本只屬于一個(gè)類，所以層次聚類屬于硬聚類。

2.1 基本概念

聚合聚類開始將 每個(gè)樣本各自分到一個(gè)類；之后將相距 最近的兩類合并，建立一個(gè)新的類，重復(fù)此操作直到滿足停止條件；得到層次化的類別。分裂聚類開始將 所有樣本分到一個(gè)類;之后將已有類中相距 最遠(yuǎn)的樣本分到兩個(gè)新的類，重復(fù)此操作直到滿足停止條件;得到層次化的類別。本書只介紹聚合聚類。

聚合聚類的具體過程如下：對(duì)于給定的樣本集合，開始將每個(gè)樣本分到一個(gè)類；然后按照一定規(guī)則，例如類間距離最小，將最滿足規(guī)則條件的兩個(gè)類進(jìn)行合并；如此反復(fù)進(jìn)行，每次減少一個(gè)類，直到滿足停止條件,如所有樣本聚為一類。

由此可知，聚合聚類需要預(yù)先確定下面三個(gè)要素:

1. 距離或相似度;

2. 合并規(guī)則;

3. 停止條件。

根據(jù)這些要素的不同組合，就可以構(gòu)成不同的聚類方法。距離或相似度可以是閔可夫斯基距離、馬哈拉諾比斯距離、相關(guān)系數(shù)、夾角余弦。合并規(guī)則一般是類間距離最小，類間距離可以是最短距離、最長距離、中心距離、平均距離。停止條件可以是類的個(gè)數(shù)達(dá)到閾值(極端情況類的個(gè)數(shù)是1)、類的直徑超過閾值。

如果采用 歐氏距離為樣本之間距離；類間距離最小為合并規(guī)則，其中最短距離為類間距離；類的個(gè)數(shù)是1，即所有樣本聚為一類，為停止條件，那么聚合聚類的算法如下。

2.2 算法描述

算法14.1 (聚合聚類算法)
輸入： n n n 個(gè)樣本組成的樣本集合及樣本之間的距離;
輸出：對(duì)樣本集合的一個(gè)層次化聚類。

2.3 例題

例： 給定5個(gè)樣本的集合，樣本之間的歐氏距離由如下矩陣 D D D 表示:

其中dj表示第 i 個(gè)樣本與第 j 個(gè)樣本之間的 歐氏距離。顯然 D 為對(duì)稱矩陣。應(yīng)用聚合層次聚類法對(duì)這5個(gè)樣本進(jìn)行聚類。

三.K均值聚類

k均值聚類是基于 樣本集合劃分 的聚類算法。k 均值聚類將樣本集合劃分為 k 個(gè)子集，構(gòu)成 k個(gè)類，將 n 個(gè)樣本分到 k 個(gè)類中，每個(gè)樣本到其所屬類的中心的距離最小。每個(gè)樣本只能屬于一個(gè)類，所以 k 均值聚類是硬聚類。下面分別介紹 k 均值聚類的模型、策略、算法，討論算法的特性及相關(guān)問題。

3.1 模型

給定 n 個(gè)樣本的集合 X=x1,x2,...,xn 每個(gè)樣本由一個(gè)特征向量表示，特征向量的維數(shù)是 m。 k 均值聚類的目標(biāo)是將 n 個(gè)樣本分到 k 個(gè)不同的類或簇中，這里假設(shè)k < n。 k 個(gè)類 G1,G2,...,Gk形成對(duì)樣本集合 X的劃分，其中

用 C 表示劃分，一個(gè)劃分對(duì)應(yīng)著一個(gè)聚類結(jié)果。

劃分 C 是一個(gè)多對(duì)一的函數(shù)。事實(shí)上，如果把每個(gè)樣本用一個(gè)整數(shù) i∈{1,2,..,n} 表示，每個(gè)類也用一個(gè)整數(shù) l∈{1,2,..,k} 表示，那么劃分或者聚類可以用函數(shù) l=C(i) 表示，其中 i∈{1,2,...,n},l∈{1,2，..,k}。所以 k 均值聚類的模型是一個(gè)從樣本到類的函數(shù)。

3.2 策略

k均值聚類歸結(jié)為樣本集合X的劃分，或者從樣本到類的函數(shù)的選擇問題。k均值聚類的策略是通過 損失函數(shù)的最小化選取最優(yōu)的劃分或函數(shù)C*。

首先，采用 歐氏距離平方(squared Euclidean distance) 作為樣本之間的距離d(xi,xj) .

然后，定義樣本與其所屬類的中心之間的距離的總和為損失函數(shù)，即

式中

是第 l 個(gè)類的均值或中心，

是指示函數(shù)，取值為 1或 0。函數(shù) W(C) 也稱為能量，表示相同類中的樣本相似的程度。

k均值聚類就是求解最優(yōu)化問題:

3.3 算法

聚類中心的初始化

樣本集 D劃分之前，先選擇代表點(diǎn)作為初始聚類核心，再將其余樣本初始分類。迭代結(jié)果與初始代表點(diǎn)選擇有關(guān)

3.3.1 K-Means ++ 中的聚類中心初始化算法：

3.3.2 聚類數(shù) K 的確定

通常要求事先給定聚類數(shù)K，若類別數(shù)目未知，可按如下方法確定

• 一般根據(jù)領(lǐng)域先驗(yàn)知識(shí)確定

• 實(shí)驗(yàn)確定:
  令k = 1,2，3…分別進(jìn)行聚類，得 Je(k)，繪制 Je(k)?k曲線圖；找出拐點(diǎn)，對(duì)應(yīng)聚類數(shù)目為最終類別數(shù)。

3.3.3 K均值聚類算法描述

3.4.例題

例： 給定含有5 個(gè)樣本的集合

試用k均值聚類算法將樣本聚到2個(gè)類中。

解：

四.密度聚類(DBSCAN)

DBSCAN 算法是一種基于 高密度連通區(qū)域的、基于密度的聚類算法。能夠?qū)⒕哂凶銐蚋呙芏鹊膮^(qū)域劃分為簇。

4.1 相關(guān)概念

給定樣本集 D={x1,?,xm}

4.2 算法描述

結(jié)語

喜歡人工智能的小伙伴記得點(diǎn)贊關(guān)注哦~