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

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

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

Алгоритъм k-средни (k-средни)

Най-често срещаните сред нейерархичните методи k-средни алгоритъм, също наричан бърз клъстерен анализ. Пълно описание на алгоритъма може да се намери в Hartigan and Wong (1978). За разлика от йерархичните методи, които не изискват предварителни предположения за броя на клъстерите, за да може да се използва този метод, е необходимо да има хипотеза за най-вероятния брой на клъстерите.

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

Общата идея на алгоритъма: даден фиксиран брой k клъстери за наблюдение се сравняват с клъстери по такъв начин, че средните стойности в клъстера (за всички променливи) да се различават възможно най-много една от друга.

Описание на алгоритъма

1. Първоначално разпределение на обектите по клъстери.

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

   Изборът на начални центроиди може да се извърши, както следва:

   • избор на k-наблюдения за максимизиране на първоначалното разстояние;
   • случаен избор на k-наблюдения;
   • избор на първите k-наблюдения.

   В резултат на това всеки обект се присвоява на конкретен клъстер.

2. Итеративен процес.

   Са изчислени клъстерни центрове, които след това и по-долу са средните по координати на клъстерите. Обектите се преразпределят отново.

   Процесът на изчисляване на центрове и преразпределение на обекти продължава, докато не бъде изпълнено едно от следните условия:

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

   На фиг. 14.1 е пример за работа k-средни алгоритъмза k равно на две.

Ориз. 14.1.

Изборът на броя на клъстерите е сложен въпрос. Ако няма предположения за това число, се препоръчва да се създадат 2 клъстера, след това 3, 4, 5 и т.н., като се сравняват резултатите.

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

Избраната точка се приема като център на хиперсфера с даден радиус R. Определя се наборът от точки, които попадат в тази сфера, и за тях се изчисляват координатите на центъра (векторът на средните стойности на характеристиките) . След това се разглежда хиперсфера със същия радиус, но с нов център и за набора от точки, които попадат в нея, отново се изчислява векторът на средните стойности, който се приема като нов център на сферата , и така нататък. Когато следващото преизчисляване на координатите на центъра на сферата доведе до същия резултат, както в предишната стъпка, движението на сферата спира, а точките, които попадат в нея, образуват клъстер и се изключват от по-нататъшния процес на групиране. За всички останали точки процедурите се повтарят.

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

Заключение

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

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

Клъстерният анализ включва набор от различни алгоритми за класификация (методът на дендрограмата може да бъде цитиран като пример за метод за клъстерен анализ).

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

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

Резултатите от клъстерния анализ най-често се представят графично, под формата на дендрограма ("дърво"), показваща реда, в който обектите се комбинират в клъстери. Интерпретацията на клъстерната структура, която в много случаи започва с броя на клъстерите, е творческо предизвикателство. За да бъде ефективно решен, изследователят трябва да разполага с достатъчно информация за групираните обекти. С обучаващото групиране резултатите могат да бъдат представени като списъци с обекти, присвоени на всеки клас.

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

Изброяваме недостатъците на клъстерния анализ:

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

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

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

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

Основните методи за йерархичен клъстерен анализ са методът на близкия съсед, методът на пълната връзка, методът на средната връзка и методът на Уорд. Последният е най-универсален.

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

Говорейки за избора на конкретен метод за групиране, още веднъж подчертаваме, че този процес изисква анализаторът да е добре запознат с естеството и предпоставките на методите, в противен случай резултатите ще бъдат подобни на „средната температура в болницата“. За да сте сигурни, че избраният метод е наистина ефективен в тази област, обикновено се прилага следната процедура:

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

Когато избирате между йерархични и нейерархични методи, трябва да обърнете внимание на следните точки:

Нейерархичните методи показват по-висока устойчивост на отклонения, неправилен избор на метрика, включване на незначителни променливи в основата за групиране и т.н. Но цената за това е думата "априори". Изследователят трябва предварително да фиксира получения брой клъстери, правилото за спиране и, ако има причини за това, началния център на клъстера. Последната точка значително влияе върху ефективността на алгоритъма. Ако няма причина за изкуствено поставяне на това условие, най-общо казано, се препоръчва използването на йерархични методи. Също така отбелязваме още един момент, който е от съществено значение и за двете групи алгоритми: групирането на всички наблюдения не винаги е правилното решение. Може да е по-точно първо да изчистите извадката от отклоненията и след това да продължите с анализа. Също така е възможно да не се задава много висок критерий за спиране.

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

За класифициране на данни X x,...,X pизползвайте концепцията за метрика или разстояние.

показателе функция p, която преобразува някакво метрично пространство в пространството на реални числа и има следните свойства (метрични аксиоми):

• 1) p(ZD>0,
• 2) p(X,Y)=p(Y, X),
• 3) p(X, Y) = 0 X=Y
• 4) P(X,Y) P(Z, Y).

Теорията на клъстерния анализ използва следните показатели за измерване на разстоянието между отделните точки (вектори):

1) Евклидово разстояние

2) претеглено евклидово разстояние

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

и приемете, че ^ w* = 1;

• 3) разстояние на Хеминг (или градски блок)-разстояние на картата между кварталите в града

4) Разстояние на Махаланобис (или ъгъл на Махаланобис)

където A е симетрична положително определена матрица на тегло (често избрана да бъде диагонална); НО -векторна ковариационна матрица X 19 ..., X p;

5) Разстояние Минковски

Разстояния 1), 2), 3) или 5) се използват в случай на нормално разпределение на независими случайни променливи X l9 ...,X n ~N(M,A)или в случай на тяхната хомогенност в геохимичен смисъл, когато всеки вектор е еднакво важен за класификация. Разстояние 4) се използва, ако има ковариационна връзка на вектори X x,...,XП.

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

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

Позволявам С(- /-ти клъстер, състоящ се от n tвектори или точки. Позволявам

X (l) - извадкова средна стойност за точките, попадащи в клъстера С f , или центърът на тежестта на клъстера 5.. Тогава се разграничават следните разстояния между клъстери, които нямат други клъстери вътре:

1) разстояние между клъстерите според принципа на „близкия съсед“.

2) разстояние между клъстерите според принципа на "далечния съсед"

3) разстояние между центровете на тежестта на групите

4) разстояние между клъстерите според принципа на "средна връзка"

5) обобщено разстояние на Колмогоров

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

където S^k^- клъстер, получен чрез комбиниране на класове S kи S t.

Всички специални случаи на разстояния се получават от тази обобщена формула. При a = p = 1/2, 8 = -1/2, y = 0 имаме разстояние по принципа на „близък съсед“, при a = p = 5 = 1/2, y = O - „далеч съсед",

на \u003d ---, p \u003d---, 5 \u003d 0, y \u003d 0 - разстояние по протежение на центровете на тежестта

p k + n i p k + n i

групи.

Методите за клъстерен анализ се разделят на I) агломеративен (комбиниращ), II) разделителен (разделящ) и III) итеративен.

Първите последователно комбинират отделни обекти в клъстери, а вторите, напротив, разчленяват клъстери в обекти. Третият съчетава първите два. Тяхната характеристика е формирането на клъстери въз основа на условията на разделяне (така наречените параметри), които могат да се променят по време на работа на алгоритъма, за да се подобри качеството на разделяне. Итеративните методи обикновено се използват за класифициране на големи количества информация.

Нека разгледаме по-подробно агломеративните методи. Агломеративните методи са най-простите и най-често срещаните сред алгоритмите за клъстерен анализ. На първата стъпка всеки вектор или обект X 19 ..., X pизходните данни се разглеждат като отделен клъстер или клас. Според изчислената матрица от разстояния се избират и комбинират най-близките едно до друго. Очевидно процесът ще приключи в (P - 1) стъпка, когато в резултат на това всички обекти ще бъдат комбинирани в един клъстер.

Последователността от асоциации може да бъде представена като дендрограма или дърво. На фиг. 1.18 показва, че векторите са комбинирани в първата стъпка X t, X 2,тъй като разстоянието между тях е 0,3.

На втората стъпка към тях беше прикрепен вектор х 3 от клъстера (X 1, X 2)до разстояние 0,5 и т.н. На последната стъпка всички вектори се комбинират в един клъстер.

Ориз. 1.18.

Агломеративните методи включват методи на единична, средна, пълна връзка и метод на Уорд.

1.един метод на свързване.Позволявам X v ..., X n -векторни данни, като всеки вектор образува един клъстер. Първо се изчислява матрица от разстояния между тези клъстери и най-близкото съседно разстояние се използва като показател. С помощта на тази матрица се избират двата най-близки вектора, които образуват първия клъстер 5,. Следващата стъпка между С]и останалите вектори (които считаме за клъстери), се изчислява нова матрица на разстоянието и разстоянието между клъстерите се комбинира в класове (a = p = 1/2, 5 = -1/2, y = 0) се използва като показател. Най-близо до предишния клас С(клъстерът се обединява с него, образувайки S2. и т.н. чрез П- 1 стъпки, получаваме, че всички вектори са комбинирани в един клъстер.

Предимства: 1) само един елемент се добавя на всяка стъпка от алгоритъма, 2) методът е изключително прост, 3) алгоритъмът е нечувствителен към трансформации на първоначалните данни (въртене, изместване, транслация, разтягане).

недостатъци: 1) необходимо е постоянно да се преизчислява матрицата на разстоянието, 2) броят на клъстерите е известен предварително и не може да бъде намален

• 2. Пълен метод на свързване.Методът на практика повтаря метода с единична връзка, с изключение на това, че включването на нов обект в клъстер става тогава и само ако разстоянието между обектите (вектори или клъстери) е по-малко от някакво предварително определено число. Номерът се задава от потребителя. Разстоянието се изчислява само според принципа на „далечния съсед“ (същото може да се каже за разстоянието между класовете, комбинирани в класове - само принципът на далечния съсед за os = p = 8 = 1/2, y = 0).
• 3.Среден метод на свързване.Алгоритъмът за формиране на клъстер съвпада с алгоритъма за единична връзка, но когато се решава дали да се включи нов обект в клъстер, изчисленията се извършват съгласно принципа на средната връзка. Както при метода на пълна връзка, всички изчислени разстояния между клъстерите се сравняват с определено от потребителя число. И ако то (разстоянието) е по-малко от дадено число, новият обект се включва в стария клас. По този начин средният метод на свързване се различава от метода на пълно свързване само по начина, по който се изчислява разстоянието между клъстерите.
• 4. Метод WARD.Позволявам X 19 ..., X p- данни, като всеки вектор образува един клъстер. Намираме матрицата на разстоянието, като използваме някаква метрика (например разстоянието на Mahalanobis), определяме най-близките един до друг клъстери по него. Изчислете сумата от квадратите на отклоненията на векторите в клъстера S kпо формулата:

където да се -номер на клъстер, аз-векторно число в клъстера, j-координатно число X tд U1 R, p към- броя на векторите в клъстера, Xjk- извадкова средна стойност X iв Ск. Стойност V kхарактеризира отклоненията на векторите един от друг в рамките на клъстера (нов Sk+Sfили стари^). Изчисляване V kтрябва да се извърши преди и след обединението и трябва да повторите всички възможни вариантиподобни асоциации. По-късно в клъстера S kдобавят се само онези вектори или клъстери, които водят до най-малка промяна V kслед сливането и в резултат на това, който ще бъде разположен на минималното разстояние от оригиналния клъстер Ск.

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

1. Метод /r-означава.Нека има вектори Xl9 ..., Xn e9F и те трябва да бъдат разделени на да секлъстери. На нулевата стъпка на Пвектори избират произволно да сеот тях, като се приеме, че всеки образува един клъстер. Получаваме набор от референтни клъстери,...,e[ 0) с тегла

coj 0) ,...,X. и изчислете матрицата на разстоянието между х.и стандарти e 1 (0),...,^ 0) според някаква метрика, например според Евклидова:

Въз основа на познаването на изчислената матрица на разстоянието, векторът Х (се поставя в стандарта, разстоянието до което е минимално. Нека приемем със сигурност какво е то. Той се заменя с нов, преизчислен, като се вземе предвид приложената точка, съгласно формулата

Освен това теглото също се преизчислява:

Ако в матрицата се появят две или повече минимални разстояния, тогава X tвключени в клъстера с най-нисък пореден номер.

На следващата стъпка се избира следващият вектор от останалите и процедурата се повтаря. Така чрез ( настолен компютър) стъпки към всяка

стандартен д^~ к)ще съответства на теглото и процедурата за клъстериране ще приключи. С голям Пи малки да сеалгоритъмът бързо достига до стабилно решение, т.е. до решение, при което стандартите, получени след първото прилагане на алгоритъма, съвпадат по брой и състав със стандартите, открити при повторение на метода. Независимо от това, алгоритмичната процедура винаги се повтаря няколко пъти, като се използва разпределението, получено при предишни изчисления, като референтни вектори (като първоначално приближение): намерени преди това референции e[ p k e (2 p k) k)взети за e (x 0) 9 ... 9 e (k 0) 9и алгоритмичната процедура се повтаря.

• 2. Метод за търсене на конденз.Това е следният итеративен алгоритъм. Не изисква априорна спецификация на броя на клъстерите. На първата стъпка матрицата на разстоянието между X X9 ... 9 X p e Y1 pспоред някакъв показател. След това произволно се избира един вектор, който да играе ролята на център на първия клъстер. Това е първоначалното приближение. Нека приемем, че този вектор лежи в центъра на p-измерна сфера с радиус R,и този радиус се задава от изследователя. След това се определят векторите X Si ,... 9 X Sk , хванати в тази сфера и селекцията се изчислява от тях
• - 1 да се

съдбовен очаквана стойност X \u003d ~ Y] X 5. След това центърът на сферата

носен в хи изчислителната процедура се повтаря. Условието за края на итеративния процес е равенството на средните вектори хнамерени на Tи (t+ 1) стъпки. Елементи, уловени вътре в сферата X 9 ... 9 X

включваме ги в един клъстер и ги изключваме от по-нататъшни изследвания. За останалите точки алгоритъмът се повтаря. Алгоритъмът се събира за всеки избор на първоначално приближение и произволно количество първоначални данни. Въпреки това, за да се получи стабилен дял (т.е. дял, в който клъстерите, открити след първото прилагане на алгоритъма, съвпадат по брой и състав с клъстерите, открити при повторение на метода), се препоръчва алгоритмичната процедура да се повтори няколко пъти за различни стойности на радиуса на сферата Р.Знак за стабилен дял ще бъде образуването на същия брой клъстери със същия състав.

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

Позволявам X X9 ... 9 X pд U1 R -някакъв набор от наблюдения, който е разделен на класове S = (S l9 ... 9 S k ) 9и да сеизвестен предварително. Тогава основните функционали за качество на разделяне за известен брой клъстери имат формата:

1) Претеглена сума на вътрешнокласовите дисперсии

където а(1)- селективно математическо очакване на клъстера Сл

Функционален Q((S)ни позволява да оценим степента на хомогенност на всички клъстери като цяло.

2) Сумата от двойните вътрешнокласови разстояния между елементите или

където стр. 1- брой елементи в клъстера С { .

3) Обобщена вътрешнокласова дисперсия

където nj- брой елементи в С., НО; . -примерна ковариационна матрица за sj.

Функционалът е средноаритметичната стойност на обобщените вътрешнокласови дисперсии, изчислени за всеки клъстер. Както е известно, обобщената дисперсия позволява да се оцени степента на дисперсия на многовариантните наблюдения. Ето защо Q 3 (S)позволява да се оцени средното разсейване на векторите на наблюдение в класовете S l9 ... 9 S k .Оттук идва и името му - обобщена вътрешнокласова дисперсия. Q 3 (S)се използва, когато е необходимо да се реши проблемът с компресирането на данни или концентрацията на наблюдения в пространство с размери, по-малки от оригиналния.

4) Качеството на класификацията на наблюденията може да бъде оценено и с помощта на критерия Hotelling. За целта прилагаме критерия за проверка на хипотезата H 0относно равенството на средните вектори на две многомерни съвкупности и изчислете статистиката

където n tи p t -брой вектори в класове Sl,Sm; X, X t- центрирани изходни данни; С*-обединена ковариационна матрица на клъстери S n S m: S* =--- (XjX l + X^X m). Както и преди, стойността Q 4 (S)

p,+p t -2

в сравнение с табличната стойност, изчислена по формулата

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

Хипотеза H 0се приема с вероятност (1-oc), ако Q 4 (S) n _ m и се отхвърля в противен случай.

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

Ако броят на клъстерите в С = (S l9 ...,S k )не е известно предварително, тогава следните функционали за качество на разделяне се използват за произволно избрано цяло число м:

азазда се 1 1 м

- - средната мярка за вътрешноклас

P i=1 n i XjeSj X"tSjДж

разпръскване на сова,

• (1 П/ 1W
• - X ~-~ r “ мярка за концентрация на точки от множеството

П nV l J J

S, - броят на елементите в клъстера, съдържащ точката X g

Имайте предвид, че за произволна стойност на параметъра Tфункционален Z m (S)достига минимум равен на I/p,ако първоначалното клъстериране S = (S l9 ...,S k )е дял на моно-клъстери S. = (Xj), защото V(Xt) = 1. В същото време Z m (S) достига максимум 1 ако С- един клъстер, съдържащ всички първоначални данни,

защото V(X() = n.В конкретни случаи може да се докаже, че Z_ l (S) =-, където да се -брой различни клъстери в S = (S l9 ... 9 S k ) 9 Z X (S) =макс - ,

*" В П)

където n t -брой елементи в клъстера S i9 Z^(S) =мин - ,

G " П)

Имайте предвид, че в случай на неизвестен брой клъстери, качеството на разделяне функционира Q(S)може да се избере като алгебрична комбинация (сума, разлика, произведение, отношение) на два функционала I m (S), Z m (S),тъй като първата е намаляваща, а другата е нарастваща функция на броя на класовете да се.Такова поведение Z m (S)

гарантира наличието на екстремум Q(S).

Изпратете добрата си работа в базата знания е лесно. Използвайте формата по-долу

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

Подобни документи

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

доклад, добавен на 02.11.2009 г


Характеристики на строителната индустрия на Краснодарския край. Прогноза за развитието на жилищното строителство. Съвременни методи и средства за клъстерен анализ. Многомерни статистически методи за диагностика на икономическото състояние на предприятието.

дисертация, добавена на 20.07.2015 г


Моделиране. Детерминизъм. Детерминирани задачи факторен анализ. Начини за измерване на влиянието на факторите в детерминистичния анализ. Изчисляване на детерминирани икономико-математически модели и методи за факторен анализ на примера на RUE "GZlin".

курсова работа, добавена на 05/12/2008


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

дисертация, добавена на 09.10.2013 г


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

резюме, добавено на 15.07.2011 г


Основна терминология, понятие и методи на факторния анализ. Основните етапи на факторния анализ и техниката на Чеботарев. Практическото значение на факторния анализ за управлението на предприятието. Методът на Лагранж при решаване на проблеми на факторния анализ.

тест, добавен на 26.11.2008 г


Извършвайте клъстерен анализ на предприятия с помощта на Statgraphics Plus. Построяване на уравнение на линейна регресия. Изчисляване на коефициенти на еластичност чрез регресионни модели. Оценка на статистическата значимост на уравнението и коефициента на детерминация.

Въведение

Терминът клъстерен анализ, въведен за първи път от Tryon през 1939 г., включва повече от 100 различни алгоритми.

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

Клъстерният анализ ви позволява да намалите размерността на данните и да ги направите визуални.

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

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

Задачите за клъстерен анализ могат да бъдат групирани в следните групи:

Разработване на типология или класификация.

Проучване на полезни концептуални схеми за групиране на обекти.

Представяне на хипотези въз основа на проучване на данни.

Тестване на хипотеза или изследване, за да се определи дали типовете (групите), идентифицирани по един или друг начин, действително присъстват в наличните данни.

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

Цел на урока

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

Практическа задача

Разработване на алгоритми за близки съседни методи и к-средство и да ги реализират под формата на компютърни програми. Генерирайте 50 реализации с помощта на DNC х= (х 1 ,х 2) - случайна двумерна променлива, чиито координати са разпределени равномерно в интервала (3.8). Разпределете ги с помощта на разработените програми в минималния брой клъстери, всеки от които е поставен в сфера с радиус 0,15.

Насоки

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

Клъстерът има следните математически характеристики:

• клъстерна дисперсия;

  стандартно отклонение.

Центърът на клъстера е геометричното място на точките в пространството на променливите.

Радиус на клъстера - максималното разстояние на точките от центъра на клъстера.

Дисперсията на клъстера е мярка за разпространението на точки в пространството спрямо центъра на клъстера.

Стандартното отклонение (RMS) на обектите спрямо центъра на клъстера е корен квадратен от дисперсията на клъстера.

Методи за клъстерен анализ

Методите за клъстерен анализ могат да бъдат разделени на две групи:

йерархичен;

нейерархичен.

Всяка група включва много подходи и алгоритми.

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

Йерархични методи за клъстерен анализ

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

Йерархични агломеративни методи(Агломеративно гнездене, AGNES)

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

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

Йерархични делими (делими) методи(DIvisive ANAlysis, ДИАНА)

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

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

Мерки за подобие

За изчисляване на разстоянието между обектите се използват различни мерки за сходство (мерки за сходство), наричани още метрики или функции за разстояние.

Евклидово разстояниее геометрично разстояние в многомерно пространство и се изчислява по формула (4.1).

Евклидовото разстояние (и неговият квадрат) се изчислява от оригиналните данни, а не от стандартизирани данни.

Евклидово разстояние на квадрат се изчислява по формула (4.2).

(4.2)

Разстояние Манхатън (разстояние от градски блок), наричано също разстояние "хаминг" или "градски блок", се изчислява като средната стойност на разликите в координатите. В повечето случаи тази мярка за разстояние води до резултати, подобни на изчисленията на евклидовото разстояние. За тази мярка обаче ефектът от отделните отклонения е по-малък, отколкото при използване на евклидовото разстояние, тъй като тук координатите не са повдигнати на квадрат. Разстоянието Манхатън се изчислява по формула (4.3).

(4.3)

Разстояние Чебишев трябва да се използва, когато е необходимо да се определят два обекта като "различни", ако се различават в едно измерение. Чебишевското разстояние се изчислява по формула (4.4).

(4.4)

Силово разстояниесе използва, когато желаете прогресивно да увеличите или намалите теглото, свързано с измерение, за което съответните обекти са много различни. Силовото разстояние се изчислява по формула (4.5).

(4.5)

където rи п-дефинирани от потребителя параметри. Параметър стротговаря за постепенното претегляне на разликите над отделните координати, параметърът rза прогресивно претегляне на големи разстояния между обекти. Ако и двата варианта rи стрса равни на две, то това разстояние съвпада с Евклидовото разстояние.

Процент на несъгласиеизползва се, когато данните са категорични. Това разстояние се изчислява по формула (4.6).

(4.6)

Методи за присъединяване или свързване

На първата стъпка, когато всеки обект е отделен клъстер, разстоянията между тези обекти се определят от избраната мярка. Въпреки това, когато множество обекти са свързани заедно, трябва да се използват други методи за определяне на разстоянието между клъстерите. Има много методи за свързване на клъстери:

Единична връзка (метод на най-близкия съсед) - разстоянието между два клъстера се определя от разстоянието между двата най-близки обекта (най-близки съседи) в различни клъстери.

Пълна връзка (метод на най-отдалечения съсед) – разстоянията между клъстерите се определят от най-голямото разстояние между всеки два обекта в различни клъстери (т.е. „най-отдалечени съседи“).

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

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

Метод на непретеглен центроид - разстоянието между два клъстера се определя като разстоянието между техните центрове на тежест.

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

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

Метод на най-близкия съсед

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

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

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

итеративни методи.

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

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

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

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

Алгоритъм k-средни (k-средни)

Сред итеративните методи най-популярният метод е методът к- среден Маккийн. За разлика от йерархичните методи, в повечето реализации на този метод потребителят сам трябва да посочи желания брой крайни клъстери, което обикновено се обозначава с " к". Алгоритъм к-средно телосложение кклъстери, разположени възможно най-далеч един от друг. Основното изискване за типа задачи, които алгоритъмът решава к-средни - наличието на предположения (хипотези) относно броя на клъстерите, като същевременно те трябва да бъдат възможно най-различни. Избор на номер кможе да се основава на предишни изследвания, теоретични съображения или интуиция.

Както при йерархичните методи за клъстериране, потребителят може да избере един или друг тип мярка за сходство. Алгоритми на различни методи к-средните се различават и по начина на избор на началните центрове на посочените клъстери. В някои версии на метода самият потребител може (или трябва) да посочи такива начални точки, или като ги избере от реални наблюдения, или като посочи координатите на тези точки за всяка от променливите. В други реализации на този метод, избор на дадено число кначалните точки се произвеждат на случаен принцип и тези начални точки (клъстерни центрове) могат впоследствие да бъдат прецизирани на няколко етапа. Има 4 основни етапа на такива методи:

избран или назначен кнаблюдения, които ще бъдат първични центрове на клъстери;

ако е необходимо, се формират междинни клъстери чрез присвояване на всяко наблюдение на най-близките дадени клъстерни центрове;

след присвояване на всички наблюдения на отделни клъстери, основните центрове на клъстери се заменят със средни клъстерни стойности;

предишната итерация се повтаря, докато промените в координатите на центровете на клъстера станат минимални.

Общата идея на алгоритъма: даден фиксиран брой k клъстери за наблюдение се сравняват с клъстери по такъв начин, че средните стойности в клъстера (за всички променливи) да се различават възможно най-много една от друга.

Описание на алгоритъма

Първоначално разпределение на обектите по клъстери.

Избран номер ки кточки. На първата стъпка тези точки се считат за "центрове" на клъстерите. Всеки клъстер съответства на един център. Изборът на начални центроиди може да се извърши, както следва:

избор к-наблюдения за максимизиране на първоначалното разстояние;

случаен избор к-наблюдения;

първи избор к-наблюдения.

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

Итеративен процес.

Изчисляват се центровете на клъстерите, които след това и по-нататък се считат за средни координати на клъстерите. Обектите се преразпределят отново. Процесът на изчисляване на центрове и преразпределение на обекти продължава, докато не бъде изпълнено едно от следните условия:

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

броят на итерациите е равен на максималния брой итерации.

Проверка на качеството на групиране

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

Предимстваk-средни алгоритъм:

лекота на използване;

скорост на използване;

яснота и прозрачност на алгоритъма.

недостатъциk-средни алгоритъм:

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

алгоритъмът може да бъде бавен при големи бази данни. Възможно решение на този проблем е използването на извадка от данни.

Докладът трябва да съдържа:

описание и блокови схеми на алгоритми;

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

резултатите от алгоритмите под формата на графики.