Exponenta Banner
exponenta event banner

knnsearch

Поиск k-ближайших соседей с помощью входных данных

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

Синтаксис

Idx = knnsearch (X, Y)
Idx = knnsearch (X, Y, имя, значение)
[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.

Примеры

свернуть все

Открыть сценарий в реальном времени

Найдите пациентов в 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
Открыть сценарий в реальном времени

Найти 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' - создает и использует дерево Kd для поиска ближайших соседей. '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).

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

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

    • Матрица м2-на-n ZJ содержащий несколько строк X или Y.

  • Возврат вектора расстояний м2 на 1 D2, чей j-й элемент - расстояние между наблюдениями 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

Максимальное количество точек данных в конечном узле Kd-дерева, указанное как разделенная запятыми пара, состоящая из '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

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

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

свернуть все

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

  • Если не указать IncludeTies (false по умолчанию), то Idx - числовая матрица m-на-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-на-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 Neighbor Search and Radius Search.

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

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

Ссылки

[1] Фридман, J. H., Дж. Бентели и Р. А. Финкель. «Алгоритм поиска наилучших совпадений за логарифмическое ожидаемое время». ACM Transactions on Mathematical Software 3, No. 3 (1977): 209-226.

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

.

См. также

| | |

Темы

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

Документация по инструментам для статистического и машинного обучения

Поддержка