27  K-keskmised

Klasterdamist võib mõista muuhulgas ka objektide kogumi mitmeks osaks tükeldamisena. See lähenemine ongi aluseks K-keskmiste klasterdamisele. Selle käigus jaotatakse tunnuste ruum osadeks nii mitu korda, kui on vaja, et iga objekt oleks võimalikult lähedal ühele klastri keskpunktile. See keskpunkt on klastrikeskmine (centroid) ning klastrikeskmiste ja seega ka soovitud klastrtite arv \(K\) tuleb määrata enne klasterdamist.

Selle klasterdamise eesmärk on jaotada objektid \(x_i\) klastritesse arvul \(K\) nii, et kaugused iga objekti ja samasse klastrisse kuuluvate objektide keskpunkti vahel oleksid võimalikult väikesed. Selleks määratakse iga objekt lähima klastrikeskmise alusel ühte klastrisse ja seejärel arvutatakse igasse klastrisse kuuluvate objektide keskpunktid \(\bar x_1, ... \bar x_K\). Kõige sobivamad klastrikeskmised saadakse korduvalt minimeerides funktsiooni \[ESS = \sum^K_{k = 1} \sum_{c(i)=k} (x_i - \bar x_k)^T(x_i - \bar x_k),\] kus \(c(i)\) on objekti \(x_i\) sisaldav klaster.

Important

K-keskmiste klasterdamist (k-means clustering) kasutades jaotatakse objektide kogum korduvalt osadeks, liigutades igal korral eelnevalt määratud arvul klastrikeskmisi. Klastrikeskmisi liigutatakse selliselt, et kõikde objektide kauguste summa nende lähimast klastrikeskmisest oleks võimalikult väike.

Võrreldes mõne muu klasterdamise meetodiga k-keskmiste klasterdamine

Protsess kõige sobivamate klastrikeskmiste leidmiseks hõlmab järgnevaid samme.

  1. Arvutatakse kauguste maatriks, milles on kaugused objektide ja (esimesel kordusel enamasti juhuslikult määratud) \(K\) klastrikeskmise vahel.
  2. Iga objekt määratakse sellesse klastrisse, mille klastrikeskmisele see kõige lähemal on.
  3. Vastavalt tekkinud uutele klastritele arvutatakse uued klastrikeskmised.
  4. Eelnevaid samme korratakse senikaua, kuni iga objekt asub klastris, mille keskmisele see kõige lähemal on.

27.1 Klastrite leidmine

Alljärgnevas klasterdamise näites kasutame enne 1983. aastat tootmises olnud autode mudelite andmeid. Üritame jaotada autod klastritesse mitmesuguseid mõõtmeid ja teisi suurusi iseloomustavate tunnuste alusel. Sisestame klasterdamiseks kasutatavad arvtunnused lihtsuse huvides eraldi objekti.

library('magrittr')
autod <- read.csv('andmed/vehicles1983.csv')
str(autod)
'data.frame':   392 obs. of  9 variables:
 $ mpg         : num  18 15 18 16 17 15 14 14 14 15 ...
 $ cylinders   : int  8 8 8 8 8 8 8 8 8 8 ...
 $ displacement: num  307 350 318 304 302 429 454 440 455 390 ...
 $ horsepower  : int  130 165 150 150 140 198 220 215 225 190 ...
 $ weight      : int  3504 3693 3436 3433 3449 4341 4354 4312 4425 3850 ...
 $ acceleration: num  12 11.5 11 12 10.5 10 9 8.5 10 8.5 ...
 $ year        : int  70 70 70 70 70 70 70 70 70 70 ...
 $ origin      : chr  "American" "American" "American" "American" ...
 $ name        : chr  "chevrolet chevelle malibu" "buick skylark 320" "plymouth satellite" "amc rebel sst" ...
autotunnused <- autod[, 1:7]

Arvtunnused mõõdavad erinevaid nähtusi ja on nii ka väga erinevatel skaaladel. Seetõttu on vajalik need väärtused enne igasuguste kauguste mõõtmist tunnuste ruumis ühtlasele skaalale viia. Samuti ei saa me mõõta kaugusi, kui mõnede vaatluste asukoht tunnuste ruumis on teadmata. Seega tuleb sellised vaatlused välja arvata.

head(autotunnused)
  mpg cylinders displacement horsepower weight acceleration year
1  18         8          307        130   3504         12.0   70
2  15         8          350        165   3693         11.5   70
3  18         8          318        150   3436         11.0   70
4  16         8          304        150   3433         12.0   70
5  17         8          302        140   3449         10.5   70
6  15         8          429        198   4341         10.0   70
autotunnused %<>% scale %>% na.omit
head(autotunnused) %>% round
     mpg cylinders displacement horsepower weight acceleration year
[1,]  -1         1            1          1      1           -1   -2
[2,]  -1         1            1          2      1           -1   -2
[3,]  -1         1            1          1      1           -2   -2
[4,]  -1         1            1          1      1           -1   -2
[5,]  -1         1            1          1      1           -2   -2
[6,]  -1         1            2          2      2           -2   -2

Seoseid arvtunnuste vahel saame ilmestada paariviisiliste hajuvusjoonistega.

pairs(autotunnused, pch = 20, cex = .2, oma = c(2,2,2,2))

Kuigi tunnuste paariviisilisel uurimisel ei ilmne klastreid, võivad need siiski olla peidus mitme tunnuse hajuvuses. Paljude tunnuste hajuvust saame enamasti suurel määral ilmestada kahe peakomponendiga.

peakomponendid <- prcomp(autotunnused)
plot(peakomponendid$x[, 1:2], pch = 20)

Saame jooniselt eristada vähemalt kolm punktikogumikku. Seega võiks nende tunnuste alusel autod jaotada kolmeks sisemiselt sarnaseks rühmaks. R keeles saame k-kesmiste alusel klastrid arvutada funktsiooniga kmeans(), mille argumendi centers väärtuseks peame sisestama soovitud klastrite arvu (või iga soovitud klastri algsed keskpunktid). Leiame alustuseks kolm klastrit.

kkesk <- kmeans(autotunnused, centers = 3)
kkesk
K-means clustering with 3 clusters of sizes 138, 154, 100

Cluster means:
         mpg  cylinders displacement horsepower     weight acceleration
1  1.0950451 -0.8374221   -0.8335268 -0.7870762 -0.8530516    0.4273365
2 -0.2548908 -0.2043414   -0.1960231 -0.2407849 -0.1142129    0.2808791
3 -1.1186304  1.4703282    1.4521425  1.4569738  1.3530991   -1.0222782
        year
1  0.8041935
2 -0.3276197
3 -0.6052528

Clustering vector:
  [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 2 2 2 2 2 2 2 2
 [38] 3 3 3 3 3 3 3 2 2 2 2 2 2 1 2 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 2 3 3 3
 [75] 3 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 1 3 3 3 3 2 2 2 2 2
[112] 2 2 2 3 3 1 2 2 2 3 2 2 3 2 2 2 1 2 1 2 2 2 2 3 3 3 3 3 1 1 2 1 1 1 2 2 2
[149] 2 1 2 2 2 2 3 3 3 3 2 2 2 2 2 3 3 1 2 2 2 2 1 2 2 1 2 2 2 2 2 1 1 1 2 1 1
[186] 3 3 3 3 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 2 2 3 2 2 2 3 3 3 3 1 1 1 1 1 3 2 3
[223] 3 2 2 2 2 3 3 3 3 1 2 1 2 1 1 1 1 2 2 2 1 1 1 1 1 2 3 3 2 2 2 1 2 2 2 2 2
[260] 2 3 3 3 3 1 1 1 1 2 2 2 1 2 2 2 2 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 2
[297] 3 1 2 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[334] 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1
[371] 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1

Within cluster sum of squares by cluster:
[1] 295.6675 421.0669 211.1070
 (between_SS / total_SS =  66.1 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
[6] "betweenss"    "size"         "iter"         "ifault"      

Funktsioon väljastab mitmesuguseid parameetreid klasterdamise protsessi ja tulemuste kohta. Igale vaatlusele saame määrata andmetabelisse klastri, kasutades funktsiooni kmeans() tulemuse osist cluster. Nt kuna sisestasime eelnevalt klasterdamise tulemuse objekti kkesk, siis saame iga vaatluse klastri kätte käsuga kkesk$cluster.

autod$klaster <- kkesk$cluster
head(autod)
  mpg cylinders displacement horsepower weight acceleration year   origin
1  18         8          307        130   3504         12.0   70 American
2  15         8          350        165   3693         11.5   70 American
3  18         8          318        150   3436         11.0   70 American
4  16         8          304        150   3433         12.0   70 American
5  17         8          302        140   3449         10.5   70 American
6  15         8          429        198   4341         10.0   70 American
                       name klaster
1 chevrolet chevelle malibu       3
2         buick skylark 320       3
3        plymouth satellite       3
4             amc rebel sst       3
5               ford torino       3
6          ford galaxie 500       3
Warning

Funktsioon kmeans() määrab klastri numbri juhuslikult, mistõttu võib samal klastril olla igal järgmisel klastrite leidmisel erinev number.

27.2 Klastrite arv

Kuna k-keskmiste korral leitakse sobivamad klastrid vaatluste kogumi korduva tükeldamise teel, siis ei ole selle tulemuseks klastrite hierarhiat, mida saaks kujutada puujoonisel. Nii ei saa kasutada puujoonist ka klastrite valimiseks.

Kõige sobivama klastrite arvu määramiseks saame aga kasutada nn Gap mõõdikut (Gap statistic). Selle mõõdiku väärtus iseloomustab, kui palju väiksemad on klastrisisesed kaugused teatud klastrite arvu korral olemasolevate andmete korral võrreldes ühtlase jaotusega andmetega. Kui klastrite lisamine annab väiksemad klastrisisesed kaugused, siis peaksime kasutama rohkem klastreid ja vastupidi. Sealjuures peame arvesse võtma ka mõõdiku usaldusvahemikke ja valima suurema klastrite arvu ainult juhul, kui mõõdiku vastavad usaldusvahemikud ei kattu mõõdiku usaldusvahemikega väiksema arvu klastrite korral.

Saame seda näitlikustada joonisega, mille saab tekitada funktsiooniga clusGap laiendusest cluster alljärgnevalt. Et teada saada klasterdamise tulemus erinevate klastrite arvuga, tuleb klasterdamist korrata ja selleks tekitame funktsiooni nimega kmFun().

library('cluster')
kmFun <- function(x, k) kmeans(x, k, nstart = 10)
kmG <- clusGap(autotunnused, kmFun, K.max = 10)
plot(kmG)

Antud joonisel on kujutatud, kui ühtsed klastrid me erineval arvul klastrite leidmisel saame. Peame joonise abil välja selgitama, millise klastrite arvu juures nende lisamine enam ühtsemaid klastreid ei anna. Näeme, et viie klastri kasutamine ei anna väiksemaid klastrisiseseid kaugusi kui nelja klastri korral. Seega on nende andmete klasterdamiseks sobilik kasutada hoopis nelja klastrit.

kkesk <- kmeans(autotunnused, centers = 4)
autod$klaster <- kkesk$cluster

27.3 Klastrite esitamine

Klastrite hierarhia asemel kujutatakse k-keskmiste alusel moodustunud klastreid enamasti hajuvusjoonisel, kus telgedel on kaks tunnuste peakomponenti ja klastrid on kujutatud erinevate värvidega.

plot(peakomponendid$x[, 1:2], pch = 20, col = autod$klaster)

Näeme, et esitatud kahe mõõtme alusel suutis algoritm üsna usutavalt vaatlused klastritesse jagada.

Vaatluse klastri määrab k-keskmise meetodi korral kõige lähem klastri keskpunkt, mis selgus korduva vaatluste jaotamis tulemusel nagu eelnevalt kirjeldatud. Funktsiooni kmeans() poolt väljastatud teabe seas on ka need klasterdamiseks kasutatud tunnuste keskmised saadud klastrite lõikes.

kkesk$centers
         mpg  cylinders displacement horsepower     weight acceleration
1 -1.2389554  1.4820530    1.6560424  1.8158112  1.4504539   -1.3279887
2 -0.2368393 -0.2460167   -0.2289452 -0.2463542 -0.1422559    0.2558054
3  1.1085960 -0.8455407   -0.8409902 -0.8052580 -0.8641792    0.4500535
4 -0.9035789  1.4310756    1.1415616  0.8931515  1.1805005   -0.4972196
        year
1 -1.1177572
2 -0.3333457
3  0.8058547
4  0.1530746

Need tunnuste keskmised väärtused klastrite lõikes toovad enamasti ilmekalt esile klastrite eripärad.

Klastritele iseloomustamiseks on veel võimalusi esitatud peatükis Peatükk 17.