Evaluation of approaches proposed to avoid overlap of markers in visualizations based on multidimensional projection techniques

Abstract

Multidimensional projection techniques provide graphical representations computed based on instance similarities to enable the analysis of abstract and possibly large data sets. However, when the data set size grows these graphical representations can hardly avoid overlap among markers. To overcome this issue, while some techniques attempt to remove overlap after multidimensional projection, some projection techniques were developed considering non-overlapping constraints. In this work, we present an analysis of four overlap removal techniques and two projection techniques considering non-overlapping. The evaluation was performed according to five metrics that consider structural and similarity relations, and based on the results we provide a guide to use a technique according to the data set and analysis goals.

Keywords

Visualization multidimensional projection overlap removal techniques layout arrangement evaluation

Introduction

In the last years, much effort has been deposited towards improving data exploration due to the amount and complexity of data generated daily. One of the approaches used to aid in the decision-making process is the integration of different areas of knowledge and a visual approach. This process is called visual analytics.¹ In this context, visualization uses visual metaphors to provide insights about data sets. Such visual metaphors can preserve and enhance the characteristics and relationship among instances or attributes.

For multidimensional data, one class of technique widely explored by the visualization community is multidimensional projections. A multidimensional projection^2–5 technique aims at mapping data from high-dimensional space $(R^{m})$ to low-dimensional space $(R^{p})$ , preserving both structures and relations existing in the high-dimensional space. For graphical representation, each instance of the data set is seen as a point in the plane or three-dimensional (3D) space, but in practice each instance is represented by a marker for better visualization. For example, images can be employed as markers in image visualization approaches.^6,7

Although multidimensional projections provide a way to explore a data set by means of similarity, an inherent problem of the dimensionality reduction is the overlap among markers when a visual metaphor is created, that is, when the circles or images used to represent the instances of a data set are obstructed by other markers. This problem impairs the user exploration and detailed analysis of instances similarity, requiring several interactions with the graphical representation. From the literature, several techniques were proposed to remove markers overlap from bi-dimensional spaces^8–10 or to place markers directly without overlap^11–13—each technique works in a distinct way in order to generate a graphical representation without overlap. Some works presented an initial evaluation of these techniques,^8,14 but they did not detail the quality of dimensionality reduction preservation when comparing the original with the modified layout, as well as if the quality of clusters are affected by layout arrangements from the initial projection, that is, the projection in which no overlap removal algorithm has yet been applied. Gansner and Hu⁹ performed a comparison, but only according to few techniques focusing on graph structures, in which results cannot be transferred to multidimensional projections, and Nieto et al.⁸ did not provide results that consider the scalability of the methods discussed here. Moreover, these works did not compare the overlap removal techniques with point placement technique that provide a layout arrangement without markers overlap, such as IncBoard¹¹ and HexBoard.¹² Therefore, in this work, we performed a detailed analysis of the quality of these techniques to choose the most accurate and precise technique, that is, the technique capable of maintaining the relationship between original multidimensional space, the original layout from a projection technique, and cluster formation. In addition, we also perform comparisons of time spent on execution. Thus, the main contributions of this article are the detailed analysis of overlap removal techniques and a guide for experts that intend to use or propose overlap removal techniques.

The remainder of this article is organized as follows. In section “Related works,” we provide a brief discussion on related works. In section “Overlap removal techniques,” we provide a description about the analyzed techniques. In section “Evaluation of overlap removal techniques,” we show the evaluation of the discussed techniques using different data sets. In section “Discussion,” we provide a discussion on the results. Finally, in section “Conclusion,” we conclude our work.

Related works

Although it does not present a new evaluation technique, our work is related to the works well discussed in the literature in which the objective is to present techniques that can be used to evaluate multidimensional projection according to class separation. However, in this work, we present such evaluation in the context of overlap removal techniques.

Tatu et al.¹⁵ presented a study where they investigate the relationship between clusters interpretation in two-dimensional (2D) scatter plots and measures automatically extracted out of them. The measures used were Class Consistency Measure (CCM),¹⁶ which is based on the distance of points to the centroid; Histogram Density Measure (one-dimensional (1D) and 2D),¹⁷ which is a quality measure for scatter plots and it considers the class distribution of points in 2D scatter plots when they are projected on the axes; and Class Density Measure (CDM),¹⁷ which evaluates scatter plots according to separation properties. Other work, presented by Seldmair et al.,¹⁸ performs a systematic evaluation of separation measures with respect to human judgment. In addition, they also provide a taxonomy of factors of data sets that influence the visual separation of clusters. Sedlmair et al.¹⁸ used the Distance Consistency,¹⁶Distribution Consistency, and 2D-Histogram Density¹⁷ measures. Recently, Wang et al.¹⁹ proposed a technique where the dimensionality reduction process is performed according to visual separation measures that simulate the human perception of class separation. The approach, perception-driven dimensionality reduction, aims at generating truthful 2D linear projections with maximal class separation.

Unlike the previous works, in this article, we present an evaluation of the behavior of overlap removal techniques using data sets with a sort of characteristics, that is, we evaluate multidimensional projections according to separation and similarity measures before and after the overlap removal process.

Overlap removal techniques

Overlap removal techniques use different approaches to remove overlap among markers—while some techniques create well-defined structures in the plane, other techniques only consider a graph structure among the instances. By minimizing overlap among instances, these techniques have to maintain the relations imposed by multidimensional projection as much as possible.

In this section, two techniques that perform dimensionality reduction and point placement without markers overlap are presented, as well as four techniques intended to remove markers overlap from bi-dimensional spaces, that is, the techniques that attempt to remove the overlap of circles or scatter plot images in the plane.

Incremental board

The Incremental Board/IncBoard¹¹ technique is a projection technique that projects instance without overlap by creating a mosaic of rectangles so that each instance is placed in an individual cell of the mosaic. The IncBoard technique considers the relative similarity of elements in an n-dimensional space to project them in the 2D space and it does not allow data overlap because it does not allow more than one element in the same cell. Using the chess board structure, IncBoard allows an effective progressive visualization of dynamic data sets, resulting in a space that maintains a coherent layout.¹¹

HexBoard

Despite of the advantages offered by IncBoard technique, it does not convey the similarity of pairs between neighboring elements effectively. Since the IncBoard technique places elements inside a grid of fixed size cells, the neighborhood of a given element is always placed at same distance, even if not all of elements in its neighborhood are equally similar. The HexBoard¹² technique improves the ability to convey similarity information of each pair of neighbors in the projection, besides supporting identification of clusters and subsets of elements. This improvement is given by the fact that the HexBoard technique uses a mosaic of hexagons instead of the chess board structure.

ProjSnippet

The ProjSnippet⁸ is a technique to visualize Web search results. The technique has an overlap removal approach which is described by the sum of two components, one that quantifies the overlapping snippets $(E_{O})$ , while the other measures the neighborhood relations resulting from the multidimensional projection $(E_{N})$

E = (1 - α) E_{O} + α E_{N}

(1)

where the parameter $α \in [0, 1]$ is used to balance the relative contributions of $E_{N}$ and $E_{O}$ .

The $E_{O}$ energy is designed with a function that measures the distance between the left corners of the rectangles, improving the general visibility and readability of the visualization. The purpose of the component $E_{O}$ is to spread the snippets in the visual space and, that way, the neighborhood component $E_{N}$ is introduced to balance this spread effect in order to preserve neighborhood relations. The neighborhood component $E_{N}$ is implemented using a k-nearest neighbor graph built from the projection, based on the feature vectors of the Web search results.

RWordle

The Wordle technique is used to define positions of tags in a tag cloud visualization. Each tag is placed in a random point and when there is overlap, the new tag is moved in spiral fashion to its initial position, in order to find a valid position (with no overlap).

In the RWordle¹³ technique, the main idea is to provide an orthogonal ordering for the Wordle technique. In this case, two geometry-directed ordering can be used:

Linear Ordering (RWordle-L), where items are classified along a scan line operating over an axis defined by an angle $α$ ;

Concentric Ordering (RWordle-C), where items are classified along their distances to the geometric center of the scene.

Variable placement with separation constraints

The variable placement with separation constraint (VPSC)¹⁰ technique attempts to remove overlap among instances using two steps: first, a set of non-overlap constraints is generated; second, the objective is to find an optimal solution based on this set.

The non-overlap constraints are generated with a line-sweep algorithm that can detect overlap among rectangles. Based on the non-overlap constraints set, the VPSC technique solves the VPSC problem: Let there be n weighted variables $v_{1}, \dots, v_{n}$ $(v_{i} . weight \geq 0)$ and a desired value $v_{i} . des$ for each of them, as well as a set of separation constraints C on the variables. The goal is to find an assignment to these variables that minimize

\sum_{i = 1}^{n} v_{i} . weight \times (v_{i} - v_{i} . des)^{2} subject to C .

(2)

Note that the VPSC considers the problem for one axis at a time, and $v_{i}$ is the position of the instance i. The algorithm works by merging the variables into larger blocks of contiguous variables, until a single block represents the solution.

PRISM

The PRISM⁹ technique attempts to remove nodes overlap by defining a proximity graph that maintains proximity relations. At first, an overlap factor is computed for each edge of the proximity graph as follows

t_{ij} = \max (\min (\frac{w_{i} + w_{j}}{| x_{i}^{0} (1) - x_{j}^{0} (1) |}, \frac{h_{i} + h_{j}}{| x_{i}^{0} (2) - x_{j}^{0} (2) |}), 1)

(3)

where $w_{i}$ and $h_{i}$ denote the half of the width and height of the node i, respectively, and $x_{i}^{0} (1)$ and $x_{i}^{0} (2)$ its x and y coordinates.

Graph nodes that do not overlap take the value $t_{ij} = 1$ . For the nodes in which there is overlap, they can be removed if the edge connecting them is expanded by that overlap factor between the nodes. Thus, the PRISM technique consists of minimizing the following stress function

\sum_{(i, j) \in E_{p}} w_{ij} (∥ x_{i} - x_{j} ∥ - d_{ij})^{2}

(4)

or, generating a layout in which each edge of the proximity graph has the length close to $t_{ij} ∥ x_{i}^{0} - x_{j}^{0} ∥$ , where $d_{ij} = s_{ij} ∥ x_{i}^{0} - x_{j}^{0} ∥$ is the ideal distance for the edge ij, $s_{ij}$ is the scale factor related to the overlap factor $t_{ij}$ , $w_{ij} = (1 / (∥ d_{ij} ∥^{2}))$ is a weighting factor, and $E_{p}$ is the set of edges in the proximity graph. The overlap factor $s_{ij} = \min (t_{ij}, S_{\max})$ limits the overlap removal in each iteration.

Evaluation of overlap removal techniques

This section presents a detailed evaluation of the techniques presented in the section “Overlap Removal Techniques.” The metrics used in the evaluation are based on the similarity between the original and the new layout without overlap, the similarity preservation of multidimensional space and the bi-dimensional space without overlap, and clustering of instances belonging to a same class. These metrics are described in the following.

Evaluation metrics

Layout similarity

Gansner and Hu⁹ proposed a technique to assess the similarity preservation between two layouts. The Layout Similarity metric attempts to quantify how much of the neighborhood structures are affected by the overlap removal algorithm. The technique calculates the length of the edges of the proximity graph created using a Delaunay Triangulation. Given the initial layout $(x^{0})$ and the final layout $(x)$ , the ratios are computed for each edge in the proximity graph as follows

r_{ij} = \frac{∥ x_{i} - x_{j} ∥}{∥ x_{i}^{0} - x_{j}^{0} ∥}, {i, j} \in E_{p}

(5)

where $E_{p}$ represents the edges in the proximity graph. A normalized standard deviation is used to represent the metric quality, in which lower values indicate better similarity.

Stress

The Stress² metric attempts to measure how much information was lost during the dimensionality reduction process. Thus, the lower the Stress value, the better the preservation of the structures.

An approach to compute the Stress (S) is shown in equation (6)

S = \sqrt{\frac{\sum_{i < j} {(d_{ij} - \bar{d_{ij}})}^{2}}{\sum_{i < j} d_{ij}^{2}}}

(6)

where d is the dissimilarities in the n-dimensional space and $\bar{d}$ is the distances in the d-dimensional space.

Silhouette coefficient

The Silhouette Coefficient²⁰ metric is used to interpret clusters consistency and to provide information on how well each instance participates in its cluster. In this case, the clusters were generated by the projection technique, which defines the clusters according to the instances’ classes.

Given an instance i, its silhouette can be computed as follows:

Compute the mean of the distances $a_{i}$ from i to all of the other instances belonging to the same cluster, providing a measure of cohesion;

Compute the smallest distance $b_{i}$ from i to all of the other instances of other clusters, providing a measure to analyze separation of clusters;

The silhouette of i is $s_{i} = ((b_{i} - a_{i}) / (\max (a_{i}, b_{i})))$ .

The value of Silhouette Coefficient is given by the silhouette mean of all instances varying from −1 to 1, where better cohesion and cluster separation are indicated by values closer to 1.

Neighborhood Preservation

The Neighborhood Preservation (NP)²¹ metric is used to assess the projection techniques according to the NP. The k-nearest neighbors of each instance in both multidimensional and projected space are used to compute the preservation ratio, that is, how many neighbors are preserved in the visual space. For example, suppose $k = 4$ and 3 instances are preserved as nearest neighbors, the value of NP is $(3 / 4) = 0.75$ .

The NP value for a projection is the mean of the NP applied to each instance in the data set. Notice that, as the value of k grows, the NP technique shows better results since more instances are maintained as nearest neighbors.

Neighborhood Hit

The Neighborhood Hit (NH)⁵ metric is used to assess the class perception in the projection. In this way, a projection technique shows good results if it is able to consistently separate the classes in the data set. For each instance, its k-nearest neighbors are found to compute the ratio of neighbors belonging to the same class of the evaluated instance. For example, suppose $k = 5$ and 2 instances has the same class as the analyzed instance, the NP value is $(2 / 5) = 0.4$ .

The NH value for a projection is the mean of the NH applied for each instance in the whole projection. Unlike the NP technique, as the value of k grows, the lower is the value of NH technique since more instances will have neighbors with different classes.

Results

The experiments were performed upon eight data sets, described in the following:

Diabetes—contains 169 instances representing patients described by eight features. The data set has 27 kB;

Iris—contains 150 instances representing types of iris plants divided in three classes of 50 instances. The data set has 4 kB;

Mammals—contains 183 instances automatically generated to represent different mammal features. Each mammal is described by 72 features. The data set has 4189 kB;

medical12—contains 72 instances of magnetic resonance images (MRI) described by 28 features. It is a reduced data set from original one with 540 instances. The data set has 21 kB;

medical6—contains 270 instances of MRI images described by 28 features. All instances are classified according to 12 classes. The data set has 75 kB;

CBR-ILP-IR—contains 574 instances of documents described by 43 terms. Each instance represents a paper of three fields: Case-Based-Reasoning (CBR), Intuitive Logic Programming (ILP), and Information Retrieval (IR). The data set has 154 kB;

Corel-1000—contains 1000 images from natural scenes and artificial objects separated in 10 classes. The data set has 1183 kB;

Segmentation—contains 2100 instances of features of 3 × 3 regions of a set of seven outdoor manually segmented images described by 19 features. The data set has 404 kB.

Notice that all data sets are structured and the greater the number of instances, the greater the probability of overlapping markers when projecting on the 2D space. Thus, the number of instances is what matters for evaluating the overlap removal techniques. After the dimensionality reduction, all data sets will have only two coordinates and the number of instances will dictate their size. The tests were performed on a computer with the following configuration: Intel Core i5-4440 CPU, 8 GB RAM, Windows 7 64 bits. The initial projections of the data sets and algorithms’ results can be visualized in Figure 1. By initial projection, we mean the data set projected on 2D space and no overlap removal technique has been applied to it.

Figure 1.

Layouts generated by application of overlap removal techniques.

While the Corel-1000 and segmentation data sets were projected using the least square projection (LSP)⁵ technique, the remaining data sets were projected using the Interactive Document Map (IDMAP)⁴ technique. We used LSP only for those two data sets due to the complexity of the projection technique. The IDMAP is a force-based technique that tries to make the relations among instances in the multidimensional space and in the projected space to be constant for each pair of points ( $x_{i}, x_{j}$ ). For this purpose, a perturbation is applied on the distances of multidimensional and projected spaces. The LSP technique, on the other hand, aims at preserving neighborhood relations existing in multidimensional space. First, a set of representative instances is projected and the remaining instances are projected in order that they reside in the convex hull of their k nearest neighbors, according to the neighborhood in the multidimensional space.

In this work, we used a scan line for the RWordle-L technique with inclination angle of $0^{o}$ to minimize the instances ordering related to the axes. For the ProjSnippet technique, we used the parameters $k = 10$ and $α = 0.5$ , aiming at balancing the components, decreasing the markers overlap, and preserving the similarity relations.

The following sections represent the results according to the selected metrics and time evaluation.

Layout similarity

The Layout Similarity metric was applied among the initial projection and the layout generated by overlap removal techniques. Figure 2 shows the results for each technique and data set.

Figure 2.

Heatmap conveying the Layout Similarity values for each technique and data set. The closer the color is to blue, the better the layout preservation.

It is possible to realize that the ProjSnippet technique was able to reach the best result for all of the data sets. This is explained by the fact that besides being able to maintain the relations imposed by the projected technique, the ProjSnippet technique could not remove all overlap in the initial layout. Such issue helps the ProjSnippet technique to generate layouts more similar to the initial projections. In the second place is the PRISM technique. Since it was able to remove all overlap in the initial layout, its result according to Layout Similarity was higher than the ProjSnippet, that is, the generated layouts were less similar to the original layouts if compared with ProjSnippet layouts. The VPSC technique removes overlaps according to the axes x and y, which does not provide much flexibility in the overlap removal process and leads to a stretched layout. Finally, since the RWordle-C and RWordle-L do not consider any structural relation, both techniques presented higher values of Layout Similarity. Notice that, for small data sets the RWordle-C and RWordle-L techniques performed well.

Silhouette coefficient

As already defined, the Silhouette Coefficient is a measure to evaluate the separation and cohesion of instances belonging to a same class—the better layouts are that whose values are close to $1.0$ and the worst are the ones that are closer to −1.0. Figure 3 shows the Silhouette Coefficient values computed for all projections—initial projections and layouts without overlap.

Figure 3.

Heatmap conveying the Silhouette Coefficient values for each technique and data set. The closer the color to red, the better the class understanding.

Unlike what happened with the results of Layout Similarity, the ProjSnippet technique presented similar results to the PRISM technique. Notice that these techniques are benefited from the fact that the Silhouette Coefficient metric presents better results when blank space is added between clusters of different classes. The IncBoard and HexBoard technique, in general, presented lower result mainly because they place instances of different classes in a close neighborhood. However, notice that for the medical6 data set, the IncBoard and HexBoard techniques were able to project instances separated by classes, leading to better results.

Stress

The Stress is commonly used to measure how much the instances similarity was preserved from the original multidimensional space in the projected space. Figure 4 shows the Stress values for all new layouts computed with the overlap removal techniques.

Figure 4.

Heatmap conveying the Stress values for each technique and data set. The closer the color is to blue, the better the similarity preservation among instances.

In general, all overlap removal techniques got satisfactory results for the Stress technique. On the other hand, since the IncBoard and HexBoard technique compact instances which were distant to each other in the multidimensional space, the Stress values for these techniques are higher.

NP

The NP metric is another way to identify how much the instance relationships were preserved in the dimensionality reduction. The metric was computed for all projections considering up to 30 neighbors. These results are presented in Figures 5 and 6. Note that, for NP and NH graphics, the initial projection is labeled as the name of the data set and the line that represents its analysis is colored by black.

Figure 5.

Performance of each technique on Neighborhood Preservation metric for the data sets (a) diabetes, (b) iris, (c) mammals, and (d) medical12. The neighborhood preservation rate was calculated varying the number of neighbors from 1 to 30. Notice that the black line is the original projection.

Figure 6.

Performance of each technique on Neighborhood Preservation metric for the data sets (a) medical6, (b) CBR-ILP-IR, (c) Corel-1000, and (d) segmentation. The neighborhood preservation rate was calculated varying the number of neighbors from 1 to 30. Notice that the black line is the original projection.

In general, the techniques presented similar results for all data sets. As we commented on the evaluation of Layout Similarity, since the ProjSnippet technique was not capable of removing all overlap among instances for the majority of data sets, its result according to NP follows the initial projection result—logically, the ability of preserving structural and similarity relations contributed to the good result as well. The RWordle-C and RWordle-L technique reached the worst results for the data sets in which classes are too closer to each other, that is, the medical6 and segmentation data sets. For small data sets, we can see that the IncBoard and HexBoard technique affect much more the structures imposed by a multidimensional projection.

NH

NH can be used to measure the quality of groups of instances belonging to a same class. Thus, we can measure if the removal overlap technique messed the groups computed in the original projection. The NH results are presented in Figures 7 and 8.

Figure 7.

Performance of each technique on Neighborhood Hit metric for the data sets (a) diabetes, (b) iris, (c) mammals, and (d) medical12. The metric values were calculated varying the number of neighbors from 1 to 30. Notice that the black line is the original projection.

Figure 8.

Performance of each technique on Neighborhood Hit metric for the data sets (a) medical6, (b) CBR-ILP-IR, (c) Corel-1000, and (d) segmentation. The metric values were calculated varying the number of neighbors from 1 to 30. Notice that the black line is the original projection.

As happened in the NP metric, the techniques presented similar results for all data sets according to the NH metric. Again, since the RWordle-C and RWordle-L technique do not consider any structural relation among instances, such techniques presented difficult and even bigger results for the medical6 and segmentation data sets. Besides that, by compacting layouts, the IncBoard and HexBoard impair their results according to the NH metric since instance of different classes are placed closer to each other. This effect can be verified for the mammals data set (see Figure 7(c)).

It is worth noticing that the ProjSnippet technique follows the results of initial projection. Figure 9 shows the distribution for each technique according to the NH and NP metrics. The PRISM and ProjSnippet techniques presented similar aspects; however, the ProjSnippet technique gave more similar results to the initial projection. Notice that according to NH metric, the distribution given by IncBoard and HexBoard techniques are smaller since the metric is only affected by boundaries of classes, which are treated by IncBoard and HexBoard techniques.

Figure 9.

Distributions of the values of (a) Neighborhood Preservation and (b) Neighborhood Hit metrics, varying the number of neighbors from 1 to 30. Each colored point represents a Neighborhood Hit/Neighborhood Preservation rate value referring to the number of neighbors.

Running time

The running time of each technique can be verified in Figure 10. The time spent by each technique is indicated in milliseconds using logarithmic scale $(lo g_{10})$ .

Figure 10.

Heatmap conveying the time execution in logarithmic scale for each technique and data set. The close the color is to yellow, the better the technique according to time execution.

We can see that only VPSC and ProjSnippet were able to maintain an acceptable time execution for all data sets. The number of instances influenced the time required to complete the process for each algorithm; however, notice that the RWordle-L and RWordle-C techniques were also impaired by the amount of overlap in the initial projection. Since the number of edges in the proximity graph is proportional to the overlap rate, the PRISM technique was also affected by this issue.

Experiment with users

We performed an experiment with 26 users to classify the overlap removal techniques according to the similarity of the layout generated by them and the original layout. For each data set, we presented the initial layout and the rearranged layout for each overlap removal technique. The users chose a score between 0 and 10 to evaluate the generated projection according to its similarity.

By analyzing the boxplots of Figure 11, we can see that the scores given to the techniques are similar, but with slightly better results to the PRISM and RWordle-C techniques. These results give us the insight that the user sometimes cannot rely only on the visualization aspects to define how good or not a projection is after overlap removal, that is, they cannot realize how much the generated layout approaches the initial layout.

Figure 11.

Boxplots of the scores given by the users to the overlap removal techniques.

Discussion

Based on experiments, it is possible to emphasize some characteristics for each technique evaluated in this article:

The IncBoard and HexBoard techniques, in general, got lower performance if compared with the remaining techniques. However, these techniques can be a good option when instances of different classes share boundaries since these techniques can be used to emphasize the separation between such instances. Besides that, the layout generated is more compact;

The RWordle-C and RWordle-L techniques are less sophisticated, therefore, their performances in critical layout characteristics, such as NP, are impaired if they are applied in layouts with high overlap rate or where groups of instances are near each other. However, they are efficient in the cases where the instances are relatively separate;

The ProjSnippet technique is recommended for layouts with low overlap rate and in data sets with a limited number of instances. The technique has the characteristic of preserving the structures, clusters, and the initial neighborhood effectively, besides being possible to control the contribution of the overlap removal and NP. It is interesting to note that the assessment results for the ProjSnippet technique follow the results given by the initial projection;

The VPSC technique presents layouts that preserve the general structure of the projection, besides having a good performance considering the processing time. It can remove the overlap with effectivity, but it presents medium performance if compared with the other techniques;

The PRISM technique presents good results according to the metrics, being able to preserve the relations imposed by the initial projection and removing any overlap. However, this technique has the difficulty of maintaining the layout compact, and the time execution can be impaired by the number of instances and overlap rate increase.

Considering these characteristics, Figure 12 shows a simple guide to use an algorithm based on the requirement of structures preservation and size of a data set—notice that a data set with moderate size and high overlap rate can be evaluated as a big data set for some techniques, such as PRISM, RWordle-L, and RWordle-C. Moreover, it is not recommended to apply IncBoard and HexBoard techniques on data sets with small or moderate sizes since the trade-off between compact shape and structures preservation is not worth it. Although the classification of data set sizes according to small, medium, and big can be empirical, we can define small data sets as those with a maximum of 200 instances, medium data sets as those with size between 201 and 500, and big data sets as those with size above 501. However, note that the overlap rate can influence the choice of a technique, that is, the higher the overlap rate, the bigger a data set must be considered.

Figure 12.

Visual guide to apply an overlap removal algorithm. The structures preservation means how much structures are needed to be preserved, that is, if one wants to preserve as many structures as possible, the option “High” must be chosen. If the final projection can have a balanced structures preservation, the option “Medium” must be chosen, and one can choose “Low” if no or low structures must be preserved. On the data set size, the choice must be made based on the complexity of the algorithms. If the data set size can be executed through $O (n^{2})$ algorithm with a reasonable amount of time, the option “Small” must be chosen, and “Medium-Big” otherwise.

Conclusion

Multidimensional projections are a powerful tool for analyzing instances similarity of a multidimensional data set. Such techniques provide an overview about the data and allow identification of trends, patterns, and anomalies. However, the overlap problem faced by the visual representation impairs effective analysis since it is not possible to visualize the data instances that are obstructed. So that, overlap removal techniques can be applied to decrease the overlap problem and to improve the exploratory process.

In this work, we compared four approaches to remove overlap in the visual metaphor used to show multidimensional projections, as well as two projection techniques that already consider overlap among markers. These techniques were evaluated according to class, neighborhood, and structure preservation. Through the assessment of these techniques, it was possible to highlight their characteristics and to provide a simple guide to choose an overlap removal or a multidimensional projection technique that has non-overlap constraints.

As future works, it is necessary to investigate these algorithms by means of clusters, in other words, the overlap removal process can be applied on small portions of data. As it was possible to realize based on results, the algorithms tend to present better layouts when applied on small data sets. If the overlap removal process is applied selectively, the issues faced by some algorithms can be decreased, such as display screen increment and processing delay.

Footnotes

Funding

This work was supported by FAPESP (São Paulo Research Foundation) (Grant numbers #2015/18238-9, #2016/11707-6, #2018/17881-3; #2018/25755-8).

ORCID iD

Wilson E Marcílio

References

Wong

Thomas

Visual analytics. IEEE Comput Graph Appl 2004; 24: 20–21.

Kruskal

JB.

Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 1964; 29: 115–129.

Tejada

Minghim

Nonato

LG.

On improved projection techniques to support visual exploration of multidimensional data sets. Inform Visual 2003; 2(4): 218–231.

Minghim

Paulovich

Lopes

AA.

Content-based text mapping using multidimensional projections for exploration of document collections. SPIE Proc: Visual Data Anal 2006; 12: 6060.

Paulovich

Nonato

Rosane

, et al. Least square projection: a fast high-precision multidimensional projection technique and its application to document mapping. IEEE T Vis Comput Gr 2008; 3: 564–575.

Eler

Nakazaki

Paulovich

, et al. Visual analysis of image collections. Vis Comput 2009; 25(10): 923–937.

Oliveira

RAP

Silva

Eler

. Hybrid visualization: a new approach to display instances relationship and attributes behaviour in a single view. In: Proceedings of the 19th international conference on information visualisation, Barcelona, 22–24 July 2015, pp.277–282. New York: IEEE.

Nieto

Roman

Pagliosa

, et al. Similarity preserving snippet-based visualization of web search results. IEEE T Vis Comput Gr 2014; 20(3): 457–470.

Gansner

Efficient, proximity-preserving node overlap removal. J Graph Algo Appl 2010; 14(1): 53–74.

10.

Dwyer

Marriott

Stuckey

PJ.

Fast node overlap removal. In: Proceedings of the 13th international conference on graph drawing, Karlsruhe, 18–20 September 2006, pp. 153–164. New York: Springer.

11.

Pinho

Oliveira

MCF

Lopes

. Incremental board: a grid-based space for visualizing dynamic data sets. In: Proceeding of the 2009 ACM symposium on applied computing, Honolulu, HI, 8–12 March 2009, pp.1757–1764.

12.

Pinho

Oliveira

MCF

. Hexboard: conveying pairwise similarity in an incremental visualization space. In: Proceedings of the 13th international conference information visualization, Barcelona, 15–17 July 2009, pp.32–37. New York: IEEE.

13.

Strobelt

Spicker

Stoffel

, et al. Rolled-out Wordles: a heuristic method for overlap removal of 2D data representatives. Comput Graph Forum 2012: 1135–1144.

14.

Gomez-Nieto

Casaca

Nonato

, et al. Mixed integer optimization for layout arrangement. In: Proceedings of the 2013 XXVI conference on graphics, patterns and images, Arequipa, Peru, 5–8 August 2013. Washington, DC: IEEE.

15.

Tatu

Bak

Bertini

, et al. Visual quality metrics and human perception: an initial study on 2D projections of large multidimensional data. In: Proceedings of the international conference on advanced visual interfaces, Roma, 26–28 May 2010, pp. 49–56. New York: ACM.

16.

Sips

Neubert

Lewis

, et al. Selecting good views of high-dimensional data using class consistency. Comput Graph Forum 2009; 28(3): 831–838.

17.

Tatu

Albuquerque

Eisemann

, et al. Combining automated analysis and visualization techniques for effective exploration of high-dimensional data. In: Proceedings of the IEEE symposium on visual analytics science and technology (VAST), Atlantic City, NJ, 12–13 October 2009, pp. 59–66. New York: IEEE.

18.

Sedlmair

Tatu

Munzner

, et al. A taxonomy of visual cluster separation factors. Comput Graph Forum 2012; 31(3pt.4): 1335–1344.

19.

Wang

Feng

Chu

, et al. A perception-driven approach to supervised dimensionality reduction for visualization. IEEE Trans Vis Comput Graph 2018; 24(5): 1828–1840

20.

Kaufman

Rousseuw

PJ.

Finding Groups in Data: An Introduction to Cluster Analysis. Principles and: Practice. Hoboken, NJ: John Wiley & Sons, 2005.

21.

Paulovich

Minghim

Hipp: a novel hierarchical point placement strategy and its application to the exploration of document collections. IEEE T Vis Comput Gr 2008; 14(6): 1229–1236.