辛冠琳　劉驚雷

摘要：針對(duì)傳統(tǒng)的推薦系統(tǒng)需要用戶給出明確的偏好矩陣（U-I矩陣），進(jìn)而使用自動(dòng)化技術(shù)來獲取用戶偏好的問題，提出了一種從偏好數(shù)據(jù)庫（preference database）中挖掘出Agent的偏好信息的方法。從知識(shí)發(fā)現(xiàn)的角度，通過Ceteris Paribus規(guī)則（CP規(guī)則），提出了k階偏好挖掘算法（kPreM）。在算法中，利用k階CP規(guī)則對(duì)偏好數(shù)據(jù)庫中的信息進(jìn)行剪枝處理，減少了數(shù)據(jù)庫掃描次數(shù)，從而提高了偏好信息的挖掘效率。隨后以一種通用的圖模型——條件偏好網(wǎng) （CP-nets）為工具，揭示了用戶的偏好可近似表達(dá)為CP-nets的定性條件偏好網(wǎng)。實(shí)驗(yàn)結(jié)果表明，用戶的偏好都是帶有條件的偏好。另外，通過挖掘得出的CP-nets偏好模型，為設(shè)計(jì)個(gè)性化的推薦系統(tǒng)提供了理論基礎(chǔ)。

關(guān)鍵詞：自動(dòng)化技術(shù)；偏好數(shù)據(jù)庫；知識(shí)發(fā)現(xiàn)；CP規(guī)則；定性條件偏好網(wǎng)

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

0引言

由于用戶偏好信息在偏好數(shù)據(jù)庫（preference database）中的必需性，增強(qiáng)數(shù)據(jù)庫系統(tǒng)的偏好功能已經(jīng)引起了許多專家學(xué)者的廣泛關(guān)注。近年來，關(guān)于Ceteris Paribus[1]的偏好挖掘問題已經(jīng)成為數(shù)據(jù)挖掘的研究熱點(diǎn)[2-3]。從信息檢索（information retrieval）[4]、推薦系統(tǒng)（recommendation system）[5]到個(gè)性化搜索引擎（personalized search engine）[6]等都能看到它的應(yīng)用。偏好挖掘廣泛存在于在線商業(yè)系統(tǒng)中，諸如音樂[7]、投票[8]和產(chǎn)品等均存在Ceteris Paribus偏好。對(duì)系統(tǒng)進(jìn)行偏好挖掘的最基本的問題之一就是如何表示用戶的偏好。其根源在于，用戶的偏好不是一成不變的，隨著外部條件的改變，用戶的偏好也會(huì)隨之改變[9]。在日常生活中，一個(gè)典型的實(shí)例就是在冬天，人們更偏好于穿棉衣；而在夏天，人們更偏好于穿單衣。這一情況說明季節(jié)的變化，影響了人們對(duì)于衣服種類的需求，這種偏好關(guān)系就是Ceteris Paribus偏好，其廣泛存在于社會(huì)生活中[10]。我們?cè)贛ovieLens數(shù)據(jù)集[11]中挖掘了用戶的偏好信息，發(fā)現(xiàn)用戶的偏好是有條件的。

但是在大多數(shù)的偏好數(shù)據(jù)庫的挖掘?qū)W習(xí)中，并沒有將Ceteris Paribus偏好考慮在內(nèi)。Boutilier等[12]對(duì)偏好的建模和推理進(jìn)行研究，為條件偏好網(wǎng) （Conditional Preference networks，CP-nets）模型提供了一個(gè)正式的語義，并對(duì)可利用的網(wǎng)絡(luò)結(jié)構(gòu)予以推理。Wilson[13]指出CP-nets的重要屬性，如一致性的存在，最優(yōu)配置可以有效地生成，并且可以很容易找到對(duì)應(yīng)的全序關(guān)系；同時(shí)，為解決CP-nets的學(xué)習(xí)問題提出了一個(gè)約束優(yōu)化方法。Pereira等[14]提出，對(duì)個(gè)性化的數(shù)據(jù)庫應(yīng)用，偏好查詢語言有較高的說服力和表現(xiàn)力。以上文獻(xiàn)均對(duì)偏好進(jìn)行了一定的研究學(xué)習(xí)，但是對(duì)于用戶在偏好數(shù)據(jù)庫中的Ceteris Paribus偏好挖掘這一工作的側(cè)重較少。

現(xiàn)有的條件偏好模型，如CP-nets[12，15-16]，增強(qiáng)的條件偏好網(wǎng) （Tradeoffs-enhanced Conditional Preference networks，TCP-nets），可分的其他條件不變的偏好網(wǎng)（Separable Ceteris Paribus preference，SCP-nets）等，盡管它們作為一種簡單直觀的圖形表示工具，可以在其他條件不變的情況下，將用戶的Ceteris Paribus偏好定性表示，但其仍然存在一些不足，主要表現(xiàn)在：空間復(fù)雜度較高和用戶偏好挖掘問題的難解性。

在這種背景下，本文研究用戶的Ceteris Paribus偏好挖掘問題。從偏好數(shù)據(jù)庫中，觀察統(tǒng)計(jì)用戶偏好的依賴情況，提取偏好規(guī)則，以挖掘Ceteris Paribus偏好，并與真實(shí)的用戶偏好模型進(jìn)行比較。本文的主要工作如下：

1）在偏好數(shù)據(jù)庫中挖掘Ceteris Paribus偏好的過程中，提出了k階Ceteris Paribus規(guī)則（簡稱k階CP規(guī)則）概念，并設(shè)計(jì)了挖掘k階CP規(guī)則的算法。其中k表示偏好數(shù)據(jù)庫中影響當(dāng)前屬性取值的父親的個(gè)數(shù)。

2）通過在MovieLens偏好數(shù)據(jù)庫上的實(shí)驗(yàn)，發(fā)現(xiàn)用戶對(duì)電影的偏好是有條件的，即不同的電影屬性取值確定了用戶對(duì)該電影的評(píng)分高低。這一結(jié)果說明了現(xiàn)實(shí)中真實(shí)的偏好數(shù)據(jù)庫常常是帶有依賴屬性的條件偏好。

3）借助于CP-nets圖模型，發(fā)現(xiàn)了偏好數(shù)據(jù)庫中的Ceteris Paribus偏好和CP-nets[17]具有一定的相似性，并設(shè)計(jì)了求偏好數(shù)據(jù)庫和CP-nets相似度的公式。實(shí)驗(yàn)結(jié)果驗(yàn)證了CP-nets和真實(shí)偏好數(shù)據(jù)庫具有一定的相似度，從而間接證明了偏好數(shù)據(jù)庫可以用CP-nets來近似表達(dá)。

1相關(guān)工作

其他條件均同，某一條件的改變引起用戶偏好的變化，我們將其稱之為Ceteris Paribus偏好。對(duì)Ceteris Paribus偏好的挖掘，根據(jù)學(xué)習(xí)方法的不同，可以分為多種方法。從是否與對(duì)象內(nèi)容有關(guān)的方面，Ceteris Paribus偏好的挖掘可以分為標(biāo)簽排序和對(duì)象排序；從挖掘偏好的方式上，挖掘用戶偏好可以分為定量方法和定性方法。

1.1標(biāo)簽排序和對(duì)象排序

Ceteris Paribus偏好表達(dá)了對(duì)所有配置的一種偏序關(guān)系。挖掘Ceteris Paribus偏好實(shí)際上就是從偏好數(shù)據(jù)庫中獲取配置之間的序的過程，因此挖掘偏好就是一種學(xué)習(xí)排序（learning to rank）[18]的過程。學(xué)習(xí)排序可以分為標(biāo)簽排序和對(duì)象排序，本文的偏好挖掘?qū)儆趯?duì)象排序。

標(biāo)簽排序是基于對(duì)象上的標(biāo)簽對(duì)對(duì)象所處的標(biāo)簽進(jìn)行排序，以確定每個(gè)對(duì)象上的標(biāo)簽之間的序關(guān)系。對(duì)象排序是在兩個(gè)給定的對(duì)象o1和o2中，基于對(duì)象的屬性，預(yù)測o1與o2之間的偏好關(guān)系。對(duì)象排序最終確定的是對(duì)象之間的序關(guān)系，而不像標(biāo)簽排序那樣，確定標(biāo)簽之間的序關(guān)系。因此，對(duì)象排序與內(nèi)容有關(guān)。本文研究的偏好挖掘，和對(duì)象排序相關(guān)，它對(duì)偏好數(shù)據(jù)庫中對(duì)象之間的序關(guān)系予以分析，探討影響對(duì)象偏好的屬性，從而實(shí)現(xiàn)對(duì)Ceteris Paribus偏好的挖掘。

1.2挖掘偏好的定量方法和定性方法

挖掘Ceteris Paribus偏好有兩種形式，定量方法[19]和定性方法[20-21]。定量挖掘方法是對(duì)配置給定一個(gè)權(quán)值，配置之間的比較可轉(zhuǎn)化為權(quán)值的比較；定性挖掘方法則無數(shù)值表示，僅給定偏序關(guān)系用以判定配置之間的偏好關(guān)系。挖掘Ceteris Paribus偏好是從偏好數(shù)據(jù)庫中挖掘定性偏好的過程。

對(duì)于定性方法， Holland等[20]在帕累托偏好模型（Pareto preference model）下，提出了基于定性方法挖掘用戶偏好的技術(shù)。作為一種新穎的偏好挖掘方法，其主要優(yōu)點(diǎn)是通過語義表達(dá)偏好的挖掘結(jié)果。Jiang等[21]提出從偏好最優(yōu)和最差的樣本中挖掘用戶偏好的方法，并利用貪心法證明其在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上都具有實(shí)用性。在偏好挖掘中，潛在的偏好模型仍是帕累托偏好模型。在該模型中，偏好是無條件的或是與上下文無關(guān)的，即一個(gè)屬性的取值不依賴于其他屬性的取值。

在定性方法中，與上下文有關(guān)的偏好模型（qualitative or contextual preference model）是本文的研究重點(diǎn)。Koriche等[22]提出了一種從用戶提供的偏好中挖掘CP-nets模型的方法。de Amo等[23]提出了一個(gè)不同的方法ProfMiner，發(fā)現(xiàn)了由一組偏好規(guī)則規(guī)定的用戶配置文件。該方法的特點(diǎn)是有高準(zhǔn)確率和低召回率。次年，de Amo等[24]又提出了CPrefMiner算法，將用戶的偏好信息表示成貝葉斯偏好網(wǎng)（Bayesian Preference Network，BPN）。而本文是從偏好數(shù)據(jù)庫中提取k階CP偏好，從而將用戶的偏好信息表示成CP-nets。

2Ceteris Paribus偏好的相關(guān)概念和定義

2.1Ceteris Paribus偏好

Ceteris Paribus偏好是由Doyle等[25]提出的關(guān)于人類偏好的一個(gè)理論公式，它表示其他條件均相同的偏好（all-else-equal preferences）。Ceteris Paribus偏好關(guān)系[26]表達(dá)了在所有可能配置上的偏好信息。

定義1Ceteris Paribus偏好。若其他條件不變，單個(gè)屬性的改變會(huì)影響對(duì)象之間的偏序關(guān)系。Ceteris Paribus偏好這一術(shù)語就是用來描述這一特性的，其形式化為式（1）所示，其中r是除φ和ψ之外的任意命題變量。

MovieLen 1M數(shù)據(jù)集在本質(zhì)上就是一個(gè)偏好數(shù)據(jù)庫。在MovieLens數(shù)據(jù)集中，用戶對(duì)電影進(jìn)行評(píng)分，分值為1～5。MovieLens包括兩個(gè)不同大小的庫，適用于不同規(guī)模的算法。在本文中，對(duì)MovieLens中大規(guī)模的庫MovieLen 1M進(jìn)行研究探索，挖掘其中的Ceteris Paribus偏好。通過對(duì)MovieLen 1M等偏好數(shù)據(jù)庫的分析，我們?cè)噲D解決如下問題：

1）在挖掘偏好數(shù)據(jù)庫的Ceteris Paribus偏好信息的過程中，挖掘偏好數(shù)據(jù)庫中的k階CP規(guī)則，確定偏好數(shù)據(jù)庫中影響當(dāng)前屬性取值的父親的個(gè)數(shù)k。

2）確認(rèn)偏好數(shù)據(jù)庫中的用戶偏好與基于G2檢驗(yàn)學(xué)習(xí)得到的CP-nets[17]是否具有相似性。

為了挖掘偏好數(shù)據(jù)庫中的Ceteris Paribus偏好信息，確定k階CP規(guī)則，對(duì)偏好數(shù)據(jù)庫中的屬性進(jìn)行了統(tǒng)計(jì)分析。若其滿足k階CP規(guī)則，表示其影響當(dāng)前屬性取值的父親的個(gè)數(shù)為k。k的取值不同，則對(duì)應(yīng)的Ceteris Paribus偏好也不相同，即偏好數(shù)據(jù)庫中是帶有依賴屬性的條件偏好。

為了判斷偏好數(shù)據(jù)庫中的條件偏好是否具有依賴屬性，在是否給定電影流派的條件下，在單個(gè)用戶中對(duì)兩個(gè)偏好次序進(jìn)行比較。將MovieLen 1M偏好數(shù)據(jù)庫中的電影信息分為兩部分：一部分給定流派，另一部分未給定流派。根據(jù)用戶對(duì)電影的評(píng)分，對(duì)在這兩部分集合中的其他流派進(jìn)行排序，作為流派不同條件下屬性的偏好次序。若兩個(gè)偏好次序不同，則認(rèn)為偏好數(shù)據(jù)庫中的條件偏好具有依賴屬性。

偏好數(shù)據(jù)庫中的Ceteris Paribus偏好與CP-nets的相似度可借助偏序關(guān)系來表示，其中，CP-nets可利用G2檢驗(yàn)[17]的方式生成。偏序關(guān)系是指在偏好數(shù)據(jù)庫挖掘信息過程中獲得的偏好序列?？蓪⑼ㄟ^挖掘得到的偏序關(guān)系與數(shù)據(jù)庫中真實(shí)的偏序關(guān)系的比值，作為判斷Ceteris Paribus偏好與CP-nets相似度的依據(jù)。

定義6相似度。N′和N分別表示挖掘得到的Ceteris Paribus偏好和真實(shí)偏好，其中：num（agree_edge）表示在兩個(gè)偏好圖中具有相同的起點(diǎn)、終點(diǎn)和相同方向的邊的數(shù)目；num（total_edge）表示在偏好圖中邊的總數(shù)目。N′和N中的相似度可由similarity（N′， N）表示，且0≤similarity（N′，N）≤1。

式（3）可表示Ceteris Paribus偏好和真實(shí)偏好的相似度。真實(shí)偏好可基于G2檢驗(yàn)學(xué)習(xí)方式獲取其對(duì)應(yīng)的CP-nets。similarity（N′， N）的值越大，表示在偏好數(shù)據(jù)庫中挖掘得到的偏好信息愈加準(zhǔn)確，與CP-nets也愈加相似。

2.3偏好挖掘?qū)嵗?/p>

例2在MovieLen 1M偏好數(shù)據(jù)庫中，任意選擇一位用戶，如userID=685的用戶，他參與評(píng)價(jià)的電影數(shù)目為137，表1中給出了該用戶對(duì)10部電影的評(píng)分。其中：Co表示Comedy（喜劇片），D表示Drama（劇情片），W表示W(wǎng)estern（西部片），Ac表示Action（動(dòng)作片），R表示Romance（愛情片），Ad表示Adventure（探險(xiǎn)片），Ch表示Childrens（兒童片），An表示Animation（動(dòng)畫片），T表示Thriller（驚悚片）。若給定電影流派為喜劇片（Co），則將表1中的電影分為兩部分，屬于喜劇片的電影（Co=1）和不屬于喜劇片的電影（Co=0）。

由表2可知，在Co=1和Co=0條件下，對(duì)應(yīng)屬性的偏好次序完全不同。因此可知，用戶對(duì)電影的偏好是有條件的。為保證實(shí)驗(yàn)的隨機(jī)性和準(zhǔn)確性，表3和表4中列出了其他單個(gè)用戶在是否給定條件下的偏好次序，結(jié)果也顯示單個(gè)用戶下偏好數(shù)據(jù)庫是帶有依賴屬性的條件偏好。

步驟1確定偏好數(shù)據(jù)庫中影響當(dāng)前屬性取值的父親的個(gè)數(shù)k，k的取值為1到n-1，n是數(shù)據(jù)庫中屬性的個(gè)數(shù)。在V={X1，X2，…，Xn}中根據(jù)k的取值，選定一個(gè)集合U作為當(dāng)前屬性取值的父親，UV。當(dāng)k>1時(shí)，采用剪枝技術(shù)，根據(jù)k-1階CP規(guī)則的結(jié)果Pruning（k-1）對(duì)所有可能的k階CP規(guī)則進(jìn)行剪枝。根據(jù)定理2，將k階CP規(guī)則的子集中含有非k-1階CP規(guī)則的屬性集合舍棄，只對(duì)余下的可能的k階CP規(guī)則進(jìn)行處理。

步驟2根據(jù)當(dāng)前屬性取值的父親U確定當(dāng)前屬性X，X是V-U中屬性的子集。對(duì)U和X對(duì)應(yīng)的偏好數(shù)據(jù)庫中的屬性進(jìn)行選擇投影，結(jié)果用t[U]和t[X]表示。在偏好數(shù)據(jù)庫中，若t1[U]≠t2[U]和t1[X]≠t2[X]同時(shí)成立，則其滿足k階CP規(guī)則，因此，U是X的k階偏好。否則，不滿足k階CP規(guī)則，因此，U不是X的k階偏好。

步驟3將k階CP規(guī)則下的偏好挖掘結(jié)果儲(chǔ)存至Pruning（k）中，為k+1階偏好的判斷做準(zhǔn)備。根據(jù)剪枝技術(shù)，可減少偏好數(shù)據(jù)庫的掃描次數(shù)，建立有效的數(shù)據(jù)結(jié)構(gòu)來提高檢索效率，從而降低kPreM算法的時(shí)間復(fù)雜度。

3.2實(shí)例

以下通過例3來說明kPreM算法的處理過程。例3只有4個(gè)屬性，數(shù)據(jù)庫很小，但對(duì)于屬性較多的偏好數(shù)據(jù)庫，kPreM算法同樣適用。

例3圖2是一個(gè)關(guān)于k階CP規(guī)則的實(shí)例。由圖2可知，A、B、C、D是偏好數(shù)據(jù)庫中的4個(gè)屬性，表示偏好規(guī)則最多為3階。現(xiàn)根據(jù)CP規(guī)則的生成順序?qū)ζ溆枰苑治觥?/p>

4算法的性質(zhì)分析

4.1正確性分析

算法的正確性是衡量算法性能的重要指標(biāo)。在本節(jié)中，通過定理3對(duì)kPreM算法的正確性進(jìn)行驗(yàn)證。

定理3在偏好數(shù)據(jù)庫中，滿足k階CP規(guī)則的屬性U必是屬性X的k階偏好。

證明通過kPreM算法遍歷偏好數(shù)據(jù)庫，得到相關(guān)的Ceteris Paribus偏好信息和偏好數(shù)據(jù)庫中影響當(dāng)前屬性取值的父親的個(gè)數(shù)k。若公式u：x滿足k階CP規(guī)則，則U是X的父親，即U是X的k階偏好；反之，U不是X的父親，可知屬性X的偏好階數(shù)未定或者屬性X是無偏好的。

同時(shí)，不滿足k階CP規(guī)則的屬性，其超集一定不滿足k+1階CP規(guī)則。因此，在k+1階CP規(guī)則生成所有可能屬性集時(shí)，可將子集中含有非k階CP規(guī)則的屬性集刪去，以減少數(shù)據(jù)庫的遍歷次數(shù)，提高挖掘算法的效率。

4.2完備性分析

算法的完備性，表示偏好數(shù)據(jù)庫中所蘊(yùn)含的結(jié)論均可通過kPreM算法獲取。在kPreM算法中，由于偏好數(shù)據(jù)庫中影響當(dāng)前屬性取值的父親的個(gè)數(shù)k的選取是從1到n-1，n是數(shù)據(jù)庫中屬性的個(gè)數(shù)，因此，算法的主要思想涵蓋了在數(shù)據(jù)庫的偏好挖掘中可能出現(xiàn)的所有情況。

定理4在偏好數(shù)據(jù)庫中，根據(jù)k階CP規(guī)則可得到所有偏好信息。

證明在掃描數(shù)據(jù)庫的過程中，通過迭代技術(shù)，記錄非k階CP規(guī)則的屬性，為k+1階Ceteris Paribus偏好信息的挖掘作準(zhǔn)備。若可能的k+1階CP規(guī)則的子集中存在非k階CP規(guī)則，則其也不是k+1階CP規(guī)則。若其滿足k階CP規(guī)則，則對(duì)k階CP規(guī)則的屬性進(jìn)行分析。由于k階CP規(guī)則取值涵蓋了偏好數(shù)據(jù)庫中的所有屬性，因此，可確定偏好數(shù)據(jù)庫中的k階Ceteris Paribus偏好。依照此步驟進(jìn)行操作，遍歷偏好數(shù)據(jù)庫，挖掘全部的Ceteris Paribus偏好信息，就是算法完備性的表現(xiàn)。

4.3高效性分析

算法的高效性分析，可以體現(xiàn)在時(shí)間復(fù)雜度分析上。時(shí)間復(fù)雜度是指在偏好數(shù)據(jù)庫中挖掘Ceteris Paribus偏好信息所花費(fèi)的時(shí)間。在kPreM算法中，利用剪枝技術(shù)，在選取k+1階偏好時(shí)，首先對(duì)所有可能的屬性集進(jìn)行驗(yàn)證，對(duì)k+1階屬性集中的子集不滿足k階CP規(guī)則的屬性進(jìn)行剪枝。因?yàn)槿绻?dāng)前屬性不滿足k階CP規(guī)則，則其一定不滿足k+1階CP規(guī)則。由此，減少了對(duì)偏好數(shù)據(jù)庫的掃描次數(shù)，提高了算法的效率，降低了算法的時(shí)間復(fù)雜度。

5實(shí)驗(yàn)與分析

5.1實(shí)驗(yàn)環(huán)境

本文中的算法挖掘?qū)嶒?yàn)在計(jì)算機(jī)上進(jìn)行，操作系統(tǒng)是Windows 7 （64位），配有8GB DDR3內(nèi)存和主頻為3.2GHz的i5-4570 Intel CPU。程序編寫語言是C語言，運(yùn)行環(huán)境是Microsoft Visual Studio 2008。實(shí)驗(yàn)中對(duì)Ceteris Paribus偏好信息的挖掘在MovieLen 1M數(shù)據(jù)庫中進(jìn)行，挖掘過程中所需的數(shù)據(jù)均來自于MovieLen 1M數(shù)據(jù)庫中的真實(shí)數(shù)據(jù)信息。

5.2實(shí)驗(yàn)過程

在偏好數(shù)據(jù)庫中挖掘Ceteris Paribus偏好過程中，首先將偏好數(shù)據(jù)庫中的數(shù)據(jù)信息轉(zhuǎn)化成為計(jì)算機(jī)可以識(shí)別的形式。例如，將當(dāng)前配置信息中具有的屬性設(shè)置為1，不具有的屬性設(shè)置為0，在實(shí)驗(yàn)中簡化計(jì)算，提高運(yùn)行效率；同時(shí)，也為后續(xù)進(jìn)行詳細(xì)的實(shí)驗(yàn)以測試偏好挖掘方法的正確性和延展性奠定了基礎(chǔ)。

在偏好挖掘?qū)嶒?yàn)中，可根據(jù)kPreM算法中描述的步驟進(jìn)行處理。輸入為偏好數(shù)據(jù)庫中的數(shù)據(jù)信息，經(jīng)過kPreM算法的處理，輸出對(duì)應(yīng)的偏序關(guān)系。

5.3評(píng)估標(biāo)準(zhǔn)

為了驗(yàn)證通過挖掘得到的用戶偏好與偏好數(shù)據(jù)庫中的真實(shí)用戶偏好的一致性，將挖掘得到的用戶偏好N′與真實(shí)用戶偏好N的一些要素進(jìn)行比較，以相似度與一致度作為評(píng)估標(biāo)準(zhǔn)，衡量算法的性能。

5.3.1相似度

相似度是指通過算法挖掘得到的Ceteris Paribus偏好N′與偏好數(shù)據(jù)庫的真實(shí)偏好N之間的相似度，即一致的邊占所有邊的比例。相似度越高，表明學(xué)習(xí)結(jié)果越精確，算法的性能越好。根據(jù)定義6中的式（3）可計(jì)算挖掘得到的Ceteris Paribus偏好和真實(shí)偏好的相似度。相似度計(jì)算公式similarity（N′， N）如下：

其中：分子表示在兩個(gè)偏好圖中具有相同的起點(diǎn)、終點(diǎn)和相同方向的邊的數(shù)目；分母表示在偏好圖中邊的總數(shù)目。由于兩個(gè)偏好圖是基于相同的配置空間，因此，其對(duì)應(yīng)的偏好圖中的邊的數(shù)目是相同的。

圖3反映了在MovieLen 1M數(shù)據(jù)庫中的685號(hào)用戶在不同條件下學(xué)習(xí)所得到的偏好圖與原偏好圖之間的相似度的變化趨勢，不同條件分別是指樣本數(shù)目和顯著性水平。顯著性水平表示可能出現(xiàn)錯(cuò)誤的概率，它不是一個(gè)固定不變的數(shù)字，可根據(jù)研究的性質(zhì)和對(duì)結(jié)論準(zhǔn)確性所持的要求而定。圖3中：樣本數(shù)目分別設(shè)置為20、50、100、200和500；顯著性水平分別取值為0.05、0.10、0.15和0.20。如圖3所示，樣本數(shù)量越多，顯著性水平越小，則對(duì)應(yīng)的相似度程度越高；反之，則相似度程度越低。隨著樣本容量的增大，相似度趨于穩(wěn)定。

5.3.2一致度

一致度是指通過算法挖掘得到的Ceteris Paribus偏好N′與偏好數(shù)據(jù)庫的真實(shí)偏好N之間的一致度，即一致的樣本占所有樣本的比例。其中，偏好數(shù)據(jù)庫的真實(shí)偏好N可根據(jù)G2檢驗(yàn)學(xué)習(xí)得到。一致度越高，表明學(xué)習(xí)結(jié)果越精確，算法的性能越好。式（6）描述了一致度的計(jì)算公式：

其中：分子表示在兩個(gè)偏好圖中含有相同成對(duì)配置的數(shù)目，分母表示在偏好圖中成對(duì)配置的總數(shù)目。由于兩個(gè)偏好圖是基于相同的配置空間，因此，其對(duì)應(yīng)的偏好圖中成對(duì)配置的數(shù)目是相同的。

圖4中的一致度描述了MovieLen 1M數(shù)據(jù)庫中的685號(hào)用戶在不同條件下的一致的樣本占整個(gè)樣本的比例。由圖4可知，樣本數(shù)量越多，顯著性水平越小，則對(duì)應(yīng)的一致度越高；反之，則一致度越低。隨著樣本容量的增大，一致度趨于穩(wěn)定。

5.4實(shí)驗(yàn)討論

在實(shí)驗(yàn)過程中算法的性能必然會(huì)受一些因素的干擾，它們對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生了一定的影響。下面主要是對(duì)出現(xiàn)在實(shí)驗(yàn)中的一些影響實(shí)驗(yàn)結(jié)果的因素進(jìn)行討論，主要有：不同用戶和樣本數(shù)目。

5.4.1不同用戶

在MovieLen 1M數(shù)據(jù)庫中，不同的用戶對(duì)相同的電影的評(píng)分是不同的，不同的用戶偏好的電影類型也是不同的。在MovieLen 1M數(shù)據(jù)庫中還隨機(jī)選取了193號(hào)用戶，對(duì)他的相似度和一致度進(jìn)行計(jì)算，結(jié)果如圖5、6所示。由圖3～6可知，不同的用戶盡管在樣本和顯著性水平的影響下的變化趨勢相同，但是其對(duì)應(yīng)的相似度和一致度仍有區(qū)別，具體體現(xiàn)在數(shù)值上，不同的用戶對(duì)應(yīng)的相似度和一致度的值是不一樣的。因此，用戶的不同是影響實(shí)驗(yàn)結(jié)果的主要因素。

5.4.2樣本數(shù)目

用戶的樣本數(shù)目也是影響實(shí)驗(yàn)結(jié)果的主要因素。通常，樣本數(shù)目越多，實(shí)驗(yàn)結(jié)果的準(zhǔn)確性也隨之提升。為確定用戶的樣本數(shù)目對(duì)實(shí)驗(yàn)的影響，實(shí)驗(yàn)中分別設(shè)置為20、50、100、200和500。實(shí)驗(yàn)結(jié)果可參照?qǐng)D3～6。由圖可知，樣本數(shù)目對(duì)實(shí)驗(yàn)有一定的影響。隨著樣本數(shù)目的增大，相似度和一致度雖有所變化，但均逐漸趨于穩(wěn)定。然而，在實(shí)踐中較大樣本的設(shè)置并不能保證算法更好的性能。樣本數(shù)目作為實(shí)驗(yàn)中的必需因素，對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生影響。

5.5實(shí)驗(yàn)對(duì)比

本文在偏好數(shù)據(jù)庫中進(jìn)行Ceteris Paribus偏好挖掘是在真實(shí)數(shù)據(jù)集MovieLen 1M上進(jìn)行的。與之前學(xué)習(xí)CP-nets[17]中運(yùn)用的隨機(jī)生成的數(shù)據(jù)集相比，本次實(shí)驗(yàn)更具有說服力和真實(shí)性。在基于G2檢驗(yàn)的CP-nets學(xué)習(xí)中，對(duì)相關(guān)偏好的挖掘是通過模擬數(shù)據(jù)進(jìn)行的。即利用隨機(jī)生成的數(shù)據(jù)生成成對(duì)比較的配置，通過G2檢驗(yàn)的方式，判斷每個(gè)屬性的依賴關(guān)系。盡管使用隨機(jī)生成的數(shù)據(jù)具有簡單、高效和避免干擾等優(yōu)點(diǎn)，但是其數(shù)據(jù)的模擬性不可避免，隨機(jī)產(chǎn)生的數(shù)據(jù)與當(dāng)前配置之間的關(guān)系無法判斷。在本文中，采用MovieLen真實(shí)數(shù)據(jù)集，一方面引用真實(shí)數(shù)據(jù)，使實(shí)驗(yàn)的真實(shí)性和正確性具有理論依據(jù)；另一方面，真實(shí)數(shù)據(jù)的引入使挖掘用戶偏好具有實(shí)際意義。

與Dimopoulos等[10]提取Ceteris Paribus偏好工作相比，本文中的實(shí)驗(yàn)對(duì)各種情況的考量更為全面。因?yàn)镈imopoulos等[10]提出的Ceteris Paribus偏好提取方法不能處理噪聲數(shù)據(jù)，也就是說在通過被動(dòng)學(xué)習(xí)方式挖掘Ceteris Paribus偏好的過程中，若根據(jù)觀測用戶得到了錯(cuò)誤的信息，則依據(jù)該方法不能挖掘得到Ceteris Paribus偏好信息。而在本文提出的挖掘偏好方法中，考慮到了噪聲數(shù)據(jù)的存在，保證了即使在噪聲數(shù)據(jù)的影響下，依然可以通過學(xué)習(xí)挖掘得到Ceteris Paribus偏好。

6結(jié)語

本文通過無關(guān)性檢驗(yàn)的方式實(shí)現(xiàn)在偏好數(shù)據(jù)庫中的Ceteris Paribus偏好挖掘。通過設(shè)計(jì)偏好挖掘算法，探索在偏好數(shù)據(jù)庫中關(guān)于用戶的偏好信息以及其影響因素，表明在偏好數(shù)據(jù)庫中的所有用戶的偏好均是有條件的；深入挖掘用戶偏好信息，發(fā)現(xiàn)用戶的偏好不僅是有條件的，并且滿足Ceteris Paribus偏好；將挖掘所得到的Ceteris Paribus偏好與CP-nets進(jìn)行比較，并計(jì)算其相似度，分析挖掘?qū)W習(xí)的性能。但是，本文僅在MovieLens數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)比較，尚未在其他實(shí)驗(yàn)數(shù)據(jù)集，如Netflix上進(jìn)行。對(duì)用戶偏好信息的挖掘只限于單個(gè)用戶，沒有考慮群體用戶的情況。

本文所設(shè)計(jì)的算法為如下工作提供了基礎(chǔ)：1） 偏好數(shù)據(jù)庫中，挖掘用戶滿足的偏好規(guī)則特性，如用戶偏好是否滿足傳遞性。2）根據(jù)k階CP規(guī)則，探索影響Ceteris Paribus偏好階數(shù)k的因素，進(jìn)一步挖掘偏好數(shù)據(jù)庫中的偏好信息；同時(shí)，將多個(gè)用戶的偏好聚合成群體用戶的偏好。3） 盡管當(dāng)前算法利用剪枝技術(shù)實(shí)現(xiàn)了偏好數(shù)據(jù)庫中Ceteris Paribus偏好的挖掘任務(wù)，但是其時(shí)間復(fù)雜度仍然較高。因此，是否能夠利用近似挖掘算法來降低時(shí)間復(fù)雜度可以作為進(jìn)一步的工作。4）解挖掘得到的用戶偏好與基于G2檢驗(yàn)學(xué)習(xí)得到CP-nets圖結(jié)構(gòu)上的漢明距離，從而說明挖掘算法所得到偏好規(guī)則的質(zhì)量。

參考文獻(xiàn)：

[1]GROSSI D， LORINI E， SCHWARZENTRUBER F. The ceteris paribus structure of logics of game forms [J]. Journal of Artificial Intelligence Research， 2015， 53（1）： 91-126.

[2]LIU W， WU C， FENG B， et al. Conditional preference in recommender systems [J]. Expert Systems with Applications， 2015， 42（2）： 774-788.

[3]陳勐，禹曉輝，劉洋.基于深度表示模型的移動(dòng)模式挖掘[J].計(jì)算機(jī)應(yīng)用，2016，36（1）：33-38. （CHEN M， YU X H， LIU Y. Mining mobility patterns based on deep representation model [J]. Journal of Computer Applications， 2016， 36（1）： 33-38.）

[4]AILON N. Learning and optimizing with preferences [C]// ALT 2013： Proceedings of the 24th International Conference on Algorithmic Learning Theory， LNCS 8139. Berlin： Springer-Verlag， 2013： 13-21.

[5]SHI Y， LARSON M， HANJALIC A. Collaborative filtering beyond the user-item matrix： a survey of the state of the art and future challenges [J]. ACM Computer Surveys， 2014， 47（1）： Article No. 3.

[6]GURUSWAMI M， SUNITHA T. Efficient robust interactive personalized mobile search engine [J]. International Journal of Computer Trends and Technology， 2015， 19（1）： 30-33.

[7]WANG X， WANG Y. Improving content-based and hybrid music recommendation using deep learning [C]// MM 14： Proceedings of the 22nd ACM International Conference on Multimedia. New York： ACM， 2014： 627-636.

[8]PROCACCIA A D， SHAH N， ZICK Y. Voting rules as error-correcting codes [J]. Artificial Intelligence， 2016， 231： 1-16.

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

http：//www.cs.cmu.edu/～nkshah/papers/error.aaai.pdf

[9]DE AMO S， DIALLO M S， DIOP C T， et al. Contextual preference mining for user profile construction [J]. Information Systems， 2015， 49： 182-199.

[10]DIMOPOULOS Y， MICHAEL L， ATHIENITOU F. Ceteris paribus preference elicitation with predictive guarantees [C]// IJCAI 09： Proceedings of the 21st International Joint Conference on Artificial Intelligence. San Francisco， CA： Morgan Kaufmann， 2009： 1890-1895.

[11]DE AMO S， BUENO M L P， ALVES G， et al. CPrefMiner： an algorithm for mining user contextual preferences based on Bayesian networks [C]// Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE， 2012， 1： 114-121.

[12]BOUTILIER C， BRAFMAN R I， DOMSHLAK C， et al. CP-nets： a tool for representing and reasoning with conditional ceteris paribus preference statements [J]. Journal of Artificial Intelligence Research， 2004， 21（1）： 135-191.

[13]WILSON N. Extending CP-nets with stronger conditional preference statements [C]// AAAI-04： Proceedings of the Nineteenth National Conference on Artificial Intelligence. Menlo Park， CA： AAAI， 2004： 735-741.

[14]PEREIRA F S F， DE AMO S. Evaluation of conditional preference queries [J]. Journal of Information and Data Management， 2010， 1（3）： 503-518.

[15]LIU J， LIAO S. Expressive efficiency of two kinds of specific CP-nets [J]. Information Sciences， 2015， 295： 379-394.

[16]劉驚雷.CP-nets及其表達(dá)能力研究[J].自動(dòng)化學(xué)報(bào)，2011，37（3）：290-302. （LIU J L. Research on CP-nets and its expressive power [J]. Acta Automatica Sinica， 2011， 37（3）： 290-302.）

[17]辛冠琳，劉驚雷.基于G方檢驗(yàn)的CP-nets學(xué)習(xí)[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，51（4）：781-795. （XIN G L， LIU J L. Learning CP-nets based on G2 test [J]. Journal of Nanjing University （Natural Sciences）， 2015， 51（4）： 781-795.）

[18]COHEN W W， SCHAPIRE R E， SINGER Y. Learning to order things [J]. Journal of Artificial Intelligence Research， 1999， 10（5）： 243-270.

http：//xueshu.baidu.com/s？wd=paperuri%3A%280c6f3a33ffc97a5ee52530d6f06a93a3%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fadsabs.harvard.edu%2Fabs%2F2011arXiv1105.5464C&ie=utf-8&sc_us=16692312367941757205

NIPS '97 Proceedings of the 1997 conference on Advances in neural information processing systems 10

Pages 451-457

MIT Press Cambridge， MA， USA 1998

[19]JOACHIMS T. Optimizing search engines using clickthrough data [C]// KDD 02： Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2002： 133-142.

[20]HOLLAND S， ESTER M， KIEΒLING W. Preference mining： a novel approach on mining user preferences for personalized applications [C]// PKDD 2003： Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases， LNCS 2838. Berlin： Springer-Verlag， 2003： 204-216.

[21]JIANG B， PEI J， LIN X， et al. Mining preferences from superior and inferior examples [C]// KDD 08： Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2008： 390-398.

[22]KORICHE F， ZANUTTINI B. Learning conditional preference networks [J]. Artificial Intelligence， 2010， 174（11）： 685-703.

[23]DE AMO S， DIALLO M S， DIOP C T， et al. Mining contextual preference rules for building user profiles [C]// Proceedings of the 14th International Conference on Data Warehousing and Knowledge Discovery， LNCS 7448. Berlin： Springer-Verlag， 2012： 229-242.

[24]DE AMO S， BUENO M L P， ALVES G， et al. Mining user contextual preferences [J]. Journal of Information & Data Management， 2013， 4（1）： 37-46.

[25]DOYLE J， SHOHAM Y， WELLMAN M P. A logic of relative desire （preliminary report） [C]// ISMIS 91： Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems. London， UK： Springer-Verlag， 1991： 16-31.

[26]MCGEACHIE M， DOYLE J. Utility functions for ceteris paribus preferences [J]. Computational Intelligence， 2004， 20（2）： 158-217.