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

マルチリレーショナルクラスタリング（多関係クラスタリング）とは、複数のリレーションに格納されたデータを活用し、データオブジェクト同士の類似性に基づいてクラスタへ分割する手法です。

CrossClusは「ユーザガイダンス付きクロスリレーショナルクラスタリング」を意味します。これは、ユーザからの指示をクラスタリングにどう活用するかを分析するとともに、物理的な結合（ジョイン）を回避するためのタプルID伝播という技術を用いる、マルチリレーショナルクラスタリングのアルゴリズムです。

マルチリレーショナルクラスタリングの主な課題

マルチリレーショナルクラスタリングにおける最大の課題は、複数のリレーションに多数の属性が存在する一方で、特定のクラスタリングタスクに関連する属性はごく一部にすぎないという点です。

例えば学生をクラスタリングする場合、属性には履修科目、論文発表歴、指導教員、所属する研究チームなど、さまざまな情報要素が含まれます。しかし、そのすべてが目的の分類に役立つわけではありません。

ユーザガイダンスの重要性

ユーザは通常、特定のデータ要素を使って学生をクラスタリングすることに関心を持っています（例：研究分野別に学生を分類するなど）。アプリケーションの要件やデータの意味論を最もよく理解しているのはユーザ自身であるため、簡単なクエリという形でのユーザの指示を取り入れることで、高次元マルチリレーショナルクラスタリングの有効性と品質を大幅に向上させることができます。

CrossClusは、ターゲットリレーションと1つ以上の関連属性を含むユーザクエリを受け付けます。これらの属性によって、ユーザのクラスタリングの目的が明確に定義されます。マルチリレーショナルクラスタリングの処理過程では、CrossClusは複数のリレーションにまたがって関連属性を探索する必要があります。

CrossClusによる関連属性の探索

探索フェーズの2つの課題

探索フェーズにおいて、CrossClusは次の2つの大きな課題に対処しなければなりません。

第一に、ターゲットリレーション R_t は一般に、複数の結合パスを通じて各非ターゲットリレーション R と結合できるため、R 内の各属性がマルチリレーショナル属性として使用可能になります。このように広大な探索空間では、全数探索（網羅的な検索）を実行することは現実的ではありません。

第二に、大量の属性の中には、ユーザクエリに関連するものと無関係なもの（例：学生の同級生の個人情報など）が混在しており、適切にふるい分ける必要があります。

ヒューリスティックな探索手法

そこでCrossClusは探索範囲を限定します。具体的には、リレーショナルスキーマをグラフとして捉え、関連付けをノード、結合をエッジとして扱います。そして、ユーザ定義属性から探索を開始し、現在の属性の近傍にある有益な属性を繰り返し探索していくヒューリスティック手法を採用しています。

このアプローチにより、接続されたリレーションへと徐々に探索範囲を広げながらも、無関係な方向へ深入りすることを防ぎます。

属性間の類似性評価

CrossClusは、各属性がターゲットタプルをどのようにクラスタリングするかに着目します。関連属性は、ユーザ定義属性との関係性に基づいて選択されます。

2つの属性がタプルをまったく異なる方法でクラスタリングする場合、それらの類似度は低く、関連している可能性は低いと判断されます。逆に、同じようにタプルをクラスタリングする場合は、両者に関連性があるとみなされます。この評価基準により、CrossClusはユーザの意図に沿った高精度なクラスタリングを実現します。