前回、教師なし学習について説明するなかで、教師なし学習が得意な課題の1つとしてクラスタリング(データのグループ化)があることを紹介しました。教師なし学習を使ったクラスタリングでは、クラスタ分け(グループ分け)という行為自体が「学習」に相当します。

これを踏まえて今回は、具体的なクラスタリング手法について解説していきます。

最も似ているもの同士をくっつける「凝集型クラスタリング」

非常にシンプルなクラスタリング方法は、最も似ているもの同士をくっつけていくことです。これは「凝集型クラスタリング」、または「ボトムアップクラスタリング」と呼ばれます。

早速、凝集型クラスタリングを実践してみましょう。今回は、学習するデータとして次の5つの文を用意しました。

  1. メロンパンとジャムパンを食べる。
  2. メロンパンとジャムパンとソーセージパンを買ってきて。
  3. ソーセージパンとクリームパンは美味しい。
  4. 野球もサッカーも好きです。
  5. サッカーはとても楽しいね。


こうしたデータは「学習データ」、または「訓練データ」と呼ばれます。呼び方は違いますが、教師あり学習における「教師データ」と同様、人間があらかじめコンピュータに与えるデータです。

最初は、これらの文は全て別々のクラスタだと考えます。「文1のみから成るクラスタ」「文2のみから成るクラスタ」といった具合に、クラスタが5つ存在する状態を想像してください。

最初は各文は別々のクラスタだと考える

後は、最も似ているクラスタ同士を順番にくっつけて(融合して)いくだけなのですが、何をもって「最も似ている」と言えばよいのでしょうか。

これに関しては、データによってさまざまな定義が考えられます。例えば、データが数値ならば、「クラスタに含まれる2つの数値の差が最も小さいもの」を最も似ていると定義すれば良いでしょう。「最も似ている」の定義は、学習データに応じて適切に決めることが大切です。

今回は「各文に含まれる名詞が一致している数」を「似ている度合い」だと考え、似ている度合いが最大のもの(同じ名詞を含んでいる数が最大のもの)を「最も似ている」と定義することにします。

文1~5はそれぞれ、以下の表で「○」が付いている名詞を含んでいます。

   
メロンパン ジャムパン ソーセージパン クリームパン 野球 サッカー
1
2
3
4
5

文1に着目してください。

まず、文1の文2~5に対する似ている度合いを算出します。似ている度合いは「各文に含まれる名詞が一致している数」ですから、文1と文2の似ている度合いは「2」、文1と文3の似ている度合いは「0」、文1と文4の似ている度合は「0」、文1と文5の似ている度合は「0」と計算できます。

次に文2に着目し、同じように似ている度合いを計算します。文2と文3の似ている度合いは「1」、文2と文4の似ている度合は「0」、文2と文5の似ている度合いは「0」です。

文3以降も同じ要領で、全ての組み合わせで似ている度合いを算出します。すると、最も似ているクラスタは、似ている度合いが「2」である文1のクラスタと文2のクラスタであることがわかります。

そこで、この2つのクラスタを融合します。これで、「文1と文2から成るクラスタ」「文3から成るクラスタ」「文4から成るクラスタ」「文5から成るクラスタ」の4つができました。

最も似ている文1のクラスタと文2のクラスタを融合した

この状態から、また最も似ているものを探していくわけです。

「単連結法」と「完全連結法」

ここで、1つの疑問が生じます。

最初はどれも文を1つだけ含むクラスタだったため、各文に含まれる名詞が一致している数が最大のものを探すことで、最も似ているクラスタを見つけられました。しかし、今は複数の文(文1と文2)が含まれたクラスタが存在します。複数の文が含まれるクラスタと、文を1つしか含まないクラスタ間で、最も似ているクラスタを探すにはどうしたら良いのでしょうか。

この問題を解決する方法はいくつかあるのですが、今回はとてもシンプルな方法を2つ紹介しましょう。いずれの方法をとるにしても、最初の作業は同じです。

文1・2から成るクラスタと文3から成るクラスタが、どのくらい似ているのかを知りたいので、まず、文1と文3、文2と文3をそれぞれ比較します。文1と文3では、一致している名詞は無いので、似ている度合いは「0」です。文2と文3は、一致している名詞が1つあるので、似ている度合いは「1」となります。

もし、文1・2から成るクラスタと文3から成るクラスタの似ている度合いを、文1と文3の似ている度合いのことだと考えるならば「0」、文2と文3の似ている度合いだと考えるならば「1」というわけです。

このとき、最も良い結果を採用するのが1つ目の方法です。すなわち、文1・2から成るクラスタと文3から成るクラスタの似ている度合いは「1」だと考えます。これは、「単連結法」と呼ばれる手法です。

反対に、最も悪い結果を採用するのが2つ目の方法です。こちらは「完全連結法」と呼ばれます。

今回は「単連結法」を使ってクラスタリングしていきましょう。文1・2を含むクラスタと文3の似ている度合いは、単連結法によって「1」だと決まります。文4と5も同様に、似ている度合いは「1」であり、その他の組み合わせの似ている度合いは「0」です。そこで、クラスタは以下のようにまとまります。

単連結法を使ったクラスタリング結果

最後は、文1・2・3から成るクラスタと、文4・5から成るクラスタの比較です。複数の文が含まれるクラスタ同士を比較する場合にも、単連結法や完全連結法などの方法を用います。

引き続き、単連結法を使ってクラスタリングすると、似ている度合いは「0」となります。似ている度合いは「0」ですが、ほかに比較対象が無いため、この2つのクラスタが最も似ているもの同士ということになり、融合されてクラスタリングは終了します。

似ている度合いは「0」だが、ほかに比較対象が無いので最も似ていると見なして融合され、クラスタリングが終わる

このように、凝集型クラスタリングでは最終的には全部くっついてしまうので、適当なところで止める必要があります。あらかじめ、「○個のクラスタが欲しい」という情報をコンピュータに与えておきましょう。

* * *

クラスタリングには、今回紹介した凝集型クラスタリング以外にもさまざまな方法があります。クラスタリングを実施する際の基本的なモチベーションは、「データをクラスタに分けたい」ということです。クラスタリング結果を見て、期待したものと異なる場合は、取得するクラスタ数を変更するか、別のクラスタリング方法を試してみると良いでしょう。

また、同じクラスタリング方法を使っていても、「何をもって最も似ていると判定するのか」「クラスタ同士の比較はどうするのか」などの設定によって、結果は異なります。教師なし学習は決して、「とりあえずデータを放り込めばうまいこと分類してくれる」という方法ではありません。機械学習を用いる場合も、目的に応じた試行錯誤が必要であることは心に留めておきましょう。

著者紹介


国立研究開発法人 情報通信研究機構
ユニバーサルコミュニケーション研究所
データ駆動知能システム研究センター 専門研究員
大西可奈子

2012年お茶の水女子大学大学院博士後期課程修了。 博士(理学)。同年、大手通信会社に入社。2016年より現職。
一貫して自然言語処理、特に対話に関する研究開発に従事。
人工知能(主に対話技術)に関する講演や記事執筆も行う。
twitter:@WHotChocolate