ОПТИКА Алгоритм кластеризации. Как получить лучший epsilon

Question

Я реализую проект, которому необходимо сгруппировать географические точки. Алгоритм OPTICS представляется очень приятным решением. В качестве входных данных (MinPts и Epsilon) требуется всего 2 параметра, которые представляют собой, соответственно, минимальное количество точек, необходимых для их рассмотрения в качестве кластера, а значение расстояния, используемое для сравнения, если две точки находятся внутри, можно разместить в одном кластере.

Моя проблема заключается в том, что из-за экстремального разнообразия точек я не могу установить фиксированный эпсилон. Просто взгляните на изображение ниже.

the problem http://s13.postimage.org/u5a08nwvb/Immagine.png

То же точки структура, но в другом масштабе привело бы к очень разные. Предположим установить MinPts = 2 и epsilon = 1Km. Слева алгоритм будет создавать 2 кластера (красный и синий), но справа он создаст один кластер, содержащий все точки (красный), но я хотел бы получить 2 кластера даже справа.

Итак, мой вопрос: есть ли способ вычислить динамическое значение epsilon для получения этого результата?

EDIT 5 июня 2012 3:15 вечера: Я думал, что с помощью реализации алгоритма OPTICS из библиотеки javaml, но мне кажется, что на самом деле является DBSCAN реализация алгоритма. Итак, вопрос в том, знает ли кто-нибудь о реализации алгоритма OPTICS на основе Java?

Большое спасибо и извините за мой бедный английский.

Marco

Answer 1

Значение epsilon в OPTICS равно только ограничивает сложность выполнения при использовании индексных структур. Если у вас нет индекса ускорения, вы можете установить его на бесконечность.

Цитирую Википедию на OPTICS

Параметр \ varepsilon, строго говоря, не является необходимым. Его можно установить на максимальное значение. Когда имеется пространственный индекс, он, однако, играет практическую роль, когда дело доходит до сложности.

У вас, похоже, больше похоже на DBSCAN, чем на ОПТИКУ. В OPTICS вам не нужно выбирать epsilon (его авторы должны были называть max-epsilon!), Но ваш метод извлечения кластера позаботится об этом. Используете ли вы экстракцию Xi, предложенную в документе OPTICS?

minPts гораздо важнее. Вы должны попробовать значение не менее 5 или 10, а не 2. С 2, вы, по существу, выполняете односвязную кластеризацию!

Пример, который вы указали выше, должен работать нормально, как только вы увеличиваете minPts!

Re: Редактировать: Как вы можете даже видеть в статье в Википедии, ELKI имеет правильную реализацию OPTICS, и она находится на Java.

Answer 2

В вашем объяснении выше, это изменение в масштабе, который создает неопределенность. Когда ваш масштаб увеличивается, ваш эпсилон должен соответствующим образом измениться. Поскольку они находятся в двух очень разных масштабах, два изображения, которые вы представили, не являются одинаковым набором точек. Они не будут одинаково реагировать на ваш алгоритм OPTICS без изменения параметров.

Одним словом, нет. нет никакого способа динамически вычислить epsilon, чтобы получить этот результат. Кластеризация подобна уже NP-Hard, и эти алгоритмы кластеризации (оптика, k-средства, верони) могут приближать только оптимальное решение.

Answer 3

Вы можете попытаться масштабировать epsilon на общий размер охватывающего прямоугольника. Например, ваши левые данные составляют около 4 км x 6 км (с помощью измерительного ящика Mark I), а справа - около 2 км x 2 км. Итак, эпсилон справа должен быть примерно в 2,5 раза меньше.

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

Answer 4

Вы можете попробовать минимальное остовное дерево, а затем удалить самый длинный край. Оставшееся остовное дерево и центр их - лучший центр для ОПТИКИ, и вы можете подсчитать количество точек вокруг него.