[發明專利]引入空間衰減函數的興趣點推薦算法

在審

• 申請號: 201610050080.0
• 申請日: 2016-01-25
• 公開（公告）號: CN105718581A
• 公開（公告）日: 2016-06-29
• 發明（設計）人: 余正生;常曉雨
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 杜軍

1.引入空間衰減函數的興趣點推薦算法，其特征在于：該方法的具 體步驟如下：

步驟1、收集簽到網站中用戶簽到數據；

表1簽到網站中用戶簽到數據集

表1中：u代表用戶的編號，1≤u≤m，m為收集的用戶總數；v代表 興趣點的編號，1≤v≤n，n為興趣點總數；r_uv代表用戶u對興趣點v的 評分，A_v代表興趣點v的緯度，O_v代表興趣點v的經度；

步驟2、建立包含興趣點位置信息的“用戶-興趣點”評分矩陣R(m ×n)，評分矩陣含m個用戶和n個興趣點，興趣點的位置信息用興趣點 的經緯度來表示，如表2所示；隨機選取1/8的簽到興趣點作為測試集， 剩余7/8的興趣點作為訓練集；

表2包含興趣點位置信息的“用戶-興趣點”評分矩陣

步驟3、使用傳統興趣點相似度求解公式求解興趣點i，j之間的相似 度w(i,j)，1≤i≤n，1≤j≤n；傳統興趣點相似度求解公式有：余弦相似度 求解公式、修正余弦相似度求解公式和皮爾遜相關系數相似度求解公式；

相關參數設置：r_ui和r_uj分別表示用戶u對興趣點i和興趣點j的評分， 用戶沒有對興趣點評分被設置為0，和分別表示m個用戶對興趣點i 和興趣點j的平均評分，表示用戶u對興趣點的平均評分，U(i)和U(j) 分別表示對興趣點i和興趣點j評分的用戶集合，U(i,j)表示同時對興趣點 i，j評分的用戶集合；

3.1余弦相似度求解公式；在余弦相似度求解公式中，通過興趣點評 分向量之間的夾角余弦來度量它們之間的相似度；興趣點i，j的余弦相 似度如下：

w(i,j)=Σu=1mruirujΣu=1m(rui)2Σu=1m(ruj)2---(1)]]>

3.2修正余弦相似度求解公式；它在余弦相似度基礎上進行了改進， 通過減去用戶對興趣點的平均評分解決了余弦相似度沒有考慮用戶評分 等級差異的問題；興趣點i，j的修正余弦相似度如下：

w(i,j)=Σu∈U(i,j)(rui-ru‾)(ruj-ru‾)Σu∈U(i)(rui-ru‾)2Σu∈U(j)(ruj-ru‾)2---(2)]]>

3.3皮爾遜相關系數相似度求解公式；與修正余弦相似度一樣，它也 解決了用戶評分等級差異的問題；興趣點i，j的皮爾遜相關系數相似度 如下：

w(i,j)=Σu∈U(i,j)(rui-ri‾)(ruj-rj‾)Σu∈U(i,j)(rui-ri‾)2Σu∈U(i,j)(ruj-rj‾)2---(3)]]>

步驟4、三種興趣點相似度求解公式分別代入興趣點的預測評分公式 形成三種傳統興趣點推薦算法，分別預測出用戶u對測試集內各個興趣 點的預測評分；用戶u對興趣點i的預測評分公式如下：

r^ui=ri‾+Σj∈S(i,K)∩N(u)w(i,j)(ruj-rj‾)Σj∈S(i,K)∩N(u)|w(i,j)|---(4)]]>

式中，S(i,K)表示和興趣點i最相似的K個興趣點的集合，N(u)表示用戶 u訪問興趣點的集合；

步驟5、每種傳統興趣點推薦算法都推薦出預測評分值最大的N個興 趣點；

步驟6、通過召回率、精準度和F指標評價傳統興趣點推薦算法的推 薦性能；

R(u)表示用戶u推薦的N個興趣點的集合，T(u)表示用戶u實際感興 趣的興趣點集合，則召回率P₁、精準度P₂和F指標F，分別由下式求得：

P1=Σu=1m|R(u)∩T(u)|Σu=1m|T(u)|---(5)]]>

P2=Σu=1m|R(u)∩T(u)|Σu=1m|R(u)|---(6)]]>

F=2P1P2P1+P2---(7)]]>

召回率描述的是在用戶實際感興趣的興趣點當中被推薦的比例，精 準度描述的是推薦列表當中用戶實際感興趣的興趣點所占的比例，但這2 個指標經常出現相互矛盾的情況，往往1個指標增大的同時另1個指標 隨之減小，為了綜合考慮召回率和精準度，還用到了綜合評價指標F指 標；

步驟7、在推薦性能最好的傳統興趣點推薦算法基礎上引入空間衰減 函數，得到引入空間衰減函數的興趣點推薦算法，具體如下：

7.1找到推薦性能最好的傳統興趣點推薦算法；

由推薦列表長度N的不同值，根據三種傳統興趣點推薦算法中召回 率、精準度和F指標選取最好的傳統興趣點推薦算法；

7.2引入空間衰減函數f(d(i,j))，其中d(i,j)是興趣點i和興趣點j之 間的大圓距離，大圓距離指的是從球面的一點出發沿球面到達球面上另 一點所經過的最短路徑的長度；設置興趣點i和興趣點j的編號分別是c 和d，1≤c≤n，1≤d≤n，分別用經緯度(A_c，O_c)和(A_d，O_d)表示興趣點i 和興趣點j的坐標，則大圓距離的計算公式如下：

d(i,j)=2R*arcsin(sin2(Ac-Ad2)+cos(Ac)cos(Ad)sin2(Oc-Od2))---(8)]]>

式中，R表示地球的平均半徑，取值為6371.009km，d(i,j)的單位為km；

空間衰減函數f(d(i,j))的定義需滿足下列條件：興趣點i和j之間的 大圓距離越大，則f(d(i,j))越小，興趣點i和j之間的相似度越小，從而 降低用戶對距離更遠的興趣點的簽到行為對推薦結果的影響；首先給出 適合簽到網站中用戶簽到數據集的空間衰減函數類型，然后對空間衰減 函數預設參數，并將含有預設參數的空間衰減函數作為權值代入步驟7.3 的公式中；在進行推薦算法推薦性能實驗時，通過給定不同的空間衰減 函數預設參數值來得到不同的召回率、精確度和F指標，根據這些指標 選取適合簽到網站中用戶簽到數據集的空間衰減函數預設參數值，此時， 即可確定適合簽到網站中用戶簽到數據集的空間衰減函數；

7.3引入空間衰減函數的興趣點推薦算法如下：

w′(i,j)＝w″(i,j)f(d(i,j))(9)

式中：w″(i,j)表示推薦性能最好的傳統興趣點推薦算法中運用的傳統 興趣點相似度求解公式。