ОПТИКА Кластерный алгоритм. Как получить лучший эпсилон
Я реализую проект, который должен кластеризовать географические точки. Алгоритм OPTICS кажется очень хорошим решением. В качестве входных данных требуется всего 2 параметра (MinPts и Epsilon), которые представляют собой, соответственно, минимальное количество точек, необходимое для их рассмотрения в качестве кластера, и значение расстояния, используемое для сравнения, если две точки находятся, можно поместить в один кластер.
Моя проблема в том, что из-за огромного разнообразия точек я не могу установить фиксированный эпсилон. Просто посмотрите на изображение ниже.
http://s13.postimage.org/u5a08nwvb/Immagine.png
Та же самая структура точек, но в другом масштабе приведет к очень разным результатам. Предположим, чтобы установить MinPts=2 и epsilon = 1 км. Слева алгоритм будет создавать 2 кластера (красный и синий), но справа он создаст один кластер, содержащий все точки (красный), но я бы хотел получить 2 кластера даже справа.
Итак, мой вопрос: есть ли способ динамического вычисления значения эпсилона, чтобы получить этот результат?
РЕДАКТИРОВАТЬ 05 июня 2012 г.15.15: Я думал, что использую реализацию алгоритма OPTICS из библиотеки javaml, но, похоже, на самом деле это реализация алгоритма DBSCAN. Таким образом, теперь возникает вопрос: кто-нибудь знает реализацию алгоритма OPTICS на основе Java?
Большое спасибо и извините за мой плохой английский.
Marco
4 ответа
Значение epsilon в OPTICS предназначено исключительно для ограничения сложности времени выполнения при использовании структур индекса. Если у вас нет индекса ускорения, вы можете установить его в бесконечность.
Цитировать Википедию по ОПТИКЕ
Параметр \varepsilon строго говоря не обязателен. Может быть установлено максимальное значение. Когда пространственный индекс доступен, он, тем не менее, играет практическую роль, когда дело доходит до сложности.
То, что у вас, похоже, больше похоже на DBSCAN, чем на OPTICS. В OPTICS вам не нужно выбирать epsilon (авторы должны были назвать его max-epsilon!), Но ваш метод извлечения кластера позаботится об этом. Используете ли вы извлечение Xi, предложенное в статье OPTICS?
minPts намного важнее. Вы должны попробовать значение по крайней мере 5 или 10, а не 2. С 2 вы, по сути, выполняете однолинейную кластеризацию!
Пример, который вы привели выше, должен нормально работать после увеличения minPts!
Re: edit: Как вы можете видеть из статьи в Википедии, ELKI имеет правильную реализацию OPTICS и работает на Java.
Вы можете попробовать минимальное связующее дерево и затем удалить самый длинный край. Оставшееся остовное дерево и его центр - лучший центр для ОПТИКИ, и вы можете подсчитать количество точек вокруг него.
Вы можете попробовать масштабировать эпсилон по общему размеру вмещающего прямоугольника. Например, ваши левые данные составляют около 4 км x 6 км (используя мое глазное яблоко Mark I для измерения), а правые - около 2 км x 2 км. Так вот, эпсилон справа должен быть примерно в 2,5 раза меньше.
Конечно, это не работает надежно. Если, по вашим правым данным, есть еще одна отдельная точка в 4 км вправо и 2 км вниз, что сделает окружающий прямоугольник справа таким же, как слева, и вы получите аналогичные (неправильные) результаты.
В вашем объяснении выше, это изменение масштаба, которое создает неопределенность. Когда ваш масштаб станет больше, ваш эпсилон должен соответственно измениться. Поскольку они представлены в двух очень разных масштабах, два изображения, которые вы представили, НЕ имеют одинаковый набор точек. Они не будут одинаково реагировать на ваш алгоритм OPTICS без изменения параметров.
Короче нет. нет способа динамически рассчитать эпсилон, чтобы получить этот результат. Подобная кластеризация уже является NP-Hard, и эти алгоритмы кластеризации (оптика, k-means, veroni) могут только приблизить оптимальное решение.