к-медоид

Алгоритам ' $k$ -медоида је алгоритам груписања који је повезан са $k$ -means алгоритмом и „медоидшифт алгоритмом“. Оба и $k$ -means and $k$ -медоид алгоритми су партитивни (раздваја скуп података на групе) и оба покушавају да умање растојање између означених тачака у кластеру и тачке одређене као центар кластера. Насупрот $k$ -means алгоритму, $k$ -медоид бира тачке података као центре (медоиди или примерци) и ради са произвољном матрицом растојања између тачака података уместо са $l_{2}$ . Овај метод је био предложен 1987. за рад са нормом $l_{1}$ и другим дистанцама.

$k$ -медоид је класична партитивна техника груписања кластера скупа података $n$ објеката у $k$ кластер познат као priori. Користан алат за одређивање $k$ је силует.

Медоид може бити дефинисан као објекат кластера, чији просек различитости за све објекте у кластеру је минималан, то је највише центално лоцирана тачка у кластеру.

Најуобичајенија реализација груписања $k$ -медоида је партиционисање око медоида (PAM) алгоритма као што следи:

Иницијализација: насумично изабрати $k$ од $n$ тачака података као медоиде
Везати сваку тачку података са најближим медоидом (“најближа” овде је дефинисана користећи било које валидно метричко растојање, најчешће Еуклидово растојање, Менхетн растојање или Минковски растојање)
За сваки медоид m
1. За сваки не-медоид тачке података o
  1. Замени $m$ и $o$ и израчунај укупну цену конфигурације
Изабери конфигурацију најниже цене
понављај кораке 2 и 4 све док нема промена на медоиду

Демонстрација PAM-а[уреди | уреди извор]

Груписати следећи скуп тачака података од десет објеката у две групе. $k = 2$ .

Размотрити цкуп података од десет објеката на следећи начин:

X₁	2	6
X₂	3	4
X₃	3	8
X₄	4	7
X₅	6	2
X₆	6	4
X₇	7	3
X₈	7	4
X₉	8	5
X₁₀	7	6

Корак 1[уреди | уреди извор]

Иницијализуј $k$ центара.

Претпоставимо да је $c 1 = (3,4)$ и $c 2 = (7,4)$

Тако да су $c 1$ и $c 2$ означени као медоиди.

Израчунати растојање тако да се удружи сваки скуп објеката са најближим медоидом. Цена је израчуната користећи Менхетн растојање (Минковски растојање са $r = 1$ ). Цена најближег медоида је показана болдовано у табели.

$i$	$c 1$		Објектни подаци ( $X i$ )		Цена (растојање)
1	3	4	2	6	3
3	3	4	3	8	4
4	3	4	4	7	4
5	3	4	6	2	5
6	3	4	6	4	3
7	3	4	7	3	5
9	3	4	8	5	6
10	3	4	7	6	6

$i$	$c 2$		Data objects ( $X i$ )		Cost (distance)
1	7	4	2	6	7
3	7	4	3	8	8
4	7	4	4	7	6
5	7	4	6	2	3
6	7	4	6	4	1
7	7	4	7	3	1
9	7	4	8	5	2
10	7	4	7	6	2

Тада групе постају:

$Cluster 1 = {(3,4)(2,6)(3,8)(4,7)}$

$Cluster 2 = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}$

Како су тачке $(2,6)$ $(3,8)$ и $(4,7)$ најближе $c 1$ дакле оне формирају једну групу док остале тачке формирају другу групу.

Тако да је укупна цена $20$ .

Где је цена између било које две тачке тражена по формули

${\mbox{cost}}(x,c)=\sum _{i=1}^{d}|x_{i}-c_{i}|$

где је $x$ било који скуп објеката, $c$ је медоид, и $d$ је димензија објекта, у овом случају је $2$ .

Укупна цена је сума цена скупа објеката из својих медоида и из група:

${\begin{aligned}{\mbox{total cost}}&=\{{\mbox{cost}}((3,4),(2,6))+{\mbox{cost}}((3,4),(3,8))+{\mbox{cost}}((3,4),(4,7))\}\\&~+\{{\mbox{cost}}((7,4),(6,2))+{\mbox{cost}}((7,4),(6,4))+{\mbox{cost}}((7,4),(7,3))\\&~+{\mbox{cost}}((7,4),(8,5))+{\mbox{cost}}((7,4),(7,6))\}\\&=(3+4+4)+(3+1+1+2+2)\\&=20\\\end{aligned}}$

Корак 2[уреди | уреди извор]

Слика 1.3 – кластери након другог корака

Изабери један од не-медоида $O'$

Претпоставимо да је $O' = (7,3)$

Тако да су сада медоиди $c 1 (3,4)$ и $O'(7,3)$

Ако су $c1$ и $O'$ нови медоиди, израчунати укупну цену

Користећи формулу из корака 1

$i$	$c 1$		Data objects ( $X i$ )		Cost (distance)
1	3	4	2	6	3
3	3	4	3	8	4
4	3	4	4	7	4
5	3	4	6	2	5
6	3	4	6	4	3
7	3	4	7	4	4
9	3	4	8	5	6
10	3	4	7	6	4

$i$	$O'$		Data objects ( $X i$ )		Cost (distance)
1	7	3	2	6	8
3	7	3	3	8	9
4	7	3	4	7	7
5	7	3	6	2	2
6	7	3	6	4	2
7	7	3	7	4	1
9	7	3	8	5	3
10	7	3	7	6	3

${\begin{aligned}{\mbox{total cost}}&=3+4+4+2+2+1+3+3\\&=22\\\end{aligned}}$

Дакле, цена мењања медоида из $c 2$ у $O'$ износи

${\begin{aligned}S&={\mbox{current total cost}}-{\mbox{past total cost}}\\&=22-20\\&=2>0.\end{aligned}}$

Тако да би померање на $O'$ било лоша идеа, што значи да је претходни избор био добар. Тако да ми пробамо са још не-медоида и дођемо до закључка да је први избор био најбољи. Тако да се конфигурација не мења и алгоритам стаје овде. Може се десити да неке тачке података се помере из једне групе у другу у зависности од њиховог најближег медоида.

У неким стандардима, k-медоиди показују боље резултате од k-means алгоритма. Пример је представљен на слици 2. У већини времена к-медоид алгоритам рачуна растојање између објеката. Ако је квадратно препроцесирање важи, растојање матрица може бити прерачунато тако да достигне доследно убрзање. Видети за пример,^[2] где аутори такође хеуристично решење за одабир иницијалног $k$ mедоида. Упоредо проучавање K-means and k-медоид алгоритма је извршена за нормалну и јединствену дистрибуцију тачака података^[3] Показано је да за асимптотику већег скупа података к-медоид алгоритма потребно мање времена.

Софтвер[уреди | уреди извор]

ELKI
GNU R

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

^ Илустрација припремљена Јава аплетом, E.M. Mirkes, K-means and K-medoids: applet Архивирано на сајту Wayback Machine (29. мај 2013). University of Leicester, 2011.
^ H.S. Park , C.H. Jun, A simple and fast algorithm for K-medoids clustering, Expert Systems with Applications, 36, (2) (2009), 3336–3341.
^ T. Velmurugan and T. Santhanam, Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points, Journal of Computer Science 6 (3) (2010), 363-368.

Спољашње везе[уреди | уреди извор]

E.M. Mirkes, K-means and K-medoids (Applet), University of Leicester, 2011.

[1] Илустрација припремљена Јава аплетом, E.M. Mirkes, K-means and K-medoids: applet Архивирано на сајту Wayback Machine (29. мај 2013). University of Leicester, 2011.

[2] H.S. Park , C.H. Jun, A simple and fast algorithm for K-medoids clustering, Expert Systems with Applications, 36, (2) (2009), 3336–3341.

[3] T. Velmurugan and T. Santhanam, Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points, Journal of Computer Science 6 (3) (2010), 363-368.

[1]

[2]

[3]