Vi föreslår ett ramverk för Semi-Supervised Active Clustering Framework (SSAC), där eleven tillåts interagera med en domän expert, frågar om två givna fall tillhör samma kluster eller inte. Vi studerar den fråge- och beräkningsmässiga komplexiteten hos klusterbildning inom detta ramverk. Vi överväger en miljö där experten anpassar sig till en centerbaserad klusterbildning med ett begrepp om marginal. Vi visar att det finns en avvägning mellan beräknings komplexitet och fråge komplexitet; Vi bevisar att när det gäller k-medel kluster (dvs. när experten överensstämmer med en lösning av k-medel), har tillgång till relativt få sådana frågor gör effektiva lösningar till annars NP svåra problem. I synnerhet tillhandahåller vi en probabilistisk polynom-tids-algoritm (BPP) för klustring i denna inställning som frågar O k 2 log k + k log n) samma-kluster frågor och körs med tids komplexitet O kn log n) (där k är antalet kluster och n är antalet instanser). Framgången för algoritmen garanteras för data som uppfyller marginalförhållanden under vilka, utan frågor, vi visar att problemet är NP hårt. Vi visar också en lägre gräns för antalet frågor som behövs för att ha en beräkningseffektiv klusteralgoritm i denna inställning.
Astiani m.fl. REF beaktade k-means-målet med samma kluster-frågor och visade att det är möjligt att återställa den optimala klustreringen under k-means-målet med hög sannolikhet genom att utfärda O(k 2 log k + k log n)-frågor om ett visst marginalvillkor gäller för varje kluster.
Clustering with Same-Cluster Queries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}