1. Abstract

The HVT package offers a suite of R functions designed to construct topology preserving maps for in-depth analysis of multivariate data. It is particularly well-suited for datasets with numerous records. The package organizes the typical workflow into several key stages:

1. Data Compression: Long datasets are compressed using Hierarchical Vector Quantization (HVQ) to achieve the desired level of data reduction.

2. Data Projection: Compressed cells are projected into one and two dimensions using dimensionality reduction algorithms, producing embeddings that preserve the original topology. This allows for intuitive visualization of complex data structures.

3. Tessellation: Voronoi tessellation partitions the projected space into distinct cells, supporting hierarchical visualizations. Heatmaps and interactive plots facilitate exploration and insights into the underlying data patterns.

4. Scoring: Test dataset is evaluated against previously generated maps, enabling their placement within the existing structure. Sequential application across multiple maps is supported if required.

2. Notebook Requirements

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("plyr", "dplyr", "reactable", "kableExtra", "geozoo",
                      "plotly", "purrr", "data.table", "gridExtra", "tidyr")

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))

3. Example : HVT with the Torus dataset

In this section, we will see how we can use 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 10 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.

Raw Torus Dataset

The torus dataset includes the following columns:

• x: This column represents the X-coordinate of each point in the torus.
• y: This column represents the Y-coordinate of each point in the torus.
• z: This column represents the Z-coordinate of each point in the torus.

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))

Now let’s have a look at structure of the torus dataset.

str(torus_df)

## '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.

• variable: The features/columns of the dataset
• min: Minimum value of that feature/column
• 1st Quartile: The value that splits the lower 25% of the data when arranged in ascending order
• median: Middle value in the ascendingly ordered dataset
• mean: Sum of all values in the dataset divided by the total number of values
• sd: Measure of the dispersion of dataset relative to its mean.
• 3rd Quartile: The value that splits the lower 75% of the data when arranged in ascending order
• max: Maximum value of that feature/column
• hist: The basic barchart of the data distribution of a feature/column
• n_row: Number of rows for that feature/column
• n_missing: Number of missing values/NAs for that feature/column

It uses an inbuilt function called edaPlots to display the above-mentioned four objects.

edaPlots(torus_df)

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 torus dataset 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 dataset.

str(torus_train)

## '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)

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 testing dataset.

str(torus_test)

## '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)

edaPlots(torus_test,output_type = "histogram")

edaPlots(torus_test, output_type = "boxplot")

edaPlots(torus_test, output_type = "correlation")

4. Map A : Base Compressed Map

Let us try to visualize the compressed Map A from the diagram below.

Figure 1: Data Segregation with highlighted bounding box in red around compressed map A

This package can perform vector quantization using the following algorithms -

• Hierarchical Vector Quantization using k−means
• Hierarchical Vector Quantization using k−medoids

For more information on vector quantization, refer the following link.

The trainHVT function constructs highly compressed hierarchical Voronoi tessellations. The raw data is first scaled and this scaled data is supplied as input to the vector quantization algorithm. The vector quantization algorithm compresses the dataset until a user-defined compression percentage rate is achieved using a parameter called quantization error which acts as a threshold and determines the compression percentage. It means that for a given user-defined compression percentage we get the ‘n’ number of cells, then all of these cells formed will have a quantization error less than the threshold quantization error.

Let’s try to comprehend the trainHVT first before moving ahead.

trainHVT(
  data,
  min_compression_perc,
  n_cells,
  depth,
  quant.err,
  normalize,
  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,
  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 an n dimensional point and 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_verbose - A logical value which indicates the t-SNE algorithm to print detailed information about its progress to the console.

• 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 map A which can be referred later in this section

Figure 2: 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.

As this is already done in HVT Vignette: please refer for more information.

Model Parameters

• Number of Cells at each Level = 500
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

set.seed(240)
torus_mapA <- 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"
)

Let’s check the compression summary for torus.

summary(torus_mapA)

We successfully compressed 90% of the data 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.

As per the manual, torus_mapA[[3]] gives us detailed information about the hierarchical vector quantized data. torus_mapA[[3]][['summary']] gives a nice tabular data containing no of points, Quantization Error and the codebook.

The datatable displayed below is the summary from torus_mapA showing Cell.ID, Centroids and Quantization Error for each of the 500 cells. For the sake of brevity, we are displaying only the first 20 rows.

displayTable(torus_mapA[[3]][['summary']])

Now let us understand what each column in the above table means:

• Segment.Level - Level 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.

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’.

Let’s plot the Voronoi tessellation for layer 1 (map A).

plotHVT(torus_mapA,plot.type = "2Dhvt") 

Figure 3: The Voronoi Tessellation for layer 1 (map A) shown for the 500 cells in the dataset ’torus’

4.1 Heatmaps

Now let’s plot the Voronoi Tessellation with the heatmap overlaid for all the features in the torus dataset 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 dataset, 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 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 torus dataset.

  plotHVT(torus_mapA,hmap.cols = "x",plot.type = '2Dheatmap') 

Figure 4: The Voronoi Tessellation with the heat map overlaid for variable ’x’ in the ’torus’ dataset

  plotHVT(torus_mapA,hmap.cols = "y",plot.type = '2Dheatmap') 

Figure 5: The Voronoi Tessellation with the heat map overlaid for variable ’y’ in the ’torus’ dataset

  plotHVT(torus_mapA, hmap.cols = "z",plot.type = '2Dheatmap') 

Figure 6: The Voronoi Tessellation with the heat map overlaid for variable ’z’ in the ’torus’ dataset

5. Map B : Compressed Novelty Map

Let us try to visualize the Map B from the diagram below.

Figure 7: Data Segregation with highlighted bounding box in red around map B

In this section, we will manually figure out the novelty cells from the plotted torus_mapA and store it in identified_Novelty_cells variable.

Note: For manual selecting the novelty cells from map A, one can enhance its interactivity by adding plotly elements to the code. This will transform map A into an interactive plot, allowing users to actively engage with the data. By hovering over the centroids of the cells, a tag containing segment child information will be displayed. Users can explore the map by hovering over different cells and selectively choose the novelty cells they wish to consider. Added an image for reference.

Figure 8: Manually selecting novelty cells

The removeNovelty function removes the identified novelty cell(s) from the training dataset (containing 9600 datapoints) and stores those records separately.

It takes input as the cell number (Segment.Child) of the manually identified novelty cell(s) and the compressed HVT map (torus_mapA) with 500 cells. It returns a list of two items: data with novelty, and data without novelty.

NOTE: As we are using torus dataset here, the identified novelty cells given are for demo purpose.

identified_Novelty_cells <<- c(273,44,61,486,185,425)   #as a example
output_list <- removeNovelty(identified_Novelty_cells, torus_mapA)
data_with_novelty <- output_list[[1]]
data_without_novelty <- output_list[[2]]

Let’s have a look at the data with novelty(containing 115 records).

novelty_data <- data_with_novelty
novelty_data$Row.No <- row.names(novelty_data)
novelty_data <- novelty_data %>% dplyr::select("Row.No","Cell.ID","Cell.Number","x","y","z")
colnames(novelty_data) <- c("Row.No","Cell.ID","Segment.Child","x","y","z")
displayTable(novelty_data, limit = 115)

5.1 Voronoi Tessellation with highlighted novelty cell

The plotNovelCells function is used to plot the Voronoi tessellation using the compressed HVT map (torus_mapA) containing 500 cells and highlights the identified novelty cell(s) i.e 6 cells (containing 115 records) in red on the map.

plotNovelCells(identified_Novelty_cells, torus_mapA,line.width = c(0.4),centroid.size = 0.01)

Figure 9: The Voronoi Tessellation constructed using the compressed HVT map (map A) with the novelty cell(s) highlighted in red

We pass the dataframe with novelty records (115 records) to trainHVT function along with other model parameters mentioned below to generate map B (layer2)

Model Parameters

• Number of Cells at each Level = 11
• Maximum Depth = 1
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

colnames(data_with_novelty) <- c("Cell.ID","Segment.Child","x","y","z")
data_with_novelty <- data_with_novelty[,-1:-2]
mapA_scale_summary = torus_mapA[[3]]$scale_summary
torus_mapB <- trainHVT(data_with_novelty,
                  n_cells = 11,   
                  depth = 1,
                  quant.err = 0.1,
                  normalize = FALSE,
                  distance_metric = "L2_Norm",
                  error_metric = "max",
                  quant_method = "kmeans",
                  dim_reduction_method = "sammon")

summary(torus_mapB)

segmentLevel	noOfCells	noOfCellsBelowQuantizationError	percentOfCellsBelowQuantizationErrorThreshold	parameters
1	11	10	0.91	n_cells: 11 quant.err: 0.1 distance_metric: L2_Norm error_metric: max quant_method: kmeans

As it can be seen from the table above, 91% of the cells have hit the quantization threshold error. Since we are successfully able to attain the desired compression percentage, so we will not further subdivide the cells

The datatable displayed below is the summary from map B (layer 2) showing Cell.ID, Centroids and Quantization Error for each of the 11 cells.

displayTable(torus_mapB[[3]][['summary']])

Segment.Level	Segment.Parent	Segment.Child	n	Cell.ID	Quant.Error	x	y	z
1	1	1	6	6	0.0497	-0.0341	-2.9882	0.1270
1	1	2	7	2	0.0672	-0.9392	-2.8448	-0.0046
1	1	3	9	10	0.0970	0.4600	2.9390	0.1984
1	1	4	7	11	0.0621	0.4633	2.9571	-0.0488
1	1	5	15	8	0.0820	2.8993	-0.6751	0.1789
1	1	6	21	9	0.1010	-2.8324	0.9469	-0.0663
1	1	7	11	5	0.0514	-0.3795	-2.9641	0.1212
1	1	8	16	7	0.0831	2.8101	-1.0120	0.0205
1	1	9	8	4	0.0730	-0.2520	-2.9278	0.3358
1	1	10	9	1	0.0481	-0.9761	-2.8015	0.2422
1	1	11	6	3	0.0622	-0.7308	-2.8890	0.1484

6. Map C : Compressed Map without Novelty

Let us try to visualize the compressed Map C from the diagram below.

Figure 10:Data Segregation with highlighted bounding box in red around compressed map C

torus_mapC <- trainHVT(dataset  = data_without_novelty,
                  n_cells = 10,
                  depth = 2,
                  quant.err = 0.1,
                  normalize = FALSE,
                  distance_metric = "L2_Norm",
                  error_metric = "max",
                  quant_method = "kmeans",
                  dim_reduction_method = "sammon")

summary(torus_mapC)

6.2 Iteration 2

Since, we are yet to achive atleast 80% compression at depth 2. Let’s try to compress again using the below mentioned set of model parameters and the data without novelty (containing 9485 records).

Model Parameters

• Number of Cells at Level 1 = 46
• Number of Cells at Level 2 = 2116 (46 x 46)
• Maximum Depth = 2
• Quantization Error Threshold = 0.1
• Error Metric = Max
• Distance Metric = Euclidean
• Dimensionality Reduction method = Sammon

torus_mapC <- trainHVT(data_without_novelty,
                  n_cells = 46,    
                  depth = 2,
                  quant.err = 0.1,
                  normalize = FALSE,
                  distance_metric = "L2_Norm",
                  error_metric = "max",
                  quant_method = "kmeans",
                  dim_reduction_method = "sammon")

summary(torus_mapC)

segmentLevel	noOfCells	noOfCellsBelowQuantizationError	percentOfCellsBelowQuantizationErrorThreshold	parameters
1	46	0	0	n_cells: 46 quant.err: 0.1 distance_metric: L2_Norm error_metric: max quant_method: kmeans
2	2116	1748	0.83	n_cells: 46 quant.err: 0.1 distance_metric: L2_Norm error_metric: max quant_method: kmeans

As it can be seen from the table above, 0% of the cells have hit the quantization threshold error in level 1 and 83% of the cells have hit the quantization threshold error in level 2.

The datatable displayed below is the summary from map C (layer2). showing Cell.ID, Centroids and Quantization Error.

displayTable(data =torus_mapC[[3]][['summary']])

Segment.Level	Segment.Parent	Segment.Child	n	Cell.ID	Quant.Error	x	y	z
1	1	1	183	567	0.3054	-1.5739	2.3989	-0.0019
1	1	2	236	355	0.3085	-1.5176	-1.2760	-0.9229
1	1	3	162	88	0.2925	-1.7876	-2.2656	0.0079
1	1	4	167	1865	0.2886	2.5078	-1.4110	-0.1993
1	1	5	183	874	0.3030	0.4550	-2.6700	-0.5138
1	1	6	251	1120	0.2282	-0.1585	1.0003	-0.0305
1	1	7	194	1576	0.2510	1.3877	-0.0061	0.7561
1	1	8	196	1208	0.3194	-0.4306	2.5131	-0.7020
1	1	9	189	2042	0.2972	1.7211	2.2262	0.3548
1	1	10	273	609	0.2847	-1.1913	-0.1942	0.6043
1	1	11	248	1320	0.2812	0.2437	1.4647	0.8136
1	1	12	257	1537	0.2358	1.2573	0.0921	-0.6336
1	1	13	187	602	0.3037	-0.1334	-2.4336	0.7936
1	1	14	207	331	0.3187	-2.2996	1.3756	-0.5613
1	1	15	154	2118	0.2917	2.6593	1.1769	0.0397
1	1	16	288	1465	0.2804	0.5899	1.2696	-0.7664
1	1	17	148	2003	0.2886	2.7567	-0.1572	0.4931
1	1	18	269	886	0.2929	-0.9237	1.3992	-0.8903
1	1	19	170	153	0.3206	-2.5259	-0.5698	-0.7073
1	1	20	243	1251	0.2330	0.8259	-0.6708	0.3379

Let’s plot the Voronoi tessellation for layer 2 (map C)

plotHVT(torus_mapC,
        line.width = c(0.2,0.1), 
        color.vec = c("navyblue","steelblue"),
        centroid.size = 0.1,
        child.level = 2, 
        plot.type = '2Dhvt')

Figure 11: The Voronoi Tessellation for layer 2 (map C) shown for the 928 cells in the dataset ’torus’ at level 2

6.3 Heatmaps

Now let’s plot all the features for each cell at level two as a heatmap for better visualization.

The heatmaps displayed below provides a visual representation of the spatial characteristics of the torus dataset, 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 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 torus dataset.

  plotHVT(
  torus_mapC,
  child.level = 2,
  hmap.cols = "x",
  line.width = c(0.2,0.1),
  color.vec = c("navyblue","steelblue"),
  centroid.size = 0.1,
  plot.type = '2Dheatmap') 

Figure 12: The Voronoi Tessellation with the heat map overlaid for feature x in the ’torus’ dataset

  plotHVT(
  torus_mapC,
  child.level = 2,
  hmap.cols = "y",
  line.width = c(0.2,0.1),
  color.vec = c("navyblue","steelblue"),
  centroid.size = 0.1,
  plot.type = '2Dheatmap') 

Figure 13: The Voronoi Tessellation with the heat map overlaid for feature y in the ’torus’ dataset

  plotHVT(
  torus_mapC,
  child.level = 2,
  hmap.cols = "z",
  line.width = c(0.2,0.1),
  color.vec = c("navyblue","steelblue"),
  centroid.size = 0.1,
  plot.type = '2Dheatmap') 

Figure 14: The Voronoi Tessellation with the heat map overlaid for feature z in the ’torus’ dataset

We now have the set of maps (map A, map B & map C) which will be used to score, which map and cell each test record is assigned to.

7. Scoring

Now once we have built the model, let us try to score using our testing dataset (containing 2400 data points) which cell and which layer each point belongs to.

The scoreLayeredHVT function is used to score the testing dataset using the scored set of maps. This function takes an input - a testing dataset and a set of maps (map A, map B, map C).

Now, Let us understand the scoreLayeredHVT function.

scoreLayeredHVT(data,
                hvt_mapA,
                hvt_mapB,
                hvt_mapC,
                child.level = 1,
                mad.threshold = 0.2,
                normalize = TRUE,
                distance_metric="L1_Norm",
                error_metric="max",
                yVar)

Each of the parameters of scoreLayeredHVT function has been explained below:

Before that, the approach of scoreLayeredHVT function is to use scoreHVT function to score the test data against the given results of trainHVT which is referred as ‘map’ here. Hence the scoreLayeredHVT scores the test dataset against map A, B & C and further process and merge the final output. So the arguments used in scoreHVT is important here for smooth execution of function.

• data - A dataframe containing the test dataset. The dataframe should have all the variable(features) used for training.

• hvt_mapA - Result obtained from trainHVT function while performing hierarchical vector quantization on train data. This list containes information about the hierarchical vector quantized data along with a summary section.

• hvt_mapB - Result obtained from trainHVT function while performing hierarchical vector quantization on data with novelty data.It is a subset of the training data obtained as a result of removeNovelty function (1st element).

• hvt_mapC - Result obtained from trainHVT function while performing hierarchical vector quantization on data without novelty. It is a subset of the training data obtained as a result of removeNovelty function (2nd element).

• 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.

• 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)

When normalize is set to TRUE, the scoreHVT 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.

• Steps involved in Normalizing the data:
• From the trainHVT results (here it is torus_mapA, torus_mapB & torus_mapC) the summary is accessed which is the third list object.
• From the summary list, the scale.summary object is taken which have two entries that stores mean_data and std_data of all the columns in training dataset.
• Those two entries are taken for the center and scale parameter in scale() which normalizes the testing dataset similar to training dataset in scoreHVT()
• Here in scoreLayeredHVT function the testing dataset is scored against all the maps (A, B & C) by using scoreHVT function and the results are merged and further processed.
• This approach ensures that the model that is evaluated on testing dataset scaled in the same way as the training dataset, maintaining consistency and improving the model’s ability to generalize to new, unseen data.

The function score based on the HVT maps - map A, map B and map C, constructed using trainHVT function. For each test record, the function will assign that record to Layer1 or Layer2. Layer1 contains the cell ids from map A and Layer 2 contains cell ids from map B (novelty map) and map C (map without novelty).

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 test dataset:

1. Calculate the distance between the point and the centroid of all the cells in the first level.
2. Find the cell whose centroid has minimum distance to the point.
3. Check if the cell drills down further to form more cells.
4. If it doesn’t, return the path. Or else repeat steps 1 to 4 till we reach a level at which the cell doesn’t drill down further.

Note : The Scoring algorithm will not work if some of the variables used to perform quantization are missing. In the testing dataset, we should not remove any features.

validation_data <- torus_test
new_score <- scoreLayeredHVT(
    data=validation_data,
    hvt_mapA = torus_mapA,
    hvt_mapB = torus_mapB,
    hvt_mapC = torus_mapC,
    normalize = FALSE )

Let’s see which cell and layer each point belongs to and check the Mean Absolute Difference for each of the 2400 records.

summary(new_score)

hist(new_score[["actual_predictedTable"]]$diff, 
     breaks = 30, col = "blue", main = "Mean Absolute Difference",
     xlab = "Difference")

Figure 16: Mean Absolute Difference

8. Executive Summary

• We have considered torus dataset for creating a scored sequence of maps using scoreLayeredHVT() in this vignette.

• Our goal is to achieve data compression upto atleast 80%.

• We construct a compressed HVT map (torus_mapA) using the trainHVT() on the training dataset by setting n_cells to 500 and quant.error to 0.1 and we were able to attain a compression of 90%.

• Based on the output of the above step, we manually identify the novelty cell(s) from the plotted map A. For this dataset, we identify the 6 cells as the novelty cells. (since torus dataset does not have outliers we are using this for demo purpose.)

• We pass the identified novelty cell(s) as a parameter to the removeNovelty() along with HVT torus_mapA. The function removes that novelty cell(s) from the dataset and stores them separately. It also returns the data without novelty(s).

• The plotNovelCells() constructs hierarchical voronoi tessellations and highlights the identified novelty cell(s) in red.

• The data with novelty is then passed to the trainHVT() to construct another HVT map (torus_mapB). But here, we set the parameters n_cells = 10, depth = 2 etc. when constructing the map.

• The data without novelty is then passed to the trainHVT() to construct another HVT map (torus_mapC). But here, we set the parameters n_cells = 46, depth = 2 etc. when constructing the map.

• Finally, the set of maps - torus_mapA,torus_mapB,torus_mapC are passed to the scoreLayeredHVT() along with the test dataset to score which map and what cell each test record is assigned to.

• The output of scoreLayeredHVT is a dataset with two columns Layer1.Cell.ID and Layer2.Cell.ID. Layer1.Cell.ID contains cell ids from map A in the form A1,A2,A3…. and Layer2.Cell.ID contains cell ids from map B as B1,B2… depending on the identified novelties and map C as C1,C2,C3…..

9. References

1. Topology Preserving Maps

2. Vector Quantization

3. K-means

4. Sammon’s Projection

5. Voronoi Tessellations