🏅
🏅
🏅
🏅
edu
Search…
⌃K

Clustering

Hilft dir meine Webseite weiter? Falls du dieses Projekt unterstützen möchtest, kannst du mir gerne einen Kaffee an paypal.me/markusbilz spenden. Danke.️
❤
​
F: Vergleichen Sie den k-means Clusteralgorithmus mit dem Basic Leader-Follower Algorithmus. Welches sind jeweils die Vor- und die Nachteile?
A:
  • Konzeptioneller Unterschied: K-means ist ein offline Learning-Verfahren. Der Leader-Follower-Algorithmus ein online-Verfahren.
  • Vorteil Basic Leader-Follower
    • Anzahl der zu bildenden Cluster muss nicht a priori festgelegt
      werden.
  • Vorteile
    kk
    -means
    • ​
      kk
      -means konvergiert typischerweise sehr schnell.
    • Konzeptionell einfach.
  • Nachteil
    kk
    -means
    • Anzahl Cluster
      kk
       ist exogener Parameter → erfordert Kenntnis
      über Datenbestand
    • Ungeeignet für nicht-konvexe Mengen
    • Kann nicht gut mit Rauschen und Ausreißern umgehen
    • Nur anwendbar, wenn (Cluster-) Mittelpunkt definiert ist →
      Schwierigkeiten bei kategorischen Daten.
  • Nachteil Basic Leader-Follower
    • Keine stabilen Cluster
F: Sie sind Leiter der technischen Abteilung der Universitätsbibliothek. Sie wollen den Empfehlungsdienst für Ihre Nutzer verbessern, indem Sie Nutzern einen Expertenstatus zuordnen (“Laie”, “Fortgeschrittener”, “Experte”). Diesen wollen Sie nutzen, um verbesserte Empfehlungen anzubieten (z.B. empfiehl nur Grundlagenwerke, falls der Nutzer Laie ist). Der Expertenstatus bezieht sich auf Fachgebiete, denen einzelne Bücher zuzuordnen sind.
Durch freiwillige Angaben können Nutzer ihren Expertenstatus zu bestimmten Büchern oder Fachgebieten angeben, Sie erhalten also einige Daten durch die Nutzerangaben selbst.
Welcher Clusteralgorithmus empfiehlt sich, um Ihren Nutzern Expertenstati zuzuordnen, und wieso? Welche Daten benötigen Sie zur Umsetzung des Clusterings und zur Nutzung der Ergebnisse für den Empfehlungsdienst?
A:
  • Die Anzahl der Cluster ist vorab bekannt mit 3 möglichen Ausprägungen. Aus diesem Grund sollte der iterative
    kk
    -means-Algorithmus verwendet werden.
  • Zum Clustering benötigt man Daten über die Nutzer. Diese könnten etwa die Anzahl bereits gelesener Dokumente, akademischer Grad, Selbsteinschätzung Vorkenntnisse o. Ä. sein.
  • Zur Nutzung im Recommendersystem reicht dann das Wissen, in welchem Cluster sich ein Nutzer befindet, aus. Hierfür muss aber ein Mapping bestehen, um zu interpretieren, welches Cluster den „Experten" o. Ä. entspricht.
F: Zur Kundendialogsteuerung sollen Entscheidungsbäumen eingesetzt werden. Erläutern Sie kurz, wie ein Entscheidungsbaum gelernt werden kann und wie er anschließend zur Dialogsteuerung verwendet wird.
A:
  1. 1.
    Zunächst ist ein Trainingsdatensatz und Testdatensatz mit Attributen zu ermitteln (z. B. 70 / 30). Attribute sind ggf. vorzuverarbeiten z. B. zu standardisieren. Weiterhin muss der Datensatz ein diskretes Klassenlabel (hier: Expertenstati), das vorhergesagt wird, enthalten.
  2. 2.
    Anhand der Entropie wird dann das Attribut mit dem höchsten durchschnittlichen Informationsgewinn ermittelt.
  3. 3.
    Man lernt den Baum solange weiter bis man keine Attribute mehr hat zum Erklären oder bis sich die Attribute nicht mehr verändern.
  4. 4.
    Der letzte Schritt kann das Pruning des gelernten Baums und die Evaluation des Baums auf nicht zum Training benutzte Testdaten sein. Gängige Maße zur Evaluation ist etwa die Accuracy. (Geyer-Schulz and Sonnenbichler 2017 S. 18, 19, 44)
F: Wie evaluieren Sie, ob gelernte Entscheidungsbäume gut für Ihr System geeignet sind?
A:
Aufteilen in Trainings- und Testdaten / Training:
Typischerweise wird der gesamte vorhandene Datenbestand in ein Trainingsset und ein Test Set gesplittet. Testdaten bleiben für das Training des Entscheidungsbaums außen vor. Der Baum wird auf Trainingsdaten gelernt.
Eine Variante ist k-fold cross validation mit folgendem Vorgehen:
  • Partitioniere das Datenset in
    kk
     Partitionen
  • Schätze
    kk
     hold-out Prädikator mit 1 Partition Validation Set und
    k−1k - 1
     Partitionen als Trainingsset, dann zweiter Durchlauf mit zweiter Partition zur Validierung und übrigen Partitionen zum Training. Analog wiederholen bis zum
    kk
    -ten Durchlauf.
Performance am Testdatensatz feststellen:
  • Das Test Set kann dann benutzt werden, um die prognostizierte Klasse z. B. Status Laie o. Ä. mit der tatsächlichen Klasse zu vergleichen. Die Performance lässt etwa mit einer Konfusionsmatrix darstellen. Typische abgeleitete Metriken sind Precision, Recall und Accuracy.
  • Obige Schritte mehrmalig wiederholen für statistische Sauberkeit. (Geyer-Schulz and Sonnenbichler 2017 S. 54)
F: Wozu dient Clusteranalyse?
A:
Entdecken einer natürlichen Struktur in Daten (Geyer-Schulz 2017 S. 6).
F: Was ist eine Segmentierungsbase, was eine Segmentierungsmethode?
A:
Segmentierungsbasen:
  • Variablen oder Kriterien für die Segmentierung
  • Auswahl auf Basis: Ziel der Segmentierung und des Marktes
Segmentierungsmethoden:
  • Methodenauswahl auf Basis: Ziel der Segmentierung und der
    Eigenschaften der Segmentierungsbasis.
F: Nennen Sie je zwei Beispiele für (beobachtbare-nicht beobachtbare) × (allgemeine-produktspezifische) Basen.
A:
Text
Allgemein
Produktspezifisch
Beobachtbar
Kulturell
Benutzerstatus
​
Geographisch
Benutzungsfrequenz
​
Soziökonomisch
Store Loyalty
​
​
Situationen
​
…
…
Nicht beobachtbar
Psychographisch
Psychographisch
​
Werte
Nutzen
​
Persönlichkeit
Wahrnehmung
​
Life-Style
Präferenzen
​
​
Absichten
​
…
…
F: Wie bewerten Sie, ob sich zwei Datenpunkte ähnlicher sind als andere? Nennen Sie zwei Beispiel-Maße.
A:
Normalisiertes, inneres Produkt:
s(x1,x2)=x1⋅x2 ∥x1 ∥ ∥x2 ∥s\left( x_{1},x_{2} \right) = \frac{x_{1} \cdot x_{2}}{\left. \ \parallel x_{1} \right.\ \parallel \left. \ \parallel x_{2} \right.\ \parallel}
Anteil der gemeinsamen Attribute:
s(x1,x2)=x1Tx2ds\left(x_{1}, x_{2}\right)=\frac{x_{1}^{T} x_{2}}{d}
F: Nennen Sie einen Anwendungsfall, wie Clusteranalyse in einem Recommenderdienst verwendet werden kann.
A:
Movielens - Anhand der Ratings aus dem each-movie dataset werden durch Clusteranalyse Geschmacks bzw. Interessengruppen gebildet. - Aus diesen Geschmacks-/Interessen Gruppen wird für Werbezwecke ein E-Mailverteiler automatisch erzeugt. - Auf Basis der Geschmacks- und Interessens-Gruppen werden neue Filmrechte erworben, die den Nutzern gefallen könnten. (Geyer-Schulz 2017 S. 7)
Use Case: Sie arbeiten für Jupiter, einen großen, deutschlandweit operierenden Elektronikanbieter, der sein Online Geschäft ausbauen möchte. Sie sollen für die Abteilung Haushaltsgeräte einen Recommenderdienst für Kühlschränke aufbauen: Ähnliche Kühlschränke sollen auf der jeweiligen Produktseite einander gegenüber gestellt werden, damit der Kunde diese besser vergleichen kann. Sie entscheiden sich deshalb für einen inhaltsbasierten Recommender auf Basis von Clusterverfahren. Ohne Use Case Bezug max. die Hälfte der Punkte!
F: Definieren Sie als erstes den “Feature Space” für Kühlschränke, in dem Sie jeden Kühlschrank mit einem Vektor
xix_{i}
 beschreiben, also Kühlschrank 1 mit
x1x_{1}
, Kühlschrank 2 mit
x2x_{2}
 usw.
xix_{i}
 ist dabei selbst ein k-dimensionaler Vektor mit
kk
 Eigenschaften des Kühlschranks. Geben Sie ein konkretes Beispiel mit 5 Dimensionen, wie ein
xix_{i}
 aussehen könnte und überlegen Sie sich, welche Eigenschaften Sie im Use Case abbilden wollen.
A:
5-Dimensionaler Feature Space mit den Dimensionen Energieeffizienz, Preis, Farbe, Einbaugerät und Eiswürfeleinheit.
Binäre / Nominale Attribute werden konvertiert in Abstand
  • Einbaugerät und Einbaugerät: Ja → 1, Nein → 0.
  • Preis wird standardisiert.
  • Energieeffizienzklasse wird auf Skala von 0-1 gemappt.
  • Farbe wird auf Skala von 0-1 gemappt.
Dimensionen
Kühlschrank 1
Kühlschrank 2
Kühlschrank 1 (standardisiert)
Kühlschrank 2 (standardisiert)
Energieeffizienz
A++
C
0
0.6
Preis
500 EUR
150 EUR
0.7
0.2
Farbe
Space Grey
Weiß
0.8
0
Einbaugerät
Ja
Nein
1
0
Eiswürfeleinheit
Ja
Nein
1
0
S=((00.70.811),(0.60.2000))S=\left(\left(\begin{array}{c} 0 \\ 0.7 \\ 0.8 \\ 1 \\ 1\end{array}\right),\left(\begin{array}{c}0.6 \\ 0.2 \\ 0 \\ 0 \\ 0\end{array}\right)\right)
F: Sie stellen einen Werkstudenten ein, der alle bei Jupiter gelisteten Kühlschränke mit den
kk
 Dimensionen erfasst. Sie erhalten als Ergebnis
nn
 _
kk
-dimensionale Vektoren __
x1,x2,…,xnx_1, x_2, \ldots, x_n
. Beschreiben Sie kurz 3 Praxis-Probleme, auf die der Werkstudent Ihrer Erwartung nach bei der Aufbereitung der Daten stoßen wird._
A:
  1. 1.
    Nominale Attribute z. B. Einbaukühlschrank vs. Freistehend müssen in Dimension abgebildet werden.
  2. 2.
    Standardisierung von Attributen z. B. müssen einzelne Attribute standardisiert werden. Würde man z. B. Temperatur (z. B. 4 - 10) und Preis (100 - 2.000) als solches beim Abstandsmaß Euklidische Distanz verwenden, wäre das Distanzmaß stark verfälscht, weil Preis Abstand stark verfälschen würde.
  3. 3.
    Fehlende Daten z. B. könnte Produktbeschreibung der Hersteller unvollständig sein. Es braucht dann eine Strategie, um fehlende Werte aufzufüllen.
  4. 4.
    Redundante Daten z. B. können Kühlschränken in mehreren Farben angeboten wären. Mit Ausnahme der Farbe hätten diese Kühlschränke eine ähnliche Position im Raum, würden dann wegen der hohen Ähnlichkeit empfohlen werden. Eigentlich handelt es sich aber um eine „schlechte / triviale Empfehlung".
  5. 5.
    Erfassungsfehler z. B. kann Werkstudent Fehler bei Datenerfassung machen, was zu fehlerhaften Empfehlungen führt.
F: Sie möchten nun die
nn
 Kühlschränke in
cc
 Partitionen trennen.
M1, m2, …, mcM_{1},\, m_{2},\,\ldots,\, m_{c}
 seien die c Clustermittelpunkte der Partitionen
D1, D2, …, DcD_{1},\, D_{2},\,\ldots,\, D_{c}
. Welches Kriterium (exakt: Zielfunktion) setzen Sie an? Geben Sie die Formel mit der hier verwendeten Notation an und erklären Sie alle Bestandteile!
A:
Man minimiert die Summe der Varianzen. Die Criterion Function ist definiert als:
J=∑i=1c∑xj∈Di ∥xj−mi ∥2,J = \sum_{i = 1}^{c}\sum_{x_{j} \in D_{i}}\left. \ \parallel x_{j} - m_{i} \right.\ \parallel^{2},
wobei
mim_{i}
, der Mittelwert der Partition
DiD_{i}
, definiert ist als:
mi=1ni∑xj∈Dixj.m_{i} = \frac{1}{n_{i}}\sum_{x_{j} \in D_{i}} x_{j}.
Man iteriert also über jeden Punkt im Cluster und berechnet die Distanz zu zum Cluster-Mittelpunkt und wiederholt das Vorgehen für jedes Cluster. Das Ergebnis wird aufsummiert. Oberhalb wird die quadrierte Norm verwendet. Liegt ein Punkt im falschen Cluster wird die Summe entsprechend groß. (Geyer-Schulz 2017 S. 25)
Problem: Man versucht eigentlich
JJ
 zu minieren (minimales Varianz-Kriterium). Hat man genauso viele Cluster wie Datenpunkte, dann ist
J=0J = 0
 wenig aussagekräftig (Geyer-Schulz 2017 S. 29)
F: Wie heißt der Fachausdruck für den “Abstand” zwischen zwei Datenpunkten
xax_{a}
 und
xbx_{b}
? Schlagen Sie eine geeignete konkrete (!) Metrik für Ihren Feature Space (aus Teil 1!) vor.
xi,kx_{i,k}
 notiere dabei die Merkmalsausprägung
kk
 des Kühlschranks
ii
.
A:
  1. 1.
    Der Fachbegriff ist Ähnlichkeitsmaß. (euklidischer Abstand)
  2. 2.
    Verhältnis der gemeinsamen Attribute zur Anzahl der Attribute in
    x1x_{1}
     oder
    x2x_{2}
     „Tanimoto"-Distanz:
s(x1,x2)=x1Tx2x1Tx1+x2Tx2−x1Tx2s\left( x_{1},x_{2} \right) = \frac{x_{1}^{T}x_{2}}{x_{1}^{T}x_{1} + x_{2}^{T}x_{2} - x_{1}^{T}x_{2}}
F: Nach welchem Kriterium wählt der Algorithmus “iterative k-means” die optimale Anzahl der Cluster aus? Wie bestimmt man allgemein die optimale Anzahl der Cluster?
A:
Die Anzahl der Cluster ist ein exogener Parameter beim
kk
-means-Algorithmus. Muss also durch den Nutzer vorgegeben werden.
Ansätze, um das optimale
kk
 zu finden:
​
H0H_{0}
: es sind
cc
 Cluster, da
(J(c))(J(c))
H1H_{1}
: es sind
c+1c+1
 Cluster, da
(J(c+1))(J(c+1))
.
J(c)−J(c+1)≤ε und P(H1wahr∣J(c)−J(c+1)≤ε)≤θ,J(c)-J(c+1) \leq \varepsilon \text { und } P\left(H_{1} \text{wahr} \mid J(c)-J(c+1) \leq \varepsilon\right) \leq \theta,
Wir akzeptieren
H0H_{0}
, wenn:
… wenn also Wahrscheinlichkeit, dass
H1H_{1}
 trotz dieser “geringen” Abnahme von
J(c+1)J(c+1)
 verglichen mit
J(c)J(c)
 stimmt, akzeptabel klein ist. (Geyer-Schulz 2017 S. 29)

Quellen

Geyer-Schulz, Andreas. 2017. “Cluster-Analyse.”
Geyer-Schulz, Andreas, and Andreas Sonnenbichler. 2017. “Verkaufsunterstützung Mit Hilfe von Entsheidungsbaumverfahren.”
Previous
Collaborative Filtering
Next
Cluster Modularity
Last modified 4mo ago