Кіраўніцтва па прагназаванні спасылак - Як прадказаць вашыя будучыя сувязі на Facebook

Агляд

  • Уводзіны для таго, каб звязаць прагноз, як ён працуе і дзе можна выкарыстоўваць яго ў рэальным свеце
  • Даведайцеся пра важнасць Link Prediction у сацыяльных медыя
  • Стварыце сваю першую мадэль прагназавання спасылак для выпадку выкарыстання Facebook з дапамогай Python

Уводзіны

Вы ніколі не задумваліся, хто можа быць вашым наступным падключэннем да Facebook? Цікава, ад каго можа з'явіцца наступны запыт?

Што рабіць, калі я сказаў вам, што ёсць спосаб прадказаць гэта?

Я люблю мазгавы штурм і прыдумваю гэтыя заявы пра праблемы, калі я праглядаю свой уліковы запіс Facebook. Гэта адзін з пераваг развіцця мыслення навукоўца дадзеных!

Большасць платформаў сацыяльных медыя, уключаючы Facebook, могуць быць структураваны як графікі. Зарэгістраваныя карыстальнікі ўзаемазвязаны ва ўсёй сетцы сетак. А каб працаваць над гэтымі сеткамі і графікамі, нам патрэбен іншы набор падыходаў, інструментаў і алгарытмаў (замест традыцыйных метадаў машыннага навучання).

Такім чынам, у гэтым артыкуле мы вырашым праблему сацыяльнай сеткі пры дапамозе графікаў і машыннага навучання. Мы спачатку разбярэмся ў асноўных канцэпцыях і кампанентах прагназавання спасылак перад тым, як заняцца тэматычным даследаваннем Facebook і рэалізаваць яго ў Python!

Я рэкамендую перагледзець прыведзеныя ніжэй артыкулы, каб даведацца, што такое графікі і як яны працуюць:

Змест

  1. Агляд аналітыкі сацыяльных сетак
  2. Буквар пра прагназаванне спасылак
  3. Стратэгія вырашэння праблемы прагназавання спасылак
  4. Тэматычнае даследаванне: прагназаванне будучых сувязяў паміж старонкамі Facebook - Разуменне дадзеных - Стварэнне мадэлі падрыхтоўкі набораў - Выманне функцый - Стварэнне мадэлі: Мадэль прадказання спасылак

Агляд аналітыкі сацыяльных сетак

Давайце вызначымся з сацыяльнай сеткай спачатку, перш чым пагрузіцца ў канцэпцыю прагназавання спасылак.

Сацыяльная сетка, па сутнасці, уяўляе сабой адносіны паміж сацыяльнымі структурамі, такімі як людзі, арганізацыі, урады, палітычныя партыі і г.д.

Узаемадзеянне гэтых суб'ектаў генеруе неймаверную колькасць дадзеных у выглядзе паведамленняў, паведамленняў у чаце, твітаў, лайкаў, каментарыяў, акцый і г.д. Гэта адкрывае акно магчымасцей і выпадкаў выкарыстання, над якімі можна працаваць.

Гэта прывядзе нас да сацыяльнай сеткі Analytics (СНС). Мы можам вызначыць гэта як спалучэнне некалькіх мерапрыемстваў, якія выконваюцца ў сацыяльных медыя. Гэтыя мерапрыемствы ўключаюць збор дадзеных з інтэрнэт-сайтаў сацыяльных медыя і выкарыстанне гэтых дадзеных для прыняцця бізнес-рашэнняў.

Перавагі аналітыкі сацыяльных сетак могуць быць вельмі карыснымі. Вось некалькі ключавых пераваг:

  • Дапамагае лепш зразумець сваю аўдыторыю
  • Выкарыстоўваецца для сегментацыі кліентаў
  • Выкарыстоўваецца для распрацоўкі рэкамендацыйных сістэм
  • Вызначце сярод іншага фальшывыя навіны

Буквар пра прагназаванне спасылак

Прагназаванне спасылак - адна з найважнейшых тэм даследавання ў галіне графікаў і сетак. Мэта прагназавання спасылкі заключаецца ў выяўленні пары вузлоў, якія альбо ў далейшым будуць фармаваць сувязь, альбо не.

Прагназаванне спасылак мае тонус выкарыстання ў рэальных дадатках. Вось некалькі важных выпадкаў выкарыстання прагназавання спасылак:

  • Прагназуйце, якія кліенты, хутчэй за ўсё, купляюць такую ​​прадукцыю на інтэрнэт-пляцоўках, як Amazon. Гэта можа дапамагчы зрабіць лепшыя рэкамендацыі па прадуктах
  • Прапануйце ўзаемадзеянне альбо супрацоўніцтва паміж супрацоўнікамі арганізацыі
  • Выманне жыццёвай інфармацыі з тэрарыстычных сетак

У гэтым артыкуле мы разгледзім крыху іншы выпадак выкарыстання прагназавання спасылак - прагназаванне спасылак у сацыяльнай сетцы Інтэрнэт!

Стратэгія вырашэння праблемы прагназавання спасылак

Калі мы можам нейкім чынам прадставіць графік у выглядзе структураванага набору дадзеных, які мае мноства функцый, то, магчыма, мы можам выкарыстоўваць машыннае навучанне, каб прадказаць фарміраванне сувязяў паміж непалучанымі парамі вузлоў графіка.

Давайце возьмем фіктыўны графік, каб зразумець гэтую ідэю. Ніжэй прыведзены графік 7 вузлоў, а непалучаныя пары вузлоў - AF, BD, BE, BG і EG:

Графік часу, г. зн

Зараз, скажам, мы прааналізуем дадзеныя і прыдумалі графік ніжэй. Было сфарміравана некалькі новых злучэнняў (спасылкі чырвоным колерам):

Графік часу t + n

Для стварэння любой мадэлі машыннага навучання нам трэба мець шэраг зменных прадказальнікаў і мэтавую зменную. Дык дзе гэтыя зменныя? Ну, мы можам атрымаць гэта з самога графіка! Давайце паглядзім, як гэта робіцца.

Нашай мэтай з'яўляецца прадказаць, ці будзе сувязь паміж любымі 2 не звязанымі вузламі. З сеткі ў час t мы можам атрымаць наступныя пары вузлоў, якія не маюць паміж сабой сувязяў:

  1. АФ
  2. BD
  3. БЫЦЬ
  4. БГ
  5. ЯГ

Звярніце ўвагу, што для зручнасці я разгледзеў толькі тыя вузлы, якія размяшчаюцца на пару спасылак.

Наступным крокам для нас з'яўляецца стварэнне функцый для кожнай пары вузлоў. Добрай навіной з'яўляецца тое, што існуе некалькі метадаў для атрымання функцый з вузлоў у сетцы. Дапусцім, мы выкарыстоўваем адзін з гэтых метадаў і будуем асаблівасці для кожнай з гэтых пар. Аднак мы ўсё яшчэ не ведаем, што такое мэтавая зменная. Не варта хвалявацца - мы таксама лёгка гэта атрымаем.

Паглядзіце на графік падчас t + n. Мы бачым, што ў пары ёсць тры новыя спасылкі для пар AF, BD і BE адпаведна. Такім чынам, мы прысвоім кожнаму з іх значэнне 1. Парам вузлоў BG і EG будзе прызначана 0, паколькі паміж вузламі да гэтага часу няма сувязяў.

Такім чынам, дадзеныя будуць выглядаць так:

Цяпер, калі ў нас ёсць мэтавая зменная, мы можам пабудаваць мадэль машыннага навучання, выкарыстоўваючы гэтыя дадзеныя для прагназавання спасылкі.

Такім чынам, гэта тое, як нам трэба выкарыстоўваць сацыяльныя графікі ў двух розных выпадках часу, каб здабыць мэтавую зменную, то ёсць наяўнасць сувязі паміж парай вузлоў. Але ўлічыце, што ў рэальных сцэнарах мы будзем мець толькі дадзеныя сучаснасці.

Выманне дадзеных з графіка для пабудовы мадэлі

У раздзеле вышэй мы змаглі атрымаць пазнакі для мэтавай зменнай, таму што мы мелі доступ да графіка падчас t + n. Аднак у рэальных сцэнарыях у нас будзе толькі адзін набор графікаў. Вось так!

Скажам, у нас прыведзены ніжэй графік сацыяльнай сеткі, дзе вузлы з'яўляюцца карыстальнікамі, а краю прадстаўляюць нейкую сувязь:

Кандыдатнымі парамі вузлоў, якія могуць у будучыні стварыць сувязь, з'яўляюцца (1 і 2), (2 і 4), (5 і 6), (8 і 10) і гэтак далей. Мы павінны пабудаваць мадэль, якая будзе прадказваць, ці будзе сувязь паміж гэтымі парамі вузла ці не. Гэта тое, пра што прагназуецца сувязь!

Аднак, каб пабудаваць мадэль прагназавання спасылак, нам трэба падрыхтаваць набор дадзеных аб падрыхтоўцы з гэтага графіка. Зрабіць гэта можна з дапамогай простага хітрасці.

Прадстаўце гэта - як бы выглядаў гэты графік у нейкі момант у мінулым? Памежнікаў паміж вузламі будзе менш, бо злучэнні ў сацыяльнай сетцы паступова будуюцца з цягам часу.

Такім чынам, памятаючы пра гэта, мы можам хаатычна схаваць некаторыя бакі ад дадзенага графіка, а потым прытрымлівацца той жа методыкі, што была растлумачана ў папярэднім раздзеле.

Закрэсліце спасылкі з графіка

Пры выдаленні спасылак і краёў мы павінны пазбягаць выдалення краю, які можа стварыць ізаляваны вузел (вузел без краю) або ізаляваную сетку. Давайце здымем некаторыя з краёў нашай сеткі:

Як бачым, краю ў парах вузлоў (1 і 4), (7 і 9) і (3 і 8) былі выдалены.

Дадайце меткі да здабытых дадзеных

Далей нам трэба будзе стварыць функцыі для ўсіх непалучаных пар вузлоў, уключаючы тыя, для якіх мы апусцілі рэбры. Выдаленыя краю будуць пазначаныя як "1", а непалучаныя пары вузлоў - "0".

Мэтавая зменная будзе вельмі збалансавана ў гэтым наборы дадзеных. З гэтым вы сутыкнецеся і ў рэальных графіках. Колькасць непазлучаных пар вузлоў была б велізарнай.

Давайце возьмемся з тэматычнага даследавання і вырашым праблему прагназавання спасылак пры дапамозе Python.

Тэматычнае даследаванне: прагназуйце будучыя сувязі паміж старонкамі Facebook

Тут мы ўжываем усё вышэйсказанае ў дзіўным сцэнарыі рэальнага свету.

Мы будзем працаваць з наборам дадзеных графікаў, у якіх вузлы - гэта старонкі папулярных суставаў ежы ў Facebook і вядомых кухараў з усяго свету. Калі якія-небудзь дзве старонкі (вузлы) падобныя адзін на аднаго, значыць, паміж імі ёсць край (спасылка).

Вы можаце загрузіць набор дадзеных тут.

Мэта: пабудаваць мадэль прагназавання спасылак для прагназавання будучых сувязяў (узаемных сімпатый) паміж не злучанымі вузламі (старонкі Facebook).

Давайце запусцім наш сшытак Юпітэр (альбо Колаб)!

Разуменне дадзеных

Мы спачатку імпартуем усе неабходныя бібліятэкі і модулі:

Давайце загружаем старонкі Facebook у якасці вузлоў і ўзаемна падабаецца паміж старонкамі як краю:

Выхад: (620, 2102)

У нас 620 вузлоў і 2 022 спасылкі. Давайце зараз створым кадр дадзеных усіх вузлоў. Кожны радок гэтага фрэйма ўяўляе сабой спасылку, сфармаваную вузламі ў слупках "node_1" і "node_2" адпаведна:

fb_df.head ()

Вузлы "276", "58", "132", "603" і "398" утвараюць спасылкі з вузлом "0". Мы можам лёгка прадставіць гэтае размяшчэнне старонак у Facebook у выглядзе графіка:

Нічога сабе, гэта выглядае зусім нечым. Гэта тое, што мы будзем мець справу - драцяная сетка на старонках Facebook (сінія кропкі). Чорныя лініі - гэта спасылкі альбо краю, якія злучаюць усе вузлы адзін з адным.

Падрыхтоўка набору дадзеных для стварэння мадэлі

Мы павінны падрыхтаваць набор дадзеных з неарыентаванага графіка. Гэты набор дадзеных будзе мець асаблівасці пары вузлоў, а мэтавая пераменная будзе мець бінарны характар, што паказвае на наяўнасць спасылак (ці не).

Атрыманне непалучаных пар вузла - адмоўныя ўзоры

Мы ўжо зразумелі, што для вырашэння праблемы прагназавання спасылак мы павінны падрыхтаваць набор дадзеных з дадзенага графіка. Асноўную частку гэтага набору дадзеных складаюць адмоўныя ўзоры альбо непалучаныя пары вузлоў. У гэтым раздзеле я пакажу вам, як мы можам здабываць злучаныя пары вузлоў з графіка.

Спачатку мы створым матрыцу суседства, каб знайсці, якія пары вузлоў не звязаны.

Напрыклад, суседства гэтага графіка ніжэй уяўляе сабой квадратную матрыцу, у якой радкі і слупкі прадстаўлены вузламі графіка:

Спасылкі абазначаюцца значэннямі ў матрыцы. 1 азначае, што існуе сувязь паміж парай вузлоў і 0 азначае, што існуе сувязь паміж парай вузлоў. Напрыклад, вузлы 1 і 3 маюць 0 на іх перасячэнні ў матрыцы, і гэтыя вузлы таксама не маюць краю на графіцы вышэй.

Мы будзем выкарыстоўваць гэтую ўласцівасць матрыцы суседства, каб знайсці ўсе непалучаныя пары вузлоў з арыгінальнага графіка G:

Давайце паглядзім форму матрыцы суседства:

adj_G.shape

Выхад: (620, 620)

Як бачыце, гэта квадратная матрыца. Зараз мы пройдзем матрыцу суседства, каб знайсці пазіцыі нулёў. Звярніце ўвагу, што нам не трэба праходзіць усю матрыцу. Значэнні ў матрыцы аднолькавыя вышэй і ніжэй дыяганалі, як вы бачыце ніжэй:

Мы можам альбо шукаць значэнні вышэй дыяганалі (зялёная частка), альбо значэнні ніжэй (чырвоная частка). Давайце шукаем дыяганальныя значэнні нуля:

Вось колькі нязлучаных пар вузлоў у нас ёсць:

len (all_unconnected_pairs)

Выхад: 19,018

У нас 19 018 непарыўных пар. Гэтыя пары вузлоў будуць выконваць ролю адмоўных узораў падчас навучання мадэлі прагназавання спасылак. Давайце захаваем гэтыя пары ў кадры дадзеных:

Выдаліце ​​спасылкі з падлучаных пар вузла - станоўчыя ўзоры

Як мы ўжо казалі вышэй, мы выпадкова адкінем некаторыя краю з графіка. Аднак выпадковае выдаленне краёў можа прывесці да адсячэння слаба звязаных вузлоў і фрагментаў графіка. Гэта тое, пра што мы павінны клапаціцца. Мы павінны пераканацца, што ў працэсе падзення краёў усе вузлы графіка павінны заставацца звязанымі.

У блоку кода ніжэй мы спачатку правяраем, ці не прывядзе пара вузел да расшчаплення графа (number_connected_components> 1) або да скарачэння колькасці вузлоў. Калі абедзве рэчы не адбудуцца, мы адкідваем пару вузлоў і паўтараем той жа працэс з наступнай парай вузла.

У рэшце рэшт, мы атрымаем спіс пар вузлоў, якія можна выкінуць з графіка, і ўсе вузлы ўсё яшчэ застануцца цэлымі:

len (ovable_links_index)

Выхад: 1483

У нас больш за 1400 спасылак, якія мы можам скінуць з графіка. Гэтыя апушчаныя краю будуць выступаць у якасці станоўчых прыкладаў трэнінгу падчас трэнінгу мадэлі прагназавання спасылак.

Дадзеныя для мадэльнага навучання

Далей мы будзем далучаць гэтыя здымныя краю да кадра дадзеных не злучаных пар вузлоў. Паколькі гэтыя новыя краю станоўчыя ўзоры, яны будуць мець мэтавае значэнне "1":

Давайце праверым размеркаванне значэнняў мэтавай зменнай:

дадзеныя ['спасылка']. value_counts ()

0 -19018 1 -1483

Аказваецца, гэта вельмі незбалансаваныя дадзеныя. Каэфіцыент спасылкі супраць адсутнасці спасылкі недалёка ад 8%. У наступным раздзеле мы здабудзем функцыі для ўсіх гэтых пар вузлоў.

Асаблівасць здабычы

Мы будзем выкарыстоўваць алгарытм node2vec для атрымання функцый вузла з графіка пасля адмены спасылак. Такім чынам, давайце спачатку створым новы графік, скінуўшы здымныя спасылкі:

Далей мы ўсталюем бібліятэку node2vec. Ён даволі падобны на алгарытм DeepWalk. Аднак гэта прадугледжвае неаб'ектыўныя выпадковыя прагулкі. Каб даведацца больш пра node2vec, вам варта абавязкова прачытаць гэты артыкул node2vec: Магчымасць навучання маштабаваным сеткам.

Пакуль што толькі ўлічыце, што node2vec выкарыстоўваецца для вектарнага прадстаўлення вузлоў графіка. Давайце ўсталюем яго:

! pip ўсталяваць node2vec

Гэта можа заняць некаторы час, каб усталяваць на вашай лакальнай машыне (гэта даволі хутка, калі вы выкарыстоўваеце Colab).

Зараз мы будзем трэніраваць мадэль node2vec на нашым графіку (G_data):

Далей мы будзем ужываць навучаную мадэль node2vec для кожнай пары вузлоў у кадры "дадзеныя". Каб вылічыць асаблівасці пары ці краю, мы складзем асаблівасці вузлоў гэтай пары:

x = [(n2w_model [str (i)] + n2w_model [str (j)]) для i, j in zip (data ['node_1'], data ['node_2'])]

Пабудова нашай мадэлі прагназавання спасылак

Для праверкі эфектыўнасці нашай мадэлі мы павінны падзяліць нашы дадзеныя на дзве часткі: адну для навучання мадэлі, а другую для праверкі прадукцыйнасці мадэлі:

Давайце спачатку падыдзем мадэль лагістычнай рэгрэсіі:

Цяпер мы будзем рабіць прагнозы на тэставым наборы:

прагнозы = lr.predict_proba (xtest)

Мы будзем выкарыстоўваць бал AUC-ROC, каб праверыць працу нашай мадэлі.

roc_auc_score (ytest, прагнозы [:, 1])

Выхад: 0,7817

Мы атрымліваем адзнаку 0,78, выкарыстоўваючы мадэль лагістычнай рэгрэсіі. Давайце паглядзім, ці зможам мы атрымаць больш высокі бал, выкарыстоўваючы больш складаную мадэль.

Навучанне спынілася пасля 208-й ітэрацыі, таму што мы ўжылі крытэрыі ранняй прыпынку. Самае галоўнае, што мадэль атрымала ўражлівы 0,9273 AUC бал на тэставым наборы. Я рэкамендую вам паглядзець дакументацыю на lightGBM, каб даведацца больш пра розныя параметры.

Канцавыя нататкі

У графах ёсць велізарны патэнцыял. Мы можам выкарыстоўваць гэта, каб вырашыць вялікую колькасць рэальных праблем, сярод якіх адно прадказанне сувязі.

У гэтым артыкуле мы прадэманстравалі, як можна справіцца з праблемай прагназавання спасылак пры дапамозе машыннага навучання і якія абмежаванні і важныя аспекты, якія мы павінны мець на ўвазе пры вырашэнні такой праблемы.

Калі ласка, задавайце любыя пытанні альбо пакіньце свае водгукі ў раздзеле каментароў ніжэй. Працягвайце вывучаць!

Першапачаткова апублікавана на https://www.analyticsvidhya.com 16 студзеня 2020 года.