Exploring Multi-dimensional Data via Subset Embedding

Let $D(d_{1},…,d_{n})$ be a multi-dimensional dataset, where $d_{i}$ is an attribute with the domain $dom(d_{i})$. A subset consists of records selected by a group of filters, i.e. $r(d_{1})$,…,$r(d_{n})$, where $r(d_{i})$ is a filter that specifies a value range on $dom(d_{i})$, i.e. $r(d_{i})\in dom(d_{i})$.

Filters whose value ranges cover the whole domain, i.e. $r(d_{i})=dom(d_{i})$, can be hidden for brevity. We call the attribute of an unhidden filter a slicing attribute. For example, in Figure 1, the subset (Crime-type: theft) has a single slicing attribute, i.e. Crime-type, while the subset (Week: Saturday, Hour: 20) takes Week and Hour as two slicing attributes.

The number of unhidden filters describes the dimensionality of the subset, denoted as $l=\left|\left\{r(d_{i})|r(d_{i})\neq dom(d_{i})\right\}\right|$. For example, (Crime-type: theft) is a 1-dimensional subset, and (Week: Saturday, Hour: 20) is a 2-dimensional subset.

Each subset can have multiple features, as in Figure 1. We write the $v$th feature of subset $S_{i}$ as $X_{i}^{(v)}$. A feature, describing an aspect of statistical information of all the included records, can be in any form, such as a number (e.g. count of all included records) or a vector (e.g. distribution of aggregate values on an attribute).

According to the above definition, we can represent a subset as a group of feature vectors. The function of the SEN thus is to take feature vectors of a subset as the input and output its embedding. The nature of subset, however, makes existing embedding techniques [MH08, XMTH11] inapplicable, as follows:

First, existing techniques target on objects with features of the same shape (e.g. number and size). Patterns, however, may exist within arbitrary subsets that have different slicing attributes and features. Figure 2a show such a case, in which we project subsets sliced on Crime-type and Week separately together and exclude features of slicing attributes (marked with dashed borders). Taking them as features will incorrectly increase the similarity of subsets, since their values are zero at most positions. Projections containing diverse subsets involve more interesting patterns. In Figure 2a, the theft subset is adjacent to Saturday and Sunday subsets. We thus speculate theft crimes mainly occur at that time. For applicability, the SEN should be able to deal with subsets with arbitrary slicing attributes (R1).

Second, existing techniques are designed to capture the overall similarity of target objects across all features. In contrast, subset patterns are often related to few features. For example, in Figure 2b, two week subsets (Saturday and Sunday) have similar values on a feature (see the feature marked in yellow). Existing techniques cannot output similar embeddings for them due to their significant differences on the other features, resulting in missing patterns or finding incorrect patterns when exploring the latent space. To capture the similarity of subsets on single features is necessary for the SEN (R2).

Finally, existing techniques are always restricted by the slow training speed. Moreover, as a self-supervised technique, a well-trained embedding network can only output embeddings for the objects in the training set, different from the offline training of classification models. Therefore, we have to train a SEN on-the-fly after slicing a multi-dimensional data into subsets. A high training efficiency is desired for the network to facilitate the application in a visual analytics environment (R3).

We use the idea of multi-view learning to design the SEN. Multi-view learning is a common kind of machine learning techniques for multi-view objects [LYZ18, ZXXS17, JY17]. A typical multi-view learning model takes multiple snapshots (views) of an object as the input, as in Figure 3a. Its purpose is taking advantage of the complementary information between views to generate embeddings, thus improving the accuracy of the following object identification or classification tasks. Inspired by multi-view learning, we consider each subset a multi-view object. Each feature can be viewed as a snapshot taken by a virtual camera from different perspectives around the subset, as in Figure 3b.

A common characteristic of multi-view learning techniques is they separately treat individual views. Along this line, we propose a SEN of multi-subnet structure, as in Figure 4b. The core idea of the structure is using independent subnets to handle different features and fuse information of different features into final embeddings. In the next section, we will show how the multi-subnet structure satisfies the above three requirements.

Following the line of “overview->details->patterns” [Shn96], we propose an explorative workflow, as in Figure 5. Analysts first partition the given multi-dimensional dataset into subsets (Progressive Data Partition). They then project the subsets according to their embeddings obtained from a SEN trained on-the-fly, and select subsets with specific distributions (e.g. outliers or clusters) in the projection (Latent Space Creation & Exploration). Analysts finally visualize feature vectors of the selected subsets and observe whether they have consistent values on any features. The more consistent feature values a group of selected subsets have, the more significant patterns they involve (Visual Pattern Discovery).

Figure 6 shows the interface of the visualization system that integrates three components, i.e. Exploration Manager (EM), Subset Projector (SP), and Pattern Explainer (PE), to achieve the above workflow, as follows:

EM implements the progressive data partition that enables analysts to generate a variety of subsets with few operations (step 1), as in Figure 6a. Its main body is a tree. Each node contains subsets selected together from those sliced on its parent.

SP is responsible for creating the projected latent space, in which analysts select subsets that may involve patterns (step 2), as in Figure 6b. It integrates rich interactions and automatic methods to assist in selecting subsets.

PE consists of a group of feature cards implemented as classic visualization techniques to show and compare feature values of selected subsets (step 3), as in Figure 6c. It uses a consistency measure (Section 4.4) to quantify the significance of the patterns.

To enable analysts’ exploration, we should generate a large number of subsets at the beginning of the exploration. For flexibility, the visualization system should support to generate subsets with any slicing attributes covering any attribute ranges. For efficiency, it is impossible to set slicing attributes and attribute ranges for each subset individually, which will introduce a large number of repetitive operations. We thus propose the progressive data partition to balance the two aspects:

First, we limit to slicing data on an attribute. Therefore, each generated subset has a single slicing attribute. Moreover, we consider subsets selected at a time as a new dataset and allow for partitioning it into subsets again, which actually add a slicing attribute.

Second, we discretize the value range of the slicing attribute. Specifically, geographical locations are grouped into nominal units, such as states, cities or zones; temporal attributes are discretized on their natural intervals, such as hours, days, or weeks; numerical attributes are divided into equal intervals. We make each generated subset cover a minimum value interval.

The visualization system utilizes EM to implement the progressive data partition. The main body of EM is a tree, as in Figure 6a. We utilize Figure 7 as an example to illustrate how analysts use EM to generate subsets with different slicing attributes. At the beginning of the exploration, there is only the root in the tree, which represents the original dataset. Analysts can select the root and specify “Week” as the slicing attribute to partition it into 7 subsets and project all the generated subsets, as in Figure 7a. They then select two groups of subsets corresponding to the weekday and the weekend respectively, which form separate child nodes of the root, as in Figure 7b-c. Analysts further select the newly added node that contains subsets of weekend and partition it into 24 subsets on Hour, as in Figure 7d. Each subset thus represents an hour on weekends. They also select two groups of subsets to form two child nodes of the weekend node, as in Figure 7e-f.

Analysts can generate arbitrary subsets they want by repeating the above process. Moreover, the progressive process balances the flexibility and efficiency of the subset generation. First, it simplifies interactive operations. Analysts can simply choose a slicing attribute to generate subsets without the needs of setting the attribute range for each subset individually. Second, it makes the implementation of the visualization system easy. The system only needs to support a type of operations, i.e. slicing a dataset into subsets on a user-specified attribute. Finally, each projected subset covers a unit of the value range of the slicing attribute, which avoids generating a large number of logically-unrelated subsets, making identified patterns more explainable.

In EM, each tree node consists of multiple colored rectangles, as in Figure 6a. Each rectangle represents a subset that covers a single unit of the value range of the slicing attribute. The more subsets a node contains, the longer the node will be. We assign a globally unique color to an attribute, see the legend in Figure 6a. The color of a rectangle indicates the slicing attribute selected at the current round. We can understand all the slicing attributes of subsets of a node by tracing colors of nodes along the path from the root to the node. For example, in Figure 6a, #1 has a single slicing attribute, i.e. Week, while #3 has two slicing attributes, i.e. Week and Hour. For attributes with continuous attribute ranges (e.g. Week and Hour), the transparency of rectangles (subsets) gradually decreases as the attribute value increases. Rectangles of categorical attributes have the same transparency.

EM will display two measure values, i.e. uniformity and the number of outliers [SS04] for each marginal distribution of the selected node (see the colorful rectangles in the upper right corner of Figure 6a, which is showing ten measure values of the root node on five attributes). The two measures provide important guidance for selecting slicing attributes, especially helpful when the dataset contains many attributes. A larger or smaller value may relate to potential patterns. Therefore, analysts can slice the node on the corresponding attribute.

We extract features for sliced subsets, project them according to their embeddings obtained from a SEN trained on-the-fly, and select parts of subsets that may involve patterns, as follows:

Feature Extraction. We calculate the distribution of the number of records on an attribute as a feature for a subset, as in Figure 2. It is also possible to add/remove features, or use other features for each subset. We exclude features of slicing attributes (the reason has been explained in Section 2.2). Using the five-dimensional Chicago crime dataset as an example (Figure 1), each 1-dimensional subset has four features, each 2-dimensional subset has three features, and so on.

Representation Learning & Projection. We train a SEN to obtain uniformly-formatted embeddings of the subsets. We then project the subsets onto a 2-dimensional plane according to their embeddings. We choose t-SNE [MH08] to generate the projection. Other dimensionality reduction techniques can also be used.

Subset Selection. Each point in the generated projection represents a subset, as in Figure 6b. The size of a point encodes the number of records contained in the subset. Analysts select subsets in the projection, which are mapped together as a child of the selected node in the tree. Common interactions, such as zoom, pan, lasso, etc., are supported by SP.

There are three ways to select subsets in the SP, as follows:

1) Analysts can freely select subsets according to the distribution of the projected subsets. Significant clusters or outliers are possible candidates for selection.

2) Analysts can highlight projected subsets within specified attribute ranges and select the highlighted subsets exclusively. For example, in Figure 9c, we highlight seven subsets (sliced on Hour). A common explorative strategy is to change the queried attribute range and observe the distribution of the highlighted subsets in the projection before selecting subsets. Having found any interesting distributions (e.g. clusters or outliers), analysts can select them for further in-depth analysis.

3) Analysts can use the clustering function to divide projected subsets into groups according to their embeddings automatically. Many clustering algorithms, such as K-means, hierarchical clustering, density-based clustering (no need to specify the number of clusters), etc., are integrated. Analysts can set parameters, such as the number of clusters, according to their prior assumptions. For example, we can divide seven subsets sliced on Week into two clusters, considering weekday and weekend are naturally different on many features. They can also interactively adjust the parameter during the exploration. Clustering results, whether expected or not, provide cues for the subset selection. A group of links will appear on the right of the projection after clustering. Each link corresponds to a cluster of subsets, as in Figure 9d. We can click a link to highlight the corresponding subsets.

We use PE to visualize the feature vectors of subsets of different nodes in the tree, as in Figure 6c. Feature vectors of subsets in a node are aggregated and visualized as a whole in each feature card. Each feature card corresponds to a feature and is implemented as a classical visualization technique suitable for the feature. For example, line chart is for showing temporal patterns; bar chart is for showing categorical patterns; thematic map (pie chart + map) is for showing spatial patterns. Analysts can select multiple nodes and add them into a feature card for comparison. Figure 6c contain two nodes respectively, in which each visual item (line/bar/sector) reflects the aggregated feature vector of all the subsets in a node. A feature card will appear when analysts click on the corresponding button in the upper left corner of the system, marked with dashed borders in Figure 6.

We propose a measure to describe the consistency of feature vectors of subsets contained in a node using $\frac{1}{D}\sum_{d=1}^{D}\sigma(d)$, where D represents the size of the feature vector, and $\sigma(d)$ represents the standard deviation of feature vector values at the $d$th positions of all subsets. A lower measure value indicates more consistent feature vectors (as in Figure 8), i.e. more significant subset patterns. We visually encode the measure value for each node in feature cards (see numbers in legends in Figure 6c).

The visualization system has a client-server architecture. The SEN is at the backend, which receives requests from the frontend (written in JavaScript using D3 library [BOH11]) and sends back embeddings. The Flask is used to transfer parameters between the front and back ends. We also build an OLAP index, i.e. data cube, to speed up the feature extraction from the original data.

We develop a visualization system on the Chicago crime dataset [chi] (about 6M records) and perform two categories of tasks to identify patterns at group and individual levels respectively:

Group Segmentation. We partition data into subsets on gradually-increasing slicing attributes. For each partition, we select groups of subsets with similar feature values. Each group thus indicates a kind of crime patterns. The exploration process is shown in Figure 9a and detailed below.

We choose Week with the highest uniformity value as the slicing attribute to partition the data into 7 subsets. We project the subsets (Figure 9b) using t-SNE (perplexity is set to 20, while other hyperparameters are kept as default settings) and find two obvious clusters, i.e. weekday (#Mon- #Fri) and weekend (#Sat-#Sun). We select them as separate tree nodes (#1 and #2) and determine patterns using feature cards. We find crime patterns in a feature card (Figure 9b1), i.e. more crimes occur in the daytime on weekdays (green line), while more occur at night on weekends (orange line).

We further partition #1 into 24 hour subsets to understand finer crime patterns of weekdays. We focus on subsets of night (19:00-1:00), when crimes occur intensively. We highlight the corresponding subsets, which form 3 clusters in the projection, as in Figure 9c. We select them as three separate tree nodes (#3-#5) and find several interesting patterns. For example, some kinds of crimes (marked with dashed borders in Figure 9c1) occur more often at midnight (0:00) than in the evening (19:00-23:00), while residences are the main locations (marked with dashed borders in Figure 9c2).

We finally partition #3 on Location-type. Each subset thus represents a location-type of weekday evening. The subsets are automatically divided into 5 clusters, as in Figure 9d. An interesting finding is two roadway-related subsets, i.e. sidewalk and street, are in two clusters. By selecting them and visualizing their features, we find they are drastically different on features of crime-type and location. Two criminal types (marked with dashed borders in Figure 9d1) and three locations (marked with dashed borders in Figure 9d2) are related to sidewalk, while crimes occurring on street are more diverse and evenly distributed throughout the city.

Individual Relationship Identification. We project subsets of crime types and those sliced on different temporal attributes (Week and Hour) together. The purpose is to know when specific kinds of crimes intensively occur, as follows:

We first project the 16 crime-type subsets with those sliced on Week, as in Figure 10a. We find weekday subsets and weekend subsets are close to different crime-type subsets and select them as tree nodes. The finding indicates that narcotics and criminal damage crimes occur more often in different periods of week, as in Figure 10a1. Their similar feature values (as in Figure 10a2) demonstrate the correctness of the projection. We also find similar patterns on theft and battery (omitted for limited space).

We partition #12 (weekday) and #14 (weekend) on Hour respectively to form two groups of hour subsets. We project 16 crime-type subsets with each group of hour subsets together, as in Figure 10b-c. We find assault subsets (#15 and #17) in the two projections are adjacent to afternoon subsets (12:00–18:00) and evening subsets (19:00–0:00) respectively. Figure 10b1 proves the correctness of the projection, in which the assault subset (#15) and the selected afternoon subsets (#16) have similar values on a feature. The observation indicates that assault crimes occur more often in the afternoon on weekdays, while assault crimes occur more often in the evening on weekends, as in Figure 10c1.

We assess whether SEN can accurately encode single-feature similarity of subsets through two experiments.

We finally test the training speed of SEN using randomly-generated records (subsets). We choose two independent variables, i.e. $|subsets|$ and $|features|$. The experiment is conducted on a GPU server (XEON E5-2680, 196G, 2080Ti).

As in Table 2, the SEN can handle hundreds of subsets with multiple features in a short time. Moreover, the longest training time is 7.5s, which is still an acceptable time cost for most visualization systems. Experiment results show high efficiency of the SEN.

DR is the most common embedding technique for multi-dimensional data. PCA [WEG87] projects data along the directions with maximum variance. MDS [BG05] preserves pairwise Euclidean distances during the projection. ISOMAP [TDSL00] changes the Euclidean distance of MDS to geodesic distance, thus enabling to capture nonlinear manifold structures in high-dimensional space. t-SNE [MH08] allows objects that are close in high-dimensional space to be projected together with high probability in low-dimensional projections. Other important DR techniques include LLE [RS00], LE [BN02], LTSA [ZZ04], etc. Many works exist for explaining the DR results [FKM19, LWCC17, FGS18, CMK20]. All these techniques, however, are to maintain global relationships [SPT19] and cannot be used to explore subset patterns that are often associated with few features.

There are many DR techniques with special objective functions [LMW^∗16, SZS^∗16, EMK^∗19]. Wang et al. [WFC^∗17] propose a DR algorithm that maximizes inter-class distances. Zhang et al. [CZC^∗15] offer a technique that can reflect the similarity of target objects on both statistic metrics and distributions. Fujiwara et al. [FCS^∗19] propose a DR technique for streaming data, which can maintain the mental map of analysts for record or dimension changes. Liu et al. [LATB20] propose a response function preserving algorithm that generates projections showing patterns related to single response functions. SEN is of this category with maintaining the similarity of objects on single features as the objective function.

Applying the neural network in data embedding is a recent trend. Hinton and Salakhutdinov [HS06] implement an autoencoder-based embedding technique that achieves better performance than PCA. Mikolov et al. [MSC^∗13] propose the famous word2vec that embeds words according to their co-occurrence in a document set. Many similar techniques, such as cite2vec [BMS16], location2vec [ZCX^∗19], poi2vec [FCAC17], etc. have been proposed. These techniques, however embed objects using their co-occurring frequency in the dataset, unable to be used to explore subset patterns.

The SEN is inspired by multi-view learning, as in Figure 3. Canonical Correlation Analysis (CCA) is a representative technique [Hot36] that can find two linear projections making the multi-view data maximally correlated. We then obtain embeddings using the basis vectors of the two projections. Many techniques extend CCA to capture nonlinear inter-view relationships [Aka06, AABL13]. These methods, however, only support two-view data. Multi-view representation fusion can exploit the complementary information of multiple views to generate the required embeddings [BJ03, CZX10, SS12]. The principle is to determine the posterior probability p(h|x,y) of the probabilistic model p(x,y,z) over the joint space of the shared latent variables z and the observed two-view data x,y. Applying the neural network in multi-view representation learning is a recent trend. Representative examples are multi-modal autoencoder [NKK^∗11], multi-view convolutional neural network [FPZ16], and multi-modal recurrent neural network [KFF15]. Literature surveys [LYZ18, ZXXS17, JY17] include most recent works. Existing techniques require objects to have the same number of views. They thus cannot be used for arbitrary subsets with different numbers of features.

Many visualization techniques aim at finding subsets where patterns exist [Shn96]. A common strategy is projecting the data into a plane [JFSK15, LT16, BSH^∗15, EDF08]. The projection works as an overview, in which analysts manipulate data and filter parts of interest. Many works combine visualization and automatic algorithms to form a generic tool [FSN^∗20, WCR^∗17, SZS^∗16, LPK^∗15, Gle13]. These methods, however, have done good jobs in searching for subsets where patterns exist, but they cannot find patterns among a group of subsets by considering their feature similarity.

Subspace analysis is a kind of technique to find patterns in dimensional subspaces to overcome the problem of the Curse of Dimensionality [BGRS99]. A common strategy is to design a measure that describes the possibility that patterns exist within a subspace. Ferdosi [FR11] proposes a measure for reordering axes of parallel coordinates to identify high-dimensional structures. Tukey et al. [TT88] propose Scagnostics to identify anomalous scatterplots in the scatterplot matrix (SPLOM). The idea is to reduce the original SPLOM with $O(n^{2})$ cells (n is the number of attributes) to a scagnostics SPLOM with $O(k^{2})$ cells, where k is the number of measures that describe the distribution of points of an original SPLOM cell. Seo et al. [SS04] propose a rank-by-feature framework, in which users sort views according to a ranking measure. There are many other measures to find views of interest [TAE^∗09, AEL^∗10, WMA^∗15]. They, however, are for evaluating views with 1D or 2D axes, i.e. low-dimensional subspaces.

Many approaches assist in exploring patterns in high-dimensional subspaces. Zhou et al. [ZLH^∗16] propose a method to preserve clusters by reconstructing dimensions of subspaces. Wang and Mueller [WM17] decompose a high-dimensional space into a series of 3D subspaces to facilitate pattern exploration. Yuan [YRWG13] proposes Dimension Projection Matrix/Tree that enables to explore record- and dimension-related patterns at the same time. Pagliosa et al. [PPM^∗15] design an interactive tool for comparing different multi-dimensional projections. Xia et al. [XYC^∗17] design the LTSD-GD view that can represent latent low-dimensional structures within multi-dimensional data. Many methods design measures to evaluate how much insights are provided by a multi-dimensional projection [MMdALO15, LT15, AWD12]. All these methods, however, work at the record level without the ability to find patterns associated with subsets.

Shadoan and Weaver [SW13] propose a visualization system for analyzing relationships between subsets. The relationship, however, reflects the common records between subsets, not as general as SEN encoding arbitrary subset features. Gratzl et al. [GGL^∗14] propose Domino that supports the flexible exploration of subsets and their relationships. Borland et al. [BWZ^∗19] propose a visual analytics method to unbiasedly selecting a representative subset for a large dataset. Gotz et al. [GZW^∗19] propose a method for interactively determining the most informative event subset in a specific analysis context. These methods, however, are different from our approach that aims at providing a generic tool to explore patterns among a large number of subsets.