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 utilizando vecinos más cercanos

Las métricas de distancia en pares

La categorización de 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 descrita a continuación. Se usa para encontrar la distancia entre un conjunto de datos y puntos de consulta.pdist2

Las métricas de distancia

Dada una matriz de datos, que se trata como (1-por-) vectores de filamxnXmxn X1, X2, ..., Xmx, y una matriz de datos, que se trata como (1-por-) vectores de filamynYmyn y1, y2, ...,ymy, las diferentes distancias entre el vector Xs 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),

    ¿Dónde está la matriz-por-diagonal cuyo elemento diagonal esVnnj (S(j))2, donde se encuentra un vector de factores de escalado para cada dimensión.S

  • Mahalanobis distancia

    dst2=(xsyt)C1(xsyt),

    donde está la matriz de covarianza.C

  • Distancia de bloque de ciudad

    dst=j=1n|xsjytj|.

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

  • Distancia Minkowski

    dst=j=1n|xsjytj|pp.

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

  • Chebychev distancia

    dst=maxj{|xsjytj|}.

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

  • La distancia del 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).

  • La distancia Jaccard

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

  • La 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 tomadox1j,x2j, ...Xmx,j, según lo calculado por.tiedrank

    • Rtj es el rango de ytj tomadoy1j,y2j, ...ymy,j, según lo calculado por.tiedrank

    • Rs Y Rt son los vectores de rango de coordenadas de Xs 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 vecino más cercano y búsqueda de RADIUSk

Dado un conjunto de puntos y una función de distancia, la búsqueda de vecino más cercano (NN) le permite encontrar los puntos más cercanos en un punto de consulta o un 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 permite comparar fácilmente los resultados de otras técnicas de clasificación con los resultados 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 computadora

  • 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

  • La 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 la distancia, como la agrupación en clústeres K-means.k

Por el contrario, para un valor real positivo, encuentra todos los puntos en 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 las mismas clases de búsqueda, y utiliza los mismos algoritmos de búsqueda.k

-Búsqueda de vecino más cercano utilizando búsqueda exhaustivak

Cuando los datos de entrada cumplen alguno de los siguientes criterios, utiliza de forma predeterminada el método de búsqueda exhaustivo 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 exhaustivo si el objeto de búsqueda es un objeto de modelo.knnsearchExhaustiveSearcher El método de búsqueda exhaustivo encuentra la distancia desde cada punto de consulta a 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 vecino más cercano utilizando un árbol-dkK

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

  • El número de columnas 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 (en contraposición a las categorías).KBucketSize Los siguientes diagramas ilustran este concepto utilizando objetos para codificar el color de los diferentes "Buckets."patch

Si desea encontrar los vecinos más cercanos a un punto de consulta determinado, hace 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 en 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, solamente el nodo 3 solapa el círculo negro sólido centrado en el punto de consulta con el radio igual a la distancia a los puntos más cercanos dentro del nodo 4.

  4. Busca nodos dentro de ese intervalo para los puntos más cercanos 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 de gran tamaño con menos de 10 dimensiones (columnas) puede ser mucho más eficaz que utilizar el método de búsqueda exhaustivo, ya que solo es necesario calcular un subconjunto de las distancias.Kknnsearch Para maximizar la eficiencia de los d-Trees, 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 eficazmente una búsqueda de los vecinos más cercanos en el modelo de búsqueda utilizando.kknnsearch O bien, puede buscar todos los vecinos dentro de un radio especificado utilizando su 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 mejor para sus datos, tenga en cuenta lo siguiente:

  • ¿Sus datos tienen 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

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

Clasificar datos de consulta

En este ejemplo se muestra cómo clasificar los datos de consulta:

  1. Cultivar un árbol-dK

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

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

Clasifique un nuevo punto basado en las dos últimas columnas de los datos de iris de Fisher. Usar solo las dos últimas columnas hace que sea más fácil trazar.

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

Trace 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 de á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

Hacer los ejes iguales por lo que las distancias calculadas corresponden a las distancias aparentes en el eje de la parcela igual y acercar 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% 

Utilizando una regla basada en el voto mayoritario de los 10 vecinos más cercanos, puede clasificar este nuevo punto como 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 en tres puntos nuevos.

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 la especie 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 con métodos y funciones, consulte las páginas de referencia individuales.knnsearch

Buscar vecinos más cercanos mediante 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. Este ejemplo utiliza datos 2-D 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 las observaciones, y las columnas son, en general, las dimensiones (por ejemplo, predictores).XY

El Chi-cuadrado distancia 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 de Chi-cuadrado. La función de distancia debe:

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

  • Compare con cada fila de.xZ

  • Devuelve 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 y las observaciones correspondientes a cada fila de.DxZ

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

Este ejemplo utiliza ponderaciones arbitrarias para la ilustración.

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

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

y son matrices de 4 por 3.idxD

  • es el índice de fila de la observación más cercana a 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 gráfica.

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 de Chi-cuadrado es equivalente a la métrica de distancia euclidiana, pero con un parámetro de escalado 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 las distancias entre las dos implementaciones de tres vecinos más cercanos son prácticamente equivalentes.

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

El modelo de clasificación le permite:ClassificationKNN

Prepare los datos para la clasificación según el procedimiento en.Pasos en el aprendizaje supervisado A continuación, construya el clasificador utilizando.fitcknn

Construya el clasificador KNN

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

Cargue los datos de iris de Fisher.

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

Construya el clasificador usando.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 usa solo un vecino más cercano.k A menudo, un clasificador es más robusto con más vecinos que eso.

Cambie el tamaño de la vecindad de a, significando que clasifique usando los cuatro vecinos más cercanos.Mdl4Mdl

Mdl.NumNeighbors = 4;

Examine 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 representación y la validación cruzada.k

Construya un clasificador KNN para los datos de iris de Fisher como en.Construya el clasificador KNN

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

Examine la pérdida de reenvío, que, de forma predeterminada, es la fracción de las clasificaciones erróneas de las predicciones de.Mdl (Para los costos, pesos o priores no predeterminados, consulte.).loss

rloss = resubLoss(Mdl)
rloss = 0.0400 

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

Construya un clasificador con validación cruzada 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 usan para el entrenamiento.

kloss = kfoldLoss(CVMdl)
kloss = 0.0333 

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

Predecir clasificación utilizando el clasificador KNN

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

Construya un clasificador KNN para los datos de iris de Fisher como en.Construya el 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'}

Modifique KNN Classifier

En este ejemplo se muestra cómo modificar un clasificador de vecino más cercano.k

Construya un clasificador KNN para los datos de iris de Fisher como en.Construya el 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 valor predeterminado de un vecino más cercano.

Mdl.NumNeighbors = 3;

Compare las predicciones de reenvío 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 de validación cruzada que el modelo con cuatro vecinos (véase).Examine 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 de coseno, debe volver a crear el modelo utilizando el método de búsqueda exhaustivo.

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

El clasificador ahora tiene un error de reenvío más bajo que antes.

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

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

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

Consulte también

| | |