Comments 4
Как я понимаю, сложность D Хёфдинга равна примерно О(N^4), всё-таки не экспонента, а степень, но высокая. А есть ли алгоритм подсчета, который использует меньше операций, в принципе?
А есть ли алгоритм подсчета, который использует меньше операций, в принципе?
В соседнем комментарии написал: при очень большом количестве точек можно обойтись O(N) ;-)
Правда, это уже будет не совсем D, а немного другая статистика, но измеряет она почти то же самое: тесноту "обобщенной" связи произвольного вида. Правда, я подозреваю, что все это будет работать только для "разумных" распределений - тогда связь действительно может быть какая угодно. Но вот если вдруг нарваться на распределения с бесконечной дисперсией (как ни странно, на практике они тоже встречаются), или на фрактальные множества , или то черт его знает...
Отличная тема, и статья неплохая! И отдельное спасибо за перевод комментариев к оригиналу.
Из недостатков - очень не хватает картинок... Если они у Вас в каком-то виде имеются, - добавьте, пожалуйста?
А теперь по существу:
Паттерн, который формируют эти точки на графике, отражает их совместное распределение: он показывает нам, как ранги в одной последовательности связаны с рангами в другой последовательности.
Имхо, это ключевая цитата. Чуть дополню ее контекст своими словами: если у нас есть плоскость (X,Y), то мы можем на ней нарисовать фактическую диаграмму рассеяния переменных (а лучше рангов) X и Y, и затем сравнить ее с "произведением" функций распределения X и Y по отдельности. Собственно, это и дает общий ответ на вопрос о наличии связи самого произвольного вида. Если два двумерных распределения совпадают, то переменные независимы. Если отличаются - то зависимы. И чем сильнее отличие, тем теснее зависимость.
Дальше уже начинаются детали: как именно мы будем два эти распределения сравнивать. Если точек очень много (многие тысячи), то нам, в общем-то, не обязательно применять полный перебор. Вполне можно разбить плоскость
на участки
в простейшем случае это будут квадратики, в чуть более оптимальном - прямоугольники, построенные так, чтобы теоретическое число точек в каждом из них было примерно одинаковое, ну и можно еще что-нибудь похитрее придумать, если не лень ;-)
в соответствии с требованиями Хи=квадрата по числу точек, и вуаля: считаем статистику Хи-квадрат, и ответ готов!
Вообще, идея сравнения двумерных распределений для проверки наличия связи - совершенно стандартная, и она наиболее точно соответствует классическому понятию независимости. Следующий шаг - это использовать вместо переменных их ранги. Это уже не совсем классика, но жутко полезно
при работе с практическими данными
В которых есть выбросы и т.п.
Ну и конечно, при этом для сравнения распределений можно использовать самые разные критерии - не обязательно Хи-квадрат. Например, D-статистика Хёфдинга очень хороша для малых выборок, и т.д. А при очень большом числе точек можно считать отношение распределений методом Монте-Карло. Мы недавно этот подход применили при работе с сейсмическими каталогами - выделяли там
групповые землетрясения
и довольно неожиданно получили очень простой и эффективный алгоритм группирования. Его идея почти тривиальна, а вычислительная сложность O(N), но при этом результаты не хуже, чем у традиционных алгоритмов группирования, которые зачастую гораздо более заумные, и вдобавок требуют "экспертного" задания настроек (читай = допускают произвол).
P.S. Полный текст этой статьи про гуппирование
можно найти вот тут, но если действительно интересно, то лучше чуть-чуть подождать: мы недавно отправили в редакцию следующую статью (про цепочки землетрясений), где идея этого алгоритма объясняется гораздо понятнее и без лишних отсылок к старым работам
P.S. Ну и добавлю, как обычно, свой warning message
про временные ряды
Как говорится, кто о чем - а вшивый о блохах. Если Вы изучаете именно взаимосвязи между временными рядами, то есть переменными, которые существенно зависят от времени, то все вышесказанное и в статье, и в моем комментарии - НЕ ДЛЯ ВАС! Так как все эти критерии связи построены для случайных величин. У которых есть генеральная совокупность, из которой мы делаем выборку, и т.д. В случае нестационарного временного ряда, когда эргодичность гарантированно отсутствует, такой генеральной совокупности у нас нет!
Попросту говоря, если значения ваших временных рядов существенно изменяются с течением времени, то ЛЮБЫЕ способы расчета корреляций, а также оценки взаимозависимостей могут (даже как бы не будут) в этом случае очень сильно лажать. Вплоть до катастрофически неправильных выводов.
Подробнее см. вот эту статью.
Нелинейные корреляции. Моя любимая статистическая мера: D Хёфдинга