Кластеризация - Интуиция за теоремой Клейнберга о невозможности

17

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

Вкратце и неформально, три описания, которые он выделяет, таковы:

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

Вопросов:

(1) Существует ли хорошая интуиция, геометрическая картина, которая может показать несоответствие между этими тремя критериями?

(2) Это относится к техническим деталям к статье. Вам нужно будет прочитать ссылку выше, чтобы понять эту часть вопроса.

В статье доказательство теоремы 3.1 немного затруднительно для меня в точках. Я застрял в: «Пусть е - функция кластеризации, удовлетворяющая согласованности. Мы утверждаем, что для любого разбиения ΓАссортимент(е) существуют положительные действительные числа a<б такие что пара (a,b) есть Γ - принуждение «.

Я не понимаю, как это может иметь место ... Разве раздел ниже контр-примера, где a>b (т.е. минимальное расстояние между кластерами больше, чем максимальное расстояние внутри кластеров)?

контрпример?

Изменить: это явно не контрпример, я запутался (см. Ответы).


Другие документы:

Алекс Уильямс
источник
Что касается «согласованности»: эта характеристика интуитивно желательна только тогда, когда кластеры уже хорошо разделены. Когда их нет, возникает проблема с количеством кластеров в данных - для анализа, поскольку они не контролируются, это вопрос. Тогда вполне нормально ожидать, что, когда вы постепенно добавляете расстояние между кластерами (как они были сгенерированы вами), анализ изменяет назначения, которые он делает во время процесса кластеризации.
ttnphns
Что касается «богатства»: извините, я не понял, что это значит (как минимум, как вы это выразили). Алгоритмы кластеризации многочисленны, как вы можете ожидать, что все они соответствуют определенным причудливым требованиям?
ttnphns
Относительно вашей картины: специальные методы кластеризации необходимы для распознавания такого шаблона. Традиционные / оригинальные методы кластеризации проистекают из биологии и социологии, где кластеры представляют собой более или менее плотные сфероидальные «островки», а не кольца атоллов. Эти методы не могут требовать справиться с данными на картинке.
ttnphns
Вы также можете быть заинтересованы в: Эстивилль-Кастро, Владимир. «Почему так много кластерных алгоритмов: позиционный документ». Информационный бюллетень ACM SIGKDD 4.1 (2002): 65-75.
Аноним-Мусс
Я не читал газету. Но во многих алгоритмах кластеризации у вас есть некоторый порог расстояния (например, DBSCAN, иерархическая кластеризация). Если вы масштабируете расстояния, то вам также необходимо соответствующим образом масштабировать ваш порог. Таким образом, я не согласен с его требованием о масштабной инвариантности. Я также не согласен с богатством. Не каждый раздел должен быть правильным решением для каждого алгоритма. Есть миллионы случайных разделов.
Аноним-Мусс

Ответы:

11

Так или иначе, каждый алгоритм кластеризации опирается на некоторое понятие «близости» точек. Интуитивно понятно, что вы можете использовать либо относительное (масштабно-инвариантное) понятие, либо абсолютное (согласованное) понятие близости, но не оба .

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

Наглядный пример

Предположим, у нас есть два набора и S 2 по 270 точек каждый, расположенных в плоскости следующим образом:S1S2270

два набора по 270 очков

Вы можете не увидеть точек на этих фотографиях, но это только потому, что многие точки очень близки друг к другу. Мы видим больше точек, когда мы увеличиваем:270

установить 1 с зумом

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

набор 2 с зумом

Если вы верите в абсолютное представление о близости или согласованности, вы все равно будете утверждать, что, независимо от того, что вы только что видели под микроскопом, состоит только из трех кластеров. Действительно, единственная разница между S 1 и S 2 заключается в том, что в каждом кластере некоторые точки теперь находятся ближе друг к другу. Если, с другой стороны, вы верите в относительное понятие близости или в масштабную инвариантность, вы будете склонны утверждать, что S 2 состоит не из 3, а из 3 × 3 = 9 кластеров. Ни одна из этих точек зрения не ошибочна, но вы должны сделать выбор так или иначе.S2S1S2S233×3=9

Случай изометрической инвариантности

Если вы сравните приведенную выше интуицию с теоремой Клейнберга, вы обнаружите, что они немного расходятся. Действительно, теорема Кляйнберга говорит о том, что вы можете достичь масштабной инвариантности и согласованности одновременно, если вам не важно третье свойство, называемое богатством. Однако богатство - не единственное свойство, которое вы теряете, если одновременно настаиваете на неизменности масштаба и последовательности. Вы также теряете другое, более фундаментальное свойство: изометрия-инвариантность. Это свойство, которым я не хотел бы жертвовать. Поскольку этого нет в статье Кляйнберга, я остановлюсь на этом на мгновение.

Короче говоря, алгоритм кластеризации является изометрическим инвариантом, если его выходные данные зависят только от расстояний между точками, а не от какой-либо дополнительной информации, такой как метки, которые вы прикрепляете к своим точкам, или от порядка, который вы накладываете на свои точки. Я надеюсь, что это звучит как очень мягкое и очень естественное состояние. Все алгоритмы, обсуждаемые в статье Клейнберга, являются изометрическими инвариантами, за исключением алгоритма одиночной связи с условием остановки кластера. Согласно описанию Кляйнберга, этот алгоритм использует лексикографическое упорядочение точек, поэтому его вывод может действительно зависеть от того, как вы их пометите. Например, для набора из трех равноотстоящих точек вывод алгоритма одиночной связи с 2k2- условие остановки кластера даст разные ответы в зависимости от того, помечаете ли вы свои три точки как «кошка», «собака», «мышь» (c <d <m) или как «Tom», «Spike», «Jerry» (J <S <T):

кластеризация {кошка, собака, мышь} против {Том, Спайк, Джерри}

Это неестественное поведение, конечно, можно легко исправить, заменив условие остановки кластера на «условие остановки ( k ) -кластера». Идея состоит в том, чтобы просто не разрывать связи между равноотстоящими точками, а также прекратить слияние кластеров, как только мы достигнем не более k кластеров. Этот отремонтированный алгоритм будет все еще производить k кластеров большую часть времени, и он будет инвариантным по изометрии и инвариантным по масштабу. В соответствии с приведенной выше интуицией, однако, она больше не будет последовательной.k(k) kk

Для точного определения изометрической инвариантности напомним, что Клейнберг определяет алгоритм кластеризации на конечном множестве как отображение, которое присваивает каждой метрике на S разбиение S : Γ : { метрики на  S } { разбиения  S }SSS изометрией я между двумя метрики d и d ' на S является перестановкой я : S S такоечто d ' ( я ( х ) , я ( у ) ) = г ( х , у ) для всех точки х и у в S .

Γ:{metrics on S}{partitions of S}dΓ(d)
iddSi:SSd(i(x),i(y))=d(x,y)xyS

Γddii(x)i(y)Γ(d)xyΓ(d)

SSS

набор точек на плоскости и два ее поворота

Вариант теоремы Клейнберга

Приведенная выше интуиция уловлена ​​следующим вариантом теоремы Клейнберга.

Теорема: не существует нетривиального изометрически-инвариантного алгоритма кластеризации, который был бы одновременно согласованным и масштабно-инвариантным.

Здесь под тривиальным алгоритмом кластеризации я подразумеваю один из следующих двух алгоритмов:

  1. S

  2. S

Утверждается, что эти глупые алгоритмы являются единственными двумя алгоритмами, инвариантными к изометрии, которые являются согласованными и масштабно-инвариантными.

SΓdSd(x,y)=1xySΓΓ(d)Γ(d)Γ(d)Γ(d)dS1dΓ(d)=Γ(d)ΓΓ(d)dS1Γ(d)=Γ(d)Γ

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

Коммуникативная алгебра
источник
7

Это та интуиция, которую я придумал (фрагмент из моего поста здесь ).

введите описание изображения здесь

d1d2d3d2d3d1d1d3d2d3

Алекс Уильямс
источник
Вы имеете в виду внизу слева для d2? Одна приятная вещь в вашей диаграмме - она ​​показывает, что согласованность не является обычно желательным свойством (или что она слишком слабо сформулирована).
xan
Да внизу слева, отредактировал ответ соответственно. Благодарность!
Алекс Уильямс
Прежде чем я полностью понял ваш ответ, я придумал логику, которая оказывается вашей двойственной: начните с кластеризации, где все точки находятся в одном кластере. Превратите его в любое другое расположение, свернув его в миниатюрную версию любого другого расположения и увеличив масштаб до полноразмерного варианта другого расположения.
xan