Непрерывная кластеризация

9

Поэтому у меня возникла проблема, связанная с кластеризацией с живыми непрерывно потоковыми данными. Поскольку у меня постоянно растущий набор данных, я не уверен, что это лучший способ запустить эффективную и действенную кластеризацию. Я придумал несколько возможных решений, в том числе:

  1. Установка ограничения на количество точек данных, которое разрешается, поэтому при достижении предела, когда другая точка данных входит в самую старую точку, удаляется. По сути, это говорит о том, что более старые данные больше не актуальны для нас, чтобы заботиться о том, что мы теряем, выбрасывая их.

  2. Когда данных достаточно для создания хорошей кластеризации, рассмотрите эту «настройку» и, когда появляются новые точки, вместо того, чтобы заново кластеризовать все данные, просто выясните, к какому центру кластера ближе всего новая точка, и добавьте ее к этому. Преимущество здесь в том, что вы можете избежать необходимости кластеризации на каждой новой точке, и вам не придется хранить все остальные точки, только центры кластеров, считая эту кластеризацию «достаточно хорошей». Недостатком является то, что повторный запуск алгоритма со всеми точками данных с самого начала может быть более точным.

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

Суреш Венкат
источник

Ответы:

6

Похоже, вы ищете онлайн алгоритмы для кластеризации.

Я предлагаю поискать "онлайн-кластеризацию" в Google Scholar. Возможно, следующие ссылки окажутся полезными (по крайней мере, в качестве отправной точки).

Джоэл Рыбицки
источник
9

Существует много работы по потоковой кластеризации (которая немного отличается от онлайн-методов, но по сути то, что вы хотите). Приведенная выше ссылка Guha et al. Является очень хорошей, и для более общего взгляда на то, какие методы работают, и какие методы использовались в прошлом (как эвристические, так и точные), вы можете взглянуть на мой опрос на кластеризацию по потокам .

Суреш Венкат
источник
7

Вы также можете взглянуть на примечания к лекции 14 и 15 моего курса об алгоритмах потоков данных.

Петр
источник
4

Мне нравится обзор Суреша, приведенный выше, и суммируются различные подходы в потоковой кластеризации. Вы не просили об этом, но, возможно, в некоторых случаях проблема заключается в том, что непрерывные данные видны распределенными серверами, необходимо поддерживать кластеризацию в центре, а не перемещать большое количество данных. Смотрите здесь .

я тоже
источник
добро пожаловать, Мутху!
Суреш Венкат