影視推薦與參觀相關(guān)地點路徑規(guī)劃算法研究

李建碩

（天津工業(yè)大學，天津 300000）

1 引言

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

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

2 相關(guān)文獻綜述

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

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

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

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

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

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

3 偏好推薦

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

3.1 Jaccard 相似系數(shù)

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

圖1 Jaccard 相似系數(shù)推薦邏輯

目前有很多相關(guān)的相似度算法：

閔可夫斯基距離：

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

3.2 倒排法優(yōu)化用戶興趣度

為了解決如上問題，本系統(tǒng)將根據(jù)用戶的喜好偏好，將用戶-物品表轉(zhuǎn)變?yōu)槲锲?用戶表。根據(jù)每一個物品下的用戶，得到用戶的相似度矩陣（如圖2）。每一個物品下相同喜好的用戶會為矩陣中對應(yīng)項的值加1。

圖2 用戶-物品表到相似度矩陣的轉(zhuǎn)化過程

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

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

3.3 堆優(yōu)化的TOP-N 分析法推薦

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

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

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

4 路線規(guī)劃

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

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

舉例來說，假設(shè)A 地在起始點東方向1 千米，B 地在起始點西方向2 千米，C 地在起始點東方向3 千米，根據(jù)此算法得到的路線結(jié)果為：A->C->B。這顯然有一段重復(fù)的路線導(dǎo)致推薦的路線并不是最優(yōu)方案。

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

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

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

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

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

重復(fù)操作，直到?jīng)]有更新產(chǎn)生，dist 數(shù)組中的最大值即為所求最短路長度。

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

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

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

5 實驗與分析

本文使用網(wǎng)絡(luò)爬蟲所獲得的地點數(shù)據(jù)集與用戶喜好數(shù)據(jù)集，并對其中的數(shù)據(jù)進行整理，構(gòu)建原始數(shù)據(jù)集與期望結(jié)果數(shù)據(jù)集，得到可用于進行計算的數(shù)據(jù)集，見表1。

表1 原始數(shù)據(jù)集

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

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

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

表2 本文算法實驗結(jié)果

表3 實驗結(jié)果對比

6 總結(jié)與展望

本文針對影視旅游中經(jīng)常出現(xiàn)的協(xié)同過濾推薦，以及最佳路徑規(guī)劃兩類算法進行了理論性的優(yōu)化，同時實現(xiàn)了以用戶個性化推薦和路徑規(guī)劃為主要功能點的影視旅游系統(tǒng)。

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

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

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