Klasterovanje Flashcards
Sta je klasterovanje?
Извршити поделу датог скупа обjеката X = {x1 , x2 , …, xn } на групе
(подскупове) тако да jе обjекат xi коjи припада групи Gl сличниjи по
неком критериjуму обjектима xj коjи припадаjу (истоj) групи Gl него
неком обjекту xk коjи припада некоj другоj групи Gm . Свака од група
G се назива кластер, а целокупан поступак поделе улазног скупа
кластеровање.
Sta utice na izbor metode klasterovanja?
Избор методе кластеровања и мере помоћу коjе се рачуна сличност у великоj
мери зависе од типа податка коjе треба кластеровати. Такође, у великом броjу
случаjева ниjе до краjа jасно дефинисано шта све могу да буду целине коjе
представљаjу кластере, тако да jе честа недоумица да ли jе броj кластера коjи се
добиjе као резултат коректан.
Sta je klaster analiza?
Проналажење група обjеката таквих да су обjекти у групи међусобно слични (или повезани), и да су обjекти у различитим групама међусобно различити (или неповезани)
Sta jeste a sta nije klaster analiza ?
Припадност обjеката (елемената) jедном кластеру не значи да су
елементи међусобно слични по свим критериjумима
Не представља свака подела материjала у групе кластер анализу.
-Класификациjа под надзором
-Jедноставна подела
-Резултат упита
Tipovi klasterovanja
1.Екслузивно/неекслузивно кластеровање, у зависности од тога да ли
поjединачни елемент коjи се кластеруjе припада само jедном (ексклузивно)
или може истовремено да се налази у више кластера (неексклузивно
кластеровање)
2.Расплинуто/нерасплинуто кластеровање. У расплинутом кластеровању
елемент припада сваком кластеру са неком тежином између 0 и 1, при
чему jе збир тежина елемента у свим кластерима jеднак 1
3.Делимично/комплетно кластеровање у зависности од тога да ли се
кластеруjе само део података или комплетан скуп
4.Хетерогено/хомогено кластеровање. Ако су кластери различите
величине, облика и/или густине тада се кластеровање назива нехомогено.
5.Код партиционог кластеровања скуп улазних података се дели у непреклапаjуће
подскупове (кластере) такве да сваки податак припада тачно jедном кластеру
6.У случаjу да кластери могу да садрже (угнеждене) кластере, тада jедан елемент
може да припада више кластера на различитим нивоима хиjерархиjе -
хиjерархиjско кластеровање
Tipovi klastera
1.Добро раздвоjени кластери (енг. well-separated)
Карактеристика добро раздвоjених кластера jе да им припадаjу
елементи такви да су ближе било ком другом елементу у кластеру
него осталим елементима коjи нису у кластеру, при чему се често
поставља праг за максималну удаљеност елемената у истом кластеру.
Оваj случаj се jавља само код природно раздвоjених кластера.
2.Кластери засновани на центру (енг. center-based,prototype-based)
Кластер jе скуп обjеката таквих да jе било коjи обjекат у кластеру
ближи (или више сличан) прототипу (“центру”) кластера у односу на
прототипове (центре) осталих кластера. Центар кластера jе често
центроид (просек свих тачака у кластеру) или медоид
(наjрепрезентативниjа тачка у кластеру)
3.Кластери засновани на графовима
Ако су елементи представљени као чворови повезаног графа, тада кластери могу да буду скупови обjеката коjи су међусобно повезани, али нису повезани са обjектима ван групе, односно коjи припадаjу изолованом
подграфу.
4.Кластери засновани на суседству (енг. contiguous based clusters)
Кластери засновани на суседству представљаjу врсту кластера заснованих на графовима код коjих два елемента припадаjу истом кластеру акко су на
растоjању коjе jе мање од унапред дефинисаног прага. Последица оваквог услова jе да за сваки елемент коjи припада овом типу кластера постоjи елемент из истог кластера коме jе он ближи него било ком елементу коjи припада другом кластеру.
5.Кластери засновани на густини (енг. density-based)
Кластери су области са великом густином тачака коjе су раздвоjене областима са малом густином тачака. Ова карактеристика кластера се користи када су кластери неправилни или испреплетени, и када су присутни шум или елементи ван граница.
6.Концептуални кластери/кластеровање на основу заjедничких особина (енг. conceptual clusters)
Оваj тип кластера се добиjа када се кластер дефинише као скуп елемената коjи имаjу исту заjедничку карактеристику. Иако ова дефинициjа обухвата велики броj претходно наведних дефинициjа кластера, постоjе случаjеви када заjедничка особина не може да се изрази преко уобичаjених мера. Тако на претходноj слици, заjедничка особина елемената jе њихов облик.
Algoritmi zasnovani na reprezentnim predstavnicima
Основни принцип: За скуп од n тачака X1 , X2 , …, Xn у d
димензионом простору циљ jе пронаћи k репрезентативних тачака
Y1 , Y2 , … Yk , где jе k коjе минимизуjу циљну функциjу
O =∑ [minj Dist(Xi , Yj )]
x где Dist(A, B) функциjа растоjања
Algoritam K-sredina
Алгоритам k-средина jе jедан од два (поред k-медиjана)
наjзначаjниjа представника модела са прототипом. У овом алгоритму
се прототип дефинише као центроид.
За разлику од алгоритама кластеровања коjи интерно одређуjу
наjбољи броj кластера, алгоритам k-средина захтева да се броj
кластера k наведе унапред. Алгоритам се извршава тако што се
инициjално свака тачка додељуjе кластеру са наjближим центроидом.
У наредном кораку се врши израчунавање нових центроида, и
ре-израчунавање припадности сваке тачке поjедином кластеру.
-За одређивање растоjања могу да се користе различите
мере (обрађене у уводном делу курса!).
-Алгоритам конвергира за поменуте мере, при чему се
наjвећи део конвергенциjе дешава у првих неколико
итерациjа
-Као услов заустављања алгоритма се задаjе броj тачака
коjе промене кластер у одређеноj итерациjи. Ако jе броj
тачака коjе промене кластер мањи од задатог прага,
алгоритам страjе.
nedostatak K-sredina
Jедан од недостатака методе jе често бирање почетних
центроида на случаjан начин. Резултат оваквог начина
избора jе добиjање кластера коjи могу да се разликуjу од
’природних’ кластера, односно добиjање
незадовољаваjућих резултата
Kako se procenjuje kvalitet dobijenih klastera
За податке у Еуклидском простору се
наjчешће као мера користи збир квадрата грешака (енг. sum of
squared errors, SSE ).
SSE = ∑ ∑dist(ci , x)^2
Jедан од начина за смањење SSE jе повећање броjа кластера k
Добро кластеровање са малим k може да има мању SSE
грешку од лошег кластеровања са великим k
Klasterovanje dokumenata k-sredinom
За документе се као мера користи косинусно растоjање
Подаци се представљаjу преко матрице термова
Степен сличности докумената у кластеру са центроидом се
назива кохезиjа кластера
Аналогон SSE у случаjу кластеровања текстуалних
докумената jе укупна кохезиjа коjа се израчунава као
Ukupna kohezija = ∑ ∑ cosinus(ci , x)
i=1 x∈C
Sta je suboptimalno klasterovanje?
У групу некоректних резултата спада и тзв. суб-оптимално
кластеровање у ком случаjу jе извршено кластеровање материjала, али ниjе
добиjена глобално већ само локално наjмања вредност SSE
Izbor pocetnih centroida
Узастопна извршавања алгоритма : primer u svakom slucajno izabrani centroid bira se onaj sa min SSE
Ако постоjи k ’реалних’ кластера тада jе вероватноћа да се изабере по jедан центроид у сваком од њих релативно мала
Ако jе k велико шанса за добар избор jе мала.
Ако кластери имаjу исту величину n, тада важи:
P = (броj начина за избор центроида у сваком кластеру) /(броj начина за избор к центроида)
#primeni se hijerarhijsko, izaberu pocetni
#primeni se m(m > k) pocetnih centroida i od njih se izabere k dobrih - treba da pokriju sto siri prostor
#postprocesiranje dobijeni rezultata
-uklanjanje elem van granica
- eliminacija malih klastera sa elementima van granice
- podela klastera sa velikim SSE
- grupisanje klastera koji su blizu
#priprema bisekcije k- sredine
- pocetni skup tacaka se podeli u 2,jedan od njih se izabere za dalju podelu i tako sve dok se ne podeli na k klastera
- nacin podele : 1. podela najveceg 2. sa najvecim SSE 3.kombinacije ta 2
Rad sa praznim klasterima
Основни алгоритам k-средина може да произведе празне кластере
при извршавању. При томе ’празан’ означава да се у том кластеру
налази само центроид, без иjедног елемента.
Стратегиjе за елиминациjу празних кластера укључуjу замену
центроида на неки од следећих начина:
1.Изабрати тачку коjа наjвише учествуjе у SSE
2.Изабрати тачку коjа jе наjдаље од текућих центроида
3.Изабрати тачку из кластера са наjвећим SSE . Оваj начин
обично доводи до деобе кластера
4.Ако има више празних кластера поновити поступак
Algoritam bisekcije k-sredina
Varijanta je algoritma k-sredina koja moze da proizvede particiono ili hijerarhijsko klasterovanje.
Основна идеjа: за добиjање k кластера подели се скуп свих тачака у
два кластера, изабере се jедан од њих за поделу, уз понављање
поступка све док се не добиjе К кластера. Различити начини поделе
кластера су:
1.подели се наjвећи кластер
2.подели се кластер са наjвећим ССЕ
3.користи се критериjум заснован и на величини кластера и на
величини ССЕ-а
Ова метода се често не користи за само кластеровање, већ се
добиjени центроиди користе за улаз у основни К-средина алгоритам
кластеровања!!!
nedostaci i ogranicenja k-sredina
1.не функционише за кластере произвољног облика
2.не функционише за кластере различитих густина
3.осетљив jе на елементе ван граница коjи могу да доведу
до jединичних или празних кластера
4.проблем представља одређивање репрезентативних
представника и броjа кластера k
Dobre strane algoritma k-sredina
1.Jедноставност имплементациjе и примене
2.Наjбоље ради са глобуларним подацима
3.Ако се као мера растоjања користи Махаланобисово
растоjање, алгоритам к-средина препознаjе кластере
различитих густина
Algoritam k-medijana
Алгоритам k-медиjана jе сличан алгоритму k-средина, при чему се
као центроид користи медиjана. Неке карактеристике овог алгоритма
су:
—Користи се растоjање такси блок.
—Показуjе се да репрезентативни представник медиjана података
по свакоj димензиjи кластера Cj
—Мања jе осетљивост на елементе ван граница
У алгортиму k-медоида избор центроида се увек врши из инциjалног
скупа тачака. Иако ниjе оптималан, разлог за овакав избор jе утицаj
елемената ван граница на медиjану, мада jе понекад тешко
израчунати центар за одређене (сложене) типове података. Као и код
k-медиjане и у овом алгоритму се као мера растоjања користи такси
блок.
Hijerarhijsko klasterovanje
Основна идеjа ове групе алгоритама jе формирање скупа
угнеждених кластера коjи су организовани у облику хиjерахиjе по нивоима.
Резултати ове групе алгоритама се наjчешће визуелизуjу у облику дендограма
или диjаграма са угнежденим кластерима на коме се, поред односа
кластер/подкластер, види и редослед формирања кластера, односно коjа два
подкластера се спjаjу у кластер
Algoritmi sakupljajuceg klasterovanja
hijerahija se formira odozdo /navise na pocetku se svaka tacka posmatra kao klaster zza sebe i u svakom koraku se spajaju najbliza 2 klastera nekom kriteriju]im dok ne ostane samo 1 klaster
neki algoritmi dopustaju presecanje -ranije zavrsavanje,ako se dodje do unapred zadatog broja klastera ili nivoa hijerarhije
- razlicite mere za rastojanje - Minkovski ..
nedostaci: cuvanje matrice rastojanja,treba je modifikovati ili povezi novi pri formiranju novog klastera
Algoritmi razdvajajuceg klasterovanja
hijerarhija se formira odozgo/nanize - na pocetku sve tacke pripadaju 1 klasteru koji se u narednim koracima deli sve dok se ne dodje do klastera koji sadrzi samo pojedinacne tacke
Slicnost klastera
- min veza( najboja ,najkraca pojedinacna veza)
- rastojanje klastera je najmanje izmedju bilo koje 2 tacke koje im pripadaju
2.max veza(najgora ,najduza)
-rastojanje je najvece moguce
3.prosecno rastojanje
-tacke koje im pripadaju mogu se ukljuciti i tezinski vaktori,zavise od br. tacaka u klasteru,rastojanje svih tacaka
4.rastojanje izmedju centroida(moze i mediana)
-spajaju se klasteri cije su centroide najblize
-ne pravi se razlika kod spajanja klastera razlicitih velicina ako je rastojanje medju centroidima isto
-posle spajanje se opet racunaju centoidi(moze da se desi da je rastojanje manje na nivou k nego na nivou k-1)
5.minimizuju promenu varijanse
-posle spajanja se menja varijansa deltaSEij = SEij -SEi-SEj
6.Ward-ов метод и коме се уместо вариjансе користи збир квадрата грешака.
Нови кластер се формира од два кластера чиjим спаjањем се добиjа минимално повећање збира квадарата грешака унутар новог кластера. Тако, у општем случаjу грешка E jе jеднака
K E = ∑ ∑ || xi − ck ||2 k=1xi∈Ck
где jе K броj кластера, и ck центроид кластера Ck добиjеног спаjањем два кластера. Промена се рачуна само за новодобиjени кластер на основу кластера од коjих jе настао и износи
∇Eij = minj ||ci −cj ||2 mi +nj
где mi и nj представљаjу броj тачака у кластерима Ci и Cj .
Koje su vrednosti sakupljajuceg klasterovanja
-posle kombinovanja klasteri ne mogu da se razdvoje, ovo se resava tako sto radimo particionisano klasterovanje za formiranje manjih klastera na kojima se vrsi hijerarhijsko kasnije
-ne postoji globalna funkcija koja se direktno minimizuje
-u zavisnosti od racunanja rastojanja javljaju se :
#осетљивост на шум и елементе ван граница
#тешкоће у обради кластера различитих величина
#тешкоће у обради неглобуларних кластера
#тенденциjа ка разбиjању великих кластера
Lance -williams formula
za slicnost klastera
omogucava da se matrica slicnosti azurira kod svakog spajanja tj. ne moraju da se cuvaju originalne tacke
R- dobijen spajanjem A i B (klaster)
P - funkcija slicnosti
slicnost klastera P i Q je:
p(R,Q) = alfaA p(A,Q)+ alfaB p(B,Q)+ alfap p(A,B)+gama(p(A,Q) -p(B,Q))
