半教師ありクラスタリングとは？仕組みと代表的な手法を解説

半教師ありクラスタリングの概要

半教師ありクラスタリング（Semi-supervised Clustering）とは、ドメイン知識（事前知識）を活用しながらラベルなしデータを分割する手法です。事前知識は、一般的にインスタンス間のペアワイズ制約として、あるいは少数のラベル付きインスタンスの集合という形で表現されます。

教師情報によるクラスタリング品質の向上

通常の教師なしクラスタリングでも、わずかな教師情報（弱い監督構造）を加えるだけで、その精度を大幅に改善できます。代表例としては、「2つのオブジェクトが同じクラスタに属する／異なるクラスタに属する」という形でラベル付けされたペアワイズ制約が挙げられます。このように、ユーザーからのフィードバックやガイダンスとなる制約に基づいて動作するクラスタリング手法を、半教師ありクラスタリングと呼びます。

半教師ありクラスタリングの2つの主要アプローチ

半教師ありクラスタリングには複数の手法が存在しますが、大きく以下の2種類に分類できます。

1. 制約ベースの半教師ありクラスタリング

ユーザーが提供したラベルや制約を活用し、アルゴリズムをより適切なデータ分割へと導く手法です。具体的には、制約に応じて目的関数を修正する方法や、ラベル付きオブジェクトを用いてクラスタリング処理を初期化・制御する方法などが含まれます。

2. 距離ベースの半教師ありクラスタリング

教師データ内のラベルや制約を満たすように学習された「適応的距離尺度」を用いる手法です。これまでに、EM（Expectation-Maximization）アルゴリズムによって学習される文字列編集距離や、最短距離アルゴリズムによって調整されるユークリッド距離など、さまざまな適応的距離尺度が利用されています。

CLTree：決定木を用いた半教師ありクラスタリング

CLTree（CLustering based on decision TREEs）は、教師なしクラスタリングと教師あり分類の考え方を統合した興味深い手法であり、制約ベースの半教師ありクラスタリングの一例です。

CLTreeでは、クラスタリング対象の点集合を「Y」というラベルを持つ1つのクラスとみなし、そこへ比較的一様に分布した「非存在点（nonexistence points）」を別のクラスラベル「N」として仮想的に追加します。これにより、データ領域をデータ密度の高い領域（密な領域）と空き領域（疎な領域）に分割する問題が、分類問題へと変換されます。

元のクラスタリング問題は、「Y」と「N」を区別するモデルを求める分類問題として捉えられます。決定木の帰納的手法を用いて空間を分割することで、「Y」の点のみから構成される領域、すなわちクラスタを特定できます。

CLTreeの課題

一方で、この手法にはいくつかの課題があります。まず、大量の「N」点を元データに追加すると、計算上の不要なオーバーヘッドが発生する可能性があります。また、非常に高次元の空間では、点を一様に分布させるために指数的な数の点が必要となるため、追加された点が実際には一様に分布しているとは言えない場合があります。