Algorithmen zur Kundensegmentierung

Heuristische, semiparametrische und parametrische Clusterverfahren

Patrick Mair

InhaltEinführung Nichtprobabilistische Clusterung

Hierarchische Clusterverfahrenk-means Clusterung

Semiparametrische Clusterung2-Step Cluster Analysis

Parametrische ClusterverfahrenMischverteilungsansätzeEM-AlgorithmusLatent Class Analyse

Ausblick

Einführung

Aufgabe von Segmentierungsalgorithmen Gruppieren von BeobachtungenAuffinden von TypenErmittlung von Segmenten

Anwendungsbereiche der ClusteranalyseMarketingTelekommunikationMedizin, BiologieSoziologie, Psychologie…

Hierarchische Clusteranalyse

Clusterbildung basiert auf DistanzmaßDatenvektor standardisierenDistanzen zwischen allen möglichen „Paaren“ berechnenSukzessives aggregieren von Clustern

DistanzmaßeEuklidische Distanz

Generell: Minowski-Metrik

( )2

1

p

XY j jj

D x y=

= −∑

Hierarchische Clusteranalyse

Erste ClusterbildungJede Beobachtung 1 ClusterDistanzmatrix berechnen

Usability Portal

11109876543P

erso

nalis

ieru

ng

11

10

9

8

7

6

5

4

3

ID

S6

S5

S4

S3

S2

S1

ID Usability Personal

S1 7 7

S2 5 4

S3 10 9

S4 9 10

S5 4 5

S6 8 7

S1 S2 S3 S4 S5 S6

S1 -

S2 13 -

S3 13 50 -

S4 13 52 2 -

S5 13 2 2 50 -

S6 1 18 8 10 20 -

* Quadrierte Euklidische Distanzen

Hierarchische Clusteranalyse

Weitere ClusterbildungBeobachtungen mit kleinster Distanz gruppierenDistanzen neu berechnen

MethodenZentroid-MethodeSingle-LinkageComplete-LinkageAverage-LinkageWard-Methode

S2 S3 S4 S5 S1& S6

S2 -

S3 50 -

S4 52 2 -

S5 2 2 50 -

S1&S6 15.25 10.25 11.25 16.25 -

ID Usability Personal

S1 & S6 7.5 7

S2 5 4

S3 10 9

S4 9 10

S5 4 5

Hierarchische ClusteranalyseEnde der Gruppierung

Wiederholen der vorherigen Schritte bis 1 Cluster übrigDendrogramm

Wieviele Cluster?Heuristische-Inhaltliche VorgangsweiseRoot-mean-squared standard deviation (RMSSTD)R-Quadrat (R²)Distanz zwischen den Clustern

Rescaled Distance Cluster Combine

C A S E 0 5 10 15 20 25Label Num +---------+---------+---------+---------+---------+

S1 1 ----------------S6 6 -- --------------------------------S3 3 ---------------- ---S4 4 --S2 2 ----------------------------------------------S5 5 --

Hierarchische Clusteranalyse

Anwendung im Data Mining kritisch!Computational aufwendig, da im ersten Schritt jede Beobachtung ein einzelner Cluster

DatenverdichtungEindimensionale ClusterrichtungMultidimensionale Datenraum wird reduziertNachfolgende Verfahren besser geeignet

VorteilErlaubt Einblick in ClustergenerierungClusteranzahl post-hoc bestimmbar

K-means Clustering

Nichthierarchischer ClusteransatzAnzahl der Cluster müssen a-priori bestimmt werden

Idee der ClustergenerierungCluster in sich möglichst homogenCluster untereinander möglichst heterogen

Schritte der Clustergenerierung 1. K Cluster Zentroide wählen2. Jede Beobachtung einem Cluster zuordnen3. Clusterzentroide neu berechnen4. Weiter mit Schritt 2 bis Abbruchkriterium erfüllt

K-means ClusteringKids Version“ oder „Das K-Means Märchen”

…es war einmal ein Land mit N Häusern…K Könige kamen ins Land.Jeder König zog ins „erste“ Haus ein. Die Leute wollten, dass er seinen Thron in die Mitte des Dorfes verlegtDies machten die Könige, aber plötzlich waren zusätzlicheHäuser näher, andere aber weiter weg.Sie übernahmen die neuen, gaben die entfernten ab und verlegten den Thron wieder ins Zentrum… usw.Irgendwann mussten sie den Thron nicht mehr bewegenund sie ließen sich dort nieder (und lebten glücklich bis ansEnde ihrer Tage...).

Applet

K-means ClusteringVorbemerkungen zum Datenmaterial

Verschiedene Skalenniveaus (kategoriell, metrisch)Euklidische Distanz

Schritt 1: Wählen der Clusterzentrenmaximin-Algorithmus in Clementine

Schritt 2: Zuordnung der Beobachtungen zu Cluster Euklidische Distanz

Schritt 3: Clusterzentroide neu berechnenClusterupdate

Schritt 4: AbbruchkriteriumFehlertoleranz, maximale Iterationsanzahl

( )2

1min

p

XC j jj

D x c=

= − →∑

* http://www.kovan.ceng.metu.edu.tr/~maya/kmeans/index.htm

( )( ) kkC X=

K-means Clustering

K-means im Data MiningComputational nicht aufwendig„Heuristische Erstlösung“ Clusterlösung nützlich als Startlösung für komplexere Methoden

NachteileClusteranzahl fix und nicht statistisch prüfbarDeterministische ZuordnungAusreißeranfällig

2-Step Clusteranalyse 2-Schritt semiparametrischer AnsatzSchritt 1: Pre-Cluster - Cluster Feature Tree (CF)*

Variablenvektoren werden einzeln (pro Beobachtung eingelesen) 1. Beobachtungsvektor – 1. SubclusterPrüfung, ob jeweiliger Vektor in einen Cluster passt, sonst neuen Cluster generierenEndknoten (leaf nodes) enthalten Datensätze und charakterisieren Subtypen, die im 2. Schritt zusammengefasst werdenAlle Daten in einem Endknoten werden durch die entsprechenden Statistiken (Mittelwert, Standardabweichung bzw. relative Häufigkeiten) repräsentiert. Das macht den Baum leichter zu speichern.Verzweigungsknoten, welche Informationen über die Zusammensetzung der zugehörigen Subknoten (child nodes) enthalten.

* BIRCH-Algorithmus (Zhang, Ramakrishnon, & Livny, 1996)

2-Step Clusteranalyse

Schritt 1: Pre-Cluster - Cluster Feature Tree (CF)*

2-Step Clusteranalyse

AusreißerhandlingAusreißer sind jede Daten, die in keinen Cluster passen. Falls auf Grund einer zu großen Anzahl der Endknoten ein Rebuilding notwendig wird, werden potenzielle Ausreißer vorübergehend eliminiert. Beobachtungen in einem CFTree Endknoten gelten als potenzielle Ausreißer, wenn die Kardinalität ihres Endknotens kleiner als 25% (DW) der maximalen Kardinalität eine Endknotens ist. Nachdem der Baum vollständig aufgebaut worden ist, wird versucht, die Ausreißer in den Baum zu integrieren. Jene Beobachtungen, die nicht passen, werden dann als Ausreißer angesehen

2-Step ClusteranalyseSchritt 2: Hierarchische Clusterung

Zu Beginn ist jeder Endknoten ein ClusterAlle Cluster werden miteinander verglichenDas Paar mit der geringsten Distanz wird zu einem neuen Cluster zusammengelegtLikelihood-Kriterium zur DistanzberechnungVorgang wird solange wiederholt bis nur mehr 1 Cluster übrig

ClusteranzahlBIC oder AIC für verschiedene Clusterlösungen berechnen

2-Step Clusteranalyse

ResumeeComputational effizientVerschiedene Skalenniveaus kein ProblemClusteranzahlen probabilistisch vergleichbarAusgabe in Clementine bzw. SPSS

Mischverteilungsansätze*

Parametrische Clusterung über Mischverteilungen„Einfache“ Verteilung

Ausgangspunkt: Dichte f(x)

Likelihood L:

ML- Schätzung: Maximiere L

( )2

2

21

1 1| , exp22

ni

i

xL μμ σσπσ=

⎡ ⎤−⎛ ⎞= −⎢ ⎥⎜ ⎟⎝ ⎠⎢ ⎥⎣ ⎦

∏x

log 0Lμ

∂=

∂μ

( )2

2

1 1exp22

ii

xf x μσπσ

⎡ ⎤−⎛ ⎞= −⎢ ⎥⎜ ⎟⎝ ⎠⎢ ⎥⎣ ⎦

* McLachlan & Peel, 2000

Mischverteilungsansätze

MischverteilungenMixed Density f(x)

Likelihood L

…nicht o.W. lösbar

( ) ( ) ( )2 21 1 2 2| , | ,i i if x f x f xπ μ σ π μ σ= +

( ) ( )2

1| ,

K

i k i kk

f x f xπ μ σ=

=∑

( ) ( )2

11

| , | , , ?n K

k i kki

L f xπ μ σ==

= ⇒ =∑∏x μ π μ π

Mischungsgewichte:

NB:

Clusteranzahl K mussfestgelegt werden

11

K

kkπ

=

=∑

0L L∂ ∂∧ =

∂ ∂μ π

EM-Algorithm*

„Philisophie“ zum Lösen der ML-GleichungenIterativer LösungsansatzExpectation-Maximization (EM)

Aufbereitung der L als „incomplete-data“ ProblemDaten: äquivalent dazu

Likelihood

Gruppenzugehörigkeit zik als unbekannte Zufallsvariable

( );ix k ( )1 2; , , , ,i i i ik iKx z z z z… …

( ) ( )1 1 1 1

log , | |n K n K

c ik k ik i i ki k i k

L z z f xπ= = = =

= +∑∑ ∑∑x z ψ θ { }0,1ikz ∈

* Dempster, Laird, & Rubin, 1977

EM-Algorithmus

Startlösung für Parametervektor festlegenZufällig oder mit Vorkenntnis

E-StepErwartungswert über log L (bzgl. Zik)

Posterior-Wahrscheinlichkeit, dass i-te Beobachtung xi zur k-ten Komponente gehört

(0)⇒ ψ

( ) ( )( ) ( ), log |m mQ E L⎡ ⎤= ⎣ ⎦ψ ψ x ψ

( ) ( ) ( ) ( )( )

( ) ( )( )

( ) ( )

1

|| 1|

|

m mk k i km

ik ik ik Km m

k k i kk

f xE Z p Z

f x

πτ

π=

= = = =

∑

θx x ψ

θ

EM-Algorithmus

M-StepUpdate der Mischungsgewichte

Update der Verteilungsparameter

Iterieren bis Konvergenz erreicht ist

( )( 1) ( )

1

1 nm m

k ikin

π τ ψ+

=

= ∑

( ) ( )( 1) ( )

1 1

log |: 0

K nm m

ikk i

Lτ+

= =

∂=

∂∑∑x θ

θ ψθ

( ) ( )( 1) ( )m mL L ε+ − <ψ ψ

Latent Class Analyse*

Parameterischer Clusteransatz auf kategoriale DatenParameter

Relative Klassengröße Klassenspezifischen Itemlösews.

Zentrale AnnahmeLokale stochastische Unabhängigkeit

m-Commerce Quesionnaire:1) Do you use m-banking?2) Do you use m-retail?3) Do you use m-ticketing?4) Do you use m-parking?

Person Item 1 Item 2 Item 3 Item4

1 1 1 0 0

2 0 0 0 1

…

n 1 0 1 0

Datenmatrix Xvi

Alternativ: mit Antwortmuster s ( )( )

( )

( )

1 1

2 2

2 2

0,0,0,0 8

0,0,0,1 14

0,1,0,0 1

0,0,0,0 8k k

s s

n

n

n

n

= =

= =

= =

= =

x

x

x

x

jπ

( )1|si j jip X K p= =

( ) ( )1| 1 sisixx

si si j ji jip X x K p p−

= = −

( ) ( )11

| 1 sisi

I xxs j ji ji

i

p K p p−

=

= −∏x

Lazarsfeld & Henry, 1968; siehe auch Formann, 1984

Latent Class AnalyseUnbedingte Wahrscheinlichkeit für Antwortmuster

Likelihood aufstellen

Likelihood prinzipiell lösbar, kann aber passieren, dassEM-Algorithmus (IPF als Spezialfall davon)

Zuordnung der Personen zu Klassen (Posterior im E-Step)Ws., Klasse Kj anzugehören, wenn Person i Muster s gezeigt hat

( ) ( ) ( )2

1 1

| , , ?I

sn

nvi s

v s

L x p x p= =

= = ⇒ =∏ ∏p π x π p

( ) ( )11 1

1 sisi

IG xxs j ji ji

j i

p p pπ−

= =

= −∑ ∏x

[ ]0,1jip ∉

( ) ( )( )

|| maxs j

j js

p Kp K j s

pπ= = →

xx