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 имя аргумента и 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',3

Типы данных: 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 ложь по умолчанию), затем 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 ложь по умолчанию), затем 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 - ближайших соседей.

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

Если вы устанавливаете knnsearch 'NSMethod' функции аргумент пары "имя-значение" соответствующему значению ('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
Поддержка
Для просмотра документации необходимо авторизоваться на сайте