Лабораторная работа 3 Операции над массивами и создание структурированных массивов
Пример задачи: K ближайших соседей
жүктеу/скачать 0,56 Mb.
|
лаб 3
| Пример задачи: K ближайших соседей
Давайте вкратце рассмотрим, как можно использовать функцию np.argpartition по нескольким осям для поиска ближайших соседей каждой точки из определенного набора. Начнем с создания случайного набора из десяти точек на двумерной плоскости. По стандартным соглашениям образуем из них массив 10 × 2: Чтобы наглядно представить себе расположение этих точек, нарисуем для них диаграмму рассеяния (рис. 4): Теперь можно вычислить расстояние между всеми парами точек. Вспоминаем, что квадрат расстояния между двумя точками равен сумме квадратов расстояний между ними по каждой из координат. Воспользовавшись возможностями эффективного транслирования и агрегирования, предоставляемыми библиотекой NumPy, мы можем вычислить матрицу квадратов расстояний с помощью одной строки кода: Рис. 4. Визуализация точек в примере K соседей Эта операция довольно сложна по синтаксису и может привести вас в замешательство, если вы плохо знакомы с правилами транслирования библиотеки NumPy. В подобных случаях полезно разбить операцию на отдельные шаги: На всякий случай для контроля проверим, что диагональ матрицы (то есть набор расстояний между каждой точкой и ей самой) состоит из нулей: Проверка пройдена! Теперь, получив матрицу квадратов расстояний между взятыми попарно точками, мы можем воспользоваться функцией np.argsort для сортировки по каждой строке. Крайние слева столбцы будут представлять собой индексы ближайших соседей: Обратите внимание, что первый столбец представляет собой числа с 0 до 9 в порядке возрастания: это происходит из-за того, что ближайший сосед каждой точки – она сама, как и можно было ожидать. Выполнив полную сортировку, мы проделали лишнюю работу. Если нас интересовали K ближайших соседей, было достаточно секционировать все строки так, чтобы сначала шли K+1 минимальных квадратов расстояний, а большие расстояния заполняли оставшиеся позиции массива. Сделать это можно с помощью функции np.argpartition: Чтобы визуализировать эту сетку соседей, выведем на диаграмму точки вдоль линий, связывающих каждую точку с ее ближайшими двумя соседями (рис. 5): От каждой нарисованной на диаграмме точки ведут линии к двум ее ближайшим соседям. На первый взгляд может показаться странным, что из некоторых точек отходит более двух линий. Дело в том, что, если точка A – один из двух ближайших соседей точки B, вовсе не обязательно, что точка B – один из двух ближайших соседей точки A. Хотя применяемые при этом транслирование и построчная сортировка могут показаться более запутанным подходом, чем написание цикла, оказывается, что такой способ работы с подобными данными на языке Python весьма эффективен. Как бы ни было заманчиво сделать то же самое, вручную организовав цикл по данным и сортировку каждого набора соседей отдельно, получившийся в итоге алгоритм почти наверняка будет работать медленнее, чем рассмотренная выше векторизованная версия. Красота такого подхода – в его независимости от размера входных данных: можно с одинаковой легкостью вычислить соседей среди 100 или 1 000 000 точек в любом количестве измерений, и код будет выглядеть точно так же. Рис. 5. Визуализация соседей каждой точки Для выполнения поисков соседей в очень больших массивах данных существуют основанные на деревьях и/или аппроксимационные алгоритмы, масштабирующиеся как O[N log N]: или даже лучше, в отличие от грубого подхода O[N2]. Один из примеров таких алгоритмов – K-мерное дерево (KD-tree), реализованное в библиотеке Scikit-Learn. Задача Ваша задача заключается в пониманиях всего данного материала и объяснения любого отрезка из данного материала своему преподавателю, также реализуйте примеры задач, код самим придется печатать из скринов и сделать вывод по всему уроку. жүктеу/скачать 0,56 Mb. Достарыңызбен бөлісу:
|