{"corpus_id":6493088,"paper_sha":"1520bec956097089b2aeb2a4b143f96458fcc0b9","doi":"10.1007/978-3-319-31753-3_21","arxiv_id":"1512.03953","pmid":null,"pmcid":null,"mag_id":2950154716,"dblp_id":"conf/pakdd/AghaeeGB16","acl_id":null,"title":"Active Distance-Based Clustering Using K-Medoids","year":2015,"publication_date":"2015-12-12","venue":"Pacific-Asia Conference on Knowledge Discovery and Data Mining","journal":{"name":"ArXiv","pages":null,"volume":"abs/1512.03953"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle","Conference"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":28,"citation_count":15,"influential_citation_count":0,"is_open_access":false,"arxiv_categories":["cs.LG"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"k-medoids algorithm is a partitional, centroid-based clustering algorithm which uses pairwise distances of data points and tries to directly decompose the dataset with n points into a set of k disjoint clusters. However, k-medoids itself requires all distances between data points that are not so easy to get in many applications. In this paper, we introduce a new method which requires only a small proportion of the whole set of distances and makes an effort to estimate an upper-bound for unknown distances using the inquired ones. This algorithm makes use of the triangle inequality to calculate an upper-bound estimation of the unknown distances. Our method is built upon a recursive approach to cluster objects and to choose some points actively from each bunch of data and acquire the distances between these prominent points from oracle. Experimental results show that the proposed method using only a small subset of the distances can find proper clustering on many real-world and synthetic datasets.","claims":[{"public_id":"cl_68023cc0685da612981115438e22a54e","status":"active","text":"A new active distance-based clustering method requires only a small proportion of pairwise distances and estimates upper bounds for unknown distances from queried ones.","confidence":0.96,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_68023cc0685da612981115438e22a54e"},{"public_id":"cl_cbe3125549d3b55474d6af3bc4f417c7","status":"active","text":"A recursive clustering procedure actively selects prominent points from each data group and queries their distances from an oracle.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_cbe3125549d3b55474d6af3bc4f417c7"},{"public_id":"cl_a8867387eb11ebec8d12a8cd0a0b12f9","status":"active","text":"Triangle inequality is used to derive upper-bound estimates for unknown distances.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_a8867387eb11ebec8d12a8cd0a0b12f9"},{"public_id":"cl_0fe5865547a8824d221d2051bb9a08fe","status":"active","text":"Using only a small subset of distances, the method finds proper clustering on many real-world and synthetic datasets.","confidence":0.9,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_0fe5865547a8824d221d2051bb9a08fe"}],"concepts":[{"public_id":"co_2e2ae5dfa9a66d08b4fbedefea56c4ad","status":"active","name":"oracle","description":"An external source that provides queried distance values for selected point pairs.","types":["information source"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_2e2ae5dfa9a66d08b4fbedefea56c4ad"},{"public_id":"co_3703e6cdc322b8e89181426368a2f12f","status":"active","name":"triangle inequality","description":"A geometric property relating distances that enables distance bounds to be inferred from known distances.","types":["mathematical property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_3703e6cdc322b8e89181426368a2f12f"},{"public_id":"co_3bf35e85559153132bb4c83ab9c1fff2","status":"active","name":"upper-bound estimation","description":"The process of computing a bound that is guaranteed to be at least as large as an unknown distance.","types":["method","estimation"],"aliases":["upper-bound for unknown distances"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_3bf35e85559153132bb4c83ab9c1fff2"},{"public_id":"co_67520c37da09fa9a7aed1b93d34e7814","status":"active","name":"active distance-based clustering","description":"A clustering approach that actively queries selected pairwise distances instead of relying on the full distance matrix.","types":["method"],"aliases":["distance-based clustering method"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_67520c37da09fa9a7aed1b93d34e7814"},{"public_id":"co_6d02b5684a11904b6e21f8447a220dc4","status":"active","name":"real-world datasets","description":"Empirical datasets used to evaluate the clustering method on practical data.","types":["dataset","evaluation data"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6d02b5684a11904b6e21f8447a220dc4"},{"public_id":"co_85f58b456052d42654492a20f13821cb","status":"active","name":"synthetic datasets","description":"Artificially generated datasets used to test the clustering method under controlled conditions.","types":["dataset","evaluation data"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_85f58b456052d42654492a20f13821cb"},{"public_id":"co_a8456624c5705072b96ca5c9defce876","status":"active","name":"prominent points","description":"Selected representative points within a group that are queried to obtain distances.","types":["representative points"],"aliases":["active points"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a8456624c5705072b96ca5c9defce876"},{"public_id":"co_adbd428599c3ed15155d58c29e4fd23c","status":"active","name":"recursive approach","description":"A clustering strategy that repeatedly applies the procedure to smaller subsets or groups.","types":["algorithmic strategy"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_adbd428599c3ed15155d58c29e4fd23c"},{"public_id":"co_d301fe32e4f191253941d3d898d752e7","status":"active","name":"pairwise distances","description":"Distances computed between pairs of data points and used as inputs to clustering.","types":["measurement","data"],"aliases":["distance matrix entries"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d301fe32e4f191253941d3d898d752e7"},{"public_id":"co_f22775dda44244a2c16be90b21700b5b","status":"active","name":"subset of distances","description":"A small fraction of the full set of pairwise distances used as input by the method.","types":["data subset"],"aliases":["small proportion of the whole set of distances"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_f22775dda44244a2c16be90b21700b5b"},{"public_id":"co_fdce8cd12e584c4679cf439d9dd29c94","status":"active","name":"k-medoids","description":"A partitional clustering algorithm that represents clusters by medoids and uses pairwise distances between data points.","types":["clustering algorithm"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_fdce8cd12e584c4679cf439d9dd29c94"}],"external_ids":{"DOI":"10.1007/978-3-319-31753-3_21","ArXiv":"1512.03953","PubMed":null,"PubMedCentral":null,"MAG":2950154716,"DBLP":"conf/pakdd/AghaeeGB16","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/1512.03953","landing_url":"https://arxiv.org/abs/1512.03953","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635394,"paper_uid":"292ea5c9-3a07-4bdd-ab79-c5a82aed4eb1","canonical_identity":{"paper_id":635394,"paper_uid":"292ea5c9-3a07-4bdd-ab79-c5a82aed4eb1","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/6493088"}