Premium

Získejte všechny články
jen za 89 Kč/měsíc

Clustering dat pomáhá nalézt jehlu v kupce sena

Na počítače jsme si zvykli pohlížet jako na exaktní stroje zpracovávající exaktní data. Počítače po desetiletí provádějí numerické výpočty, zpracovávají databáze nebo luští šifry. Co když bychom však počítače požádali, aby srovnával podobnost mezi různými soubory s nestrukturovanými daty nebo dokonce odvodil jejich vzájemnou hierarchii?
Na počítače jsme si zvykli pohlížet jako na exaktní stroje zpracovávající exaktní data. Počítače po desetiletí provádějí numerické výpočty, zpracovávají databáze nebo luští šifry. Co když bychom však počítače požádali, aby srovnával podobnost mezi různými soubory s nestrukturovanými daty nebo dokonce odvodil jejich vzájemnou hierarchii?

Pracovníci tiskového oddělení sledují v monitoringu tisku všechny zmínky o své společnosti. Rádi by zprávy automaticky třídili dle témat, avšak témata článků se však průběžně mění. Dokázal by počítač setřídit témata, aniž by uživatelé tušili, jaká různá témata se objeví zítra? Produktoví manažeři chtějí důkladně zmapovat trh, výrobky se však liší v mnoha kritériích. Uměl by počítač najít skupiny výrobků a jejich vzájemné vztahy? Složka s doručenými e-maily obsahuje tisíce neroztříděných zpráv. Šlo by je automaticky roztřídit? Plagiáty slohových prací nejsou totožné do posledního bitu, dokázal by je však počítač odhalit?

Hodil by se nám algoritmus, který by posoudil podobnost dvou různých entit a přiřadil jí nějaké skóre. Výsledky srovnávání bychom uložili do matice a z nich bychom usuzovali na vzájemnou příbuznost. První fáze clusteringu skutečně probíhá podobným způsobem. Vezmeme některou z entit, postupně porovnáváme její podobnost se všemi ostatními a do společného clusteru k vybrané entitě zařazujeme všechny ostatní, jejichž míra podobnosti přesahuje určitý práh. Na konci tohoto kroku nám zbyde první cluster a ostatní entity, které se do něj nevešly. v dalším kroku tedy budeme hledat druhý cluster mezi nimi. Později se dostaneme do fáze, kdy další clustery již nemůžeme vytvářet a kromě již hotových clusterů nám zbyde jen nesourodá směs některých nezařazených entit. Některé algoritmy jdou ještě dále a dynamicky mění práh podobnosti globálně i pro jednotlivé clustery, aby dosáhly vyrovnané velikosti různých clusterů.

Shluky dat

Pokud jsme chtěli třídit články v monitoringu tisku, clustery udělaly většinu práce za nás. Clustering článků na internetu nabízí hned několik serverů zcela zdarma. Všeobecné zpravodajtví v češtině z různých zdrojů třídí automaticky server Novyden.cz, technologické zpravodajství server Prehled.net. Na světovém webu fungují podobným způsobem Google News, Topix.net či MSN Newsbot. Zvláště server Topix.net ovšem využívá hybridní přístup, zprávy třídí do velkého množství předem definovaných kategorií, clustering pak probíhá uvnitř kategorií a z každého clusteru je zobrazena pouze jediná zpráva. Při fulltextovém hledání ve zprávách však Topix.net ukazuje všechny zprávy v každém clusteru a žádné neschovává.

Clusterování výsledků dotazů kladených ad hoc je náročné na výpočetní výkon i na paměť serveru. Vypočtené hodnoty míry podobnosti dvojic je však možné ukládat do vyrovnávací paměti.

Pokud se budeme pídit po hierarchii mezi jednotlivými entitami, můžeme je malé clustery spolu sluřovat podle vzájemné podobnosti nwbo velké clustery dělit na menší. Nakonec nám vznikne stromová struktura, která hierarchii vystihne. Můžeme tak získat diagramy vyjadřující podobnost automobilů, podobnost složení mateřského mléka u různých savců nebo příbuznost různých druhů skotské whisky.

Co je pod kapotou

Zajímavý je matematický postup, pomocí kterého změříme podobnost dvou různých textů. Je možné hledat nejdelší posloupnost znaků, která se objevuje v obou textech současně, a jako skóre použít její délku. V praxi se však nejčastěji používá kosínová podobnost (cosine similarity), při jejímž výpočtu si oba texty představýme jako mnhorozměrné vektory. Každá složka obou vektorů odpovídá počtu výskytů jiného klíčového slova, vektory dvou podobných textů tedy jakoby ukazují podobným směrem. Provedeme-li skalární součin vektorů a vydělíme-li jej součinem jejich absolutních hodnot, získáme hodnotu kosínu úhlu sevřeného oběma vektory. Ta je rovná jedné, pokud jsou oba texty totožné, s nižší podobností vektorů klesá i velikost kosínu sevřeného úhlu. Kosínová podobnost je spolehlivou a osvědčenou metodou, její různé modifikace dávají ještě lepší výsledky.

Radikálně jiný postup navrhla trojice italských vědců ve své práci Language Trees and Zipping. Vycházeli z funkce algoritmů pro kompresi dat, jaké využívá například populární formát Zip. Kompresní algoritmy například z rodiny Lempel-Ziv se zpravidla na vstupních datech postupně "učí" a hledají opakující se sekvence bajtů ve vyrovnávací paměti. Pokud tedy dva texty zkopírujeme do jediného textového souboru a ten zkomprimujeme, délka komprimovaného souboru by měla být tím nižší, čím jsou si oba texty podobné. Pokud porovnáme velikost komprimovaného souboru obsahující jeden textový soubor s oběma texty se součtem velikostí dvou souborů obsahujících vždy jediný text, můžeme spočítat skóre vyjadřující podobnost dvou textů. (Pozorovaný efekt je mimochodem využíván kompresními programy řady RAR při vytváření takzvaných solid archives). Autoři porovnávali vzájemnou podobnost evropských jazyků, výsledky velmi dobře odpovídaly vzájemné příbuznosti jazyků a

Jinou implementací tohoto algoritmu je volně šiřitelný program FindFraud pro nalezení plagiátů mezi texty či zdrojovými kódy programů odevzdávanými studenty. Podobně je možné srovnávat i jiná data, jako třeba sekvence DNA.

Díky zvyšujícímu se výkonu a kapacitě počítačů i rostoucímu povědomí odborné veřejnosti o clusterování dokumentů se s touto metodou budeme setkávat stále častěji. Clusterování se již spíše než konkurenní výhodou stává holou nutností. To by si měli uvědomit IT manažeři při poptávání software nebo služeb pro zpracovávání databází i vývojáři při návrhu tohoto software. Samotné fulltextové vyhledávání nemusí uživatelům stačit.

Více informací najdete na www.telnet.cz.

  • Nejčtenější

Na to jsme čekali: revoluční funkce Bluetooth konečně míří do produktů

Berlín (od zpravodaje Technet.iDNES.cz) Tichá diskotéka nebo letní kino? Patera sluchátka u jednoho televizoru? Hlas průvodce z vlastních sluchátek? Nejen to umožní nová funkce Bluetooth nazvaná Auracast – k jednomu přehrávacímu zařízení...

6. září 2024

Loď Starliner se vrací. Anatomie průšvihu Boeingu, jaký tu ještě nebyl

Kosmická loď Starliner, která se vrací z Mezinárodní kosmické stanice, nese na paměť výzkumné lodi oceánografa Jacquese Cousteaua hrdý název Calypso. Vzhledem k technickým problémům a veletočům,...

6. září 2024

{NADPIS reklamního článku dlouhý přes dva řádky}

{POPISEK reklamního článku, také dlouhý přes dva a možná dokonce až tři řádky, končící na tři tečky...}

Houstone, co je to za zvuky? NASA zjistila, co „ťuká“ v Boeingu u ISS

Kosmická loď Starliner vyvolává další a další otázky. Stroj, který společnost Boeing vyslala k Mezinárodní vesmírné stanici při první testovací pilotované misi, se nyní znovu doslova ozval. Alespoň...

3. září 2024  9:43

Konec učení jazyků se blíží. Vyzkoušeli jsme nová sluchátka s překladačem

Premium

Berlín (od zpravodaje Technet.iDNES.cz) Jako ve Star Treku by si mohli připadat uživatelé sluchátek Timekettle W4 PRO, které měly na veletrhu IFA 2024 světovou premiéru. Mají zvládnout překládat 40 jazyků a 93 akcentů. Firma slibuje až...

7. září 2024

{NADPIS reklamního článku dlouhý přes dva řádky}

{POPISEK reklamního článku, také dlouhý přes dva a možná dokonce až tři řádky, končící na tři tečky...}

Byly potíže, ale Starliner je zpět. Dobré přistání, hlásila posádka z vesmíru

S několikaměsíčním zpožděním se na Zemi vrátila kosmická loď Starliner. Samotné přistání proběhlo bez nehody, ale i tak zůstanou manažerům Boeingu z tohoto první testovacího letu s posádkou vrásky...

7. září 2024  7:50,  aktualizováno  8:50

Odstartovala mise, při níž miliardář s posádkou vystoupí do volného kosmu

Po mnoha odkladech se se konečně povedl start posádky čtyř soukromých astronautů na riskantní misi Polaris Dawn, při níž se pokusí o historicky první soukromý výstup do vesmíru s využitím nových...

10. září 2024  8:10,  aktualizováno  11:24

FOTODUEL: Neuvěřitelné klávesnice. Která se vám líbí nejvíce?

Krásné, vtipné, trhlé, nápadité, praktické, nepraktické, kýčovité, nevkusné ... na veletrhu IFA 2024 jsme potkali obrovské množství klávesnic, které mezi návštěvníky poutaly nečekanou pozornost a...

10. září 2024

AirPods mají potlačení okolního hluku, verze Pro zastane naslouchátko

Apple na svém podzimním uvedení novinek aktualizoval celou svoji nabídku sluchátek. AirPods 4 a AirPods Pro 2 výrazněji, model Max jen trochu.

9. září 2024  21:12

První soukromá mise s výstupem do volného vesmíru přiblíží lidstvo k Marsu

Opakované průlety radiačními pásy Země, testování nových skafandrů pro výstup do otevřeného prostoru, skoro čtyřicet vědeckých experimentů. Takovouto náplň kosmického letu zřejmě čekáte od NASA nebo...

9. září 2024

Soutěžte s ČPZP a vyhrajte dárkový balíček
Soutěžte s ČPZP a vyhrajte dárkový balíček

Tento týden pro vás máme soutěž s Českou průmyslovou zdravotní pojišťovnou. Stačí odpovědět na jednoduchou soutěžní otázku a jeden z pěti dárkových...

Pavel Novotný zdrtil v kleci Zdeňka Godlu. Herce odváděli zdravotníci

Herec Zdeněk Godla (49) se v sobotu během galavečera Clash of the Stars utkal v kleci se starostou Řeporyjí Pavlem...

Herečka Anna Polívková se na pláži provdala za italského přítele

Herečka Anna Polívková (45) se v sobotu provdala. Svatba se uskutečnila v Itálii, protože manžel české herečky odtamtud...

Pro syna chtěla lepší partii. Těhotnou snachu rozpůlila a pohřbila ve sklepě

Premium Seděl ve služebně Veřejné bezpečnosti a otázky příslušníků mu byly evidentně nepříjemné. „Proč jste nenahlásil zmizení...

Schwarzenegger se v Praze proháněl na kole. Vyfotil se také s „Klukem s kamením“

Legendární herec a bývalý guvernér Kalifornie Arnold Schwarzenegger (77) je v Praze. O víkendu si užíval kávu na...

Za úklid orální sex. Katy Perry popsala vztah s Orlandem Bloomem

Zpěvačka Katy Perry (39) se rozpovídala v podcastu Call Her Daddy o svém vztahu s hercem Orlandem Bloomem (47)....