一種基於AdaBoost的鏈路預測算法
2023-10-09 01:23:34
一種基於AdaBoost的鏈路預測算法
【專利摘要】本發明提供了一種基於AdaBoost的鏈路預測算法，該方法適用於為當前拓撲結構中的通信實體預測其將來發生通信的可能性。用戶輸入當前網絡的通信關係，通過一系列的計算，能夠得到對下一時刻的通信實體是否發送通信的預測。該方法將Boosting方法中提升弱學習方法為強學習方法的思想應用到鏈路預測之中。本發明的優勢在於相對於現有的各種常用的預測算法而言，具有更高的靈敏度和更低的誤報率，能夠在顯著提高算法召回率的同時，保持計算結果的正確性。
【專利說明】一種基於AdaBoost的鏈路預測算法
【技術領域】
[0001]本發明涉及網際網路技術，具體涉及一種鏈路預測的實現方法。
【背景技術】
[0002]鏈路預測是鏈路挖掘中將連結作為挖掘對象的應用。主要預測已經存在但尚未被發現的連結以及尚未連結的節點間未來產生連結的可能性。隨著一些鏈路預測算法開始在商業領域得到應用，與之相關的研究已經成為一個熱門領域，其中基於拓撲圖的鏈路預測算法研究工作在近年來受到了廣泛重視。例如Facebook採用基於RWR(Random Walk withRestart)的方法預測用戶的朋友關係，據此提高好友推薦的成功率。
[0003]基於網絡拓撲圖的鏈路預測算法主要包括基於節點鄰居的相似性，基於最大似然估計以及基於概率模型等三種類型。代表性算法包括基於局部信息相似性的共同鄰居(CommonNeighbors)算法，基於路徑相似性的Katz算法和基於隨機遊走相似性的RWR算法。其中，基於節點鄰居相似性的鏈路預測算法研究較早，在實際工作中取得了廣泛應用。另一類取得實際推廣應用的方法是基於隨機遊走的鏈路預測算法。這類算法的基本思想都是對圖中節點所有可能的組合進行排序，選擇其中最可能出現在新圖中的節點對(即圖中的邊)。然而近一兩年來，無論是在對已有算法的改進，還是在提出新算法方面，都沒有出現有突破性的成果，基於拓撲的鏈路預測算法的召回率依然較低。
【發明內容】
[0004]本發明的目的是提供一種基於AdaBoost的鏈路預測算法。使用本發明提供的實施例，可以對當前網絡拓撲圖中將來可能發生連結的節點對進行預測。
[0005]為了克服當前主流的基於網絡拓撲結構的鏈路預測算法普遍存在召回率較低的問題。通過我們的研究發現，現有的主流鏈路預測方法的預測結果並不完全相交，利用算法結果的疊加提高召回率。但是，直接累加求和並不可行，因為會降低總的算法精度。據此考慮採用Boosting方法對其進行改進。首先將鏈路預測問題看作二分類問題，對下一時刻網絡中每一條可能存在的邊(節點對)，其分類結果為兩類:存在或不存在。接下來借用Boosting方法通過錯誤反饋提升弱學習算法得到強學習算法的思想，根據一定的原則選擇若干鏈路預測算法作為弱分類器，基於AdaBoost算法提出並實現了一個新的鏈路預測方法。
[0006]該方法的步驟包括:
[0007]讀取預測訓練樣本以及預測測試樣本；
[0008]為預測訓練樣本附上其真實所在類的標籤值；
[0009]為每個樣本的權重賦初始值；
[0010]選取若干鏈路預測算法作為弱分類器；
[0011]使用各個分類器為訓練樣本做分類；
[0012]計算每個分類器的投票權重；[0013]使用每個分類器為預測測試集合中的樣本做分類；
[0014]按上述各分類器的分類結果為預測測試集合中的樣本投票，做出最終預測；
[0015]輸出對預測測試集合中樣本的預測結果；
[0016]最後，實施本發明具有以下有益效果:
[0017]本發明實施例的有益效果是，將Boosting思想應用於連結預測之中，相對於現有的各種常用算法而言，具有更高的靈敏度和更低的誤報率，能夠在顯著提高算法召回率的同時，保持計算結果的正確性。
【專利附圖】
【附圖說明】
[0018]附圖是本發明改進現有鏈路預測算法提出的一種基於AdaBoost的鏈路預測算法的算法流程。
【具體實施方式】
[0019]下面結合附圖對本發明的【具體實施方式】進行描述，以便本領域的技術人員更好地理解本發明。
[0020]在本實施例中，如圖所示，提供了一個優化的算法流程:
[0021]步驟101、讀取預測訓練樣本以及預測測試樣本；
[0022]對於預測訓練樣本以及訓練測 試樣本，讀取其信息並生成網絡拓撲圖。
[0023]步驟102、為預測訓練樣本附上其真實所在類的標籤值；
[0024]對於一組長度為m的預測訓練集合C。Ω表示Xi被分類的類型值的集合。對於Xi,如果它確實出現在下一時間段的圖中，則Ii = I，反之，Yi = -1o
[0025]步驟103、為每個樣本的權重賦初始值；
[0026]每個樣本的權重初始值相等，是整個樣本長度的倒數，即為1/m。
[0027]步驟104、選取若干鏈路預測算法作為弱分類器；
[0028]按照預測結果互補的原則選取基於節點鄰居的相似性，基於最大似然估計以及基於概率模型等三種類型鏈路預測的方法作為弱分類器。
[0029]步驟105、使用各個分類器為訓練樣本做分類；
[0030]對每一種預測算法t，使用算法為C中每一對節點計算一個值，然後按照該值對節點對進行降序排列，選取前?個節點對，形成集合P，表示算法t認為這些節點對會在下一時刻的圖中存在，剩下的形成集合Q，表示算法t認為這些節點對不會在下一時刻的圖中存在。y是集合C中實際存在於下一時間段的圖中的節點對的數目。將預測算法t看作一個弱分類器t, t做出的假設為ht。如果Xi e P，則Iit(Xi) = I,反之,若Xi e Q，Iit(Xi) =-1。
[0031]步驟106、計算每個分類器的投票權重；
[0032]進行T次循環，t = I,..,T:每一次循環時，首先為每個分類器計算當前的錯誤率。對於每一個樣本，將分類器t對其的分類與其本身所屬類型相比，如果不一致，則在此分類器的錯誤率上加上該樣本的權重。計算並找出錯誤率最小的分類器作為當前的分類器。但是如果錯誤率大於1/2，就停止算法。對錯誤率進行歸一化處理，作為當前分類器t的投票權重。更新每個樣本的權重，如果該樣本被當前分類器錯誤分類，則它的權重上升。相對來說Xi如果被正確分類那麼它的權重就降低了。T次循環後，得到每個分類器的投票權重。[0033]步驟107、使用每個分類器為預測測試集合中的樣本做分類；
[0034]預測測試集合D中，使用&表示D中的每個節點對，η為D中所有節點對的數目。對於每種預測算法t，為預測測試集合D中每一對節點計算一個值，然後進行按照該值對節點對進行降序排列，選取前m』個節點對，形成集合P』，剩下的形成集合Q』。m』是集合D中實際存在於下一時間的圖中的節點對的數目。如果e」e P』，則ht(ej) = 1，反之，若e」e Q』，ht (ej) = -1。
[0035]步驟108、為測試樣本做出最終預測；
[0036]對於每個ep由每個弱分類器t對其進行投票。如果分類器t認為&在下一時刻圖中存在，則&的權重加上此分類器的投票權重。如果分類器t認為&在下一時刻圖中不存在，則為h的權重減去此分類器的投票權重。在所有分類器對h投票完成之後，若θ」的權重為正，即預測&會在下一時刻的圖中存在。反之，&的權重為負，則預測&不會在下一時刻的圖中存在。
[0037]步驟109、輸出對預測測試樣本的預測結果
[0038]對預測結果進行輸出
[0039]儘管上面對本發明說明性的【具體實施方式】進行了描述，以便於本技術領的技術人員理解本發明，但應該清楚，本發明不限於【具體實施方式】的範圍，對本【技術領域】的普通技術人員來講，只要各種變化在所附的權利要求限定和確定的本發明的精神和範圍內，這些變化是顯而易見的，一切利用本發明構思的發明創造均在保護之列。
【權利要求】
1.一種基於AdaBoost的鏈路預測算法:其特徵在於，首先讀取預測訓練樣本以及預測測試樣本；為預測訓練樣本附上其真實所在類的標籤值；為每個樣本的權重賦初始值；按照算法結果互補原則選取若干鏈路預測算法作為弱分類器；使用各個分類器為訓練樣本做分類；循環計算得到所有分類器投票權重，對每次循環，按照分類結果是否正確計算各個分類器當前錯誤率，選擇出錯誤率最小的分類器，計算其投票權重，並對所有的樣本進行權重升級。循環結束後得到每個分類器的投票權重；使用每個分類器為預測測試集合中的樣本做分類；按上述各分類器的分類結果為預測測試集合中的樣本投票，最終投票結果為正的樣本即為預測其會在將來發生連結，投票結果為負的樣本即為預測其不會再將來發生連結。
【文檔編號】G06F19/00GK103886169SQ201210553291
【公開日】2014年6月25日 申請日期:2012年12月19日 優先權日:2012年12月19日
【發明者】秦志光, 劉嶠, 梁棋, 秦臻, 鄭榮輝, 沐曉帆, 李汝佟 申請人:電子科技大學