Hierarchical classes: Model and data analysis

A discrete, categorical model and a corresponding data-analysis method are presented for two-way two-mode (objects × attributes) data arrays with 0, 1 entries. The model contains the following two basic components: a set-theoretical formulation of the relations among objects and attributes; a Boolean decomposition of the matrix. The set-theoretical formulation defines a subset of the possible decompositions as consistent with it. A general method for graphically representing the set-theoretical decomposition is described. The data-analysis algorithm, dubbed HICLAS, aims at recovering the underlying structure in a data matrix by minimizing the discrepancies between the data and the recovered structure. HICLAS is evaluated with a simulation study and two empirical applications.This research was supported in part by a grant from the Belgian NSF (NFWO) to Paul De Boeck and in part by NSF Grant BNS-83-01027 to Seymour Rosenberg. We thank Iven Van Mechelen for clarifying several aspects of the Boolean algebraic formulation of the model and Phipps Arabie for his comments on an earlier draft.     

On three arguments against categorical structuralism

Some mathematicians and philosophers contend that set theory plays a foundational role in mathematics. However, the development of category theory during the second half of the twentieth century has encouraged the view that this theory can provide a structuralist alternative to set-theoretical foundations. Against this tendency, criticisms have been made that category theory depends on set-theoretical notions and, because of this, category theory fails to show that set-theoretical foundations are dispensable. The goal of this paper is to show that these criticisms are misguided by arguing that category theory is entirely autonomous from set theory.     

Some applications of graph theory to clustering

This paper attempts to review and expand upon the relationship between graph theory and the clustering of a set of objects. Several graphtheoretic criteria are proposed for use within a general clustering paradigm as a means of developing procedures in between the extremes of complete-link and single-link hierarchical partitioning; these same ideas are then extended to include the more general problem of constructing subsets of objects with overlap. Finally, a number of related topics are surveyed within the general context of reinterpreting and justifying methods of clustering either through standard concepts in graph theory or their simple extensions.     

Axiomatization of certain problems of minimization

Summary In Part I of this paper, an abstract analogue of the minimization problem for Boolean functions and of the notion of prime implicant is defined, so that this general problem can be solved in the same steps as in the classical case: 1) determination of the prime implicants; 2) determination ofall the solutions made up of prime implicants. In Part II it is shown that the classical minimization problem, as well as certain set-theoretical and graphtheoretical problems are particular cases of the general problem defined in Part I. Allatum est die 27 Novembris1965     

Compact integer-programming models for extracting subsets of stimuli from confusion matrices

This paper presents an integer linear programming formulation for the problem of extracting a subset of stimuli from a confusion matrix. The objective is to select stimuli such that total confusion among the stimuli is minimized for a particular subset size. This formulation provides a drastic reduction in the number of variables and constraints relative to a previously proposed formulation for the same problem. An extension of the formulation is provided for a biobjective problem that considers both confusion and recognition in the objective function. Demonstrations using an empirical interletter confusion matrix from the psychological literature revealed that a commercial branch-and-bound integer programming code was always able to identify optimal solutions for both the single-objective and biobjective formulations within a matter of seconds. A further extension and demonstration of the model is provided for the extraction of multiple subsets of stimuli, wherein the objectives are to maximize similarity within subsets and minimize similarity between subsets.     

Nonmetric grouping: Clusters and cliques

A class of related nonmetric (“monotone invariant”) hierarchical grouping methods is presented. The methods are defined in terms of generalized cliques, based on a systematically varying specification of the degree of indirectness of permitted relationships (i.e., degree of “chaining”). This approach to grouping is shown to provide a useful framework for grouping methods based on ana priori specification of the properties of the desired subsets, and includes a natural generalization for “complete linkage” and “single linkage” clustering, such as the methods of Johnson [1967]. The central feature of the class of methods is a simple iterative matrix operation on the original disparities (“inverse-proximities” or “dissimilarities”) matrix, and one of the methods also constitutes a very efficient single linkage clustering procedure.     

Elementary Particles,Hidden Variables,And Hidden Predicates

We recently showed that it is possible to deal withcollections of indistinguishable elementary particles (in thecontext of quantum mechanics) in a set-theoretical framework, byusing hidden variables. We propose in the presentpaper another axiomatics for collections of indiscernibleswithout hidden variables, where hidden predicates are implicitlyassumed. We also discuss the possibility of a quasi-settheoretical picture for quantum theory. Quasi-set theory, basedon Zermelo-Fraenkel set theory, was developed for dealing withcollections of indistinguishable, but, not identical objects.     

An evaluation of exact methods for the multiple subset maximum cardinality selection problem

The maximum cardinality subset selection problem requires finding the largest possible subset from a set of objects, such that one or more conditions are satisfied. An important extension of this problem is to extract multiple subsets, where the addition of one more object to a larger subset would always be preferred to increases in the size of one or more smaller subsets. We refer to this as the multiple subset maximum cardinality selection problem (MSMCSP). A recently published branch‐and‐bound algorithm solves the MSMCSP as a partitioning problem. Unfortunately, the computational requirement associated with the algorithm is often enormous, thus rendering the method infeasible from a practical standpoint. In this paper, we present an alternative approach that successively solves a series of binary integer linear programs to obtain a globally optimal solution to the MSMCSP. Computational comparisons of the methods using published similarity data for 45 food items reveal that the proposed sequential method is computationally far more efficient than the branch‐and‐bound approach.     

A geometric counterpart to Tversky's set-theoretic model of similarity

It is shown that Junge's (1978) geometric similarity model corresponds to Tversky's set-theoretical model of similarity.     

Measures of kearnels of reducibility axioms and singlets

The present paper is a generalization and further development of the theory of Kernel measures of reducibility axioms formulated in [1], [2], [3] in. the years 1969–1973. In this paper logical connections of Kernel measures with some set-theoretical notions are studied and some suggestions related to these connections are formulated.     

A choice model for paired comparison data based on imperfectly nested sets

A ratio scale of subjective magnitude is developed from paired-comparison data. The model attempts to combine arguments of Restle, Ekman, and Luce relating data obtained from paired comparisons and corresponding data from direct psychophysical scaling methods at the ratio level. The basic set-theoretical model involves the use of imperfectly nested sets. A numerical example illustrates the application of the theory.This research was supported by the Swedish Social Science Research Council and by the Swedish Board of Computing Machinery. I am indebted to Mr. U. Forsberg for computational assistance.     

Clustering, seriation, and subset extraction of confusion data

The study of confusion data is a well established practice in psychology. Although many types of analytical approaches for confusion data are available, among the most common methods are the extraction of 1 or more subsets of stimuli, the partitioning of the complete stimulus set into distinct groups, and the ordering of the stimulus set. Although standard commercial software packages can sometimes facilitate these types of analyses, they are not guaranteed to produce optimal solutions. The authors present a MATLAB *.m file for preprocessing confusion matrices, which includes fitting of the similarity-choice model. Two additional MATLAB programs are available for optimally clustering stimuli on the basis of confusion data. The authors also developed programs for optimally ordering stimuli and extracting subsets of stimuli using information from confusion matrices. Together, these programs provide several pragmatic alternatives for the applied researcher when analyzing confusion data. Although the programs are described within the context of confusion data, they are also amenable to other types of proximity data.     

A Dynamic Characterization of the Pure Logic of Relevant Implication

This paper spells out a dynamic proof format for the pure logic of relevant implication. (A proof is dynamic if a formula derived at some stage need not be derived at a later stage.) The paper illustrates three interesting points. (i) A set of properties that characterizes an inference relation on the (very natural) dynamic proof interpretation, need not characterize the same inference relation (or even any inference relation) on the usual set-theoretical interpretation. (ii) A proof format may display an internal dynamics (defeasible conclusions) in the absence of an external dynamics (non-monotonicity). (iii) A monotonic logic may have a non-monotonic characterization.     

On Hodgkin and Huxley's theory of excitable membranes

Using Sneed's metatheory an attempt is made to reconstruct Hodgkin and Huxley's theory of excitation of cell membranes. The structure of this theory is uncovered by defining set-theoretical predicates for the partial potential models, potential models, and models of the theory. The function of permeability is said to be the only theoretical function with respect to this theory. The main underlying assumptions of the theory are briefly outlined.     

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.     

Representations of qualitative and quantitative dimensions

Geometric representations of psychological dimensions are analyzed and compared to an alternative set-theoretical approach. Judgments of similarity between forms and figures reveal the following effects: (a) qualitative attributes are curved relative to quantitative attributes, contrary to intradimensional subtractivity; (b) quantitative attributes augment differences in qualitative attributes, contrary to interdimensional additivity; (c) adding a new dimension with a fixed value increases similarity, contrary to translation invariance. The implications of these results to multidimensional representations of proximity data are discussed.     

Indclas: A three-way hierarchical classes model

A three-way three-mode extension of De Boeck and Rosenberg's (1988) two-way two-mode hierarchical classes model is presented for the analysis of individual differences in binary object × attribute arrays. In line with the two-way hierarchical classes model, the three-way extension represents both the association relation among the three modes and the set-theoretical relations among the elements of each model. An algorithm for fitting the model is presented and evaluated in a simulation study. The model is illustrated with data on psychiatric diagnosis. Finally, the relation between the model and extant models for three-way data is discussed.The research reported in this paper was partially supported by NATO (Grant CRG.921321 to Iven Van Mechelen and Seymour Rosenberg).     

Mathematical Intuition Vs. Mathematical Monsters*

Geometrical and physical intuition, both untutored andcultivated, is ubiquitous in the research, teaching,and development of mathematics. A number ofmathematical ``monsters', or pathological objects, havebeen produced which – according to somemathematicians – seriously challenge the reliability ofintuition. We examine several famous geometrical,topological and set-theoretical examples of suchmonsters in order to see to what extent, if at all,intuition is undermined in its everyday roles.     

Some types of clustering with relational constraints

For the clustering problem with general (not necessarily symmetric) relational constraints, different sets of feasible clusterings, also called clustering types, determined by the same relation, can be defined. In this paper some clustering types are discussed and adaptations of the hierarchical clustering method compatible with these clustering types are proposed.