Кластеризация посредством сжатия

Мы представляем новый метод кластеризации, основанный на сжатии. Метод не использует специфические для предметной области признаки или фоновые знания и работает следующим образом. Сначала мы определяем универсальное расстояние сходства — нормализованное расстояние сжатия (NCD), вычисляемое по длинам сжатых файлов данных (отдельно и при попарной конкатенации). Затем мы применяем метод иерархической кластеризации. NCD является универсальным, поскольку не ограничен конкретной областью применения и работает на границах между различными областями. Теоретический предшественник этого метода — нормализованное информационное расстояние, одним из разработчиков которого был один из авторов, — доказуемо оптимален, но использует невычислимое понятие сложности Колмогорова. Мы вводим точные понятия метрики сходства и нормального компрессора и показываем, что NCD, основанное на нормальном компрессоре, является метрикой сходства, приближающей универсальность. Для извлечения иерархии кластеров из матрицы расстояний мы строим дендрограмму (бинарное дерево) с помощью нового квартетного метода и быстрого эвристического алгоритма его реализации. Метод реализован и доступен в виде общедоступного программного обеспечения; он устойчив к выбору различных компрессоров. В подтверждение наших утверждений об универсальности и устойчивости мы приводим свидетельства успешного применения в таких разнообразных областях, как геномика, вирусология, языки, литература, музыка, рукописные цифры, астрономия, а также при сочетании объектов из совершенно разных предметных областей с использованием статистических, словарных компрессоров и компрессоров на основе блочной сортировки. В геномике мы представляем новые данные по ключевым вопросам эволюции млекопитающих, полученные на основе анализа полных митохондриальных геномов: порядков Eutheria и гипотезы Marsupionta в противопоставлении гипотезе Theria.