Pareto Local Search for Alternative Clustering

Supervised alternative clusterings is the problem of finding a set of clusterings which are of high quality and different from a given negative clustering. The task is therefore a clear multi-objective optimization problem. Optimizing two conflicting objectives at the same time requires dealing with tradeoffs. Most approaches in the literature optimize these objectives sequentially (one objective after another one) or indirectly (by some heuristic combination of the objectives). Solving a multi-objective optimization problem in these ways can result in solutions which are dominated (and not Pareto-optimal). We develop a direct multi objective local search algorithm based on Pareto Local Search, called PLSAC, which fully acknowledges the multiple objectives, optimizes them directly and simultaneously, and produces solutions approximating the Pareto front. PLSAC has no sensitive parameters to be tuned by the user, provides solutions which dominate those obtained by other state-of-the-art algorithms, and can accept arbitrary clustering quality and dissimilarity objectives. Besides, it can also be guided by the user to explore specific regions of interest along the Pareto front in an interactive manner.