Distanzmaße - Lehrstuhl für Wirtschaftsinformatik

Business Intelligence
Distanzmaße
05.11.2015
Lehrstuhl für Wirtschaftsinformatik
Univ.-Prof. Dr. Johannes Ruhland
Referent:
Vogel, Stephan
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Distanzmaße für nicht-kardinalskalierte Daten
• für Skalenniveaus
• nominalskaliert: Ausprägungen sind unterscheidbar
(Farben)
• ordinalskaliert: einfache Rangfolge der Ausprägung
(Schulnoten)
• messen Abstand zwischen zwei Objekten
• Distanzen werden hier durch Ähnlichkeiten gemessen
• hierdurch ist eine Clusterung von Daten möglich
Folie 2
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Hamming-Distanz
• benannt nach dem Mathematiker Richard Wesley Hamming
• vergleicht zwei gleichlange Vektoren miteinander
• Hamming-Distanz ist dabei die Summe der Unterschiede
zweier Vektoren
𝑔𝑒𝑔𝑒𝑏𝑒𝑛: 𝑉𝑒𝑘𝑡𝑜𝑟𝑒𝑛 𝑥 = 𝑥1 , … , 𝑥𝑛 ,
𝐻𝑎𝑚𝑚𝑖𝑛𝑔 𝐷𝑖𝑠𝑡𝑎𝑛𝑧 𝑒𝑛𝑑𝑙𝑖𝑐ℎ𝑒𝑠 𝐴𝑙𝑝ℎ𝑎𝑏𝑒𝑡
∆ 𝑥, 𝑦 = |{𝑗 ∈ 1, … , 𝑛 |𝑥𝑗 ≠ 𝑦𝑗 }|
𝑦 = 𝑦1 , … , 𝑦𝑛
𝐻𝑎𝑚𝑚𝑖𝑛𝑔 𝐷𝑖𝑠𝑡𝑎𝑛𝑧 𝐵𝑖𝑛ä𝑟𝑑𝑎𝑡𝑒𝑛
𝑛
∆ 𝑥, 𝑦 =
|𝑥𝑗 − 𝑦𝑗 |
𝑖=1
𝑗 ∈ 1, … , 𝑛
𝑥, 𝑦 ∈ {0, 1}
Folie 3
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Hamming-Distanz Anwendung
•
Fehlererkennung bei Code-Übermittlung
• Einigung auf Code-Wörter
• Hamming-Distanz ist ausschlaggebend für Erkennung und
Korrektur von Fehlern
• Iris-Scanner-Algorithmus
• Clustering von z.B. Kunden
Folie 4
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Ulam-Distanz
• misst den Unterschied zweier ordinal strukturierter Vektoren,
indem sie die minimalste Anzahl an Lösch-, Verschiebe- und
Einfüge-Operationen zählt, die dazu nötig sind den einen in
den anderen Vektor zu überführen.
• Ablauf der Operationen für einen Durchgang
1.
2.
3.
4.
Folie 5
Lösche oder schneide ein Element aus, welches nicht mit seinem
zugehörigen Element übereinstimmt.
Verschiebe die restlichen Elemente, um die Lücke zu entfernen.
Verschiebe die Elemente, um eine Lücke für das neue entsprechende
Element zu schaffen.
Füge das neue oder ausgeschnittene Element ein.
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Ulam-Distanz Anwendung
• Rechtschreibprüfung
• Genetik
• Clustering von Tickets
Folie 6
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Ulam-Distanz Anwendung
Folie 7
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Folie 8
A n we d u n g
A
A
A
A
n
n
n
n
we d
we d
we n d
we n d
u
u
u
u
n
n
n
n
g
g
g
g
Ausschneiden
Verschieben
Verschieben
Einfügen
A w e d u n g
A w
d u n g
A w n d u n g
w n d
wn d u
w
n d
wa n d
wa n d
u
n
u
u
u
n
g
n
n
n
g
g
g
g
1. Operation
we d u n g
1. Operation
Ausschneiden
Verschieben
Verschieben
Einfügen
A
Ausschneiden
Verschieben
Verschieben
Einfügen
2. Operation
1. Operation
Ausschneiden
Verschieben
Verschieben
Einfügen
2. Operation
A w e d u n g
Ausschneiden
Verschieben
Verschieben
Einfügen
2. Operation
Ulam-Distanz Anwendung
Ausschneiden
Verschieben
Verschieben
Einfügen
A
A
A
A
A
w e
e
e d
e d
e d
d u n
d u n
u n g
u n
r u n
A
A
A
A
A
d r u
d r u n
d
r u
d e r u
d e r u
n
g
n
n
n
g
g
g
g
g
g
g
g
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Hamming-Distanz vs. Ulam-Metrik
Eigenschaft
Hamming
Ulam
Vektorenlänge
Vektoren müssen gleiche Länge
haben
Vektoren können
unterschiedlich lang sein
Skalenniveau
ordinal- und nominalskalierte
Daten
ordinal- und nominalskalierte
Daten
Operationsaufwand niedrig
Hoch
Mögliche Elemente
gesamtes Alphabet
Folie 9
gesamtes Alphabet
Vertiefungsmodul Daten-, Informations-, Wissensmanagement
Literatur
• Christoph Beierle, Gabriele Kern-Isberner; Methoden
wissensbasierter Systeme: Grundlagen Algorithmen
Anwendungen; Springer-Verlag 2013; Seite 180 f..
• Moses Charikar, Robert Krauthgamer; Embedding the Ulam
metric into l1; erschienen in THEORY OF COMPUTING, Volume
2; THEORY OF COMPUTING 2006; Seite 208 ff..
• Teknomo Kardi; Online: http://people.revoledu.com/kardi/
tutorial/Similarity/HammingDistance.html ; Zugriff 03.11.15.
• Teknomo Kardi; Online: http://people.revoledu.com/kardi/
tutorial/Similarity/UlamDistance.html ; Zugriff 04.11.15.
Folie 10

Download Report