Main Content

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.

Clasificación con los vecinos más cercanos

Métricas de distancia por pares

Clasificar los puntos de consulta en función de su distancia a los puntos de un conjunto de datos de entrenamiento puede ser una forma sencilla pero eficaz de clasificar nuevos puntos. Puede utilizar varias métricas para determinar la distancia, que se describe a continuación. Se utiliza para buscar la distancia entre un conjunto de datos y puntos de consulta.pdist2

Métricas de distancia

Dada una matriz de datos -por-, que se trata como vectores de fila (1 por)mxnXmxn X1, X2, ..., Xmx, y una matriz de datos -por-, que se trata como vectores de fila (1 por )mynYmyn y y1, y y2, ...,y ymy, las distintas distancias entre el vector Xs Y y yt se definen de la siguiente manera:

  • Distancia euclidiana

    dst2=(xsyt)(xsyt).

    La distancia euclidiana es un caso especial de la distancia Minkowski, donde p = 2.

  • Distancia euclidiana estandarizada

    dst2=(xsyt)V1(xsyt),

    donde está la matriz diagonal -por- cuyo elemento diagonal esVnnj (S(j))2, donde hay un vector de factores de escala para cada dimensión.S

  • Distancia Mahalanobis

    dst2=(xsyt)C1(xsyt),

    donde está la matriz de covarianza.C

  • Distancia del bloque de la ciudad

    dst=j=1n|xsjytj|.

    La distancia de la manzana de la ciudad es un caso especial de la distancia Minkowski, donde p = 1.

  • Distancia de Minkowski

    dst=j=1n|xsjytj|pp.

    Para el caso especial de p = 1, la distancia de Minkowski da a la manzana de la ciudad distancia. Para el caso especial de p = 2, la distancia De Minkowski da la distancia euclidiana. Para el caso especial de p = ∞, la distancia de Minkowski da la distancia Chebychev.

  • Distancia de Chebychev

    dst=maxj{|xsjytj|}.

    La distancia de Chebychev es un caso especial de la distancia Minkowski, donde p = ∞.

  • Distancia coseno

    dst=(1xsyt(xsxs)(ytyt)).

  • Distancia de correlación

    dst=1(xsx¯s)(yty¯t)(xsx¯s)(xsx¯s)(yty¯t)(yty¯t),

    Dónde

    x¯s=1njxsj

    Y

    y¯t=1njytj.

  • Distancia de Hamming

    dst=(#(xsjytj)/n).

  • Distancia Jaccard

    dst=#[(xsjytj)((xsj0)(ytj0))]#[(xsj0)(ytj0)].

  • Distancia de Spearman

    dst=1(rsr¯s)(rtr¯t)(rsr¯s)(rsr¯s)(rtr¯t)(rtr¯t),

    Dónde

    • Rsj es el rango de Xsj tomado el controlx1j, x2j, ...Xmx,j, calculado por .tiedrank

    • Rtj es el rango de y ytj tomado el controly1j, y2j, ...y ymy,j, calculado por .tiedrank

    • Rs Y Rt son los vectores de rango coordinado de Xs Y y ytI.e. Rs = (Rs1, Rs2, ... Rsn) y Rt = (rt1, rt2, ... Rtn).

    • r¯s=1njrsj=(n+1)2.

    • r¯t=1njrtj=(n+1)2.

-Búsqueda de vecinos más cercano y búsqueda de radiok

Dado un conjunto de puntos y una función de distancia, la búsqueda -nearest neighbor (NN) le permite encontrar los puntos más cercanos a un punto de consulta o conjunto de puntos.XnkkkXY La técnica de búsqueda NN y los algoritmos basados en NN se utilizan ampliamente como reglas de aprendizaje de referencia.kk La simplicidad relativa de la técnica de búsqueda NN facilita la comparación de los resultados de otras técnicas de clasificación con los resultados de NN.kk La técnica se ha utilizado en diversas áreas tales como:

  • Bioinformática

  • procesamiento de imágenes y compresión de datos

  • recuperación de documentos

  • visión por ordenador

  • base de datos multimedia

  • análisis de datos de marketing

Puede utilizar la búsqueda NN para otros algoritmos de aprendizaje automático, como:k

  • Clasificación NNk

  • regresión ponderada local

  • falta de imputación e interpolación de datos

  • estimación de densidad

También puede utilizar la búsqueda NN con muchas funciones de aprendizaje basadas en distancia, como la agrupación en clústeres de K-means.k

Por el contrario, para un valor real positivo, encuentra todos los puntos que están dentro de una distancia de cada punto en .rrangesearchXrY Esta búsqueda de radio fijo está estrechamente relacionada con la búsqueda NN, ya que admite las mismas métricas de distancia y clases de búsqueda, y utiliza los mismos algoritmos de búsqueda.k

-Búsqueda de vecinos más cercana mediante búsqueda exhaustivak

Cuando los datos de entrada cumplen cualquiera de los siguientes criterios, utiliza el método de búsqueda exhaustiva de forma predeterminada para encontrar los vecinos más cercanos:knnsearchk

  • El número de columnas de es más de 10.X

  • es escaso.X

  • La métrica de distancia es:

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • Una función de distancia personalizada

también utiliza el método de búsqueda exhaustiva si el objeto de búsqueda es un objeto de modelo.knnsearchExhaustiveSearcher El método de búsqueda exhaustiva busca la distancia desde cada punto de consulta hasta cada punto en , los clasifica en orden ascendente y devuelve los puntos con las distancias más pequeñas.Xk Por ejemplo, este diagrama muestra el k = 3 vecinos más cercanos.

-Búsqueda de vecinos más cercano usando un d-TreekK

Cuando los datos de entrada cumplen todos los criterios siguientes, crea un árbol d de forma predeterminada para buscar los vecinos más cercanos:knnsearchKk

  • El número de columnas de es menor que 10.X

  • no es escaso.X

  • La métrica de distancia es:

    • (predeterminado)'euclidean'

    • 'cityblock'

    • 'minkowski'

    • 'chebychev'

también utiliza un árbol d si el objeto de búsqueda es un objeto de modelo.knnsearchKKDTreeSearcher

los árboles d dividen los datos en nodos con como máximo (el valor predeterminado es 50) puntos por nodo, en función de las coordenadas (a diferencia de las categorías).KBucketSize Los diagramas siguientes ilustran este concepto utilizando objetos para codificar en color los diferentes "buckets".patch

Si desea encontrar los vecinos -más cercanos a un punto de consulta determinado, haga lo siguiente:kknnsearch

  1. Determina el nodo al que pertenece el punto de consulta. En el ejemplo siguiente, el punto de consulta (32,90) pertenece al nodo 4.

  2. Busca los puntos más cercanos dentro de ese nodo y su distancia al punto de consulta.k En el ejemplo siguiente, los puntos de los círculos rojos son equidistantes del punto de consulta y son los puntos más cercanos al punto de consulta dentro del nodo 4.

  3. Elige todos los demás nodos que tengan cualquier área que esté dentro de la misma distancia, en cualquier dirección, desde el punto de consulta hasta el punto más cercano.k En este ejemplo, solo el nodo 3 se superpone al círculo negro sólido centrado en el punto de consulta con un radio igual a la distancia a los puntos más cercanos dentro del nodo 4.

  4. Busca nodos dentro de ese intervalo para cualquier punto más cercano al punto de consulta. En el ejemplo siguiente, el punto de un cuadrado rojo está ligeramente más cerca del punto de consulta que los del nodo 4.

El uso de un árbol d para conjuntos de datos grandes con menos de 10 dimensiones (columnas) puede ser mucho más eficaz que usar el método de búsqueda exhaustiva, ya que necesita calcular solo un subconjunto de las distancias.Kknnsearch Para maximizar la eficiencia de los árboles d, utilice un modelo.KKDTreeSearcher

¿Qué son los objetos de modelo de búsqueda?

Básicamente, los objetos de modelo son una forma cómoda de almacenar información. Los modelos relacionados tienen las mismas propiedades con valores y tipos relevantes para un método de búsqueda especificado. Además de almacenar información dentro de los modelos, puede realizar ciertas acciones en los modelos.

Puede realizar de forma eficiente una búsqueda de vecinos más cercanos en su modelo de búsqueda utilizando .kknnsearch O bien, puede buscar todos los vecinos dentro de un radio especificado utilizando el modelo de búsqueda y .rangesearch Además, hay un genérico y funciones que buscan sin crear o usar un modelo.knnsearchrangesearch

Para determinar qué tipo de modelo y método de búsqueda es el mejor para sus datos, tenga en cuenta lo siguiente:

  • ¿Tienen sus datos muchas columnas, digamos más de 10? El modelo puede funcionar mejor.ExhaustiveSearcher

  • ¿Sus datos son escasos? Utilice el modelo.ExhaustiveSearcher

  • ¿Desea utilizar una de estas métricas de distancia para encontrar los vecinos más cercanos? Utilice el modelo.ExhaustiveSearcher

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • Una función de distancia personalizada

  • ¿Su conjunto de datos es enorme (pero con menos de 10 columnas)? Utilice el modelo.KDTreeSearcher

  • ¿Está buscando los vecinos más cercanos para un gran número de puntos de consulta? Utilice el modelo.KDTreeSearcher

Clasificar datos de consulta

Este ejemplo muestra cómo clasificar los datos de consulta por:

  1. Cultivo de un árbol dK

  2. Realizar una búsqueda de vecino más cercana utilizando el árbol cultivado.k

  3. Asignar a cada punto de consulta la clase con la representación más alta entre sus respectivos vecinos más cercanos.

Clasificar un nuevo punto basado en las dos últimas columnas de los datos del iris de Fisher. El uso de solo las dos últimas columnas facilita el trazado.

load fisheriris x = meas(:,3:4); gscatter(x(:,1),x(:,2),species) legend('Location','best')

Trazar el nuevo punto.

newpoint = [5 1.45]; line(newpoint(1),newpoint(2),'marker','x','color','k',...    'markersize',10,'linewidth',2)

Prepare un modelo de buscador de vecinos del árbol d.K

Mdl = KDTreeSearcher(x)
Mdl =    KDTreeSearcher with properties:         BucketSize: 50          Distance: 'euclidean'     DistParameter: []                 X: [150x2 double]  

es un modelo.MdlKDTreeSearcher De forma predeterminada, la métrica de distancia que utiliza para buscar vecinos es la distancia euclidiana.

Encuentre los 10 puntos de muestra más cercanos al nuevo punto.

[n,d] = knnsearch(Mdl,newpoint,'k',10); line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o',...     'linestyle','none','markersize',10)

Parece que sólo ha encontrado a los ocho vecinos más cercanos.knnsearch De hecho, este conjunto de datos en particular contiene valores duplicados.

x(n,:)
ans = 10×2

    5.0000    1.5000
    4.9000    1.5000
    4.9000    1.5000
    5.1000    1.5000
    5.1000    1.6000
    4.8000    1.4000
    5.0000    1.7000
    4.7000    1.4000
    4.7000    1.4000
    4.7000    1.5000

Haga que los ejes sean iguales para que las distancias calculadas correspondan a las distancias aparentes en el eje de trazado iguales y haga zoom para ver mejor a los vecinos.

xlim([4.5 5.5]); ylim([1 2]); axis square

Encuentra la especie de los 10 vecinos.

tabulate(species(n))
       Value    Count   Percent    virginica        2     20.00%   versicolor        8     80.00% 

Usando una regla basada en el voto mayoritario de los 10 vecinos más cercanos, puede clasificar este nuevo punto como un versicolor.

Identifique visualmente a los vecinos dibujando un círculo alrededor del grupo de ellos. Defina el centro y el diámetro de un círculo, en función de la ubicación del nuevo punto.

ctr = newpoint - d(end); diameter = 2*d(end); % Draw a circle around the 10 nearest neighbors. h = rectangle('position',[ctr,diameter,diameter],...    'curvature',[1 1]); h.LineStyle = ':';

Con el mismo conjunto de datos, busque los 10 vecinos más cercanos a tres nuevos puntos.

figure  newpoint2 = [5 1.45;6 2;2.75 .75]; gscatter(x(:,1),x(:,2),species) legend('location','best') [n2,d2] = knnsearch(Mdl,newpoint2,'k',10); line(x(n2,1),x(n2,2),'color',[.5 .5 .5],'marker','o',...    'linestyle','none','markersize',10) line(newpoint2(:,1),newpoint2(:,2),'marker','x','color','k',...    'markersize',10,'linewidth',2,'linestyle','none')

Encuentra las especies de los 10 vecinos más cercanos para cada nuevo punto.

tabulate(species(n2(1,:)))
       Value    Count   Percent    virginica        2     20.00%   versicolor        8     80.00% 
tabulate(species(n2(2,:)))
      Value    Count   Percent   virginica       10    100.00% 
tabulate(species(n2(3,:)))
       Value    Count   Percent   versicolor        7     70.00%       setosa        3     30.00% 

Para obtener más ejemplos de uso de métodos y funciones, consulte las páginas de referencia individuales.knnsearch

Encontrar vecinos más cercanos usando una métrica de distancia personalizada

Este ejemplo muestra cómo encontrar los índices de las tres observaciones más cercanas en cada observación con respecto a la distancia chi-cuadrada.XY Esta métrica de distancia se utiliza en el análisis de correspondencia, particularmente en aplicaciones ecológicas.

Genere aleatoriamente datos distribuidos normalmente en dos matrices. El número de filas puede variar, pero el número de columnas debe ser igual. En este ejemplo se utilizan datos 2D para el trazado.

rng(1); % For reproducibility X = randn(50,2); Y = randn(4,2);  h = zeros(3,1); figure; h(1) = plot(X(:,1),X(:,2),'bx'); hold on; h(2) = plot(Y(:,1),Y(:,2),'rs','MarkerSize',10); title('Heterogenous Data')

Las filas de y corresponden a observaciones, y las columnas son, en general, dimensiones (por ejemplo, predictores).XY

La distancia chi-cuadrada entre los puntos -dimensionales y esjxz

<math display="block">
<mrow>
<mi>χ</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>,</mo>
<mi>z</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<msqrt>
<mrow>
<mstyle displaystyle="true" scriptlevel="0">
<mrow>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mi>J</mi>
</mrow>
</munderover>
<msub>
<mrow>
<mi>w</mi>
</mrow>
<mrow>
<mi>j</mi>
</mrow>
</msub>
<msup>
<mrow>
<mo>(</mo>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>j</mi>
</mrow>
</msub>
<mo>-</mo>
<msub>
<mrow>
<mi>z</mi>
</mrow>
<mrow>
<mi>j</mi>
</mrow>
</msub>
<mo>)</mo>
</mrow>
<mrow>
<mn>2</mn>
</mrow>
</msup>
</mrow>
</mstyle>
</mrow>
</msqrt>
<mo>,</mo>
</mrow>
</math>

Dónde

<math display="block">
<mrow>
<msub>
<mrow>
<mi>w</mi>
</mrow>
<mrow>
<mi>j</mi>
</mrow>
</msub>
</mrow>
</math>
es el peso asociado a la dimensión.j

Elija ponderaciones para cada cota y especifique la función de distancia chi-cuadrada. La función de distancia debe:

  • Tome como argumentos de entrada una fila de , por ejemplo, , y la matriz .XxZ

  • Compárese con cada fila de .xZ

  • Devolver un vector de longitudD

    <math display="block">
    <mrow>
    <msub>
    <mrow>
    <mi>n</mi>
    </mrow>
    <mrow>
    <mi>z</mi>
    </mrow>
    </msub>
    </mrow>
    </math>
    Dónde
    <math display="block">
    <mrow>
    <msub>
    <mrow>
    <mi>n</mi>
    </mrow>
    <mrow>
    <mi>z</mi>
    </mrow>
    </msub>
    </mrow>
    </math>
    es el número de filas de .Z Cada elemento de es la distancia entre la observación correspondiente a y las observaciones correspondientes a cada fila de .DxZ

w = [0.4; 0.6]; chiSqrDist = @(x,Z)sqrt((bsxfun(@minus,x,Z).^2)*w);

En este ejemplo se utilizan ponderaciones arbitrarias para la ilustración.

Encuentre los índices de las tres observaciones más cercanas en cada observación en .XY

k = 3; [Idx,D] = knnsearch(X,Y,'Distance',chiSqrDist,'k',k);

y son 4 por 3 matrices.idxD

  • es el índice de fila de la observación más cercana en la observación de , y es su distancia.idx(j,1)XjYD(j,1)

  • es el índice de fila de la siguiente observación más cercana en la observación de , y es su distancia.idx(j,2)XjYD(j,2)

  • Y así sucesivamente.

Identifique las observaciones más cercanas en la parcela.

for j = 1:k;     h(3) = plot(X(Idx(:,j),1),X(Idx(:,j),2),'ko','MarkerSize',10); end  legend(h,{'\texttt{X}','\texttt{Y}','Nearest Neighbor'},'Interpreter','latex'); title('Heterogenous Data and Nearest Neighbors') hold off;

Varias observaciones de compartir vecinos más cercanos.Y

Compruebe que la métrica de distancia chi-cuadrada es equivalente a la métrica de distancia euclidiana, pero con un parámetro de escala opcional.

[IdxE,DE] = knnsearch(X,Y,'Distance','seuclidean','k',k,...     'Scale',1./(sqrt(w))); AreDiffIdx = sum(sum(Idx ~= IdxE))
AreDiffIdx = 0 
AreDiffDist = sum(sum(abs(D - DE) > eps))
AreDiffDist = 0 

Los índices y distancias entre las dos implementaciones de tres vecinos más cercanos son prácticamente equivalentes.

-Clasificación de vecinos más cercano para el aprendizaje supervisadoK

El modelo de clasificación le permite:ClassificationKNN

Prepare sus datos para la clasificación de acuerdo con el procedimiento en .Pasos en el Aprendizaje Supervisado A continuación, construya el clasificador utilizando .fitcknn

Construir clasificador KNN

Este ejemplo muestra cómo construir un clasificador de vecino más cercano para los datos de iris de Fisher.k

Cargue los datos del iris de Fisher.

load fisheriris X = meas;    % Use all data for fitting Y = species; % Response data

Construya el clasificador utilizando .fitcknn

Mdl = fitcknn(X,Y)
Mdl =    ClassificationKNN              ResponseName: 'Y'     CategoricalPredictors: []                ClassNames: {'setosa'  'versicolor'  'virginica'}            ScoreTransform: 'none'           NumObservations: 150                  Distance: 'euclidean'              NumNeighbors: 1     Properties, Methods  

Un clasificador de vecino predeterminado -más cercano utiliza un solo vecino más cercano.k A menudo, un clasificador es más robusto con más vecinos que eso.

Cambie el tamaño de vecindad de a , lo que significa que clasifica usando los cuatro vecinos más cercanos.Mdl4Mdl

Mdl.NumNeighbors = 4;

Examinar la calidad del clasificador KNN

En este ejemplo se muestra cómo examinar la calidad de un clasificador de vecino más cercano mediante la resustitución y la validación cruzada.k

Construir un clasificador KNN para los datos del iris Fisher como en .Construir clasificador KNN

load fisheriris X = meas;     Y = species;  rng(10); % For reproducibility Mdl = fitcknn(X,Y,'NumNeighbors',4);

Examine la pérdida de resustitución, que, de forma predeterminada, es la fracción de las clasificaciones erróneas de las predicciones de .Mdl (Para el costo, pesos o antecedentes no predeterminados, véase .).loss

rloss = resubLoss(Mdl)
rloss = 0.0400 

El clasificador predice incorrectamente el 4% de los datos de entrenamiento.

Construir un clasificador validado cruzadamente a partir del modelo.

CVMdl = crossval(Mdl);

Examine la pérdida de validación cruzada, que es la pérdida media de cada modelo de validación cruzada al predecir los datos que no se utilizan para el entrenamiento.

kloss = kfoldLoss(CVMdl)
kloss = 0.0333 

La precisión de clasificación validada cruzada se asemeja a la precisión de la resustitución. Por lo tanto, puede esperar clasificar erróneamente aproximadamente el 4% de los datos nuevos, suponiendo que los nuevos datos tienen aproximadamente la misma distribución que los datos de entrenamiento.Mdl

Predecir clasificación utilizando clasificador KNN

Este ejemplo muestra cómo predecir la clasificación para un clasificador de vecino -más cercano.k

Construir un clasificador KNN para los datos del iris Fisher como en .Construir clasificador KNN

load fisheriris X = meas;     Y = species;  Mdl = fitcknn(X,Y,'NumNeighbors',4);

Predecir la clasificación de una flor promedio.

flwr = mean(X); % an average flower flwrClass = predict(Mdl,flwr)
flwrClass = 1x1 cell array
    {'versicolor'}

Modificar clasificador KNN

Este ejemplo muestra cómo modificar un clasificador de vecino -más cercano.k

Construir un clasificador KNN para los datos del iris Fisher como en .Construir clasificador KNN

load fisheriris X = meas;     Y = species;  Mdl = fitcknn(X,Y,'NumNeighbors',4);

Modifique el modelo para utilizar los tres vecinos más cercanos, en lugar del vecino más cercano predeterminado.

Mdl.NumNeighbors = 3;

Compare las predicciones de resustitución y la pérdida de validación cruzada con el nuevo número de vecinos.

loss = resubLoss(Mdl)
loss = 0.0400 
 rng(10); % For reproducibility CVMdl = crossval(Mdl,'KFold',5); kloss = kfoldLoss(CVMdl)
kloss = 0.0333 

En este caso, el modelo con tres vecinos tiene la misma pérdida validada cruzada que el modelo con cuatro vecinos (consulte ).Examinar la calidad del clasificador KNN

Modifique el modelo para utilizar la distancia de coseno en lugar del valor predeterminado y examine la pérdida. Para utilizar la distancia coseno, debe volver a crear el modelo mediante el método de búsqueda exhaustiva.

CMdl = fitcknn(X,Y,'NSMethod','exhaustive','Distance','cosine'); CMdl.NumNeighbors = 3; closs = resubLoss(CMdl)
closs = 0.0200 

El clasificador ahora tiene un error de resustitución más bajo que antes.

Compruebe la calidad de una versión validada cruzada del nuevo modelo.

CVCMdl = crossval(CMdl); kcloss = kfoldLoss(CVCMdl)
kcloss = 0.0200 

tiene una pérdida mejor validada cruzada que .CVCMdlCVMdl Sin embargo, en general, la mejora del error de resustitución no produce necesariamente un modelo con mejores predicciones de prueba-muestra.

Consulte también

| | |