Abstract
Many applications in operations research begin with a set of points in a Euclidean space that is partitioned into clusters. Common data analysis tasks then are to devise a classifier deciding to which of the clusters a new point is associated, 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 to develop new, 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 the maximum number of points we wish 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. We show that its locally optimal solutions satisfy the aforementioned point counting properties, by studying the corresponding optimality conditions. For our target applications that use fixed sites, our algorithms are efficiently solvable to global optimality by linear programming.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Al-Harbi, S.H., Rayward-Smith, V.J.: Adapting k-means for supervised clustering. Appl. Intell. 24, 219–226 (2006)
Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)
Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20, 61–76 (1998)
Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Handbook of Computational Geometry, pp. 201–290. Elsevier Science (1999)
Bennett, K.P., Mangasarian, O.L.: Multicategory discrimination via linear programming. Optim. Methods Softw. 3, 27–39 (1992)
Borgwardt, S.: A Combinatorial Optimization Approach to Constrained Clustering. PhD thesis, Tech. Univ. Munich (2010)
Bredensteiner, E.J., Bennett, K.P.: Multicategory classification by support vector machines. Comput. Optim. Appl. 12, 53–79 (1999)
Brieden, A., Gritzmann, P.: On optimal weighted balanced clusterings: Gravity bodies and power diagrams. SIAM J. Discret. Math. 26, 415–434 (2012)
Chang, C.-C., Lin, C.-J.: LIBSVM: A library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 1:27–27:27 (2011)
Cortes, C., Vapnik, V.: Support-vector networks. In: Machine Learning, pp. 273–297 (1995)
Crammer, K., Singer, Y.: On the algorithmic implementation of multiclass kernel-based vector machines. J. Mach. Learn. Res. 2, 265–292 (2001)
Gaul, W.: Data analysis and operations research. In: Selected Contributions in Data Analysis and Classification, Studies in Classification, Data Analysis, and Knowledge Organization, pp. 357–366 (2007)
Hsu, C.-W., Lin, C.-J.: A comparison of methods for multiclass support vector machines. IEEE Trans. Neural Netw. 13(2), 415–425 (2002)
Nguyen, Q., Rayward-Smith, V.J.: CLAM: Clustering large applications using metaheuristics. J. Math. Model. Algorithm. 10, 57–78 (2011)
Perez-Cruz, F, Weston, J., Herrmann, D., Schölkopf, B.: Extension of the ν-svm range for classification. In: Advances in Learning Theory: Methods, Models and Applications, volume III of Nato Science Series, pp. 179–196. IOS Press (2003)
Schölkopf, B., Smola, A.J., Williamson, R.C., Bartlett, P.L.: New support vector algorithms. Neuronal Comput. 12, 1207–1245 (2000)
Tatsumi, K, Kawachi, R., Hayashida, K., Tanino, T.: Multiobjective multiclass soft-margin support vector machine and its solving technique based on Bensons method. In: Modeling Decisions for Artificial Intelligence, volume 5861 of Lecture Notes in Computer Science, pp. 360–371. Springer, Berlin / Heidelberg (2009)
Tatsumi, K., Kawachi, R., Hayashida, K., Tanino, T.: Multiobjective multiclass soft-margin support vector machine maximizing pair-wise interclass margins. In: Advances in Neuro-Information Processing, volume 5506 of Lecture Notes in Computer Science, pp. 970–977. Springer, Berlin / Heidelberg (2009)
Vapnik, V.: Statistical Learning Theory. Wiley (1998)
Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)
Weston, J., Watkins, C.: Multi-class support vector machines. Technical report, University of London (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Borgwardt, S. On Soft Power Diagrams. J Math Model Algor 14, 173–196 (2015). https://doi.org/10.1007/s10852-014-9263-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-014-9263-y
Keywords
- Power diagrams
- Least-squares assignments
- Soft-margin separation
- Operations research
- Linear programming
- Machine learning