Участник:Denemmy/Partitioning Around Medoids (Алгоритм): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 13: Строка 13:
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
  
−
''Реализация алгоритма на python'':
+
''Псевдокод алгоритма'':
  
−
  1  def kMedoids(D, k, tmax=100):
+
  1  функция PAM(D, k, tmax=100):
−
  2      <span style="color:#408080"># determine dimensions of distance matrix D</span>
+
  2      <span style="color:#408080"># D - матрица расстояний, k - число кластеров, tmax - маскимальное число итераций</span>
−
  3      m, n = D.shape
+
  3      выполнить фазу BUILD, получить множество метоидов M и множество не-метоидов L
−
  4      <span style="color:#408080"># build phase: initialize an array of k medoid indices</span>
+
  4      вычислить значение целевой функции F
−
  5      M = np.sort(np.random.choice(n, k))
+
  5      для t = 0..tmax-1:
−
  6     <span style="color:#408080"># create a copy of the array of medoid indices</span>
+
  6         выполнить фазу SWAP, вычислить значение целевой функции F'
−
  7     Mnew = np.copy(M)
+
  7         delta = F' - F
−
  8     <span style="color:#408080"># initialize a dictionary to represent clusters</span>
+
  8         если delta > 0:
−
  9     C = {}
+
  9             обновить множества M и L
−
  10     for t in xrange(tmax):
+
  10             F = F'
−
  11        <span style="color:#408080"># determine clusters, i.e. arrays of data indices</span>
+
  11        иначе:
−
  12         J = np.argmin(D[:,M], axis=1)
+
  12             выйти из цикла
−
  13         for kappa in range(k):
+
  13    вернуть М
−
14            C[kappa] = np.where(J==kappa)[0]
 
−
15        <span style="color:#408080"># update cluster medoids</span>
 
−
16        for kappa in range(k):
 
−
17            J = np.mean(D[np.ix_(C[kappa],C[kappa])],axis=1)
 
−
18            j = np.argmin(J)
 
−
19            Mnew[kappa] = C[kappa][j]
 
−
20        np.sort(Mnew)
 
−
21        <span style="color:#408080"># check for convergence</span>
 
−
22        if np.array_equal(M, Mnew):
 
−
23            break
 
−
24        M = np.copy(Mnew)
 
−
25     else:
 
−
26        <span style="color:#408080"># final update of cluster memberships</span>
 
−
27        J = np.argmin(D[:,M], axis=1)
 
−
28        for kappa in range(k):
 
−
29            C[kappa] = np.where(J==kappa)[0]
 
−
30    <span style="color:#408080"># return results</span>
 
−
31    return M, C
 
  
 
=== Последовательная сложность алгоритма===
 
=== Последовательная сложность алгоритма===

Версия 11:47, 15 октября 2016

Авторы: Галеев Д.Ф, Запутляев И.

Содержание

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Кластеризация - это задача из области машинного обучения, которая заключается в том, что нужно выделить некоторое число групп в исходном множестве, в каждой из которых содержатся схожие по некоторой метрике элементы.
Partitioning Around Medoids (PAM) - это одна из реализаций алгоритма кластеризации k-medoids. PAM использует жадный алгоритм, который может не найти оптимального решения, однако он гораздо быстрее полного перебора.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

Псевдокод алгоритма: 

1  функция PAM(D, k, tmax=100):
2      # D - матрица расстояний, k - число кластеров, tmax - маскимальное число итераций
3      выполнить фазу BUILD, получить множество метоидов M и множество не-метоидов L
4      вычислить значение целевой функции F
5      для t = 0..tmax-1:
6          выполнить фазу SWAP, вычислить значение целевой функции F'
7          delta = F' - F
8          если delta > 0:
9              обновить множества M и L
10             F = F'
11         иначе:
12             выйти из цикла
13     вернуть М

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

2.7.1 Открытое программное обеспечение

2.7.2 Проприетарное программное обеспечение

3 Литература

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Denemmy/Partitioning_Around_Medoids_(Алгоритм)&oldid=8765