呢篇文 需要
熟悉呢方面 嘅人幫手寫。
詳情請去討論頁 睇。
K-平均聚類法 (英文 :k -means clustering )係一種常用嘅聚類分析 演算法 。
而家
k
=
3
{\displaystyle k=3}
,研究者想將啲數據分做三個聚類-由藍色 圓圈、黃色 交叉同埋紅色 十字代表。
K-平均聚類法嘅出發點係假定咗已知拃數據分幾多個聚類(聚類數量
=
k
{\displaystyle =k}
)。喺最簡單嗰種情況下,K-平均聚類法可以噉嚟想像[ 1] [ 2] :
設
n
{\displaystyle n}
做個案嘅數量而
k
{\displaystyle k}
做聚類數量;
建立
k
{\displaystyle k}
咁多個中心點 (cluster center),每個中心點嘅位置叫
μ
i
{\displaystyle {\boldsymbol {\mu }}_{i}}
[ 註 1] ;
是但攞其中一個個案
x
i
{\displaystyle \mathbf {x} _{i}}
嚟睇,
‖
x
i
−
μ
i
‖
{\displaystyle \left\|\mathbf {x} _{i}-{\boldsymbol {\mu }}_{i}\right\|}
表示
x
i
{\displaystyle \mathbf {x} _{i}}
同離佢最近嗰個
μ
i
{\displaystyle {\boldsymbol {\mu }}_{i}}
之間嘅距離;
慢慢調節啲中心點嘅位置[ 註 2] ,務求令啲
‖
x
−
μ
i
‖
{\displaystyle \left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|}
嘅總值有咁細得咁細 [ 註 3] [ 3] 。
數學化啲噉講,K-平均聚類法係要將
n
{\displaystyle n}
個個案分拆做
k
{\displaystyle k}
個集 (
k
≤
n
{\displaystyle k\leq n}
),
S
=
{
S
1
,
S
2
,
.
.
.
S
k
}
{\displaystyle \mathbf {S} =\{S_{1},S_{2},...S_{k}\}}
,搵出:
a
r
g
m
i
n
S
∑
i
=
1
k
∑
x
∈
S
i
‖
x
−
μ
i
‖
2
=
a
r
g
m
i
n
S
∑
i
=
1
k
|
S
i
|
Var
S
i
{\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}={\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}|S_{i}|\operatorname {Var} S_{i}}
K-平均聚類法亦可以用圖嚟表示。睇吓附圖幅 gif :想像家陣
k
=
3
{\displaystyle k=3}
,研究者想將啲數據分做三個聚類-聚類由藍色 圓圈、黃色 交叉同埋紅色 十字代表;當中大藍色 圓圈、大黃色 交叉同大紅色 十字表示嗰三個聚類嘅預想中心點;K-平均聚類法就可以當成一次一次(隨住 iteration
數值上升)噉郁動三個中心點,直接達到理想數值(例如
‖
x
−
μ
i
‖
{\displaystyle \left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|}
嘅總值去到最細)為止。
↑ 初始化 嗰陣,中心點嘅位置可以隨機 噉設。
↑ 即係好似爬山演算法 等嘅最佳化 做法噉。
↑ K-平均聚類法仲可以用第啲基準嚟界定乜先係「理想嘅中心點位置」,例如係要每個聚類內部嘅距離有咁細得咁細。
↑ Tryon, Robert C. (1939). Cluster Analysis: Correlation Profile and Orthometric (factor) Analysis for the Isolation of Unities in Mind and Personality . Edwards Brothers.
↑ Arthur, David; Manthey, B.; Roeglin, H. (2009). "k-means has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS) . arXiv:0904.1113.
↑ 引用錯誤 無效嘅<ref>
標籤;無文字提供畀叫做kaufman1990
嘅參照