# Method for 'Simple' Clustering?

In a recent adult education class I took the prof shared a spreadsheet that was written in VBA code and takes ages to execute, I'm sure Python (SciPy, Pandas, Numpy) can handle this much faster.

The problem is a Direct Clustering Algorithm (DCA) one, all the searches I've done to solve this keep showing solutions trying to use K-mean which is not applicable.

The x-axis is different manufactured parts, and the y-axis are the different machines used in the manufacturing of the parts. 0 = not used, 1 = used.

The best description I can come up with is this: It's trying to make as clean a diagonal across the matrix from the top left to the bottom right based on the 1s as possible.

Below shows the flow of how the VBA solution works through the problem. In my final Python solution I'm not worried about the flow matching, just the final output. Starting data set:

           Part
a b c d e f
machine a 1 1 0 1 0 0
b 0 0 1 0 1 0
c 1 0 0 1 0 0
d 0 0 1 0 0 1
e 0 0 1 0 0 1


Step 1, Need columns decreasing and rows increasing number of 1s:

           Part
c f d a e b
machine e 1 1 0 0 0 0
d 1 1 0 0 0 0
c 0 0 1 1 0 0
b 1 0 0 0 1 0
a 0 0 1 1 0 1


Step 2, Part d moved, move machine b up to obtain the following matrix:

           Part
c f d a e b
machine e 1 1 0 0 0 0
d 1 1 0 0 0 0
b 0 0 0 1 0 0
c 1 0 1 0 1 0
a 0 0 1 1 0 1


Then part e was moved to obtain the following end matrix:

           Part
c f e d a b
machine e 1 1 0 0 0 0
d 1 1 0 0 0 0
b 1 0 1 0 0 0
c 0 0 0 1 1 0
a 0 0 0 1 1 1


As you can see, the final product is a diagonal of the 1s across the matrix.

To put in in perspective, I've got thousands of part numbers to work with and the VBA solution shared in a spreadsheet can handle 350 at best but takes a LONG time (~30 min) to execute.

I have tried to search but it seems this kind of grouping which a mean/average isn't applicable doesn't seem to come up in the articles I could find.

I really appreciate the help in solving this.

• Clustering is simply the wrong term here. It's an allocation problem – Has QUIT--Anony-Mousse Oct 23 '19 at 21:57
• Hi, I think your description of what the expected result is (the clean diagonal) is not sufficient. Eg if you just look at the diagonal, you could use the result of the first step and switch the order of row a and b and would have a diagonal already. – jottbe Oct 24 '19 at 6:53
• But generally speaking, I think Excel is a general purpose program and not optimized for such operations. I guess that the Excel Basic interpreter probably isn't that optimized as e.g. Python. So if you just translate the Excel algorithm to a numpy based Python algorithm, it should run much faster. – jottbe Oct 24 '19 at 6:56
• Maybe this article describes the same or at least a similar clustering approach: arxiv.org/pdf/1212.5265.pdf. I guess DCA itself was not invented by an indian scientist, so it might differ. – jottbe Oct 24 '19 at 7:04
• @jottbe That article looks exactly like what is trying to be accomplished in this question. – Python_Learner_DK Oct 24 '19 at 7:28