March 2002

BACK   

Many data analysis problems involve clustering of a large set of points in an arbitrary metric space. The input to such problems is specified by a set of points P={p_1...p_n}, and a distance function D(.,.). It is assumed that for any two points p,q, the value of D(p,q) can be computed within a fixed time (say T). The goal is to partition P into a set of k clusters C_1...C_k in order to minimize certain objective function describing the clustering quality.

For example, the clustering can be defined by a set of k points (called centers) c_1..c_k, and setting C_i to be the set of points in P for whom c_i is the closest center. The quality of the clustering can be then defined e.g., by a "sum-sum" function

Since the number of points n is large, even computing D(p,q) for all pairs p,q, and then clustering based on this information is infeasible. In this talk we show how to overcome this difficulty. In particular, we show an algorithm which provably finds an *approximately* optimal clustering (w.r.t. "sum-sum" function) by doing only about O(kn) distance computations. Thus, when k << n, the algorithm runs in time *sublinear* in the description size of a metric (which is Omega(n^2)). We also show some extensions of this algorithm, as well as results for other clustering objective functions.

Related papers:

• D. Hochbaum, D. Shmoys. "A best possible approximation algorithm for the k-center problem". Math. Oper. Res., 10, 1985, 180--184
• T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293-306
• P. Indyk, "Sublinear time algorithms for metric space problems", STOC'99.
• Sudipto Guha Nina Mishra Rajeev Motwani Liadan O'Callaghan, "Clustering Data Streams," IEEE Symposium on Foundations of Computer Science, 2000.

BACK

Last Updated: March. 30, 2002