Q&A
上記コードの中で「k-meansが収束しない」とはどこの部分がどうなることを指しているのでしょうか？
K-meansで画像圧縮のコードを書いていました
128 * 128 pixelsの画像があり、各pixelには(R, G, B)の値が0~255でNumPy Arrayで格納されています。k-meansアルゴリズムを用いて、各pixelを１つのサンプルとみなし（つまり128*128サンプルある）、(R, G, B)の空間上で16色のクラスタに分け、各pixelをクラスタ中心点に置き換えることで、画像圧縮をしようとしました。
発生している問題・エラーメッセージ
以下のコードは、kmeansにおいて各クラスタの中心点をアップデートする部分の関数です。
以下のソースコードにおいて、
python
1#---この行がないと、kmeansが収束しない!---# 2centroids = np.zeros((num_clusters, c)) # init centroids
の部分がないと、k-meansが収束せず、逆にこの行を加えるとkmeansが動いたのですが、なぜこの行でcentroids（Numpy Array）の初期化が必要なのか、理解できません。
該当のソースコード
以下のコードは、centroids=init_centroids（k-meansにおいて初めにランダムに中心点を初期化したもの）を引数として受け取ります。クラスタの中心点をアップデートする部分の関数です。
python
1def update_centroids(centroids, image, max_iter=30, print_every=10): 2 """ 3 Carry out k-means centroid update step `max_iter` times 4 5 Parameters 6 ---------- 7 centroids : nparray 8 The centroids stored as an nparray 9 image : nparray 10 (H, W, C) image represented as an nparray 11 max_iter : int 12 Number of iterations to run 13 print_every : int 14 Frequency of status update 15 16 Returns 17 ------- 18 new_centroids : nparray 19 Updated centroids 20 """ 21 (h, w, c, num_clusters) = (image.shape[0], image.shape[1], image.shape[2], centroids.shape[0]) # 画像のh高さ、w幅、c色の数、num_clustersクラスタの数（16） 22 image_flat = image.reshape(h * w, c) # flatten the image --> each row: pixel, each column: color 23 for _iter in range(max_iter): 24 dist = np.array([np.linalg.norm(pixel - centroids, ord=2, axis=1) for pixel in image_flat]) # 各pixelと各クラスタの中心点までの距離を計算 25 idx = np.argmin(dist, axis=1) 26 # Find closest centroid and update `new_centroids` 27 28 #---この行がないと、kmeansが収束しない!---# 29 centroids = np.zeros((num_clusters, c)) # centroidsをゼロで初期化 30 #----- -----# 31 32 for k in range(num_clusters): 33 centroids[k] = np.mean(image_flat[idx == k], axis=0) 34 if _iter % print_every == 0: 35 print("{} iterations done.".format(_iter)) 36 print("index of cluster (idx[::100]): \n") 37 print(idx[::100]) 38 print("centroids' RGB values: \n") 39 print(centroids) 40 print(25*"-") 41 new_centroids = np.copy(centroids) 42 return new_centroids
- 全体の関数設計（補足）
python
1centroids_init = init_centroids(num_clusters, image) 2centroids = update_centroids(centroids_init, image, max_iter, print_every)
init_centroids関数は、以下のようになっています。
python
1def init_centroids(num_clusters, image): 2 (h, w, c) = (image.shape[0], image.shape[1], image.shape[2]) 3 image_flat = image.reshape(h * w, c) 4 init_centroid_index = np.array([random.randint(0, h * w) for _ in range(num_clusters)]) 5 centroids_init = image_flat[init_centroid_index] 6 return centroids_init
仮説
NumPy配列の変数アドレスの問題か何かだと思うのですが、毎イタレーションごとに、各要素を書き換えているので、問題ない気がしています。なのでなぜ該当行がないと動かないのか分かりません。メモリの問題？なお、distはshape=(128*128, 16)の配列です。
補足情報（FW/ツールのバージョンなど）
使用しているライブラリはNumPyのみです。
追記（2019/8/11/09:00)
なお、centroids配列は次のようになっています。
- 収束しない時（centroids配列をゼロで初期化しないとき）
python
110 iterations done. 2index of cluster (idx[::100]): 3 4[ 9 9 6 15 9 9 15 14 15 15 15 9 9 15 13 1 9 14 15 9 9 9 9 9 5 11 9 9 15 9 14 14 9 9 9 9 9 9 15 15 7 9 11 9 13 9 9 9 14 6 9 15 9 15 14 14 15 9 14 9 15 14 15 14 14 9 9 14 11 11 9 6 9 14 7 15 9 9 15 9 9 11 15 14 15 9 9 15 9 15 9 13 9 15 9 9 9 9 15 8 9 15 11 14 9 9 13 9 15 9 14 13 9 9 14 9 9 15 9 9 9 9 15 9 9 9 9 9 14 9 9 9 15 9 9 9 14 9 9 9 9 15 15 9 9 14 15 9 9 10 9 9 15 12 9 14 15 7 14 9 2 15 9 14 3 2 9 9 9 1] 11centroids' RGB values: 12 13[[197 220 187] 14 [185 212 158] 15 [195 207 116] 16 [197 211 153] 17 [200 216 159] 18 [203 221 196] 19 [194 216 184] 20 [207 89 67] 21 [192 212 139] 22 [140 93 52] 23 [202 214 108] 24 [183 204 109] 25 [196 144 134] 26 [142 189 120] 27 [125 30 24] 28 [168 184 91]] 29------------------------- 3020 iterations done. 31index of cluster (idx[::100]): 32 33[ 7 7 2 9 7 7 9 7 15 15 9 9 7 9 11 12 7 7 1 7 1 7 7 9 34 12 1 7 6 7 1 1 7 7 7 1 1 7 9 15 1 7 12 7 0 7 9 1 7 35 7 9 7 9 7 1 9 7 14 7 9 14 9 1 7 9 7 14 6 12 7 3 7 7 36 9 7 7 6 7 14 12 9 14 12 14 7 9 7 9 7 9 9 12 7 7 9 7 9 37 7 6 6 14 7 7 9 7 9 7 14 7 7 7 7 9 7 9 7 7 7 7 9 7 38 7 7 9 14 7 7 7 9 7 9 7 14 7 7 7 7 12 9 14 7 14 9 7 7 39 7 14 7 13 7 14 12 1 14 7 12 12 7 14 3 12 7 7 7 12] 40centroids' RGB values: 41 42[[206 173 150] 43 [201 74 52] 44 [192 213 163] 45 [195 216 174] 46 [199 216 188] 47 [203 219 183] 48 [171 198 125] 49 [147 87 50] 50 [209 203 183] 51 [151 182 89] 52 [202 214 108] 53 [152 177 125] 54 [188 206 111] 55 [203 221 204] 56 [ 81 12 10] 57 [197 170 88]] 58-------------------------
値が激しく変化しています。クラスタの配属変化も激しいです。
- 収束するとき（centroids配列をきちんとゼロで初期化する時）
python
110 iterations done. 2index of cluster (idx[::100]): 3 4[11 10 3 2 11 1 6 15 14 7 8 10 15 2 6 3 15 15 0 1 15 15 4 2 5 7 15 1 3 10 15 15 15 1 1 15 15 4 6 14 14 1 7 10 5 15 10 1 15 6 15 8 4 6 15 15 0 10 12 11 8 12 2 15 15 2 4 12 5 7 11 3 15 15 7 2 14 4 6 1 9 8 2 4 7 9 4 2 13 2 15 13 10 7 9 9 13 13 2 8 9 5 3 12 4 15 6 13 8 9 12 13 1 0 15 13 10 2 4 9 1 1 2 15 9 13 1 0 12 9 10 1 8 4 13 10 12 9 9 10 1 8 8 12 4 12 2 9 10 10 1 12 0 3 12 12 7 15 12 4 7 7 11 12 5 7 1 11 11 5] 11centroids' RGB values: 12 13[[156.91060291 148.36382536 65.34303534] 14 [115.60351413 113.881589 55.83346066] 15 [149.43956044 180.28671329 82.11788212] 16 [192.38899083 218.05321101 191.79449541] 17 [106.05243902 60.4597561 34.56585366] 18 [189.56716418 201.32338308 148.12271973] 19 [151.72988506 196.17241379 129.73754789] 20 [191.81183317 204.19786615 92.38312318] 21 [172.34967623 194.25531915 84.92969473] 22 [143.43722564 21.54784899 24.15276558] 23 [115.6759195 156.87369882 74.57113116] 24 [172.82359081 52.58037578 41.93841336] 25 [ 64.18624044 6.95969423 5.67268937] 26 [126.88624339 180.91269841 96.17107584] 27 [203.56716418 106.52487562 76.47761194] 28 [200.2748184 49.78006457 41.54560129]] 29------------------------- 3020 iterations done. 31index of cluster (idx[::100]): 32 33[11 10 3 2 15 1 6 15 14 7 8 10 15 2 6 3 15 15 8 10 15 15 4 2 34 7 15 1 3 10 15 15 15 10 1 15 15 4 5 14 14 1 7 13 5 11 10 1 15 35 15 8 4 5 15 15 2 13 12 11 8 12 2 15 15 2 4 12 5 7 11 3 15 15 36 2 14 4 6 1 9 7 2 4 7 9 1 2 13 2 15 6 13 7 9 11 13 13 2 37 9 5 3 12 4 15 6 13 8 9 12 13 1 0 15 13 10 8 4 9 10 1 8 11 38 13 1 0 12 11 10 1 8 1 13 10 12 9 9 10 1 8 8 12 4 12 2 9 10 39 1 12 0 3 12 12 7 15 12 4 7 7 11 12 5 7 1 11 11 5] 40centroids' RGB values: 41 42[[154.13868613 140.83698297 62.75912409] 43 [116.4886562 106.15794066 53.08202443] 44 [147.43695015 177.84359726 80.51221896] 45 [192.87184116 218.00180505 191.34115523] 46 [104.56811989 55.91008174 32.53814714] 47 [184.55113636 201.33238636 147.74431818] 48 [144.18470418 192.13275613 118.23809524] 49 [189.66607302 205.07569012 93.33926981] 50 [172.52888087 190.85920578 82.72292419] 51 [140.20383451 19.89101917 22.60443996] 52 [112.52730375 147.36433447 68.76450512] 53 [171.89906542 43.12149533 38.25420561] 54 [ 63.49573257 6.6116643 5.42318634] 55 [122.00744048 174.20089286 88.81994048] 56 [202.94634146 107.63902439 76.84634146] 57 [200.11342685 52.06092184 42.48857715]] 58-------------------------
中心点の値はそれほど変動せず、クラスタの配属が安定的です。
「centroids = np.zeros((num_clusters, c))」の前後で”centroids”の値がどうなっているのかを確認されましたか？
ご連絡ありがとうございます！
本来、k-meansアルゴリズムを回していると、クラスタの中心点（上のsrcでいうcentroidsというnp.array）が徐々に収束して一定値に向かいますが、収束しないときはずっと激しく変化したままになります。centroids配列をprintしていると、変化が止まらないことが観察できます。
centroidsの具体的な値については、質問を修正します！
”「centroids = np.zeros((num_clusters, c))」の前後で”centroids”の値がどうなっているのか”というのはプログラム中で”centroids”がどう変化するのかデバッグしたら何か判るのでは？という意味でした。
ところで、関数の引数に「centroids」を渡しているのに、関数中で初期化して問題ないのですか？
（初期化するなら渡す意味もないような）
あまり関係ないかもですが、
この update_centroids() を呼び出すときの 最初の centroids はどういう値を与えているのでしょうか？
printしてみたのですが、centroidsがゼロにきちんと初期化されている、ということ以外には分かりませんでした。
関数内の初期化については、全体の関数設計について僕の説明不足でした。k-meansにおいて、一番初めにクラスタの中心点を決める際、ランダムに中心点を決めるので、その中心点をinit_centroidsと名付けており、update_centroids関数は、init_centroidsを引数として受け取ります。引数の名前がややこしくて申し訳ありません。
失礼いたしました。質問内容に補足いたします。
回答1件
0
ベストアンサー
もしかすると、その関数の入力の centroids の型が int系なのではないでしょうか。
なので、 centroids[k] = np.mean(..) の結果が int に cast されて計算が正しくされないから収束しないのでは、と思いました。
import numpy as np z_int = np.arange(6).reshape(3, 2) z_float = z_int * 1. print(z_int) """ [[0 1] [2 3] [4 5]] """ print(z_float) """ [[0. 1.] [2. 3.] [4. 5.]] """ #%% z_int[0] = np.mean(z_float) * 0.567 print(z_int) # ndarrayの型が int だと castされる """ [[1 1] [2 3] [4 5]] """ z_float[0] = np.mean(z_float) * 0.567 print(z_float) # float系だと大丈夫 """ [[1.4175 1.4175] [2. 3. ] [4. 5. ]] """
■ 追記1
あとひとつ気になったのが、
centroids[k] = np.mean(image_flat[idx == k], axis=0)
で cluster-k に所属するPixelが一つもない場合
np.mean(image_flat[idx == k], axis=0) が nan になってしまって少し気持ち悪いので、
idx == k が存在しないときは更新しないような処理を入れるほうが良い気がしました。
投稿2019/08/11 00:32
編集2019/08/11 00:42総合スコア948
まさにこれでした。image_flatというnp.arrayのデータ型を見ると、uint8となっておりました。RGBのピクセル値なので、納得です。
dist = np.array([np.linalg.norm(np.array(pixel, dtype='float64') - centroids, ord=2, axis=1) for pixel in image_flat])のように、dist配列を求めるときに、pixelのデータ型をきちんと指定してあげれば、挙動が正常になりました。
追記1について、ありがとうございます。更新しない処理を含めておきます。
あなたの回答
tips
プレビュー
