正对

正对指定点之间的相似关系。在计算机视觉任务中，正对通常由数据增强技术 [23] 、 [37] 、 [74] （如旋转图像）指定，以提供实例判别能力。与计算机视觉任务不同，我们寻找集群级别的判别，而不是实例判别。因此，我们需要将属于同一集群的对指定为正对。我们注意到，k 最近邻 （kNN） [61] 被广泛认为属于相同的类/集群，例如，基于 kNN 的分类算法 [89] 。 [90] 因此，对于每个 xi∈X ，我们对其 kNN 中的一个点 xj 进行采样以构造一个正对 P(xi,xj) 。抽样概率是根据 UMAP [55] 定义的。具体来说，点 xi 和点 xj 是正对的概率计算为

View Source\begin{equation*}p_{ij}=(p_{j\vert i}+p_{i\vert j})-p_{j\vert i}p_{i\vert j}\tag{1}\end{equation*} 其中 pj|i 是条件概率，定义为

pj|i=exp(−dist(xi,xj)−ρiσi)(2)

View Source\begin{equation*}p_{j\vert i}=\exp\left(-\frac{dist(x_{i},x_{j})-\rho_{i}}{\sigma_{i}}\right)\tag{2}\end{equation*} 其中 dist(xi,xj) 表示两点之间的欧几里得距离。这是 ρi 到其最近邻域的距离 xi 。这是 σi 归一化项，计算方法是该点 xi 与其 k 个最近邻配对的概率之和。

 负对

如果只有正对，模型将折叠以将所有点嵌入到同一位置 [35] 。因此，我们需要指定负对来分离不同的点。遵循 对比学习 [23] 中使用的常用策略 ，对于每个点 xi ，其消极对应物被视为所有其他点，不包括积极对应物。由于不同邻居比相似邻居更有可能被采样为负对应对象，因此该策略可确保嵌入中不同邻居的平衡位置，从而缓解模型折叠问题。具体来说，在每次迭代中，训练数据被随机分组为大小相等的批次。在我们的实现中，我们将批次数设置为 10。每个批次都包含 B 点及其正对的对应项。因此，每个批次最终有 2B 点。对于批次中的每个点，其他 2（B - 1） 个点（不包括自身及其正对对应项）被指定为负对 N(xi,xj) 的对应项。

对比损失函数

我们采用 NT-Xent （归一化温度标度交叉熵损失） [72] 作为对比损失函数，并对其进行调整以进行降维。在训练批次中，point zi 的 NT-Xent 定义为

View Source\begin{equation*}L_{NT}(z_{i})=- \log\frac{\exp(q_{ij}/\tau)}{\sum\nolimits_{k=1}^{2B}1\!\mathrm{l}_{[k\neq i]}\exp(q_{ik}/\tau)}\tag{3}\end{equation*} 其中 1l[k≠i]∈{0,1} 是一个指示函数，计算结果为 1 if k≠i ， τ 表示温度参数。 qij 表示 和 之间的 zi zj 相似性，它们分别是 xi 和 xj 的嵌入。理想情况下，我们将 zi 和 zj [55]

S(zi,zj)={1exp(−(∥zi−zj∥2−ξ))if ∥zi−zj∥2≤ξotherwise(4)

View Source\begin{equation*}S(z_{i},z_{j})=\begin{cases} 1 &\text{if}\ \Vert z_{i}-z_{j}\Vert_{2}\leq\xi\\ \exp(-(\Vert z_{i}-z_{j}\Vert_{2}-\xi)) &\text{otherwise}\end{cases}\tag{4} \end{equation*} 之间的相似性定义为 其中 ξ 是两点之间的最小嵌入距离，其默认值为 0.1。然而，这个定义是不可区分的。相反，我们使用具有一个自由度的 Student t 分布来定义 qij ，以近似 S(zi,zj) 为

qij=11+a(∥zi−zj∥22)b(5)

View Source\begin{equation*}q_{ij}= \frac{1}{1+a(\Vert z_{i}-z_{j}\Vert_{2}^{2})^{b}}\tag{5}\end{equation*} 其中 a 和 b 由非线性最小二乘法根据 的 S 曲线拟合 来选择 。

与交叉熵损失相比，NT-Xent 增加了一个温度参数 τ 。如上所述，高维空间中一个点的 kNN 可能包含不同集群中的点。简单地在低维空间中保留所有 k 最近邻会将这些误差保留在嵌入结果中。因此，我们希望加强区分负对的能力，尤其是相似度高的负对。考虑到 NT-Xent 相对于负对 N(zi,zj) 相似性的 qij 梯度，

View Source\begin{equation*}\frac{\partial L_{NT}(z_{i})}{\partial q_{ij}}=\frac{1}{\tau}\frac{exp(q_{ij}/\tau)}{\sum\nolimits_{k=1}^{2B}1\!\mathrm{l}_{[k\neq i]}\exp(q_{ik}/\tau)}\tag{6}\end{equation*}

 图 2.

相对于负相似度 qij 的梯度。（a） 不同 τ 值下 NT-Xent 损失的梯度。（b） 梯度重新定义后相对于负相似性的梯度。根据 τ=0.15 和 SN（−40， 0.11， 0.13） 的偏态分布。

Show All

Fig. 2 (a) 显示对应于 的不同值的梯度 τ 。当等于 1 时 τ ，NT-Xent 退化为交叉熵损失。对于梯度到具有高相似度的负对（曲线的右侧部分），当 the τ 变低时，其值也会增加。但是，较高的值 （a τ ） 也会将梯度降低为具有中等相似度的负对。因此，我们选择 τ=0.15 in default。

Network Structure

The input of our model are high-dimensional data points. For image data, we emply SimCLR [23] to transfer it into a 512-dimensional vector. Similar to SimCLR [23], our training model has an encoder that learns the representation of data and a projection head that embeds the representation into a 2-dimensional embedding space (Fig. 4). The encoder is a Dense Neural Network that consists of four densely-connected layers. The four layers contain 128, 256, 256, and 512 units, respectively. We add a batch normalization layer after each layer to avoid the gradient vanishing. A ReLU activation function is applied to each layer. The projection head contains a densely-connected layer with 512 units, a ReLU activation function, and a densely-connected layer with 2 units.

Fig. 3.

The distribution of negative pairs in similarity. The stacked bars represent the ratio of two kinds of bars.

Show All

Fig. 4.

The network structure of CDR.

Show All

Training Process

We employ the Adam optimizer for network training, with an initial learning rate of 0.001. The learning rate is successively decayed by 10% when the number of epochs reaches 0.8E and 0.9E. E denotes the total number of epochs, which is set as 1000 in our implementation. The batch size is set as B=n/10, where n is the size of the dataset. Because the trained model is used to embed the training dataset only, all data points are used for training. We adopt a multi-stage training strategy: 1) we use the NT-Xent to warm up the model for 150 epochs; 2) we train the model with gradient redefinition for 700 epochs; and 3) we use the NT-Xent again to obtain a stable embedding with 150 epochs. When users specify link-based constraints, we sample 30% data points for fine-tuning the model. We use fewer epochs than the initial training to update the embeddings. The default is 30 epochs. The first 85% epochs use the proposed gradient redefinition, and the last 15% epochs use the adapted NT-Xent.

Datasets

We use 10 real-world datasets including Animals [26], Cifar10 [46], Indian Food [4], Isolet [33], MNIST [51], Stanford Dogs [44], Texture [7], USPS [38], Weathers [77] and WiFi [12]. The types of data contain image data, tabular data, and text data. All of them have at least two clusters and have class labels as the ground truth.

DR Techniques

For comparison, we select five non-parametric DR techniques, i.e., ISOMAP [73], Landmark ISOMAP (LISOMAP) [70], t-SNE [76], AtSNE [34], and UMAP [55]; and four parametric DR techniqcues, i.e., Parametric t-SNE (PtSNE) [75], Parametric UMAP (PUMAP) [67], Deep Recursive Embedding (DRE) [92], and the Dimensionality Reduction by Learning an Invariant Mapping (Dr-LIM) [36]. Although there are many contrastive learning applications in computer vision, to the best of our knowledge, DrLIM is the only contrastive learning technique for general DR tasks. We employ the implementation of ISOMAP, t-SNE, and UMAP in the sklearn library. For other techniques, we use the code published by their authors. Because we cannot find the code of LISOMAP, we implement it according to the paper. In the ablation experiments, we test the contrastive learning framework with Cross Entropy (CE), NT-Xent (NX-CDR), and gradient redefinition (CDR). All results are without user steering.

Parameters

We set the perplexity of t-SNE, AtSNE and PtSNE as 30, and the size of kNN neighbor in UMAP, PUMAP, ISOMAP and LISOMAP as k=15, following the settings in previous studies [55], [67], [76], [84]. The other parameters of these techniques are set as their default values. In consistency with UMAP, we set k=15 in CE, NX-CDR, and CDR. UMAP, t-SNE and AtSNE are optimized with 1000 iterations to ensure convergence on all tested datasets. For all the parametric techniques, we use the same network architecture as described in Section 3.4 and also trained them for 1000 epochs.

4.1.1 Measures

From literature review [32], [68], we employ six measures to evaluate the DR techniques. Specifically, we select Trustworthiness & Continuity [43] for preserving neighborhood structures, kNN classifier accuracy [27] & Neighbor Hit [59] for correcting false neighbors, and Distance Consistency [71] & Silhouette Coefficient [65] for visual cluster separation. For the first four measures that need to specify the kNN, we set k=15, which is consistent with the tested techniques.

Trustworthiness measures how much the kNN neighborhood of a point in the embedding space reflects the true neighborhood in the high-dimensional space.

Continuity measures how much the kNN neighborhood of a point in the high-dimensional space is preserved in the embedding space.

k-NN classifier accuracy (kNN-CA) measures the accuracy of the kNN-based classification in the embedding space. For each point, we predict its class label by majority voting of its kNN in the embedding space. A high kNN-CA close to 1 indicates a high consistency between points and their kNN in terms of classification.

Neighbor Hit (NH) measures the proportion of points in the kNN that belong to the same cluster as their center point in the embedding space. A high NH that is close to 1 indicates good quality. On the contrary, a low NH that is close to 0 indicates that many false neighbors are preserved in the embedding space.

Distance Consistency (DSC) is the proportion of points which have the same class as their nearest class centroids. DSC is the best separation measure according to Sedlmair and Aupetit [68].

Silhouette Coefficient (SC) measures the difference of between-class and within-class average distances normalized by the maximum of them. Compared to DSC which measures the point-class relationship, SC evaluates separation from a class-class perspective. It is also widely used in measuring visual class separation.

Except for SC, which is ranged from −1 to 1, the other five measures are normalized to [0, 1]. Higher value refers to higher quality for all six measures. It is worth noting that we use class labels as the ground truth clusters in kNN-CA, NH, DSC, and SC. Although this is a common practice in evaluating DR techniques [60], [92], the possible class-cluster mismatching [8] should be aware. In our experiments, we choose datasets with well-known cluster structures to address this issue.

Table 1. Comparisons of trustworthiness

Table 2. Comparisons of continuity

Table 3. Comparisons of KNN-CA

Table 4. Comparisons of neighbor hit

Table 5. Comparisons of DSC

Table 6. Comparisons of SC

Table 7. Comparisons of running time(s)

4.1.2 Comparison Results

Table 1 to Table 6 present the quantitative comparison of well-known existing techniques with CDR on 10 datasets with respect to each of the six measures. From Table 1 and Table 2, it is observed that CDR achieves the best average Trustworthiness than other techniques, but its average Continuity is slightly lower than t-SNE, UMAP, PtSNE, and PUMAP. The main reason is that the calculation of Continuity includes false neighbors. Removing false neighbors in the embedding space, although improves the embedding quality, results in a decrease of Continuity. This is verified by the results on correcting false neighbors. According to Table 3 and Table 4, CDR achieves the best performance in most datasets in terms of kNN-CA and Neighbor Hit, demonstrating its improved neighborhood accuracy and ability to correct false neighbors. In terms of visual cluster separation, Table 5 and Table 6 show that CDR outperforms all other techniques in DSC and SC. Fig. 6 shows the embedding results of the selected techniques on three typical datasets. CDR presents a much clearer visual cluster separation in the embedding results. In conclusion, CDR achieves comparable quality to t-SNE and UMAP in terms of preserving neighborhood structures. Considering the false neighbors, CDR outperforms all other techniques in terms of preserving correct neighborhood structures. CDR also achieves the best performance in terms of visual cluster separation.

4.1.3 Results of Ablation Experiments

We compare the performance of CE, NX-CDR, and CDR to evaluate the effectiveness of the adapted NT-Xent and the proposed gradient redefinition. In terms of preserving neighborhood structures, NX-CDR performs better than CE. CDR achieves higher average Trustworthiness but lower average Continuity than NX-CDR (see Table 1 and Table 2). In terms of correcting false neighbors, NX-CDR also performs better than CE. CDR performs better than NX-CDR (see Table 3 and Table 4). Again, the results suggest that Continuity is distorted by false neighbors. In terms of visual cluster separation, CDR outperforms CE and NX-CDR in DSC and SC for all datasets (see Table 5 and Table 6). In conclusion, the adapted NT-Xent has positive effects on preserving correct neighborhood structures. The proposed gradient redefinition is effective in improving visual cluster separation.

4.1.4 Runtime Performance

Table 7 shows the running time of the evaluated techniques. Among them AtSNE and UMAP are the fastest with the cost of slightly decreased quality than t-SNE. CDR runs faster than original t-SNE, but much slower than other non-parametric techniques. Among parametric techniques, CDR runs faster than PtSNE and PUMAP, which are the parametric version of t-SNE and UMAP. In our experiments, we use the same backbone network in DRE and CDR. Therefore, they have similar time performances. DrLIM achieves better time performance than CDR because it has a simpler loss function. Generally, parametric techniques run slower than non-parametric ones due to their training process. However, it is worthwhile to develop parametric techniques not only because of the better embedding qualities, but also parametric techniques offer several opportunities to DR applications. We will discuss these opportunities in Section 5.

Tasks

We designed a controlled experiment for evaluating the performance of cluster identification. They were tested using the three DR techniques on 20 datasets. 10 of them are the same as described Section 4.1. The remainings are described in the appendix. The controlled experiment was based on the cluster identification task (E1) described in Xia et al. [84]. We followed the same task design and asked each participant to complete 3(techniques)×20(datasets)=60 trials for identifying clusters.

Participants, Apparatus, and Procedure

We recruited 20 participants (16 males and 4 females) for the user study, aged 23 to 27. None of them reported color blindness or color weakness. All the participants are graduate students with research experience in data visualization. To remove any bias from the analysis processes, we adopted the same testing application described in Xia et al. [84] and integrated CDR and the baseline techniques. All the participants took the experiments one by one on standard desktop computers in our research lab. Each computer is equipped with a standard keyboard, a mouse, and a DELL 27-inch U2720QM monitor. The computer has a 2,560×1,440 screen resolution and chrome browser. The two experiments were conducted based on the same procedure described in Xia et al. [84]. In the controlled experiment, instead of randomly selecting datasets and DR techniques for each trial, we adopted a Latin square design where the datasets were sorted based on a Latin square upon which one of the three DR techniques was randomly selected for a trial. Compared with Xia et al. [84], this design minimizes the potential learning effects resulting from visualizing the datasets in certain orders. To evaluate the results of the two experiments, we adopted similar analysis conditions, statistical measures, and analysis approaches described in Xia et al. [84]. Here, the Shapiro-Wilk test and Paired Wilcoxon test were added to validate the normality in precision/recall and completion time, respectively.

Results

The results of precision and recall values for the controlled experiment are displayed in Fig. 7(a) and Fig. 7(b). Among the three techniques, CDR has the best precision (80.68%) and recall (69.29%). There is a relatively small difference between t-SNE and UMAP on precision (65.64% and 66.25%, respectively) and recall (55.49% and 55.50%, respectively). The Friedman tests show statistical significance of precision (X2(2)=14.8,p<0.05) and recall (X2(2)=17.5,p<0.05). Therefore, hypothesis H1 is confirmed. In terms of the average completion time (Fig. 7(c)), both CDR and UMAP show better performance (14.481s and 14.603s, respectively) than t-SNE (16.592s). The Friedman tests show statistical significance of average completion time (X2(2)=10.8,p<0.05). However, although CDR has a slightly shorter completion time than UMAP, there is no statistical significance between them. As a consequence, the hypothesis H2 was partially confirmed.

Fig. 6.

Comparison among different techniques on datasets isolet, MNIST and texture.

Show All

We conducted a post-interview to subjectively compare CDR with t-SNE and UMAP by reviewing their results side by side for each dataset. All participants agree that CDR performs better than t-SNE and UMAP in terms of presenting visually separated cluster patterns. They point out that the clearer visual separation makes them more confident in identifying clusters. However, they also feel somewhat uncertain about the results, as the ground truth is unknown. Some participants point out that providing the quality measures, such as Trustworthiness and Continuity, can strengthen their confidence.

Fig. 7.

The results of the user study. (a)-(c) the statistics of precision, recall, and completion time for the objective task.

Show All

Animals

The Animals dataset contains 10000 animal images. Each image is encoded into a 512-dimensional feature vector as mentioned in Section 3.4. Using the default parameters, the data were embedded into the scatterplot view, as shown in Fig. 1(e). 11 clusters were observed. However, there was a much smaller cluster at the top left corner. Hoovering over points in this cluster and its neighboring two clusters, we found both the small cluster and the cluster at the top left corner contained butterfly images. Switched to the image mode, we found that the larger cluster contained images where butterflies dominate the foreground, while the smaller cluster contained images where the backgrounds dominate. That is why they formed two clusters. However, considering the interest is in animals, we would like to merge the two clusters into one. Therefore, we added a must link between the two clusters. As merging two clusters is essential to align the two clusters' centers, we chose the two ends of the must link to be the butterfly images near the two cluster centers. After re-embedding, the two clusters were successfully merged (Fig. 1(g)). Some spider images were observed at the boundary of the merged cluster (e.g., Fig. 1(g) A). We thus further improved the results by adding more links. We first added a cannot link between one of the spider images at the boundary and a nearby butterfly image to push away the mis-clustered spider images. We then added a must link between one of the mis-clustered spider images and a spider image near the center of the spider cluster to attract them together. Fig. 1(h) shows the results. With only the three links added, our method successfully merged the two butterfly clusters and separated the spider images. This demonstrated the effectiveness of adding links to improve clustering results. However, added links are expected to assist the similarity measure to improve the clustering results, rather than being the dominant factor to determine the clustering results. We thus expect some resistance of our method to “bad” links added. To verify this, we added a must link between two significantly different clusters: chicken and dog. As shown at the top of Fig. 8(b), the overall clustering pattern remained unchanged. It was not until three must links were added (Fig. 8(b)) then the chicken and the dog clusters were merged (Fig. 8(c)), in comparison to the only one must link needed to merge the two butterfly clusters. This demonstrated some degree of resistance of our method to “bad” links. Meanwhile, the Trustworthiness and Continuity measures were also significantly decreased (from 0.910 to 0.757 and 0.910 to 0.853. respectively).

Fig. 8.

The case of the animals dataset. (a) The species of animals in each cluster. (b) Three must links are imposed between chicken and dog cluster in three interactions. (c) Updated embedding result.

Show All

Fig. 9.

The case of the WiFi dataset. (a)-(c) the initial embedding, embedding after one cannot link, and embedding after one must link, respectively. (d)-(f) the parallel coordinates plots of C1, C2, and C3, respectively.

Show All

WiFi

We then moved on to analyze the clustering results on the WiFi dataset. This dataset contains 2000 vectors recording the signal strengths at 2000 locations in four rooms (500 locations in each room). There are 7 routers in the space, from which the received signal strengths constitute the 7 dimensions of each vector. A good clustering of these vectors is expected to correspond to the four different rooms. Fig. 9(a) shows the embedding results using the default parameters. Five clusters were observed rather than four as expected. The problem seemed to lie in the three clusters (C1, C2, C3) that were closely positioned at the bottom right. We would like to find the reasons and thus had a closer examination of their parallel coordinates. It is observed that the data points in C1 and C2 did exhibit similar patterns in parallel coordinates (Fig. 9(d), (e)). The distributions along the dimensions had large overlaps, especially along A0, A1, A2, A3, and A4. This means a large number of data points (locations) in C1 and C2 had similar distances to these routers. We considered that is why C1 and C2 were closely positioned in the embedding space. To refine the CDR to better distinguish locations in the two clusters, we added a cannot link. The re-embedding results showed the successful separation of the two clusters (Fig. 9(b)). We then examined C3. C3 had much smaller number of data points, which indicated it was separated from its main cluster. Comparing the parallel coordinates between C3 (Fig. 9(f)) and C1/C2, it can be observed that C3 had very different distributions along A0 and A3 compared with C1 and C2. However, along the other 5 dimensions, the distributions of C3 were fully enclosed by the distributions of C2. Together with the closest positions of C3 and C2 in the embedding space, these were strong indications that the locations in C3 should be in the same room as those in C2. Their differences along A0 and A3 explained their separation, but these were more likely due to obstacles in the room. Based on the reasoning, we would like to refine the CDR to merge C2 and C3. We thus added a must link between C2 and C3. After re-embedding, the results had four well -separated clusters as expected (Fig. 9(c)), demonstrating the improved dimensionality reduction for visual cluster analysis.

Lesson Learned

Our case studies show that the link-based interaction is very efficient. To merge similar clusters or separate dissimilar clusters, only one or two links are needed. Regarding “bad” links, such as must links between dissimilar clusters, our technique shows some degree of resistance. Three or more links are required for counterfactual interactions. Users should be aware of the power of the interactions when exploring cluster patterns. A suggestion is using the embedding quality measures as the indication of whether the interaction is correct.