Archives and Documentation Center
Digital Archives

Using lagrangian relaxation and column generation for data clustering

Show simple item record

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Altınel, İ. Kuban.
dc.contributor.author Ayrancı, Mehmet.
dc.date.accessioned 2023-03-16T10:28:03Z
dc.date.available 2023-03-16T10:28:03Z
dc.date.issued 2009.
dc.identifier.other IE 2009 A87
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13226
dc.description.abstract Clustering is the organization of patterns, which are usually represented as vec- tors in multidimensional spaces, into a given number of groups with similar character- istics. It can be formulated as a mathematical optimization model whose objective is to locate cluster representatives so that the sum of dissimilarities with the representa- tive and given data vectors is minimized. In this work, we first formulate clustering problem for the minimization of the total expected distances between cluster repre- sentatives and data vectors, assuming that dissimilarities are measured using a metric separable with respect to the coordinates. We then propose a Lagrangian relaxation scheme for the solution of the resulting mixed integer linear programming problem. Our second formulation is for any distance metric and is analogous to the formulation of the multi-facilityWeber problem in many dimensions. The resulting nonconvex opti- mization problem is solved using column generation and d.c. programming techniques. According to our computational experiments we say that although the first one has low accuracy, the second one overperforms k-means algorithm.
dc.format.extent 30cm.
dc.publisher Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009.
dc.relation Includes appendices.
dc.relation Includes appendices.
dc.subject.lcsh Cluster analysis -- Data processing.
dc.subject.lcsh Production scheduling.
dc.title Using lagrangian relaxation and column generation for data clustering
dc.format.pages x, 57 leaves;


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Digital Archive


Browse

My Account