Back

ⓘ К-медоид




                                     

ⓘ К-медоид

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

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

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

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

  • За сваки медоид m
  • Замени m и o и израчунај укупну цену конфигурације
  • Везати сваку тачку података са најближим медоидом
  • Иницијализација: насумично изабрати k од n тачака података као медоиде
  • За сваки не-медоид тачке података o
  • Изабери конфигурацију најниже цене
  • понављај кораке 2 и 4 све док нема промена на медоиду
                                     

1.1. Демонстрација PAM-а Корак 1

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

Претпоставимо да је c 1 = 3.4 и c 2 = 7.4

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

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

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

Cluster 1 = {3.42.63.84.7}

Cluster 2 = {7.46.26.47.38.57.6}

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

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

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

cost x, c = ∑ i = 1 d | x i − c i | {\displaystyle {\mbox{cost}}x,c=\sum _{i=1}^{d}|x_{i}-c_{i}|}

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

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

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

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

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

Users also searched:

...