Как сделать иерархическую кластеризацию для матрицы большого сходства
У меня есть около 50 тыс. Наборов данных, значение которых может находиться в диапазоне от 0 до 10. Я хочу применить HAC для кластеризации этих данных. Но чтобы применить HAC, мне нужно подготовить матрицу подобия N*N.
Для N = 50K эта матрица будет просто слишком большой, чтобы ее можно было хранить в памяти, даже если я использую short.
Есть ли способ сделать HAC в пакетном режиме или любой другой метод, который может помочь мне применить HAC с точками данных 50K. Я планирую реализовать это в Java.
Я также беспокоюсь о том, сколько времени это займет, любые указания по этому поводу были бы весьма полезны.
2 ответа
Если вы хотите применить кластерный подход "сверху вниз", вы можете легко распространить его, соответствующую статью: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf
Короткая история (цитата из другой статьи): После первого разделения узла каждый созданный узел можно отправить в распределенный процесс для повторного разделения и т. Д. Каждый распределенный процесс должен знать только подмножество набора данных. это расщепление. Только родительский процесс знает полный набор данных.
Подход "снизу вверх" распространять гораздо сложнее, и я не буду здесь ничего предлагать.
Но вам не нужно писать это на Java самостоятельно, библиотеки Mahout или MLLib уже имеют его, и они поддерживают Java. И hadoop
В любом случае, вот ваш пример на Java для hadoop, если вы хотите написать его самостоятельно: http://sujitpal.blogspot.ru/2009/09/hierarchical-agglomerative-clustering.html
Наконец, хорошая и большая работа по сравнению различных распределенных подходов для иерархической кластеризации:
C. F. Olson. "Parallel Algorithms for Hierarchical Clustering." Parallel Computing, 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.
Существуют различные методы HAC, но все они, как правило, ограничены снизу сложностью O(n^2). Таким образом, хотя 50 тыс. Все еще выполнимое количество точек данных, вы не сможете масштабировать это слишком далеко.
Я не знаю, какой код вы используете, но вам не нужно явно хранить матрицу подобия размером N^2, значения сходства можно вычислять на лету / по мере необходимости. Scikit learn сделает это без явного формирования матрицы.