The HVT package is a collection of R functions to facilitate building topology preserving maps for rich multivariate data analysis, see Figure 1 as an example of a 3D torus map generated from the package. Tending towards a big data preponderance, a large number of rows. A collection of R functions for this typical workflow is organized below:
Data Compression: Vector quantization (VQ), HVQ (hierarchical vector quantization) using means or medians. This step compresses the rows (long data frame) using a compression objective.
Data Projection: Dimension projection of the compressed cells to 1D,2D or Interactive surface plot with the Sammons Non-linear Algorithm. This step creates topology preserving map (also called embeddings) coordinates into the desired output dimension.
Tessellation: Create cells required for object visualization using the Voronoi Tessellation method, package includes heatmap plots for hierarchical Voronoi tessellations (HVT). This step enables data insights, visualization, and interaction with the topology preserving map useful for semi-supervised tasks.
Scoring: Scoring new data sets or test data and recording their assignment using the map objects from the above steps, in a sequence of maps if required.
Temporal Analysis and Visualization: Collection of functions that analyzes time series data for its underlying patterns, calculation of transitioning probabilities and the visualizations for the flow of data over time.
Dynamic Forecasting: Simulate future states of dynamic systems using Monte Carlo simulations of Markov Chain (MSM), enabling ex-ante predictions for time-series data.
Compression is a technique used to reduce the data size while preserving its essential information, allowing for efficient storage and decompression to reconstruct the original data. While Vector quantization (VQ) is a technique used in data compression to represent a set of data points with a smaller number of representative vectors. It achieves compression by exploiting redundancies or patterns in the data and replacing similar data points with representative vectors.
This package offers several advantages for performing data compression as it is designed to handle high-dimensional data more efficiently. It provides a hierarchical compression approach, allowing multi-resolution representation of the data. The hierarchical structure enables efficient compression and storage of the data while preserving different levels of detail. HVT aims to preserve the topological structure of the data during compression. Spatial data with irregular shapes and complex structures in high-dimensional data can contain valuable information about relationships and patterns. HVT seeks to capture and retain these topological characteristics, enabling meaningful analysis and visualization.This package employs tessellation to divide the compressed data space into distinct cells or regions while preserving the topology of the original data. This means that the relationships and connectivity between data points are maintained in the compressed representation.
This package can perform vector quantization using the following algorithms-
The second and third steps are iterated until a predefined number of iterations is reached or the clusters converge. The runtime for the algorithm is O(n).
2.1.2 Using k-medoidsThe second and third steps are iterated until a predefined number of iterations is reached or the clusters converge. The runtime for the algorithm is O(k * (n-k)^2).
These algorithm divides the dataset recursively into cells using \(k-means\) or \(k-medoids\) algorithm. The maximum number of subsets are decided by setting \(n_cells\) to, say five, in order to divide the dataset into maximum of five subsets. These five subsets are further divided into five subsets(or less), resulting in a total of twenty five (5*5) subsets. The recursion terminates when the cells either contain less than three data point or a stop criterion is reached. In this case, the stop criterion is set to when the cell error exceeds the quantization threshold.
The steps for this method are as follows:
The stop criterion is when the quantization error of a cell satisfies one of the below conditions:
The quantization error for a cell is defined as follows:
\[QE = \max_i(||A-F_i||_{p})\]
where
Let us try to understand quantization error with an example.
Figure 1: The Voronoi tessellation for level 1 shown for the 5 cells with the points overlayed
An example of a 2 dimensional VQ is shown above.
In the above image, we can see 5 cells with each cell containing a certain number of points. The centroid for each cell is shown in blue. These centroids are also known as codewords since they represent all the points in that cell. The set of all codewords is called a codebook.
Now we want to calculate quantization error for each cell. For the sake of simplicity, letâs consider only one cell having centroid A and m data points \(F_i\) for calculating quantization error.
For each point, we calculate the distance between the point and the centroid.
\[ d = ||A - F_i||_{p} \]
In the above equation, p = 1 means L1_Norm distance whereas p = 2 means L2_Norm distance. In the package, the L1_Norm distance is chosen by default. The user can pass either L1_Norm, L2_Norm or a custom function to calculate the distance between two points in n dimensions.
\[QE = \max_i(||A-F_i||_{p})\]
Now, we take the maximum calculated distance of all m points. This gives us the furthest distance of a point in the cell from the centroid, which we refer to as Quantization Error. If the Quantization Error is higher than the given threshold, the centroid/ codevector is not a good representation for the points in the cell. Now we can perform further Vector Quantization on these points and repeat the above steps.
Please note that the user can select mean, max or any custom function to calculate the Quantization Error. The custom function takes a vector of m value (where each value is a distance between point in n dimensions and centroids) and returns a single value which is the Quantization Error for the cell.
If we select mean as the error metric, the above Quantization Error equation will look like this:
\[QE = \frac{1}{m}\sum_{i=1}^m||A-F_i||_{p}\]
3. Data ProjectionProjection mainly involves converting data from its original form to a different space or coordinate system while preserving certain properties of it. By projecting data into a common coordinate system, spatial relationships, distances, areas, and other spatial attributes can be accurately measured and compared.
HVT performs projection as part of its workflow to visualize and explore high-dimensional data. The projection step in HVT involves mapping the compressed data, represented by the hierarchical structure of cells, onto a lower-dimensional space for visualization purposes, as human perception is more suited to interpreting information in lower-dimensional spaces.Users can zoom in/out, rotate, and explore different regions of the projected space to gain insights and understand the data from different perspectives.
Sammonâs projection is an algorithm used in this package to map a high-dimensional space to a space of lower dimensionality while attempting to preserve the structure of inter-point distances in the projection. It is particularly suited for use in exploratory data analysis and is usually considered a non-linear approach since the mapping cannot be represented as a linear combination of the original variables. The centroids are plotted in 2D after performing Sammonâs projection at every level of the tessellation.
Denoting the distance between \(i^{th}\) and \(j^{th}\) objects in the original space by \(d_{ij}^*\), and the distance between their projections by \(d_{ij}\). Sammonâs mapping aims to minimize the below error function, which is often referred to as Sammonâs stress or Sammonâs error.
\[E=\frac{1}{\sum_{i<j} d_{ij}^*}\sum_{i<j}\frac{(d_{ij}^*-d_{ij})^2}{d_{ij}^*}\]
The minimization of this can be performed either by gradient descent, as proposed initially, or by other means, usually involving iterative methods. The number of iterations need to be experimentally determined and convergent solutions are not always guaranteed. Many implementations prefer to use the first Principal Components as a starting configuration.
4. TessellationA Voronoi diagram is a way of dividing space into a number of regions. A set of points (called seeds, sites, or generators) is specified beforehand and for each seed, there will be a corresponding region consisting of all points within proximity of that seed. These regions are called Voronoi cells. It is complementary to Delaunay triangulation is a geometrical algorithm used to create a triangulated mesh from a set of points in a plane which has the property that no data point lies within the circumcircle of any triangle in the triangulation. This property guarantees that the resulting cells in the tessellation do not overlap with each other.
By using Delaunay triangulation, HVT can achieve a partitioning of the data space into distinct and non-overlapping regions, which is crucial for accurately representing and analyzing the compressed data.Additionally, the use of Delaunay triangulation for tessellation ensures that the resulting cells have well-defined shapes, typically triangles in two dimensions or tetrahedra in three dimensions.
The hierarchical structure resulting from tessellation preserves the inherent structure and relationships within the data. It captures clusters, subclusters, and other patterns in the data, allowing for a more organized and interpretable representation. The hierarchical structure reduces redundancy and enables more compact representations.
Tessellate: Constructing Voronoi Tesselation
In this package, we use sammons from the package MASS to project higher dimensional data to a 2D space. The function hvq called from the trainHVT function returns hierarchical quantized data which will be the input for construction of the tessellations. The data is then represented in 2D coordinates and the tessellations are plotted using these coordinates as centroids. We use the package deldir for this purpose. The deldir package computes the Delaunay triangulation (and hence the Dirichlet or Voronoi tessellation) of a planar point set according to the second (iterative) algorithm of Lee and Schacter. For subsequent levels, transformation is performed on the 2D coordinates to get all the points within its parent tile. Tessellations are plotted using these transformed points as centroids. The lines in the tessellations are chopped in places so that they do not protrude outside the parent polygon. This is done for all the subsequent levels.
Scoring basically refers to the process of chalking up or estimating future values or outcomes based on existing data patterns.In training process, a model is developed based on historical data or a training dataset, and this model is then used to score new, unseen data. The model captures the underlying patterns, trends, and relationships present in the training data, allowing it to pin point the cell of the similar or related data points.
In this package, we use scoreHVT function to score each point in the testing dataset.
Scoring Algorithm
The Scoring algorithm recursively calculates the distance between each point in the testing dataset and the cell centroids for each level. The following steps explain the scoring method for a single point in the testing dataset:
This chunk verifies the installation of all the necessary packages to successfully run this vignette, if not, installs them and attach all the packages in the session environment.
list.of.packages <- c("dplyr", "kableExtra", "geozoo", "plotly", "purrr",
"data.table", "gridExtra","plyr","DT","HVT")
new.packages <-list.of.packages[!(list.of.packages %in% installed.packages()[, "Package"])]
if (length(new.packages))
install.packages(new.packages, dependencies = TRUE, repos='https://cloud.r-project.org/')
invisible(lapply(list.of.packages, library, character.only = TRUE))In this section we explore the capacity of the package to visualize multidimensional data by projecting them to two dimensions using Sammonâs projection and further used for Scoring.
Data Understanding
First of all, let us see how to generate data for torus. We are using a library geozoo for this purpose. Geo Zoo (stands for Geometric Zoo) is a compilation of geometric objects ranging from three to ten dimensions. Geo Zoo contains regular or well-known objects, eg cube and sphere, and some abstract objects, e.g. Boyâs surface, Torus and Hyper-Torus.
Here, we will generate a 3D torus (a torus is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanar with the circle) with 12000 points.
Torus Dataset
The torus dataset includes the following columns:
Lets, explore the torus dataset containing 12000 points. For the sake of brevity we are displaying first 6 rows.
set.seed(240)
# Here p represents dimension of object, n represents number of points
torus <- geozoo::torus(p = 3,n = 12000)
torus_df <- data.frame(torus$points)
colnames(torus_df) <- c("x","y","z")
torus_df <- torus_df %>% round(4)
displayTable(head(torus_df))Letâs visualize the torus (donut) in 3D Space.
plot_ly(x = torus_df$x, y = torus_df$y, z = torus_df$z, type = 'scatter3d',mode = 'markers',
marker = list(color = torus_df$z,colorscale = c('red', 'blue'),showscale = TRUE,size = 3,colorbar = list(title = 'z'))) %>%
layout(scene = list(xaxis = list(title = 'x'),yaxis = list(title = 'y'),zaxis = list(title = 'z'),
aspectratio = list(x = 1, y = 1, z = 0.4)))Now letâs have a look at structure of the torus dataset.
## 'data.frame': 12000 obs. of 3 variables:
## $ x: num -2.63 -1.42 -1.03 1.88 -1.95 ...
## $ y: num 0.566 -0.89 1.107 0.19 -2.251 ...
## $ z: num -0.725 0.946 -0.873 0.994 0.207 ...Data distribution
This section displays four objects.
Variable Histograms: The histogram distribution of all the features in the dataset.
Box Plots: Box plots for all the features in the dataset. These plots will display the median and Interquartile range of each column at a panel level.
Correlation Matrix: This calculates the Pearson correlation which is a bivariate correlation value measuring the linear correlation between two numeric columns. The output plot is shown as a matrix.
Summary EDA: The table provides descriptive statistics for all the features in the dataset.
It uses an inbuilt function called edaPlots to display the above-mentioned four objects.
NOTE: The input dataset should be a data frame object and the columns should be only numeric type.
edaPlots(torus_df, output_type = 'histogram')edaPlots(torus_df, output_type = 'boxplot')edaPlots(torus_df, output_type = 'correlation')Train - Test Split
Let us split the torus dataset into train and test. We will randomly select 80% of the data as train and remaining as test.
smp_size <- floor(0.80 * nrow(torus_df))
set.seed(279)
train_ind <- sample(seq_len(nrow(torus_df)), size = smp_size)
torus_train <- torus_df[train_ind, ]
torus_test <- torus_df[-train_ind, ]Training Dataset
Now, lets have a look at the selected training dataset containing (9600 data points). For the sake of brevity we are displaying first six rows.
rownames(torus_train) <- NULL
displayTable(head(torus_train))Now lets have a look at structure of the training data.
## 'data.frame': 9600 obs. of 3 variables:
## $ x: num 1.796 0.712 1.929 1.018 -0.274 ...
## $ y: num -0.4204 -2.3528 1.2034 0.0344 1.1298 ...
## $ z: num -0.988 -0.889 0.962 -0.189 -0.546 ...Data Distribution
edaPlots(torus_train, output_type = "histogram")edaPlots(torus_train, output_type = "boxplot")edaPlots(torus_train, output_type = "correlation")Testing Dataset
Now, lets have a look at testing dataset containing(2400 data points).For the sake of brevity we are displaying first six rows.
rownames(torus_test) <- NULL
displayTable(head(torus_test))Now lets have a look at structure of the test data.
## 'data.frame': 2400 obs. of 3 variables:
## $ x: num -2.628 2.747 -2.445 -2.649 -0.268 ...
## $ y: num 0.566 -0.999 -1.653 -0.575 -1.08 ...
## $ z: num -0.725 -0.385 0.31 0.704 -0.461 ...Data Distribution
edaPlots(torus_test, output_type = "histogram")edaPlots(torus_test, output_type = "boxplot")edaPlots(torus_test, output_type = "correlation")Note: The steps of compression, projection, and tessellation are iteratively performed until a minimum compression rate of 80% is achieved. Once the desired compression is attained, the resulting model object is used for scoring using the scoreHVT() function
The core function for compression in the workflow is HVQ, which is called within the trainHVT function. we have a parameter called quantization error. This parameter acts as a threshold and determines the number of levels in the hierarchy. It means that, if there are ânâ number of levels in the hierarchy, then all the clusters formed till this level will have quantization error equal or greater than the threshold quantization error. The user can define the number of clusters in the first level of hierarchy and then each cluster in first level is sub-divided into the same number of clusters as there are in the first level. This process continues and each group is divided into smaller clusters as long as the threshold quantization error is met. The output of this technique will be hierarchically arranged vector quantized data.
However, letâs try to comprehend the trainHVT function first before moving on.
trainHVT(
data,
min_compression_perc,
n_cells,
depth,
quant.err,
normalize = TRUE,
distance_metric = c("L1_Norm", "L2_Norm"),
error_metric = c("mean", "max"),
quant_method = c("kmeans", "kmedoids"),
dim_reduction_method = c("sammon" , "tsne" , "umap")
scale_summary = NA,
diagnose = FALSE,
hvt_validation = FALSE,
train_validation_split_ratio = 0.8,
projection.scale,
tsne_perplexity,tsne_theta,tsne_verbose,
tsne_eta,tsne_max_iter,
umap_n_neighbors,umap_min_dist
)Each of the parameters of trainHVT function have been explained below:
data - A dataframe, with numeric columns (features) that will be used for training the model.
min_compression_perc - An integer, indicating the minimum compression percentage to be achieved for the dataset. It indicates the desired level of reduction in dataset size compared to its original size.
n_cells - An integer, indicating the number of cells per hierarchy (level). This parameter determines the granularity or level of detail in the hierarchical vector quantization. Minimum n_cells per hierarchy is 3.
depth - An integer, indicating the number of levels. A depth of 1 means no hierarchy (single level), while higher values indicate multiple levels (hierarchy).
quant.err - A number indicating the quantization error threshold. A cell will only breakdown into further cells if the quantization error of the cell is above the defined quantization error threshold.
normalize - A logical value indicating if the dataset should be normalized. When set to TRUE, scales the values of all features to have a mean of 0 and a standard deviation of 1 (Z-score)
distance_metric - The distance metric can be L1_Norm(Manhattan) or L2_Norm(Euclidean). L1_Norm is selected by default. The distance metric is used to calculate the distance between a datapoint and its centroid.
error_metric - The error metric can be mean or max. max is selected by default. max will return the max of m values and mean will take mean of m values where each value is a distance between a point and centroid of the cell.
quant_method - The quantization method can be kmeans or kmedoids. Kmeans uses means (centroids) as cluster centers while Kmedoids uses actual data points (medoids) as cluster centers. kmeans is selected by default.
dim_reduction_method - The dimensionality reduction method to be chosen. options are âtsneâ , âumapâ & âsammonâ. Default is âsammonâ.
scale_summary - A list with user defined mean and standard deviation values for all the features in the dataset. Pass the scale summary when normalize is set to FALSE.
diagnose - A logical value indicating whether user wants to perform diagnostics on the model. Default value is FALSE.
hvt_validation - A logical value indicating whether user wants to holdout a validation set and find mean absolute deviation of the validation points from the centroid. Default value is FALSE.
train_validation_split_ratio - A numeric value indicating train validation split ratio. This argument is only used when hvt_validation has been set to TRUE. Default value for the argument is 0.8.
tsne_perplexity - A numeric, balances the attention t-SNE gives to local and global aspects of the data. Lower values focus more on local structure, while higher values consider more global structure. It is recommended to be between 5 and 50. Default value is 30.
tsne_theta - A numeric, speed/accuracy trade-off parameter for Barnes-Hut approximation. If set to 0, exact t-SNE is performed, which is slower. If set to greater than 0, an approximation is used, which speeds up the process but may reduce accuracy. Default value is 0.5
tsne_eta (learning_rate) - A numeric, learning rate for t-SNE optimization.Determines the step size during optimization. If too low, the algorithm might get stuck in local minima; if too high, the solution may become unstable. Default value is 200.
tsne_max_iter - An integer, maximum number of iterations. Number of iterations for the optimization process. More iterations can improve results but increase computation time. Default value is 1000.
umap_n_neighbors - An integer, the size of the local neighborhood (in terms of number of neighboring sample points) used for manifold approximation, controls the balance between local and global structure in the data, smaller values focus on local structure, while larger values capture more global structures. Default value is 15.
umap_min_dist - A numeric, the minimum distance between points in the embedded space, controls how tightly UMAP packs points together, lower values result in a more clustered embedding. Default value is 0.1
The output of trainHVT function (list of 7 elements) have been explained below with an image attached for clear understanding.
NOTE: Here the attached image is the snapshot of output list generated from iteration 1 which can be referred later in this section
Figure 3: The Output list generated by trainHVT function.
The â1st elementâ is a list containing information related to plotting tessellations. This information might include coordinates, boundaries, or other details necessary for visualizing the tessellations
The â2nd elementâ is a list containing information related to Sammonâs projection coordinates of the data points in the reduced-dimensional space.
The â3rd elementâ is a list containing detailed information about the hierarchical vector quantized data along with a summary section containing no of points, Quantization Error and the centroids for each cell for 2D.
The â4th elementâ is a list that contains all the diagnostics information of the model when diagnose is set to TRUE. Otherwise NA.
The â5th elementâ is a list that contains all the information required to generates a Mean Absolute Deviation (MAD) plot, if hvt_validation is set to TRUE. Otherwise NA
The â6th elementâ is a list containing detailed information about the hierarchical vector quantized data along with a summary section containing no of points, Quantization Error and the centroids for each cell which is the output of hvq.
The â7th elementâ (model info) is a list that contains model generated timestamp, input parameters passed to the model, validation results and the dimensionality reduction evaluation metrics table.
We will use the trainHVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the trainHVT function again.
In our example we will iteratively increase the number of cells until the desired compression percentage is reached instead of increasing the quantization threshold because it may reduce the level of detail captured in the data representation
Iteration 1:
We will pass the below mentioned model parameters along with torus training dataset (containing 9600 datapoints) to trainHVT function.
Model Parameters
hvt.torus <- trainHVT(
torus_train,
n_cells = 100,
depth = 1,
quant.err = 0.1,
normalize = FALSE,
distance_metric = "L2_Norm",
error_metric = "max",
quant_method = "kmeans",
dim_reduction_method = "sammon")As it can be seen from the table above, none of the 100 cells have reached the quantization threshold error. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if desired compression (80%) is reached
Letâs take a look on the 1D projection of this iteration. The output of hvq from the trainHVT function is then passed to the plotHVT function, which applies Sammonâs 1D using MASS package. The resulting 1D Sammonâs points are used to determine their corresponding cell IDs and subsequently plotted in a plotly object.
plotHVT(hvt.torus, plot.type = '1D')Figure 4: Sammons 1D x Cell ID plot for layer 1 shown for the 100 cells in the torus training dataset
Iteration 2:
Letâs retry by increasing the n_cells parameter to 300 for torus training dataset (containing 9600 datapoints).
Model Parameters
hvt.torus2 <- trainHVT(
torus_train,
n_cells = 300,
depth = 1,
quant.err = 0.1,
normalize = FALSE,
distance_metric = "L2_Norm",
error_metric = "max",
quant_method = "kmeans",
dim_reduction_method = "sammon"
)It can be observed from the table above that only 143 cells out of 300 i.e. 48% of the cells reached the Quantization Error threshold. Therefore we can further subdivide the cells by increasing the n_cells parameters and then see if 80% compression is reached
plotHVT(hvt.torus2, plot.type = '1D')Figure 5: Sammons 1D x Cell ID plot for layer 1 shown for the 300 cells in the torus training dataset
Iteration 3:
Since we are yet to achieve the compression of atleast 80%, lets try again by increasing the n_cells parameter to 500 for torus training dataset (containing 9600 datapoints) .
Model Parameters
set.seed(240)
hvt.torus3 <- trainHVT(
torus_train,
n_cells = 500,
depth = 1,
quant.err = 0.1,
normalize = FALSE,
distance_metric = "L2_Norm",
error_metric = "max",
quant_method = "kmeans",
dim_reduction_method = "sammon"
)By increasing the number of cells to 500, we were successfully able to compress 90% of the data, so we will not further subdivide the cells
We successfully compressed data to 90% using n_cells parameter as 500, the next step involves performing data projection on the compressed data. In this step, the compressed data will be transformed and projected onto a lower-dimensional space to visualize and analyze the data in a more manageable form.
plotHVT(hvt.torus3, plot.type = '1D')Figure 6: Sammons 1D x Cell ID plot for layer 1 shown for the 500 cells in the torus training dataset
7.2 Step 2: Data ProjectionThis section focusses on projecting the sammonâs dimensionality reduction from multi dimension to 2D. The following plots will have the centroids plotted in 2D space with x coordinate of the centroid points on X-axis and y coordinate of the centroid points on Y-axis.
Now letâs try to understand plotHVT function. The parameters have been explained in detail below:
plotHVT <-(hvt.results,line.width,color.vec,
centroid.size, centroid.color,
child.level, hmap.cols,
cell_id, cell_id_size,
cell_id_position,quant.error.hmap,
separation_width, layer_opacity,
dim_size, plot.type = '2Dhvt') hvt.results - (1D/2Dproj/2Dhvt/2Dheatmap/surface_plot) A list obtained from the trainHVT function. This list provides an overview of the hierarchical vector quantized data, including diagnostics, tessellation details, Sammonâs projection coordinates, and model input information.
line.width - (2Dhvt/2Dheatmap) A vector indicating the line widths of the tessellation boundaries for each layer.
color.vec - (2Dhvt/2Dheatmap) A vector indicating the colors of the tessellations boundaries at each layer.
centroid.size - (2Dhvt/2Dheatmap) A vector of size of centroids for each level of tessellations.
centroid.color - (2Dhvt/2Dheatmap) A vector of color of centroids for each level of tessellations.
child.level - (2Dhvt/2Dheatmap/surface_plot) A Number indicating the level for which the plot is to be plotted.
hmap.cols - (2Dheatmap/surface_plot) A Number or a Character which is the column number or column name from the dataset indicating the variables for which the plot should be displayed.
cell_id - (2Dhvt/2Dheatmap) A Logical value to indicate whether the plot should have Cell IDs or not. Only applicable for the level 1. (default = FALSE)
cell_id_size - (2Dhvt/2Dheatmap) A number indicating the size of the cell ID text. Only applicable for the level 1. (default = 1)
cell_id_position - (2Dhvt/2Dheatmap) A Character indicating the position of the cell ID text. Only applicable for the level 1. Accepted entries are âtopâ, âleftâ, âbottomâ or ârightâ. (default = âbottomâ)
quant.error.hmap - (2Dheatmap) A number representing the quantization error threshold to be highlighted in the heatmap. When a value is provided, it will emphasize cells with quantization errors equal or less than the specified threshold, indicating that these cells cannot be further subdivided in the next depth layer. The default value is NULL, meaning all cells will be colored in the heatmap across various depths.
sepration_width - (surface_plot) An integer indicating the width between hierarchical levels in surface plot.
layer_opacity - (surface_plot) A vector indicating the opacity of each hierarchical levels in surface plot.
dim_size - (surface_plot) An integer controls the resolution or granularity of the 3D surface grid. (Higher dim_size = more detailed/smoother surface but slower rendering while Lower dim_size = less detailed/blockier surface but faster rendering)
plot.type - A Character indicating which type of plot should be generated. Accepted entries are â1Dâ, â2Dprojâ,â2Dhvtâ,â2Dheatmapâ & âsurface_plotâ. Default value is â2Dhvtâ.
Iteration 1:
Lets see the projected Sammons 2D onto a plane with n_cell set to 100 in first iteration.
plotHVT(hvt.torus, plot.type = '2Dproj')Figure 7: Sammons 2D Plot for 100 cells
Iteration 2:
Lets see the projected Sammons 2D onto a plane with n_cell set to 300 in second iteration.
plotHVT(hvt.torus2, plot.type = '2Dproj')Figure 8: Sammons 2D Plot for 300 cells
Iteration 3:
Lets see the projected Sammons 2D onto a plane with n_cell set to 500 in third iteration.
plotHVT(hvt.torus3, plot.type = '2Dproj')Figure 9: Sammons 2D Plot for 500 cells
7.3 Step 3: TessellationThe deldir package computes the Delaunay triangulation (and hence the Dirichlet or Voronoi tessellation) of a planar point set according to the second (iterative) algorithm of Lee and Schacter. For subsequent levels, transformation is performed on the 2D coordinates to get all the points within its parent tile. Tessellations are plotted using these transformed points as centroids. plotHVT is the main function to plot hierarchical voronoi tessellation.
Iteration 1:
To enhance visualization, letâs generate a plot of the Voronoi tessellation for the first iteration where we set n_cells parameter as 100. This plot will provide a visual representation of the Voronoi regions corresponding to the data points, aiding in the analysis and understanding of the data distribution.
plotHVT(hvt.torus,plot.type = '2Dhvt')Figure 10: The Voronoi tessellation for layer 1 shown for the 100 cells in the torus training dataset
Iteration 2:
Now, letâs plot the Voronoi tessellation for the second iteration where we set n_cells parameter to 300.
plotHVT(hvt.torus2,plot.type = '2Dhvt')Figure 11: The Voronoi tessellation for layer 1 shown for the 300 cells in the torus training dataset
Iteration 3:
Now, letâs plot the Voronoi tessellation again, for the third iteration where we set n_cells parameter to 500.
plotHVT(hvt.torus3,plot.type = '2Dhvt')Figure 12: The Voronoi tessellation for layer 1 shown for the 500 cells in the torus training dataset
From the presented plot, the inherent structure of the donut can be easily observed in the two-dimensional space
7.3.1 Heat MapsNow letâs plot the Voronoi Tessellation with the heatmap overlaid for all the features in the torus data for better visualization and interpretation of data patterns and distributions.
The heatmaps displayed below provides a visual representation of the spatial characteristics of the torus, allowing us to observe patterns and trends in the distribution of each of the features (x,y,z). The sheer green shades highlight regions with higher coordinate values in each of the heatmaps, while the indigo shades indicate areas with the lowest coordinate values in each of the heatmaps. By analyzing these heatmaps, we can gain insights into the variations and relationships between each of these features within the torus structure.
plotHVT(hvt.torus3,hmap.cols = "n",plot.type = '2Dheatmap')Figure 13: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for No. of entities in each cell in the torus dataset
plotHVT(hvt.torus3,hmap.cols = "x",plot.type = '2Dheatmap')Figure 14: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable x in the torus dataset
plotHVT(hvt.torus3,hmap.cols = "y",plot.type = '2Dheatmap')Figure 15: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable y in the torus dataset
plotHVT(hvt.torus3,hmap.cols = "z", plot.type = '2Dheatmap')Figure 16: The Voronoi tessellation for layer 1 and number of cells 500 with the heat map overlaid for variable z in the torus dataset
Letâs try to comprehend the scoreHVT function first before moving on
scoreHVT(dataset,
hvt.results.model,
child.level,
mad.threshold,
line.width,
color.vec,
normalize,
distance_metric,
error_metric,
yVar,
analysis.plots,
names.column)The parameters for the function scoreHVT are explained below:
dataset - A dataframe containing the testing dataset. The dataframe should have all the variable(features) used for training.
hvt.results.model - A list obtained from the trainHVT function while performing hierarchical vector quantization on training data. This list provides an overview of the hierarchical vector quantized data, including diagnostics, tessellation details, Sammonâs projection coordinates, and model input information.
child.level - A number indicating the depth for which the heat map is to be plotted. Each depth represents a different level of clustering or partitioning of the data.
mad.threshold - A numeric value indicating the permissible Mean Absolute Deviation which is obtained from Minimum Intra centroid plot(when diagnose is set to TRUE in trainHVT). mad.threshold value is important since it is used in anomaly detection.Default value is 0.2 NOTE: for a given datapoint, when the quantization error is above mad.threshold it is denoted as anomaly else not.
line.width - A vector indicating the line widths of the tessellation boundaries for each layer. (Optional Parameters)
color.vec - A vector indicating the colors of the tessellations boundaries at each layer. (Optional Parameters)
normalize - A logical value indicating if the dataset should be normalized. When set to TRUE, the data (testing dataset) is standardized by mean and sd of the training dataset referred from the trainHVT(). When set to FALSE, the data is used as such without any changes.
distance_metric - The distance metric can be L1_Norm(Manhattan) or L2_Norm(Euclidean). The metric is used when calculating distance between each datapoint(in test dataset) with the centroids obtained from results of trainHVT. Default is L1_Norm.
error_metric - The error metric can be mean or max. max will return the max of m values and mean will take mean of m values where each value is a distance between the datapoint and centroid of the cell. This helps in calculating the scored quantization error. Default value is max.
yVar - A character or a vector representing the name of the dependent variable(s)
The below given arguments are used only when character column can be mapped over the scored results. since torus doesnât have a character column, we are not using them in this vignette.
analysis.plots - A logical value to indicate whether to include the insight plots which are useful in viewing the contents and clusters of cells. Default is FALSE.
names.column - The column of names of the datapoints which will be displayed as the contents of the cell in âscoredPlotlyâ. Default is NULL.
Now once we have built the model, let us try to score using our testing dataset (containing 2400 data points) which cell and which level each point belongs to.
scoring_torus <- scoreHVT(torus_test, hvt.torus3, normalize = FALSE)hist(scoring_torus[["actual_predictedTable"]]$diff,
breaks = 20, col = "blue", main = "Mean Absolute Difference",
xlab = "Difference",xlim = c(0,0.20), ylim = c(0,500))Figure 17: Mean Absolute Difference
8. Example II: HVT with the Personal Computer datasetData Understanding
In this section, we will use the Prices of Personal Computers dataset. This dataset contains 6259 observations and 10 features. The dataset observes the price from 1993 to 1995 of 486 personal computers in the US. The variables are price, speed, ram, screen, cd, etc. The dataset can be downloaded from here.
In this example, we will compress this dataset by using hierarchical VQ via k-means and visualize the Voronoi Tessellation plots using Sammons projection. Later on, we will overlay all the variables as a heatmap to generate further insights.
Here, we load the data and store into a variable computers.
computers <- read.csv("https://raw.githubusercontent.com/Mu-Sigma/HVT/master/vignettes/sample_dataset/Computers.csv")Personal Computers Dataset
The Computers dataset includes the following columns:
Letâs explore the Personal Computers Dataset containing (6259 points). For the sake of brevity we are displaying first six rows.
computers <- computers[,-1]
displayTable(head(computers))Now letâs have a look at structure of the dataset.
## 'data.frame': 6259 obs. of 10 variables:
## $ price : int 1499 1795 1595 1849 3295 3695 1720 1995 2225 2575 ...
## $ speed : int 25 33 25 25 33 66 25 50 50 50 ...
## $ hd : int 80 85 170 170 340 340 170 85 210 210 ...
## $ ram : int 4 2 4 8 16 16 4 2 8 4 ...
## $ screen : int 14 14 15 14 14 14 14 14 14 15 ...
## $ cd : chr "no" "no" "no" "no" ...
## $ multi : chr "no" "no" "no" "no" ...
## $ premium: chr "yes" "yes" "yes" "no" ...
## $ ads : int 94 94 94 94 94 94 94 94 94 94 ...
## $ trend : int 1 1 1 1 1 1 1 1 1 1 ...Further process will be carried out after removing non-numeric columns from the dataset, since the distribution plots will take only the continuous variables and K-means is not suitable for factor variables as the sample space for factor variables is discrete. A Euclidean distance function on such a space isnât really meaningful. Hence, we will delete the factor variables(X, cd, multi, premium, trend) in our dataset.
computers <-computers %>% dplyr::select(-c( cd, multi, premium, trend))Data Distribution
edaPlots(computers, output_type = 'histogram')edaPlots(computers, output_type = 'boxplot')edaPlots(computers, output_type = 'correlation')Train - Test Split
Let us split the computers data into train and test. We will randomly select 80% of the data as train and remaining as test.
num_rows <- nrow(computers)
set.seed(123)
train_indices <- sample(1:num_rows, 0.8 * num_rows)
trainComputers <- computers[train_indices, ]
testComputers <- computers[-train_indices, ]Training Dataset
Now, lets have a look at the randomly selected training dataset containing (5007 data points). For the sake of brevity we are displaying first six rows.
trainComputers_data <- trainComputers %>% as.data.frame() %>% round(4)
trainComputers_data <- trainComputers_data %>% dplyr::select(price,speed,hd,ram,screen,ads)
row.names(trainComputers_data) <- NULL
displayTable(head(trainComputers_data))Now letâs have a look at structure of the training dataset.
## 'data.frame': 5007 obs. of 6 variables:
## $ price : num 2799 2197 2744 2999 1974 ...
## $ speed : num 50 33 50 66 33 33 66 33 25 50 ...
## $ hd : num 230 270 340 245 200 528 424 212 528 545 ...
## $ ram : num 8 4 8 16 4 16 16 4 16 4 ...
## $ screen: num 15 14 17 15 14 14 15 17 14 15 ...
## $ ads : num 216 216 275 139 248 267 259 298 307 158 ...Data Distribution
edaPlots(trainComputers_data)edaPlots(trainComputers_data,output_type = 'histogram')edaPlots(trainComputers_data,output_type = 'boxplot')edaPlots(trainComputers_data,output_type = 'correlation')Testing Dataset
Now, lets have a look at the testing dataset containing (1252 data points). For the sake of brevity we are displaying first six rows.
testComputers_data <- testComputers %>% as.data.frame() %>% round(4)
testComputers_data <- testComputers_data %>% dplyr::select(price,speed,hd,ram,screen,ads)
rownames(testComputers_data) <- NULL
displayTable(head(testComputers_data))Now letâs have a look at structure of the testing dataset.
## 'data.frame': 1252 obs. of 6 variables:
## $ price : num 1595 1849 1720 2575 2195 ...
## $ speed : num 25 25 25 50 33 25 50 33 66 50 ...
## $ hd : num 170 170 170 210 170 245 212 250 130 210 ...
## $ ram : num 4 8 4 4 8 8 8 4 4 4 ...
## $ screen: num 15 14 14 15 15 14 14 15 14 17 ...
## $ ads : num 94 94 94 94 94 94 94 94 94 94 ...Data Distribution
edaPlots(testComputers_data)edaPlots(testComputers_data, output_type = "histogram")edaPlots(testComputers_data, output_type = "boxplot")edaPlots(testComputers_data, output_type = "correlation")As we are familiar with the structure of the computers data, we will now follow the following steps to get the scores using the Computers dataset.
8.1 Step 1: Data CompressionFor more detailed information on Data Compression please refer to section 7.1 of this vignette.
We will use the trainHVT function to compress our data while preserving essential features of the dataset. Our goal is to achieve data compression upto atleast 80%. In situations where the compression ratio does not meet the desired target, we can explore adjusting the model parameters as a potential solution. This involves making modifications to parameters such as the quantization error threshold or increasing the number of cells and then rerunning the trainHVT function again.
We will pass the below mentioned model parameters along with computers training dataset (5007) to trainHVT function.
Model Parameters
hvt.results <- trainHVT(trainComputers,
n_cells = 300,
depth = 1,
quant.err = 0.2,
normalize = TRUE,
distance_metric = "L2_Norm",
error_metric = "max",
quant_method = "kmeans",
dim_reduction_method = "sammon")As it can be seen from the table above, 91% of the cells have reached the quantization threshold error. Since we are successfully able to attain the desired compression percentage, so we will not further subdivide the cells
hvt.results[[3]] gives us detailed information about the compressed data.
hvt.results[[3]][['summary']] gives a nice tabular data containing no of points, Quantization Error and the centroids.
The datatable displayed below is the summary from hvt.results showing Cell.IDs, Centroids and Quantization Error for the 300 cells.
For the sake of brevity, we are displaying only the first 20 rows.
displayTable(hvt.results[[3]]$summary)Now let us understand what each column in the above summary table means:
Segment.Level - Layers of the cell. In this case, we have performed Vector Quantization for depth 1. Hence Segment Level is 1
Segment.Parent - Parent segment of the cell
Segment.Child (Cell.Number) - The children of a particular cell. In this case, it is the total number of cells at which we achieved the defined compression percentage
n - No of points in each cell
Cell.ID - Cell_IDâs are generated for the multivariate data using 1-D Sammonâs Projection algorithm
Quant.Error - Quantization Error for each cell
All the columns after this will contain centroids for each cell. They can also be called a codebook, which represents a collection of all centroids or codewords.
plotHVT(hvt.results, plot.type = '1D')Figure 18: Sammons 1D x Cell ID plot for layer 1 shown for the 300 cells in the dataset âcomputersâ
8.2 Step 2: Data ProjectionFor more detailed information on Data Projection please refer to section 7.2 of this vignette.
Lets visualize the projected Sammons 2D for n_cell set to 300 onto a plane.
plotHVT(hvt.results, plot.type = '2Dproj')Figure 19: Sammons 2D Plot for 300 cells
8.3 Step 3: TessellationFor more detailed information on voronoi tessellation please refer to section 7.3 of this vignette.
For better visualisation, letâs plot the Voronoi tessellation using the plotHVT function.
plotHVT(hvt.results,plot.type = '2Dhvt')Figure 20: The Voronoi Tessellation for layer 1 shown for the 300 cells in the dataset âcomputersâ
8.3.1 Heat MapsNow letâs plot the Voronoi Tessellation with the heatmap overlaid for all the features in the computers dataset for better visualization.
The heatmaps displayed below provides a visual representation of the spatial characteristics of the computers data, allowing us to observe patterns and trends in the distribution of each of the features (price,speed,hd,ram,screen,ads). The sheer green shades highlight regions with higher values in each of the heatmaps, while the indigo shades indicate areas with the lowest values in each of the heatmaps. By analyzing these heatmaps, we can gain insights into the variations and relationships between each of these features within the computers data
plotHVT(hvt.results,hmap.cols = "n",plot.type = '2Dheatmap')Figure 21: The Voronoi Tessellation with the heat map overlaid over the No. of entities in each cell in the âcomputersâ dataset
plotHVT(hvt.results,hmap.cols = "price",plot.type = '2Dheatmap')Figure 22: The Voronoi Tessellation with the heat map overlaid over the variable price in the âcomputersâ dataset
plotHVT(hvt.results,hmap.cols = "hd",plot.type = '2Dheatmap')Figure 23: The Voronoi Tessellation with the heat map overlaid over the variable hd in the âcomputersâ dataset
plotHVT(hvt.results, hmap.cols = "ram",plot.type = '2Dheatmap')Figure 24: The Voronoi Tessellation with the heat map overlaid over the variable ram in the âcomputersâ dataset
plotHVT(hvt.results, hmap.cols = "screen",plot.type = '2Dheatmap')Figure 25: The Voronoi Tessellation with the heat map overlaid over the variable screen in the âcomputersâ dataset
plotHVT( hvt.results,hmap.cols = "ads",plot.type = '2Dheatmap')Figure 26: The Voronoi Tessellation with the heat map overlaid over the variable ads in the âcomputersâ dataset
For more detailed information on scoring please refer to section 7.4 of this vignette.
Now once we have built the model, let us try to score using our testing dataset containing(1252 data points) which cell and which level each point belongs to.
scoreHVT(dataset,
hvt.results.model,
child.level,
mad.threshold,
line.width,
color.vec,
normalize,
seed,
distance_metric,
error_metric,
yVar,
analysis.plots,
names.column)The parameters for the function scoreHVT are explained below:
dataset - A dataframe containing the testing dataset. The dataframe should have all the variable(features) used for training.
hvt.results.model - A list obtained from the trainHVT function while performing hierarchical vector quantization on training data. This list provides an overview of the hierarchical vector quantized data, including diagnostics, tessellation details, Sammonâs projection coordinates, and model input information.
child.level - A number indicating the depth for which the heat map is to be plotted. Each depth represents a different level of clustering or partitioning of the data.
mad.threshold - A numeric value indicating the permissible Mean Absolute Deviation which is obtained from Minimum Intra centroid plot(when diagnose is set to TRUE in trainHVT). mad.threshold value is important since it is used in anomaly detection.Default value is 0.2 NOTE: for a given datapoint, when the quantization error is above mad.threshold it is denoted as anomaly else not.
line.width - A vector indicating the line widths of the tessellation boundaries for each layer. (Optional Parameters)
color.vec - A vector indicating the colors of the tessellations boundaries at each layer. (Optional Parameters)
normalize - A logical value indicating if the dataset should be normalized. When set to TRUE, the data (testing dataset) is standardized by mean and sd of the training dataset referred from the trainHVT(). When set to FALSE, the data is used as such without any changes.
distance_metric - The distance metric can be L1_Norm(Manhattan) or L2_Norm(Euclidean). The metric is used when calculating distance between each datapoint(in test dataset) with the centroids obtained from results of trainHVT. Default is L1_Norm.
error_metric - The error metric can be mean or max. max will return the max of m values and mean will take mean of m values where each value is a distance between the datapoint and centroid of the cell. This helps in calculating the scored quantization error. Default value is max.
yVar - A character or a vector representing the name of the dependent variable(s)
The below given arguments are used only when character column can be mapped over the scored results. since torus doesnât have a character column, we are not using them in this vignette.
analysis.plots - A logical value to indicate whether to include the insight plots which are useful in viewing the contents and clusters of cells. Default is FALSE.
names.column - The column of names of the datapoints which will be displayed as the contents of the cell in âscoredPlotlyâ. Default is NULL.
set.seed(240)
scoring_comp <-scoreHVT(
testComputers,
hvt.results,
normalize = TRUE)When normalize is set to TRUE while using scoreHVT, the function has an inbuilt feature to standardize the testing dataset based on the mean and standard deviation of the training dataset from the trainHVT results.
hist(scoring_comp[["actual_predictedTable"]]$diff,
breaks = 20, col = "blue", main = "Mean Absolute Difference",
xlab = "Difference",xlim = c(0,0.6), ylim = c(0,250))Figure 27: Mean Absolute Difference
9. Executive SummaryExample I: HVT with the Torus dataset
We have considered torus dataset for multidimensional data visualization using Sammons projection.
We have randomly selected 9600 datapoints for training and remaining datapoints for validation.
Our goal is to achieve data compression upto atleast 80%
We constructed a compressed HVT map (hvt.torus) by applying the trainHVT() on the torus dataset. We set the parameters as follows: n_cells = 100, quant.error = 0.1, and depth = 1. Upon analyzing the compression summary, we found that none of the 100 cells has the quantization error below the threshold.
We created another compressed HVT map (hvt.torus2) using the trainHVT() algorithm on the torus dataset. This time, we adjusted the parameters to n_cells = 300, quant.error = 0.1, and depth = 1. After examining the compression summary, we discovered that 48% of the cells have reached the quantization threshold error.
Once again, we generated a compressed HVT map (hvt.torus3) using the trainHVT() algorithm on the torus dataset. The parameters for this map were set to n_cells = 500, quant.error = 0.1, and depth = 1. Upon analyzing the compression summary, we found that 90% of the 100 cells have reached the quantization threshold error and we can clearly visualize the 3D torus(donut) in 2D space.
Example II: HVT with the Personal Computer dataset
We have considered Computer dataset for multidimensional data visualization using Sammons projection.
We have randomly selected 80% of datapoints for training and rest for validation.
Our goal is to achieve data compression upto atleast 80%
We construct a compressed HVT map using the trainHVT() on the training dataset by setting n_cells to 300 and quant.error to 0.2, and we were able to attain a compression of 91%
We then plot the Voronoi Tessellation with the heatmap overlaid for all the features in the computers dataset for better visualization
Next, we pass the validation dataset along with the HVT map obtained from trainHVT() to scoreHVT() to see which cell and level each point belongs to
Pricing Segmentation - The package can be used to discover groups of similar customers based on the customer spend pattern and understand price sensitivity of customers
Market Segmentation - The package can be helpful in market segmentation where we have to identify micro and macro segments. The method used in this package can do both kinds of segmentation in one go
Anomaly Detection - This method can help us categorize system behavior over time and help us find anomaly when there are changes in the system. For e.g. Finding fraudulent claims in healthcare insurance
The package can help us understand the underlying structure of the data. Suppose we want to analyze a curved surface such as sphere or vase, we can approximate it by a lot of small low-order polygons in the form of tessellations using this package
In biology, Voronoi diagrams are used to model a number of different biological structures, including cells and bone microarchitecture
Using the base idea of Systems Dynamics, these diagrams can also be used to depict customer state changes over a period of time
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4