Testing of clustering

Sean Dar, N. Alon, D. Ron, M. Parnas

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


A set X of points in /spl Rfr//sup d/ is (k,b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms that by sampling from a set X, distinguish between the case that X is (k,b)-clusterable and the case that X is /spl epsiv/-far from being (k,b')-clusterable for any given 0>/spl epsiv//spl les/1 and for b'/spl ges/b. In /spl epsiv/-far from being (k,b')-clusterable we mean that more than /spl epsiv/.|X| points should be removed from X so that it becomes (k,b')-clusterable. We give algorithms for a variety of cost measures that use a sample of size independent of |X|, and polynomial in k and 1//spl epsiv/. Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an /spl epsiv/-fraction of the points in X that have optimal (or close to optimal) cost. The benefit of our algorithms is that they construct an implicit representation of such clusterings in time independent of |X|. That is, without actually having to partition all points in X, the implicit representation can be used to answer queries concerning the cluster any given point belongs to.
שפה מקוריתאנגלית
כותר פרסום המארחProceedings 41st Annual Symposium on Foundations of Computer Science
מקום הפרסוםLos Alamitos, CA, USA
מוציא לאורIEEE Computer Society
מספר עמודים1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 נוב׳ 2000
אירוע41st Annual Symposium on Foundations of Computer Science - Redondo Beach, CA, ארצות הברית
משך הזמן: 12 נוב׳ 200014 נוב׳ 2000


כנס41st Annual Symposium on Foundations of Computer Science
מדינה/אזורארצות הברית
עירRedondo Beach, CA

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Testing of clustering'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי