0

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

アルゴリズムについてはHEREスライドの12,13ページにあります。
データ生成コード
適応前

Global K-means実行結果は以下のとうりです(K=3)
結果

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")
6
  • Python のエラーは行番号まで含めて出力されていると思います。その部分まで含めてコピー&ペーストして頂けませんか? 現在のコードだと np.concatenate((self.centroid, 〜 の行でカッコの対応がとれていないので syntax error が起こります。
    – nekketsuuu
    Commented 2018年6月13日 13:26
  • すいません、今ちょうどエラーが解決しました。しかし、コードがうまくいっていません。質問内容を更新します。
    – user28277
    Commented 2018年6月13日 13:40
  • 更新前のエラーであった index のエラーは、centroid 等の形がおかしいのが原因っぽいですね。思っている形になっているか逐一 print(***.shape) するのが良さそうです。
    – nekketsuuu
    Commented 2018年6月13日 13:42
  • そのとうりです。centroidの形が間違っていました。++質問内容を更新させていただきました。よろしければ回答の方お願いします。
    – user28277
    Commented 2018年6月13日 13:45
  • タイトルも合わせて更新してくださいませんでしょうか? また、コード部分はコード全体を範囲選択して、エディタ上部の {} を押すと Markdown として装飾できますので、お試しください。
    – nekketsuuu
    Commented 2018年6月13日 13:47

1 件の回答 1

0

スライドの "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

上手く行っていそうなクラスタリング結果です

3
  • ありがとうございます。assignのところをコピペで書き換えると次のエラーが出ました。 ValueError: The shape of the initial centers ((2, 2)) does not match the number of clusters 1 他にも書き換える必要があるんですか?
    – user28277
    Commented 2018年6月13日 23:42
  • すいません、そのとおりで、他にも書き換えたところがあります。具体的には fit のところで k=1 のときは mean で計算できているので、k=2 から assign を呼ぶようにしています。こちらで動作確認した全ソースコードを gist にアップロードいたしましたので、ご確認下さい。
    – nekketsuuu
    Commented 2018年6月14日 0:09
  • そこに気づきk=2にしたんですが同様のエラーが出たんです、、ありがとうございます。授業が終わり次第拝見します。
    – user28277
    Commented 2018年6月14日 0:11

この質問に回答するには、ログインする必要があります。