A method for searching for a globally optimal k-partition of higher-dimensional datasets

Kristian Sabo (), Rudolf Scitovski (), Šime Ungar () and Zoran Tomljanović ()
Additional contact information
Kristian Sabo: University of Osijek
Rudolf Scitovski: University of Osijek
Šime Ungar: University of Zagreb
Zoran Tomljanović: University of Osijek

Journal of Global Optimization, 2024, vol. 89, issue 3, No 4, 633-653

Abstract: Abstract The problem of finding a globally optimal k-partition of a set $$\mathcal {A}$$ A is a very intricate optimization problem for which in general, except in the case of one-dimensional data, i.e., for data with one feature ( $$\mathcal {A}\subset \mathbb {R}$$ A ⊂ R ), there is no method to solve. Only in the one-dimensional case, there are efficient methods based on the fact that the search for a globally optimal k-partition is equivalent to solving a global optimization problem for a symmetric Lipschitz-continuous function using the global optimization algorithm DIRECT. In the present paper, we propose a method for finding a globally optimal k-partition in the general case ( $$\mathcal {A}\subset \mathbb {R}^n$$ A ⊂ R n , $$n\ge 1$$ n ≥ 1 ), generalizing an idea for solving the Lipschitz global optimization for symmetric functions. To do this, we propose a method that combines a global optimization algorithm with linear constraints and the k-means algorithm. The first of these two algorithms is used only to find a good initial approximation for the k-means algorithm. The method was tested on a number of artificial datasets and on several examples from the UCI Machine Learning Repository, and an application in spectral clustering for linearly non-separable datasets is also demonstrated. Our proposed method proved to be very efficient.

Keywords: Lipschitz continuous function; Global optimization; Globally optimal k-partition; DIRECT; Linear constrained problem; 65K05; 90C26; 90C27; 90C56; 90C57; 05E05 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01372-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:89:y:2024:i:3:d:10.1007_s10898-024-01372-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01372-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().