Лично подоходно облагане


Категория на документа: Финанси


Нека условието D21>Т е изпълнено, т.е. Z2 е център на нов кластер. На следващата стъпка се изчисляват разстоянията D31 и D32 на образа Х3 до центровете на кластерите Z1 и Z2. Ако двете разстояния са по-големи от прага Т, то се формира нов кластер с център Z3=X3. В противен случай Х3 се зачислява към един от първите два кластера, чиито център е по-близо до Х3. По подобен начин се изчислява разстоянието от всеки нов образ до всеки център на известен вече кластер. Тези разстояния се сравняват с праговата стойност Т. Ако всички те са > Т, се формира нов център на кластер, В противен случай образът се зачислява в кластера с най-близко разположен център.

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

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

Фиг 4.2. Илюстрация на влиянието на избора на прага и изходната точка върху кластеризацията

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

2. Алгоритъм на мини-максното-разстояние (минимално-максималното)

Алгоритъмът, основан на принципа на max-min. разстояние, представлява друга проста евристична процедура, използваща евклидовото разстояние [...]. По принцип той е аналогичен на описаната в точка 4 схема, с изключение на това, че

Фиг 4.3. а) извадка от образи, използвани за илюстрация на алгоритъма на max-min разстояние; б) таблица, съдържащи образи от извадката и класовете

най-напред той отделят най-отдалечените кластери. Процедурата ще бъде пояснена с конкретен пример. Разглеждме извадка, състояща се от 10 двумерни образи (фиг.4.3.а.). До началото на процедурата таблиците от фиг4.3.б са празни. На първата стъпка от алгоритъма един от обектите , например Х1, по произволен начин се определя като център на първия кластер ( на фиг. 4.3б този кластер е означен с Z1 ). Цифрите, разположени над стрелките на фиг.4.3б показват поредния номер на стъпката, на която се извършва определянето на съответния кластер.

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

На третата стъпка от алгоритъма се изчисляват разстоянията между всички останали образи от извадката и центровете на кластерите Z1 и Z2. От всяка двойка от тези разстояния се определя минималното разстояние. След това от определените минимални разстояния се определя на най-голямото (максималното). Ако последното представлява значителна част от разстоянието между центровете на кластерите Z1 и Z2 (примерно най-малко половината от това разстояние) съответстващия образ се избира за център на нов кластер Z3. В противен случай процедурата се прекратява. Ако се използва този критерий, в разглеждания пример център на новия кластер Z3 става образът X7.

На следващата стъпка от алгоритъма се изчислява разстоянието между трите отделени центрове на кластерите и всички останали образи от извадката. Във всяка група от трите разстояния се избира минималното. След това, както и в предишната стъпка, се намира максималното от тези минимални разстояния. Ако последното представлява значителна част от "типичните" предидущи max. разстояния, то съответстващият образ се определя за център на нов кластер Z4. В противен случай процедурата се прекратява. Добра мярка за оценка на "типичните" предидущи разстояния е средната им стойност. Ако приложим този критерий за разглеждания пример и се представи изискването, че новото max. разстояние трябва да се поне половината от средното max. разстояние, то от фиг.4.3.а, следва, че поредното max. разстояние, което е разстоянието между образите Х1 и Х3, не удовлетворява това условие. Затова след тази стъпка процедурата се прекратява. В общия случай описаната процедура се повтаря до тогава, докато на някоя стъпка не бъде получено max. разстояние, за което условието, определящо формирането на нов кластер, не се изпълнява.

В разглеждания прост пример процедурата отделя три кластерни центъра Х1, Х6, и Х7. При отнасяне на останалите образи от извадката към един от формираните вече кластери се използва критерий, според който класифицираният образ се зачислява в този кластер, центърът на който се намира най-близо до образа. За фиг. 4.3а получените три кластера са : { X1, X3, X4 }, { X2, X6 } и { X5, X7, X8, X9, X10 }. Резултатите съответстват за нашето интуитивно представяне за групирането на тези данни. Може по-точно да се определят центровете на кластерите, изчислявайки за всеки набор координатите на осреднения център по формула (4.10), като за целта се използват координатите на точките от съответния набор. Тези осреднени образи се считат за новите центрове на кластерите.

3.Алгоритъм на К-вътрешногрупираните средни.

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

1.Стъпка: избират се К изходни центрове на кластери Z1(1), Z2(1)...ZК(1). Изборът обикновено е произволен и най-често като изходни центрове се вземат първите К елемента от зададеното множество образи. За разлика от предходните процедури тук предварително се задава броят на класовете, в които трябва да се разпределят входните данни.

2.Стъпка: На к-тата стъпка от итерационната процедура зададеното множество от образи {X} се разпределя в К кластера по следното правило

X  Sj(k), ако ||X-Zj(k)|| < ||X-Zi(k)|| 4.11
за всяко i=1,2,...К, ij, където Sj(k) е множеството от образи, влизащи в кластер с център Zj(k). В случай на равенство в (4.11) решението се взема произволно.

3.Стъпка: Въз основа на резултатите от стъпка 2 се определят новите центрове на кластерите Zj(k+1), j=1,2...K, изхождайки от условието, че сумата на квадратите на разстоянията между всички образи, принадлежащи на множеството Sj(k) и новият център на кластера трябва да бъдат минимални. С други думи новите центрове на кластерите Zj(k+1) се избират така, че да се минимизира показателя на качество

, j=1,2, ...K 4.12 Центърът Zj(k+1), осигуряващ минимизация на показателя на качество, всъщност е среден за извадката, определено по множеството Sj(k). Следователно новите центрове на кластерите се определят като

, j=1,2,...K, 4.13
където Nj е броят на образите от извадката, влизащи в множеството Sj(k).

4.Стъпка: Равенството Zj(k+1)=Zj(k) при j=1,2,...K се явява условие за сходимост на алгоритъма, и при неговото достигане алгоритъмът завършва. В противен случай алгоритъмът се повтаря от стъпка 2.

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

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

Фиг 4.4. Извадка от образи, илюстрираща работата на алгоритъма за два центъра на кластеризация



Сподели линка с приятел:





Яндекс.Метрика
Лично подоходно облагане 9 out of 10 based on 2 ratings. 2 user reviews.