スペクトラルクラスタリング


クラスタリング分析の話になっております。前回の記事にはGMMモデルMini Batch K-Meansについて話しました。この記事では、スペクトラルクラスタリング(Spectral Clustering)について話していきます。

スペクトラルクラスタリングとは

スペクトラルクラスタリングとは、クラスタリングの機械学習の方法のうち、教師なし学習に分類されます。スペクトルクラスタリングでは、データをグラフに置き換え、繋がりがある近いデータ程一緒にわけられやすくなっています。

KMeansやGaussian mixture modelはクラスタの中心点からの距離に基づいてクラスタリングのモデルですが、スペクトラルクラスタリングでは連結性に注目してクラスタリングのモデルのため、KMeansやGaussian mixtureではうまくクラスタリングできなかったようなデータをうまくクラスタリングできることがあります。

下記の円形と月形のグラフのクラスタリング結果を見ると、スペクトラルクラスタリングがよく対応出来ています。但し、学習時間は20倍以上になっています。

Spectral Clustering2

Python Scriptの説明

# ライブラリの読み込み

print(__doc__)

import time

import warnings

import numpy as np

import matplotlib.pyplot as plt

from sklearn import cluster, datasets, mixture

from sklearn.preprocessing import StandardScaler

from itertools import cycle, islice

np.random.seed(0)

# データセット作成

n_samples = 1500

noisy_circles = datasets.make_circles(n_samples=n_samples, factor=.5,

                                      noise=.05)

noisy_moons = datasets.make_moons(n_samples=n_samples, noise=.05)

# クラスターのパラメーター作成

plt.figure(figsize=(9 * 2 + 3, 12.5))

plt.subplots_adjust(left=.02, right=.98, bottom=.001, top=.96, wspace=.05,

                    hspace=.01)

plot_num = 1

default_base = {‘quantile’: .3,

                ‘eps’: .3,

                ‘damping’: .9,

                ‘preference’: -200,

                ‘n_neighbors’: 10,

                ‘n_clusters’: 3}

datasets = [

    (noisy_circles, {‘damping’: .77, ‘preference’: -240,

                     ‘quantile’: .2, ‘n_clusters’: 2}),

    (noisy_moons, {‘damping’: .75, ‘preference’: -220, ‘n_clusters’: 2}),]

for i_dataset, (dataset, algo_params) in enumerate(datasets):

    params = default_base.copy()

    params.update(algo_params)

    X, y = dataset

    #データセットを正規化する

    X = StandardScaler().fit_transform(X)

    #帯域幅作成

    bandwidth = cluster.estimate_bandwidth(X, quantile=params[‘quantile’])

    # クラスタリングモデルの作成

    ms = cluster.MeanShift(bandwidth=bandwidth, bin_seeding=True)

    two_means = cluster.KMeans(n_clusters=params[‘n_clusters’])

    spectral = cluster.SpectralClustering(

        n_clusters=params[‘n_clusters’], eigen_solver=’arpack’,

        affinity=”nearest_neighbors”)

    gmm = mixture.GaussianMixture(

        n_components=params[‘n_clusters’], covariance_type=’full’)

    clustering_algorithms = (

        (‘KMeans’, two_means),

        (‘SpectralClustering’, spectral),

        (‘GaussianMixture’, gmm)

    )

    for name, algorithm in clustering_algorithms:

        t0 = time.time()

        # kneighbors_graphに関連する警告をキャッチ

        with warnings.catch_warnings():

            warnings.filterwarnings(

                “ignore”,

                message=”the number of connected components of the ” +

                “connectivity matrix is [0-9]{1,2}” +

                ” > 1. Completing it to avoid stopping the tree early.”,

                category=UserWarning)

            warnings.filterwarnings(

                “ignore”,

                message=”Graph is not fully connected, spectral embedding” +

                ” may not work as expected.”,

                category=UserWarning)

            algorithm.fit(X)

        t1 = time.time()

        if hasattr(algorithm, ‘labels_’):

            y_pred = algorithm.labels_.astype(np.int)

        else:

            y_pred = algorithm.predict(X)

# 結果の図を作成する

        plt.subplot(len(datasets), len(clustering_algorithms), plot_num)

        if i_dataset == 0:

            plt.title(name, size=30)

        colors = np.array(list(islice(cycle([‘#377eb8’, ‘#ff7f00’, ‘#4daf4a’,

                                             ‘#f781bf’, ‘#a65628’, ‘#984ea3’,

                                             ‘#999999’, ‘#e41a1c’, ‘#dede00’]),

                                      int(max(y_pred) + 1))))

        plt.scatter(X[:, 0], X[:, 1], s=10, color=colors[y_pred])

        plt.xlim(-2.5, 2.5)

        plt.ylim(-2.5, 2.5)

        plt.xticks(())

        plt.yticks(())

        plt.text(.99, .01, (‘%.2fs’ % (t1 – t0)).lstrip(‘0’),

                 transform=plt.gca().transAxes, size=30,

                 horizontalalignment=’right’)

        plot_num += 1

plt.show()

スペクトラルクラスタリングで画像セグメンテーションの実験

この例では、重なった円の画像のデータからスペクトルクラスタリングを使用して円を分離するという問題を考えていきます

 

スペクトルクラスタリング手法は、繋がっているデータを同じクラスタとして認識していきます。画像はクラスタを5としたときに、どう分けられているのかを可視化しています。スペクトルクラスタリングアルゴリズムは、カットと円の体積の比率を最小にするクラスタを選択します。

Spectral Clustering3

Python Scriptの説明

# ライブラリの読み込む
print(__doc__)
import numpy as np
import matplotlib.pyplot as plt

from sklearn.feature_extraction import image
from sklearn.cluster import spectral_clustering

# データセット作成
l = 100
x, y = np.indices((l, l))

center1 = (28, 24)
center2 = (40, 50)
center3 = (67, 58)
center4 = (24, 70)

radius1, radius2, radius3, radius4 = 16, 14, 15, 14

circle1 = (x – center1[0]) ** 2 + (y – center1[1]) ** 2 < radius1 ** 2
circle2 = (x – center2[0]) ** 2 + (y – center2[1]) ** 2 < radius2 ** 2
circle3 = (x – center3[0]) ** 2 + (y – center3[1]) ** 2 < radius3 ** 2
circle4 = (x – center4[0]) ** 2 + (y – center4[1]) ** 2 < radius4 ** 2

#4円のデータセット
img = circle1 + circle2 + circle3 + circle4

# マスク作成
mask = img.astype(bool)
img = img.astype(float)
img += 1 + 0.2 * np.random.randn(*img.shape)

# 画像をグラフに変換する
graph = image.img_to_graph(img, mask=mask)

#モデルの学習
graph.data = np.exp(-graph.data / graph.data.std())
labels = spectral_clustering(graph, n_clusters=4, eigen_solver=’arpack’)
label_im = -np.ones(mask.shape)
label_im[mask] = labels
#結果の図を作成する
plt.matshow(img)
plt.matshow(label_im)

# ##########################
#2円のデータセット
img = circle1 + circle2
mask = img.astype(bool)
img = img.astype(float)

img += 1 + 0.2 * np.random.randn(*img.shape)

#モデルの学習
graph = image.img_to_graph(img, mask=mask)
graph.data = np.exp(-graph.data / graph.data.std())

labels = spectral_clustering(graph, n_clusters=2, eigen_solver=’arpack’)
label_im = -np.ones(mask.shape)
label_im[mask] = labels

#結果の図を作成する
plt.matshow(img)
plt.matshow(label_im)

plt.show()