Using lagrangian relaxation and column generation for data clustering

Simple item page
dc.contributorGraduate Program in Industrial Engineering.
dc.contributor.advisorAltınel, İ. Kuban.
dc.contributor.authorAyrancı, Mehmet.
dc.date.accessioned2023-03-16T10:28:03Z
dc.date.available2023-03-16T10:28:03Z
dc.date.issued2009.
dc.description.abstractClustering 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.extent30cm.
dc.format.pagesx, 57 leaves;
dc.identifier.otherIE 2009 A87
dc.identifier.urihttps://digitalarchive.library.bogazici.edu.tr/handle/123456789/13226
dc.publisherThesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009.
dc.relationIncludes appendices.
dc.relationIncludes appendices.
dc.subject.lcshCluster analysis -- Data processing.
dc.subject.lcshProduction scheduling.
dc.titleUsing lagrangian relaxation and column generation for data clustering

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
b1557955.005656.001.PDF
Size:
466.3 KB
Format:
Adobe Portable Document Format
Download

Collections

M.S. Theses