Участник: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


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

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

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

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

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

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

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

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

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

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

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

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     вернуть М

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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