3
$\begingroup$

Given an hierarchical clustering of data points, some of which are labeled, are there good ways to use the tree/dendrogram to make predictions for the unlabeled points?

One approach might be to find the "best" place to cut the tree so that clusters match labels. I'd be especially interested in efficient ways to cut each cluster at a different height. But I'd also be interested in approaches that don't use "hard" cuts to make the predictions.

$\endgroup$
  • $\begingroup$ Perhaps you should clarify how you came about this clustering. In principle, it does no make sense to do clustering and then "hope" you can use the result for classification. There are different algorithms for that. $\endgroup$ – Nick Sabbe May 24 '11 at 6:38
  • 2
    $\begingroup$ Hierarchical clustering relies on a dissimilarity metric that determines the distance from a point to a cluster. Why don't you use the labeled points as clusters, and calculate, for each unabeled point, the dissimilarity to all clusters? Then, you can either make a hard assignment using the smallest dissimilarity, or you can make a soft assignment using relative dissimilarities. $\endgroup$ – Jonas May 24 '11 at 13:24
1
$\begingroup$

I'm answering about another approach that doesn't use hard cuts on the dendrogram. I would suggest you to use something like linear discriminant analysis (LDA) or any other technique that allows you to predict the class of the unlabeled points. (There are many techniques that can do the job, but I find LDA the easiest)

LAD is used when you have a set of multivariate observations, and those observations belong to a particular class. This dataset is composed by the labeled points. On the other hand you may have a set of points in the same variables but the class is unknown. These are the unlabeled points.

The goal of LDA is to classify the unknown points in the given classes. It is important to notice that in your case, the classes are defined by the hierarchical clustering you've already performed.

Discriminant analysis tries to define linear boundaries between the classes, creating some sort of "territories" (or regions) for each class. For any unlabeled point, you must check to which region it belongs.

You can check this lecture on LDA. It is simple and sufficiently explained.

If you need software to accomplish this task, you might check R documentation on the functions lda() and predict.lda() in MASS package. Check Quick-R for additional help. SPSS has a very easy implementation of LDA.

In fact, I think it is very odd to "force" the dendrogram to include the unlabeled points. Normally, the dendrogram is built using all of the unlabeled points in a dataset.

Hope this is useful :)

$\endgroup$
0
$\begingroup$

Just my two cents, but I would look at decision trees or using your initial cluster analysis to determine a suitable number of clusters, and then use kmeans to refine. From there, you can get the cluster centers and reclassify new cases based on those centers.

HTH.

$\endgroup$

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.