一般的に、より具体的には、ベルヌーイ混合モデル (別名、潜在クラス分析) の場合です。
質問する
8749 次
3 に答える
8
EM は、k-means のロイズ変種とほとんど同じです。したがって、各反復にはO(n*k)距離計算が必要です。それらはより複雑な距離計算ですが、最終的にはマハラノビス距離の変形です。
ただし、k-means には非常に優れた終了動作があります。可能なクラスター割り当ては k^n のみです。各ステップでより良いものを選択した場合、すべての k^n を試した後、最新のものを終了する必要があります。しかし、実際には、通常、多くても数十ステップで終了します。
EM の場合、これは簡単ではありません。オブジェクトは単一のクラスターに割り当てられませんが、fuzzy-c-means のように、すべてのクラスターに相対的に割り当てられます。そして、それはあなたがこの終了保証を失うときです.
したがって、停止しきい値がなければ、EM はクラスター割り当てを無限の精度まで無限に最適化します (無限の精度で実装すると仮定します)。
したがって、EM の理論上の実行時間は無限です。
任意のしきい値 (およびそれがハードウェアの浮動小数点精度の場合) は、より早く終了します。O(n*k*i)ただし、ここで反復回数とは異なる理論上の制限を取得するのは困難ですi(無限の可能性がありますが0、単一の反復を実行したくない場合は設定することもできます)。
于 2012-12-30T12:51:32.983 に答える
0
EMアルゴリズムは本質的に反復的であるため、終了基準を決定する必要があります。ステップ数の上限を修正すると、実行時の分析は明らかに簡単になります。他の終了基準（一定の差までの収束など）については、状況を具体的に分析する必要があります。
簡単に言うと、「EM」の説明には終了基準が含まれていないため、質問にそのように答えることはできません。
于 2012-12-27T13:49:55.223 に答える
0
これは私が思うことです: をEM algorithm使用すると仮定するとlinear algebra、その複雑さはO(mn^3)になるはずです。ここで、m は反復回数、n はパラメーターの数です。
反復回数は、開始値の品質に影響されます。開始値が良いということは、m が小さいことを意味します。
開始値があまり良くないということは、m が大きくなったり、局所解への収束が原因で失敗したりすることを意味します。である尤度関数に EM が使用されているため、局所的な解が存在する可能性がありますnonlinear。
適切な開始値とは、グローバル最適解の軌跡を囲む引力の凸状ゾーンから開始することを意味します。
于 2016-11-08T07:19:36.963 に答える