Contenido principal

La traducción de esta página aún no se ha actualizado a la versión más reciente. Haga clic aquí para ver la última versión en inglés.

knnsearch

Encontrar los k vecinos más cercanos utilizando datos de entrada

Descripción

Idx = knnsearch(X,Y) encuentra el vecino más cercano de X para cada punto de consulta de Y y devuelve los índices de los vecinos más cercanos de Idx, un vector columna. Idx tiene el mismo número de filas que Y.

ejemplo

Idx = knnsearch(X,Y,Name,Value) devuelve Idx con más opciones especificadas con uno o más argumentos de par nombre-valor. Por ejemplo, puede especificar el número de vecinos más cercanos que desea buscar y la métrica de distancia utilizada en la búsqueda.

ejemplo

[Idx,D] = knnsearch(___) devuelve además la matriz D, utilizando cualquiera de los argumentos de entrada de las sintaxis anteriores. D contiene las distancias entre cada observación en Y y las correspondientes observaciones más cercanas en X.

ejemplo

Ejemplos

contraer todo

Encuentre los pacientes del conjunto de datos hospital que más se parezcan a los pacientes de Y, en lo que respecta a la edad y el peso.

Cargue el conjunto de datos hospital.

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

Realice una knnsearch entre X e Y para encontrar los índices de los vecinos más cercanos.

Idx = knnsearch(X,Y);

Encuentre los pacientes de X más próximos en edad y peso a los de Y.

X(Idx,:)
ans = 5×2

    25   171
    25   171
    39   164
    49   170
    50   172

Encuentre los 10 vecinos más cercanos de X a cada punto de Y, primero utilizando la métrica de distancia de Minkowski y después utilizando la métrica de distancia de Chebychev.

Cargue el conjunto de datos Iris de Fisher.

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

Realice una knnsearch entre X y los puntos de consulta de Y utilizando las métricas de distancia de Minkowski y Chebychev.

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

Visualice los resultados de las dos búsquedas del vecino más cercano. Represente los datos de entrenamiento. Represente los puntos de consulta con el marcador X. Utilice círculos para denotar los vecinos más cercanos de Minkowski. Utilice pentagramas para denotar los vecinos más cercanos de Chebychev.

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')

Cree dos matrices grandes de puntos y, luego, mida el tiempo utilizado por knnsearch con la métrica de distancia predeterminada "euclidean".

rng default % For reproducibility
N = 10000;
X = randn(N,1000);
Y = randn(N,1000);
Idx = knnsearch(X,Y); % Warm up function for more reliable timing information
tic
Idx = knnsearch(X,Y);
standard = toc
standard = 28.1783

A continuación, mida el tiempo utilizado por knnsearch con la métrica de distancia "fasteuclidean". Especifique un tamaño de caché de 100.

Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); % Warm up function
tic
Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100);
accelerated = toc
accelerated = 2.7198

Evalúe por qué factor es más rápido el cálculo acelerado en comparación con el estándar.

standard/accelerated
ans = 10.3606

La versión acelerada es más de tres veces más rápida en este ejemplo.

Argumentos de entrada

contraer todo

Datos de entrada, especificados como matriz numérica. Las filas de X corresponden a observaciones y las columnas corresponden a variables.

Tipos de datos: single | double

Puntos de consulta, especificados como matriz numérica. Las filas de Y corresponden a las observaciones y las columnas, a las variables. Y debe tener el mismo número de columnas que X.

Tipos de datos: single | double

Argumentos de par nombre-valor

contraer todo

Especifique pares de argumentos opcionales Name1=Value1,...,NameN=ValueN, donde Name es el nombre del argumento y Value es el valor correspondiente. Los argumentos nombre-valor deben aparecer después de otros argumentos, pero el orden de los pares no importa.

En versiones anteriores a R2021a, use comas para separar cada nombre y valor y encierre Name entre comillas.

Ejemplo: knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock') busca los 10 vecinos más cercanos, incluyendo los empates y utilizando la distancia Manhattan.

Número de vecinos más cercanos que se desea encontrar en X para cada punto en Y, especificado como el par separado por comas que consta de 'K' y un entero positivo.

Ejemplo: 'K',10

Tipos de datos: single | double

Marcador para incluir todos los vecinos más cercanos que tengan la misma distancia desde los puntos de consulta, especificado como el par separado por comas que consta de 'IncludeTies' y false (0) o true (1).

Si 'IncludeTies' es false, knnsearch elige la observación con el índice más pequeño entre las observaciones que tienen la misma distancia a un punto de consulta.

Si 'IncludeTies' es true, entonces:

  • knnsearch incluye a todos los vecinos más cercanos cuyas distancias sean iguales a la k-ésima distancia más pequeña de los argumentos de salida. Para especificar k, utilice el argumento de par nombre-valor 'K'.

  • Idx y D son arreglos de celdas de m por 1 tales que cada celda contiene un vector de al menos k índices y distancias, respectivamente. Cada vector de D contiene distancias establecidas en orden ascendente. Cada fila de Idx contiene los índices de los vecinos más cercanos correspondientes a las distancias de D.

Ejemplo: 'IncludeTies',true

Método de búsqueda del vecino más cercano, especificado como el par separado por comas que consta de 'NSMethod' y uno de estos valores.

  • 'kdtree': crea y utiliza un árbol Kd para encontrar vecinos más cercanos. 'kdtree' es el valor predeterminado cuando el número de columnas de X es menor o igual a 10, X no es dispersa y la métrica de distancia es 'euclidean', 'cityblock', 'chebychev' o 'minkowski'. En caso contrario, el valor predeterminado es 'exhaustive'.

    El valor 'kdtree' solo es válido cuando la métrica de distancia es una de las cuatro métricas señaladas anteriormente.

  • 'exhaustive': utiliza el algoritmo de búsqueda exhaustiva calculando los valores de distancia de todos los puntos de X a cada punto de Y.

Ejemplo: 'NSMethod','exhaustive'

Usos de la métrica de distancia knnsearch, especificados como uno de los valores de esta tabla o un identificador de función.

ValorDescripción
'euclidean'Distancia euclidiana
'seuclidean'Distancia euclidiana estandarizada. Cada diferencia de coordenadas entre las filas de X y la matriz de consultas Y se escala dividiendo por el elemento correspondiente de la desviación estándar calculada a partir de X. Para especificar una escala diferente, utilice el argumento nombre-valor 'Scale'.
'fasteuclidean'Distancia euclidiana calculada utilizando un algoritmo alternativo que ahorra tiempo cuando el número de predictores es al menos 10. En algunos casos, este algoritmo más rápido puede reducir la precisión. Esta métrica de distancia solo está disponible cuando NSMethod es 'exhaustive'. Los algoritmos que empiezan con 'fast' no admiten datos dispersos. Para obtener más detalles, consulte Algoritmos.
'fastseuclidean'Distancia euclidiana estandarizada calculada utilizando un algoritmo alternativo que ahorra tiempo cuando el número de predictores es al menos 10. En algunos casos, este algoritmo más rápido puede reducir la precisión. Esta métrica de distancia solo está disponible cuando NSMethod es 'exhaustive'. Los algoritmos que empiezan con 'fast' no admiten datos dispersos. Para obtener más detalles, consulte Algoritmos.
'cityblock'Distancia Manhattan
'chebychev'Distancia de Chebyshov (diferencia de coordenada máxima)
'minkowski'Distancia de Minkowski. El exponente predeterminado es 2. Para especificar un exponente diferente, utilice el argumento nombre-valor 'P'.
'mahalanobis'Distancia de Mahalanobis, calculada utilizando una matriz de covarianzas definida positiva. Para cambiar el valor de la matriz de covarianzas, utilice el argumento nombre-valor 'Cov'.
'cosine'Uno menos el coseno del ángulo incluido entre observaciones (tratadas como vectores)
'correlation'Uno menos la correlación lineal de muestra entre observaciones (tratadas como secuencias de valores)
'spearman'Uno menos la correlación del coeficiente de Spearman entre observaciones (tratadas como secuencias de valores)
'hamming'Distancia de Hamming, que es el porcentaje de coordenadas que difieren
'jaccard'Uno menos el coeficiente de Jaccard, que es el porcentaje de coordenadas, que no son cero, que difieren

También puede especificar un identificador de función para una métrica de distancia personalizada utilizando @ (por ejemplo, @distfun). Una función de distancia personalizada debe:

  • Tener la forma function D2 = distfun(ZI,ZJ).

  • Tomar como argumentos:

    • Un vector ZI de 1 por n que contenga una única fila de X o de los puntos de consulta Y.

    • Una matriz ZJ de m2 por n que contenga varias filas de X o Y.

  • Devolver un vector de m2 por 1 de distancias D2, cuyo j-ésimo elemento es la distancia entre las observaciones ZI y ZJ(j,:).

Para obtener más información, consulte Distance Metrics.

Ejemplo: 'Distance','chebychev'

Tipos de datos: char | string | function_handle

Tamaño de la matriz de Gram en megabytes, especificado como un escalar positivo o "maximal". La función knnsearch puede utilizar CacheSize solo cuando el argumento nombre-valor Distance empiece por fast y el argumento nombre-valor NSMethod se establezca en 'exhaustive'.

Si establece CacheSize en "maximal", knnsearch intenta asignar suficiente memoria para una matriz intermedia entera cuyo tamaño es MX por MY, donde MX es el número de filas de los datos de entrada X y MY es el número de filas de los datos de entrada Y. El tamaño de la caché no tiene que ser lo suficientemente grande para una matriz intermedia completa, pero debe ser al menos lo suficientemente grande como para contener un vector de MX por 1. De lo contrario, knnsearch usa el algoritmo estándar para calcular la distancia euclidiana.

Si el valor del argumento Distance empieza por fast, el valor de NSMethod es 'exhaustive' y el valor de CacheSize es demasiado grande o "maximal", knnsearch puede intentar asignar una matriz de Gram que supere la memoria disponible. En este caso, MATLAB® muestra un error.

Ejemplo: CacheSize="maximal"

Tipos de datos: double | char | string

Exponente para la métrica de distancia de Minkowski, especificado como el par separado por comas que consta de 'P' y un escalar positivo.

Este argumento solo es válido si 'Distance' es 'minkowski'.

Ejemplo: 'P',3

Tipos de datos: single | double

Matriz de covarianzas para la métrica de distancia de Mahalanobis, especificada como el par separado por comas que consta de 'Cov' y una matriz definida positiva.

Este argumento solo es válido si 'Distance' es 'mahalanobis'.

Ejemplo: 'Cov',eye(4)

Tipos de datos: single | double

Valor del parámetro de escala para la métrica de distancia euclidiana estandarizada, especificado como el par separado por comas que consta de 'Scale' y un vector numérico no negativo. 'Scale' tiene una longitud igual al número de columnas de X. Cuando knnsearch calcula la distancia euclidiana estandarizada, cada coordenada de X se escala por el elemento correspondiente de 'Scale', al igual que cada punto de consulta. Este argumento solo es válido cuando 'Distance' es 'seuclidean'.

Ejemplo: 'Scale',quantile(X,0.75) - quantile(X,0.25)

Tipos de datos: single | double

Número máximo de puntos de datos en el nodo hoja del árbol Kd, especificado como el par separado por comas que consta de 'BucketSize' y un entero positivo. Este argumento solo es válido cuando NSMethod es 'kdtree'.

Ejemplo: 'BucketSize',20

Tipos de datos: single | double

Marcador para ordenar los índices devueltos en función de la distancia, especificado como el par separado por comas que consta de 'SortIndices' y true (1) o false (0).

Para un rendimiento más rápido, puede establecer SortIndices en false cuando se cumplan las siguientes condiciones:

  • Y contiene muchas observaciones que tienen muchos vecinos más cercanos en X.

  • NSMethod es 'kdtree'.

  • IncludeTies es false.

En este caso, knnsearch devuelve los índices de los vecinos más cercanos sin ningún orden en particular. Cuando SortIndices es true, la función establece los índices de los vecinos más cercanos en orden ascendente por distancia.

SortIndices es true de forma predeterminada. Cuando NSMethod es 'exhaustive' o IncludeTies es true, la función siempre ordena los índices.

Ejemplo: 'SortIndices',false

Tipos de datos: logical

Argumentos de salida

contraer todo

Índices de datos de entrada de los vecinos más cercanos, devueltos como matriz numérica o arreglo de celdas de vectores numéricos.

  • Si no especifica IncludeTies (false de forma predeterminada), Idx es una matriz numérica de m por k, donde m es el número de filas en Y y k es el número de vecinos más cercanos buscados. Idx(j,i) indica que X(Idx(j,i),:) es una de las k observaciones más cercanas de X al punto de consulta Y(j,:).

  • Si especifica 'IncludeTies',true, Idx es un arreglo de celdas de m por 1 tal que la celda j (Idx{j}) contiene un vector de al menos k índices de las observaciones más cercanas de X al punto de consulta Y(j,:).

Si SortIndices es true, knnsearch establece los índices en orden ascendente por distancia.

Distancias de los vecinos más cercanos a los puntos de consulta, devueltas como matriz numérica o arreglo de celdas de vectores numéricos.

  • Si no especifica IncludeTies (false de forma predeterminada), D es una matriz numérica de m por k, donde m es el número de filas de Y y k es el número de vecinos más cercanos buscados. D(j,i) es la distancia entre X(Idx(j,i),:) y Y(j,:) con respecto a la métrica de distancia.

  • Si especifica 'IncludeTies',true, D es un arreglo de celdas de m por 1 tal que la celda j (D{j}) contiene un vector de al menos k distancias de las observaciones más cercanas de X al punto de consulta Y(j,:).

Si SortIndices es true, knnsearch establece las distancias en orden ascendente.

Sugerencias

  • Para un entero positivo fijo k, knnsearch encuentra los k puntos de X que más se aproximan a cada punto de Y. Para encontrar todos los puntos de X dentro de una distancia fija de cada punto de Y, utilice rangesearch.

  • knnsearch no guarda un objeto de búsqueda. Para crear un objeto de búsqueda, utilice createns.

Algoritmos

contraer todo

Para obtener información sobre un algoritmo de búsqueda específico, consulte k-Nearest Neighbor Search and Radius Search.

Funcionalidad alternativa

Si establece el argumento de par nombre-valor 'NSMethod' de la función knnsearch en el valor adecuado ('exhaustive' para un algoritmo de búsqueda exhaustiva o 'kdtree' para un algoritmo del árbol Kd), los resultados de la búsqueda son equivalentes a los resultados obtenidos realizando una búsqueda de distancia utilizando la función del objeto knnsearch. A diferencia de la función knnsearch, la función del objeto knnsearch requiere un objeto ExhaustiveSearcher o un objeto de modelo KDTreeSearcher.

Bloque de Simulink

Para integrar una búsqueda de los k vecinos más cercanos en Simulink®, puede utilizar el bloque KNN Search de la biblioteca Statistics and Machine Learning Toolbox™ o un bloque Function de MATLAB con la función knnsearch. Para ver un ejemplo, consulte Predict Class Labels Using MATLAB Function Block.

A la hora de decidir qué enfoque utilizar, considere lo siguiente:

  • Si utiliza el bloque de biblioteca Statistics and Machine Learning Toolbox, puede utilizar la herramienta Fixed-Point Tool (Fixed-Point Designer) para convertir un modelo de punto flotante en uno de punto fijo.

  • La compatibilidad con los arreglos de tamaño variable debe activarse para un bloque de funciones de MATLAB con la función knnsearch.

Referencias

[1] Friedman, J. H., J. Bentley, and R. A. Finkel. “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM Transactions on Mathematical Software 3, no. 3 (1977): 209–226.

Capacidades ampliadas

expandir todo

Historial de versiones

Introducido en R2010a

expandir todo