algorithm - clustering - Algoritmo para detectar "clusters" de puntos
algoritmos de agrupamiento clustering (17)
- Ajustar una función de densidad de probabilidad a los datos. Usaría una "mezcla de gaussianos" y lo ajustaría usando el aprendizaje de maximización de expectativas preparado por el algoritmo K-means. El K-means en sí mismo a veces puede ser suficiente sin EM. La cantidad de clústeres debería estar cebada con un algoritmo de selección de orden modelo.
- Luego, cada punto se puede calificar con p (x) usando el modelo. Es decir, obtener la probabilidad posterior de que el punto haya sido generado por el modelo.
- Encuentre el máximo de p (x) para encontrar los centroides del grupo.
Esto puede codificarse muy rápidamente en una herramienta como Matlab utilizando una caja de herramientas de aprendizaje automático. Los grupos de aprendizaje MoG / EM / K-Means se discuten ampliamente en la web / textos estándar. Mi texto favorito es "Clasificación de patrones" por Duda / Hart.
Tengo un área 2D con "puntos" distribuidos en esta área. Ahora trato de detectar "clusters" de puntos, es decir, áreas con una cierta alta densidad de puntos.
¿Alguna idea (o enlaces a artículos con pensamientos sobre) cómo detectar elegantemente estas áreas?
"Áreas con una cierta alta densidad" implica que usted sabe aproximadamente cuántos puntos por unidad de área considera que son altos. Esto me lleva a un enfoque de cuadrícula, donde se divide el área total en subáreas del tamaño adecuado, luego se cuenta el número de puntos en cada área. Una vez que encuentre áreas de su grilla cerca de su umbral, también puede buscar áreas vecinas de la grilla.
¿Has probado soluciones simples y listas para usar como ImagXpress de Accusoft Pegasus?
El método BlobRemoval se puede ajustar para el conteo de píxeles y la densidad para encontrar perforaciones, incluso si no son continuas. (También puedes probar una función Dilate para cerrar huecos)
Con un poco de juego, es probable que pueda obtener los resultados que necesita en la gran mayoría de los casos, con muy poco código o ciencia.
DO#:
public void DocumentBlobRemoval (Área de rectángulo, int MinPixelCount, int MaxPixelCount, MinDensity corto)
¿Qué le parece si define una resolución arbitraria para su espacio y calcula para cada punto de esa matriz, una medida de la distancia desde ese punto a todos los puntos, entonces podría hacer un "gráfico de calor" y usar un umbral para definir los clústeres.
Es un buen ejercicio para procesar, quizás más tarde publique una solución.
EDITAR:
Aquí está:
//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
//parameters
int resolution = 5; //distance between points in the gridq
int distance = 8; //distance at wich two points are considered near
float threshold = 0.5;
int level = 240; //leven to detect the dots
int sensitivity = 1; //how much does each dot matters
//calculate the "heat" on each point of the grid
color black = color(0,0,0);
loadPixels();
for(int a=0; a<width; a+=resolution){
for(int b=0; b<height; b+=resolution){
for(int x=0; x<width; x++){
for(int y=0; y<height; y++){
color c = sample.pixels[y*sample.width+x];
/**
* the heat should be a function of the brightness and the distance,
* but this works (tm)
*/
if(brightness(c)<level && dist(x,y,a,b)<distance){
heat[a][b] += sensitivity;
}
}
}
}
}
//render the output
for(int a=0; a<width; ++a){
for(int b=0; b<height; ++b){
pixels[b*sample.width+a] = color(heat[a][b],0,0);
}
}
updatePixels();
filter(THRESHOLD,threshold);
EDIT 2 (código ligeramente menos ineficiente pero mismo resultado):
//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
int dotQ = 0;
int[][] dots = new int[width*height][2];
int X = 0;
int Y = 1;
//parameters
int resolution = 1; //distance between points in the grid
int distance = 20; //distance at wich two points are considered near
float threshold = 0.6;
int level = 240; //minimum brightness to detect the dots
int sensitivity = 1; //how much does each dot matters
//detect all dots in the sample
loadPixels();
for(int x=0; x<width; x++){
for(int y=0; y<height; y++){
color c = pixels[y*sample.width+x];
if(brightness(c)<level) {
dots[dotQ][X] += x;
dots[dotQ++][Y] += y;
}
}
}
//calculate heat
for(int x=0; x<width; x+=resolution){
for(int y=0; y<height; y+=resolution){
for(int d=0; d<dotQ; d++){
if(dist(x,y,dots[d][X],dots[d][Y]) < distance)
heat[x][y]+=sensitivity;
}
}
}
//render the output
for(int a=0; a<width; ++a){
for(int b=0; b<height; ++b){
pixels[b*sample.width+a] = color(heat[a][b],0,0);
}
}
updatePixels();
filter(THRESHOLD,threshold);
/** This smooths the ouput with low resolutions
* for(int i=0; i<10; ++i) filter(DILATE);
* for(int i=0; i<3; ++i) filter(BLUR);
* filter(THRESHOLD);
*/
Y la salida con una muestra Kent (reducida):
¿Qué tal un enfoque de morfología?
Dilate la imagen con umbral por algún número (dependiendo de la densidad de puntos), luego los puntos en un grupo aparecerán como un solo objeto.
OpenCV admite operaciones morfológicas (como lo haría una gama de bibliotecas de procesamiento de imágenes):
http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology
Aplique un filtro de desenfoque a una copia de su área 2D. Algo como
1 2 3 2 1
2 4 6 4 2
3 6 9 6 3
2 4 6 4 2
1 2 3 2 1
Las áreas "más oscuras" ahora identifican grupos de puntos.
Aquí hay un gran tutorial de algoritmos de agrupamiento, que analizan K-means y K-gaussians.
Calculo las distancias desde cada punto a todos los otros puntos. Luego ordena las distancias. Los puntos que tienen una distancia uno del otro que está por debajo de un umbral se consideran cercanos . Un grupo de puntos que está cerca uno del otro es un grupo.
El problema es que el clúster puede ser claro para un ser humano cuando ve el gráfico, pero no tiene una definición matemática clara. Necesita definir su umbral cercano , probablemente ajustando empíricamente hasta que el resultado de su algoritmo sea (más o menos) igual a lo que percibe como agrupado.
Creo que depende de la separación que haya entre los puntos y los clústeres. Si las distancias son grandes e irregulares, inicialmente triangulate los puntos y luego eliminaré / esconderé todos los triángulos con longitudes de borde estadísticamente grandes. Las sub-triangulaciones restantes forman grupos de forma arbitraria. Atravesar los bordes de estas sub-triangulaciones produce polígonos que se pueden usar para determinar qué puntos específicos se encuentran en cada grupo. Los polígonos también se pueden comparar para conocer formas, como el toro de Kent Fredric, según sea necesario.
OMI, los métodos de cuadrícula son buenos para soluciones rápidas y sucias, pero se ponen muy hambrientos muy rápidamente en datos dispersos. Los árboles cuádruples son mejores, pero los TIN son mi favorito personal para cualquier análisis más complejo.
El clúster 3.0 incluye una biblioteca de métodos C para llevar a cabo la agrupación estadística. Tiene algunos métodos diferentes que pueden o no resolver su problema depediendo en qué forma toman sus agrupaciones de puntos. La biblioteca está disponible aquí y se distribuye bajo la licencia de Python.
Esto realmente suena como una pregunta académica.
La solución que viene a la mente implica r * árboles. Esto divide su área total en cuadros de tamaño individual y posiblemente superpuestos. Después de hacer esto, puede determinar si cada cuadro representa un "grupo" o no para usted calculando la distancia media.
Si ese enfoque se vuelve difícil de implementar, es mejor dividir su cuadrícula de datos en subdivisiones de igual tamaño y determinar si un clúster se produce en cada una; Sin embargo, tendrás que ser muy consciente de las condiciones del borde con este enfoque. Sugeriría que después de la división inicial, atravieses y recombinas áreas con puntos de datos dentro de un cierto umbral del borde definido.
Para agregar un poco de ayuda a la declaración de Trebs , creo que es importante primero definir de forma realista cuál es la definición de un clúster, seguro, "puntos más cerca", eso es bastante vago.
Toma este conjunto de muestras que generé, sé que hay una forma de conglomerado allí, lo creé.
Sin embargo, identificar este "cluster" programáticamente puede ser difícil.
Un ser humano podría considerar que es un clúster toroidal grande, pero es más probable que su programa automatizado lo decida una serie de clusters más pequeños en una proximidad cercana.
Además, tenga en cuenta que hay regiones de super alta densidad, que están en el contexto de la imagen más grande, meramente distracciones
Deberá tener en cuenta este comportamiento y posiblemente encadenar agrupaciones de densidad similar separadas solo por vacíos insignificantes de menor densidad, según la aplicación específica.
Cualquier cosa que desarrolles, al menos estaría interesado en cómo identifica los datos en este conjunto.
(Creo que investigar las tecnologías detrás de HDRI ToneMapping podría estar en orden, porque funcionan más o menos en densidad de luz, y hay mapas de tonos "locales" y de tonos "globales", cada uno arrojando resultados diferentes)
Permítanme organizar esto como un trabajo de investigación
a. Planteamiento del problema
Para citar a Epaga : "Tengo un área 2D con" puntos "distribuidos en esta área. Ahora estoy tratando de detectar" cúmulos "de puntos, es decir, áreas con una cierta alta densidad de puntos".
Tenga en cuenta que en ninguna parte se menciona que los puntos son de una imagen. (Aunque podrían ordenarse como uno).
b. Caso de Metodo 1: Si los puntos son simplemente puntos (puntos = puntos en el espacio 2D). En este escenario, ya tendrá ambas ubicaciones X e Y para todos los puntos. El problema se reduce a uno de agrupar los puntos. Ivan ha hecho un gran trabajo proponiendo una solución. También resumió otras respuestas de sabor similar. Mis 2cts, además de su publicación, es que consideres si sabes la cantidad de clusters a priori o no. Algoritmos (agrupamiento supervisado vs no supervisado se puede elegir en consecuencia).
caso 2: si los puntos provienen de una imagen. Aquí el problema necesita ser aclarado. Déjame explicarte usando esta imagen Si no se hace distinción en el valor gris de los puntos, los grupos 1, 2, 3, 4 y 5 son todos "grupos distintos". Sin embargo, si la distinción se hace sobre la base del valor de gris, el grupo 5 es complicado, ya que el punto tiene diferentes valores de gris.
De todos modos, este problema se puede reducir al caso 1 mediante el barrido de trama de la imagen y el almacenamiento de coordenadas de píxeles distintos de cero (no blancos). Los algoritmos de agrupamiento, como se propuso anteriormente, pueden emplearse para calcular la cantidad de clusters y centros de clusters.
Podría intentar crear una representación de Quadtree de los datos. Los caminos más cortos en el gráfico corresponderían a áreas de alta densidad.
O, para decirlo más claramente: dado un Quadtree y un recorrido de nivel, cada nodo de nivel inferior compuesto por "puntos" representaría un área de alta densidad. A medida que aumenta el nivel de los nodos, dichos nodos representan áreas de "puntos" de menor densidad
Podría superponer una grilla lógica sobre su plano. Si una cuadrícula tiene una cierta cantidad de puntos contenidos, se considera "densa" y luego puede reducirse. Esto se hace mucho en aplicaciones GIS cuando se trabaja con tolerancias de clúster. Usar la grilla ayuda a compartimentar su algoritmo de adelgazamiento.
Podría usar un algoritmo genético para esto. Si define un "clúster" como, por ejemplo, un subárea rectangular con una densidad de puntos alta, puede crear un conjunto inicial de "soluciones", cada una de las cuales consiste en cierto número de clústeres rectangulares no superpuestos generados aleatoriamente. . A continuación, escribiría una "función de acondicionamiento físico" que evalúa cada solución; en este caso, desearía que la función de acondicionamiento físico minimice el número total de grupos mientras maximiza la densidad de puntos dentro de cada grupo.
Su conjunto inicial de "soluciones" será terrible, muy probablemente, pero algunas serán ligeramente menos terribles que las demás. Utiliza la función de acondicionamiento físico para eliminar las peores soluciones, luego crea la próxima generación de soluciones mediante el cruce de los "ganadores" de la última generación. Al repetir este proceso, generación por generación, debe terminar con una o más buenas soluciones a este problema.
Para que un algoritmo genético funcione, las diferentes soluciones posibles para un espacio problemático tienen que ser incrementalmente diferentes entre sí en términos de qué tan bien resuelven el problema. Los clusters de puntos son perfectos para esto.
Sugeriría usar un kernel de cambio de medias para encontrar el centro de densidad de tus puntos.
Esta figura muestra un kernel de cambio de media (centrado inicialmente en el borde del clúster) que converge hacia el punto de mayor densidad del clúster.
En teoría (en pocas palabras):
Varias respuestas a estas preguntas ya insinuaban la forma de hacer el cambio medio:
P Daddy borrando la imagen y encontrando el punto más oscuro es en realidad un método de estimación de la densidad del kernel (KDE), que es la base teórica de la media-shift.
Tanto j0rd4n como Bill the Lizard sugirieron discretizar tu espacio en bloques e inspeccionar sus densidades.
Lo que se ve en la figura animada es una combinación de estas dos sugerencias: utiliza un "bloque" móvil (es decir, el núcleo) para buscar la densidad más alta localmente.
El cambio de media es un método iterativo que utiliza un vecindario de píxeles llamado kernel (similar a este ) y lo usa para calcular la media de los datos de imagen subyacentes. La media en este contexto es el promedio ponderado de píxeles de las coordenadas del kernel.
En cada iteración, la media del kernel define sus coordenadas centrales para la siguiente iteración; esto se llama shift . De ahí el nombre mean-shift . La condición de parada para las iteraciones es cuando la distancia de desplazamiento cae a 0 (es decir, estamos en el punto más denso del vecindario).
Se puede encontrar una introducción completa al cambio medio (tanto en teoría como en aplicación) en esta presentación de ppt.
En la práctica:
Una implementación de Mean-Shift está disponible en OpenCV :
int cvMeanShift( const CvArr* prob_image, CvRect window,
CvTermCriteria criteria, CvConnectedComp* comp );
O''Reilly''s Learning OpenCv (extractos de libros de google) también tiene una buena explicación sobre cómo funciona. Básicamente solo alimente su imagen de puntos (prob_image).
En la práctica, el truco es elegir el tamaño de kernel adecuado . Mientras más pequeño sea el núcleo, más cerca se necesita iniciarlo en el clúster. Cuanto más grande es el kernel, más aleatoria puede ser tu posición inicial. Sin embargo, si hay varios grupos de puntos en su imagen, el kernel podría converger directamente entre ellos.