DMS Pregled podru cja: metode segmentiranja

Metode segmentiranja podataka

Tehnike segmentiranja podataka spadaju u grupu tzv. indirektnih metoda ("undirected data mining"), dok se u području strojnog učenja primjenjuje naziv 'učenje bez nadzora' ("unsupervised learning"). Cilj indirektnih metoda je otkrivanje globalne strukture podataka. U ovom pristupu ne postoji definiran ciljni atribut, kao u direktnih metoda poput metode stabla odlučivanja, pa ne postoji razlika izmedju atributa.

Metode segmentiranja koriste se radi podjele primjera u niz grupa ili podskupkupova ("clusters"), koji zadovoljavaju dva osnovna kriterija:

svaka grupa predstavlja homogen skup: primjeri koji pripadaju istoj grupi su medjusobno slični;
svaka grupa mora se razlikovati od ostalih grupa, t.j. primjeri koji pripadaju odredjenoj grupi značajno se razlikuju od primjera koji pripadaju ostalim grupama.

Zavisno od konkretne metode, grupe mogu biti definirane na različit način:

identificirane grupe mogu biti ekskluzivne, tako da svaki primjer pripada isključivo jednoj od grupa;
grupe se mogu preklapati; primjer može istovremeno pripadati nekolicini grupa;
grupe mogu biti definirane probabilistički: u tom slučaju primjer pripada svakoj od grupa s odredjenom vjerojatnosti
grupe mogu biti hijerarhijski strukturirane, sa grubom podjelom primjera na najvišem nivou, koji se potom može finije strukturirati na nižim nivoima.

U nastavku ćemo objasniti osnove najjednostavnije metode segmentiranja: tzv. algoritma 'k-srednjih vrijednosti', ("k-means"). Postoji čitav niz metoda segmentiranja koje su značajno kompleksnije kao što su samo-organizirajuće neuralne mreže (Kohonen-ove mreže), probabilističke metode (AutoClass algoritam), no metoda k-srednjih vrijednosti čini se najboljim primjerom za ilustraciju osnovnih principa.

Algoritam K-srednjih vrijednost

Ovaj algoritam ima kao ulaznu vrijednost prethodno definiran broj grupa, odnosno k (otuda i ime k...). Srednja vrijednost u algoritmu odnosi se na 'prosječnu' lokaciju (u više dimenzionalnom prostoru definarnom atributima). Kada se govori o metodama segmentiranja podataka, nužno je uvesti pojam više-dimenzionalnog prostora, koji je definiran atributima kao osima tog prostora. Vrijednost svakog atributa primjera predstavlja udaljenost tog primjera od ishodišta takvog prostora po koordinati atributa. Naravno, da bi ovu geometriju mogli efikasno koristiti, vrijednosti atributa moraju biti numeričke (vrijednosti nominalnih atributa moraju biti transformirane u numeričke vrijednosti!), a zatim i normalizirane da bi se omogućilo ravnopravno izračunavanje po svim koordinatama (atributima) prostora .

Algoritam K-srednjih vrijednosti je jednostavna, iterativna procedura u kojoj centralnu ulogu igra pojam 'centroida' ("centroid"). Centroid je umjetna točka u prostoru primjera, koja ustvari reprezentira 'srednju' ili 'prosječnu lokaciju odredjene grupe primjera. Koordinate ove točke izračunavaju se kao prosječne vrijednosti koordinata svih primjera koji pripadaju toj grupi. Algoritam K-srednjih vrijednosti prikazan je na Slici 1.

____________________________________________________________________

Odaberi proizvoljno (slučajno) k točaka (to mogu biti i konkretni primjeri iz skupa podataka!) kao početne točke
centroide svih k grupa.

Pridjeli svaki primjer centroidu kojem je primjer najbliži,
formirajući na taj način k ekskluzivnih grupa primjera.

Izračunaj nove centroide grupa i to na taj način da usrednjiš,
po pojedinim atributima, vrijednosti svih primjera koji pripadaju odredjenoj grupi,
odnosno (centroidu).

Provjeri da li su centroidi grupa promijenili svoje "koordinate" iznad .
prethodno definiranih minimalnih vrijednosti.
Ako jesu, kreni iznova od točke 2. Ako ne, odredjivanje grupa je završeno,
(svi primjeri pridijeljeni su odgovarajućoj grupi).

____________________________________________________________________

Slika 1. Algoritam K-srednjih vrijednosti

Obično ova iterativna procedura redefiniranja centroida te rasporedjivanja primjera u odgovaraju'ce grupe zahtijeva samo nekoliko iteracija do zadovoljavajuće konvergencije.

Posebni aspekti metoda segmentiranja podataka

Posebni aspekti metoda automatskog segmentiranja podataka vezani su uz pitanja koja želimo riješiti procesom obrade podataka, odnosno proces pripreme podataka za njihovu efikasnu primjenu.

Pitanje mjerenja udaljenosti primjera (metrika prostora)

Većina metoda segmentiranja koristi Euklidsku mjeru udaljenosti u prostoru primjera (kvadatni korijen zbroja kvadrata udaljenosti po svim koordinatama (atributima) prostora).

Nominalni atributi moraju se prethodno transformirati i normirati prije za primjenu metode segmentiranja. O ovoj transformaciji umnogome zavisi koliko će ovi atributi biti važni za sam proces segmentiranja. Oni mogu biti dominantni, ali i potpuno nebitni, ako se transformacija izvede na odredjeni način.

Izbor ispravnog broja grupa

Ako je broj grupa K u metodi K-srednjih vrijednosti pogrešno odabran, konačni rezultati neće biti dobri. Ispravan pristup odabiru broja grupa bio bi da se eksperimentira s različitim brojem grupa. U principu, optimalan broj grupa imat će najpovoljniji omjer intra-grupnih i inter-grupnih udaljenosti primjera. Sofisticiranije tehnike segmentiranja mjere ovaj omjer i same automatski optimiraju broj grupa u dodatnoj petlji (AutoClass).

Interpretacija grupa

Jednom otkrivene grupe potrebno je interpretirati, kako bi rezultat segmentiranja podataka bio od koristi za proces obrade podataka. Postoji nekoliko načina da se iskoriste rezultati segmentiranja podataka:

Pripadnost odredjenoj grupi može se iskoristiti kao poseban ciljni atribut za odvojeni, novi, klasifikacijski problem. Neka od deskriptivnih tehnika modeliranja podataka (npr. stabla odlučivanja) može se iskoristiti za opis pojedinih grupa primjera.
Grupe se mogu vizualno prikazati korištenjem 2D ili 3D grafova, ili nekom od novijih 'više-dimenzionalnih' vizualizacijskih tehnika.
Razlike izmedju vrijednosti atributa pojedinih grupa mogu se razmatrati pojedinačno, od atributa do atributa.

Aspekti primjene tehnika segmentiranja

Tehnike segmentiranja koriste se u slučajevima kada se očekuje postojanje 'prirodnih' grupa u podacima. Otkriveni segmenti ili grupe podataka trebali bi predstavljati grupe primjera koji imaju mnogo toga zajedničkog. Stvaranje grupa primjera prije primjene neke druge tehnike modeliranja podataka (neuralnih mreža, stabla odlučivanja) može znatno reducirati kompleksnost odredjenog problema, podjelom skupa primjera za modeliranje. Ovakvi podskupovi primjera za učenje potom se mogu modelirati odvojeno, a takva dvo-stepena procedura na kraju može rezultirati boljim konačnim rezultatima (bilo u prediktivnom ili deskriptivnom smislu), nego bez prethodne primjene tehnika segmentiranja podataka.

WWW tekstovi o tehnikama segmentiranja

Data Clustering and Its Applications
by Raza Ali, Usman Ghani , Aasim Saeed
http://members.tripod.com/asim_saeed/paper.htm