基于三支決策的組織關聯知識推送服務

張建華,劉 柯,葉建文

(鄭州大學 管理工程學院,鄭州 450001)

在知識經濟時代,知識的地位和作用有如資本之于工業經濟、土地之于農業經濟,已經上升為首要的生產要素。高效應用知識、實現其價值,成為廣受關注的話題。知識的價值實現依托于知識的傳播、應用、創新和服務,是組織進步和發展的重要驅動力。面對知識體量的快速增長,知識推送作為一項基礎性知識服務方式,可以有效解決廣大知識用戶的“知識迷向”問題,能夠促進組織內知識的傳播、共享與應用,確保知識價值的有效實現；同時,高效的知識推送亦能對組織的知識創新形成有效支持,從而為組織自身增益。

推薦技術是知識推送服務的基礎與核心。目前對推薦技術的研究主要包括4大類：

(1)協同過濾推薦算法基于“物以類聚,人以群分”的思想,利用用戶-項目行為矩陣計算用戶之間或項目之間的相似度實施知識推薦。它不考慮項目的具體內容以及用戶的具體興趣,是目前研究和應用最為廣泛的推薦算法,在電子商務、社交媒體等領域的應用中均取得了良好的效果；但該類方法存在冷啟動、評價稀疏等問題,且基于用戶評分的相似度計算方法亦存在主觀性過強的問題。

(2)基于內容的推薦算法主要利用項目相對客觀的內容信息,將用戶特征與項目特征匹配,從而為用戶推薦相似項目,推薦結果易解釋；但該類方法基于用戶以前喜歡的項目范疇,在一定程度上受限于用戶視野,不利于創新。

(3)基于數據挖掘的推薦主要表現為基于關聯規則的推薦。它根據用戶的偏好集產生關聯規則,進而根據關聯規則將新項目推薦給用戶[1]。此方法通過挖掘并利用關聯規則這一內隱知識產生用戶意想不到的結果；但關聯規則的發現耗時且有時難以理解,質量或難以保證。

(4)由于各類推薦算法兼具優缺點,在實踐中,人們常采用混合推薦算法[2]。該方法將兩種或兩種以上的推薦技術相融合,以此來彌補各算法的不足,從而優化推薦結果。目前常用的融合方式有加權、變換、混合、特征組合、層疊、特征擴充以及元級別融合等。

王道平等[3]基于協同過濾算法,綜合考慮用戶興趣和項目屬性因素,利用內容相似度解決了用戶-項目評分矩陣的數據稀疏性等問題。周明建等[4]提出基于屬性相似度的知識推送算法,通過對用戶所瀏覽知識的屬性相似度進行分析得到用戶的興趣信息,然后將新知識與用戶興趣信息進行匹配,從而得到推薦結果。郭均鵬等[5]利用混合推薦策略,將基于內容的推薦與基于項目的協同過濾推薦技術相結合,從而克服冷啟動問題及用戶-項目評分矩陣稀疏性問題。然而,若只將基于內容的推薦算法與協同過濾算法相融合,因其只以知識相似性度量為基準對用戶實施推薦,推薦結果只能反映知識之間的相似性,卻未能兼顧知識間的關聯度。相似度低但關聯度高的知識有利于激發用戶的創新思維,而過于相似的知識對用戶而言因冗余而增加成本、耗費精力。由此,曲朝陽等[6]將知識關聯度與相似度相結合,共同作用于推薦結果、提高推薦質量。

成本是組織運營需要考慮的重要因素。大部分推薦算法都將推薦決策劃分為推薦和不推薦兩種,非此即彼、缺乏包容性,增大了因錯誤分類而產生的成本。在現實生活中,人們認知和解決問題常常基于一種三元思維。例如,將對某種觀點的態度劃分為接受、中立和拒絕,將過程控制劃分為事前、事中和事后,專家在論文評審過程中接收、拒稿或返修再審[7]。三支決策最早由YAO 提出[8]。作為符合人類認知規律的模型,已經應用于信息咨詢、管理決策、醫療和工程等多個領域并取得了良好成效[9]。Zhang等[10]兼顧學習成本和誤分類成本,把三支決策模型與隨機森林整合,建立了一個新的推薦系統,實驗證明應用三支決策產生的推薦成本低于傳統的二分法。Zhang等[11]提出了一個基于回歸的三支推薦模型,并尋找最優閾值來最小化推薦成本。葉曉慶等[12]考慮了推薦成本以及項目特征對用戶評分的影響,將三支決策思想和粒計算思想引入,從而提高了推薦質量并降低了推薦成本。

有鑒于此,本文以基于知識屬性的視圖相似度衡量知識間的相似度,以用戶偏好集為基礎,采用Apriori算法挖掘并利用關聯規則這一內隱知識衡量知識之間的關聯度,將兩者融合得到一種新的知識相關度模型,并據此預測評分。如此,不僅能緩解傳統協同過濾算法的數據稀疏問題,也將知識關聯度考慮在內,可更好地滿足組織知識推送需求。而后,在推薦決策中引入三支決策,提出基于三支決策的組織關聯知識推送算法,并用Movie Lens數據集檢驗了該算法的效果。

1 相關定義

1.1 知識視圖相似度

針對知識多樣性,根據其所屬領域、可解決問題類型等賦予知識不同的屬性,從而依據知識屬性集進行知識建模,實現組織對知識的統一管理。

本文通過基于計算知識屬性的視圖相似度來表征知識間的相似度,為此構建如表1所示的知識-屬性矩陣Kattr。

表1 知識屬性矩陣

其中,aij表示知識i是否具有屬性j,其取值如下所示：

基于知識屬性文本特征和集合性,選用Jaccard相似系數表征兩條知識之間的屬性相似度,相應的計算公式為

基于每條知識所具有屬性的不同將知識加以區分,并兼顧不同屬性對知識區分度的作用差異,通過信息熵的大小為屬性賦權,得到信息加權的Jaccard知識視圖相似度[13]：

式(3)中：w(Ak)為屬性Ak的信息熵；p(Ak)為屬性Ak出現的概率,其計算公式如式(4)所示。其中：為知識的總數目；n(Ak)為屬性Ak出現的次數。

1.2 知識關聯度

通過知識視圖相似度可以辨別相似的知識,但相似的知識對于組織成員的效用有限,因為不完全相似但存在關聯的知識反而有利于拓展組織成員的思維,進而激發他們的創新行為,提高知識的利用價值。因此,基于組織成員的知識偏好集,本文基于經典的關聯規則挖掘算法——Apriori的基本原理,采用改造后的算法挖掘兩兩知識之間的關聯規則,并以關聯規則的置信度表示知識之間關聯度的大小。

算法步驟：①遍歷所有用戶知識偏好集,對每條知識進行計數得到候選項集C1,將支持度計數等于0的知識項剔除,得到頻繁1項集；②再次掃描數據集,計算所有候選2項集的支持度計數,設置2項集支持度閾值c,將支持度計數小于閾值的候選集的置信度設置為0；③計算所有候選2項集的置信度conf,建立知識關聯度矩陣,并將空缺值補為0；④由于關聯規則知識i→知識j以及知識j→知識i的意義不同,其各自的置信度conf(i,j)和conf(j,i)亦不同,故知識i、j之間的關聯度可融合計算如下所示：

1.3 協同過濾算法

協同過濾算法以用戶-項目評分矩陣為基礎,自提出以來就被廣泛應用并取得了良好效果。其按原理不同可劃分為兩類：基于用戶的協同過濾算法和基于項目的協同過濾算法。其中,前者從計算用戶相似度出發,根據與目標用戶相似的近鄰用戶對項目的評分預測目標用戶對某項目的評分；后者則以計算項目相似度為起點,根據與目標項目相似的、目標用戶已評分的近鄰項目預測目標用戶對目標項目的評分[14]。知識推送系統的作用在于依據用戶日常瀏覽的知識范疇為用戶推送相關知識,故選取基于項目的協同過濾算法,依據組織成員的歷史知識偏好為其推送相關知識。

1.4 三支決策

三支決策是對概率粗糙集的語義擴展,是粗糙集理論和決策理論的一種融合,為粗糙集理論在實際決策問題中的應用建立起一座橋梁[9]。絕大部分推薦算法都只有推薦和不推薦兩種推薦決策。顯然,這種二支決策模型(見表2)的決策劃分非此即彼、缺乏包容性,增大了因錯誤分類而產生的成本。

表2 二支推薦模型

有鑒于此,基于對知識推送成本的考慮,將已有基于決策粗糙集的三支決策模型引入,以此建立本文的知識推送模型,如表3所示。該模型基于用戶對知識的兩種偏好,根據對應決策區域劃分的“正域”“邊界域”和“負域”分別定義了“推送”“延遲推送”和“不推送”3種知識推送決策。相較于二支推薦模型,本文的知識推送模型增加了在掌握信息不充分時應采取的延遲策略,以此來降低因錯誤分類進而采取錯誤決策而導致的推送成本。

表3 三支推送模型

在表2、3中,P(X|[x])表示任何一個實體在屬于等價類[x]的條件下,屬于類別X的條件概率。

2 基于三支決策的關聯知識推送

基于三支決策的關聯知識推送主要包括兩個部分：①基于項目最近鄰的協同過濾的關聯知識評分預測。首先計算知識之間的相關度,然后采用傳統的基于項目的協同過濾算法根據最近鄰預測用戶評分。②三支知識推送決策。以所得的預測評分為基礎,根據基于決策粗糙集的三支決策模型實現三支知識推送。

2.1 基于協同過濾的關聯知識評分預測

考慮知識特性,本文改變傳統協同過濾推薦算法中依據用戶評分來計算項目之間相似度的思路,而是首先通過知識所具有的屬性計算知識之間的相似度,并采用關聯規則挖掘算法測度知識之間關聯度；然后,將兩者按最優融合系數加以融合,建立新的知識相關度指標,用它來衡量知識之間的關系；最后,以對知識的平均打分為基礎、以知識相關度為權重預測用戶對未評分知識的評分。

(1)知識相關度計算。在分別計算知識間視圖相似度和關聯度后,需對兩者進行融合得到新的指標——知識相關度。線性融合是融合的經典思路,其關鍵在于融合系數的確定。采用實驗研究方法,確定使得推薦結果誤差最小的融合系數,并通過下式計算得到兩兩知識之間的相關度：

式中：q為融合系數；similarity(i,j)是由式(2)得到的信息熵加權的知識視圖相似度,association(i,j)是由式(5)得到的知識關聯度。知識相關度矩陣Kcorr如表4所示。

表4 知識相關度矩陣

(2)尋找最近鄰。在尋找知識的最近鄰時,基于固定數量的鄰居原則,根據知識相關度矩陣Kcorr,選擇與每條知識相關度最大的前k條知識作為其最近鄰知識。

(3)預測評分。根據知識間相關度以及每條知識近的鄰知識的評分記錄,預測組織成員對未評分知識的評分,其計算公式為

2.2 三支知識推送模型

根據預測評分、知識推送成本,借助基于決策粗糙集的三支決策模型做出最后的知識推送決策。該模型包含3個部分：①基于用戶對知識的“有幫助”和“無幫助”兩種偏好,根據對應決策區域即用戶未觸及知識的“正域”“邊界域”和“負域”劃分,分別定義3種知識推送決策：推送(PP)、延遲推送(PB)和不推送(PN)；②根據誤分類成本和學習成本,建立一個如表5 所示的成本矩陣；③根據此成本矩陣,計算各決策區域的劃分閾值α和β。

表5 知識推送成本矩陣

基于用戶對知識的兩種偏好,用H表示用戶認為“有幫助”的知識的集合,用U表示用戶認為“沒有幫助”的知識的集合。如表5所示,不同決策行為對應不同的成本。如果一條知識被某用戶認為有幫助(H),則λPH、λBH和λNH表示對此知識采取推送(PP)、延遲推送(PB)和不推送(PN)3種決策對應產生的成本；如果一條知識被某用戶認為沒有幫助(U),則λPU、λBU和λNU表示對此知識采取不同的推送決策所產生的成本。

至此,對知識庫中的知識采取不同決策行為的期望成本為：

根據貝葉斯決策過程中的最小風險原則,可得如下區域劃分規則：如果CP≤CB且CP≤CN,則將知識x劃入正域；如果CB≤CP且CB≤CN,則將x劃入邊界域；如果CN≤CP且CN≤CB,則將x劃入負域。

基于知識用戶對知識的兩種偏好劃分,則有

在知識推送過程中,誤分類成本一般比延遲推送所需的學習成本要高,而學習成本一般比正確推送的成本要高。將屬于H的知識x劃分到正域的損失小于或等于將x劃分到邊界域中的損失,并且這兩種損失都嚴格小于將x劃分到負域的損失；類似地,屬于U的知識x同理。這符合三支決策的一個基本前提條件[8],即：

基于條件式(9)、(10),可將區域劃分規則式(8)重新表達為：如果P(H|[x])≥α且P(H|[x])≥γ,則將知識x劃入正域；如果P(H|[x])≤α且P(H|[x])≥β,則將知識x劃入邊界域；如果P(H|[x])≤β且P(H|[x])≤λ,則將知識x劃入負域。

由式(8)～(10)及區域劃分規則,可得α、β和γ的表達式為：

式中,γ為二支推送決策中的劃分閾值。

同時,根據決策粗糙集,還需考慮另一條件：

至此可得0≤β＜α≤1。前述區域劃分規則可進一步表達為：如果P(H|[x])≥α,則將知識x劃分入正域；如果β＜P(H|[x])＜α,則將知識x劃入邊界域；如果P(H|[x])≤β,則將知識x劃入負域。

若要將用戶未觸及的知識劃分決策區域,除了需要劃分閾值外,還需知道用戶認為某知識“有幫助”的概率pu,i。預測評分的高低反映了用戶對知識評價的高低,用戶對某知識的評分越高,表明此知識對用戶有幫助的概率越大。將預測評分轉化為用戶認為某知識有幫助的概率,其計算公式為

根據用戶認為某知識“有幫助”的概率值pu,i以及決策區域劃分閾值α和β,即可將知識劃入正域、邊界域或負域中,進而做出知識推送決策。

3 實驗與分析

實驗選用眾所周知的Movielens數據集,并根據本文算法的適用場景選擇Movielens-100k 數據集的前10 000條評分數據作為實驗數據。這其中包含了93名用戶對1 682部電影的評分信息,且每個用戶至少對20部電影進行了評價。實驗隨機將數據按80%和20%的比例劃分為訓練集和測試集。實驗將每部電影作為知識單位(結構體),將電影類別作為知識屬性,以用戶平均打分為界限,若評分大于或等于用戶平均打分,則認為用戶喜歡該電影；否則,用戶不喜歡該電影。如此,每個用戶喜歡的電影集合亦即用戶認為“有幫助”的知識集合。

首先,通過實驗確定計算知識相關度所需的融合系數,然后通過與傳統推送模型的對比分析,測試本文推送模型的效果。實驗對關聯知識二支推送模型、關聯知識三支推送模型、基于傳統ICF 的二支推送模型和基于傳統ICF 的三支推送模進行兩兩比較,對比它們的推送效果。推送效果評價指標包括平均推送成本、準確率、召回率和覆蓋率。

3.1 推送效果評價指標

采用平均成本來衡量二支和三支模型的推送成本。根據成本矩陣(見表5),推送總成本和平均推送成本的計算方式如下所示：

式中：TC為推送總成本；NPH、NBH和NNH分別為將用戶認為“有幫助”的知識推送、延遲推送和不推送給用戶的數量,NPU、NBU和NNU分別為將用戶認為“無幫助”的知識推送、延遲推送和不推送給用戶的數量。基于現實情況及三支推送決策中成本約束(見式(10)、(12)),實驗設定的成本矩陣如表6 所示。相對而言,本文將正確決策的成本視為零,即λPH=λNU=0。

知識推送的目的在于將合適的知識推送至用戶,故推送的效果可用推送的準確度來衡量。準確率(Precision)和召回率(Recall)是信息檢索和統計學分類領域常用的兩個指標,同時也廣泛應用于推薦領域[15]。它們將所得的預測評分轉化到分類問題上,用分類準確度代替評分精確度,適用本文的實際應用場景,故采用準確率和召回率來衡量二支和三支模型推送的準確度,兩者在本文中的計算方式如下所示：

式中,NPH、NPU和NNH的含義與推送總成本相同。準確率表征了推送結果被用戶認為“有幫助”的水平,召回率表征了用戶認為“有幫助”的知識被推送的能力,故準確率和召回率越高,推薦系統的推薦效果越好。

在推薦算法常用的測評指標中,覆蓋率(Coverage)反映了算法對項目的平均推薦能力。本文采用覆蓋率來衡量推送模型對知識的推薦率,其計算方式為

式中：R(u)為用戶u的知識推送集；I為總的知識集；為相對應的個數。覆蓋率表征了推送模型對知識的平均推送能力,其值越高,對冷門知識的推薦能力越高。

3.2 支持度閾值的確定

前已述及,知識關聯度的計算受支持度閾值的影響。根據本文推送模型的應用場景及本實驗所選數據集的特點(包含93名用戶),設定當支持度閾值c=3時,即至少有3名用戶共同認為某兩條知識“有幫助”時,將置信度的大小作為知識之間的關聯度。

3.3 融合系數的確定

因為用戶的偏好集并不局限于特定的屬性范疇,所以由此得到的知識關聯度與知識之間基于屬性的視圖相似度不同。根據實驗所得數據,有些項目之間相似度很低但關聯度很高,同樣亦存在有些項目之間相似度很高但關聯度很低的情形,故采用md來說明。其為每個項目的相似度與關聯度之間差異的均平方,計算方式如下所示：

經計算得md=0.382 3,這體現了項目之間的關聯度與項目之間的相似度的差異性。

在進行算法效果的對比實驗之前,還需確定計算知識相關度時所需的融合系數q的大小,即知識相關度中知識屬性相似度和知識關聯度各自所占的比重。采用實驗的方法,通過計算并比較不同融合系數下的預測結果誤差,選擇使得誤差最小的融合系數作為最終的融合系數。具體地,實驗在支持度閾值c=3,最近鄰數目k=10的條件下,在0.1～1范圍內以0.1為跨度設置q,并以預測評分的平均絕對誤差MAE來衡量預測結果誤差,計算方法為

圖1 不同融合系數q 下的MAE

3.4 實驗結果與分析

為比較不同推送模型的推送成本、準確率、召回率和覆蓋率,實驗根據不同模型評分預測方式、決策方式及對應決策成本的不同,分別計算了不同最近鄰數目下基于傳統ICF的二支、三支推送模型和關聯知識二支、三支推送模型的平均推送成本、準確率、召回率和覆蓋率,實驗結果見圖2～5。

(1)推送成本。由圖2可知,在相同的評分預測方式下,三支推送模型在不同最近鄰數目下的平均推送成本均低于二支推送模型；而在相同的決策方式下,關聯知識推送模型的平均推送成本均低于基于傳統ICF的推送模型。總體而言,三支關聯知識推送模型的平均推送成本最低,較傳統ICF 二支推送模型平均降低3.25 單位成本,較傳統ICF 二支推送模型平均降低23.98%。

圖2 不同最近鄰數目下的平均推送成本

(2)準確率。由圖3可知,在相同的評分預測方式下,三支推送模型在不同最近鄰數目下的準確率均高于二支推送模型。三支決策方式下,在最近鄰數目為2～18,關聯知識推送模型的準確率均高于基于傳統ICF的推送模型；當最近鄰數目大于18后,兩者趨于相同。二支決策方式下,情況類似。總體而言,三支關聯知識推送模型的準確率更高,較傳統ICF二支推送模型平均提升7.15%。

圖3 不同最近鄰數目下的準確率

(3)召回率。由圖4可知,在相同的評分預測方式下,三支推送模型在不同最近鄰數目下的召回率均高于二支推送模型；而在相同的決策方式下,關聯知識推送模型的召回率均高于基于傳統ICF 的推送模型。總體而言,三支關聯知識推送模型的召回率更高,較傳統ICF 二支推送模型平均提升20.2%。

圖4 不同最近鄰數目下的召回率

(4)覆蓋率。由圖5可知,在相同的評分預測方式下,三支推送模型在不同最近鄰數目下的覆蓋率均低于二支推送模型；而在相同的決策方式下,關聯知識推送模型的覆蓋率均高于基于傳統ICF 的推送模型。本文的三支關聯知識推送模型的覆蓋率較傳統ICF 二支推送模型平均降低18.09%,但較傳統ICF三支推送模型平均提升7.99%。

圖5 不同最近鄰數目下的覆蓋率

綜合上述實驗結果,可得出如下結論：①三支關聯知識推送模型在平均推送成本、準確率和召回率的平均表現均優于其他3個推送模型。②本文提出的三支關聯知識推送模型的覆蓋率雖低于二支推送模型,但從側面反映了三支關聯知識推送模型犧牲了一定的覆蓋率、縮小了推送知識的范圍,從而提升了推送的準確率、降低了推送成本。

4 結語

考慮到知識關聯度的重要性以及傳統推送決策的二分性質,本文提出了一種基于三支決策的關聯知識推送算法。為挖掘并利用知識之間的潛在聯系,將知識關聯度融入評分預測中,構建了融合知識相似度和知識關聯度的知識相關度模型。同時,為了減少傳統二分法中因錯誤分類而產生的推送成本,在最終的推薦決策中引入了三支決策思想,實現了三支推送,并通過實驗驗證了三支推送模型的推送成本、準確率和召回率均優于二支推送模型,但覆蓋率表現不如二支推送模型。在本文構建的知識推送系統中,尚未考慮用戶評分偏好的問題,項目冷啟動問題依然存在,欠缺對延遲推送決策項目的后續處理,課題組將在后續研究中繼續優化與補充。