Алгоритам 'k-медоида је алгоритам груписања који је повезан са k-means алгоритмом и „медоидшифт алгоритмом“. Оба и k-means and k-медоид алгоритми су партитивни (раздваја скуп података на групе) и оба покушавају да умање растојање између означених тачака у кластеру и тачке одређене као центар кластера. Насупрот k-means алгоритму, k-медоид бира тачке података као центре (медоиди или примерци) и ради са произвољном матрицом растојања између тачака података уместо са . Овај метод је био предложен 1987. за рад са нормом и другим дистанцама.
k-медоид је класична партитивна техника груписања кластера скупа података n објеката у k кластер познат као priori. Користан алат за одређивање k је силует.
Медоид може бити дефинисан као објекат кластера, чији просек различитости за све објекте у кластеру је минималан, то је највише центално лоцирана тачка у кластеру.
Најуобичајенија реализација груписања k-медоида је партиционисање око медоида (PAM) алгоритма као што следи:
Иницијализација: насумично изабрати k од n тачака података као медоиде
Замени m и o и израчунај укупну цену конфигурације
Изабери конфигурацију најниже цене
понављај кораке 2 и 4 све док нема промена на медоиду
Демонстрација PAM-а
Груписати следећи скуп тачака података од десет објеката у две групе. k = 2.
Размотрити цкуп података од десет објеката на следећи начин:
Слика 1.1 – дистрибуција података
X1
2
6
X2
3
4
X3
3
8
X4
4
7
X5
6
2
X6
6
4
X7
7
3
X8
7
4
X9
8
5
X10
7
6
Корак 1
Слика 1.2 – кластери након првог корака
Иницијализуј k центара.
Претпоставимо да је c1 = (3,4) и c2 = (7,4)
Тако да су c1 и c2 означени као медоиди.
Израчунати растојање тако да се удружи сваки скуп објеката са најближим медоидом. Цена је израчуната користећи Менхетн растојање (Минковски растојање са r = 1). Цена најближег медоида је показана болдовано у табели.
i
c1
Објектни подаци (Xi)
Цена (растојање)
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
c2
Data objects (Xi)
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
Тада групе постају:
Cluster1 = {(3,4)(2,6)(3,8)(4,7)}
Cluster2 = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}
Како су тачке (2,6)(3,8) и (4,7) најближе c1 дакле оне формирају једну групу док остале тачке формирају другу групу.
Тако да је укупна цена 20.
Где је цена између било које две тачке тражена по формули
где је x било који скуп објеката, c је медоид, и d је димензија објекта, у овом случају је 2.
Укупна цена је сума цена скупа објеката из својих медоида и из група:
Корак 2
Слика 1.3 – кластери након другог корака
Изабери један од не-медоида O'
Претпоставимо да је O' = (7,3)
Тако да су сада медоиди c1(3,4) и O'(7,3)
Ако су c1 и O' нови медоиди, израчунати укупну цену
Користећи формулу из корака 1
i
c1
Data objects (Xi)
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 (Xi)
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
Слика 2. К-медоиди насупрот к-средина. слике 2.1a-2.1f представљају типичне примере конвергенције k-средина ка локалном минимуму. Овај резултат кластеризовања k-срединама представља контрадикцију очигледној структури кластера скупа података. У овом примеру, алгоритам k-медоида (слике 2.2a-2.2h) са истим почетним положајем медоида (слика 2.2a) конвергира очигледној структури кластера. Мали кругови су подаци, четири зрачне звезде су центроиди (средине), девет зрачних звезда су медоиди.[1]
Дакле, цена мењања медоида из c2 у O' износи
Тако да би померање на O' било лоша идеа, што значи да је претходни избор био добар. Тако да ми пробамо са још не-медоида и дођемо до закључка да је први избор био најбољи. Тако да се конфигурација не мења и алгоритам стаје овде.
Може се десити да неке тачке података се помере из једне групе у другу у зависности од њиховог најближег медоида.
У неким стандардима, k-медоиди показују боље резултате од k-means алгоритма. Пример је представљен на слици 2.
У већини времена к-медоид алгоритам рачуна растојање између објеката. Ако је квадратно препроцесирање важи, растојање матрица може бити прерачунато тако да достигне доследно убрзање. Видети за пример,[2] где аутори такође хеуристично решење за одабир иницијалногk mедоида. Упоредо проучавање K-means and k-медоид алгоритма је извршена за нормалну и јединствену дистрибуцију тачака података[3] Показано је да за асимптотику већег скупа података к-медоид алгоритма потребно мање времена.
^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.
