Преглед на йерархичния анализ на клъстеринга

Преди да продължим напред и да разберем за йерархичния клъстер анализ, нека първо се опитаме да разберем какво е клъстер? И какво е клъстер анализ? Клъстер е съвкупност от обекти на данни; точките от данни в един клъстер са по-подобни една на друга и се различават от точките с данни в другия клъстер. Анализът на клъстерите е основно групиране на тези точки от данни в клъстера. Клъстерирането е вид алгоритъм за непрекъснато управление на машинно обучение, при който няма набори от данни, обозначени с обучение. Има различни видове анализ на клъстеринг, един такъв тип е йерархично клъстериране.

Йерархичното клъстериране ще помогне за създаването на клъстери в правилен ред / йерархия. Пример: най-често срещаният ежедневен пример, който виждаме, е как подреждаме нашите файлове и папки в нашия компютър чрез правилна йерархия.

Видове йерархични клъстери

Йерархичното клъстериране е допълнително класифицирано в два типа, т.е. Агломеративно клъстериране и разделно клъстериране (DIANA)

Агломеративно групиране

В този случай на клъстериране, йерархичното разлагане се извършва с помощта на стратегия отдолу нагоре, където тя започва със създаване на атомни (малки) клъстери, като добавя по един обект от данни наведнъж и след това ги обединява заедно, за да образува голям клъстер в края, където този клъстер отговаря на всички условия за прекратяване. Тази процедура е итеративна, докато всички точки от данни се поставят под един единствен голям клъстер.

AGNES (AGglomerative NESting) е вид агломеративно клъстеризиране, което обединява данните от обекти в клъстер въз основа на сходството. Резултатът от този алгоритъм е структурирана на дърво структура, наречена Dendrogram. Тук той използва показателите за разстояние, за да определи кои точки от данни трябва да се комбинират с кой клъстер. По принцип той конструира матрица за разстояние и проверява за двойката клъстери с най-малко разстояние и ги комбинира.

Горната фигура показва Агломеративно срещу Дивизионно групиране

Въз основа на това как се измерва разстоянието между всеки клъстер можем да имаме 3 различни метода

  • Единична връзка : Когато най-краткото разстояние между двете точки във всеки клъстер се определя като разстоянието между клъстерите.
  • Пълна връзка : В този случай ще разгледаме най-голямото разстояние между точките във всеки клъстер като разстоянието между клъстерите.
  • Средно свързване: Тук ще вземем средната стойност между всяка точка от един клъстер до всяка друга точка в другия клъстер.

Сега нека да обсъдим силните и слабите страни на AGNES; този алгоритъм има сложност във времето най-малко O (n 2 ), следователно той не се справя добре в мащабирането и още един основен недостатък е, че всичко, което е направено, никога не може да бъде отменено, т.е. Ако неправилно групираме някой клъстер в по-ранен етап на алгоритъмът тогава няма да можем да променим резултата / да го модифицираме. Но този алгоритъм има и ярка страна, тъй като има много по-малки клъстери, които се формират, той може да бъде полезен в процеса на откриване и създава подреждане на обекти, което е много полезно за визуализацията.

Разделяне на клъстеринг (DIANA)

Диана основно означава разделящ анализ; това е друг тип йерархична клъстеризация, където в основата си той работи на принципа на подход „отгоре надолу“ (обратно на AGNES), където алгоритъмът започва с образуване на голям клъстер и рекурсивно разделя най-различния клъстер на две и продължава, докато ние “ всички подобни точки от данни принадлежат към съответните им групи. Тези разделителни алгоритми водят до много точни йерархии от агломеративния подход, но са изчислително скъпи.

Горната фигура показва разделяне на клъстеринг стъпка по стъпка

Многофазна йерархична клъстеризация

За да подобрим качеството на клъстерите, генерирани от гореспоменатите йерархични техники за клъстериране, ние интегрираме нашите йерархични техники за клъстериране с други техники за клъстериране; това се нарича многофазно групиране. Различните видове многофазни клъстери са както следва:

  • BIRCH (Балансирано итеративно намаляване и клъстериране с помощта на йерархии)
  • ROCK (клъстериране на RObust с помощта на връзки)
  • хамелеон

1. Балансирано итеративно намаляване и клъстериране с помощта на йерархии

Този метод се използва главно за клъстеризиране на огромно количество числови данни чрез интегриране на нашата йерархична / микро клъстеризация в началната фаза и макро клъстериране / итеративно разделяне на по-късния етап. Този метод помага за преодоляване на проблема с мащабируемостта, с който се сблъскахме в AGNES, и невъзможността да се отмени това, което е направено преди стъпка. BIRCH използва две важни концепции в своя алгоритъм

а. Клъстериране (Помага при обобщаването на клъстера)

CF се дефинира като (n - брой точки от данни в клъстера, линейната сума от n точки, квадратната сума от n точки). Съхраняването на характеристиката на клъстер по този начин помага да се избегне съхраняването на подробна информация за него и CF има характер на добавки за различни клъстери.

CF1 + CF2 = 1+ n 2, LS 1 + LS 2, SS 1 + SS 2 >

б. Клъстеризиращо дърво с функции (помага при представянето на клъстер като йерархия)

CF дърво е балансирано дърво с разклоняващ се фактор В (максимален брой деца) и праг Т (макс. Брой подгрупи, които могат да се съхраняват в листни възли).

Алгоритъмът основно работи в 2 фази; във фаза 1 той сканира базата данни и изгражда CF дърво в паметта, а във фаза 2 използва алгоритъма за клъстериране, който помага при групирането на листните възли, като премахва остатъците (оскъдни клъстери) и групира клъстера с максимална плътност. Единственият недостатък на този алгоритъм е, че той обработва само числовия тип данни.

2. Здраво обединяване с помощта на връзки

Връзката се дефинира като брой общи съседи между два обекта. Алгоритъмът ROCK е вид алгоритъм за клъстериране, който използва тази концепция за връзка с категоричния набор от данни. Както знаем, че алгоритмите за клъстериране, измерени от разстояние, не осигуряват висококачествени клъстери за категоричния набор от данни, но в случая на ROCK, той разглежда кварталите на точките с данни, т.е. ако две точки от данни имат една и съща квадратура, тогава те са най-вероятно да принадлежат към един и същ клъстер. Алгоритъмът ще конструира оскъдна графика в първата стъпка, като взема предвид матрицата на прилика с концепцията за съседство и праг на сходство. Във втората стъпка използва агломеративната йерархична техника на клъстериране на графика на оскъдни.

3. Хамелеон

Този тип алгоритъм на йерархичен клъстер използва концепцията за динамично моделиране. Чудите се защо се нарича динамичен? Нарича се динамичен, защото има способността да се адаптира към вътрешните характеристики на клъстера автоматично, като оценява сходството на клъстера, т.е. колко добре са свързани точките от данни в клъстера и в близостта на клъстерите. Един от недостатъците на хамелеона е, че разходите за обработка са твърде високи (O (n 2 ) за n обекти е най-лошият времеви сложност).

Източник на изображения - Google

заключение

В тази статия научихме какво е клъстер и какво е клъстер анализ, различни видове йерархични техники на клъстеринг техните предимства и недостатъци. Всяка от техниките, които обсъждахме, има свой плюс и минус, затова преди да продължим с алгоритъм, ние трябва да разберем нашите данни с подходящ проучвателен анализ на данните и да изберем алгоритъма с повишено внимание.

Препоръчителни статии

Това е ръководство за йерархичен анализ на клъстеринга. Тук обсъждаме преглед, агломеративно клъстериране, разделящо клъстериране (DIANA) и многофазно йерархично клъстериране. Можете също да разгледате следните статии, за да научите повече

  1. Йерархична клъстеризация в R
  2. Алгоритъм на клъстеризация
  3. клъстери
  4. Методи на клъстериране
  5. Клъстеризиране в машинно обучение
  6. Йерархично клъстериране | Агломеративно и разделно клъстеризиране

Категория:

Голяма информация