10
правок
Изменения
Ссылки внутри викиконспетов
=== Параллелизм в методе k ближайших соседей ===
Основное время работы [[Метрический классификатор и метод ближайших соседей|метода k ближайших соседей ]] составляет поиск ближайших соседей.
Так как расстояния до разных объектов независимы, то можно разбить объекты на группы, параллельно решить задачу во всех группах, а потом объединить результат<ref>[http://ceres-journal.eu/download.php?file=2019_01_01.pdf Implementation of a Parallel K-Nearest Neighbor Algorithm Using MPI]</ref>.
Альтернативный подход — параллельная сортировка всех объектов, например, с использованием битонной сортировки<ref>[https://users.cs.duke.edu/~nikos/reprints/knn-TR-CS-2012-03.pdf Parallel Search of k-Nearest Neighbors with Synchronous Operations]</ref>.
=== Параллелизм в методе опорных веторов ===
Вычислительная сложность [[Метод опорных векторов (SVM)|метода опорных векторов ]] заключается в минимизации квадратичной функции.
Первый вариант распараллеливания задачи — добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMO<ref>[https://publikationen.uni-tuebingen.de/xmlui/bitstream/handle/10900/49015/pdf/tech_21.pdf Parallel Support Vector Machines]</ref>.
Второй подход — запись алгоритма через матричные операции, которые легко параллелизируемы<ref>[https://www.researchgate.net/publication/6265163_Multiplicative_Updates_for_Nonnegative_Quadratic_Programming Multiplicative Updates for Nonnegative Quadratic Programming]</ref>.
