アソシエーションルールクラスタリングシステム（ARCS）に含まれる手順とは？

アソシエーションルールクラスタリングシステム（ARCS）には、主に「ビニング」と「頻出述語集合の発見」という2つの重要なステップが含まれます。以下、それぞれの手順について詳しく解説します。

1. ビニング（Binning）

量的属性は、その定義域を表す非常に広い範囲の値を持ちます。例えば、「年齢」と「収入」を軸として2次元グリッドを描くことを考えてみましょう。年齢の取り得るすべての値が一方の軸上の特定の位置に対応し、同様に収入のすべての値がもう一方の軸上の位置に対応すると、グリッドは膨大なサイズになってしまいます。

そこで、グリッドを管理可能なサイズに抑えるために、量的属性の範囲をいくつかの区間に分割します。これらの区間は、マイニング段階で組み合わせることができるため強力です。この分割段階は「ビニング」と呼ばれ、各区間は「ビン（bin）」として扱われます。

3つの一般的なビニング戦略

• 等幅ビニング（Equal-width binning）：各ビンの区間幅が同一となる方法です。
• 等頻度ビニング（Equal-frequency binning）：各ビンにほぼ同じ数のタプルが割り当てられる方法です。
• クラスタリングベースのビニング（Clustering-based binning）：量的属性に対してクラスタリングを実行し、さまざまな距離尺度に基づいて近傍の点を同じビンにグループ化する方法です。

ARCSでは等幅ビニングが用いられ、各量的属性のビンサイズはユーザーが入力します。そして、両方の量的属性を含むすべての可能なビンの組み合わせに対して、2次元配列が生成されます。

各配列セルには、ルールの右辺にあるカテゴリ属性の各クラスに対応するカウント分布が格納されます。このデータ構造を作成することで、タスクに関連するデータのスキャンは一度だけで済みます。さらに、同じ2次元配列を使い回すことで、同じ2つの量的属性に基づくカテゴリ属性の任意の値に対するルールを生成することも可能です。

2. 頻出述語集合の発見（Finding frequent predicate sets）

各カテゴリのカウント分布を含む2次元配列が構築されると、それをスキャンして、最小支持度を満たし、かつ最小信頼度も満たす頻出述語集合を発見できます。

アルゴリズムはグリッドを調べ、長方形のルールクラスタを探索します。この手法では、ルールクラスタ内に出現する量的属性のビンを組み合わせることができるため、量的属性の動的な離散化が実現されます。

このグリッドベースの手法により、元のアソシエーションルールを長方形の領域にクラスタリングできることが示されています。クラスタリングを実行する前に、平滑化手法を用いてレコードからノイズや外れ値を除去することもできます。ただし、長方形クラスタは情報を過度に単純化してしまう可能性がある点には注意が必要です。

より汎用的な非グリッドベースのアプローチ

より汎用的な量的アソシエーションルールを発見するための非グリッドベースのアプローチも提案されています。このアプローチでは、複数の量的属性およびカテゴリ属性がルールのどちら側にも現れることが許容されます。

この手法では、量的属性は等頻度ビニングによって動的に分割され、分割によって失われるデータ量を定量化する「部分完全性（partial completeness）」の尺度に基づいて、パーティションが結合されます。