Какво представлява клъстерирането на K-средства?

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

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

Дефиниране на групиране

Преди да разгледаме точните алгоритми, използвани за извършване на клъстериране на K-среднини, нека отделим малко време, за да дефинираме клъстерирането като цяло.

Клъстерите са просто групи от елементи, а клъстерирането е просто поставяне на елементи в тези групи. В смисъла на науката за данните, клъстерни алгоритми имайте за цел да направите две неща:

• Уверете се, че всички точки от данни в клъстер са възможно най-сходни една с друга.
• Уверете се, че всички точки от данни в различни клъстери са възможно най-различни една от друга.

Алгоритмите за клъстериране групират елементи заедно въз основа на някакъв показател за сходство. Това често се прави чрез намиране на „центъроида“ на различните възможни групи в набора от данни, макар и не изключително. Има множество различни алгоритми за клъстериране, но целта на всички алгоритми за клъстериране е една и съща, да определят групите, присъщи на набор от данни.

К-средства групиране

K-Means Clustering е един от най-старите и най-често използвани типове алгоритми за клъстериране и работи въз основа на векторно квантуване. Има точка в пространството, избрана като начало, след което векторите се изчертават от началото към всички точки от данни в набора от данни.

Като цяло групирането на K-означава може да бъде разделено на пет различни стъпки:

• Поставете всички екземпляри в подмножества, където броят на подмножествата е равен на K.
• Намерете средната точка/център на новосъздадените клъстерни дялове.
• Въз основа на тези центроиди, присвоете всяка точка на конкретен клъстер.
• Изчислете разстоянията от всяка точка до центроидите и задайте точки на клъстерите, където разстоянието от центроида е минимално.
• След като точките са присвоени на клъстерите, намерете новия центроид на клъстерите.

Горните стъпки се повтарят, докато тренировъчният процес приключи.

В началната фаза центроидите се поставят някъде сред точките с данни.
Снимка: Weston.pace чрез wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Като алтернатива, след като центроидите са поставени, можем да си представим клъстерирането на K-означава като смяна напред и назад между две различни фази: етикетиране на точки от данни и актуализиране на центроиди.

Във втората стъпка се използва показател за разстояние като евклидовото разстояние, за да се изчисли до кой центроид е най-близка дадена точка и след това точките се присвояват на класа на този центроид. Снимка: Weston.pace чрез Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

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

В третата стъпка центроидът се премества към средната стойност на всички точки от данни. След това класовете се преразпределят. Снимка: Weston.pace чрез Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

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

Как да изберете правилната стойност за „K“

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

Една техника за избор на правилната K-стойност се нарича „техниката на лакътя”. Техниката на лакътя се състои от изпълнение на алгоритъм за групиране на K-средни стойности за диапазон от различни K-стойности и използване на метрика за точност, обикновено сумата на квадратната грешка, за да се определи кои стойности на K дават най-добри резултати. Сумата на квадратната грешка се определя чрез изчисляване на средното разстояние между центроида на клъстер и точките от данни в този клъстер.

Терминът „техника на лакътя“ идва от факта, че когато начертаете SSE по отношение на различните стойности на K, получената линейна графика често ще има форма на „лакът“, където SSE намалява бързо за първите няколко стойности на K, но след това се изравнява. При такива условия стойността на K, намираща се в лакътя, е най-добрата стойност за K, тъй като има бързо намаляваща възвръщаемост след тази стойност.

Мини-партида K-означава групиране

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

Mini-Batch K-означава групиране е вариант на K-означава групиране където размерът на разглеждания набор от данни е ограничен. Нормалното K-означава клъстериране работи върху целия набор от данни/партида наведнъж, докато мини-партида K-означава клъстериране разбива набора от данни на подмножества. Мини-партидите се вземат на случаен принцип от целия набор от данни и за всяка нова итерация се избира нова произволна извадка и се използва за актуализиране на позицията на центроидите.

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

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

Приложения на K-Means Clustering

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

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

K-означава клъстерирането може да се използва и за по-отворени задачи като създаване на системи за препоръки. Потребителите на система като Netflix могат да бъдат групирани заедно въз основа на модели на гледане и препоръчано подобно съдържание. Клъстерирането на K-означава може да се използва за задачи за откриване на аномалии, подчертавайки потенциални случаи на измама или дефектни елементи.