The Metric Bridge Partition Problem: Partitioning of a Metric Space into Two Subspaces Linked by an Edge in Any Optimal Realization

Let G = (V,E,w) be a graph with vertex and edge sets V and E, respectively, and w:E → R ⁺ a function which assigns a positive weight or length to each edge of G. G is called a realization of a finite metric space (M,d), with M = { 1,...,n} if and only if { 1,...,n} ⫅ V and d(i,j) is equal to the length of the shortest chain linking i and j in G ∀ i,j = 1,...,n. A realization G of (M,d), is said optimal if the sum of its weights is minimal among all the realizations of (M,d). Consider a partition of M into two nonempty subsets K and L, and let e be an edge in a realization G of (M,d); we say that e is a bridge linking K with L if e belongs to all chains in G linking a vertex of K with a vertex of L. The Metric Bridge Partition Problem is to determine if the elements of a finite metric space (M,d) can be partitioned into two nonempty subsets K and L such that all optimal realizations of (M,d) contain a bridge linking K with L. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of (M,d) from optimal realizations of (K,d|_K) and (L,d|_L).     

The weighted sum of split and diameter clustering

In this paper, we propose a bicriterion objective function for clustering a given set ofN entities, which minimizes [d–(1–)s], where 01, andd ands are the diameter and the split of the clustering, respectively. When =1, the problem reduces to minimum diameter clustering, and when =0, maximum split clustering. We show that this objective provides an effective way to compromise between the two often conflicting criteria. While the problem is NP-hard in general, a polynomial algorithm with the worst-case time complexityO(N ²) is devised to solve the bipartition version. This algorithm actually gives all the Pareto optimal bipartitions with respect to diameter and split, and it can be extended to yield an efficient divisive hierarchical scheme. An extension of the approach to the objective [(d ₁+d ₂)–2(1–)s] is also proposed, whered ₁ andd ₂ are diameters of the two clusters of a bipartition.This research was supported in part by the National Science and Engineering Research Council of Canada (Grant OGP 0104900). The authors wish to thank two anonymous referees, whose detailed comments on earlier drafts improved the paper.     

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.

     

Espaliers: A generalization of dendrograms

Dendrograms are widely used to represent graphically the clusters and partitions obtained with hierarchical clustering schemes. Espaliers are generalized dendrograms in which the length of horizontal lines is used in addition to their level in order to display the values of two characteristics of each cluster (e.g., the split and the diameter) instead of only one. An algorithm is first presented to transform a dendrogram into an espalier without rotation of any part of the former. This is done by stretching some of the horizontal lines to obtain a diagram with vertical and horizontal lines only, the cutting off by diagonal lines the parts of the horizontal lines exceeding their prescribed length. The problem of finding if, allowing rotations, no diagonal lines are needed is solved by anO(N ²) algorithm whereN is the number of entities to be classified. This algorithm is the generalized to obtain espaliers with minimum width and, possibly, some diagonal lines.Work of the first and second authors has been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) grant 92EQ1048, and grant N00014-92-J-1194 from the Office of Naval Research. Work of the first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) grant to École des Hautes Études Commerciales, Montréal and by NSERC grant GP0105574. Work of the second author has been supported by NSERC grant GP0036426, by FCAR grant 90NC0305, and by an NSF Professorship for Women in Science at Princeton University from September 1990 until December 1991. Work of the third author was done in part during a visit to GERAD, Montréal.     

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.     

Maximum sum-of-splits clustering

ConsiderN entities to be classified, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside it. The single-linkage algorithm provides partitions intoM clusters for which the smallest split is maximum. We study here the average split of the clusters or, equivalently, the sum of splits. A (N ²) algorithm is provided to determine maximum sum-of-splits partitions intoM clusters for allM betweenN – 1 and 2, using the dual graph of the single-linkage dendrogram.

---

Résumé SoientN objets à classifier et une matrice de dissimilarit és entre paires de ces objets. L'écart d'une classe est la plus petite dissimilarité entre un objet de cette classe et un objet en dehors d'elle. L'algorithme du lien simple fournit des partitions enM classes dont le plus petit écart est maximum. On étudie l'écart moyen des classes, ou, ce qui est équivalent, la somme des écarts. On propose un algorithme en (N ²) pour déterminer des partitions enM classes dont la somme des écarts est maximum pourM allant deN – 1 à 2, basé sur le graphe dual du dendrogramme de la méthode du lien simple.

     

绿蓝问题与简单性方案

绿蓝问题是假说选择问题的一种范型.科学假说精确的逻辑结构应该包含假说适用的情景和敏感因子.简单性标准是广为接受的一种假说选择标准,在运用到解决绿蓝问题时,提出了简单性的句法理论和语义理论.但这两种理论分别遭遇了对表达系统和概念框架的相对性,不能处理某些绿蓝型问题,甚至会陷入反直观境地的难题.     

果糖基生物质生物炼制中的基础科学问题

果聚糖是继蔗糖、淀粉之后,植物中第三大储藏性碳水化合物,是果糖的天然来源。利用富含果聚糖的生物质资源,开展基于果糖平台的生物炼制,是一个充满前景并具有挑战性的课题。深入研究基于果糖基生物质生物炼制中的基础科学问题,将有助于推动果糖基生物质生物炼制产业的发展,从而对我国的能源安全、粮食安全、生态安全以及和谐社会的建立产生积极的影响。     

从迪昂问题看证伪主义与历史主义之争

迪昂问题是从整体论的立场提出的，它论述的问题是：既然一个证据只能反驳一组假设。那么一个证据反驳某一单个假设如何可能？这一问题成为当代科学哲学争论的主题之一。波普尔、库恩和拉卡托斯之问的争论代表证伪主义与历史主义之间的争论，其理论都与迪昂问题密切相关，事实上，他们直接或间接地对迪昂问题给出不同的解答或对待。不过，他们的观点都是不能令人满意的。     

论知识定义的困境与转向

关于知识定义的传统分析自从葛梯尔问题出现之后就陷入了困境.反思"知道"与"知识"的区别,指出传统分析所体现的"主体-客体"二元认识模式的缺陷,从"知识的功能"角度反思"知识的条件是什么",从讨论和解决"知识是否具有客观有效性"、"客观有效性是否就是公共性"、"公共性是否是确证知识的合理条件"等问题,可为知识的准确定义提供新途径.     

从心-身问题看功能主义的困境

主流功能主义在心-身问题上试图保留物理主义的基本立场,但又反对把心理状态还原为物理状态。这种非还原的物理主义是以“多重实现”为事实根据的。金在权提出功能还原模型,并通过局部还原将多重实现化解为一重实现,进而转向还原的物理主义。然而,金在权的功能还原理论对于心灵哲学最为重要的研究对象即意识却是无能为力的。     

现代技术:问题与出路--论雅斯贝尔斯的技术观

作为存在主义哲学代表人物之一，尽管雅斯贝尔斯思想并未得到足够重视，特别地，作为其重要学术生长点的技术哲学思想，更需进一步挖掘。从历史文化动力学的新颖视角，雅斯贝尔斯对现代技术进行了存在主义反思，对技术问题做了深刻剖析，并对问题解决提出了独到见解。系统研究其技术思想具有重要意义。     

The Young-Householder algorithm and the least squares multidimensional scaling of squared distances

It is shown that replacement of the zero diagonal elements of the symmetric data matrix of approximate squared distances by certain other quantities in the Young-Householder algorithm will yield a least squares fit to squared distances instead of to scalar products. Iterative algorithms for obtaining these replacement diagonal elements are described and relationships with the ELEGANT algorithm (de Leeuw 1975; Takane 1977) are discussed. In large residual situations a penalty function approach, motivated by the ELEGANT algorithm, is adopted. Empirical comparisons of the algorithms are given.An early version of this paper was presented at the Multidimensional Data Analysis Workshop, Pembroke College, Cambridge, July 1985. I want to thank Jan de Leeuw and Yoshio Takane for bringing the ELEGANT algorithm to my attention and for clarifying its rationale and notation. My thanks go also to Stephen du Toit for help with the ALSCAL computations reported in Section 7.     

"世界"是如何可能的?--论康德通过世界问题为科学奠基的策略

"世界"问题是哲学追问的核心问题,因为人类的一切思想活动和实践活动都立足于其在世界中的存在.康德改变了提问方式,追问世界是如何对我们显现的,追问对于我们而言"世界是如何可能的".康德认为感性世界的可能性在于先天纯直观形式与物自体刺激相结合,知性世界的可能性在于范畴对于感性知识的加工.前者是数学作为一门科学的合法性所在,而后者是自然科学作为科学的合法性所在.     

从整体辩护到局部策略——归纳问题解决思路的转变及哲学反思

归纳问题是归纳逻辑中的根基性问题,对它的解决经历了从整体辩护到局部策略,再向新的整体辩护复苏的思路转变。归纳问题至今依然存在。必须对之进行深刻的哲学反思,才能推动问题的相对解决和归纳逻辑的进一步发展。     

The generation of random ultrametric matrices representing dendrograms

Many methods and algorithms to generate random trees of many kinds have been proposed in the literature. No procedure exists however for the generation of dendrograms with randomized fusion levels. Randomized dendrograms can be obtained by randomizing the associated cophenetic matrix. Two algorithms are described. The first one generates completely random dendrograms, i.e., trees with a random topology, random fusion level values, and random assignment of the labels. The second algorithm uses a double-permutation procedure to randomize a given dendrogram; it proceeds by randomization of the fixed fusion levels, instead of using random fusion level values. A proof is presented that the double-permutation procedure is a Uniform Random Generation Algorithmsensu Furnas (1984), and a complete example is given. This work was supported by NSERC Grant No. A7738 to P. Legendre and by a NSERC scholarship to F.-J. Lapointe.