Handbook of Research on Machine Learning Applications and Trends

Alexander N. Gorban, Andreï Zinovyev, Marcelino Martinez-Sober, Jose Rafael Magdalena-Benedito, Antonio José Serrano LópezIGI 2010 · DOI · arXiv · OpenAlex

Abstract

In many physical, statistical, biological and other investigations it is desirable to approximate a system of points by objects of lower dimension and/or complexity. For this purpose, Karl Pearson invented principal component analysis in 1901 and found 'lines and planes of closest fit to system of points'. The famous k-means algorithm solves the approximation problem too, but by finite sets instead of lines and planes. This chapter gives a brief practical introduction into the methods of construction of general principal objects, i.e. objects embedded in the 'middle' of the multidimensional data set. As a basis, the unifying framework of mean squared distance approximation of finite datasets is selected. Principal graphs and manifolds are constructed as generalisations of principal components and k-means principal points. For this purpose, the family of expectation/maximization algorithms with nearest generalisations is presented. Construction of principal graphs with controlled complexity is based on the graph grammar approach.

Introduction

Modern scientific inquiry frequently produces datasets of immense dimensionality, ranging from gene expression profiles to linguistic frequency vectors. While the human cognitive system is optimized for three-dimensional spatial reasoning, these high-dimensional "point clouds" often contain critical structural information that is obscured by their complexity. Traditional dimensionality reduction techniques, such as Principal Component Analysis (PCA) and k-means clustering, offer limited solutions: PCA is restricted to linear subspaces, while k-means produces disconnected point sets that fail to capture the underlying topological continuity or branching nature of the data.

This research introduces a unifying framework for "Principal Objects"—non-linear manifolds and branched graphs that serve as a "skeleton" for complex data. By positioning these objects in the "middle" of the data distribution, researchers can extract intuitive, low-dimensional representations that preserve essential structural features.

Methodology: The Framework of Principal Objects

The core of the proposed approach is the Mean Squared Distance (MSD) approximation. The objective is to find a low-complexity object that minimizes the average squared distance from the data points to their nearest projections on the object.

The Expectation-Maximization (EM) Engine

The construction of these objects relies on a generalized EM algorithm. This iterative process alternates between two steps:

  1. Expectation (Projection): Each data point is associated with its closest point on the current principal object.
  2. Maximization (Optimization): The object’s parameters are adjusted to minimize the MSD, effectively pulling the object toward the local density of the data.

Elastic Maps and Physical Regularization

To ensure that the resulting manifolds are smooth and interpretable, the authors incorporate physical metaphors of elasticity. By treating manifolds as elastic membranes, the algorithm minimizes a functional that balances approximation error with "elastic energy"—penalties for stretching and bending. This regularization provides a robust alternative to traditional statistical smoothing, allowing for faster convergence and more intuitive control over the manifold's stiffness.

Graph Grammars and Advanced Modeling

For datasets with branching structures, the authors employ Graph Grammars. This method uses a formal set of rules—such as adding a node or bisecting an edge—to dynamically grow "Principal Graphs." This allows the model to adapt its topology to the data's branching patterns while maintaining strict control over structural complexity. Furthermore, the framework utilizes Pluriharmonic Graphs to generalize "straightness" for branched structures and Principal Cubic Complexes to handle high-dimensional internal structures without falling victim to the exponential "curse of dimensionality."

Applications and Empirical Validation

The framework's versatility is demonstrated across several distinct domains:

  • Genomics: In 64-dimensional space representing bacterial genome triplet frequencies, the "metro map" visualization successfully isolated seven distinct clusters corresponding to coding frameshifts. These clusters were inseparable using standard linear projections.
  • Oncology: Applied to breast cancer microarray data, 2D non-linear elastic maps achieved superior separation of the "basal" subtype compared to PCA. The results indicated that a 2D non-linear map could capture structural information equivalent to a 4D linear model.
  • Structural Biology: The 1D principal curve algorithm was able to autonomously reconstruct the helical backbone of a DNA molecule from a point cloud of its Van-der-Waals surface.

Key Insights and Discussion

A key insight of this work is the concept of self-consistency: a principal object is considered optimal when every point on it represents the average of the data points projecting onto it. This property ensures that the "metro map" metaphor holds—providing a schematic yet faithful representation of data flow and cluster relationships.

However, challenges remain. The EM-based optimization is susceptible to local minima. While "softening strategies" (gradually reducing elasticity) can mitigate this, they do not guarantee global optimality. Furthermore, the selection of elasticity parameters and the computational cost of high-dimensional internal structures remain areas for future refinement.

Conclusion

By bridging the gap between linear PCA and unstructured clustering, the framework of Principal Objects provides a powerful toolkit for data visualization and structural analysis. The combination of physical regularization and evolutionary graph grammars enables the discovery of complex, non-linear patterns that define the next frontier of high-dimensional data science.

Summary updated

Abstract

In many physical, statistical, biological and other investigations it is desirable to approximate a system of points by objects of lower dimension and/or complexity. For this purpose, Karl Pearson invented principal component analysis in 1901 and found 'lines and planes of closest fit to system of points'. The famous k-means algorithm solves the approximation problem too, but by finite sets instead of lines and planes. This chapter gives a brief practical introduction into the methods of construction of general principal objects, i.e. objects embedded in the 'middle' of the multidimensional data set. As a basis, the unifying framework of mean squared distance approximation of finite datasets is selected. Principal graphs and manifolds are constructed as generalisations of principal components and k-means principal points. For this purpose, the family of expectation/maximisation algorithms with nearest generalisations is presented. Construction of principal graphs with controlled complexity is based on the graph grammar approach.
BibTeX
@inproceedings{gorban2010handbook,
  author = {Alexander N. Gorban and Andreï Zinovyev and Marcelino Martinez-Sober and Jose Rafael Magdalena-Benedito and Antonio José Serrano López},
  title = {{Handbook of Research on Machine Learning Applications and Trends}},
  booktitle = {IGI},
  year = {2010},
  doi = {10.4018/978-1-60566-766-9},
}
Figure