knnsearch

Найдите k - самые близкие соседи, использующие объект искателя

Описание

пример

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

пример

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

пример

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

Примеры

свернуть все

knnsearch принимает ExhaustiveSearcher или KDTreeSearcher объекты модели, чтобы искать обучающие данные самых близких соседей данных о запросе. ExhaustiveSearcher модель вызывает исчерпывающий алгоритм искателя и KDTreeSearcher модель задает Kd-дерево, который knnsearch использование, чтобы искать самых близких соседей.

Загрузите ирисовый набор данных Фишера. Случайным образом зарезервируйте пять наблюдений из данных для данных о запросе.

load fisheriris
rng(1); % For reproducibility
n = size(meas,1);
idx = randsample(n,5);
X = meas(~ismember(1:n,idx),:); % Training data
Y = meas(idx,:);                % Query data

Переменная meas содержит 4 предиктора.

Вырастите четырехмерное Kd-дерево по умолчанию.

MdlKDT = KDTreeSearcher(X)
MdlKDT = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'euclidean'
    DistParameter: []
                X: [145x4 double]

MdlKDT KDTreeSearcher объект модели. Можно изменить его перезаписываемые свойства с помощью записи через точку.

Подготовьте исчерпывающего самого близкого соседнего искателя.

MdlES = ExhaustiveSearcher(X)
MdlES = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [145x4 double]

MdlKDT ExhaustiveSearcher объект модели. Это содержит опции, такие как метрика расстояния, чтобы использовать, чтобы найти самых близких соседей.

В качестве альтернативы можно вырастить Kd-дерево или подготовить исчерпывающего самого близкого соседнего искателя, использующего createns.

Ищите обучающие данные самые близкие соседние индексы, которые соответствуют каждому наблюдению запроса. Проведите оба типа поисковых запросов с помощью настроек по умолчанию. По умолчанию количеством соседей, чтобы искать на наблюдение запроса является 1.

IdxKDT = knnsearch(MdlKDT,Y);
IdxES = knnsearch(MdlES,Y);
[IdxKDT IdxES]
ans = 5×2

    17    17
     6     6
     1     1
    89    89
   124   124

В этом случае результатами поиска является то же самое.

Вырастите Kd-дерево самый близкий соседний объект искателя при помощи createns функция. Передайте объект и запросите данные к knnsearch функционируйте, чтобы найти k - ближайших соседей.

Загрузите ирисовый набор данных Фишера.

load fisheriris

Удалите пять ирисовых диафрагм случайным образом из данных о предикторе, чтобы использовать в качестве набора запроса.

rng(1);                     % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
tIdx = ~ismember(1:n,qIdx); % Indices of training data
Q = meas(qIdx,:);
X = meas(tIdx,:);

Вырастите четырехмерное Kd-дерево с помощью обучающих данных. Задайте расстояние Минковскего для нахождения самых близких соседей.

Mdl = createns(X,'Distance','minkowski')
Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [145x4 double]

Поскольку X имеет четыре столбца, и метрикой расстояния является Минковский, createns создает KDTreeSearcher объект модели по умолчанию. Экспонентой расстояния Минковскего является 2 по умолчанию.

Найдите индексы обучающих данных (Mdl.X) это - два самых близких соседа каждой точки в данных о запросе (Q).

IdxNN = knnsearch(Mdl,Q,'K',2)
IdxNN = 5×2

    17     4
     6     2
     1    12
    89    66
   124   100

Каждая строка IdxNN соответствует наблюдению данных о запросе, и порядок следования столбцов соответствует порядку самых близких соседей относительно возрастающего расстояния. Например, на основе расстояния Минковскего, второго самого близкого соседа Q(3,:) X(12,:).

Загрузите ирисовый набор данных Фишера.

load fisheriris

Удалите пять ирисовых диафрагм случайным образом из данных о предикторе, чтобы использовать в качестве набора запроса.

rng(4);                     % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
X = meas(~ismember(1:n,qIdx),:);
Y = meas(qIdx,:);

Вырастите четырехмерное Kd-дерево с помощью обучающих данных. Задайте расстояние Минковскего для нахождения самых близких соседей.

Mdl = KDTreeSearcher(X);

Mdl KDTreeSearcher объект модели. По умолчанию метрика расстояния для нахождения самых близких соседей является Евклидовой метрикой.

Найдите индексы обучающих данных (X) это - семь самых близких соседей каждой точки в данных о запросе (Y).

[Idx,D] = knnsearch(Mdl,Y,'K',7,'IncludeTies',true);

Idx и D массивы ячеек с пятью элементами векторов, с каждым вектором, имеющим по крайней мере семь элементов.

Отобразите длины векторов в Idx.

cellfun('length',Idx)
ans = 5×1

     8
     7
     7
     7
     7

Поскольку ячейка 1 содержит вектор с длиной, больше, чем k = 7, наблюдение запроса 1 (Y(1,:)) одинаково близко к по крайней мере двум наблюдениям в X.

Отобразите индексы самых близких соседей Y(1,:) и их расстояния.

nn5 = Idx{1}
nn5 = 1×8

    91    98    67    69    71    93    88    95

nn5d = D{1}
nn5d = 1×8

    0.1414    0.2646    0.2828    0.3000    0.3464    0.3742    0.3873    0.3873

Учебные наблюдения 88 и 95 на расстоянии в 0,3873 см от наблюдения запроса 1.

Обучите два KDTreeSearcher модели с помощью различных метрик расстояния, и сравнивают k - ближайших соседей данных о запросе для этих двух моделей.

Загрузите ирисовый набор данных Фишера. Рассмотрите лепестковые измерения как предикторы.

load fisheriris
X = meas(:,3:4); % Predictors
Y = species;     % Response

Обучите KDTreeSearcher объект модели при помощи предикторов. Задайте расстояние Минковскего с экспонентой 5.

KDTreeMdl = KDTreeSearcher(X,'Distance','minkowski','P',5)
KDTreeMdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 5
                X: [150x2 double]

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

newpoint = [5 1.45];
[IdxMk,DMk] = knnsearch(KDTreeMdl,newpoint,'k',10);
[IdxCb,DCb] = knnsearch(KDTreeMdl,newpoint,'k',10,'Distance','chebychev');

IdxMk и IdxCb 1 10 матрицы, содержащие индексы строки X соответствие самым близким соседям newpoint использование расстояний Минковскего и Чебычева, соответственно. Элемент (1,1) является самым близким, элемент (1,2) является следующим самым близким и так далее.

Отобразите на графике обучающие данные, точку запроса и самых близких соседей.

figure;
gscatter(X(:,1),X(:,2),Y);
title('Fisher''s Iris Data -- Nearest Neighbors');
xlabel('Petal length (cm)');
ylabel('Petal width (cm)');
hold on
plot(newpoint(1),newpoint(2),'kx','MarkerSize',10,'LineWidth',2);   % Query point 
plot(X(IdxMk,1),X(IdxMk,2),'o','Color',[.5 .5 .5],'MarkerSize',10); % Minkowski nearest neighbors
plot(X(IdxCb,1),X(IdxCb,2),'p','Color',[.5 .5 .5],'MarkerSize',10); % Chebychev nearest neighbors
legend('setosa','versicolor','virginica','query point',...
   'minkowski','chebychev','Location','Best');

Увеличьте масштаб интересных мест.

h = gca; % Get current axis handle.
h.XLim = [4.5 5.5];
h.YLim = [1 2];
axis square;

Несколько наблюдений равны, который является, почему только восемь самых близких соседей идентифицированы в графике.

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

свернуть все

Самый близкий соседний искатель, заданный как ExhaustiveSearcher или KDTreeSearcher объект модели, соответственно.

Если Mdl ExhaustiveSearcher модель, затем knnsearch поиски самых близких соседей, использующих исчерпывающий поиск. В противном случае, knnsearch использует выращенное d-дерево K, чтобы искать самых близких соседей.

Запросите данные, заданные как числовая матрица.

Y m-by-K матрица. Строки Y соответствуйте наблюдениям (т.е. примеры), и столбцы соответствуют предикторам (т.е. переменные или функции). Y должен иметь одинаковое число столбцов как обучающие данные, хранимые в Mdl.X.

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

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

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

Пример: 'K',2,'Distance','minkowski' задает, чтобы найти двух самых близких соседей Mdl.X к каждой точке в Y и использовать метрику расстояния Минковскего.

Для обоих самых близких соседних искателей

свернуть все

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

Для обоих типов самых близких соседних искателей, knnsearch поддержки эти метрики расстояния.

ЗначениеОписание
'chebychev'Расстояние Чебычева (максимум координируют различие).
'cityblock'Расстояние городского квартала.
'euclidean'Евклидово расстояние.
'minkowski'Расстояние Минковскего. Экспонента по умолчанию равняется 2. Чтобы задать различную экспоненту, используйте 'P' аргумент пары "имя-значение".

Если Mdl ExhaustiveSearcher объект модели, затем knnsearch также поддержки эти метрики расстояния.

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

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

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

  • Возьмите в качестве аргументов:

    • 1 K векторным ZI содержа одну строку от Mdl.X или Y, где K является количеством столбцов Mdl.X.

    • m-by-K матричный ZJ содержа несколько строк Mdl.X или Y, где m является положительным целым числом.

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

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

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

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

Если IncludeTies trueзатем:

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

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

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

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

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

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

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

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

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

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

Для d-дерева K самые близкие соседние искатели

свернуть все

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

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

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

  • Mdl KDTreeSearcher объект модели.

  • IncludeTies false.

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

SortIndices true по умолчанию. Когда Mdl ExhaustiveSearcher объект модели или IncludeTies true, функция всегда сортирует индексы.

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

Типы данных: логический

Для исчерпывающих самых близких соседних искателей

свернуть все

Ковариационная матрица для метрики расстояния Mahalanobis, заданной как разделенная запятой пара, состоящая из 'Cov' и положительная определенная матрица. Cov K-by-K матрица, где K является количеством столбцов Mdl.X. Если вы задаете Cov и не задавайте 'Distance','mahalanobis', затем knnsearch возвращает сообщение об ошибке.

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

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

Значение масштабного коэффициента для стандартизированной Евклидовой метрики расстояния, заданной как разделенная запятой пара, состоящая из 'Scale' и неотрицательный числовой вектор. Scale имеет длину K, где K является количеством столбцов Mdl.X.

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

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

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

Примечание

Если вы задаете 'Distance', 'Cov', 'P', или 'Scale', затем Mdl.Distance и Mdl.DistParameter не изменяйте значение.

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

свернуть все

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

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

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

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

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

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

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

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

Советы

knnsearch находит k (положительное целое число) точками в Mdl.X это - k - самый близкий для каждого Y точка. В отличие от этого rangesearch находит все точки в Mdl.X это - на расстоянии r (положительная скалярная величина) каждого Y точка.

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

  • knnsearch объектная функция, которая требует ExhaustiveSearcher или KDTreeSearcher объект модели и данные о запросе. При эквивалентных условиях, knnsearch объектная функция возвращает те же результаты как knnsearch функционируйте, когда вы зададите аргумент пары "имя-значение" 'NSMethod','exhaustive' или 'NSMethod','kdtree', соответственно.

  • Для k - самая близкая классификация соседей, смотрите fitcknn и ClassificationKNN.

Ссылки

[1] Фридман, J. H. Bentely, J. и Finkel, R. A. (1977). “Алгоритм для Нахождения Лучших Соответствий в Логарифмическое Ожидаемое Время”. Транзакции ACM на Издании 3 Mathematical Software, Выпуске 3, сентябрь 1977, стр 209–226.

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

Введен в R2010a

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