ゼロからはじめるデータサイエンス 第2版 ―Pythonで学ぶ基本と実践

290

■

20

章 クラスタリング

20.2

 モデル

各入力は

d

次元空間のベクトルとします。そしていつものように、数値のリストで表

現します。ここでの目的は、同じような入力で構成されるクラスタを識別し、各クラス

タの代表値を求めることです。

例えば、入力がブログのタイトルを表す数値ベクトルだとしましょう。この目的は、

類似したブログ記事のクラスタを見つけ、ユーザがどのようなブログを書いているの

かを理解することです。または、（赤、緑、青）の組み合わせで構成された数千もの色

を使った画像を

10

色だけで印刷しなければならない状況を考えます。クラスタリング

により

10

色 を 選 び 、「 色 の 誤 差 」 を で き る だ け 小 さ く す る こ と で す 。

最も単純なクラスタリングアルゴリズムの

1

つが k平均法です。これはクラスタの数

k

をあらかじめ決めておき、クラスタ内の平均からの距離の二乗和が最小となるよう

に、入力を

S

1

から

S

k

に分類するというものです。

n

個の点を

k

個のクラスタに分ける方法は、何種類もあります。つまり最適なクラス

タを求めるのは非常に難しい問題であることを示しています。ここでは、たいていの

場合で比較的良い結果が求められる繰り返しを使ったアルゴリズムを使うことにしま

しょう。

1. d

次元空間の

k

個の中心点からスタートする

2.

各点を最も近い中心点のクラスタに割り当てる

3.

割り当てが変更されなければ、終了とする

4.

クラスタへの割り当てが変更されていれば、中心点を再計算し、 ...