ОБУЧЕНИЕ БЕЗ КОНТРОЛЯ
Понимание OPTICS и реализация с Python
В этом посте я кратко расскажу о том, как понять метод обучения без учителя, OPTICS и его реализацию в Python.
OPTICS означает Точки упорядочения для определения структуры кластеризации. Это на основе плотности алгоритм обучения без учителя, разработанный той же исследовательской группой, что и DBSCAN. Как обсуждалось в моем последнем посте, у DBSCAN есть главный недостаток, заключающийся в том, что он изо всех сил пытается идентифицировать кластеры в данных переменной плотности. Однако OPTICS не требует, чтобы плотность была одинаковой во всем наборе данных.
Один простой пример, иллюстрирующий преимущество OPTICS над DBSCAN, показан ниже.
В приведенном выше примере параметр постоянного расстояния eps в DBSCAN может рассматривать только точки в пределах eps друг от друга как соседние и, очевидно, пропускает кластер в правом нижнем углу рисунка. (Читайте этот пост для получения более подробной информации о параметрах в DBSCAN). Если бы мы использовали больший параметр eps, этот кластер можно было бы идентифицировать, но он также может объединить два других верхних кластера вместе. Таким образом, очень сложно предопределить идеальный eps в DBSCAN; однако в ОПТИКЕ нам не нужно об этом беспокоиться.
В этом посте я расскажу о том, как понять этот алгоритм и как реализовать его на Python. Надеюсь статья будет полезной.
Понимание ОПТИКА
Как вы помните, в DBSCAN применяется единственное ограничение расстояния, чтобы определить, близки ли две точки данных друг к другу (соседи) или нет. Но, как показано в приведенном выше примере, это может быть не идеальное решение, потому что «большое» расстояние в одном кластере может быть «коротким» расстоянием в другом.
Как и цены на жилье по всей стране, дом за 300 тысяч довольно дорогой в городе, где я живу, но дешевый на Манхэттене. Вот почему важно иметь в виду разные стандарты цен, когда мы смотрим на разные группы (кластеры) домов (точки данных).
Итак, в ОПТИКЕ, как мы можем принять во внимание разные «стандарты» расстояния между группами? Один из самых простых способов — просто сравнить с локальной средой (контекстом). В частности, если нас интересует, является ли расстояние от точки A до точки B большим или малым, мы можем сравнить расстояние (от A до B) со всеми попарными расстояниями в локальной среде.
Как видно из графика выше, расстояние от A до B не так уж велико по сравнению со всеми попарными расстояниями в этой локальной среде, верно? Итак, мы должны рассматривать A и B как соседей (A близок к B по расстоянию).
Возможно, вы уже заметили несколько вещей, которые не очень ясны в предыдущих шагах, чтобы определить, велико ли расстояние от A до B или нет. Например,
1. как определить «местный район»? и особенно когда нет такого четкого разделения данных как показано в примере?
2. Как определить, стоит ли исследовать местную среду? Что, если у меня нет достаточного парного расстояния для сравнения?
3. Действительно ли необходимо учитывать все попарные расстояния в области? Например, справедливо ли сравнивать расстояние от A до B с расстоянием от B до D (особенно когда мы уже знаем, что B и D кажутся противоположными границами локальной области)?
Если у вас есть вопросы, перечисленные выше, поздравляем! потому что вы думаете в правильном направлении!
Во-первых, чтобы определить «локальную область», нам нужны центр и радиус (те же понятия в DBSCAN). Например, точка А — это первая точка, которую мы хотим посетить, и мы хотим осмотреть окрестности точки А. Мы устанавливаем A в качестве центра и предопределенное значение r в качестве радиуса, а локальная область определяется как область внутри круга (показано ниже).
В приведенном выше примере графика, очевидно, r является хорошим выбором радиуса вокруг точки A, потому что он идеально покрывает «локальный кластер» точек данных. Однако на самом деле мы не видим всей картины данных или у нас нет тех четких разделений «локальных кластеров». Таким образом, обычно рекомендуется устанавливать r как относительно большое значение, чтобы избежать выделения очень маленькой области, когда вы стоите в точке A.
Во-вторых, чтобы определить, стоит ли исследовать область, мы устанавливаем минимальное количество точек данных в качестве критерия. Например, «локальную область», определенную на предыдущем шаге, стоит исследовать только в том случае, если имеется не менее N точек данных (включая сам центр).
На приведенном выше графике мы установили N = 3, что означает, что область стоит исследовать только в том случае, если имеется более 3 точек данных. Итак, область вокруг точки P мы не будем рассматривать как «локальную область», потому что она не имеет соседей и мы не можем сравнивать никакие попарные расстояния.
В-третьих, как вы могли заметить, нет необходимости вычислять все попарные расстояния в пределах «локальной области», когда мы хотим определить, велико ли расстояние от A до B или нет. Давайте снова посмотрим на попарные расстояния в локальной области,
Как показано на левом графике выше, точки A и B являются «смежными» на графике, а точки B и D — нет. Нет никаких сомнений в том, что AB короче BD, поэтому несправедливо и нецелесообразно сравнивать расстояние от A до B с расстоянием от B до D. Есть ли у нас способ рассматривать только эти расстояния между «соседними» точками (как показано на рисунке). на правом графике выше)?
На самом деле, сокращение сравнений слева направо на графике выше очень идеально, потому что в реальности у нас больше точек данных с более сложным расположением, и нам сложно вручную выбрать те края, которые будут сравниваться с расстоянием от A до B.
В качестве альтернативы, можем ли мы решить проблему итерационным способом? например, мы посещаем точки в локальной области одну за другой, и каждый раз мы только записываем расстояние от текущей точки до соседних с ней точек, а затем переходим к следующей точке. Посетив все точки области, мы зафиксировали все соседние расстояния. Таким образом, нам не нужно заранее видеть всю картину расстояний или выбирать их вручную после посещения всех попарных расстояний.
Это хороший способ, но можем ли мы еще больше уменьшить сложность?
Хорошо, я не хочу, чтобы вы чувствовали себя потерянными, поэтому позвольте мне еще раз изложить проблему. Мы хотим сравнить расстояние между A и B со всеми другими попарно «соседними» расстояниями, чтобы определить, близки ли A и B друг к другу.
Вы все еще помните, почему мы хотели знать, больше или меньше расстояние между A и B по сравнению с другими попарными расстояниями? Мы хотим знать, принадлежит ли B к текущему посещению кластера точек данных (кластер с центром вокруг точки A). Другими словами, мы хотим использовать метрику расстояния, чтобы определить, является ли точка достижимой для кластера точек данных.
Достижимый или недостижимый. Хм… Можем ли мы присвоить каждой точке оценку достижимости? Это было бы намного проще? Большой показатель достижимости находится где-то, чего кластер не может достичь, а малый показатель достижимости находится где-то достижимом внутри кластера.
Не волнуйтесь, если вы чувствуете себя немного потерянным здесь. Пожалуйста, следуйте за мной, чтобы пройти весь процесс, и я уверен, что вы поймете, что я говорю.
Вот шаги:
Во-первых, мы посещаем локальную область вокруг точки A. Мы вычисляем расстояния от центральной точки до всех других точек области, AB, AC, AD, AE и AF, и записываем их. Мы упорядочиваем записанные расстояния и рассматриваем эти расстояния как текущую оценку досягаемости. Нам также нужно протолкнуть A в окончательный список очков, чтобы не посещать его снова. В качестве начальной точки A не присвоена оценка, поэтому давайте оставим ее пустой (или мы можем присвоить ей очень большое значение).
Затем мы посещаем точку с наименьшим показателем достижимости (точка D), которая также является ближайшей точкой к текущей центральной точке. Мы используем эту новую точку в качестве центральной точки и вычисляем расстояния от текущей центральной точки до других точек, которые не были посещены в ее окрестности.
Как показано на графике выше, мы вычисляем только расстояние от D до C и от D до E, потому что A уже был посещен (нет необходимости вычислять снова). Затем мы обновляем текущий список показателей достижимости меньшим значением, если оно доступно. Здесь E имеет новую оценку 1, которая меньше, чем на предыдущем шаге (E=1,4 на шаге 1). Итак, мы обновляем показатель Е. Но точка C имеет больший балл, чем первый шаг, а это означает, что точка C более достижима из точки A, чем из точки D. Таким образом, мы сохраняем оценку точки C неизменной на этом шаге. Без исследования B и F не обновляются на этом этапе.
Помните, что мы хотим записывать наименьшую оценку достижимости каждой точки, чтобы утверждать, принадлежит ли она к текущему кластеру или нет, поэтому мы не можем использовать большую оценку для C, когда доступна меньшая оценка. Будет несправедливо по отношению к точке C, если мы исключим ее из кластера только потому, что мы не использовали ее лучшую оценку.
В-третьих, мы переходим к E, потому что E имеет наименьший показатель достижимости в текущем списке.
Как показано на графике выше, нам нужно только рассчитать расстояние от E до F, поскольку A и D уже были выполнены на предыдущих шагах. Мы получаем немного меньшую оценку достижимости для F (F = 1,9), поэтому мы обновляем ее в текущем списке оценок.
Затем точка B имеет наименьший показатель достижимости, поэтому мы используем ее в качестве текущей центральной точки на этом шаге.
На шаге 4 показатель достижимости не обновляется, потому что мы не можем найти меньшие значения. Затем мы переходим к шагу 5 с C в качестве центральной точки.
А затем мы используем точку F в качестве центральной точки и выводим показатель достижимости F в список.
До сих пор мы посетили все шесть точек в текущем районе и получили окончательный список баллов досягаемости. Таким образом, мы не пропустили ни одного попарного расстояния от «соседних» точек. Кроме того, мы получили упорядоченный список оценок, которые измеряют, насколько достижимы точки из исследуемого кластера.
Является ли описанная выше процедура намного проще, чем вычисление всех попарных расстояний в области?
Фактически, мы можем применить эту процедуру ко всему набору данных. Например, после посещения F в качестве центральной точки у нас нет других непосещенных точек в локальной области. Затем следующей центральной точкой может быть любая другая точка данных в наборе данных.
Если мы нарисуем один из возможных полных путей, соединяющих центральные точки в порядке посещения, это может быть что-то вроде графика ниже.
Вы можете представить путь как жадную змею, которая хочет съесть все шары (точки данных) на графике, всегда кусая следующий ближайший шар (в списке очков).
У единственной точки в правом верхнем углу есть один «сосед» с предопределенной окрестностью среднего кластера (с радиусом r), поэтому она была посещена на последнем шаге для оранжевой части. Однако точка в левом нижнем углу вообще не имеет «соседей», поэтому она никогда не исследовалась, потому что не соответствует нашим критериям, согласно которым область стоит исследовать только в том случае, если она имеет не менее N = 3 соседей (включая себя). .
Сделав все это, мы получим список оценок достижимости. Что мы можем с ним сделать? Не забывайте, что наша цель — определить, принадлежит ли точка локальному кластеру или нет. Например, вот список результатов, который мы получаем,
Если мы нанесем счет в виде гистограммы, мы можем визуализировать их, как показано ниже.
Возможно, вы уже заметили, что три долины на гистограмме справа соответствуют трем кластерам слева. Итак, используя окончательный список оценок достижимости, мы можем обнаружить кластеры, даже если они имеют разную плотность.
Кроме того, вы можете обнаружить, что более плотный кластер (коричневый в верхнем левом углу левой панели) соответствует более глубокой долине на гистограмме (долина, обведенная коричневым цветом на правой панели). И более редкий кластер (синий кластер в правом нижнем углу левой панели) соответствует относительно более мелкой долине (самый левый кружок на гистограмме).
Помните, что мы определяем район, который стоит посетить, как район, в котором есть как минимум 3 соседа. Мы можем рассматривать трех соседей как ядро соседства. И на самом деле нас не слишком волнуют точки, если они расположены в ядре, потому что они явно принадлежат кластеру. Таким образом, обычно для всех точек внутри ядра мы устанавливаем размер ядра в качестве показателя их достижимости.
Например, на приведенном ниже графике есть шесть точек в области с центром в A и радиусом r. Ядро области формируется точками A, D и E, поскольку D и E являются двумя ближайшими точками к A (N = 3). Мы знаем, что D находится внутри ядра, поэтому нам не нужно записывать точное расстояние между A и D (крошечное значение). Мы можем просто присвоить размер ядра (радиус ядра) как оценку точки D.
После аппроксимации количества точек в ядре размером ядра наименьшее значение, которое мы можем получить из окончательного списка показателей достижимости, — это размер ядра. Зачем мы это делаем? Во-первых, чтобы не записывать так много бесполезных крошечных значений; во-вторых, чтобы впадины на гистограмме выглядели более сглаженными (как показано ниже).
Никакой концепции из ОПТИКИ я не использовал, но описанная выше процедура и есть именно ОПТИКА. Вы уже поняли ОПТИКУ, если дошли до конца.
Позвольте мне просто взять некоторые описания из учебников и кратко проиллюстрировать, как они встроены в мое объяснение выше.
Алгоритм ОПТИКА
Большинство учебников начинаются со слов: «Основная идея OPTICS похожа на DBSCAN, но в ней на два понятия больше, чем в DBSCAN». Позвольте мне использовать несколько официальных слов, чтобы описать эти две концепции в ОПТИКЕ, и сказать вам, что эти сложные термины на самом деле относятся к моему простому описанию выше.
В ОПТИКЕ каждой точке назначается центральное расстояние, которое описывает расстояние до MinPts ближайшей точки, и расстояние достижимости другой точки o от точка p, которая представляет собой либо расстояние между o и p, либо центральное расстояние p, в зависимости от того, что больше.
Расстояние ядра — это просто размер ядра, как я описал, который просто служит порогом для аппроксимации расстояний между точками внутри ядра. Расстояние достижимости — это просто оценка достижимости, которую мы записываем для каждой точки.
А вот и псевдокод алгоритма из учебников.
function OPTICS(DB, eps, MinPts) is
for each point p of DB do
p.reachability-distance = UNDEFINED
for each unprocessed point p of DB do
N = getNeighbors(p, eps)
mark p as processed
output p to the ordered list
if core-distance(p, eps, MinPts) != UNDEFINED then
Seeds = empty priority queue
update(N, p, Seeds, eps, MinPts)
for each next q in Seeds do
N' = getNeighbors(q, eps)
mark q as processed
output q to the ordered list
if core-distance(q, eps, MinPts) != UNDEFINED do
update(N', q, Seeds, eps, MinPts)
Я знаю, что это трудно понять. Итак, игнорируйте это, это точно такие же шаги, которые я использовал в предыдущих абзацах. Конечным результатом OPTICS здесь является список расстояний достижимости, который точно соответствует списку показателей достижимости, который мы видели ранее.
На самом деле OPTICS останавливается, когда генерируется гистограмма расстояния досягаемости. Последний шаг кластеризации необходимо выполнить вручную, поэтому, строго говоря, OPTICS — это НЕ метод кластеризации, а метод отображения структуры набора данных.
Реализация на Python
Реализация OPTICS в Python очень проста,
from sklearn.cluster import OPTICS optics_clustering = OPTICS(min_samples=3).fit(X)
Если вы хотите узнать окончательные метки точек данных, используйте
optics_clustering.labels_
Легко, верно?
Вы могли заметить, что в коде реализации OPTICS нет параметра eps. Это потому, что этот параметр на самом деле не влияет на результат, если он не очень мал. Представьте это как максимальное поле зрения, когда вы стоите в точке А на самом первом шаге. Почему? если еще раз просмотреть пост, то легко получить ответ.
Вот и все! Если вам понравилось читать мой пост. Пожалуйста, подпишитесь на мой аккаунт Medium!
Ваше здоровье!
