knnsearch
Encontrar los k vecinos más cercanos utilizando datos de entrada
Descripción
devuelve Idx = knnsearch(X,Y,Name,Value)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.
Ejemplos
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
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
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.
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:
knnsearchincluye 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'.IdxyDson arreglos de celdas de m por1tales que cada celda contiene un vector de al menos k índices y distancias, respectivamente. Cada vector deDcontiene distancias establecidas en orden ascendente. Cada fila deIdxcontiene los índices de los vecinos más cercanos correspondientes a las distancias deD.
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 deXes menor o igual a 10,Xno 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 deXa cada punto deY.
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.
| Valor | Descripció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
ZIde 1 por n que contenga una única fila deXo de los puntos de consultaY.Una matriz
ZJde m2 por n que contenga varias filas deXoY.
Devolver un vector de m2 por 1 de distancias
D2, cuyoj-ésimo elemento es la distancia entre las observacionesZIyZJ(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:
Ycontiene muchas observaciones que tienen muchos vecinos más cercanos enX.NSMethodes'kdtree'.IncludeTiesesfalse.
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
Í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(falsede forma predeterminada),Idxes una matriz numérica de m por k, donde m es el número de filas enYy k es el número de vecinos más cercanos buscados.Idx(j,i)indica queX(Idx(j,i),:)es una de las k observaciones más cercanas deXal punto de consultaY(j,:).Si especifica
'IncludeTies',true,Idxes un arreglo de celdas de m por1tal que la celdaj(Idx{j}) contiene un vector de al menos k índices de las observaciones más cercanas deXal punto de consultaY(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(falsede forma predeterminada),Des una matriz numérica de m por k, donde m es el número de filas deYy k es el número de vecinos más cercanos buscados.D(j,i)es la distancia entreX(Idx(j,i),:)yY(j,:)con respecto a la métrica de distancia.Si especifica
'IncludeTies',true,Des un arreglo de celdas de m por1tal que la celdaj(D{j}) contiene un vector de al menos k distancias de las observaciones más cercanas deXal punto de consultaY(j,:).
Si SortIndices es true, knnsearch establece las distancias en orden ascendente.
Sugerencias
Para un entero positivo fijo k,
knnsearchencuentra los k puntos deXque más se aproximan a cada punto deY. Para encontrar todos los puntos deXdentro de una distancia fija de cada punto deY, utilicerangesearch.knnsearchno guarda un objeto de búsqueda. Para crear un objeto de búsqueda, utilicecreatens.
Algoritmos
Para obtener información sobre un algoritmo de búsqueda específico, consulte k-Nearest Neighbor Search and Radius Search.
Los valores del argumento Distance que empiezan con fast (como 'fasteuclidean' y 'fastseuclidean') calculan distancias euclidianas utilizando un algoritmo que utiliza memoria adicional para ahorrar tiempo de cálculo. Este algoritmo se denomina "Euclidean Distance Matrix Trick" en Albanie [1] y en otros lugares. Las pruebas internas muestran que este algoritmo ahorra tiempo cuando el número de predictores es al menos 10. Los algoritmos que empiezan con 'fast' no admiten datos dispersos.
Para encontrar la matriz D de distancias entre todos los puntos xi y xj, donde cada xi tiene n variables, el algoritmo calcula la distancia usando la línea final de las ecuaciones siguientes:
La matriz de la última línea de las ecuaciones se denominada la matriz de Gram. Cuando se calcula y se utiliza la matriz de Gram en lugar de calcular las distancias al cuadrado mediante el cuadrado y la suma, calcular el conjunto de distancias cuadradas es más rápido, pero ligeramente menos estable numéricamente. Para obtener más información, consulte Albanie [1].
Para almacenar la matriz de Gram, el software usa una caché con el tamaño predeterminado de 1e3 megabytes. Puede establecer el tamaño de la caché utilizando el argumento de nombre-valor CacheSize. Si 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.
Referencias
[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://www.robots.ox.ac.uk/%7Ealbanie/notes/Euclidean_distance_trick.pdf.
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
Notas y limitaciones de uso:
Si
Xes un arreglo alto,Yno puede ser un arreglo alto. De manera similar, siYes un arreglo alto,Xno puede ser un arreglo alto.
Para obtener más información, consulte Arreglos altos.
Notas y limitaciones de uso:
Para la generación de código, el valor predeterminado del argumento de par nombre-valor
'NSMethod'es'exhaustive'cuando el número de columnas deXes mayor que 7.El valor del argumento de par nombre-valor
'Distance'debe ser una constante en tiempo de compilación y no puede ser una función de distancia personalizada.El valor del argumento de par nombre-valor
'IncludeTies'debe ser una constante en tiempo de compilación.El argumento de par nombre-valor
'SortIndices'no es compatible. Los argumentos de salida siempre están ordenados.knnsearchno admite la generación de código para cálculos rápidos de distancia euclidiana, lo que significa que no es compatible con las métricas de distancia cuyos nombres empiezan confast(por ejemplo,'fasteuclidean').Los nombres de los argumentos nombre-valor deben ser constantes en tiempo de compilación. Por ejemplo, para permitir un exponente definido por el usuario para la distancia de Minkowski en el código generado, incluya
{coder.Constant('Distance'),coder.Constant('Minkowski'),coder.Constant('P'),0}en el valor-argsdecodegen(MATLAB Coder).Cuando especifique
'IncludeTies'comotrue, la posición en el orden para distancias idénticas en el código generado puede diferir del orden en MATLAB debido a la precisión numérica.Cuando
knnsearchutiliza el algoritmo de búsqueda del árbol kd y el tipo de construcción de generación de código es una función MEX,codegen(MATLAB Coder) genera una función MEX utilizando Threading Building Blocks (TBB) de Intel® para el cálculo paralelo. En caso contrario,codegengenera código utilizandoparfor(MATLAB Coder).Función MEX para el algoritmo de búsqueda del árbol kd:
codegengenera una función MEX optimizada utilizando TBB de Intel para el cálculo paralelo en plataformas multinúcleo. Puede utilizar la función MEX para acelerar los algoritmos de MATLAB. Para obtener más información sobre TBB de Intel, consulte https://www.intel.com/content/www/us/en/developer/tools/oneapi/onetbb.html.Si genera la función MEX para probar el código generado de la versión
parfor, puede deshabilitar el uso de TBB de Intel. Establezca la propiedadExtrinsicCallsdel objeto de configuración MEX enfalse. Para obtener más detalles, consultecoder.MexCodeConfig(MATLAB Coder).Función MEX para el algoritmo de búsqueda exhaustiva y código C/C++ independiente para ambos algoritmos: el código generado de
knnsearchutilizaparfor(MATLAB Coder) para crear bucles que se ejecutan en paralelo en plataformas multinúcleo de memoria compartida compatibles con el código generado. Si su compilador no es compatible con la interfaz de la aplicación de multiprocesamiento abierto (OpenMP) o desactiva la biblioteca OpenMP, MATLAB Coder™ trata los buclesparforcomo buclesfor. Para encontrar compiladores compatibles, consulte compiladores compatibles. Para desactivar la biblioteca OpenMP, establezca la propiedadEnableOpenMPdel objeto de configuración comofalse. Para obtener más detalles, consultecoder.CodeConfig(MATLAB Coder).
knnsearchdevuelve índices de tipo de valor entero (int32) en código C/C++ independiente generado. Por lo tanto, la función permite un soporte de precisión simple estricto cuando utiliza entradas de precisión simple. Para la generación de código MEX, la función sigue devolviendo índices de precisión doble para igualar el comportamiento de MATLAB.
Para obtener más información sobre la generación de código, consulte Introduction to Code Generation y General Code Generation Workflow.
Notas y limitaciones de uso:
El argumento nombre-valor
NSMethoddebe especificarse como"exhaustive".Los argumentos nombre-valor
IncludeTiesySortIndicesdeben especificarse con sus valores predeterminados.No puede especificar el argumento nombre-valor
Distancecomo"fasteuclidean"o"fastseuclidean".
Para obtener más información, consulte Run MATLAB Functions on a GPU (Parallel Computing Toolbox).
Historial de versiones
Introducido en R2010aLas métricas de distancia 'fasteuclidean' y 'fastseuclidean' aceleran el cálculo de las distancias euclidianas utilizando una caché y un algoritmo diferente (consulte Algoritmos). Establezca el tamaño de la caché utilizando el argumento de nombre-valor CacheSize.
Consulte también
createns | knnsearch | ExhaustiveSearcher | KDTreeSearcher | hnswSearcher | rangesearch
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Seleccione un país/idioma
Seleccione un país/idioma para obtener contenido traducido, si está disponible, y ver eventos y ofertas de productos y servicios locales. Según su ubicación geográfica, recomendamos que seleccione: .
También puede seleccionar uno de estos países/idiomas:
Cómo obtener el mejor rendimiento
Seleccione China (en idioma chino o inglés) para obtener el mejor rendimiento. Los sitios web de otros países no están optimizados para ser accedidos desde su ubicación geográfica.
América
- América Latina (Español)
- Canada (English)
- United States (English)
Europa
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)