【k-meansのアルゴリズム】
- 分割するクラスター数Kを決める
- クラスターの中心点の初期値をランダムにK個選択する
- 全てのデータ点と各中心点の距離を測る
- それぞれのデータ点を最も近い中心点のクラスターに分類する。
- 各クラスターのデータ点の重心を求め、新たな中心点とする。
- 全てのデータ点に割り当てられるクラスターが変化しなくなるまで、3.～5.を繰り返す。
点と点の間の距離を使うだけのアルゴリズムで成り立っているため、スクラッチでも比較的簡単に実装できる。
def kmeans(X,K,centers,n_iter):
#Xのサンプル数だけ空のラベルを作る。これがクラスター番号の入れ物になる。
idx = np.zeros(X.shape[0])
for _ in range(n_iter):
#データ点と中心点の距離を計算し、一番近い中心点のインデックス(クラスター番号)を返す。
for i in range(X.shape[0]):
idx[i] = np.argmin(np.sum((X[i,:] - centers)**2,axis=1))
sumでaxis＝１で横方向に足し算していく。
#重心を計算して中心点を移動させる
for k in range(K):
centers[k,:] = X[idx==k,:].mean(axis=0)
axis=0 列ごと axis=1行ごと
return idx,centers#データの生成
np.random.seed(123)
x1 = np.r_[np.random.normal(size=20,loc=1,scale=2),np.random.normal(size=20,loc=8,scale=2)
,np.random.normal(size=20,loc=15,scale=2),np.random.normal(size=20,loc=25,scale=2)]
x2 = np.r_[np.random.normal(size=20,loc=15,scale=2),np.random.normal(size=20,loc=1,scale=2)
,np.random.normal(size=20,loc=20,scale=2),np.random.normal(size=20,loc=0,scale=2)]
X = np.c_[x1,x2]
#可視化
plt.figure(figsize=(6,6))
plt.scatter(X[:,0],X[:,1],c="black",s=10,alpha=0.5)
plt.show()
このデータをk-means法で4グループにクラスタリングしてみる。
簡単のため、繰り返し回数は4回とする。
K=4
centers = np.array([[0,5],[5,0],[10,15],[20,10]])
n_iter = 4
plt.figure(figsize=(8,8))
for j in range(n_iter):
idx = kmeans(X, K, centers, j)[0]
centers = kmeans(X, K, centers, j)[1]
data = pd.DataFrame(X, columns=["X","Y"])
data["idx"] = idx
data0 = data[data.idx==0]
data1 = data[data.idx==1]
data2 = data[data.idx==2]
data3 = data[data.idx==3]
plt.subplot(2, 2, j+1)
plt.scatter(data0.X, data0.Y, color="r", s=10, alpha=0.5)
plt.scatter(data1.X, data1.Y, color="b", s=10, alpha=0.5)
plt.scatter(data2.X, data2.Y, color="g", s=10, alpha=0.5)
plt.scatter(data3.X, data3.Y, color="orange", s=10, alpha=0.5)
plt.scatter(centers[:,0], centers[:,1], color=["r","b","g","orange"])
plt.show()
k-meansは便利だが、実は弱点がある。
それは、最初の中心点が近い位置に固まると、クラスタリングがうまくいかないということだ。
例えば、以下のような中心点が選ばれたとする。
centers = np.array([[0,5],[0,3],[0,0],[20,10]])
plt.figure(figsize=(6,6))
plt.scatter(X[:,0],X[:,1],c="black",s=10,alpha=0.5)
plt.scatter(centers[:,0],centers[:,1],color=["r","b","g","orange"])
plt.show()
この場合は、赤と青、そして緑の中心点が近い位置に固まってしまっている。
すると、何度更新しても上手くクラスタリングできない。
K=4
centers = np.array([[0,5],[0,3],[0,0],[20,10]])
n_iter = 9
plt.figure(figsize=(8,8))
for j in range(n_iter):
idx = kmeans(X, K, centers, j)[0]
centers = kmeans(X, K, centers, j)[1]
data = pd.DataFrame(X, columns=["X","Y"])
data["idx"] = idx
data0 = data[data.idx==0]
data1 = data[data.idx==1]
data2 = data[data.idx==2]
data3 = data[data.idx==3]
plt.subplot(3, 3, j+1)
plt.scatter(data0.X, data0.Y, color="r", s=10, alpha=0.5)
plt.scatter(data1.X, data1.Y, color="b", s=10, alpha=0.5)
plt.scatter(data2.X, data2.Y, color="g", s=10, alpha=0.5)
plt.scatter(data3.X, data3.Y, color="orange", s=10, alpha=0.5)
plt.scatter(centers[:,0], centers[:,1], color=["r","b","g","orange"])
plt.show()
黄色のクラスターが多くなり、青と緑のクラスターが混ざってしまっている。
このように、最初の中心点の選択を間違えると、k-meansが失敗する可能性があるのだ。
k-means++
このようなk-meansの初期値選択の弱点を解消したのが、k-means++である。
k-means++では、中心点が互いに遠いところに配置されるような確率が高くなるように操作する。
アルゴリズムは次の通りである。
- 1つ目の中心点を、データ点の中から均等な確率でランダムに選ぶ。
- 残り全てのデータ点について、既存の中心点との距離の2乗を計算して足し合わせる。
- 2.の結果を合計した値で、それぞれの距離の2乗を割る。
- 3.の結果を新たな確率として、2つ目の中心点を選ぶ。
- 2.～4.を、クラスター数と同じ数の中心点が出来るまで繰り返す。
要約すると、既にある中心点から遠い位置にあるデータ点が次の中心点に選ばれやすくなるという手法だ。
スクラッチで実装すると、以下のようになる。
K = 4
n = X.shape[0]
distance = np.zeros(n*K).reshape(n,K)
centers = np.zeros(X.shape[1]*K).reshape(K,-1)
#最初の確率は均等
pr = np.repeat(1/n,n)
#1つ目の中心点はランダムに選ぶ
centers[0,:] = X[np.random.choice(np.arange(n),1,p=pr),]
distance[:,0] = np.sum((X-centers[0,:])**2,axis=1)
for k in np.arange(1,K):
#1つ目の中心点からの距離によって確率を変更
pr = np.sum(distance,axis=1)/np.sum(distance)
#確率に従って2つ目以降の点を選ぶ
centers[k,:] = X[np.random.choice(np.arange(n),1,p=pr),]
distance[:,k] = np.sum((X-centers[k,:])**2,axis=1)
plt.figure(figsize=(6,6))
plt.scatter(X[:,0],X[:,1],c="black",s=10,alpha=0.5, zorder=1)
plt.scatter(centers[:,0],centers[:,1],color=["r","b","g","orange"], zorder=2)
plt.show()
この初期値選択を組み込んだk-means++法の関数が、以下のコードである。
中心点の初期値を引数に入れる必要が無くなっている。
def kmeansplus(X,K,n_iter):
n = X.shape[0]
idx = np.zeros(X.shape[0])
distance = np.zeros(n*K).reshape(n,K)
centers = np.zeros(X.shape[1]*K).reshape(K,-1)
#最初の確率は均等
pr = np.repeat(1/n,n)
#1つ目の中心点はランダムに選ぶ
centers[0,:] = X[np.random.choice(np.arange(n),1,p=pr),]
distance[:,0] = np.sum((X-centers[0,:])**2,axis=1)
for k in np.arange(1,K):
pr = np.sum(distance,axis=1)/np.sum(distance)
centers[k,:] = X[np.random.choice(np.arange(n),1,p=pr),]
distance[:,k] = np.sum((X-centers[k,:])**2,axis=1)
→試験に流れが出る
for _ in range(n_iter):
#データ点と中心点の距離を計算し、一番近い中心点のインデックス(クラスター番号)を返す。
for i in range(X.shape[0]):
idx[i] = np.argmin(np.sum((X[i,:] - centers)**2,axis=1))
#重心を計算して中心点を移動させる
for k in range(K):
centers[k,:] = X[idx==k,:].mean(axis=0)
return idx,centers上の関数を使って、サンプルデータX = np.c_[x1,x2]をk-means++クラスタリングしたものが下図である。
なお、クラスター数は4として、アルゴリズムを9回繰り返している。
#データの生成
np.random.seed(123)
x1 = np.r_[np.random.normal(size=20,loc=1,scale=2),np.random.normal(size=20,loc=8,scale=2)
,np.random.normal(size=20,loc=15,scale=2),np.random.normal(size=20,loc=25,scale=2)]
x2 = np.r_[np.random.normal(size=20,loc=15,scale=2),np.random.normal(size=20,loc=1,scale=2)
,np.random.normal(size=20,loc=20,scale=2),np.random.normal(size=20,loc=0,scale=2)]
X = np.c_[x1,x2]
K = 4
inter = 9
idx = kmeansplus(X,K,inter)[0]
centers = kmeansplus(X,K,inter)[1]
data = pd.DataFrame(X,columns=["X","Y"])
data["idx"] = idx
data0 = data[data.idx==0]
data1 = data[data.idx==1]
data2 = data[data.idx==2]
data3 = data[data.idx==3]
plt.figure(figsize=(6,6))
plt.scatter(data0.X,data0.Y,color="r",s=10,alpha=0.5)
plt.scatter(data1.X,data1.Y,color="b",s=10,alpha=0.5)
plt.scatter(data2.X,data2.Y,color="g",s=10,alpha=0.5)
plt.scatter(data3.X,data3.Y,color="orange",s=10,alpha=0.5)
plt.scatter(centers[:,0],centers[:,1],color=["r","b","g","orange"])
plt.show()
ライブラリを使用する方法
前節ではアルゴリズムを理解するために、フルスクラッチで実装した。
一般的には、sklearn.clusterからKMeansを呼び出すことで、簡単にk-meansやk-means++を利用できる。
パラメータは以下のセルの通りである。
initはk-meansかk-means++かを選択するもので、デフォルトではk-means++になっている。
from sklearn.cluster import KMeans
NUM_CLUSTER = 4
km_plus = KMeans(n_clusters = NUM_CLUSTER, # クラスター数
init='k-means++', # 中心の設定 default:'k-means++'
n_init=100, # 異なる初期値を用いたk-meansの実行回数
max_iter=300, # 最大イテレーション回数 default: '300'
tol=1e-04, # 収束と判定するための相対的な許容誤差 default: '1e-04'
random_state=0) 今回はNUM_CLUSTERを4に指定して、データXを4つのクラスターに分類する。
分類器に対して.fit_predict()でデータを入力すると、各データが分類されるクラスター番号を取得できる。
idxplus = km_plus.fit_predict(X)
idxplusarray([3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
また、データを分類した後に.cluster_centers_を使用すると、各クラスターの中心となるベクトルを取得できる。
center = km_plus.cluster_centers_
centerarray([[15.89211899, 20.35762159],
[24.56943538, 0.08101047],
[ 7.4376432 , 0.92262059],
[ 1.22883546, 15.1430577 ]])
クラスター番号idxplusをlabelsとしてラベル付けして、データフレームに変換する。
lsa2_df = pd.DataFrame(X, columns = ["x","y"])
lsa2_df["labels"] = idxplus
lsa2_df| x | y | labels | |
|---|---|---|---|
| 0 | -1.171261 | 17.510475 | 3 |
| 1 | 2.994691 | 13.622262 | 3 |
| 2 | 1.565957 | 18.321905 | 3 |
| 3 | -2.012589 | 16.614616 | 3 |
| 4 | -0.157201 | 14.370484 | 3 |
| … | … | … | … |
| 75 | 27.079454 | 0.335885 | 1 |
| 76 | 24.193268 | 1.107712 | 1 |
| 77 | 24.747941 | -1.061349 | 1 |
| 78 | 23.324967 | 2.754515 | 1 |
| 79 | 21.788074 | -0.286352 | 1 |
圧縮したデータをmatplotlibで散布図にプロットする。
クラスターごとに色を分けて、クラスターの中心点は黒点で表示した。
fig = plt.figure(figsize=(6,6))
ax1 = fig.add_subplot(111, xlabel = "x", ylabel = "y", alpha = 0)
ax1.scatter(center[:,0], center[:,1], color="black", s=100, zorder=2)
for name, group in lsa2_df.groupby('labels'):
ax1.plot(group.x, group.y,marker='o', linestyle='', ms=8, label=name, alpha = 0.5, zorder=1)
ax1.legend()
コメント