A mixed-integer programming approach to the clustering problem with an application in customer segmentation

Abstract

Kümeleme problemi belirli bir takım özelliklere göre birbirine benzer olan varlıklarıbelirleyen önemli bir veri madenciliği problemidir. Bu tezde iki matematiksel programlamatemelli kümeleme yaklaşımı sunulmuştur. Önerilen matematiksel programlama temelliyaklaşımlar bir dijital platform firmasının müşterilerine ait operasyonel veri setineuygulanmıştır. İlk modelde, kümeleme problemi kümeleme sonucunda oluşan kümeçaplarından en büyüğünün en küçüklenmesi amacı ile bir tam sayılı programlama modeli ileformule edilmiştir. Problemin hesaplama güçlüklerinin üstesinden gelebilme amacı ile testettiğimiz örnek veri setlerinin büyük bir kısmında en iyi çözümden ödün vermeden modelinçözüm zamanını azaltan bir buluşsal algoritma önerilmiştir. İkinci model, kümeleme problemiküme içi mesafelerin toplamının en küçüklenmesi amacı ile bir tam sayılı karma doğrusalolmayan programlama modeli ile formüle edilmiştir. Modelin doğrusal olmayangevşetilmesinde her uç nokta çözümün tam sayı olacağı unimodulerite özelliğine sahip olduğuispatlanarak gösterilmiştir. Modelin sürekli gevşetilmesi çözülmüş, tam sayılı sonuçlaralınmış ve modelin çözüm zamanının çok kısa olduğu gözlemlenmiştir. Yaklaşımlarınperformansları bir örnek veri seti ve gerçek veri seti üzerinde test edilmiştir. Deneylerden eldeettiğimiz sonuçlar yaklaşımların veri setini anlamlı bir şekilde kümelediğini ve çözüm zamanıaçısından etkin olduğunu göstermiştir.Danışman: Metin Türkay Tarih: 21 Temmuz 2005Enstitü Müdürü: Yaman Arkun Tarih: 21 Temmuz 2005

Clustering is an important data mining problem that identifies groups of entities thatare similar to each other with respect to a certain number of attributes. In this thesis, twomathematical programming based approaches to clustering are presented. The proposedmathematical programming based approaches are applied to a digital platform company?scustomer segmentation problem involving transactional attributes related to thecustomers. In the first model, the clustering problem is formulated as a mixed-integerlinear programming problem with the objective of minimizing the maximum clusterdiameter among all clusters. In order to overcome difficulties related to computationalcomplexity of this model, a heuristic clustering approach is developed that improvescomputational times dramatically without compromising from optimality in most of thecases that were tested. In the second model, the clustering problem is modeled as amixed-integer nonlinear programming problem with the objective of minimization of sumof within-group distances. We show that every extreme point solution of the nonlinearrelaxation of the model is integer due to the unimodularity property of the constraint setof the model. We solve the continuous relaxation of the model, obtain integer solutionsand observe that solution time of the model is very short. Although the model is solved tolocal optimality, the interpretations derived from the solution of the model are promising.The performance of the approaches is tested both on an illustrative example and on a realproblem. The analysis of the results indicates that the approaches are computationallyefficient and create meaningful segmentation of data.Advisor: Metin Türkay Date: July 21, 2005Director: Yaman Arkun Date: July 21, 2005