How to sample clustering to estimate precision and recall? There is a system containing $N$ clusters and in each cluster there are some elements. The clusters' sizes varies dramatically and most of the clusters are singletons.  
I need to know the precision and recall of this system, but since I need to check it manually it is impossible to check too many units. 
My question is: if I draw samples, the sampling unit should be cluster or element? 
Also, precision is a kind of easy to check (given I know the definition of each cluster), but how could I check the recall? I need to check in the scope of sample only, or I need to search from the entire population?
Is there anything else I need to know? 
Thanks a lot!
 A: For cluster algorithm evaluation you have to create small manual clusters and check how well they distributed among resulted clusters. Check this article http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html 
A: Drawing Validation Samples with Clustered Data Structure
You need to draw samples from a structural level where samples are statistically independent.
So if I have several patients (= your clusters?) and varying numbers of (e.g. repeated) measurements per patient (= your elements?) then I draw test patients. That is, unless I can show that the variance between patients is negligible compared to the variance between measurements of one patient.
Validation of Cluster Analysis
I'd use someting like cluster purity and/or the number of clusters samples of a given group are assigned to.
Precision, Recall & Co. don't seem quite appropriate: Think of a very bad classifier that always assigns B to class A samples and vice versa. That would be 0 precision and recall. But cluster analysis doesn't claim that the cluster where it assigns all B samples is actually class B. You'd need to assume something like the cluster with highest B predictions is actually B. So you'd always get at least $\frac{1}{n_{classes}}$ correct assignments due to this assumption.
Generalization of Precision & Recall
I use the following generalizations. I derived them from the medical diagnostics meaning, where the binary case disease X vs. not disease X (often called healthy in every day language)
(see p. 12 of http://softclassval.r-forge.r-project.org/Beleites2011b.pdf for an illustration)

*

*recall = sensitivity = How good does the classifier recognize class C samples? = fraction of cases where reference says it is class C that is (correctly) assigned to class C,

*specificity = How good does the classifer recognize that a sample does not come from class C? = fraction of cases where reference says it is not class C that is (correctly) not assigned to class C.

*precision = positive predictive value = If the classifier says it is C, what is the probability that this is correct? = fraction of cases with reference C of predicted class C cases.

*negative predictive value = Given the classifier said it is not class C, what is the probability this is correct? = fraction of cases with reference not C of cases predicted to be something else than C.

