Tree-structured Data Clustering

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

2018 INFORMS Annual Meeting, Arizona, Amerika Birleşik Devletleri, 4 - 07 Kasım 2018, ss.403

  • Yayın Türü: Bildiri / Özet Bildiri
  • Basıldığı Şehir: Arizona
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.403
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.