Comparando Clustering: Rand Index vs Variation of Information

Fiquei me perguntando se alguém tinha algum insight ou intuição por trás da diferença entre a Variação da Informação e o Índice Rand para comparar agrupamentos.

Eu li o artigo " Comparando Clusterings - Uma Distância Baseada em Informações ", de Marina Melia (Journal of Multivariate Analysis, 2007), mas, além de perceber a diferença nas definições, não entendo o que é a variação de informações. captura que o índice rand não captura.

A diferença entre os dois métodos é sutil. A melhor maneira de pensar sobre isso é considerar a estrutura definida pela operação de divisão de mesclagem em agrupamentos. Ambas as medidas podem ser reconstruídas definindo uma função em um cluster e, em seguida, definindo a distância entre dois agrupamentos pela fórmula:$f$

que C ∧ C ′ é a junção dos dois agrupamentos na rede.

Agora deixe e deixe n i = | C i | . Definindo F ( C ) = Σ n 2 i produz o índice de margem, e definindo F ( C ) = Σ n i log n i produz VI.$C = \{ C_1, C_2, \ldots, C_k\}$$n_i = |C_i|$$f(C) = \sum n_i^2$$f(C) = \sum n_i \log n_i$

Na minha opinião, existem enormes diferenças. O índice Rand é muito afetado pela granularidade dos agrupamentos nos quais opera. A seguir, usarei a distância Mirkin, que é uma forma ajustada do índice Rand (fácil de ver, mas veja, por exemplo, Meila). Também utilizarei a distância de divisão / junção, que também é mencionada em alguns dos documentos de Meila (aviso: a distância de divisão / junção foi proposta por mim). Suponha um universo de cem elementos. Usarei Top para indicar o cluster com um único cluster contendo todos os elementos, Bottom para indicar o cluster em que todos os nós estão em conjuntos separados de singleton, à esquerda para indicar o cluster {{1,2, .. 10}, {11, 12..20}, {21,22..30}, ..., {91,92, .. 100}} e Direito de denotar o agrupamento {{1,11, .. 91}, {2, 12, .. 92}, {3,13, .. 93}, ..., {10,20, .. 100}}.

Na minha opinião, Inferior e Superior são agrupamentos consistentes (aninhados), enquanto Esquerda e Direita são agrupamentos maximamente conflitantes. As distâncias das métricas mencionadas para essas duas comparações pareadas são as seguintes:

               Top-Bottom     Left-Right 

Mirkin            9900          1800
VI                4.605         4.605
Split/join        99            180

Segue-se que Mirkin / Rand considera o par superior / inferior consistente muito mais distante do que o par esquerda-direita maximamente conflitante. Este é um exemplo extremo para ilustrar o ponto, mas, em geral, Mirkin / Rand é muito afetado pela granularidade dos agrupamentos em que opera. A razão subjacente a isso é uma relação quadrática entre esses tamanhos de métrica e cluster, explicada pelo fato de a contagem de pares de nós estar envolvida. Com efeito, a distância de Mirkin é uma distância de Hamming entre conjuntos de arestas de uniões de gráficos completos induzidos por agrupamentos (esta é a resposta para sua pergunta, eu acho).

Em relação às diferenças entre Variação da informação e Divisão / Junção, a primeira é mais sensível a determinadas situações de conflito, como demonstrado por Meila. Ou seja, Dividir / Unir considera apenas a melhor correspondência para cada cluster e desconsidera a fragmentação que pode ocorrer na parte restante desse cluster, enquanto a Variação de Informações seleciona isso. Dito isso, Split / Join é facilmente interpretável como o número de nós que precisam ser movidos para obter um cluster do outro e, nesse sentido, seu alcance é mais facilmente compreendido; na prática, a questão da fragmentação também pode não ser tão comum.

Cada uma dessas métricas pode ser formada como a soma de duas distâncias, a saber, as distâncias de cada um dos dois agrupamentos até o maior subconjunto comum. Eu acho que muitas vezes é benéfico trabalhar com essas partes separadas, e não apenas com a soma delas. A tabela acima se torna:

               Top-Bottom     Left-Right 

Mirkin          0,9900          900,900
VI              0,4.605       2.303,2.303
Split/join      0,99             90,90

O relacionamento de subsunção entre Superior e Inferior se torna imediatamente claro. Muitas vezes, é bastante útil saber se dois agrupamentos são consistentes (ou seja, um é (quase) um sub- agrupamento do outro) como um relaxamento da questão de saber se eles estão próximos . Um agrupamento pode estar bem distante de um padrão-ouro, mas ainda assim ser consistente ou quase consistente. Nesse caso, pode não haver razão para considerar ruim o agrupamento em relação a esse padrão-ouro. Obviamente, os agrupamentos triviais Superior e Inferior serão consistentes com qualquer cluster, portanto, isso deve ser levado em consideração.

Finalmente, acredito que métricas como Mirkin, Variation of Information e Split / Join são as ferramentas naturais para comparar agrupamentos. Para a maioria das aplicações, os métodos que tentam incorporar independência estatística e corrigir o acaso são excessivamente inventados e ofuscam, em vez de esclarecer.

Segundo exemplo Considere os seguintes pares de agrupamentos: C1 = {{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, 12, 13, 14, 15, 16}} com C2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}}

e C3 = {{1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}} com {{1, 2, 3 , 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16}}

Aqui, C2 pode ser formado a partir de C1 movendo os nós 9 e 10 e C3 pode ser formado a partir de C3 movendo os nós 11 e 12. Ambas as alterações são idênticas ("mova dois nós"), exceto pelo fato de que os tamanhos dos clusters envolvidos diferem . A tabela de métricas de cluster para esses dois exemplos é a seguinte:

            C1-C2         C3-C4

Mirkin       56            40 
VI            0.594         0.520
Split/Join    4             4

Pode-se observar que Mirkin / Rand e Variation of information são afetados pelos tamanhos de cluster (e Mirkin em maior extensão; isso será mais pronunciado à medida que os tamanhos de cluster divergem), enquanto a distância Split / Join não é (seu valor é 4 como "move" os nós de um cluster para o outro sempre através do maior sub-cluster comum). Essa pode ser uma característica desejável, dependendo das circunstâncias. A interpretação simples de Split / Join (número de nós a serem movidos) e sua independência do tamanho do cluster merecem atenção. Entre Mirkin e Variação da Informação, acho que o último é muito preferível.