マルチリレーショナルクラスタリングとは？CrossClusアルゴリズムの仕組みと課題

マルチリレーショナルクラスタリングとは

マルチリレーショナルクラスタリング（多関係クラスタリング）とは、複数のリレーション（関係）に含まれる情報を活用し、データオブジェクト同士の類似性に基づいてクラスタの集合へと分割する処理のことです。本記事では、この手法を実現するアルゴリズムの一つである CrossClus（ユーザガイダンスを用いたクロスリレーショナルクラスタリング）を紹介します。CrossClusは、クラスタリングにおいてユーザからのガイダンスをどのように活用するか、また物理的な結合（ジョイン）を避けるためにタプルID伝播をどのように利用するかを探求したアルゴリズムです。

主要な課題：膨大な属性の中から関連するものを見つける

マルチリレーショナルクラスタリングにおける大きな課題の一つは、異なるリレーションに属性が多すぎることです。通常、その中で特定のクラスタリングタスクに関連する属性はごく一部に過ぎません。

例：コンピュータサイエンス学科のデータベース

コンピュータサイエンス学科のデータベースを例に考えてみましょう。学生をクラスタリングする場合、属性は「学生が履修した講義」「学生の出版物」「指導教員や所属する研究グループ」など、多岐にわたる情報の側面をカバーします。

ユーザは通常、情報の中のある特定の側面を用いて学生をクラスタリングすることに関心があります（例：研究分野による学生のクラスタリング）。ユーザはアプリケーションの要件やデータの意味論（セマンティクス）をよく把握しているため、そのガイダンスは単純なクエリ構造として表現でき、高次元のマルチリレーショナルクラスタリングの効率と品質の向上に活かすことができます。

ユーザクエリとマルチリレーショナル属性の定義

CrossClusは、ターゲットリレーションと1つ以上の関連属性を含むユーザクエリを受け付けます。これらは合わせて、ユーザのクラスタリングの目標を指定するものです。

CrossClusではマルチリレーショナル属性を定義します。マルチリレーショナル属性 A' は、結合パス R_t ⋈ R₁ … ⋈ R_k、R_k の属性 R_k.A、および（オプションで）集約演算子（平均・カウント・最大値など）によって定義されます。

A' は正式には [A'.join path, A'.attr, A'.aggr] として表現され、A'.aggr は省略可能です。マルチリレーショナル属性 A' は、R_k.A がカテゴリ型か数値型かに応じて、カテゴリ特徴量または数値特徴量のいずれかになります。A' がカテゴリ特徴量である場合、ターゲットタプル t に対する t.A' は、t と結合可能な R_k 内のタプル間における値の分布を表します。

属性探索における2つの大きな課題

マルチリレーショナルクラスタリングの過程で、CrossClusは複数のリレーションにわたって関連属性を検索する必要があります。この検索過程において、CrossClusは次の2つの大きな課題に取り組まなければなりません。

第一に、検索空間が膨大である点です。ターゲットリレーション R_t は通常、多くの異なる結合パスを介して各非ターゲットリレーション R と結合でき、R 内の各属性はマルチリレーショナル属性として使用できます。この巨大な検索空間に対して、あらゆる種類の網羅的探索を実行することは現実的に不可能です。

第二に、関連性の判別が難しい点です。膨大な数の属性の中には、ユーザクエリに関連するもの（例：学生の指導教員はその研究分野と関連する）がある一方で、無関係なものも数多く存在します（例：学生のクラスメートの個人情報など）。