Порог слияния кластеров

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

Как мне найти правильное значение для использования в качестве порога??
(я могу использовать любое значение, и от него зависит результат, но мне нужно оптимальное значение)


cluster-analysis threshold kernel-density
person Federico Catalano    schedule 24.01.2013    source источник
comment
в будущем внимательно выбирайте теги: размещение неправильных тегов, скорее всего, сделает ваш вопрос невидимым для людей, которые могут знать, как на него ответить.   -  person Shai    schedule 24.01.2013
comment
Вы не думали об использовании ядра-таблетки: оно имеет лучшие свойства сходимости.   -  person Shai    schedule 24.01.2013
comment
ядро таблетки? я не знаю, что это такое... но моя проблема не касается свойств сходимости, мне нужно только установить соответствующий порог для объединения точек в кластер, только я не знаю, как выбрать лучшее значение! своего рода выбор k в k-средних)   -  person Federico Catalano    schedule 24.01.2013
comment
при кластеризации среднего сдвига каждый кластер представлен как отдельный бассейн притяжения в индуцированной плотности. Если близкие точки данных сходятся к разным модам функции плотности, значит, ваше ядро ​​недостаточно гладкое: у вас слишком много локальных мод. Вам нужно более локализованное и гладкое ядро. Одним из таких ядер является унифицированное ядро ​​с конечной поддержкой (также известное как ядро-таблетка).   -  person Shai    schedule 24.01.2013
comment
у меня есть трехмерная точка, поэтому, если одна точка, например, сходится к (11.345,23.896, 87.52), а другая точка к (11.789,23.24,87.25), они не принадлежат к одному и тому же кластеру, и проблема в том, что мое ядро недостаточно гладкий? (тогда точка должна быть точно такой же, верно?) приятно знать... где я могу найти несколько примеров об этом ядре-таблетке?   -  person Federico Catalano    schedule 24.01.2013
comment
ядро таблетки, вероятно, также известно как ядро ​​коробки. Действительно, это должно дать вам точно такую ​​же точку сходимости, когда гауссовское ядро ​​все еще будет варьироваться (поскольку оно не взвешивает соседей). Но пробовали ли вы использовать порог, такой как 0,1 * ширина ядра? Обычно это должно работать.   -  person Has QUIT--Anony-Mousse    schedule 25.01.2013
comment
@Shai, его вопрос: с гладким ядром, таким как гауссовское, когда два режима одинаковы?   -  person Has QUIT--Anony-Mousse    schedule 25.01.2013
comment
@ Anony-Mousse, и мой ответ: по определению два кластера одинаковы, когда они сходятся в одном и том же режиме. Если ваша оценка плотности слишком негладкая (я не знаю, как это называется), то у вас проблема в настройках: либо более сглаженная (более широкое гауссовское ядро), либо используйте другое ядро, более локализованное. В любом случае, вы должны знать, что делаете, простое набрасывание порогов на принципиальный алгоритм кластеризации не принесет вам пользы, если вы не понимаете, что происходит.   -  person Shai    schedule 25.01.2013
comment
Я не думаю, что дальнейшее увеличение пропускной способности ядра или использование глупого ядра — лучшая идея. Вместо этого нужно понимать, что некоторые режимы, возможно, придется считать одинаковыми. В любом случае, знаете ли вы формальное определение среднего сдвига для фактической кластеризации? Я видел только очень нечеткие описания принципа, но ничего, на чем можно было бы проверить реализацию.   -  person Has QUIT--Anony-Mousse    schedule 25.01.2013
comment
Для практического использования вы делаете хотите иметь средний сдвиг, когда кластер может состоять из нескольких мод, если они близки друг к другу.   -  person Has QUIT--Anony-Mousse    schedule 25.01.2013
comment
1) во-первых, я нашел ошибку в своем коде, точки останавливаются как минимум за один шаг до сходимости, и я это исправил! 2) единственный способ смоделировать математическую конвергенцию - это вычислить расстояние от точки до среднего значения окна, и, если это расстояние очень-очень мало (я установил 1e-3), это означает, что точка достигла сходимость, да?   -  person Federico Catalano    schedule 25.01.2013
comment
3) поскольку мы используем значение для проверки сходимости, точки не будут приводить все к одному и тому же (я имею в виду точно такое же) значение, может быть найдена небольшая разница (в моем примере в порядке 1e-3). 4) затем я установил второй порог на то же значение, что и первый, поэтому кластеризация зависит только от пропускной способности, которую я делаю правильно, или я все еще в темноте?   -  person Federico Catalano    schedule 25.01.2013

Ответы (1)


arrow_upward
0
arrow_downward

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

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

threshold = 0.5 * kernel_bandwidth
clusters = []
for p in shifted_points:
    cluster = findExistingClusterWithinThresholdOfPoint(p, clusters, threshold)
    if cluster == null:
        // create new cluster with p as its first point
        newCluster = [p]
        clusters.add(newCluster)
    else:
        // add p to cluster
        cluster.add(p)

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

Кажется, это работает очень хорошо. Надеюсь это поможет.

person mattnedrich    schedule 24.06.2014