Hide/Show Apps

Tree-structured Data Clustering

Dinler, Derya
Tural, Mustafa Kemal
Özdemirel, Nur Evin
Tree-structured Data ClusteringWe consider a clustering problem in which data objects are rooted trees withunweighted or weighted edges and propose a k-means based algorithm whichrepeats assignment and update steps until convergence. The assignment steputilizes Vertex Edge Overlap to assign each data object to the most similarcentroid. In the update step, each centroid is updated by considering the dataobjects assigned to it. For the unweighted edges case, we propose a NonlinearInteger Programming (NIP) formulation to find the centroid of a given cluster andsolve the formulation to optimality with a heuristic. When edges are weighted,we also provide an NIP formulation for which we have a heuristic notguaranteeing optimality.