Kernel K-means 実装 in Python

投稿者: user28277

環境: Mac, Jupyter-Notebook, Python2.7
Kernel K-meansを実装したんですが、うまく動作しません。コードにエラーは出ません。どこかの計算が間違っているんだと思いますが、どこかわからないので誰か助けてください。

Algorithmについてはこちらがわかりやすいかと思います
Link_01
Link_02

とりあえずデータを貼ります、下に実際のコードを書きました。

データ生成

    from sklearn.metrics.pairwise import pairwise_kernels

    class Kernel_Kmeans(object):

        def __init__(self, n_clusters=3, max_iter=50, kernel="linear",
                    gamma=None, degree=3, coef0=1, kernel_params=None):
            self.n_clusters = n_clusters
            self.max_iter = max_iter
            self.kernel = kernel
            self.gamma = gamma
            self.degree = degree
            self.coef0 = coef0
            self.kernel_params = kernel_params

        def kernel_matrix(self, X, Y = None):
            if callable(self.kernel):
                prams = self.kernel_params or {}
            else:
                params = {"gamma": self.gamma,
                          "degree": self.degree,
                          "coef0": self.coef0}

            return pairwise_kernels(X, Y, metric = self.kernel,
                                    filter_params = True, **params)

        def initialize_cluster(self, X):
            self.labels = np.random.choice(xrange(self.n_clusters), X.shape[0])
            #self.cluster_size = np.bincount(self.labels)


        def fit(self, X):
            n_samples = X.shape[0]
            self.initialize_cluster(X)

            for ite in xrange(self.max_iter):
                self.cluster_size = np.bincount(self.labels)
                for i in xrange(n_samples):
                    data = X[self.labels == 0]
                    xm = np.sum(self.kernel_matrix(data, Y = X[i].reshape(1, X.shape[1])))/self.cluster_size[0]
                    mm = np.sum(self.kernel_matrix(data))/(self.cluster_size[0]**2)
                    min_dist = mm - 2*xm 
                    for j in xrange(self.n_clusters

):
                    if j == (self.n_clusters-1):
                        continue
                    tmp_data = X[self.labels == j+1]
                    tmp_xm = np.sum(self.kernel_matrix(data, Y = X[i].reshape(1, X.shape[1])))/self.cluster_size[j+1]
                    tmp_mm = np.sum(self.kernel_matrix(data))/(self.cluster_size[j+1]**2)
                    tmp_dist = tmp_mm - 2*tmp_xm 
                    if tmp_dist < min_dist:
                        min_dist = tmp_dist
                        self.labels[i] = j

解決

いくつかバグがあるので気づいたものを箇条書きします。

  • 特徴空間における距離の計算 (E step) と、どのクラスタに属するかの計算 (M step) は分けて行うべきです。距離の計算を行っている最中にクラスタの割り当てを変えてしまうと、クラスタサイズが計算途中に変わってしまいます。
  • クラスタサイズの計算は各イテレーションごとに行う必要があります。
  • datatmp_data、および jj+1 を取り違えている箇所があります。E step と M step を分けるとそもそも tmp_*** を作る必要もインデックスをずらす必要も無くなり、単純になると思います。
  • 収束判定が無いので毎回 max_iter 回繰り返しています。ただしこれは無くてもクラスタリング結果は変わりません。

また、バグでは無いと思いますが、半径1の円と半径2の円だと分離しにくいみたいです。こちらの環境で自分で書き直した実装と他の方実装でも試してみたのですが、γ=0.1 の RBF では分離できませんでした。半径1と半径5であれば分離できることを確認しました。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *