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

關(guān)鍵詞：推薦系統(tǒng);內(nèi)容相似性;過濾冗余信息;LZ77算法;哈夫曼編碼

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

0 引言（Introduction）

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

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

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

1 相關(guān)工作（Related work）

本文首先分析了兩種信息優(yōu)化算法，即LZ77算法和哈夫曼編碼。這兩種算法都是優(yōu)化信息領(lǐng)域的經(jīng)典算法，它們分別通過利用數(shù)據(jù)的重復(fù)結(jié)構(gòu)信息和字符出現(xiàn)頻率信息，實現(xiàn)了有效的冗余信息處理。在此基礎(chǔ)上，本文利用這兩種方法研究如何計算文本內(nèi)容的相似性，以期提升文本相似性評估的準確性。

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

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

近年來，LZ77算法的研究主要集中在提高信息優(yōu)化效率和速度、適應(yīng)不同類型的數(shù)據(jù)、結(jié)合其他信息優(yōu)化技術(shù)等方面。

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

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

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

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

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

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

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

2 方法（Method）

2.1 方法概述

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

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

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

輸入：用戶輸入文本內(nèi)容信息U，電影內(nèi)容信息C_i

輸出：經(jīng)過基于過濾冗余信息相似性算法預(yù)測的電影M

1： 初始化查找緩沖區(qū)和輸入緩沖區(qū)

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

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

4： FOR 每個字符 DO

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

6： IF 找到匹配子串 THEN

7： 根據(jù)公式（3），輸出三元組

8： ELSE

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

10： END IF

11： 添加三元組到序列L

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

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

14： IF 查找緩沖區(qū)超過m 個字符 THEN

15： 刪除最左邊的字符

16： END IF

17： END FOR

18： 統(tǒng)計L 中元素，構(gòu)建哈夫曼樹

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

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

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

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

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

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

3實驗（Experiment）

3.1 數(shù)據(jù)集選取

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

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

3.2 實驗方法及實驗環(huán)境

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

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

3.3 基準對比算法

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

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

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

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

3.4 評價指標

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

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

其中：TP（True Positive）表示用戶實際感興趣且被推薦的電影數(shù)量，TN（True Negative）表示用戶實際不感興趣且未被推薦的電影數(shù)量，F(xiàn)P（False Positive）表示用戶實際不感興趣但被推薦的電影數(shù)量，F(xiàn)N（False Negative）表示用戶實際感興趣但未被推薦的電影數(shù)量。

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

3.5 實驗結(jié)果

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

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

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

從圖5可以看出，在將RIFS算法的F1值設(shè)定為基準（100%）的情況下，預(yù)測1部電影時，Sentiment的F1值約是RIFS的2.38%，Seq2seq的F1值約是RIFS的9.23%，第二名Character的F1值約是RIFS的70.24%;預(yù)測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。

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

4 結(jié)論（Conclusion）

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

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

作者簡介：

艾均（1980-），男，博士，副教授。研究領(lǐng)域：通用人工智能，推薦系統(tǒng)，社交網(wǎng)絡(luò)計算。

孫陽（1999-），男，碩士生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。

蘇湛（1983-），女，博士，副教授。研究領(lǐng)域：通用人工智能，推薦系統(tǒng)，社交網(wǎng)絡(luò)計算。

方元江（1999-），男，本科生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。

謝正彬（1999-），男，本科生。研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，推薦系統(tǒng)。