Come valutare la somiglianza di due istogrammi?

Un documento recente che potrebbe valere la pena leggere è:

Cao, Y. Petzold, L. Limiti di accuratezza e misurazione degli errori nella simulazione stocastica di sistemi che reagiscono chimicamente, 2006.

Sebbene il focus di questo articolo sia sul confronto di algoritmi di simulazione stocastica, essenzialmente lidea principale è come confrontare due istogrammi .

Puoi accedere al pdf dalla pagina web dellautore.

Commenti

• Ciao, è un bel documento, grazie per aver fornito il link al pdf .. I ‘ passerò sicuramente attraverso questo documento ..
• Invece di fornire un riferimento sarebbe bene se ‘ riassumessi i punti principali del documento. I link muoiono, quindi in futuro la tua risposta potrebbe diventare inutile per i non abbonati a questa rivista (e la stragrande maggioranza della popolazione umana è composta da non abbonati).

Ci sono molti misure di distanza tra due istogrammi. Puoi leggere una buona categorizzazione di queste misure in:

K. Meshgi e S. Ishii, “Expanding Histogram of Colors with Gridding to Improve Tracking Accuracy, “in Proc. of MVA15, Tokyo, Japan, May 2015.

Le funzioni di distanza più popolari sono elencate qui per tua comodità:

• $ L_0 $ o Hellinger Distance

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

• $ L_1 $ , Manhattan o City Block Distance

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

• $ L = 2 $ o distanza euclidea

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

• L $ _ {\ infty} $ o Chybyshev Distance

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

• L $ _ p $ o frazionario Distanza (parte della famiglia della distanza Minkowski)

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

• Intersezione istogramma

$ 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)} $

• Distanza del coseno

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

• Distanza 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)} $

• Coefficiente di correlazione di 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}} $

• Diverganza Kolmogorov-Smirnov

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

• Distanza corrispondenza

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

• Distanza di Cramer-von Mises

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

• $ \ chi ^ 2 $ Statistiche

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

• Distanza Bhattacharyya

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

• Squared Chord

$ 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) $

• Earth Mover “s Distance (questo è il primo membro di Distanze di trasporto che incorporano le informazioni sul raggruppamento $ A $ nella distanza. Per ulteriori informazioni, fai riferimento al documento sopra menzionato o Wikipedia voce.

$ 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} $ rappresenta il flusso da $ i $ a $ j $

• Quadratic Dist ance

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

• Distanza Chi quadratica

$ 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 $

Unimplementazione Matlab di alcune di queste distanze è disponibile dal mio repository GitHub: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Inoltre puoi cercare ragazzi come Yossi Rubner, Ofir Pele, Marco Cuturi e Haibin Ling per distanze più allavanguardia.

Aggiornamento: Spiegazioni alternative per le distanze appaiono qua e là nella letteratura, quindi le elenco qui per completezza.

• Canberra distance (unaltra versione)

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

• Dissimilarità di Bray-Curtis, distanza di Sorensen (dal la somma degli istogrammi è uguale a uno, è uguale 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)} $

• Distanza Jaccard (ovvero intersezione su unione, unaltra versione)

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

Commenti

• Benvenuto nel nostro sito! Grazie per questo contributo.
• Ecco il link cartaceo: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Grazie, un elenco è meraviglioso, mentre ‘ non consente di creare un operatore di confronto per listogramma, ad es. per dire che hist1 < hist2
• La tua divergenza KS è implementata nel codice come $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Sembra incoerente con lequazione che hai sopra. Mi manca qualcosa?
• Immagino sia un errore nel mio codice. Lo esaminerò. Grazie per averlo indicato

La risposta standard a questa domanda è la test del chi quadrato . Il test KS è per i dati non accumulati, non per i dati raggruppati. (Se hai i dati non vincolati, usa assolutamente un test in stile KS, ma se hai solo listogramma, il test KS non è appropriato.)

Commenti

• Hai ragione sul fatto che il test KS non è appropriato per gli istogrammi quando è inteso come un test di ipotesi sulla distribuzione dei dati sottostanti, ma non vedo motivo per cui la statistica non ‘ funzionerebbe bene come misura delluguaglianza di due istogrammi.
• Una spiegazione del motivo per cui il test di Kolmogorov-Smirnov non è appropriato con i dati raggruppati sarebbe utile.
• Questo potrebbe non essere utile nellelaborazione delle immagini come nella valutazione delladattamento statistico. Spesso nellelaborazione delle immagini, un istogramma di dati viene utilizzato come descrittore di una regione di unimmagine e lobiettivo è che una distanza tra gli istogrammi rifletta la distanza tra le patch dellimmagine. Si può sapere poco, o forse niente, delle statistiche generali sulla popolazione dei dati di immagine sottostanti utilizzati per ottenere listogramma. Ad esempio, le statistiche sulla popolazione sottostante quando si utilizzano istogrammi di gradienti orientati differirebbero notevolmente in base al contenuto effettivo delle immagini.
• naught101 ‘ ha risposto alla domanda Stochtastic: stats.stackexchange.com/a/108523/37373

Stai “cercando il test di Kolmogorov-Smirnov . Non dimenticare di dividere le altezze delle barre per la somma di tutte le osservazioni di ogni istogramma.

Nota che il test KS riporta anche una differenza se ad es le medie delle distribuzioni sono spostate luna rispetto allaltra. Se la traduzione dellistogramma lungo lasse x non è significativa nella tua applicazione, potresti prima sottrarre la media da ciascun istogramma.

Commenti

• Sottraendo la media cambia la distribuzione nulla della statistica KS. @David Wright solleva comunque una valida obiezione allapplicazione del test KS agli istogrammi.

As La risposta di David sottolinea che il test del chi quadrato è necessario per i dati cestinati poiché il test KS presuppone distribuzioni continue. Per quanto riguarda il motivo per cui il test KS è inappropriato (commento di naught101), ci sono state alcune discussioni sul problema nellapplicazione letteratura statistica che vale la pena raccogliere qui.

Uno scambio divertente è iniziato con laffermazione ( García-Berthou e Alcaraz, 2004 ) che un terzo degli articoli su Nature contiene errori statistici. Tuttavia, un documento successivo ( Jeng, 2006 , “ Errore nei test statistici di errore nei test statistici ” – forse il mio tutto- titolo dellarticolo preferito dal tempo) hanno mostrato che Garcia-Berthou e Alcaraz (2005) hanno utilizzato test KS su dati discreti, portando a riportare valori p imprecisi nel loro meta-studio. Il documento di Jeng (2006) fornisce una bella discussione del problema, mostrando anche che è possibile modificare il test KS per lavorare con dati discreti. In questo caso specifico, la distinzione si riduce alla differenza tra una distribuzione uniforme della cifra finale su [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (nel test KS errato) e una distribuzione combinata di funzioni delta, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (nella forma corretta e modificata).Come risultato dellerrore originale, Garcia-Berthou e Alcaraz (2004) hanno erroneamente rifiutato il valore nullo, mentre il test del chi-quadrato e KS modificato non lo fanno. In ogni caso, il test del chi quadrato è la scelta standard in questo scenario, anche se KS può essere modificato per funzionare qui.