k-Means
Say we have n points x1,x2,…,xn. WewanttopartitionthemintoksetsS1,S2,…,Sk suchthatthecostofthe
partition, cpS1 , S2 , . . . , Sk q, is minimised:
nˆ ̇2
ÿ
cpS1,S2,…,Skq “ min dpxi,μjq i“1 jPrks
,
where μi is the mid-point of each cluster, i.e.,
1
μi “ |Si|
ÿ
j PSi
xj
⃝c -Trenn, King’s College London
2
k-Means
Say we have n points x1,x2,…,xn. WewanttopartitionthemintoksetsS1,S2,…,Sk suchthatthecostofthe
partition, cpS1 , S2 , . . . , Sk q, is minimised:
nˆ ̇2
ÿ
cpS1,S2,…,Skq “ min dpxi,μjq i“1 jPrks
,
where μi is the mid-point of each cluster, i.e.,
1
μi “ |Si| Note that xi and μi are vectors for i P rns.
ÿ
j PSi
xj
⃝c -Trenn, King’s College London
3
k-Means
Say we have n points x1,x2,…,xn. WewanttopartitionthemintoksetsS1,S2,…,Sk suchthatthecostofthe
partition, cpS1 , S2 , . . . , Sk q, is minimised:
nˆ ̇2
ÿ
cpS1,S2,…,Skq “ min dpxi,μjq , i“1 jPrks
where μi is the mid-point of each cluster, i.e.,
1
μi “ |Si| Note that xi and μi are vectors for i P rns.
̈ ̨ ̈ ̨ ̈ ̨
̊1‹ ̊3‹ ̊2‹ E.g.,ifS1 “tx1,x2uwithx1 “ ̊ ‹andx2 “ ̊ ‹,thenμ1 “ ̊ ‹
̋‚ ̋‚ ̋‚
243
ÿ
j PSi
xj
⃝c -Trenn, King’s College London
4
k-Means
1. Select k cluster centres arbitrarily.
2. Repeat until convergence: 2.1 AssignmentStep:
2.1.1 Assigneachpointtotheclusterwiththenearestmean 2.1.2 Si “ txj | dpxj,μiq ď dpxi,μlq for all l P rksu,
where each point is assigned to exactly one cluster Si. 2.2 UpdateStep:
2.2.1 Recalculatethemeanpointofthecluster 2.2.2μ“1ř x
i |Si| jPSi j
⃝c -Trenn, King’s College London
5
k-Means
⃝c -Trenn, King’s College London 6
k-Means: Example with Optimal Instance
Consider this example with four points. The optimal cluster is shown.
⃝c -Trenn, King’s College London 7
k-Means
We can see that if we start with sub-optimal clusters, and we never change them! This can be made arbitrarily bad (by increasing the width of the rectangle).
⃝c -Trenn, King’s College London 8
k-Means++
The way this can be solved is by using k-Means++
It can be shown that the approximation factor is at most Oplog kq.
⃝c -Trenn, King’s College London 9
k-Means++
1. Set the first centre to be one of the input points chosen uniformly at random, i.e., μ1 “uniformpx1,x2,…,xnq
2. Forclusteri“2tok:
2.1 For each point xj compute the distance to the nearest centre, i.e., calculate
dj “minldpxj,μlq
2.2 Openanewcentreatapointusingtheweightedprobabilitydistributionthatis
proportional to d2j . That is,
3. Continue with k-Means
⃝c -Trenn, King’s College London
10
d2j Prpnewcentreinxjq“ř d2
ll
k-Median
Say we have n points x1,x2,…,xn. WewanttopartitionthemintoksetsS1,S2,…,Sk suchthatthecostofthe
partition, cpS1 , S2 , . . . , Sk q, is minimised: nˆ ̇
ÿ
cpS1,S2,…,Skq “ min dpxi,μjq i“1 jPrks
,
where μi is the mid-point of each cluster, i.e.,
1
μi “ |Si|
ÿ
j PSi
xj
⃝c -Trenn, King’s College London
11
k-Median
Say we have n points x1,x2,…,xn. WewanttopartitionthemintoksetsS1,S2,…,Sk suchthatthecostofthe
partition, cpS1 , S2 , . . . , Sk q, is minimised: nˆ ̇
ÿ
cpS1,S2,…,Skq “ min dpxi,μjq i“1 jPrks
,
where μi is the mid-point of each cluster, i.e.,
Recall that k-Means uses
⃝c -Trenn, King’s College London
12
1
ÿ
μi “ |Si|
nˆ ̇2
ÿ
mindpxi,μjq i“1 jPrks
j PSi
xj
k-Median
K-Means minimises the Euclidean/geometric distance K-Medians minimises the Manhattan distance
Source: Wikipedia
⃝c -Trenn, King’s College London 13