0
$\begingroup$

I'm faced with an interesting problem and need some help finding existing best techniques to solve it. I suspect that the answer will end up being preparing data to run through R. Right now, I don't have a specific R question, I'm hoping to get some advice on the algorithm that I need to use. After that, I'm sure to have R questions to match!

The setup is that we're analyzing a large system trying to find what I call "hidden subassemblies." Using round numbers, there are 1,000 different basic parts that are used in 10,000 different combinations or "assemblies". (I call a unique full combination an "assembly.") One assembly might have 150 parts, another 700.

What we're trying to do is efficiently detect "hidden subassemblies." Namely, groups of parts that frequently show up together. I'm sure there's an existing body of research and practice, algorithms and statistical methods for exactly this problem...but I don't know what it is, can't invent it myself (sad but true), and don't know the terminology to look it up. Can anyone point me in the right direction? This seems like a problem that would be found in manufacturing, anything related to groups of people, and genetics.

In case I haven't been clear enough, what I'm trying to find are groups of parts that are commonly (or always) used together. Say that there's a #3 bolt and it's always used along with a #3 nut. That's what I mean by a "hidden subassembly." In practice, we're actually likely to find much larger hidden subassemblies, but they may not be 100% the same across all assemblies.

I'd be incredibly grateful for suggestions. While I'm no good at inventing mathematical solutions, I can usually bang them out (eventually) if pointed in the right direction.

Thanks very much!

$\endgroup$
0
$\begingroup$

The problem you are describing can be seen as a factorization problem. Try to find two matrices, one with the "sub-assemblies" that are used in each assembly and one with the parts which are used in each sub-assembly.

It sounds like your matrix is binary, i.e. each part is only used one. In that case, you have a binary matrix factorization problem (also known as boolean matrix factorization). There are several algorithms around for binary matrix factorization, I personally find the ones based on formal concept analysis to be most well-founded theoretically, however, the computation times may be quite high. One such algorithm is described here.

These terms should give you at least a starting point for further research.

$\endgroup$
0
$\begingroup$

Thanks! I'm checking on boolean matrix factorization now.

You're right, I described the data set as though a part can be used only once. I figured making it a binary would be simpler than the actual case, where quantities are variable. So, yes, a part can appear more than once in an assembly. However, even being able to find part groupings without quantity is going to be a huge step forward. I guess I was assuming it would have to be less computationally demanding than including quantity as well.

$\endgroup$
  • $\begingroup$ Seems to be more like a comment than an answer. $\endgroup$ – Michael R. Chernick Feb 19 '18 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.