Прост преглед на техниките зад известни алгоритми за клъстериране

„Птици от перушина се събират заедно“

Това е добре позната поговорка, която всички сме чували от младини. Това предполага, че индивиди от един и същи тип или с подобни черти са склонни да бъдат по-близо един до друг.

В науката за данните този природен феномен се нарича групиране и се използва за намиране на групиране сред данни чрез откриване на няколко групи, в които обектите са значително подобни на тези в същата група, когато се сравняват с обекти в другите групи.

Приложения

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

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

Категории алгоритми за групиране

Може би си мислите, че групирането на обекти е лесно. Но опитвали ли сте го по методичен начин, така че дори машина да може да го направи.

Отпреди години изследователите са измислили толкова много алгоритми, за да постигнат това и има няколко много често използвани алгоритми като K Means, агломативно клъстериране и т.н. Познанията за тях са много ценни за обучаващи се в науката за данни, практикуващи или всеки, който в областта. Това е така, защото всеки алгоритъм има свои собствени предимства и недостатъци, поради което е необходимо тяхното задълбочено разбиране при избора на правилния метод за клъстериране за конкретна задача.

Фокусът на статията е да има преглед на основните категории алгоритми за клъстериране. Повечето добре познати алгоритми могат да бъдат разделени на три категории.

  • Частично клъстериране
  • Йерархично групиране
  • Групиране на базата на плътност

Частично клъстериране

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

Изберете k различни клъстерни центъра и започнете да привличате точки от данни, които са най-близо до клъстера.

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

Основна характеристика на тези подходи е, че те изискват от потребителя да определи броя на клъстерите, който се обозначава с променливата k. K-средства, k-medoids и k режим са три примера за техники за разделяне на клъстери.

Силни страни
-Прост, ефективен, мащабируем и лесен за внедряване
- Изчислява всички достижими клъстери синхронно.
- Работят добре, когато клъстерите имат сферична форма.

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

Йерархично групиране

При йерархично клъстериране групирането ще се извърши след подреждането им в йерархия. Има два основни начина да направите това:

  • Подходът отдолу нагоре сенарича Агломеративно групиране.

Разгледайте всяко наблюдение като отделен клъстер и след това започнете да обединявате двойка най-близки клъстери итеративно.

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

  • Подходът отгоре надолу се нарича Разделящо групиране

Разглеждайте всички данни като един клъстер и след това започнете да разделяте най-малко подобните клъстери на всяка стъпка, докато останат само единични точки от данни.

Подобно на горния пример, това може да се обясни с това как се случва разделението в една общност. Първо, всички индивиди са в една общност. Тогава, ако две групи имат различни вярвания, общността ще се раздели на две групи, образувайки две подобщности. Това теоретично може да се случи итеративно, докато една общност най-накрая има само един индивид.

Традиционната визуализация на клъстерната йерархия е дендрограма. Дендрограмата е дървовидна йерархия от точки, получена от тези подходи.

Подобно на частичното клъстериране, броят на клъстерите (k) в йерархичното клъстериране често се избира от потребителя. Клъстерите се създават чрез изрязване на дендрограмата на определена дълбочина, което води до k групи от по-малки дендрограми.

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

Слабости
-Сскъпо от изчислителна гледна точка.
- Може да бъде доста чувствителен към отклонения

Методи, базирани на плътност

Тук групирането се извършва по плътността на точките от данни в даден регион. Той разпознава места, където точките са плътно подредени и са разделени от празни или редки области. По принцип, то

Счита данните, опаковани плътно една до друга — области с висока плътност като клъстер

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

Примери за често използвани алгоритми за клъстериране, базирани на плътност, включват DBSCAN (базирано на плътност пространствено клъстериране на приложения с шум) и OPTICS (подреждане на точки за идентифициране на структурата на клъстериране).

Силни страни
-По-добро идентифициране на сродници с произволна форма.
- Устойчивост на отклонения.
- Няма нужда за да определите броя на клъстерите в началото

Слабости
-Трудни за идентифициране клъстери с различни плътности
- Трудни за справяне с многомерни пространства

Заключение

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

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