检索结果-内蒙古大学图书馆

Morph-based local-search heuristics for large-scale combinatorial data analysis

JOURNAL OF CLASSIFICATION 1999年第2期16卷 163-180页

作者： Brusco, MJ Florida State Univ Coll Business Informat & Management Sci Dept Tallahassee FL 32306 USA

There are a variety of data analysis techniques in the social and behavioral sciences that require the solution of NP-complete optimization problems. Unfortunately, optimal solution methods are generally intractable for problems of practical size and thus there has been an emphasis on the development of heuristic procedures. Although local-search procedures, such as simulated annealing, have been tested on several combinatorial data analysis problems, they have frequently been criticized as computationally inefficient and therefore impractical for large problems. This paper presents a process called 'morphing' that can substantially increase the efficiency and effectiveness of local-search heuristics. The new procedure is compared to replications of a heuristic battery of local-operations across a set of large metric unidimensional scaling (seriation) problems. Generalizations of the morphing process to other problems in combinatorial data analysis are also discussed.

关键词： local-search methods combinatorial data analysis unidimensional scaling seriation

来源：评论

学校读者我要写书评

暂无评论

Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis

引用

PSYCHOMETRIKA 2008年第3期73卷 503-522页

作者： Brusco, Michael J. Koehn, Hans-Friedrich Stahl, Stephanie Florida State Univ Coll Business Dept Mkt Tallahassee FL 32306 USA Univ Missouri Columbia Columbia MO USA

Dynamic programming methods for matrix permutation problems in combinatorial data analysis can produce globally-optimal solutions for matrices up to size 30x30, but are computationally infeasible for larger matrices because of enormous computer memory requirements. Branch-and-bound methods also guarantee globally-optimal solutions, but computation time considerations generally limit their applicability to matrix sizes no greater than 35x35. Accordingly, a variety of heuristic methods have been proposed for larger matrices, including iterative quadratic assignment, tabu search, simulated annealing, and variable neighborhood search. Although these heuristics can produce exceptional results, they are prone to converge to local optima where the permutation is difficult to dislodge via traditional neighborhood moves (e.g., pairwise interchanges, object-block relocations, object-block reversals, etc.). We show that a heuristic implementation of dynamic programming yields an efficient procedure for escaping local optima. Specifically, we propose applying dynamic programming to reasonably-sized subsequences of consecutive objects in the locally-optimal permutation, identified by simulated annealing, to further improve the value of the objective function. Experimental results are provided for three classic matrix permutation problems in the combinatorial data analysis literature: (a) maximizing a dominance index for an asymmetric proximity matrix;(b) least-squares unidimensional scaling of a symmetric dissimilarity matrix;and (c) approximating an anti-Robinson structure for a symmetric dissimilarity matrix.

关键词： combinatorial data analysis matrix permutation dynamic programming heuristics

来源：评论

学校读者我要写书评

暂无评论

combinatorial data analysis: Confirmatory comparisons between sets of matrices

引用

Applied Stochastic Models and data analysis 1989年第3期5卷 273-325页

作者： Hubert, Lawrence Arabie, Phipps Department of Psychology University of Illinois Champaign Illinois 61820 603 East Daniel Street United States

The task of assessing the similarity of pattern between the entries of two square matrices has been discussed extensively over the last decade, as a unifying strategy for approaching a variety of seemingly disparate statistical problems. As typically defined, the comparison depends on a measure of matrix correspondence, usually a normalized cross‐product measure of some form, that is evaluated for relative size by the use of a reference distribution constructed through an equally likely permutation hypothesis defined at the level of the objects corresponding to the rows and columns of the two matrices. The extreme generality provided by this very simple framework subsumes a variety of different statistical problems, ranging from the study of spatial autocorrelation for variables observed over a set of geographic locations, to the topics of analysis of variance, the measurement of rank correlation, and confirmation techniques concerned with various conjectures of combinatorial structure that might be posited for an empirically determined measure of relationship between pairs of a given set of objects. The comparison strategies extant always assume that both matrices are fixed, and in those cases where one of the matrices codifies a given theoretical structure to be evaluated according to a second, this assumption can lead to substantial arbitrariness in how matrix similarity might be indexed, and thus, in how the comparison is implemented. As developed in this paper, exactly the same principles appropriate for use in the fixed comparison context can be extended to include matrices constructed through optimally weighted linear combinations of other sets of matrices. This generalization provides one mechanism for developing comparison strategies that allow assessment against very broad classes of matrices, which in turn serve to represent very general conjectures of possible combinatorial structure. This paper reviews some of these extensions in detail, with a particul

关键词： combinatorial data analysis combinatorial structure Multiple matrix comparisons Permutation methods Randomization tests

来源：评论

学校读者我要写书评

暂无评论

A New Measure for Analyzing and Fusing Sequences of Objects

引用

IEEE TRANSACTIONS ON PATTERN analysis AND MACHINE INTELLIGENCE 2016年第5期38卷 833-848页

作者： Goulermas, John Yannis Kostopoulos, Alexandros Mu, Tingting Univ Liverpool Dept Comp Sci Ashton Bldg Liverpool L69 3BX Merseyside England Univ Liverpool Dept Elect Engn & Elect Brownlow Hill Liverpool L69 3GJ Merseyside England

This work is related to the combinatorial data analysis problem of seriation used for data visualization and exploratory analysis. Seriation re-sequences the data, so that more similar samples or objects appear closer together, whereas dissimilar ones are further apart. Despite the large number of current algorithms to realize such re-sequencing, there has not been a systematic way for analyzing the resulting sequences, comparing them, or fusing them to obtain a single unifying one. We propose a new positional proximity measure that evaluates the similarity of two arbitrary sequences based on their agreement on pairwise positional information of the sequenced objects. Furthermore, we present various statistical properties of this measure as well as its normalized version modeled as an instance of the generalized correlation coefficient. Based on this measure, we define a new procedure for consensus seriation that fuses multiple arbitrary sequences based on a quadratic assignment problem formulation and an efficient way of approximating its solution. We also derive theoretical links with other permutation distance functions and present their associated combinatorial optimization forms for consensus tasks. The utility of the proposed contributions is demonstrated through the comparison and fusion of multiple seriation algorithms we have implemented, using many real-world datasets from different application domains.

关键词： Seriation sequencing consensus/ensemble seriation combinatorial data analysis positional proximity coefficient quadratic assignment problem

来源：评论

学校读者我要写书评

暂无评论

Continuation methods for approximate large scale object sequencing

引用

MACHINE LEARNING 2019年第4期108卷 595-626页

作者： Evangelopoulos, Xenophon Brockmeier, Austin J. Mu, Tingting Goulermas, John Y. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Manchester Sch Comp Sci Manchester Lancs England

We propose a set of highly scalable algorithms for the combinatorial data analysis problem of seriating similarity matrices. Seriation consists of finding a permutation of data instances, such that similar instances are nearby in the ordering. Applications of the seriation problem can be found in various disciplines such as in bioinformatics for genome sequencing, data visualization and exploratory data analysis. Our algorithms attempt to minimize certain p-SUM objectives, which also arise in the problem of envelope reduction of sparse matrices. In particular, we present a set of graduated non-convexity algorithms for vector-based relaxations of the general p-SUM problem for p that can scale to very large problem sizes. Different choices of p emphasize global versus local similarity pattern structure. We conduct a number of experiments to compare our algorithms to various state-of-the-art combinatorial optimization methods on real and synthetic datasets. The experimental results demonstrate that compared to other approaches, the proposed algorithms are very competitive and scale well with large problem sizes.

关键词： combinatorial data analysis combinatorial optimization Graduated non-convexity Sequencing Seriation

来源：评论

学校读者我要写书评

暂无评论

Residual analysis for unidimensional scaling in the L2-norm

引用

COMMUNICATIONS IN STATISTICS-SIMULATION AND COMPUTATION 2019年第7期48卷 2210-2221页

作者： Brusco, Michael J. Steinley, Douglas Kohn, Hans-Friedrich Florida State Univ Dept Business Analyt Informat Syst & Supply Chain Tallahassee FL 32306 USA Univ Missouri Dept Psychol Sci Columbia MO USA Univ Illinois Dept Psychol Champaign IL USA

We present a procedure (RAUS) for residual analysis of a dissimilarity matrix whereby unidimensional scaling is successively applied to the absolute value of residuals. A key advantage of RAUS is that the efficient Defays formulation of unidimensional scaling can be used for the fitting of each scale. An example using U.S. Supreme Court voting data is provided to illustrate the interpretation of successive scales. A simulation study was performed to evaluate RAUS.

关键词： combinatorial data analysis Least-squares unidimensional scaling Residual analysis Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

combinatorial individual differences scaling within the city-block metric

引用

COMPUTATIONAL STATISTICS & data analysis 2006年第2期51卷 931-946页

作者： Kohn, Hans-Friedrich Univ Illinois Urbana IL 61801 USA

A new method is proposed for conducting individual differences scaling within the city-block metric that does not rely on gradient or subgradient-based optimization. lnstead, a combinatorial optimization scheme is utilized for identifying object coordinates minimizing the least-squares loss function. The illustrative application of combinatorial individual differences scaling within the city-block metric to schematic face stimuli suggests that the new method offers a promising alternative to gradient-based attempts for fitting city-block scaling models, which suffer from the well-documented difficulty of local minima. (c) 2005 Elsevier B.V. All rights reserved.

关键词： combinatorial data analysis combinatorial optimization city-block metric INDSCAL model individual differences scaling iterative projection uni-/multidimensional scaling quadratic assignment

来源：评论

学校读者我要写书评

暂无评论

Application of a Key-Value Paradigm to Logic Factoring

引用

PROCEEDINGS OF THE IEEE 2015年第11期103卷 2076-2092页

作者： Kravets, Victor N. IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

Over three decades ago an algebraic factoring algorithm was created as part of active logic synthesis efforts in the semiconductor industry. It initiated logic synthesis successes and steered synthesis in the direction of practical design tools: they can now take a design from its initial state to the final chip that meets a complex set of constraints. The evolved computing platforms today stimulate new exploratory avenues to extend the functionality of fundamental synthesis algorithms. We reexamine logic factoring in an effort to establish a stronger connection to the functional intent rather than structural implications of a design description within synthesis. A scalable factoring algorithm that reduces its dependence on the two-level minimization is described to improve the area of synthesized circuits. It is implemented using a new distributed environment that harnesses the key-value concept to find solutions through systematic transformations of a data set.

关键词： Combinational circuits combinatorial data analysis distributed computing logic design logic synthesis and optimization MapReduce

来源：评论

学校读者我要写书评

暂无评论

Inducing a blockmodel structure of two-mode binary data using seriation procedures

引用

JOURNAL OF MATHEMATICAL PSYCHOLOGY 2006年第5期50卷 468-477页

作者： Brusco, Michael Steinley, Douglas Florida State Univ Dept Mkt Tallahassee FL 32306 USA Univ Missouri Columbia MO USA

We show that seriation of the rows and columns of a two-mode, binary matrix can be an effective method for producing a reordering of the matrix that reveals a blockmodel structure of the data. The objective criterion of the seriation process is based on Robinson patterning of matrix elements. The key advantages of the proposed method are: (a) it can be used in conjunction with existing two-mode blockmodeling algorithms by facilitating selection of the number of classes for the rows and columns of the matrix and the appropriate types of ideal blocks;(b) the model uses a well-grounded index based on Robinson structure, (c) guaranteed optimal solutions can be obtained for problems of practical size, and (d) the seriation method is frequently capable of producing a solution that has a substantive interpretation with respect to the orderings of the row objects and column items. (c) 2006 Elsevier Inc. All rights reserved.

关键词： combinatorial data analysis seriation Robinson matrix blockmodel two-mode binary data

来源：评论

学校读者我要写书评

暂无评论

An evaluation of two algorithms for hierarchical classes analysis

引用

JOURNAL OF CLASSIFICATION 2001年第1期18卷 57-80页

作者： Leenen, I Van Mechelen, I Katholieke Univ Leuven Dept Psychol B-3000 Louvain Belgium

The family of hierarchical classes models is a distinctive collection of direct two-sided clustering models for two-way two-mode binary data. In the associated data analysis, a data matrix D is approximated by a binary matrix M that can be represented by a hierarchical classes model of a prespecified rank k. In this procedure, a least-squares loss function in terms of discrepancies between D and R I is minimized. The present paper describes the original hierarchical classes algorithm proposed by De Boeck and Rosenberg (1988), which is based on an alternating greedy heuristic, and proposes a new algorithm, based on an alternating branch-and-bound procedure. An extensive simulation study is reported in which both algorithms are evaluated and compared according to goodness-of-fit to the data and goodness-of-recovery of the underlying true structure. Furthermore, three heuristics for selecting models of different ranks for a given D are presented and compared. The simulation results show that the new algorithm yields models with slightly higher goodness-of-fit and goodness-of-recovery values.

关键词： hierarchical classification binary data combinatorial data analysis branch-and-bound algorithm simulation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：