Grupowanie metodą k-średnich
Jacek Kluska
Politechnika Rzeszowska
2010
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 1 / 14
Na czym polega metoda grupowania k-średnich?
Algorytm grupowania k-średnich opracował J. MacQueen (1967) a
następnie J. A. Hartigan i M. A. Wong (1975).
Algorytm grupowania k-średnich służy do klasyfikacji, tzn.
grupowania obiektów na podstawie atrybutów do k grup.
Grupowanie polega na minimalizacji sumy kwadratów odległości
między danymi i odpowiednimi centrami grup (klastrów).
Celem grupowania k-średnich jest sklasyfikowanie danych.
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 2 / 14
Przykład
Dane są 4 obiekty będące danymi uczącymi; każdy obiekt ma 2 atrybuty.
Obiekt x y Klasa
Lekarstwo A 1 1 ?
Lekarstwo B 2 1 ?
Lekarstwo C 4 3 ?
Lekarstwo D 5 4 ?
1 2 4 5
M = xA xB xC xD =
1 1 3 4
Celem jest zgrupowanie tych obiektów do k = 2 grup lekarstw.
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 3 / 14
Przykład - c.d.
5
y
4
3
2
1
0
0 1 2 3 4 5 6
x
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 4 / 14
Algorytm grupowania k-średnich
Najpierw
określamy liczbę grup (klastrów) k,
zakładamy punkt centralny dla każdej grupy.
Jako początkowe punkty centralne możemy wybrać k losowo wybranych
obiektów lub k pierwszych obiektów.
Wykonaj kroki aż do osiągnięcia stanu stabilnego, tzn. gdy żaden
obiekt nie może opuścić grupy:
1
Wyznacz współrzędne punktów centralnych.
2
Wyznacz odległość między każdym obiektem i każdym punktem
centralnym.
3
Zgrupuj obiekty na podstawie minimalnej odległości (znajdz

najbliższy punkt centalny).
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 5 / 14
Przykład - c.d.: początkowe punkty centralne
Założenie. Początkowe punkty centralne: lekarstwo A, lekarstwo B:
c1 = [1, 1] , c2 = [2, 1]
5
y
4
3
2
1
0
0 1 2 3 4 5 6
x
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 6 / 14
Przykład - c.d.: odległości między obiektami a punktami
centralnymi
Dla xA = [1, 1] , xB = [2, 1] , xC = [4, 3] , xD = [5, 4], przyjmujÄ…c
odległość Euklidesową, w iteracji  0 otrzymujemy macierz odległości:
D0 = {di,j }2,4 = { ci - xj }2,4 , j " {A, B, C, D}
c1 - xA c1 - xB c1 - xC c1 - xD
D0 =
c2 - xA c2 - xB c2 - xC c2 - xD
0.00 1.00 3.61 5.00 grupa 1, (i = 1)
D0 =
1.00 0.00 2.83 4.24 grupa 2, (i = 2)
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 7 / 14
Przykład - c.d.: grupowanie obiektów
Dla
0.00 1.00 3.61 5.00 grupa 1
D0 =
1.00 0.00 2.83 4.24 grupa 2
wyznaczamy macierz grup (wskazanie minimalnego elementu w kolumnie)
1 Ô! di,j = minc=1,2 {dc,j }
G0 = {gi,j }2,4 , gi,j =
0 oth.
1 0 0 0 grupa 1
G0 =
0 1 1 1 grupa 2
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 8 / 14
Przykład - c.d. - iteracja 1: wyznaczenie punktów
centralnych
Wyznaczenie nowego punktu centralnego dla każdej grupy na podstawie
aktualnych przynależności
1 2 4 5 1 0 0 0 grupa 1
M = {mi,j }2,4 = , G0 =
1 1 3 4 0 1 1 1 grupa 2
g1,1xA + g1,2xB + g1,3xC + g1,4xD 1xA + 0xB + 0xC + 0xD
cnew = =
1
g1,1 + g1,2 + g1,3 + g1,4 1 + 0 + 0 + 0
= 1 1
g2,1xA + g2,2xB + g2,3xC + g2,4xD 0xA + 1xB + 1xC + 1xD
cnew = =
2
g2,1 + g2,2 + g2,3 + g2,4 0 + 1 + 1 + 1
11 8
=
3 3
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 9 / 14
Przykład - c.d. - iteracja 1: wyznaczenie macierzy
odległości i macierzy grup
11 8
Dla c1 = [1, 1] , c2 = , macierz odległości
3 3
c1 - xA c1 - xB c1 - xC c1 - xD
D1 = {di,j }2,4 =
c2 - xA c2 - xB c2 - xC c2 - xD
0 1.0 3.6056 5.0 grupa 1
=
3.1447 2.357 0.4714 1.885 6 grupa 2
macierz grup
1 1 0 0 grupa 1
G1 =
0 0 1 1 grupa 2
G1 = G0 Ò! kontynuuj iteracjÄ™.
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 10 / 14
Przykład - c.d. - iteracja 2: wyznaczenie punktów
centralnych
Wyznaczenie nowego punktu centralnego dla każdej grupy na podstawie
aktualnych przynależności
1 2 4 5 1 1 0 0 grupa 1
M = {mi,j }2,4 = , G1 =
1 1 3 4 0 0 1 1 grupa 2
g1,1xA + g1,2xB + g1,3xC + g1,4xD 1xA + 1xB + 0xC + 0xD
cnew = =
1
g1,1 + g1,2 + g1,3 + g1,4 1 + 1 + 0 + 0
3
=
1
2
g2,1xA + g2,2xB + g2,3xC + g2,4xD 0xA + 0xB + 1xC + 1xD
cnew = =
2
g2,1 + g2,2 + g2,3 + g2,4 0 + 0 + 1 + 1
9 7
=
2 2
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 11 / 14
Przykład - c.d. - iteracja 2: wyznaczenie macierzy
odległości i macierzy grup
3 9 7
Dla c1 = , c2 = , macierz odległości
1
2 2 2
c1 - xA c1 - xB c1 - xC c1 - xD
D2 = {di,j }2,4 =
c2 - xA c2 - xB c2 - xC c2 - xD
0.5 0.5 3.2016 4.6098 grupa 1
=
4.3012 3.5355 0.70711 0.70711 grupa 2
macierz grup
1 1 0 0 grupa 1
G2 =
0 0 1 1 grupa 2
G2 = G1 Ò! STOP.
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 12 / 14
Przykład - c.d.: rezultat
Macierz grup
1 1 0 0 grupa 1
G2 =
0 0 1 1 grupa 2
pokazuje, że
Obiekt x y Klasa
Lekarstwo A 1 1 1
Lekarstwo B 2 1 1
Lekarstwo C 4 3 2
Lekarstwo D 5 4 2
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 13 / 14
Przykład - c.d.: interpretacja wyniku
3 9 7
c1 = , c2 =
1
2 2 2
5
y
4
3
2
1
0
0 1 2 3 4 5 6
x
Jacek Kluska (Politechnika Rzeszowska) (k-means clustering) 2010 14 / 14