Hur bedömer jag likheten mellan två histogram?

En tidning som nyligen kan vara värt att läsa är:

Cao, Y. Petzold, L. Noggrannhetsbegränsningar och mätning av fel i den stokastiska simuleringen av kemiskt reagerande system, 2006.

Även om detta dokument fokuserar på att jämföra stokastiska simuleringsalgoritmer, är huvudsakligen huvudidén hur man jämför två histogram .

Du kan komma åt pdf från författarens hemsida.

Kommentarer

• Hej, det är trevligt papper, thanx för att ge pdf-länk .. Jag ’ Jag kommer säkert att gå igenom det här papperet ..
• Istället att tillhandahålla en referens skulle det vara bra om du ’ d sammanfattar de viktigaste punkterna i tidningen. Länkar dör, så i framtiden kan ditt svar bli värdelöst för icke-prenumeranter på denna tidskrift (och den stora majoriteten av den mänskliga befolkningen är icke-prenumeranter).

Det finns gott om avståndsmått mellan två histogram. Du kan läsa en bra kategorisering av dessa mått i:

K. Meshgi och S. Ishii, “Expanding Histogram of Colors med Gridding för att förbättra spårningsnoggrannheten, ”i Proc. av MVA15, Tokyo, Japan, maj 2015.

De mest populära avståndsfunktionerna listas här för din bekvämlighet:

• $ L_0 $ eller Hellinger Distance

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

• $ L_1 $ , Manhattan eller City Block Distance

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

• $ L = 2 $ eller euklidiskt avstånd

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

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

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

• L $ _ p $ eller Fractional Avstånd (del av Minkowski distansfamilj)

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

• Histogramkorsning

$ D _ {\ cap} = 1 – \ frac {\ sum_ {i} \ left (min (h_1 (i)) , h_2 (i) \ höger)} {min \ vänster (\ vert h_1 (i) \ vert, \ vert h_2 (i) \ vert \ höger)} $

• Cosine Distance

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

• Canberra Distance

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

• Pearsons korrelationskoefficient

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

• Matchavstånd

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

• Cramer-von Mises Distance

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

• $ \ chi ^ 2 $ Statistik

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

• Bhattacharyya Distance

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

• Kvadratiskt ackord

$ 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 Movers Distance (detta är den första medlemmen i Transportsträckor som bäddar in binninginformation $ A $ på avstånd, för mer information hänvisas till ovannämnda papper eller Wikipedia post.

$ 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) $ och $ f_ {ij} $ representerar flödet från $ i $ till $ j $

• Quadratic Dist ance

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

• Quadratic-Chi Distance

$ 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) \ höger) \ höger) ^ m} \ höger) \ vänster (\ frac {h_1 (j) – h_2 (j)} {\ vänster (\ sum_c A_ {cj} \ vänster (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ och $ \ frac {0} {0} \ equiv 0 $

En implementering av Matlab för några av dessa avstånd finns i mitt GitHub-arkiv: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Du kan också söka i killar som Yossi Rubner, Ofir Pele, Marco Cuturi och Haibin Ling för mer avancerade avstånd.

Uppdatering: Alternativ förklaring till avstånden visas här och där i litteraturen, så jag listar dem här för fullständighetens skull.

• Canberra-avstånd (annan version)

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

• Bray-Curtis Olikhet, Sorensen Distance (sedan summan av histogram är lika med ett, det är lika med $ 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)} $

• Jaccard Distance (dvs. korsning över union, en annan version)

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

Kommentarer

• Välkommen till vår webbplats! Tack för detta bidrag.
• Här är papperslänken: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Tack, en lista är underbar, medan den ’ inte tillåter att skapa en jämförelseoperator för histogram, t.ex. att säga att hist1 < hist2
• Din KS-avvikelse implementeras i kod som $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Detta verkar vara oförenligt med ekvationen du har ovan. Saknar jag något?
• Jag antar att det är ett misstag i min kod. Jag kommer att undersöka detta. Tack för att ni påpekade det

Standardsvaret på denna fråga är chi-squared test . KS-testet avser icke-bundna data, inte inbyggda data. (Om du har de oförbundna uppgifterna, använd i alla fall ett KS-typ-test, men om du bara har histogrammet är KS-testet inte lämpligt.)

Kommentarer

Du har rätt i att KS-testet inte är lämpligt för histogram när det förstås som ett hypotesprov om fördelningen av underliggande data, men jag ser ingen anledning till varför KS -statistiken skulle ’ inte fungera bra som ett mått på likhet mellan två histogram.

En förklaring till varför Kolmogorov-Smirnov-testet inte är lämpligt med binnedata skulle vara användbart.

Detta kanske inte är lika användbart vid bildbehandling som vid bedömning av statistisk passform. Ofta vid bildbehandling används ett histogram med data som en deskriptor för en region av en bild, och målet är att ett avstånd mellan histogram ska återspegla avståndet mellan bildplåster. Lite eller möjligen ingenting alls kan vara känt om den allmänna befolkningsstatistiken för den underliggande bilddata som används för att få histogrammet. Till exempel skulle den underliggande befolkningsstatistiken vid användning av histogram av orienterade lutningar skilja sig avsevärt baserat på det faktiska innehållet i bilderna.

naught101 ’ s fråga besvarades av Stochtastic: stats.stackexchange.com/a/108523/37373

Du letar efter Kolmogorov-Smirnov-testet . Glöm inte att dela stapelhöjderna med summan av alla observationer av varje histogram.

Observera att KS-testet också rapporterar en skillnad om t.ex. medel för fördelningarna flyttas i förhållande till varandra. Om översättning av histogrammet längs x-axeln inte är meningsfullt i din applikation, kanske du vill subtrahera medelvärdet från varje histogram först.

Kommentarer

• Att subtrahera medelvärdet ändrar nollfördelningen av KS-statistiken. @David Wright väcker ändå en giltig invändning mot tillämpningen av KS-testet på histogram.

Som Davids svar påpekar att chi-kvadrat-testet är nödvändigt för binned data eftersom KS-testet förutsätter kontinuerliga fördelningar. När det gäller varför KS-testet är olämpligt (ingen101s kommentar) har det diskuterats något i frågan i den tillämpade statistiklitteratur som är värt att ta upp här.

Ett underhållande utbyte började med påståendet ( García-Berthou och Alcaraz, 2004 ) att en tredjedel av Nature-papper innehåller statistiska fel. En efterföljande artikel ( Jeng, 2006 , ” Fel i statistiska felprov i statistiska test ” – kanske min all- tidens favoritpappertitel) visade att Garcia-Berthou och Alcaraz (2005) använde KS-tester på diskreta data, vilket ledde till att de rapporterade felaktiga p-värden i sin metastudie. Jeng (2006) ger en trevlig diskussion om frågan, till och med visar att man kan ändra KS-testet för att arbeta för diskreta data. I det här specifika fallet beror skillnaden på skillnaden mellan en enhetlig fördelning av efterföljande siffra på [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (i fel KS-test) och en kamfördelning av deltafunktioner, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (i rätt, modifierad form).Som ett resultat av det ursprungliga felet avvisade Garcia-Berthou och Alcaraz (2004) felaktigt noll, medan det chi-kvadrerade och modifierade KS-testet inte gjorde det. I vilket fall som helst är chi-kvadrat-testet standardvalet i detta scenario, även om KS kan ändras för att fungera här.