基于馬爾可夫聚類和混合協同過濾的電視節目推薦

趙 宇 劉 鳳 舒巧媛 韋鵬程

(重慶第二師范學院數學與信息工程學院 重慶 400065)

0 引 言

自從電視誕生以來，觀看電視節目一直都是人類精神生活中的重要組成部分。如今，由于計算機技術和網絡技術的飛速發展，人們越來越習慣于在互聯網平臺上觀看視頻節目，這也對傳統廣播電視運營商帶來了沖擊。對于廣播電視運營商而言，客戶的流失雖然為其帶來了許多挑戰，但也帶來了新的機遇。現在，付費頻道是廣播電視的主要業務，也是收入的重要來源。如果廣播電視運營商可以準確地知道每個用戶的收視偏好，為其推薦相似的電視節目，從而挖掘潛在的付費用戶，那么廣播電視的競爭力就能得到顯著提高。另一方面，大量數據的產生、推薦算法和數據挖掘等技術的發展，為廣播電視運營商實現精準推薦提供了技術支持。因此，研究個性化的電視節目推薦算法具有重要意義[1-4]。

目前廣泛使用的推薦系統都是通過搜集用戶的個人行為信息，然后使用基于用戶的推薦算法或者基于物品的推薦算法幫助用戶篩選出其可能感興趣的物品。Karabadji等[5]關注用戶特征搜索空間的增長，提出了一個基于多目標優化的推薦系統來提取用戶信息，使其與活躍用戶的相似性達到最大化，提升推薦準確率。Liang等[6]提出了一種基于概率的算法，將用戶對物品的曝光程度直接融合到協同過濾中，并把此曝光程度建模為一個潛在變量，算法通過數據推斷此變量的值，以此來提升推薦結果的準確度。為了解決推薦過程里的數據的稀疏性和高維度問題，Koohi等[7]通過使用基于子空間聚類的方法來進行鄰居用戶查找，此算法在推薦時將數據劃分為三個不同的子集：感興趣集合、既不感興趣也不厭惡集合、厭惡集合，基于這三個集合，為被推薦用戶創建三個層次的鄰居樹，然后進行推薦。Papneja等[8]提出了一種基于擴展激活的上下文感知個性化內容推薦算法，通過分析物品和用戶信息之間的關系，將有意義的物品推薦給用戶。Wan等[9]提出了一個同時建模顯示特征與隱式特征的推薦框架，將用戶對物品的一系列動作抽象成單調行為鏈，用來描述物品的信息，從而按照物品的相似度為用戶進行推薦。

以上這些研究在推薦系統領域都取得了令人滿意的推薦準確率，然而這些研究在關注推薦準確率的同時，卻存在一個潛在的問題：忽略了推薦結果的驚喜度和推薦結果的相關性對于用戶體驗的改善。一般而言，基于物品的推薦算法由于推薦的是相似物品，其推薦結果的驚喜程度比較低，而基于用戶的推薦算法由于是按照相似用戶進行推薦，其推薦結果和目標用戶的歷史偏好的相關性會降低，這兩點因素都會影響推薦系統的用戶轉化率[10]。為了解決這個問題，本文提出了一種基于馬爾可夫聚類和混合協同過濾的推薦算法MCL-HCF。首先，使用馬爾可夫聚類算法[11]對各個時間段內的用戶進行聚類，得到多個用戶群組，降低群組內用戶和整個群組之間的偏好差異性，然后以群組為單位進行推薦。在推薦階段，本文使用IUF(inverse user frequence)[12]和IIF(inverse item frequence)[13]參數來修正用戶相似度和物品相似度的計算。最后，加權融合兩種協同過濾算法的結果，解決推薦結果的驚喜度和相關性的矛盾問題。

1 MCL-HCF推薦算法

MCL-HCF算法是結合了馬爾可夫聚類與混合協同過濾的推薦算法。首先，MCL-HCF利用馬爾可夫聚類算法找出在各個時間段內具有相似偏好的用戶，然后將其看作一個群組，重新定義這個群組的觀看信息，最后再通過混合協同過濾算法來獲得最終的推薦結果，達到推薦驚喜度和相關性的平衡。

1.1 建立相似用戶的群組

一般而言，一個家庭里多個成員的電視節目觀看模式為：單個家庭由多個家庭成員組成，在某一個時間段St，某些成員對節目Pi感興趣，那么，這些成員將在這個時間段構成一個新的群組Ub。同理，在其他的時間段，同樣對應著其他的群組，并且從聚類的結果來看，一個家庭里的不同成員可以被劃分到多個群組中。

如圖1所示，用戶1、用戶2和用戶3在時段1觀看了節目1，所以將他們歸為群組1；用戶1、用戶2在時段2觀看了節目2，那么將他們歸為群組2；用戶3、用戶4在時段3觀看了節目3，那么將他們歸為群組3。由此可以看出，同一個用戶在不同時段被劃分到不同的群組。

圖1 分時段用戶群組示例

本文使用馬爾可夫聚類算法來建立各個時間段內的群組。馬爾可夫聚類算法基于圖進行聚類，其通過多次擴展和膨脹操作，使得最后聚族達到穩定狀態。

1.1.1建立同一時段的鄰接矩陣

本文篩選出在同一時間段內觀看節目的用戶，當兩個用戶同時觀看了同一個節目時，其鄰接矩陣對應元素加上1。由此可建立如下所示的鄰接矩陣:

1.1.2消除奇偶性依賴

基于圖的馬爾可夫聚類算法的核心操作之一是擴展操作。擴展操作模擬了流對象在圖上的隨機游走行為。流對象在具有某些特定結構的圖上執行隨機游走時，會產生奇偶性依賴效應。為了解決擴展操作所產生的這種問題，需要在對圖的狀態轉移矩陣進行處理之前，為每個頂點增加自循環，即矩陣對角線的值置為1，得到如下所示改進的鄰接矩陣：

1.1.3標準化概率矩陣

利用改進的鄰接矩陣，可以使用下式來計算得到概率矩陣：

(1)

1.1.4對概率矩陣進行擴展和膨脹交替操作

擴展和膨脹的交替操作是聚類過程的核心內容，首先執行的是擴展。如下式所示，擴展操作是使概率矩陣自乘e次，讓流對象擴展到圖的不同區域，其指數e的大小決定游走區域的大小。

P=Pe

(2)

然后，對概率矩陣P進行膨脹操作，膨脹操作的作用是增強聚簇節點內部的關聯，弱化非聚簇節點之間的關聯，即增大當前大概率，減小當前小概率。膨脹操作在作用于概率矩陣時，其參數r將會決定這種作用的強度，進而影響聚簇的粒度。其具體計算公式如下：

(3)

式中：ΓrP表示膨脹操作，pij∈P表示位于P的第i行、第j列的元素。

1.1.5聚類過程優化

為減小算法的迭代次數，加快馬爾可夫聚類過程，本文為其設置一個閾值θ。概率矩陣經過擴展膨脹操作后，遍歷所有pij，當pij≤θ時，令pij=0。這樣的操作可以有效地過濾掉矩陣內部的噪聲并加快馬爾可夫聚類過程的收斂速度。對于θ和r的取值見2.1節的實驗結果分析。

1.2 基于加權融合的混合推薦

協同過濾推薦算法可以分為兩大類：基于物品的協同過濾算法ItemCF(item-based collaborative filtering)、基于用戶的協同過濾算法UserCF(user-based collaborative filtering)。在此基礎上，本文分別引入IUF參數和IIF參數來修正改進兩種算法。

1.2.1基于物品的推薦

ItemCF-IUF算法的主要步驟如下：

Step1通過電視節目的歷史播放信息，建立電視節目的相似度矩陣。

Step2根據用戶的歷史觀看行為，為該用戶推薦與其觀看歷史相似的節目。

在進行推薦之前，本文先對數據進行預處理。

1) 數據預處理：

(1) 數據合并。將群組內所有用戶的觀看記錄合并在一起，以便計算群組的偏好。以下涉及的用戶的各個指標全部是以群組為單位進行計算。

(2) 除噪。刪去觀看時間低于5分鐘的記錄。

(3) 分組。將每個時間段的用戶分組。本文共分為5個時間段，如表1所示。

表1 觀看時間段

(4) 評分計算。計算各個群組對每個節目的評分。由于一般的廣播電視很少會有評分系統，所以，本文利用各個群組觀看每個節目的時長、次數、付費金額經過加權融合得到加權總頻率，并以此作為群組對節目評分的量化，得到評分矩陣D。其計算公式如下：

(4)

式中：Dij表示第i個群組對第j個節目的評分，a1、a2和a3分別表示觀看時長、次數和金額的權重，tij、fij和dij分別表示第i個群組觀看第j個節目的時長、次數和金額。在本文實驗中，取a1=1，a2=1，a3=2。

2) 計算節目相似度矩陣。考慮到用戶活躍度對節目相似度的影響，即活躍的用戶相比不活躍的用戶，對節目之間相似度的貢獻更小。例如，一個喜歡多個節目的人，比一個只喜歡節目的人，對節目的相似度貢獻較小，所以本文加入了IUF參數來修正相似度的計算。其計算公式如下：

(5)

式中：KIUF表示IUF參數，Nu表示用戶u喜歡的節目總數，Nu越大表示該用戶的活躍度越高，其對節目相似度的貢獻越小。

所以，節目相似度矩陣的計算公式如下：

(6)

式中:Wij表示節目i與節目j的相似度，Ni表示喜歡節目i的用戶數，Nj表示喜歡節目j的用戶數。

3) 節目相似度歸一化。為了提高推薦結果的準確度，本文遵循Karypis的研究[14-15]，將ItemCF-IUF的相似度矩陣按最大值歸一化。其計算公式如下：

(7)

4) 基于興趣度生成推薦列表。在評分矩陣D中，找到各個群組觀看歷史記錄里評分最高的節目，再按照與該節目興趣度的差異大小來進行排序，生成其他節目的推薦列表，推薦給這一群組里的用戶。在ItemCF-IUF算法中，通過如下公式計算群組u對一個節目j的興趣度：

(8)

Iuj越大，表示此群組對這個節目的興趣度越高，因此可以將推薦列表里興趣度較高的前幾個節目推薦給群組里的用戶。

1.2.2基于用戶的推薦

UserCF-IIF算法的主要步驟如下：

Step1找到和目標用戶興趣相似的用戶集合，即建立用戶相似度矩陣。

Step2在這個集合中查找目標用戶沒有觀看過的節目推薦給目標用戶。

1) 計算用戶相似度矩陣。節目受眾程度對用戶相似度的計算存在影響。受眾程度高的節目，相對于受眾程度低的節目而言，其對用戶相似度的貢獻更小。例如，一個受眾程度高的節目，兩個用戶都看過，但這并不能表明這兩個用戶興趣相似，反之，如果這兩個用戶都看過受眾程度很低的節目，那就可以認為這兩個用戶興趣比較相似。為了解決上述問題，我們在相似度計算過程里引入IIF參數，用于對熱門節目進行一定的懲罰。IIF參數的計算公式如下：

(9)

式中：KIIF表示IIF參數，Ni表示喜歡看i節目的群組個數，Ni越大表示這個節目的受眾程度越高，其對用戶相似度的貢獻就越小。

結合式(9)，可以得到如下的用戶相似度矩陣計算公式：

(10)

式中：Wuv表示用戶u與用戶v的相似度，Nu表示用戶u喜歡的節目集合，Nv表示用戶v喜歡的節目集合。

2) 用戶相似度歸一化。為了提高推薦準確率，我們依然對用戶相似度進行歸一化，其計算公式如下：

(11)

3) 生成推薦列表。通過馬爾可夫聚類，將聚在一類的用戶看作一個群組，對群組進行推薦。在UserCF-IIF算法中，通過下式計算群組u對節目i的興趣度：

(12)

Iui越大，表示此群組對這個節目的興趣度越高，則可以將興趣度較高的前幾個節目推薦給此群組里的用戶。

1.2.3混合推薦

混合推薦方法是在考慮不同推薦方法的缺點的基礎上建立的。混合推薦方法的準則是組合多種方法，發揮不同推薦方法的優點，消除各自的缺點。由于ItemCF-IUF給用戶推薦的是相似物品，所以其推薦的節目的驚喜度比較低。UserCF-IIF根據用戶相似度來推薦，其推薦驚喜度較高，但推薦結果的相關性較弱。

推薦節目的驚喜度可以這樣理解：用戶對某一類節目很少涉及，但是用戶在接收到此類節目的推薦后愿意觀看它。本文定義如下公式來表示推薦節目的驚喜度：

(13)

式中：Ps表示推薦的驚喜度，NG表示群組總數，PLEA(i)表示第i個群組的推薦分類中排名最低的分類節目總數，GEN表示推薦總數。

推薦節目的相關性可以這樣理解：為用戶推薦的節目與用戶觀看過的節目間的相關程度，即這兩方面節目是否屬于同一類。本文定義下式來表示推薦節目的相關性：

(14)

式中：Co表示推薦結果的相關性，NG表示群組總數，REC(i)表示第i個群組的推薦結果中每一個節目所屬類別總數的集合，GEN表示推薦總數。

為了在推薦節目的驚喜度和相關性之間取得一個平衡，本文使用了混合推薦方法，把ItemCF-IUF算法和UserCF-IIF算法所獲得的推薦結果，按M∶N的比例進行加權融合，形成最終的推薦結果，其過程如算法1所示。其中，Gk表示目標群組，Total為推薦列表的長度，topk表示篩選前k個推薦結果，k的值由輸入參數確定，cascade表示級聯操作，用于將篩選后的ItemCF-IUF和UserCF-IIF兩種算法的推薦結果進行組合。本文就ItemCF-IUF和UserCF-IIF兩種算法結果的推薦比例M∶N的最佳取值進行了探討，具體見2.2節的實驗結果分析。

算法1混合推薦

Input: Gk,Total,M,N

Output: Result

1: while j=1,2,…,Total do

2: resItem[j]←ItemCF-IIF(Gk)

3: resUser[j]←UserCF-IUF(Gk)

4: end while

5: resM←topk(resItem,(M*Total)/(M+N))

6: resN←topk(resUser,(N*Total)/(M+N))

7: Result←cascade(resM,resN)

8: return Result

2 實驗結果及分析

為了驗證提出的算法的有效性，本文使用了泰迪杯數據挖掘挑戰賽的公開數據集[16]。使用的數據集包含250位志愿者在3個月內，對100個節目觀看時產生的15 375條數據。實驗在擁有Intel i5處理器、8 GB內存的計算機上進行，計算環境為MATLAB 2018。

2.1 群組劃分結果分析

本文按照群組為單位進行電視節目推薦，群組劃分時聚類結果是否良好對最終的推薦結果會產生不同影響。本文關注的重點是各個群組內不同成員收視偏好的一致性，即追求在不同時間段內聚類得到的各個群組的組員與它所屬的群組的偏好差異最小化。首先，本文采用平均絕對誤差MAE[17-18]來衡量一個群組內的組員和群組整體的偏好差異，其定義如下：

(15)

式中：Dui表示用戶u對i的評分，DGi表示群組G對節目i的評分，N表示推薦節目的個數。

由于MAE僅僅是衡量單個群組與組內個體的偏好差異，而本文是按照群組為單位在不同時間段進行電視節目推薦的，所以本文定義一個新的衡量各個群組在不同時間段內的偏好差異的指標——群組平均絕對誤差MAEG，其計算公式如下：

(16)

利用上述公式，討論了馬爾可夫聚類參數θ和r的不同取值對于算法的收斂速度和群組劃分效果的影響，其結果如圖2和圖3所示。

圖2 迭代次數隨聚類參數的變化趨勢

圖3 MAEG指標隨聚類參數的變化趨勢

由圖2可以看出，馬爾可夫聚類的收斂速度由θ和r的大小決定，θ與r越大，其收斂速度越快，且隨著θ的變大逐漸趨于穩定。由圖3可以看出，當θ較小時，MAEG變化緩慢，當θ增加到一定值時，MAEG開始降低。結合圖2和圖3的結果可以看出，當θ=0.009，r=5時，群組平方絕對誤差MAEG=0.14，此時聚類得到的各個群組取得組內差異最小化，這表明此時的群組劃分達到最優，有利于提高最終的推薦準確率，且聚類過程也能達到較理想的收斂速度。

2.2 混合推薦比例分析

為了確定混合推薦比例M∶N的最佳值，以達到推薦結果驚喜度和相關性的平衡，本文對不同的比例組合進行了對比，分別計算在不同M∶N取值下的推薦結果驚喜度和相關性，結果如圖4和圖5所示。

圖4 推薦驚喜度對比

圖5 推薦相關性對比

在圖4和圖5中，time1-time5表示時間段，各個時間段對應的具體時刻見表1。由圖4可以看出，各個時間段的驚喜度在M∶N取1 ∶3處達到最大。由圖5可以看出，各個時間段在M∶N取1 ∶2處達到最高的推薦相關性，在1 ∶3處達到次高的推薦相關性。

通過對驚喜度和相關性的綜合比較，當ItemCF-IUF和UserCF-IIF的推薦節目個數比例M∶N達到1 ∶3時，推薦節目的驚喜程度和節目間的相關程度均達到相對較高的值，所以本文的混合推薦比例M∶N確定為1 ∶3。

2.3 推薦結果分析

為檢驗提出的推薦方法的有效性，本文在公開數據集[16]上進行了實驗，得到推薦的準確率、新鮮度和個體多樣性。結合如表2所示的混淆矩陣定義，本文通過下式來計算節目推薦的準確率：

(17)

式中：Acc表示推薦方法的準確率。

表2 混淆矩陣

除了推薦的準確率之外，推薦結果的新鮮度和個體多樣性也是衡量推薦算法性能的重要指標。新鮮度反映了推薦算法向用戶推薦非流行物品的能力；個體多樣性反映了推薦算法為用戶推薦相似度低且符合其興趣偏好的物品的能力。本文采用下式來定義推薦結果的新鮮度：

(18)

式中：Fre表示新鮮度，NG表示群組總數，λ(u)表示推薦節目是否是流行節目，若是，λ(u)=1，否則，λ(u)=0。而一個節目的流行度采用下式定義：

(19)

此外，本文采用下式來定義推薦結果的個體多樣性：

(20)

式中：Div表示個體多樣性，LN(u)表示群組u的推薦列表，N代表推薦節目個數，Wjk表示節目j和節目k的相似度。

通過使用250位實驗者觀看電視節目的行為數據進行實驗，本文對提出的MCL-HCF混合推薦算法進行了準確率、新鮮度和個體多樣性的分析。在實驗中，本文將電視節目劃分為綜藝、電視劇、電影、動畫、紀錄片、其他，共六大類。對于群組內單個用戶是否喜歡某個推薦節目的判斷依據是：在用戶歷史觀看記錄的評分矩陣中找出其喜歡的幾個節目類型，通過判斷推薦節目是否屬于用戶的偏好節目類型，確定用戶是否喜歡推薦的節目。推薦節目的準確率如表3和圖6所示。

表3 推薦準確率

圖6 準確率對比

表3中的time1-time5表示時間段，各個時間段對應的具體時刻見表1。Acc2表示用戶喜歡兩個節目類型時的準確率，Acc3表示用戶喜歡三個節目類型時的準確率。通過表3可以看出，使用MCL-HCF混合推薦算法對這250位用戶進行電視節目推薦的準確率總體比較高，Acc2各個時間段的均值為0.93，Acc3各個時間段的均值為0.96，這表明本文提出的先聚類得到群組再進行混合推薦的策略在電視節目推薦問題上能取得令人滿意的推薦準確率。

同時，從表3和圖6可以看出，各個時間段的Acc3比Acc2要大，這是因為當用戶喜歡的節目類型增加時，相當于擴大用戶的偏好范圍，這會提升對此用戶的推薦準確率。

推薦結果的新鮮度和個體多樣性如表4和表5所示，其中time1-time5表示的時間段具體范圍見表1。通過表4可以看出，除了time3時段外，本文提出的算法能取得較高的推薦新鮮度，具備為用戶推薦非流行節目的能力。通過分析time3(14:00-20:00)時段的觀看記錄，我們發現此時段播出的節目主要是以受眾程度較高的綜藝、電視劇和動畫類節目為主，這些類型的節目具備更高的普適觀眾的能力，這是在此時段進行推薦時新鮮度低于其他時段的原因。從表5可以看出，本文提出的算法在各個時段都能取得令人滿意的個體多樣性，能夠為用戶推薦更多不同類型的且符合其偏好的節目，從而能夠提升用戶的使用體驗。

表4 推薦新鮮度

表5 推薦個體多樣性

3 結 語

本文主要關注為家庭用戶進行電視節目的個性化推薦問題。為此，本文提出了MCL-HCF混合推薦算法。首先，使用馬爾可夫聚類算法對各個時間段內的用戶進行聚類，得到不同的用戶群組。為了衡量聚類結果的有效性，我們引入了組平均絕對誤差MAEG，在追求MAEG最小的策略下，優化了群組劃分的結果。然后，本文以群組為單位進行電視節目推薦，在使用ItemCF-IUF和UserCF-IIF兩種算法得到各自的推薦列表后，我們使用加權融合的方式進行了混合推薦，以此來解決傳統推薦算法在推薦結果的驚喜度和相關性上的矛盾。在公開數據集上的實驗結果表明本文提出的MCL-HCF算法具有如下優點：(1) 能夠降低群組內用戶和群組整體之間的偏好差異程度，提升對整個家庭的用戶推薦節目時的準確率；(2) 混合推薦的最終結果能夠在保持推薦準確率的同時，使推薦節目的驚喜度和相關性達到平衡。在后續研究中將主要關注尋找新的群組劃分策略，提升群組成員的內聚程度，進一步提高推薦效果。