К-медоид

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

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

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

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

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

Демонстрација PAM-а

Груписати следећи скуп тачака података од десет објеката у две групе. Шаблон:Math.

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

Слика 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 – кластери након првог корака

Иницијализуј Шаблон:Math центара.

Претпоставимо да је Шаблон:Math и Шаблон:Math

Тако да су Шаблон:Math и Шаблон:Math означени као медоиди.

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

Шаблон:Math	Шаблон:Math		Објектни подаци (Шаблон:Math)		Цена (растојање)
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

Шаблон:Math	Шаблон:Math		Data objects (Шаблон:Math)		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

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

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

Тако да је укупна цена Шаблон:Math.

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

$\text{cost}(x,c)=\sum _{i=1}^d|x_i-c_i|$

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

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

$\begin{array}{cc}\text{total cost}& =\{\text{cost}((3,4),(2,6))+\text{cost}((3,4),(3,8))+\text{cost}((3,4),(4,7))\}\\ & +\{\text{cost}((7,4),(6,2))+\text{cost}((7,4),(6,4))+\text{cost}((7,4),(7,3))\\ & +\text{cost}((7,4),(8,5))+\text{cost}((7,4),(7,6))\}\\ & =(3+4+4)+(3+1+1+2+2)\\ & =20\\ \end{array}$

Корак 2

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

Изабери један од не-медоида Шаблон:Math

Претпоставимо да је Шаблон:Math

Тако да су сада медоиди Шаблон:Math и Шаблон:Math

Ако су Шаблон:Math и Шаблон:Math нови медоиди, израчунати укупну цену

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

Шаблон:Math	Шаблон:Math		Data objects (Шаблон:Math)		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

Шаблон:Math	Шаблон:Math		Data objects (Шаблон:Math)		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) конвергира очигледној структури кластера. Мали кругови су подаци, четири зрачне звезде су центроиди (средине), девет зрачних звезда су медоиди.

$\begin{array}{cc}\text{total cost}& =3+4+4+2+2+1+3+3\\ & =22\\ \end{array}$

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

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

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

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

Софтвер

• ELKI
• GNU R

Види још

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

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

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