Масштабируемые алгоритмы кластерного анализа: назад в будущее?

- Прежде чем бежать в магазин за новым оборудованием, посмотрите на чердаках, - практично предложила Карин.
Л.М.Буджолд, "Гражданская кампания"

Заметка отражает мнение, частично полярное выводам работы [1]. Хочу подчеркнуть, что это не критика текста [1], а небольшое уточнение и иной взгляд на один из перечисленных там алгоритмов.

Рассматриваются методы и алгоритмы кластерного анализа (кластеризации, автоматической классификации) данных и масштабируемость таких алгоритмов при росте размеров обрабатываемых выборок данных до десятков-сотен тысяч и даже миллионов ситуаций-паттернов (строк в базе данных). В [1] приводятся два утверждения, которые хочется уточнить.

Первая фраза - "разработаны масштабируемые аналоги алгоритма типа k-means" - наталкивает на мысль, что с базовым методом k-means (синонимы: метод к-средних, метод динамических ядер) в случае больших баз данных ловить нечего и что относительно простыми средствами он не масштабируется - нужны именно специальные варианты (причем в [1] указана только одна ссылка на такие алгоритмы - на статью [2]). Однако, это не так.

Алгоритм [2] предполагает сжатие-декомпрессию блоков данных - сжатие для запихивания в имеющийся объем памяти как можно большего фрагмента базы данных (которая вся целиком в оперативную память компьютера не влезает) и динамическую распаковку сжатых данных (с возможностью организации итераций по этим данным - т.к. итерации в памяти гораздо быстрее, чем запросы данных с жесткого диска). Но позже, в статье [3] было показано, что этот алгоритм проигрывает простейшей масштабируемой версии алгоритма k-means. Предложенный в [3] масштабируемый вариант метода динамических ядер является однопроходным по базе данных, не требует выделения дополнительной памяти для хранения исходных данных. Отличие алгоритма кластерного анализа [3] от базового варианта k-means заключается просто в периодическом пересчете центров кластеров во время единственного прохода по таблице. Действительно, в режиме онлайн, т.е. с корректировкой центров кластеров после просмотра каждого очередного паттерна, алгоритм k-means является неустойчивым, кластеры могут "водить хоровод" и не обеспечивать сходимости решения. Но и корректировать центры кластеров после просмотра всей выборки неэкономично (для сходимости потребуется несколько проходов по выборке), поэтому можно корректировать кластеры после просмотра репрезентативного фрагмента выборки - тогда коррекция по нескольким последовательным фрагментам эквивалентна нескольким итерациям по всей выборке данных.

Дополнительную возможность ускорения вариантов алгоритма k-means при числе кластеров больше трех дает еще одна статья Чарльза Элкана [4] - вычисление парных расстояний между текущими позициями центров кластеров (расстояния вычисляются однократно на каждой эпохе) и использование затем неравенства треугольника позволяет снизить число вычисления парных расстояний между текущим примером выборки и векторами-центрами кластеров, т.е. снизить затраты на вычисление локальной функции оптимизации (по терминам из [1]).

Соответственно, другое приведенное в [1] высказывание о масштабируемости алгоритмов кластерного анализа через отказ от локальной функции оптимизации не является прямым запрещением использования алгоритма k-means как масштабируемого алгоритма (или теоретическим доказательством о несовместимости k-means и отличной от локальной функции оптимизации). Так, предложенный в [3] вариант использует только один проход по базе данных (или несколько проходов - если пользователь захочет перестраховаться с гарантией сходимости) - это минимум, ниже которого не опустится никакой масштабируемый алгоритм кластерного анализа. А алгоритм [4] позволяет еще сильнее снизить вычислительную сложность метода динамических ядер: если исходно на каждой итерации-эпохе сложность составляет СnN операций, где С - число кластеров, n - размерность векторов, N - число примеров, то в модификации [4] сложность эпохи будет сnN, где c<С, и чем больше число кластеров С, тем больше может быть относительное ускорение.

Итог. Простейший метод кластерного анализа - алгоритм динамических ядер - очень просто дорабатывается для достижения потенциально пиковой масштабируемости при минимально задействуемом объеме дополнительной памяти (накапливаемые на фрагментах выборки вектора поправок к ядрам для [3] и матрица парных расстояний между центрами кластеров для [4]). И длина текста программы реализации этого модифицированного масштабируемого алгоритма будет меньше, чем для иных алгоритмов - т.е. снижаются трудозатраты на этапе программирования и требования к квалификации программиста.

Отмечу, что выводы похожи на озвученное в другой заметке утверждение об относительно высокой эффективности многих базовых алгоритмов обработки и анализа данных по сравнению с сверхсовременными разработками. Действительно, простенькая доработка алгоритма k-means вывела его если и не в безусловные лидеры, то гарантированно в группу лидеров по многим характеристикам. K-means forever? :)

Литература
1. Паклин Н. Алгоритмы кластеризации на службе Data Mining. 2006. http://basegroup.ru/clusterization/datamining.htm
2. Bradley P.S., Fayyad U.M., Reina C.A. Scaling clustering algorithms to large databases / Proc. 4th Int. Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, Calif., 1998. - pp.9-15.
3. Farnstrom F., Lewis J., Elkan C. Scalability for clustering algorithms revisited / SIGKDD Explorations, 2000. Vol.2 No.1. - pp.51-57.
4. Elkan C. Using the triangle inequality to accelerate k-means / Proc. Twentieth Int. Conf. on Machine Learning (ICML'03), 2003. - pp.147-153.