k個の均質な部分でシーケンスを分割する方法は？

Question

私はシーケンスをk個の部分に分割し、これらの部分の均質性を最適化したいと思います。ここで

Example : 0 0 0 0 0 1 1 2 3 3 3 2 2 3 2 1 0 0 0 
Result : 0 0 0 0 0 | 1 1 2 | 3 3 3 2 2 3 2 | 1 0 0 0 when you ask for 4 parts (k = 4) 

、アルゴリズムは、固定長の部分に分割しようとするが、代わりに同じ部分の要素ができるだけ均一であることを確認してみましたしませんでした。

どのアルゴリズムを使用しますか？ Rの実装はありますか？

Answer 1

おそらくExpectation-maximization algorithmを使用できます。あなたのポイントは(value, position)です。 EMアルゴリズムで

、結果は（手で）ようなものになるだろう：あなたの例では、これは何かのようになります

この所望の出力があり、これを使用することを検討し、すべてのシナリオで実際に機能するかどうかを検討することができます。注釈は、必要なクラスタ数を事前に割り当てる必要がありますが、質問を設定しているので、問題はないと思います。

が、これは働いていた場合、私に教えてください;）

編集：

この絵を参照してください、あなたはについて語ったものです。 k-meansを使用すると、delta valueを制御する必要があります。これは、ポジションのインクリメントによって、その値は値と同じスケールになります。しかし、E-Mではこれは問題ではありません。

編集2：

[OK]を私はあなたがdelta valueを制御する必要が、正しくありませんでした。あなたが言ったように、このアルゴリズムは、その位置であれば隣人でないポイントをクラスタ化することを決定することができ、

したがって（2つのクラスタ）：あなたが1または3で位置をインクリメントする場合、それは同じではありませんはるかに近いものの、その価値は近いです。 deltaの高いインクリメントでこれが起こらないことを保証する必要があります。私はあなたのシーケンスの2 *（最大 - 最小）値の増加でこれは起こらないと思います。

あなたのポイントは、(value, delta * position)の形式になります。