起步
由於 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
））
