Как стать автором
Обновить

Комментарии 4

Как я понимаю, сложность D Хёфдинга равна примерно О(N^4), всё-таки не экспонента, а степень, но высокая. А есть ли алгоритм подсчета, который использует меньше операций, в принципе?

А есть ли алгоритм подсчета, который использует меньше операций, в принципе?

В соседнем комментарии написал: при очень большом количестве точек можно обойтись O(N) ;-)

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

Отличная тема, и статья неплохая! И отдельное спасибо за перевод комментариев к оригиналу.

Из недостатков - очень не хватает картинок... Если они у Вас в каком-то виде имеются, - добавьте, пожалуйста?

А теперь по существу:

Паттерн, который формируют эти точки на графике, отражает их совместное распределение: он показывает нам, как ранги в одной последовательности связаны с рангами в другой последовательности.

Имхо, это ключевая цитата. Чуть дополню ее контекст своими словами: если у нас есть плоскость (X,Y), то мы можем на ней нарисовать фактическую диаграмму рассеяния переменных (а лучше рангов) X и Y, и затем сравнить ее с "произведением" функций распределения X и Y по отдельности. Собственно, это и дает общий ответ на вопрос о наличии связи самого произвольного вида. Если два двумерных распределения совпадают, то переменные независимы. Если отличаются - то зависимы. И чем сильнее отличие, тем теснее зависимость.

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

на участки

в простейшем случае это будут квадратики, в чуть более оптимальном - прямоугольники, построенные так, чтобы теоретическое число точек в каждом из них было примерно одинаковое, ну и можно еще что-нибудь похитрее придумать, если не лень ;-)

в соответствии с требованиями Хи=квадрата по числу точек, и вуаля: считаем статистику Хи-квадрат, и ответ готов!

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

при работе с практическими данными

В которых есть выбросы и т.п.

Ну и конечно, при этом для сравнения распределений можно использовать самые разные критерии - не обязательно Хи-квадрат. Например, D-статистика Хёфдинга очень хороша для малых выборок, и т.д. А при очень большом числе точек можно считать отношение распределений методом Монте-Карло. Мы недавно этот подход применили при работе с сейсмическими каталогами - выделяли там

групповые землетрясения

и довольно неожиданно получили очень простой и эффективный алгоритм группирования. Его идея почти тривиальна, а вычислительная сложность O(N), но при этом результаты не хуже, чем у традиционных алгоритмов группирования, которые зачастую гораздо более заумные, и вдобавок требуют "экспертного" задания настроек (читай = допускают произвол).

P.S. Полный текст этой статьи про гуппирование

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

P.S. Ну и добавлю, как обычно, свой warning message

про временные ряды

Как говорится, кто о чем - а вшивый о блохах. Если Вы изучаете именно взаимосвязи между временными рядами, то есть переменными, которые существенно зависят от времени, то все вышесказанное и в статье, и в моем комментарии - НЕ ДЛЯ ВАС! Так как все эти критерии связи построены для случайных величин. У которых есть генеральная совокупность, из которой мы делаем выборку, и т.д. В случае нестационарного временного ряда, когда эргодичность гарантированно отсутствует, такой генеральной совокупности у нас нет!

Попросту говоря, если значения ваших временных рядов существенно изменяются с течением времени, то ЛЮБЫЕ способы расчета корреляций, а также оценки взаимозависимостей могут (даже как бы не будут) в этом случае очень сильно лажать. Вплоть до катастрофически неправильных выводов.

Подробнее см. вот эту статью.

Попросту говоря, если значения ваших временных рядов существенно изменяются с течением времени, то...

Вот не совсем так. Значения могут как угодно меняться со временем. А вот если основные стат моменты начинают меняться со временем существенно ("неадиабатически"), тогда...

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации