Изворни код странице К-медоид

{{Lowercase}}
Алгоритам '''{{math|<var>k</var>}}-медоида '' је [[алгоритам груписања]] који је повезан са [[k-means|{{math|<var>k</var>}}-means]] алгоритмом и „медоидшифт алгоритмом“. Оба и {{math|<var>k</var>}}-means and {{math|<var>k</var>}}-медоид алгоритми су партитивни (раздваја скуп података на групе) и оба покушавају да умање растојање између означених тачака у кластеру и тачке одређене као центар кластера. Насупрот {{math|<var>k</var>}}-means алгоритму, {{math|<var>k</var>}}-медоид бира тачке података као центре ([[медоиди]] или примерци) и ради са произвољном матрицом растојања између тачака података уместо са <math>l_2</math>. Овај метод је био предложен 1987. за рад са нормом <math>l_1</math> и другим дистанцама.

{{math|<var>k</var>}}-медоид је класична партитивна техника груписања кластера скупа података {{math|<var>n</var>}} објеката у {{math|<var>k</var>}} кластер познат као ''-{priori}-''. Користан алат за одређивање {{math|<var>k</var>}} је [[силует (кластеризација)|силует]].

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

Најуобичајенија реализација груписања {{math|<var>k</var>}}-медоида је партиционисање око медоида (PAM) алгоритма као што следи:
# Иницијализација: насумично изабрати {{math|<var>k</var>}} од {{math|<var>n</var>}} тачака података као медоиде
# Везати сваку тачку података са најближим медоидом (“најближа” овде је дефинисана користећи било које валидно [[метричко растојање]], најчешће [[Еуклидово растојање]], [[Менхетн растојање]] или [[Минковски растојање]])
# За сваки медоид {{math|<var>m</var>}}
## За сваки не-медоид тачке података {{math|<var>o</var>}}
### Замени {{math|<var>m</var>}} и {{math|<var>o</var>}} и израчунај укупну цену конфигурације
# Изабери конфигурацију најниже цене
# понављај кораке 2 и 4 све док нема промена на медоиду

== Демонстрација PAM-а ==
Груписати следећи скуп тачака података од десет објеката у две групе. {{math|<var>k</var> {{=}} 2}}.

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

[[Датотека:kmedoid1.jpg|мини|десно|350 px|Слика 1.1 – дистрибуција података]]

{| class="wikitable" width=20%
| width=33% | X<sub>1</sub>
| width=33% | 2 
| width=33% | 6
|-
| X<sub>2</sub> || 3 || 4
|-
| X<sub>3</sub> || 3 || 8
|-
| X<sub>4</sub> || 4 || 7
|-
| X<sub>5</sub> || 6 || 2
|-
| X<sub>6</sub> || 6 || 4
|-
| X<sub>7</sub> || 7 || 3
|-
| X<sub>8</sub> || 7 || 4
|-
| X<sub>9</sub> || 8 || 5
|-
| X<sub>10</sub> || 7 || 6
|}

{{-}}

=== Корак 1 ===
[[Датотека:kmedoid2.jpg|мини|десно|350 px|Слика 1.2 – кластери након првог корака]]

Иницијализуј {{math|<var>k</var>}} центара.

Претпоставимо да је {{math|c<sub>1</sub> {{=}} (3,4)}} и {{math|c<sub>2</sub> {{=}} (7,4)}}

Тако да су {{math|c<sub>1</sub>}} и {{math|c<sub>2</sub>}} означени као медоиди.

Израчунати растојање тако да се удружи сваки скуп објеката са најближим медоидом. Цена је израчуната користећи [[Менхетн растојање]] ([[Минковски растојање]] са {{math|<var>r</var> {{=}} 1}}). Цена најближег медоида је показана болдовано у табели.

{| class="wikitable" width=40%
| colspan=1 align="center" | {{math|''i''}}
| colspan=2 align="center" | {{math|c<sub>1</sub>}}
| colspan=2 | Објектни подаци ({{math|X<sub>''i''</sub>}})
| Цена (растојање)
|-
| width=20% | 1
| width=20% | 3
| width=20% | 4
| width=20% | 2
| width=20% | 6
| width=20% | '''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
|}

{| class="wikitable" width=40%
| colspan=1 align="center" | {{math|''i''}}
| colspan=2 align="center" | {{math|c<sub>2</sub>}}
| colspan=2 | Data objects ({{math|X<sub>''i''</sub>}})
| Cost (distance)
|-
| width=20% | 1
| width=20% | 7
| width=20% | 4
| width=20% | 2
| width=20% | 6
| width=20% | 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'''
|}

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

{{math|Cluster<sub>1</sub> {{=}} {(3,4)(2,6)(3,8)(4,7)} }}

{{math|Cluster<sub>2</sub> {{=}} {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)} }}

Како су тачке {{math|(2,6)}} {{math|(3,8)}} и {{math|(4,7)}} најближе {{math|c<sub>1</sub>}} дакле оне формирају једну групу док остале тачке формирају другу групу.

Тако да је укупна цена {{math|20}}.

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

<math>
\mbox{cost}(x,c) = \sum_{i=1}^d | x_{i} - c_{i} |
</math>

где је {{math|<var>x</var>}} било који скуп објеката, {{math|<var>c</var>}} је медоид, и {{math|<var>d</var>}} је димензија објекта, у овом случају је {{math|2}}.

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

{{-}}

<math>
\begin{align}
\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{align}
</math>

=== Корак 2 ===
[[Датотека:kmedoid3.jpg|мини|десно|350 px|Слика 1.3 – кластери након другог корака]]
Изабери један од не-медоида {{math|O'}}

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

Тако да су сада медоиди {{math|c<sub>1</sub>(3,4)}} и {{math|O'(7,3)}}

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

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

{| class="wikitable" width=40%
| colspan=1 align="center" | {{math|''i''}}
| colspan=2 align="center" | {{math|c<sub>1</sub>}}
| colspan=2 | Data objects ({{math|X<sub>''i''</sub>}})
| Cost (distance)
|-
| width=20% | 1
| width=20% | 3
| width=20% | 4
| width=20% | 2
| width=20% | 6
| width=20% | '''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
|}

{| class="wikitable" width=40%
| colspan=1 align="center" | {{math|''i''}}
| colspan=2 align="center" | {{math|O'}}
| colspan=2 | Data objects ({{math|X<sub>''i''</sub>}})
| Cost (distance)
|-
| width=20% | 1
| width=20% | 7
| width=20% | 3
| width=20% | 2
| width=20% | 6
| width=20% | 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'''
|}

{{-}}
[[Датотека:K-means versus k-medoids.png|мини|550 px|Слика 2. К-медоиди насупрот к-средина. слике 2.1a-2.1f представљају типичне примере конвергенције k-средина ка локалном минимуму. Овај резултат кластеризовања k-срединама представља контрадикцију очигледној структури кластера скупа података. У овом примеру, алгоритам k-медоида (слике 2.2a-2.2h) са истим почетним положајем медоида (слика 2.2a) конвергира очигледној структури кластера. Мали кругови су подаци, четири зрачне звезде су центроиди (средине), девет зрачних звезда су медоиди.<ref>Илустрација припремљена Јава аплетом, -{E.M. Mirkes, [http://www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids: applet] {{Wayback|url=http://www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html |date=20130529193511 }}. University of Leicester, 2011.}-</ref>]]

<math>
\begin{align}
\mbox{total cost} & = 3 + 4 + 4 + 2 + 2 + 1 + 3 + 3 \\
 & = 22 \\
\end{align}
</math>

Дакле, цена мењања медоида из {{math|c<sub>2</sub>}} у {{math|O'}} износи

<math>
\begin{align}
 S & = \mbox{current total cost} - \mbox{past total cost} \\
 & = 22 - 20 \\
 & = 2 > 0.
\end{align}
</math>

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

У неким стандардима, k-медоиди показују боље резултате од k-means алгоритма. Пример је представљен на слици 2.
У већини времена к-медоид алгоритам рачуна растојање између објеката. Ако је квадратно препроцесирање важи, растојање матрица може бити прерачунато тако да достигне доследно убрзање. Видети за пример,<ref>-{H.S. Park , C.H. Jun, A simple and fast algorithm for K-medoids clustering, Expert Systems with Applications, 36, (2) (2009), 3336–3341.}-</ref> где аутори такође хеуристично решење за одабир иницијалног{{math|<var>k</var>}} mедоида. Упоредо проучавање K-means and k-медоид алгоритма је извршена за нормалну и јединствену дистрибуцију тачака података<ref>-{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.}-</ref> Показано је да за асимптотику већег скупа података к-медоид алгоритма потребно мање времена.

== Софтвер ==
* [[ELKI]]
* [[GNU R]]

== Види још ==
* [[Кластерска анализа]]
* [[k-means]]
* [[К-медијанска кластеризација]]
* [[Медоид]]

== Референце ==
{{reflist}}

== Спољашње везе ==
{{Портал бар|Информатика}}
* -{E.M. Mirkes, [https://web.archive.org/web/20130529193511/http://www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids] (Applet), [[Универзитет Лестер|University of Leicester]], 2011.}-

{{нормативна контрола}}

[[Категорија:Статистички алгоритми]]
[[Категорија:Алгоритми кластеризације података]]