A visualization metric for dimensionality reduction

Data visualization of high-dimensional data is possible through the use of dimensionality reduction techniques. However, in deciding which dimensionality reduction techniques to use in practice, quantitative metrics are necessary for evaluating the results of the transformation and visualization of the lower dimensional embedding. In this paper, we propose a manifold visualization metric based on the pairwise correlation of the geodesic distance in a data manifold. This metric is compared with other metrics based on the Euclidean distance, Mahalanobis distance, City Block metric, Minkowski metric, cosine distance, Chebychev distance, and Spearman distance. The results of applying different dimensionality reduction techniques on various types of nonlinear manifolds are compared and discussed. Our experiments show that our proposed metric is suitable for quantitatively evaluating the results of the dimensionality reduction techniques if the data lies on an open planar nonlinear manifold. This has practical significance in the implementation of knowledge-based visualization systems and the application of knowledge-based dimensionality reduction methods.     

Nonlinear Dimensionality Reduction and Data Visualization： A Review

Dimensionality reduction and data visualization are useful and important processes in pattern recognition.Many techniques have been developed in the recent years.The self-organizing map (SOM) can be an efficient method for this purpose.This paper reviews recent advances in this area and related approaches such as multidimensional scaling (MDS),nonlinear PCA,principal manifolds,as well as the connections of the SOM and its recent variant,the visualization induced SOM (ViSOM),with these approaches. The SOM is shown to produce a quantized,qualitative scaling and while the ViSOM a quantitative or metric scaling and approximates principal curve/surface.The SOM can also be regarded as a generalized MDS to relate two metric spaces by forming a topological mapping between them.The relationships among various recently proposed techniques such as ViSOM,Isomap,LLE,and eigenmap are discussed and compared.     

Supervised nonlinear dimensionality reduction for visualization and classification.

When performing visualization and classification, people often confront the problem of dimensionality reduction. Isomap is one of the most promising nonlinear dimensionality reduction techniques. However, when Isomap is applied to real-world data, it shows some limitations, such as being sensitive to noise. In this paper, an improved version of Isomap, namely S-Isomap, is proposed. S-Isomap utilizes class information to guide the procedure of nonlinear dimensionality reduction. Such a kind of procedure is called supervised nonlinear dimensionality reduction. In S-Isomap, the neighborhood graph of the input data is constructed according to a certain kind of dissimilarity between data points, which is specially designed to integrate the class information. The dissimilarity has several good properties which help to discover the true neighborhood of the data and, thus, makes S-Isomap a robust technique for both visualization and classification, especially for real-world problems. In the visualization experiments, S-Isomap is compared with Isomap, LLE, and WeightedIso. The results show that S-Isomap performs the best. In the classification experiments, S-Isomap is used as a preprocess of classification and compared with Isomap, WeightedIso, as well as some other well-established classification methods, including the K-nearest neighbor classifier, BP neural network, J4.8 decision tree, and SVM. The results reveal that S-Isomap excels compared to Isomap and WeightedIso in classification, and it is highly competitive with those well-known classification methods.     

非线性降维算法及其在医院绩效考核上的应用

流形学习算法中的等距嵌入算法（ISOMAP）具有对离群点敏感的瑕疵,针对此问题,提出利用基于共享近邻的距离度量方式,并充分利用了流形上对象的局部密度信息,有效改善了算法的性能,提高了算法的健壮性。同时,首次尝试将该改进的流形学习算法应用于医院绩效考核。人工数据与真实数据上的实验表明,改进的算法健壮且有效,在绩效考核上应用成功。     

改进的非线性数据降维方法及其应用

局部线性嵌入算法（Locally Linear Embedding,LLE）是基于流形学习的非线性降维方法之一。LLE利用样本点的近邻点的线性组合对每个样本点进行局部重构,而不同近邻个数的选取会产生不同的重构误差,从而影响整体算法的实施。提出了一种LLE的改进算法,算法有效地降低了近邻点个数对算法的影响,并很好地学习了高维数据的流形结构。所提方法的有效性在人造和真实数据的对比实验中得到了证实。     

A scalable supervised algorithm for dimensionality reduction on streaming data

Algorithms on streaming data have attracted increasing attention in the past decade. Among them, dimensionality reduction algorithms are greatly interesting due to the desirability of real tasks. Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are two of the most widely used dimensionality reduction approaches. However, PCA is not optimal for general classification problems because it is unsupervised and ignores valuable label information for classification. On the other hand, the performance of LDA is degraded when encountering limited available low-dimensional spaces and singularity problem. Recently, Maximum Margin Criterion (MMC) was proposed to overcome the shortcomings of PCA and LDA. Nevertheless, the original MMC algorithm could not satisfy the streaming data model to handle large-scale high-dimensional data set. Thus an effective, efficient and scalable approach is needed. In this paper, we propose a supervised incremental dimensionality reduction algorithm and its extension to infer adaptive low-dimensional spaces by optimizing the maximum margin criterion. Experimental results on a synthetic dataset and real datasets demonstrate the superior performance of our proposed algorithm on streaming data.     

Sentiment visualization and classification via semi-supervised nonlinear dimensionality reduction

Sentiment analysis, which detects the subjectivity or polarity of documents, is one of the fundamental tasks in text data analytics. Recently, the number of documents available online and offline is increasing dramatically, and preprocessed text data have more features. This development makes analysis more complex to be analyzed effectively. This paper proposes a novel semi-supervised Laplacian eigenmap (SS-LE). The SS-LE removes redundant features effectively by decreasing detection errors of sentiments. Moreover, it enables visualization of documents in perceptible low dimensional embedded space to provide a useful tool for text analytics. The proposed method is evaluated using multi-domain review data set in sentiment visualization and classification by comparing other dimensionality reduction methods. SS-LE provides a better similarity measure in the visualization result by separating positive and negative documents properly. Sentiment classification models trained over reduced data by SS-LE show higher accuracy. Overall, experimental results suggest that SS-LE has the potential to be used to visualize documents for the ease of analysis and to train a predictive model in sentiment analysis. SS-LE can also be applied to any other partially annotated text data sets.     

Perceptual relativity-based semi-supervised dimensionality reduction algorithm

As we all know, a well-designed graph tends to result in good performance for graph-based semi-supervised learning. Although most graph-based semi-supervised dimensionality reduction approaches perform very well on clean data sets, they usually cannot construct a faithful graph which plays an important role in getting a good performance, when performing on the high dimensional, sparse or noisy data. So this will generally lead to a dramatic performance degradation. To deal with these issues, this paper proposes a feasible strategy called relative semi-supervised dimensionality reduction (RSSDR) by utilizing the perceptual relativity to semi-supervised dimensionality reduction. In RSSDR, firstly, relative transformation will be performed over the training samples to build the relative space. It should be indicated that relative transformation improves the distinguishing ability among data points and diminishes the impact of noise on semi-supervised dimensionality reduction. Secondly, the edge weights of neighborhood graph will be determined through minimizing the local reconstruction error in the relative space such that it can preserve the global geometric structure as well as the local one of the data. Extensive experiments on face, UCI, gene expression, artificial and noisy data sets have been provided to validate the feasibility and effectiveness of the proposed algorithm with the promising results both in classification accuracy and robustness.     

On numerical algorithm and interactive visualization for optimal control problems

We present methods for the visualization of the numerical solution of optimal control problems. The solution is based on dynamic programming techniques where the corresponding optimal value function is approximated on an adaptively refined grid. This approximation is then used in order to compute approximately optimal solution trajectories. We discuss requirements for the efficient visualization of both the optimal value functions and the optimal trajectories and develop graphic routines that in particular support adaptive, hierarchical grid structures, interactivity and animation. Several implementational aspects using the Graphics Programming Environment ‘GRAPE’ are discussed. Received: 4 December 1997 / Accepted: 5 August 1998     

基于自变量简约的大规模稀疏多目标优化

现有的大多数进化算法在求解大规模优化问题时性能会随决策变量维数的增长而下降。通常,多目标优化的Pareto有效解集是自变量空间的一个低维流形,该流形的维度远小于自变量空间的维度。鉴于此,提出一种基于自变量简约的多目标进化算法求解大规模稀疏多目标优化问题。该算法通过引入局部保持投影降维,保留原始自变量空间中的局部近邻关系,并设计一个归档集,将寻找到的非劣解存入其中进行训练,以提高投影的准确性。将该算法与四种流行的多目标进化算法在一系列测试问题和实际应用问题上进行了比较。实验结果表明,所提算法在解决稀疏多目标问题上具有较好的效果。因此,通过自变量简约能降低问题的求解难度,提高算法的搜索效率,在解决大规模稀疏多目标问题方面具有显著的优势。     

分层交互式蚁群优化算法及其应用

传统蚁群优化算法在求解优化性能指标难以数量化的定性系统问题时无能为力,为此提出一种利用人对问题解进行评价的分层交互式蚁群优化算法。设计了一个基本交互式蚁群优化模型结构,讨论了信息素的更新策略和性质。给出分层的思想、分层的时机和分层的具体实现方法。算法用户参与评价时,只需指出每一代中最感兴趣的解,而不必给出每个解的具体数量值,可以极大降低用户评价疲劳。将算法应用于汽车造型设计,实验结果表明所提出算法具有较高运行性能。     

一种邻域线性竞争的排列降维方法

局部线性嵌入算法以及局部切空间排列算法是目前对降维研究有着重要影响的算法, 但对于稀疏数据及噪声数据, 在使用这些经典算法降维时效果欠佳。一个重要问题就是这些算法在处理局部邻域时存在信息涵盖量不足。对经典算法中全局信息和局部信息的提取机制进行分析后, 提出一种邻域线性竞争的排列方法（neighborhood linear rival alignment algorithm, NLRA）。通过对数据点的近邻作局部结构提取, 有效挖掘稀疏数据内部信息, 使得数据整体降维效果更加稳定。通过手工流形和真实数据集的实验, 验证了算法的有效性和稳定性。     

A novel supervised dimensionality reduction algorithm: Graph-based Fisher analysis

In this paper, a novel supervised dimensionality reduction (DR) algorithm called graph- based Fisher analysis (GbFA) is proposed. More specifically, we redefine the intrinsic and penalty graph and trade off the importance degrees of the same-class points to the intrinsic graph and the importance degrees of the not-same-class points to the penalty graph by a strictly monotone decreasing function; then the novel feature extraction criterion based on the intrinsic and penalty graph is applied. For the non-linearly separable problems, we study the kernel extensions of GbFA with respect to positive definite kernels and indefinite kernels, respectively. In addition, experiments are provided for analyzing and illustrating our results.     

An adaptive class pairwise dimensionality reduction algorithm

Support vector machines (SVM) has achieved great success in multi-class classification. However, with the increase in dimension, the irrelevant or redundant features may degrade the generalization performances of the SVM classifiers, which make dimensionality reduction (DR) become indispensable for high-dimensional data. At present, most of the DR algorithms reduce all data points to the same dimension for multi-class datasets, or search the local latent dimension for each class, but they neglect the fact that different class pairs also have different local latent dimensions. In this paper, we propose an adaptive class pairwise dimensionality reduction algorithm (ACPDR) to improve the generalization performances of the multi-class SVM classifiers. In the proposed algorithm, on the one hand, different class pairs are reduced to different dimensions; on the other hand, a tabu strategy is adopted to select adaptively a suitable embedding dimension. Five popular DR algorithms are employed in our experiment, and the numerical results on some benchmark multi-class datasets show that compared with the traditional DR algorithms, the proposed ACPDR can improve the generalization performances of the multi-class SVM classifiers, and also verify that it is reasonable to consider the different class pairs have different local dimensions.     

A streaming narrow-band algorithm: interactive computation and visualization of level sets

Deformable isosurfaces, implemented with level-set methods, have demonstrated a great potential in visualization and computer graphics for applications such as segmentation, surface processing, and physically-based modeling. Their usefulness has been limited, however, by their high computational cost and reliance on significant parameter tuning. This paper presents a solution to these challenges by describing graphics processor (GPU) based algorithms for solving and visualizing level-set solutions at interactive rates. The proposed solution is based on a new, streaming implementation of the narrow-band algorithm. The new algorithm packs the level-set isosurface data into 2D texture memory via a multidimensional virtual memory system. As the level set moves, this texture-based representation is dynamically updated via a novel GPU-to-CPU message passing scheme. By integrating the level-set solver with a real-time volume renderer, a user can visualize and intuitively steer the level-set surface as it evolves. We demonstrate the capabilities of this technology for interactive volume segmentation and visualization.     

基于QR分解的鉴别维数压缩及其在人脸识别中的应用

维数压缩是当前模式识别研究领域中的一个重要研究方向．但是当前部分维数压缩方法缺乏有效的鉴别信息保留机制，并且在利用Fisher鉴别准则的时候经常会遇到小样本问题．简单介绍了维数压缩中的鉴别信息保留，并且提出了一种新的直接线性鉴别分析方法——DLDA／QR算法．该方法首先利用矩阵的QR分解算法实现目标函数的优化，再在一个较小的空间内实现有效鉴别信息的提取．在ORL人脸数据库上的实验结果验证了算法的有效性．     

A unified framework for semi-supervised dimensionality reduction

In practice, many applications require a dimensionality reduction method to deal with the partially labeled problem. In this paper, we propose a semi-supervised dimensionality reduction framework, which can efficiently handle the unlabeled data. Under the framework, several classical methods, such as principal component analysis (PCA), linear discriminant analysis (LDA), maximum margin criterion (MMC), locality preserving projections (LPP) and their corresponding kernel versions can be seen as special cases. For high-dimensional data, we can give a low-dimensional embedding result for both discriminating multi-class sub-manifolds and preserving local manifold structure. Experiments show that our algorithms can significantly improve the accuracy rates of the corresponding supervised and unsupervised approaches.     

动态SVDD人机交互预警算法及其应用

分析了当前主要的预警方法,指出了其不足,提出了动态SVDD人机交互预警算法。其中,人机交互技术的引入是为了让专家介入预警工作,以使系统能够准确地区分预警对象的状态。针对人机交互预警,分析了已有的SVDD技术,并指出随着训练样本数目的增加,该算法会因为过大的优化规模而无法操作。为此,提出动态SVDD算法,从而大大减小了优化规模,提高了人机交互预警系统的效率。     

基于遗传算法的无监督分形属性规约技术

属性规约是应对“维数灾难”的有效技术,分形属性规约FDR（Fractal Dimensionality Reduction）是近年来出现的一种无监督属性选择技术,令人遗憾的是其需要多遍扫描数据集,因而难于应对高维数据集情况;基于遗传算法的属性规约技术对于高维数据而言优越于传统属性选择技术,但其无法应用于无监督学习领域。为此,结合遗传算法内在随机并行寻优机制及分形属性选择的无监督特点,设计并实现了基于遗传算法的无监督分形属性子集选择算法GABUFSS（Genetic Algorithm Based Unsupervised Feature Subset Selection）。基于合成与实际数据集的实验对比分析了GABUFSS算法与FDR算法的性能,结果表明GABUFSS相对优于FDR算法,并具有发现等价结果属性子集的特点。     

自适应加权t-SNE算法及其在脑网络状态观测矩阵降维中的应用研究

针对目前数据降维算法受高维空间样本分布影响效果不佳的问题,提出了一种自适应加权的t分布随机近邻嵌入（t-SNE）算法。该算法对两样本点在高维空间中的欧氏距离进行归一化后按距离的不同分布状况进行分组分析,分别按照近距离、较近距离和远距离三种情况在计算高维空间内样本点间的相似概率时进行自适应加权处理,以加权相对距离代替欧氏绝对距离,从而更真实地度量每一组不同样本在高维空间的相似程度。在高维脑网络状态观测矩阵中的降维实验结果表明,自适应加权t-SNE的降维聚类可视化效果优于其它降维算法,与传统t-SNE算法相比,聚类指标值DBI值平均降低了28.39%,DI值平均提高了161.84%,并且有效地消除了分散、交叉和散点等问题。