13 期待値最大化
関連項目
13.1 期待値最大化とは
混合モデルの期待値最大化(EM)推定は、様々なアプリケーションで使用される一般的な確率密度推定の技術です。Oracle Data Miningでは、EMを使用して分布ベースのクラスタリング・アルゴリズム(EMクラスタリング)を実装します。
13.1.1 期待値ステップと最大化ステップ
期待値最大化は、反復的な方法です。それは、初期パラメータの不確定要素で始まります。パラメータ値を使用して、現在のモデルの可能性が計算されます。これは、期待値ステップです。次にパラメータ値は、可能性を最大化するよう再計算されます。これは、最大化ステップです。新しいパラメータ推定値を使用して新しい期待値が計算され、推定値は、可能性を最大化するように再び最適化されます。この反復プロセスは、モデルが収束するまで続きます。
13.2 アルゴリズムの拡張
期待値最大化(EM)は、分布ベースのクラスタリング・アルゴリズムとして確立されていますが、その標準形式では多少扱いづらいところがあります。Oracle Data Miningの実装には、大容量データのスケーラブルな処理や自動パラメータ初期化などの重要な拡張が含まれます。Oracle Data MiningがEMクラスタリングに固有の制限事項に対処するために使用する方針については、この項の後の部分を参照してください。
ノート:
EMの略称は、ここではEMクラスタリングを示すために使用しています。標準の期待値最大化の制限事項:
-
スケーラビリティ: EMには、レコードと属性の数に応じた線形のスケーラビリティがあります。収束に至るまでの反復回数は、増大するデータ・サイズ(行と列の両方)に伴って増加する傾向があります。EMの収束は、複雑な問題に対応する場合は速度が低下し、計算リソースに相当な負荷をかける可能性があります。
-
高いディメンション性: EMにおける高次元(ワイド)データのモデリング用の容量には制限があります。多くの属性の存在がモデルの収束速度を低下させ、アルゴリズムが意味のある属性とノイズを区別する能力も低下します。そのため、アルゴリズムによる相関検出能力は弱まります。
-
成分数: EMでは、通常、ユーザーが成分数を指定する必要があります。ほとんどの場合、これは、ユーザーが前もって知ることができる情報ではありません。
-
パラメータ初期化: 適切な初期パラメータ値の選択が、モデルの品質に重大な影響を与えることがあります。EMに使用されている初期化の方針は、一般的に、計算上高い負荷を伴います。
-
成分からクラスタへ: EMモデルの成分は、通常、クラスタとして扱われます。密集性の高いクラスタは、通常、複数の成分によってモデル化されるため、このアプローチには問題があります。複雑な形状を持つクラスタは、複数の成分によってモデル化される必要があります。
13.2.1 スケーラビリティ
Oracle Data Miningの期待値最大化(EM)は、データベースのパラレル処理を利用して優れたスケーラビリティを実現します。
期待値最大化(EM)のOracle Data Miningによる実装では、データベースのパラレル処理を使用して高度なスケーラビリティを実現します。EMの計算は、基本的に、行のパラレル処理に役立つもので、部分的な結果は容易に集計されます。パラレル実装によって、計算集中型の作業がスレーブ・プロセス全体に効率的に分散され、部分的な結果が結合されて最終的な解決策が生成されます。
13.2.2 高いディメンション性
期待値最大化(EM)のOracle Data Miningによる実装では、数千の属性を持つ高次元データを効率的に処理できます。これは、次の2段階のプロセスを通じて実行されます。
-
単一列(ネストなし)属性のデータ空間が、ペアワイズ相関用に分析されます。他の属性と重大な相関性のある属性のみが、EM混合モデルに含まれます。アルゴリズムは、M個の最も相関性のある属性にディメンション性を制限するように構成することも可能です。
-
同様のタイプのイベントを測定する高次元の(ネストした)量的データは、EMによってモデル化された低次元の特徴セットに投影されます。高次元の量的データの例として、テキスト、推奨事項、遺伝子発現、マーケット・バスケット・データなどがあります。
13.2.3 成分数
期待値最大化(EM)の典型的な実装では、ユーザーは、モデルの成分数を指定する必要があります。ユーザーは一般的に正しい成分数を知らないため、これには問題があります。選択する成分が多すぎたり少なすぎたりすると、それぞれオーバーフィットやアンダーフィットが発生する可能性があります。
モデル検索を有効にすると、EMの成分数は自動的に決定されます。アルゴリズムでは、保持サンプルを使用して正しい成分数を決定しますが、ベイズ情報量規準(BIC)の正則化が使用されている場合の非常に小規模なデータセットについては除外します。
13.2.4 パラメータ初期化
適切な初期パラメータ値の選択が、解決策の品質に重大な影響を与えることがあります。期待値最大化(EM)は、尤度関数の全体的な最大値に収束することは保証されませんが、かわりに局所的な最大値に収束する可能性があります。そのため、異なる初期パラメータ値によって、異なるモデル・パラメータおよび異なるモデル品質が導かれることがあります。
モデル検索の過程において、EMモデルは独自に拡大します。新しい成分が追加されると、それらのパラメータは、分布適用が少ない領域に初期化されます。
13.2.5 成分からクラスタへ
期待値最大化(EM)モデルの成分は、通常、クラスタとして扱われます。ただし、このアプローチでは問題が発生する可能性があります。密集性の高いクラスタは、通常、複数の成分によってモデル化されます。EMで使用される確率密度関数の形状によって、識別されたクラスタの形状が効率的に前もって決定されます。たとえば、ガウス密度関数では、単一ピークの対称クラスタを識別できます。より複雑な形状のクラスタは、複数の成分によってモデル化される必要があります。
任意の形状の高密度領域は、単一クラスタとして解釈される必要があります。これを実現するため、Oracle Data MiningによるEM実装では、個々の成分の分布の重複に基づいた成分階層を構築します。Oracle Data MiningのEMでは、凝集型階層クラスタリングを使用します。成分分布の重複は、バタチャリア距離関数を使用して測定されます。階層内の適切なカットオフ・レベルを選択すると、高レベル・クラスタの数が自動的に決定されます。
Oracle Data MiningによるEM実装では、モデル成分の高レベル・クラスタへの割当てが生成されます。平均、分散、最頻値、ヒストグラムおよびルールなどの統計では、追加で高レベル・クラスタを説明します。アルゴリズムは、クラスタリング割当てを成分レベルで生成するか、クラスタ・レベルで生成するように構成できます。
13.3 アルゴリズムの構成
期待値最大化(EM)を構成します。
Oracle Data Miningでは、期待値最大化(EM)によって、ユーザーが初期化パラメータを指定したり、モデルの成分数を指定することなく、非常に大規模なデータセット(行と列の両方)を効果的にモデル化できます。アルゴリズムによって合理的なデフォルトが提供されますが、同時に柔軟性も得ることができます。
次のリストで、EMの構成可能ないくつかの要素について説明します。
-
ネストしていない列の独立属性をモデルに含めるかどうか。この選択は、デフォルトでシステムによって決定されます。
-
量的属性にベルヌーイ分布またはガウス分布のどちらを使用するか。デフォルトでは、アルゴリズムによって最も適切な分布が選択されますが、個々の属性では異なる分布を使用できます。分布は、ユーザーによって指定されると、すべての量的属性に使用されます。
-
収束基準を保持データセットまたはベイズ情報量規準(BIC)のどちらに基づかせるか。収束基準は、デフォルトでシステムによって決定されます。
-
新しい成分をモデルに追加するために必要な対数尤度関数の値における割合の改善。デフォルトの割合は0.001です。
-
クラスタを個別の成分として定義するか、成分のグループとして定義するか。クラスタは、デフォルトで成分のグループに関連付けられます。
-
モデルの成分の最大数。モデル検索が有効である場合、アルゴリズムによって、尤度関数の改良または正則化(BIC)に基づいて成分の数が(指定した最大値を限度に)決定されます。
-
凝集型クラスタリング・ステップ用の結合関数で、枝内の最近隣距離(単一結合)、枝内の平均距離(平均結合)、または枝内の最大距離(完全結合)のどれを使用するか。デフォルトでは、アルゴリズムによって単一結合が使用されます。
13.4 期待値最大化用のデータ準備
期待値最大化(EM)のデータを準備する方法を学習します。
自動データ準備(ADP)を使用する場合、期待値最大化用の追加のデータ準備を指定する必要はありません。ネストしていない列の量的属性は、ガウス分布でモデル化される場合、ADPによって正規化されます。ADPは、上位Nのビニング変換を質的属性に適用します。
欠損値の処理は、Oracle Data Miningのアルゴリズムによって自動的に行われるため、必要ありません。期待値最大化アルゴリズムによって、欠損値は、ガウス分布でモデル化される単一列の量的属性の平均値に置換されます。他の単一列の属性(ベルヌーイ分布でモデル化される質的属性および量的属性)では、NULLは、独自の頻度数を持つ個別値として扱われるため、置換されません。ネストした列では、欠損値は0 (ゼロ)として扱われます。