Интерпретация результатов кластеризации OPTICSxi

Question

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

В отличие от DBSCAN, алгоритм OPTICS создает не строгий кластерный раздел, а расширенный порядок базы данных. Для создания раздела кластера я использую OPTICSxi, который является еще одним алгоритмом, который производит классификацию на основе выходных данных OPTICS. Есть несколько библиотек, способных извлечь раздел кластера из вывода OPTICS, и реализация ELTI OPTICSxi является одной из них.

Мне очень ясно, как интерпретировать результаты DBSCAN (хотя это не так просто, чтобы установить "значимые" глобальные параметры); DBSCAN обнаруживает "прототип" кластера, характеризующийся плотностью, выраженной в количестве точек на область (minpts/epsilon). Результаты OPTICSxi кажутся немного более сложными для интерпретации.

Есть два явления, которые я иногда обнаруживаю в выходах OPTICSxi, и которые я не могу объяснить. Одним из них является появление "всплеск" кластеров, которые связывают части карты. Я не могу их объяснить, потому что они, кажется, сделаны из очень немногих пунктов, и я не понимаю, как алгоритм решает сгруппировать их в одном кластере. Действительно ли они представляют собой "коридор" изменения плотности? глядя на базовые данные, это не выглядит так. Вы можете увидеть эти "шипы" на изображении ниже.

Другое явление, которое я не могу объяснить, заключается в том, что иногда существуют "перекрывающиеся" кластеры одного и того же иерархического уровня. OPTICSxi основана на упорядочении базы данных OPTICS (например, дендрограммы), и на этой диаграмме нет повторяющихся точек.

Поскольку это иерархическая кластеризация, мы считаем, что кластеры более низкого уровня содержат кластеры более высокого уровня, и эта идея реализуется при построении выпуклых оболочек. Однако я не вижу никакого оправдания тому, чтобы кластеры пересекали другие кластеры на одном и том же иерархическом уровне, что на практике означало бы, что некоторые точки будут иметь двойное кластерное "членство". На изображении ниже мы видим несколько пересекающихся кластеров с одинаковым иерархическим уровнем (0).

И, наконец, самая важная мысль / вопрос, который я хочу оставить перед вами: что мы ожидаем увидеть в классификации кластеров OPTICSxi? Этот вопрос тесно связан с задачей параметризации OPTICSxi.

Поскольку я почти не вижу исследований с использованием OPTICSxi для конкретной кластерной проблемы, я изо всех сил пытаюсь найти оптимальную классификацию кластеризации; то есть: тот, который может обеспечить некоторые значимые / полезные результаты и добавить некоторую ценность к кластеризации DBSCAN. Чтобы помочь мне ответить на этот вопрос, я выполнил много прогонов OPTICSxi с различными комбинациями параметров и выбрал три, о которых я расскажу ниже.

На этом этапе я использовал большое значение эпсилона (2 км); смысл этого значения в том, что мы принимаем большие кластеры (до 2 км); поскольку алгоритм "объединяет" кластеры, мы получим несколько очень больших кластеров, которые почти наверняка будут иметь низкую плотность. Мне нравится этот вывод, потому что он раскрывает иерархическую структуру классификации и фактически напоминает мне о нескольких прогонах DBSCAN с разной комбинацией параметров (для разных плотностей), что является объявленной "силой" OPTICS. Как было упомянуто ранее, более мелкие кластеры соответствуют более высоким уровням в иерархическом масштабе и более высоким плотностям.

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

Этот прогон имеет выбор параметров, который похож на предыдущий, за исключением того, что minpts больше; в результате мы не только находим меньше кластеров, они меньше перекрываются, но и находятся в основном на одном уровне.

С точки зрения добавления значения в DBSCAN я бы выбрал первую комбинацию параметров, поскольку она обеспечивает иерархическую картину данных, четко показывая, какие области являются более плотными. ИМХО последняя комбинация параметров не дает представления о глобальном распределении плотности, поскольку она находит похожие кластеры по всей исследуемой территории. Мне интересно читать другие мнения.

Answer 1

Проблема извлечения кластеров из графика OPTICS - это первый и последний элементы кластера. Только из сюжета вы не можете (в моем понимании) решить, должен ли последний элемент принадлежать предыдущему кластеру или нет.

Рассмотрим такой сюжет

*
*        *
*        *
*       **
**************
A B C D EF G H

Это может быть кластер, где A находится посередине, BE рядом, а F- ближайший элемент в совершенно другом кластере. Например, набор данных может выглядеть так:

  *   D           *
B   A     E     F   G 
  *   C           H   *

Или, A находится на границе первого кластера, BD являются частью кластера, тогда как E является элементом выброса, перекрывающим разрыв с кластером FH. Набор данных, который вызывает такой эффект, может выглядеть так:

  D   *                 *
*   C   B  A    E     F   G 
  E   *                 H   *

OpticsXi работает визуально. F- "более крутая" точка для разделения, поэтому E в каждом случае будет частью первого кластера. Это буквально лучшее предположение, которое OpticsXi может сделать, не глядя на точки данных.

Это, вероятно, эффект, вызывающий всплески, которые вы наблюдали.

Я вижу четыре варианта:

1. улучшить OpticsXi самостоятельно. Если вам интересно, мы можем обсудить некоторые возможные эвристические методы, чтобы различить эти два случая выше.

2. реализовать один из других методов извлечения, таких как точки перегиба (но они могут страдать от тех же самых эффектов, также как они находятся в сюжете AFAICT)

3. использовать HDBSCAN (извините, еще не включен в ELKI, хотя у нас есть версия, которая работает) - вероятно, в 0.7.0

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