Identifying a Reordering of Rows and Columns for Multiple Proximity Matrices Using Multiobjective Programming

This paper is concerned with a problem where K (n×n) proximity matrices are available for a set of n objects. The goal is to identify a single permutation of the n objects that provides an adequate structural fit, as measured by an appropriate index, for each of the K matrices. A multiobjective programming approach for this problem, which seeks to optimize a weighted function of the K indices, is proposed, and illustrative examples are provided using a set of proximity matrices from the psychological literature. These examples show that, by solving the multiobjective programming model under different weighting schemes, the quantitative analyst can uncover information about the relationships among the matrices and often identify one or more permutations that provide good to excellent index values for all matrices.     

ConPar: a method for identifying groups of concordant subject proximity matrices for subsequent multidimensional scaling analyses

A common representation of data within the context of multidimensional scaling (MDS) is a collection of symmetric proximity (similarity or dissimilarity) matrices for each of M subjects. There are a number of possible alternatives for analyzing these data, which include: (a) conducting an MDS analysis on a single matrix obtained by pooling (averaging) the M subject matrices, (b) fitting a separate MDS structure for each of the M matrices, or (c) employing an individual differences MDS model. We discuss each of these approaches, and subsequently propose a straightforward new method (CONcordance PARtitioning—ConPar), which can be used to identify groups of individual-subject matrices with concordant proximity structures. This method collapses the three-way data into a subject×subject dissimilarity matrix, which is subsequently clustered using a branch-and-bound algorithm that minimizes partition diameter. Extensive Monte Carlo testing revealed that, when compared to K-means clustering of the proximity data, ConPar generally provided better recovery of the true subject cluster memberships. A demonstration using empirical three-way data is also provided to illustrate the efficacy of the proposed method.     

Reduced products of logical matrices

The class Matr(C) of all matrices for a prepositional logic (, C) is investigated. The paper contains general results with no special reference to particular logics. The main theorem (Th. (5.1)) which gives the algebraic characterization of the class Matr(C) states the following. Assume C to be the consequence operation on a prepositional language induced by a class K of matrices. Let m be a regular cardinal not less than the cardinality of C. Then Matr (C) is the least class of matrices containing K and closed under m-reduced products, submatrices, matrix homomorphisms, and matrix homomorphic counter-images.     

Correspondence analysis and optimal structural representations

Many well-known measures for the comparison of distinct partitions of the same set ofn objects are based on the structure of class overlap presented in the form of a contingency table (e.g., Pearson's chi-square statistic, Rand's measure, or Goodman-Kruskal'sτ _b ), but they all can be rephrased through the use of a simple cross-product index defined between the corresponding entries from twon ×n proximity matrices that provide particular a priori (numerical) codings of the within- and between-class relationships for each of the partitions. We consider the task of optimally constructing the proximity matrices characterizing the partitions (under suitable restriction) so as to maximize the cross-product measure, or equivalently, the Pearson correlation between their entries. The major result presented states that within the broad classes of matrices that are either symmetric, skew-symmetric, or completely arbitrary, optimal representations are already derivable from what is given by a simple one-dimensional correspondence analysis solution. Besides severely limiting the type of structures that might be of interest to consider for representing the proximity matrices, this result also implies that correspondence analysis beyond one dimension must always be justified from logical bases other than the optimization of a single correlational relationship between the matrices representing the two partitions.     

Hubert's multi-rater kappa revisited

There is a frequent need to measure the degree of agreement among R observers who independently classify n subjects within K nominal or ordinal categories. The most popular methods are usually kappa-type measurements. When R = 2, Cohen's kappa coefficient (weighted or not) is well known. When defined in the ordinal case while assuming quadratic weights, Cohen's kappa has the advantage of coinciding with the intraclass and concordance correlation coefficients. When R > 2, there are more discrepancies because the definition of the kappa coefficient depends on how the phrase ‘an agreement has occurred’ is interpreted. In this paper, Hubert's interpretation, that ‘an agreement occurs if and only if all raters agree on the categorization of an object’, is used, which leads to Hubert's (nominal) and Schuster and Smith's (ordinal) kappa coefficients. Formulae for the large-sample variances for the estimators of all these coefficients are given, allowing the latter to illustrate the different ways of carrying out inference and, with the use of simulation, to select the optimal procedure. In addition, it is shown that Schuster and Smith's kappa coefficient coincides with the intraclass and concordance correlation coefficients if the first coefficient is also defined assuming quadratic weights.     

A Note on Matrices for Systems of nonsense-logics

We construct a class K of algebras which are matrices of the logical system Z introduced in [4]. It is shown that algebras belonging to the class K are decomposable into disjoint subalgebras which are Boolean algebras.To the memory of Jerzy SupeckiTranslated From the Polish by Jan Zygmunt.     

On the concordance among empirical confusion matrices for visual and tactual letter recognition

In this article, we examine the concordance among 19 empirical confusion matrices for visual and tactual recognition of capital letters of the alphabet. As a measure of concordance, we employed an index based on within-stimulus triads of letters. Unlike correlation measures of agreement that are based on a one-to-one matching of matrix elements, the selected index directly captures the internal structures of the confusion matrices prior to the comparison. Permutation tests revealed statistically significant concordance among 166 of 171 pairs of matrices in the study. Concordance of confusion structure among tactual matrices tended to be somewhat stronger than concordance among the visual matrices.     

A consistency-based framework for merging knowledge bases

We present a framework for expressing various merging operators for belief sets. This framework generalises our earlier work on consistency-based belief revision and contraction. Two primary merging operators are identified: in the first approach, belief sources are consistently combined so that the result of merging knowledge bases K₁,…,K_n is a maximal consistent (if possible) set of formulas comprising the joint knowledge of the knowledge bases. This approach then accords with one's intuitions as to what a “merge” operator should do. The second approach is more akin to a generalised belief revision operator. Knowledge bases K₁,…,K_n are “projected” onto another (in the simplest case the knowledge base where only tautologies are known). Properties of these operators are investigated, primarily by comparing their properties with postulates that have been identified previously in the literature. Notably, the approach is independent of syntax, in that merging knowledge bases K₁,…,K_n is independent of how each K_i is expressed. As well, we investigate the role of entailment-based and consistency-based integrity constraints, the interrelationships between these approaches and belief revision, and the expression of further merging operators.     

A heuristic method for the comparison of related structures

By extending a technique for testing the difference between two dependent correlations developed by Wolfe, a strategy is proposed in a more general matrix context for evaluating a variety of data analysis schemes that are supposed to clarify the structure underlying a set of proximity measures. In the applications considered, a data analysis scheme is assumed to reconstruct in matrix form the given data set (represented as a proximity matrix) based on some specific model or procedure. Thus, an evaluation of the adequacy of reconstruction can be developed by comparing matrices, one containing the original proximities and the second containing the reconstructed values. Possible applications in multidimensional scaling, clustering, and related contexts are emphasized using four broad categories: (a) Given two different reconstructions based on a single data set, does either represent the data significantly better than the other? (b) Given two reconstructions based on a single data set using two different procedures (or possibly, two distinct data sets and a common method), is either reconstruction significantly closer to a particular theoretical structure that is assumed to underlie the data (where the latter is also represented in matrix form)? (c) Given two theoretical structures and one reconstruction based on a single data set, does either represent the reconstruction better than the other? (d) Given a single reconstruction based on one data set, is the information present in the data accounted for satisfactorily by the reconstruction? In all cases, these tasks can be approached by a nonparametric procedure that assesses the similarity in pattern between two appropriately defined matrices. The latter are obtained from the original data, the reconstructions, and/or the theoretical structures. Finally, two numerical examples are given to illustrate the more general discussion.     

A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices

The clustering of two-mode proximity matrices is a challenging combinatorial optimization problem that has important applications in the quantitative social sciences. We focus on one particular type of problem related to the clustering of a two-mode binary matrix, which is relevant to the establishment of generalized blockmodels for social networks. In this context, clusters for the rows of the two-mode matrix intersect with clusters of the columns to form blocks, which should ideally be either complete (all 1s) or null (all 0s). A new procedure based on variable neighborhood search is presented and compared to an existing two-mode K-means clustering algorithm. The new procedure generally provided slightly greater explained variation; however, both methods yielded exceptional recovery of cluster structure.     

Criteria for admissibility of inference rules. Modal and intermediate logics with the branching property

The main result of this paper is the following theorem: each modal logic extendingK4 having the branching property belowm and the effective m-drop point property is decidable with respect to admissibility. A similar result is obtained for intermediate intuitionistic logics with the branching property belowm and the strong effective m-drop point property. Thus, general algorithmic criteria which allow to recognize the admissibility of inference rules for modal and intermediate logics of the above kind are found. These criteria are applicable to most modal logics for which decidability with respect to admissibility is known and to many others, for instance, to the modal logicsK4,K4.1,K4.2,K4.3,S4.1,S4.2,GL.2; to all smallest and greatest counterparts of intermediate Gabbay-De-Jong logicsD _n; to all intermediate Gabbay-De-Jong logicsD _n; to all finitely axiomatizable modal and intermediate logics of finite depth etc. Semantic criteria for recognizing admissibility for these logics are offered as well.The results of this paper were obtained by the author during a stay at the Free University of Berlin with support of the Alexander von Humboldt Foundation in 1992 – 1993.Presented byWolfgang Rauntenberg     

K‐means clustering: A half‐century synthesis

This paper synthesizes the results, methodology, and research conducted concerning the K‐means clustering method over the last fifty years. The K‐means method is first introduced, various formulations of the minimum variance loss function and alternative loss functions within the same class are outlined, and different methods of choosing the number of clusters and initialization, variable preprocessing, and data reduction schemes are discussed. Theoretic statistical results are provided and various extensions of K‐means using different metrics or modifications of the original algorithm are given, leading to a unifying treatment of K‐means and some of its extensions. Finally, several future studies are outlined that could enhance the understanding of numerous subtleties affecting the performance of the K‐means method.     

A branch-and-bound algorithm for fitting anti-robinson structures to symmetric dissimilarity matrices

The seriation of proximity matrices is an important problem in combinatorial data analysis and can be conducted using a variety of objective criteria. Some of the most popular criteria for evaluating an ordering of objects are based on (anti-) Robinson forms, which reflect the pattern of elements within each row and/or column of the reordered matrix when moving away from the main diagonal. This paper presents a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results are provided for several proximity matrices from the literature using four different anti-Robinson criteria. The results suggest that with respect to computational efficiency, the branch-and-bound algorithm is generally competitive with dynamic programming. Further, because it requires much less storage than dynamic programming, the branch-and-bound algorithm can provide guaranteed optimal solutions for matrices that are too large for dynamic programming implementations.     

A k-sample significance test for independent alpha coefficients

The earlier two-sample procedure of Feldt [1969] for comparing independent alpha reliability coefficients is extended to the case ofK 2 independent samples. Details of a normalization of the statistic under consideration are presented, leading to computational procedures for the overallK-group significance test and accompanying multiple comparisons. Results based on computer simulation methods are presented, demonstrating that the procedures control Type I error adequately. The results of a power comparison of the case ofK=2 with Feldt's [1969]F test are also presented. The differences in power were negligible. Some final observations, along with suggestions for further research, are noted.The authors gratefully acknowledge the assistance of Michael E. Masson, in the computations performed, and of Leonard S. Feldt, in suggesting the data generation procedures used in the study. In addition, the authors thank James Zidek and the Institute of Applied Mathematics and Statistics, University of British Columbia, for advice concerning some of the theoretical development.     

A model and algorithm for multidimensional scaling with external constraints on the distances

A method for externally constraining certain distances in multidimensional scaling configurations is introduced and illustrated. The approach defines an objective function which is a linear composite of the loss function of the point configurationX relative to the proximity dataP and the loss ofX relative to a pseudo-data matrixR. The matrixR is set up such that the side constraints to be imposed onX's distances are expressed by the relations amongR's numerical elements. One then uses a double-phase procedure with relative penalties on the loss components to generate a constrained solutionX. Various possibilities for constructing actual MDS algorithms are conceivable: the major classes are defined by the specification of metric or nonmetric loss for data and/or constraints, and by the various possibilities for partitioning the matricesP andR. Further generalizations are introduced by substitutingR by a set ofR matrices,R _i ,i=1, ...r, which opens the way for formulating overlapping constraints as, e.g., in patterns that are both row- and column-conditional at the same time.     

Algebras and Matrices for Annotated Logics

We study the matrices, reduced matrices and algebras associated to the systems SA_T of structural annotated logics. In previous papers, these systems were proven algebraizable in the finitary case and the class of matrices analyzed here was proven to be a matrix semantics for them.We prove that the equivalent algebraic semantics associated with the systems SA_T are proper quasivarieties, we describe the reduced matrices, the subdirectly irreducible algebras and we give a general decomposition theorem. As a consequence we obtain a decision procedure for these logics.     

A concordance for wittgenstein's remarks on the foundations of mathematics

The numbering in the new edition of Wittgenstein's Remarks (MIT Press, 1983) does not in general correspond to the part and section numbers of the 1956 edition. The following concordance is useful for making cross references between the two editions.     

Degrees of maximality of Klukasiewicz-like sentential calculi

The paper is concerned with the problem of characterization of strengthenings of the so-called Lukasiewicz-like sentential calculi. The calculi under consideration are determined byn-valued Lukasiewicz matrices (n>2,n finite) with superdesignated logical values. In general. Lukasiewicz-like sentential calculi are not implicative in the sense of [7]. Despite of this fact, in our considerations we use matrices analogous toS-algebras of Rasiowa. The main result of the paper says that the degree of maximality of anyn-valued Lukasiewicz-like sentential calculus is finite and equal to the degree of maximality of the correspondingn-valued Lukasiewicz calculus. Allatum est die 15 Octobris 1976     

The Generalized DINA Model Framework

The G-DINA (generalized deterministic inputs, noisy “and” gate) model is a generalization of the DINA model with more relaxed assumptions. In its saturated form, the G-DINA model is equivalent to other general models for cognitive diagnosis based on alternative link functions. When appropriate constraints are applied, several commonly used cognitive diagnosis models (CDMs) can be shown to be special cases of the general models. In addition to model formulation, the G-DINA model as a general CDM framework includes a component for item-by-item model estimation based on design and weight matrices, and a component for item-by-item model comparison based on the Wald test. The paper illustrates the estimation and application of the G-DINA model as a framework using real and simulated data. It concludes by discussing several potential implications of and relevant issues concerning the proposed framework.