Constrained k-means algorithms in R (must-link constraints)

Question

I currently face an unsupervised learning task that is to be approaches using clustering. More specifically, it is a segementation task and hence there is some prior knowledge about a) the number of clusters and b) the rough content of each segment. From literature this seems like a prime example, where "constrained k-means" would come into play and I'm really eager to try it out. Both of the above mentionend pieces of prior knowledge can be incorporated in "constrained k-means" as a) is represented by k and b) can be expressed in "must-link constraints". (For a good overview over constrained k-means see Wagstaff, Cardie, Rogers, Schrödl, & others (2001).)

My problem now is that I can't find a suitable implementation in R on CRAN. Programming it myself in R would be ok, based on the pseudocode, but my programming is most certainly not efficient enough, since we are talking about a somewhat large dataset (75.000 x 30).

So, I turn to this community hoping that someone has found an efficient implementation of "constrained k-means" in R or is willing to provide code that is somewhat efficient.

Thank you very much,

Clemens

Update 23.06.2016: Thanks for your replies so far. In order to make the problem a little more succint please see a sample data file here. (Note: this is not an excerpt of my original data as it is highly sensitive, but an artificial dataset with the same characteristics (less rows though))

Two examples of simple constraints:

• all observations that have either a 1 in v305 or a 1 in v306 must be linked (must-link-constraint)
• all observations that have a 1 in v258 and v262 must be linked (must-link-constraint)

Currently looking at your suggestions, Rahul. Thanks very much.

Answer 1

The R package conclust seems to be what you are looking for.

From the package description:

There are 4 main functions in this package: ckmeans(), lcvqe(), mpckm() and ccls(). They take an unlabeled dataset and two lists of must-link and cannot-link constraints as input and produce a clustering as output.

There exist also a python implementations (Disclaimer: I have developed it).

Answer 2

For the given problem I would apply constrained Hierarchical clustering in R. That is more efficient in this case. If you like to apply Hierarchical clustering the package is "rioja" and the function that you can use is chclust().
This is not constrained K-means implementation in R but this should solve your actual problem.

There are two types of constrained in chclust() function, you can set those with the help of method parameter in function. This will add the constraint on the basis of sum of square.You can read in detail about these constraint with simple search.

This chclust function will produce the constraint object and you can check the proper number of group by using other functions in "rioja" package.

A practical implementation of same can be checked on below link: https://gist.github.com/benmarwick/7097120