<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    <del id="afajh"><form id="afajh"></form></del>
        1. <th id="afajh"><progress id="afajh"></progress></th>
          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>

          使用DeepWalk從圖中提取特征

          共 10366字,需瀏覽 21分鐘

           ·

          2021-05-16 07:05

          點擊上方小白學(xué)視覺”,選擇加"星標(biāo)"或“置頂

          重磅干貨,第一時間送達

          本文轉(zhuǎn)自:opencv學(xué)堂


          概述


          • 從表格或圖像數(shù)據(jù)中提取特征的方法已經(jīng)眾所周知了,但是圖(數(shù)據(jù)結(jié)構(gòu)的圖)數(shù)據(jù)呢?
          • 學(xué)習(xí)如何使用DeepWalk從圖中提取特征
          • 我們還將用Python實現(xiàn)DeepWalk來查找相似的Wikipedia頁面

          介紹


          我被谷歌搜索的工作方式迷住了。每次我搜索一個主題都會有很多小問題出現(xiàn)。以“人們也在搜索?”為例。當(dāng)我搜索一個特定的人或一本書,從谷歌我總是得到與搜索內(nèi)容類似的建議。

          例如,當(dāng)我搜索“Lewis Hamilton”時,我得到了其他著名f1車手的名單:
          這些豐富而相關(guān)的內(nèi)容是由高度復(fù)雜的圖處理數(shù)據(jù)處理算法提供的。正是這種圖和網(wǎng)的力量讓我(以及許多其他數(shù)據(jù)科學(xué)家)著迷!自從我開始使用圖以來,出現(xiàn)了許多新的技術(shù)。
          在本文中,我將介紹任何機器學(xué)習(xí)項目中最重要的步驟之一—特征提取不過,這里有一個小小的轉(zhuǎn)折。我們將從圖數(shù)據(jù)集中提取特征,并使用這些特征來查找相似的節(jié)點(實體)。

          目錄


          1. 數(shù)據(jù)的圖示

          2. 不同類型的基于圖的特征

          • 節(jié)點屬性

          • 局部結(jié)構(gòu)特征

          • 節(jié)點嵌入

          1. DeepWalk簡介

          2. 在Python中實施DeepWalk以查找相似的Wikipedia頁面


          數(shù)據(jù)的圖示


          當(dāng)你想到“網(wǎng)絡(luò)”時,會想到什么?通常是諸如社交網(wǎng)絡(luò),互聯(lián)網(wǎng),已連接的IoT設(shè)備,鐵路網(wǎng)絡(luò)或電信網(wǎng)絡(luò)之類的事物。在圖論中,這些網(wǎng)絡(luò)稱為圖

          網(wǎng)絡(luò)是互連節(jié)點的集合。節(jié)點表示實體,它們之間的連接是某種關(guān)系。

          例如,我們可以用圖的形式表示一組社交媒體帳戶:

          節(jié)點是用戶的數(shù)字檔案,連接表示他們之間的關(guān)系,例如誰跟隨誰或誰與誰是朋友。
          圖的用例不僅限于社交媒體!我們還可以使用圖和網(wǎng)絡(luò)表示其他類型的數(shù)據(jù)(并且在本文中我們將介紹一個獨特的行業(yè)用例)。

          為什么我們將數(shù)據(jù)表示為圖?

          為什么不僅僅使用典型的數(shù)據(jù)可視化技術(shù)來可視化數(shù)據(jù)?為什么要更復(fù)雜并學(xué)習(xí)新概念?下面我們會給出答案。
          圖數(shù)據(jù)集和數(shù)據(jù)庫可幫助我們應(yīng)對在處理結(jié)構(gòu)化數(shù)據(jù)時面臨的若干挑戰(zhàn)這就是為什么當(dāng)今的主要科技公司,例如Google,Uber,Amazon和Facebook使用某種形式的圖的原因。
          讓我們以一個例子來理解為什么圖是數(shù)據(jù)的重要表示形式。看下圖:
          這是一小部分Facebook用戶(a, B, C, D, E, F, G)的數(shù)據(jù)集。圖像的左半邊包含這個數(shù)據(jù)的表格形式。每一行代表一個用戶和他/她的一個朋友。
          右半部分包含代表同一組用戶的圖。該圖的邊緣告訴我們,連接的節(jié)點是Facebook上的朋友。現(xiàn)在,讓我們解決一個簡單的查詢:
          “找到用戶A的朋友和用戶A朋友的朋友。
          查看表格數(shù)據(jù)和上面的圖。哪種數(shù)據(jù)形式更適合回答此類查詢?
          使用圖來解決該問題要容易得多,因為我們只需要遍歷從節(jié)點A長度為2的路徑(ABC和ADF),即可找到朋友和朋友的朋友。
          因此,圖可以輕松捕獲節(jié)點之間的關(guān)系,這在常規(guī)數(shù)據(jù)結(jié)構(gòu)中是一項艱巨的任務(wù)現(xiàn)在,讓我們看看使用圖可以解決什么樣的問題。
          基于圖的特征的不同類型


          為了解決上述問題,我們無法將圖直接提供給機器學(xué)習(xí)模型。我們必須首先從中創(chuàng)建特征,然后模型將使用這些特征。
          此過程類似于我們在自然語言處理(NLP)或計算機視覺中所做的過程。我們首先從文本或圖像中提取數(shù)字特征,然后將這些特征作為輸入提供給機器學(xué)習(xí)模型:
          從圖中提取的特征可以大致分為三類:
          1. 節(jié)點屬性我們知道圖中的節(jié)點代表實體,并且這些實體具有自己的特征屬性。我們可以將這些屬性用作每個節(jié)點的特征。例如,在航空公司航線網(wǎng)絡(luò)中,節(jié)點將代表機場。這些節(jié)點將具有飛機容量,航站樓數(shù)量,著陸區(qū)等特征。
            2.局部結(jié)構(gòu)特點節(jié)點的(相鄰節(jié)點的數(shù)量),相鄰節(jié)點的平均度,一個節(jié)點與其他節(jié)點形成的三角形數(shù),等等。
          2. 節(jié)點嵌入上面討論的特征僅包含與節(jié)點有關(guān)的信息。它們不捕獲有關(guān)節(jié)點上下文的信息。在上下文中,我指的是周圍的節(jié)點。節(jié)點嵌入通過用固定長度向量表示每個節(jié)點,在一定程度上解決了這個問題。這些向量能夠捕獲有關(guān)周圍節(jié)點的信息(上下文信息)
          用于學(xué)習(xí)節(jié)點嵌入的兩個重要的現(xiàn)代算法是DeepWalkNode2Vec在本文中,我們將介紹并實現(xiàn)DeepWalk算法。
          DeepWalk簡介


          要了解DeepWalk,重要的是要正確理解詞嵌入及其在NLP中的使用方式。我建議在下面的文章中仔細(xì)閱讀Word2Vec的解釋:
          https://www.analyticsvidhya.com/blog/2019/07/how-to-build-recommendation-system-word2vec-python/?utm_source=blog&utm_medium=graph-feature-extraction-deepwalk
          為了將事物置于上下文中,詞嵌入是文本的向量表示形式,它們捕獲上下文信息。讓我們看看下面的句子:
          • 我乘巴士孟買
          • 我乘火車去孟買
          粗體字(公共汽車和火車)的向量將非常相似,因為它們出現(xiàn)在相同的上下文中,即粗體文本之前和之后的詞。該信息對于許多NLP任務(wù)非常有用,例如文本分類,命名實體識別,語言建模,機器翻譯等等。
          我們還可以在每個節(jié)點的圖中捕獲此類上下文信息。但是,為了學(xué)習(xí)NLP空間中的詞嵌入,我們將句子提供給Skip-gram模型(淺層神經(jīng)網(wǎng)絡(luò))。句子是按一定順序排列的單詞序列。
          因此,要獲得節(jié)點嵌入,我們首先需要安排圖中的節(jié)點序列。我們?nèi)绾螐膱D中獲得這些序列?有一項針對該任務(wù)的技術(shù)稱為隨機游走。

          什么是隨機游走?

          隨機游走是一種從圖中提取序列的技術(shù)。我們可以使用這些序列來訓(xùn)練一個skip-gram模型來學(xué)習(xí)節(jié)點嵌入。

          讓我說明一下隨機游走的工作原理。讓我們考慮下面的無向圖:
          我們將在該圖上應(yīng)用隨機游走并從中提取節(jié)點序列。我們將從節(jié)點1開始,并覆蓋任意方向的兩條邊:
          從節(jié)點1,我們可以轉(zhuǎn)到任何連接的節(jié)點(節(jié)點3或節(jié)點4)。我們隨機選擇了節(jié)點4。現(xiàn)在再次從節(jié)點4開始,我們不得不隨機選擇前進的方向。我們將轉(zhuǎn)到節(jié)點5。現(xiàn)在我們有3個節(jié)點的序列:[節(jié)點1 –節(jié)點4 –節(jié)點5]。
          讓我們生成另一個序列,但是這次是從另一個節(jié)點生成的:
          讓我們選擇節(jié)點15作為原始節(jié)點。從節(jié)點5和6,我們將隨機選擇節(jié)點6。然后從節(jié)點11和2,我們選擇節(jié)點2。新序列為[節(jié)點15 –節(jié)點6 –節(jié)點2]。
          我們將對圖中的每個節(jié)點重復(fù)此過程。這就是隨機游走技術(shù)的工作原理。

          在生成節(jié)點序列之后,我們必須將它們提供給一個skip-gram模型以獲得節(jié)點嵌入。整個過程被稱為Deepwalk。

          在下一節(jié)中,我們將在Wikipedia文章網(wǎng)絡(luò)上從頭開始實施DeepWalk。
          在Python中實施DeepWalk以查找相似的Wikipedia頁面
          這將是本文中最令人興奮的部分,尤其是如果你喜歡代碼。因此,請啟動這些Jupyter notebook!
          我們將使用Wikipedia文章圖,并使用DeepWalk從中提取節(jié)點嵌入然后,我們將使用這些嵌入來查找相似的Wikipedia頁面。
          我們不會觸及這些文章中的任何文本。我們的目標(biāo)是純粹基于圖的結(jié)構(gòu)來計算頁面之間的相似度。
          但是,等等。我們?nèi)绾我约霸诤翁帿@得Wikipedia圖數(shù)據(jù)集?Seealsology這個出色的工具將為我們提供幫助。這有助于我們從任何Wikipedia頁面創(chuàng)建圖。你甚至可以提供多個Wikipedia頁面作為輸入。這是該工具的屏幕截圖:
          如果一個頁面鏈接到另一個頁面,就會有一個圖表示兩個頁面之間的聯(lián)系。
          看看在Seealsology中該圖的形成方式。值得一看:
          https://s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/11/graph_buildup.mp4?_=1
          圖中的節(jié)點非常接近,并不一定意味著它們在語義上相似因此,需要在向量空間中表示這些節(jié)點,我們可以在其中識別相似的節(jié)點。
          當(dāng)然,我們可以使用其他方法來完成此任務(wù)。例如,我們可以解析這些節(jié)點(Wikipedia頁面)中的所有文本,并在詞嵌入的幫助下用向量表示每個頁面。然后,我們可以計算這些向量之間的相似度以找到相似的頁面。但是,這種基于NLP的方法存在一些缺點:
          • 如果有數(shù)百萬個節(jié)點,那么我們需要大量的計算能力來解析文本并從所有這些節(jié)點或頁面中學(xué)習(xí)詞嵌入
          • 這種方法不會捕獲這些頁面之間連接的信息。例如,一對直接連接的頁面可能比一對間接連接的頁面具有更強的關(guān)系
          這些缺點可以通過圖和節(jié)點嵌入輕松解決。因此,一旦你的圖準(zhǔn)備就緒,就可以從Seealsology下載TSV文件。在此文件中,每一行都是一對節(jié)點。我們將使用此數(shù)據(jù)來重構(gòu)圖,并在其上應(yīng)用DeepWalk算法以獲得節(jié)點嵌入。
          讓我們開始吧!你可以為此使用Jupyter Notebook或Colab。

          導(dǎo)入所需的Python庫

          import networkx as nximport pandas as pdimport numpy as npimport randomfrom tqdm import tqdmfrom sklearn.decomposition import PCA
          import matplotlib.pyplot as plt%matplotlib inline

          加載數(shù)據(jù)集

          你可以從這里下載.tsv文件:
          https://s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/11/space_data.zip
          df = pd.read_csv("space_data.tsv", sep = "\t")df.head()

          Output:

          目標(biāo)都包含Wikipedia實體。對于所有行,目標(biāo)實體在源實體的Wikipedia頁面有其超鏈接。

          構(gòu)造圖

          G = nx.from_pandas_edgelist(df, "source", "target", edge_attr=True, create_using=nx.Graph())

          讓我們檢查圖中的節(jié)點數(shù):

          len(G)

          Output: 2088

          我們將處理2,088個Wikipedia頁面。

          隨機游走

          在這里,我定義了一個函數(shù),將節(jié)點和被遍歷的路徑的長度作為輸入。它將從指定的輸入節(jié)點以隨機的方式穿過連接節(jié)點。最后,它將返回遍歷節(jié)點的順序:
          def get_randomwalk(node, path_length):
          random_walk = [node]
          for i in range(path_length-1): temp = list(G.neighbors(node)) temp = list(set(temp) - set(random_walk)) if len(temp) == 0: break
          random_node = random.choice(temp) random_walk.append(random_node) node = random_node
              return random_walk

          讓我們來試試節(jié)點“space exploration”這個函數(shù):

          get_randomwalk('space exploration', 10)

          輸出

          在這里,我已指定要遍歷的長度為10。你可以更改此數(shù)字并進行操作。接下來,我們將捕獲數(shù)據(jù)集中所有節(jié)點的隨機游走序列:
          # 從圖獲取所有節(jié)點的列表all_nodes = list(G.nodes())
          random_walks = []for n in tqdm(all_nodes): for i in range(5): random_walks.append(get_randomwalk(n,10))
          # 序列個數(shù)len(random_walks)
          輸出: 10,440
          因此,將遍歷長度設(shè)置為10,我們得到了10,440個節(jié)點的隨機游動序列。我們可以將這些序列用作skip-gram模型的輸入,并提取該模型學(xué)習(xí)到的權(quán)重。
          # importing required libraries
          import pandas as pdimport networkx as nximport numpy as npimport randomfrom tqdm import tqdmfrom sklearn.decomposition import PCAimport pprintfrom gensim.models import Word2Vecimport warningswarnings.filterwarnings('ignore')
          # read the datasetdf = pd.read_csv("space_data.tsv", sep = "\t")print(df.head())
          G = nx.from_pandas_edgelist(df, "source", "target", edge_attr=True, create_using=nx.Graph())
          G = nx.from_pandas_edgelist(df, "source", "target", edge_attr=True, create_using=nx.Graph())
          print('The number of nodes in pur graph: ',len(G))
          def get_randomwalk(node, path_length): random_walk = [node] for i in range(path_length-1): temp = list(G.neighbors(node)) temp = list(set(temp) - set(random_walk)) if len(temp) == 0: break
          random_node = random.choice(temp) random_walk.append(random_node) node = random_node return random_walk
          print('\n\nRandom sequence of nodes generated from Random Walk\n\n')while True: first_node = input("Enter name of first node (for example 'space exploration') : ") if len(first_node) > 0: breakpprint.pprint(get_randomwalk(first_node, 10))


          # 從圖中獲取所有節(jié)點的列表all_nodes = list(G.nodes())
          random_walks = []for n in tqdm(all_nodes): for i in range(5): random_walks.append(get_randomwalk(n,10)) # 序列長度len(random_walks)

          # 訓(xùn)練skip-gram (word2vec)模型model = Word2Vec(window = 4, sg = 1, hs = 0, negative = 10, # 負(fù)采樣 alpha=0.03, min_alpha=0.0007, seed = 14)
          model.build_vocab(random_walks, progress_per=2)
          model.train(random_walks, total_examples = model.corpus_count, epochs=20, report_delay=1)print('\n\n Get similar nodes\n\n')while True: any_node = input("Enter name of any node (for example 'space toursim') : ") if len(any_node) > 0: breakpprint.pprint(model.similar_by_word(any_node))
          結(jié)尾
          我真的很喜歡在本文中探索DeepWalk中的圖形數(shù)據(jù),我迫不及待地想嘗試其他圖形算法。在接下來的幾周里,繼續(xù)關(guān)注這個系列吧!
          我鼓勵你實施此代碼,試用它,并建立自己的圖模型。這是學(xué)習(xí)任何概念的最佳方法。完整的代碼在這里:https://github.com/prateekjoshi565/DeepWalk
          下載1:OpenCV-Contrib擴展模塊中文版教程
          在「小白學(xué)視覺」公眾號后臺回復(fù):擴展模塊中文教程即可下載全網(wǎng)第一份OpenCV擴展模塊教程中文版,涵蓋擴展模塊安裝、SFM算法、立體視覺、目標(biāo)跟蹤、生物視覺、超分辨率處理等二十多章內(nèi)容。

          下載2:Python視覺實戰(zhàn)項目52講
          小白學(xué)視覺公眾號后臺回復(fù):Python視覺實戰(zhàn)項目即可下載包括圖像分割、口罩檢測、車道線檢測、車輛計數(shù)、添加眼線、車牌識別、字符識別、情緒檢測、文本內(nèi)容提取、面部識別等31個視覺實戰(zhàn)項目,助力快速學(xué)校計算機視覺。

          下載3:OpenCV實戰(zhàn)項目20講
          小白學(xué)視覺公眾號后臺回復(fù):OpenCV實戰(zhàn)項目20講即可下載含有20個基于OpenCV實現(xiàn)20個實戰(zhàn)項目,實現(xiàn)OpenCV學(xué)習(xí)進階。

          交流群


          歡迎加入公眾號讀者群一起和同行交流,目前有SLAM、三維視覺、傳感器自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學(xué)影像、GAN算法競賽等微信群(以后會逐漸細(xì)分),請掃描下面微信號加群,備注:”昵稱+學(xué)校/公司+研究方向“,例如:”張三 + 上海交大 + 視覺SLAM“。請按照格式備注,否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關(guān)微信群。請勿在群內(nèi)發(fā)送廣告,否則會請出群,謝謝理解~



          瀏覽 27
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          評論
          圖片
          表情
          推薦
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            <del id="afajh"><form id="afajh"></form></del>
                1. <th id="afajh"><progress id="afajh"></progress></th>
                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  黄色一级片 | 日本中文在线 | 操B网站| 考逼免费网站 | 国产成人在线免费观看视频 |