knnsearch

Найдите k - ближайших соседей, использующих входные данные

Свернуть все на странице

Синтаксис

Idx = knnsearch(X,Y)
Idx = knnsearch(X,Y,Name,Value)
[Idx,D] = knnsearch(___)

Описание

пример

Idx = knnsearch(X,Y) находит ближайшего соседа в X для каждой точки запроса в Y и возвращает индексы ближайших соседей в Idx, а вектор-столбец. Idx имеет одинаковое число строк как Y.

Idx = knnsearch(X,Y,Name,Value) возвращает Idx с дополнительными опциями, заданными с помощью одного или нескольких аргументов пары "имя-значение". Для примера можно задать количество ближайших соседей для поиска и метрику расстояния, используемую в поиске.

пример

[Idx,D] = knnsearch(___) дополнительно возвращает матрицу D, с использованием любого из входных параметров в предыдущих синтаксисах. D содержит расстояния между каждым наблюдением в Y и соответствующие ближайшие наблюдения в X.

Примеры

свернуть все

Открыть Live Script

Найти пациентов в hospital набор данных, который наиболее сильно похож на пациентов в Y, в зависимости от возраста и веса.

Загрузите hospital набор данных.

load hospital;
X = [hospital.Age hospital.Weight];
Y = [20 162; 30 169; 40 168; 50 170; 60 171];   % New patients

Выполните knnsearch между X и Y для поиска индексов ближайших соседей.

Idx = knnsearch(X,Y);

Найти пациентов в X самый близкий по возрасту и весу к тем, кто в Y.

X(Idx,:)
ans = 5×2

    25   171
    25   171
    39   164
    49   170
    50   172
Открыть Live Script

Найдите 10 ближайших соседей в X в каждую точку Y, сначала с помощью метрики расстояния Минковского, а затем с помощью метрики расстояния Чебычева.

Загрузите набор данных радужки Фишера.

load fisheriris
X = meas(:,3:4);    % Measurements of original flowers
Y = [5 1.45;6 2;2.75 .75];  % New flower data

Выполните knnsearch между X и точки запроса Y используя дистанционные метрики Минковского и Чебычева.

[mIdx,mD] = knnsearch(X,Y,'K',10,'Distance','minkowski','P',5);
[cIdx,cD] = knnsearch(X,Y,'K',10,'Distance','chebychev');

Визуализируйте результаты двух ближайших соседних поисков. Постройте график обучающих данных. Постройте график точек запроса с помощью маркера X. Используйте круги, чтобы обозначить ближайших соседей Минковского. Используйте пентаграммы для обозначения ближайших соседей по Чебычеву.

gscatter(X(:,1),X(:,2),species)
line(Y(:,1),Y(:,2),'Marker','x','Color','k',...
   'Markersize',10,'Linewidth',2,'Linestyle','none')
line(X(mIdx,1),X(mIdx,2),'Color',[.5 .5 .5],'Marker','o',...
   'Linestyle','none','Markersize',10)
line(X(cIdx,1),X(cIdx,2),'Color',[.5 .5 .5],'Marker','p',...
   'Linestyle','none','Markersize',10)
legend('setosa','versicolor','virginica','query point',...
'minkowski','chebychev','Location','best')

Figure contains an axes. The axes contains 6 objects of type line. These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

Входные параметры

свернуть все

Входные данные, заданные как числовая матрица. Строки X соответствуют наблюдениям, а столбцы - переменным.

Типы данных: single | double

Точки запроса, заданные как числовая матрица. Строки Y соответствуют наблюдениям, а столбцы - переменным. Y должно иметь одинаковое число столбцов как X.

Типы данных: single | double

Аргументы в виде пар имя-значение

Задайте необязательные разделенные разделенными запятой парами Name,Value аргументы. Name - имя аргумента и Value - соответствующее значение. Name должны находиться внутри кавычек. Можно задать несколько аргументов в виде пар имен и значений в любом порядке Name1,Value1,...,NameN,ValueN.

Пример: knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock') ищет 10 ближайших соседей, включая галстуки и использование городской блочной дистанции.

Количество ближайших соседей, которых можно найти в X для каждой точки в Y, заданная как разделенная разделенными запятой парами, состоящая из 'K' и положительное целое число.

Пример: 'K',10

Типы данных: single | double

Флаг для включения всех ближайших соседей, которые имеют одинаковое расстояние от точек запроса, заданный как разделенная разделенными запятой парами, состоящая из 'IncludeTies' и false (0) или true (1).

Если 'IncludeTies' является false, затем knnsearch выбирает наблюдение с наименьшим индексом среди наблюдений, которые имеют то же расстояние от точки запроса.

Если 'IncludeTies' является true, затем:

  • knnsearch включает всех ближайших соседей, расстояния которых равны k-му наименьшему расстоянию в выходных аргументах. Чтобы задать k, используйте 'K' аргумент пары "имя-значение".

  • Idx и D m -by- 1 массивы ячеек, такие что каждая камера содержит вектор, по меньшей мере, k индексов и расстояний, соответственно. Каждый вектор в D содержит расстояния, расположенные в порядке возрастания. Каждая строка в Idx содержит индексы ближайших соседей, соответствующие расстояниям в D.

Пример: 'IncludeTies',true

Метод поиска по ближайшему соседу, заданный как разделенная разделенными запятой парами, состоящая из 'NSMethod' и одно из этих значений.

  • 'kdtree' - Создает и использует K d-дерево для поиска ближайших соседей. 'kdtree' является значением по умолчанию, когда количество столбцов в X меньше или равно 10, X не разрежен, и метрика расстояния 'euclidean', 'cityblock', 'chebychev', или 'minkowski'. В противном случае значение по умолчанию является 'exhaustive'.

    Значение 'kdtree' действителен только, когда метрика расстояния является одной из четырех метрик, отмеченных выше.

  • 'exhaustive' - Использует алгоритм исчерпывающего поиска путем вычисления значений расстояния от всех точек в X в каждую точку Y.

Пример: 'NSMethod','exhaustive'

Метрика расстояния knnsearch использует, заданный как разделенная разделенными запятой парами, состоящая из 'Distance' и одно из значений в этой таблице или указателе на функцию.

ЗначениеОписание
'euclidean'Евклидово расстояние.
'seuclidean'Стандартизированное евклидово расстояние. Каждая координата различия между строками в X и матрицу запросов Y масштабируется путем деления на соответствующий элемент стандартного отклонения, вычисленного из X. Чтобы задать другое масштабирование, используйте 'Scale' аргумент пары "имя-значение".
'cityblock'Расстояние между блоками.
'chebychev'Расстояние Чебычева (максимальное различие координат).
'minkowski'Расстояние Минковского. Экспонента по умолчанию является 2. Чтобы задать другую экспоненту, используйте 'P' аргумент пары "имя-значение".
'mahalanobis'Расстояние Махаланобиса, вычисленное с помощью положительной определенной ковариационной матрицы. Чтобы изменить значение ковариационной матрицы, используйте 'Cov' аргумент пары "имя-значение".
'cosine'Один минус косинус включенного угла между наблюдениями (обрабатывается как векторы).
'correlation'Один минус выборка линейной корреляции между наблюдениями (рассматривается как последовательности значений).
'spearman'Один минус выборки корреляции ранга Спирмана между наблюдениями (рассматриваются как последовательности значений).
'hamming'Расстояние Хемминга, которое является процентом различий координат.
'jaccard'Один минус коэффициент Жаккара, который является процентом ненулевых координат, которые различаются.

Можно также задать указатель на функцию для пользовательской метрики расстояния при помощи @ (например, @distfun). Пользовательская функция расстояния должна:

  • Иметь форму function D2 = distfun(ZI,ZJ).

  • Примите за аргументы:

    • Вектор A 1 n байта ZI содержащий одну строку из X или из точек запроса Y.

    • Матрица m2 -by n ZJ содержит несколько строк X или Y.

  • Верните вектор m2 -by-1 расстояний D2, чьи jth-й элемент - расстояние между наблюдениями ZI и ZJ(j,:).

Для получения дополнительной информации см. «Метрики расстояния».

Пример: 'Distance','chebychev'

Экспонента для метрики расстояния Минковского, заданная как разделенная разделенными запятой парами, состоящая из 'P' и положительная скалярная величина.

Этот аргумент действителен только в том случае, если 'Distance' является 'minkowski'.

Пример: 'P',3

Типы данных: single | double

Ковариационная матрица для метрики расстояния Махаланобиса, заданная как разделенная разделенными запятой парами, состоящая из 'Cov' и положительно определенную матрицу.

Этот аргумент действителен только в том случае, если 'Distance' является 'mahalanobis'.

Пример: 'Cov',eye(4)

Типы данных: single | double

Значение параметров для стандартизированной метрики Евклидова расстояния, заданное как разделенная разделенными запятой парами, состоящая из 'Scale' и неотрицательный числовой вектор. 'Scale' имеет длину, равную количеству столбцов в X. Когда knnsearch вычисляет стандартизированное евклидово расстояние, каждую координату X масштабируется соответствующим элементом 'Scale', как и каждая точка запроса. Этот аргумент действителен только при 'Distance' является 'seuclidean'.

Пример: 'Scale',quantile(X,0.75) - quantile(X,0.25)

Типы данных: single | double

Максимальное количество точек данных в конечном узле K d-дерева, заданное как разделенная разделенными запятой парами, состоящая из 'BucketSize' и положительное целое число. Этот аргумент действителен только при NSMethod является 'kdtree'.

Пример: 'BucketSize',20

Типы данных: single | double

Флаг для сортировки возвращенных индексов в соответствии с расстоянием, заданный как разделенная разделенными запятой парами, состоящая из 'SortIndices' и любой из них true (1) или false (0).

Для более высокой эффективности можно задать SortIndices на false когда следующее имеет значение true:

  • Y содержит много наблюдений, которые имеют много ближайших соседей в X.

  • NSMethod является 'kdtree'.

  • IncludeTies является false.

В этом случае, knnsearch возвращает индексы ближайших соседей не в определенном порядке. Когда SortIndices является trueфункция упорядочивает индексы ближайшего соседа в порядке возрастания по расстоянию.

SortIndices является true по умолчанию. Когда NSMethod является 'exhaustive' или IncludeTies является trueфункция всегда сортирует индексы.

Пример: 'SortIndices',false

Типы данных: logical

Выходные аргументы

свернуть все

Индексы входных данных ближайших соседей, возвращенные как числовая матрица или массив ячеек из числовых векторов.

  • Если вы не задаете IncludeTies (false по умолчанию), затем Idx является m -by k числовой матрицей, где m - количество строк в Y и k количество искомых ближайших соседей. Idx(j,i) указывает, что X(Idx(j,i),:) является одним из k ближайших наблюдений в X к точке запроса Y(j,:).

  • Если вы задаете 'IncludeTies',true, затем Idx является m -by- 1 массив ячеек такой, что камера j (Idx{j}) содержит вектор, по меньшей мере, k индексов ближайших наблюдений в X к точке запроса Y(j,:).

Если SortIndices является true, затем knnsearch устанавливает индексы в порядке возрастания по расстоянию.

Расстояния ближайших соседей до точек запроса, возвращенные как числовая матрица или массив ячеек из числовых векторов.

  • Если вы не задаете IncludeTies (false по умолчанию), затем D является m -by k числовой матрицей, где m - количество строк в Y и k количество искомых ближайших соседей. D(j,i) - расстояние между X(Idx(j,i),:) и Y(j,:) относительно метрики расстояния.

  • Если вы задаете 'IncludeTies',true, затем D является m -by- 1 массив ячеек такой, что камера j (D{j}) содержит вектор не менее k расстояний ближайших наблюдений в X к точке запроса Y(j,:).

Если SortIndices является true, затем knnsearch устанавливает расстояния в порядке возрастания.

Совет

  • Для фиксированного положительного целого k, knnsearch находит k точки в X которые являются ближайшими к каждой точке в Y. Чтобы найти все точки в X в пределах фиксированного расстояния от каждой точки в Y, использование rangesearch.

  • knnsearch не сохраняет объект поиска. Чтобы создать объект поиска, используйте createns.

Алгоритмы

Для получения информации об определенном алгоритме поиска смотрите k-ближайших соседей Search и Radius Search.

Альтернативная функциональность

Если вы устанавливаете knnsearch функции 'NSMethod' Аргумент пары "имя-значение" к соответствующему значению ('exhaustive' для исчерпывающего алгоритма поиска или 'kdtree' для K алгоритма d-tree), тогда результаты поиска эквивалентны результатам, полученным путем проведения поиска на расстоянии с помощью knnsearch функция объекта. В отличие от knnsearch функции, knnsearch функция объекта требует ExhaustiveSearcher или KDTreeSearcher объект модели.

Ссылки

[1] Friedman, J. H., J. Bentely, and R. A. Finkel. «Алгоритм нахождения оптимальных соответствий за логарифмическое ожидаемое время». Транзакции ACM на математическом программном обеспечении 3, № 3 (1977): 209-226.

Расширенные возможности

.

См. также

| | |

Темы

Введенный в R2010a

Statistics and Machine Learning Toolbox документация

Поддержка

Для просмотра документации необходимо авторизоваться на сайте