A new mathematical programming formulation for multivariate regression clustering with a store clustering application in retail sector

Abstract

Kümeleme, birbirine benzer elemanların benzer gruplara ayrılmasını amaçlayan, gözetimsiz öğrenme tekniklerinden biridir. Doğrusal regresyon tabanlı kümeleme ise benzer elemanları, her bir grup için uyarlanan doğrusal regresyon model hatalarının belirli bir normda en iyilecek şekilde gruplamasıdır---literatürde genellikle L^2-normu (Öklid normu) minimize eden en küçük kareler yöntemi kullanılarak regresyon parametreleri tahmin edilir. Bu çalışma yüksek korelasyona sahip birden fazla bağımlı değişkenin varlığında kullanılabilecek doğrusal regresyon tabanlı kümeleme modelini dikkate almaktadır. Ayrıca iki adet yeni karmaşık tamsayılı doğrusal programlama formülasyonu önerilmiştir. İlk formülasyon literatürde bulunan klasik büyük M kısıtlı modelin birden fazla bağımlı değişkeni dikkate alacak şekilde genişletilmiş halidir. Bununla birlikte amaç fonksiyonunda L^1 ve L^2 norm yerine L^∞ normu minimize edilmektedir. Ancak büyük M değeri bilinmeyen kümeleme ve regresyon parametrelerine bağımlı olduğundan dolayı, uygun bir büyük M değerini önceden bilmek mümkün değildir. Çok büyük bir büyük M değeri çözümde sayısal dengesizliklere, çok küçük bir büyük M değeri ise optimal sonuca ulaşamamaya neden olmaktadır. Bu yüzden çalışmamızda büyük M kısıtlarını içeren klasik formülasyon yerine tip 1 özel sıralı set değişkenlerini içeren formülasyon önerilmiştir.Birden fazla çıktı değişkeni için önerilen yeni büyük M kısıtlı formülasyon literatürde bulunan JURA veri setine uygulanmıştır. JURA veri setindeki farklı bölgelerden alınan toprak örneklerinde ölçüm maliyeti düşük olan metallerin konsantrasyonu ile ölçüm maliyeti yüksek olan metallerin konsantrasyonu tahmin edilmeye çalışılmaktadır. Bu uygulamada, her bir çıktı değişkenini ayrı ayrı dikkate alarak gerçekleştirilen kümeleme sonuçlarının birbirinden farklı olduğu ve bu nedenle hangi örneğin hangi kümeye ait olduğu bilgisinin belirli olmadığı gösterilmiştir. Her çıktı değişkenini ayrı ayrı dikkate alarak gerçekleştirilen kümeleme sonuçları birbiri ile aynı olsa bile, bütün değişkenleri eş zamanlı değerlendirerek yapılan kümeleme sonuçlarından farklı olabilecektir. Bu nedenle birden fazla yüksek korelasyona sahip değişkenin bulunduğu durumlarda bu klasik yaklaşım yanlış kümeleme sonuçlarına neden olabilir.Son olarak, önerilen yeni matematiksel formülasyonlar Türkiye'de faaliyet gösteren bir moda perakendecisine ait mağazaların kümelenmesi problemine uygulanmıştır. Mağaza kümelenmesi kısaca önceden belirlenen özelliklere dayanarak benzer mağazaların gruplara ayrılmasını ifade eder. Bu kümeleme çalışmasının amacı küme bazında değişiklik gösterecek olan lokasyon, müşteri ve mağazaya ait özelliklerin ilgili mağaza performansı üzerindeki etkilerini belirlemek ve analiz etmektir. Önerilen matematiksel modeller Gurobi 8.1.0 çözücüsünde dal kesme algoritması kullanılarak çözümlenmiştir.

Clustering in machine learning is an unsupervised learning technique, and it is the study of grouping similar entities together. In particular, clustering via regression groups entities such that the fit of a linear-in-parameter model is `best` with respect to a norm function of residuals---usually an L^2-norm (Euclidean norm) of residuals, which gives the least-squares estimates of the unknown regression parameters. This study considers linear-in-parameters regression model-based clustering when there are multiple correlated responses (i.e., dependent variables). Furthermore, this study proposes two new mixed-integer linear programming formulations, where the first formulation is a simple extension of the classic formulations with the big-M constraints in the literature for multiple responses. Besides, the objective function minimizes L^∞-norm of residuals instead of L^1-norm or L^2-norm. However, the big-M in the formulations depends on the unknown clusters and regression parameters, and hence, it is impossible to know a `good` value for the big-M a priori. A too big value for the big-M results in numerical instabilities, and a too small value for the big-M cuts the true optimal solution. Therefore, this study proposes to replace the classic formulations with the big-M constraints with formulations that have special ordered sets of type one (SOS Type-1) variables.The proposed formulation for multiple responses with the big-M constraints is applied to the JURA dataset, which clusters locations to predict the concentration of some metals that are more expensive to measure using measurements of metals that are cheaper to sample. For this numerical example, this study illustrates that the classic approach in the literature, which considers one response at-a-time, usually assigns the same entity to different clusters with respect to different responses; hence, eventually, it is not evident to which cluster that entity belongs to. Also, even though the classic approach assigns that entity to the same cluster with respect to all responses, this assignment can be different than the one obtained when all responses are considered simultaneously; hence, the classic approach can result in a false clustering when multiple corelated responses have to be considered at the same time.The proposed formulations and algorithms are also applied for store clustering problem of a fashion retailer in Turkey. The store clustering problem simply means grouping of the stores based on some predetermined characteristics so that those stores within the same group are more similar to each other than the other stores. The purpose of such a clustering can be to detect and analyze the effects of location, customer and store characteristics on the store performance, which can depend on different clusters. The proposed models are solved using the branch-and-cut algorithm using optimization software Gurobi 8.1.0 C API.