Lookalike Clustering for Customer Segmentation: a Comparative Study of Quantum Annealing and Classical Algorithms

Customer segmentation is strategic for increasing business revenues, as it allows a company to offer tailored products and services. Companies have access to vast amounts of information to generate customer clusters. In the banking sector, for instance, transactional data may reveal several hidden customer characteristics. The lookalike clustering problem aims to expand an initial cluster by detecting similar customers from a larger set. In this work, we model the lookalike clustering problem as a Quadratic Unconstrained Binary Optimization problem and solve it by means of a Quantum Annealer (QA). We tune the penalization parameters of the QA through an adaptive subgradient-inspired algorithm. We then compare QA performance against those obtained by a Simulated Annealing and the classical integer programming solver Gurobi. The results show that QA, when properly tuned, is able to find the optimal solution for small instances of the problem, even when the number of variables exceeds the number of couplers of QA. It fails, instead, for larger ones, due to the high level of noise. The results also show that QA requires a very short time to generate feasible and optimal solutions compared to classical algorithms, thus proving its potential for the solution of fully connected graphs.