Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

knnsearch

Buscar-vecinos más cercanos mediante el objeto buscadork

Descripción

ejemplo

Idx = knnsearch(Mdl,Y) busca el vecino más cercano (es decir, el punto más cercano, la fila o la observación) en cada punto (es decir, fila o observación) en los datos de la consulta utilizando una búsqueda exhaustiva o un árbol-d. Devuelve, que es un vector de columna de los índices en la representación de los vecinos más cercanos.Mdl.XYKknnsearchIdxMdl.X

ejemplo

Idx = knnsearch(Mdl,Y,Name,Value) Devuelve los índices de los puntos más cercanos a con opciones adicionales especificadas por uno o más argumentos de par.Mdl.XYName,Value Por ejemplo, especifique el número de vecinos más cercanos para buscar, distancia métrica diferente de la almacenada en.Mdl.Distance También puede especificar qué acción se debe realizar si se atan las distancias más cercanas.

ejemplo

[Idx,D] = knnsearch(___) Además devuelve la matriz utilizando cualquiera de los argumentos de entrada en las sintaxis anteriores. contiene las distancias entre cada observación en que corresponden a las observaciones más cercanas en.DDYMdl.X De forma predeterminada, la función organiza las columnas en orden ascendente por cercanía, con respecto a la métrica de distancia.D

Ejemplos

contraer todo

acepta o Modele objetos para buscar los datos de entrenamiento de los vecinos más cercanos a los datos de la consulta.knnsearchExhaustiveSearcherKDTreeSearcher Un modelo invoca el algoritmo de buscador exhaustivo y un modelo define un árbol-d, que utiliza para buscar vecinos más cercanos.ExhaustiveSearcherKDTreeSearcherKknnsearch

Cargue el conjunto de datos de iris de Fisher. Reserve aleatoriamente cinco observaciones de los datos para los datos de consulta.

load fisheriris rng(1); % For reproducibility n = size(meas,1); idx = randsample(n,5); X = meas(~ismember(1:n,idx),:); % Training data Y = meas(idx,:);                % Query data

La variable contiene 4 predictores.meas

Cultivar un árbol-d de cuatro dimensiones por defecto.K

MdlKDT = KDTreeSearcher(X)
MdlKDT =    KDTreeSearcher with properties:         BucketSize: 50          Distance: 'euclidean'     DistParameter: []                 X: [145x4 double]  

es un objeto de modelo.MdlKDTKDTreeSearcher Puede alterar sus propiedades de escritura mediante la notación de puntos.

Prepare un buscador de vecinos exhaustivo más cercano.

MdlES = ExhaustiveSearcher(X)
MdlES =    ExhaustiveSearcher with properties:           Distance: 'euclidean'     DistParameter: []                 X: [145x4 double]  

es un objeto de modelo.MdlKDTExhaustiveSearcher Contiene las opciones, como la métrica de distancia, que se usarán para buscar los vecinos más cercanos.

Alternativamente, puede hacer crecer un árbol-d o preparar un buscador de vecino más cercano con un exhaustivo uso.Kcreatens

Busque los datos de entrenamiento para los índices de vecinos más cercanos que corresponden a cada observación de consulta. Realice ambos tipos de búsquedas utilizando la configuración predeterminada. De forma predeterminada, el número de vecinos que se buscan para la observación por consulta es.1

IdxKDT = knnsearch(MdlKDT,Y); IdxES = knnsearch(MdlES,Y); [IdxKDT IdxES]
ans = 5×2

    17    17
     6     6
     1     1
    89    89
   124   124

En este caso, los resultados de la búsqueda son los mismos.

Cultivar un objeto buscador vecino más cercano de d-Tree mediante la función.Kcreatens Pase el objeto y consulte los datos a la función para buscar los vecinos más cercanos.knnsearchk

Cargue el conjunto de datos de iris de Fisher.

load fisheriris

Quite cinco iris aleatoriamente de los datos del predictor para usarlos como conjunto de consultas.

rng(1);                     % For reproducibility n = size(meas,1);           % Sample size qIdx = randsample(n,5);     % Indices of query data tIdx = ~ismember(1:n,qIdx); % Indices of training data Q = meas(qIdx,:); X = meas(tIdx,:);

Cultivar un árbol-d de cuatro dimensiones usando los datos de entrenamiento.K Especifique la distancia de Minkowski para encontrar los vecinos más cercanos.

Mdl = createns(X,'Distance','minkowski')
Mdl =    KDTreeSearcher with properties:         BucketSize: 50          Distance: 'minkowski'     DistParameter: 2                 X: [145x4 double]  

Dado que tiene cuatro columnas y la métrica de distancia es Minkowski, crea un objeto de modelo de forma predeterminada.XcreatensKDTreeSearcher El exponente de distancia de Minkowski es por defecto.2

Busque los índices de los datos de entrenamiento () que son los dos vecinos más cercanos de cada punto de la consulta Data ().Mdl.XQ

IdxNN = knnsearch(Mdl,Q,'K',2)
IdxNN = 5×2

    17     4
     6     2
     1    12
    89    66
   124   100

Cada fila de corresponde a una observación de datos de consulta y el orden de columna corresponde al orden de los vecinos más cercanos, con respecto a la distancia ascendente.IdxNN Por ejemplo, basado en la distancia Minkowski, el segundo vecino más cercano de es.Q(3,:)X(12,:)

Cargue el conjunto de datos de iris de Fisher.

load fisheriris

Quite cinco iris aleatoriamente de los datos del predictor para usarlos como conjunto de consultas.

rng(4);                     % For reproducibility n = size(meas,1);           % Sample size qIdx = randsample(n,5);     % Indices of query data X = meas(~ismember(1:n,qIdx),:); Y = meas(qIdx,:);

Cultivar un árbol-d de cuatro dimensiones usando los datos de entrenamiento.K Especifique la distancia de Minkowski para encontrar los vecinos más cercanos.

Mdl = KDTreeSearcher(X);

es un objeto de modelo.MdlKDTreeSearcher De forma predeterminada, la métrica de distancia para encontrar los vecinos más cercanos es la métrica euclidiana.

Busque los índices de los datos de entrenamiento () que son los siete vecinos más cercanos de cada punto de la consulta Data ().XY

[Idx,D] = knnsearch(Mdl,Y,'K',7,'IncludeTies',true);

y son matrices de celdas de cinco elementos de vectores, con cada vector que tiene al menos siete elemento.IdxD

Visualice las longitudes de los vectores.Idx

cellfun('length',Idx)
ans = 5×1

     8
     7
     7
     7
     7

Dado que la celda contiene un vector con una longitud mayor que = 7, la observación de consulta 1 () está igualmente cerca de al menos dos observaciones.1kY(1,:)X

Visualice los índices de los vecinos más cercanos y sus distancias.Y(1,:)

nn5 = Idx{1}
nn5 = 1×8

    91    98    67    69    71    93    88    95

nn5d = D{1}
nn5d = 1×8

    0.1414    0.2646    0.2828    0.3000    0.3464    0.3742    0.3873    0.3873

Observaciones de entrenamiento y están a 0,3873 cm de distancia de la observación de consultas.88951

Entrenar dos modelos con diferentes métricas de distancia y comparar los vecinos más cercanos de los datos de consulta para los dos modelos.KDTreeSearcherk

Cargue el conjunto de datos de iris de Fisher. Considere las mediciones de pétalo como predictores.

load fisheriris X = meas(:,3:4); % Predictors Y = species;     % Response

Entrenar un objeto de modelo mediante el uso de los predictores.KDTreeSearcher Especifique la distancia de Minkowski con el exponente 5.

KDTreeMdl = KDTreeSearcher(X,'Distance','minkowski','P',5)
KDTreeMdl =    KDTreeSearcher with properties:         BucketSize: 50          Distance: 'minkowski'     DistParameter: 5                 X: [150x2 double]  

Encontrar los 10 vecinos más cercanos a un punto de consulta (), primero usando Minkowski entonces Chebychev métricas de distancia.Xnewpoint El punto de consulta debe tener la misma dimensión de columna que los datos utilizados para entrenar el modelo.

newpoint = [5 1.45]; [IdxMk,DMk] = knnsearch(KDTreeMdl,newpoint,'k',10); [IdxCb,DCb] = knnsearch(KDTreeMdl,newpoint,'k',10,'Distance','chebychev');

y son matrices de 1 por 10 que contienen los índices de fila correspondientes a los vecinos más cercanos al uso de distancias de Minkowski y Chebychev, respectivamente.IdxMkIdxCbXnewpoint El elemento (1, 1) es el más cercano, el elemento (1, 2) es el siguiente más cercano, y así sucesivamente.

Trace los datos de entrenamiento, el punto de consulta y los vecinos más cercanos.

figure; gscatter(X(:,1),X(:,2),Y); title('Fisher''s Iris Data -- Nearest Neighbors'); xlabel('Petal length (cm)'); ylabel('Petal width (cm)'); hold on plot(newpoint(1),newpoint(2),'kx','MarkerSize',10,'LineWidth',2);   % Query point  plot(X(IdxMk,1),X(IdxMk,2),'o','Color',[.5 .5 .5],'MarkerSize',10); % Minkowski nearest neighbors plot(X(IdxCb,1),X(IdxCb,2),'p','Color',[.5 .5 .5],'MarkerSize',10); % Chebychev nearest neighbors legend('setosa','versicolor','virginica','query point',...    'minkowski','chebychev','Location','Best');

Amplíe los puntos de interés.

h = gca; % Get current axis handle. h.XLim = [4.5 5.5]; h.YLim = [1 2]; axis square;

Varias observaciones son iguales, razón por la cual sólo ocho vecinos más cercanos se identifican en la trama.

Argumentos de entrada

contraer todo

Buscador de vecino más cercano, especificado como un objeto de modelo o, respectivamente.ExhaustiveSearcherKDTreeSearcher

Si es un modelo,MdlExhaustiveSearcher knnsearch busca los vecinos más cercanos mediante una búsqueda exhaustiva. Lo contrario knnsearch utiliza el árbol d cultivado para buscar vecinos más cercanos.K

Datos de consulta, especificados como una matriz numérica.

es una-por-matriz.YmK Las filas corresponden a las observaciones (es decir, ejemplos) y las columnas corresponden a los predictores (es decir, variables o características). debe tener el mismo número de columnas que los datos de entrenamiento almacenados.YYMdl.X

Tipos de datos: single | double

Argumentos de par nombre-valor

Especifique pares de argumentos separados por comas opcionales. es el nombre del argumento y es el valor correspondiente. deben aparecer dentro de las cotizaciones.Name,ValueNameValueName Puede especificar varios argumentos de par de nombre y valor en cualquier orden como.Name1,Value1,...,NameN,ValueN

Ejemplo: especifica para encontrar los dos vecinos más cercanos de cada punto en y para utilizar la métrica de distancia Minkowski.'K',2,'Distance','minkowski'Mdl.XY

Para los buscadores de vecinos más cercanos

contraer todo

Métrica de distancia utilizada para buscar los vecinos de los datos de entrenamiento en las observaciones de la consulta, especificadas como el par separado por comas que consta de un vector de caracteres, un escalar de cadena o un identificador de función.'Distance'

Para ambos tipos de buscadores de vecinos más cercanos, knnsearch admite estas métricas de distancia.

ValorDescripción
'chebychev'Chebychev distancia (diferencia máxima de coordenadas).
'cityblock'Distancia de bloque de ciudad.
'euclidean'Distancia euclidiana.
'minkowski'Distancia Minkowski. El exponente predeterminado es 2. Para especificar un exponente diferente, utilice el argumento de par nombre-valor.'P'

Si es un objeto de modelo,MdlExhaustiveSearcher knnsearch también admite estas métricas de distancia.

ValorDescripción
'correlation'Uno menos la correlación lineal de muestra entre las observaciones (tratadas como secuencias de valores).
'cosine'Uno menos el coseno del ángulo incluido entre las observaciones (tratado como vectores de fila).
'hamming'Distancia de Hamming, que es el porcentaje de coordenadas que difieren.
'jaccard'Uno menos el coeficiente Jaccard, que es el porcentaje de coordenadas distintas de cero que difieren.
'mahalanobis'Distancia de Mahalanobis, calculada utilizando una matriz de covarianza definida positiva. Para cambiar el valor de la matriz de covarianza, utilice el argumento de par nombre-valor.'Cov'
'seuclidean'Distancia euclidiana estandarizada. Cada diferencia de coordenadas entre las filas y la matriz de consulta se escala dividiendo por el elemento correspondiente de la desviación estándar calculada desde.Mdl.XMdl.X Para especificar otro escalado, use el argumento de par nombre-valor.'Scale'
'spearman'Uno menos la correlación de rango de Spearman de muestra entre las observaciones (tratadas como secuencias de valores).

Si es un objeto de modelo, también puede especificar un identificador de función para una métrica de distancia personalizada mediante (por ejemplo,).MdlExhaustiveSearcher@@distfun La función de distancia personalizada debe:

  • Tenga el formulario.function D2 = distfun(ZI,ZJ)

  • Tome como argumentos:

    • Un 1 por vector que contiene una sola fila de o, donde es el número de columnas de.KZIMdl.XYKMdl.X

    • Una-por-matriz que contiene varias filas de o, donde es un entero positivo.mKZJMdl.XYm

  • Devuelve un vector de distancias de un-por-1, dondemD2 D2(j) es la distancia entre las observaciones yZI ZJ(j,:).

Para obtener más información, consulte.Las métricas de distancia

Ejemplo: 'Distance','minkowski'

Marca para incluir los vecinos más cercanos que tienen la misma distancia de las observaciones de la consulta, especificado como el par separado por comas que consta de y () o ().'IncludeTies'false0true1

Si es, entonces:IncludeTiestrue

  • incluye todos los vecinos más cercanos cuyas distancias son iguales a la menor distancia en los argumentos de salida, donde es el número de vecinos más cercanos buscados especificado por el argumento de par nombre-valor.knnsearchkk'K'

  • y las matrices son por celda, de forma que cada celda contiene un vector de al menos índices y distancias, respectivamente.IdxDm1k Cada vector en contiene distancias dispuestas en orden ascendente.D Cada fila en contiene los índices de los vecinos más cercanos que corresponden a las distancias en.IdxD

Si es así, elige la observación con el índice más pequeño entre las observaciones que tienen la misma distancia desde un punto de consulta.IncludeTiesfalseknnsearch

Ejemplo: 'IncludeTies',true

Número de vecinos más cercanos para buscar en los datos de entrenamiento por observación de consulta, especificados como el par separado por comas que consta de y un entero positivo.'K'

Ejemplo: 'K',2

Tipos de datos: single | double

Exponente de la métrica de distancia Minkowski, especificada como el par separado por comas que consta de un escalar positivo.'P' Este argumento sólo es válido si es.'Distance''minkowski'

Ejemplo: 'P',3

Tipos de datos: single | double

Para los buscadores de vecinos más cercanos de d-TreeK

contraer todo

Marcar para ordenar los índices devueltos según la distancia, especificado como el par separado por comas que consta de y cualquiera () o ().'SortIndices'true1false0

Para un rendimiento más rápido, puede establecer cuando se cumplen los siguientes pasos:SortIndicesfalse

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

  • es un objeto de modelo.MdlKDTreeSearcher

  • Es.IncludeTiesfalse

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

es de forma predeterminada.SortIndicestrue Cuando es un objeto de modelo o es, la función siempre ordena los índices.MdlExhaustiveSearcherIncludeTiestrue

Ejemplo: 'SortIndices',false

Tipos de datos: logical

Para los buscadores de vecinos más cercanos

contraer todo

Matriz de covarianza para la métrica de distancia de Mahalanobis, especificada como el par separado por comas que consta de una matriz definida positiva. es un-por-matriz, donde es el número de columnas de.'Cov'CovKKKMdl.X Si especifica y no especifica,Cov'Distance','mahalanobis' knnsearch Devuelve un mensaje de error.

Ejemplo: 'Cov',eye(3)

Tipos de datos: single | double

Valor de parámetro de escala para la métrica de distancia euclidiana estandarizada, especificada como el par separado por comas que consta de un vector numérico no negativo. tiene longitud, donde está el número de columnas de.'Scale'ScaleKKMdl.X

El software escala cada diferencia entre los datos de entrenamiento y consulta utilizando el elemento correspondiente de.Scale Si especifica y no especifica,Scale'Distance','seuclidean' knnsearch Devuelve un mensaje de error.

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

Tipos de datos: single | double

Nota

Si especifica,, o, a continuación, y no cambia el valor.'Distance''Cov''P''Scale'Mdl.DistanceMdl.DistParameter

Argumentos de salida

contraer todo

Los índices de datos de entrenamiento de los vecinos más cercanos, devueltos como una matriz numérica o matriz de celdas de vectores numéricos.

  • Si no especifica (de forma predeterminada), entonces es una matriz numérica, donde es el número de filas y es el número de vecinos más cercanos buscados por el argumento de par nombre-valor. indica que es una de las observaciones más cercanas a la observación de la consulta.IncludeTiesfalseIdxmkmYk'K'Idx(j,i)Mdl.X(Idx(j,i),:)kMdl.XY(j,:)

  • Si especifica, a continuación, es una matriz de-por-celda tal que Cell () contiene un vector de al menos los índices de las observaciones más cercanas en la observación de la consulta.'IncludeTies',trueIdxm1jIdx{j}kMdl.XY(j,:)

Si es así, organiza los índices en orden ascendente por distancia.SortIndicestrueknnsearch

Distancias de los vecinos más cercanos a los datos de consulta, devueltos como una matriz numérica o matriz de vectores numéricos.

  • Si no especifica (de forma predeterminada), entonces es una matriz numérica, donde es el número de filas y es el número de vecinos más cercanos buscados por el argumento de par nombre-valor. es la distancia entre y la observación de la consulta con respecto a la métrica de distancia.IncludeTiesfalseDmkmYk'K'D(j,i)Mdl.X(Idx(j,i),:)Y(j,:)

  • Si se especifica, se trata de una matriz por celda, de forma que Cell () contenga un vector de al menos distancias de las observaciones más cercanas a la observación de la consulta.'IncludeTies',trueDm1jD{j}kMdl.XY(j,:)

Si es así, organiza las distancias en orden ascendente.SortIndicestrueknnsearch

Sugerencias

encuentra los puntos (entero positivo) en que son más cercanos para cada punto.knnsearchkMdl.XkY Por el contrario, encuentra todos los puntos que están dentro de la distancia (escalar positivo) de cada punto.rangesearchMdl.XrY

Funcionalidad alternativa

  • knnsearch es una función de objeto que requiere un objeto de modelo y datos de consulta.ExhaustiveSearcherKDTreeSearcher En condiciones equivalentes, el knnsearch función de objeto devuelve los mismos resultados que la función cuando se especifica el argumento de par nombre-valor o, respectivamente.knnsearch'NSMethod','exhaustive''NSMethod','kdtree'

  • Para la clasificación de vecinos más cercanos, consulte y.kfitcknnClassificationKNN

Referencias

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

Capacidades ampliadas

Introducido en R2010a