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ší

Kam pro filmy bez Ulož.to? Přinášíme další várku streamovacích služeb do TV

v diskusi je 125 příspěvků

26. března 2024

S vhodnou aplikací na vás mohou v televizoru na stisk tlačítka čekat tisíce filmů, seriálů nebo...

Z jaderné triády zbyly Britům už jen ponorky. A ty musejí posílit

v diskusi je 76 příspěvků

27. března 2024

Jadernou triádu tvoří strategické bombardéry s jadernými zbraněmi, mezikontinentální balistické...

{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...}

Hlučínsko patří nám. Před 100 lety byl podepsán definitivní protokol o hranici

v diskusi je 41 příspěvků

28. března 2024

Před 100 lety definitivně skončily tahanice o československo-německé hranice. 28. března 1924 byl...

Rusko zastavilo odlet na ISS s první Běloruskou, letět měla i Američanka

v diskusi je 50 příspěvků

21. března 2024  10:23,  aktualizováno  14:26

Ve čtvrtek 21. března se necelých deset minut před půl třetí odpoledne měla vydat na Mezinárodní...

{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...}

Američané odepsali modul, který je vrátil po půl století na Měsíc

v diskusi je 20 příspěvků

28. března 2024,  aktualizováno  11:41

Od začátku letošního roku je na Měsíci a kolem něj poměrně rušno. Vedle řady sond, které zamířily...

Za vyhynutím dinosaurům mohla být i doba temna

v diskusi nejsou příspěvky

29. března 2024

Dopad planetky je nyní většinou odborníků považován za hlavní příčinu vyhynutí zhruba 73 až 76 %...

Podívejte se na Boeing C-17 Globemaster, který do Česka přivezl nové vrtulníky

v diskusi nejsou příspěvky

29. března 2024

V sobotu 23. března dosedl v Praze nákladní letoun USAF, který vezl obzvlášť cenný náklad. Z...

Dočasná raketa se po téměř 70 letech loučí. Bude startovat naposledy

v diskusi jsou 4 příspěvky

28. března 2024  15:36,  aktualizováno  19:54

Tento čtvrtek stojí na startovací rampě mysu Canaveral poslední potomek raket Thor, nosič Delta IV...

Američané odepsali modul, který je vrátil po půl století na Měsíc

v diskusi je 20 příspěvků

28. března 2024,  aktualizováno  11:41

Od začátku letošního roku je na Měsíci a kolem něj poměrně rušno. Vedle řady sond, které zamířily...

Akční letáky
Akční letáky

Všechny akční letáky na jednom místě!

Smoljak nechtěl Sobotu v Jáchymovi. Zničil jsi nám film, řekl mu

Příběh naivního vesnického mladíka Františka, který získá v Praze díky kondiciogramu nejen pracovní místo, ale i...

Rejžo, jdu do naha! Balzerová vzpomínala na nahou scénu v Zlatých úhořích

Eliška Balzerová (74) v 7 pádech Honzy Dědka přiznala, že dodnes neví, ve který den se narodila. Kromě toho, že...

Pliveme vám do piva. Centrum Málagy zaplavily nenávistné vzkazy turistům

Mezi turisticky oblíbené destinace se dlouhá léta řadí i španělská Málaga. Přístavní město na jihu země láká na...

Kam pro filmy bez Ulož.to? Přinášíme další várku streamovacích služeb do TV

S vhodnou aplikací na vás mohou v televizoru na stisk tlačítka čekat tisíce filmů, seriálů nebo divadelních...

Stále víc hráčů dobrovolně opouští Survivor. Je znamením doby zhýčkanost?

Letošní ročník reality show Survivor je zatím nejkritizovanějším v celé historii soutěže. Může za to fakt, že už...