PROBLEMI DI CLUSTERING CON VINCOLI: ALGORITMI E COMPLESSITÀ

This thesis introduces and studies the problem of 1-dimensional bounded clustering: for any fixed p ≥ 1, given reals x1, x2..., xn, and integers k1, k2.., km, determine the partition (A1, A2... Am) of {1, 2, ..., n} with |A1| = k1, |A2| = k2 , ... , |Am| = km which minimizes Σk Σi Ak |xi - μk |p where μk is the p-centroid of Ak First, we prove that the optimum partition is contiguous (String Property), that is if i,j  Ak, and xi < xs < xj, then s  Ak . As a consequence, we determine an efficient algorithm for bi-clustering (if p is an integer); however, we show that the general problem is NP-complete, while a relaxed version of it admits a polynomial-time algorithm. When p is not an integer, we prove that the problem of deciding if the centroid μ is less than a given integer is in the Counting Hierarchy CH. As an application, the relaxed clustering algorithm used as a step for solving a problem in the field of Bioinformatics: the Localization of promoter regions in genomic sequences. The results are compared with those obtained through another methodology (MADAP).

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2010

Author dc:creator

• SACCA', FRANCESCO

Contributors dc:contributor

• tutor: A. Bertoni
• G. Valentini
• F. Sacca'
• BERTONI, ALBERTO

• clustering
• NP-complete
• Settore INF/01 - Informatica

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

ita

Identifier

10.13130/sacca-francesco_phd2010-12-17

OAI identifier oai:identifier

oai:air.unimi.it:2434/150055