| Oracle Data Mining概要 11g リリース2(11.2) E48231-01 |
|
 前 |
 次 |
この章では、Oracle独自のクラスタリング・アルゴリズムである直行パーティショニング・クラスタリング(O-Cluster)について説明します。
|
参考: 『Clustering Large Databases with Numeric and Nominal Values Using Orthogonal Projections』(Campos, M.M.、Milenova, B.L.共著、Oracle Data Mining Technologies, Oracle Corporation) |
この章には、次の項が含まれます。
O-Clusterは、大規模な高次元データセットのマイニングに適した、高速でスケーラブルなグリッドベースのクラスタリング・アルゴリズムです。このアルゴリズムでは、ユーザー定義のパラメータに依存せずに高品質なクラスタを生成できます。
O-Clusterの目的は、データ中の高密度領域を識別し、密度の高い領域をクラスタに分割することです。軸平行な1次元(直交)のデータ投影を使用して、密度の高い領域を識別します。アルゴリズムでは分割ポイントが検索され、重複しておらずサイズがバランスする個別クラスタになります。
O-Clusterは、2分木階層を作成して再帰的に動作します。リーフ・クラスタの数は、自動的に決定されます。アルゴリズムは、クラスタの最大数を制限するように構成できます。
パーティショニング方針とは、属性ヒストグラムの密度領域を検出するプロセスのことです。プロセスは、量的データと質的データで異なります。両方のデータが存在する場合、アルゴリズムでは、別々に検索が実行されてからその結果が比較されます。
パーティションの選択では、アルゴリズムによって、2つの目的(適切に分割されたクラスタを検出することと、サイズがバランスするクラスタを作成すること)が調整されます。次の項では、量的属性および質的属性のパーティションの識別方法について詳細に説明します。
最も有効な切断面を見つけるため、O-Clusterでは、高密度(ピーク)のビンの間にある低密度(谷)のビンに対応する属性ヒストグラムを検索します。O-Clusterは、ピークと谷の間のヒストグラム数の差が統計的に有意である、谷を挟んだ1組のピークの検出を試みます。
sensitivityレベル・パラメータで、ピークとみなされる最も低い密度を指定します。sensitivityは、数値データのオプションのパラメータです。分割ポイントの候補のフィルタにも使用できます。
質的な値には、固有の順序が関連付けられていません。そのため、量的な値のパーティショニングに使用されるヒストグラムのピークと谷の概念を適用することはできません。
かわりに、個々の値の数でヒストグラムを構成します。個数の多いビンは、高密度の領域として解釈されます。クラスタリングの目的は、これらの高密度領域を分割して、データのエントロピ(ランダム性)を効果的に低減することです。
O-Clusterは、個々の投影に従って最高度のエントロピを持つヒストグラムを識別します。エントロピは、sensitivityレベルを超えるビンの数として測定されます。O-Clusterは、個別のパーティションに最も大きい2つのビンを配置することで、分岐条件を作成します。ビンの残りは、結果となる2つのパーティションにランダムに割り当てられます。
O-Clusterアルゴリズムは、サイズが制限されているデータ・バッファで操作します。アクティブなサンプリング・メカニズムを使用して、メモリに収まらないデータセットを処理します。
初期ランダム・サンプルを処理した後、O-Clusterは、これ以上必要としないケースを識別します。このようなケースは、今後分割する可能性が非常に低い凍結パーティションに属します。これらのケースは、適切な分割面を検出してパーティショニングを継続するためにより多くの情報(追加のケース)が必要とされる不明瞭領域の例に置換されます。パーティションは、有効な分割がより低い信頼度レベルでのみ検出される場合、不明瞭とみなされます。
凍結パーティションに関連付けられたケースは、バッファから削除するものとしてマークされます。これらは、不明瞭パーティションに属するケースに置換されます。不明瞭パーティションのヒストグラムは更新され、分割ポイントは再評価されます。
O-Clusterアルゴリズムでは、パーティションのすべての投影に対して適用可能な分割ポイントを評価し、最適なものを選択して、データを2つの新しいパーティションに分割します。アルゴリズムは、新しく作成されたパーティション内で適切な切断面の検索を続行します。つまり、O-Clusterは、入力空間を重複や間隙のない矩形領域に分割する2分木構造を作成します。
主な処理段階は次のとおりです。
バッファをロードします。初期バッファから単一のアクティブ・ルート・パーティションにすべてのケースを割り当てます。
アクティブ・パーティションごとに、直交する1次元の投影に従ってヒストグラムを計算します。
アクティブ・パーティションの最適な分割ポイントを見つけます。
不明瞭パーティションと凍結パーティションをフラグ付けします。
有効なセパレータが存在する場合、アクティブ・パーティションを2つの新しいアクティブ・パーティションに分割して手順2から再度開始します。
現在のバッファで再帰的パーティショニングがすべて完了した後に、バッファを再ロードします。バッファのロードは、バッファが再度一杯になるか、データセットの最後に到達するか、ケースの数がデータ・バッファのサイズに等しくなるまで継続されます。
|
注意: O-Clusterでは、データ全体に1つ以下のパスが必要です。 |
O-Clusterアルゴリズムでは、2つの作成時設定がサポートされます。どちらの設定にもデフォルト値があります。特定の方法でアルゴリズムの動作に影響を与える場合を除き、デフォルトを上書きする必要はありません。
次のいずれかを指定してO-Clusterを構成できます。
バッファ・サイズ - 処理バッファのサイズ。(「アクティブなサンプリング」を参照。)
感度係数 - 新しいクラスタを分割するために必要なピーク密度を指定する割合。(「パーティショニング方針」を参照。)
|
関連項目: O-Cluster構築設定の詳細は、『Oracle Database PL/SQLパッケージおよびタイプ・リファレンス』を参照してください。 |
O-Clusterに対する自動データ準備では、量的属性のビニングが実行されます。特殊な等幅ビニングを使用して、属性ごとのビンの数が自動的に計算されます。すべてNULLまたは単一の値を持つ数値列は除外されます。
O-Clusterでは、欠損値をそのまま(ランダムに欠損している値として)処理します。アルゴリズムでは、ネストした列はサポートされていないため、スパース・データもサポートされていません。
O-Cluster用のデータをユーザー自身が準備する場合は、次の内容に留意してください。
O-Clusterでは、モデルを作成する際、必ずしもすべての入力データを使用するわけではありません。O-Clusterは、データをバッチで読み込みます(デフォルトのバッチ・サイズは50,000)。統計テストに基づいて、まだ見つかっていないクラスタが存在すると考えられる場合にのみ、別のバッチを読み込みます。
2項属性は、質的属性として宣言する必要があります。
自動等幅ビニングの使用をお薦めします。ビン識別子は、通常、1から始まる正の連続する整数にします。例については、『Oracle Database PL/SQLパッケージおよびタイプ・リファレンス』を参照してください。
外れ値が存在すると、クラスタリング・アルゴリズムに大きな影響を与える可能性があります。ビニングまたは正規化を行う前に、クリッピング変換を実行してください。等幅ビニングで外れ値が存在すると、O-Clusterでクラスタを検出できなくなる場合があります。その結果、母集団全体が1つのクラスタ内に含まれているように見えます。
