Nonlinear Dimensionality Reduction Techniques: A Data Structure Preservation Approach

Foreword
Preface
Acknowledgements
Funding
Contents
Acronyms
Nomenclature
	Metric Data
	Dimensionality Reduction
	Neighbourhood Characterization
	Class-Information
List of Figures
List of Tables
1 Data Science Context
	1.1 Data in a Metric Space
		1.1.1 Measuring Dissimilarities and Similarities
		1.1.2 Neighbourhood Ranks
		1.1.3 Embedding Space Notations
		1.1.4 Multidimensional Data
		1.1.5 Sequence Data
		1.1.6 Network Data
		1.1.7 A Few Multidimensional Datasets
			1.1.7.1 Geometric Datasets
			1.1.7.2 Real Datasets
	1.2 Automated Tasks
		1.2.1 Underlying Distribution
		1.2.2 Category Identification
			1.2.2.1 Clusters and Flat Clustering
			1.2.2.2 Outliers and Outlier Detection
			1.2.2.3 Hierarchies and Hierarchical Clustering
		1.2.3 Data Manifold Analysis
			1.2.3.1 Latent Variables Extraction and Manifold Learning
			1.2.3.2 Continua and Topology Learning
		1.2.4 Model Learning
			1.2.4.1 Classification
		1.2.5 Regression
	1.3 Visual Exploration and Visual Encoding
		1.3.1 Human in the Loop Using Graphic Variables
		1.3.2 Spatialization and Gestalt Principles
		1.3.3 Scatter Plots
			1.3.3.1 2D and Interactive 3D Scatter Plots
			1.3.3.2 Circular Background and Procrustes Transform
			1.3.3.3 Glyphs
			1.3.3.4 Scatter Plot Matrices (SPLOM)
			1.3.3.5 Grand Tour
		1.3.4 Parallel Coordinates
		1.3.5 Colour Coding
			1.3.5.1 Colour Models
			1.3.5.2 Taxonomy of Colour Maps
		1.3.6 Multiple Coordinated Views and Visual Interaction
		1.3.7 Graph Drawing
	1.4 Intermediate Conclusions
2 Intrinsic Dimensionality
	2.1 Curse of Dimensionality
		2.1.1 Data Sparsity
		2.1.2 Norm Concentration
	2.2 Estimating Intrinsic Dimensionality
		2.2.1 Covariance-Based Approaches
			2.2.1.1 Scree Plot
			2.2.1.2 Local Covariance Dimension
		2.2.2 Fractal Approaches
			2.2.2.1 Correlation Dimension
			2.2.2.2 Nearest Neighbours Dimension
		2.2.3 Towards Local Estimation
			2.2.3.1 Hidalgo
			2.2.3.2 Hill Estimator
	2.3 Two-Nearest Neigbhours Intrinsic Dimensionality LocalEstimator
		2.3.1 Gaussian Mixture Modelling
		2.3.2 Test of TIDLE on a Two Clusters Case
		2.3.3 TIDLE Perspectives
3 Map Evaluation
	3.1 Objective and Practical Indicators
		3.1.1 Subjectivity of Indicators
		3.1.2 User Studies on Specific Tasks
	3.2 Unsupervised Global Evaluation
		3.2.1 Types of Distortions
			3.2.1.1 Distance Distortions
			3.2.1.2 Rank Distortions
		3.2.2 Link Between Distortions and Mapping Continuity
		3.2.3 Reasons of Distortions Ubiquity
		3.2.4 Scalar Indicators
			3.2.4.1 Distance-Based Indicators
			3.2.4.2 Rank-Based Indicators
		3.2.5 Aggregation
			3.2.5.1 Indicators Aggregation
			3.2.5.2 Scale Aggregation
		3.2.6 Diagrams
			3.2.6.1 Shepard Diagram
			3.2.6.2 Co-Ranking Matrix
	3.3 Class-Aware Indicators
		3.3.1 Class Separation and Aggregation
			3.3.1.1 Class Separation
			3.3.1.2 Classification Accuracy in the Map
			3.3.1.3 Confusion Matrix
			3.3.1.4 Class Aggregation
		3.3.2 Comparing Scores Between the Two Spaces
		3.3.3 Class Cohesion and Distinction
		3.3.4 The Case of One Cluster per Class
		3.3.5 Intermediate Conclusions
4 Map Interpretation
	4.1 Axes Recovery
		4.1.1 Linear Case: Biplots
		4.1.2 Non-Linear Case
	4.2 Local Evaluation
		4.2.1 Point-Wise Aggregation
			4.2.1.1 Point Markers
			4.2.1.2 Background Colouring
		4.2.2 One to Many Relations with Focus Point
		4.2.3 Many to Many Relations
			4.2.3.1 Matrix View
			4.2.3.2 Graph Display
	4.3 Map Interpretation Using Neighbourhood Graphs
		4.3.1 Uniform Formulation of Rank-Based Indicators
		4.3.2 MING Graphs
		4.3.3 MING Analysis for a Toy Dataset
		4.3.4 Impact of MING Parameters
			4.3.4.1 Digits Interpretation
			4.3.4.2 Impact of the Scale
			4.3.4.3 Impact of the Distortion Measure
		4.3.5 Visual Clutter
			4.3.5.1 Interactive Edge Filtering
			4.3.5.2 Edge Bundling
		4.3.6 Oil Flow
		4.3.7 COIL-20 Dataset
		4.3.8 MING Perspectives
5 Stress Functions for Unsupervised Dimensionality Reduction
	5.1 Spectral Projections
		5.1.1 Principal Component Analysis
			5.1.1.1 Variance Interpretation
			5.1.1.2 Reconstruction Error
			5.1.1.3 Latent Variable Model
		5.1.2 Classical MultiDimensional Scaling
			5.1.2.1 Limitations of Linear Methods
		5.1.3 Kernel Methods: Isompap, KPCA, LE
			5.1.3.1 Kernel PCA
			5.1.3.2 Isomap
			5.1.3.3 Laplacian Eigenmap
			5.1.3.4 Locally Linear Embedding
	5.2 Non-Linear MultiDimensional Scaling
		5.2.1 Metric MultiDimensional Scaling
			5.2.1.1 Sammon Non-Linear Mapping and Curvilinear Component Analysis
			5.2.1.2 Local MultiDimensional Scaling
			5.2.1.3 Data-Driven High Dimensional Scaling
		5.2.2 Non-Metric MultiDimensional Scaling
			5.2.2.1 RankVisu
	5.3 Neighbourhood Embedding Methods
		5.3.1 General Principle: SNE
		5.3.2 Scale Setting
		5.3.3 Divergence Choice: NeRV and JSE
		5.3.4 Symmetrization
		5.3.5 Solving the Crowding Problem: tSNE
		5.3.6 Kernel Choice
		5.3.7 Adaptive Student Kernel Imbedding
	5.4 Graph Layout
		5.4.1 Force Directed Graph Layout: Elastic Embedding
		5.4.2 Probabilistic Graph Layout: LargeVis
		5.4.3 Topological Method UMAP
	5.5 Artificial Neural Networks
		5.5.1 Auto-Encoders
		5.5.2 IVIS
		5.5.3 Intermediate Conclusions
6 Stress Functions for Supervised Dimensionality Reduction
	6.1 Types of Supervision
		6.1.1 Full Supervision
		6.1.2 Weak Supervision
		6.1.3 Semi-Supervision
	6.2 Parametric with Class Purity
		6.2.1 Linear Discriminant Analysis
		6.2.2 Neighbourhood Component Analysis
	6.3 Metric Learning
		6.3.1 Mahalanobis Distances
		6.3.2 Riemannian Metric
		6.3.3 Direct Distances Transformation
			6.3.3.1 Additive Transformation
			6.3.3.2 Multiplicative Transformation
			6.3.3.3 Concave vs Convex Transformations
		6.3.4 Similarities Learning
		6.3.5 Metric Learning Limitations
	6.4 Class Adaptive Scale
	6.5 Class-Guiding Principle: Classimap
	6.6 Class-Guided Neighbourhood Embedding
		6.6.1 ClassNeRV Stress
		6.6.2 Flexibility of the Supervision
		6.6.3 Ablation Study
			6.6.3.1 Comparison with Other Dimensionality Reduction Methods
		6.6.4 Isolet 5 Case Study
		6.6.5 Robustness to Class Misinformation
		6.6.6 Extension to the Type 2 Mixture: ClassJSE
		6.6.7 Extension to Semi-Supervision and Weak-Supervision
		6.6.8 Extension to Soft Labels
		6.6.9 Intermediate Conclusions
7 Optimization, Acceleration and Out of Sample Extensions
	7.1 Optimization
		7.1.1 Global and Local Optima
		7.1.2 Gradient Descent and Quasi-Newton Methods
		7.1.3 Initialization
		7.1.4 Multi-Scale Optimization
		7.1.5 Force-Directed Placement Interpretation
			7.1.5.1 Elastic and Plastic Behaviours
			7.1.5.2 Stochastic Gradient Descent
			7.1.5.3 Attractive-Repulsive Decomposition
			7.1.5.4 Blockade Effect
			7.1.5.5 Auxiliary Dimensions
	7.2 Acceleration Strategies
		7.2.1 Attractive Forces Approximation
		7.2.2 Binary Search Trees
		7.2.3 Repulsive Forces
			7.2.3.1 Forces Sampling
			7.2.3.2 Forces Aggregation
		7.2.4 Landmarks Approximation
	7.3 Out of Sample Extension
		7.3.1 Applications
			7.3.1.1 Mapping Acceleration
			7.3.1.2 Mapping Interaction
			7.3.1.3 Incremental Positioning: Data Streams
			7.3.1.4 Classification in the Map
		7.3.2 Parametric Case: Model-Constrained Mapping
			7.3.2.1 Spectral Projection Methods
		7.3.3 Non-parametric Stress with Neural Network Model
		7.3.4 Non-parametric Case
			7.3.4.1 Local Linear Transformations: LAMP
			7.3.4.2 Manifold Reconstruction
			7.3.4.3 Radial Basis Functions Interpolation
		7.3.5 Intermediate Conclusions
8 Applications of Dimensionality Reduction to the Diagnosis of Energy Systems
	8.1 Smart Buildings Commissioning
		8.1.1 System and Rules
		8.1.2 Mapping
	8.2 Photovoltaics
		8.2.1 I–V Curves
		8.2.2 Comparing Normalized I–V Curves
		8.2.3 Colour Description of the Chemical Compositions
	8.3 Batteries
		8.3.1 Case 1
		8.3.2 Case 2
9 Conclusions
A Some Technical Results
	A.1 Equivalence Between Triangle Inequality and Convexity of Balls for a Pseudo-Norm
	A.2 From Pareto to Exponential Distribution
	A.3 Spiral and Swiss roll
B Kullback–Leibler Divergence
	B.1 Generalized Kullback–Leibler Divergence
		B.1.1 Perplexity with Hard Neighbourhoods
	B.2 Link Between Soft and Hard Recall and Precision
C Details of Calculations
	C.1 General Gradient of Stress Function
	C.2 Neighbourhood Embedding
		C.2.1 Supervised Neighbourhood Embedding (Asymmetric Case)
		C.2.2 Mixtures
			C.2.2.1 Type 1
			C.2.2.2 Type 2
			C.2.2.3 Asymptotic Behaviour
		C.2.3 Membership Degrees
		C.2.4 Soft-Min Arguments
			C.2.4.1 Gaussian Kernel
			C.2.4.2 Student Kernel
			C.2.4.3 Asymptotic Behaviour
		C.2.5 Scale Setting by Perplexity
		C.2.6 Force Interpretation
D Spectral Projections Algebra
	D.1 PCA as Matrix Factorization and SVD Resolution
	D.2 Link with Linear Projection
	D.3 Sparse Expression
	D.4 PCA and Centering: From Affine to Linear
	D.5 Link with Covariance and Gram Matrices
	D.6 From Distances to Gram Matrix
		D.6.1 Probabilistic Interpretation and Maximum Likelihood
	D.7 Nyström Approximation
Conflict of Interest Statement
Disclaimer Statement
References
Index