Intelligent Choice of the Number of Clusters in K-Means Clustering: An Experimental Study with Different Cluster Spreads

The issue of determining “the right number of clusters” in K-Means has attracted considerable interest, especially in the recent years. Cluster intermix appears to be a factor most affecting the clustering results. This paper proposes an experimental setting for comparison of different approaches at data generated from Gaussian clusters with the controlled parameters of between- and within-cluster spread to model cluster intermix. The setting allows for evaluating the centroid recovery on par with conventional evaluation of the cluster recovery. The subjects of our interest are two versions of the “intelligent” K-Means method, ik-Means, that find the “right” number of clusters by extracting “anomalous patterns” from the data one-by-one. We compare them with seven other methods, including Hartigan’s rule, averaged Silhouette width and Gap statistic, under different between- and within-cluster spread-shape conditions. There are several consistent patterns in the results of our experiments, such as that the right K is reproduced best by Hartigan’s rule – but not clusters or their centroids. This leads us to propose an adjusted version of iK-Means, which performs well in the current experiment setting.     

The Arrow of Time and Meaning

All the attempts to find the justification of the privileged evolution of phenomena exclusively in the external world need to refer to the inescapable fact that we are living in such an asymmetric universe. This leads us to look for the origin of the “arrow of time” in the relationship between the subject and the world. The anthropic argument shows that the arrow of time is the condition of the possibility of emergence and maintenance of life in the universe. Moreover, according to Bohr’s, Poincaré’s and Watanabe’s analysis, this agreement between the earlier-later direction of entropy increase and the past-future direction of life is the very condition of the possibility for meaningful action, representation and creation. Beyond this relationship of logical necessity between the meaning process and the arrow of time the question of their possible physical connection is explored. To answer affirmatively to this question, the meaning process is modelled as an evolving tree-like structure, called “Semantic Time”, where thermodynamic irreversibility can be shown. Time is the substance I am made of. Time is a river which sweeps me along, but I am the river ; it is a tiger which destroys me, but I am the tiger ; it is a fire which consumes me, but I am the fire. – (Jorge Luis Borges)     

Minimum sum of diameters clustering

The problem of determining a partition of a given set ofN entities intoM clusters such that the sum of the diameters of these clusters is minimum has been studied by Brucker (1978). He proved that it is NP-complete forM3 and mentioned that its complexity was unknown forM=2. We provide anO(N ³ logN) algorithm for this latter case. Moreover, we show that determining a partition into two clusters which minimizes any given function of the diameters can be done inO(N ⁵) time.Acknowledgments: This research was supported by the Air Force Office of Scientific Research Grant AFOSR 0271 to Rutgers University. We are grateful to Yves Crama for several insightful remarks and to an anonymous referee for detailed comments.     

The Constructive Realist Account of Science and Its Application to Ilya Prigogine’s Conception of Laws of Nature

Sciences are often regarded as providing the best, or, ideally, exact, knowledge of the world, especially in providing laws of nature. Ilya Prigogine, who was awarded the Nobel Prize for his theory of non-equilibrium chemical processes—this being also an important attempt to bridge the gap between exact and non-exact sciences [mentioned in the Presentation Speech by Professor Stig Claesson (nobelprize.org, The Nobel Prize in Chemistry 1977)]—has had this ideal in mind when trying to formulate a new kind of science. Philosophers of science distinguish theory and reality, examining relations between these two. Nancy Cartwright’s distinction of fundamental and phenomenological laws, Rein Vihalemm’s conception of the peculiarity of the exact sciences, and Ronald Giere’s account of models in science and science as a set of models are deployed in this article to criticise the common view of science and analyse Ilya Prigogine’s view in particular. We will conclude that on a more abstract, philosophical level, Prigogine’s understanding of science doesn’t differ from the common understanding.

On the Discrepancy Measures for the Optimal Equal Probability Partitioning in Bayesian Multivariate Micro-Aggregation

Data holders, such as statistical institutions and financial organizations, have a very serious and demanding task when producing data for official and public use. It’s about controlling the risk of identity disclosure and protecting sensitive information when they communicate data-sets among themselves, to governmental agencies and to the public. One of the techniques applied is that of micro-aggregation. In a Bayesian setting, micro-aggregation can be viewed as the optimal partitioning of the original data-set based on the minimization of an appropriate measure of discrepancy, or distance, between two posterior distributions, one of which is conditional on the original data-set and the other conditional on the aggregated data-set. Assuming d-variate normal data-sets and using several measures of discrepancy, it is shown that the asymptotically optimal equal probability m-partition of , with m ^1/d ∈ , is the convex one which is provided by hypercubes whose sides are formed by hyperplanes perpendicular to the canonical axes, no matter which discrepancy measure has been used. On the basis of the above result, a method that produces a sub-optimal partition with a very small computational cost is presented. Published online xx, xx, xxxx.     

Efficient algorithms for divisive hierarchical clustering with the diameter criterion

Divisive hierarchical clustering algorithms with the diameter criterion proceed by recursively selecting the cluster with largest diameter and partitioning it into two clusters whose largest diameter is smallest possible. We provide two such algorithms with complexitiesO( N ²) andO(N ²logN) respectively, where denotes the maximum number of clusters in a partition andN the number of entities to be clustered. The former algorithm, an efficient implementation of an algorithm of Hubert, allows to find all partitions into at most clusters and is inO(N ²) for fixed . Moreover, if in each partitioning the size of the largest cluster is bounded byp times the number of entities in the set to be partitioned, with 1/2<=p<1, it provides a complete hierarchy of partitionsO(N ² logN) time. The latter algorithm, a refinement of an algorithm of Rao allows to build a complete hierarchy of partitions inO(N ² logN) time without any restriction. Comparative computational experiments with both algorithms and with an agglomerative hierarchical algorithm of Benzécri are reported.

---

Résumé Les algorithmes de classification hiérarchique descendante utilisant le critère du diamètre, sélectionnent récursivement la classe de plus grand diamètre et la partitionnent en deux classes, dont le plus grand diamètre est le plus, petit possible. Nous proposons deux tels algorithmes, avec des complexités enO ( N²) etO(N ² logN) respectivement, où désigne le nombre maximum de classes d'une partition etN le nombre d'objets à classifier. Le premier algorithme, une implantation d'un algorithme de Hubert, permet de construire des partitions avec au plus classes et est enO(N ²) pour fixé. De plus, si dans chaque bipartition le nombre d'objets de la plus grande classe, est borné parp fois le nombre d'objets de l'ensemble à partitionner, où 1/2≤p<1, cet algorithme permet de construire une hiérarchie complète de partitions en tempsO(N ² logN). Le second algorithme, un raffinement d'un algorithme de Rao, permet de construire une hiérarchie complète de partitions en tempsO(N ² logN) sans aucune restriction On présente également des résultats de calcul comparatifs pour les deux algorithmes et pour l'algorithme de classification hiérarchique ascendante de Benzécri.

     

Optimization Strategies for Two-Mode Partitioning

Two-mode partitioning is a relatively new form of clustering that clusters both rows and columns of a data matrix. In this paper, we consider deterministic two-mode partitioning methods in which a criterion similar to k-means is optimized. A variety of optimization methods have been proposed for this type of problem. However, it is still unclear which method should be used, as various methods may lead to non-global optima. This paper reviews and compares several optimization methods for two-mode partitioning. Several known methods are discussed, and a new fuzzy steps method is introduced. The fuzzy steps method is based on the fuzzy c-means algorithm of Bezdek (1981) and the fuzzy steps approach of Heiser and Groenen (1997) and Groenen and Jajuga (2001). The performances of all methods are compared in a large simulation study. In our simulations, a two-mode k-means optimization method most often gives the best results. Finally, an empirical data set is used to give a practical example of two-mode partitioning. We would like to thank two anonymous referees whose comments have improved the quality of this paper. We are also grateful to Peter Verhoef for providing the data set used in this paper.     

Axiomatization and Models of Scientific Theories

In this paper we discuss two approaches to the axiomatization of scientific theories in the context of the so called semantic approach, according to which (roughly) a theory can be seen as a class of models. The two approaches are associated respectively to Suppes’ and to da Costa and Chuaqui’s works. We argue that theories can be developed both in a way more akin to the usual mathematical practice (Suppes), in an informal set theoretical environment, writing the set theoretical predicate in the language of set theory itself or, more rigorously (da Costa and Chuaqui), by employing formal languages that help us in writing the postulates to define a class of structures. Both approaches are called internal, for we work within a mathematical framework, here taken to be first-order ZFC. We contrast these approaches with an external one, here discussed briefly. We argue that each one has its strong and weak points, whose discussion is relevant for the philosophical foundations of science.     

Inventing Electric Potential

Investigations with electrometers in the 1770s led Volta to envision mobile charge in electrical conductors as a compressible fluid. A pressure-like condition in this fluid, which Volta described as the fluid’s “effort to push itself out” of its conducting container, was the causal agent that makes the fluid move. In this paper I discuss Volta’s use of analogy and imagery in model building, and compare with a successful contemporary conceptual approach to introducing ideas about electric potential in instruction. The concept that today is called “electric potential” was defined mathematically by Poisson in 1811. It was understood after about 1850 to predict the same results in conducting matter as Volta’s pressure-like concept—and to predict electrostatic effects in the exterior space where Volta’s concept had nothing to say. Complete quantification in addition to greater generality made the mathematical concept a superior research tool for scientists. However, its spreading use in instruction has marginalized approaches to model building based on the analogy and imagery resources that students bring into the classroom. Data from pre and post testing in high schools show greater conceptual and confidence gains using the new conceptual approach than using conventional instruction. This provides evidence for reviving Volta’s compressible fluid model as an intuitive foundation which can then be modified to include electrostatic distant action. Volta tried to modify his compressible fluid model to include distant action, using imagery borrowed from distant heating by a flame. This project remained incomplete, because he did not envision an external field mediating the heating. However, pursuing Volta’s strategy of model modification to completion now enables students taught with the new conceptual approach to add distant action to an initial compressible fluid model. I suggest that a partial correspondence to the evolving model sequence that works for beginning students can help illuminate Volta’s use of intermediate explanatory models.

<Emphasis Type="Italic">k</Emphasis>-Adic Similarity Coefficients for Binary (Presence/Absence) Data

k-Adic formulations (for groups of objects of size k) of a variety of 2-adic similarity coefficients (for pairs of objects) for binary (presence/absence) data are presented. The formulations are not functions of 2-adic similarity coefficients. Instead, the main objective of the the paper is to present k-adic formulations that reflect certain basic characteristics of, and have a similar interpretation as, their 2-adic versions. Two major classes are distinguished. The first class is referred to as Bennani-Heiser similarity coefficients, which contains all coefficients that can be defined using just the matches, the number of attributes that are present and that are absent in k objects, and the total number of attributes. The coefficients in the second class can be formulated as functions of Dice’s association indices. The author thanks Willem Heiser and three anonymous reviewers for their helpful comments and valuable suggestions on earlier versions of this article.     

Handling Missing Values with Regularized Iterative Multiple Correspondence Analysis

A common approach to deal with missing values in multivariate exploratory data analysis consists in minimizing the loss function over all non-missing elements, which can be achieved by EM-type algorithms where an iterative imputation of the missing values is performed during the estimation of the axes and components. This paper proposes such an algorithm, named iterative multiple correspondence analysis, to handle missing values in multiple correspondence analysis (MCA). The algorithm, based on an iterative PCA algorithm, is described and its properties are studied. We point out the overfitting problem and propose a regularized version of the algorithm to overcome this major issue. Finally, performances of the regularized iterative MCA algorithm (implemented in the R-package named missMDA) are assessed from both simulations and a real dataset. Results are promising with respect to other methods such as the missing-data passive modified margin method, an adaptation of the missing passive method used in Gifi’s Homogeneity analysis framework.     

Friends of Wisdom?

This commentary addresses the question of the meaning of critique in relation to objectivism or dogmatism. Inspired by Kant’s critical philosophy and Husserl’s phenomenology, it defines the first in terms of conditionality, the second in terms of oppositionality. It works out an application on the basis of Salthe’s (Found Sci 15 4(6):357–367, 2010a) paper on development and evolution, where competition is criticized in oppositional, more than in conditional terms.     

A Theory of Scientific Model Construction: <Emphasis Type="Italic">The Conceptual Process of Abstraction and Concretisation</Emphasis>

The process of abstraction and concretisation is a label used for an explicative theory of scientific model-construction. In scientific theorising this process enters at various levels. We could identify two principal levels of abstraction that are useful to our understanding of theory-application. The first level is that of selecting a small number of variables and parameters abstracted from the universe of discourse and used to characterise the general laws of a theory. In classical mechanics, for example, we select position and momentum and establish a relation amongst the two variables, which we call Newton’s 2nd law. The specification of the unspecified elements of scientific laws, e.g. the force function in Newton’s 2nd law, is what would establish the link between the assertions of the theory and physical systems. In order to unravel how and with what conceptual resources scientific models are constructed, how they function and how they relate to theory, we need a view of theory-application that can accommodate our constructions of representation models. For this we need to expand our understanding of the process of abstraction to also explicate the process of specifying force functions etc. This is the second principal level at which abstraction enters in our theorising and in which I focus. In this paper, I attempt to elaborate a general analysis of the process of abstraction and concretisation involved in scientific- model construction, and argue why it provides an explication of the construction of models of the nuclear structure.     

On the Foundations of Constructive Mathematics – Especially in Relation to the Theory of Continuous Functions

We discuss the foundations of constructive mathematics, including recursive mathematics and intuitionism, in relation to classical mathematics. There are connections with the foundations of physics, due to the way in which the different branches of mathematics reflect reality. Many different axioms and their interrelationship are discussed. We show that there is a fundamental problem in BISH (Bishop’s school of constructive mathematics) with regard to its current definition of ‘continuous function’. This problem is closely related to the definition in BISH of ‘locally compact’. Possible approaches to this problem are discussed. Topology seems to be a key to understanding many issues. We offer several new simplifying axioms, which can form bridges between the various branches of constructive mathematics and classical mathematics (‘reuniting the antipodes’). We give a simplification of basic intuitionistic theory, especially with regard to so-called ‘bar induction’. We then plead for a limited number of axiomatic systems, which differentiate between the various branches of mathematics. Finally, in the appendix we offer BISH an elegant topological definition of ‘locally compact’, which unlike the current definition is equivalent to the usual classical and/or intuitionistic definition in classical and intuitionistic mathematics, respectively.     

Seeking Allies: Modelling How Listeners Choose Their Musical Friends

In this paper we describe in some detail a formal computer model of inferential discourse based on a belief system. The key issue is that a logical model in a computer, based on rational sets, can usefully model a human situation based on irrational sets. The background of this work is explained elsewhere, as is the issue of rational and irrational sets (Billinge and Addis, in: Magnani and Dossena (eds.), Computing, philosophy and cognition, 2004; Stepney et al., Journey: Non-classical philosophy—socially sensitive computing in journeys non-classical computation: A grand challenge for computing research, 2004). The model is based on the Belief System (Addis and Gooding, Proceedings of the AISB’99 Symposium on Scientific Creativity, 1999) and it provides a mechanism for choosing queries based on a range of belief. We explain how it provides a way to update the belief based on query results, thus modelling others’ experience by inference. We also demonstrate that for the same internal experience, different models can be built for different actors.

The Future of Life and What it Means for Humanity

Vidal’s (Found Sci, 2010) and Rottiers’s (Found Sci, 2010) commentaries on my (2010) paper raised a number of important issues about the possible future trajectory of evolution and its implications for humanity. My response emphasizes that despite the inherent uncertainty involved in extrapolating the trajectory of evolution into the far future, the possibilities it reveals nonetheless have significant strategic implications for what we do with our lives here and now, individually and collectively. One important implication is the replacement of postmodern scepticism and relativism with an evolutionary grand narrative that can guide humanity to participate successfully in the future evolution of life in the universe.     

Symmetries and Symmetry-Breakings: The Fabric of Physical Interactions and the Flow of Time

This short note develops some ideas along the lines of the stimulating paper by Heylighen (Found Sci 15 4(3):345–356, 2010a). It summarizes a theme in several writings with Francis Bailly, downloadable from this author’s web page. The “geometrization” of time and causality is the common ground of the analysis hinted here and in Heylighen’s paper. Heylighen adds a logical notion, consistency, in order to understand a possible origin of the selective process that may have originated this organization of natural phenomena. We will join our perspectives by hinting to some gnoseological complexes, common to mathematics and physics, which may shed light on the issues raised by Heylighen.     

Embodied Anomaly Resolution in Molecular Genetics: A Case Study of RNAi

Scientific anomalies are observations and facts that contradict current scientific theories and they are instrumental in scientific theory change. Philosophers of science have approached scientific theory change from different perspectives as Darden (Theory change in science: Strategies from Mendelian genetics, 1991) observes: Lakatos (In: Lakatos, Musgrave (eds) Criticism and the growth of knowledge, 1970) approaches it as a progressive “research programmes” consisting of incremental improvements (“monster barring” in Lakatos, Proofs and refutations: The logic of mathematical discovery, 1976), Kuhn (The structure of scientific revolutions, 1996) observes that changes in “paradigms” are instigated by a crisis from some anomaly, and Hanson (In: Feigl, Maxwell (eds) Current issues in the philosophy of science, 1961) proposes that discovery does not begin with hypothesis but with some “problematic phenomena requiring explanation”. Even though anomalies are important in all of these approaches to scientific theory change, there have been only few investigations into the specific role anomalies play in scientific theory change. Furthermore, much of these approaches focus on the theories themselves and not on how the scientists and their experiments bring about scientific change (Gooding, Experiment and the making of meaning: Human agency in scientific observation and experiment, 1990). To address these issues, this paper approaches scientific anomaly resolution from a meaning construction point of view. Conceptual integration theory (Fauconnier and Turner, Cogn Sci 22:133–187, 1996; The way we think: Conceptual blending and mind’s hidden complexities, 2002) from cognitive linguistics describes how one constructs meaning from various stimuli, such as text and diagrams, through conceptual integration or blending. The conceptual integration networks that describe the conceptual integration process characterize cognition that occurs unconsciously during meaning construction. These same networks are used to describe some of the cognition while resolving an anomaly in molecular genetics called RNA interference (RNAi) in a case study. The RNAi case study is a cognitive-historical reconstruction (Nersessian, In: Giere (ed) Cognitive models of science, 1992) that reconstructs how the RNAi anomaly was resolved. This reconstruction traces four relevant molecular genetics publications in describing the cognition necessary in accounting for how RNAi was resolved through strategies (Darden 1991), abductive reasoning (Peirce, In: Hartshorne, Weiss (eds) Collected papers, 1958), and experimental reasoning (Gooding 1990). The results of the case study show that experiments play a crucial role in formulating an explanation of the RNAi anomaly and the integration networks describe the experiments’ role. Furthermore, these results suggest that RNAi anomaly resolution is embodied. It is embodied in a sense that cognition described in the cognitive-historical reconstruction is experientially based.

Algorithms for ℓ<Subscript>1</Subscript>-Embeddability and Related Problems

Assouad has shown that a real-valued distance d = (d_ij)_{1 ≤ i < j ≤ n} is isometrically embeddable in ℓ₁space if and only if it belongs to the cut cone on n points. Determining if this condition holds is NP-complete. We use Assouad's result in a constructive column generation algorithm for ℓ₁-embeddability. The subproblem is an unconstrained 0-1 quadratic program, solved by Tabu Search and Variable Neighborhood Search heuristics as well as by an exact enumerative algorithm. Computational results are reported. Several ways to approximate a distance which is not ℓ₁-embeddable by another one which is are also studied.