K-средства кластеризации в библиотеке OpenIMAJ

Question

Я не очень опытный в машинном обучении и кластерного анализа, но я следующая проблема:

У меня есть ~ 100kk-1000kk куски данных, которые я не могу загрузить в память все в один раз, и мне нужно разделить его на несколько классов (например, 1-10k или даже 100k классов) для дальнейших анализов. Для этого я выбрал алгоритм K-Means, реализованный в библиотеке OpenIMAJ (класс FloatKMeans). Я понимаю, что алгоритм K-средства можно разделить на 2 этапа:

1. этапа обучения - где я прохожу во всех данных я должен создать/заполнение классов
2. Assignemnt фазы - где я могу задать кластер, к которому принадлежит данная часть данных

Я планирую построить кластерную модель, используя фазу сокращения Hadoop, где я получу части данных один за другим (поэтому я не могу передавать данные все сразу к алгоритму)

Мои вопросы:

• Является ли реализация OpenIMAJ оптимальной для использования в таком случае «bigdata»? Не будет ли это принято навсегда, чтобы рассчитать?
• Возможно ли «перетекать» данные в алгоритм во время хаоса, чтобы уменьшить неудобство, чтобы изучить кластер?
• Возможно ли сохранить извлеченный кластер (модель) в виде байтов, чтобы передать модель на следующую работу hadoop?
• Можно ли запустить фазу назначения алгоритма во время отображения привязки?

Спасибо за помощь

Answer 1

K-средства кластеризации является итерационным алгоритмом, который делает несколько проходов по данным. В каждом проходе точки назначаются центроидам кластеров, а затем после того, как все точки были назначены, центроиды кластера пересчитываются как среднее из назначенных точек. Вы не можете «передавать» данные в алгоритм в традиционном смысле, так как вам нужно будет вернуться к нему во время последующих итераций.

Что касается реализации OpenIMAJ FloatKMeans: да это может обрабатывать «большие данные» в том смысле, что он не возражает, где он получает данные из - за DataSource, например, что он принимает в качестве входных данных может считывать данные с диска при необходимости. Единственное требование состоит в том, что вы можете удерживать все центроиды в памяти во время выполнения алгоритма. Реализация многопоточная, поэтому все ядра процессора могут использоваться во время вычислений. Здесь приведен пример кода: https://github.com/openimaj/openimaj/blob/master/demos/examples/src/main/java/org/openimaj/examples/ml/clustering/kmeans/BigDataClusterExample.java. Методы OpenIMAJ IOUtils.writeBinary(...) могут использоваться для сохранения результирующих центроидов кластера в объекте FloatCentroidsResult.

Одной из самых больших затрат в K-Means является вычисление расстояний между каждой точкой данных и каждым центроидом кластера, чтобы найти ближайший. Стоимость этого связана с размерностью данных и количеством центроидов. Если у вас есть большое количество центроидов и высокоразмерных данных, то использование приблизительной реализации K-Means может иметь большие преимущества скорости за счет небольшой потери точности (например, FloatKMeans.createKDTreeEnsemble() - здесь используется ансамбль KD -Trees для ускорения вычислений соседа).

Что касается интеграции с Hadoop, можно реализовать K-Means как серию задач Map-Reduce (каждая пара соответствует итерации алгоритма).См. Эту статью для обсуждения: http://eprints.soton.ac.uk/344243/1/paper.pdf. Если вы хотите спуститься по этому маршруту, OpenIMAJ имеет здесь очень грубую реализацию, которую вы могли бы построить: https://github.com/openimaj/openimaj/tree/master/hadoop/tools/HadoopFastKMeans. Как упоминалось в связанной статье, Apache Mahout также содержит реализацию: https://mahout.apache.org. Одна из проблем в обеих этих реализациях заключается в том, что они требовали передачи большого количества данных между преобразователями и редуктором (каждый преобразователь испускает текущую точку данных и назначенный ей идентификатор кластера). Степень этого может означать, что было бы быстрее использовать реализацию алгоритма, отличную от Hadoop, но это будет зависеть от того, какие ресурсы обработки у вас имеются и характер набора данных. Проблема передачи данных между картой и сокращением, вероятно, также может быть уменьшена с помощью умного Hadoop Combiner и вычисляет взвешенные центроиды из подмножеств данных, а затем передает их на (модифицированный) редуктор, чтобы вычислить фактические центроиды.