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.
