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

Table of Contents
Sintaxis Descripción Ejemplos Encontrar los vecinos más cercanos Encontrar los k vecinos más cercanos utilizando diferentes métricas de distancia Acelerar el cálculo de la distancia usando la distancia fasteuclidean Argumentos de entrada X — Datos de entrada matriz numérica Y — Puntos de consulta matriz numérica Argumentos de par nombre-valor K — Número de vecinos más cercanos1 (predeterminado) | entero positivo IncludeTies — Marcador para incluir todos los vecinos más cercanos false (0) (predeterminado) | true (1) NSMethod — Método de búsqueda del vecino más cercano 'kdtree' | 'exhaustive' Distance — Métrica de distancia 'euclidean' (predeterminado) | 'seuclidean' | 'fasteuclidean' | 'fastseuclidean' | 'cityblock' | 'chebychev' | 'minkowski' | 'mahalanobis' | 'cosine' | 'correlation' | 'spearman' | 'hamming' | 'jaccard' | identificador de función | ... CacheSize — Tamaño de la matriz de Gram en megabytes 1e3 (predeterminado) | escalar positivo | "maximal" Scale — Valor del parámetro de escala para la métrica de distancia euclidiana estandarizadastd(X,'omitnan') (predeterminado) | vector numérico no negativo BucketSize — Número máximo de puntos de datos en el nodo hoja del árbol Kd 50 (predeterminado) | entero positivo SortIndices — Marcador para ordenar los índices devueltos según la distancia true (1) (predeterminado) | false (0) Argumentos de salida Idx — Índices de datos de entrada de vecinos más cercanos matriz numérica | arreglo de celdas de vectores numéricos D — Distancias de los vecinos más cercanos matriz numérica | arreglo de celdas de vectores numéricos Sugerencias Algoritmos Algoritmo de distancia euclidiana rápida Referencias Funcionalidad alternativa Bloque de Simulink Referencias Capacidades ampliadas Arreglos altos Realice cálculos con arreglos que tienen más filas de las que caben en la memoria. Generación de código C/C++ Genere código C y C++ mediante MATLAB® Coder™. Arreglos GPU Acelere código mediante la ejecución en una unidad de procesamiento gráfico (GPU) mediante Parallel Computing Toolbox™. Historial de versiones R2023a: Distancia euclidiana rápida usando una caché Consulte también Temas Comando de MATLAB Americas Europe Asia Pacific References

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

contraer todo en la página

Sintaxis

Idx = knnsearch(X,Y)

Idx = knnsearch(X,Y,Name,Value)

[Idx,D] = knnsearch(___)

Descripción

ejemplo

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.

Ejemplos

contraer todo

Encontrar los vecinos más cercanos

Abrir script en vivo

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

Encontrar los k vecinos más cercanos utilizando diferentes métricas de distancia

Abrir script en vivo

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 fisheririsX = meas(:,3:4); % Measurements of original flowersY = [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')

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

Acelerar el cálculo de la distancia usando la distancia fasteuclidean

Abrir script en vivo

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 reproducibilityN = 10000;X = randn(N,1000);Y = randn(N,1000);Idx = knnsearch(X,Y); % Warm up function for more reliable timing informationticIdx = 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 functionticIdx2 = 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

XDatos de entrada
matriz numérica

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

YPuntos de consulta
matriz numérica

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.

KNúmero de vecinos más cercanos
1 (predeterminado) | entero positivo

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

IncludeTiesMarcador para incluir todos los vecinos más cercanos
false (0) (predeterminado) | true (1)

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

NSMethodMétodo de búsqueda del vecino más cercano
'kdtree' | 'exhaustive'

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'

DistanceMétrica de distancia
'euclidean' (predeterminado) | 'seuclidean' | 'fasteuclidean' | 'fastseuclidean' | 'cityblock' | 'chebychev' | 'minkowski' | 'mahalanobis' | 'cosine' | 'correlation' | 'spearman' | 'hamming' | 'jaccard' | identificador de función | ...

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

CacheSizeTamaño de la matriz de Gram en megabytes
1e3 (predeterminado) | escalar positivo | "maximal"

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 MXporMY, 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 MXpor1. 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

ScaleValor del parámetro de escala para la métrica de distancia euclidiana estandarizada
std(X,'omitnan') (predeterminado) | vector numérico no negativo

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

BucketSizeNúmero máximo de puntos de datos en el nodo hoja del árbol Kd
50 (predeterminado) | entero positivo

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

SortIndicesMarcador para ordenar los índices devueltos según la distancia
true (1) (predeterminado) | false (0)

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

Idx — Índices de datos de entrada de vecinos más cercanos
matriz numérica | arreglo de celdas de vectores numéricos

Í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.

D — Distancias de los vecinos más cercanos
matriz numérica | arreglo de celdas de vectores numéricos

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.

Algoritmo de distancia euclidiana rápida

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:

Di,j2=xixj2=(xixj)T(xixj)=xi22xiTxj+xj2.

La matriz xiTxj 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

Historial de versiones

Introducido en R2010a

expandir todo

Las 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

Temas

  • k-Nearest Neighbor Search and Radius Search
  • Distance Metrics

Comando de MATLAB

Ha hecho clic en un enlace que corresponde a este comando de MATLAB:

 

Ejecute el comando introduciéndolo en la ventana de comandos de MATLAB. Los navegadores web no admiten comandos de MATLAB.

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

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

Americas

  • América Latina (Español)
  • Canada (English)
  • United States (English)

Europe

  • 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
    • Deutsch
    • English
    • Français
  • United Kingdom (English)

Asia Pacific

Contact your local office

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

References

Top Articles
Latest Posts
Article information

Author: Aron Pacocha

Last Updated:

Views: 5655

Rating: 4.8 / 5 (48 voted)

Reviews: 87% of readers found this page helpful

Author information

Name: Aron Pacocha

Birthday: 1999-08-12

Address: 3808 Moen Corner, Gorczanyport, FL 67364-2074

Phone: +393457723392

Job: Retail Consultant

Hobby: Jewelry making, Cooking, Gaming, Reading, Juggling, Cabaret, Origami

Introduction: My name is Aron Pacocha, I am a happy, tasty, innocent, proud, talented, courageous, magnificent person who loves writing and wants to share my knowledge and understanding with you.