Медоид

Медоиды - это репрезентативные объекты набора данных или кластера в наборе данных, среднее отличие которых от всех объектов в кластере минимально. ^[1] Медоиды похожи по концепции на средства или центроиды , но медоиды всегда могут быть членами набора данных. Медоиды чаще всего используются для данных, когда невозможно определить среднее значение или центроид, например для графиков. Они также используются в контекстах, где центроид не является репрезентативным для набора данных, как на изображениях, трехмерных траекториях и экспрессии генов ^[2](где пока данные разрежены, медоида быть не обязательно). Они также интересны при желании найти представителя, использующего некоторое расстояние, отличное от квадрата евклидова расстояния (например, в рейтингах фильмов).

Для некоторых наборов данных может быть более одного медоида, как в случае с медианами. Распространенным применением medoid является алгоритм кластеризации k-medoids , который похож на алгоритм k-средних , но работает, когда среднее значение или центроид не определены. Этот алгоритм в основном работает следующим образом. Сначала случайным образом выбирается набор медоидов. Во-вторых, вычисляются расстояния до других точек. В-третьих, данные сгруппированы в соответствии с медоидом, на который они наиболее похожи. В-четвертых, набор медоидов оптимизируется с помощью итеративного процесса.

Обратите внимание, что медоид не эквивалентен медиане , геометрической медиане или центроиду . Медиана определяется только на 1-мерных данных, и это минимизирует только несходство к другим точкам для метрик , индуцированных нормой (таких , как Manhattan расстояние или евклидова расстояния ). Геометрическая медианный определена в любом измерении, но не обязательно является точкой внутри исходного набора данных.

Определение [ править ]

Позвольте быть набором точек в пространстве с функцией расстояния d. Медоид определяется как${\ textstyle {\ mathcal {X}}: = \ {x_ {1}, x_ {2}, \ dots, x_ {n} \}}$${\ textstyle n}$

${\ displaystyle x _ {\ text {medoid}} = \ arg \ min _ {y \ in {\ mathcal {X}}} \ sum _ {i = 1} ^ {n} d (y, x_ {i}) .}$

Алгоритмы вычисления медоидов [ править ]

Из приведенного выше определения ясно, что медоид можно вычислить после вычисления всех попарных расстояний между точками в ансамбле. Это потребует оценки расстояния. В худшем случае невозможно вычислить medoid с меньшим количеством оценок расстояния. ^{[3] [4]} Однако существует множество подходов, которые позволяют нам вычислять медоиды точно или приблизительно за субквадратичное время при различных статистических моделях.${\ textstyle O (п ^ {2})}$

Если точки лежат на реальной линии, вычисление медианы сводится к вычислению медианы, что может быть выполнено с помощью алгоритма быстрого выбора Хоара. ^[5] Однако в реальных пространствах более высокой размерности алгоритм линейного времени не известен. RAND ^[6] - это алгоритм, который оценивает среднее расстояние от каждой точки до всех других точек путем выборки случайного подмножества других точек. Для аппроксимации медиоида с высокой вероятностью требуется вычисление всего расстояния , где - максимальное расстояние между двумя точками в ансамбле. Обратите внимание, что RAND - это алгоритм аппроксимации и, более того, не может${\ textstyle O (п)}$${\ textstyle O \ left ({\ frac {n \ log n} {\ epsilon ^ {2}}} \ right)}$${\textstyle (1+\epsilon \Delta )}$${\textstyle \Delta }$${\textstyle \Delta }$ быть известным априори.

RAND был использован TOPRANK ^[7], который использует оценки, полученные RAND, чтобы сосредоточиться на небольшом подмножестве точек-кандидатов, точно оценивает среднее расстояние до этих точек и выбирает минимальное из них. TOPRANK нуждается в вычислениях расстояний, чтобы найти точный медоид с высокой вероятностью в предположении распределения на средних расстояниях.${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$

trimed ^[3] представляет алгоритм поиска медоида с оценками расстояния при предположении распределения по точкам. Алгоритм использует неравенство треугольника, чтобы сократить пространство поиска.${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$

Meddit ^[4] использует связь вычисления medoid с многорукими бандитами и использует алгоритм с верхним доверительным интервалом, чтобы получить алгоритм, который оценивает расстояние при статистических допущениях по точкам.${\textstyle O(n\log n)}$

Коррелированное последовательное сокращение вдвое ^[8] также использует методы многорукого бандита, улучшая Meddit . Используя корреляционную структуру в задаче, алгоритм может обеспечить резкое улучшение (обычно примерно на 1-2 порядка) как количества необходимых вычислений расстояния, так и времени настенных часов.

Реализации [ править ]

Реализацию RAND , TOPRANK и trimed можно найти здесь . Реализацию Meddit можно найти здесь и здесь . Реализацию коррелированного последовательного сокращения вдвое можно найти здесь .

См. Также [ править ]

• k-medoids
• алгоритм k-средних
• Центроид

Ссылки [ править ]