Как по-простому определить наличие кластеров во временных данных?

Question

[Сергей Соколов]

Для небольших наборов timestamp требуется определить, распределены ли они относительно равномерно, или кучкуются около отдельных временных точек?

Курс статистики забыт. Наверное, есть какая-то мера равномерности распределения точек вдоль одной оси?

Например:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] // k = 0, идеально равномерно
[1, 2.92, 2.95, 2.96, 2.98, 3.05, 3.07, 6.9, 6.95, 6.99, 7.01, 10] // 1 > k > 0, кластеры около примерно 3 и 7
[5, 5, 5, 5, 5, 5, 5, 5] // k = 1, 100%-плотный кластер в 5

Как найти кластеры и меру и рассеянности? Делать планирую на JS, но язык/среда не принципиальны – понять бы принцип решения.

Answer 1

[x67]

Для массива А(10)
1. Считаешь дельту между каждыми соседними точками - синий график Б(9)
2. Считаешь мат. ожидание - оранжевая линия
3. Считаешь разницу между мат. ожиданием и дельтой в каждой точке, получая С(9)
3. Считаешь площадь на интервалах одинаковой длины в массиве С. Пусть интервал будет равен 3. Получаешь массив Д(9/3=3) Чем больше площадь на интервале, тем выше там плотность. Ищешь максимумы или минимумы площадей на интервалах нужной тебе длины. Там точки или будут кучковаться или самыми редкими. Чем больше временных точек в целом, тем красивее графики.

Answer 2

[Sly_tom_cat .]

Есть в машинном обучении специальный класс задач - кластеризация: https://habrahabr.ru/post/67078/ - какраз для решения таких задач

Comments

[Сергей Соколов]

эт да, сейчас как раз на 4-й неделе Coursera'вского Machine Learning с Andrew Ng. Но прикладная задача для одномерного набора значений, кажется, решается совсем простым алгоритмом, который знают все, кроме меня : ) Что-то вроде конволюции при правильном (как подобрать?) размере окна найдёт наибольший из кластеров, и если тот не занимает весь отрезок значений, значит, данные как-то кучкуются, а не распределены равномерно.

Answer 3

[dmshar]

Если делать все "как надо", то первым делом надо ответить на вопрос - распределение выборки отличается от равномерного или нет. Если отличается - то тогда можно идти дальше - искать кластеры, или выяснять, какое у выборки (а через нее - и у генеральной совокупности) распределение в действительности, и т.д. По большому счету, в дальнейшем даже выбор метода кластеризации, если его делать "правильно", должен зависеть и от результат этого этапа в том числе. Если-же не отличается - ну тогда и так все ясно, дальнейших исследований не требуется. Не забудьте после применения критерия проверить значимость полученных результатов, что-бы понимать, на сколько им можно доверять.

Для определения "равномерности" выборки существуют ряд специальных критериев, наиболее распространенный из которых - т.н. критерий Шермана. Вычислительно простой и статистически мощный. (Существуют и другие критерии, но оптимальный выбор конкретного критерия - это уже тема более глубокого анализа).

И еще хочу обратить ваше внимание, что кластеризация временнЫх рядов (именно рядов!) - это немного другое, чем просто кластеризация значений этих самых рядов (по сути, не отличающееся от кластеризации статических данных). Разные цели и разные методы.

Comments

[Сергей Соколов]

задача – классификация аккаунтов в соц.сети на фековые или настоящие, опираясь только на даты постов. Фейки часто делают по многу постов примерно в одно время, затем пропадают надолго. Таких пиков у них может быть несколько.

[Сергей Соколов]

Человечьи аккаунты постят по-всякому. Да, по-хорошему, надо тренировать сеть или логистическую регрессию. Но думалось, просто найти кластеры постов и тогда подозревать фейковость аккаунта.

Answer 4

[xandox]

Я бы предложил критерий кси-квадрат на то что распределение является распределением Пуассона.

Answer 5

[⚡ Kotobotov ⚡]

смотри ты хочешь сгруппировать отдельные записи в группы, заменяя свойства в отдельных записях, на свойства целой группы, соответственно ты теряешь определённые данные у записей.
и ты можешь для себя решить на какой размер потерянных данных ты готов пойти при группировке (упрощении) данных.
тоесть померить размер ошибки после группировки, размер кластеризации у тебя ограничен сверху количеством записей, снизу единицей, ты можешь начать с количества кластеров равного размеру количества записей, постоянно сокращая количество кластеров, и оценивая ошибку после этого сокращения, до тех пор пока размер ошибки не превысит максимально допустимую.
это один метод.
==========
возможен второй метод: например связанный с оценкой динамики роста размера ошибок и сокращения количества кластеров, ты точно также можешь сокращать количество кластеров, не задавая сам размер ошибки, а оценивая скорость роста ошибки. Грубо говоря например ты сократил количество кластеров на 20% ошибка выросла на 1%, ты сократил ещё раз количество кластеров на 20%, ошибка выросла на 2%, ты сократил количество кластеров ещё на 20% ошибка выросла на 30% (наверно последний шаг не стоит приминять, и количество кластеров оставить на предыдущем уровне, ну или попробовать сократить не на 20% а на 10% и опять оценить)
======
можно и другие методы придумать, связанные с мерой близости между отдельными элементами, при обьединении их в кластер.