On soft power diagrams

DOI10.1007/S10852-014-9263-YzbMATH Open1327.90406arXiv1307.3949OpenAlexW2963042458MaRDI QIDQ894534FDOQ894534

N. E. Zubov

Publication date: 1 December 2015

Published in: Journal of Mathematical Modelling and Algorithms in Operations Research (Search for Journal in Brave)

Abstract: Many applications in data analysis begin with a set of points in a Euclidean space that is partitioned into clusters. Common tasks then are to devise a classifier deciding which of the clusters a new point is associated to, finding outliers with respect to the clusters, or identifying the type of clustering used for the partition. One of the common kinds of clusterings are (balanced) least-squares assignments with respect to a given set of sites. For these, there is a 'separating power diagram' for which each cluster lies in its own cell. In the present paper, we aim for efficient algorithms for outlier detection and the computation of thresholds that measure how similar a clustering is to a least-squares assignment for fixed sites. For this purpose, we devise a new model for the computation of a 'soft power diagram', which allows a soft separation of the clusters with 'point counting properties'; e.g. we are able to prescribe how many points we want to classify as outliers. As our results hold for a more general non-convex model of free sites, we describe it and our proofs in this more general way. Its locally optimal solutions satisfy the aforementioned point counting properties. For our target applications that use fixed sites, our algorithms are efficiently solvable to global optimality by linear programming.

Full work available at URL: https://arxiv.org/abs/1307.3949

Recommendations

• Soft power: upgrading chain macroeconomic policy through soft forks
• scientific article; zbMATH DE number 2169341
• Remarks on power structures
• scientific article; zbMATH DE number 3932826
• Power, cooperation indices and coalition structures
• On the power of simple diagrams
• Soft nexuses
• On soft mappings
• scientific article; zbMATH DE number 975325

zbMATH Keywords

linear programmingmachine learningoperations researchleast-squares assignmentspower diagramssoft-margin separation

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Applications of mathematical programming (90C90) Computational learning theory (68Q32)

Cites Work

• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Support-vector networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minkowski-type theorems and least-squares clustering
• Power Diagrams: Properties, Algorithms and Applications
• Multicategory classification by support vector machines
• 10.1162/15324430260185628
• Multiobjective Multiclass Soft-Margin Support Vector Machine and Its Solving Technique Based on Benson’s Method
• On optimal weighted balanced clusterings: gravity bodies and power diagrams
• Data Analysis and Operations Research

Cited In (3)

• Good Clusterings Have Large Volume
• On the basic properties and the structure of power cells
• Power diagram detection with applications to information elicitation

Uses Software

• Ipopt
• LIBSVM

This page was built for publication: On soft power diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894534)