概念クラスタリングとは？COBWEBとカテゴリユーティリティの仕組みを徹底解説

概念クラスタリングとは

概念クラスタリング（Conceptual Clustering）は、機械学習におけるクラスタリング手法の一つで、ラベル付けされていないオブジェクトの集合に対して分類構造を構築するアプローチです。従来のクラスタリングが単に似た性質を持つオブジェクトのグループを識別するにとどまるのに対し、概念クラスタリングはさらに一歩進み、各グループの特徴的な定義を自動的に発見します。このとき、各グループは一つの概念（クラス）として定義されます。

2段階のプロセス：クラスタリングと特徴付け

概念クラスタリングは、まずクラスタリングを実行し、その後に特徴付け（characterization）を行うという2段階のプロセスで構成されます。そのため、クラスタリングの品質は個々のオブジェクト単体ではなく、全体の構造によって評価されます。ほとんどの概念クラスタリング手法は、確率測度を用いた統計的手法を採用しており、これによって概念やクラスタの決定を行います。また、導出された各概念は、一般的に確率的な記述によって表現されます。

代表的な手法「COBWEB」

COBWEBは、増分的（インクリメンタル）な概念クラスタリングを実現する有名かつシンプルなアルゴリズムです。入力となるオブジェクトはカテゴリ型の属性値ペアで定義され、COBWEBは「分類木」と呼ばれる階層的クラスタリング構造を構築します。

分類木と決定木の違い

分類木は決定木とは異なるものです。分類木の各ノードは一つの概念を定義し、そのノード配下に分類されたオブジェクト群を要約する確率的記述を保持します。この確率記述には、概念の出現確率と、P(A_i=v_ij|C_k) という形式の条件付き確率が含まれます。ここで A_i=v_ij は属性値ペア（i番目の属性がj番目に取り得る値を取ること）、C_k は概念クラスを表します。

カテゴリユーティリティ（CU）による木の構築

COBWEBは、「カテゴリユーティリティ（Category Utility: CU）」として知られるヒューリスティックな評価尺度を用いて、木の構築を制御します。CUは次のように定義されます。

$$\frac{\sum_{k=1}^{n}P(C_{k})\left [\sum_{i}\sum_{j}P(A_{i}=v_{ij}|C_{k})^{2}-\sum_{i}\sum_{j}P(A_{i}=v_{ij})^{2}\right ]}{n}$$

ここで n は、木のあるレベルにおける分割 {C₁, C₂, …, C_n} を構成するノード（概念・「カテゴリ」）の数です。言い換えれば、カテゴリユーティリティとは、ある分割情報が与えられたときに完全に推測できる属性値の期待数（項 P(C_k)ΣΣP(A_i=v_ij|C_k)² に相当）が、そのような知識がない場合の正答推測の期待数（項 ΣΣP(A_i=v_ij)² に相当）に対してどれだけ向上するかを示す指標です。導出の詳細は省きますが、カテゴリユーティリティは「クラス内類似性」と「クラス間非類似性」の両方に報酬を与える性質を持っています。

クラス内類似性とクラス間非類似性

クラス内類似性（Intraclass Similarity）
確率 P(A_i=v_ij|C_k) で表されます。この値が高いほど、その属性値ペアを共有するクラスメンバーの割合が高く、クラスのメンバーにとって当該ペアの予測が容易であることを意味します。

クラス間非類似性（Interclass Dissimilarity）
確率 P(C_k|A_i=v_ij) で表されます。この値が高いほど、対照的なクラスにおいて当該属性値ペアを共有するオブジェクトが少なく、そのペアがクラスを強く予測する手がかりになることを意味します。

COBWEBにおける「ベストホスト」の探索

COBWEBは、新規オブジェクトを分類すべき「ベストホスト」（最適なノード）を見つけるため、適切な経路に沿って木を下降しながら、途中でカウント値を更新していきます。この判断は、オブジェクトを各ノードに一時的に配置し、その結果得られる分割についてカテゴリユーティリティを評価することで行われます。そして、最も高いカテゴリユーティリティをもたらす配置こそが、そのオブジェクトにとって最良のホストと判定されます。