Участник:Denemmy/Partitioning Around Medoids (Алгоритм)

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

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

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

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

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

Реализация алгоритма на python:

1  def kMedoids(D, k, tmax=100):
2      # determine dimensions of distance matrix D
3      m, n = D.shape
4      # randomly initialize an array of k medoid indices
5      M = np.sort(np.random.choice(n, k))
6      # create a copy of the array of medoid indices
7      Mnew = np.copy(M)
8      # initialize a dictionary to represent clusters
9      C = {}
10     for t in xrange(tmax):
11         # determine clusters, i.e. arrays of data indices
12         J = np.argmin(D[:,M], axis=1)
13         for kappa in range(k):
14             C[kappa] = np.where(J==kappa)[0]
15         # update cluster medoids
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         # check for convergence
22         if np.array_equal(M, Mnew):
23             break
24         M = np.copy(Mnew)
25     else:
26         # final update of cluster memberships
27         J = np.argmin(D[:,M], axis=1)
28         for kappa in range(k):
29             C[kappa] = np.where(J==kappa)[0]
30    # return results
31    return M, C