Hogyan illeszthetünk el egy elefántot egy táblázatba

Hivatkozások táblázata

Absztrakt és 1 Bevezetés

2 Előkészületek és kapcsolódó munka

2.1 A mintavételi stratégiákról

2.2 Egyéb Coreset stratégiák

2.3 Magkészletek adatbázis-alkalmazásokhoz

2.4 Quadtree beágyazások

3 Fast-Coreset

4 A terjedés hatásának csökkentése

4.1 Nyers felső korlát kiszámítása

4.2 A hozzávetőleges megoldástól a csökkentett szórásig

5 Gyors tömörítés a gyakorlatban

5.1 Az empirikus elemzés célja és hatóköre

5.2 Kísérleti beállítás

5.3 A mintavételi stratégiák értékelése

5.4 Streaming beállítás és 5.5 Elvihető

6 Következtetés

7 Köszönetnyilvánítás

8 Bizonyítások, álkódok és kiterjesztések és 8.1 Következmény bizonyítása 3.2

8.2 A k-átlagok redukálása k-mediánra

8.3 Az optimális költség becslése egy fában

8.4 Az 1. algoritmus kiterjesztései

Hivatkozások

Absztrakt

Tanulmányozzuk a k-átlagok és a k-medián klaszterezés elméleti és gyakorlati futásidejű korlátait nagy adathalmazokon. Mivel gyakorlatilag minden fürtözési módszer lassabb, mint az adathalmaz kiolvasásához szükséges idő, a leggyorsabb módszer az adatok gyors tömörítése és a tömörített reprezentáció fürtözése. Sajnos nincs univerzális legjobb választás a pontok számának tömörítésére – míg a véletlenszerű mintavétel szublineáris időben fut, és a maghalmazok elméleti garanciákat adnak, addig az előbbi nem érvényesíti a pontosságot, míg az utóbbi túl lassú a pontok és klaszterek számának növekedésével. Valójában azt sejtették, hogy minden érzékenység alapú magkészlet-konstrukció szuperlineáris időt igényel az adatkészlet méretében.

Ezt az összefüggést úgy vizsgáljuk meg, hogy először megmutatjuk, hogy létezik olyan algoritmus, amely érzékenységi mintavétellel, ténylegesen lineáris időben – az adatok kiolvasásához szükséges idő log-tényezőin belül – nyer maghalmazokat. Minden olyan megközelítésnek, amely ezt jelentősen javítja, gyakorlati heurisztikákhoz kell folyamodnia, ami arra késztet bennünket, hogy figyelembe vegyük a mintavételi stratégiák spektrumát mind a valós, mind a mesterséges adatkészletekben a statikus és streaming beállításokban. Ezen keresztül megmutatjuk, hogy milyen körülmények között szükségesek a maghalmazok a klaszter érvényességének megőrzéséhez, illetve milyen beállítások esetén elegendőek a gyorsabb, nyersebb mintavételi stratégiák. Ennek eredményeként átfogó elméleti és gyakorlati tervezetet adunk a hatékony klaszterezéshez az adatmérettől függetlenül. Kódunk nyilvánosan elérhető a forrásnál, és szkriptjei vannak a kísérletek újbóli létrehozásához.

1 Bevezetés

A modern adatelemzőnek nincs hiánya klaszterezési algoritmusokból, de a releváns adatkészletek egyre növekvő mérete miatt sok gyakran túl lassú ahhoz, hogy gyakorlatilag hasznos legyen. Ez különösen fontos a nagy adatforgalmú folyamatok esetében, ahol a tömörítéshez általában klaszterezési algoritmusokat használnak. A cél az, hogy egy nagyon nagy adatkészletet lecseréljenek egy kisebb, jobban kezelhetőre a downstream feladatokhoz, abban a reményben, hogy jól reprezentálja az eredeti bemenetet. A Lloyd-algoritmus [49] éppen ezért került bevezetésre, és minimalizálja a kvantálási hibát – az egyes bemeneti pontok és a tömörített adathalmaz reprezentánsa közötti négyzetes távolság összegét. A vitathatatlanul legnépszerűbb fürtözési algoritmus, a Lloyd's többszörös iteráción fut a konvergenciáig minden O(ndk) időt igénylő iterációval, ahol n a pontok száma, d a jellemzők száma, k pedig a klaszterek száma – vagy a célzott tömörítés mérete. Az ilyen alkalmazásoknál a pontok száma könnyen elérheti a százmilliókat, és mivel a tömörítés minősége k-val növekszik, a standard objektívek k értéke több ezer is lehet [41, 4]. Ilyen beállítások mellett bármely O(ndk) algoritmus túlságosan lassú.

Az ehhez hasonló példák ösztönözték a big data algoritmusok térnyerését, amelyek mind elméleti, mind gyakorlati futásidejű fejlesztéseket biztosítanak. Az elméleti megalapozottság és a gyakorlati hatékonyság perspektívái azonban gyakran ellentétesek egymással. Egyrészt az elméleti garanciák biztosítékot adnak arra, hogy az algoritmus működni fog, függetlenül attól, hogy milyen szerencsétlen bemeneteket kap. Másrészt nehéz lehet rávenni magát az elméletileg optimális algoritmus megvalósítására, ha vannak nyersebb módszerek, amelyek gyorsabban indulnak be, és jól teljesítenek a gyakorlatban.

Mivel az adathalmazok nagyok lehetnek az n pontok és/vagy a d jellemzők számában, a big-data módszereknek mindkettő hatásait mérsékelniük kell. Ami a jellemzőteret illeti, a kérdés gyakorlatilag lezárt, mivel a véletlenszerű vetítések gyorsak (effektíve lineáris időben futnak), praktikusak [50], és szigorú garanciákat adnak a beágyazás méretére és minőségére. Az n pontok számának csökkentése során a kilátások kevésbé egyértelműek, és két különálló paradigma létezik, amelyek mindegyike külön előnyöket biztosít. Egyrészt egységes mintavételünk van, amely szublineáris időben fut, de előfordulhat, hogy az adatok fontos részhalmazai kimaradnak, és ezért csak bizonyos erős adatfeltevések mellett tudja garantálni a pontosságot [45]. Másrészt a legpontosabb mintavételi stratégiák az erős magkészlet garanciát adják, ahol a tömörített adatokon lévő bármely megoldás költsége egy ε-tényezőn belül van az eredeti adatkészleten lévő megoldás költségéhez képest [25].

Hozzájárulásaink Mindkét paradigmát (az egységes mintavételt és az erős maghalmazokat) tanulmányozzuk egy klasszikus probléma – a k-átlagok és a k-medián célkitűzések tömörítése – vonatkozásában. Míg az egyenletes mintavételezés optimális sebességet biztosít, de nem garantálja a legrosszabb eset pontosságát, az összes rendelkezésre álló magkészlet-konstrukció futási ideje legalább Ω˜(nd + nk), amikor a pontos tömörítéshez szükséges minimális számú minta szigorú határokat ad.

Könnyen kimutatható, hogy minden tömörítési garanciát elérő algoritmusnak be kell olvasnia a teljes adatkészletet[1]. Így egyértelmű nyitott kérdés, hogy lineáris vagy közel lineáris időben milyen garanciák érhetők el. Valójában a klaszterezéshez jelenleg rendelkezésre álló gyors mintavételi algoritmusok [6, 5] nem tudnak erős magkészlet-garanciákat elérni. Nemrég [31] olyan módszert javasolt erős magkészletekre, amelyek O˜(nd + nk) időben futnak, és azt sejtették, hogy ez optimális a k-medián és a k-közép szempontjából.

Míg ez a korlát gyakorlatilag optimális kis k értékeihez, számos olyan alkalmazás létezik, mint például a számítógépes látás [34] vagy az algoritmikus igazságosság [18], ahol a klaszterek száma több nagyságrenddel nagyobb lehet, mint a jellemzők száma. Ilyen beállításoknál az idő-optimális magkészletek kérdése nyitva marad. Mivel az optimális méretű maghalmaz meghatározásának kérdése a közelmúltban lezárult [25, 28, 44], vitathatatlanul ez a fő nyitott probléma a központ alapú klaszterezés maghalmaz-kutatásában. Ezt úgy oldjuk meg, hogy megmutatjuk, hogy létezik egy könnyen megvalósítható algoritmus, amely O˜(nd) idő alatt állítja össze a maghalmazokat – csak logaritmikus tényezőket veszünk figyelembe az adathalmaz beolvasásának idejétől.

Mindazonáltal ez nem világítja meg teljes mértékben a gyakorlatban a klaszterezés mintavételi algoritmusainak helyzetét. Bár az algoritmusunk optimális futási időt és optimális tömörítést is elér, minden bizonnyal lehetséges, hogy más, nyersebb módszerek is ugyanolyan életképesek lehetnek minden gyakorlati célra. Ezt formálisan a következő kérdésben fogalmazzuk meg: Mikor szükségesek az optimális k-közép és k-medián magkészletek, és mi a gyakorlati kompromisszum a magkészlet sebessége és pontossága között?

Ennek megválaszolásához alapos összehasonlítást végzünk a javasolt módszerünknél gyorsabb mintavételi algoritmusok teljes skáláján. Ezzel ellenőrizzük, hogy bár ezek a gyorsabb módszerek kellően pontosak sok valós adatkészleten, léteznek olyan adateloszlások, amelyek mindegyiknél katasztrofális kudarcot okoznak. Valójában ezek az esetek csak erős-coreset módszerrel kerülhetők el. Így bár sok gyakorlati beállítás nem igényli a teljes magkészlet garanciát, az ember nem vághat bele, ha biztos akar lenni a tömörítésben. Ellenőrizzük, hogy ez kiterjed-e a streaming paradigmára, és vonatkozik-e a downstream klaszterezési megközelítésekre.

Összefoglalva, hozzájárulásaink a következők:

• Megmutatjuk, hogy O˜(nd) idő alatt erős maghalmazokat kaphatunk k-középre és k-mediánra. Ez megoldja a k-közép magkészletek szükséges futási idejére vonatkozó sejtést [31], és elméletileg optimális a log-faktorokig.

• Az adatkészletek, feladatok és streaming/nem streaming paradigmák átfogó elemzésével igazoljuk, hogy a lineáris és szublineáris idejű mintavételi módszerek között megvan-e a szükséges kompromisszum a sebesség és a pontosság között. Ez a fürtözést végző szakember számára vázlatot ad arra vonatkozóan, hogy mikor kell használni az egyes tömörítési algoritmusokat a hatékony fürtözési eredmények érdekében a lehető leggyorsabban.