Како уклопити слона у табелу

Табела веза

Апстракт и 1 Увод

2 Прелиминарни и повезани радови

2.1 О стратегијама узорковања

2.2 Друге Цоресет стратегије

2.3 Корезети за апликације базе података

2.4 Куадтрее Ембеддингс

3 Фаст-Цоресетс

4 Смањење утицаја ширења

4.1 Израчунавање грубе горње границе

4.2 Од приближног решења до смањеног ширења

5 Брза компресија у пракси

5.1 Циљ и обим емпиријске анализе

5.2 Експериментално подешавање

5.3 Процена стратегија узорковања

5.4 Подешавање стриминга и 5.5 Такеаваис

6 Закључак

7 Признања

8 Докази, псеудо-код и проширења и 8.1 Доказ последице 3.2

8.2 Редукција к-средње вредности на к-медијану

8.3 Процена оптималне цене у стаблу

8.4 Проширења за алгоритам 1

Референце

Абстрацт

Проучавамо теоријске и практичне границе времена извођења к-средњих вредности и к-медијана груписања на великим скуповима података. Пошто су ефективно све методе груписања спорије од времена које је потребно за читање скупа података, најбржи приступ је брзо компресовање података и извођење груписања на компримованом представљању. Нажалост, не постоји универзални најбољи избор за компримовање броја тачака – док насумично узорковање тече у сулинеарном времену и језгрови пружају теоријске гаранције, прво не спроводи тачност док је друго преспоро како број тачака и кластера расте. Заиста, претпоставља се да било која конструкција језгра заснована на осетљивости захтева суперлинеарно време у величини скупа података.

Ми испитујемо овај однос тако што прво показујемо да постоји алгоритам који добија језгре путем узорковања осетљивости у ефективно линеарном времену – унутар лог-фактора времена потребног за читање података. Сваки приступ који значајно унапреди ово мора онда да прибегне практичној хеуристици, што нас наводи да размотримо спектар стратегија узорковања како у стварним тако и у вештачким скуповима података у статичким и стриминг поставкама. Кроз ово показујемо услове у којима су језгрови неопходни за очување ваљаности кластера, као и поставке у којима су довољне брже, грубље стратегије узорковања. Као резултат, пружамо свеобухватан теоријски и практични план за ефикасно груписање без обзира на величину података. Наш код је јавно доступан код извора и има скрипте за поновно креирање експеримената.

1 Увод

Савремени аналитичар података нема недостатак алгоритама за груписање између којих може да бира, али, с обзиром на све већу величину релевантних скупова података, многи су често преспоро да би били практично корисни. Ово је посебно релевантно за цевоводе великих података, где се алгоритми груписања обично користе за компресију. Циљ је да се веома велики скуп података замени мањим, управљивијим за низводне задатке, са надом да добро представља оригинални улаз. Лојдов алгоритам [49] је уведен управо из тог разлога и минимизира грешку квантизације – збир квадратног растојања од сваке улазне тачке до њеног представника у компримованом скупу података. Вероватно најпопуларнији алгоритам за груписање, Ллоид'с ради за више итерација до конвергенције са сваком итерацијом која захтева О(ндк) време, где је н број тачака, д је број карактеристика, а к је број кластера – или величина циљане компресије. За такве апликације, број тачака лако може бити стотине милиона, а пошто се квалитет компресије повећава са к, стандардни циљеви могу имати к у хиљадама [41, 4]. У таквим подешавањима, било који О(ндк) алгоритам је претерано спор.

Овакви примери су подстакли пораст алгоритама за велике податке који обезбеђују и теоријска и практична побољшања времена извршавања. Перспективе теоријске исправности и практичне ефикасности су, међутим, често у супротности једна са другом. С једне стране, теоријске гаранције обезбеђују сигурност да ће алгоритам функционисати без обзира на несрећне инпуте које прими. С друге стране, може бити тешко убедити себе да применимо теоретски оптимални алгоритам када постоје грубије методе које се брже функционишу и раде добро у пракси.

Пошто скупови података могу бити велики у броју тачака н и/или броју карактеристика д, методе великих података морају да ублаже ефекте оба. Што се тиче простора карактеристика, питање је практично затворено јер су насумичне пројекције брзе (покрећу се у ефективно линеарном времену), практичне за имплементацију [50] и пружају чврсте гаранције за величину и квалитет уградње. Изгледи су мање јасни када се смањи број тачака н, а постоје две одвојене парадигме од којих свака пружа јасне предности. С једне стране, имамо униформно узорковање, које се одвија у сулинеарном времену, али може пропустити важне подскупове података и стога може гарантовати тачност само под одређеним јаким претпоставкама о подацима [45]. С друге стране, најпрецизније стратегије узорковања обезбеђују снажну гаранцију скупа језгра, при чему је цена било ког решења на компримованим подацима унутар ε-фактора цене тог решења на оригиналном скупу података [25].

Наши доприноси Проучавамо обе парадигме (једнако узорковање и јаке језгре) у погледу класичног проблема – компресије за к-средње и к-медијане циљеве. Док униформно узорковање обезбеђује оптималну брзину, али не гарантује тачност у најгорем случају, све доступне конструкције језгра имају време рада од најмање Ω˜(нд + нк) када дају чврсте границе минималног броја узорака потребних за прецизну компресију.

Лако је показати да сваки алгоритам који постиже гаранцију компресије мора прочитати цео скуп података[1]. Стога је јасно отворено питање које се гаранције могу постићи у линеарном или скоро линеарном времену. Заиста, тренутно доступни алгоритми брзог узорковања за груписање [6, 5] не могу постићи јаке гаранције скупа језгра. Недавно је [31] предложио метод за јаке скупове језгра који се одвија у времену О˜(нд + нк) и претпоставио да је то оптимално за к-медијану и к-средње вредности.

Иако је ова граница ефективно оптимална за мале вредности к, постоје многе апликације као што су компјутерски вид [34] или алгоритамска праведност [18] где број кластера може бити већи од броја карактеристика за неколико редова величине. У таквим поставкама остаје отворено питање временски оптималних језгра. Пошто је питање одређивања скупа језгара оптималне величине недавно затворено [25, 28, 44], ово је вероватно главни отворени проблем у истраживању скупа језгара за кластерисање засновано на центру. Ово решавамо тако што показујемо да постоји алгоритам који се лако примењује и који конструише језгре у О˜(нд) времену – само логаритамски фактори удаљени од времена потребног за читање у скупу података.

Без обзира на то, ово не осветљава у потпуности пејзаж међу алгоритмима узорковања за груписање у пракси. Иако наш алгоритам постиже и оптимално време рада и оптималну компресију, свакако је могуће да и друге, грубље методе могу бити једнако одрживе за све практичне сврхе. Ово формално наводимо у следећем питању: Када су неопходне оптималне к-средње вредности и к-медијане језгре и који је практичан компромис између брзине скупа језгра и тачности?

о одговору на ово, вршимо темељно поређење у целом распону алгоритама узорковања који су бржи од нашег предложеног метода. Овим потврђујемо да, иако су ове брже методе довољно тачне за многе скупове података из стварног света, постоје дистрибуције података које узрокују катастрофалан неуспех за сваки од њих. Заиста, ови случајеви се могу избећи само методом јаког коресетовања. Стога, иако многа практична подешавања не захтевају потпуну гаранцију језгра, не можете да скренете углове ако желите да будете сигурни у њихову компресију. Потврђујемо да се ово протеже на парадигму стримовања и да се примењује на низводне приступе груписања.

Укратко, наши доприноси су следећи:

• Показали смо да се могу добити јаки скупови језгра за к-средње вредности и к-медијана у О˜(нд) времену. Ово разрешава претпоставку о неопходном времену извођења за к-меанс цоресетс [31] и теоретски је оптимално до лог фактора.

• Кроз свеобухватну анализу скупова података, задатака и парадигми стримовања/нестриминга, ми потврђујемо да постоји неопходан компромис између брзине и тачности између метода узорковања линеарног и сублинеарног времена. Ово даје практичару кластеризације нацрт када да користи сваки алгоритам компресије за ефективне резултате кластерисања у најбржем могућем времену.