First, are your categories independent of each other? If this is really four parallel problems, solve one at a time and it'll simplify things a bit.
Second, the heart of clustering is the distance function between any two observations. Because your data has missing values, you need to explicitly decide how to handle them. A common approach is to ignore the problem by throwing away any rows that have any null values, which won't work at all for your data.
A simple approach would be to ignore any NA columns, but keep the rest of the columns--for category C, the difference between rows 1 and 2 would be 4 (columns 11, 14, 15, and 16 are all off by one). There's an issue with this approach that I'll get to later, but let's implement it for now.
For each category, we need three rows of centroid positions (we might as well start off with randomly selected rows that have no missing values in them). We then calculate distance to each centroid using a bunch of summed ifs: if(matrix cell != NA, matrix cell - centroid cell, 0) across all the columns. (If you're doing this computation in a spreadsheet, I'd use intermediate cells to calculate the pieces instead of dealing with one huge formula.)
We then optimize the centroids with a standard iterative procedure: each row gets a group membership corresponding to the closest centroid, then each centroid becomes the mean of its group members (and it looks like your mean function automatically excludes NAs), then we repeat until satisfied.
Why did I specify that we had to seed with a row without NAs? If you allow NA measurements in the centroids, this will fail because a row of all NAs is as central as it gets! If our update step never lets us move to NAs, the NA column will be transient, but what happens when we take the mean of a missing column? (In your sample data, consider what happens if rows 4-12 are a group in the B category.)
So if we want to allow NAs in the centroids, we need to modify our distance function to something like the following:
- If both cells are numbers, the distance is the difference
- If both cells are NA, the distance is 2
- If only one cell is NA, the distance is 3.
Those numbers are chosen such that for any full column of numbers, a numerical value in the centroid position will be closer, but if the column has sufficiently many NA rows, a NA value in the centroid will be closer. You might want to adjust the values so that the NA threshold looks like what you want it to.
In order to find the centroid of a set of rows using our distance function, we should use an optimization procedure, but we can cheat: if the number of NAs in the group is above the threshold, we set it to NA, and otherwise we set it to the mean.