Wie kann man die Ähnlichkeit zweier Histogramme beurteilen?

Ein kürzlich gelesenes Papier ist möglicherweise:

Cao, Y. Petzold, L. Genauigkeitsbeschränkungen und die Messung von Fehlern bei der stochastischen Simulation chemisch reagierender Systeme, 2006.

Obwohl der Schwerpunkt dieses Papiers auf dem Vergleich stochastischer Simulationsalgorithmen liegt, besteht die Hauptidee im Wesentlichen darin, zwei Histogramme zu vergleichen .

Sie können über die Webseite des Autors auf das pdf zugreifen.

Kommentare

• Hallo, es ist ein schönes Papier, danke für die PDF-Verknüpfung. Ich ‚ werde dieses Papier sicherlich durchgehen.
• Stattdessen Um eine Referenz bereitzustellen, wäre es gut, wenn Sie ‚ die Hauptpunkte des Papiers zusammenfassen würden. Links sterben, sodass Ihre Antwort in Zukunft für Nicht-Abonnenten dieses Journals unbrauchbar werden könnte (und die überwiegende Mehrheit der menschlichen Bevölkerung sind Nicht-Abonnenten).

Es gibt viele Abstandsmaße zwischen zwei Histogrammen. Eine gute Kategorisierung dieser Maße finden Sie in:

K. Meshgi und S. Ishii, „Erweitern des Histogramms der Farben mit Gitter zur Verbesserung der Tracking-Genauigkeit “in Proc. von MVA15, Tokio, Japan, Mai 2015.

Die beliebtesten Distanzfunktionen sind hier zur Vereinfachung aufgeführt:

• $ L_0 $ oder Hellinger Distance

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

• $ L_1 $ , Manhattan oder Stadtblockentfernung

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

• $ L = 2 $ oder euklidischer Abstand

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

• L $ _ {\ infty} $ oder Chybyshev-Entfernung

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

• L $ _ p $ oder Bruch Entfernung (Teil der Minkowski-Entfernungsfamilie)

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

• Histogrammschnitt

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

• Kosinusabstand

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

• Canberra-Abstand

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

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

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

• Übereinstimmungsabstand

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

• Cramer-von-Mises-Abstand

$ D_ {CM} = \ sum \ limit_ {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-Entfernung

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

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

• Entfernung des Erdbewegers (dies ist das erste Mitglied von Transportentfernungen, in die Binning-Informationen $ A $ in die Entfernung eingebettet sind. Weitere Informationen finden Sie im oben genannten Dokument oder in Wikipedia Eintrag.

$ 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) $ und $ f_ {ij} $ repräsentiert den Fluss von $ i $ zu $ j $

• Quadratic Dist ance

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

• Quadratischer Chi-Abstand

$ 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) \ rechts) \ rechts) ^ m} \ rechts) \ links (\ frac {h_1 (j) – h_2 (j)} {\ links (\ sum_c A_ {cj} \ links (h_1) (c) + h_2 (c) \ rechts) \ rechts) ^ m} \ rechts)} $ und $ \ frac {0} {0} \ equiv 0 $

Eine Matlab-Implementierung einiger dieser Entfernungen ist in meinem GitHub-Repository verfügbar: https://github.com/meshgi/Histogram_of_Color_Advancements/tree/master/distance Sie können auch Leute wie Yossi Rubner, Ofir Pele, Marco Cuturi und Haibin Ling nach Entfernungen auf dem neuesten Stand der Technik suchen.

Update: Eine alternative Erklärung für die Entfernungen erscheint hier und da in der Literatur, daher liste ich sie der Vollständigkeit halber hier auf.

• Canberra-Abstand (eine andere Version)

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

• Bray-Curtis-Unähnlichkeit, Sorensen-Entfernung (seit dem Die Summe der Histogramme ist gleich eins. Sie entspricht $ 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-Abstand (dh Schnittpunkt über Vereinigung, eine andere Version)

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

Kommentare

• Willkommen auf unserer Seite! Vielen Dank für diesen Beitrag.
• Hier ist der Papierlink: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf
• Danke, eine Liste ist wunderbar, während sie ‚ nicht erlaubt, einen Vergleichsoperator für das Histogramm zu erstellen, z zu sagen, dass hist1 < hist2
• Ihre KS-Divergenz im Code implementiert ist als $$ D_ {KS} = max_ {i} \ lvert \ sum_i h_1 (i) – \ sum_i h_2 (i) \ rvert $$ Dies scheint nicht mit der obigen Gleichung übereinzustimmen. Vermisse ich etwas?
• Ich denke, es ist ein Fehler in meinem Code. Ich werde das untersuchen. Vielen Dank für den Hinweis

Die Standardantwort auf diese Frage lautet Chi-Quadrat-Test . Der KS-Test gilt für nicht gruppierte Daten, nicht für gruppierte Daten. (Wenn Sie die nicht gruppierten Daten haben, verwenden Sie auf jeden Fall einen Test im KS-Stil. Wenn Sie jedoch nur das Histogramm haben, ist der KS-Test nicht geeignet.)

Kommentare

• Sie haben Recht, dass der KS-Test nicht für Histogramme geeignet ist, wenn er als Hypothesentest über die Verteilung der zugrunde liegenden Daten verstanden wird, aber ich sehe keinen Grund, warum die KS -Statistik würde ‚ nicht gut als Maß für die Gleichheit von zwei Histogrammen funktionieren.
• Eine Erklärung, warum der Kolmogorov-Smirnov-Test für gruppierte Daten nicht geeignet ist wäre nützlich.
• Dies ist möglicherweise bei der Bildverarbeitung nicht so nützlich wie bei der statistischen Anpassungsbewertung. Bei der Bildverarbeitung wird häufig ein Histogramm von Daten als Deskriptor für einen Bereich eines Bildes verwendet, und das Ziel besteht darin, dass ein Abstand zwischen Histogrammen den Abstand zwischen Bildfeldern widerspiegelt. Über die allgemeine Bevölkerungsstatistik der zugrunde liegenden Bilddaten, die zum Abrufen des Histogramms verwendet wurden, ist möglicherweise wenig oder möglicherweise gar nichts bekannt. Beispielsweise würde sich die zugrunde liegende Bevölkerungsstatistik bei Verwendung von Histogrammen orientierter Gradienten basierend auf dem tatsächlichen Inhalt der Bilder erheblich unterscheiden.
• naught101 ‚ Die Frage wurde von beantwortet Stochtastic: stats.stackexchange.com/a/108523/37373

Sie suchen nach dem Kolmogorov-Smirnov-Test . Vergessen Sie nicht, die Balkenhöhen durch die Summe von zu teilen alle Beobachtungen jedes Histogramms.

Beachten Sie, dass der KS-Test auch einen Unterschied meldet, wenn z Die Mittelwerte der Verteilungen sind relativ zueinander verschoben. Wenn die Übersetzung des Histogramms entlang der x-Achse in Ihrer Anwendung nicht sinnvoll ist, möchten Sie möglicherweise zuerst den Mittelwert von jedem Histogramm abziehen.

Kommentare

• Durch Subtrahieren des Mittelwerts wird die Nullverteilung der KS-Statistik geändert. @ David Wright erhebt ohnehin einen berechtigten Einwand gegen die Anwendung des KS-Tests auf Histogramme.

As Davids Antwort weist darauf hin, dass der Chi-Quadrat-Test für gruppierte Daten erforderlich ist, da der KS-Test kontinuierliche Verteilungen voraussetzt. In Bezug darauf, warum der KS-Test unangemessen ist (Kommentar von naught101), wurde das Problem im angewandten Fall diskutiert Statistikliteratur, die es wert ist, hier angesprochen zu werden.

Ein amüsanter Austausch begann mit der Behauptung ( García-Berthou und Alcaraz, 2004 ), dass ein Drittel der Nature-Papiere statistische Fehler enthält. Ein nachfolgendes Papier ( Jeng, 2006 , „ Fehler bei statistischen Tests von Fehlern bei statistischen Tests “ – vielleicht mein All- Zeitfavoritentitel) zeigten, dass Garcia-Berthou und Alcaraz (2005) KS-Tests für diskrete Daten verwendeten, was dazu führte, dass sie in ihrer Metastudie ungenaue p-Werte berichteten. Das Papier von Jeng (2006) bietet eine nette Diskussion des Problems und zeigt sogar, dass man den KS-Test so modifizieren kann, dass er für diskrete Daten funktioniert. In diesem speziellen Fall läuft die Unterscheidung auf den Unterschied zwischen einer gleichmäßigen Verteilung der nachfolgenden Ziffer auf [0,9], $$ P (x) = \ frac {1} {9}, \ (0 \ leq x \) hinaus leq 9) $$ (im falschen KS-Test) und eine Kammverteilung von Delta-Funktionen, $$ P (x) = \ frac {1} {10} \ sum_ {j = 0} ^ 9 \ delta (xj) $ $ (in der richtigen, geänderten Form).Aufgrund des ursprünglichen Fehlers lehnten Garcia-Berthou und Alcaraz (2004) die Null fälschlicherweise ab, während der Chi-Quadrat- und der modifizierte KS-Test dies nicht tun. In jedem Fall ist der Chi-Quadrat-Test in diesem Szenario die Standardauswahl, auch wenn KS so geändert werden kann, dass er hier funktioniert.