Búsqueda de subconjuntos ocultos

Question

Me encuentro con un problema interesante y necesito ayuda para encontrar las mejores técnicas existentes para resolverlo. Sospecho que la respuesta acabará siendo la preparación de los datos para pasarlos por R. En este momento, no tengo una pregunta específica sobre R, sino que espero recibir algún consejo sobre el algoritmo que debo utilizar. Después de eso, ¡seguro que tendré preguntas de R a juego!

La configuración es que estamos analizando un gran sistema tratando de encontrar lo que yo llamo "subconjuntos ocultos". Utilizando números redondos, hay 1.000 piezas básicas diferentes que se utilizan en 10.000 combinaciones o "conjuntos" diferentes. (Yo llamo "ensamblaje" a una combinación completa única). Un ensamblaje puede tener 150 piezas, otro 700.

Lo que tratamos de hacer es detectar eficazmente los "subconjuntos ocultos". Es decir, grupos de piezas que aparecen juntos con frecuencia. Estoy seguro de que existe un cuerpo de investigación y práctica, algoritmos y métodos estadísticos para exactamente este problema... pero no sé lo que es, no puedo inventarlo yo mismo (triste pero cierto), y no conozco la terminología para buscarlo. ¿Puede alguien indicarme la dirección correcta? Esto parece un problema que se encontraría en la fabricación, cualquier cosa relacionada con grupos de personas, y la genética.

En caso de que no haya sido lo suficientemente claro, lo que estoy tratando de encontrar son grupos de piezas que se utilizan comúnmente (o siempre) juntos. Digamos que hay un tornillo #3 y que siempre se utiliza junto con una tuerca #3. Eso es lo que quiero decir con un "subconjunto oculto". En la práctica, es probable que encontremos subconjuntos ocultos mucho más grandes, pero puede que no sean 100% iguales en todos los conjuntos.

Estaría increíblemente agradecido por las sugerencias. Aunque no se me da bien inventar soluciones matemáticas, suelo ser capaz de encontrarlas (eventualmente) si se me indica la dirección correcta.

Answer 1

El problema que describes puede verse como un problema de factorización. Intenta encontrar dos matrices, una con los "subconjuntos" que se utilizan en cada montaje y otra con las piezas que se utilizan en cada subconjunto.

Parece que tu matriz es binaria, es decir, que cada parte sólo se utiliza una vez. En ese caso, tienes un problema de factorización de matrices binarias (también conocido como factorización de matrices booleanas). Existen varios algoritmos para la factorización de matrices binarias, personalmente encuentro que los que se basan en el análisis formal de conceptos son los más fundamentados teóricamente, sin embargo, los tiempos de cálculo pueden ser bastante elevados. Uno de estos algoritmos se describe aquí .

Estos términos deberían proporcionarle al menos un punto de partida para seguir investigando.

Answer 2

Gracias. Ahora estoy comprobando la factorización matricial booleana.

Tienes razón, he descrito el conjunto de datos como si una parte sólo pudiera utilizarse una vez. Pensé que hacerlo binario sería más sencillo que el caso real, donde las cantidades son variables. Así que, sí, una pieza puede aparecer más de una vez en un conjunto. Sin embargo, incluso ser capaz de encontrar agrupaciones de piezas sin cantidad va a ser un gran paso adelante. Supongo que estaba asumiendo que tendría que ser menos exigente computacionalmente que incluir la cantidad también.