起步
由於 K-means 演算法的分類結果會受到初始點的選取而有所區別,因此有提出這種演算法的改進:
K-means++
。
演算法步驟
其實這個演算法也只是對初始點的選擇有改進而已,其他步驟都一樣。初始質心選取的基本思路就是,
初始的聚類中心之間的相互距離要儘可能的遠
。
演算法描述如下:
步驟一:隨機選取一個樣本作為第一個聚類中心 c1;
步驟二:計算每個樣本與當前已有類聚中心最短距離(即與最近一個聚類中心的距離),用
D(x)
表示;這個值越大,表示被選取作為聚類中心的機率較大;最後,用輪盤法選出下一個聚類中心;
步驟三:重複步驟二,知道選出 k 個聚類中心。
選出初始點後,就繼續使用標準的 k-means 演算法了。
效率
K-means++ 能顯著的改善分類結果的最終誤差。儘管計算初始點時花費了額外的時間,但是在迭代過程中,k-mean 本身能快速收斂,因此演算法實際上降低了計算時間。網上有人使用真實和合成的資料集測試了他們的方法,速度通常提高了 2 倍,對於某些資料集,誤差提高了近 1000 倍。
python實現
這裡只說明初始點篩選的程式碼,因為其他步驟和k-means 一樣,不再累贅:
# coding: utf-8
import
math
import
random
from
sklearn
import
datasets
def
euler_distance
(
point1
:
list
,
point2
:
list
)
->
float
:
“”“
計算兩點之間的尤拉距離,支援多維
”“”
distance
=
0。0
for
a
,
b
in
zip
(
point1
,
point2
):
distance
+=
math
。
pow
(
a
-
b
,
2
)
return
math
。
sqrt
(
distance
)
def
get_closest_dist
(
point
,
centroids
):
min_dist
=
math
。
inf
# 初始設為無窮大
for
i
,
centroid
in
enumerate
(
centroids
):
dist
=
euler_distance
(
centroid
,
point
)
if
dist
<
min_dist
:
min_dist
=
dist
return
min_dist
def
kpp_centers
(
data_set
:
list
,
k
:
int
)
->
list
:
“”“
從資料集中返回 k 個物件可作為質心
”“”
cluster_centers
=
[]
cluster_centers
。
append
(
random
。
choice
(
data_set
))
d
=
[
0
for
_
in
range
(
len
(
data_set
))]
for
_
in
range
(
1
,
k
):
total
=
0。0
for
i
,
point
in
enumerate
(
data_set
):
d
[
i
]
=
get_closest_dist
(
point
,
cluster_centers
)
# 與最近一個聚類中心的距離
total
+=
d
[
i
]
total
*=
random
。
random
()
for
i
,
di
in
enumerate
(
d
):
# 輪盤法選出下一個聚類中心;
total
-=
di
if
total
>
0
:
continue
cluster_centers
。
append
(
data_set
[
i
])
break
return
cluster_centers
if
__name__
==
“__main__”
:
iris
=
datasets
。
load_iris
()
(
kpp_centers
(
iris
。
data
,
4
))