L 1 Optimization under Linear Inequality Constraints

1 optimization under linear inequality constraints based upon iteratively reweighted iterative projection (or IRIP). IRIP is compared to a linear programming (LP) strategy for L₁ minimization (Sp?th 1987, Chapter 5.3) using the ultrametric condition as an exemlar class of constraints to be fitted. Coded for general constraints, the LP approach proves to be faster. Both methods, however, suffer from a serious limitation in being unable to process reasonably-sized data sets because of storage requirements for the constraints. When the simplicity of vector projections is used to allow IRIP to be coded for specific (in this case, ultrametric) constraints, we obtain a fast and efficient algorithm capable of handling large data sets. It is also possible to extend IRIP to operate as a heuristic search strategy that simultaneously identifies both a reasonable set of constraints to impose and the optimally-estimated parameters satisfying these constraints. A few noteworthy characteristics of L₁ optimal ultrametrics are discussed, including other strategies for reformulating the ultrametric optimization problem.     

A mathematical programming approach to fitting general graphs

We present an algorithm for fitting general graphs to proximity data. The algorithm utilizes a mathematical programming procedure based on a penalty function approach to impose additivity constraints upon parameters. For a user-specified number of links, the algorithm seeks to provide the connected network that gives the least-squares approximation to the proximity data with the specified number of links, allowing for linear transformations of the data. The network distance is the minimum-path-length metric for connected graphs. As a limiting case, the algorithm provides a tree where each node corresponds to an object, if the number of links is set equal to the number of objects minus one. A Monte Carlo investigation indicates that the resulting networks tend to fall within one percentage point of the least-squares solution in terms of the variance accounted for, but do not always attain this global optimum. The network model is discussed in relation to ordinal network representations (Klauer 1989) and NETSCAL (Hutchinson 1989), and applied to several well-known data sets.     

A Binary Integer Program to Maximize the Agreement Between Partitions

This research note focuses on a problem where the cluster sizes for two partitions of the same object set are assumed known; however, the actual assignments of objects to clusters are unknown for one or both partitions. The objective is to find a contingency table that produces maximum possible agreement between the two partitions, subject to constraints that the row and column marginal frequencies for the table correspond exactly to the cluster sizes for the partitions. This problem was described by H. Messatfa (Journal of Classification, 1992, pp. 5–15), who provided a heuristic procedure based on the linear transportation problem. We present an exact solution procedure using binary integer programming. We demonstrate that our proposed method efficiently obtains optimal solutions for problems of practical size. We would like to thank the Editor, Willem Heiser, and an anonymous reviewer for helpful comments that resulted in improvements of this article.     

Some Interpretative Tools for Non-Symmetrical Correspondence Analysis

Non-symmetrical correspondence analysis (NSCA) is a very practical statistical technique for the identification of the structure of association between asymmetrically related categorical variables forming a contingency table. This paper considers some tools that can be used to numerically and graphically explore in detail the association between these variables and include the use of confidence regions, the establishment of the link between NSCA and the analysis of variance of categorical variables, and the effect of imposing linear constraints on a variable. The authors would like to thank the anonymous referees for their comments and suggestions during the preparation of this paper.     

A sequential fitting procedure for linear data analysis models

A particular factor analysis model with parameter constraints is generalized to include classification problems definable within a framework of fitting linear models. The sequential fitting (SEFIT) approach of principal component analysis is extended to include several nonstandard data analysis and classification tasks. SEFIT methods attempt to explain the variability in the initial data (commonly defined by a sum of squares) through an additive decomposition attributable to the various terms in the model. New methods are developed for both traditional and fuzzy clustering that have useful theoretic and computational properties (principal cluster analysis, additive clustering, and so on). Connections to several known classification strategies are also stated.The author is grateful to P. Arabie and L. J. Hubert for editorial assistance and reviewing going well beyond traditional levels.     

A classification of presence/absence based dissimilarity coefficients

Several desirable order properties for dissimilarity coefficients based on presence/absence of attributes are given and several popular dissimilarity coefficients are examined with respect to these properties. A characterization for rational functions with linear numerator and linear denominator satisfying all of the desirable properties is given.     

Dealing with Distances and Transformations for Fuzzy C-Means Clustering of Compositional Data

Clustering techniques are based upon a dissimilarity or distance measure between objects and clusters. This paper focuses on the simplex space, whose elements??compositions??are subject to non-negativity and constant-sum constraints. Any data analysis involving compositions should fulfill two main principles: scale invariance and subcompositional coherence. Among fuzzy clustering methods, the FCM algorithm is broadly applied in a variety of fields, but it is not well-behaved when dealing with compositions. Here, the adequacy of different dissimilarities in the simplex, together with the behavior of the common log-ratio transformations, is discussed in the basis of compositional principles. As a result, a well-founded strategy for FCM clustering of compositions is suggested. Theoretical findings are accompanied by numerical evidence, and a detailed account of our proposal is provided. Finally, a case study is illustrated using a nutritional data set known in the clustering literature.     

Free Knot Splines for Supervised Classification

Data in many different fields come to practitioners through a process naturally described as functional. We propose a classification procedure of oxidation curves. Our algorithm is based on two stages: fitting the functional data by linear splines with free knots and classifying the estimated knots which estimate useful oxidation parameters. A real data set on 57 oxidation curves is used to illustrate our approach.     

On the Import of Constraints in Complex Dynamical Systems

Complexity arises from interaction dynamics, but its forms are co-determined by the operative constraints within which the dynamics are expressed. The basic interaction dynamics underlying complex systems is mostly well understood. The formation and operation of constraints is often not, and oftener under appreciated. The attempt to reduce constraints to basic interaction fails in key cases. The overall aim of this paper is to highlight the key role played by constraints in shaping the field of complex systems. Following an introduction to constraints (Sect. 1), the paper develops the roles of constraints in specifying forms of complexity (Sect. 2) and illustrates the roles of constraints in formulating the fundamental challenges to understanding posed by complex systems (Sect. 3).     

科技信息资源共享的约束与调控分析

共享是实现科技信息资源合理配置、提高资源利用效率的有效途径。本文基于资源共享的基本内涵,进一步从经济学和系统科学的视角,总结了限制科技信息资源共享的约束条件。重点剖析了共享成本的构成及其产生的约束,包括单个参与主体的成本约束和系统性约束。提出了科技信息资源共享的双向寻优模型和针对共享约束的调控对策,倡导主动共享和有限共享相结合,从而实现适度共享,以期最大程度地提高科技信息资源的利用效率。     

Fixed Point Clusters for Linear Regression: Computation and Comparison

In this paper an algorithm is developed, which aims to find all FPCs of a dataset corresponding to well separated linear regression subpopulations. Its ability to find such subpopulations under the occurence of outliers is compared to methods based on ML-estimation of mixture models by means of a simulation study. Furthermore, FPC analysis is applied to a real dataset.     

Structural Similarity: Spectral Methods for Relaxed Blockmodeling

In this paper we propose the concept of structural similarity as a relaxation of blockmodeling in social network analysis. Most previous approaches attempt to relax the constraints on partitions, for instance, that of being a structural or regular equivalence to being approximately structural or regular, respectively. In contrast, our approach is to relax the partitions themselves: structural similarities yield similarity values instead of equivalence or non-equivalence of actors, while strictly obeying the requirement made for exact regular equivalences. Structural similarities are based on a vector space interpretation and yield efficient spectral methods that, in a more restrictive manner, have been successfully applied to difficult combinatorial problems such as graph coloring. While traditional blockmodeling approaches have to rely on local search heuristics, our framework yields algorithms that are provably optimal for specific data-generation models. Furthermore, the stability of structural similarities can be well characterized making them suitable for the analysis of noisy or dynamically changing network data.     

一次同余式组的欧拉解法和黄宗宪反乘率新术

该文着重于用初等数论方法严格核对黄宗宪的反乘率新术，指出它同欧拉的一个一次同余式组解法是一致的，尽管在时间上晚于欧拉，但思路有所不同。黄宗宪是从研究改进秦九韶的大衍求一术出发，得到反乘率概念，再独立研究出反乘率新术，在计算上更体现出传统数学的算法化倾向。     

Mechanistic Explanations and Models in Molecular Systems Biology

Mechanistic models in molecular systems biology are generally mathematical models of the action of networks of biochemical reactions, involving metabolism, signal transduction, and/or gene expression. They can be either simulated numerically or analyzed analytically. Systems biology integrates quantitative molecular data acquisition with mathematical models to design new experiments, discriminate between alternative mechanisms and explain the molecular basis of cellular properties. At the heart of this approach are mechanistic models of molecular networks. We focus on the articulation and development of mechanistic models, identifying five constraints which guide the articulation of models in molecular systems biology. These constraints are not independent of one another, with the result that modeling becomes an iterative process. We illustrate the use of these constraints in the modeling of the mechanism for bistability in the lac operon.     

On the Uniqueness of the Selection Criterion in Neighbor-Joining

The Neighbor-Joining (NJ) method of Saitou and Nei is the most widely used distance based method in phylogenetic analysis. Central to the method is the selection criterion, the formula used to choose which pair of objects to amalgamate next. Here we analyze the NJ selection criterion using an axiomatic approach. We show that any selection criterion that is linear, permutation equivariant, statistically consistent and based solely on distance data will give the same trees as those created by NJ.     

Materialism: Replies to Comments from Readers

The canonical developmental trajectory (CDT), as represented in this paper is both conservative and emergentist. Emerging modes of existence, as new informational constraints, require the material continuation of prior modes upon which they are launched. Informational constraints are material configurations. The paper is not meant to be a direct critique of existing views within science, but an oblique one presented as an alternative, developmental model.     

Classification Using Class Cover Catch Digraphs

class cover catch digraphs based on proximity between training observations. Performance comparisons are presented on synthetic and real examples versus k-nearest neighbors, Fisher's linear discriminant and support vector machines. We demonstrate that the proposed semiparametric classifier has performance approaching that of the optimal parametric classifier in cases for which the optimal is available for comparison.     

区域集群创新:一个基于生成式的分析框架

区域集群创新是创新的一种新形式,它不同于传统上创新主体限于单个机构或个人,创新过程以单一线性为主的模式,有着更为复杂的实现机制。本文依创新本身的生成逻辑,构建了一个综合性分析框架。区域集群主体基于丰富的地理、社会和行业接近性所生成的互动网络是创新产生的基础,它纾解了主体间知识转移的障碍,使集群整体层面呈现出协同进化特征,而个体关系层面的竞争和合作催生了创新的“涨落”效应,由此推动了创新的不断生成演进。     

等差级数与插值法

《周髀算经》中求“衡径”和“晷长”的方法可以视为一次插值法的应用，《大衍历》中“先定日数，径求积度及分”的方法实与刘徽提出的等差级数求和公式一致。一般来说，一个（ｋ—１）阶等差级数的求和公式等价于一个ｋ阶等间距插值公式。在中国古代数学中，等差级数和插值法是两个相互关联的题材，宋元数学家在充分认识高阶等差级数的基础上方有可能得到一般的等间距插值公式。     

Comparison of classifications using measures intermediate between metric dissimilarity and consensus similarity

Two fundamental approaches to the comparison of classifications (e g, partitions on the same finite set of objects) can be distinguished One approach is based upon measures of metric dissimilarity while the other is based upon measures of similarity, or consensus These approaches are not necessarily simple complements of each other Instead, each captures different, limited views of comparison of two classifications The properties of these measures are clarified by their relationships to Day's complexity models and to association measures of numerical taxonomy The two approaches to comparison are equated with the use of separation and minimum value sensitive measures, suggesting the potential application of an intermediate sensitive measure to the problem of comparison of classifications Such a measure is a linear combination of separation sensitive and minimum value sensitive components The application of these intermediate measures is contrasted with the two extremes The intermediate measure for the comparison of classifications is applied to a problem of character weighting arising in the analysis of Australian stream basinsWe thank Bill Day, Mike Austin, Peter Minchin and two anonymous referees for many helpful comments We also thank P Arabie for useful discussion of consensus methods and character weighting