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