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