Tree-structured Data Clustering

Dinler D., Tural M. K. , Özdemirel N. E.

2018 INFORMS Annual Meeting, Arizona, United States Of America, 4 - 07 November 2018, pp.403

  • Publication Type: Conference Paper / Summary Text
  • City: Arizona
  • Country: United States Of America
  • Page Numbers: pp.403
  • Middle East Technical University Affiliated: Yes


Tree-structured Data Clustering

We consider a clustering problem in which data objects are rooted trees with
unweighted or weighted edges and propose a k-means based algorithm which
repeats assignment and update steps until convergence. The assignment step
utilizes Vertex Edge Overlap to assign each data object to the most similar
centroid. In the update step, each centroid is updated by considering the data
objects assigned to it. For the unweighted edges case, we propose a Nonlinear
Integer Programming (NIP) formulation to find the centroid of a given cluster and
solve the formulation to optimality with a heuristic. When edges are weighted,
we also provide an NIP formulation for which we have a heuristic not
guaranteeing optimality.