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.

Примеры

свернуть все

Скрипт Open 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
Скрипт Open 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')

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

свернуть все

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

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

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

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (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 th наименьшее расстояние в выходных аргументах. Чтобы задать k, используйте аргумент пары "имя-значение" 'K'.

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

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

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

  • 'kdtree' — Создает и использует d-дерево K, чтобы найти самых близких соседей. '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'Расстояние Mahalanobis, вычисленное использование положительной определенной ковариационной матрицы. Чтобы изменить значение ковариационной матрицы, используйте аргумент пары "имя-значение" 'Cov'.
'cosine'Один минус косинус включенного угла между наблюдениями (обработанный как векторы).
'correlation'Один минус демонстрационная линейная корреляция между наблюдениями (обработанный как последовательности значений).
'spearman'Один минус порядковая корреляция демонстрационного Копьеносца между наблюдениями (обработанный как последовательности значений).
'hamming'Расстояние Хемминга, которое является процентом координат, которые отличаются.
'jaccard'Один минус коэффициент Jaccard, который является процентом ненулевых координат, которые отличаются.

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

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

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

    • 1 n векторным ZI, содержащим одну строку от X или от точек запроса Y.

    • m2-by-n матричный ZJ, содержащий несколько строк X или Y.

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

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

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

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

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

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

Ковариационная матрица для метрики расстояния Mahalanobis, заданной как пара, разделенная запятой, состоящая из '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

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

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

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

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

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

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

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

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

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

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

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

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

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

свернуть все

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

  • Если вы не задаете 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-Nearest.

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

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

Ссылки

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

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

Смотрите также

| | |

Темы

Представленный в R2010a

Документация Statistics and Machine Learning Toolbox
Поддержка
Для просмотра документации необходимо авторизоваться на сайте