Heuristic approach for minimizing the projection error in the integrated mapping

In this paper, we have developed and examined a heuristic approach for minimizing the projection error in Sammon’s mapping applied in combination with the self-organizing map (SOM). As a final result, we need to visualize the neurons-winners of the SOM. The criterion of visualization quality is the projection error of Sammon’s mapping. Two combinations were considered: (1) a consecutive application of the SOM and Sammon’s mapping and (2) Sammon’s mapping taking into account the learning flow of the self-organizing neural network (integrated combination of the mapping methods). The goal is to obtain a lower projection error and its lower dependence on the so-called “magic factor” in Sammon’s mapping. Different modifications of Sammon’s mapping are examined experimentally and applied in the combination with the SOM. A parallel algorithm of the integrated combination has been proposed.     

Optimization of the Local Search in the Training for SAMANN Neural Network

In this paper, we discuss the visualization of multidimensional data. A well-known procedure for mapping data from a high-dimensional space onto a lower-dimensional one is Sammon’s mapping. This algorithm preserves as well as possible all interpattern distances. We investigate an unsupervised backpropagation algorithm to train a multilayer feed-forward neural network (SAMANN) to perform the Sammon’s nonlinear projection. Sammon mapping has a disadvantage. It lacks generalization, which means that new points cannot be added to the obtained map without recalculating it. The SAMANN network offers the generalization ability of projecting new data, which is not present in the original Sammon’s projection algorithm. To save computation time without losing the mapping quality, we need to select optimal values of control parameters. In our research the emphasis is put on the optimization of the learning rate. The experiments are carried out both on artificial and real data. Two cases have been analyzed: (1) training of the SAMANN network with full data set, (2) retraining of the network when the new data points appear.     

Data Visualization With Multidimensional Scaling

We discuss methodology for multidimensional scaling (MDS) and its implementation in two software systems, GGvis and XGvis. MDS is a visualization technique for proximity data, that is, data in the form of N × N dissimilarity matrices. MDS constructs maps (“configurations,” “embeddings”) in IR^k by interpreting the dissimilarities as distances. Two frequent sources of dissimilarities are high-dimensional data and graphs. When the dissimilarities are distances between high-dimensional objects, MDS acts as a (often nonlinear) dimension-reduction technique. When the dissimilarities are shortest-path distances in a graph, MDS acts as a graph layout technique. MDS has found recent attention in machine learning motivated by image databases (“Isomap”). MDS is also of interest in view of the popularity of “kernelizing” approaches inspired by Support Vector Machines (SVMs; “kernel PCA”).

This article discusses the following general topics: (1) the stability and multiplicity of MDS solutions; (2) the analysis of structure within and between subsets of objects with missing value schemes in dissimilarity matrices; (3) gradient descent for optimizing general MDS loss functions (“Strain” and “Stress”); (4) a unification of classical (Strain-based) and distance (Stress-based) MDS.

Particular topics include the following: (1) blending of automatic optimization with interactive displacement of configuration points to assist in the search for global optima; (2) forming groups of objects with interactive brushing to create patterned missing values in MDS loss functions; (3) optimizing MDS loss functions for large numbers of objects relative to a small set of anchor points (“external unfolding”); and (4) a non-metric version of classical MDS.

We show applications to the mapping of computer usage data, to the dimension reduction of marketing segmentation data, to the layout of mathematical graphs and social networks, and finally to the spatial reconstruction of molecules.     

A two-phase algorithm for consensus building in AHP-group decision making

Group decision making through the AHP has received significant attention in contemporary research, the primary focus of which has been on the issues of consistency and consensus building. In this paper, we concentrate on the latter and present a two-phase algorithm based on the optimal clustering of decision makers (members of a group) into sub groups followed by consensus building both within sub groups and between sub groups. Two-dimensional Sammon’s mapping is proposed as a tool for generating an approximate visualization of sub groups identified in multidimensional vector space, while the consensus convergence model is suggested for reaching agreement amongst individuals in and between sub groups. As a given, all decision makers evaluate the same decision elements within the AHP framework and produce individual scores of these decision elements. The consensual scores are obtained through the iterative procedure and the final scores are declared as the group decision. The results of two selected numerical examples are compared with two sets of results: the results obtained by the commonly used geometric mean aggregation method and also the results obtained if the consensus convergence model is applied directly without the prior clustering of the decision makers. The comparisons indicated the expected differences among the aggregation schemes and the final group scores. The matrices of respect values in the consensus convergence model, obtained for cases when the decision makers are optimally clustered and when they are not, show that in the latter case the decision makers receive lower weights of respect from other members in the group. Various tests showed that our approach is efficient in cases when no clusters can be visually and undoubtedly identified, especially if the number of group members is high.     

Multiple outlier detection in multivariate data using self-organizing maps title

Summary  The problem of detection of multidimensional outliers is a fundamental and important problem in applied statistics. The unreliability of multivariate outlier detection techniques such as Mahalanobis distance and hat matrix leverage has led to development of techniques which have been known in the statistical community for well over a decade. The literature on this subject is vast and growing. In this paper, we propose to use the artificial intelligence technique ofself-organizing map (SOM) for detecting multiple outliers in multidimensional datasets. SOM, which produces a topology-preserving mapping of the multidimensional data cloud onto lower dimensional visualizable plane, provides an easy way of detection of multidimensional outliers in the data, at respective levels of leverage. The proposed SOM based method for outlier detection not only identifies the multidimensional outliers, it actually provides information about the entire outlier neighbourhood. Being an artificial intelligence technique, SOM based outlier detection technique is non-parametric and can be used to detect outliers from very large multidimensional datasets. The method is applied to detect outliers from varied types of simulated multivariate datasets, a benchmark dataset and also to real life cheque processing dataset. The results show that SOM can effectively be used as a useful technique for multidimensional outlier detection.     

基于非线性变换的PCP-C模型及其在地下水动态分类中的应用

为了克服目前地下水动态分类方法中存在的不能揭示分类指标空间到类型空间的非线性映射关系、方法复杂、计算量大等缺陷,可采用基于非线性变换的主成分投影(PCP)-聚类(C)模型,对地下水动态进行分类.方法首先对分类指标数据进行对数中心化变换,然后应用主成分投影法将变换后的多维指标向量映射到最优一维向量空间,并根据各样本指标在一维向量空间的投影值进行聚类分析,由此得到地下水动态分类结果.地下水动态分类结果表明,建议方法概念清晰,结构简单,计算简便,分类结果可信,是一种有效的地下水动态分类方法.     

Multidimensional scaling analysis of soccer dynamics

This paper studies the behavior of teams competing within soccer national leagues. The dissimilarities between teams are measured using the match results at each round and that information feeds a multidimensional scaling (MDS) algorithm for visualizing teams’ performance. Data characterizing four European leagues during season 2014–2015 is adopted and processed using three distinct approaches. In the first, one dissimilarity matrix and one MDS map per round are generated. After, Procrustes analysis is applied to linearly transform the MDS charts for maximum superposition and to build one global MDS representation for the whole season. In the second approach, all data is combined into one dissimilarity matrix leading to a single global MDS chart. In the third approach, the results per round are used to generate time series for all teams. Then, the time series are compared, generating a dissimilarity matrix and the corresponding MDS map. In all cases, the points on the maps represent teams state up to a given round. The set of points corresponding to each team forms a locus representative of its performance versus time.     

Efficiency ranking of decision making units in data envelopment analysis by using TOPSIS-DEA method

Data envelopment analysis methods classify the decision making units into two groups: efficient and inefficient ones. Therefore, the fully ranking all DMUs is demanded by most of the decision makers. However, data envelopment analysis and multiple criteria decision making units are developed independently and designed for different purposes. However, there are some applications in problem solving such as ranking, where these two methods are combined. Combination of multiple criteria decision making methods with data envelopment analysis is a new idea for elimination of disadvantages when applied independently. In this paper, first the new combined method is proposed named TOPSIS-DEA for ranking efficient units which not only includes the benefits of both data envelopment analysis and multiple criteria decision making methods, but also solves the issues that appear in former methods. Then properties and advantages of the suggested method are discussed and compared with super efficiency method, MAJ method, statistical-based model (CCA), statistical-based model (DR/DEA), cross-efficiency—aggressive, cross-efficiency—benevolent, Liang et al.’s model, through several illustrative examples. Finally, the proposed methods are validated.     

Methods for the analysis of asymmetric pairwise relationships

Asymmetric pairwise relationships are frequently observed in experimental and non-experimental studies. They can be analysed with different aims and approaches. A brief review of models and methods of multidimensional scaling and cluster analysis able to deal with asymmetric proximities is provided taking a ‘data-analytic’ approach and emphasizing data visualization.

     

Multicriteria identification sets method

A multicriteria identification and prediction method for mathematical models of simulation type in the case of several identification criteria (error functions) is proposed. The necessity of the multicriteria formulation arises, for example, when one needs to take into account errors of completely different origins (not reducible to a single characteristic) or when there is no information on the class of noise in the data to be analyzed. An identification sets method is described based on the approximation and visualization of the multidimensional graph of the identification error function and sets of suboptimal parameters. This method allows for additional advantages of the multicriteria approach, namely, the construction and visual analysis of the frontier and the effective identification set (frontier and the Pareto set for identification criteria), various representations of the sets of Pareto effective and subeffective parameter combinations, and the corresponding predictive trajectory tubes. The approximation is based on the deep holes method, which yields metric ε-coverings with nearly optimal properties, and on multiphase approximation methods for the Edgeworth–Pareto hull. The visualization relies on the approach of interactive decision maps. With the use of the multicriteria method, multiple-choice solutions of identification and prediction problems can be produced and justified by analyzing the stability of the optimal solution not only with respect to the parameters (robustness with respect to data) but also with respect to the chosen set of identification criteria (robustness with respect to the given collection of functionals).     

Rotation Techniques in Asymmetric Multidimensional Scaling

Multidimensional scaling (MDS) is a set of techniques, used especially in behavioral and social sciences, that enable a researcher to visualize proximity data in a multidimensional space. This article focuses on a particular class of MDS models proposed to deal with proximities which describe asymmetric relationships (i.e., trade indices for a set of countries, brand switching data, occupational mobility tables, and so on). They are based on the decomposition of the relationships into a symmetric and a skew-symmetric part. In this way the objects are represented as points in a multidimensional space and the intensity of their relationships as scalar products (symmetry) or triangle areas (skew-symmetry). These models are seen as special cases of a general model and their rotational indeterminacy is investigated. The aim is to propose a rotation method that makes easier the visual inspection of the graphical representation, highlighting the simple structure of the data. In particular an orthomax-like family of rotation methods and a general algorithm are proposed. Advantages of the proposal are illustrated by analysis of import-export data.     

State-Space Regularization: Geometric Theory

Regularization of nonlinear ill-posed inverse problems is analyzed for a class of problems that is characterized by mappings which are the composition of a well-posed nonlinear and an ill-posed linear mapping. Regularization is carried out in the range of the nonlinear mapping. In applications this corresponds to the state-space variable of a partial differential equation or to preconditioning of data. The geometric theory of projection onto quasi-convex sets is used to analyze the stabilizing properties of this regularization technique and to describe its asymptotic behavior as the regularization parameter tends to zero. Accepted 26 April 1996     

Method of “transition into space of derivatives”: 40 years of evolution

In 1975, the “method of transition into space of derivatives” was proposed. It is an efficiently verifiable frequency criterion for the existence of a nontrivial periodic solution in multidimensional models of automatic control systems with one differentiable nonlinear term. The method used the classical torus principle and refrained from any constructions in the phase space of the system under study. Moreover, the method allowed researchers to broaden the class of systems to which it could be applied. In this work, we give a survey of the results presenting generalization and expansion of the method. We also show the connection between the method of transition into space of derivatives, the well-known generalized Poincaré–Bendixson principle proposed by R. A. Smith, and the results of contemporary authors who are active in the theory of oscillations in multidimensional systems. In the recent years, the author obtained frequency criteria for the existence of orbitally stable cycles in multiinput multioutput (MIMO) control systems and methods for the construction of multidimensional systems having a unique equilibrium and an arbitrarily prescribed number of orbitally stable cycles, which are described in the paper. The extension of the generalized Poincaré–Bendixson principle to multidimensional systems with angular coordinate is presented. We show the application of described methods of investigation of oscillation processes in multidimensional dynamical systems to solving S. Smale’s problem in the chemical kinetics theory of biological cells and also to finding hidden attractors of the generalized Chua system and the minimal global attractor of a system with a polynomial nonlinear term. The publication is illustrated by numerous examples.     

Visualizing high density clusters in multidimensional data using optimized star coordinates

Multidimensional multivariate data have been studied in different areas for quite some time. Commonly, the analysis goal is not to look into individual records but to understand the distribution of the records at large and to find clusters of records that exhibit correlations between dimensions or variables. We propose a visualization method that operates on density rather than individual records. To not restrict our search for clusters, we compute density in the given multidimensional space. Clusters are formed by areas of high density. We present an approach that automatically computes a hierarchical tree of high density clusters. For visualization purposes, we propose a method to project the multidimensional clusters to a 2D or 3D layout. The projection method uses an optimized star coordinates layout. The optimization procedure minimizes the overlap of projected clusters and maximally maintains the cluster shapes, compactness, and distribution. The star coordinate visualization allows for an interactive analysis of the distribution of clusters and comprehension of the relations between clusters and the original dimensions. Clusters are being visualized using nested sequences of density level sets leading to a quantitative understanding of information content, patterns, and relationships.     

A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs

This paper considers solving a special case of the nonadditive traffic equilibrium problem presented by Gabriel and Bernstein [Transportation Science 31 (4) (1997) 337–348] in which the cost incurred on each path is made up of the sum of the arc travel times plus a path-specific cost for traveling on that path. A self-adaptive projection and contraction method is suggested to solve the path-specific cost traffic equilibrium problem, which is formulated as a nonlinear complementarity problem (NCP). The computational effort required per iteration is very modest. It consists of only two function evaluations and a simple projection on the nonnegative orthant. A self-adaptive technique is embedded in the projection and contraction method to find suitable scaling factor without the need to do a line search. The method is simple and has the ability to handle a general monotone mapping F. Numerical results are provided to demonstrate the features of the projection and contraction method.     

Self-organizing map of soil properties in the context of hydrological modeling

One of the most relevant inputs for hydrological modeling is the soil map. The soil sources and scales for the soil properties are diverse, and the quality of soil mapping is increasing, but soil surveying is time-consuming and large area campaigns are expensive. The taxonomic unit approach for soil mapping is common and limited to one layer of data. This limitation causes errors in simulated water fluxes through the soil when taxonomic units approach is implemented during hydrological modeling analysis. Some strategies using geostatistics and machine learning algorithms such as Kriging and Self-Organizing maps (SOM) are improving the taxonomic units’ approach and could serve as an alternative for soil mapping for hydrological purposes. The aim of this work is to study the influence of different soil maps and resolutions on the main hydrological components of a sub-arid watershed in central Spain. For this, the Soil Water and Assessment Tool (SWAT) was parameterized with three different soil maps. A first one was based on Harmonized World Soil database from FAO, at scale 1:1,000,000 (HWSD). The other two were based on a Kriging interpolation at 100 × 100 m from soil samples. To obtain soil properties map from it, two strategies were applied: one was to average the soil properties following the official taxonomic soil units at 1:400,000 scale (Agricultural Technological Institute of Castilla and Leon - ITACyL) and the other was to applied Self-organizing map (SOM) to create the soil units (SOMM).The results suggest that scale and soil properties mapping influence HRU definition, which in turn affects water flow through the soils. Statistical metrics of model performance were improved from R² =0.62 and NSE=0.46 with HWSD soil map to R² =0.86 and NSE=0.84 with SOM and similar values were achieved during validation. Thus, the SOM is presented as an innovative algorithm applied for hydrological modeling with SWAT, significantly increasing the level of model accuracy to stream flow in sub-arid watersheds.     

A Set of Greedy Randomized Adaptive Local Search Procedure (GRASP) Implementations for the Multidimensional Assignment Problem

The focal problem for centralized multisensor multitarget tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Large classes of these association problems can be formulated as multidimensional assignment problems, which are known to be NP-hard for three dimensions or more. The assignment problems that result from tracking are large scale, sparse and noisy. Solution methods must execute in real-time. The Greedy Randomized Adaptive Local Search Procedure (GRASP) has proven highly effective for solving many classes NP-hard optimization problems. This paper introduces four GRASP implementations for the multidimensional assignment problem, which are combinations of two constructive methods (randomized reduced cost greedy and randomized max regret) and two local search methods (two-assignment-exchange and variable depth exchange). Numerical results are shown for a two random problem classes and one tracking problem class.     

On the convergence of projection methods: Application to the decomposition of affine variational inequalities

In this paper, we first discuss the global convergence of symmetric projection methods for solving nonlinear monotone variational inequalities under a cocoercivity assumption. A similar analysis is applied to asymmetric projection methods, when the mapping is affine and monotone. Under a suitable choice of the projection matrix, decomposition can be achieved. It is proved that this scheme achieves a linear convergence rate, thus enhancing results previously obtained by Tseng (Ref. 1) and by Luo and Tseng (Ref. 2).The research of the first author was supported by NSERC Grant A5789 and DND-FUHBP. The research of the second author was supported by NSERC Grant OGP-0157735.The authors are indebted to the referees and Associate Editor P. Tseng for their constructive comments.     

Reduction of multidimensional first order equations with multi-homogeneous function of derivatives

We present an analysis of solutions to multidimensional first order equation order with several independent variables under assumption that the nonlinear part of the equation is a multi-homogeneous function of derivatives. The reduction of the original equation is performed for the class of solutions depending on linear combinations of prescribed groups of initial variables. We obtain solutions to the reduced equation. We consider also the cases of additional, multiplicational and combined separation of variables.     

Projektive Newton-Verfahren und Anwendungen auf nichtlineare Randwertaufgaben

Summary In this paper we consider the following Newton-like methods for the solution of nonlinear equations. In each step of the Newton method the linear equations are solved approximatively by a projection method. We call this a Projective Newton method. For a fixed projection method the approximations often are the same as those of the Newton method applied to a nonlinear projection method. But the efficiency can be increased by adapting the accuracy of the projection method to the convergence of the approximations. We investigate the convergence and the order of convergence for these methods. The results are applied to some Projective Newton methods for nonlinear two point boundary value problems. Some numerical results indicate the efficiency of these methods.