Electronic Resource
Analysis of Agglomerative Clustering
| العنوان: | Analysis of Agglomerative Clustering |
|---|---|
| المؤلفون: | Marcel R. Ackermann and Johannes Bloemer and Daniel Kuntze and Christian Sohler, Ackermann, Marcel R., Bloemer, Johannes, Kuntze, Daniel, Sohler, Christian |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2011 |
| نوع الوثيقة: | Electronic Resource |
| مستخلص: | The diameter k-clustering problem is the problem of partitioning a finite subset of R^d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem for all values of k is the agglomerative clustering algorithm with the complete linkage strategy. For decades this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension dis a constant, we show that for any k the solution computed by this algorithm is an O(log k)-approximation to the diameter k-clustering problem. Moreover, our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. |
| مصطلحات الفهرس: | agglomerative clustering, hierarchical clustering, complete linkage, approximation guarantees, InProceedings, Text, doc-type:ResearchArticle, publishedVersion |
| DOI: | 10.4230.LIPIcs.STACS.2011.308 |
| URL: | Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
| الاتاحة: | Open access content. Open access content https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode |
| ملاحظة: | application/pdf English |
| Other Numbers: | DEDAG oai:drops-oai.dagstuhl.de:2994 doi:10.4230/LIPIcs.STACS.2011.308 urn:nbn:de:0030-drops-29942 1358719308 |
| المصدر المساهم: | SCHLOSS DAGSTUHL LEIBNIZ ZENTRUM GMBH From OAIster®, provided by the OCLC Cooperative. |
| رقم الانضمام: | edsoai.on1358719308 |
| قاعدة البيانات: | OAIster |
| DOI: | 10.4230.LIPIcs.STACS.2011.308 |
|---|