Pseudo-Boolean clustering
Giovanni Rossi · 2010
Abstract This paper proposes to cluster any finite data set by optimizing with respect to a cluster score function,assigning a positive real worth to each data subset and thereby dealt with in pseudo-Boolean form, sothat the multilinear extension (MLE) allows to evaluate fuzzy data subsets or clusters as well. A fuzzyclustering being a collection of fuzzy clusters over which every data point has to distribute a unitary mem-bership mass, the objective function (to be maximized) is global worth, obtained through summation overconstituents fuzzy clusters of their own worth as given by the score function MLE. Optimization thenproceeds by means of pseudo-Boolean techniques, leading to a local-search algorithm. Also, any fuzzyclustering is shown to admit some hard one (or partition of the data set) that does at least as good, andconcavity of the objective function is interpreted in terms of the underlying clustering problem. Key words: pseudo-Boolean function, optimization, clustering, fuzzy clustering, algorithm.