Mathematical concepts and novel heuristic methods for data clustering and visualization
Nicholas DeClaris, Tung-Duong Tran-Luu · 1996
This thesis advances a data clustering methodology that, unlike many others, does not impose a solution, but rather suggests an acceptable one. Specifically, a method is presented where the elements of the data proximity are reordered into an acceptable block form, enabling the visualization of the data structure. Three intuitive qualitative criteria for an acceptable block form are given. Quantitatively, this blockness is measured by two values: the Bond Energy (previously defined) and the Linear Placement (applied to the situation for the first time). The problem of minimizing these quantities is NP-complete (no exact efficient solution is known), and the thesis develops two heuristic solutions. The first one consists of linearizing the Minimum Spanning Tree (MST) via optimal linear placement. The second one linearizes the dendrogram as generated by the single-link algorithm. The effectiveness of those methods are studied by means of several examples (7 artificially generated data sets and 9 real-world data sets). It is shown that the MST Linearization is competitive with 4 other algorithms, frequently encountered because of their simplicity or performance. In addition, the thesis makes significant contributions by solving two problems of importance to data clustering. The first problem is that of defining a good distance measure for qualitative variables. Our solution is: found through the use of semantic trees. The second problem is that of selecting appropriate scaling factors for the coordinate axes, a difficult choice because the clusters can be adversely affected; this problem undercuts the notion of a cluster itself. We define a cluster as a region over which the probability density function is unimodal. It is then shown that, when the empirical probability distributions are used, such regions are asymptotically scale invariant. However, this notion of cluster, which is based on the distribution density function, poses a difficulty when the clustering itself involves the notion of distance. This incompatibility is reconciled by showing that points contained in a level set of the (estimated) density function are also the points contained in the MST thresholded at certain value. This result provides a justification for the use distance as a basis for clustering.