Clustering - Intuição por trás do Teorema da Impossibilidade de Kleinberg

17

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ΓRange(f)a<b(a,b)Γ

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

contra-exemplo?

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


Outros artigos:

Alex Williams
fonte
No que diz respeito à "consistência": essa característica é intuitivamente desejada somente quando os agrupamentos já estão bem separados. Quando não existem, há um problema no número de clusters nos dados - para a análise, uma vez que não é supervisionado, é uma pergunta. Portanto, é bastante normal esperar que, à medida que você gradualmente adicione distância entre os clusters (como eles foram gerados por você), a análise altere as atribuições que realiza durante o processo de cluster.
ttnphns
No que diz respeito à "riqueza": desculpe-me por não ter entendido o que isso significa (pelo menos como você colocou). Os algoritmos de agrupamento são muitos; como você pode esperar que todos eles obedeçam a algum requisito especial?
ttnphns
Em relação à sua imagem: são necessários métodos especiais de agrupamento para reconhecer esse padrão. Os métodos de agrupamento tradicionais / originais derivam da biologia e da sociologia, onde os agrupamentos são "ilhas" mais ou menos densas de esferóides, e não anéis de atol. Esses métodos não podem exigir lidar com os dados na imagem.
ttnphns
Você também pode estar interessado em: Estivill-Castro, Vladimir. "Por que tantos algoritmos de agrupamento: um documento de posicionamento". Boletim de exploração ACM SIGKDD 4.1 (2002): 65-75.
Anony-Mousse -Reinstala Monica
Eu não li o jornal. Mas em muitos algoritmos de armazenamento em cluster você tem algum limite de distância (por exemplo, DBSCAN, armazenamento em cluster hierárquico). Se você escalar as distâncias, é claro que também precisará escalar seu limite de acordo. Assim, discordo de seu requisito de invariância à escala. Eu também discordo de riqueza. Nem toda partição deve ser uma solução válida para todos os algoritmos. Existem milhões de partições aleatórias.
Anony-Mousse -Reinstala Monica

Respostas:

11

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:S1S2270

dois conjuntos de 270 pontos

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

conjunto 1 com zoom

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:S2

conjunto 2 com zoom

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.S2S1S2S233×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 2k2A 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):

agrupamento de {gato, cachorro, rato} versus {Tom, Spike, Jerry}

É 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) kk

SSS

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

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 .Γddii(x)i(y)Γ(d)xyΓ(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.SSS

um conjunto de pontos no plano e duas rotações dele

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ΓdSd(x,y)=1xyΓ Γ ( 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. ∎dS1dΓ(d)=Γ(d)ΓΓ(d)dS1Γ(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.

Álgebra Comunicativa
fonte
7

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

insira a descrição da imagem 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 1d 3 d 2d 3d1d2d3d2d3d1d1d3d2d3

Alex Williams
fonte
Você quer dizer canto inferior esquerdo para d2? Uma coisa interessante sobre o seu diagrama é que ele mostra como a consistência não é uma propriedade geralmente desejável (ou que é muito vagamente formulada).
xan
Sim, no canto inferior esquerdo, editei a resposta de acordo. Obrigado!
Alex Williams
Antes de entender completamente sua resposta, criei uma lógica que acaba sendo a sua: comece com um agrupamento em que todos os pontos estão no mesmo agrupamento. Transforme-o em qualquer outro arranjo, encolhendo-o em uma versão em miniatura de qualquer outro arranjo e escalando-o para uma versão em tamanho real do outro arranjo.
xan