Emergent community agglomeration from data set geometry

In the statistical learning language, samples are snapshots of random vectors drawn from some unknown distribution. Such vectors usually reside in a high-dimensional Euclidean space, and thus the “curse of dimensionality” often undermines the power of learning methods, including community detection and clustering algorithms, that rely on Euclidean geometry. This paper presents the idea of effective dissimilarity transformation (EDT) on empirical dissimilarity hyperspheres and studies its effects using synthetic and gene expression data sets. Iterating the EDT turns a static data distribution into a dynamical process purely driven by the empirical data set geometry and adaptively ameliorates the curse of dimensionality, partly through changing the topology of a Euclidean feature space ${\mathbb{R}}^n$ into a compact hypersphere $S^n$. The EDT often improves the performance of hierarchical clustering via the automatic grouping information emerging from global interactions of data points. The EDT is not restricted to hierarchical clustering, and other learning methods based on pairwise dissimilarity should also benefit from the many desirable properties of EDT.

Figure 1

(a) Schematic illustration of the network structure of effective dissimilarity transformations (EDT) parametrized by $\tau$. The $(i,j)\mathrm{th}$ entry of $d^{\left(\tau \right)}$ arises from transforming the $i\mathrm{th}$ and $j\mathrm{th}$ columns of $d^{(\tau -1)}$. (b) Illustrations of perspective contraction effect of EDT. (c) Two ideal clusters with radius $r$ and centroid-centroid distance $\ell$ in ${\mathbb{R}}^2$. (d) The detector used in the measurement of local deformation of data distributions in ${\mathbb{R}}^2$. (e) An ideal cluster of radius $r$ in ${\mathbb{R}}^2$ and an outlier at distance $\ell$ from the cluster centroid. (f) An ideal cluster of radius $r$ in the $xy$ plane of ${\mathbb{R}}^3$ with symmetrically located outliers on the $z$ axis at distance ${\ell }_{\frac{1}{2}}=\frac{\ell }{2}$ from cluster centroid.

Figure 2

Results of Gedankenexperimente: (a) cluster condensation [Fig. 1], (b) single outlier absorption [Fig. 1], (c),(d) two outliers perpendicular to an ideal cluster [Fig. 1], and (e),(f) probabilistic sampling.

Figure 3

Comparison of hierarchical clustering results using (a)–(c) Euclidean distance vs (d)–(f) EDT-enhanced Euclidean distance with (a),(d) single, (b),(e) average, and (c),(f) complete linkages. The number of clusters was chosen to be three in the analysis.

Figure 4

$\nu$ distribution for three data sets: (a) two Gaussian distributions with equal variance, but different sample sizes $m_{\mathrm{left}}=70$ and $m_{\mathrm{right}}=30$; (b) two layers of circularly distributed points with radius $r_{\mathrm{outer}}=2r_{\mathrm{inner}}$ (bottom left); (c) points distributed in the shape of the word “COS.” Each $\nu$ distribution was normalized by dividing by its maximum; the white segment in each plot indicates the diameter of the detector used in the measurement of $\nu$.

Figure 5

$\kappa$ distribution for three data sets: (a) two Gaussian distributions with equal variance, but different sample sizes $m_{\mathrm{left}}=70$ and $m_{\mathrm{right}}=30$; (b) two layers of circularly distributed points with radius $r_{\mathrm{outer}}=2r_{\mathrm{inner}}$; (c) points distributed in the shape of the word “COS.” Each $\kappa$ distribution was normalized by dividing by its maximum; the white segment in each plot indicates the diameter of the detector used in the measurement of $\kappa$.

Figure 6

Cluster of points can pull back or “trap” an outlier. Figure shows the case illustrated in Fig. 1 for varying values of the ratio $\ell /r$ in the range $[0.5,1.5]$ and for 20 satellite points. The top gray circles indicate the actual locations of points in ${\mathbb{R}}^2$; the bottom colored circles illustrate the corresponding effective locations after EDT, where we doubled the distortions to visualize the effect more clearly. As $\ell /r$ increased from left to right, the deformed circle behaved like an elastic membrane trying to trap the outlier from escaping and demonstrated singular behavior at $\ell =r$.

Figure 7

EDT approximately identifies the points at infinity. We designed two uniformly circularly distributed data sets with (a) a uniform increment in radius, or (e) a small increment in radius near the center and a large increment for the outermost three circles. For both data sets, the outer circles became relatively closer as $\tau$ increased. The values $\tau =1,2,$ and 3 correspond to (b),(f), (c),(g), and (d),(h), respectively. The effect was more pronounced in the case (e), and the outermost three circles were visibly mapped to the south pole. The mapping method can be found in Appendix pp2-s4.

Figure 8

Hierarchical clustering results on (a)–(d) “easy” and (e)–(h) “hard” annulus data sets using Euclidean metric ($\tau =0$) or EDT-enhanced dissimilarities up to three iterations and using average linkage. From left to right, (a),(e), (b),(f), (c),(g), and (d),(h) correspond to $\tau =0,1,2,$ and 3, respectively. Dramatic improvements were seen after just one iteration of EDT.

Figure 9

Spectral clustering results for the (a)–(d) “easy” and (e)–(h) “hard” data sets from Fig. 8 using the Gaussian RBF kernel $exp\left(-\gamma {‖\mathbf{x}-\mathbf{y}‖}^2\right)$ with $\gamma =0.05,0.1$, and 0.2 in (a),(e), (b),(f), and (c),(g), respectively, and (d),(h) the “nearest neighbors” method retaining only 10 nearest neighbors of each point to assemble a sparse similarity matrix. In SVM, nonlinear kernels with tunable hyperparameters are usually more powerful than a vanilla linear kernel $\mathbf{x}·\mathbf{y}$; however, an unthresholded continuous measure of relatedness between sample points is not necessarily a blessing for unsupervised learning algorithms.

Figure 10

Hierarchical clustering of NCI60 cancer cell lines [(a)–(d): $m=59$ samples] and human differentiated blood cells [(e),(f): $m=116$ samples] with $n=4000$ most variable genes (with largest standard deviations across all samples) in each data set. For the NCI60 data, the original Euclidean distance [(a): $\tau =0]$ gave minimum VI of 1.042; but, after two rounds of EDT [(c): $\tau =2]$, the VI reduced by $31.7\%$ to 0.712. The original Euclidean distance failed to combine all leukemia (LE) cell lines, but EDT [(c),(d): $\tau =2,3]$ brought LE cell lines together into a single cluster. From the very beginning [(a): $\tau =0]$, the melanoma cell lines were in a distinct single cluster except for one outlier LOXIM-VI, which is a desmoplastic melanoma cell line and is biologically similar to neurofibroma. Among the misclassified cell lines after two iterations of EDT, the LOXIM-VI found itself more similar to the mixture cluster of central nervous system (CNS) and breast cancer (BR) cell lines. (e) For the blood cell data, the original Euclidean distance split the erythrocyte ($\mathrm{E}k$, where larger values of $k$ indicate latter stages of maturity) samples into several small subclusters, and the VI was 0.706. (f) After one iteration of EDT, the VI reduced by $54.0\%$ to 0.325, and all $\mathrm{E}k$ samples were grouped into a single cluster with two branches—immature red blood cells (E1, E2) and more mature blood cells (E3, E4, E5)—well separated from the immune cells: T-cells, B-cells, and natural killer (NK) cells. These results support that the EDT can help improve clustering performance in real data analysis.

Figure 11

Outlier absorption effect under different $\alpha$ values. Figures (a)–(f) correspond to $\alpha =\frac{1}{20},\frac{1}{4},\frac{1}{2},1,2,5,$ respectively. For $\alpha >\frac{1}{2}$, the singularity at $\ell /r=1$ was attenuated, and the trapping window was shortened as $\alpha$ increased; by contrast, for $\alpha <\frac{1}{2}$, the singular peak grew sharper as $\alpha$ decreased, and the outlier far from the ideal cluster can still be absorbed into the cluster.

Figure 12

Effects of generalized EDT. We measured (a) the volume effect captured by $\nu$ and (b) anisotropy $\kappa$ of a bivariate Gaussian cloud $\mathcal{N}({(0,0)}^{\top },{\sigma }^2=0.01)$ of 50 samples in a plane, using the detector shown in Fig. 1. The original EDT $(\alpha =\frac{1}{2})$ showed $1/r$ power law decay, where $r$ is the distance between the center of Gaussian cloud and center of the detector. For $\alpha \gg \frac{1}{2}$, both volume effect and anisotropy deviated from simple power laws.

Figure 13

Plots of the empirical function $f$ that satisfies ${\ell }^{\prime }=f\left({\theta }^{\prime }\right){\ell }_{max}^{\prime }$, where ${\ell }^{\prime }$ is the EDT dissimilarity between two neighboring points on a circle and ${\theta }^{\prime }$ is the EDT dissimilarity between the centroid and the circle. The three plots on the top (a)–(c) correspond to the top three spheres in Fig. 7, and similarly for the three plots on the bottom (d)–(f).

Figure 14

Plots of maximum and minimum dissimilarities normalized by mean dissimilarity: $d_{max}^{\left(\tau \right)}/{\overline{d}}^{\left(\tau \right)}$ (solid) and $d_{min}^{\left(\tau \right)}/{\overline{d}}^{\left(\tau \right)}$ (dashed) of two multivariate normal distributions $\mathcal{N}({(\pm \ell /2,0,...,0,0)}^t,{\sigma }^2{I}_n)$ in ${\mathbb{R}}^n$ with variations in (a) $\ell /\sigma =0$, (b) $\ell /\sigma =4$, and (c) $\ell /\sigma =10$. For all three cases (a)–(c), EDT ($\tau >0$) enlarged the difference between $d_{max}^{\left(\tau \right)}/{\overline{d}}^{\left(\tau \right)}$ and $d_{min}^{\left(\tau \right)}/{\overline{d}}^{\left(\tau \right)}$, and hence enhanced the contrast; when the initial intercluster distance $\ell \gg \sigma$, EDT with high index $\tau$ preserved contrast dramatically relative to initial Euclidean distance $d^{\left(0\right)}$, consistent with cluster condensation effect of EDT.