メインコンテンツへジャンプ

TensorFlow™ on Databricks

Illustration

クラスタリングと k-means 法

k-means アルゴリズムでクラスタリングした最初のアプリケーションに取り組みます。クラスタリングはデータマイニングの手法で、たくさんのデータを集めて互いに類似している点のグループを見つけます。K-means 法は、多くの種類のデータセットからクラスタを見つけるのに適したアルゴリズムです。

クラスタと k-means 法について詳しくは、k-means アルゴリズムに関する scikit-learn のドキュメントを参照するか、次のビデオをご覧ください。

サンプルの作成

まず最初に、いくつかのサンプルを生成する必要があります。サンプルをランダムに生成することもできますが、その場合、非常にまばらに分布したり、あるいは 1 つの大きなグループしか得られない可能性が高く、クラスタリングにはあまり向いていません。

その代わりに、3 つのセントロイド（重心点）を作成し、その点の周囲を（正規分布で）ランダムに選択します。まずは、その方法をご紹介しましょう。

 

import tensorflow as tf
import numpy as np


def create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed):
    np.random.seed(seed)
    slices = []
    centroids = []
    # Create samples for each cluster
    for i in range(n_clusters):
        samples = tf.random_normal((n_samples_per_cluster, n_features),
                                   mean=0.0, stddev=5.0, dtype=tf.float32, seed=seed, name="cluster_{}".format(i))
        current_centroid = (np.random.random((1, n_features)) * embiggen_factor) - (embiggen_factor/2)
        centroids.append(current_centroid)
        samples += current_centroid
        slices.append(samples)
    # Create a big "samples" dataset
    samples = tf.concat(slices, 0, name='samples')
    centroids = tf.concat(centroids, 0, name='centroids')
    return centroids, samples

 

functions.py にコードを記述する

この方法は、n_clusters の異なるセントロイドを np.random.random((1, n_features)) を使用してランダムに作成し、tf.random_normal の中心点として使用します。tf.random_normal 関数が正規分布の乱数値を生成し、現在の中心点に追加します。これにより、中心の周辺に点のかたまりが作成されます。次に、セントロイド（centroids.append）と生成されたサンプル（slices.append(samples)）を記録します。最後に、tf.concat を使用して「1 つの大きなサンプルリスト」を作成し、同じく tf.concat を使用してセントロイドを TensorFlow の変数に変換します。

この create_samples メソッドを functions.py というファイルに保存することで、これらのメソッドをこの（そして次の！）レッスンのスクリプトにインポートできるようになります。次のコードを含む generate_samples.py という新しいファイルを作成します。

 

import tensorflow as tf
import numpy as np

from functions import create_samples

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70

np.random.seed(seed)

centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    centroid_values = session.run(centroids)

 

これは、クラスタと特徴の数（後で可視化できるように、特徴の数は 2 にしておくことをおすすめします）と、生成するサンプル数を設定するだけです。embiggen_factor を増やすと、クラスタの「広がり」やサイズが大きくなります。ここでは、視覚的に識別可能なクラスタを生成するために、適切な学習機会を提供する値を選択しました。

結果を可視化するために、matplotlib を使用してプロット関数を作成しましょう。次のコードを functions.py に追加します。

 

def plot_clusters(all_samples, centroids, n_samples_per_cluster):
     import matplotlib.pyplot as plt
    #Plot out the different clusters
     #Choose a different colour for each cluster
     colour = plt.cm.rainbow(np.linspace(0,1,len(centroids)))
    for i, centroid in enumerate(centroids):
         #Grab just the samples fpr the given cluster and plot them out with a new colour
         samples = all_samples[i*n_samples_per_cluster:(i+1)*n_samples_per_cluster]
         plt.scatter(samples[:,0], samples[:,1], c=colour[i])
         #Also plot centroid
         plt.plot(centroid[0], centroid[1], markersize=35, marker="x", color='k', mew=10)
         plt.plot(centroid[0], centroid[1], markersize=30, marker="x", color='m', mew=5)
     plt.show()

 

functions.py にコードを記述する

このコードは、各クラスタのサンプルを異なる色でプロットし、セントロイドがあるところに大きなマゼンタ色の X を作成するだけです。セントロイドは引数として与えられ、これはあとで便利です。

この関数をインポートするために、generate_samples.py を更新します。ファイルの先頭に from functions import plot_clusters を追加します。そして、次のコードを一番下に追加します。

 

plot_clusters(sample_values, centroid_values, n_samples_per_cluster)

 

generate_samples.py を実行すると、次のプロットが得られます。

初期化

k-means アルゴリズムは、初期セントロイドの選択から始まりますが、これはデータ中の実際のセントロイドをランダムに推測したものに過ぎません。次の関数は、この初期推測値として機能するようにデータセットからランダムにいくつかのサンプルを選択します。

 

def choose_random_centroids(samples, n_clusters):
    # Step 0: Initialisation: Select `n_clusters` number of random points
    n_samples = tf.shape(samples)[0]
    random_indices = tf.random_shuffle(tf.range(0, n_samples))
    begin = [0,]
    size = [n_clusters,]
    size[0] = n_clusters
    centroid_indices = tf.slice(random_indices, begin, size)
    initial_centroids = tf.gather(samples, centroid_indices)
    return initial_centroids

 

functions.py にコードを記述する

このコードでは、まず tf.range(0, n_samples) を使用して各サンプルのインデックスを作成し、次にランダムにシャッフルします。そこから、固定数（n_clusters）のインデックスを選択するために、tf.slice を使用します。これらのインデックスが初期セントロイドに相関し、tf.gather を使用してグループ化され、初期セントロイドの配列が形成されます。

この新しい choose_random_centorids 関数を functions.py に追加し、次のような新しいスクリプトを作成、または以前のスクリプトを更新します。

 

import tensorflow as tf
import numpy as np

from functions import create_samples, choose_random_centroids, plot_clusters

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70

centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)
initial_centroids = choose_random_centroids(samples, n_clusters)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    updated_centroid_value = session.run(initial_centroids)

plot_clusters(sample_values, updated_centroid_value, n_samples_per_cluster)

 

ここでの大きな変更点は、これらの初期セントロイドの変数を作成し、セッション内でその値を計算することです。そして、データの生成に使用された実際のセントロイドではなく、それらの最初の推測値を plot_cluster にプロットします。

これを実行すると、上と同じような画像が得られますが、セントロイドの位置はランダムになります。このスクリプトを数回実行してみて、セントロイドがかなり移動することに注目してください。

セントロイドの更新

セントロイドの位置の推測から開始した後、k-means アルゴリズムはデータに基づいてそれらの推測を更新します。このプロセスでは、各サンプルに最も近いセントロイドを表すクラスタ番号を割り当てます。その後、セントロイドは、そのクラスタに割り当てられた全てのサンプルの平均となるように更新されます。次のコードは、最も近いクラスタに割り当てるステップを処理します。

 

def assign_to_nearest(samples, centroids):
    # Finds the nearest centroid for each sample

    # START from https://esciencegroup.com/2016/01/05/an-encounter-with-googles-tensorflow/
    expanded_vectors = tf.expand_dims(samples, 0)
    expanded_centroids = tf.expand_dims(centroids, 1)
    distances = tf.reduce_sum( tf.square(
               tf.subtract(expanded_vectors, expanded_centroids)), 2)
    mins = tf.argmin(distances, 0)
    # END from https://esciencegroup.com/2016/01/05/an-encounter-with-googles-tensorflow/
    nearest_indices = mins
    return nearest_indices

 

異なるタイプの k-means アルゴリズムと、その他多くの有用な情報を持つこちらのページからコードを拝借したことを、ここに書き添えておきます。

この方法は、各サンプルと各セントロイド間の距離を計算するもので、distance = 行で行われます。ここでの距離の計算は、ユークリッド距離です。重要なポイントは、tf.subtract が 2 つの引数のサイズを自動的に拡大するということです。つまり、サンプルを行列、セントロイドを列ベクトルとして持つことで、それらの間のペアワイズ減算が行われることを意味します。これを行うために、tf.expand_dims を使用して、サンプルとセントロイドの両方に追加の次元を作成し、tf.subtract のこの動作を強制します。

次のコードは、セントロイドを更新します。

def update_centroids(samples, nearest_indices, n_clusters):
    # Updates the centroid to be the mean of all samples associated with it.
    nearest_indices = tf.to_int32(nearest_indices)
    partitions = tf.dynamic_partition(samples, nearest_indices, n_clusters)
    new_centroids = tf.concat([tf.expand_dims(tf.reduce_mean(partition, 0), 0) for partition in partitions], 0)
    return new_centroids

 

このコードは、各サンプルの最も近いインデックスを取得し、tf.dynamic_partition を使用して別々のグループとして取り出します。ここから 1 つのグループに対してtf.reduce_mean を使用してグループの平均を求め、新しいセントロイドを形成します。ここからtf.concat で新しいセントロイドを作成するだけです。

これで必要なものが揃ったので、スクリプトにこれらの呼び出しを追加（または新規作成）できます。

 

import tensorflow as tf
import numpy as np

from functions import *

n_features = 2
n_clusters = 3
n_samples_per_cluster = 500
seed = 700
embiggen_factor = 70


data_centroids, samples = create_samples(n_clusters, n_samples_per_cluster, n_features, embiggen_factor, seed)
initial_centroids = choose_random_centroids(samples, n_clusters)
nearest_indices = assign_to_nearest(samples, initial_centroids)
updated_centroids = update_centroids(samples, nearest_indices, n_clusters)

model = tf.global_variables_initializer()
with tf.Session() as session:
    sample_values = session.run(samples)
    updated_centroid_value = session.run(updated_centroids)
    print(updated_centroid_value)

plot_clusters(sample_values, updated_centroid_value, n_samples_per_cluster)

 

このコードは、次のことを行います。

  1. 初期セントロイドからサンプルを生成する
  2. 初期セントロイドをランダムに選択する
  3. 各サンプルを最も近いセントロイドに関連付ける
  4. 各セントロイドを関連付けられたサンプルの平均となるように更新する

これは、k-means 法の 1 回の実行です！これを反復バージョンにする演習に挑戦することをおすすめします。

1）generate_samples に渡されるシード（種）のオプションは、スクリプトを実行するたびに「ランダムに」生成されるサンプルが一貫していることを保証します。choose_random_centroids 関数にシードを渡していないので、スクリプトを実行するたびに初期セントロイドが異なります。スクリプトを更新して、ランダムなセントロイドのための新しいシードが含まれるようにします。

2）k-means アルゴリズムは反復的に実行され、前の反復で更新されたセントロイドがクラスタの割り当てに使用され、そのクラスタはセントロイドの更新に使用されます。言い換えると、アルゴリズムは assign_to_nearest と update_centroids を交互に呼び出します。停止する前にこの反復を 10 回実行するようにコードを更新します。k-means 法の反復回数が多いほど、結果として得られるセントロイドが平均してより近くなることがわかるでしょう。（k-means 法の経験者向けに、今後のチュートリアルでは、収束関数とその他の停止基準について解説する予定です。）