隨機遊走演算法

㈠ 協同過濾演算法

用戶行為數據在網站上最簡單的存在形式就是日誌，比如用戶在電子商務網站中的網頁瀏覽、購買、點擊、評分和評論等活動。 用戶行為在個性化推薦系統中一般分兩種——顯性反饋行為(explicit feedback)和隱性反饋 行為(implicit feedback)。顯性反饋行為包括用戶明確表示對物品喜好的行為。網站中收集顯性反饋的主要方式就是評分和喜歡/不喜歡。隱性反饋行為指的是那些不能明確反應用戶喜好 的行為。最具代表性的隱性反饋行為就是頁面瀏覽行為。 按照反饋的明確性分，用戶行為數據可以分為顯性反饋和隱性反饋，但按照反饋的方向分， 又可以分為正反饋和負反饋。正反饋指用戶的行為傾向於指用戶喜歡該物品，而負反饋指用戶的 行為傾向於指用戶不喜歡該物品。在顯性反饋中，很容易區分一個用戶行為是正反饋還是負反饋， 而在隱性反饋行為中，就相對比較難以確定。

在利用用戶行為數據設計推薦演算法之前，研究人員首先需要對用戶行為數據進行分析，了解 數據中蘊含的一般規律，這樣才能對演算法的設計起到指導作用。

(1) 用戶活躍度和物品流行度

(2) 用戶活躍度和物品流行度的關系

一般認為，新用戶傾向於瀏覽熱門的物品，因為他 們對網站還不熟悉，只能點擊首頁的熱門物品，而老用戶會逐漸開始瀏覽冷門的物品。如果用橫坐標表示用戶活躍度，縱坐標表示具有某個活躍度的所有用戶評過分的物品的平均流行度。圖中曲線呈明顯下 降的趨勢，這表明用戶越活躍，越傾向於瀏覽冷門的物品。

僅僅基於用戶行為數據設計的推薦演算法一般稱為協同過濾演算法。學術界對協同過濾演算法進行了深入研究，提出了很多方法，比如基於鄰域的方法(neighborhood-based)、隱語義模型 (latent factor model)、基於圖的隨機遊走演算法(random walk on graph)等。在這些方法中， 最著名的、在業界得到最廣泛應用的演算法是基於鄰域的方法，而基於鄰域的方法主要包含下面兩種演算法。

基於用戶的協同過濾演算法 ：這種演算法給用戶推薦和他興趣相似的其他用戶喜歡的物品

基於物品的協同過濾演算法： 這種演算法給用戶推薦和他之前喜歡的物品相似的物品

基於鄰域的演算法是推薦系統中最基本的演算法，該演算法不僅在學術界得到了深入研究，而且在 業界得到了廣泛應用。基於鄰域的演算法分為兩大類，一類是基於用戶的協同過濾演算法，另一類是 基於物品的協同過濾演算法。現在我們所說的協同過濾，基本上就就是指基於用戶或者是基於物品的協同過濾演算法，因此，我們可以說基於鄰域的演算法即是我們常說的協同過濾演算法

(1) 基於用戶的協同過濾演算法（UserCF）

基於用戶的協同過濾演算法的基本思想是：在一個在線個性化推薦系統中，當一個用戶A需要個性化推薦 時，可以先找到和他有相似興趣的其他用戶，然後把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。

Ø 從上面的描述中可以看到，基於用戶的協同過濾演算法主要包括兩個步驟。 第一步：找到和目標用戶興趣相似的用戶集合。 第二步： 找到這個集合中的用戶喜歡的，且目標用戶沒有聽說過的物品推薦給目標用戶。

這里，步驟1的關鍵是計算兩個用戶的興趣相似度，協同過濾演算法主要利用行為的相似度計算興趣的相似度。給定用戶u和用戶v，令N(u)表示用戶u曾經有過正反饋的物品集合，令N(v) 為用戶v曾經有過正反饋的物品集合。那麼我們可以通過以下方法計算用戶的相似度：

基於餘弦相似度

(2) 基於物品的協同過濾演算法（itemCF）
與UserCF同理
(3) UserCF和itemCF的比 較

首先我們提出一個問題，為什麼新聞網站一般使用UserCF，而圖書、電商網站一般使用ItemCF呢？ 首先回顧一下UserCF演算法和ItemCF演算法的推薦原理。UserCF給用戶推薦那些和他有共同興 趣愛好的用戶喜歡的物品，而ItemCF給用戶推薦那些和他之前喜歡的物品類似的物品。從這個算 法的原理可以看到，UserCF的推薦結果著重於反映和用戶興趣相似的小群體的熱點，而ItemCF 的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反映了用戶所在的小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反映了用戶自己的興趣傳承。 在新聞網站中，用戶的興趣不是特別細化，絕大多數用戶都喜歡看熱門的新聞。個性化新聞推薦更加強調抓住 新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，而個性化相對於這兩點略顯次要。因 此，UserCF可以給用戶推薦和他有相似愛好的一群其他用戶今天都在看的新聞，這樣在抓住熱 點和時效性的同時，保證了一定程度的個性化。同時，在新聞網站中，物品的更新速度遠遠快於新用戶的加入速度，而且 對於新用戶，完全可以給他推薦最熱門的新聞，因此UserCF顯然是利大於弊。

但是，在圖書、電子商務和電影網站，比如亞馬遜、豆瓣、Netflix中，ItemCF則能極大地發 揮優勢。首先，在這些網站中，用戶的興趣是比較固定和持久的。一個技術人員可能都是在購買 技術方面的書，而且他們對書的熱門程度並不是那麼敏感，事實上越是資深的技術人員，他們看 的書就越可能不熱門。此外，這些系統中的用戶大都不太需要流行度來輔助他們判斷一個物品的 好壞，而是可以通過自己熟悉領域的知識自己判斷物品的質量。因此，這些網站中個性化推薦的 任務是幫助用戶發現和他研究領域相關的物品。因此，ItemCF演算法成為了這些網站的首選演算法。 此外，這些網站的物品更新速度不會特別快，一天一次更新物品相似度矩陣對它們來說不會造成 太大的損失，是可以接受的。同時，從技術上考慮，UserCF需要維護一個用戶相似度的矩陣，而ItemCF需要維護一個物品 相似度矩陣。從存儲的角度說，如果用戶很多，那麼維護用戶興趣相似度矩陣需要很大的空間， 同理，如果物品很多，那麼維護物品相似度矩陣代價較大

下表是對二者的一個全面的表較：

㈡ Graph Embedding之metapath2vec

  Metapath2vec是Yuxiao Dong等於2017年提出的一種用於異構信息網路（Heterogeneous Information Network, HIN）的頂點嵌入方法。 metapath2vec 使用基於meta-path的random walks來構建每個頂點的異構鄰域，然後用 Skip-Gram 模型來完成頂點的嵌入。在 metapath2vec 的基礎上，作者還提出了 metapath2vec++ 來同時實現異構網路中的結構和語義關聯的建模。

  作者首先提到了基於神經網路的學習模型可以捕獲不同類型數據的潛在信息和復雜關系，如圖像，語音和語言等。同樣地，基於神經網路的模型針對復雜網路的表示學習也有非常好的效果。作者提到了當前已經提出的採用了word2vec思想的網路表示演算法，如 Deepwalk ， node2vec 以及 LINE 等。但是作者也明確指出了，上述這些演算法雖然可以用於網路表示學習，但僅適合那些只包含一類頂點類型和邊類型的同構網路（Homogeneous Networks），並不能很好地用於包含多種頂點類型和邊類型的復雜關系網路。於是作者在基於meta-path的基礎上，提出了能很好應對指定scheme結構的異構復雜關系網路的表示學習方法—— metapath2vec 和 metapath2vec++ 。 metapath2vec 的目標是最大化保留一個異構網路的結構和語義信息的似然，首先使用基於meta-path的隨機遊走獲取異構網路中每種不同類型頂點的異構領域，然後使用擴展的Skip-Gram處理前面獲取的頂點領域，最終學習每個不同類型頂點的網路嵌入表示。跟之前的網路嵌入成果相比，作者認為metapath2vec具有以下貢獻：

  異構網路定義為： ，其中每個頂點和邊對應的映射函數為： 和 ，其中 和 分布表示頂點和邊的類型，另外還滿足 。

  異構網路表徵學習定義為：給定一個異構網路 ，學習一個 維的潛在表徵 可以表徵網路中頂點之間的結構信息和語義場景關系。異構網路表徵學習的輸出是一個低維的矩陣 ，其中 行是一個 維的向量，表示頂點 的表徵。這里需要注意的是，雖然頂點的類型不同，但是不同類型的頂點的表徵向量映射到同一個維度空間。由於網路異構性的存在，傳統的基於同構網路的頂點嵌入表徵方法很難有效地直接應用在異構網路上。

  在正式介紹metapath2vec方法之前，作者首先介紹了同構網路上的基於random walk的graph embedding演算法的基本思想，如：Deepwalk和node2vec等。該類方法採用了類似word2vec的思想，即：使用skip-gram模型對每個頂點的局部領域頂點信息進行預測，進而學習到每個頂點的特徵表示。通常，對於一個同構網路 ，目標是從每個頂點的局部領域上最大化網路似然：
其中 表示頂點 的領域，如1-hop以內的鄰接頂點，2-hop以內的鄰接頂點。 表示給定頂點 後，頂點 的條件概率。下面正式給出基於異構網路的metapath2vec嵌入演算法。metapath2vec分為兩個部分，分別是Meta-Path-Based Random Walks和Heterogeneous Skip-Gram。

  在metapath2vec中，作者使用Skip-Gram模型通過在頂點 的領域 上最大化條件概率來學習異構網路 上的頂點表徵。
其中 表示頂點 的類型為 的領域頂點集合。 通常定義為一個softmax函數，即：
其中 是矩陣 的第 行矩陣，表示頂點 的嵌入向量。為了提升參數更新效率，metapath2vec採用了Negative Sampling進行參數迭代更新，給定一個Negative Sampling的大小 ，參數更新過程如下：
其中 ， 是一個negative node 在M次采樣中的預定義分布。
metapath2vec通過不考慮頂點的類型進行節點抽取來確定當前頂點的頻率。

  在同構網路中，DeepWalk和node2vec等演算法通過隨機遊走的方式來構建Skip-Gram模型的上下文語料庫，受此啟發，作者提出了一種異構網路上的隨機遊走方式。在不考慮頂點類型和邊類型的情況下， 表示從頂點 向其鄰居頂點 的轉移概率。然而Sun等已證明異構網路上的隨機遊走會偏向於某些高度可見的類型的頂點，這些頂點的路徑在網路中具有一定的統治地位，而這些有一定比例的路徑指向一小部分節點的集合。鑒於此，作者提出了一種基於meta-path的隨機遊走方式來生成Skip-Gram模型的鄰域上下文。該隨機遊走方式可以同時捕獲不同類型頂點之間語義關系和結構關系，促進了異構網路結構向metapath2vec的Skip-Gram模型的轉換。
  一個meta-path的scheme可以定義成如下形式：
其中
表示頂點 和頂點 之間的路徑組合。例如圖（a）中，「APA」表示一種固定語義的meta-path，「APVPA」表示另外一種固定語義的meta-path。並且很多之前的研究成果都表明，meta-path在很多異構網路數據挖掘中很很大作用。因此，在本文中，作者給出了基於meta-path的隨機遊走方式。給定一個異構網路 和一個meta-path的scheme :
那麼在第 步的轉移概率定義如下：
其中 ， 表示頂點 的 類型的領域頂點集合。換言之， ，也就是說隨機遊走是在預定義的meta-path scheme 條件下的有偏遊走。初次之外，meta-path通常是以一種對稱的方式來使用，也就是說在上述路徑組合中，頂點 的類型和 的類型相同。即：
基於meta-path的隨機遊走保證不同類型頂點之間的語義關系可以適當的融入Skip-Gram模型中。

  metapath2vec在為每個頂點構建領域時，通過meta-path來指導隨機遊走過程向指定類型的頂點進行有偏遊走。但是在softmax環節中，並沒有頂點的類型，而是將所有的頂點認為是同一種類型的頂點。換言之，metapath2vec在Negative Sampling環節采樣的negative 樣本並沒有考慮頂點的類型，也就是說metapath2vec支持任意類型頂點的Negative Sampling。於是作者在metapath2vec的基礎上又提出了改進方案metapath2vec++。

在metapath2vec++中，softmax函數根據不同類型的頂點的上下文 進行歸一化。也就是說 根據固定類型的頂點進行調整。即：
其中 是網路中 類型頂點集合。在這種情況下，metapath2vec++為Skip-Gram模型的輸出層中的每種類型的領域指定了一個多項式分布的集合。而在metapath2vec，DeepWalk和node2vec中，Skip-Gram輸出多項式分布的維度等於整個網路中頂點的數目，然而對於metapath2vec++的Skip-Gram，其針對特定類型的輸出多項式的維度取決於網路中當前類型頂點的數目。如圖（c）所示。最終我們可以得到如下的目標函數：
可以得出其梯度如下：
其中 是一個指示函數，用來指示 在 時是否是頂點 的上下文。該演算法使用隨機梯度下降進行參數優化。整個metapath2vec++演算法如下。

  以上就是metapath的全部內容，該演算法沿用了之前同構網路上基於隨機遊走的Embedding演算法的思想，作者通過在異構網路上，引入預置meta-paths來指導隨機遊走的過程，另外通過meta-path的領域來改進傳統的Skip-Gram模型，使得該嵌入方法不僅能保留網路中的異構信息和語義關系信息，同時針對大規模網路，性能也有了本質上的提升。具體細節可以參考原論文，鏈接如下。

㈢ 隨機遊走圖 穩定分布怎麼 計算

對於同樣的輸入，每次執行同樣的演算法會有不同的輸出」這句話對「隨機演算法」是不一定成立的，事實上它往往是不成立的。許多隨機演算法的隨機性體現在：1、運行時間隨機，但大多數情況下會低於某個值；2、計算結果大多數時候正確，但是有極低概率會給出不正確的結果。 對於random walker演算法，它的前進路線是由勢函數引導的，在圖形邊界，這個勢函數會非常大，所以random walker穿過這個邊界的概率很低。而且，random walker演算法不是要真的執行「走」的這個過程，而是要直接算「從任一點出發，先到達哪個初始點的概率更高」。這種情況下，結果基本是確定的。就好像問「一個腳上綁著10kg重物的人，和一個沒有帶重物的人賽跑，誰獲勝的概率高」？確實前者不是沒有可能獲勝，但是你比較概率大小的話，結果是顯而易見的。

㈣ 隨機遊走演算法是什麼

這個……設置一個1到4的隨機數（假定遊走的空間是二維的），如果隨機數結果為1，就向上走一個單位，如果為2，向左走一個單位，如果為3，向下走一個單位，如果為4，向右走一個單位，每走一個單位，重復一遍上面的過程。

㈤ 辮狀河道的二維隨機遊走模型模擬

王家華

（西安石油學院計算機科學系，西安710065）

張團峰

（西安石油學院基礎科學部，西安710065）

黃滄鈿

（西安石油學院計算機科學系，西安710065）

摘要本文用隨機遊走模型模擬了頻繁連接和分支的辮狀河道的二維分布。作為滲透率、孔隙度和泥質含量三個參數的線性組合，二維網格數據PP（i,j）可用來區分網格節點的類型：河道、泥岩或介於河道與泥岩之間的砂岩。使用了分數維布朗運動來模擬油井中這三個參數的二維分布。首先定義河道中心線，然後再考慮河道邊界。在文末，描述了遼河油田的有100口井的沈－84地區的一個研究實例。

關鍵詞隨機遊走模擬實現辮狀河道

1引言

研究區位於三角洲前扇和三角洲平原之間的子區域，沉積物來自於東北方向，由辮狀河道和介於河道與泥岩之間的砂岩組成。由於三角洲扇沉積時弱的水動力條件，故位於河道和點砂壩之間的砂岩很少，且辮狀河道是研究區域的主骨架。

在儲層中，單獨河道砂體有鞋帶狀和扁豆狀兩種形態。所有的辮狀河道呈東北到西南方向展布。由於河道寬度小，在沉積過程中河道頻繁地發生分支，所以這些辮狀河道常常分路迂迴、相互連接、相互交叉。

儲層的油藏物理參數變化很大。例如，在相同的層，縱向和橫向的滲透率可以相差10～100倍。

2儲層油藏物理參數的條件模擬

由於儲層強烈的非均質性，可以用分數維布朗運動來模擬地球物理參數的分布。即可用二維隨機場｛Z（x）；x∈D）來建立地球物理參數模型，並假設隨機場的增量滿足從一種趨勢移走的高斯過程。在研究中，使用了一次趨勢面。期望值EZ（x）選擇如下：

f^T（x）β＝β₁＋β₂x₁＋β₃x₂

式中：β^T＝（β₁，β₂，β₃）。

考慮濾掉這種趨勢面的隨機過程：

Y（x）=Z（x）-f^T（x）β

式中：Y（x）為EY（x）=0的平穩高斯過程。令D_L為研究區域中的一個大小為（2ⁿ+1）×（2ⁿ+1）的網格系統，N₀=（2ⁿ+1）×（2ⁿ+1）-1,D₀代表位置i從D_L移出之後D_L的剩餘部分。於是，此條件概率的分布就是高斯型的：

數學地質和地質信息

式中：

；γ是模型的變異函數，γ_i是一個大小為1×（N₀+1）的向量，其第j個分量為－γ_｜i-j｜，當j∈D₀時，向量的第（N₀+1）個分量為1；

是一個大小為（N₀+1）×（N₀+1）的矩陣，其元素為－γ_｜k-l｜,k,l∈D₀，除了（N₀+1）×（N₀+1）位置處的元素為0外，最後一行和最後一列元素為1；Z^＊是一個大小為1×（N₀+1）的向量，其分量為Z_j；j∈D₀，最後分量值為0。

滲透率、孔隙度和泥質含量的實現可通過序貫窗口層次演算法獲得，並可用它來作模擬辮狀河道的輸入。實際過程如下。

3辮狀河道的條件模擬

根據研究區域的儲層特徵，用前面的三個地球物理參數來確定辮狀河道的位置。當深度增加時，由於地球物理參數會變小，於是，為了確定河道，就應用深度來校準這些值。

令Per、Por、Sh和H分別代表滲透率、孔隙度、泥質含量和層深。可以用一個區分值PP來確定一個二維點是否屬於一個河道：

數學地質和地質信息

式中：α₁、α₂、a₃是由地質經驗確定的非原始系數，且依賴於深度H。若PP≥Q，則此位置屬於一個河道；若PP＜Q，則此位置屬於介於河道和泥岩之間的砂岩；若Per=0，則此位置屬於泥岩。在這里，值Q是一個由地質經驗確定的值，且也依賴於深度H。

基於公式（1），可以利用Por,Per,Sh的網格數據得到網格數據｛PP（i,j）；j=1，…，N_y；i=1，…，N_x）。N_x是x方向的網格節點數，N_y是y方向的網格節點數。PP值可作為模擬河道位置的輸入，當要確定河道寬度時會再一次考慮它。

下面討論模擬辮狀河道位置的過程。第一，模擬每一河道的中心線；第二，通過加寬河道中心線來得到河道的邊界。此過程可保證被模擬的河道以1的概率穿過所觀察的井中河道。河道的連接和分支遵循地質經驗。

3.1辮狀河道位置的模擬

核心技術是辮狀河道位置的模擬。首先，在研究區域里搜索每一河道的出發點，然後用隨機遊走模型來找出河道中心線。其結果是一系列的網格節點，在這些節點中，開始點就是第一節點。

在這里要考慮的主要因素有：①井的位置；②由井中數據（河道、泥岩及介於河道與泥岩之間的砂岩）所表示的相分布；③PP值。以這些為基礎，可以確定所有可能的河道，同時也考慮了辮狀河道的連接與分支。

首先，把在每一井中的有關的相信息分配到距井位置最近的一個網格節點。一個整數KG（i,j）可能會有下面幾個可能的值：

數學地質和地質信息

3.2河道開始位置

令D_L是一個在研究區域的網格系統（圖1），Δx和Δy包含若干個網格間距（在這里是5個），是兩個窄帶的相應寬度。從（i,j）開始，在沿著東西方向的一個窄帶中，i從1到N_x，j從Ⅳ_j到N_y搜索。假如在KG（i₁,j₁）等於3的網格節點發現了第一個位置（i₁,j₁），並且在KG（i₂,j₂）等於2或1的網格節點獲得下一位置（i₂,j₂），那麼就可以認為i₁是第一個河道開始點的x坐標。

同理，從（i,j）點開始，在沿著南北方向的另一個窄帶中，i從N，到N_x,j從1到N_y搜索。假如在KG（i₃,j₃）等於3處找到了第一個位置（i₃,j₃），這樣就能夠把j₃-N_j標記為一個河道開始位置的y坐標。

圖1尋找河道初始位置

圖2網格節點的轉移

在研究區域內，全部可能河道的開始點可以根據前面的過程依次找到。

可以用二維隨機遊走模型來確定一個網格節點是否向a、b和c中的一個方向轉移（見圖2）。

3.3第一個河道的流動和分叉位置的條件模擬

設當前位置為Q（i,j），下一點的確定就依賴於a、b、c三方向之一。

（1）方向a

沿著方向a從位置Q（i,j）出發找到最近的觀察位置（i_a,j），在這里，i_a表示相應的最近的位置。令Λ表示「找到一個位置（i,j+1），它滿足KG（i,j+1）=3」。假如P〔Q（i,j）→Q（i+1,j）代表轉移概率，則有

數學地質和地質信息

式中：DA=｜i_a-i｜×d_x

；D_x＝（N_x-1）×d_x；d_x表示x方向上兩個相鄰網格節點間的距離；maxPP是網格系統中PP值的最大值；α₁、α₂、α₃、α₄是由地質經驗來確定的非負值，且0＜α_i＜1,i=1,2,3,4。

假如沿著方向a找到了下一點，就令KG（i+1,j）＝3，否則就考慮方向b。

（2）方向b

方向b是向左下方的，遷移概率為P〔Q（i,j）→Q（i+1,j+1）〕：

數學地質和地質信息

式中：

；d_x表示在x方向上兩個相鄰網格節點間的距離。D_y-（N_y－1）×d_y；d_y表示在y方向上兩個相鄰網格節點間的距離。β₁，β₂，β₃，β₄是由地質經驗來確定的非負值，且0＜β_i＜1,i=1,2,3,4。

假如一個河道的實現正向方向b轉移，也就是Q（i,j）→Q（i+1,j+1），則令KG（i+1，j+1）=3，否則就考慮方向c。

（3）方向c

如果轉移方向既不是a也不是b，那一定是c，其通路就是從Q（i,j）到Q（i,j+1），同時，令KG（i,j+1）=3。

重復執行前面的過程直至KG（i,j）＝一1，這樣就模擬出了第一個河道的位置。

3.4所有其他可能河道的模擬

為了模擬其他河道的位置，KG（i,j）的值就要作如下改變：

數學地質和地質信息

在下面幾部分將會考慮河道的連接和分支。

（1）方向a

令位置Q（i,j）向方向a轉移，直到找到第一個河道的位置是（ia,j）為止，並且A＝「從位置（i,j+1）向方向a找到一個位置（i,j+1），它滿足KG（i,j+1）=3，並且i″滿足i＜i″＜i′，KG（i″,j+1）＝1或KG（i″,j+1）=2″。P〔Q（i,j）→Q（i+1,j）表示轉移概率，這樣就有

P〔Q（i,j）→Q（i+1,j）〕＝

數學地質和地質信息

式中：D_A=|i_a一i|×d_x,D_x與d_x和前面一樣有相同含義；maxPP是網格系統中PP值的最大值；γ₁，γ₂，γ₃，γ₄，γ₅，γ。是由地質經驗來確定的非負值，且

0＜γ_i＜1,i=1,2,3,4,5,6；

γ₁＋γ₂≤1，γ₃＋γ₄≤1，γ₅＋γ₆≤1；

γ₁≥γ₃≥γ₅，γ₂≥γ₄≥γ₆。

顯然，假如最近的搜索位置屬於一個河道，則最近搜索距離就越小，轉移概率就越大。因此，河道將以更大的概率相互連接。條件γ₁≥γ₃≥γ₅及γ₂≥γ₄≥γ₆可以表示這樣的特徵：在河道間觀測到泥岩，則河道的分支機會就會增加。

假如河道軌跡是從Q（i,j）到Q（i+1,j），當位置Q（i+1,j）不是河道位置時就令KG（i+1,j）等於4，否則就令KG（i+1,j）等於5。如果河道軌跡不是從Q（i,j）到Q（i+1,j），就要考慮方向b。

（2）方向b

令位置Q（i,j）向左下方向轉移直到找到標記為（i_a,j_b）的第一個位置。如果KG（i+1,j）＝1或＝2，並且Q（i,j）沒有轉移到Q（i+1,j+1），這樣從Q（i,j）到Q（i+1,j+1）的轉移概率就是

數學地質和地質信息

式中：

；D_x,D_y,d_x及d_y的含義同前面；δ₁，δ₂，δ₃，δ₄，δ₅，δ₆是由地質經驗確定的非負參數，且

0＜δ_i＜1,i=1,2,3,4,5,6；

δ₁＋δ₂≤1，δ₃＋δ₄≤1；δ₅＋δ₆≤1；

δ₁≥δ₃≥δ₅，δ₂≥δ₄≥δ₆。

因為河道軌跡是從東北到西南方向伸展的，參數δ_i及γ_i必須滿足下面的關系：

δ_i＞γ_i,i=1,2,3,4,5,6

如果河道軌跡是向著方向b的，也就是Q（i,j）→Q（i+1,j+1），那麼就令

數學地質和地質信息

否則，就要考慮方向c。

（3）方向c

假如河道軌跡既不沿方向a也不沿方向b，那一定是沿方向c，也就是Q（i,j）→Q（i,j+1）。同時，必須用（2）式來修改KG（i,j+1）的值。

為了找到更多的分支河道，就重復執行前面的過程直到KG（i,j）=-1，此過程的循環參數依賴於研究區域的實際地質特徵。總體看來，搜索到的分支河道數越多，河道的連接與分支就越頻繁。在研究中，每一河道僅搜索一個分支河道。

3.5其他河道及其分支河道的模擬

可以用同樣的方法來找到其他河道及其分支河道。

4河道邊界的確定

每一河道的寬度依賴於PP值。PP值越大，河道就越寬。

4.1參數

假如河道軌跡是M→N→L，就應移去位置N。顯然這種處理可以簡化加寬河道這一過程，但它不會改變每一河道的軌跡（圖3）。

圖3加寬河道前的預處理

4.2河道邊界的確定

河道寬度公式如下：

寬度＝Δ₁+PP（i,j）×Δ₂/maxPP

式中：Δ₁是研究區域中河道寬度最小值；Δ₂是河道寬度最大值；PP（i,j）是與河道相鄰位置的最近的網格節點的PP值（圖4）。

5案例研究

本案例研究區域為中國遼河油田的沈－84。

圖4加寬河道

在這一區域，使用了100口井的數據，包括如滲透率、孔隙度和泥質含量這樣的油藏物理參數信息，以及如河道、泥岩和介於河道與泥岩之間的砂岩這樣的相信息。通過分數維布朗運動模型得到了三個地球物理參數的實現。

以這些地球物理參數的模擬為基礎，通過隨機遊走模型可以產生相的實現（圖5）。

圖5辮狀河道模擬的一個實現

該模型的參數通過如下方法來選擇：

N_x=N_y=65；D_x=50m,D_y=30m；

α₁=0.2，α₂=0.3，α₃=0.1，α₄=0.2；

β₁=0.3，β₂=0.4，β₃=0.2，β₄=0.3；

γ₁=0.2，γ₂=0.3，γ₃=0.1，γ₄=0.2，γ₅=0.1，γ₆=0.2；

δ₁=0.3，δ₂=0.5，δ₃=0.3，δ₄=0.4，δ₅=0.2，δ₆=0.3，Δ₁=70m，Δ₂=50m。

6結論

在三角洲沉積環境中，由辮狀河道控制的儲層具有極大的非均質性，這是因為河道的寬度較窄且有頻繁的連接與分支。描述辮狀河道的二維分布是十分重要的。

在本文中，隨機遊走作為一種二維隨機模擬方法，可用來描述辮狀河道的分布。這些實現產生了一些重要的辮狀河道的特徵：頻繁發生的河道連接與分支。同時，在模型中也考慮了河道的寬度，並且保留了河道連續性和平滑性。

致謝特別感謝遼河石油管理局地質科學院的鄭容植和李煥鵬兩位高級工程師的技術支持。

參考文獻

[1]H.H.Haldorsen.A new approach to shale management in field scale simulation models.SPE（10976）,1984,447～457.

[2]G.Matheron,H.Beucher,C.de Fouqqet,A.Galli,D.Guerillout and C.Ravenne.Conditional simulation of the geometry of fluriodeltaic reservoirs.SPE 62nd Annual Conference Dallas,Texas,1987,591～599.

[3]Olivier Dubrule.A review of stochastic models for petroleum reservoirs.GEOSTATISTICS,1989,2:493～506.

㈥ 隨機遊走演算法怎麼體現隨機

隨機遊走這一名稱由Karl Pearson在1905年提出[Pearson, K. (1905). The problem of the Random Walk. Nature. 72, 294.]。
本來是基於物理中」布朗運動」相關的微觀粒子的運動形成的一個模型，後來這一模型作為數理金融中的重要的假設，指的是證券價格的時間序列將呈現隨機狀態，不會表現出某種可觀測或統計的確定趨勢，即證券價格的變動是不可預測的。

㈦ 股票價格的隨機遊走的含義

「隨機遊走」（random walk）是指基於過去的表現，無法預測將來的發展步驟和方向。應用到股市上，則意味著股票價格的短期走勢不可預知，意味著投資咨詢服務、收益預測和復雜的圖表模型全無用處。在華爾街上，「隨機遊走」這個名詞是個諱語，是學術界杜撰的一個粗詞，是對專業預言者的一種侮辱攻擊。若將這一術語的邏輯內涵推向極致，便意味著一隻戴上眼罩的猴子，隨意向報紙的金融版面擲一些飛鏢，選出的投資組合就可與投資專家精心挑選出的一樣出色。

㈧ 基於社區發現演算法和圖分析Neo4j解讀《權力的游戲》下篇

其中的分析和可視化是用Gephi做的，Gephi是非常流行的圖分析工具。但作者覺得使用Neo4j來實現更有趣。

節點中心度
節點中心度給出網路中節點的重要性的相對度量。有許多不同的方式來度量中心度，每種方式都代表不同類型的「重要性」。

度中心性(Degree Centrality)
度中心性是最簡單度量，即為某個節點在網路中的聯結數。在《權力的游戲》的圖中，某個角色的度中心性是指該角色接觸的其他角色數。作者使用Cypher計算度中心性：
MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

character
degree

Tyrion
36

Jon
26

Sansa
26

Robb
25

Jaime
24

Tywin
22

Cersei
20

Arya
19

Joffrey
18

Robert
18

從上面可以發現，在《權力的游戲》網路中提利昂·蘭尼斯特（Tyrion）和最多的角色有接觸。鑒於他的心計，我們覺得這是有道理的。

加權度中心性（Weighted Degree Centrality）
作者存儲一對角色接觸的次數作為 INTERACTS 關系的 weight 屬性。對該角色的 INTERACTS 關系的所有 weight 相加得到加權度中心性。作者使用Cypher計算所有角色的這個度量：
MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

character
weightedDegree

Tyrion
551

Jon
442

Sansa
383

Jaime
372

Bran
344

Robb
342

Samwell
282

Arya
269

Joffrey
255

Daenerys
232

介數中心性（Betweenness Centrality）
介數中心性：在網路中，一個節點的介數中心性是指其它兩個節點的所有最短路徑都經過這個節點，則這些所有最短路徑數即為此節點的介數中心性。介數中心性是一種重要的度量，因為它可以鑒別出網路中的「信息中間人」或者網路聚類後的聯結點。

圖6中紅色節點是具有高的介數中心性，網路聚類的聯結點。
為了計算介數中心性，作者使用Neo4j 3.x或者apoc庫。安裝apoc後能用Cypher調用其170+的程序：
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Jon
1279.7533534055322

Robert
1165.6025171231624

Tyrion
1101.3849724234349

Daenerys
874.8372110508583

Robb
706.5572832464792

Sansa
705.1985623519137

Stannis
571.5247305125714

Jaime
556.1852522889822

Arya
443.01358430043337

Tywin
364.7212195528086

緊度中心性（Closeness centrality）
緊度中心性是指到網路中所有其他角色的平均距離的倒數。在圖中，具有高緊度中心性的節點在聚類社區之間被高度聯結，但在社區之外不一定是高度聯結的。

圖7 ：網路中具有高緊度中心性的節點被其它節點高度聯結
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Tyrion
0.004830917874396135

Sansa
0.004807692307692308

Robert
0.0047169811320754715

Robb
0.004608294930875576

Arya
0.0045871559633027525

Jaime
0.004524886877828055

Stannis
0.004524886877828055

Jon
0.004524886877828055

Tywin
0.004424778761061947

Eddard
0.004347826086956522

使用python-igraph
Neo4j與其它工具（比如，R和Python數據科學工具）完美結合。我們繼續使用apoc運行 PageRank和社區發現（community detection）演算法。這里接著使用python-igraph計算分析。Python-igraph移植自R的igraph圖形分析庫。 使用 pip install python-igraph 安裝它。

從Neo4j構建一個igraph實例
為了在《權力的游戲》的數據的圖分析中使用igraph，首先需要從Neo4j拉取數據，用Python建立igraph實例。作者使用 Neo4j 的Python驅動庫py2neo。我們能直接傳入Py2neo查詢結果對象到igraph的 TupleList 構造器，創建igraph實例：
from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)

現在有了igraph對象，可以運行igraph實現的各種圖演算法來。

PageRank
作者使用igraph運行的第一個演算法是PageRank。PageRank演算法源自Google的網頁排名。它是一種特徵向量中心性(eigenvector centrality)演算法。
在igraph實例中運行PageRank演算法，然後把結果寫回Neo4j，在角色節點創建一個pagerank屬性存儲igraph計算的值：
pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)

現在可以在Neo4j的圖中查詢最高PageRank值的節點：
MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

name
pagerank

Tyrion
0.042884981999963316

Jon
0.03582869669163558

Robb
0.03017114665594764

Sansa
0.030009716660108578

Daenerys
0.02881425425830273

Jaime
0.028727587587471206

Tywin
0.02570016262642541

Robert
0.022292016521362864

Cersei
0.022287327589773507

Arya
0.022050209663844467

社區發現（Community detection）

圖8
社區發現演算法用來找出圖中的社區聚類。作者使用igraph實現的隨機遊走演算法（ walktrap）來找到在社區中頻繁有接觸的角色社區，在社區之外角色不怎麼接觸。
在igraph中運行隨機遊走的社區發現演算法，然後把社區發現的結果導入Neo4j，其中每個角色所屬的社區用一個整數來表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)

我們能在Neo4j中查詢有多少個社區以及每個社區的成員數：
MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC

cluster
members

0
[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]

1
[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]

2
[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]

3
[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]

4
[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]

5
[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]

6
[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]

7
[Lancel]

角色「大合影」
《權力的游戲》的權力圖。節點的大小正比於介數中心性，顏色表示社區（由隨機遊走演算法獲得），邊的厚度正比於兩節點接觸的次數。現在已經計算好這些圖的分析數據，讓我們對其進行可視化，讓數據看起來更有意義。
Neo4j自帶瀏覽器可以對Cypher查詢的結果進行很好的可視化，但如果我們想把可視化好的圖嵌入到其它應用中，可以使用Javascript可視化庫Vis.js。從Neo4j拉取數據，用Vis.js的neovis.js構建可視化圖。Neovis.js提供簡單的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }; var viz = new NeoVis(config); viz.render;

其中：
節點帶有標簽Character，屬性name；

節點的大小正比於betweenness屬性；

可視化中包括INTERACTS關系；

關系的厚度正比於weight屬性；

節點的顏色是根據網路中社區community屬性決定；

從本地伺服器localhost拉取Neo4j的數據；

在一個id為viz的DOM元素中展示可視化。

㈨ 推薦演算法簡介

寫在最前面：本文內容主要來自於書籍《推薦系統實踐》和《推薦系統與深度學習》。

推薦系統是目前互聯網世界最常見的智能產品形式。從電子商務、音樂視頻網站，到作為互聯網經濟支柱的在線廣告和新穎的在線應用推薦，到處都有推薦系統的身影。推薦演算法是推薦系統的核心，其本質是通過一定的方式將用戶和物品聯系起來，而不同的推薦系統利用了不同的方式。

推薦系統的主要功能是以個性化的方式幫助用戶從極大的搜索空間中快速找到感興趣的對象。因此，目前所用的推薦系統多為個性化推薦系統。個性化推薦的成功應用需要兩個條件：

在推薦系統的眾多演算法中，基於協同的推薦和基於內容的推薦在實踐中得到了最廣泛的應用。本文也將從這兩種演算法開始，結合時間、地點上下文環境以及社交環境，對常見的推薦演算法做一個簡單的介紹。

基於內容的演算法的本質是對物品內容進行分析，從中提取特徵，然後基於用戶對何種特徵感興趣來推薦含有用戶感興趣特徵的物品。因此，基於內容的推薦演算法有兩個最基本的要求：

下面我們以一個簡單的電影推薦來介紹基於內容的推薦演算法。

現在有兩個用戶A、B和他們看過的電影以及打分情況如下：

其中問好（?）表示用戶未看過。用戶A對《銀河護衛隊 》《變形金剛》《星際迷航》三部科幻電影都有評分，平均分為 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；對《三生三世》《美人魚》《北京遇上西雅圖》三部愛情電影評分平均分為 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。現在需要給A推薦電影，很明顯A更傾向於科幻電影，因此推薦系統會給A推薦獨立日。而對於用戶B，通過簡單的計算我們可以知道更喜歡愛情電影，因此給其推薦《三生三世》。當然，在實際推薦系統中，預測打分比這更加復雜些，但是其原理是一樣的。

現在，我們可以將基於內容的推薦歸納為以下四個步驟：

通過上面四步就能快速構建一個簡單的推薦系統。基於內容的推薦系統通常簡單有效，可解釋性好，沒有物品冷啟動問題。但他也有兩個明顯的缺點：

最後，順便提一下特徵提取方法：對於某些特徵較為明確的物品，一般可以直接對其打標簽，如電影類別。而對於文本類別的特徵，則主要是其主題情感等，則些可以通過tf-idf或LDA等方法得到。

基於協同的演算法在很多地方也叫基於鄰域的演算法，主要可分為兩種：基於用戶的協同演算法和基於物品的協同演算法。

啤酒和尿布的故事在數據挖掘領域十分有名，該故事講述了美國沃爾瑪超市統計發現啤酒和尿布一起被購買的次數非常多，因此將啤酒和尿布擺在了一起，最後啤酒和尿布的銷量雙雙增加了。這便是一個典型的物品協同過濾的例子。

基於物品的協同過濾指基於物品的行為相似度（如啤酒尿布被同時購買）來進行物品推薦。該演算法認為，物品A和物品B具有很大相似度是因為喜歡物品A的用戶大都也喜歡物品B。

基於物品的協同過濾演算法主要分為兩步：

基於物品的協同過濾演算法中計算物品相似度的方法有以下幾種：
（1）基於共同喜歡物品的用戶列表計算。

此外，John S. Breese再其論文中還提及了IUF（Inverse User Frequence，逆用戶活躍度）的參數，其認為活躍用戶對物品相似度的貢獻應該小於不活躍的用戶，應該增加IUF參數來修正物品相似度的公式：

上面的公式只是對活躍用戶做了一種軟性的懲罰， 但對於很多過於活躍的用戶， 比如某位買了當當網80%圖書的用戶， 為了避免相似度矩陣過於稠密， 我們在實際計算中一般直接忽略他的興趣列表， 而不將其納入到相似度計算的數據集中。

（2）基於餘弦相似度計算。

（3）熱門物品的懲罰。
從上面（1）的相似度計算公式中，我們可以發現當物品 i 被更多人購買時，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都會增長。對於熱門物品，分子 N(i) ∩ N(j) 的增長速度往往高於 N(i)，這就會使得物品 i 和很多其他的物品相似度都偏高，這就是 ItemCF 中的物品熱門問題。推薦結果過於熱門，會使得個性化感知下降。以歌曲相似度為例，大部分用戶都會收藏《小蘋果》這些熱門歌曲，從而導致《小蘋果》出現在很多的相似歌曲中。為了解決這個問題，我們對於物品 i 進行懲罰，例如下式， 當α∈(0, 0.5) 時，N(i) 越小，懲罰得越厲害，從而使熱門物品相關性分數下降（ 博主註：這部分未充分理解 ）：

此外，Kary pis在研究中發現如果將ItemCF的相似度矩陣按最大值歸一化， 可以提高推薦的准確率。 其研究表明， 如果已經得到了物品相似度矩陣w， 那麼可以用如下公式得到歸一化之後的相似度矩陣w'：

歸一化的好處不僅僅在於增加推薦的准確度，它還可以提高推薦的覆蓋率和多樣性。一般來說，物品總是屬於很多不同的類，每一類中的物品聯系比較緊密。假設物品分為兩類——A和B， A類物品之間的相似度為0.5， B類物品之間的相似度為0.6， 而A類物品和B類物品之間的相似度是0.2。 在這種情況下， 如果一個用戶喜歡了5個A類物品和5個B類物品， 用ItemCF給他進行推薦， 推薦的就都是B類物品， 因為B類物品之間的相似度大。 但如果歸一化之後， A類物品之間的相似度變成了1， B類物品之間的相似度也是1， 那麼這種情況下， 用戶如果喜歡5個A類物品和5個B類物品， 那麼他的推薦列表中A類物品和B類物品的數目也應該是大致相等的。 從這個例子可以看出， 相似度的歸一化可以提高推薦的多樣性。

那麼，對於兩個不同的類，什麼樣的類其類內物品之間的相似度高，什麼樣的類其類內物品相似度低呢？一般來說，熱門的類其類內物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類裡面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆蓋率。

最後，利用物品相似度矩陣和用戶打過分的物品記錄就可以對一個用戶進行推薦評分：

基於用戶的協同演算法與基於物品的協同演算法原理類似，只不過基於物品的協同是用戶U購買了A物品，會計算經常有哪些物品與A一起購買（也即相似度），然後推薦給用戶U這些與A相似的物品。而基於用戶的協同則是先計算用戶的相似性（通過計算這些用戶購買過的相同的物品），然後將這些相似用戶購買過的物品推薦給用戶U。

基於用戶的協同過濾演算法主要包括兩個步驟：

步驟（1）的關鍵是計算用戶的興趣相似度，主要是利用用戶的行為相似度計算用戶相似度。給定用戶 u 和 v，N(u) 表示用戶u曾經有過正反饋（譬如購買）的物品集合，N(v) 表示用戶 v 曾經有過正反饋的物品集合。那麼我們可以通過如下的 Jaccard 公式簡單的計算 u 和 v 的相似度：

或通過餘弦相似度：

得到用戶之間的相似度之後，UserCF演算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下的公式度量了UserCF演算法中用戶 u 對物品 i 的感興趣程度：

首先回顧一下UserCF演算法和ItemCF演算法的推薦原理：UserCF給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品， 而ItemCF給用戶推薦那些和他之前喜歡的物品具有類似行為的物品。

（1）從推薦場景考慮
首先從場景來看，如果用戶數量遠遠超過物品數量，如購物網站淘寶，那麼可以考慮ItemCF，因為維護一個非常大的用戶關系網是不容易的。其次，物品數據一般較為穩定，因此物品相似度矩陣不必頻繁更新，維護代價較小。

UserCF的推薦結果著重於反應和用戶興趣相似的小群體的熱點，而ItemCF的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反應了用戶所在小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反應了用戶自己的個性傳承。因此UserCF更適合新聞、微博或微內容的推薦，而且新聞內容更新頻率非常高，想要維護這樣一個非常大而且更新頻繁的表無疑是非常難的。

在新聞類網站中，用戶的興趣愛好往往比較粗粒度，很少會有用戶說只看某個話題的新聞，而且往往某個話題也不是每天都會有新聞。 個性化新聞推薦更強調新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，個性化是補充，所以 UserCF 給用戶推薦和他有相同興趣愛好的人關注的新聞，這樣在保證了熱點和時效性的同時，兼顧了個性化。

（2）從系統多樣性（也稱覆蓋率，指一個推薦系統能否給用戶提供多種選擇）方面來看，ItemCF的多樣性要遠遠好於UserCF，因為UserCF更傾向於推薦熱門物品。而ItemCF具有較好的新穎性，能夠發現長尾物品。所以大多數情況下，ItemCF在精度上較小於UserCF，但其在覆蓋率和新穎性上面卻比UserCF要好很多。

在介紹本節基於矩陣分解的隱語義模型之前，讓我們先來回顧一下傳統的矩陣分解方法SVD在推薦系統的應用吧。

基於SVD矩陣分解在推薦中的應用可分為如下幾步：

SVD在計算前會先把評分矩陣 A 缺失值補全，補全之後稀疏矩陣 A 表示成稠密矩陣，然後將分解成 A' = U∑V T 。但是這種方法有兩個缺點：（1）補成稠密矩陣後需要耗費巨大的儲存空間，對這樣巨大的稠密矩陣進行儲存是不現實的；（2）SVD的計算復雜度很高，對這樣大的稠密矩陣中進行計算式不現實的。因此，隱語義模型就被發明了出來。

更詳細的SVD在推薦系統的應用可參考 奇異值分解SVD簡介及其在推薦系統中的簡單應用 。

隱語義模型（Latent Factor Model）最早在文本挖掘領域被提出，用於找到文本的隱含語義。相關的演算法有LSI，pLSA，LDA和Topic Model。本節將對隱語義模型在Top-N推薦中的應用進行詳細介紹，並通過實際的數據評測該模型。

隱語義模型的核心思想是通過隱含特徵聯系用戶興趣和物品。讓我們通過一個例子來理解一下這個模型。

現有兩個用戶，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書，而用戶B的興趣比較集中在數學和機器學習方面。那麼如何給A和B推薦圖書呢？

我們可以對書和物品的興趣進行分類。對於某個用戶，首先得到他的興趣分類，然後從分類中挑選他可能喜歡的物品。簡言之，這個基於興趣分類的方法大概需要解決3個問題：

對於第一個問題的簡單解決方案是找相關專業人員給物品分類。以圖書為例，每本書出版時，編輯都會給出一個分類。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：（1）編輯的意見不能代表各種用戶的意見；（2）編輯很難控制分類的細粒度；（3）編輯很難給一個物品多個分類；（4）編輯很難給一個物品多個分類；（5）編輯很難給出多個維度的分類；（6）編輯很難決定一個物品在某一個類別中的權重。

為了解決上述問題，研究員提出可以從數據出發，自動找到那些分類，然後進行個性化推薦。隱語義模型由於採用基於用戶行為統計的自動聚類，較好地解決了上面提出的5個問題。

LFM將矩陣分解成2個而不是3個：

推薦系統中用戶和物品的交互數據分為顯性反饋和隱性反饋數據。隱式模型中多了一個置信參數，具體涉及到ALS（交替最小二乘法，Alternating Least Squares）中對於隱式反饋模型的處理方式——有的文章稱為「加權的正則化矩陣分解」：

一個小細節：在隱性反饋數據集中，只有正樣本（正反饋）沒有負反饋（負樣本），因此如何給用戶生成負樣本來進行訓練是一個重要的問題。Rong Pan在其文章中對此進行了探討，對比了如下幾種方法：

用戶行為很容易用二分圖表示，因此很多圖演算法都可以應用到推薦系統中。基於圖的模型（graph-based model）是推薦系統中的重要內容。很多研究人員把基於領域的模型也稱為基於圖的模型，因為可以把基於領域的模型看作基於圖的模型的簡單形式。

在研究基於圖的模型之前，需要將用戶行為數據表示成圖的形式。本節的數據是由一系列用戶物品二元組 (u, i) 組成的，其中 u 表示用戶對物品 i 產生過行為。

令 G(V, E) 表示用戶物品二分圖，其中 V=V U UV I 由用戶頂點 V U 和物品節點 V I 組成。對於數據集中每一個二元組 (u, i) ，圖中都有一套對應的邊 e(v u , v i )，其中 v u ∈V U 是用戶對應的頂點，v i ∈V I 是物品i對應的頂點。如下圖是一個簡單的物品二分圖，其中圓形節點代表用戶，方形節點代表物品，用戶物品的直接連線代表用戶對物品產生過行為。比如下圖中的用戶A對物品a、b、d產生過行為。

度量圖中兩個頂點之間相關性的方法很多，但一般來說圖中頂點的相關性主要取決於下面3個因素：

而相關性高的一對頂點一般具有如下特徵：

舉個例子，如下圖，用戶A和物品c、e沒有邊直連，但A可通過一條長度為3的路徑到達c，而Ae之間有兩條長度為3的路徑。那麼A和e的相關性要高於頂點A和c，因而物品e在用戶A的推薦列表中應該排在物品c之前，因為Ae之間有兩條路徑。其中，（A,b,C,e）路徑經過的頂點的出度為（3，2，2，2），而 (A,d,D,e) 路徑經過了一個出度比較大的頂點D，所以 (A,d,D,e) 對頂點A與e之間相關性的貢獻要小於（A,b,C,e）。

基於上面3個主要因素，研究人員設計了很多計算圖中頂點相關性的方法，本節將介紹一種基於隨機遊走的PersonalRank演算法。

假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 v u 開始在用戶物品二分圖上進行隨機遊走。遊走到任一節點時，首先按照概率α決定是繼續遊走還是停止這次遊走並從 v u 節點重新開始遊走。若決定繼續遊走，則從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為遊走下次經過的節點。這樣，經過很多次隨機遊走後，每個物品被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。

上述演算法可以表示成下面的公式：

雖然通過隨機遊走可以很好地在理論上解釋PersonalRank演算法，但是該演算法在時間復雜度上有明顯的缺點。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代，知道所有頂點的PR值都收斂。這一過程的時間復雜度非常高，不僅無法在線進行實時推薦，離線計算也是非常耗時的。

有兩種方法可以解決上面PersonalRank時間復雜度高的問題：
（1）減少迭代次數，在收斂之前停止迭代。但是這樣會影響最終的精度。

（2）從矩陣論出發，重新涉及演算法。另M為用戶物品二分圖的轉移概率矩陣，即：

網路社交是當今社會非常重要甚至可以說是必不可少的社交方式，用戶在互聯網上的時間有相當大的一部分都用在了社交網路上。

當前國外最著名的社交網站是Facebook和Twitter，國內的代表則是微信/QQ和微博。這些社交網站可以分為兩類：

需要指出的是，任何一個社交網站都不是單純的社交圖譜或興趣圖譜。如QQ上有些興趣愛好群可以認識不同的陌生人，而微博中的好友也可以是現實中認識的。

社交網路定義了用戶之間的聯系，因此可以用圖定義社交網路。我們用圖 G(V,E,w) 定義一個社交網路，其中V是頂點集合，每個頂點代表一個用戶，E是邊集合，如果用戶va和vb有社交網路關系，那麼就有一條邊 e(v a , v b ) 連接這兩個用戶，而 w(v a , v b )定義了邊的權重。一般來說，有三種不同的社交網路數據：

和一般購物網站中的用戶活躍度分布和物品流行度分布類似，社交網路中用戶的入度（in degree，表示有多少人關注）和出度（out degree，表示關注多少人）的分布也是滿足長尾分布的。即大部分人關注的人都很少，被關注很多的人也很少。

給定一個社交網路和一份用戶行為數據集。其中社交網路定義了用戶之間的好友關系，而用戶行為數據集定義了不同用戶的歷史行為和興趣數據。那麼最簡單的演算法就是給用戶推薦好友喜歡的物品集合。即用戶u對物品i的興趣 p ui 可以通過如下公式計算。

用戶u和用戶v的熟悉程度描述了用戶u和用戶在現實社會中的熟悉程度。一般來說，用戶更加相信自己熟悉的好友的推薦，因此我們需要考慮用戶之間的熟悉度。下面介紹3中衡量用戶熟悉程度的方法。

（1）對於用戶u和用戶v，可以使用共同好友比例來計算他們的相似度：

上式中 out(u) 可以理解為用戶u關注的用戶合集，因此 out(u) ∩ out(v) 定義了用戶u、v共同關注的用戶集合。

（2）使用被關注的用戶數量來計算用戶之間的相似度，只要將公式中的 out(u) 修改為 in(u)：

in(u) 是指關注用戶u的集合。在無向社交網路中，in(u)和out(u)是相同的，而在微博這種有向社交網路中，這兩個集合的含義就不痛了。一般來說，本方法適合用來計算微博大V之間的相似度，因為大v往往被關注的人數比較多；而方法（1）適用於計算普通用戶之間的相似度，因為普通用戶往往關注行為比較豐富。

（3）除此之外，還可以定義第三種有向的相似度：這個相似度的含義是用戶u關注的用戶中，有多大比例也關注了用戶v：

這個相似度有一個缺點，就是在該相似度下所有人都和大v有很大的相似度，這是因為公式中的分母並沒有考慮 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，來降低大v與其他用戶的相似度：

上面介紹了3種計算用戶之間相似度（或稱熟悉度）的計算方法。除了熟悉程度，還需要考慮用戶之間的興趣相似度。我們和父母很熟悉，但很多時候我們和父母的興趣確不相似，因此也不會喜歡他們喜歡的物品。因此，在度量用戶相似度時，還需要考慮興趣相似度，而興趣相似度可以通過和UserCF類似的方法度量，即如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度很高。

最後，我們可以通過加權的形式將兩種權重合並起來，便得到了各個好有用戶的權重了。

有了權重，我們便可以針對用戶u挑選k個最相似的用戶，把他們購買過的物品中，u未購買過的物品推薦給用戶u即可。打分公式如下：

其中 w' 是合並後的權重，score是用戶v對物品的打分。

node2vec的整體思路分為兩個步驟：第一個步驟是隨機遊走（random walk），即通過一定規則隨機抽取一些點的序列；第二個步驟是將點的序列輸入至word2vec模型從而得到每個點的embedding向量。

隨機遊走在前面基於圖的模型中已經介紹過，其主要分為兩步：（1）選擇起始節點；（2）選擇下一節點。起始節點選擇有兩種方法：按一定規則抽取一定量的節點或者以圖中所有節點作為起始節點。一般來說會選擇後一種方法以保證所有節點都會被選取到。

在選擇下一節點方法上，最簡單的是按邊的權重來選擇，但在實際應用中需要通過廣度優先還是深度優先的方法來控制遊走范圍。一般來說，深度優先發現能力更強，廣度優先更能使社區內（較相似）的節點出現在一個路徑里。

斯坦福大學Jure Leskovec教授給出了一種可以控制廣度優先或者深度優先的方法。

以上圖為例，假設第一步是從t隨機遊走到v，這時候我們要確定下一步的鄰接節點。本例中，作者定義了p和q兩個參數變數來調節遊走，首先計算其鄰居節點與上一節點t的距離d，根據下面的公式得到α：

一般從每個節點開始遊走5~10次，步長則根據點的數量N遊走根號N步。如此便可通過random walk生成點的序列樣本。

得到序列之後，便可以通過word2vec的方式訓練得到各個用戶的特徵向量，通過餘弦相似度便可以計算各個用戶的相似度了。有了相似度，便可以使用基於用戶的推薦演算法了。

推薦系統需要根據用戶的歷史行為和興趣預測用戶未來的行為和興趣，因此大量的用戶行為數據就成為推薦系統的重要組成部分和先決條件。如何在沒有大量用戶數據的情況下設計個性化推薦系統並且讓用戶對推薦結果滿意從而願意使用推薦系統，就是冷啟動問題。

冷啟動問題主要分為三類：

針對用戶冷啟動，下面給出一些簡要的方案：
（1）有效利用賬戶信息。利用用戶注冊時提供的年齡、性別等數據做粗粒度的個性化；
（2）利用用戶的社交網路賬號登錄（需要用戶授權），導入用戶在社交網站上的好友信息，然後給用戶推薦其好友喜歡的物品；
（3）要求用戶在登錄時對一些物品進行反饋，手機用戶對這些物品的興趣信息，然後給用推薦那些和這些物品相似的物品；
（4）提供非個性化推薦。非個性化推薦的最簡單例子就是熱門排行榜，我們可以給用戶推薦熱門排行榜，然後等到用戶數據收集到一定的時候，在切換為個性化推薦。

對於物品冷啟動，可以利用新加入物品的內容信息，將它們推薦給喜歡過和他們相似的物品的用戶。

對於系統冷啟動，可以引入專家知識，通過一定高效的方式快速建立起物品的相關度表。

在上面介紹了一些推薦系統的基礎演算法知識，這些演算法大都是比較經典且現在還在使用的。但是需要注意的是，在實踐中，任何一種推薦演算法都不是單獨使用的，而是將多種推薦演算法結合起來，也就是混合推薦系統，但是在這里並不準備介紹，感興趣的可以查閱《推薦系統》或《推薦系統與深度學習》等書籍。此外，在推薦中非常重要的點擊率模型以及基於矩陣的一些排序演算法在這里並沒有提及，感興趣的也可自行學習。

雖然現在用的很多演算法都是基於深度學習的，但是這些經典演算法能夠讓我們對推薦系統的發展有一個比較好的理解，同時，更重要的一點——「推陳出新」，只有掌握了這些經典的演算法，才能提出或理解現在的一些更好地演算法。

㈩ 優化演算法筆記（二十五）飛蛾撲火演算法

（以下描述，均不是學術用語，僅供大家快樂的閱讀）
飛蛾撲火演算法（Moth-Flame Optimization）是受飛蛾圍繞火焰飛行啟發而提出的演算法。演算法提出於2015年5月（投稿日期），雖可算作一個新演算法，不過無數研究者就像飛蛾見了火一樣，發表了如此之多的論文，驚了。
飛蛾撲火演算法中有兩種個體，飛蛾和火焰，飛蛾選擇並圍繞火焰以螺線方式飛行搜索，搜索完後，火焰將移動位置，以保持火焰是飛蛾和火焰群體中最優的位置。
演算法的流程簡單，螺線搜索在之前的鯨魚演算法中也出現過，這里會較為詳細的記錄記錄螺線搜索的具體情況。

顯然,飛蛾撲火演算法中有兩種角色,飛蛾與火焰。初始時飛蛾與火焰的數量均為N。為了方便查看，將飛蛾的位置表示為XM ，火焰的位置為 XF。
初始化時，會在解空間內初始化N個飛蛾與M(M=N)個火焰。在演算法過程中，飛蛾將會圍繞它所選擇的火焰飛行，之後將這N個飛蛾與M個火焰按優劣排序，並將M個火焰移動到較優的前M個個體的位置。其中火焰的數量M會隨著迭代次數的改變而不斷變化，論文中階梯遞減至1。
演算法的主要步驟如下：
1. 飛蛾選擇火焰（將火焰分配給飛蛾）。
2. 飛蛾圍繞火焰飛行。
3. 移動火焰到相應位置。
從步驟可以看出，演算法中飛蛾的飛行是一種無貪心演算法的操作，而火焰的移動則是一種變相的貪心操作。

初始化時，會有N個飛蛾和N個火焰（M=N）,故每隻飛蛾都可以選擇互不相同的火焰。隨著迭代次數的遞增，火焰的數量會遞減。其數量根據以下公式計算得出：

其圖像如下圖所示：

其實就是將火焰數量M線性遞減到1，由於火焰數量是正數，故圖像呈階梯狀。
隨著迭代次數增加，火焰數量遞減，每隻飛蛾無法選擇互不相同的火焰，此時可以隨機選擇火焰或者飛蛾群體按順序依次往後選取，類似於取模。兩種方式的差別不大。

該步驟是演算法的核心計算步驟。
對於飛蛾 ,它圍繞火焰 飛行後到達的新位置XM_new根據以下公式計算得出：

其圖像如下

而演算法中的飛行軌跡應該是這樣的：

取出一維看看

其中i為計算次數。

圖像就是cos函數圖像的變形。考慮到飛蛾與火焰之間的距離會越來越短，其飛行圖像應該與上圖相反，即振幅越來越小，局部搜索能力越來越強。

N只飛蛾圍繞M個火焰飛行後，會到N個新位置，計算這N個新位置的適應度值，將這N個新位置與M個火焰這（N+M）個位置按優劣排序，並將其中較優的M個位置作為下一輪中火焰的位置。

其飛蛾撲火演算法流程圖如下：

由於飛蛾撲火演算法可以說是對蟻獅演算法和鯨魚演算法的結合，這里就看看演算法的圖像，不再做其他處理了。
適應度函數 。

實驗一：

從結果看來，飛蛾撲火演算法的性能穩定也優於蟻獅演算法，從圖像看演算法收斂性不如蟻獅演算法但局部搜索性能要強於蟻獅演算法。
可見螺線的局部搜索能力還是強於隨機遊走的，不過其全局搜索要弱於隨機遊走。相比蟻獅演算法，飛蛾撲火演算法更容易陷入局部最優（其實與蟻獅差不多，只要火焰/蟻獅陷入局部最優基本完蛋，不過蟻獅數量恆定，火焰數量遞減，所有火焰更容易局部最優）。

飛蛾撲火演算法是根據飛蛾圍繞火焰飛行的行為而提出的演算法。演算法的結構比較簡單，與蟻獅演算法類似，只是搜索步驟將隨機遊走替換成了螺線搜索（當然還有跟多細節上的不同，可以看看原文）。演算法的局部搜索能力非常強，依靠螺線就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力強弱由其極半徑決定，演算法中由b決定。不過演算法缺少跳出局部最優的能力，在平滑函數中的效果非常好，在局部最優較多的函數中效果中規中矩。

參考文獻
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取碼：koy9
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記（二十四）帝王蝶演算法
下一篇 優化演算法筆記（二十六）和聲搜索演算法