近似概念的遺傳生成算法及其推薦應用

劉忠慧，王梓宥，閔 帆，2*

（1.西南石油大學計算機科學學院，成都 610500；2.西南石油大學人工智能研究院，成都 610500）

0 引言

形式概念分析（Formal Concept Analysis，FCA）［1］是一種在形式背景上進行的數據分析與規則提取方法，近年來被廣泛應用于機器學習、數據挖掘、知識發現等領域。形式背景包含了對象、屬性以及它們之間的二元關系，由形式背景生成的概念是對象集合與屬性集合組成的二元組，包含了二者之間的對應關系，能很好地描述推薦系統中用戶的消費記錄或偏好，因此FCA 被引入推薦系統當中。

由于形式概念的定義非常嚴格，在形式背景中存在許多不完全滿足該定義，但有實際意義的二元組，因此有研究者通過弱化概念生成中的條件提出近似概念［2-7］。范妍等［4］提出k級近似概念的相關理論知識，Li 等［2］研究了近似概念的構建及其在知識約簡與規則獲取領域的應用。然而，這些研究處于理論階段，還未與推薦系統結合。

概念格［1］是將形式概念通過偏序關系連接起來的格結構。FCA 應用于推薦系統的最初方案是構建概念格，根據概念格中的層次關系向目標用戶進行推薦［8］。概念格構建［9-10］方式主要有批處理式構造算法、漸進式構造算法以及并行算法［11］，但其時空復雜度都會隨著形式背景的規模增大而急劇增加。推薦系統的實際應用場景往往面臨的是大規模數據集，因此概念格在推薦系統中的應用受到了限制。

針對該問題，劉忠慧等［12］提出了利用啟發式信息生成概念集合代替概念格進行推薦應用。啟發式概念構造的組推薦（Group Recommendation based on Heuristic Concept set，GRHC）算法利用面積作為啟發式信息，生成包含每一個對象的概念集合，實施推薦。該算法與概念格推薦算法的效果相當，算法運行效率遠優于后者。但GRHC 算法只考慮了面積約束，忽略了相似度和近似概念的作用。

本文提出基于遺傳算法的近似概念生成算法（Approximate Concept Generate Algorithm，ACGA）及其推薦應用方案。首先利用啟發式方法生成初始概念集合；其次以外延相似度以及外延與內涵閾值為約束條件，對概念進行交叉、選擇及變異操作，得到近似概念；最后根據鄰居用戶的偏好，向目標用戶進行個性化推薦。本文工作的優勢主要表現在兩方面：一方面，啟發式概念集合生成保證了較低的時間復雜度；另一方面，近似概念提升了推薦的精度。

1 相關工作

本章給出形式概念分析以及遺傳算法的基本概念。

1.1 形式概念分析相關知識

定義1形式背景［1］。三元組T=(G，M，R)為一個形式背景，其中：G是對象的集合；M是屬性的集合；R是G和M之間的二元關系，R?G×M。若(g，m)∈R，記為gRm，表示對象g擁有屬性m。

對對象集X?G和屬性集B?M，分別定義如下運算：

表1 是一個簡單的形式背景，記錄了10 位用戶對7 部電影的觀看情況。若用戶ui(0≤i≤9)觀看過電影mj(0≤j≤6)，則(ui，mj)=1；反之(ui，mj)=0。

表1 一個形式背景的例子Tab.1 Example of formal context

定義2評分形式背景［13］。三元組O=(G，M，S)為一個評分形式背景，其中：G是對象集，M是屬性集，S是對象對屬性的評分數據。

表2 是一個簡單的評分形式背景示例，其中記錄了10 位用戶對7 部電影的評分情況，分值范圍為0～5。若用戶ui(0≤i≤9)觀看過電影mj(0≤j≤6)，則(ui，mj)表示用戶ui對電影mj的評分，(ui，mj)=0 代表用戶ui未觀看過電影mj。

表2 一個評分形式背景的例子Tab.2 Example of scoring formal context

定義3形式概念［1］。在形式背景T=(G，M，R)中，令E?G，I?M，若二元組(E，I)滿足E*=I，I*=E，則稱(E，I)為形式背景T的一個形式概念，簡稱概念。E稱為概念的外延，I稱為概念的內涵。

C=({u2，u3，u4}，{m0，m3})為表1 所示形式背景的一個概念，其中{u2，u3，u4}為外延，{m0，m3}為內涵。

定義4偏序關系［1］。給定形式背景T的概念C1=(E1，I1)和C2=(E2，I2)，若E1?E2(?I1?I2)，則稱C1為C2的子概念，記作C1?C2，顯然，“?”定義了概念之間的一個偏序關系。

定義5概念格［1］。在形式背景T=(G，M，R)中所有概念通過概念之間的偏序關系構成的格結構稱為概念格，記為L(G，M，R)。

定義6近似概念［4］。給定形式背景T=(G，M，R)，二元組P=(E，I)，由定義2 可知若E*=I，且I*=E則二元組P稱為T中的一個概念；相反地，若E*=I但I*≠E，則二元組P稱為T中的一個近似概念。

1.2 遺傳算法相關知識

遺傳算法［14-15］是一種基于自然選擇和遺傳機制的隨機搜索算法。遺傳算法對自然選擇和自然遺傳過程中的繁殖、交叉和變異進行了模擬。在每一次的迭代過程中均按照某種指標對當前種群進行篩選，保留較優個體，再利用交叉、變異、選擇算子產生下一代種群，重復直到滿足某種收斂指標為止。

概念的生成過程與此類似，需要外延對象相似度高，同時內涵具有一定規模。交叉、變異操作會增加更多樣性的概念，包括近似概念，豐富概念集合。杜鵑等［16］利用遺傳算法生成了概念集合，證明了遺傳算法可以應用到概念生成過程中。

1.3 推薦系統相關知識

當今時代，互聯網聯系著人們生活的方方面面，也因此使人們進入了一個大數據時代。在規模龐大的數據中，用戶如何快速獲取有用信息成為一個待解決的問題。推薦系統［17-18］為該問題提供了一個高效的解決方案。組推薦［19-20］、社會化推薦［21-22］等方法都為用戶提供了高效準確的推薦方案。同時，利用形式概念分析進行推薦［23-24］，也是一種有效的解決方案。

2 問題分解

本章主要介紹近似概念生成及推薦過程所涉及到的兩個子問題：一是基于遺傳算法構造近似概念集合；二是利用近似概念進行推薦。

2.1 近似概念集合構造

在對該問題進行描述之前，先給出該問題所涉及的相關定義。

本文利用用戶之間的距離表示用戶相似度，定義如下：

定義7用戶相似度。給定評分形式背景O=(G，M，S)，用戶ui，uj∈G，則ui，uj基于M的相似度計算公式定義如下：

其中：mk∈R，R為用戶ui、uj共同擁有的項目集合；s(u，m)表示在形式背景O中對象u對于屬性m的評分。特別地，若i=j，simM(ui，uj)=0。

由定義7 可相應地給出外延相似度的計算公式如下：

其中：uk∈E-{u}。

問題1 基于遺傳算法的近似概念集合構造。

輸入 評分形式背景O=(G，M，S)，初始概念集合CR。

輸出 近似概念集合SP。

約束條件 ?C1，C2?CR，u∈C1∩C2，simP(u)≥。

優化目標 max(simP(u))。

約束條件表示得到的近似概念P的外延相似度至少應大于或等于參與生成的原概念外延相似度的最小值；優化目標為近似概念的相似度最大。

2.2 基于近似概念的推薦

為推薦更加準確，給出推薦置信度的定義如下：

定義8推薦置信度［12］。給定形式背景T=(G，M，R)，其中的一個概念C=(E，I)，x∈E，r(x，i)=0，則基于概念C向x推薦i的推薦置信度計算公式如下：

問題2 基于近似概念的推薦

輸入 評分形式背景O=(G，M，S)，近似概念集合SP，推薦閾值α。

輸出 推薦矩陣L。

約束條件 ?(E，I)∈SP，?u∈E，m∈M-I滿足向u推薦m的用戶數量在該概念的外延長度中所占比例不低于α。

優化目標 max(F1)。

約束條件表示向用戶進行推薦時，外延中擁有待推薦項目的用戶數量應大于推薦閾值；優化目標為推薦時的F1 值最大化，以達到更好的推薦效果。

3 方案與算法設計

本章針對上述問題，給出了相應的算法方案以及偽代碼描述，最后對算法的復雜度進行了分析，并給出了一個算法運行實例。

將遺傳算法引入概念生成，需要對交叉、選擇和變異算子根據算法方案進行重新定義。

定義9交叉算子。設C1=(E1，I1)，C2=(E2，I2)是形式背景T中的兩個概念，且E1∩E2≠?，交叉算子cross 的計算為：

式（6）對兩個概念的外延求交集，得到新外延后更新內涵。

定義10選擇算子。設P=(E，I)是形式背景T的一個近似概念，且u∈E，λ為外延相似度閾值，α為內涵閾值，β為外延閾值，SP為近似概念集合，選擇算子select 的計算式為：

滿足外延相似度閾值、外延個數和內涵個數的近似概念P被選中。

定義11變異算子。設P=(E，I)是形式背景T的一個近似概念，且u∈E，若u′滿足max(simM(u，u′))，則變異算子mutate 的計算為：

根據相似度為近似概念的外延添加新用戶。

3.1 近似概念集合生成算法

近似概念生成算法（ACGA）是在啟發式方法［12］生成的概念集合上進行操作，包含兩個子算法：算法1 對概念進行交叉和選擇運算，算法2 對概念進行變異和選擇運算。

啟發式算法以每個對象為代表，逐一添加屬性到內涵中，直至概念面積不再增加，生成了新概念。

算法1 對兩個概念進行交叉運算。SPC為變異運算概念候選集，SP為近似概念集合。首先在包含用戶u的概念集合Cu（Cu?CR）中選取兩個概念Ci、Cj，對其外延取交集，見算法第4）行。接著，根據取交集得到的用戶集合E來更新內涵，得到I，見算法第5）行。若P滿足外延相似度大于Ci、Cj外延相似度的最小值且其內涵與外延長度均滿足閾值，則存入SP；否則，將其存入SPC中進行下一步操作。

算法2 對算法1 得到的變異運算候選集進行變異操作。第3）行表示對形式背景中的對象按用戶相似度降序排列并存入Du。向P′的外延依次添加Du中的用戶u′，見算法第5）～7）行。每添加一個用戶計算一次外延相似度，見算法第10）行。若外延長度達到閾值或外延相似度不再增加，則存入SP。

3.2 基于近似概念集合的推薦算法

基于近似概念集合的推薦算法（Recommendation method based on Approximate Concept Set，RACS）是基于所有包含用戶u的近似概念，向用戶u推薦其未擁有的項目。第5）行表示對于u未擁有的項目m，若基于近似概念P得到的推薦置信度大于推薦閾值γ，則向用戶u給出對于項目m的推薦。

3.3 時間復雜度分析

下面對算法1、算法2 進行時間復雜度分析。假定形式背景的規模為n×m，即其中有n個對象、m個屬性。在算法1 中，對兩個概念外延進行交叉操作時，最壞的情況就是參與交叉的兩個概念的外延長度均為n，因此交叉操作的時間復雜度為O(n3)；算法2 中變異操作的最壞情況就是對一個長度為n的外延的每一個位置都進行變異，則其時間復雜度為O(n2)；算法3 中利用近似概念為每一個用戶進行推薦的時間復雜度為O(n2m)，則算法的總時間復雜度為O(n3+n2m)。但實際應用中屬性個數小于對象個數，包含相同對象的概念數遠小于n，因此算法的時間復雜度小于O(n3)。

3.4 運行實例

下面以表2 所示的形式背景為例，描述針對用戶u2的近似概念生成以及推薦過程。其中外延閾值β=4，推薦閾值γ=0.5。

在表2 所示的形式背景中，以啟發式方法為每個用戶生成相應的概念，u2參與生成的其中兩個概念分別為C1=({u2，u3，u4}，{m0，m3})，C2=({u2，u4，u7}，{m0，m2，m6})。首先對C1和C2的外延求交集，得到E′={u2，u4}，接著根據E′更新內涵，得到I′={m0，m2，m3，m6}，由此得到用戶u2的一個候選 近似概念P=({u2，u4}，{m0，m2，m3，m6})；接下來計算P的外延相似度simP(u2)=1.5，而=1.5，=1.9，近似概念P滿足相似度不小于C1或C2，但由于概念P的外延長度小于外延閾值，因此需對其進行變異操作。按照用戶相似度降序排序，首先向P的外延E中添加1 號用戶，得到E={u1，u2，u4}，由此得到內涵I={m2}，此時P=({u1，u2，u4}，{m2})，且計算可得simP(u2)=2；繼續向E中添加9 號用戶，得到E={u1，u2，u4，u9}，由此得到I={m2}。此時P=({u1，u2，u4，u9}，{m2})，計算可得simP(u2)=2.33；若再繼續向E中添加用戶，得到的內涵長度將變為0，因此停止添加。至此，得到用戶u2的一個近似概念P=({u1，u2，u4，u9}，{m2})。重復上述過程可得到每一個用戶的近似概念。

以近似概念P向用戶u2推薦m1為例描述推薦過程。在概念P中，用戶u2的鄰居用戶為u1、u4、u9，其中用戶u1、u4觀看過電影m1，因此cfP(u2，m1)=0.67，大于推薦閾值，因此向u2推薦m1。

4 實驗與結果分析

4.1 實驗數據集

實驗數據集采用ML-100K（Movielens-100K）、ML-1M（Movielens-1M）、EachMovie、Jester，以及它們的抽樣數據集，并在實驗中將每一個數據集都劃分為訓練集及測試集兩個部分，其中80%數據作為訓練集，20%數據作為測試集。表3 是四個數據集的詳細信息。

表3 實驗數據集Tab.3 Experimental datasets

4.2 推薦效果評價指標

在本文中對推薦效果的評價主要采用精確度、召回率以及F1 三個值作為指標。

精確度［25］表示預測為正的樣本中真正為正樣本的數目，其計算式為：

其中：TP表示預測為正，實際也為正的樣本數；FP表示預測為正，實際為負的樣本數。

召回率［25］表示樣本整體中正樣本被預測為正的數目，其計算式為：

其中：FN表示預測為負、實際為正的樣本數。

F 值［26］是將精確度與召回率綜合評價的一個指標，其計算式為：

當α=1 時，F 值即為F1 值。

4.3 與GRHC、KNN以及PMF的對比

為驗證ACGA 推薦時的有效性，在7 個抽樣數據集上與GRHC 算法以及K最近鄰（K-Nearest Neighbor，KNN）算法進行了對比。由于ACGA 在初始概念集合上進行一輪遺傳運算與多輪遺傳迭代得到的近似概念數量不變，后者時間復雜度高，因此本文ACGA 僅進行一輪遺傳操作。在抽樣數據集上的對比實驗結果如表4 所示。

表4 ACGA與GRHC算法以及KNN算法在抽樣數據集上的對比Tab.4 Comparison of ACGA，GRHC algorithm and KNN algorithm on sampling datasets

從表4 可以看出，在以上7 個抽樣數據集中，ACGA 的召回率在大部分抽樣數據集上高于GRHC 以及KNN 算法；在精確度方面，ACGA 在ML-100K 的兩個抽樣數據集上優于GRHC 以及KNN 算法，在其余幾個抽樣數據集上持平或略差于GRHC 以及KNN 的效果；在F1 方面，ACGA 基本與GRHC以及KNN 算法持平，甚至優于其余兩個算法。因此由遺傳算法生成的近似概念在推薦過程中起到了提升推薦效果的作用。

另外，在ML-100K 和ML-1M 的完整數據集上對比了ACGA 與GRHC 算法、KNN（k=3）以及概率矩陣分解（Probabilistic Matrix Factorization，PMF）算法［27-28］的推薦效果，見表5。PMF 算法在矩陣分解算法的基礎上融入了概率論相關知識，以概率來預測用戶對項目的評分。

如表5 所示，ACGA 在兩個數據集上均較GRHC 的推薦效果有一定幅度的提升，證明了近似概念的有效性；對比基線算法，ACGA 精確度高于PMF 以及KNN，分別提升了57%和12%，召回率僅次于KNN，較PMF 提升了104%，F1 值與KNN 基本持平，較PMF 提升了78%。

表5 ACGA與其他算法在完整數據集上的對比Tab.5 Comparison of ACGA and other algorithms on complete datasets

5 結語

本文提出基于遺傳算法的近似概念構造算法，并將近似概念用于推薦過程。通過對概念的交叉、選擇與變異操作，得到外延相似度高的近似概念，以提高推薦時的準確性。本文提供了一種利用近似概念進行推薦的方案，發揮了近似概念中包含的有價值信息的作用，豐富了概念集合所包含的信息。目前的研究中近似概念生成時的約束條件以及交叉、變異方案還較單一，不利于生成更多的近似概念；另外在近似概念相似度計算時僅利用了評分形式背景，對于屬性的類別等信息未加以利用；最后推薦時僅在二值的基礎上進行推薦置信度的計算，未利用評分信息。這些問題在今后的研究當中都可繼續深入。