The input of most clustering algorithms is a symmetric matrix quantifying similarity within data pairs. Such a matrix is here turned into a quadratic set function measuring cluster score or similarity within data subsets larger than pairs. In general, any set function reasonably assigning a cluster score to data subsets gives rise to an objective function-based clustering problem. When considered in pseudo-Boolean form, cluster score enables to evaluate fuzzy clusters through multilinear extension MLE, while the global score of fuzzy clusterings simply is the sum over constituents fuzzy clusters of their MLE score. This is shown to be no greater than the global score of hard clusterings or partitions of the data set, thereby expanding a known result on extremizers of pseudo-Boolean functions. Yet, a multilinear objective function allows to search for optimality in the interior of the hypercube. The proposed method only requires a fuzzy clustering as initial candidate solution, for the appropriate number of clusters is implicitly extracted from the given data set.
Clustering is here approached by firstly quantifying the cluster score of every non-empty data subset, and secondly in terms of the associated set partitioning combinatorial optimization problem @cite_23 . Cluster score thus is a set function or, geometrically, a point in @math , and rather than measuring a cost (or sum of distances) to be minimized (see above), it measures a worth to be maximized. The idea is to quantify, for every data subset, both internal similarity and dissimilarity with respect to its complement. This resembles the in information-based clustering @cite_8 . Objective function-based clustering intrisically relies on the assumption that every data subset has an associated real-valued worth (or, alternatively, a cost). A main novelty proposed below is to deal with both hard and fuzzy clusters at once by means of the pseudo-Boolean form of set functions. In order to have the same input as in many clustering algorithms, the basic cluster score function provided in the next section obtains from a given similarity matrix, and has polynomial MLE of degree 2 [pp. 157, 162] BorosHammer02 . This also keeps the computational burden at a seemingly reasonable level.
@cite_23 @cite_8
1557310162 1966168239
This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. It contains complete but concise proofs, also for many deep results, some of which did not appear in a textbook before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state of the art of combinatorial optimization. This fourth edition is again significantly extended, most notably with new material on linear programming, the network simplex algorithm, and the max-cut problem. Many further additions and updates are included as well. From the reviews of the previous editions: "This book on combinatorial optimization is a beautiful example of the ideal textbook." Operations Research Letters 33 (2005), p.216-217 "The second edition (with corrections and many updates) of this very recommendable book documents the relevant knowledge on combinatorial optimization and records those problems and algorithms that define this discipline today. To read this is very stimulating for all the researchers, practitioners, and students interested in combinatorial optimization." OR News 19 (2003), p.42 "... has become a standard textbook in the field." Zentralblatt MATH 1099.90054 In an age of increasingly large data sets, investigators in many different disciplines have turned to clustering as a tool for data analysis and exploration. Existing clustering methods, however, typically depend on several nontrivial assumptions about the structure of data. Here, we reformulate the clustering problem from an information theoretic perspective that avoids many of these assumptions. In particular, our formulation obviates the need for defining a cluster “prototype,” does not require an a priori similarity metric, is invariant to changes in the representation of the data, and naturally captures nonlinear relations. We apply this approach to different domains and find that it consistently produces clusters that are more coherent than those extracted by existing algorithms. Finally, our approach provides a way of clustering based on collective notions of similarity rather than the traditional pairwise measures.