Hierarkisk klusterbildning baserad på parvisa likheter är ett vanligt verktyg som används i ett brett spektrum av vetenskapliga tillämpningar. Men i många problem kan det vara dyrt att få eller beräkna likheter mellan de objekt som ska samlas. Detta dokument undersöker den hierarkiska klungan av N-poster baserat på en liten delmängd av parvisa likheter, betydligt mindre än den fullständiga uppsättningen N (N − 1)/2 likheter. För det första visar vi att om den intraklustra likheter överstiger intercluster likheter, då är det möjligt att korrekt bestämma den hierarkiska klustret från så få som 3N log N likheter. Vi visar denna storleksordning besparingar i antalet parvisa likheter kräver sekventiellt välja vilka likheter att få på ett adaptivt sätt, snarare än att plocka dem på måfå. Vi föreslår sedan en aktiv klustermetod som är robust till en begränsad bråkdel av avvikande likheter, och visar hur även i närvaro av dessa bullriga likhetsvärden vi kan lösa hierarkisk kluster med endast O N log 2 N parvis likheter.
REF visar att aktivt utvalda parvisa likheter är tillräckliga för att återställa den hierarkiska klusterstrukturen.
Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}