柚子快報邀請碼778899分享：人工智能 數(shù)據(jù)挖掘-聚類分析
柚子快報邀請碼778899分享：人工智能 數(shù)據(jù)挖掘-聚類分析
來自塞?程序員 Truraly | 田園 的博客，最新文章首發(fā)于：田園幻想鄉(xiāng) | 原文鏈接 | github （歡迎關(guān)注）
文章目錄
概念距離度量
基于分割的聚類算法 K-Means&K-MedoidsK-Means 算法（K-均值算法）K-Medoids 算法（K-中心點算法）
層次聚類算法AGNES 算法DIANA 算法優(yōu)點和缺點
BIRCH 算法距離度量
密度聚類算法概念拓展DBSCAN 算法
基于網(wǎng)格的聚類算法基于模型的聚類算法
概念
聚類是無監(jiān)督學(xué)習(xí)，分類&預(yù)測是有監(jiān)督學(xué)習(xí)。
輸入數(shù)據(jù)集，輸出聚類結(jié)果。輸出結(jié)果是 K 組簇，每個簇是一組相似的對象。
距離度量
距離度量有很多方法：
Minkowski 距離：
D
i
j
=
(
∑
k
=
1
d
∣
x
i
k
?
x
j
k
∣
n
)
1
n
D_{ij} = (\sum_{k=1}^d|x_{ik}-x_{jk}|^n)^{\frac{1}{n}}
Dij?=(∑k=1d?∣xik??xjk?∣n)n1? 當(dāng) n=1 時，就是曼哈頓距離/絕對值（City-block）
D
i
j
=
∑
k
=
1
d
∣
x
i
k
?
x
j
k
∣
D_{ij} = \sum_{k=1}^d|x_{ik}-x_{jk}|
Dij?=∑k=1d?∣xik??xjk?∣
:::warning 考試請使用曼哈頓距離，不要使用歐式距離 :::
當(dāng) n=2 時，就是歐氏距離（Euclidean）
D
i
j
=
(
∑
k
=
1
d
∣
x
i
k
?
x
j
k
∣
2
)
1
2
D_{ij} = (\sum_{k=1}^d|x_{ik}-x_{jk}|^2)^{\frac{1}{2}}
Dij?=(∑k=1d?∣xik??xjk?∣2)21?
當(dāng) n=∞ 時，就是切比雪夫距離（Chebyshev）
D
i
j
=
max
?
k
=
1
d
∣
x
i
k
?
x
j
k
∣
D_{ij} = \max_{k=1}^d|x_{ik}-x_{jk}|
Dij?=maxk=1d?∣xik??xjk?∣
Mahalanobis 距離：
D
i
j
=
(
x
i
?
x
j
)
T
S
?
1
(
x
i
?
x
j
)
D_{ij} = \sqrt{(x_i-x_j)^TS^{-1}(x_i-x_j)}
Dij?=(xi??xj?)TS?1(xi??xj?)
?
其中 S 是協(xié)方差矩陣，
S
i
j
=
1
n
?
1
∑
k
=
1
n
(
x
k
i
?
μ
i
)
(
x
k
j
?
μ
j
)
S_{ij}=\frac{1}{n-1}\sum_{k=1}^n(x_{ki}-\mu_i)(x_{kj}-\mu_j)
Sij?=n?11?∑k=1n?(xki??μi?)(xkj??μj?)
點對稱距離
基于分割的聚類算法 K-Means&K-Medoids
一般把 K 值作為輸入，作為目標(biāo)聚類數(shù)。
K-Means 算法（K-均值算法）
【機(jī)器學(xué)習(xí)】K-means（非常詳細(xì)）| 知乎
機(jī)器學(xué)習(xí)系列（九）聚類之 AGNES | 知乎
首先選取 K 個點作為初始聚類中心然后計算每個點到這 K 個點的距離，把每個點分配到距離最近的聚類中心然后重新計算每個簇的中心點
a
i
=
1
∣
C
i
∣
∑
x
∈
C
i
x
a_i=\frac{1}{|C_i|}\sum_{x\in C_i}x
ai?=∣Ci?∣1?∑x∈Ci??x
重復(fù)這個過程直到聚類中心不再變化或者平均誤差收斂
平均誤差：
E
=
∑
i
=
1
K
∑
x
∈
C
i
d
(
x
,
a
i
)
E=\sum_{i=1}^K\sum_{x\in C_i}d(x,a_i)
E=∑i=1K?∑x∈Ci??d(x,ai?)
優(yōu)點：
算法的復(fù)雜度是
O
(
t
K
n
)
O(tKn)
O(tKn)，t 是迭代次數(shù)，n 是數(shù)據(jù)集大小。
缺點：
K 值的選取不好確定對噪聲和離群點敏感，有較大的離群點時，聚類中心會被拉偏對初始聚類中心的選擇敏感，初始聚類中心不同，聚類結(jié)果也不同不能發(fā)現(xiàn)非凸形狀的簇，比如環(huán)形簇
K-Medoids 算法（K-中心點算法）
數(shù)據(jù)挖掘入門筆記——K-Medoids（以一知萬）| 知乎
k-mediods 每次選取的質(zhì)心，必須是樣本點，
而 k-means 每次選取的質(zhì)心可以是樣本點之外的點，
就好比中位數(shù)和平均值的區(qū)別
K-Medoids 和 K-Means 方法類似，在選取聚類中心時，K-Medoids 選取的是樣本點，而 K-Means 選取的是樣本點之外的點。
首先選取 K 個點作為初始聚類中心然后計算每個點到這 K 個點的距離，把每個點分配到距離最近的聚類中心選取當(dāng)前簇中所有其他點到該中心點的距離之和最小的點作為新的中心點重復(fù)這個過程直到聚類中心不再變化
優(yōu)點：
對噪聲和離群點不敏感
缺點：
算法的復(fù)雜度是
O
(
t
K
n
2
)
O(tKn^2)
O(tKn2)，t 是迭代次數(shù)，n 是數(shù)據(jù)集大小。復(fù)雜度偏大，難以處理大數(shù)據(jù)集
層次聚類算法
采用距離作為衡量標(biāo)準(zhǔn)，分為凝聚式（AGNES）和分裂式（DIANA）。
AGNES 算法
輸入一個 K 值，作為目標(biāo)聚類數(shù)。
把點和點集都視為簇，每次把距離最近的兩個簇合并，直到聚類數(shù)為 K。
距離的計算方式有很多種，比如最短距離、最長距離、平均距離、中心距離等。
距離相同隨便分，優(yōu)先分離落單的點。
DIANA 算法
DIANA 算法 | 博客園
思想和 AGNES 相反，從一個簇開始，每次把距離最遠(yuǎn)的點分離出來，直到聚類數(shù)為 K。
首先把所有點作為一個簇
尋找直徑最大的簇，作為待分裂的簇
直徑：
d
i
a
m
(
C
i
)
=
max
?
x
,
y
∈
C
i
d
(
x
,
y
)
diam(C_i)=\max_{x,y\in C_i}d(x,y)
diam(Ci?)=maxx,y∈Ci??d(x,y)
也可以選擇相異度等其他標(biāo)準(zhǔn)來選擇待分裂的簇
尋找直徑最大的簇中，距離簇中所有其他點距離之和最大的點，作為分裂出來的簇（分裂出來的簇只有一個點）在原來的簇中，尋找距離分裂出來的簇最近的點，如果這個點到新簇的距離小于到原來簇中任意點的距離，則把這個點加入新簇重復(fù) 3 直到原來的簇中沒有點可以加入新簇重復(fù) 1-4 直到聚類數(shù)為 K
優(yōu)點和缺點
優(yōu)點：
不需要預(yù)先指定聚類數(shù)可以發(fā)現(xiàn)任意形狀的簇可以發(fā)現(xiàn)離群點對噪聲和離群點不敏感
缺點：
算法的復(fù)雜度是
O
(
n
2
)
O(n^2)
O(n2)，n 是數(shù)據(jù)集大小。復(fù)雜度偏大，難以處理大數(shù)據(jù)集過程不可逆，一旦分裂就無法合并
BIRCH 算法
作為 AGNES 和 DIANA 的改進(jìn)，BIRCH 算法把數(shù)據(jù)集先聚類成 CF 樹，然后再從 CF 樹中選取聚類中心。
距離度量
距離度量有很多方法
最短距離（單連接）
d
m
i
n
(
C
i
,
C
j
)
=
min
?
x
∈
C
i
,
y
∈
C
j
d
(
x
,
y
)
d_{min}(C_i,C_j)=\min_{x\in C_i,y\in C_j}d(x,y)
dmin?(Ci?,Cj?)=minx∈Ci?,y∈Cj??d(x,y)
最長距離（完全連接）
d
m
a
x
(
C
i
,
C
j
)
=
max
?
x
∈
C
i
,
y
∈
C
j
d
(
x
,
y
)
d_{max}(C_i,C_j)=\max_{x\in C_i,y\in C_j}d(x,y)
dmax?(Ci?,Cj?)=maxx∈Ci?,y∈Cj??d(x,y)
平均距離
d
a
v
g
(
C
i
,
C
j
)
=
1
∣
C
i
∣
∣
C
j
∣
∑
x
∈
C
i
∑
y
∈
C
j
d
(
x
,
y
)
d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{x\in C_i}\sum_{y\in C_j}d(x,y)
davg?(Ci?,Cj?)=∣Ci?∣∣Cj?∣1?∑x∈Ci??∑y∈Cj??d(x,y)
中心距離（均值距離）
用簇的中心點來代表簇
d
c
e
n
(
C
i
,
C
j
)
=
d
(
μ
i
,
μ
j
)
d_{cen}(C_i,C_j)=d(\mu_i,\mu_j)
dcen?(Ci?,Cj?)=d(μi?,μj?)
密度聚類算法
聚類（四）—— 基于密度的聚類 | CSDN
基于密度的聚類算法的主要思想是：只要鄰近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閾值，就把它加到與之相近的聚類中。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目的點。 基于密度的聚類算法代表算法有：DBSCAN 算法、OPTICS 算法及 DENCLUE 算法等。
概念拓展
鄰域數(shù)、直接密度可達(dá)、密度可達(dá)、密度相連的概念 | CSDN
基于密度的聚類算法常見 2 個參數(shù)：
?
\epsilon
?
鄰域半徑，表示一個點的鄰域的大小
M
i
n
P
t
s
MinPts
MinPts
鄰域內(nèi)最少點的個數(shù)，表示一個點的鄰域內(nèi)最少有多少個點
中心對象（核心對象）：如果一個點的鄰域內(nèi)至少有 MinPts 個點，則這個點是一個中心對象。
直接密度可達(dá)：如果 A 在 B 的
?
\epsilon
?-鄰域內(nèi)，且 B 是一個中心對象，則 A 直接密度可達(dá) B。
密度可達(dá)：A 雖然不在 B 的
?
\epsilon
?-鄰域內(nèi)，在 C 的
?
\epsilon
?-鄰域內(nèi)，且 C 是 B 的
?
\epsilon
?-鄰域內(nèi)的點，且 B 是一個中心對象，則 A 密度可達(dá) B。
（密度可達(dá)的傳遞性）
密度相連：如果 A 和 B 都密度可達(dá) C，則 A 和 B 密度相連。
DBSCAN 算法
首先選取一個點 P如果 P 是一個中心對象（即滿足鄰域內(nèi)至少有 MinPts 個點），則把 P 以及所有密度可達(dá)的點加入一個簇如果 P 不是一個中心對象，則把 P 標(biāo)記為噪聲點重復(fù) 1-3 直到所有點都被訪問過
基于網(wǎng)格的聚類算法
基于模型的聚類算法
————————————————
版權(quán)聲明：本文為 田園幻想鄉(xiāng) 的原創(chuàng)文章，遵循 CC 4.0 BY-NA-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。 原文鏈接：http://truraly.fun/課程筆記/數(shù)據(jù)挖掘/【7】聚類分析.html
柚子快報邀請碼778899分享：人工智能 數(shù)據(jù)挖掘-聚類分析
推薦文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
CasasBahia家居優(yōu)選
