Como avaliar a semelhança de dois histogramas?

Um artigo recente que pode valer a pena ler é:

Cao, Y. Petzold, L. Limitações de precisão e medição de erros na simulação estocástica de sistemas que reagem quimicamente, 2006.

Embora o foco deste artigo seja comparar algoritmos de simulação estocástica, essencialmente a ideia principal é como comparar dois histogramas .

Você pode acessar o pdf da página do autor na web.

Comentários

• Olá, é um bom artigo, obrigado por fornecer o link do pdf. Eu ‘ com certeza vou ler este artigo.
• Em vez disso de fornecer uma referência, seria bom se você ‘ d resumisse os pontos principais do artigo. Os links morrem, portanto, no futuro, sua resposta pode se tornar inútil para os não assinantes desta revista (e a grande maioria da população humana é formada por não assinantes).

Existem muitos medidas de distância entre dois histogramas. Você pode ler uma boa categorização dessas medidas em:

K. Meshgi e S. Ishii, “Expanding Histogram of Colors with Gridding to improvement Tracking Accuracy, “in Proc. of MVA15, Tóquio, Japão, maio de 2015.

As funções de distância mais populares estão listadas aqui para sua conveniência:

• $ L_0 $ ou Distância de Hellinger

$ D_ {L0} = \ sum \ limits_ {i} h_1 (i) \ neq h_2 (i) $

• $ L_1 $ , Manhattan ou City Block Distance

$ D_ {L1} = \ sum_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• $ L = 2 $ ou distância euclidiana

$ D_ { L2} = \ sqrt {\ sum_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2} $

• L $ _ {\ infty} $ ou Distância Chybyshev

$ D_ {L \ infty} = max_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• L $ _ p $ ou Fracionário Distância (parte da família de distância de Minkowski)

$ D_ {Lp} = \ left (\ sum \ limits_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert ^ p \ right) ^ {1 / p} $ e $ 0 < p < 1 $

• Intersecção do histograma

$ D _ {\ cap} = 1 – \ frac {\ sum_ {i} \ left (min (h_1 (i) , h_2 (i) \ right)} {min \ left (\ vert h_1 (i) \ vert, \ vert h_2 (i) \ vert \ right)} $

• Distância de cosseno

$ D_ {CO} = 1 – \ sum_i h_1 (i) h2_ (i) $

• Distância de Canberra

$ D_ {CB} = \ sum_i \ frac {\ lvert h_1 (i) -h_2 (i ) \ rvert} {min \ left (\ lvert h_1 (i) \ rvert, \ lvert h_2 (i) \ rvert \ right)} $

• Coeficiente de correlação de Pearson

$ D_ {CR} = \ frac {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right ) \ left (h_2 (i) – \ frac {1} {n} \ right)} {\ sqrt {\ sum_i \ left (h_1 (i) – \ frac {1} {n} \ right) ^ 2 \ sum_i \ left (h_2 (i) – \ frac {1} {n} \ right) ^ 2}} $

• Kolmogorov-Smirnov Divergance

$ D_ {KS} = max_ {i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Distância de correspondência

$ D_ {MA} = \ sum \ limits_ { i} \ lvert h_1 (i) – h_2 (i) \ rvert $

• Distância de Cramer-von Mises

$ D_ {CM} = \ sum \ limits_ {i} \ left (h_1 (i) – h_2 (i) \ right) ^ 2 $

• $ \ chi ^ 2 $ Estatísticas

$ D _ {\ chi ^ 2 } = \ sum_i \ frac {\ left (h_1 (i) – h_2 (i) \ right) ^ 2} {h_1 (i) + h_2 (i)} $

• Distância Bhattacharyya

$ D_ {BH} = \ sqrt {1- \ sum_i \ sqrt {h_1 (i) h_2 (i)}} $ & hellinger

• Acorde quadrado

$ D_ {SC} = \ sum_i \ left (\ sqrt {h_1 (i)} – \ sqrt {h_2 (i)} \ right) ^ 2 $

• Kullback -Liebler Divergance

$ D_ {KL} = \ sum_i h_1 (i) log \ frac {h_1 (i)} {m (i)} $

• Jefferey Divergence

$ D_ {JD} = \ sum_i \ left (h_1 (i) log \ frac {h_1 (i)} {m (i)} + h_2 (i) log \ frac {h_2 (i)} {m (i)} \ right) $

• Distância do Movimentador da Terra (este é o primeiro membro de Distâncias de transporte que incorporam informações de armazenamento $ A $ à distância; para obter mais informações, consulte o artigo mencionado acima ou a Wikipedia entrada.

$ D_ {EM} = \ frac {min_ {f_ {ij}} \ sum_ {i, j} f_ {ij} A_ {ij}} {sum_ {i, j} f_ {ij}} $ $ \ sum_j f_ {ij} \ leq h_1 (i), \ sum_j f_ {ij} \ leq h_2 (j), \ sum_ {i, j} f_ {ij} = min \ left (\ sum_i h_1 (i) \ sum_j h_2 (j) \ right) $ e $ f_ {ij} $ representa o fluxo de $ i $ para $ j $

• Distância Quadrática ance

$ D_ {QU} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (h_1 (i) – h_2 (j) \ right) ^ 2} $

• Distância qui quadrática

$ D_ {QC} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (\ frac {h_1 (i) – h_2 (i)} {\ left (\ sum_c A_ {ci} \ left (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right) \ left (\ frac {h_1 (j) – h_2 (j)} {\ left (\ sum_c A_ {cj} \ left (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ e $ \ frac {0} {0} \ equiv 0 $

Uma implementação Matlab de algumas dessas distâncias está disponível em meu repositório GitHub: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Além disso, você pode pesquisar caras como Yossi Rubner, Ofir Pele, Marco Cuturi e Haibin Ling para obter distâncias mais modernas.

Atualização: A explicação alternativa para as distâncias aparece aqui e ali na literatura, então eu as listo aqui para fins de completude.

• Distância de Canberra (outra versão)

$ D_ {CB} = \ sum_i \ frac {| h_1 (i) -h_2 (i) |} {| h_1 (i) | + | h_2 (i) |} $

• Dissimilaridade de Bray-Curtis, Distância de Sorensen (desde o soma dos histogramas é igual a um, é igual a $ D_ {L0} $ )

$ D_ {BC} = 1 – \ frac {2 \ sum_i h_1 (i) = h_2 (i)} {\ sum_i h_1 (i) + \ sum_i h_2 (i)} $

• Distância de Jaccard (ou seja, interseção sobre união, outra versão)

$ D_ {IOU} = 1 – \ frac { \ sum_i min (h_1 (i), h_2 (i))} {\ sum_i max (h_1 (i), h_2 (i))} $

Comentários

• Bem-vindo ao nosso site! Obrigado por esta contribuição.
• Aqui está o link do artigo: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Obrigado, uma lista é maravilhosa, embora não ‘ permita criar um operador de comparação para o histograma, por exemplo dizer que hist1 < hist2
• Sua divergência KS é implementada no código como $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Isso parece inconsistente com a equação que você tem acima. Estou perdendo alguma coisa?
• Acho que é um erro no meu código. Eu vou olhar para isso. Obrigado por apontar isso

A resposta padrão para essa pergunta é teste qui-quadrado . O teste KS é para dados não categorizados, não dados categorizados. (Se você tiver os dados não delimitados, use um teste no estilo KS, mas se você tiver apenas o histograma, o teste KS não é apropriado.)

Comentários

• Você está correto ao afirmar que o teste KS não é apropriado para histogramas quando é entendido como um teste de hipótese sobre a distribuição dos dados subjacentes, mas não vejo razão para a estatística KS não ‘ funcionaria bem como uma medida de uniformidade de quaisquer dois histogramas.
• Uma explicação de por que o teste de Kolmogorov-Smirnov não é apropriado com dados binned seria útil.
• Isso pode não ser tão útil no processamento de imagens quanto na avaliação de ajuste estatístico. Freqüentemente, no processamento de imagens, um histograma de dados é usado como um descritor para uma região de uma imagem, e o objetivo é fazer com que uma distância entre os histogramas reflita a distância entre os fragmentos da imagem. Pouco, ou possivelmente nada, pode ser conhecido sobre as estatísticas gerais da população dos dados de imagem subjacentes usados para obter o histograma. Por exemplo, as estatísticas populacionais subjacentes ao usar histogramas de gradientes orientados diferem consideravelmente com base no conteúdo real das imagens.
• naught101 ‘ a pergunta foi respondida por Stochtastic: stats.stackexchange.com/a/108523/37373

Você “está procurando pelo teste de Kolmogorov-Smirnov . Não se esqueça de dividir as alturas das barras pela soma de todas as observações de cada histograma.

Observe que o teste KS também está relatando uma diferença se, por exemplo, as médias das distribuições são alteradas umas em relação às outras. Se a tradução do histograma ao longo do eixo x não for significativa em seu aplicativo, você pode querer subtrair a média de cada histograma primeiro.

Comentários

• Subtrair a média muda a distribuição nula da estatística KS. @David Wright levanta uma objeção válida à aplicação do teste KS a histogramas de qualquer maneira.

Como A resposta de David aponta que o teste qui-quadrado é necessário para dados agrupados, já que o teste KS assume distribuições contínuas. Quanto ao motivo do teste KS ser inadequado (comentário de naught101), houve alguma discussão sobre o problema na literatura estatística que vale a pena levantar aqui.

Uma troca divertida começou com a afirmação ( García-Berthou e Alcaraz, 2004 ) de que um terço dos artigos da Nature contém erros estatísticos. No entanto, um artigo subsequente ( Jeng, 2006 , “ Erro em testes estatísticos de erro em testes estatísticos ” – talvez meu tudo- time favorite paper title) mostrou que Garcia-Berthou e Alcaraz (2005) usaram testes KS em dados discretos, levando a que relatassem p-valores imprecisos em seu metaestudo. O artigo de Jeng (2006) fornece uma boa discussão sobre o assunto, mesmo mostrando que é possível modificar o teste KS para trabalhar com dados discretos. Neste caso específico, a distinção se resume à diferença entre uma distribuição uniforme do dígito final em [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (no teste KS incorreto) e uma distribuição comb de funções delta, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (na forma correta e modificada).Como resultado do erro original, Garcia-Berthou e Alcaraz (2004) rejeitaram incorretamente o nulo, enquanto o teste qui-quadrado e o KS modificado não. Em qualquer caso, o teste qui-quadrado é a escolha padrão neste cenário, mesmo que KS possa ser modificado para funcionar aqui.