28 O-Cluster

Oracle独自のクラスタリング・アルゴリズムである直行パーティショニング・クラスタリング(O-Cluster)の使用方法を学習します。

• O-Clusterとは
  O-Clusterは、大規模な高次元データセットの分析に適した、高速でスケーラブルなグリッドベースのクラスタリング・アルゴリズムです。このアルゴリズムでは、ユーザー定義のパラメータに依存せずに高品質なクラスタを生成できます。
• O-Clusterアルゴリズムのチューニング
  O-Clusterの作成時設定を構成できます。
• O-Cluster用のデータ準備
  欠損値のビニングおよび処理に自動データ準備(ADP)を使用して、最適なクラスタリング・パフォーマンスを実現します。

関連項目:

『Clustering Large Databases with Numeric and Nominal Values Using Orthogonal Projections』(Campos, M.M.、Milenova, B.L.共著、Oracle Data Mining Technologies, Oracle Corporation)

28.1 O-Clusterとは

O-Clusterは、大規模な高次元データセットの分析に適した、高速でスケーラブルなグリッドベースのクラスタリング・アルゴリズムです。このアルゴリズムでは、ユーザー定義のパラメータに依存せずに高品質なクラスタを生成できます。

O-Clusterの目的は、データ内で高密度の領域を特定し、それらの領域をクラスタに分割することです。それは、軸平行な1次元の(直行の)データ投影を使用して、高密度な領域を特定します。このアルゴリズムでは、重複がなく、サイズのバランスがとれた個別のクラスタに分割するための分割ポイントが検索されます。

O-Clusterは、2分木階層を作成して再帰的に動作します。リーフ・クラスタの数は、自動的に決定されます。アルゴリズムは、クラスタの最大数を制限するように構成できます。

• パーティショニング方針
  O-Clusterでは、ヒストグラムを使用して密度の高い領域が識別されて、適切に分割されたクラスタとサイズのバランスがとられます。
• アクティブなサンプリング
  O-Clusterアルゴリズムは、限られたサイズのデータ・バッファに効果があります。それは、アクティブなサンプリングのメカニズムを使用して、メモリーに収まらないデータセットを処理します。
• プロセス・フロー
  大まかに述べると、O-Clusterアルゴリズムでは、データが評価され、新しいパーティションに分割され、新しいパーティション内の切断面が検索されます。
• スコアリング
  O-Clusterでは、検出されたクラスタに基づいて、新しいデータをスコアリングするためのベイズ確率モデルが生成されます。

28.1.1 パーティショニング方針

O-Clusterでは、ヒストグラムを使用して密度の高い領域が識別されて、適切に分割されたクラスタとサイズのバランスがとられます。

パーティショニング方針とは、属性ヒストグラムの密度領域を検出するプロセスのことです。プロセスは、量的データと質的データで異なります。両方のデータが存在する場合、アルゴリズムでは、別々に検索が実行されてからその結果が比較されます。

パーティションの選択では、アルゴリズムによって、2つの目的(適切に分割されたクラスタを検出することと、サイズがバランスするクラスタを作成すること)が調整されます。次の項では、量的属性および質的属性のパーティションの識別方法について詳細に説明します。

• 量的属性のパーティショニング
  最も有効な切断面を見つけるため、O-Clusterでは、高密度(ピーク)のビンの間にある低密度(谷)のビンに対応する属性ヒストグラムが検索されます。
• 質的属性のパーティショニング
  質的な値には、固有の順序が関連付けられていません。そのため、量的な値のパーティショニングに使用されるヒストグラムのピークと谷の概念を適用することはできません。かわりに、個々の値の数でヒストグラムを構成します。

28.1.1.1 量的属性のパーティショニング

最も有効な切断面を見つけるため、O-Clusterでは、高密度(ピーク)のビンの間にある低密度(谷)のビンに対応する属性ヒストグラムを検索します。

O-Clusterは、ピークと谷の間のヒストグラム数の差が統計的に有意である、谷を挟んだ1組のピークの検出を試みます。

sensitivityレベルのパラメータは、ピークとみなされる可能性のある最小の密度を指定します。sensitivityは、数値データ用のオプションのパラメータです。それは、候補となる分割ポイントをフィルタ処理するために使用できます。

28.1.1.2 質的属性のパーティショニング

質的な値には、固有の順序が関連付けられていません。そのため、量的な値のパーティショニングに使用されるヒストグラムのピークと谷の概念を適用することはできません。かわりに、個々の値の数でヒストグラムを構成します。

個数の多いビンは、高密度の領域として解釈されます。クラスタリングの目的は、これらの高密度領域を分割して、データのエントロピ(ランダム性)を効果的に低減することです。

O-Clusterは、個々の投影に従って最高度のエントロピを持つヒストグラムを識別します。エントロピは、sensitivityレベルを超えるビンの数として測定されます。O-Clusterは、個別のパーティションに最も大きい2つのビンを配置することで、分岐条件を作成します。ビンの残りは、結果となる2つのパーティションにランダムに割り当てられます。

28.1.2 アクティブなサンプリング

O-Clusterアルゴリズムは、制限されたサイズのデータ・バッファで動作します。それは、アクティブなサンプリングのメカニズムを使用して、メモリーに収まらないデータセットを処理します。

初期ランダム・サンプルを処理した後、O-Clusterは、これ以上必要としないケースを識別します。このようなケースは、今後分割する可能性が非常に低い凍結パーティションに属します。これらのケースは、適切な分割面を検出してパーティショニングを継続するためにより多くの情報(追加のケース)が必要とされる不明瞭領域の例に置換されます。パーティションは、有効な分割がより低い信頼度レベルでのみ検出される場合、不明瞭とみなされます。

凍結パーティションに関連付けられたケースは、バッファから削除するものとしてマークされます。これらは、不明瞭パーティションに属するケースに置換されます。不明瞭パーティションのヒストグラムは更新され、分割ポイントは再評価されます。

28.1.3 プロセス・フロー

大まかに述べると、O-Clusterアルゴリズムは、データを評価し、新しいパーティションに分割し、新しいパーティション内の切断面を検索します。

O-Clusterアルゴリズムでは、パーティションのすべての投影に対して適用可能な分割ポイントを評価し、最適なものを選択して、データを2つの新しいパーティションに分割します。アルゴリズムは、新しく作成されたパーティション内で適切な切断面の検索を続行します。つまり、O-Clusterは、入力空間を重複や間隙のない矩形領域に分割する2分木構造を作成します。

主な処理段階は次のとおりです。

1. バッファをロードします。初期バッファから単一のアクティブ・ルート・パーティションにすべてのケースを割り当てます。

2. アクティブ・パーティションごとに、直交する1次元の投影に従ってヒストグラムを計算します。

3. アクティブ・パーティションの最適な分割ポイントを見つけます。

4. 不明瞭パーティションと凍結パーティションをフラグ付けします。

5. 有効なセパレータが存在する場合、アクティブ・パーティションを2つの新しいアクティブ・パーティションに分割してステップ2から再度開始します。

6. 現在のバッファで再帰的パーティショニングがすべて完了した後に、バッファを再ロードします。バッファのロードは、バッファが再度一杯になるか、データセットの最後に到達するか、ケースの数がデータ・バッファのサイズに等しくなるまで継続されます。

   ノート:

   O-Clusterでは、データ全体に1つ以下のパスが必要です。

28.1.4 スコアリング

O-Clusterでは、検出されたクラスタに基づいて、新しいデータをスコアリングするためのベイズ確率モデルが生成されます。

生成される確率モデルは混合モデルで、混合要素は、量的属性の独立正規分布と質的属性の多項分布の積によって表されます。

28.2 O-Clusterアルゴリズムのチューニング

O-Clusterの作成時設定を構成できます。

O-Clusterアルゴリズムでは、2つの作成時設定がサポートされます。どちらの設定にもデフォルト値があります。特定の方法でアルゴリズムの動作に影響を与える場合を除き、デフォルトを上書きする必要はありません。

次の内容を指定してO-Clusterを構成できます。

感度係数 — 新しいクラスタを分割するために必要なピーク密度を指定する割合。

関連項目:

使用可能なモデル設定のリストおよび説明は、DBMS_DATA_MINING - アルゴリズムの設定: O-Clusterを参照してください。

ノート:

モデル設定と同じ意味でハイパーパラメータという用語も使用されます。

28.3 O-Cluster用のデータ準備

欠損値のビニングおよび処理に自動データ準備(ADP)を使用して、最適なクラスタリング・パフォーマンスを実現します。

O-Clusterの場合は、ADPでは量的属性のビニングが実行されます。特殊な等幅ビニングを使用して、属性ごとのビンの数が自動的に計算されます。すべてNULLまたは単一の値を持つ数値列は除外されます。O-Clusterでは、欠損値をそのまま(ランダムに欠損している値として)処理します。

ノート:

O-Clusterでは、ネストした列、スパース・データまたは非構造化テキストはサポートされません。

• O-Cluster用のユーザー定義のデータ準備
  等幅ビニングを考慮し外れ値を管理することで、O-Cluster用にデータを準備できます。

28.3.1 O-Cluster用のユーザー定義のデータ準備

等幅ビニングを考慮し外れ値を管理することで、O-Cluster用にデータを準備できます。

O-Cluster用のデータをユーザー自身が準備する場合は、次の内容に留意してください。

• O-Clusterでは、モデルを作成する際、必ずしもすべての入力データを使用するわけではありません。データはバッチで読み込みます(デフォルトのバッチ・サイズは50,000)。統計テストに基づいて、見つかっていないクラスタが存在できると考えられる場合にのみ、別のバッチを読み込みます。

• 2項属性は、質的属性として宣言する必要があります。

• 自動等幅ビニングの使用をお薦めします。ビン識別子は、通常、1から始まる正の連続する整数にします。

• 外れ値が存在すると、クラスタリング・アルゴリズムに大きな影響を与える可能性があります。ビニングまたは正規化を行う前に、クリッピング変換を実行してください。等幅ビニングで外れ値が存在すると、O-Clusterでクラスタを検出できなくなる場合があります。その結果、母集団全体が1つのクラスタ内に含まれているように見えます。