影視推薦與參觀相關地點路徑規劃算法研究

李建碩

（天津工業大學，天津 300000）

1 引言

根據互聯網搜索到的數據顯示，我國電影業和旅游業增長迅速，從2011 年全國總票房100 億，到2018 年全國總票房609 億，6 年的時間，總票房翻了5 倍，2017 年全年國內游客達到50.01 億人次，比上年增長12.8%，這表明人們生活越來越多元化，對于精神層面的需求越來越高。一部電影的成功與否，不僅在于主演、題材等主要因素，更取決于電影場景的選取。根據世界各國影視旅游情況，結合一些經典電影景點，指出雖然電影的經濟效益是一時的，但是一些電影中的場景隨著影片的熱映而聞名，吸引到大批游客，帶動當地經濟發展。因此影視旅游的概念近幾年在國內興起[1]。

然而，大多數游客想要到這些旅游景點進行游覽時，需要自己發掘電影拍攝景點信息并查找大量旅游攻略制定路線圖，這一過程費時費力。因此，通過基于用戶喜好的協同過濾算法，實現電影經典的個性化推薦以及智能路線規劃功能符合市場需求。本文針對現有的一些智能推薦和路線規劃方案進行了算法上的優化，以獲得更為高效、實用的影視旅游系統。

2 相關文獻綜述

傳統的相似度計算忽略了用戶共同評分項目數與用戶平均評分的影響，以至于在數據稀疏時不能很好地度量用戶間的相似度。提出了兩個修正因子來改進傳統相似度，同時改進了協同過濾算法，將其應用于電影推薦。

2016 年，李昂等人[2]針對跨系統協同過濾推薦中用戶信息安全問題，提出一個安全計算模型。模型基于安全多方計算理論，使用輕量級分組密碼算法LBlock 加密第三方提供的數據,并用RSA 密碼系統管理密鑰。

2018 年,張麗等人[3]發布Slope One 視頻推薦算法的研究與實現，該算法基于Slope One 算法上，把時間衰減引起的評分權重函數作為一個權值參與到評分預測的公式中。而對于推薦的誤差較大問題，本文對皮爾遜相關系數法做了改進，并將改進后的項目相似度作為權值參與到評分預測公式計算中。

2020 年，陳浩銓等人[4]發布熱度和用戶愛好程度的關聯推薦算法研究，于景點熱度和用戶愛好程度的個性化旅游推薦算法，分析用戶所到過的旅游景點，根據旅游時長推算出用戶的興趣程度，基于該景點的熱度和用戶的愛好設計出適合的最佳旅游路線。

2020 年，余洋等人[5]對Slope one 算法進行了進一步改進與研究，應用到基于輔助項的多權重slop one 算法。

2020 年，劉榮權等人[6]發布屬性聚類與矩陣填充的景點推薦算法，將二分k－means 聚類算法應用到用戶屬性聚類中，因為同一類用戶的特征越相似，則它們的相似度越高，這使得目標用戶的相近鄰用戶集越準確。

3 偏好推薦

本文以Jaccard 相似系數作為協同過濾算法的基礎，通過倒排法解決不同用戶相似喜好過少導致的無意義計算，獲得相似度矩陣。之后利用相似度矩陣計算出用戶對物品的興趣度。最后采用借助“堆”實現的TOP-N 分析法，得到為用戶推薦的物品，并對熱門物品的影響進行了削減。

3.1 Jaccard 相似系數

為了判斷用戶喜好偏好，為其進行個性化推薦，常使用相似系數將目標用戶過去的行為軌跡與其他用戶進行對比，計算出相似度（見圖1）。

圖1 Jaccard 相似系數推薦邏輯

目前有很多相關的相似度算法：

閔可夫斯基距離：

一般來說Jaccard 算法不適合協同過濾，因為在協同過濾中，評分是一個很關鍵的參考因素，Jaccard 算法忽略了其中的評分環節。而本系統中針對目標用戶所喜好的物品只有電影和旅游地兩類，不需要考慮評分偏好，因此選擇較為簡單的Jaccard 算法來簡單計算兩用戶之間興趣相似度：

3.2 倒排法優化用戶興趣度

為了解決如上問題，本系統將根據用戶的喜好偏好，將用戶-物品表轉變為物品-用戶表。根據每一個物品下的用戶，得到用戶的相似度矩陣（如圖2）。每一個物品下相同喜好的用戶會為矩陣中對應項的值加1。

圖2 用戶-物品表到相似度矩陣的轉化過程

在得到了用戶的相似度矩陣后，便很容易得到用戶u 對某未知物品i 的興趣度公式：

其中，p(u,i)表示用戶u 對物品i 的感興趣程度，Auv是用戶相似度矩陣中用戶u 和用戶v 所對應的值，Wvi是用戶v 對于物品i的感興趣度。此處由于喜歡與否只根據用戶選擇來決定，因此這個值非0 即1。

3.3 堆優化的TOP-N 分析法推薦

得到用戶對物品的興趣度后，使用TOP-N 算法進行推薦，此處含義為推薦用戶最感興趣的N 個物品。由于N 的值可以在系統中動態更改，后續可能會對喜好進行更新。如果簡單使用排序求前N 大的物品，只能滿足一次系統調用的需求，若每次都需要重新計算該用戶感興趣度，則每次都需要花費O(nlog2n)的時間復雜度用于排序，大大降低了系統運行效率。

為了解決這種無意義的系統運行開銷，同時保證在更新用戶信息時能更加快速有效，本系統采用“小頂堆”這種數據結構對傳統影視旅游所采用的簡單TOP-N 分析法進行優化。將為每位用戶所推薦的最感興趣的N 個物品存入堆中，當需要更新時，只需要將新物品插入堆中，并執行“up 操作”[7]，最后將堆頂元素刪除，并保證堆大小為N。這樣即可用O(logn)的時間復雜度完成用戶喜好的更新。

而此方法的缺點在于，需要為用戶額外分配n 個物品大小的空間內存，屬于以空間效率換取時間效率的做法?？紤]到推薦物品數量不多，即占用的系統空間可以接收，因此此方法具有可行性。

4 路線規劃

根據通過偏好推薦算法所獲得的推薦地點，為用戶進行路徑規劃。由于需要為用戶推薦的是N 個景點的規劃線路，而非單源匯最短路問題，因此不適宜使用簡單的最短路算法進行處理。以往影視旅游研究中所采用弧面距離與實際道路距離相擬合的方式（圖3），雖然能得到可行解，但當目標地點在起始點左右分布較為分散時，這種做法會產生極大的不穩定性。

圖3 弧面距離與實際道路距離相擬合算法流程圖

舉例來說，假設A 地在起始點東方向1 千米，B 地在起始點西方向2 千米，C 地在起始點東方向3 千米，根據此算法得到的路線結果為：A->C->B。這顯然有一段重復的路線導致推薦的路線并不是最優方案。

本文采用基于迭代思想（動態規劃）的Bellman-Ford 算法[8]來求得推薦地點的最優旅游路線。首先將起始位置抽象成點0，推薦的N 個點抽象成點1 至點n，構成一張圖。將0號點設置為超級源點，向所有其他點連一條邊，作為該點的初始距離。對于圖中的任意一條邊(x,y,z)若滿足：

dist[y]≤dist[x]+z(6)

成立，則該邊滿足三角形不等式。其中dist[x]表示第x 號點到0 號點的距離，dist[y]表示第y 號點到0 號點的距離，z表示這兩點間的實際道路距離。當圖中所有邊均滿足三角形不等式時，dist 數組中所存的即為最短路線。

Bellman-Ford 算法的算法流程如下：

遍歷所有邊(x,y,z)，用dist[x]+z更新所有dist[y]>dist[x]+z的邊。

重復操作，直到沒有更新產生，dist 數組中的最大值即為所求最短路長度。

由于對每個點均遍歷了所有邊的情況，因此該算法時間復雜度為O(mm)。m 為圖中總邊數。

由于實際景點路線錯綜復雜，因此針對Bellman-Ford 算法可以使用隊列進行優化，將時間復雜度降低到O (km)級別，k 是一個很小的常數。本系統中采用的就是這種優化后的算法，本文中不再詳細描述。

所獲得的dist 數組與實際距離進行比對，可以得到清晰的最短路徑，將其作為結果展示給用戶即可。

5 實驗與分析

本文使用網絡爬蟲所獲得的地點數據集與用戶喜好數據集，并對其中的數據進行整理，構建原始數據集與期望結果數據集，得到可用于進行計算的數據集，見表1。

表1 原始數據集

由于喜好推薦其本身的主觀性，且數據集數量有限，缺少高數量用戶的樣本，缺少了推薦結果與用戶個人信息的吻合，故而對于推薦結果的準確性評估僅停留在理論層面，本文無法對其給出量化評估。

本文對以往影視旅游研究中所采用弧面距離與實際道路距離相擬合的方式進行了改進，故本文將使用原始數據集中的最優路線規劃數據集與計算所得的最優路線規劃數據集進行比較。

本文最后得到如下實驗結果，見表2-3。

表2 本文算法實驗結果

表3 實驗結果對比

6 總結與展望

本文針對影視旅游中經常出現的協同過濾推薦，以及最佳路徑規劃兩類算法進行了理論性的優化，同時實現了以用戶個性化推薦和路徑規劃為主要功能點的影視旅游系統。

在協同過濾算法中，首先，考慮到電影資源以及旅游地點的多樣性，針對Jaccard 相似系數，采用倒排法進行優化，避免過多無效物品對于用戶偏好計算過程效率的影響。其次，針對用戶對于某一物品的興趣度公式，進行了簡化，可以更容易在程序和系統中實現相應算法。最后，為了降低重復計算用戶感興趣物品所帶來的時間損耗，本文采用“堆”這類數據結構對TOP-N 分析法進行了改進優化，加快系統運行效率。

在路徑規劃算法中，證明出傳統的以球面距離與實際道路距離相映射這種方法的局限性。同時提出了一種基于Bellman-Ford 算法，針對全局的路徑規劃方案，提高了路徑推薦算法的可靠性。

在系統實際運行測試中，數據集數量有限，均來自管理員手動輸入。雖能夠保證在用戶數量較低的情況下系統的正確運行，但缺少高數量用戶的樣本，同時缺少了推薦結果與用戶個人信息的吻合，對于推薦結果的準確性僅停留在理論層面。為了解決這些問題，接下來將重點提高用戶數據量，并考慮添加用戶對于推薦結果滿意度的反饋功能，幫助改進推薦算法，實現系統功能的完善。