Průvodce předpovědí odkazů - Jak předpovídat budoucí připojení na Facebooku

Přehled

  • Úvod do propojení predikce, jak to funguje a kde ji můžete použít v reálném světě
  • Přečtěte si o důležitosti předpovědi odkazů na sociálních médiích
  • Vytvořte svůj první model předpovědi propojení pro případ použití na Facebooku pomocí Pythonu

Úvod

Přemýšleli jste někdy o tom, jaké bude vaše další připojení k Facebooku? Zajímá vás, od koho by další žádost mohla vycházet?

Co kdybych vám řekl, že existuje způsob, jak to předpovědět?

Miluji brainstorming a přicházím s těmito problémy, když procházím svůj účet na Facebooku. Je to jeden z výhod, které mají datové vědce myšlení!

Většina platforem sociálních médií, včetně Facebooku, může být strukturována jako grafy. Registrovaní uživatelé jsou propojeni ve vesmíru sítí. Abychom mohli pracovat na těchto sítích a grafech, potřebujeme jinou sadu přístupů, nástrojů a algoritmů (místo tradičních metod strojového učení).

V tomto článku tedy vyřešíme problém sociální sítě pomocí grafů a strojového učení. Nejprve porozumíme základním konceptům a komponentám predikce odkazů, než se pustíme do případové studie na Facebooku a implementujeme ji v Pythonu!

Doporučuji projít si níže uvedené články, abyste zjistili, jaké jsou grafy a jak fungují:

Obsah

  1. Přehled analýzy sociálních sítí
  2. Primer na predikci odkazu
  3. Strategie k řešení problému předpovědi odkazu
  4. Případová studie: Predikce budoucích propojení mezi stránkami Facebooku - Porozumění datům - Vytváření modelů datových sad - Extrakce prvků - Vytváření modelů: Model predikce odkazů

Přehled analýzy sociálních sítí

Nejprve definujeme sociální síť, než se pustíme do koncepce predikce odkazu.

Sociální síť je v podstatě reprezentací vztahů mezi sociálními subjekty, jako jsou lidé, organizace, vlády, politické strany atd.

Interakce mezi těmito entitami vytvářejí nepředstavitelné množství dat ve formě příspěvků, chatových zpráv, tweetů, lajků, komentářů, sdílení atd. Tím se otevírá okno příležitostí a případů použití, na kterých můžeme pracovat.

To nás přivádí k analýze sociálních sítí (SNA). Můžeme to definovat jako kombinaci několika činností, které jsou prováděny na sociálních médiích. Tyto činnosti zahrnují sběr dat z online sociálních médií a jejich použití k obchodním rozhodnutím.

Výhody analýzy sociálních sítí mohou být vysoce prospěšné. Zde je několik klíčových výhod:

  • Pomůže vám lépe porozumět vašemu publiku
  • Používá se pro segmentaci zákazníků
  • Používá se k návrhu doporučení systémů
  • Zjistit mimo jiné falešné zprávy

Primer na predikci odkazu

Predikce propojení je jedním z nejdůležitějších výzkumných témat v oblasti grafů a sítí. Cílem predikce odkazu je identifikovat páry uzlů, které budou v budoucnu tvořit odkaz nebo nikoli.

Predikce propojení má spoustu použití v reálných aplikacích. Zde jsou některé důležité případy použití predikce odkazu:

  • Předpovídejte, kteří zákazníci si pravděpodobně kupují, jaké produkty na online trzích, jako je Amazon. Může to pomoci při tvorbě lepších doporučení produktů
  • Navrhněte interakce nebo spolupráce mezi zaměstnanci v organizaci
  • Extrahujte důležité poznatky z teroristických sítí

V tomto článku prozkoumáme mírně odlišné použití předpovědi odkazů - předpovídání odkazů v online sociální síti!

Strategie k řešení problému předpovědi odkazu

Pokud můžeme nějak reprezentovat graf ve formě strukturované datové sady se sadou funkcí, pak možná můžeme pomocí strojového učení předpovídat vytváření vazeb mezi nespojenými uzlovými páry grafu.

Vezměme si fiktivní graf, abychom pochopili tento nápad. Níže je uveden 7 uzlový graf a nespojené dvojice uzlů jsou AF, BD, BE, BG a EG:

Graf v čase t

Nyní řekněme, že analyzujeme data a přišli s níže uvedeným grafem. Bylo vytvořeno několik nových spojení (odkazy červeně):

Graf v čase t + n

Potřebujeme sadu predikčních proměnných a cílovou proměnnou, abychom vytvořili jakýkoli model strojového učení, že? Takže kde jsou tyto proměnné? Můžeme to získat ze samotného grafu! Uvidíme, jak se to dělá.

Naším cílem je předpovídat, zda by existovalo spojení mezi libovolnými 2 nepřipojenými uzly. Ze sítě v čase t můžeme extrahovat následující páry uzlů, které mezi nimi nemají žádné vazby:

  1. AF
  2. BD
  3. BÝT
  4. BG
  5. NAPŘ

Vezměte prosím na vědomí, že pro větší pohodlí jsem zvažoval pouze ty uzly, které jsou od sebe pár odkazů.

Dalším krokem pro nás je vytvoření funkcí pro každý pár uzlů. Dobrou zprávou je, že existuje několik technik, jak extrahovat funkce z uzlů v síti. Řekněme, že používáme jednu z těchto technik a vytváříme prvky pro každý z těchto párů. Stále však nevíme, co je cílová proměnná. Nemusíte se obávat - to také snadno dokážeme získat.

Podívejte se na graf v čase t + n. Vidíme, že v síti existují tři nové odkazy pro páry AF, BD a BE. Proto každému z nich přiřadíme hodnotu 1. Dvojicům uzlů BG a EG bude přiděleno 0, protože mezi uzly stále neexistují žádná propojení.

Data tedy budou vypadat takto:

Nyní, když máme cílovou proměnnou, můžeme pomocí těchto dat vytvořit model strojového učení k provedení predikce spojení.

Proto potřebujeme použít sociální grafy ve dvou různých časových okamžicích k extrahování cílové proměnné, tj. Přítomnosti spojení mezi párem uzlů. Mějte však na paměti, že v reálných scénářích budeme mít pouze data o současnosti.

Extrahujte data z grafu pro sestavení modelu

Ve výše uvedené části jsme dokázali získat popisky pro cílovou proměnnou, protože jsme měli přístup k grafu v čase t + n. V reálných scénářích bychom však měli k dispozici pouze jeden datový soubor grafu. A je to!

Řekněme, že máme níže uvedený graf sociální sítě, kde uzly jsou uživatelé a hrany představují určitý druh vztahu:

Páry kandidátských uzlů, které mohou v budoucnu tvořit spojení, jsou (1 a 2), (2 a 4), (5 a 6), (8 a 10) atd. Musíme vytvořit model, který bude předpovídat, zda by mezi těmito páry uzlů existovalo spojení nebo ne. To je to, o čem je předpovědi odkazů!

K vytvoření modelu predikce propojení však musíme z tohoto grafu připravit datový soubor školení. To lze provést pomocí jednoduchého triku.

Představte si toto - jak by tento graf vypadal v určitém okamžiku v minulosti? Mezi uzly by bylo méně okrajů, protože připojení v sociální síti se postupně vytvářejí.

S ohledem na to můžeme náhodně skrýt některé okraje z daného grafu a pak postupovat podle stejné techniky, jak je vysvětleno v předchozí části, a vytvořit datový soubor školení.

Odškrtněte odkazy z grafu

Při odstraňování odkazů nebo hran bychom se měli vyvarovat odstranění hran, které mohou vytvářet izolovaný uzel (uzel bez hrany) nebo izolovanou síť. Sundejme některé okraje z naší sítě:

Jak vidíte, byly hrany ve dvojicích uzlů (1 a 4), (7 a 9) a (3 a 8) odstraněny.

Přidejte k extrahovaným datům štítky

Dále bychom museli vytvořit funkce pro všechny nespojené páry uzlů, včetně těch, pro které jsme vynechali hrany. Odstraněné hrany budou označeny jako „1“ a nespojené páry uzlů jako „0“.

Cílová proměnná bude v tomto datovém souboru vysoce nevyvážená. To se také setkáte v grafech skutečného světa. Počet párů nespojených uzlů by byl obrovský.

Podívejme se na případovou studii a vyřešíme problém predikce odkazu pomocí Pythonu.

Případová studie: Předpovídejte budoucí propojení mezi stránkami Facebooku

To je místo, kde použijeme všechny výše uvedené do úžasného scénáře skutečného světa.

Budeme pracovat s datovým souborem grafu, ve kterém jsou uzly stránky Facebooku oblíbených potravinových kloubů a renomovaných kuchařů z celého světa. Pokud jsou nějaké dvě stránky (uzly) podobné sobě, pak je mezi nimi hrana (odkaz).

Datový soubor si můžete stáhnout zde.

Cíl: Sestavte model predikce odkazů pro predikci budoucích odkazů (vzájemných hodnocení) mezi nepřipojenými uzly (stránky Facebooku).

Vyhoďme náš notebook Jupyter (nebo Colab)!

Porozumění datům

Nejprve importujeme všechny potřebné knihovny a moduly:

Pojďme načíst stránky Facebooku jako uzly a vzájemné hodnocení mezi stránkami jako okraje:

Výstup: (620, 2102)

Máme 620 uzlů a 2 102 odkazů. Nyní vytvořme dataframe všech uzlů. Každý řádek tohoto datového rámce představuje odkaz tvořený uzly ve sloupcích 'node_1' a 'node_2':

fb_df.head ()

Uzly „276“, „58“, „132“, „603“ a „398“ tvoří spojení s uzlem „0“. Toto uspořádání stránek na Facebooku můžeme snadno znázornit ve formě grafu:

Páni, to vypadá docela něco. Tím se budeme zabývat - drátěné pletivo stránek na Facebooku (modré tečky). Černé čáry jsou odkazy nebo hrany spojující všechny uzly navzájem.

Příprava datové sady pro vytváření modelů

Potřebujeme připravit datový soubor z nepřímého grafu. Tento datový soubor bude mít vlastnosti párů uzlů a cílová proměnná by měla binární povahu, což naznačuje přítomnost odkazů (nebo ne).

Načíst dvojice nespojených uzlů - negativní vzorky

Už jsme pochopili, že k vyřešení problému predikce odkazu musíme připravit dataset z daného grafu. Hlavní částí tohoto souboru dat jsou negativní vzorky nebo nespojené páry uzlů. V této části vám ukážu, jak můžeme z grafu extrahovat nespojené dvojice uzlů.

Nejprve vytvoříme matici sousednosti, abychom zjistili, které páry uzlů nejsou spojeny.

Například sousednost níže uvedeného grafu je čtvercová matice, ve které jsou řádky a sloupce reprezentovány uzly grafu:

Odkazy jsou označeny hodnotami v matici. 1 znamená, že existuje spojení mezi párem uzlů a 0 znamená, že existuje spojení mezi párem uzlů. Například uzly 1 a 3 mají na svém křížovém spoji 0 v matici 0 a tyto uzly také nemají hranu ve výše uvedeném grafu.

Tuto vlastnost matice přiblížení použijeme k nalezení všech nespojených párů uzlů z původního grafu G:

Podívejme se na tvar sousední matice:

adj_G.shape

Výstup: (620, 620)

Jak vidíte, jedná se o čtvercovou matici. Nyní projdeme matici sousednosti, abychom našli polohu nul. Upozorňujeme, že nemusíme procházet celou maticí. Hodnoty v matici jsou stejné nad a pod úhlopříčkou, jak můžete vidět níže:

Můžeme prohledávat hodnoty nad diagonální (zelená část) nebo níže uvedené hodnoty (červená část). Pojďme hledat diagonální hodnoty pro nulu:

Zde je počet párů nespojených uzlů, které máme v našem datovém souboru:

len (all_unconnected_pairs)

Výstup: 19,018

Máme 19 018 nespojených párů. Tyto páry uzlů budou působit jako negativní vzorky během tréninku predikčního modelu odkazu. Udržujme tyto páry v datovém rámci:

Odebrání odkazů z párů propojených uzlů - pozitivní vzorky

Jak jsme diskutovali výše, náhodně vynecháme některé hrany z grafu. Náhodné odstranění hran však může mít za následek oříznutí volně spojených uzlů a fragmentů grafu. To je něco, o co se musíme starat. Musíme se ujistit, že v procesu klesání hran by všechny uzly grafu měly zůstat připojeny.

V níže uvedeném bloku kódu nejprve zkontrolujeme, zda vynechání dvojice uzlů povede k rozdělení grafu (number_connected_component> 1) nebo ke snížení počtu uzlů. Pokud se obě věci nestanou, vypustíme tento pár uzlů a opakujeme stejný proces s dalším párem uzlů.

Nakonec dostaneme seznam párů uzlů, které lze z grafu vynechat, a všechny uzly by zůstaly neporušené:

len (omissible_links_index)

Výstup: 1483

Máme přes 1400 odkazů, které můžeme z grafu vynechat. Tyto vypuštěné hrany budou působit jako pozitivní příklady školení během tréninku predikčního modelu.

Data pro modelový trénink

Dále připojíme tyto odnímatelné okraje k datovému rámečku nespojených párů uzlů. Protože tyto nové hrany jsou pozitivní vzorky, budou mít cílovou hodnotu '1':

Podívejme se na rozložení hodnot cílové proměnné:

data ['link']. value_counts ()

0 -19018 1 -1483

Ukazuje se, že se jedná o vysoce nevyvážená data. Poměr odkazu k žádnému odkazu je blízko 8%. V další části vyjmeme funkce pro všechny tyto páry uzlů.

Extrakce funkcí

Po vynechání odkazů použijeme algoritmus node2vec k extrahování prvků uzlu z grafu. Nejprve tedy vytvořte nový graf po odstranění odstranitelných odkazů:

Dále nainstalujeme knihovnu node2vec. Je to docela podobné algoritmu DeepWalk. To však zahrnuje zkreslené náhodné procházky. Chcete-li se dozvědět více o node2vec, měli byste si určitě prohlédnout tento dokument node2vec: Scalable Feature Learning for Networks.

Prozatím mějte na paměti, že pro vektorovou reprezentaci uzlů grafu se používá node2vec. Pojďme to nainstalovat:

! pip install node2vec

Instalace na lokální počítač může chvíli trvat (pokud používáte Colab), je to docela rychlé.

Nyní budeme trénovat model node2vec na našem grafu (G_data):

Dále použijeme trénovaný model node2vec na každou dvojici uzlů v datovém rámečku „data“. Pro výpočet funkcí dvojice nebo hrany přidáme funkce uzlů této dvojice:

x = [(n2w_model [str (i)] + n2w_model [str (j)]) pro i, j v zipu (data ['node_1'], data ['node_2'])]]

Budování našeho modelu předpovědi odkazů

Abychom ověřili výkon našeho modelu, měli bychom naše data rozdělit do dvou částí - jednu pro trénink modelu a druhou pro testování výkonu modelu:

Pojďme nejprve zařadit logistický regresní model:

Nyní provedeme předpovědi na testovací sadě:

predikce = lr.predict_proba (xtest)

Použijeme skóre AUC-ROC ke kontrole výkonu našeho modelu.

roc_auc_score (ytest, předpovědi [:, 1])

Výstup: 0,7817

Získáme skóre 0,78 pomocí logistického regresního modelu. Uvidíme, jestli můžeme získat lepší skóre pomocí složitějšího modelu.

Trénink se zastavil po 208. iteraci, protože jsme použili kritéria předčasného zastavení. A co je nejdůležitější, model získal na testovací sadě impozantní 0,9273 AUC skóre. Doporučujeme, abyste se seznámili s dokumentací lightGBM a dozvěděli se více o různých parametrech.

Konec poznámky

V grafech je obrovský potenciál. Můžeme to využít k vyřešení velkého počtu skutečných problémů, z nichž jeden je predikce spojení.

V tomto článku jsme ukázali, jak lze problém predikce propojení řešit pomocí strojového učení a jaká jsou omezení a důležité aspekty, které musíme mít na paměti při řešení takového problému.

Prosím, neváhejte se zeptat na jakékoli dotazy nebo nechte svůj názor v sekci komentářů níže. Pokračujte v průzkumu!

Původně zveřejněno na adrese https://www.analyticsvidhya.com 16. ledna 2020.