Участник:Антон Тодуа/Partitioning Around Medoids (PAM): различия между версиями
| Строка 16: | Строка 16: | ||
=== Информационный граф === | === Информационный граф === | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| − | + | == Входные и выходные данные алгоритма == | |
| + | '''Входные данные''': | ||
| + | |||
| + | 1. Матрица непохожести объектов кластеризации (dissimilarity matrix) <math>D</math> (элементы <math>d_{ij}</math>). | ||
| + | Дополнительные ограничения: | ||
| + | * <math>D</math> – симметрическая матрица порядка <math>N</math>, т.е. <math>d_{ij}= a_{ji}, i, j = 1, \ldots, N</math> | ||
| + | * <math>D</math> – содержит нули на главной диагонали, т.е. <math>d_{ii}= 0, i = 1, \ldots, N</math> | ||
| + | |||
| + | 2. <math>K</math> - число кластеров, на которое следует разбить исходные объекты | ||
| + | |||
| + | '''Объём входных данных''': <math>\frac{N (N - 1)}{2}</math> (в силу симметричности и нулевой главной диагонали достаточно хранить только над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом. | ||
| + | |||
| + | '''Выходные данные''': <math>N</math> чисел <math>k_{1}, k_{2}, \ldots, k_{N}</math>, где <math>k_{i}</math> - целое число, соответствующее кластеру <math>i</math>-го объекта. | ||
| + | |||
| + | '''Объём выходных данных''': <math>N</math> | ||
| + | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 23:46, 10 октября 2016
Основные авторы описания: Тодуа А.Р., Гусева Ю.В.
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Самый распространённый вариант реализации [math]k[/math]-medoids называется PAM (Partitioning Around Medoids). Он представляет собой «жадный» алгоритм с очень неэффективной эвристикой. Данный метод был предложен Кауфманом в 1987 году.
Алгоритм начинается с выбора набора данных, состоящих из медоидов и остальных объектов. После выбора [math]k[/math] произвольных объектов в качестве медоидов, необходимо для каждой пары [math]{x_i}[/math] и [math]{m_k}[/math] вычислить значение [math]S({x_{i}}{m_{k}})[/math]. По ходу выполнения алгоритма происходит итеративная замена одного из медоидов [math]x_i[/math] одним из остальных объектов [math]m_k[/math], если посчитанное ранее значение [math]S[/math] меньше нуля. Процесс будет повторятся, пока медоиды не стабилизируются.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
2 Входные и выходные данные алгоритма
Входные данные:
1. Матрица непохожести объектов кластеризации (dissimilarity matrix) [math]D[/math] (элементы [math]d_{ij}[/math]). Дополнительные ограничения:
- [math]D[/math] – симметрическая матрица порядка [math]N[/math], т.е. [math]d_{ij}= a_{ji}, i, j = 1, \ldots, N[/math]
- [math]D[/math] – содержит нули на главной диагонали, т.е. [math]d_{ii}= 0, i = 1, \ldots, N[/math]
2. [math]K[/math] - число кластеров, на которое следует разбить исходные объекты
Объём входных данных: [math]\frac{N (N - 1)}{2}[/math] (в силу симметричности и нулевой главной диагонали достаточно хранить только над/поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом.
Выходные данные: [math]N[/math] чисел [math]k_{1}, k_{2}, \ldots, k_{N}[/math], где [math]k_{i}[/math] - целое число, соответствующее кластеру [math]i[/math]-го объекта.
Объём выходных данных: [math]N[/math]
