啟發式概念構造的組推薦方法*

劉忠慧，鄒 璐，楊 梅，閔 帆,2+

1.西南石油大學 計算機科學學院，成都 610500

2.西南石油大學 人工智能研究院，成都 610500

1 引言

形式概念分析[1]（formal concept analysis，FCA）是一種針對形式背景的數據分析和規則提取方法，常用于機器學習、數據挖掘、知識發現等[2-5]領域。形式背景表示了對象、屬性以及它們之間的二元關系，能描述電子商務中的用戶消費記錄或偏好，因此近幾年FCA 被引入到推薦系統領域[6-8]。

當前，基于FCA 的推薦思路是先構建概念格，然后根據概念間的層次關系計算用戶或項目的鄰域。然而概念格構造效率低，幾乎與形式背景的規模呈指數關系[9-10]。為降低構造的復雜度，研究者提出了構建概念格的優化算法，如基于統計的概念格構造[11]、基于剪枝的概念格構造[12]等。基于樹結構的增量算法[13]在構造概念格時，通過快速定位父子節點的范圍，縮短搜索時間，但在數據稀疏時改進效果不明顯。形式背景分解法[14-16]利用并行計算，加速子概念格的構造，但在概念格合并時花費的時間較長，也未解決構造效率低的問題。

基于概念格的推薦[7-8]通常只考慮概念中用戶的相互關系，而概念間的層次關系僅用來尋找鄰居。因此只要保證概念集合能正確表示形式背景的信息，推薦效果就有望得到保障，故概念格的構造對于推薦應用不是必要的步驟。

本文提出一種不構建概念格的方案，使用啟發式算法挖掘重要概念進行推薦，從根本上解決效率問題。

新方案包含兩個階段：第一階段是概念構造，即生成一系列內涵與外延均較大的概念，同時滿足它們對整個對象集合的覆蓋；第二階段是組推薦，即利用概念本身的群組特性進行推薦。

在抽樣數據集和MovieLens 上，對比了本文算法與兩類不同的推薦方法。結果表明，本文算法的概念生成效率高，推薦效果比基于概念格的推薦方法好，與KNN（K-nearest neighbor）算法[17]效果相當。

2 相關工作

本章主要介紹FCA 的相關概念和知識，以及兩類常見推薦系統。

2.1 相關定義

定義1[1]（形式背景）形式背景是一個三元組T=(O,A,R)，其中O為對象集，A為屬性集，R為O和A之間的二元關系，O×A→R。對于r(x,a)=1，表示對象x擁有屬性a，也可以表示為xRa。

對象集X?O和屬性集B?A，分別定義運算：

表1 是電影評分表轉化后的形式背景，記錄了10位用戶觀看7 部電影的情況。如果用戶ui(0 ≤i≤9)看過電影mj(0 ≤j≤6)，則r(mi,mj)=1；反之r(mi,mj)=0。

Table 1 Exemple of formal context表1 一個形式背景的例子

定義2[18]（形式概念）在形式背景T=(O,A,R)中，令E?O，I?A，當二元組(E,I) 滿足E*=I，I*=E時，則稱C=(E,I)為形式概念，簡稱概念。E(C)表示概念的外延，I(C)表示概念的內涵，簡寫為E和I。

從表1 中可得一個概念C=({u1,u5},{m1,m4})，其外延為u1、u5，內涵為m1、m4。

定義3[18]（偏序關系）設C1=(E1,I1)，C2=(E2,I2)是T的兩個概念。若C1≤C2?E1?E2?I2?I1，且不存在概念C3使得C1≤C3≤C2，則可稱C2是C1的父概念，C1是C2的子概念，稱“≤”為概念間的偏序關系。

定義4[18]（概念格）形式背景中所有概念通過概念間的偏序關系構成的格L(O,A,R)稱為概念格。

Hasse 圖是概念格的圖形表示方式，按照父概念在上，子概念在下的原則，用線段把父子概念連接起來。圖1 為表1 的概念格，共33 個概念，其中接近50%的概念外延或內涵只有一個元素。

2.2 常見推薦系統

目前常見有兩類推薦系統，分別是基于鄰域的推薦系統和基于群組的推薦系統。

基于鄰域的推薦系統由Zaier等人[19]在2007 年提出，其核心思想是通過相似度計算，找到相關鄰域，利用鄰域信息進行推薦。主要分為基于用戶的推薦[20]和基于項目的推薦[21]，前者是根據鄰居用戶的喜好進行推薦，后者是根據項目的相似度進行推薦。基于概念格的推薦屬于鄰域推薦，它通過概念間的偏序關系來尋找目標用戶的鄰居。

組推薦系統（group recommender system）由Garcia等人[22]在2012 年提出，推薦對象是整個群組。組推薦系統統計所有群組成員的偏好，通過共享和交互縮小群組成員之間的偏好差異，融合得到群組偏好，最后利用群組偏好進行推薦[23]。

本文結合FCA 和組推薦思想，根據用戶所在的群組，以及群組成員的偏好，實現用戶的相互推薦。

3 問題描述與方案分析

概念由用戶集和項目集組成，用戶集中的成員具有相同的偏好（概念內涵），從協同過濾[24]的角度可知，他們之間可以進行相互推薦。

3.1 問題描述

利用概念進行推薦，需要解決兩個子問題：一是概念集合的構建；二是基于概念集合的組推薦。

問題1 概念集合的構建

輸入：形式背景T=(O,A,R)。

輸出：概念集C 。

約束條件1：∪(E,I)∈CE=O。

約束條件2：?(E,I)∈C,|I|≥α。

優化目標：min|C|。

Fig.1 Hasse of table 1圖1 表1 的Hasse圖

其中，約束條件1 表示概念集覆蓋了T的所有對象，保證任一對象至少屬于一個概念，為后一階段的推薦做準備。約束條件2 表示所挖掘概念的內涵規模不小于閾值α，從推薦系統的角度，僅當用戶之間擁有足夠多的共同項目，所形成的群組才有意義。優化目標為最小化概念集合，其目的是獲得更簡潔的表示，以提高模型的泛化性。

問題2 基于概念集合的組推薦

輸入：形式背景T=(O,A,R)，概念集C，推薦閾值β。

輸出：推薦矩陣L。

約束條件：?(E,I)∈C，?u∈E，m∈A且r(u,m)=0，滿足E中至少有β個對象向u推薦m。

優化目標：max(F1)。

將概念用戶集視為一個群組，約束條件表示向目標用戶推薦項目，需要滿足組內至少達到推薦閾值的用戶有m偏好。優化目標是最大化推薦F1 指標，實現高質量的推薦。

3.2 方案分析

KNN 算法是借助k個近鄰對象進行推薦，本文算法則基于高質量概念。根據問題1 的優化目標，應盡量挖掘對象多的概念。而為使推薦效果更好，這些對象需具有更強的共同愛好，即概念的內涵更大。為此，定義了衡量概念質量的指標。

定義5（概念面積）形式概念C=(E,I)的面積為：

其中，|·|表示集合的基數。

由定義5 可知概念面積由外延和內涵的規模共同決定。外延規模大表示對象的鄰居多，穩定性強；內涵規模大表示對象群組相似度高，推薦成功率高。基于此，給出強概念定義如下。

定義6（強概念）(E,I)為x∈E的強概念，當且僅當不存在x∈E′，Area(E,I)＜Area(E′,I′)且|I|≥α，其中(E′,I′)為概念，α為內涵閾值。

例1 構建表1 中u5的強概念，α為2。通過計算，共3 個概念，C1=({u2,u3,u4,u5,u7,u9},{m0}),C2=({u4,u5},{m0,m1}),C3=({u5},{m0,m1,m4})。根據式（3）可知C2的面積為4，且滿足強概念的條件，將保留用于第二階段的推薦。

根據問題2 的優化目標，保證推薦質量，定義推薦置信度如下。

定義7（推薦置信度）給定形式背景T=(O,A,R)，概念C=(E,I)，對象x∈E，屬性i∈A-I，r(x,i)=0 。則基于C向x推薦i的置信度為：

由式（4）可知置信度由對象群組每個對象的推薦綜合決定。

4 算法設計

本章采用啟發式方法構造概念來解決問題1，基于概念進行組成員推薦來解決問題2。啟發式概念構造的組推薦算法（group recommendation based on heuristic concept set，GRHC）由3 個子算法構成：算法1構建一個對象代表的強概念，算法2構建基于形式背景的強概念集合，算法3 利用概念集合進行組推薦。

圖4為各方案擾動能量隨時間的演變。由圖4d可知,平均來講,擾動能量的增長據降水量調整方案最大,其次為傳統BGM方案,另外兩種調整方案效果相對較弱。據降水量調整方案各層分開來看,模式第8層擾動能量在預報18 h后穩定維持在較大數值(圖4a),模式第16層(約500 hPa)增長飽和時間則提前到14 h左右(圖4b),而在模式第25層(約200 hPa),擾動能量在預報18 h之后大幅度下降(圖4c)。該方案24 h預報擾動能量在中低層增長到某一數值后穩定維持,說明集合預報對中低層影響較大,能較好地作用于控制預報誤差,從而最有可能改善預報效果。

4.1 概念構造算法

采用啟發式方法構建形式概念主要基于兩個原因：其一，不是所有概念都對推薦有用。在極端情況下，某些概念的外延集合只有一個對象，或者內涵集合只有一個屬性。這類概念包含的信息較少，不利于推薦。其二，不同的概念對推薦的貢獻程度不同，群組的規模和對象間的相似度決定了推薦的準確度。因此，挖掘強概念是本文的關鍵，通過設計針對性的啟發式方法可以達到此目的。

啟發式方法構建形式概念，通過逐一添加對象代表的屬性作為候選概念的內涵，同時更新候選概念的外延（見算法1 的第7 行），計算概念的面積并判斷內涵大小是否滿足閾值（見算法1 的第10～第16行），最終獲得對象代表的強概念。

為了簡化算法表示，做如下定義。

定義8（對象的屬性集合）形式背景T=(O,A,R)，任意對象u∈O，對象u的屬性集合記為：

對象集合U?O的屬性集合記為：

定義9（屬性的對象集合）形式背景T=(O,A,R)，任意屬性i∈A，屬性i的對象集合記為：

屬性集合I?A的對象集合記為：

算法1 構建強概念

算法2 按照屬性個數將對象有序排列（見第2行），依次選出對象代表，調用算法1 進行強概念構造（見第4 行）。從對象代表集合中刪除新概念中的對象（見第6 行），再選代表繼續下一個強概念的構造，直到所有對象都被包含在概念集合C 中。

4.2 組推薦算法

本文組推薦算法是基于算法2 得到的概念集合。一個概念中的用戶具有共同的偏好和興趣。組推薦方法通過統計用戶群組在某個項目上的喜好程度，以決定是否推薦該項目給同一群組的其他用戶，也就是計算基于概念向用戶推薦某個項目的置信度（見算法3 的第3～6 行）。

算法3 基于概念集合的組推薦算法

4.3 復雜度分析

下面分析算法1 和算法2 的復雜度。假設形式背景由m個對象和n個屬性組成，則任一個對象最多有n個非零屬性。在構建其概念時，選擇一個屬性作為內涵，最多比較m-1 次。因此最壞情況下構建一個強概念的時間復雜度為O(mn)，構建該形式背景下強概念集合時間復雜度為O(m2n)。

實際情況下，對象擁有的屬性遠遠小于n，因此構建強概念集合所花的時間遠小于O(m2n)。對比構建概念格的時間復雜度O(m2n)[9]，GRHC 算法的優勢較為明顯。

4.4 運行實例

根據表1 的形式背景，下面描述GRHC 算法的運行實例。其中，設置內涵閾值為2，推薦閾值為0.5。

構造以u4為代表的強概念。oca(u4)={m0,m1,m2,m3,m6}，將擁有用戶數最多的m0選中為備選概念的內涵，獲得外延{u2,u3,u4,u5,u7,u9}，備選概念面積為6；將u4余下項目依次與內涵結合，可得同時擁有m0、m2的用戶數最多；添加m2到內涵中，并更新外延為{u2,u4,u7,u9}，此時備選概念面積為8，大于前一個概念的面積；根據上述選擇策略，在({u2,u4,u7,u9},{m0,m2})的基礎上繼續構造，直到同時滿足內涵基數不低于2，概念面積最大。最終得到以u4為代表的強概念C=({u2,u4,u7},{m0,m2,m6})。

基于概念C為u4進行組推薦。u4的組成員為u2和u7，推薦候選項為m4、m5。根據表1 可知，u2推薦m4，u7無推薦。由式（4）可得基于C向u4推薦m4、m5的置信度分別為0.5 和0，因此滿足推薦閾值m4被推薦給u4。

5 實驗與結果

實驗數據集為MovieLens，包含943 個用戶和1 682 部電影，共10 萬條評分數據。實驗對比了概念格推薦方法、KNN 推薦方法。由于概念格無法在MoviesLens 上快速建立，因此實驗先使用抽樣數據集，對比GRHC 算法、概念格算法和KNN 算法，驗證算法效率；然后GRHC 算法在MovieLens 中進行不同內涵閾值和推薦閾值的實驗，討論其對概念生成、概念集合規模的影響。

5.1 推薦效果指標

本文采用推薦系統常用的評價指標：精確度（precision）、召回率（recall）和F1-measure。令L(O)為算法對所有用戶的推薦矩陣，T(O)為所有用戶在測試集中的行為矩陣。則推薦結果的精確度為：

推薦結果的召回率為：

綜合評價指標F1-measure為：

5.2 兩類對比算法

將GRHC 算法和KNN 以及概念格推薦算法進行對比。與KNN 算法對比是為了驗證GRHC 的正確性和推薦的有效性，而對比概念格推薦算法是由于兩者都基于FCA。

KNN 推薦算法：利用相似度方法找到與目標用戶最為相似的前k個鄰居用戶，再根據鄰居用戶的偏好信息來進行推薦預測。相似度計算一般采用杰卡德相似度，其計算公式如下：

其中，A、B為用戶集合。

概念格推薦算法[7]：采用漸進式算法構建概念格，根據概念間的父子關系找到目標用戶所在概念的兄弟概念與子概念，以此來得到候選項目列表。然后根據全局偏好度的計算結果，推薦與目標用戶所擁有項目最為相似的前k個項目。用戶u對候選項目i′的全局偏好度計算公式如下：

其中，I為用戶u的項目集合，Ui為與項目i有關的用戶集合，Ui′為與項目i′有關的用戶集合。

5.3 抽樣數據的實驗和結果

從MovieLens 隨機抽樣4 組大小為230×420 作為實驗數據集，其中每個數據集劃分80%訓練，20%測試。設置推薦閾值為0.5，內涵閾值為2。實驗中，將對象代表按擁有的屬性個數升序、降序以及原始序3 種情況分別驗證GRHC 算法；概念格算法選取全局偏好度最大的前10 個項目予以推薦；KNN 算法選取與目標用戶最為相似的前3 個鄰居用戶進行偏好信息推薦。

各算法的時間、精確度、召回率和F1 值如表2 所示，其中GRHC-D 表示對象代表為降序選擇，GRHC-A 表示對象代表為升序選擇，GRHC 表示對象代表按原序選擇。表3 對比了在相同數據集下，GRHC 算法和概念格推薦算法生成的概念個數和運行的時間。

Table 2 Experimental results on sampled datasets表2 抽樣數據集上的實驗結果

Table 3 Comparison of GRHC algorithm and concept lattice algorithm表3 GRHC 算法與概念格算法對比

實驗結果表明，不管采用何種對象代表選擇策略，GRHC 算法生成的概念個數和運行時間均遠低于概念格算法；從圖2 可以看出，在精確度、召回率和F1上，GRHC 算法明顯優于概念格推薦算法，略高于KNN(k=3)算法。這體現了GRHC 生成的概念數雖較少，通過半數推薦約束，最終推薦效果能保持在較好的水平，從而證明強概念在具有泛化性的同時還有實效性。

5.4 MovieLens數據集的實驗和結果

隨機劃分MovieLens 數據集80%訓練，20%測試，推薦閾值為0.5，GRHC 算法內涵閾值范圍為1～8，重復100 次，取這100 次結果的平均值作為最終結果，如表4 所示。

Table 4 Experimental results of GRHC algorithm on MovieLens表4 GRHC 算法在MovieLens上的實驗結果

Fig.2 Experimental results of GRHC compared to other algorithms圖2 GRHC 對比其他算法的實驗結果

實驗結果表明，GRHC 算法生成的概念個數與內涵閾值呈正相關，而對象代表的有序選擇將減少生成的概念個數。當內涵閾值為4，概念數在200～300之間時，GRHC 算法的推薦效果較好，如圖3 所示。當內涵閾值增大時，推薦效果隨之降低，這說明了概念的泛化性，更有利于推薦模型的構成。在Movie-Lens 數據集上GRHC 算法的推薦效果略低于KNN 算法(k=3)的推薦效果(F1 ≈0.25)。

Fig.3 Impact of intention threshold on F1圖3 內涵閾值對F1 的影響

6 總結和展望

本文提出了一種基于概念集合的組推薦算法。在概念構造時，采用了啟發式方法快速獲得滿足內涵閾值的強概念，確保每個概念對推薦有用，同時利用概念中對象共同的特性進行相互推薦。解決了如何設計啟發式構建信息，從何處開始概念的構建以及優化內涵閾值等問題。為形式概念分析方法提供了一種高效的推薦解決方案。目前的研究還缺乏對概念中項目組的信息挖掘，當前只考慮了對象群組的關聯；另外在推薦應用時，僅考慮二值情況，未進行評分預測；最后數據集的粒度較單一，未引入電影和用戶信息等特征值，這些都將成為今后繼續研究和探討的問題。