Рекомендуемый алгоритм для кластеризации на основе времени

Question

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

У меня есть набор данных о нагрузке (в диапазоне от 0-500), и я хочу кластеризоватьони по временным интервалам.

Моя проблема в том, что я хочу найти точки времени, в которых на интервале времени наблюдаются существенные различия.Я точно буду знать, сколько их должно быть группировок (например, 5 отдельных кластеров), но не буду знать, где заканчивается один и начинается следующий.

Есть ли хороший алгоритм для применения в этом случае?Я смотрел на K-Means, но, похоже, он очень хорошо разбирается в кластерах, не обращая внимания на время, и я больше ищу границы, смотрящие на данные о нагрузке.

Answer 1

Я думаю, вы могли бы получить хорошие результаты от динамической программы. Для каждого интервала [i, j) пусть C(i, j) будет функцией потерь, которая ниже, когда значения интервала, скорее всего, будут одним кластером. Тогда пусть L(k, r) будет минимальной потерей для k кластеров элементов [0, r), у нас есть уравнения

L(1, r) = C(0, r)
L(k, r), k > 1 = min over s in [0, r) of L(k-1, s) + C(s, r).

Если необходимы O(1) значения k, для оценки этих уравнений с запоминанием требуется O(n^2) время и O(n) пространство, где n - количество выборок.

Правдоподобным первым выбором для C(i, j) будет статистическая дисперсия выборок в этом интервале. Наивно, для этого требуется Theta(n^3) время для вычисления для каждого интервала, но алгоритм Уэлфорда может использоваться для вычисления дисперсии в режиме онлайн, если вы итерируете s от его наибольшего значения до его наименьшего значения, поэтому общий алгоритм все равно будет быть O(n^2).