Estive pensando em escrever um post sobre essa interessante análise de Kleinberg (2002) que explora a dificuldade de agrupar. Kleinberg descreve três desiderata aparentemente intuitivos para uma função de agrupamento e prova que essa função não existe. Existem muitos algoritmos de cluster que satisfazem dois dos três critérios; no entanto, nenhuma função pode satisfazer todos os três simultaneamente.

Resumidamente e informalmente, os três desiderata que ele descreve são:

• Invariância de escala : se transformarmos os dados para que tudo seja estendido igualmente em todas as direções, o resultado do cluster não deverá mudar.
• Consistência : se esticarmos os dados para que as distâncias entre os clusters aumentem e / ou as distâncias dentro dos clusters diminuam, o resultado do cluster não deverá mudar.
• Riqueza : a função de agrupamento deve, teoricamente, ser capaz de produzir qualquer partição / agrupamento arbitrário de pontos de dados (na ausência de conhecer a distância entre pares de dois pontos)

Questões:

(1) Existe uma boa intuição, quadro geométrico que pode mostrar a inconsistência entre esses três critérios?

(2) Refere-se a detalhes técnicos do artigo. Você precisará ler o link acima para entender esta parte da pergunta.

No artigo, a prova do teorema 3.1 é um pouco difícil de seguir em alguns pontos. Estou preso em: "Seja uma função de agrupamento que satisfaça a consistência. Afirmamos que para qualquer partição , existem números reais positivos tais que o par é force. "Γ ∈ Gama ( f ) a < b ( a , b ) $f$$\Gamma \in \text{Range}(f)$$a < b$$(a, b)$$\Gamma$

Não vejo como isso pode ser o caso ... A partição abaixo não é um contra-exemplo em que (ou seja, a distância mínima entre os clusters é maior que a distância máxima dentro dos clusters)?$a > b$

Edit: isso claramente não é um contra-exemplo, eu estava me confundindo (ver respostas).

• Ackerman e Ben-David (2009). Medidas de qualidade de clustering: um conjunto de axiomas para clustering
  • Salienta alguns problemas com o axioma "consistência"

De uma forma ou de outra, todo algoritmo de agrupamento depende de alguma noção de "proximidade" de pontos. Parece intuitivamente claro que você pode usar uma noção relativa (invariável à escala) ou uma noção absoluta (consistente) de proximidade, mas não as duas .

Primeiro tentarei ilustrar isso com um exemplo, e depois continuarei dizendo como essa intuição se encaixa no Teorema de Kleinberg.

Um exemplo ilustrativo

Suponha que temos dois conjuntos e S 2 de 270 pontos cada, organizados no plano assim:$S_1$$S_2$$270$

$\hskip{6em}$

Você pode não ver pontos em nenhuma dessas fotos, mas isso ocorre porque muitos dos pontos estão muito próximos. Vemos mais pontos quando aumentamos o zoom:$270$

$\hskip{3em}$

Você provavelmente concordará espontaneamente que, em ambos os conjuntos de dados, os pontos são organizados em três grupos. No entanto, acontece que, se você ampliar um dos três grupos de , verá o seguinte:$S_2$

$\hskip{3em}$

Se você acredita em uma noção absoluta de proximidade, ou na consistência, você ainda sustentam que, independentemente do que você acabou de ver sob o microscópio, consiste em apenas três clusters. De fato, a única diferença entre S 1 e S 2 é que, dentro de cada cluster, alguns pontos estão agora mais próximos. Se, por outro lado, você acredita em uma noção relativa de proximidade ou em invariância de escala, sente-se inclinado a argumentar que S 2 consiste não de 3, mas de 3 × 3 = 9 aglomerados. Nenhum desses pontos de vista está errado, mas você precisa fazer uma escolha de uma maneira ou de outra.$S_2$$S_1$$S_2$$S_2$$3$$3×3 = 9$

Um caso de invariância isométrica

Se você comparar a intuição acima com o Teorema de Kleinberg, descobrirá que elas estão ligeiramente em desacordo. De fato, o Teorema de Kleinberg parece dizer que você pode obter invariância e consistência de escala simultaneamente, desde que não se importe com uma terceira propriedade chamada riqueza. No entanto, a riqueza não é a única propriedade a ser perdida se você insistir simultaneamente na invariância e consistência da escala. Você também perde outra propriedade mais fundamental: invariância isométrica. Esta é uma propriedade que eu não estaria disposto a sacrificar. Como não aparece no artigo de Kleinberg, vou me debruçar sobre isso por um momento.

Em resumo, um algoritmo de agrupamento é isométrico invariante se sua saída depende apenas das distâncias entre os pontos, e não de algumas informações adicionais, como etiquetas que você anexa aos seus pontos ou de uma ordem que você impõe aos seus pontos. Espero que isso pareça uma condição muito leve e muito natural. Todos os algoritmos discutidos no artigo de Kleinberg são isométricos invariantes, exceto o algoritmo de ligação única com a condição de parada do cluster . De acordo com a descrição de Kleinberg, esse algoritmo usa uma ordem lexicográfica dos pontos, portanto sua saída pode realmente depender de como você os rotula. Por exemplo, para um conjunto de três pontos equidistantes, a saída do algoritmo de ligação única com os $k$$2$A condição de parada do cluster fornecerá respostas diferentes, dependendo de você rotular seus três pontos como "gato", "cachorro", "rato" (c <d <m) ou como "Tom", "Spike", "Jerry" (J <S <T):

$\hskip{6em}$

É claro que esse comportamento não natural pode ser facilmente reparado substituindo a condição de parada do cluster por uma “condição de parada do cluster k ( ≤ k ) ”. A idéia é simplesmente não romper os laços entre pontos equidistantes e parar de fundir clusters assim que atingirmos o máximo de k clusters. Esse algoritmo reparado ainda produzirá k clusters na maioria das vezes, e será isométrico invariante e escalar invariante. De acordo com a intuição acima, ela não será mais consistente.$k$$(≤ k)$ $k$$k$

$S$$S$$S$

Definição: Um algoritmo de agrupamento é isométrica invariante se satisfizer a seguinte condição: para qualquer métrica e e qualquer isometria entre elas, os pontos e estão no mesmo cluster de se e somente se os pontos originais e estiverem no mesmo agrupamento de .$Γ$$d$$d'$$i$$i(x)$$i(y)$$Γ(d')$$x$$y$$Γ(d)$

Quando pensamos em algoritmos de agrupamento, geralmente identificamos o conjunto abstrato com um conjunto concreto de pontos no plano ou em algum outro espaço ambiente e imaginamos variar a métrica em ao mover os pontos de ao redor. De fato, esse é o ponto de vista que adotamos no exemplo ilustrativo acima. Nesse contexto, invariância isométrica significa que nosso algoritmo de agrupamento é insensível a rotações, reflexões e traduções.$S$$S$$S$

$\hskip{6em}$

Uma variante do Teorema de Kleinberg

A intuição dada acima é capturada pela seguinte variante do Teorema de Kleinberg.

Teorema: Não existe um algoritmo de agrupamento não trivial e invariante em isometria que seja simultaneamente consistente e invariável em escala.

Aqui, por um algoritmo de agrupamento trivial , quero dizer um dos dois algoritmos a seguir:

1. $S$

2. $S$

A alegação é que esses algoritmos tolos são os únicos dois algoritmos invariantes de isometria que são consistentes e invariáveis ​​em escala.

$S$$Γ$$d₁$$S$$d₁(x,y) = 1$$x ≠ y$Γ Γ ( d ₁ ) Γ ( d ₁ ) Γ$S$$Γ$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$é a partição discreta. Dada qualquer métrica em , podemos redimensioná-la para que todos os pares de pontos tenham distância sob . Então, por consistência, encontramos que . Portanto, nesse caso, é o algoritmo trivial que atribui a partição discreta a cada métrica. Segundo, vamos considerar o caso em que é a partição global. Podemos redimensionar qualquer métrica em para que todos os pares de pontos tenham distância , então novamente a consistência implica que . Então também é trivial neste caso. ∎$d$$S$$≥ 1$$d$$Γ(d) = Γ(d₁)$$Γ$$Γ(d₁)$$d$$S$$≤ 1$$Γ(d)=Γ(d₁)$$Γ$

Evidentemente, essa prova está muito próxima da prova de Margareta Ackerman do teorema original de Kleinberg, discutida na resposta de Alex Williams.

Essa é a intuição que eu criei (um trecho do meu blog aqui ).

Uma conseqüência do axioma da riqueza é que podemos definir duas funções de distância diferentes, (canto superior esquerdo) e (canto inferior esquerdo), que respectivamente colocam todos os pontos de dados em clusters individuais e em algum outro cluster. Então, podemos definir uma função de terceira distância (superior e inferior direita) que simplesmente escala para que a distância mínima entre pontos no espaço seja maior que a distância máxima no espaço . Em seguida, chegamos a uma contradição, pois, por consistência, o agrupamento deve ser o mesmo para a transformação , mas também o mesmo para a transformação .d 2 d 3 d 2 d 3 d 1 d 1 → d 3 d 2 → d $d_1$$d_2$$d_3$$d_2$$d_3$$d_1$$d_1 \rightarrow d_3$$d_2 \rightarrow d_3$