Szerzői:  (1) Andrew Draganov, az Aarhusi Egyetem és minden szerző egyformán hozzájárult ehhez a kutatáshoz;  (2) David Saulpic, Université Paris Cité & CNRS;  (3) Chris Schwiegelshohn, Aarhusi Egyetem.  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.  Ez a papír a CC BY 4.0 DEED licenc alatt   .  érhető el az arxiv oldalon

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Scripting.tech

Weaving spells of logic and creativity, bringing ideas to life, and automating the impossible.

scripting's blog

Ez a hanganyag a történet eredeti nyelvén készült!

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

About Author

HOZZÁSZÓLÁSOK

HANG TAGOK

EZT A CIKKET BEMUTATTA

Related Stories

THE LAST DAY OF NEW YORK

A SECOND ENIGMA

Of The First and Last Things: Part 1

THE HABITS OF INSECTS IN RELATION TO THE FERTILISATION OF FLOWERS

THE LAST DAY OF NEW YORK

A SECOND ENIGMA

Of The First and Last Things: Part 1

THE HABITS OF INSECTS IN RELATION TO THE FERTILISATION OF FLOWERS

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps