Algoritmi za grupisanje podataka. Algoritmi zasnovani na teoriji grafova

Klaster analiza je

Dobar dan. Ovdje poštujem ljude koji su ljubitelji svog rada.

Maksim, moj prijatelj, pripada ovoj kategoriji. Konstantno radi sa brojkama, analizira ih, pravi relevantne izvještaje.

Jučer smo zajedno ručali, pa mi je skoro pola sata pričao o klaster analizi – šta je to i u kojim slučajevima je njena primena razumna i svrsishodna. Pa, šta je sa mnom?

Imam dobro pamćenje, pa ću vam, inače, dati sve ove podatke za koje sam već znao u originalnom i najinformativnijem obliku.

Klaster analiza je dizajnirana da podijeli skup objekata u homogene grupe (klastere ili klase). Ovo je zadatak multivarijantne klasifikacije podataka.

Postoji oko 100 različitih algoritama klasteriranja, međutim, najčešće se koriste hijerarhijska analiza klastera i k-means klasterizacija.

Gdje se primjenjuje klaster analiza? U marketingu je to segmentacija konkurenata i potrošača.

U menadžmentu: podjela osoblja na grupe različitih nivoa motivacije, klasifikacija dobavljača, identifikacija sličnih proizvodnih situacija u kojima dolazi do braka.

U medicini, klasifikacija simptoma, pacijenata, lijekova. U sociologiji je podjela ispitanika na homogene grupe. Zapravo, klaster analiza se dobro dokazala u svim sferama ljudskog života.

Ljepota ove metode je u tome što radi čak i kada ima malo podataka i kada nisu ispunjeni zahtjevi za normalnost distribucija slučajnih varijabli i drugi zahtjevi klasičnih metoda statističke analize.

Objasnimo suštinu klaster analize bez pribjegavanja strogoj terminologiji:
Recimo da ste sproveli anketu zaposlenih i želite da utvrdite kako najefikasnije upravljate svojim osobljem.

Odnosno, želite podijeliti zaposlenike u grupe i odabrati najefikasnije kontrolne poluge za svaku od njih. Istovremeno, razlike između grupa treba da budu očigledne, a unutar grupe ispitanici treba da budu što sličniji.

Za rješavanje problema predlaže se korištenje hijerarhijske klaster analize.

Kao rezultat, dobićemo stablo, gledajući u koje moramo odlučiti na koliko klasa (klastera) želimo da podelimo osoblje.

Pretpostavimo da odlučimo podijeliti osoblje u tri grupe, a zatim da proučimo ispitanike koji su upali u svaki klaster, dobijemo tablet sa sljedećim sadržajem:

Objasnimo kako je formirana gornja tabela. Prva kolona sadrži broj klastera — grupe čiji se podaci odražavaju u redu.

Na primjer, prvi klaster je 80% muškaraca. 90% prvog klastera spada u starosnu grupu od 30 do 50 godina, a 12% ispitanika smatra da su beneficije veoma važne. I tako dalje.

Pokušajmo napraviti portrete ispitanika svakog klastera:

Prva grupa su uglavnom muškarci zrele dobi, koji zauzimaju rukovodeće pozicije. Socijalni paket (MED, LGOTI, VRIJEME-slobodno vrijeme) ih ne zanima. Više vole da primaju dobru platu, nego pomoć od poslodavca.
Grupa dva, naprotiv, preferira socijalni paket. Sastoji se uglavnom od "starih" ljudi koji zauzimaju niske pozicije. Plata im je svakako bitna, ali tu su i drugi prioriteti.
Treća grupa je „najmlađi“. Za razliku od prethodna dva, postoji očigledan interes za učenje i mogućnosti profesionalnog razvoja. Ova kategorija zaposlenih ima dobre šanse da uskoro popuni prvu grupu.

Dakle, prilikom planiranja kampanje za uvođenje efikasnih metoda upravljanja kadrovima, očigledno je da je u našoj situaciji moguće povećati socijalni paket za drugu grupu na štetu, na primjer, plata.

Ako govorimo o tome koje stručnjake treba poslati na obuku, onda svakako možemo preporučiti da obratite pažnju na treću grupu.

Izvor: http://www.nickart.spb.ru/analysis/cluster.php

Karakteristike klaster analize

Klaster je cijena sredstva u određenom vremenskom periodu tokom kojeg su izvršene transakcije. Rezultirajući obim kupovine i prodaje označen je brojem unutar klastera.

Traka bilo kojeg TF-a sadrži, po pravilu, nekoliko klastera. Ovo vam omogućava da detaljno vidite obim kupovine, prodaje i njihov saldo u svakom pojedinačnom baru, za svaki nivo cijene.

Promjena cijene jedne aktive neminovno povlači lanac kretanja cijena i na drugim instrumentima.

Pažnja!

U većini slučajeva, razumijevanje kretanja trenda događa se već u trenutku kada se brzo razvija, a ulazak na tržište uz trend je prepun padanja u korektivni val.

Za uspješnu trgovinu potrebno je razumjeti trenutnu situaciju i biti u stanju predvidjeti buduća kretanja cijena. Ovo se može naučiti analizom klaster grafa.

Uz pomoć klaster analize možete vidjeti aktivnost tržišnih učesnika i unutar najmanje cijene. Ovo je najpreciznija i najdetaljnija analiza, jer pokazuje tačku distribucije obima transakcija za svaki nivo cijene imovine.

Na tržištu postoji stalna konfrontacija između interesa prodavača i kupaca. I svako najmanje kretanje cijene (kvačica) je pomak ka kompromisu - nivou cijene - koji u ovom trenutku odgovara objema stranama.

Ali tržište je dinamično, broj prodavača i kupaca se stalno mijenja. Ako su u jednom trenutku tržištem dominirali prodavci, onda će u sledećem trenutku, najverovatnije, biti kupaca.

Broj izvršenih transakcija na susjednim nivoima cijena također nije isti. Pa ipak, prvo se tržišna situacija odražava na ukupan obim transakcija, a tek onda na cijenu.

Ako vidite akcije dominantnih učesnika na tržištu (prodavaca ili kupaca), onda možete predvidjeti samo kretanje cijene.

Da biste uspješno primijenili klaster analizu, prvo morate razumjeti šta su klaster i delta.

Klaster se naziva kretanje cena, koje je podeljeno na nivoe na kojima su transakcije izvršene sa poznatim količinama. Delta pokazuje razliku između kupovine i prodaje u svakom klasteru.

Svaki klaster, ili grupa delta, omogućava vam da shvatite da li kupci ili prodavci dominiraju tržištem u datom trenutku.

Dovoljno je samo izračunati ukupnu deltu zbrajanjem prodaje i kupovine. Ako je delta negativna, onda je tržište preprodano, postoje suvišne transakcije prodaje. Kada je delta pozitivna, tržištem jasno dominiraju kupci.

Sama delta može poprimiti normalnu ili kritičnu vrijednost. Vrijednost delta volumena iznad normalne vrijednosti u klasteru je označena crvenom bojom.

Ako je delta umjerena, onda to karakterizira ravno stanje na tržištu. Kod normalne delta vrijednosti, na tržištu se uočava kretanje trenda, ali kritična vrijednost je uvijek predznak preokreta cijene.

Forex trgovanje sa CA

Da biste dobili maksimalan profit, morate biti u mogućnosti odrediti prijelaz delte sa umjerenog nivoa na normalan. Zaista, u ovom slučaju možete primijetiti sam početak tranzicije sa ravnog na trend kretanja i moći ćete dobiti najveći profit.

Klaster grafikon je vizualniji, na njemu možete vidjeti značajne nivoe akumulacije i distribucije volumena, nivoe podrške i otpora izgradnje. Ovo omogućava trgovcu da pronađe tačan ulaz u trgovinu.

Koristeći deltu, može se suditi o prevlasti prodaje ili kupovine na tržištu. Klaster analiza vam omogućava da posmatrate transakcije i pratite njihov obim unutar trake bilo kog TF-a.

Ovo je posebno važno kada se približavate značajnim nivoima podrške ili otpora. Klasterske prosudbe su ključ za razumijevanje tržišta.

Izvor: http://orderflowtrading.ru/analitika-rynka/obemy/klasternyy-analiz/

Područja i karakteristike primjene klaster analize

Termin klaster analiza (prvi je uveo Tryon, 1939) zapravo uključuje skup različitih klasifikacionih algoritama.

Uobičajeno pitanje koje postavljaju istraživači u mnogim oblastima je kako organizovati posmatrane podatke u vizuelne strukture, tj. proširiti taksonomije.

Prema savremenom sistemu prihvaćenom u biologiji, čovjek pripada primatima, sisarima, amniotima, kralježnjacima i životinjama.

Imajte na umu da u ovoj klasifikaciji, što je viši nivo agregacije, to je manje sličnosti između članova odgovarajuće klase.

Čovjek ima više sličnosti s drugim primatima (tj. majmunima) nego sa "udaljenim" članovima porodice sisara (tj. psima) i tako dalje.

Imajte na umu da se prethodna diskusija odnosi na algoritme za grupisanje, ali ne spominje ništa o testiranju statističke značajnosti.

U stvari, klaster analiza nije toliko obična statistička metoda koliko „skup“ različitih algoritama za „distribuciju objekata u klastere“.

Postoji stajalište da se, za razliku od mnogih drugih statističkih procedura, metode klaster analize koriste u većini slučajeva kada nemate nijednu apriornu hipotezu o klasama, ali ste još uvijek u deskriptivnoj fazi istraživanja.

Pažnja!

Treba shvatiti da klaster analiza određuje "najvažniju odluku".

Stoga, testiranje statističke značajnosti ovdje nije stvarno primjenjivo, čak ni u slučajevima kada su p-nivoi poznati (kao, na primjer, u metodi K-means).

Tehnika grupisanja koristi se u raznim oblastima. Hartigan (1975) je dao odličan pregled mnogih objavljenih studija koje sadrže rezultate dobijene metodama klaster analize.

Na primjer, u području medicine, grupisanje bolesti, liječenje bolesti ili simptoma bolesti dovodi do široko korištenih taksonomija.

U polju psihijatrije, ispravna dijagnoza klastera simptoma kao što su paranoja, šizofrenija, itd. je ključna za uspješnu terapiju. U arheologiji, koristeći klaster analizu, istraživači pokušavaju uspostaviti taksonomije kamenog oruđa, pogrebnih predmeta itd.

Postoje široke primjene klaster analize u marketinškim istraživanjima. Općenito, kad god je potrebno klasificirati "gorove" informacija u grupe pogodne za dalju obradu, klaster analiza se pokazuje kao vrlo korisna i efikasna.

Grupiranje stabala

Primjer u odjeljku Primarna svrha objašnjava svrhu algoritma spajanja (klastera stabla).

Svrha ovog algoritma je da kombinuje objekte (na primjer, životinje) u dovoljno velike klastere koristeći neku mjeru sličnosti ili udaljenosti između objekata. Tipičan rezultat takvog grupisanja je hijerarhijsko stablo.

Razmotrite horizontalni dijagram stabla. Dijagram počinje sa svakim objektom u klasi (na lijevoj strani dijagrama).

Sada zamislite da postepeno (u vrlo malim koracima) "slabite" svoj kriterij za to koji su objekti jedinstveni, a koji nisu.

Drugim riječima, snižavate prag vezan za odluku o kombiniranju dva ili više objekata u jedan klaster.

Kao rezultat, povezujete sve više i više objekata zajedno i agregirate (kombinujete) sve više i više klastera sve različitih elemenata.

Konačno, u posljednjem koraku, svi objekti se spajaju. Na ovim grafikonima, horizontalne ose predstavljaju udaljenost spajanja (u vertikalnim dendrogramima, vertikalne ose predstavljaju udaljenost spajanja).

Dakle, za svaki čvor na grafu (gdje se formira novi klaster), možete vidjeti količinu udaljenosti za koju su odgovarajući elementi povezani u novi pojedinačni klaster.

Kada podaci imaju jasnu "strukturu" u smislu klastera objekata koji su međusobno slični, tada će se ova struktura vjerovatno odraziti u hijerarhijskom stablu kroz različite grane.

Kao rezultat uspješne analize metodom spajanja, postaje moguće otkriti klastere (grane) i interpretirati ih.

Metoda ujedinjenja ili klastera stabla koristi se u formiranju klastera različitosti ili udaljenosti između objekata. Ove udaljenosti se mogu definirati u jednodimenzionalnom ili višedimenzionalnom prostoru.

Na primjer, ako morate grupirati vrste hrane u kafiću, možete uzeti u obzir broj kalorija sadržanih u njemu, cijenu, subjektivnu procjenu ukusa itd.

Najdirektniji način za izračunavanje udaljenosti između objekata u višedimenzionalnom prostoru je izračunavanje euklidskih udaljenosti.

Ako imate 2D ili 3D prostor, onda je ova mjera stvarna geometrijska udaljenost između objekata u prostoru (kao da su udaljenosti između objekata mjerene mjernom trakom).

Međutim, algoritam za objedinjavanje ne "briga" o tome da li su udaljenosti "predviđene" za to stvarne ili neke druge izvedene mjere udaljenosti, što je istraživaču značajnije; a izazov za istraživače je odabrati pravu metodu za specifične primjene.

Euklidska udaljenost.Čini se da je ovo najčešći tip udaljenosti. To je jednostavno geometrijska udaljenost u višedimenzionalnom prostoru i izračunava se na sljedeći način:

Imajte na umu da se Euklidska udaljenost (i njen kvadrat) izračunavaju iz originalnih podataka, a ne iz standardiziranih podataka.

Ovo je uobičajeni način izračunavanja, koji ima određene prednosti (na primjer, udaljenost između dva objekta se ne mijenja kada se u analizu uvede novi objekt, koji se može pokazati kao outlier).

Pažnja!

Međutim, na udaljenosti mogu uvelike utjecati razlike između osa iz kojih se izračunavaju udaljenosti. Na primjer, ako se jedna od osi mjeri u centimetrima, a zatim je pretvorite u milimetre (množenjem vrijednosti sa 10), tada će konačna euklidska udaljenost (ili kvadrat euklidske udaljenosti) izračunata iz koordinata dramatično se mijenjaju i, kao rezultat, rezultati klaster analize mogu biti vrlo različiti od prethodnih.

Kvadrat euklidske udaljenosti. Ponekad ćete možda htjeti kvadrature standardne euklidske udaljenosti da biste dali veću težinu udaljenijim objektima.

Ova udaljenost se izračunava na sljedeći način:

Udaljenost od gradskog bloka (udaljenost Manhattana). Ova udaljenost je jednostavno prosjek razlika u koordinatama.

U većini slučajeva, ova mjera udaljenosti dovodi do istih rezultata kao i za uobičajenu Euklidovu udaljenost.

Međutim, imajte na umu da se za ovu mjeru smanjuje utjecaj pojedinačnih velikih razlika (odstupanja) (jer nisu na kvadrat). Udaljenost Manhattana se izračunava pomoću formule:

Chebyshev distance. Ova udaljenost može biti korisna kada se želi definirati dva objekta kao "različita" ako se razlikuju u bilo kojoj koordinati (bilo kojoj jednoj dimenziji). Čebiševljeva udaljenost se izračunava po formuli:

Udaljenost snage. Ponekad se želi progresivno povećavati ili smanjivati težinu koja se odnosi na dimenziju za koju su odgovarajući objekti vrlo različiti.

To se može postići korištenjem udaljenosti po stepenu. Udaljenost snage se izračunava po formuli:

gdje su r i p korisnički definirani parametri. Nekoliko primjera proračuna može pokazati kako ova mjera "funkcioniše".

Parametar p je odgovoran za postepeno ponderisanje razlika u pojedinačnim koordinatama, parametar r je odgovoran za progresivno ponderisanje velikih udaljenosti između objekata. Ako su oba parametra - r i p, jednaka dva, tada se ta udaljenost poklapa s euklidskom udaljenosti.

Procenat neslaganja. Ova mjera se koristi kada su podaci kategorični. Ova udaljenost se izračunava po formuli:

Pravila udruženja ili udruženja

U prvom koraku, kada je svaki objekt zaseban klaster, udaljenosti između ovih objekata određuju se odabranom mjerom.

Međutim, kada je više objekata povezano, postavlja se pitanje kako odrediti udaljenosti između klastera?

Drugim riječima, potrebno vam je pravilo spajanja ili povezivanja za dva klastera. Ovdje postoje različite mogućnosti: na primjer, možete povezati dva klastera zajedno kada su bilo koja dva objekta u dva klastera bliža jedan drugom od odgovarajuće udaljenosti veze.

Drugim riječima, koristite "pravilo najbližeg susjeda" da odredite udaljenost između klastera; ova metoda se naziva metodom jedne veze.

Ovo pravilo gradi "vlaknaste" klastere, tj. klasteri "povezani zajedno" samo pojedinačnim elementima koji su bliži jedan drugom od ostalih.

Alternativno, možete koristiti susjede u klasterima koji su najudaljeniji jedan od drugog od svih ostalih parova karakteristika. Ova metoda se zove metoda pune veze.

Postoje i mnoge druge metode za spajanje klastera, slične onima o kojima se raspravljalo.

Jedna veza (metoda najbližeg susjeda). Kao što je gore opisano, u ovoj metodi, udaljenost između dva klastera određena je rastojanjem između dva najbliža objekta (najbližih susjeda) u različitim klasterima.

Ovo pravilo mora, na neki način, nizati objekte zajedno kako bi formirali klastere, a rezultirajući klasteri imaju tendenciju da budu predstavljeni dugim "stringovima".

Potpuna veza (metoda najudaljenijih susjeda). U ovoj metodi, udaljenosti između klastera su definirane kao najveća udaljenost između bilo koja dva objekta u različitim klasterima (tj. "najudaljeniji susjedi").

Neponderisana srednja vrednost u paru. U ovoj metodi, udaljenost između dva različita klastera izračunava se kao prosječna udaljenost između svih parova objekata u njima.

Metoda je efikasna kada objekti zapravo formiraju različite "šume", ali jednako dobro radi i u slučajevima proširenih ("lančanog" tipa) klastera.

Imajte na umu da u svojoj knjizi Sneath i Sokal (1973) uvode skraćenicu UPGMA koja označava ovu metodu kao metodu neponderisane grupe parova koristeći aritmetičke proseke.

Ponderisana srednja vrednost u parovima. Metoda je identična metodi neponderisanog prosjeka u paru, osim što se veličina odgovarajućih klastera (tj. broj objekata koje sadrže) koristi kao težinski faktor u proračunima.

Stoga predloženu metodu treba koristiti (a ne prethodni) kada se pretpostavljaju nejednake veličine klastera.

Sneath i Sokal (1973) uvode skraćenicu WPGMA koja označava ovu metodu kao metodu ponderisane grupe parova koristeći aritmetičke prosjeke.

Neponderirana metoda centroida. U ovoj metodi, udaljenost između dva klastera se definira kao udaljenost između njihovih centara gravitacije.

Pažnja!

Sneath i Sokal (1973) koriste akronim UPGMC kako bi označili ovu metodu kao metodu neponderisane grupe parova koristeći prosjek centroida.

Metoda ponderisanog centroida (medijan). Ova metoda je identična prethodnoj, osim što se u proračunima koriste ponderi kako bi se uzela u obzir razlika između veličina klastera (tj. broj objekata u njima).

Stoga, ako postoje (ili se sumnja) značajne razlike u veličinama klastera, ova metoda je poželjnija od prethodne.

Sneath i Sokal (1973) su koristili skraćenicu WPGMC kako bi je nazvali metodom ponderisane grupe parova koristeći prosjek centroida.

Ward metoda. Ova metoda se razlikuje od svih ostalih metoda jer koristi ANOVA metode za procjenu udaljenosti između klastera.

Metoda minimizira zbir kvadrata (SS) za bilo koja dva (hipotetička) klastera koja se mogu formirati u svakom koraku.

Detalji se mogu naći u Ward (1963). Općenito se čini da je metoda vrlo efikasna, ali ima tendenciju stvaranja malih klastera.

Ranije se o ovoj metodi raspravljalo u smislu "objekata" koji bi trebali biti grupirani. U svim drugim vrstama analize, pitanje od interesa za istraživača obično se izražava u vidu zapažanja ili varijabli.

Ispostavilo se da grupisanje, kako prema opservacijama tako i prema varijablama, može dovesti do prilično zanimljivih rezultata.

Na primjer, zamislite da medicinski istraživač prikuplja podatke o različitim karakteristikama (varijable) stanja (opažanja) pacijenata sa srčanim oboljenjima.

Istraživač može htjeti grupirati opservacije (pacijenata) kako bi identificirao grupe pacijenata sa sličnim simptomima.

U isto vrijeme, istraživač će možda htjeti grupirati varijable kako bi identificirao klastere varijabli koje su povezane sa sličnim fizičkim stanjem.e

Nakon ove rasprave o tome da li grupirati opažanja ili varijable, moglo bi se zapitati, zašto ne grupirati u oba smjera?

Modul Cluster Analysis sadrži efikasnu dvosmjernu proceduru spajanja koja radi upravo to.

Međutim, dvosmjerno udruživanje se koristi (relativno rijetko) u okolnostima u kojima se očekuje da i zapažanja i varijable istovremeno doprinose otkrivanju značajnih klastera.

Dakle, vraćajući se na prethodni primjer, možemo pretpostaviti da medicinski istraživač treba da identifikuje klastere pacijenata koji su slični u odnosu na određene klastere karakteristika fizičkog stanja.

Poteškoće u tumačenju dobijenih rezultata proizilaze iz činjenice da sličnosti između različitih klastera mogu proizaći iz (ili biti uzrok) neke razlike u podskupovima varijabli.

Stoga su rezultirajući klasteri inherentno heterogeni. Možda u početku izgleda pomalo maglovito; zaista, u poređenju s drugim opisanim metodama klaster analize, dvosmjerno udruživanje je vjerovatno najmanje korištena metoda.

Međutim, neki istraživači vjeruju da nudi moćan alat za istraživačku analizu podataka (za više informacija pogledajte Hartiganov opis ove metode (Hartigan, 1975)).

K znači metoda

Ova metoda grupiranja značajno se razlikuje od aglomerativnih metoda kao što su Union (klasterizacija stabala) i Dvosmjerna unija. Pretpostavimo da već imate hipoteze o broju klastera (prema posmatranju ili promenljivoj).

Možete reći sistemu da formira tačno tri klastera tako da se razlikuju što je više moguće.

To je upravo tip problema koji K-Means algoritam rješava. Općenito, K-means metoda gradi tačno K različitih klastera razmaknutih što je više moguće.

U primjeru fizičkog stanja, medicinski istraživač može imati "predosjećaj" iz svog kliničkog iskustva da njegovi pacijenti općenito spadaju u tri različite kategorije.

Pažnja!

Ako je tako, onda bi sredstva različitih mjera fizičkih parametara za svaki klaster pružila kvantitativni način predstavljanja hipoteza istraživača (npr. pacijenti u klasteru 1 imaju visoki parametar 1, niži parametar 2, itd.).

Sa računske tačke gledišta, ovu metodu možete zamisliti kao analizu varijanse "obrnuto". Program počinje sa K nasumično odabranih klastera, a zatim im mijenja pripadnost objekata kako bi:

minimizirati varijabilnost unutar klastera,
maksimizirati varijabilnost između klastera.

Ova metoda je slična reverznoj analizi varijanse (ANOVA) po tome što test značajnosti u ANOVA upoređuje varijabilnost između grupa i unutar grupe u testiranju hipoteze da se srednje vrijednosti grupe razlikuju jedna od druge.

U grupiranju K-means, program premešta objekte (tj. zapažanja) iz jedne grupe (klastera) u drugu kako bi se dobio najznačajniji rezultat pri izvođenju analize varijanse (ANOVA).

Obično, kada se dobiju rezultati analize klastera K-srednje vrednosti, može se izračunati srednje vrednosti za svaki klaster za svaku dimenziju kako bi se procenilo kako se klasteri međusobno razlikuju.

U idealnom slučaju, trebali biste dobiti vrlo različita sredstva za većinu, ako ne i za sva mjerenja koja se koriste u analizi.

Izvor: http://www.biometrica.tomsk.ru/textbook/modules/stcluan.html

Klasifikacija objekata prema njihovim karakteristikama

Klaster analiza (klaster analiza) - skup višedimenzionalnih statističkih metoda za klasifikaciju objekata prema njihovim karakteristikama, podjelu skupa objekata u homogene grupe koje su bliske po kriteriju definiranja, odabir objekata određene grupe.

Klaster je grupa objekata identifikovanih kao rezultat analize klastera na osnovu date mere sličnosti ili razlike između objekata.

Predmet su specifični predmeti proučavanja koje je potrebno klasifikovati. Objekti u klasifikaciji su, po pravilu, zapažanja. Na primjer, potrošači proizvoda, zemlje ili regije, proizvodi itd.

Iako je moguće izvršiti klaster analizu po varijablama. Klasifikacija objekata u multidimenzionalnoj klaster analizi odvija se prema više kriterijuma istovremeno.

To mogu biti i kvantitativne i kategorijalne varijable, u zavisnosti od metode klaster analize. Dakle, glavni cilj klaster analize je pronaći grupe sličnih objekata u uzorku.

Skup multidimenzionalnih statističkih metoda klasterske analize može se podijeliti na hijerarhijske metode (aglomerativne i razdjelne) i nehijerarhijske (metoda k-srednjih vrijednosti, dvostepena klasterska analiza).

Međutim, ne postoji opšteprihvaćena klasifikacija metoda, a ponekad metode klaster analize uključuju i metode za konstruisanje stabala odlučivanja, neuronske mreže, diskriminantnu analizu i logističku regresiju.

Opseg klaster analize, zbog svoje svestranosti, veoma je širok. Klaster analiza se koristi u ekonomiji, marketingu, arheologiji, medicini, psihologiji, hemiji, biologiji, javnoj upravi, filologiji, antropologiji, sociologiji i drugim oblastima.

Evo nekoliko primjera primjene klaster analize:

medicina - klasifikacija bolesti, njihovih simptoma, metoda liječenja, klasifikacija grupa pacijenata;
marketing - zadaci optimizacije proizvodne linije kompanije, segmentiranje tržišta po grupama robe ili potrošača, identifikacija potencijalnog potrošača;
sociologija - podjela ispitanika u homogene grupe;
psihijatrija - tačna dijagnoza grupa simptoma je ključna za uspješnu terapiju;
biologija - klasifikacija organizama po grupama;
ekonomija - klasifikacija subjekata Ruske Federacije prema investicijskoj privlačnosti.

Izvor: http://www.statmethods.ru/konsalting/statistics-methody/121-klasternyj-analyz.html

Opće informacije o klaster analizi

Klaster analiza uključuje skup različitih klasifikacionih algoritama. Uobičajeno pitanje koje postavljaju istraživači u mnogim oblastima je kako organizirati promatrane podatke u vizualne strukture.

Na primjer, biolozi imaju za cilj da razdvoje životinje na različite vrste kako bi smisleno opisali razlike među njima.

Zadatak klaster analize je podijeliti početni skup objekata u grupe sličnih, bliskih objekata. Ove grupe se nazivaju klasteri.

Drugim riječima, klaster analiza je jedan od načina klasifikacije objekata prema njihovim karakteristikama. Poželjno je da rezultati klasifikacije imaju smislenu interpretaciju.

Rezultati dobijeni metodama klaster analize koriste se u različitim oblastima. U marketingu, to je segmentacija konkurenata i potrošača.

U psihijatriji je tačna dijagnoza simptoma kao što su paranoja, šizofrenija itd. ključna za uspješnu terapiju.

U menadžmentu je važna klasifikacija dobavljača, identifikacija sličnih proizvodnih situacija u kojima dolazi do braka. U sociologiji je podjela ispitanika na homogene grupe. U portfolio ulaganju važno je grupirati vrijednosne papire prema njihovoj sličnosti u trendu prinosa kako bi se, na osnovu dobijenih informacija o berzi, sastavio optimalan investicijski portfolio koji omogućava maksimiziranje povrata na ulaganja za dati stepen rizika. .

Generalno, kad god je potrebno klasifikovati veliku količinu informacija ove vrste i predstaviti ih u obliku pogodnom za dalju obradu, klaster analiza se pokazuje kao veoma korisna i efikasna.

Klaster analiza omogućava razmatranje prilično velike količine informacija i uvelike komprimiranje velikih nizova socio-ekonomskih informacija, čineći ih kompaktnim i vizualnim.

Pažnja!

Klaster analiza je od velikog značaja u odnosu na skupove vremenskih serija koje karakterišu ekonomski razvoj (na primer, opšti ekonomski i robni uslovi).

Ovdje je moguće izdvojiti periode kada su vrijednosti odgovarajućih pokazatelja bile prilično bliske, kao i odrediti grupe vremenskih serija čija je dinamika najsličnija.

U problemima socio-ekonomskog predviđanja, veoma je obećavajuće kombinovanje klaster analize sa drugim kvantitativnim metodama (na primer, sa regresionom analizom).

Prednosti i nedostaci

Klaster analiza omogućava objektivnu klasifikaciju svih objekata koje karakteriše niz karakteristika. Postoji niz prednosti koje se mogu izvući iz ovoga:

Nastali klasteri mogu se interpretirati, odnosno opisati kakve grupe zapravo postoje.
Pojedinačni klasteri mogu biti odbačeni. Ovo je korisno u slučajevima kada su napravljene određene greške u skupu podataka, zbog čega vrijednosti indikatora za pojedinačne objekte naglo odstupaju. Prilikom primjene klaster analize, takvi objekti spadaju u poseban klaster.
Za dalju analizu mogu se odabrati samo oni klasteri koji imaju karakteristike od interesa.

Kao i svaka druga metoda, klaster analiza ima određene nedostatke i ograničenja. Posebno, sastav i broj klastera ovisi o odabranim kriterijima particioniranja.

Prilikom svođenja početnog niza podataka na kompaktniji oblik može doći do određenih izobličenja, a mogu se izgubiti i pojedinačne karakteristike pojedinačnih objekata zbog njihove zamjene karakteristikama generaliziranih vrijednosti parametara klastera.

Metode

Trenutno je poznato više od stotinu različitih algoritama za grupisanje. Njihova raznolikost se objašnjava ne samo različitim računskim metodama, već i različitim konceptima koji su u osnovi klasteriranja.

Paket Statistica implementira sljedeće metode klasteriranja.

Hijerarhijski algoritmi - grupiranje stabala. Hijerarhijski algoritmi su zasnovani na ideji sekvencijalnog grupisanja. U početnom koraku, svaki objekat se smatra zasebnim klasterom. U sljedećem koraku, neki od klastera koji su najbliži jedan drugom će biti spojeni u poseban klaster.
K-means metoda. Ova metoda je najčešće korištena. Spada u grupu tzv. referentnih metoda klaster analize. Broj klastera K postavlja korisnik.
Dvosmjerna asocijacija. Kada se koristi ova metoda, grupisanje se vrši istovremeno i po varijablama (kolone) i po rezultatima posmatranja (redovi).

Dvosmjerna procedura spajanja se izvodi kada se može očekivati da će simultano grupisanje na varijablama i opservacijama dati značajne rezultate.

Rezultati postupka su deskriptivna statistika o varijablama i slučajevima, kao i dvodimenzionalni dijagram boja na kojem su vrijednosti podataka označene bojama.

Po distribuciji boja možete dobiti ideju o homogenim grupama.

Normalizacija varijabli

Podjela početnog skupa objekata u klastere povezana je s proračunom udaljenosti između objekata i izborom objekata, među kojima je udaljenost najmanja od svih mogućih.

Najčešće korištena je euklidska (geometrijska) udaljenost poznata svima nama. Ova metrika odgovara intuitivnim idejama o blizini objekata u prostoru (kao da su udaljenosti između objekata mjerene mjernom trakom).

Ali za datu metriku, na udaljenost između objekata mogu snažno utjecati promjene skala (mjernih jedinica). Na primjer, ako se jedna od karakteristika izmjeri u milimetrima, a zatim se njena vrijednost pretvori u centimetre, euklidska udaljenost između objekata će se dramatično promijeniti. To će dovesti do činjenice da se rezultati klaster analize mogu značajno razlikovati od prethodnih.

Ako se varijable mjere u različitim mjernim jedinicama, onda je potrebna njihova preliminarna normalizacija, odnosno transformacija početnih podataka, čime se pretvaraju u bezdimenzionalne veličine.

Normalizacija snažno iskrivljuje geometriju originalnog prostora, što može promijeniti rezultate grupiranja

U paketu Statistica, svaka varijabla x je normalizirana prema formuli:

Da biste to uradili, kliknite desnim tasterom miša na ime varijable i izaberite redosled naredbi iz menija koji se otvori: Popuni/ Standardiziraj blok/ Standardiziraj kolone. Vrijednosti normalizirane varijable će postati jednake nuli, a varijanse će postati jednake jedan.

K-means metoda u Statistici

Metoda K-means dijeli skup objekata na određeni broj K različitih klastera koji se nalaze na najvećoj mogućoj udaljenosti jedan od drugog.

Tipično, kada se dobiju rezultati analize klastera K-srednje vrednosti, može se izračunati prosječne vrednosti za svaki klaster za svaku dimenziju kako bi se procenilo kako se klasteri međusobno razlikuju.

U idealnom slučaju, trebali biste dobiti vrlo različita sredstva za većinu mjerenja koja se koriste u analizi.

Vrijednosti F-statistike dobivene za svaku dimenziju su još jedan pokazatelj koliko dobro odgovarajuća dimenzija razlikuje klastere.

Kao primjer, razmotrite rezultate ankete 17 zaposlenih u jednom preduzeću o zadovoljstvu indikatorima kvaliteta karijere. Tabela sadrži odgovore na pitanja upitnika na desetostepenoj skali (1 je minimalna ocjena, 10 je maksimalna).

Imena varijabli odgovaraju odgovorima na sljedeća pitanja:

SLT - kombinacija ličnih ciljeva i ciljeva organizacije;
OSO - osećaj pravičnosti u platama;
TBD - teritorijalna blizina kuće;
PEW - osjećaj ekonomskog blagostanja;
CR - razvoj karijere;
ZhSR - želja za promjenom posla;
OSB je osjećaj društvenog blagostanja.

Koristeći ove podatke, potrebno je zaposlenike podijeliti u grupe i odabrati najefikasnije poluge kontrole za svaku od njih.

Istovremeno, razlike između grupa treba da budu očigledne, a unutar grupe ispitanici treba da budu što sličniji.

Do danas većina socioloških istraživanja daje samo procenat glasova: uzima se u obzir glavni broj pozitivnih odgovora, odnosno procenat onih koji su nezadovoljni, ali se ovo pitanje ne razmatra sistematski.

Najčešće anketa ne pokazuje trendove situacije. U nekim slučajevima potrebno je brojati ne broj ljudi koji su “za” ili “protiv”, već udaljenost, odnosno mjeru sličnosti, odnosno odrediti grupe ljudi koji misle o istom.

Postupci klaster analize mogu se koristiti za identifikaciju, na osnovu podataka ankete, nekih stvarno postojećih odnosa karakteristika i generisanje njihove tipologije na osnovu toga.

Pažnja!

Prisustvo bilo koje apriorne hipoteze sociologa pri radu sa procedurama klaster analize nije neophodan uslov.

U programu Statistica klaster analiza se izvodi na sljedeći način.

Prilikom odabira broja klastera vodite se sljedećim: broj klastera, ako je moguće, ne smije biti prevelik.

Udaljenost na kojoj su objekti datog klastera spojeni trebala bi, ako je moguće, biti mnogo manja od udaljenosti na kojoj se nešto drugo pridruži ovom klasteru.

Prilikom odabira broja klastera najčešće postoji nekoliko ispravnih rješenja u isto vrijeme.

Zanima nas, na primjer, kako su odgovori na pitanja upitnika u korelaciji sa običnim zaposlenima i menadžmentom preduzeća. Stoga biramo K=2. Za dalju segmentaciju, možete povećati broj klastera.

izaberite opažanja sa maksimalnom udaljenosti između centara klastera;
sortiranje udaljenosti i odabir opažanja u redovnim intervalima (podrazumevana postavka);
uzmite prve centre za posmatranje i pričvrstite ostale objekte na njih.

Opcija 1 je pogodna za naše potrebe.

Mnogi algoritmi za grupisanje često „nametnu“ strukturu koja nije inherentna podacima i dezorijentišu istraživača. Stoga je izuzetno potrebno primijeniti nekoliko algoritama klaster analize i izvući zaključke na osnovu opće procjene rezultata algoritama.

Rezultate analize možete pogledati u dijaloškom okviru koji se pojavljuje:

Ako odaberete karticu Graf srednjih vrijednosti, iscrtat će se grafikon koordinata centara klastera:

Svaka isprekidana linija na ovom grafikonu odgovara jednom od klastera. Svaka podjela horizontalne ose grafa odgovara jednoj od varijabli uključenih u analizu.

Vertikalna os odgovara prosječnim vrijednostima varijabli za objekte uključene u svaki od klastera.

Može se primijetiti da postoje značajne razlike u stavu dvije grupe ljudi prema uslužnoj karijeri po gotovo svim pitanjima. Samo u jednom pitanju postoji potpuna jednoglasnost – u smislu društvenog blagostanja (OSB), odnosno njegovog nedostatka (2,5 poena od 10).

Može se pretpostaviti da klaster 1 predstavlja radnike, a klaster 2 menadžment. Menadžeri su zadovoljniji razvojem karijere (CR), kombinacijom ličnih i organizacionih ciljeva (SOL).

Imaju viši osjećaj ekonomskog blagostanja (SEW) i osjećaj pravednosti plata (SWA).

Oni su manje zabrinuti zbog blizine kuće nego radnici, vjerovatno zbog manje problema sa transportom. Takođe, menadžeri imaju manje želje za promjenom posla (JSR).

Uprkos činjenici da su radnici podijeljeni u dvije kategorije, na većinu pitanja daju relativno iste odgovore. Drugim riječima, ako nešto ne odgovara opštoj grupi zaposlenih, isto ne odgovara višem menadžmentu i obrnuto.

Usklađivanje grafova nam omogućava da zaključimo da se dobrobit jedne grupe odražava u dobrobiti druge.

Klaster 1 nije zadovoljan teritorijalnom blizinom kuće. Ova grupa je glavni deo radnika koji uglavnom dolaze u preduzeće iz različitih delova grada.

Stoga je moguće ponuditi najvišem rukovodstvu da dio dobiti izdvoji za izgradnju stambenih objekata za zaposlene u preduzeću.

Značajne razlike se vide u stavu dvije grupe ljudi prema uslužnoj karijeri. Oni zaposleni koji su zadovoljni razvojem karijere, koji imaju visoku podudarnost ličnih ciljeva i ciljeva organizacije, nemaju želju za promjenom posla i osjećaju zadovoljstvo rezultatima svog rada.

Nasuprot tome, zaposleni koji žele promijeniti posao i koji su nezadovoljni rezultatima svog rada nisu zadovoljni navedenim pokazateljima. Viši menadžment treba da obrati posebnu pažnju na trenutnu situaciju.

Rezultati analize varijanse za svaki atribut se prikazuju pritiskom na dugme Analiza varijanse.

Prikazuju se zbroji kvadrata odstupanja objekata od centara klastera (SS Within) i zbira kvadrata odstupanja između centara klastera (SS Between), vrednosti F-statistike i p nivoa značajnosti.

Pažnja!

Za naš primjer, nivoi značajnosti za dvije varijable su prilično veliki, što se objašnjava malim brojem zapažanja. U punoj verziji studije, koja se nalazi u radu, hipoteze o jednakosti sredina za klaster centre odbacuju se na nivoima značajnosti manjim od 0,01.

Dugme Sačuvaj klasifikacije i udaljenosti prikazuje brojeve objekata uključenih u svaki klaster i udaljenosti objekata do centra svakog klastera.

Tabela prikazuje brojeve slučajeva (CASE_NO) koji čine klastere sa brojevima KLUSTER i udaljenosti od centra svakog klastera (DISTANCE).

Informacije o objektima koji pripadaju klasterima mogu se zapisati u datoteku i koristiti u daljoj analizi. U ovom primeru, poređenje rezultata dobijenih sa upitnicima pokazalo je da se klaster 1 sastoji uglavnom od običnih radnika, a klaster 2 - od menadžera.

Dakle, može se vidjeti da se prilikom obrade rezultata ankete klaster analiza pokazala kao moćna metoda koja omogućava izvlačenje zaključaka do kojih se ne može doći konstruiranjem histograma prosjeka ili izračunavanjem procenta onih koji su zadovoljni različitim pokazateljima. kvalitetu radnog života.

Grupiranje stabala je primjer hijerarhijskog algoritma, čiji je princip da se u klaster sekvencijalno grupišu prvo najbliži, a zatim sve udaljeniji elementi.

Većina ovih algoritama polazi od matrice sličnosti (udaljenosti), a svaki pojedinačni element se u početku smatra zasebnim klasterom.

Nakon učitavanja modula za analizu klastera i odabira Pridruživanje (klasterizacija stabla), možete promijeniti sljedeće parametre u prozoru za unos parametara klasteriranja:

Početni podaci (Input). Mogu biti u obliku matrice proučavanih podataka (Raw data) iu obliku matrice udaljenosti (Distance matrix).
Grupiranje (Cluster) zapažanja (Slučajevi (sirovo)) ili varijabli (Varijabla (kolone)), opisivanje stanja objekta.
Mjere udaljenosti. Ovdje možete odabrati sljedeće mjere: Euklidske udaljenosti, Euklidske udaljenosti na kvadrat, udaljenost gradskog bloka (Menhetn), Čebičevljeva metrika udaljenosti, Snaga...), procenat neslaganja (Procenat neslaganja).
Metoda grupisanja (pravilo spajanja (povezivanja)). Ovdje su moguće sljedeće opcije: Pojedinačna veza, Potpuna veza, Neponderisani prosjek grupe parova, Ponderirani prosjek grupe parova, Neponderirani centar grupe parova, Ponderirani centar grupe parova (medijan), Wardova metoda.

Kao rezultat grupiranja, gradi se horizontalni ili vertikalni dendrogram - graf na kojem se određuju udaljenosti između objekata i klastera kada se oni uzastopno kombiniraju.

Struktura stabla grafa vam omogućava da definišete klastere u zavisnosti od izabranog praga - date udaljenosti između klastera.

Osim toga, prikazuje se matrica udaljenosti između originalnih objekata (Matrica udaljenosti); srednje i standardne devijacije za svaki izvorni objekt (Distiptive statistics).

Za razmatrani primjer, izvršit ćemo klaster analizu varijabli sa zadanim postavkama. Rezultirajući dendrogram je prikazan na slici.

Vertikalna os dendrograma prikazuje udaljenosti između objekata i između objekata i klastera. Dakle, rastojanje između varijabli SEB i OSD je jednako pet. Ove varijable u prvom koraku se kombinuju u jedan klaster.

Horizontalni segmenti dendrograma su nacrtani na nivoima koji odgovaraju graničnim udaljenostima odabranim za dati korak grupisanja.

Iz grafikona se može vidjeti da pitanje „želja za promjenom posla“ (JSR) čini poseban klaster. Općenito, želja za odlaganjem bilo gdje posjećuje sve podjednako. Nadalje, poseban klaster je pitanje teritorijalne blizine domu (LHB).

Po važnosti je na drugom mjestu, što potvrđuje zaključak o potrebi stambene izgradnje, donesen prema rezultatima istraživanja metodom K-srednje vrijednosti.

Kombinovani su osjećaji ekonomskog blagostanja (PEW) i pravednosti plaća (PWA) – ovo je blok ekonomskih pitanja. Napredovanje u karijeri (CR) i kombinacija ličnih i organizacionih ciljeva (COL) su takođe kombinovani.

Druge metode grupisanja, kao i izbor drugih tipova udaljenosti, ne dovode do značajnije promjene u dendrogramu.

Rezultati:

Klaster analiza je moćan alat za istraživačku analizu podataka i statistička istraživanja u bilo kojoj predmetnoj oblasti.
Program Statistica implementira i hijerarhijske i strukturne metode klaster analize. Prednosti ovog statističkog paketa su zbog njegovih grafičkih mogućnosti. Dati su dvodimenzionalni i trodimenzionalni grafički prikazi dobijenih klastera u prostoru proučavanih varijabli, kao i rezultati hijerarhijske procedure grupisanja objekata.
Potrebno je primijeniti nekoliko algoritama klaster analize i izvući zaključke na osnovu opće procjene rezultata algoritama.
Klaster analiza se može smatrati uspješnom ako se izvodi na različite načine, ako se uporede rezultati i pronađu zajednički obrasci, te se pronađu stabilni klasteri bez obzira na metodu klasteriranja.
Klaster analiza vam omogućava da identifikujete problematične situacije i odredite načine za njihovo rešavanje. Stoga se ova metoda neparametarske statistike može smatrati sastavnim dijelom analize sistema.

Vrste unosa

Indikativni opis objekata. Svaki objekat je opisan skupom njegovih karakteristika, tzv znakovi. Karakteristike mogu biti numeričke ili nenumeričke.
Matrica udaljenosti između objekata. Svaki objekt je opisan udaljenostima do svih ostalih objekata u uzorku za obuku.

Ciljevi grupisanja

Razumijevanje podataka identificiranjem strukture klastera. Podjela uzorka na grupe sličnih objekata omogućava pojednostavljenje dalje obrade podataka i donošenja odluka primjenom vlastite metode analize na svaki klaster (strategija „zavadi pa vladaj“).
Kompresija podataka. Ako je početni uzorak pretjerano velik, onda se može smanjiti, ostavljajući po jednog od najtipičnijih predstavnika iz svakog klastera.
detekcija noviteta. detekcija noviteta). Odabiru se netipični objekti koji se ne mogu priključiti ni jednom od klastera.

U prvom slučaju pokušavaju smanjiti broj klastera. U drugom slučaju, važnije je osigurati visok stepen sličnosti objekata unutar svakog klastera, a klastera može postojati bilo koji broj. U trećem slučaju, od najvećeg su interesa pojedinačni objekti koji se ne uklapaju ni u jedan od klastera.

Rezultat taksonomije je hijerarhijska struktura nalik stablu. Osim toga, svaki objekt karakterizira nabrajanje svih klastera kojima pripada, obično od velikih do malih.

Klasičan primjer taksonomije zasnovane na sličnosti je binomna nomenklatura živih bića koju je predložio Carl Linnaeus sredinom 18. stoljeća. Slične sistematizacije se grade u mnogim oblastima znanja kako bi se organizovale informacije o velikom broju objekata.

Metode grupisanja

Formalna izjava o problemu grupisanja

Neka je skup objekata, biti skup brojeva (imena, oznaka) klastera. Zadana je funkcija udaljenosti između objekata. Postoji konačan skup objekata za obuku. Potrebno je podijeliti uzorak na podskupove koji se ne preklapaju, tzv klasteri, tako da se svaki klaster sastoji od objekata bliskih po metrici, a objekti različitih klastera se značajno razlikuju. U ovom slučaju, svakom objektu je dodijeljen broj klastera.

Algoritam grupisanja je funkcija koja povezuje bilo koji objekt s brojem klastera. Skup je u nekim slučajevima poznat unaprijed, ali češće je zadatak odrediti optimalan broj klastera, sa stanovišta jednog ili drugog kriterijumi kvaliteta grupisanje.

Književnost

Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Primijenjena statistika: klasifikacija i redukcija dimenzija. - M.: Finansije i statistika, 1989.
Žuravljev Yu. I., Ryazanov V. V., Senko O. V."Priznanje". Matematičke metode. Softverski sistem. Praktične primjene. - M.: Fazis, 2006. ISBN 5-7036-0108-8.
Zagoruiko N. G. Primijenjene metode analize podataka i znanja. - Novosibirsk: IM SO RAN, 1999. ISBN 5-86134-060-9.
Mandel I. D. klaster analiza. - M.: Finansije i statistika, 1988. ISBN 5-279-00050-7.
Šlesinger M., Glavač V. Deset predavanja o statističkom i strukturnom prepoznavanju. - Kijev: Naukova dumka, 2004. ISBN 966-00-0341-2.
Hastie T., Tibširani R., Friedman J. Elementi statističkog učenja. - Springer, 2001. ISBN 0-387-95284-5.
Jain Murty Flynn Grupiranje podataka: pregled. // ACM Comput. Surv. 31 (3) , 1999

Eksterne veze

Na ruskom

www.MachineLearning.ru - profesionalni wiki resurs posvećen mašinskom učenju i rudarenju podataka
S. Nikolenko. Slajdovi predavanja o algoritmima grupisanja

Na engleskom

COMPACT - Uporedni paket za procjenu klastera. Besplatan Matlab paket, 2006.
P. Berkhin, Istraživanje klastering tehnika rudarenja podataka, Accue Software, 2002.
Jain, Murty i Flynn: Grupiranje podataka: pregled, ACM Comp. Surv., 1999.
za drugu prezentaciju hijerarhijskih, k-srednjih i rasplinutih c-sredina pogledajte ovaj uvod u grupisanje. Također ima objašnjenje o mješavini Gaussovih.
David Dowe, Stranica za modeliranje mješavine- ostale veze modela klastera i mešavine.
tutorijal o grupiranju
On-line udžbenik: Teorija informacija, zaključivanje i algoritmi učenja, autora Davida J.C. MacKay uključuje poglavlja o k-means grupisanju, mekom k-means grupisanju i derivacijama uključujući E-M algoritam i varijacioni pogled na E-M algoritam.
"Samoorganizovani gen", tutorijal koji objašnjava grupisanje kroz takmičarsko učenje i samoorganizovane mape.
kernlab - R paket za strojno učenje bazirano na kernelu (uključuje implementaciju spektralnog klasteriranja)
Tutorial - Tutorijal sa uvođenjem algoritama za grupisanje (k-means, fuzzy-c-means, hijerarhijski, mješavina gaussovih) + neke interaktivne demonstracije (java apleti)
Softver za rudarenje podataka - Softver za rudarenje podataka često koristi tehnike klasteriranja.
Java Competitive Learning aplikacija Paket nenadziranih neuronskih mreža za grupisanje. Napisano na Javi. Kompletno sa svim izvornim kodom.

klaster analiza

Većina istraživača sklona je vjerovanju da je po prvi put termin "klaster analiza" (eng. klaster- hrpa, ugrušak, hrpa) predložio je matematičar R. Trion. Nakon toga su se pojavili brojni termini koji se danas smatraju sinonimima za termin "analiza klastera": automatska klasifikacija; botriologija.

Klaster analiza je višedimenzionalna statistička procedura koja prikuplja podatke koji sadrže informacije o uzorku objekata, a zatim sređuje objekte u relativno homogene grupe (klastere) (Q-clustering, ili Q-tehnika, sama klaster analiza). Klaster - grupa elemenata koju karakteriše zajedničko svojstvo, glavni cilj klaster analize je pronalaženje grupa sličnih objekata u uzorku. Spektar primjene klaster analize je vrlo širok: koristi se u arheologiji, medicini, psihologiji, hemiji, biologiji, javnoj upravi, filologiji, antropologiji, marketingu, sociologiji i drugim disciplinama. Međutim, univerzalnost primjene dovela je do pojave velikog broja nekompatibilnih pojmova, metoda i pristupa koji otežavaju jednoznačno korištenje i dosljedno tumačenje klaster analize. Orlov A. I. predlaže razlikovanje na sljedeći način:

Zadaci i uslovi

Klaster analiza izvodi sljedeće glavni ciljevi:

Razvoj tipologije ili klasifikacije.
Istraživanje korisnih konceptualnih shema za grupisanje objekata.
Generisanje hipoteza na osnovu istraživanja podataka.
Testiranje hipoteza ili istraživanje kako bi se utvrdilo da li su tipovi (grupe) identificirani na ovaj ili onaj način zaista prisutni u dostupnim podacima.

Bez obzira na predmet proučavanja, upotreba klaster analize uključuje sljedeći koraci:

Uzorkovanje za grupisanje. Podrazumijeva se da ima smisla grupirati samo kvantitativne podatke.
Definicija skupa varijabli pomoću kojih će se evaluirati objekti u uzorku, odnosno prostor karakteristika.
Izračunavanje vrijednosti jedne ili druge mjere sličnosti (ili razlike) između objekata.
Primjena metode klaster analize za kreiranje grupa sličnih objekata.
Validacija rezultata klaster rješenja.

Klaster analiza predstavlja sljedeće zahtjevi za podacima:

indikatori ne bi trebali korelirati jedan s drugim;
indikatori ne bi trebali biti u suprotnosti sa teorijom mjerenja;
distribucija indikatora treba da bude blizu normalne;
indikatori moraju ispunjavati zahtjev "stabilnosti", što znači odsustvo utjecaja na njihove vrijednosti od strane slučajnih faktora;
uzorak treba da bude homogen, da ne sadrži "izuzetne vrednosti".

Možete pronaći opis dva osnovna zahtjeva za podatke - uniformnost i potpunost:

Homogenost zahtijeva da svi entiteti predstavljeni u tabeli budu iste prirode. Uslov za kompletnost je da skupovi I i J predstavio kompletan opis manifestacija razmatranog fenomena. Ako uzmemo u obzir tabelu u kojoj I je zbirka, i J- skup varijabli koje opisuju ovu populaciju, onda to treba da bude reprezentativan uzorak iz proučavane populacije, i sistem karakteristika J treba da daju zadovoljavajuću vektorsku reprezentaciju pojedinaca i sa stanovišta istraživača.

Ako klaster analizi prethodi faktorska analiza, tada uzorak ne treba „popravljati“ – navedeni zahtjevi se izvršavaju automatski samim postupkom faktorskog modeliranja (postoji još jedna prednost - z-standardizacija bez negativnih posljedica za uzorak; ako provodi se direktno za klaster analizu, može dovesti do smanjenja jasnoće razdvajanja grupa). U suprotnom, uzorak se mora prilagoditi.

Tipologija problema klasteriranja

Vrste unosa

U savremenoj nauci koristi se nekoliko algoritama za obradu ulaznih podataka. Analiza upoređivanjem objekata na osnovu karakteristika (najčešća u biološkim naukama) naziva se Q- vrsta analize, au slučaju poređenja karakteristika, na osnovu objekata - R- vrsta analize. Postoje pokušaji da se koriste hibridni tipovi analize (npr. RQ analiza), ali ova metodologija još nije pravilno razvijena.

Ciljevi grupisanja

Razumijevanje podataka identificiranjem strukture klastera. Podjela uzorka na grupe sličnih objekata omogućava pojednostavljenje dalje obrade podataka i donošenja odluka primjenom vlastite metode analize na svaki klaster (strategija „zavadi pa vladaj“).
Kompresija podataka. Ako je početni uzorak pretjerano velik, onda se može smanjiti, ostavljajući po jednog od najtipičnijih predstavnika iz svakog klastera.
detekcija noviteta. detekcija noviteta). Odabiru se netipični objekti koji se ne mogu priključiti ni jednom od klastera.

U svim ovim slučajevima može se primijeniti hijerarhijsko grupiranje, kada se veliki klasteri dijele na manje, koji se, pak, dijele na još manje, itd. Takvi zadaci se nazivaju taksonomijski zadaci. Rezultat taksonomije je hijerarhijska struktura nalik stablu. Osim toga, svaki objekt karakterizira nabrajanje svih klastera kojima pripada, obično od velikih do malih.

Metode grupisanja

Ne postoji općeprihvaćena klasifikacija metoda klasteriranja, ali se može primijetiti solidan pokušaj V. S. Berikova i G. S. Lbova. Ako generaliziramo različite klasifikacije metoda klasteriranja, možemo razlikovati brojne grupe (neke metode se mogu pripisati nekoliko grupa odjednom, pa se stoga predlaže da se ova tipizacija smatra nekom aproksimacijom stvarnoj klasifikaciji metoda klasteriranja):

Vjerovatni pristup. Pretpostavlja se da svaki predmet koji se razmatra pripada jednoj od k klasa. Neki autori (npr. A. I. Orlov) smatraju da ova grupa uopšte ne pripada grupisanju i protive joj se pod nazivom "diskriminacija", odnosno izbor pripisivanja objekata nekoj od poznatih grupa (uzorci za obuku).
Pristupi zasnovani na sistemima veštačke inteligencije. Vrlo uslovna grupa, jer postoji mnogo AI metoda i metodički su veoma različite.
logičan pristup. Konstrukcija dendrograma se izvodi pomoću stabla odlučivanja.
Teorijski pristup grafovima.
- Algoritmi za grupisanje grafova
Hijerarhijski pristup. Pretpostavlja se prisustvo ugniježđenih grupa (klastera različitog reda). Algoritmi se, pak, dijele na aglomerativne (ujedinjujuće) i razdjelne (razdvajajuće). Prema broju karakteristika, ponekad se razlikuju monotetičke i politetičke metode klasifikacije.
- Hijerarhijsko divizijsko grupiranje ili taksonomija. Problemi grupisanja se razmatraju u kvantitativnoj taksonomiji.
Druge metode. Nije uključeno u prethodne grupe.
- Statistički algoritmi za grupisanje
- Ansambl klastera
- Algoritmi porodice KRAB
- Algoritam zasnovan na metodi prosijavanja
- DBSCAN itd.

Pristupi 4 i 5 se ponekad kombinuju pod nazivom strukturalni ili geometrijski pristup, koji ima formalizovaniji koncept blizine. Unatoč značajnim razlikama između navedenih metoda, sve se oslanjaju na originalne " hipoteza o kompaktnosti»: u prostoru objekata, svi bliski objekti moraju pripadati istom klasteru, a svi različiti objekti, respektivno, moraju biti u različitim klasterima.

Formalna izjava o problemu grupisanja

Grupiranje (učenje bez nadzora) razlikuje se od klasifikacije (učenje pod nadzorom) po tome što oznake originalnih objekata nisu inicijalno postavljene, a sam skup može čak biti nepoznat.

Rješenje problema klasteriranja je u osnovi dvosmisleno, a za to postoji nekoliko razloga (prema brojnim autorima):

ne postoji jedinstveno najbolji kriterijum za kvalitet grupisanja. Poznato je više heurističkih kriterijuma, kao i niz algoritama koji nemaju jasno definisan kriterijum, ali sprovode prilično razumno grupisanje „po konstrukciji“. Svi oni mogu dati različite rezultate. Stoga je za utvrđivanje kvaliteta klasteriranja potreban stručnjak iz predmetne oblasti koji bi mogao ocijeniti smislenost odabira klastera.
broj klastera je obično unapred nepoznat i postavlja se prema nekom subjektivnom kriterijumu. Ovo vrijedi samo za metode diskriminacije, jer se u metodama klasteriranja klasteri odabiru korištenjem formaliziranog pristupa zasnovanog na mjerama blizine.
rezultat grupiranja značajno zavisi od metrike, čiji je izbor, po pravilu, takođe subjektivan i određuje ga stručnjak. Ali vrijedi napomenuti da postoji niz preporuka za odabir mjera blizine za različite zadatke.

Aplikacija

U biologiji

U biologiji, grupisanje ima mnogo primjena u raznim oblastima. Na primjer, u bioinformatici se koristi za analizu složenih mreža gena u interakciji, koje se ponekad sastoje od stotina ili čak hiljada elemenata. Klaster analiza vam omogućava da identifikujete podmreže, uska grla, čvorišta i druga skrivena svojstva sistema koji se proučava, što vam na kraju omogućava da saznate doprinos svakog gena formiranju fenomena koji se proučava.

U oblasti ekologije, široko se koristi za identifikaciju prostorno homogenih grupa organizama, zajednica, itd. Ređe se koriste metode klaster analize za proučavanje zajednica tokom vremena. Heterogenost strukture zajednica dovodi do pojave netrivijalnih metoda klaster analize (na primjer, metoda Czekanowskog).

Općenito, vrijedno je napomenuti da se historijski gledano, mjere sličnosti češće koriste kao mjere blizine u biologiji, a ne mjere razlike (udaljenosti).

U sociologiji

Prilikom analize rezultata socioloških istraživanja, preporučuje se da se analiza provede korištenjem metoda hijerarhijske aglomerativne porodice, odnosno Wardove metode, u kojoj se optimizira minimalna disperzija unutar klastera, kao rezultat toga, klasteri približno jednake veličine. su kreirani. Wardova metoda je najuspješnija za analizu socioloških podataka. Kao mjera razlike, kvadratna euklidska udaljenost je bolja, što doprinosi povećanju kontrasta klastera. Glavni rezultat hijerarhijske klaster analize je dendrogram ili „slađi dijagram“. Prilikom tumačenja, istraživači se suočavaju sa problemom iste vrste kao i interpretacija rezultata faktorske analize – nepostojanje nedvosmislenih kriterijuma za identifikaciju klastera. Preporučljivo je koristiti dvije metode kao glavne - vizualnu analizu dendrograma i poređenje rezultata grupiranja izvedenog različitim metodama.

Vizuelna analiza dendrograma uključuje "rezanje" stabla na optimalnom nivou sličnosti elemenata uzorka. „Granu vinove loze“ (terminologija Oldenderfera M.S. i Blashfielda R.K.) treba „odsjeći“ na oko 5 na skali kombinovane grozdove poređane udaljenosti, čime se postiže nivo sličnosti od 80%. Ako je odabir klastera po ovoj oznaci težak (na njoj se nekoliko malih klastera spaja u jedan veliki), onda možete odabrati drugu oznaku. Ovu tehniku predlažu Oldenderfer i Blashfield.

Sada se postavlja pitanje stabilnosti usvojenog klaster rješenja. U stvari, provjera stabilnosti klasteriranja svodi se na provjeru njegove pouzdanosti. Ovdje postoji pravilo - stabilna tipologija je očuvana kada se metode klasteriranja mijenjaju. Rezultati hijerarhijske analize klastera mogu se verificirati iterativnom k-means klaster analizom. Ako upoređene klasifikacije grupa ispitanika imaju udio podudarnosti veći od 70% (više od 2/3 podudarnosti), onda se donosi klaster odluka.

Nemoguće je provjeriti adekvatnost rješenja bez pribjegavanja drugoj vrsti analize. Barem teoretski, ovaj problem nije riješen. Oldenderferova i Blashfieldova klasična analiza klastera razrađuje i na kraju odbacuje pet dodatnih metoda testiranja robusnosti:

U informatici

Grupiranje rezultata pretraživanja - koristi se za "inteligentno" grupisanje rezultata prilikom pretraživanja datoteka, web stranica, drugih objekata, omogućavajući korisniku da se brzo kreće, odabere podskup koji je očito relevantniji i isključuje poznati manje relevantan - što može povećati upotrebljivost interfejsa u poređenju sa izlazom u obliku jednostavne sortirane po relevantnosti liste.
- Clusty - Vivísimov pretraživač za grupisanje
- Nigma - ruski pretraživač sa automatskim grupisanjem rezultata
- Quintura - vizualno grupisanje u obliku oblaka ključnih riječi
Segmentacija slike segmentacija slike) - Grupiranje se može koristiti za razbijanje digitalne slike na različite regije u svrhu detekcije ivica. detekcija ivica) ili prepoznavanje objekata.
Data mining rudarenje podataka)- Klasterizacija u Data Mining-u postaje vrijedna kada djeluje kao jedna od faza analize podataka, izgrađujući kompletno analitičko rješenje. Analitičaru je često lakše da identifikuje grupe sličnih objekata, prouči njihove karakteristike i izgradi poseban model za svaku grupu nego da kreira jedan opšti model za sve podatke. Ova tehnika se stalno koristi u marketingu, naglašavajući grupe kupaca, kupaca, robe i razvijajući posebnu strategiju za svaku od njih.

vidi takođe

Bilješke

Linkovi

Na ruskom

www.MachineLearning.ru - profesionalni wiki resurs posvećen mašinskom učenju i rudarenju podataka

Na engleskom

COMPACT - Uporedni paket za procjenu klastera. Besplatan Matlab paket, 2006.
P. Berkhin, Istraživanje klastering tehnika rudarenja podataka, Accue Software, 2002.
Jain, Murty i Flynn: Grupiranje podataka: pregled, ACM Comp. Surv., 1999.
za drugu prezentaciju hijerarhijskih, k-srednjih i rasplinutih c-sredina pogledajte ovaj uvod u grupisanje. Također ima objašnjenje o mješavini Gaussovih.
David Dowe, Stranica za modeliranje mješavine- ostale veze modela klastera i mešavine.
tutorijal o grupiranju
On-line udžbenik: Teorija informacija, zaključivanje i algoritmi učenja, autora Davida J.C. MacKay uključuje poglavlja o k-means grupisanju, mekom k-means grupisanju i derivacijama uključujući E-M algoritam i varijacioni pogled na E-M algoritam.
"The Self-Organized Gene", tutorijal koji objašnjava grupisanje kroz konkurentno učenje i samoorganizirajuće mape.
kernlab - R paket za strojno učenje bazirano na kernelu (uključuje implementaciju spektralnog klasteriranja)
Tutorial - Tutorijal sa uvođenjem algoritama za grupisanje (k-means, fuzzy-c-means, hijerarhijski, mješavina gaussovih) + neke interaktivne demonstracije (java apleti)
Softver za rudarenje podataka - Softver za rudarenje podataka često koristi tehnike klasteriranja.
Java Competitive Learning aplikacija Paket nenadziranih neuronskih mreža za grupisanje. Napisano na Javi. Kompletno sa svim izvornim kodom.
Softver za strojno učenje - također sadrži mnogo softvera za klasteriranje.

Znamo da je Zemlja jedna od 8 planeta koje se okreću oko Sunca. Sunce je samo zvezda među oko 200 milijardi zvezda u galaksiji Mlečni put. Veoma je teško razumjeti ovaj broj. Znajući ovo, može se napraviti pretpostavka o broju zvijezda u svemiru - otprilike 4X10^22. Možemo vidjeti oko milion zvijezda na nebu, iako je to samo mali dio stvarnog broja zvijezda. Dakle, imamo dva pitanja:

Šta je galaksija?
I kakva je veza između galaksija i teme članka (analiza klastera)

Galaksija je skup zvijezda, plina, prašine, planeta i međuzvjezdanih oblaka. Obično galaksije liče na spiralnu ili edeptičku figuru. U svemiru su galaksije odvojene jedna od druge. Ogromne crne rupe najčešće su centri većine galaksija.

Kao što ćemo raspravljati u sljedećem odjeljku, postoji mnogo sličnosti između galaksija i analize klastera. Galaksije postoje u trodimenzionalnom prostoru, analiza klastera je multidimenzionalna analiza koja se provodi u n-dimenzionalnom prostoru.

Napomena: Crna rupa je centar galaksije. Koristićemo sličnu ideju za centroide za analizu klastera.

klaster analiza

Recimo da ste šef marketinga i odnosa s kupcima u telekomunikacijskoj kompaniji. Shvaćate da su svi kupci različiti i da su vam potrebne različite strategije da biste dosegli različite kupce. Cijenit ćete moć takvog alata kao što je segmentacija kupaca za optimizaciju troškova. Da biste pojačali svoje znanje o klaster analizi, razmotrite sljedeći primjer, koji ilustruje 8 kupaca i njihovo prosječno trajanje razgovora (lokalnog i međunarodnog). Ispod su podaci:

Radi bolje percepcije, nacrtajmo grafikon gdje će osa x biti prosječno trajanje međunarodnih poziva, a osa y - prosječno trajanje lokalnih poziva. Ispod je grafikon:

Napomena: Ovo je slično analizi položaja zvijezda na noćnom nebu (ovdje su zvijezde zamijenjene potrošačima). Osim toga, umjesto 3D prostora, imamo 2D prostor, definiran trajanjem lokalnih i međunarodnih poziva, kao x i y ose.
Sada, govoreći u terminima galaksija, problem je formulisan na sledeći način – pronaći položaj crnih rupa; u klaster analizi nazivaju se centroidi. Da bismo otkrili centroide, počećemo tako što ćemo uzeti proizvoljne tačke kao položaj težišta.

Euklidska udaljenost za pronalaženje centroida za klastere

U našem slučaju ćemo nasumično postaviti dva težišta (C1 i C2) u tačke sa koordinatama (1, 1) i (3, 4). Zašto smo odabrali ova dva centroida? Vizuelni prikaz tačaka na grafikonu nam pokazuje da postoje dva klastera koje ćemo analizirati. Međutim, kasnije ćemo vidjeti da odgovor na ovo pitanje neće biti tako jednostavan za veliki skup podataka.
Zatim ćemo izmjeriti udaljenost između težišta (C1 i C2) i svih tačaka na grafu koristeći Euklidovu formulu da bismo pronašli udaljenost između dvije tačke.

Napomena: Udaljenost se također može izračunati korištenjem drugih formula, na primjer,

kvadrat euklidske udaljenosti - da bi se dala težina objektima koji su udaljeniji jedan od drugog
Udaljenost od Manhattana - za smanjenje utjecaja emisija
distanca snage - za povećanje / smanjenje utjecaja na određene koordinate
postotak neslaganja - za kategoričke podatke
i sl.

Kolona 3 i 4 (Udaljenost od C1 i C2) je udaljenost izračunata pomoću ove formule. Na primjer, za prvog korisnika

Pripadnost centroidima (zadnji stupac) izračunava se prema principu blizine centroidima (C1 i C2). Prvi potrošač je bliži centroidu #1 (1,41 u odnosu na 2,24) pa pripada grupi sa centrom C1.

Ispod je grafikon koji ilustruje centre C1 i C2 (prikazano kao plavi i narandžasti dijamant). Potrošači su prikazani u boji odgovarajućeg centroida kojem su dodijeljeni.

Pošto smo proizvoljno odabrali centre, drugi korak je da ovaj izbor učinimo iterativnim. Novi položaj centara se bira kao prosjek za tačke odgovarajućeg klastera. Tako, na primjer, za prvi centar (to su potrošači 1, 2 i 3). Dakle, nova x-koordinata za centar C1 je prosjek x-koordinata ovih potrošača (2+1+1)/3 = 1,33. Dobićemo nove koordinate za C1 (1.33, 2.33) i C2 (4.4, 4.2).Novi grafikon je ispod:

Konačno, središta ćemo postaviti u centar odgovarajućeg klastera. Grafikon ispod:

Položaji naših crnih rupa (centra klastera) u našem primjeru su C1 (1,75, 2,25) i C2 (4,75, 4,75). Dva gornja jata su poput dvije galaksije odvojene u svemiru jedna od druge.

Dakle, pogledajmo dalje primjere. Suočimo se sa zadatkom segmentiranja potrošača prema dva parametra: starosti i prihodu. Pretpostavimo da imamo 2 potrošača starosti 37 i 44 godine sa prihodima od 90.000 dolara i 62.000 dolara respektivno. Ako želimo da izmerimo euklidsku udaljenost između tačaka (37, 90000) i (44, 62000), videćemo da u ovom slučaju varijabla dohotka „dominira“ varijablom starosti i njena promena snažno utiče na udaljenost. Potrebna nam je neka vrsta strategije za rješavanje ovog problema, inače će naša analiza dati pogrešan rezultat. Rješenje ovog problema je dovođenje naših vrijednosti na uporedive skale. Normalizacija je rješenje za naš problem.

Normalizacija podataka

Postoji mnogo pristupa za normalizaciju podataka. Na primjer, minimalno-maksimalna normalizacija. Za ovu normalizaciju koristi se sljedeća formula

u ovom slučaju, X* je normalizirana vrijednost, min i max su minimalne i maksimalne koordinate za cijeli skup X
(Napomena, ova formula postavlja sve koordinate na segment)
Razmotrimo naš primjer, neka maksimalni prihod bude 130.000 dolara, a minimalni 45.000 dolara. Normalizirana vrijednost dohotka za potrošača A je

Ovu vježbu ćemo uraditi za sve tačke za svaku varijablu (koordinatu). Prihod za drugog potrošača (62000) će nakon procedure normalizacije postati 0,2. Uz to, neka minimalna i maksimalna starost budu 23 odnosno 58 godina. Nakon normalizacije, starost naša dva potrošača biće 0,4 i 0,6 godina.

Lako je vidjeti da su sada svi naši podaci između 0 i 1. Stoga sada imamo normalizirane skupove podataka na uporedivim skalama.

Zapamtite, prije procedure klaster analize potrebno je izvršiti normalizaciju.

Vrste unosa

Indikativni opis objekata. Svaki objekat je opisan skupom njegovih karakteristika, tzv znakovi. Karakteristike mogu biti numeričke ili nenumeričke.
Matrica udaljenosti između objekata. Svaki objekt je opisan udaljenostima do svih ostalih objekata u uzorku za obuku.

Matrica udaljenosti može se izračunati iz matrice opisa karakteristika objekata na beskonačan broj načina, ovisno o tome kako uvesti funkciju udaljenosti (metriku) između opisa karakteristika. Euklidska metrika se često koristi, ali ovaj izbor je u većini slučajeva heuristički i nastaje samo zbog pogodnosti.

Inverzni problem - obnavljanje opisa karakteristika matricom parnih udaljenosti između objekata - u opštem slučaju nema rješenja, a približno rješenje nije jedinstveno i može imati značajnu grešku. Ovaj problem se rješava multidimenzionalnim metodama skaliranja.

Dakle, formulacija problema grupisanja po matrica udaljenosti je opštija. S druge strane, u prisustvu opisa karakteristika, često je moguće izgraditi efikasnije metode klasteriranja.

Ciljevi grupisanja

Razumijevanje podataka identificiranjem strukture klastera. Podjela uzorka na grupe sličnih objekata omogućava pojednostavljenje dalje obrade podataka i donošenja odluka primjenom vlastite metode analize na svaki klaster (strategija „zavadi pa vladaj“).
Kompresija podataka. Ako je početni uzorak pretjerano velik, onda se može smanjiti, ostavljajući po jednog od najtipičnijih predstavnika iz svakog klastera.
Detekcija noviteta. Odabiru se netipični objekti koji se ne mogu priključiti ni jednom od klastera.

U prvom slučaju pokušavaju smanjiti broj klastera. U drugom slučaju, važnije je osigurati visok (ili fiksni) stepen sličnosti objekata unutar svakog klastera, a klastera može postojati bilo koji broj. U trećem slučaju, od najvećeg su interesa pojedinačni objekti koji se ne uklapaju ni u jedan od klastera.

Rezultat taksonomije je hijerarhijska struktura nalik stablu. Osim toga, svaki objekt karakterizira nabrajanje svih klastera kojima pripada, obično od velikih do malih. Vizuelno, taksonomija je predstavljena kao graf koji se naziva dendrogram.

Klasičan primjer taksonomije zasnovane na sličnosti je binomna nomenklatura živih bića koju je predložio Carl Linnaeus sredinom 18. vijeka. Slične sistematizacije se grade u mnogim oblastima znanja kako bi se organizovale informacije o velikom broju objekata.

Funkcije udaljenosti

Metode grupisanja

Statistički algoritmi za grupisanje
Hijerarhijsko grupiranje ili taksonomija

Formalna izjava o problemu grupisanja

Grupiranje (učenje bez nadzora) razlikuje se od klasifikacije (učenje pod nadzorom) po tome što oznake originalnih objekata nisu inicijalno postavljene, a sam skup može čak biti nepoznat.

Rješenje problema klasteriranja je u osnovi dvosmisleno, a za to postoji nekoliko razloga:

Ne postoji jedinstveno najbolji kriterijum za kvalitet grupisanja. Poznato je više heurističkih kriterijuma, kao i niz algoritama koji nemaju jasno definisan kriterijum, ali sprovode prilično razumno grupisanje „po konstrukciji“. Svi oni mogu dati različite rezultate.
Broj klastera je obično nepoznat unapred i određuje se prema nekom subjektivnom kriterijumu.
Rezultat grupiranja značajno zavisi od metrike, čiji je izbor, po pravilu, takođe subjektivan i određuje ga stručnjak.

Linkovi

Vorontsov K.V. Metode nastave matematike po presedanima. Moskovski institut za fiziku i tehnologiju (2004), VMiK MGU (2007).
Sergej Nikolenko. Slajdovi predavanja "Algoritmi grupisanja 1" i "Algoritmi grupisanja 2". Kurs "Sistemi za samoučenje".

Književnost

Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Primijenjena statistika: klasifikacija i redukcija dimenzija. - M.: Finansije i statistika, 1989.
Žuravljev Yu. I., Ryazanov V. V., Senko O. V."Priznanje". Matematičke metode. Softverski sistem. Praktične primjene. - M.: Fazis, 2006. .
Zagoruiko N. G. Primijenjene metode analize podataka i znanja. - Novosibirsk: IM SO RAN, 1999. .
Mandel I. D. klaster analiza. - M.: Finansije i statistika, 1988. .
Šlesinger M., Glavač V. Deset predavanja o statističkom i strukturnom prepoznavanju. - Kijev: Naukova dumka, 2004. .
Hastie T., Tibširani R., Friedman J. Elementi statističkog učenja. - Springer, 2001. .