Увод у хијерархијски алгоритам кластерирања
Хијерархијски алгоритам кластерирања је техника надзора машинског учења без надзора. Његов циљ је проналажење природног групирања на основу карактеристика података.
Алгоритам хијерархијског кластерирања има за циљ проналажење угнијежђених група података изградњом хијерархије. Слично је са биолошком таксономијом биљног или животињског царства. Хијерархијски кластери су генерално представљени помоћу хијерархијског стабла познатог као дендрограм.
Типови хијерархијског алгоритма кластерирања
Хијерархијски алгоритми кластерирања су 2 типа:
- Дивисиве
- Агломеративе
1. Дивисиве
Ово је приступ одоздо на доле, где се у почетку читави подаци размотре као једна група, а затим их итеративно раздваја на подгрупе. Ако је познат број алгоритма хијерархијског кластерирања, тада се процес поделе зауставља када се постигне број кластера. Иначе, процес се зауставља када се подаци не могу више раздвајати, што значи да је подгрупа добијена тренутном итерацијом једнака оној добијеној из претходне итерације (такође се може узети у обзир да се подјела зауставља када је свака точка података кластер ).
2. Агломеративе
То је приступ одоздо према горе који се ослања на спајање кластера. У почетку се подаци деле на м једнотонске кластере (где је вредност м број узорака / тачака података). Два кластера су спојена у један итеративно, чиме се смањује број кластера у свакој итерацији. Овај процес спајања кластера престаје када су сви кластери спојени у један или је постигнут број жељених кластера.
На нивоу 1, постоје м кластери који се своде на 1 кластер на нивоу м. Оне тачке података које се спајају ради формирања кластера на нижем нивоу остају у истом кластеру и на вишим нивоима. Нпр. Претпоставимо да постоји 8 тачака к1..к8, тако да у почетку постоји 8 кластера на нивоу 1. Претпоставимо да се тачке к1 и к2 спајају у кластер на нивоу 2, а затим до нивоа 8, остају у истом кластеру.
На горњој слици је приказан дендрограмски приказ кластера агломерације за 8 података, као и скала сличности која одговара сваком нивоу.
Нивои кластера дају нам представу колико су сличне тачке података у кластерима. Као што је приказано на слици 1, раније се тачке података спајају у кластер, сличне су. Дакле, податковне тачке у кластеру на нивоу 2 (нпр. Кс2 и к3) су сличније од оних података у кластеру на нивоу 6 (нпр. Кс1 и к2).
Горња слика приказује Сет или Венн дијаграм приказ агломеративног приступа кластера горе наведених 8 података. И дендрограми и постављени прикази могу се користити за кластерирање. Међутим, дендрограм је обично пожељно представљање имовине, а не може квантитативно представити сличности кластера.
Кораци за хијерархијски алгоритам кластерирања
Слиједимо сљедеће кораке за хијерархијски алгоритам кластерирања који су дати у наставку:
1. Алгоритам
Алгоритам агломеративног хијерархијског кластерирања
- Започните иницијализацију ц, ц1 = н, Ди = (ки), и = 1, …, н '
- Учините ц1 = ц1 - 1
- Пронађите најближе кластере, рецимо, Ди и Дј
- Спајање Ди и Дј
- Све док ц = ц1
- Повратак ц кластера
- Крај
Овај алгоритам започиње с н кластера у почетку где је свака тачка података кластер. Сваком итерацијом број кластера смањује се за 1 док се 2 најближа кластера спајају. Овај процес се наставља све док се број кластера не смањи на унапред дефинисану вредност ц.
Како одлучити који су кластери у близини?
То је дефинисано коришћењем неколико метричких растојања које су следеће:
- Минимална удаљеност између кластера дмин (Ди, Дј). Корисно за самце.
- Максимална удаљеност између кластера дмак (Ди, Дј). Корисно за комплете.
- Просечна удаљеност између кластера давг (Ди, Дј).
Шта је једно повезивање и потпуна веза?
- Када се дмин (ди, дј) користи за проналазак удаљености између два кластера, а алгоритам се прекида ако удаљеност између најближих кластера прелази праг, тада се алгоритам назива алгоритам јединствене везе.
- Када се дмак (Ди, Дј) користи за проналазак удаљености између два кластера, а алгоритам се прекида ако удаљеност између најближих кластера прелази праг, тада се алгоритам назива алгоритам потпуне везе.
- Размотримо сваку точку података као чвор графикона. Постоји ивица између две тачке података ако припадају истом кластеру. Када се два најближа кластера споје, додаје се ивица. Зове се једна веза јер постоји јединствена стаза од једног чвора до другог.
- Комплетни алгоритам повезивања обједињује два кластера смањујући удаљеност између две најудаљеније тачке.
- Један алгоритам повезивања генерише опружно стабло. Међутим, овај алгоритам је подложан буци. Комплетни алгоритам повезивања генерише комплетан граф.
Шта је временска сложеност алгоритма?
Претпоставимо да у д-димензионалном простору имамо н образаца, а дмин (Ди, Дј) користимо за формирање ц кластера. Морамо израчунати н (н - 1) растојања међу тачкама - од којих је свако О (д 2 ) прорачун - и резултате ставити у табелу растојања између тачака. Сложеност простора је О (н 2 ). Проналажење пара минималних растојања (за прво спајање) захтијева да пређемо комплетну листу, задржавајући индекс најмање удаљености.
Према томе, за први агломеративни корак сложеност је О (н (н - 1) (д 2 + 1)) = О (н 2 д 2 ). За други произвољни корак агломерације (тј. Од ц1 до ц1 - 1), само корак кроз н (н - 1) - ц1 „неискоришћене“ растојања у листи и проналазимо најмању вредност за коју к и к 'леже у различитим кластерима . Ово је, опет, О (н (н-1) −ц1). Укупна временска сложеност је, дакле, О (цн 2 д 2 ), а у типичним условима н >> ц.
2. Визуализација
Једном када се подаци поделе на кластере, добра је пракса да се кластери визуализују како би се стекла идеја о томе како груписање изгледа. Али тешко је визуелизовати податке велике димензије. Отуда користимо анализу главних компоненти (ПЦА) за визуелизацију. Након ПЦА, добијамо тачке података у простору малих димензија (углавном 2Д или 3Д) које можемо да замислимо како бисмо видели груписање.
Напомена: Велика димензија значи велики број функција, а не број података.3. Процена
Једна од метода за оцењивање кластера је да удаљеност тачака између кластера (међу-кластер растојање) треба да буде много већа од растојања тачака унутар кластера (интракластерски удаљеност).
Закључак
Следи неколико кључних поступака:
- Хијерархијски алгоритам кластерирања користи се за проналажење угнијежђених образаца у подацима
- Хијерархијско групирање је две врсте - подељено и агломеративно
- Дендрограм и сет / Венн дијаграм могу се користити за репрезентацију
- Појединачна веза спаја два кластера смањујући минималну удаљеност између њих. Формира распон
- Комплетна веза спаја два кластера минимизирајући максималну удаљеност између ње.
- Укупна временска сложеност хијерархијског алгоритма групирања је О (цн 2 д 2 ), где је ц предефинисани број кластера, н је број образаца и д је димензионални простор н образаца.
Препоручени чланци
Ово је водич за алгоритам хијерархијског кластерирања. Овдје ћемо расправљати о типовима и корацима алгоритама хијерархијског групирања. Такође можете погледати следеће чланке да бисте сазнали више -
- Хијерархијска анализа кластерирања
- Хијерархијско кластерирање у Р '
- Алгоритам кластера
- Шта је кластерирање у Рударству података?
- Хијерархијско кластерирање | Агломеративно и подељено кластерирање
- Ц ++ алгоритам | Примери алгоритма Ц ++