K-medijanska klasterizacija

U statistici i analizi podataka, k-medijanska klasterizacija je algoritam grupisanja podataka . On je varijacija k-means klastera gde umesto izračunavanja mean za svaki klaster da bi odredili njegov centroid, umesto toga izračunava se mediana. Ovo ima efekat smanjenja greške nad svim klasterima poštujući 1-norma metričkog rastojanja, za razliku od kvadrata 2-norma metričkog rastojanja (što k-means radi.)

Ovo se direktno povezuje sa k-media problemom koji je problem pronalaženja k centara takav da klasteri formirani od njih su najviše kompaktni. Formalno, date su tačke skupa x, k centri c_i treba da budu izabrani tako da smanje sumu rastojanja od svakog x do najbližeg c_i.

Kriterijum funkcije formulisan na ovaj način je ponekad bolji od kriterijuma uk-means clustering algoritmu, u kom je korišćena suma kvadratnog rastojanja. Suma distanci je veoma korišćena u aplikacijama kao što je facility location.

Predloženi algoritam koristi Lojdov stil ponavljanja, koji alternira između očekivane vrednosti (E) i maksimalno (M) koraka, praveci Expectation–maximization algoritam. U E koraku svi predmeti su dodeljeni njihovom najbližem medijanu. U M koraku, medijane su ponovo izračunate koristeći medijanu u svakoj dimenziji ponaosob.

Mediane i medoidi

Kako je medijan izračunat u svakoj dimenziji ponaosob, pojedinačna svojstva će se videti iz skupa, čineći ovaj algoritam pouzdanijim za diskretne ili čak binarne skupove podataka. Međutim, sredstva nisu neophodno slučajevi iz skupa podataka, dok svojstva mogu doći iz različitih slučajeva. Ovaj algoritam je često zbunjen k-medoid algoritmom. Međutim, median mora da bude slučaj iz skupa podataka, dok za (multivarijantnu) medianu ovo važi za pojedinačna svojstva vrednosti. Mediana prema tome može biti kombinacija višestrukih svojstava. Dati su vektori $(0,1)$, $(1,0)$ i $(2,2)$, mediana je očigledno $(1,1)$ i ne postoji u originalnom skupu i prema tome ne može biti medoid.

Softver

• ELKI includes various k-means variants, including k-medians.
• GNU R includes k-medians in the "flexclust" package.

Vidi ostalo

• cluster analysis
• k-means
• medoid
• silhouette