基于過濾冗余信息相似性的電影推薦算法

關鍵詞：推薦系統;內容相似性;過濾冗余信息;LZ77算法;哈夫曼編碼

中圖分類號：TP391.4 文獻標志碼：A

0 引言（Introduction）

在基于內容相似性的方法中，文本相似性具有重要意義[1]。文本相似性是指兩個文本之間的語義相似程度，它是自然語言處理領域中的一個基本問題，其研究領域廣泛，涵蓋多個方面，主要包括基于詞袋模型的算法[2]、基于詞匯的算法[3]及基于深度學習的算法[4]等。

然而，現有的文本相似性算法也存在一些不足?；谠~袋模型的算法在處理文本信息時，忽略了文本中的詞序和上下文信息，導致無法準確評估文本之間的相似性[5]。基于詞匯的算法雖然考慮了詞序和上下文信息，但在處理大規模數據集時的計算復雜度較高，效率低[6]?；谏疃葘W習的算法在處理文本時，缺乏對文本語義的深入理解，容易受到局部信息的干擾[7]。

針對上述文本相似性算法出現的問題，本文提出了一種基于過濾冗余信息相似性的內容推薦算法，旨在改進現有文本相似性算法的不足。

1 相關工作（Related work）

本文首先分析了兩種信息優化算法，即LZ77算法和哈夫曼編碼。這兩種算法都是優化信息領域的經典算法，它們分別通過利用數據的重復結構信息和字符出現頻率信息，實現了有效的冗余信息處理。在此基礎上，本文利用這兩種方法研究如何計算文本內容的相似性，以期提升文本相似性評估的準確性。

LZ77算法以獨特的方式識別并過濾冗余信息，使數據變得更加緊湊，同時保留了原始信息的完整性。LZ77算法是由以色列工程師雅各布·齊夫和阿布拉罕·萊姆佩爾提出的。

該算法使用了一個滑動窗口字典存儲歷史數據，并在其中查找與當前數據最長的匹配串，然后用一個三元組（偏移量，長度，下一個字符）表示匹配結果。

近年來，LZ77算法的研究主要集中在提高信息優化效率和速度、適應不同類型的數據、結合其他信息優化技術等方面。

SUN等[8]提出了LZ77改進算法，結合靜態共享字典和自適應動態字典等方法，獲得了更好的數據優化程度，可以顯著提高正則表達式的預處理及匹配性能，但是可能會導致在處理大規模數據時出現內存溢出的問題，并且處理具有高度復雜性和隨機性的數據時的算法效率不高。

OSWALD等[9]提出了一種結合LZ77的混合算法，該算法可以處理跨域的語料庫，有效識別出哪些跨域的數據是冗余的，并采用了更高效的數據表示方式。這種優化方式使得跨域數據之間的相關性得到了顯著提高，從而提高了數據處理和分析的效率。但是，該算法在識別冗余跨域數據并使用更高效的數據表示方式時，可能會忽視不同跨域數據的一些重要特性，從而影響跨域數據的完整性和準確性。

哈夫曼編碼由美國計算機科學家大衛·哈夫曼提出，旨在最小化平均編碼的長度，并且具有唯一可譯性。該編碼技術在不損失原始信息的前提下，能夠盡可能地減少數據的大小;其核心在于采用了一種基于貪心策略的自下向上方法，通過構造一棵最優二叉樹，并為每個字符分配一個前綴不重復的二進制編碼，從而實現高效的數據壓縮。

近年來，哈夫曼編碼的研究主要集中在幾個方面：一是改進哈夫曼編碼的構造方法和編碼方式;二是探索將哈夫曼編碼應用于不同領域和場景;三是研究如何將哈夫曼編碼與其他信息優化技術相結合。

RAHMAN等[10]提出了一種使用Burrows-Wheeler變換和哈夫曼編碼的文本信息處理技術，該技術在很大程度上縮短了原始文本文件的長度，在保留原始文本內容的前提下，節省了存儲空間并提高了文本的傳輸速度。但是，該技術也存在一些局限性。第一，這種方法在處理復雜結構和大量獨特字符的文本時效果有限。第二，該技術需要預先計算輸入數據的概率分布，在處理動態變化的數據時會產生一些問題。

QIAN等[11]提出一種基于增量哈夫曼樹合并的在線詞向量模型生成方法。該方法能夠實現基于增量學習的在線詞向量模型生成，其顯著的特點是處理速度更快、性能更優，能滿足對大量在線文本數據的高實時性處理要求。這種方法的原理是將新出現的詞或者詞頻發生變化的詞插入已有的哈夫曼樹中，從而避免了重新構建整個哈夫曼樹的開銷。然而，這種技術也會導致哈夫曼樹的結構發生變化，從而影響詞向量的編碼和解碼。如果哈夫曼樹的結構變化過于頻繁，那么詞向量的穩定性和一致性就會受到一定程度的影響。

通過前述分析可以看出，LZ77算法和哈夫曼編碼在信息優化領域展現出了強大的能力，它們可以有效地識別出冗余的信息，從而實現信息的精簡和壓縮。這兩種算法各自擁有豐富的理論與實踐研究基礎，為信息壓縮領域的發展做出了重要貢獻。在信息壓縮領域，它們可以結合使用，形成更高效的方案，例如LZH、ZIP、PNG等。因此，本文致力于探究將這兩種算法相結合的方法，并研究對應的內容相似性度量方法，以及其在推薦系統中的應用。

2 方法（Method）

2.1 方法概述

本文提出的RIFS （Redundant Information Filtering Similaritybased Movie" Recommendation Algorithm ）是一種基于過濾冗余信息相似性的電影推薦算法，它融合了LZ77算法和哈夫曼編碼在信息優化方面的優勢。首先，該算法利用LZ77算法分別對每部電影信息及該部電影信息加上用戶輸入內容的冗余信息進行過濾，過濾冗余信息后分別將其以三元組序列的方式作為輸出;其次，構建哈夫曼樹，進行哈夫曼編碼后，分別計算經過哈夫曼編碼輸出的總位數的長度;再次，建立用戶輸入內容與電影信息的相似性公式;最后，根據相似性降序得出預測電影，生成預測電影的電影推薦列表后推薦給用戶。算法結構圖如圖1所示。

為了實現一個基于文本內容相似性的電影推薦系統，本文使用了RIFS算法對電影數據集進行冗余信息處理。RIFS算法結合了LZ77算法和哈夫曼編碼在信息優化方面的優勢，既能保證數據的完整性，又能保證達到較好的推薦效果。綜上所述，本文提出的算法的具體過程如下所示。

算法1 基于過濾冗余信息相似性的電影推薦算法

輸入：用戶輸入文本內容信息U，電影內容信息C_i

輸出：經過基于過濾冗余信息相似性算法預測的電影M

1： 初始化查找緩沖區和輸入緩沖區

2： 將Ci 的前n 個字符放入輸入緩沖區

3： 將Ci 的剩余字符放入待處理隊列

4： FOR 每個字符 DO

5： 根據公式（1），公式（2），尋找最長匹配子串

6： IF 找到匹配子串 THEN

7： 根據公式（3），輸出三元組

8： ELSE

9： 輸出三元組（0，0，當前字符）

10： END IF

11： 添加三元組到序列L

12： 移出處理過的字符，補充待處理隊列的字符到輸入緩沖區

13： 將移出的字符添加到查找緩沖區

14： IF 查找緩沖區超過m 個字符 THEN

15： 刪除最左邊的字符

16： END IF

17： END FOR

18： 統計L 中元素，構建哈夫曼樹

19： 得到字符集合C={c₁，c₂，…，c_n}及對應的頻率集合W ={w₁，w₂，…，w_n}

20： 根據公式（4），計算哈夫曼編碼輸出的總位數B₁

21： 將C_i+U 重復以上步驟計算哈夫曼編碼輸出的總位數B₂

22： 根據公式（5），公式（6），計算U 與C_i 的相似性

23： 將相似性降序排序，得出最相似的電影M

24： RETURN 基于過濾冗余信息相似性算法預測的電影M

3實驗（Experiment）

3.1 數據集選取

經過調研，當前主流的公開數據集都難以滿足本文的算法需求。本文所提算法建立在對電影文本內容的深入分析之上，然而一些流行的電影數據集包含了大量用戶對電影的評分信息，但是缺乏對電影的詳細描述和評論，如Movie Lens[12]、Netflix[13]及TMDB數據集等，因此這些數據集并不滿足本文算法的計算條件。為了滿足本文算法的計算條件，本文利用Python爬蟲技術對豆瓣電影Top250數據集[14]進行爬取。

本文使用的豆瓣電影Top250數據集是一個包含豆瓣網站上評分最高的250部電影信息的數據集。這個數據集中的每一部電影都有一些關鍵的屬性，包括電影名稱、導演、主演、編劇、上映日期、地區、簡介、類型、豆瓣評分、豆瓣用戶評價及評價人數。

3.2 實驗方法及實驗環境

豆瓣電影Top250數據集可以很好地應用于基于過濾冗余信息相似性的電影內容推薦算法，本文將每部電影的導演、主演、編劇、豆瓣用戶評價組合拆分成短句子作為用戶輸入內容，分別與電影名對應，構建了用戶輸入內容與電影名對應的數據集。實驗驗證時，利用每部電影名對應的電影簡介信息以及該電影簡介信息加上用戶輸入內容計算相似性，以此預測電影名。實驗采用十折驗證的方式，將數據隨機分為10組，依次選取1組數據作為測試集，剩余9組數據作為訓練集，每次選取完后，算法只用訓練集數據訓練，用測試集數據驗證，用10次實驗的平均值作為最終結果。

實驗所用處理器為12th Gen Intel（R） Core（TM） i7-12700H2.30 GHz，所用的顯卡為NVIDIA GeForce RTX 3060 LaptopGPU，內存容量為32 GB，操作系統為64位Windows 11，所有的實驗都是在上述的實驗環境中進行的，使本文能夠在相同的條件下對實驗結果進行公正的比較。

3.3 基準對比算法

本文選取了3種流行的文本相似性算法作對比實驗。

（1）基于字符頻率的推薦算法[15]（Character Frequency-Based Recommendation Algorithm，Character）：該算法是一種利用用戶輸入文本的字符頻率推薦相關內容的方法。用戶可以輸入自己喜歡的電影類型、導演、演員、情節等關鍵詞，然后系統會根據這些文本信息計算與不同電影的相似性，從而推薦最符合用戶的電影。

（2）融合文本情感的推薦算法[16] （Sentiment-BasedRecommendation Algorithm，Sentiment）：該算法可以實現一種根據用戶輸入的文本推薦符合用戶情感需求的電影的功能。用戶可以輸入文本，然后系統會根據這些文本信息計算與不同電影的情感向量相似性，從而推薦最適合用戶的電影。

（3）Seq2seq編碼器解碼器模型[17]（Sequence-to-SequenceEncoder-Decoder Model，Seq2seq）：該算法利用神經網絡技術分析文本內容信息。用戶輸入文本之后，根據其與不同電影的相似性為用戶提供個性化的電影推薦。這種方法可以讓用戶發現自己喜歡的電影類型或風格，也可以讓系統有效地利用電影的文本信息。

3.4 評價指標

本文從推薦系統的整體效果、用戶滿意度、用戶需求覆蓋和兩者的平衡性4個指標做度量，這些指標是準確率[18]（Accuracy）、精確率[19]（Precision）、召回率[20]（Recall）和F1值[21]（F1-score）。這些指標的計算公式和含義如下：

準確率（Accuracy）是指推薦系統正確推薦的電影數量占全部電影數量的比例，它反映了推薦系統的整體效果。準確率的計算公式是

其中：TP（True Positive）表示用戶實際感興趣且被推薦的電影數量，TN（True Negative）表示用戶實際不感興趣且未被推薦的電影數量，FP（False Positive）表示用戶實際不感興趣但被推薦的電影數量，FN（False Negative）表示用戶實際感興趣但未被推薦的電影數量。

精確率（Precision）是指推薦系統推薦給用戶的電影中用戶實際感興趣的電影的比例，它反映了推薦系統的用戶滿意度。精確率的計算公式是

3.5 實驗結果

從圖2可以看出，預測1部電影時RIFS比Sentiment提升了約0.24百分點，比Seq2seq提升了約0.23百分點，高于第二名Character約0.07 百分點。預測3 部電影時RIFS 比Sentiment提升了約0.30百分點，比Seq2seq提升了約0.29百分點，高于第二名Character約0.05百分點。

從圖3中可以看出，在將RIFS算法的精確率設定為基準（100%）的情況下，預測1部電影時，Sentiment的精確率約是RIFS的2.38%，Seq2seq的精確率約是RIFS的9.23%，第二名Character的精確率約是RIFS的70.24%;預測3部電影時，Sentiment的精確率約是RIFS的3.78%，Seq2seq的精確率約是RIFS的9.46%，第二名Character的精確率約是RIFS的84.87%。

從圖4可以看出，在將RIFS算法的召回率設定為基準（100%）的情況下，預測1部電影時，Sentiment的召回率約是RIFS的2.38%，Seq2seq的召回率約是RIFS的9.23%，第二名Character的召回率約是RIFS的70.24%;預測3部電影時，Sentiment的召回率約是RIFS的3.78%，Seq2seq的召回率約是RIFS的9.46%，第二名Character的召回率約是RIFS的84.87%。

從圖5可以看出，在將RIFS算法的F1值設定為基準（100%）的情況下，預測1部電影時，Sentiment的F1值約是RIFS的2.38%，Seq2seq的F1值約是RIFS的9.23%，第二名Character的F1值約是RIFS的70.24%;預測3部電影時，Sentiment的F1值約是RIFS的3.78%，Seq2seq的F1值約是RIFS的9.46%，第二名Character的F1值約是RIFS的84.87%。

從圖6可以看出，RIFS算法的用時比Sentiment減少了約4.2 s，比Seq2seq減少了約1.62 s，多于Character約0.89 s。

本文設計的RIFS算法，通過有效過濾內容的冗余信息，并進一步比較文本之間的內容相似性，使得對內容相關程度的判斷更加準確且嚴謹。在文本相似性類方法的性能方面，本文算法都顯著優于其他幾種算法，同時在計算復雜度方面犧牲的時間不多。與之相比，Character算法可以評估字詞對內容相似性的重要程度，但是未能考慮到文本內容中的詞序及上下文信息。Sentiment算法只考慮了內容之間的情感相似性，但是同樣的詞或短語在不同的上下文中可能具有完全不同的情感含義。Seq2seq算法可以學習文本內容的高層特征，但是訓練模型時通常需要大量的數據且計算復雜度較高。因此，本文提出的模型是有效的，并且具有時間復雜度低、可解釋性強的特點。

4 結論（Conclusion）

本文提出了一種基于過濾冗余信息相似性的啟發式方法，并將其應用于電影內容推薦領域，解決了文本內容相似性算法難以充分覆蓋文本內容信息的問題。本文使用LZ77算法過濾了文本內容的冗余信息，并對過濾后的信息進行哈夫曼編碼，利用電影信息經過哈夫曼編碼輸出的總位數的長度及電影信息加上用戶輸入文本經過哈夫曼編碼輸出的總位數的長度，構建用戶輸入內容與每部電影的相似性，實現了更準確地推薦電影。通過實驗驗證，本文所提RIFS算法在各個指標上的表現明顯優于Sentiment、Seq2seq和Character，證明了其高準確性和低計算復雜度的優勢。

在未來的研究中，可以進一步探索如何度量信息完全沒有冗余并對原始信息進行加權，還可以和深度學習的方法結合，雖然可能會增加一定的計算時間，但是有望進一步提升算法的整體性能。

作者簡介：

艾均（1980-），男，博士，副教授。研究領域：通用人工智能，推薦系統，社交網絡計算。

孫陽（1999-），男，碩士生。研究領域：復雜網絡，推薦系統。

蘇湛（1983-），女，博士，副教授。研究領域：通用人工智能，推薦系統，社交網絡計算。

方元江（1999-），男，本科生。研究領域：復雜網絡，推薦系統。

謝正彬（1999-），男，本科生。研究領域：復雜網絡，推薦系統。