Hoe de gelijkenis van twee histogrammen beoordelen?

Een recent artikel dat het lezen waard kan zijn, is:

Cao, Y. Petzold, L. Nauwkeurigheidsbeperkingen en het meten van fouten in de stochastische simulatie van chemisch reagerende systemen, 2006.

Hoewel de focus van dit artikel ligt op het vergelijken van stochastische simulatiealgoritmen, is het belangrijkste idee om twee histogrammen te vergelijken. .

Je hebt toegang tot de pdf vanaf de webpagina van de auteur.

Opmerkingen

• Hallo, het is een mooi document, bedankt voor het geven van een pdf-link. Ik ‘ zal dit document zeker doornemen.
• In plaats daarvan voor het verstrekken van een referentie zou het goed zijn als u ‘ de hoofdpunten van het artikel samenvat. Links verdwijnen, dus in de toekomst kan uw antwoord nutteloos worden voor niet-abonnees van dit tijdschrift (en de overgrote meerderheid van de menselijke bevolking zijn de niet-abonnees).

Er zijn genoeg afstandsmaten tussen twee histogrammen. U kunt een goede indeling van deze maten lezen in:

K. Meshgi en S. Ishii, “Expanding Histogram of Colors with Gridding to Improve Tracking Accuracy, ”in Proc. of MVA15, Tokio, Japan, mei 2015.

De meest populaire afstandsfuncties worden hier voor uw gemak vermeld:

• $ L_0 $ of Hellinger Afstand

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

• $ L_1 $ , Manhattan of City Block Distance

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

• $ L = 2 $ of Euclidische afstand

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

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

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

• L $ _ p $ of fractioneel Afstand (onderdeel van de afstandsfamilie van Minkowski)

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

• Histogramkruising

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

• Cosinus afstand

$ 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 correlatiecoëfficiënt

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

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

• $ \ chi ^ 2 $ Statistieken

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

• Bhattacharyya Afstand

$ 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 Movers Distance (dit is het eerste lid van Transportafstanden die binning-informatie $ A $ in de afstand insluiten, raadpleeg voor meer informatie het bovengenoemde artikel of Wikipedia invoer.

$ 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) $ en $ f_ {ij} $ vertegenwoordigt de stroom van $ i $ naar $ j $

• Kwadratisch dist ance

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

• Kwadratische-Chi-afstand

$ 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)} $ en $ \ frac {0} {0} \ equiv 0 $

Een Matlab-implementatie van enkele van deze afstanden is beschikbaar in mijn GitHub-repository: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Ook kun je jongens als Yossi Rubner, Ofir Pele, Marco Cuturi en Haibin Ling zoeken naar meer geavanceerde afstanden.

Update: Alternatieve uitleg voor de afstanden verschijnt hier en daar in de literatuur, dus ik noem ze hier voor de volledigheid.

• Canberra-afstand (een andere versie)

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

• Bray-Curtis Dissimilarity, Sorensen Distance (sinds de som van histogrammen is gelijk aan één, het is gelijk aan $ 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 (dwz kruising over vereniging, een andere versie)

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

Reacties

• Welkom op onze site! Bedankt voor deze bijdrage.
• Hier is de papieren link: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Bedankt, een lijst is geweldig, terwijl het ‘ niet toestaat om een vergelijkingsoperator voor histogrammen te maken, bijv. om te zeggen dat hist1 < hist2
• Je KS-divergentie is geïmplementeerd in code als $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Dit lijkt niet in overeenstemming met de bovenstaande vergelijking. Mis ik iets?
• Ik denk dat het een fout in mijn code is. Ik zal dit onderzoeken. Bedankt dat je erop hebt gewezen

Het standaardantwoord op deze vraag is de chikwadraat-test . De KS-test is voor niet-gebonden gegevens, niet voor weggegooide gegevens. (Als je de niet-gebonden gegevens hebt, gebruik dan in ieder geval een test in KS-stijl, maar als je alleen het histogram hebt, is de KS-test niet geschikt.)

Opmerkingen

• U hebt gelijk dat de KS-test niet geschikt is voor histogrammen wanneer deze wordt opgevat als een hypothesetest over de verdeling van de onderliggende gegevens, maar ik zie geen reden waarom de KS -statistiek wouldn ‘ t werkt goed als een maat voor gelijkheid van twee willekeurige histogrammen.
• Een verklaring waarom de Kolmogorov-Smirnov-test niet geschikt is met opgeslagen gegevens zou nuttig zijn.
• Dit is misschien niet zo nuttig bij beeldverwerking als bij statistische fit-beoordeling. Vaak wordt bij beeldverwerking een histogram van gegevens gebruikt als een descriptor voor een gebied van een afbeelding, en het doel is dat een afstand tussen histogrammen de afstand tussen beeldvlakken weergeeft. Er is mogelijk weinig of helemaal niets bekend over de algemene populatiestatistieken van de onderliggende beeldgegevens die zijn gebruikt om het histogram te verkrijgen. De onderliggende populatiestatistieken bij het gebruik van histogrammen van georiënteerde verlopen zouden bijvoorbeeld aanzienlijk verschillen op basis van de daadwerkelijke inhoud van de afbeeldingen.
• naught101 ‘ s vraag werd beantwoord door Stochtastic: stats.stackexchange.com/a/108523/37373

U “zoekt naar de Kolmogorov-Smirnov-test . Vergeet niet de staafhoogten te delen door de som van alle waarnemingen van elk histogram.

Merk op dat de KS-test ook een verschil rapporteert als bijv de gemiddelden van de verdelingen zijn ten opzichte van elkaar verschoven. Als vertaling van het histogram langs de x-as niet zinvol is in uw toepassing, wilt u misschien eerst het gemiddelde van elk histogram aftrekken.

Opmerkingen

• Door het gemiddelde af te trekken, verandert de nulverdeling van de KS-statistiek. @David Wright maakt toch een geldig bezwaar tegen de toepassing van de KS-test op histogrammen.

Als Davids antwoord wijst erop dat de chi-kwadraat-test noodzakelijk is voor opgeslagen gegevens, aangezien de KS-test uitgaat van continue distributies. Met betrekking tot waarom de KS-test ongepast is (de opmerking van naught101), is er enige discussie geweest over het probleem in de toegepaste statistische literatuur die hier de moeite waard is.

Een grappig gesprek begon met de bewering ( García-Berthou en Alcaraz, 2004 ) dat een derde van de Nature-artikelen statistische fouten bevat. Een volgende paper ( Jeng, 2006 , “ Error in statistische fouttests in statistische tests ” – misschien mijn alles- time favorite paper title) toonden aan dat Garcia-Berthou en Alcaraz (2005) KS-tests gebruikten op discrete data, wat leidde tot het rapporteren van onnauwkeurige p-waarden in hun metastudie. Het artikel van Jeng (2006) geeft een mooie bespreking van de kwestie, en laat zelfs zien dat men de KS-test kan aanpassen om voor discrete gegevens te werken. In dit specifieke geval komt het onderscheid neer op het verschil tussen een uniforme verdeling van het volgcijfer op [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \ leq 9) $$ (in de onjuiste KS-test) en een comb-verdeling van deltafuncties, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (in de juiste, gewijzigde vorm).Als gevolg van de oorspronkelijke fout hebben Garcia-Berthou en Alcaraz (2004) ten onrechte de nul verworpen, terwijl de chikwadraat- en gemodificeerde KS-test dat niet doen. In elk geval is de chikwadraat-test de standaardkeuze in dit scenario, zelfs als KS kan worden aangepast om hier te werken.