Как следует из названия, ограниченная кластеризация - это исследование и разработка алгоритмов кластеризации, которые пытаются объединить предыдущие знания данных в процессе кластеризации.

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

Введение

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

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

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

  • (a, b) ∈ необходимо связать ⊆ D x D ↔ экземпляр a и b должен быть в одном кластере
  • (a, b) ∈ не может установить связь ⊆ D x D ↔ экземпляр a и b не должны находиться в одном кластере
  • Обязательная ссылка - это симметричное, рефлексивное и транзитивное отношение (это отношение эквивалентности).
  • Отношение невозможности связывания является симметричным отношением
  • Если (a, b) ∈ must-link ∧ (b, c) ∈ cannot-link → (a, c) ∈ cannot- ссылка на сайт

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

Было предложено множество алгоритмов для рассмотрения этих типов ограничений, но в этой статье я сосредоточусь на двух, которые я считаю наиболее известными: COP-KMeans и PCK-Means. Эти алгоритмы, как следует из названия, представляют собой разновидность хорошо известного алгоритма кластеризации K-средних, единственные различия заключаются в одном из этапов исходного алгоритма K-средних.

Ограниченные K-средние (COP-KMeans)

Он рассматривает ограничения как жесткие, их необходимо соблюдать. Результирующие кластеры, если алгоритм не дает сбоев, будут соответствовать ограничениям, заданным пользователем.

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

Другая проблема с COP-KMeans заключается в том, что этап назначения (1) зависит от порядка, в котором посещаются объекты. Если ограничений нет, COP-KMeans эквивалентно стандартному K-среднему.

Парные ограниченные K-средние ( PC-K-средние)

Этот алгоритм можно рассматривать как упрощенную версию алгоритма COP-KMeans. В этом алгоритме может случиться так, что некоторые из начальных ограничений не будут удовлетворены в конце алгоритма, алгоритм не потерпит неудачу, если некоторые из ограничений не выполнятся. В статье PC-KMeans также предлагается алгоритм для выбора наиболее информативных ограничений, которые будут использоваться на этапе кластеризации, но в этой статье я решил выделить только алгоритм кластеризации.

Если у нас есть некоторая информация о том, насколько важны отдельные ограничения, мы можем различать значения условий наказания w_ {i, j} и \ hat {w} _ {i, j}, но как правило, эта информация недоступна, и все они имеют одно и то же значение .

Как и в случае алгоритма COP-KMeans, в алгоритме PC-KMeans этап назначения (1) зависит от порядка, в котором посещаются объекты. Другая проблема в том, что нам нужно выбрать больше параметров, сроки штрафов.

Если условия штрафов установлены на ноль, PC-KMeans эквивалентен стандартным K-средним.

использованная литература

Вагстафф К., Карди К., Роджерс С. и Шредл С. (2001, июнь). Ограниченная кластеризация K-средних с фоновыми знаниями. В ICML (том 1, стр. 577–584).

Басу, С., Банерджи, А., и Муни, Р. Дж. (2004, апрель). Активный полунадзор для парной кластеризации с ограничениями. В материалах Международной конференции SIAM 2004 г. по интеллектуальному анализу данных (стр. 333–344). Общество промышленной и прикладной математики.

Благодарности

Историю написали:

Федерико Риччиути, специалист по анализу данных

Не стесняйтесь добавлять меня в Linkedin:
linkedin.com/in/federico-ricciuti-b490ab59

В сотрудничестве с: