Abstrakt. Ashtiani m.fl. (NIPS 2016) införde ett halvövervakat ramverk för klusterbildning (SSAC) där en elev tillåts ställa sammaklusterfrågor. Mer specifikt, i sin modell, finns det en fråga oracle som besvarar frågor av formen "med tanke på två hörn, tillhör de samma optimala kluster?". I många klustersammanhang är denna typ av orakelfrågor möjliga. Ashtiani m.fl. visade nyttan av en sådan frågeram genom att ge en polynomisk tidsalgoritm för k-means klusterproblem där indatauppsättningen uppfyller något separationstillstånd. Ailon m.fl. Utöka ovanstående arbete till approximationsinställningen genom att ge en effektiv (1+ε) approximationsalgoritm för k-medelvärden för alla små ε > 0 och eventuella datauppsättningar inom ramen för SSAC. I detta arbete utvidgar vi denna studielinje till att omfatta problemet med korrelationskluster. Korrelationskluster är ett problem med grafkluster där parvis likhet (eller olikhet) information ges för varje par av hörn och målet är att dela upp hörnen i kluster som minimerar oenigheten (eller maximerar överenskommelsen) med den parvisa information som ges som indata. Dessa problem är populärt kända som MinDisAgree och MaxAgree problem, och MinDisAgree [k] och MaxAgree [k] är versioner av dessa problem där antalet optimala kluster är som mest k. Det finns Polynom tid Catimation Scheme (PTAS) för MinDisAgree [k] och MaxAgree [k] där approximationsgarantin är (1 + ε) för alla små ε och körtiden är polynom i indataparametrarna men exponentiellt i k och 1/ε. Vi får en betydande tidsförbättring inom SSAC-ramverket till priset av att göra ett litet antal samma-kluster frågor. Vi får en (1+ε)-tillnärmningsalgoritm för alla små ε med körtid som är polynom i indataparametrarna och även i k och 1/ε. Vi ger också icke-triviala övre och nedre gränser på antalet samma-kluster frågor, den nedre gränsen baseras på Exponential Time Hypothesis (ETH). Observera att förekomsten av en effektiv algoritm för MinDisAgree [k] i SSAC-inställningen uppvisar kraften i samma-kluster frågor eftersom sådana polynom tid algoritm (polynom även i k och 1/ε) inte är möjligt i den klassiska (icke-query) inställning på grund av våra villkorade lägre gränser. Vår villkorade nedre gräns är särskilt intressant eftersom den inte bara fastställer en lägre gräns för antalet samma klusterfrågor i SSAC-ramverket utan också fastställer en villkorad lägre gräns för körtiden för någon (1 + ε)-tillnärmningsalgoritm för MinDisAgree [k].
På senare tid har Ref övervägt problemet med korrelationskluster i närvaro av ett orakel.
Approximate Correlation Clustering Using Same-Cluster Queries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}