Увод у невођено учење: Кластеризација
До сада смо се сретали само са примјерима вођеног учења. То је значило да су наши подаци били означени (енг. \(labeled\)), тј. за дате податке знали смо вриједност зависне промјенљиве \(Y\). На основу познатог узорка правили смо модел, који смо послије користили на новим подацима.
Код невођеног учења не постоји зависна промјенљива \(Y\). Просто су нам дати подаци и ми сами треба да одлучимо шта са њима да радимо. Овдје се, поред непостојања зависне промјенљиве, отварају и многи други проблеми:
- Како провјерити тачност добијених резултата, када немамо са чиме да их упоредимо?
- Како извршити подјелу скупа на валидацију и тест?
- У зависности од циља, постоји ли више (и колико тачних рјешења)?
Једна од основних грана невођеног учења јесте кластеризација (кластеровање).
Кластеризација: теоријски увод
Кластеризација представља процес груписања података у групе (тзв. кластере) на тај начин да су подаци унутар кластера међусобно слични, а кластери међусобно што различитији.
Напомена: Наш појам кластера није исти као из теорије узорака! Оно што се у машинском учењу зове кластер, у теорији узорака звало би се стратум.
Потребе за кластеризацијом су многе, а неке од њих укључују издвајање група на друштвеним мрежама зарад циљаног оглашавања, детекција малигног и бенигног ткива на рендгенским снимцима, раздвајање људи у групе на основу разних психолошких тестова итд. Такође, кластеризација се може користити у сврхе претпроцесирања података, тако што у првом кораку обраде података кластери бивају замјењени својим представницима. Ово може бити корисно у смислу рачунске једноставности, али у зависности од ситуације може и смањити квалитет модела.
Такође, кластеризација је корисна и за кросвалидацију. Наиме, веома је корисно подијелити податке на кластере, те затим сваки од кластера на \(k\) једнаких дијелова, те фолдове за \(k-fold\) правити тако што се бира по један из сваког кластера. Тиме су фолдови учињени репрезентативнијим него што би потенцијално били случајним одабиром.
Треба напоменути и да кластеризација није јединствена, јер увијек можемо разматрати грубље, односно финије подјеле. Већина алгоритама за кластеризацију омогућава подешавање (“штеловање”) финоће самог процеса.
У вези са претходним разликујемо и различите врсте кластера: Глобуларни или центрички кластери јесу они који попуњавају унутрашњост лопте или евентуално елипсоида (у одговарајућем броју димензија, не мора три). Кластери су добро раздвојени уколико је свака тачка неког кластера ближа свим тачкама свог кластера неголи било којој тачки неког другог кластера. Кластери су хијерархијски, уколико у оквиру кластера можемо уочавати кластере.
\(K-means\) кластеризација
Један од најједноставнијих типова кластеризације јесте \(K-means\) кластеризација, или, на српском, кластеризација \(K\)-средина. Сада ћемо изложити како алгоритам ради.
За почетак, бира се број кластера, \(K\). Очекује се да овај број буде процјењен на основу претходних сазнања о подацима. Бира се \(K\) такозваних центроида, односно центара кластера, на случајан начин. Ако се зна нешто више о подацима, овај одабир свакако не мора бити случајан, и пожељније је да не буде. Затим се понављају следећи кораци:
За сваку опсервацију рачунамо којој је центроиди најближа. Када срачунамо, додијелимо јој кластер који одговара тој центроиди.
Рачунамо центар новодобијеног кластера и у њега премијештамо центроиду.
Претходна два корака понављамо све док процес не исконвергира. У вези са \(K-means\) кластеризацијом треба напоменути пар ствари:
- Одабир метрике. Особина “бити најближа центроиди” коју има нека опсервација зависи од одабира метрике. За нумеричка обиљежја, јер таква морају да буду пошто рачунамо просјеке, је то углавном еуклидска метрика, или, евентуално, нека од \(l^p\) метрика. За одабир еуклидске метрике \(d\), може се показати да \(k-means\) кластеризација заправо минимизује функцију
\[\sum_{i=1}^K \sum_{x\in C_i} d(x,c_i)^2,\]
гдје је \(C_i\) кластер а \(c_i\) центроида. Минимизација наравно иде по центроидама.
Како је у овом случају алгоритам заснован на минимизовању еуклдских растојања, он тежи проналаску кластера у облику лопте.
Кластеровање, макар и за фиксно \(K\), не мора да буде јединствено. На примјер, довољно је да имамо податке униформно распоређене унутар круга и да их треба поделити на два кластера. Такође, горња сума може имати локалне минимуме, који су већи од глобалног, и алгоритам у њима може да “заглави”. Због тога се у пракси кластеризација понавља више пута, са различитим почетним одабиром центроида, те се гледа шта буде у највећем броју случајева.
Одабир броја \(K\). Веома често није јасно колико кластера се очекује, те се не зна које \(K\) прослиједити алгоритму. Једно од правила јесте и “правило лакта”. Оно подразумева да се за различите вриједности броја \(K\) изврши кластеризација, те се у сваком од тих случајева срачуна унутаркластерна сума квадрата растојања, а затим се нацрта зависност збира тих сума у односу на \(K\), као на слици испод.
Бирамо оно \(K\) које је “на лакту”, јер након њега видимо заравњење у суми квадрата, што значи да је додавање нових кластера скоро па никако не смањује.
Мјешавина нормалних расподјела и ЕМ алгоритам
Предност алгоритма \(K-means\) свакако јесте његова једноставност. Међутим, појављују се и многи проблеми:
Свака опсервација била је додјељена тачно једном кластеру. Међутим, постоје опсервације које су “на граници”, и чије додјељивање кластеру јесте толико несигурно, да се може сматрати и случајним погађањем. Жељели бисмо да некако за такве опсервације сачувамо неодређеност.
Користи еуклидско растојање. Чак иако одаберемо неку од других \(l^p\) норми, облик кластера никад неће бити, рецимо, елипса. Шта ако кластер није кружан, већ елиптичан?
Након извршене кластеризације, исти је однос према подацима близу и далеко од центроиде кластера. А за ове ближе смо сигурнији.
Шта ако се кластери преклапају, као на слици испод?
Због тога ћемо изложити мало софистициранију верзију \(K-means\) алгоритма, која је позната под називом Мjешавина нормалних расподjела, у комбинацији са ЕМ алгоритмом. Користићемо скраћеницу \(GMM\), од енглеског \(Gaussian \, Mixture \, Model\). ЕМ алгоритам би требало да је, као концепт, познат са Математичке статстике, те му овдjе нећемо доказивати теоријска својства, већ ћемо их само наводити по потреби.
Идеја \(GMM\) алгоритма јесте да се опсервацијама, умјесто кластера коме припадају, додijели вjероватноћа припадања сваком од кластера. За почетак, треба дефинисати број кластера, \(C\), што и овдjе радимо “од ока” или на основу неких сазнања о подацима “са стране”. Рецимо да имамо \(n\) опсервација и \(d\) предиктора. Ако погледамо на слику изнад, дјелује нам да су подаци дати у виду три дводимензионе нормалне расподјеле. Ако се подсјетимо, густина вишедимензионе нормалне расподјеле зависи од вектора просека \(\mu\) и од коваријационе матрице \(\Sigma\), а дата је формулом:
\[f_{\mu, \Sigma}(x) = \frac{|\Sigma|^{-1/2}}{(2\pi)^{d/2}} \exp (-(x-\mu)^T\Sigma^{-1}(x-\mu)).\]
Сада је природно задати густину свих наших података као неку конвексну комбинацију густина појединачних кластера:
\[f(x) = \sum_{c=1}^C \pi_cf_{\mu_c,\Sigma_c}(x).\]
Идеја је да се крене од произвољних параметара \(\pi_c\), \(\mu_c\) и \(\Sigma_c\), те да се они итеративно “побољшавају”. Једну илустрацију густине \(f\) можемо видјети на слици испод.
Густина \(f\) може се схватити и на сљедећи начин. Можемо уочити да заправо постоји једна скривена, латентна случајна величина \(Z\), која заправо представља расподјелу вјероватноћа \(\pi_j\) по кластерима:
\[Z:\pmatrix{c_1 & c_2 & ... & c_C\\ \pi_1 & \pi_2 & ... & \pi_C}.\]
Сада се може записати да је
\[f(x|Z=c) = f_{\mu_c,\Sigma_c}(x).\]
Ово је згодан начин за представљање, уколико бисмо жељели да генеришемо опсервацију са густином \(f\), јер је \(f(\cdot) = f(\cdot | Z=c)\pi_c\), a све на десној страни знамо да генеришемо.
Океј, вратимо се \(GMM\) алгоритму. Крећемо од произвољног (или не, ако знамо нешто) одабира почетних елемената \(\mu_c\), \(\Sigma_c\), \(\pi_c\). Затим спроводимо сљедеће кораке:
- Е корак. За сваку опсервацију \(x_i\) рачунамо вјероватноћу да припада \(c\)-том кластеру као:
\[r_{ic} = \frac{\pi_c f_{\mu_c,\Sigma_c}(x^i)}{\sum_{c'=1}^C\pi_{c'}f_{\mu_{c'}, \Sigma_{c'}}(x^i)}.\]
- М корак. На основу срачунате вјероватноће припадања, ажурирамо информације о кластерима. Прво ћемо да рачунамо \(n_c\) које представља суму свих вјероватноћа припадања за \(c\)-ти кластер:
\[n_c = \sum_{i=1}^n r_{ic}.\]
Ажурирану вредност за \(\pi_c\) сада добијамо као количник \(n_c\) и \(n\):
\[\pi_c=\frac{n_c}{n}.\]
Oна се ажурира на овај начин јер у неком смислу представља “тежину” \(c\)-тог кластера у заједничкој суми. Средњу вриједност и коваријациону матрицу сада, природно, рачунамо као тежинске средине:
\[\mu_c=\sum_{i=1}^n \frac{r_{ic}}{n_c}x^i, \quad \Sigma_c = \sum_{i=1}^n \frac{r_{ic}}{n_c}(x^i-\mu_c)(x^i-\mu_c)^T.\]
Напомена. Може се доказати да свака итерација повећава функцију вјеродостојности, те овај алгоритам сигурно конвергира. Међутим, он може исконвергирати локалном, а не глобалном максимуму. Стога се и овдје препоручује “пуштање” алгоритма више пута, са различитим почетним параметрима.
Илустрација \(GMM+EM\) за два кластера и 20 итерација дата је на слици испод:
На наредној слици, скроз лијево приказани су подаци, вјештачки генерисани, онаквима какви јесу. На средњој слици видимо их обједињене. На десној слици, интензитет боје сваке тачке сразмеран је броју \(r_{ic}\). Видимо да је на преклапању кластера боја најблијеђа, и долази до преклапања боја, што осликава нашу несигурност око одабира кластера за те тачке.
Уколико ипак желимо да опсервацију доделимо неком кластеру, а не да је оставимо са вјероватноћом, просто ћемо одабрати онај кластер чија је вјероватноћа припадности највећа. Уколико добијемо нову опсервацију поступамо идентично.
За одабир броја кластера и овде важи “лакат правило”.
Уочимо још и да је \(k-means\) алгоритам заправо специјалан случај алгоритма \(GMM\) и то за:
- \(\Sigma_c=\sigma^2I\) за све \(c\),
- \(\pi_c = 1/C\) за све \(c\),
- \(P\{Z=c|x^i\}\) је \(1\) ако је \(x^i\) најближа просјеку \(\mu_c\), а нула иначе.
\(DBSCAN\) кластеризација
Сљедећи тип кластеризације са којим ћемо се упознати јесте алгоритам \(DBSCAN\). Име му је акроним и скраћеница је од енглеског \(Density-Based \, Spatial \, Clustering \, and \, Application \, with \, Noise\). Прије него што дамо детаљан опис алгоритма, мотивисаћемо.
Код алгоритма \(K-means\) успјевали смо да издвајамо кластере правилног(симетричног) облика. За еуклидску метрику то су били кружни кластери, док би за неки други одабир метрике то био неки други правилан облик. Коришћењем \(GMM+ЕМ\) успјели смо да кластере које смо у стању да уочимо проширимо на елиптичне кластере.
Међутим, размотримо наредну слику.
У сва три случаја јасно су, људском оку, уочљиви кластери. Међутим, јасно је да свака од поменуте двије методе неће бити у стању да их препозна на адекватан начин, јер сами клсатери нису одговарајућег облика (осим на првој слици).
Идеја \(DBSCAN\) алгоритма јесте да кластере замишљамо као области велике густине, а да их раздвајамо областима мање густине. Два основна параметра у вези са овим јесу:
- \(\epsilon\) (епсилон) - параметар који дефинише полупречник, такав да за неку тачку \(x\) кажемо да је лопта \(B(x, \epsilon)\) њен “комшилук”, а да свака већа није њен комшилук.
Напомена: На енглеском језику, појам се зове neighbourhood, што би се на српски превело као околина. Међутим, како овај појам не одговара тополошком појму околине, одлучио сам се да уведем термин комшилук.
- \(z\) - минималан број тачака у околини неке тачке - њених “комшија”.
Сада ћемо дефинисати неколико појмова.
Опсервација \(x\) са бројем комшија барем \(z\) (рачунајући и њу) је главна тачка (енг. core point).
Ако је \(x\) таква да има мање од \(z\) комшшија, али се налази у комшилуку неке главне тачке, кажемо да је она гранична тачка (енг. border point).
Ако \(x\) није ни главна ни гранична тачка, кажемо да је тачка шума (енг. noise point).
На наредној слици дата је једна илустрација поменутих типова тачака.
Сада смо корак ближе томе да извршимо кластеризацију. Треба нам још појмова.
Тачка (опсервација) \(A\) је директно дохватљива (енг. direct density reachable) из тачке \(B\) ако је \(A\) у комшилуку од \(B\) и ако је \(B\) главна тачка.
Тачка \(A\) је дохватљива (енг. density reachable) из тачке \(B\) ако постоји низ главних тачака који води од \(B\) до \(A\).
Тачке \(A\) и \(B\) су повезане (енг. density connected) ако постоји главна тачка \(C\) таква да су обе из ње дохватљиве.
Сада смо коначно спремни да опишемо \(DBSCAN\) алгоритам.
За сваку тачку \(x^i\) рачунамо њено растојање од осталих тачака. Уочавамо све тачке које су јој комшије. Сваку која има више од \(z\) комшија прогласимо за главну тачку.
За сваку главну тачку, ако већ није у кластеру, правимо нови кластер. У њен кластер смјештамо све са њом повезане тачке.
Понављамо процес кроз све тачке.
Она тачка која није главна и није припала ниједном кластеру, јесте тачка шума и њу не класификујемо. На наредној слици видимо наставак примера са претходне слике. За дато \(z = 3\) и одговарајуће \(\epsilon\) алгоритам је уочио два кластера и једну тачку шума.
Неке од главних предности овог алгоритма јесу то што не захтјева да му се предефинише број кластера, већ га он сам проналази. Овај алгоритам проналази кластере произвољног облика, а у стању је и да детектује аутлајере (тачке шума).
Основни недостатак јесте тај што није јасно како одабрати \(\epsilon\) и \(z\). Наравно да ни овдје не постоји генерално правило. Пракса је показала да, уколико имамо велики број опсервација, можемо бирати \(z\) које је ред величине броја предиктора. За \(\epsilon\) прича иде мало теже. Овдје је пракса показала да можемо за сваку опсервацију срачунати њену удаљеност од \(z\)-тог комшије, затим сортирати тај низ удаљености. Идеално, добићемо график сличан оном на наредној слици.
Бирамо удаљеност оног \(z\)-тог комшије који је “на лакту”. Ако немамо “лакат”, наравно, онда ништа, морамо на осећај.
Кластеризација - практично у \(R\)-у
\(K-means\)
Користићемо функцију \(kmeans\) из основног пакета \(stats\). Користићемо базу података \(USArrests\). Свака опсервација је једна Америчка савезна држава, а предиктора има 4: стопа убистава, стопа напада, стопа урбане популације и стопа силовања.
data("USArrests")Одмах треба скалирати податке, јер желимо да сваки предиктор има исти ред величине, због рачунања растојања.
df <- data.frame(scale(USArrests))Потпис функције \(kmeans\) је сљедећи
\[\mathrm{kmeans(x, centers, iter.max = 10, nstart = 1).}\]
Аргумент \(x\) представља базу података. Аргумент \(centers\) представља почетни одабир центроида, а ако му се прослиједи само један број онда то схвата као број кластера, а почетне центроиде бира насумично из врста од \(x\). Аргумент \(iter.max\), јасно, представља максималан дозвољен број итерација алгоритма, док посљедњи аргумент представља број почетних одабира центроида. Ако је већи од један, онда се бира она кластеризација која минимизује суму квадрата растојања од центроида, у свим кластерима. Пожељно је да овај аргумент буде већи од 1.
Користићемо и библиотеку \(factoextra\) због лијепих графичких приказа. За почетак, треба одредити оптималан број кластера “правилом лакта”.
library(factoextra)
fviz_nbclust(x = df,
method = "wss", # "within sum of squares"
FUNcluster = kmeans
)
Видимо да сума квадрата достиже минимум за \(4\) кластера, па расте за \(5\), те наставља да опада након \(6\) кластера. Овдје није јасно да ли узети \(4\) или \(6\) кластера. Без неког нарочитог разлога одлучићемо се за \(4\) кластера, јер нам је циљ да демонстрирамо метод.
Сада спроводимо кластеризацију.
set.seed(123)
km_result <- kmeans(df, 4, nstart = 15)То је у суштини то, још да видимо шта враћа функција \(kmeans\). Она враћа листу компоненти, а у њој је:
\(cluster\) - вектор природних бројева дужине оригиналних података, који говори о томе ком је кластеру опсервација додјељена;
\(centers\) - финални вектор центроида;
\(totss\) - \(SSTO\) са ЛСМ; мјери укупну суму квадрата растојања свих података;
\(withinss\) - вектор унутаркластерних сума квадрата растојања;
\(tot.withinss\) - сума претходног вектора;
\(betweenss\) - једнака \(totss - tot.withinss\);
\(size\) - вектор величина кластера.
km_result## K-means clustering with 4 clusters of sizes 8, 13, 16, 13
##
## Cluster means:
## Murder Assault UrbanPop Rape
## 1 1.4118898 0.8743346 -0.8145211 0.01927104
## 2 -0.9615407 -1.1066010 -0.9301069 -0.96676331
## 3 -0.4894375 -0.3826001 0.5758298 -0.26165379
## 4 0.6950701 1.0394414 0.7226370 1.27693964
##
## Clustering vector:
## Alabama Alaska Arizona Arkansas California
## 1 4 4 1 4
## Colorado Connecticut Delaware Florida Georgia
## 4 3 3 4 1
## Hawaii Idaho Illinois Indiana Iowa
## 3 2 4 3 2
## Kansas Kentucky Louisiana Maine Maryland
## 3 2 1 2 4
## Massachusetts Michigan Minnesota Mississippi Missouri
## 3 4 2 1 4
## Montana Nebraska Nevada New Hampshire New Jersey
## 2 2 4 2 3
## New Mexico New York North Carolina North Dakota Ohio
## 4 4 1 2 3
## Oklahoma Oregon Pennsylvania Rhode Island South Carolina
## 3 3 3 3 1
## South Dakota Tennessee Texas Utah Vermont
## 2 1 4 3 2
## Virginia Washington West Virginia Wisconsin Wyoming
## 3 3 2 2 3
##
## Within cluster sum of squares by cluster:
## [1] 8.316061 11.952463 16.212213 19.922437
## (between_SS / total_SS = 71.2 %)
##
## Available components:
##
## [1] "cluster" "centers" "totss" "withinss" "tot.withinss"
## [6] "betweenss" "size" "iter" "ifault"\(GMM+EM\)
Пошто смо у теоријском дијелу видјели како алгоритам ради, трудићемо се да што мање ствари програмирамо ручно, већ да користимо уграђене функције. Користимо пакет \(mclust\).
library(mclust)База коју ћемо користити јесте база \(iris\), која садржи податке о цвијету рода Ирис. Она има сљедеће колоне
names(iris)## [1] "Sepal.Length" "Sepal.Width" "Petal.Length" "Petal.Width" "Species"Прве \(4\) говоре о вриједностима одређених димензија цвијета, док посљедња представља једну од три врсте у оквиру рода Ирис, а то су:
levels(iris$Species)## [1] "setosa" "versicolor" "virginica"Посљедњу нећемо користити јер представља баш кластере, које ми желимо да одредимо невођено, те је се рјешавамо.
df <- iris[, 1:4]Сада све иде аутоматски, позивом функције \(Mclust\). Сви параметри могу се и ручно иницијализовати, али ми ћемо оставити функцији да ради сама, битно је само да знамо да може.
mcl_model_iris <- Mclust(df, 3)Ако позовемо \(class\), добијамо
class(mcl_model_iris)## [1] "Mclust"Ово је заправо листа неких стандардних повратних вриједности, свих оних о којима смо говорили у теоријском уводу, те се нећемо замарати свима, за то постоји help. Оно што је згодно јесте то што се објекат ове класе може директно проследити функцији plot.
plot(mcl_model_iris, what = "classification")
Јасно, на овој слици су кластери додјељени по принципу највеће вјероватноће, па нема флуидног прелаза боја. То се може добити играњем са ggplot-ом и повратним вредностима за Mclust.
\(DBSCAN\)
Овај алгоритам у \(R\)-у може бити имплементиран коришћењем два пакета: \(dbscan\) и \(fpc\). Ми ћемо се одлучити за овај други за саму кластеризацију, док ћемо за одабир епсилона користити први. Разлика је мање-више у синтакси. Користићемо и пакет \(factoextra\) због визуализације кластера, уграђене базе \(multishapes\), а \(fpc\) смо бирали између осталог јер се слаже са овим пакетом у смилсу визуализације. Прецизније, оно што враћа функција из пакета \(fpc\) можемо прослеђивати функцијама из \(factoextra\) као аргумент, док за \(dbscan\) то не можемо.
library(fpc)
library(factoextra)
library(dbscan)Прво ћемо учитати податке.
data("multishapes", package = "factoextra")
df <- multishapes[, 1:2]Узели смо прве двије промјенљиве јер је трећа категоричка и говори о томе која је права вриједност кластера у који опсервација спада (подаци су вјештачки генерисани па се зна).
plot(df)
Јасно је да уочавамо \(5\) кластера. Након кластеровања функцијом из пакета \(factoextra\) направићемо љепшу слику. Сада вршимо кластеризацију помоћу пакета \(fpc\).
set.seed(123)
db <- fpc::dbscan(df, eps = 0.15, MinPts = 5)
# class(db) vraca "dbscan"Број \(z\) дат је аргументом \(MinPts\). Бирали смо \(5\), иако имамо \(2\) предиктора, јер бисмо спољни “прстен” жељели да класификујемо као један кластер, па за сваки случај, да не направи прекид.
Епсилон смо одабрали уз помоћ “лакат” технике, а то се спроводи на сљедећи начин.
dbscan::kNNdistplot(df, k = 5)
Видимо да је \(0.15\) отприлике “на лакту”.
Сада цртамо љепшу слику.
fviz_cluster(db,
data = df,
stand = FALSE, # ne radimo PCA, ne treba nam (zvati help)
ellipse = FALSE, # da ne zaokruzuje klastere
show.clust.cent = FALSE,
geom = "point",
palette = "jco",
ggtheme = theme_classic()
)
И голим оком да се наслутити да је већину аутлајера погодио како треба. Тек за неке нам је смислено да припадају неком кластеру, а да их је алгоритам прогласио аутлајерима (шумом).
Предвиђање за нове тачке врши се функцијом \(predict.dbscan\) из пакета \(fpc\).
На наредној слици дат је примјер шта се деси када исте податке покушамо да кластерујемо методом \(K-means\), за одређене почетне центроиде (нећемо спроводити поступак, само као примјер). Није баш како треба.
Задаци за самосталан рад
Задатак 1. У бази \(mtcars\) налазе се подаци о потрошњи горива и 10 аспеката дизајна и перформанси за 32 аутомобила. Извршити кластеризацију података методом \(K-means\) и \(DBSCAN\). Приказати визуализацију уочених кластера.