A unified framework for approximating and clustering data

Dan Feldman, Michael Langberg

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


Given a set F of n positive functions over a ground set X, we consider the problem of computing x* that minimizes the expression Σ f ∈ Ff(x), over x ∈ X. A typical application is shape fitting, where we wish to approximate a set P of n elements (say, points) by a shape x from a (possibly infinite) family X of shapes. Here, each point p ∈ P corresponds to a function f such that f(x) is the distance from p to x, and we seek a shape x that minimizes the sum of distances from each point in P. In the k-clustering variant, each x\in X is a tuple of k shapes, and f(x) is the distance from p to its closest shape in x. Our main result is a unified framework for constructing coresets and approximate clustering for such general sets of functions. To achieve our results, we forge a link between the classic and well defined notion of ε-approximations from the theory of PAC Learning and VC dimension, to the relatively new (and not so consistent) paradigm of coresets, which are some kind of "compressed representation" of the input set F. Using traditional techniques, a coreset usually implies an LTAS (linear time approximation scheme) for the corresponding optimization problem, which can be computed in parallel, via one pass over the data, and using only polylogarithmic space (i.e, in the streaming model). For several function families F for which coresets are known not to exist, or the corresponding (approximate) optimization problems are hard, our framework yields bicriteria approximations, or coresets that are large, but contained in a low-dimensional space. We demonstrate our unified framework by applying it on projective clustering problems. We obtain new coreset constructions and significantly smaller coresets, over the ones that appeared in the literature during the past years, for problems such as: k-Median [Har-Peled and Mazumdar,STOC'04], [Chen, SODA'06], [Langberg and Schulman, SODA'10]; k-Line median [Feldman, Fiat and Sharir, FOCS'06], [Deshpande and Varadarajan, STOC'07]; Projective clustering [Deshpande et al., SODA'06] [Deshpande and Varadarajan, STOC'07]; Linear l p regression [Clarkson, Woodruff, STOC'09 ]; Low-rank approximation [Sarlos, FOCS'06]; Subspace approximation [Shyamalkumar and Varadarajan, SODA'07], [Feldman, Monemizadeh, Sohler and Woodruff, SODA'10], [Deshpande, Tulsiani, and Vishnoi, SODA'11]. The running times of the corresponding optimization problems are also significantly improved. We show how to generalize the results of our framework for squared distances (as in k-mean), distances to the qth power, and deterministic constructions.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
ناشرAssociation for Computing Machinery
عدد الصفحات10
رقم المعيار الدولي للكتب (المطبوع)9781450306911
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2011
الحدث43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, الولايات المتّحدة
المدة: ٦ يونيو ٢٠١١٨ يونيو ٢٠١١

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing
رقم المعيار الدولي للدوريات (المطبوع)0737-8017


!!Conference43rd ACM Symposium on Theory of Computing, STOC 2011
الدولة/الإقليمالولايات المتّحدة
المدينةSan Jose


أدرس بدقة موضوعات البحث “A unified framework for approximating and clustering data'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا