Как разбить последовательность на 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, то результат будет что-то вроде (вручную):

Это желаемый результат, поэтому вы можете рассмотреть возможность использования этого, и если он действительно работает во всех ваших сценариях. Аннотации, вы должны назначить ранее количество кластеров, которые вы хотите, но я думаю, что это не проблема для вас, поскольку вы задали свой вопрос.

Позвольте мне знать, если это работает;)

Edit:

Смотреть эту картину, то, что вы говорили. С помощью k-средств вы должны управлять delta value, это так, как позиция приращение, чтобы его значение имело тот же масштаб, что и значение. Но с E-M это не имеет значения.

Edit 2:

Хорошо, я не был прав, вы должны контролировать delta value. Это не то же самое, если вы увеличивать позиции на 1 или 3: (две группы)

Таким образом, как вы сказали, этот алгоритм может решить кластер точек, которые не являются соседними, если их положение далеко, но их ценность близка. Вы должны гарантировать, что этого не произойдет, с высоким приращением delta. Я думаю, что с приращением 2 * (max - min) значений вашей последовательности этого не произойдет.

Теперь ваши баллы будут иметь форму (value, delta * position).