Hvordan vurdere likheten mellom to histogrammer?

Et nylig papir som kan være verdt å lese er:

Cao, Y. Petzold, L. Nøyaktighetsbegrensninger og måling av feil i den stokastiske simuleringen av kjemisk reagerende systemer, 2006.

Selv om denne artikkelen fokuserer på å sammenligne stokastiske simuleringsalgoritmer, er egentlig hovedideen hvordan man sammenligner to histogram .

Du kan få tilgang til pdf fra forfatterens webside.

Kommentarer

• Hei, det er fint papir, thanx for å gi pdf-lenke .. Jeg ‘ Jeg vil helt sikkert gå gjennom dette papiret ..
• I stedet å gi en referanse ville det være bra hvis du ‘ oppsummerer hovedpoengene i avisen. Koblinger dør, så i fremtiden kan svaret ditt bli ubrukelig for ikke-abonnenter på denne tidsskriftet. (og det store flertallet av menneskelig befolkning er ikke-abonnenter).

Det er nok av avstandsmålinger mellom to histogrammer. Du kan lese en god kategorisering av disse målene i:

K. Meshgi og S. Ishii, “Utvidet fargevisogram med Gridding to Improve Tracking Accuracy, ”i Proc. of MVA15, Tokyo, Japan, mai 2015.

De mest populære avstandsfunksjonene er oppført her for enkelhets skyld:

• $ 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 euklidisk avstand

$ 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 Brøk Avstand (del av Minkowski avstandsfamilie)

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

• Histogramkryss

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

• 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 korrelasjonskoeffisient

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

• Match Distance

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

$ 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

• Kvadratisk akkord

$ 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) logg \ frac {h_2 (i)} {m (i)} \ right) $

• Earth Movers Distance (dette er det første medlemmet av Transportavstander som legger inn binninginformasjon $ A $ i det fjerne, for mer informasjon, se ovennevnte papir eller Wikipedia oppføring.

$ 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) $ og $ f_ {ij} $ representerer flyten fra $ i $ til $ j $

• Quadratic Dist ance

$ D_ {QU} = \ sqrt {\ sum_ {i, j} A_ {ij} \ left (h_1 (i) – h_2 (j) \ høyre) ^ 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øyre) \ høyre) ^ m} \ høyre) \ venstre (\ frac {h_1 (j) – h_2 (j)} {\ venstre (\ sum_c A_ {cj} \ venstre (h_1 (c) + h_2 (c) \ right) \ right) ^ m} \ right)} $ og $ \ frac {0} {0} \ equiv 0 $

En Matlab-implementering av noen av disse avstandene er tilgjengelig fra GitHub-depotet mitt: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Du kan også søke på gutter som Yossi Rubner, Ofir Pele, Marco Cuturi og Haibin Ling etter mer moderne avstander.

Oppdatering: Alternativ forklaring på avstandene vises her og der i litteraturen, så jeg lister dem opp her for fullstendighets skyld.

• Canberra avstand (en annen versjon)

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

• Bray-Curtis Ulikhet, Sorensen Distance (siden summen av histogrammer er lik ett, det tilsvarer $ 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. kryss over union, en annen versjon)

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

Kommentarer

• Velkommen til siden vår! Takk for dette bidraget.
• Her er papirlinken: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Takk, en liste er fantastisk, mens den ikke ‘ ikke tillater å lage en sammenligningsoperator for histogram, f.eks. å si at hist1 < hist2
• Din KS-avvik er implementert i kode som $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Dette virker uforenlig med ligningen du har ovenfor. Mangler jeg noe?
• Jeg antar at det er en feil i koden min. Jeg vil se på dette. Takk for at du påpekte det

Standardsvaret på dette spørsmålet er chi-squared test . KS-testen er for ubundne data, ikke for innbyggede data. (Hvis du har ubundne data, så bruk for all del en KS-stil-test, men hvis du bare har histogrammet, er KS-testen ikke passende.)

Kommentarer

• Du har rett i at KS-testen ikke er passende for histogrammer når den forstås som en hypotesetest om fordelingen av de underliggende dataene, men jeg ser ingen grunn til at KS -statistikken ville ikke fungere ‘ som et mål for likhet med to histogrammer.
• En forklaring på hvorfor Kolmogorov-Smirnov-testen ikke er hensiktsmessig med binnedata ville være nyttig.
• Dette er kanskje ikke så nyttig i bildebehandling som i statistisk tilpasningsvurdering. Ofte i bildebehandling brukes et histogram av data som en deskriptor for en region av et bilde, og målet er at en avstand mellom histogrammer skal gjenspeile avstanden mellom bildeplaster. Lite, eller muligens ingenting i det hele tatt, kan være kjent om den generelle befolkningsstatistikken for de underliggende bildedataene som ble brukt for å få histogrammet. For eksempel vil den underliggende populasjonsstatistikken ved bruk av histogrammer av orienterte gradienter variere betydelig basert på det faktiske innholdet i bildene.
• naught101 ‘ spørsmål ble besvart av Stochtastic: stats.stackexchange.com/a/108523/37373

Du leter etter Kolmogorov-Smirnov-testen . Ikke glem å dele barhøydene med summen av alle observasjoner av hvert histogram.

Merk at KS-testen også rapporterer en forskjell hvis f.eks midlene til fordelingen forskyves i forhold til hverandre. Hvis oversettelse av histogrammet langs x-aksen ikke er meningsfylt i applikasjonen din, kan det være lurt å trekke gjennomsnittet fra hvert histogram først.

Kommentarer

• Å trekke gjennomsnittet endrer nullfordelingen av KS-statistikken. @David Wright reiser allikevel en gyldig innsigelse mot anvendelse av KS-testen på histogrammer.

Som Davids svar påpeker at chi-squared-testen er nødvendig for binned data da KS-testen forutsetter kontinuerlige distribusjoner. Når det gjelder hvorfor KS-testen er upassende (ingen101s kommentar), har det vært noen diskusjon om problemet i den anvendte statistikklitteratur som det er verdt å heve her.

En morsom utveksling startet med påstanden ( García-Berthou og Alcaraz, 2004 ) om at en tredjedel av Nature-papirene inneholder statistiske feil. Imidlertid er et påfølgende papir ( Jeng, 2006 , « Feil i statistiske feiltester i statistiske tester » – kanskje min all- tid favoritt papir tittel) viste at Garcia-Berthou og Alcaraz (2005) brukte KS tester på diskrete data, noe som førte til at de rapporterte unøyaktige p-verdier i metastudien. Jeng (2006) -papiret gir en fin diskusjon av problemet, og viser til og med at man kan endre KS-testen for å arbeide for diskrete data. I dette spesifikke tilfellet koker skillet ned til forskjellen mellom en jevn fordeling av baksifferet på [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (i feil KS-test) og en kamfordeling av delta-funksjoner, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (i riktig, modifisert form).Som et resultat av den opprinnelige feilen avviste Garcia-Berthou og Alcaraz (2004) feilen null, mens chi-kvadrat og modifisert KS-test ikke gjør det. Uansett er chi-kvadrat-testen standardvalget i dette scenariet, selv om KS kan modifiseres for å fungere her.