Take the 2-minute tour ×

I have a collection of documents related to a particular domain and have trained the centroid classifier based on that collection. What I want to do is, I will be feeding the classifier with documents from different domains and want to determine how much they are relevant to the trained domain. I can use the cosine similarity for this to get a numerical value but my question is what is the best way to determine the threshold value?

For this, I can download several documents from different domains and inspect their similarity scores to determine the threshold value. But is this the way to go, does it sound statistically good? What are the other approaches for this?

share|improve this question
add comment

2 Answers

Actually there is another issue with centroids in sparse vectors. The problem is that they usually are significantly less sparse than the original data. For examples, this increases computation costs. And it can yield vectors that are themselves actually atypical because they have a different sparsity pattern. This effect is similar to using arithmetic means of discrete data: say the mean number of doors in a car is 3.4; yet obviously no car exists that actually has 3.4 doors. So in particular, there will be no car with an euclidean distance of less than 0.4 to the centroid! - so how "central" is the centroid then really?

Sometimes it helps to use medoids instead of centroids, because they actually are proper objects of your data set.

Make sure you control such effects on your data!

share|improve this answer
thanks. but you haven't addressed my question, determining thresholds?? –  user601 Aug 5 '12 at 2:39
No I havn't. Because I actually believe there won't be a satisfactory threshold. Thresholds usually don't work in high-dimensional data, but only in 2d, 3d stuff. In high dimensional data, due to the curse of dimensionality, the number of significant digits needed for a threshold may be quite high. So while in low dimensionality a threshold such as 0.2 may work, in high dimensoionality a threshold difference of 1e-20 may make the difference. –  Anony-Mousse Aug 5 '12 at 2:51
add comment

A simple method to try would be to employ various machine-learning algorithms - and in particular, tree-based ones - on the distances from your centroids.

As mentioned in another answer(@Anony-Mousse), this won't necessarily provide you with good or usable answers, but it just might. Using a ML framework for this procedure, E.g. WEKA, will also help you with estimating your accuracy in a more rigorous manner.

Here are the steps to take, using WEKA:

  • Generate a train set by finding a decent amount of documents representing each of your classes (to get valid estimations, I'd recommend at least a few dozens per class)

  • Calculate the distance from each document to each of your centroids.

  • Generate a feature vector for each such document, composed of the distances from this document to the centroids. You can either use a single feature - the distance to the nearest centroid; or use all distances, if you'd like to try a more elaborate thresholding scheme. For example, if you chose the simpler method of using a single feature, the vector representing a document with a distance of 0.2 to the nearest centroid, belonging to class A would be: "0.2,A"

  • Save this set in ARFF or CSV format, load into WEKA, and try classifying, e.g. using a J48 tree.

  • The results would provide you with an overall accuracy estimation, with a detailed confusion matrix, and - of course - with a specific model, e.g. a tree, you can use for classifying additional documents.

  • These results can be used to iteratively improve the models and thresholds by collecting additional train documents for problematic classes, either by recreating the centroids or by retraining the thresholds classifier.

share|improve this answer
add comment

Your Answer


