Encontrar el centro de un clúster

Question

Tengo el siguiente resumen con problemas para resaltar los problemas clave.

Tengo 10 puntos cada uno que está a cierta distancia del otro. Quiero

1. ser capaz de encontrar el centro de la agrupación es decir, el punto para el que se minimiza la distancia pairwise a cada otro punto,
   Sea P (j) ~ p (k) representan la distancia pairwise beteen puntos j y k
   p (i) es el punto central del cluster iff p (i) st min [sum (p (j) ~ p (k))] para todos 0 < j, k < = n donde tenemos n puntos en el clúster
2. determine cómo dividir el clúster en dos clústeres una vez que el número de los puntos de datos en el clúster van por encima de algún umbral t.

Esto no es espacio euclidiano. Pero las distancias se pueden resumir de la siguiente manera - p (i) es el punto i:

 p(1) p(2) p(3) p(4) p(5) p(6) p(7) p(8) p(9) p(10) 
p(1) 0  2  1  3  2  3  3  2  3  4 
p(2) 2  0  1  3  2  3  3  2  3  4 
p(3) 1  1  0  2  0  1  2  1  2  3 
p(4) 3  3  2  0  1  2  3  2  3  4  
p(5) 2  2  1  1  0  1  2  1  2  3 
p(6) 3  3  2  2  1  0  3  2  3  4 
p(7) 3  3  2  3  2  3  0  1  2  3 
p(8) 2  2  1  2  1  2  1  0  1  2 
p(9) 3  3  2  3  2  3  2  1  0  1 
p(10) 4  4  3  4  3  4  3  2  1  0 

¿Cómo podría yo calculo que es el punto central de este grupo?

Answer 1

Por lo que yo entiendo esto se parece a K-means, y lo que busca por lo general se conoce como '' medoides.

Ver aquí: http://en.wikipedia.org/wiki/Medoids o aquí: http://en.wikipedia.org/wiki/K-medoids

Answer 2

una)

• valores medios de todas las distancias hallazgo mediana o. = avgAll
• Para cada p, encuentre la distancia promedio a otras máquinas. = avgP (i)
• Elija el más cercano como centro. avgAll ~ = AVGP (i)

b) ni idea por ahora ..

tal vez para cada p, encontrar la máquina más cerca.

por esta lógica hacer un gráfico.

de alguna manera (no sé todavía) dividir el gráfico

Answer 3

Lo que estamos tratando de hacer, o al menos (b) pertenece al análisis cluster. Una rama de las matemáticas/estadísticas/econometría donde los puntos de datos (por ejemplo, los puntos en el espacio n-dimensional) se dividen entre grupos o grupos. Cómo hacer esto no es una pregunta trivial, hay muchas, muchas formas posibles.

Lee más en the wikipedia article on cluster analysis.

Answer 4

Puedo estar a punto de tener ese escalofrío que viene justo antes de mostrar una total estupidez. ¿Pero esto no cede fácilmente a la fuerza bruta? En Python:

distances = [ 
[ 0 , 2 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ], 
[ 2 , 0 , 1 , 3 , 2 , 3 , 3 , 2 , 3 , 4 , ], 
[ 1 , 1 , 0 , 2 , 0 , 1 , 2 , 1 , 2 , 3 , ], 
[ 3 , 3 , 2 , 0 , 1 , 2 , 3 , 2 , 3 , 4 , ], 
[ 2 , 2 , 1 , 1 , 0 , 1 , 2 , 1 , 2 , 3 , ], 
[ 3 , 3 , 2 , 2 , 1 , 0 , 3 , 2 , 3 , 4 , ], 
[ 3 , 3 , 2 , 3 , 2 , 3 , 0 , 1 , 2 , 3 , ], 
[ 2 , 2 , 1 , 2 , 1 , 2 , 1 , 0 , 1 , 2 , ], 
[ 3 , 3 , 2 , 3 , 2 , 3 , 2 , 1 , 0 , 1 , ], 
[ 4 , 4 , 3 , 4 , 3 , 4 , 3 , 2 , 1 , 0 , ], 
] 

currentMinimum = 99999 

for point in range (10) : 
    distance_sum = 0 
    for second_point in range (10) : 
     if point == second_point : continue 
     distance_sum += distances [ point ] [ second_point ] 
    print '>>>>>', point, distance_sum 

    if distance_sum < currentMinimum : 
     currentMinimum = distance_sum 
     centre = point 

print centre