M A S A R Y K O V A UNIVERZITA F A K U L T A I N F O R M A T I K Y ^ÄS Rozpoznání anomálních uživatelů na českém Twitteru D I P L O M O V Á PRÁCE Petr Jirásek Brno, jaro 2015 Prohlášení Prohlašuji, že tato diplomová práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. Petr Jirásek Vedoucí práce: doc. RNDr. Lubomír Popelínský, Ph.D. i Klíčová slova Dolování z dat, detekce odlehlých bodů, rozpoznání anomálních uživatelů, Twitter, klasifikace sentimentu ii Poděkování Rád bych poděkoval vedoucímu práce doc. RNDr. Lubomíru Popelínskému, Ph.D. za jeho odborné vedení a věcné rady. Dále bych rád poděkoval své rodině za podporu při psaní této práce a svým přátelům za poskytnutí zpětné vazby. Zvláště bych rád poděkoval Jiřímu Jiráskovi a Josefu Buryanovi za pomoc při anotaci dat. iii Shrnutí Diplomová práce se zabývá návrhem metody pro rozpoznání anomálních uživatelů na sociální síti Twitter, jejich charakteristikou a vlivem metody odstranění anomálií na výsledky klasifikace. V práci je čtenář seznámen se specifiky sociální sítě Twitter a způsobem dolování získaných dat. Dále práce specifikuje pojem anomálního a normálního uživatele a popisuje existující přístupy v této oblasti. V hlavní části práce je podrobně popsána navržená metoda včetně výsledků testovaných přístupů. Následuje analýza anomálních uživatelů a jejich charakteristika doplněná o příklady. Zvláštní pozornost je pak věnována klasifikaci sentimentu a ověření vlivu navržené metody na výsledky klasifikace. iv Obsah 1 Úvod 1 2 Dolování dat z Twitteru a jeho specifika 3 2.1 Sociální síť Twitter 3 2.1.1 Terminologie 4 2.1.2 Specifika sítě 5 2.1.3 Komunity 6 2.2 Dolování z dat a detekce anomálií 6 2.3 Dolování dat z Twitteru 7 2.3.1 Twitter API 8 2.3.2 Česká datová sada 8 2.3.3 Anglická datová sada 10 3 Anomální uživatelé a existující metody pro jejich detekci . . . 11 3.1 Kdo je to anomální a normální uživatel? 11 3.2 Motivace pro hledání anomálních uživatelů 12 3.3 Existující metody 12 3.3.1 Detekce robotických účtů s využitím klasifikace . . 12 3.3.2 Detekce spam účtů s využitím klasifikace 13 3.3.3 Detekce spam účtů seskupením uživatelů 14 3.3.4 Detekce spam účtů metodou shlukování 15 4 Návrh metody pro rozpoznání anomálních uživatelů 17 4.1 Informace o uživateli 17 4.1.1 Chování uživatele a informace o jeho účtu 17 4.1.2 Časové informace 21 4.1.3 Obsah příspěvků 21 4.2 Anotace uživatelů 22 4.3 Předzpracování příspěvků 23 4.4 Výběr atributů 24 4.4.1 Chování atributů 24 4.4.2 Výběr pomoci selektivních algoritmů 27 4.4.3 Testování a konečný výběr 29 4.5 Testované přístupy a jejich výsledky 30 4.5.1 Učení bez učitele 31 4.5.2 Učení z klasifikovaných a neklasifikovaných příkladů 34 4.5.3 Učení s učitelem 35 4.6 Shrnutí 37 v 5 Charakteristika anomálních uživatelů 39 5.1 Shlukování anomálních uživatelů 39 5.1.1 Hierarchické shlukování 40 5.1.2 K-means 41 5.2 Charakteristiky uživatelů 42 5.2.1 Robotické účty 42 5.2.2 Spamúčty 43 5.2.3 RSS čtečky, informační a propagační účty 43 5.2.4 Jednosmerne tématicky zaměřené účty 44 6 Klasifikace a vliv anomálních uživatelů 45 6.1 Klasifikace sentimentu 45 6.2 Učení na základě emotikonů 45 6.3 Trénovací množina 46 6.4 Testovací množina 47 6.5 Výsledky klasifikace do tří tříd 48 6.5.1 Bez odstranění anomálních uživatelů 48 6.5.2 Po odstranění anomálních uživatelů 48 6.6 Výsledky klasifikace do dvou tříd 52 6.6.1 Bez odstranění anomálních uživatelů 52 6.6.2 Po odstranění anomálních uživatelů 53 6.6.3 Využití pro klasifikaci do tří tříd 56 6.7 Shrnutí 57 7 Závěr 59 A Nástroj pro anotaci uživatelů 67 B Obsah přiložených souborů 68 vi 1 Úvod Poslední roky zažíváme rozmach sociálních sítí a rozsáhlých komunitních služeb, které využívají miliony uživatelů a zanechávají zde svá data, ať už se jedná o osobní informace nebo informace o svém chování v kontextu používané služby. S ohledem na současný trend dolování informací je tak možné data z těchto služeb využít k hlubší analýze a hledat mezi daty skryté závislosti a jevy, které nám mohou pomoci pochopit chování uživatelů a vazby mezi nimi. Příkladem takového chování může být jednání osoby snažící se šířit hromadné nevyžádané zprávy nebo chování osoby vykazující podezřelou aktivitu v kontextu svého okolí nadměrným užíváním zřídka se vyskytujících klíčových slov. Sociální síť Twitterje jednou z největších sociálních sítí na světě. Odhaduje se, že její počet měsíčně aktivních uživatelů dosahuje 288 miliónů [1]. I mezi uživateli na sociální síti Twitter se nacházejí účty, které se chovají odlišně než ostatní a jedná se o tzv. anomální uživatele. Jejich nalezením můžeme analyzovat, zda se tito uživatelé nechovají proti obecným pravidlům sítě, zda se kupříkladu jedná o tzv. robotické účty nebo pouze o účty, které se v některých ze svých znaků chovají příliš odlišně. Twitter netvoří pouze uživatelské profily, ale jsou to především příspěvky a obsah, který uživatelé vytváří. Obsah, který je díky jeho velikosti a dostupnosti ve strojově čitelné podobě dále možné využít pro účely klasifikace a jiných metod nejen z oblasti strojového učení. Lze tak prostřednictvím těchto dat kupříkladu učit různé nástroje, které jsou schopny rozpoznat téma příspěvku nebo určit jeho sentiment [2, 3]. Úspěšnost těchto nástrojů je ale zpravidla tak dobrá, jak dobrá jsou data, z kterých se nástroje učí. Cílem této práce je tedy navrhnout metodu pro rozpoznání anomálních uživatelů, provést jejich charakteristiku a ověřit vliv informace o anomálních uživatelích na výsledky klasifikace sentimentu na sociální síti Twitter. Práce je rozdělena do několika kapitol. V kapitole 2 se seznámíme se sociální síti Twitter, pojmem dolování z dat a způsobem dolování dat z této sítě. V následující kapitole je věnována pozornost pojmu anomální uživatel a existujícím přístupům pro detekci některých podskupin těchto uživatelů. Ve čtvrté kapitole se práce zabývá návrhem metody pro rozpoznání anomálních uživatelů a jejími výsledky. Poté následuje kapitola zabývající se charakteristikou anomálních uživatelů doplněná o příklady. V šesté kapitole je věnována pozornost klasifikaci sentimentu a vlivu informace o anomálních 1 1. Ú V O D uživatelích na výsledky klasifikace při použití navržené metody. Poslední kapitola pak obsahuje závěrečné shrnutí výsledků a možná pokračování této práce. 2 2 Dolování dat z Twitteru a jeho specifika V první části se kapitola zabývá základním popisem sociální sítě Twitter ajejich specifik včetně popisu základní terminologie. V další části pak představuje stručný úvod do oblasti dolování z dat a detekci anomálií a poté se dále zaměřuje na dolování dat z českého a anglického Twitteru. Popisuje heuristiky pro získání dat a doplňuje související informace. 2.1 Sociální síť Twitter Sociální síť Twitter je jednou z největších sociálních sítí a řadí se svou velikosti k sítím jako Facebook nebo Instagram [4]. Svým charakterem se jedná o mikroblogovací službu, kde uživatelé vkládají příspěvky krátké velikosti (tzv. tweet) s maximální délkou 140 znaků na svou nástěnku a mohou zároveň reagovat na příspěvky ostatních. Právě svým omezením na počet znaků se sociální síť Twitter výrazně odlišuje od ostatních sociálních sítí. Příspěvky mohou obsahovat kromě textu také odkazy, zmínky uživatelů nebo klíčová slova, což pomáhá k větší interakci v rámci sítě a umožňuje uživatelům vyhledávat zprávy dle jejich oblasti zájmu. Uživatelé mohou od jiných uživatelů odebírat jejich zprávy a zároveň mají své vlastní odběratele. Dále mohou příspěvky uživatelů, od kterých odebírají obsah, označit jako oblíbené nebo převzít a sdílet svým odběratelům umístěním zprávy na svou nástěnku. Právě díky funkci převzetí příspěvku dochází k rychlému šíření informací v síti, přičemž taková informace může být pravdivá, ale také falešná (viz. případ napadení účtu tiskové agentury [5]). Obrázek 2.1 zobrazuje ukázku profilu uživatele s příspěvky na sociální síti Twitter. 3 2. D O L O V Á N Í DAT Z T W I T T E R U A JEHO SPECIFIKA ^ Petr Jirásek gPelrJiragek Mař 3 Vyh od a komu n ikace s vývojářem z N oveh o Zéland u je ta. ze mame sladenou pracovni dobu. Aspoň v mem pripade:oj i | Petr Jirásek @PetjJirasel< • Feb27 Poprvé se mi podařilo dostat cas na 5 km pod 25 min. Novy osobák je 24:53, i když to tempo bylo pro me trochu drasticky.:) #running | Petr Jirásek gPeuJirasek Feb22 Přehled informaci pro desitinace vhodne k digitálnímu nomadstvi nomadlist.coir Povedeny web. hezl?/ zpracovaný. «> o * 1
  • Úspěšnost Přesnost F-míra Unigramy YATSI-NBM 65,0 % 77,0 % 60,6 % Unigramy YATSI-RF 70,4 % 71,9 % 69,9 %Unigramy CF 87,5 % 87,7 % 87,5 % Bigramy YATSI-NBM 59,6 % 71,3 % 53,1 % Bigramy YATSI-RF 54,6 % 76,2 % 42,8 %Bigramy CF 90,0 % 90,0 % 90,0 % Uni + big YATSI-NBM 60,4 % 77,9 % 53,1 % Uni + big YATSI-RF 88,3 % 88,4 % 88,3 %Uni + big CF 90,8 % 90,8 % 90,8 % Tabulka 4.10: Výsledky metod učení z klasifikovaných a neklasifikovaných příkladů pro anglickou množinu Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 80,0 % 85,7 % 79,2 % Unigramy SVM 68,0 % 80,5 % 64,3 % Unigramy RF 88,0 % 88,2 % 88,0 %Unigramy J48 85,0 % 85,4 % 85,0 % Unigramy Vote 89,0 % 89,8 % 88,9 % Bigramy N B M 76,0 % 83,8 % 74,5 % Bigramy SVM 82,0 % 86,8 % 81,4% Bigramy RF 83,0 % 83,3 % 83,0 %Bigramy J48 88,0 % 88,1 % 88,0 % Bigramy Vote 89,0 % 89,8 % 88,9 % Uni + big N B M 78,0 % 84,7 % 76,9 % Uni + big SVM 66,0 % 79,8 % 61,6 % Uni + big RF 86,0 % 86,5 % 85,9 %Uni + big J48 87,0 % 87,1 % 87,0 % Uni + big Vote 89,0 % 90,3 % 88,9 % Tabulka 4.11: Výsledky metod učení s učitelem pro českou množinu 36 4. NÁVRH METODY PRO ROZPOZNÁNÍ ANOMÁLNÍCH UŽIVATELŮ Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 77,0 % 82,8 % 75,9 % Unigramy SVM 56,0 % 76,6 % 45,4 % Unigramy RF 92,0 % 92,1 % 92,0 %Unigramy J48 92,0 % 92,0 % 92,0 % Unigramy Vote 92,0 % 92,1 % 92,0 % Bigramy N B M 70,0 % 81,3 % 67,0 % Bigramy SVM 57,0 % 76,9 % 47,2 % Bigramy RF 88,0 % 88,0 % 88,0 %Bigramy J48 92,0 % 92,0 % 92,0 % Bigramy Vote 89,0 % 89,8 % 88,9 % Uni + big N B M 75,0 % 83,3 % 73,3 % Uni + big SVM 56,0 % 76,6 % 45,4 % Uni + big RF 94,0 % 94,0 % 94,0 %Uni + big J48 93,0 % 93,0 % 93,0 % Uni + big Vote 94,0 % 94,0 % 94,0 % Tabulka 4.12: Výsledky metod učení s učitelem pro anglickou množinu 4.6 Shrnutí Při testování dosahovala nejlepší úspěšnosti až 98 % metoda LOF a dobrých výsledků dosahovala také klasifikace s využitím metody RandomForest a to až 94 %. Při porovnávání obou přístupů je nutné uvažovat také jejich rozdílnost. Klasifikační metody se musí vypořádat jak s klasifikací normálních a anomálních uživatelů, tak také musí být schopny rozhodnout pro každou testovanou instanci. Naopak metoda využívající LOF nám vrátí pouze seznam uživatelů seřazených sestupně dle přiřazeného skóre, kde předpokládáme, že největší hustota anomálních uživatelů se nachází na začátku seznamu a dále postupně klesá. Dalším aspektem, který je nutné brát v úvahu při hodnocení vhodnosti zvoleného přístupu, jsou nároky na reálné nasazení v praxi. V případě klasifikace se klasifikátor naučí požadovaný model a klasifikace poté probíhá velmi rychle. Naopak u LOF je nutné, aby metoda provedla analýzu vždy na celé množině a není tudíž vhodná pro rozpoznání anomálních uživatelů v případě požadavku na detekci v reálném čase. Na druhou stranu, pokud by byla použita inkrementální implementace algoritmu LOF, bylo by možné 37 4. NÁVRH METODY PRO ROZPOZNÁNÍ ANOMÁLNÍCH UŽIVATELŮ toto omezení překonat [34]. LOF je tedy vhodné použít tehdy, pakliže máme množinu uživatelů a potřebujeme získat „nejvíce" anomální uživatele (uživatelé ohodnoceni nejvyšším koeficientem odlehlosti). Typicky se tak jedná o případy, kdy chceme očistit trénovací množinu apod. Naopak klasifikaci je vhodné použít tehdy, pokud je kladen důraz na rychlé rozpoznání uživatele a je požadováno přiřazení třídy každé testované instanci. 38 5 Charakteristika anomálních uživatelů Zdá se, že anomální uživatelé nejsou zpravidla pouze jednotlivé odlehlé instance, ale shluky, které lze charakterizovat chováním v některých jejich atributech. Proto v této kapitole provedeme analýzu anomálních uživatelů pomoci shlukové analýzy. Na základě pozorování pak vytvoříme charakteristiku anomálních uživatelů popisující jednotlivé tendence těchto skupin s uvedením konkrétních příkladů na Twitteru. 5.1 Shlukování anomálních uživatelů Na základě pozorování anomálních uživatelů a jejich hodnot atributů se ukazuje, že řada uživatelů má v některých svých atributech podobné tendence chování a je možné jednotlivé typy anomálních uživatelů charakterizovat. Jednou z metod, kterou lze použít pro rozdělení anomálních uživatelů do jednotlivých skupin, je použití metody shlukování. Metoda sama o sobě nedá informaci o tom, o jakou skupinu uživatelů se jedná, ale bližší analýzou těchto účtů můžeme provést jejich studium a pokusit se skupiny uživatelů charakterizovat. U shlukování je zpravidla důležité vědět, kolik shluků hledáme. Zde budeme vycházet z již existujících metod [35, 17, 21], které hledají skupiny anomálních účtů jako jsou spam účty, robotické účty nebo informační účty včetně RSS čteček. Dále z pozorování víme, že existuje zvláštní skupina jednosměrně tématicky zaměřených účtů, které jsou odlišné především svým slovníkem. V případě, že bylo nutné při analýze zvolit parametr počtu hledaných shluků, byla vybrána tato hodnota z intervalu 3 až 5. Při analýze byla využita metoda hierarchického shlukování a metoda hledání nejbližších sousedů. Pomoci obou metod byla provedena shluková analýza nad 150 anomálními uživateli jak v české, tak v anglické datové sadě, přičemž množina atributů neobsahovala atributy odvozené z dokumentu příspěvků uživatele, jelikož naší motivací je pokusit se charakterizovat jednotlivé skupiny pouze na základě chování uživatelů a jejich aktivitě. S využitím poznatků získaných při pozorování byly poté vyvozeny charakteristiky chování anomálních uživatelů. 39 5. C H A R A K T E R I S T I K A A N O M Á L N Í C H UŽIVATELŮ 5.1.1 Hierarchické shlukování Analýza byla provedena pomocí implementace v jazyce R [36], kde byly testovány různé aglomerační přístupy. Jako vhodný přístup se ukázalo použít výchozí nastavení, kde vzdálenost mezi body se spočítala s využitím Euklidovské vzdálenosti a způsob výpočtu vzdálenosti shluků byl nastaven na průměr. Na základě analýzy byl také vytvořen dendrogram pro českou a anglickou množinu anomálních uživatelů, kde byla provedena hlubší analýza pro 5 nejvýše postavených shluků. U české množiny na obrázku 5.1 můžeme vidět dominanci dvou shluků. Červený shluk představuje účty s určitou mírou automatizace. Účty v tomto shluku vykazují vysokou aktivitu pouze v jedinou hodinu dne, nevykazují interakci s okolím a jejich slovník neobsahuje velký počet unikátních slov oproti jiným uživatelům. Zároveň některé účty vykazují nízké odchylky v délce vkládaných příspěvků. Naopak zelený, modrý a žlutý shluk obsahuje uživatele, které lze charakterizovat jako spam účty. Shluky se pak liší pouze zvolenou strategií pro šíření svých zpráv. Uživatelé v zeleném shluku vykazují vysoký počet použití klíčových slov v kombinaci s URL odkazy, naopak žlutý a modrý shluk obsahuje mnohem agresivnější uživatele co do počtu použití klíčových slov. Černý shluk pak zastupuje uživatelské účty, které lze charakterizovat jako informační účty a RSS čtečky s téměř žádnou interakcí s okolím, ale s vysokým počtem užití URL odkazů v příspěvku. Spam účty Obrázek 5.1: Dendrogram pro českou množinu 40 5. C H A R A K T E R I S T I K A A N O M Á L N Í C H UŽIVATELŮ Naopak v anglické množině na obrázku 5.2 dominují 3 větší shluky a dva menší. Červený shluk reprezentuje skupinu uživatelů, které lze označit jako informační účty a RSS čtečky. Jejich hlavními znaky je vysoký počet použitých URL odkazů a naopak téměř nulová interakce s okolím. Slovník, který tyto účty používají, je rozmanitý. Zelený, modrý a žlutý shluk lze označit jako spam účty, přičemž každý shluk odlišuje strategie, jakou tyto účty používají. Dominantní žlutý shluk obsahuje účty, které dosahují vysokého počtu použitých klíčových slov a odkazů. Naopak zelený shluk svou strategii doplňuje i o vysoký počet zmínění. Modrý shluk pak používá obdobnou strategii jako žlutý shluk, ale z pohledu použití klíčových slov je mnohem agresivnější. Všechny tři shluky také používají nízký počet unikátních slov ve svém slovníku. Poslední černý shluk lze označit jako shluk robotických účtů v kombinaci s automatizovanými propagačními účty. Slovník tohoto shluku není příliš rozmanitý, řada účtů má vysokou aktivitu pouze v jedinou hodinu dne. Obrázek 5.2: Dendrogram pro anglickou množinu 5.1.2 K-means Analýza byla provedena pomoci implementace algoritmu hledání nejbližších sousedů k-means v jazyce R s výchozím nastavením [37], kde vzdálenost mezi body se spočítala s využitím Euklidovské vzdálenosti a maxi- 41 5. C H A R A K T E R I S T I K A A N O M Á L N Í C H UŽIVATELŮ mální počet iterací byl nastaven na hodnotu 1 000. Parametr počtu hledaných shluků byl roven hodnotě 4. Při pozorování bylo rozdělení uživatelů zařazených do jednotlivých shluků obdobné s rozdělením u předchozí metody. Snížení počtu hledaných shluků vedlo ke sloučení shluků spam účtů, přičemž byly stále zachovány shluky představující robotické účty a informačně propagační účty kombinované s RSS čtečkami. U české množiny došlo ke sloučení všech tří shluků obsahujících spam účty do jednoho shluku, naopak informačně propagační účty se rozdělily do dvou shluků, kde rozdělujícím atributem byla rozmanitost použitého slovníku jednotlivých účtů. 5.2 Charakteristiky uživatelů Na základě analýzy pomoci shlukování anomálních uživatelů v kapitole 5.1 bylo provedeno pozorování jednotlivých uživatelů a jejich zařazení v rámci shluku. Díky této zkušenosti bylo možné lépe sledovat tendence v chování u jednotlivých atributů v daných skupinách a také provést jejich charakteristiku. Při analýze byly charakterizovány tři hlavní skupiny anomálií a to robotické účty, spam účty a informační, propagační účty včetně RSS čteček vykazující nulovou interakci s okolím. Zvláštní odlehlou skupinou jsou pak jednosměrně tématicky zaměřené účty. 5.2.1 Robotické účty Robotické účty vkládají své příspěvky v určité periodě. Perioda může být různě dlouhá, zpravidla se ale jedná o periody hodinové nebo denní. Roboti často přispívají v jedinou hodinu během dne a tudíž distribuce rozložení příspěvků oproti normálnímu uživateli je velmi odlišná. Rada účtů také nedosahuje vysoké rozmanitosti používaného slovníku, jestliže účet informuje pouze o změně nějaké hodnoty (účty o aktuální naměřené teplotě apod.), protože hodnota je vkládána stále do stejné šablony zprávy. Od toho se také odvíjí nízké odchylky v délce vkládaných příspěvků. Robotické účty například informují o počasí, o TV programu nebo aktuálním dni (jaký je den, kdo má svátek, kurzy měn) apod. ©PocasiPraha: po: 1/6 ° C , Možnost deště, út: 3/7 ° C , Zataženo, st: 4/9 °C, Možnost deště, čt: 2/7 °C, Možnost deště. [38] 42 5. C H A R A K T E R I S T I K A A N O M Á L N Í C H UŽIVATELŮ @TV_program_CT24:20:00: Zprávy, 20:05: Hyde Park, 21:00: Zprávy I http://vtelevizi.cz [39] 5.2.2 Spamúčty Spam účty zpravidla vykazují ve své aktivitě vysoký počet použití klíčových slov ve svých příspěvcích doprovázený vyšším počtem URL odkazů, jelikož díky použití klíčových slov se rozšiřuje potencionální okruh uživatelů, kteří mohou daný příspěvek sledovat. Výjimkou také není použití vyššího počtu zmínění jiných uživatelských účtů, což automaticky vede k zasláni notifikace zmíněným uživatelům a šancí spam účtu na vyšší přesměrování přes jeho URL odkazy. Samotný obsah příspěvků je často podřízen strategii získání co největší audience a počtu odběratelů. Zpravidla se tak jedná o propagační účty s agresivní marketingovou politikou, závadné účty odkazující na závadný nebo nevyžádaný komerční obsah. Účty také někdy vyzývají ostatní uživatele, aby spam účet sledovali a na oplátku nabízí, že odběratele budou sledovat zpět. Rozšiřují si tak dosah v síti a na první pohled se mohou tvářit jako významné účty s vysokým počtem odběratelů. Na druhou stranu, samotné závadné účty se sledují někdy i mezi sebou, aby si uměle navyšovaly statistiky sledovanosti a působily důvěryhodněji. ©JulezPooh: #VnAmuzik @jakki2004 @VicesAdulation @RT2EAT ©MarclTT ©TwitWhizz [40] ©FotoHanus: Soccer league Pražský přebor #prebor #press #fotbalpraha #canon #ldiv #300mm #pro #report #praha... https://instagram.eom/p/1 Yk2bRN 1 zH/ [41 ] 5.2.3 RSS čtečky, informační a propagační účty Účty tohoto typu zpravidla vykazují vysoký počet URL odkazů, nižší rozmanitost použitého slovníku nebo nízké výkyvy v délce příspěvků. Zároveň tyto účty nevykazují téměř žádnou interakci s okolím prostřednictvím reakcí na jiné uživatele nebo sdílením jejich příspěvků. Někdy jsou URL odkazy nahrazeny doprovodnými obrázky nebo videi k příspěvkům, které jsou motivovány danou propagační strategií. Příspěvky informačních účtů a RSS čteček také málokdy vykazují použití emotikonů ve svých zprávách. Jedná se tak o účty některých informačních služeb a webových aplikací, které automaticky přispívají aktualizacemi o změnách, nových příspěvcích 43 5. C H A R A K T E R I S T I K A A N O M Á L N Í C H UŽIVATELŮ nebo nových produktech. Výjimkou také nejsou uživatelé, kteří aktivně používají sociální síť Facebook, ale příspěvky z této sítě si nechávají automaticky v rámci některé služby přeposílat na svůj Twitter účet, přičemž jej aktivně vůbec nepoužívají a účet tak upadá do podoby pouhé RSS čtečky příspěvků z jiné sociální sítě. Mimo to, takové příspěvky nejsou kompletní, jelikož s omezením délky zprávy na 140 znaků dochází k uříznutí příspěvku a jejího pokračování mimo síť Twitter. ©webfaircz: Nové vlákno: Koupím adult, gambling http://goo.gl/fbAVuaah [42] @EngineersDay: New Job: Mechanical & Electrical Engineers, Company: (Dublin, OH, United States) http://ift.tt/HpHBla [43] 5.2.4 Jednosměrně tématicky zaměřené účty Jednosměrně tématicky zaměřené účty jsou speciální skupinou účtů, které svým charakterem nelze vždy zcela jednoznačně zařadit do některé z předchozích skupin, přitom svým chováním můžou nést některé z jejich rysů. Klíčový u těchto účtů je především jejich slovník, který tyto účty odhaluje. Mohou to být úzce zaměřené účty informující o zemětřesení nebo dopravě v konkrétním městě, účty vkládající neustále stejný obsah, počítající počet dnů do konce světa nebo citující pasáže z bible apod. Existují také svým zaměřením zvláštní robotické účty, které informují o tom, kdy zrovna odbíjí hodiny na Pražském orloji nebo britském Big Benu. @big_ben_clock: BONG BONG BONG BONG BONG BONG BONG BONG BONG BONG BONG BONG [44] @vorloj: bim bam bim bam bim bam bim bam bim bam bim [45] 44 6 Klasifikace a vliv anomálních uživatelů Klasifikace je důležitou metodou, která se využívá na sociální síti Twitter při řešení řady problémů. Používá se nejen při detekci robotických účtů [17], ale také při klasifikaci sentimentu [26] nebo rozpoznání politické preference voliče [46]. Výsledky klasifikace jsou ale často závislé na kvalitě dat, na kterých dochází k učení, tudíž je vhodné vždy data pročistit. Jednou z metod může být zohlednění vlivu anomálních uživatelů a filtrace jejich obsahu. V této kapitole se zaměříme na problém klasifikace sentimentu, kde se zaměříme na klasifikaci příspěvků do dvou (pozitivní a negativní) a do tří (pozitivní, neutrální a negativní) tříd. Dále popíšeme tvorbu trénovací a testovací množiny, způsob předzpracování a dosažené výsledky. Také použijeme navrženou metodu pro detekci anomálních uživatelů a ověříme, zda odstranění anomálních uživatelů z trénovací množiny má vliv na výsledky klasifikace a může tak být relevantní technikou pro zvýšení kvality učících dat. 6.1 Klasifikace sentimentu Analýza sentimentu se v posledních letech stává čím dál populárnější oblastí pro studium. Může se kupříkladu využít v oblasti predikce cen akcií na finančních trzích díky sledování zpráv na sociálních sítích [47] nebo při marketingové analýze ohlasů zákazníků na nový produkt vstupující na trh nebo jejich recenzí [48]. Stává se čím dál populárnější také na sociální síti Twitter a to především kvůli specifickému jazykovému modelu a omezením, které se zde projevují [49]. Klasifikace sentimentu spočívá v detekci pozitivních nebo negativních emocí v příspěvků uživatele. Pokud příspěvek není pozitivní ani negativní, pak je považován za neutrální. Rozpoznání třídy sentimentu není jednoduchý problém, jelikož jeden příspěvek může obsahovat i více emocí zároveň, projevy ironie nebo sarkazmu, což určení třídy sentimentu ztěžuje [50]. 6.2 Učení na základě emotikonů Uživatelé na sociálních sítích s oblibou vkládají do svých příspěvků emotikony označující jejich subjektivní sentiment. Díky dostupnosti velkého 45 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ množství příspěvků je tak možné takto označené příspěvky sdružovat do datových sad a místo lidské práce anotátorů použít právě emotikony jako zdroj informace o sentimentu ve zprávě. Na druhou stranu, je třeba si uvědomit, že informace od uživatelů nemusí být vždy zcela správné a v některých případech nemusí emotikon korespondovat se skutečným sentimentem zprávy. Metoda analýzy sentimentu učením na základě emotikonů byla použita již při analýze sentimentu příspěvků na anglickém Twitteru [26], kde dosahovala úspěšnosti 83 % při klasifikaci do dvou tříd (pozitivní a negativní) nad testovací množinou o velikosti 359 příspěvků. Trénovací množina měla 800 000 příspěvků z každé třídy. 6.3 Trénovací množina Trénovací množina pro účely klasifikace sentimentu v této práci byla vybudována s využitím metody učení na základě emotikonů. Aby každá třída měla rovné zastoupení v trénovací množině, bylo náhodně vybráno ze získaných dat 18 000 příspěvků z každé třídy pro českou množinu a 8 000 z každé třídy pro anglickou, přičemž rozdílnost velikosti množin se odvíjí od počtu získaných příspěvků obsahujících emotikony pro každý jazyk. Třídy byly detekovány podle obsažených emotikonů v těle zprávy. Konkrétní emotikony pro každou třídu jsou uvedeny v tabulce 6.1. Třída Emotikony Pozitivní :),:-), :o), :-o), :D, :-D, XD,;),;-), ;o), ;-o), ;D, ;-D Negativní :(,:-(, :o(, :-o(,:,-(,:'-(,;(,:-(, ;o(, ;-o(,;,-(,;'-( Neutrální Neobsahuje pozitivní ani negativní emotikon. Tabulka 6.1: Třídy sentimentu dle emotikonů V případě, že zpráva obsahuje emotikon ze skupiny pozitivních a negativních emotikonů zároveň, pak taková zpráva nebyla zařazena do trénovací množiny. Předzpracování probíhá totožným způsobem, jako v podkapitole 4.3. 46 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ 6.4 Testovací množina Testovací množina byla vytvořena z náhodně vybraných příspěvků1 , kterým byla dále přiřazena třída sentimentu na základě anotace dvou osob. Tabulky 6.2 a 6.3 ukazují, jaká panovala shoda mezi anotátory při přiřazování jednotlivých tříd. Cohenovo kappa pro českou testovací množinu je rovno hodnotě 0,749 a pro anglickou testovací množinu 0,740, což splňuje požadavky na důvěryhodnost anotace. Čistá shoda anotátorů pro českou množinu je 83,28 % a pro anglickou 82,68 %. Anotátor B Pozitivní Neutrální Negativní Anotátor A Pozitivní 161 27 9 Anotátor A Neutrální 23 159 14Anotátor A Negativní 10 14 163 Tabulka 6.2: Shoda anotátorů pro českou testovací množinu sentimentu Anotátor B Pozitivní Neutrální Negativní Anotátor A Pozitivní 129 17 7 Anotátor A Neutrální 21 130 11Anotátor A Negativní 6 17 118 Tabulka 6.3: Shoda anotátorů pro anglickou testovací množinu sentimentu V případě, že se anotátoři při přiřazení třídy příspěvku lišili, rozhodla o přiřazení jedné z tříd třetí osoba. Tabulka 6.4 ukazuje rozdělení příspěvků do jednotlivých tříd v testovací množině. Třída Česká množina Anglická množina Pozitivní 181 145 Neutrální 209 164 Negativní 190 147 Tabulka 6.4: Rozdělení tříd v testovací množině při klasifikaci sentimentu 1. V tomto případě výběr probíhal ze všech příspěvků, bez ohledu na to, zda příspěvek obsahoval emotikon 47 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ 6.5 Výsledky klasifikace do tří tříd Nyní si představíme výsledky klasifikace sentimentu na pozitivní, neutrální a negativní sentiment. V první části rozebereme výsledky využívající tónovací množinu včetně příspěvků anomálních uživatelů, poté příspěvky těchto uživatelů odstraníme a budeme sledovat, jaký vliv na výsledky klasifikace bude zaznamenán. Měření provedeme vždy jak pro českou, tak anglickou tónovací množinu, abychom eliminovali vedlejší vlivy spojené s vlastnostmi konkrétního jazyka. Při každém měření jsou výsledky uvedeny pro klasifikátory NBM, SVM a PvF. Zároveň byla vždy provedena tokenizace textu na unigramy, bigramy a na kombinaci obsahující jak unigramy, tak bigramy. Počet tokenů byl vždy omezen na 3 000 nej frekventovanějších pro každou třídu. K vyhodnocení byl použit program Weka. Detailní informace o nastavení jednotlivých klasifikátorů a tokenizaci textu lze nalézt v příloze B. 6.5.1 Bez odstranění anomálních uživatelů Nejprve si ukážeme výsledky klasifikace sentimentu do tří tříd se zachováním příspěvků anomálních uživatelů v tónovací množině. Baseline pro českou množinu dosahuje hodnoty 35,4 % a pro anglickou 36 %. Tabulka 6.5 zobrazuje výsledky klasifikace sentimentu do tří tříd pro českou množinu a tabulka 6.6 pro anglickou. V obou případech si můžeme povšimnout, že nejlepších výsledků obou množin dosahuje tokenizace na unigramy v kombinaci s klasifikátorem NBM, kde je úspěšnost vyšší než 62 % a u anglické množiny dokonce vyšší než 64 %. Naopak tokenizace na bigramy dosahuje nejhorších výsledků, kde jednou z příčin může být řidší matice atributů obsahujících informace o výskytu jednotlivých tokenů. 6.5.2 Po odstranění anomálních uživatelů Nyní využijeme navrženou metodu pro rozpoznání anomálních uživatelů aplikací metody LOF, která dosahovala při experimentech v podkapitole 4.5.1 lepších výsledků, než metoda OR. Zároveň LOF použijeme se stejným nastavením, jako v podkapitole 4.5.1. Ke každému příspěvku v tónovací množině je vždy evidován uživatel, který je jeho autorem. Díky tomu získáme množinu uživatelů, kteří jsou autory příspěvků naší tónovací množiny pro klasifikaci sentimentu. Poté uživatele, kteří disponují v historii ale- 48 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ spoň 200 příspěvky, podrobíme metodě pro detekci anomálních uživatelů. Uživatelé s nižším počtem příspěvků nebereme v úvahu, jelikož stáří jejich účtu není dostatečné na to, aby se u nich projevil trend chování. Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 62,9 % 65,6 % 61,4% Unigramy SVM 49,8 % 47,4 % 43,6 %Unigramy RF 53,4 % 53,7 % 52,0 % Bigramy N B M 44,5 % 43,6 % 43,2 % Bigramy SVM 35,5 % 25,6 % 25,6 %Bigramy RF 47,1 % 47,1 % 44,2 % Uni + big N B M 61,6% 63,8 % 59,7 % Uni + big SVM 50,7 % 48,8 % 44,0 %Uni + big RF 50,0 % 50,1 % 48,5 % Tabulka 6.5: Klasifikace sentimentu v české datové sadě na pozitivní, neutrální a negativní příspěvky bez odstranění anomálních uživatelů Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 64,5 % 65,2 % 64,2 % Unigramy SVM 55,9 % 57,3 % 56,1 %Unigramy RF 57,7 % 58,7 % 57,9 % Bigramy N B M 51,1 % 54,5 % 51,2% Bigramy SVM 46,5 % 48,2 % 42,3 %Bigramy RF 52,0 % 54,0 % 51,9% Uni + big N B M 61,2% 63,2 % 61,5 % Uni + big SVM 56,4 % 57,6 % 56,5 %Uni + big RF 56,8 % 58,0 % 56,9 % Tabulka 6.6: Klasifikace sentimentu v anglické datové sadě na pozitivní, neutrální a negativní příspěvky bez odstranění anomálních uživatelů Po aplikaci metody získáme graf, který zobrazuje distribuci koeficientu odlehlosti, přičemž ke každému uživateli známe jemu přiřazenou hodnotu. Z chování metody víme, že anomální uživatelé dosahují nejvyššího koeficientu odlehlosti, který se pohybuje kolem hodnoty 2 a více. Příspěvky anomálních uživatelů odstraníme z trénovací množiny. 49 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Pro českou množinu lze graf distribuce koeficientu odlehlosti vidět na obrázku 6.1 a pro anglickou na obrázku 6.2. V obou případech na základě distribuce hodnot vybereme 200 uživatelů s nejvyšší hodnotou odlehlosti a jejich příspěvky odstraníme z trénovacích množin. Tabulka 6.7 zobrazuje, o jaký počet příspěvků se sníží velikost trénovacích množin. Po odstranění příspěvků provedeme vyhodnocení totožným způsobem, jako bylo provedeno bez odstranění anomálních uživatelů. Pro lepší přehlednost srovnání budou nyní v tabulkách výsledků zaznamenány změny v naměřených výsledcích oproti předchozímu měření bez použití metody. Stav v Česká množina Anglická množina Před odstraněním 48 000 24 000 Po odstranění 47 539 23 378 Tabulka 6.7: Změna velikosti trénovacích množin klasifikace sentimentu do dvou tříd po odstranění anomálních uživatelů Tabulka 6.8 zobrazuje vliv na klasifikaci sentimentu pro českou množinu a tabulka 6.9 pro anglickou. Můžeme si povšimnout, že jak u české, tak anglické množiny došlo v obou případech ke zlepšení u klasifikátoru N B M při tokenizaci na unigramy. U české množiny došlo také ke zlepšení u kombinace unigramů a bigramů pro klasifikátor RF a u anglické množiny naopak při tokenizaci na bigramy u klasifikátoru NBM. Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 0,7 % 0,9% 0,7 % Unigramy SVM 0 0 0Unigramy RF 0 0,2% 0,4% Bigramy N B M -0,5 % -0,6 % -0,6 % Bigramy SVM -1,5 % 12,9 % -2,3 %Bigramy RF -0,5 % -1,0% -0,7 % Uni + big N B M -0,7 % -0,9 % -0,7 % Uni + big SVM -0,4 % -0,5 % -0,5 %Uni + big RF 1,7 % 1,8 % 1,6 % Tabulka 6.8: Vliv na klasifikaci sentimentu v české datové sadě na pozitivní, neutrální a negativní příspěvky po odstranění anomálních uživatelů 50 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 1,3 % 0,8 % 1,2% Unigramy SVM 0 -0,4 % 0Unigramy RF -1,1 % -0,8 % -1,0% Bigramy N B M 2,0% 1,8 % 2,0% Bigramy SVM -4,0 % 2,7 % -7,1 %Bigramy RF -1,1 % -1,3 % -1,0% Uni + big N B M -0,2 % -0,8 % -0,3 % Uni + big SVM 0 -0,1 % 0Uni + big RF -1,5 % -1,5 % -1,4% Tabulka 6.9: Vliv na klasifikaci sentimentu v anglické datové sadě na pozitivní, neutrální a negativní příspěvky po odstranění anomálních uživatelů Obrázek 6.1: Distribuce koeficientu odlehlosti pro českou množinu autorů příspěvků v trénovací množině pro klasifikaci do tří tříd 51 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Obrázek 6.2: Distribuce koeficientu odlehlosti pro anglickou množinu autorů příspěvků v trénovací množině pro klasifikaci do tří tříd 6.6 Výsledky klasifikace do dvou tříd Nyní si představíme výsledky klasifikace sentimentu na pozitivní a negativní sentiment. Postup při získávání výsledků je shodný s postupem popsaným v kapitole 6.5 při klasifikaci do tří tříd. Jediným rozdílem je odstranění neutrální třídy příspěvků z trénovací a testovací množiny pro každý jazyk. 6.6.1 Bez odstranění anomálních uživatelů Tabulka 6.10 zobrazuje výsledky klasifikace sentimentu do dvou tříd pro českou množinu. Výsledky pro anglickou množinu lze nalézt v tabulce 6.11. V obou případech si můžeme povšimnout, že nejlepších výsledků obou množin dosahuje tokenizace na unigramy v kombinaci s metodou NBM, kde je úspěšnost vyšší než 80 %. Naopak tokenizace na bigramy dosahuje nejhorších výsledků. Baseline pro českou množinu dosahuje hodnoty 51,2 % a pro anglickou 50,3 %. 52 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 80,6 % 81,7 % 80,5 % Unigramy SVM 70,4 % 70,5 % 70,2 %Unigramy RF 75,5 % 76,1 % 75,4 % Bigramy N B M 62,0 % 62,0 % 62,0 % Bigramy SVM 51,2% 26,2 % 34,7 %Bigramy RF 63,3 % 64,7 % 62,7 % Uni + big N B M 78,7 % 80,4 % 78,5 % Uni + big SVM 70,4 % 70,5 % 70,2 %Uni + big RF 75,2 % 76,1 % 75,1 % Tabulka 6.10: Klasifikace sentimentu v české datové sadě na pozitivní a negativní příspěvky bez odstranění anomálních uživatelů Tokenizace Metoda > Úspěšnost Přesnost F-míra Unigramy N B M 82,5 % 83,7 % 82,4 % Unigramy SVM 70,9 % 74,1 % 69,9 %Unigramy RF 80,1 % 82,6 % 79,8 % Bigramy N B M 75,3 % 79,1 % 74,6 % Bigramy SVM 60,3 % 66,3 % 56,4 %Bigramy RF 72,6 % 73,6 % 72,3 % Uni + big N B M 80,1 % 82,4 % 79,8 % Uni + big SVM 72,3 % 75,4 % 71,4%Uni + big RF 78,8 % 79,7 % 78,6 % Tabulka 6.11: Klasifikace sentimentu v anglické datové sadě na pozitivní a negativní příspěvky bez odstranění anomálních uživatelů 6.6.2 Po odstranění anomálních uživatelů Nyní opět využijeme navrženou metodu pro rozpoznání anomálních uživatelů stejným způsobem, jako tomu bylo při klasifikaci sentimentu do tří tříd s odstraněním anomálních uživatelů. Pro českou množinu lze graf distribuce koeficientu odlehlosti vidět na obrázku 6.3 a pro anglickou na obrázku 6.4. V obou případech na základě distribuce hodnot vybereme 100 uživatelů s nej vyšší hodnotou odlehlosti 53 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ a jejich příspěvky odstraníme z tónovacích množin. Tabulka 6.12 zobrazuje, o jaký počet příspěvků se sníží velikost tónovacích množin. Stav Česká množina Anglická množina Před odstraněním 32 000 16 000 Po odstranění 31 713 15 520 Tabulka 6.12: Změna velikosti tónovacích množin klasifikace sentimentu do dvou tříd po odstranění anomálních uživatelů Tabulka 6.13 zobrazuje vliv na klasifikaci sentimentu pro českou množinu a tabulka 6.14 pro anglickou. Můžeme si povšimnout, že u české i anglické množiny došlo v obou případech ke zlepšení u klasifikátorů N B M a PvF při tokenizaci na unigramy, přičemž se nejedná o jediná zlepšení, která byla zaznamenána. Tokenizace Metoda T Úspěšnost Přesnost F-míra Unigramy N B M 1,3 % 1,6% 1,3 % Unigramy SVM 0 , 2 % 0 , 2 % 0,3 %Unigramy PvF 1,3 % 1,1 % 1,4% Bigramy N B M -0,5 % -0,5 % -0,5 % Bigramy SVM 0 0 0Bigramy RF 1,4% 1,0% 1,6 % Uni + big N B M 0 0 0 Uni + big SVM 0 -0,1 % 0,1 %Uni + big PvF 0,5 % 0 , 2 % 0,6 % Tabulka 6.13: Vliv na klasifikace sentimentu v české datové sadě na pozitivní a negativní příspěvky po odstranění anomálních uživatelů 54 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Tokenizace Metoda > Úspěšnost Přesnost F-míra N B M 2,1 % 1,8 % 2,1 % Unigramy SVM 0,3 % -0,5 % 0,6 % RF 1,4% 0,3 % 1,5 % N B M 0 -1,9% 0,3 % Bigramy SVM 2,4% -3,6 % 6,2 % RF 1,4% 1,2% 1,5 % N B M 1,7 % 1,7 % 1,8 % Uni + big SVM 0,3 % 0,3 % 0,4% RF 0 0,4% 0 Tabulka 6.14: Vliv na klasifikaci sentimentu v anglické datové sadě na pozitivní a negativní příspěvky po odstranění anomálních uživatelů Obrázek 6.3: Distribuce koeficientu odlehlosti pro českou množinu autorů příspěvků v trénovací množině pro klasifikaci do dvou tříd 55 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ Obrázek 6.4: Distribuce koeficientu odlehlosti pro anglickou množinu autorů příspěvků v trénovací množině pro klasifikaci do dvou tříd 6.6.3 Využití pro klasifikaci do tří tříd Abychom mohli využít klasifikátor na pozitivní a negativní příspěvky při praktickém použití, je nezbytné vyřešit, jakým způsobem zajistíme, aby příspěvky, které bude klasifikátor klasifikovat, byly skutečně buď pozitivní nebo negativní. Proto byla pro každý jazyk otestována kaskáda klasifiká- torů. První klasifikátor v kaskádě se naučí na trénovací množině obsahující neutrální a sentimentální třídu, přičemž sentimentální třída označuje příspěvky, které jsou pozitivní nebo negativní. Jako trénovací množina je použita množina uvedená v 6.3 a testovací množina uvedená v 6.4. Cílem klasifikátoru je dále propustit jen ty příspěvky, které označí jako sentimentální. Příspěvky, které jsou označeny jako sentimentální, dále klasifikuje klasifikátor do dvou tříd, který byl již v této kapitole popsán a dosahuje mnohem lepší úspěšnosti, než samotný klasifikátor do tří tříd. První klasifikátor využívá kombinaci N B M a tokenizaci na unigramy, která při experimentech dosahovala nejlepších výsledků. U české množiny první klasifikátor v kaskádě dosahoval úspěšnosti 65 % při baseline 64 %. Druhý klasifikátor pak dosahoval úspěšnosti na příspěv- 56 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ cích označených jako sentimentální 67,2 % při baseline 55,1 %. Matici záměn pro celou kaskádu zobrazuje tabulka 6.15. Úspěšnost celé kaskády dosahuje hodnoty 58,6 % při baseline 36 %. Klasifikován j ako: Pozitivní Neutrální Negativní Třída Pozitivní 56 111 14 Třída Neutrální 31 156 22Třída Negativní 23 39 128 Tabulka 6.15: Matice záměn pro kaskádu klasifikátorů pro českou množinu U anglické množiny první klasifikátor dosahoval úspěšnosti 68 % při baseline 64 %. Druhý klasifikátor pak dosahoval úspěšnosti 66,8 % při baseline 38,7 %. Matici záměn pro celou kaskádu zobrazuje tabulka 6.16. Úspěšnost celé kaskády dosahuje hodnoty 62,7 % při baseline 36 %. Získané výsledky naznačují, že hlavní problém při využití klasifikátorů do dvou tříd při reálném nasazení vychází právě z úspěšnosti, s jakou jsme schopni klasifikovat neutrální a sentimentální příspěvky. Jedním z hledisek, které je nutné brát na zřetel, je skutečnost, že třída neutrálních příspěvků v trénovací množině obsahuje příspěvky bez emotikonů, což nezaručuje absenci pozitivních a negativních příspěvků. Klasifikován jako: Pozitivní Neutrální Negativní Třída Pozitivní 93 41 13 Třída Neutrální 21 91 52Třída Negativní 11 32 102 Tabulka 6.16: Matice záměn pro kaskádu klasifikátorů pro anglickou mno­ žinu 6.7 Shrnutí Klasifikace sentimentu na sociální síti Twitter při klasifikaci na pozitivní, neutrální a negativní sentiment dle provedených experimentů dosahuje pro českou množinu úspěšnosti 62,9 % a pro anglickou 64,5 %. V případě klasifikace pouze na pozitivní a negativní sentiment dosahuje nejlepší český 57 6. K L A S I F I K A C E A V L I V A N O M Á L N Í C H UŽIVATELŮ klasifikátor úspěšnosti 80,6 % a anglický 82,5 %. Je třeba si ale uvědomit, že klasifikátor do dvou tříd v případě praktického použití nemůže ignorovat skutečnost, že v testovaných instancích se budou vyskytovat i neutrální zprávy, což lze řešit klasifikátory v kaskádě, kde první klasifikátor propustí jen ty zprávy, které budou buď pozitivní nebo negativní. Při testování se ale ukázalo, že taková kaskáda dosahuje nižší úspěšnosti, než samostatný klasifikátor do tří tříd sentimentu a pro dosažení lepších výsledků je nezbytné zvýšit úspěšnost prvního klasifikátoru v kaskádě. Dále bylo zjištěno, že při aplikaci metody pro detekci anomálních uživatelů můžeme odstraněním minoritní části příspěvků z trénovacích množin zvýšit úspěšnost výsledných klasifikátoru. U klasifikace do tří tříd došlo ke zlepšení u české množiny o 0,7 % na 63,6 %. U anglické došlo ke zlepšení o 1,7 % na 65,8 %. U klasifikátoru do dvou tříd došlo u české množiny ke zlepšení o 1,3 % na 81,9 % a u anglické o 2,1 % na 84,6 %. Při porovnání s jinými pracemi zabývajícími se klasifikací sentimentu dosahuje získaný klasifikátor pro anglický Twitter s využitím metody pro detekci anomálních uživatelů vyšší úspěšnosti, než práce zaměřující se na klasifikaci sentimentu pomoci emotikonů na Twitteru, kde autoři dosáhli úspěšnosti 83 % [26]. Naopak česká práce [48] zaměřená na klasifikaci do dvou a do tří tříd s využitím příspěvků ze sociální sítě Facebook dosahuje lepších výsledků, které jsou ovlivněny hlavně rozdílným přístupem, jelikož práce nevyužívala emotikony k přiřazení tříd příspěvkům v trénovacích množinách, ale příspěvky byly ručně anotovány, přičemž informace o obsažených emotikonech v příspěvku byly rozšiřujícím atributem. Při klasifikaci do tří tříd práce dosáhla F-míry 69 % a při klasifikaci do dvou tříd F-míry 9 0 % . 58 7 Závěr V rámci této práce byla navržena metoda pro rozpoznání anomálních uživatelů, kde metoda LOF dosahuje úspěšnosti až 98 % a metoda využívající klasifikaci s pomocí algoritmu RandomForest dosahuje úspěšnosti až 94 %. Při návrhu metody byly testovány i další přístupy jako učení z klasifikovaných a neklasifikovaných příkladů a dále byla navržena řada nových atributů vhodných pro detekci anomálních uživatelů. Mezi tyto atributy kupříkladu patří počet pozitivních příspěvků, počet médií, počet unikátních slov, směrodatná odchylka délky příspěvků uživatele nebo také maximální denní aktivita a další. Zároveň byla provedena charakteristika anomálních uživatelů pomocí metody shlukování a jednotlivé podskupiny anomálních uživatelů byly analyzovány a blíže popsány. Ukázalo se, že jak na českém, tak anglickém Twitteru lze rozdělit anomální uživatele do stejných podskupin, které jsou vyznačeny podobným chováním v několika znacích uživatele. Byly tak odhaleny hlavní tři třídy anomálních účtů, mezi které patří spam účty, robotické účty a propagační a informační účty s nulovou interakcí s okolím. Mimo tyto třídy byla charakterizována také skupina účtů, které svým charakterem nelze vždy zcela jednoznačně zařadit do některé z předchozích skupin, přitom svým chováním můžou nést některé z jejich rysů. Při klasifikaci sentimentu na pozitivní, neutrální a negativní příspěvky bylo dosaženo úspěšnosti až 65,8 % a při klasifikaci na pozitivní a negativní příspěvky úspěšnosti až 84,6 %, přičemž pro český Twitter byla vždy úspěšnost mírně nižší. Také byl navržen postup, jakým způsobem lze využít metodu pro rozpoznání anomálních uživatelů ke zlepšení výsledků klasifikace, což se ukázalo být relevantním postupem. Aplikovaná metoda v některých případech po odstranění příspěvků anomálních uživatelů z trénovací množiny zvýšila úspěšnost klasifikace v nejlepším případě až o 2,1 %. Metoda by tak mohla pomoci v řadě aplikací, kde jsou využívány příspěvky uživatelů k řešení různých klasifikačních problémů. Všechny provedené experimenty byly vždy provedeny jak s využitím dat z českého, tak anglického Twitteru, což pomohlo ověřit uplatnitelnost navržené metody bez závislosti na zvoleném jazyce a zároveň sledovat rozdílnost výsledků klasifikace sentimentu pro oba jazyky. Také byly navrženy heuristiky pro získání vzorku dat české a anglické komunity a vznikl jednoduchý nástroj pro anotaci uživatelů na sociální síti Twitter. 59 7. ZÁVĚR Práce by se v budoucnu mohla rozšiřovat v několika směrech. Mezi tyto směry patří: • otestování dalších algoritmů a jejich úspěšnosti při detekci anomálních uživatelů • návrh dalších atributů • doplnění metody o schopnost rozpoznat, do jaké třídy anomální uživatel patří • nalezení a analýza odlehlých anomálních uživatelů v rámci své podskupiny s využitím příslušných metod • ověřit vliv navržené metody na výsledky dalších klasifikačních problémů na sociální síti Twitter, jako je klasifikace tématu příspěvku a další • zlepšit úspěšnost klasifikátoru, který v rámci kaskády při klasifikaci sentimentu rozděluje příspěvky na neutrální a příspěvky obsahující sentiment • testování dalších metod předzpracování příspěvků uživatele, jako je lemmatizace a další 60 Literatura [1] About Twitter, [online]. 2015. [cit. 2015-04-11]. Dostupné z: https://about.twitter.com/company [2] KOULOUMPIS, E.; WILSON, T; MOORE, J.: Twitter sentiment analysis: The good the bad and the omg! ICWSM, ročník 11, 2011: s. 538-541. [3] SRIRAM, B.; FUHRY, D.; DEMIR, E.; aj.: Short text classification in twitter to improve information filtering. Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval, 2010: s. 841-842. [4] DUGGAN, M.: Social Media Update 2014. [online]. 2015. [cit. 2015-04-01]. Dostupné z: h t t p : / /www. p e w i n t e r n e t . o r g / 2015/01/0 9/social-media-update-2014/ [5] MOORE, H.; ROBERTS, D.: AP Twitter hack causes panic on Wall Street and sends Dow plunging, [online]. 2013. [cit. 2015-04-01]. Dostupné z: h t t p : //www. t h e g u a r d i a n . com/business/ 2 0 1 3 / a p r / 2 3 / a p - t w e e t - h a c k - w a l l - s t r e e t - f r e e f a l l [6] MICHL, P.: Infografika: Sociální sítě v Česku, [online]. 2013. [cit. 2015-02-20]. Dostupné z: h t t p : //www.m-journal.cz/cs/internet/sociálni-site/ infografika--sociálni-site-v-česku s416x97 8 8. html [7] Klábosení, [online], [cit. 2015-04-11]. Dostupné z: http://www.kláboseni.cz/ [8] BERKA, P: Dobývání znalostí z databází. Academia, 2003, ISBN 80-200-1062-9. [9] HAN, J.; KAMBER, M.; PEI, J.: Data Mining: Concepts and Techniques. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011, ISBN 978-0123814791. [10] Twitter API. [online]. 2015. [cit. 2015-04-11]. Dostupné z: h t t p s : / / d e v . t w i t t e r . c o m / r e s t / p u b l i c 61 7. ZÁVĚR [11] Twitter Advanced Search, [online]. 2015. [cit. 2015-04-11]. Dostupné z: h t t p s : / / t w i t t e r . com/search-advanced [12] Terms: Agreement and Policy, [online]. 2015. [cit. 2015-04-11]. Dostupné z: h t t p s : / /dev. t w i t t e r . com/overview/ t e r m s / a g r e e m e n t - a n d - p o l i c y [13] Introducing new metadata for Tweets, [online]. 2013. [cit. 2015-04-11]. Dostupné z: h t t p s : / / b l o g . t w i t t e r . com/ 2 0 1 3 / i n t r o d u c i n g - n e w - m e t a d a t a - f o r - t w e e t s [14] SHUYO, N.: Language Detection Library for Java, [online]. 2010. [cit. 2015-04-11]. Dostupné z: h t t p s : / / c o d e . g o o g l e . c o m / p / l a n g u a g e - d e t e c t i o n / [15] MySQL, [online]. 2015. [cit. 2015-04-11]. Dostupné z: http://www.mysql.com/ [16] Quarterly report pursuant to section 13 or 15(d) of the securities exchange act of 1934. [online]. 2014. [cit. 2015-03-09]. Dostupné z: http://www.sec.gov/Archives/edgar/data/ 1418091/000156459014003474/twtr-10q_20140630. htm?_ga=l.172053859.1713638677.1406023469 [17] CHU, Z.; GIANVECCHIO, S.; WANG, H.; aj.: Detecting Automation of Twitter Accounts: Are you a human, bot, or cyborg? IEEE Transactions on Dependable and Secure Computing, ročník 9, č. 6, 2012: s. 811-824. Dostupné z: h t t p : / / i e e e x p l o r e . i e e e . o r g / l p d o c s / e p i c 0 3/ wrapper.htm?arnumber=62 8 0 553 [18] MANNING, C. D.; RAGHAVAN, P.; SCHÜTZE, H.: Introduction to information retrieval. Cambridge: Cambridge university press, 2008, ISBN 978-0-521-86571-5. [19] MCCORD, M.; CHUAH, M.: Spam detection on twitter using traditional classifiers. Autonomic and trusted computing, 2011: s. 175-186. [20] HALL, M.; FRANK, E.; HOLMES, G.; aj.: The W E K A Data Mining Software: An Update. SIGKDD Explorations, ročník 11, 2009. 62 7. ZÁVĚR [21] CHU, Z.; WIDJAJA, L; WANG, H.: Detecting Social Spam Campaigns on Twitter. In Applied Cryptography and Network Security, Springer, 2012, s. 455-472. Dostupné z: h t t p : / /1 i n k . springer.com/10.1007/978-3-642-31284-7_27 [22] MILLER, Z.; DICKINSON, B.; DEITRICK, W.; aj.: Twitter spammer detection using data stream clustering. Information Sciences, ročník 260, 2014: s. 64-73. Dostupné z: h t t p : / / l i n k i n g h u b . e l s e v i e r . c o m / r e t r i e v e / p i i / S0020025513008037 [23] ESTER, M . ; KRIEGEL, H.-R; SANDER, J.; aj.: A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd, ročník 96, 1996, s. 226-231. [24] ARTHUR, D.; VASSILVITSKII, S.: k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2007, s. 1027-1035. [25] PUSTEJOVSKY, J.: Natural language annotation for machine learning. O'Reilly, 2013, ISBN 978-1-449-30666-3. [26] GO, A.; BHAYANI, R.; HUANG, L.: Twitter Sentiment Classification using Distant Supervision. CS224N Project Report, Stanford, 2009: s. 1-12. [27] KOSARA, R.: Parallel Coordinates, [online]. 2010. [cit. 2015-05-16]. Dostupné z: h t t p s : //eagereyes . o r g / t e c h n i q u e s / p a r a l l e l - c o o r d i n a t e s [28] BREUNIG, M . M . ; KRIEGEL, H.-P; NG, R. T; aj.: LOF. ACM SIGMOD Record, ročník 29, č. 2, 2000: s. 93-104, ISSN 01635808. Dostupné z: h t t p : / / p o r t a l . acm. o r g / c i t a t i o n . cfm? doid=335191.335388 [29] TORGO, L : Package DMwR. [online]. 2015. [cit. 2015-02-20]. Dostupné z: h t t p : / /cran . r - p r o j e c t . org/web/ packages/DMwR/DMwR.pdf 63 7. ZÁVĚR [30] PFAHRINGER, B.; DRIESSENS, K.; REUTEMANN, P.: Semi-Supervised Learning and Collective Classification, [online], [cit. 2015-04-24]. Dostupne z: http://www.cms.waikato.ac.nz/~fracpete/ p r o j e c t s / c o l l e c t i v e - c l a s s i f i c a t i o n / [31] PFAHRINGER, B.; DRIESSENS, K.; REUTEMANN, P.: Collective Classifiers, [online], [cit. 2015-04-24]. Dostupne z: http://www.cms.waikato.ac.nz/~fracpete/ p r o j e c t s / c o l l e c t i v e - c l a s s i f i c a t i o n / d o c u m e n t a t i o n / c l a s s i f i e r s . p d f [32] BREIMAN, L.: Random forests. Machine learning, rocnik 45, c. 1, 2001: s. 5-32. [33] CHANG, C.-C; LIN, C.-J.: LIBSVM. ACM Transactions on Intelligent Systems and Technology, rocnik 2, c. 3, 2011: s. 1-27, ISSN 21576904. [34] POKRAJAC, D.; LAZAREVIC, A.; LATECKI, L. J.: Incremental local outlier detection for data streams. In Computational Intelligence and Data Mining, 2007. CIDM2007. IEEE Symposium on, IEEE, 2007, s. 504-515. [35] AHMED, F ; ABULAISH, M.: A generic statistical approach for spam detection in Online Social Networks. Computer Communications, rocnik 36, c. 10-11, 2013: s. 1120-1129. Dostupne z: h t t p : / / l i n k i n g h u b . e l s e v i e r . c o m / r e t r i e v e / p i i / S0140366413001047 [36] Hierarchical Clustering, [online], [cit. 2015-04-11]. Dostupne z: h t t p s : / / s t a t . e t h z . c h / R - m a n u a l / R - p a t c h e d / l i b r a r y / s t a t s / h t m l / h c l u s t . h t m l [37] K-Means Clustering, [online], [cit. 2015-04-11]. Dostupne z: h t t p s : / / s t a t . e t h z . c h / R - m a n u a l / R - d e v e l / l i b r a r y / stats/html/kmeans.html [38] PocasiPraha (Twitter), [online]. 2010. [cit. 2015-03-31]. Dostupne z: h t t p s : / / t w i t t e r . c o m / P o c a s i P r a h a / s t a t u s / 1514265563369473 64 7. ZÁVĚR [39] TV_program_CT24 (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . com/TV_program_CT24 / s t a t u s / 5 91255252403388416 [40] JulezPooh (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . c o m / J u l e z P o o h / s t a t u s / 591377830178476032 [41] FotoHanus (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . c o m / F o t o H a n u s / s t a t u s / 587312906003423232 [42] webfaircz (Twitter), [online]. 2011. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . c o m / w e b f a i r c z / s t a t u s / 152749051807416320 [43] EngineersDay (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z : h t t p s : / / t w i t t e r . c o m / E n g i n e e r s D a y / s t a t u s / 580353927373303808 [44] big_ben_clock (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . c o m / b i g _ b e n _ c l o c k / s t a t u s / 591376008374329344 [45] vorloj (Twitter), [online]. 2015. [cit. 2015-04-24]. Dostupne z: h t t p s : / / t w i t t e r . c o m / v o r l o j / s t a t u s / 2 5 8 1 9 7 7 2 6 7 3 [46] PENNACCHIOTTI, M . ; POPESCU, A.-M.: Democrats, republicans and Starbucks afficionados. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11, New York, New York, USA: A C M Press, 2011, str. 430. Dostupne z: h t t p : //dl.acm.org/citation.cfm?doid=2020408.2020477 [47] Y U , L . - C ; WU, J.-L.; CHANG, P.-C; aj.: Using a contextual entropy model to expand emotion words and their intensity for the sentiment classification of stock market news. Knowledge-Based Systems, rocnfk 41, 2013: s. 89-97. Dostupne z: h t t p : / / l i n k i n g h u b . e l s e v i e r . c o m / r e t r i e v e / p i i / S O 95070511300004X 65 7. ZÁVĚR [48] HABERNAL, L; PTÁČEK, T; STEINBERGER, J.: Supervised sentiment analysis in Czech social media. Information Processing & Management, ročník 50, č. 5, 2014: s. 693-707. Dostupné z: h t t p : / / l i n k i n g h u b . e l s e v i e r . c o m / r e t r i e v e / p i i / S0306457314000399 [49] SAIF, H.: Evaluation datasets for Twitter sentiment analysis a survey and a new dataset, the STS-Gold. CEUR Workshop Proceedings, ročník 1096, 2013: s. 9 - 2 1 . [50] GROOT, R. D.: Data mining for tweet sentiment classifícation. LAP LAMBERT Academic Publishing, 2012, ISBN 978-3-659-29517-1. 66 A Nástroj pro anotaci uživatelů Nástroj pro anotaci uživatelů vznikl za účelem zefektivnění práce při anotaci normálních a anomálních uživatelů. Jedná se o jednoduchou aplikaci napsanou v programovacím jazyce C#, která umožňuje procházet a přiřazovat třídu uživatelům ve frontě čekajících na její přiřazení. Po spuštění programu je nutné načíst frontu uživatelů z textového souboru. Formát textového souboru vyžaduje, aby každý uživatel reprezentovaný jeho uživatelským jménem na sociální síti Twitter byl na samostatném řádku, přičemž uživatelské jméno uvádíme bez uvozujícího symbolu „@". Anotátor poté pomocí rozhraní programu postupně přiřazuje třídu jednotlivým uživatelům. Jakmile přiřadí třídu poslednímu, uloží seznam uživatelů i s přiřazenými třídami ve formátu CSV, kde oddělovačem je středník. CSV soubor lze pak podrobit dalšímu zpracování. Aplikace je součástí přílohy práce včetně ukázkového vstupu a výstupu. Obrázek A . l zobrazuje náhled aplikace při reálném použití. Obrázek A. 1: Nástroj pro anotaci uživatelů 67 B Obsah přiložených souborů Součástí práce je příloha, která obsahuje doplňující informace k této práci. Součásti přílohy jsou: • obrázky použité v textu práce v plném rozlišení • výstupy všech probíraných experimentů z programu Weka při prováděných experimentech • grafické výstupy metod • nástroj pro anotaci uživatelů včetně ukázkového konfiguračního souboru a náhledu Příloha je dostupná ke stažení v elektronickém archivu závěrečných prací Masarykovy univerzity. 68