Saltar al contenido

Cómo calcular distancias entre centroides y matriz de datos (para el algoritmo kmeans)

Si hallas alguna incompatibilidad en tu código o trabajo, recuerda probar siempre en un entorno de testing antes subir el código al proyecto final.

Solución:

Su pregunta principal parece ser cómo calcular las distancias entre una matriz de datos y algún conjunto de puntos (“centros”).

Para esto, puede escribir una función que tome como entrada una matriz de datos y su conjunto de puntos y devuelva distancias para cada fila (punto) en la matriz de datos a todos los “centros”.

Aquí hay una función de este tipo:

myEuclid <- function(points1, points2) 
    distanceMatrix <- matrix(NA, nrow=dim(points1)[1], ncol=dim(points2)[1])
    for(i in 1:nrow(points2)) 
        distanceMatrix[,i] <- sqrt(rowSums(t(t(points1)-points2[i,])^2))
    
    distanceMatrix

points1 es la matriz de datos con puntos como filas y dimensiones como columnas. points2 es la matriz de centros (puntos como filas nuevamente). La primera línea de código simplemente define la matriz de respuesta (que tendrá tantas filas como filas haya en la matriz de datos y tantas columnas como centros). Entonces el punto i,j en la matriz de resultados será la distancia desde el con señala al jth centrar.

Luego, el bucle for itera sobre todos los centros. Para cada centro, calcula la distancia euclidiana desde cada punto al centro actual y devuelve el resultado. Esta línea aquí: sqrt(rowSums(t(t(points1)-points2[i,])^2)) es la distancia euclidiana. Inspeccione más de cerca y busque la fórmula si tiene algún problema con eso. (las transposiciones allí se realizan principalmente para asegurarse de que la resta se realice en filas).

Ahora también puede implementar el algoritmo k-means:

myKmeans <- function(x, centers, distFun, nItter=10) 
    clusterHistory <- vector(nItter, mode="list")
    centerHistory <- vector(nItter, mode="list")

    for(i in 1:nItter) 
        distsToCenters <- distFun(x, centers)
        clusters <- apply(distsToCenters, 1, which.min)
        centers <- apply(x, 2, tapply, clusters, mean)
        # Saving history
        clusterHistory[[i]] <- clusters
        centerHistory[[i]] <- centers
    

    list(clusters=clusterHistory, centers=centerHistory)

Como puede ver, también es una función muy simple: toma la matriz de datos, los centros, su función de distancia (la definida anteriormente) y el número de iteraciones deseadas.

Los grupos se definen asignando el centro más cercano para cada punto. Y los centros se actualizan como una media de los puntos asignados a ese centro. Que es un algoritmo básico de k-medias).

Probémoslo. Defina algunos puntos aleatorios (en 2d, entonces número de columnas = 2)

mat <- matrix(rnorm(100), ncol=2)

Asigne 5 puntos aleatorios de esa matriz como centros iniciales:

centers <- mat[sample(nrow(mat), 5),]

Ahora ejecuta el algoritmo:

theResult <- myKmeans(mat, centers, myEuclid, 10)

Aquí están los centros en la décima iteración:

theResult$centers[[10]]
        [,1]        [,2]
1 -0.1343239  1.27925285
2 -0.8004432 -0.77838017
3  0.1956119 -0.19193849
4  0.3886721 -1.80298698
5  1.3640693 -0.04091114

Compare eso con implementado kmeans función:

theResult2 <- kmeans(mat, centers, 10, algorithm="Forgy")

theResult2$centers
        [,1]        [,2]
1 -0.1343239  1.27925285
2 -0.8004432 -0.77838017
3  0.1956119 -0.19193849
4  0.3886721 -1.80298698
5  1.3640693 -0.04091114

Funciona bien. Sin embargo, nuestra función rastrea las iteraciones. Podemos trazar el progreso en las primeras 4 iteraciones de esta manera:

par(mfrow=c(2,2))
for(i in 1:4) 
    plot(mat, col=theResult$clusters[[i]], main=paste("itteration:", i), xlab="x", ylab="y")
    points(theResult$centers[[i]], cex=3, pch=19, col=1:nrow(theResult$centers[[i]]))

K significa

Bonito.

Sin embargo, este diseño simple permite mucho más. Por ejemplo, si queremos usar otro tipo de distancia (no euclidiana), podemos usar cualquier función que tome datos y centros como entradas. Aquí hay uno para distancias de correlación:

myCor <- function(points1, points2) 
    return(1 - ((cor(t(points1), t(points2))+1)/2))

Y luego podemos hacer Kmeans basados ​​en esos:

theResult <- myKmeans(mat, centers, myCor, 10)

La imagen resultante para 4 iteraciones se ve así:

ingrese la descripción de la imagen aquí

Incluso si especificamos 5 grupos, quedaban 2 al final. Esto se debe a que para 2 dimensiones la correlación puede tener valores, ya sea +1 o -1. Luego, al buscar los grupos, cada punto se asigna a un centro, incluso si tiene la misma distancia a varios centros, se elige el primero.

De todos modos, esto ahora está saliendo de su alcance. La conclusión es que hay muchas métricas de distancia posibles y una función simple le permite usar cualquier distancia que desee y rastrear los resultados en iteraciones.

Se modificó la función de matriz de distancia anterior (se agregó otro bucle para el número de puntos) ya que la función anterior muestra solo la distancia del primer punto desde todos los grupos y no todos los puntos, que es lo que busca la pregunta:

myEuclid <- function(points1, points2) 
    distanceMatrix <- matrix(NA, nrow=dim(points1)[1], ncol=dim(points2)[1])
    for(i in 1:nrow(points2)) 
        for (j in c(1:dim(t(points1))[2])) 
            
        distanceMatrix[j,i] <- sqrt(rowSums(t(t(points1)[,j]-t(points2[i,]))^2))
            
    
    distanceMatrix

¡Avísame si esto funciona bien!

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *