Čínský šepot (metoda shlukování) - Chinese Whispers (clustering method)

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Červen 2015)

Čínský šepot je shlukovací metoda používaná v síťové vědě pojmenovaná po slavné šeptající hra.^[1] Metody shlukování se v zásadě používají k identifikaci komunit uzlů nebo odkazů v dané síti. Tento algoritmus navrhl Chris Biemann a Sven Teresniak v roce 2005.^[1] Název vychází ze skutečnosti, že proces lze modelovat jako oddělení komunit, kde si uzly navzájem posílají stejný typ informací.^[1]

Chinese Whispers je tvrdé rozdělení, randomizované, ploché shlukování (č hierarchické vztahy mezi klastry ) metoda.^[1] Náhodná vlastnost znamená, že několikanásobné spuštění procesu ve stejné síti může vést k různým výsledkům, zatímco kvůli pevnému rozdělení může jeden uzel v daném okamžiku patřit pouze jednomu klastru. Původní algoritmus je použitelný pro neorientované, vážené a nevážené grafy. Čínský šepot je časově lineární, což znamená, že je extrémně rychlý, i když je počet uzlů a odkazů v síti velmi vysoký.^[1]

Algoritmus

Příklad toho, jak funguje čínský šepot v akci. Různé barvy představují různé třídy.

Algoritmus pracuje následujícím způsobem v neorientovaném neváženém grafu:^[1]

1. Všechny uzly jsou přiřazeny k odlišné třídě (Počet počátečních tříd se rovná počtu uzlů).
2. Pak jsou všechny síťové uzly vybrány jeden po druhém v náhodném pořadí. Každý uzel se přesune do třídy, kterou daný uzel spojuje s největším počtem odkazů. V případě rovnosti je shluk náhodně vybrán ze stejně propojených tříd.
3. Krok dva se opakuje, dokud nedojde k předem určenému počtu iterací nebo dokud proces nedojde ke konvergenci. Nakonec vznikající třídy představují klastry sítě.

Je nutná předem stanovená prahová hodnota pro počet iterací, protože je možné, že proces nekonverguje. Na druhou stranu v síti s přibližně 10 000 uzly se klastry po 40–50 iteracích významně nezmění, i když nedochází ke konvergenci.^[1]

Silné a slabé stránky

Hlavní síla čínského šepotu spočívá v jeho časové lineární vlastnosti. Protože doba zpracování se zvyšuje lineárně s počtem uzlů, je algoritmus schopen velmi rychle identifikovat komunity v síti. Z tohoto důvodu je Chinese Whispers dobrým nástrojem k analýze struktur komunity v grafu s velmi vysokým počtem uzlů. Účinnost metody se dále zvyšuje, pokud síť má malý světový majetek.^[1]

Na druhou stranu, protože algoritmus není v případě malého počtu uzlů deterministický, výsledné klastry se od sebe často významně liší. Důvodem je to, že v případě malé sítě záleží více na tom, od kterého uzlu začne iterační proces, zatímco ve velkých sítích zmizí relevance výchozích bodů.^[1] Z tohoto důvodu se u malých grafů doporučují jiné metody shlukování.

Aplikace

Čínský šepot se používá v mnoha oborech síťové vědy. Nejčastěji je zmiňován v kontextu zpracování přirozeného jazyka problémy.^[2][3] Na druhou stranu je algoritmus použitelný na jakýkoli druh problému identifikace komunity, který souvisí se síťovým rámcem. Chinese Whispers je k dispozici pro osobní použití jako rozšiřující balíček pro Gephi^[4] což je otevřený zdroj program určený pro síťovou analýzu.

Reference

externí odkazy

• Implementace v Pythonu