Korrelationskluster är kanske den mest naturliga formuleringen av kluster. Med tanke på n objekt och en parvis likhet mått, är målet att samla objekten så att, i bästa möjliga utsträckning, liknande objekt placeras i samma kluster och olika objekt placeras i olika kluster. Trots sin teoretiska dragningskraft är den praktiska betydelsen av korrelationskluster fortfarande i stort sett outforskad. Detta beror främst på det faktum att korrelationskluster kräver de två parvisa likheterna som indata. I stora datauppsättningar är det omöjligt att beräkna eller bara lagra. I detta dokument inleder vi undersökningen av lokala algoritmer för korrelationskluster, vilket lägger den teoretiska grunden för klusterbildning "big data". I lokala korrelationskluster får vi identifiera ett enda objekt och vi vill returnera det kluster som det hör till i någon globalt konsekvent nära-optimal klusterbildning, med hjälp av ett litet antal likhetsfrågor. Lokala algoritmer för korrelationskluster öppnar dörren till sublinjära tidsalgoritmer, som är särskilt användbara när likheten mellan objekt är kostsam att beräkna, som det ofta är fallet i många praktiska tillämpningsområden. De innebär också (i) distribuerade och strömmande klusteralgoritmer, (ii) estimatorer och testare för klusterredigeringsavstånd, och (iii) egenskapsbevarande parallella rekonstruktionsalgoritmer för klusterbarhet. Specifikt, vi utformar en lokal kluster algoritm uppnå en (3, ε)- tillnärmning (en lösning med kostnad på högst 3 · OPT + εn 2, där OPT är den optimala kostnaden). Dess körtid är O(1/ε 2 ) oberoende av datamängdens storlek. Om så önskas kan en explicit ungefärlig klusterbildning för alla n objekt produceras i tid O (n/ε) (vilket är påtagligt optimalt). Vi ger också en fullständig tillsats (1, ε) - approximation med lokala frågor komplexitet poly(1/ε) och tid komplexitet 2 poly(1/ε). Den explicita klusterbildningen finns i tid n · poly(1/ε) + 2 poly(1/ε). Den senare ger den snabbaste polynom-tids approximationsschemat för korrelation klustring känd hittills.
Slutligen nämner vi det senaste arbetet med Ref som har infört en lokal algoritm för korrelationskluster för att hantera enorma datauppsättningar.
Local correlation clustering
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}