7. Similiarity Search

Question 1

Allgemein/Definition Similiarity Search

Nennen Sie Ausgewählte Anwendungsfälle

Answer 1

Suche nach ähnlichen Objekte (DM Basistechnik)
> zwei ähnliche Objekte haben oft gemeinsame Eigenschaften

Ausgewählte Anwendungsfälle:

• Nutzung der Ähnlickeit zur Klassifikation und Regression
• Gruppierung ähnlicher Objekte (Clustering)
• Wissen aus ähnlichen Fällen extrahieren (Medizin/Recht)
• Erstellung von Kaufempfehlung

Question 2

Similiarity Search in Verbindung mit Ähnlichkeits- u. Distanzmaße

Answer 2

Ähnlichkeiten von 2 Objekten wird anhand der Distanz bestimmt

Dafür gibt es unterschiedlcieh Distanzmaße für:

Numerische Attribute
> Euklidische Distanz
> Manhatten Distanz
> Minkowski Distanz

Nichtnumerische Distanzmaße für binäre, nominale und ordinale Werte
> Jaccard Distanz
> Cosine Distanz
> Edit Distanz

Question 3

Wie funktioniert die Anwendung von Neares-Neighbor -Algorithmus in Vorhersagemodellen

Answer 3

Vorhersagen der Zielvariable einer neuen Instanz durch:

• Suchen der ähnlichsten Instanzen in den Trainingsdaten (nearest Neighbor)
• Vorhersagen der Zielvariable basierend auf den Zielvariablen der ähnlichsten Instanzen (der NN)

2. Arten

Klassifizierung: Ableitung von der Klassenzugehörigkeit der NN

Wahrscheinlichkeitsabschätzungen: Wie viele der Nearest Neighbors gehören der Klassen an?

Regression: Vorhersage der Zielvariable durch Berechnung des Median oder des Durchschnitts

Question 4

NN, Anzahl der Nachbarn und ihre Gewichtung

Answer 4

> Bestimmung der optimalen Anzahl der Nachbarn
- k-NN Algorithmen (k = Anzahl der Nachbarn z.B. 3-NN)
Je größer k => Je größer die Glättung zwischen Nachbarn
Ähnlichkeiten zwischen Nachbarn sind unterschhiedlich
- Gewichtung der Meinungen? Gewichtete Abstimmung
- Anzahl der Nachbarn hat weniger Einfluss
(je größer k desto geringer der Abstand)

Question 5

Was sind die 3 Problemkategorie des Nearest Neighbor Ansatz in Verbindung mit Similarity Search

Answer 5

Verständlichkeit
> NN fehlt aber ein spezifisches Entscheidungsmodell
> Vermeidung von NN, wenn Begründung der Entscheidung und Verständlichkeit wichtig sind

Dimensionalität
> Distanzberechnung bezieht alle Merkmale mit ein
- Wertebereiche der Merkmale müssen normiert werden (z.B.: Einkommen, Anzahl, Kinder) => Transformieren in ein Maß)
- zu viele irrelevante Merkmale verwirrt die Distanzberechnung (Fluch der Dimensionalität)

Lösung:
> Merkmalsauswahl
> Einbau des Fachwissens in Distanzberechnung (Bestimmung der Gewichtung)

Effizienz der Berechnung
> Modellbildung erforder kaum Rechneraufwand
- Speicherung der Instanzen
> Vorhersage/Klassifizierung neuer Instanzen rechnenintensiv
- schnelle Vorhersagen schwierig

Lösung: Locality Sensitiv Hashing (LSH)
= hasht die Instanzen, sodass ähnliche Instanzen im selben Bucket abgelegt werden
- Suche nach NN kann dann innerhalb Buckets erfolgen