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

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

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

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

Демонстрација PAM-а 
Груписати следећи скуп тачака података од десет објеката у две групе. .

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

Корак 1 

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

Претпоставимо да је  и 

Тако да су  и  означени као медоиди.

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

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

Како су тачке   и  најближе  дакле оне формирају једну групу док остале тачке формирају другу групу.

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

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

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

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

Корак 2 

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

Претпоставимо да је 

Тако да су сада медоиди  и 

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

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

Дакле, цена мењања медоида из  у  износи

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

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

Софтвер 
 ELKI
 GNU R

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

Референце

Спољашње везе 

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

Статистички алгоритми
Алгоритми кластеризације података
Алгоритам ' -медоида је алгоритам груписања који је повезан са -means алгоритмом и „ медоидшифт алгоритмом “ . Оба и -means and -медоид алгоритми су партитивни ( раздваја скуп података на групе ) и оба покушавају да умање растојање између означених тачака у кластеру и тачке одређене као центар кластера . Насупрот -means алгоритму , -медоид бира тачке података као центре ( медоиди или примерци ) и ради са произвољном матрицом растојања између тачака података уместо са \ . Овај метод је био предложен за рад са нормом и другим дистанцама . -медоид је класична партитивна техника груписања кластера скупа података објеката у кластер познат као -{ priori } - . Користан алат за одређивање је силует . Медоид може бити дефинисан као објекат кластера , чији просек различитости за све објекте у кластеру је минималан , то је највише центално лоцирана тачка у кластеру . Најуобичајенија реализација груписања -медоида је партиционисање око медоида ( PAM ) алгоритма као што следи : Иницијализација : насумично изабрати од тачака података као медоиде Везати сваку тачку података са најближим медоидом ( “ најближа ” овде је дефинисана користећи било које валидно метричко растојање , најчешће Еуклидово растојање , Менхетн растојање или Минковски растојање ) За сваки медоид За сваки не-медоид тачке података Замени и и израчунај укупну цену конфигурације Изабери конфигурацију најниже цене понављај коракеисве док нема промена на медоиду Демонстрација PAM-а Груписати следећи скуп тачака података од десет објеката у две групе . \ . Размотрити цкуп података од десет објеката на следећи начин : Корак Иницијализуј центара . Претпоставимо да је и Тако да су и означени као медоиди . Израчунати растојање тако да се удружи сваки скуп објеката са најближим медоидом . Цена је израчуната користећи Менхетн растојање ( Минковски растојање са ) . Цена најближег медоида је показана болдовано у табели . Тада групе постају : Како су тачке и најближе дакле оне формирају једну групу док остале тачке формирају другу групу . Тако да је укупна цена \ . Где је цена између било које две тачке тражена по формули где је било који скуп објеката , је медоид , и је димензија објекта , у овом случају је \ . Укупна цена је сума цена скупа објеката из својих медоида и из група : Корак Изабери један од не-медоида Претпоставимо да је Тако да су сада медоиди и Ако су и нови медоиди , израчунати укупну цену Користећи формулу из корака 1 Дакле , цена мењања медоида из у износи Тако да би померање на било лоша идеа , што значи да је претходни избор био добар . Тако да ми пробамо са још не-медоида и дођемо до закључка да је први избор био најбољи . Тако да се конфигурација не мења и алгоритам стаје овде . Може се десити да неке тачке података се помере из једне групе у другу у зависности од њиховог најближег медоида . У неким стандардима , k-медоиди показују боље резултате од k-means алгоритма . Пример је представљен на слици У већини времена к-медоид алгоритам рачуна растојање између објеката . Ако је квадратно препроцесирање важи , растојање матрица може бити прерачунато тако да достигне доследно убрзање . Видети за пример , где аутори такође хеуристично решење за одабир иницијалног mедоида . Упоредо проучавање K-means and k-медоид алгоритма је извршена за нормалну и јединствену дистрибуцију тачака података Показано је да за асимптотику већег скупа података к-медоид алгоритма потребно мање времена . Софтвер ELKI GNU R Види још Кластерска анализа k-means К-медијанска кластеризација Медоид Референце Спољашње везе -{ E.M . Mirkes , K-means and K-medoids ( Applet ) , University of Leicester , }- Статистички алгоритми Алгоритми кластеризације података