High Dimensional Pattern Recognition using Diffusion Maps and Earth Mover's Distance
Linh H. Lieu, Naoki Saito · 2009
We propose a new method for matching, comparing, and discriminating datasets con-sisting of high-dimensional data (e.g., signals and images). Our approach first performs dimension reduction and feature extraction of training datasets using the diffusion maps developed by Coifman and Lafon [1, 2]. This leads to a compact representation of the given classes in the so-called “diffusion space ” whose dimension is much lower than the original ambient space. In fact, each class in the diffusion space is represented as a set of cluster centroids called “signatures”. Dimension reduction via diffusion maps offers the advantage of preserving the underlying geometry in the data. To classify an unlabeled test dataset, we extend (or embed) that dataset into the diffusion space con-structed during the training stage, construct its signature, and then measure the “close-ness ” or similarity between the test signature and the class signatures using the Earth Mover’s Distance (EMD) [3, 4], which is more robust than other measures. Finally, we will demonstrate the usefulness of our method using two practical real applications and compare the performance of the dimension reduction capability of our method with that of the standard Principal Component Analysis.