Обсуждение:DBSCAN

Без названия

Действительно ли необходимо сокращение epsilon до eps? Pflaquerre (обс.) 07:52, 15 июля 2008 (UTC) [ ответить ]

Нет, это не так, но это соответствует оригинальной публикации Эстер, Кригеля, Сандера и Сюй. mathias ( обсуждение ) 17:52, 7 апреля 2009 (UTC) [ ответ ]

Кажется, алгоритму не помешало бы небольшое разъяснение. Что именно мы рекурсируем? Является ли C глобальным? Каковы параметры процедуры/функции? Почему шум никогда не помечается как посещенный? Pflaquerre (обсуждение) 07:55, 15 июля 2008 (UTC) [ ответить ]

Я поддерживаю это Креншоу (выступление) 23:42, 26 ноября 2008 (UTC) [ ответить ]

В Steps говорится: «начальная точка и ее соседи добавляются в этот кластер». В псевдокоде есть только: «отметить P как посещенную». Должен ли псевдокод говорить «Отметить P и все точки в N как посещенные?» — Предыдущий неподписанный комментарий добавлен 98.207.54.162 (обсуждение) 20:59, 7 февраля 2009 (UTC) [ ответить ]

Проблема нотации «большое О»

обозначение "O((n2-n)/2)" в разделе "Обнаружение ближайшего соседства" использовано неправильно. Должно быть O(n^2), поскольку константа "2" и низший порядок "n" асимптотически незначимы. --Dexter (обс.) 02:18, 28 апреля 2009 (UTC) [ ответить ]

Неверный псевдокод?

Timmenzies ( обсуждение ) 15:07, 14 июня 2011 (UTC) [ ответ ]

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

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

В любом случае, чтобы соответствовать статье и обработать этот особый случай, разве псевдокод не должен быть следующим? (все мои изменения отмечены знаком //

DBSCAN(D, eps, MinPts) С = 0 для каждой непосещенной точки P в наборе данных D отметить P как посещённый N = getNeighbors (P, eps) если sizeof(N) < MinPts отметьте P как ШУМ еще C = следующий кластер C.id = новый идентификатор // новый expandCluster(P, N, C, eps, MinPts) expandCluster(P, N, C, eps, MinPts) добавить P в кластер C для каждой точки P' в N если P' не посещается отметить P' как посещённый N' = getNeighbors(P', eps) если sizeof(N') >= MinPts N = N соединено с N' если P' еще не является членом какого-либо кластера добавить P' к кластеру C иначе // новый C.id = идентификатор кластера, содержащего P' // новый
Результат DBSCAN недетерминирован на граничных точках; но вы явно НЕ хотите объединять кластеры, когда они разделяют граничную точку, потому что это нарушит модель связности плотности. Ваша модификация приведет к этому, нарушив всю модель связности плотности. Также я считаю, что ваше первое предложение неверно. IIRC новая *точка* сохраняет идентификатор кластера старого кластера, что и делает код. Альтернативой было бы просто перезаписать назначение кластера. Два варианта изоморфны, вы можете эмулировать другой, просто обработав набор данных в обратном порядке.
Пограничные точки достижимы по плотности из кластера, но сами по себе не плотные. Они могут быть достижимы по плотности двумя кластерами, но поскольку они не являются основными точками, они НЕ объединят два кластера. Будучи достижимыми по плотности, они будут принадлежать обоим кластерам, но алгоритм DBSCAN назначает их тому кластеру, который обнаружил их первым. Они обычно не являются значимыми, и таким образом вы получаете правильное разбиение, а не нечеткую или перекрывающуюся кластеризацию. -- 87.174.53.81 (обсуждение) 22:13, 14 июня 2011 (UTC) [ ответить ]

Фотографии

Эта статья остро нуждается в картинках. Особенно раздел «Основная идея». — Предыдущий неподписанный комментарий добавлен 99.181.61.118 (обсуждение) 22:19, 15 августа 2011 (UTC) [ ответить ]

В подписи к рисунку в разделе «Предварительные данные» некоторые из основных точек имеют только 3 достижимых соседа. Если я не ошибаюсь, то, учитывая определение или основные точки, либо метка неверна (minPts = 4 должно быть minPts = 3), ЛИБО рисунок неверен, и только две точки следует считать основными точками (я думаю, исправить подпись проще, чем исправить рисунок). Я не хотел редактировать, пока не буду уверен. — Предыдущий неподписанный комментарий добавлен 143.239.81.7 ( talk ) 14:13, 26 сентября 2018 (UTC) [ ответить ]

Количество точек равно 4. Не сказано "количество точек, отличающихся от точки запроса". Запрос диапазона не исключает точку запроса - она ​​является частью базы данных. Chire ( talk ) 14:29, 12 октября 2018 (UTC) [ ответить ]

Тема не совсем ясна... какой порядок создается...

На этой странице есть несколько изображений, которые кажутся более полезными http://de.wikipedia.org/wiki/OPTICS

Более того, нет объяснения порядка... Возможно, пример был бы очень полезен. Пожалуйста, помогите, нужно реализовать, но не имею представления, как работает порядок.

не могу найти другого лучшего источника Спасибо Варункумар Джаяпол jv5k5-wiz@yahoo.co.in — Предыдущий неподписанный комментарий добавлен 203.196.165.100 (обсуждение) 12:36, 14 июня 2012 (UTC) [ ответить ]

DBSCAN не генерирует упорядочивание. Вы путаете его с алгоритмом OPTICS . Вы не думали посмотреть оригинальные публикации? Они содержат псевдокод. -- Chire ( обсуждение ) 16:17, 14 июня 2012 (UTC) [ ответить ]

Раздел «Основная идея» нечитаем

Раздел «Основная идея» непонятен тому, кто не понимает алгоритм заранее, из-за слишком большого количества местоимений. «It's» может быть p или q.

192.249.47.174 ( обсуждение ) 15:51, 21 июня 2012 (UTC) [ ответить ]

В деталях алгоритма следует отметить, что DBSCAN может создать кластер размером меньше minPts

Кластер в DBSCAN гарантированно состоит как минимум из 1 основной точки.

Поскольку пограничные точки, принадлежащие более чем одному кластеру, будут "случайным образом" (обычно: первый пришел) назначены одному из кластеров, основная точка может не иметь возможности сохранить/получить всех своих соседей. Таким образом, она может быть меньше minPts.

Одномерный пример: minPts=4, epsilon=1:

0,0 0,5 1,0 2,0 3,0 3,5 4,0

|-------X-------| Основная точка 1,0, Кластер 1. |-------X-------| Основная точка 3.0, Кластер 2.

Все остальные точки не являются основными точками. Поскольку точка 2.0 не является основной точкой, она не соединяет два кластера. Один из кластеров будет иметь 4 члена, другой — только 3. — Предыдущий неподписанный комментарий добавлен 208.38.35.13 (обсуждение) 16:21, 25 февраля 2014 г.

При копировании данных с веб-сайта ( Stackoverflow ): [1] вы должны A) соблюдать авторские права и B) указывать источник. -- 188.98.200.186 (обсуждение) 11:31, 2 марта 2014 (UTC) [ ответить ]

RegionQuery: Включая контрольную точку P?

Текущий regionQuery также явно содержит заданную опорную точку P.

regionQuery(P, eps): return all points within P's eps-neighborhood (including P)

В оригинальной статье авторы заявляют:

Вызов SetOfPoints.regionQuery(Point, Eps) возвращает Eps -окрестность точки в SetOfPoints в виде списка точек.

В книге «Соседство» (теория_графов) утверждается:

... Описанная выше окрестность не включает в себя сам v и, более конкретно, является открытой окрестностью v; также можно определить окрестность, в которую включен сам v, называемую закрытой окрестностью и обозначаемую NG[v]. При указании без каких-либо уточнений предполагается, что окрестность является открытой. ...

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

-- Fretdf ( обсуждение ) 06:27, 20 августа 2014 (UTC) [ ответить ]

В контексте базы данных, например, при использовании R*-дерева , как рекомендуют авторы, запрос будет включать точку запроса. Она также является частью базы данных. -- Chire ( talk ) 11:24, 20 августа 2014 (UTC) [ ответить ]
Я также проверил, посмотрев на исходный код . Точка запроса включена (насколько я могу судить). -- Chire ( talk ) 13:01, 20 августа 2014 (UTC) [ ответить ]

Вчера я добавил ссылку на реализацию SPMF DBScan, и она была удалена IP-адресом "94.216.196.253" как "реклама". Однако SPMF — это известная библиотека интеллектуального анализа данных, используемая в более чем 160 научных работах (см. веб-сайт SPMF — страница цитат), и у нее много пользователей (более 70 000 посетителей веб-сайта в прошлом году). Поэтому уместно упомянуть, что она предлагает реализацию DBScan. Кроме того, интересно отметить, что IP-адрес, с которого была удалена ссылка на SPMF, находится в Мюнхене, Германия. Таким образом, она могла быть удалена членами библиотеки интеллектуального анализа данных ELKI, и это может выглядеть как конфликт интересов... Кстати, я основатель SPMF. — Предыдущий неподписанный комментарий, добавленный 139.103.155.68 (обсуждение) 19:31, 8 марта 2015 (UTC) [ ответить ]

Вы добавили это в три статьи (WEKA, k-means и эту, поэтому я отменил все три...):
Реализации GPL-V3 Java более 80 алгоритмов добычи данных . Он предлагает эффективную реализацию алгоритма DBScan на Java с использованием KD-Tree, которую легко интегрировать в другое программное обеспечение Java. Предоставляются графический интерфейс и интерфейс командной строки.
Это рекламный текст. — Предыдущий неподписанный комментарий добавлен 94.216.196.253 (обсуждение) 23:43, 8 марта 2015 (UTC) [ ответить ]
Библиотека SPMF актуальна. Если вы считаете, что есть проблема со стилем письма, что субъективно, я предлагаю переписать, а не удалять. Вам нужно удалить только ту часть, которую вы считаете неподходящей. Я верну текст для страницы Weka и K-Means, но перепишу его по-другому. Опять же, если у вас есть проблема с текстом, вы можете переписать. — Предыдущий неподписанный комментарий добавлен 99.252.71.54 ( обсуждение ) 01:17, 9 марта 2015 (UTC)[ отвечать ]

Дискретизация пространства для графовой аналогии

Я не уверен, насколько это важно для опытных читателей, но тот факт, что возможно непрерывное пространство рассматривается как граф, должен быть явным; я хотел бы поговорить о ребрах и путях только после того, как будут изложены следующие моменты: - каждая точка в пространстве является узлом - существует ребро (x,y), если d(x,y)<=e Спасибо! Reim ( talk ) 12:17, 1 июля 2015 (UTC) [ ответить ]

Отрицательное описание другого программного обеспечения

Я только что вернулся на эту страницу через несколько месяцев и прочитал, что описание SPMF было изменено на следующее: "* SPMF предлагает минималистичную реализацию GPL-V3 Java алгоритма DBSCAN только для евклидового расстояния с поддержкой KD-Tree , которая часто вообще не дает никакого результата". Согласно IP-адресу, похоже, что текст был переписан авторами программного обеспечения Elki. Утверждается, что он часто не дает никакого результата. Но я запускаю алгоритм, и он определенно дает результат. Если была обнаружена ошибка, которая не дает результата в некоторых случаях (что необходимо продемонстрировать), как насчет того, чтобы сообщить о ней, чтобы ее можно было исправить, как это делают большинство пользователей при обнаружении ошибки, вместо того, чтобы писать очень негативное описание в Википедии. Я имею в виду, что вы можете продвигать свое программное обеспечение, не описывая негативные вещи, подобные этим, о другом программном обеспечении. Кроме того, в SPMF предлагается более одной функции расстояния (подклассы DistanceFunction). Это просто не было четко упомянуто в документации SPMF. Документация и код были обновлены, чтобы сделать это более понятным и исправить это. Я исправил описание в статье Википедии. В будущем, если вы найдете ошибку, сообщите мне о ней, и я ее исправлю. Я основатель SPMF. ~~ 

Связь с алгоритмом «Друзья друзей».

Алгоритм широко используется в космологии для определения гало темной материи с помощью моделирования под названием FOF (friends-of-friends):

Алгоритм FOF был описан и изучен на странице 382, ​​раздел e) функции кратности

http://adsabs.harvard.edu/abs/1985ApJ...292..371D

Это использование имело место гораздо раньше, чем статья 1996 года.

Краткое обсуждение FOF и DBSCAN приведено в разделе «Связанные работы» на стр. 4

http://homes.cs.washington.edu/~magda/papers/kwon-ssdbm10.pdf

FOF — это особый случай, когда minPTS == 1. Хотя при FOF объекты с количеством точек менее (обычно 32) удаляются из каталога.

Исходя из этого, я предлагаю добавить предложение где-нибудь в этой статье:

 особый случай DBSCAN, известный как «Друзья друзей» Алгоритм был впервые предложен Дэвисом и др. в 1985 году и до сих пор широко используется в космологии.

Возражения?

Юй Фэн Рэйнвудман (обс.) 20:03, 18 сентября 2015 (UTC) [ ответить ]

Бессмысленный случай minPts < 2 также является частным случаем односвязной иерархической кластеризации , и этот вид кластеризации обсуждался уже Снитом в 1957 году. Я сомневаюсь, что "FOF" является первым. Это не что иное, как транзитивное замыкание соседнего отношения, и его вообще не стоит называть "алгоритмом" - транзитивные замыкания - это хорошо понятная и старая математическая концепция. Обсуждал ли Дэвис что-либо, чтобы сделать это быстрее? 93.204.126.210 (обсуждение) 08:42, 19 сентября 2015 (UTC) [ ответить ]
В статье это уже обсуждается:

Низкое значение minPts = 1 не имеет смысла, так как тогда каждая точка сама по себе уже будет кластером. При minPts = 2 результат будет таким же, как и при иерархической кластеризации с метрикой одиночной связи, с разрезом дендрограммы на высоте ε.

Другими словами, они используют кластеризацию с одной связью под названием «FOF» в космологии, а не DBSCAN. 93.204.126.210 (обсуждение) 08:45, 19 сентября 2015 (UTC) [ ответить ]

Шумовые точки против псевдокода

В функции DBSCAN в псевдокоде точка может быть помечена как шум, однако позже эта уже помеченная шумовая точка может стать частью кластера. Это также упоминается в оригинальной статье: "ClId (clusterId) точек, которые были помечены как ШУМ, могут быть изменены позже, если они достижимы по плотности из какой-то другой точки базы данных".

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

expandCluster(P, NeighborPts, C, eps, MinPts) { добавить P в кластер C для каждой точки P' в NeighborPts { если P' не посещается { отметить P' как посещённый NeighborPts' = regionQuery(P', eps) если sizeof(NeighborPts') >= MinPts NeighborPts = NeighborPts присоединились к NeighborPts' } если P' еще не является членом какого-либо кластера добавить P' к кластеру C если P' отмечен как ШУМ // < здесь снять отметку P' как NOISE // < здесь }}

DeVi (обсуждение) 11:39, 28 ноября 2016 (UTC) [ ответить ]

Я бы предпочел придерживаться опубликованного псевдокода, чем делать его версию в Википедии и в худшем случае вносить некоторые ошибки. Я также предпочел бы сохранить псевдокод коротким. Chire ( talk ) 16:23, 1 декабря 2016 (UTC) [ ответить ]

Сложность

Авторы алгоритма утверждают, что можно достичь DBSCAN с временной сложностью O(n log n) с реализацией на основе индексных структур. Однако продолжается дискуссия о том, является ли это утверждение обоснованным. Насколько мне известно, формального доказательства линейной сложности не существует.

Правка была отменена с комментарием "уже обсуждалось в статье. см. ссылки." -- Я не вижу ссылок на анализ сложности в статье. Линейное утверждение было подвергнуто сомнению, например, в:

Гунаван, А. и де Берг, М., 2013. Более быстрый алгоритм для DBSCAN. Магистерская диссертация.

Gan, J. и Tao, Y., 2015, май. DBSCAN снова: Mis-claim, un-fixability, and approx. В трудах международной конференции ACM SIGMOD 2015 года по управлению данными (стр. 519-530).

или даже:

Шуберт, Э., Сандер, Дж., Эстер, М., Кригель, Х. П. и Сюй, Х., 2017. DBSCAN снова и снова: почему и как вам следует (все еще) использовать DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), стр. 1-21. 91.193.208.197 (обсуждение) 14:30, 9 мая 2024 (UTC) [ ответить ]

никто из них не сомневается, что «худшая сложность времени выполнения остается O(n²)». - так что статья кажется актуальной, и я бы сказал, что последняя статья положила конец «продолжающейся дискуссии» - было ли что-то новое за последние 5 лет? Проверьте, поддерживает ли статья утверждение «O(n²) в худшем случае» статьи в Википедии, а затем просто повторно используйте цитату.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:DBSCAN&oldid=1223099242"