Approximating Hierarchical MV-sets for Hierarchical Clustering
The goal of hierarchical clustering is to construct a cluster tree, which can be viewed as the modal structure of a density. For this purpose, we use a convex optimization program that can efficiently estimate a family of hierarchical dense sets in high-dimensional distributions. We further extend existing graph-based methods to approximate the cluster tree of a distribution. By avoiding direct density estimation, our method is able to handle high-dimensional data more efficiently than existing density-based approaches. We present empirical results that demonstrate the superiority of our method over existing ones.
The paper introduces a new method for estimating cluster trees by direct estimation of the MV-sets rather than separate density estimation and recursive estimation of the tree using level sets. This avoids the issues inherent in producing stable high-dimensional density estimates. The method uses a graph cutting technique (with the full dataset being the graph nodes) to produce a set of high-density clusters.Essentially the q-OCSVM method is used to create a different method for specifying the graph edge weights between observations. After this point the algorithm largely follows the cluster tree estimation method set out by Stuetzle and Nugent. The issue of bandwidth selection is an important one and the authors mention it only briefly. Their suggestion of specifying the bandwidth which gives the number of modes that the user would expect does allow for expert knowledge to be incorporated into the procedure which is an advantage (and could be emphasised more in the paper) but only when such knowledge is available. They suggest no alternative for cases where a more objective solution might be required.The simulations are acceptable and the methods chosen for comparison are reasonable. Quality: The motivation for the new method is clear and the analysis/results sections are reasonable. It is an interesting approach that could be of use.Clarity: The paper is very well written, with a good summary of the background of all elements of the approach.Originality: This method is the application of an already developed method for MV estimation to an existing graph-based approach to building cluster trees. The combination is novel but the different elements are not.Significance: The results seem to suggest that the new graph edge weight metric has merit but there are outstanding issues with the choice of bandwidth that I suspect will limit the impact of this work on practitioners.Small details:If you have space I would suggest emphasising the advantage of this method over existing density-estimation based methods in high-dimensional datasets in the abstract.The authors give a very nice summary of the concept of a (non-parametric) cluster tree and level sets. Figure 1 level set lines should really have (light) vertical lines dropping to x-axis at points of intersection with the density to illustrate the level sets properly. Line 082: The phrase "feature vectors" (and "features") seems a little confusing here and elsewhere. Perhaps "observation vectors" would be better. Since "features" often refers to variables.Line 232, expected is used too many times. Perhaps change the second to the "number specified/recommended by the user".The description of the quality measure in section 4.1 needs more detail. Better clarifying what it meant by cluster and class here would improve the readability of this part. Are clusters defined just for a single level or over all levels? Similarly are classes defined over a tree or a single level? Presumably clusters refers to the partitions resulting from the tree estimated by the method in the paper?There is an issue in formatting with the caption of Figure 3 overlapping the line on the bottom of page 6.There needs to be a line to space things out between the bottom of the captions for Figures 4 and 5 and the main text.Line 370 "1, 092" should be "1,092"