劉忠慧,鄒 璐,楊 梅,閔 帆,2+
1.西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,成都 610500
2.西南石油大學(xué) 人工智能研究院,成都 610500
形式概念分析[1](formal concept analysis,F(xiàn)CA)是一種針對(duì)形式背景的數(shù)據(jù)分析和規(guī)則提取方法,常用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、知識(shí)發(fā)現(xiàn)等[2-5]領(lǐng)域。形式背景表示了對(duì)象、屬性以及它們之間的二元關(guān)系,能描述電子商務(wù)中的用戶消費(fèi)記錄或偏好,因此近幾年FCA 被引入到推薦系統(tǒng)領(lǐng)域[6-8]。
當(dāng)前,基于FCA 的推薦思路是先構(gòu)建概念格,然后根據(jù)概念間的層次關(guān)系計(jì)算用戶或項(xiàng)目的鄰域。然而概念格構(gòu)造效率低,幾乎與形式背景的規(guī)模呈指數(shù)關(guān)系[9-10]。為降低構(gòu)造的復(fù)雜度,研究者提出了構(gòu)建概念格的優(yōu)化算法,如基于統(tǒng)計(jì)的概念格構(gòu)造[11]、基于剪枝的概念格構(gòu)造[12]等?;跇?shù)結(jié)構(gòu)的增量算法[13]在構(gòu)造概念格時(shí),通過(guò)快速定位父子節(jié)點(diǎn)的范圍,縮短搜索時(shí)間,但在數(shù)據(jù)稀疏時(shí)改進(jìn)效果不明顯。形式背景分解法[14-16]利用并行計(jì)算,加速子概念格的構(gòu)造,但在概念格合并時(shí)花費(fèi)的時(shí)間較長(zhǎng),也未解決構(gòu)造效率低的問(wèn)題。
基于概念格的推薦[7-8]通常只考慮概念中用戶的相互關(guān)系,而概念間的層次關(guān)系僅用來(lái)尋找鄰居。因此只要保證概念集合能正確表示形式背景的信息,推薦效果就有望得到保障,故概念格的構(gòu)造對(duì)于推薦應(yīng)用不是必要的步驟。
本文提出一種不構(gòu)建概念格的方案,使用啟發(fā)式算法挖掘重要概念進(jìn)行推薦,從根本上解決效率問(wèn)題。
新方案包含兩個(gè)階段:第一階段是概念構(gòu)造,即生成一系列內(nèi)涵與外延均較大的概念,同時(shí)滿足它們對(duì)整個(gè)對(duì)象集合的覆蓋;第二階段是組推薦,即利用概念本身的群組特性進(jìn)行推薦。
在抽樣數(shù)據(jù)集和MovieLens 上,對(duì)比了本文算法與兩類不同的推薦方法。結(jié)果表明,本文算法的概念生成效率高,推薦效果比基于概念格的推薦方法好,與KNN(K-nearest neighbor)算法[17]效果相當(dāng)。
本章主要介紹FCA 的相關(guān)概念和知識(shí),以及兩類常見(jiàn)推薦系統(tǒng)。
定義1[1](形式背景)形式背景是一個(gè)三元組T=(O,A,R),其中O為對(duì)象集,A為屬性集,R為O和A之間的二元關(guān)系,O×A→R。對(duì)于r(x,a)=1,表示對(duì)象x擁有屬性a,也可以表示為xRa。
對(duì)象集X?O和屬性集B?A,分別定義運(yùn)算:
表1 是電影評(píng)分表轉(zhuǎn)化后的形式背景,記錄了10位用戶觀看7 部電影的情況。如果用戶ui(0 ≤i≤9)看過(guò)電影mj(0 ≤j≤6),則r(mi,mj)=1;反之r(mi,mj)=0。
Table 1 Exemple of formal context表1 一個(gè)形式背景的例子
定義2[18](形式概念)在形式背景T=(O,A,R)中,令E?O,I?A,當(dāng)二元組(E,I) 滿足E*=I,I*=E時(shí),則稱C=(E,I)為形式概念,簡(jiǎn)稱概念。E(C)表示概念的外延,I(C)表示概念的內(nèi)涵,簡(jiǎn)寫(xiě)為E和I。
從表1 中可得一個(gè)概念C=({u1,u5},{m1,m4}),其外延為u1、u5,內(nèi)涵為m1、m4。
定義3[18](偏序關(guān)系)設(shè)C1=(E1,I1),C2=(E2,I2)是T的兩個(gè)概念。若C1≤C2?E1?E2?I2?I1,且不存在概念C3使得C1≤C3≤C2,則可稱C2是C1的父概念,C1是C2的子概念,稱“≤”為概念間的偏序關(guān)系。
定義4[18](概念格)形式背景中所有概念通過(guò)概念間的偏序關(guān)系構(gòu)成的格L(O,A,R)稱為概念格。
Hasse 圖是概念格的圖形表示方式,按照父概念在上,子概念在下的原則,用線段把父子概念連接起來(lái)。圖1 為表1 的概念格,共33 個(gè)概念,其中接近50%的概念外延或內(nèi)涵只有一個(gè)元素。
目前常見(jiàn)有兩類推薦系統(tǒng),分別是基于鄰域的推薦系統(tǒng)和基于群組的推薦系統(tǒng)。
基于鄰域的推薦系統(tǒng)由Zaier等人[19]在2007 年提出,其核心思想是通過(guò)相似度計(jì)算,找到相關(guān)鄰域,利用鄰域信息進(jìn)行推薦。主要分為基于用戶的推薦[20]和基于項(xiàng)目的推薦[21],前者是根據(jù)鄰居用戶的喜好進(jìn)行推薦,后者是根據(jù)項(xiàng)目的相似度進(jìn)行推薦?;诟拍罡竦耐扑]屬于鄰域推薦,它通過(guò)概念間的偏序關(guān)系來(lái)尋找目標(biāo)用戶的鄰居。
組推薦系統(tǒng)(group recommender system)由Garcia等人[22]在2012 年提出,推薦對(duì)象是整個(gè)群組。組推薦系統(tǒng)統(tǒng)計(jì)所有群組成員的偏好,通過(guò)共享和交互縮小群組成員之間的偏好差異,融合得到群組偏好,最后利用群組偏好進(jìn)行推薦[23]。
本文結(jié)合FCA 和組推薦思想,根據(jù)用戶所在的群組,以及群組成員的偏好,實(shí)現(xiàn)用戶的相互推薦。
概念由用戶集和項(xiàng)目集組成,用戶集中的成員具有相同的偏好(概念內(nèi)涵),從協(xié)同過(guò)濾[24]的角度可知,他們之間可以進(jìn)行相互推薦。
利用概念進(jìn)行推薦,需要解決兩個(gè)子問(wèn)題:一是概念集合的構(gòu)建;二是基于概念集合的組推薦。
問(wèn)題1 概念集合的構(gòu)建
輸入:形式背景T=(O,A,R)。
輸出:概念集C 。
約束條件1:∪(E,I)∈CE=O。
約束條件2:?(E,I)∈C,|I|≥α。
優(yōu)化目標(biāo):min|C|。
Fig.1 Hasse of table 1圖1 表1 的Hasse圖
其中,約束條件1 表示概念集覆蓋了T的所有對(duì)象,保證任一對(duì)象至少屬于一個(gè)概念,為后一階段的推薦做準(zhǔn)備。約束條件2 表示所挖掘概念的內(nèi)涵規(guī)模不小于閾值α,從推薦系統(tǒng)的角度,僅當(dāng)用戶之間擁有足夠多的共同項(xiàng)目,所形成的群組才有意義。優(yōu)化目標(biāo)為最小化概念集合,其目的是獲得更簡(jiǎn)潔的表示,以提高模型的泛化性。
問(wèn)題2 基于概念集合的組推薦
輸入:形式背景T=(O,A,R),概念集C,推薦閾值β。
輸出:推薦矩陣L。
約束條件:?(E,I)∈C,?u∈E,m∈A且r(u,m)=0,滿足E中至少有β個(gè)對(duì)象向u推薦m。
優(yōu)化目標(biāo):max(F1)。
將概念用戶集視為一個(gè)群組,約束條件表示向目標(biāo)用戶推薦項(xiàng)目,需要滿足組內(nèi)至少達(dá)到推薦閾值的用戶有m偏好。優(yōu)化目標(biāo)是最大化推薦F1 指標(biāo),實(shí)現(xiàn)高質(zhì)量的推薦。
KNN 算法是借助k個(gè)近鄰對(duì)象進(jìn)行推薦,本文算法則基于高質(zhì)量概念。根據(jù)問(wèn)題1 的優(yōu)化目標(biāo),應(yīng)盡量挖掘?qū)ο蠖嗟母拍?。而為使推薦效果更好,這些對(duì)象需具有更強(qiáng)的共同愛(ài)好,即概念的內(nèi)涵更大。為此,定義了衡量概念質(zhì)量的指標(biāo)。
定義5(概念面積)形式概念C=(E,I)的面積為:
其中,|·|表示集合的基數(shù)。
由定義5 可知概念面積由外延和內(nèi)涵的規(guī)模共同決定。外延規(guī)模大表示對(duì)象的鄰居多,穩(wěn)定性強(qiáng);內(nèi)涵規(guī)模大表示對(duì)象群組相似度高,推薦成功率高?;诖?,給出強(qiáng)概念定義如下。
定義6(強(qiáng)概念)(E,I)為x∈E的強(qiáng)概念,當(dāng)且僅當(dāng)不存在x∈E′,Area(E,I)<Area(E′,I′)且|I|≥α,其中(E′,I′)為概念,α為內(nèi)涵閾值。
例1 構(gòu)建表1 中u5的強(qiáng)概念,α為2。通過(guò)計(jì)算,共3 個(gè)概念,C1=({u2,u3,u4,u5,u7,u9},{m0}),C2=({u4,u5},{m0,m1}),C3=({u5},{m0,m1,m4})。根據(jù)式(3)可知C2的面積為4,且滿足強(qiáng)概念的條件,將保留用于第二階段的推薦。
根據(jù)問(wèn)題2 的優(yōu)化目標(biāo),保證推薦質(zhì)量,定義推薦置信度如下。
定義7(推薦置信度)給定形式背景T=(O,A,R),概念C=(E,I),對(duì)象x∈E,屬性i∈A-I,r(x,i)=0 。則基于C向x推薦i的置信度為:
由式(4)可知置信度由對(duì)象群組每個(gè)對(duì)象的推薦綜合決定。
本章采用啟發(fā)式方法構(gòu)造概念來(lái)解決問(wèn)題1,基于概念進(jìn)行組成員推薦來(lái)解決問(wèn)題2。啟發(fā)式概念構(gòu)造的組推薦算法(group recommendation based on heuristic concept set,GRHC)由3 個(gè)子算法構(gòu)成:算法1構(gòu)建一個(gè)對(duì)象代表的強(qiáng)概念,算法2構(gòu)建基于形式背景的強(qiáng)概念集合,算法3 利用概念集合進(jìn)行組推薦。
圖4為各方案擾動(dòng)能量隨時(shí)間的演變。由圖4d可知,平均來(lái)講,擾動(dòng)能量的增長(zhǎng)據(jù)降水量調(diào)整方案最大,其次為傳統(tǒng)BGM方案,另外兩種調(diào)整方案效果相對(duì)較弱。據(jù)降水量調(diào)整方案各層分開(kāi)來(lái)看,模式第8層擾動(dòng)能量在預(yù)報(bào)18 h后穩(wěn)定維持在較大數(shù)值(圖4a),模式第16層(約500 hPa)增長(zhǎng)飽和時(shí)間則提前到14 h左右(圖4b),而在模式第25層(約200 hPa),擾動(dòng)能量在預(yù)報(bào)18 h之后大幅度下降(圖4c)。該方案24 h預(yù)報(bào)擾動(dòng)能量在中低層增長(zhǎng)到某一數(shù)值后穩(wěn)定維持,說(shuō)明集合預(yù)報(bào)對(duì)中低層影響較大,能較好地作用于控制預(yù)報(bào)誤差,從而最有可能改善預(yù)報(bào)效果。
采用啟發(fā)式方法構(gòu)建形式概念主要基于兩個(gè)原因:其一,不是所有概念都對(duì)推薦有用。在極端情況下,某些概念的外延集合只有一個(gè)對(duì)象,或者內(nèi)涵集合只有一個(gè)屬性。這類概念包含的信息較少,不利于推薦。其二,不同的概念對(duì)推薦的貢獻(xiàn)程度不同,群組的規(guī)模和對(duì)象間的相似度決定了推薦的準(zhǔn)確度。因此,挖掘強(qiáng)概念是本文的關(guān)鍵,通過(guò)設(shè)計(jì)針對(duì)性的啟發(fā)式方法可以達(dá)到此目的。
啟發(fā)式方法構(gòu)建形式概念,通過(guò)逐一添加對(duì)象代表的屬性作為候選概念的內(nèi)涵,同時(shí)更新候選概念的外延(見(jiàn)算法1 的第7 行),計(jì)算概念的面積并判斷內(nèi)涵大小是否滿足閾值(見(jiàn)算法1 的第10~第16行),最終獲得對(duì)象代表的強(qiáng)概念。
為了簡(jiǎn)化算法表示,做如下定義。
定義8(對(duì)象的屬性集合)形式背景T=(O,A,R),任意對(duì)象u∈O,對(duì)象u的屬性集合記為:
對(duì)象集合U?O的屬性集合記為:
定義9(屬性的對(duì)象集合)形式背景T=(O,A,R),任意屬性i∈A,屬性i的對(duì)象集合記為:
屬性集合I?A的對(duì)象集合記為:
算法1 構(gòu)建強(qiáng)概念
算法2 按照屬性個(gè)數(shù)將對(duì)象有序排列(見(jiàn)第2行),依次選出對(duì)象代表,調(diào)用算法1 進(jìn)行強(qiáng)概念構(gòu)造(見(jiàn)第4 行)。從對(duì)象代表集合中刪除新概念中的對(duì)象(見(jiàn)第6 行),再選代表繼續(xù)下一個(gè)強(qiáng)概念的構(gòu)造,直到所有對(duì)象都被包含在概念集合C 中。
本文組推薦算法是基于算法2 得到的概念集合。一個(gè)概念中的用戶具有共同的偏好和興趣。組推薦方法通過(guò)統(tǒng)計(jì)用戶群組在某個(gè)項(xiàng)目上的喜好程度,以決定是否推薦該項(xiàng)目給同一群組的其他用戶,也就是計(jì)算基于概念向用戶推薦某個(gè)項(xiàng)目的置信度(見(jiàn)算法3 的第3~6 行)。
算法3 基于概念集合的組推薦算法
下面分析算法1 和算法2 的復(fù)雜度。假設(shè)形式背景由m個(gè)對(duì)象和n個(gè)屬性組成,則任一個(gè)對(duì)象最多有n個(gè)非零屬性。在構(gòu)建其概念時(shí),選擇一個(gè)屬性作為內(nèi)涵,最多比較m-1 次。因此最壞情況下構(gòu)建一個(gè)強(qiáng)概念的時(shí)間復(fù)雜度為O(mn),構(gòu)建該形式背景下強(qiáng)概念集合時(shí)間復(fù)雜度為O(m2n)。
實(shí)際情況下,對(duì)象擁有的屬性遠(yuǎn)遠(yuǎn)小于n,因此構(gòu)建強(qiáng)概念集合所花的時(shí)間遠(yuǎn)小于O(m2n)。對(duì)比構(gòu)建概念格的時(shí)間復(fù)雜度O(m2n)[9],GRHC 算法的優(yōu)勢(shì)較為明顯。
根據(jù)表1 的形式背景,下面描述GRHC 算法的運(yùn)行實(shí)例。其中,設(shè)置內(nèi)涵閾值為2,推薦閾值為0.5。
構(gòu)造以u(píng)4為代表的強(qiáng)概念。oca(u4)={m0,m1,m2,m3,m6},將擁有用戶數(shù)最多的m0選中為備選概念的內(nèi)涵,獲得外延{u2,u3,u4,u5,u7,u9},備選概念面積為6;將u4余下項(xiàng)目依次與內(nèi)涵結(jié)合,可得同時(shí)擁有m0、m2的用戶數(shù)最多;添加m2到內(nèi)涵中,并更新外延為{u2,u4,u7,u9},此時(shí)備選概念面積為8,大于前一個(gè)概念的面積;根據(jù)上述選擇策略,在({u2,u4,u7,u9},{m0,m2})的基礎(chǔ)上繼續(xù)構(gòu)造,直到同時(shí)滿足內(nèi)涵基數(shù)不低于2,概念面積最大。最終得到以u(píng)4為代表的強(qiáng)概念C=({u2,u4,u7},{m0,m2,m6})。
基于概念C為u4進(jìn)行組推薦。u4的組成員為u2和u7,推薦候選項(xiàng)為m4、m5。根據(jù)表1 可知,u2推薦m4,u7無(wú)推薦。由式(4)可得基于C向u4推薦m4、m5的置信度分別為0.5 和0,因此滿足推薦閾值m4被推薦給u4。
實(shí)驗(yàn)數(shù)據(jù)集為MovieLens,包含943 個(gè)用戶和1 682 部電影,共10 萬(wàn)條評(píng)分?jǐn)?shù)據(jù)。實(shí)驗(yàn)對(duì)比了概念格推薦方法、KNN 推薦方法。由于概念格無(wú)法在MoviesLens 上快速建立,因此實(shí)驗(yàn)先使用抽樣數(shù)據(jù)集,對(duì)比GRHC 算法、概念格算法和KNN 算法,驗(yàn)證算法效率;然后GRHC 算法在MovieLens 中進(jìn)行不同內(nèi)涵閾值和推薦閾值的實(shí)驗(yàn),討論其對(duì)概念生成、概念集合規(guī)模的影響。
本文采用推薦系統(tǒng)常用的評(píng)價(jià)指標(biāo):精確度(precision)、召回率(recall)和F1-measure。令L(O)為算法對(duì)所有用戶的推薦矩陣,T(O)為所有用戶在測(cè)試集中的行為矩陣。則推薦結(jié)果的精確度為:
推薦結(jié)果的召回率為:
綜合評(píng)價(jià)指標(biāo)F1-measure為:
將GRHC 算法和KNN 以及概念格推薦算法進(jìn)行對(duì)比。與KNN 算法對(duì)比是為了驗(yàn)證GRHC 的正確性和推薦的有效性,而對(duì)比概念格推薦算法是由于兩者都基于FCA。
KNN 推薦算法:利用相似度方法找到與目標(biāo)用戶最為相似的前k個(gè)鄰居用戶,再根據(jù)鄰居用戶的偏好信息來(lái)進(jìn)行推薦預(yù)測(cè)。相似度計(jì)算一般采用杰卡德相似度,其計(jì)算公式如下:
其中,A、B為用戶集合。
概念格推薦算法[7]:采用漸進(jìn)式算法構(gòu)建概念格,根據(jù)概念間的父子關(guān)系找到目標(biāo)用戶所在概念的兄弟概念與子概念,以此來(lái)得到候選項(xiàng)目列表。然后根據(jù)全局偏好度的計(jì)算結(jié)果,推薦與目標(biāo)用戶所擁有項(xiàng)目最為相似的前k個(gè)項(xiàng)目。用戶u對(duì)候選項(xiàng)目i′的全局偏好度計(jì)算公式如下:
其中,I為用戶u的項(xiàng)目集合,Ui為與項(xiàng)目i有關(guān)的用戶集合,Ui′為與項(xiàng)目i′有關(guān)的用戶集合。
從MovieLens 隨機(jī)抽樣4 組大小為230×420 作為實(shí)驗(yàn)數(shù)據(jù)集,其中每個(gè)數(shù)據(jù)集劃分80%訓(xùn)練,20%測(cè)試。設(shè)置推薦閾值為0.5,內(nèi)涵閾值為2。實(shí)驗(yàn)中,將對(duì)象代表按擁有的屬性個(gè)數(shù)升序、降序以及原始序3 種情況分別驗(yàn)證GRHC 算法;概念格算法選取全局偏好度最大的前10 個(gè)項(xiàng)目予以推薦;KNN 算法選取與目標(biāo)用戶最為相似的前3 個(gè)鄰居用戶進(jìn)行偏好信息推薦。
各算法的時(shí)間、精確度、召回率和F1 值如表2 所示,其中GRHC-D 表示對(duì)象代表為降序選擇,GRHC-A 表示對(duì)象代表為升序選擇,GRHC 表示對(duì)象代表按原序選擇。表3 對(duì)比了在相同數(shù)據(jù)集下,GRHC 算法和概念格推薦算法生成的概念個(gè)數(shù)和運(yùn)行的時(shí)間。
Table 2 Experimental results on sampled datasets表2 抽樣數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果
Table 3 Comparison of GRHC algorithm and concept lattice algorithm表3 GRHC 算法與概念格算法對(duì)比
實(shí)驗(yàn)結(jié)果表明,不管采用何種對(duì)象代表選擇策略,GRHC 算法生成的概念個(gè)數(shù)和運(yùn)行時(shí)間均遠(yuǎn)低于概念格算法;從圖2 可以看出,在精確度、召回率和F1上,GRHC 算法明顯優(yōu)于概念格推薦算法,略高于KNN(k=3)算法。這體現(xiàn)了GRHC 生成的概念數(shù)雖較少,通過(guò)半數(shù)推薦約束,最終推薦效果能保持在較好的水平,從而證明強(qiáng)概念在具有泛化性的同時(shí)還有實(shí)效性。
隨機(jī)劃分MovieLens 數(shù)據(jù)集80%訓(xùn)練,20%測(cè)試,推薦閾值為0.5,GRHC 算法內(nèi)涵閾值范圍為1~8,重復(fù)100 次,取這100 次結(jié)果的平均值作為最終結(jié)果,如表4 所示。
Table 4 Experimental results of GRHC algorithm on MovieLens表4 GRHC 算法在MovieLens上的實(shí)驗(yàn)結(jié)果
Fig.2 Experimental results of GRHC compared to other algorithms圖2 GRHC 對(duì)比其他算法的實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)結(jié)果表明,GRHC 算法生成的概念個(gè)數(shù)與內(nèi)涵閾值呈正相關(guān),而對(duì)象代表的有序選擇將減少生成的概念個(gè)數(shù)。當(dāng)內(nèi)涵閾值為4,概念數(shù)在200~300之間時(shí),GRHC 算法的推薦效果較好,如圖3 所示。當(dāng)內(nèi)涵閾值增大時(shí),推薦效果隨之降低,這說(shuō)明了概念的泛化性,更有利于推薦模型的構(gòu)成。在Movie-Lens 數(shù)據(jù)集上GRHC 算法的推薦效果略低于KNN 算法(k=3)的推薦效果(F1 ≈0.25)。
Fig.3 Impact of intention threshold on F1圖3 內(nèi)涵閾值對(duì)F1 的影響
本文提出了一種基于概念集合的組推薦算法。在概念構(gòu)造時(shí),采用了啟發(fā)式方法快速獲得滿足內(nèi)涵閾值的強(qiáng)概念,確保每個(gè)概念對(duì)推薦有用,同時(shí)利用概念中對(duì)象共同的特性進(jìn)行相互推薦。解決了如何設(shè)計(jì)啟發(fā)式構(gòu)建信息,從何處開(kāi)始概念的構(gòu)建以及優(yōu)化內(nèi)涵閾值等問(wèn)題。為形式概念分析方法提供了一種高效的推薦解決方案。目前的研究還缺乏對(duì)概念中項(xiàng)目組的信息挖掘,當(dāng)前只考慮了對(duì)象群組的關(guān)聯(lián);另外在推薦應(yīng)用時(shí),僅考慮二值情況,未進(jìn)行評(píng)分預(yù)測(cè);最后數(shù)據(jù)集的粒度較單一,未引入電影和用戶信息等特征值,這些都將成為今后繼續(xù)研究和探討的問(wèn)題。