44755
環境: Jupyter Notebook, Macbook air, Python2.7  
Global
K-meansを実装したんですが、アルゴリズムがうまく働いていないのでそれについて質問させてもらいました。K=3以上のクラスタリングになるとなぜかcentroidが近くに設置されます。どこがおかしいんでしょうか？

アルゴリズムについては[HEREスライド](http://slideplayer.com/slide/7295998/)の12,13ページにあります。  
[![データ生成コード](https://i.stack.imgur.com/PZlLz.png)](https://i.stack.imgur.com/PZlLz.png)  
[![適応前](https://i.stack.imgur.com/WJk50.png)](https://i.stack.imgur.com/WJk50.png)

Global K-means実行結果は以下のとうりです(K=3)  
[![結果](https://i.stack.imgur.com/WZ5ck.png)](https://i.stack.imgur.com/WZ5ck.png)

```

    class GlobalKmeans(object):
    
        def __init__(self, X, cluster):
            self.X = X
            self.num = X.shape[0]
            self.label = np.zeros((self.num, 1))
            self.cluster = cluster
    
    
        def distance(self, x, y):
            return np.linalg.norm(x-y)
    
    
        def assign(self):
            # Make array for storing value of Cost function
            current_distance = 0
            temp_dis = 0
            clas_rabel = 0
            for i in xrange(self.num):
                # self.X[i]をcentroid候補として固定
                for j in xrange(self.num):
                    # まず固定したcentroid候補とcurrentデータとの距離測定
                    kyori = self.distance(self.X[i], self.X[j])
                    for k in xrange(self.k):
                        # currentデータと各centroidsとの距離測定
                        k_kyori = self.distance(self.centroid[k], self.X[j])
                        #from IPython.core.debugger import Pdb; Pdb().set_trace()
    
                        # 一番近い距離をkyoriにする
                        if k_kyori < kyori:
                            kyori = k_kyori
                        else:
                            kyori = kyori
                    # 1回目
                    if i == 0:
                        current_distance = current_distance + kyori
                    # 2回目以降はtemp
                    else:
                        temp_dis = temp_dis + kyori
                # ラベル更新         
                if temp_dis <= current_distance:
                    clas_rabel = i
    
            if self.k < self.cluster:
                # Add centroid
                self.centroid = np.concatenate((self.centroid, self.X[clas_rabel].reshape((1,2))), axis = 0)   
            #from IPython.core.debugger import Pdb; Pdb().set_trace()
    
    
        def give_label(self):
            for i in xrange(self.num):
                temp = self.distance(self.X[i], self.centroid[0])
                labe = 0
                for k in xrange(self.k):
                    if k == 0:
                        continue
                    if temp > self.distance(self.X[i], self.centroid[k]):
                        labe = k
    
                self.label[i] = labe
    
    
        def fit(self):
            self.k = 1
            self.centroid = np.mean(self.X, axis = 0).reshape((1,2))
            while(self.k <= self.cluster):
                self.assign()
                self.k = self.k + 1
            self.k = self.k - 1
            self.give_label()
    
        def plot(self):
            plt.figure(figsize=(10,10))
            for j in xrange(self.cluster):
                points = X[np.where(self.label == j)[0]]
                plt.scatter(points[:,0], points[:,1])
                plt.scatter(self.centroid[j,0], self.centroid[j,1], s = 300, marker = "x")
    
```
CC BY-SA 4.0
2018-06-13T12:22:22.553
44751
2018-06-13T16:18:35.150
2018-06-13T14:13:03.167
question
python 機械学習
Global K-means 実装がうまくいかない
スライドの "Global K-means" をナイーブに実装した場合、初期値を指定した K-means
をたくさん繰り返すことになります。今回のプログラムではその K-means
が正しく実装できていません。具体的には、初期値を元に1回ラベルをつけた後、収束計算をしていません。

また、一番近い centroid を見つける部分で最短距離 `temp` を更新していないため、出力時のラベル付けにもバグがあります。

確認のため、私の環境において `assign` 関数の中で自前の K-means ではなく `sklearn.cluster.KMeans`
を使ったところ、良さそうなクラスタリングができることを確認しました。

```

    from sklearn.cluster import KMeans
    
```

```

    def assign(self):
        min_inertia = 0.0
        new_centroids = np.zeros((self.k, self.X.shape[1]))
        for i in xrange(self.num):
            cs = np.concatenate((self.centroid, self.X[i].reshape((1, 2))), axis=0)
            kmeans = KMeans(n_clusters=self.k, init=cs, n_init=1).fit(self.X)
            if i == 0 or min_inertia > kmeans.inertia_:
                min_inertia = kmeans.inertia_
                new_centroids = kmeans.cluster_centers_
            self.centroid = new_centroids
    
```

[![上手く行っていそうなクラスタリング結果です](https://i.stack.imgur.com/sut33.png)](https://i.stack.imgur.com/sut33.png)
CC BY-SA 4.0
2018-06-13T16:18:35.150
44755
2018-06-13T16:18:35.150
19110
44751
answer