基于最大團(tuán)的條件偏好挖掘

譚 征，劉驚雷，余 航

(煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院, 山東 煙臺(tái) 264005)

基于最大團(tuán)的條件偏好挖掘

譚 征，劉驚雷*，余 航

(煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院, 山東 煙臺(tái) 264005)

針對(duì)在數(shù)據(jù)庫的個(gè)性化查詢中條件約束(或上下文約束)沒有被充分考慮的問題，首先提出了條件約束模型i+?i-|X，它表示在上下文X的約束下，相對(duì)于i-，用戶更偏好i+。在此模型的基礎(chǔ)上，采用最大團(tuán)(MaxClique)關(guān)聯(lián)規(guī)則算法挖掘獲得用戶偏好；隨后又提出了條件偏好挖掘(CPM)算法，該算法結(jié)合上下文用于挖掘偏好規(guī)則，從而得出用戶的偏好。實(shí)驗(yàn)結(jié)果表明，基于CPM算法的偏好挖掘模型具有較強(qiáng)的偏好表達(dá)能力, 將CPM算法與基于Apriori的算法以及CONTENUM算法進(jìn)行了實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)的主要參數(shù)為最小支持度、最小可信度、數(shù)據(jù)規(guī)模等，實(shí)驗(yàn)結(jié)果進(jìn)一步表明所提出的CPM算法可明顯提高用戶偏好規(guī)則的產(chǎn)生效率。

最大團(tuán)；關(guān)聯(lián)規(guī)則；偏好數(shù)據(jù)庫；條件偏好規(guī)則；偏好挖掘

0 引言

電子商務(wù)的飛速發(fā)展使得人們更愿意通過網(wǎng)絡(luò)快捷地選擇商品和服務(wù)。但由于Web數(shù)據(jù)庫中通常蘊(yùn)含海量數(shù)據(jù)，增加了用戶選擇商品的成本。大多數(shù)推薦系統(tǒng)能通過偏好抽取的手段獲取用戶的偏好要求，并以經(jīng)濟(jì)的方式獲取商品的信息。因此研究用戶條件偏好的挖掘具有十分重要的意義。

目前已存在的一些電子商務(wù)推薦系統(tǒng)在實(shí)際運(yùn)用中還存在著問題，推薦效率較低，有些還不能滿足用戶的個(gè)性化需求。優(yōu)化具有條件偏好(即本文所指的上下文偏好)的查詢功能的數(shù)據(jù)庫系統(tǒng)引起了數(shù)據(jù)庫領(lǐng)域研究者極大的興趣。無論是電子商務(wù)還是個(gè)性化推薦系統(tǒng)，用戶偏好在系統(tǒng)模型的設(shè)計(jì)中都是基本要素[1]。消費(fèi)者偏好是一種消費(fèi)心理，反映消費(fèi)者對(duì)某種產(chǎn)品或服務(wù)的興趣或愛好程度，受消費(fèi)者個(gè)性特征以及外界環(huán)境等主客觀因素的共同影響，把握消費(fèi)者偏好的變化規(guī)律比較困難，消費(fèi)者的偏好往往通過購買行為體現(xiàn)[2]，因此偏好抽取是關(guān)鍵技術(shù)所在。偏好抽取的結(jié)果能使用戶明白自身的偏好要求，并能以最經(jīng)濟(jì)的方式獲取偏好商品信息。偏好挖掘的使用方法中，基于關(guān)聯(lián)規(guī)則的技術(shù)是較為熱門的，但在實(shí)際應(yīng)用中，關(guān)聯(lián)規(guī)則推薦技術(shù)也存在著一些問題，比如：發(fā)現(xiàn)關(guān)聯(lián)規(guī)則比較困難，關(guān)聯(lián)規(guī)則的產(chǎn)生僅與用戶消費(fèi)的結(jié)果有關(guān)而忽視了產(chǎn)生偏好的上下文約束，而用戶的偏好不穩(wěn)定往往隨著上下文的不同變化。本文主要闡述用偏好挖掘的算法獲取用戶的潛在偏好，使用的是系統(tǒng)事先收集的樣本，用成對(duì)出現(xiàn)的數(shù)據(jù)表達(dá)用戶的偏好。用戶偏好由一系列條件偏好規(guī)則詳細(xì)說明，這些規(guī)則滿足一定的興趣標(biāo)準(zhǔn)，并具有較強(qiáng)的預(yù)測(cè)性。本文提出基于條件的偏好規(guī)則的模型為i+?i-|X，它表示在上下文X的約束下，相對(duì)于i-，用戶更偏好i+。這里的條件約束就是指上下文約束。

例如，電影偏好數(shù)據(jù)庫中的元組信息表明了用戶的偏好，這些偏好是由用戶對(duì)點(diǎn)擊電影標(biāo)記表示他們的興趣而產(chǎn)生的。標(biāo)記A、B、C、D、E分別代表電影的導(dǎo)演、主演、影片類型等。如：A為張藝謀，B為章子怡，C為戲劇片，D為鞏俐，E為動(dòng)作片，每個(gè)ti(i=1, 2, …,n)代表用戶的事物標(biāo)記TID，假設(shè)用戶點(diǎn)擊了10次t1，點(diǎn)擊了6次t3，則表明他們對(duì)與t1有關(guān)的電影更感興趣，就得到一條偏好，用〈t1,t3〉表示，以此形成一個(gè)偏好數(shù)據(jù)庫P，如圖1(b)所示。

分析偏好規(guī)則〈t1,t3〉，發(fā)現(xiàn)無論在哪個(gè)元組中包含了標(biāo)記A(張藝謀)和標(biāo)記C(戲劇片)，用戶更喜歡帶有標(biāo)記D(鞏俐)而不是帶有標(biāo)記B(章子怡)主演的電影。所以條件偏好規(guī)則為：在兩部由張藝謀執(zhí)導(dǎo)的戲劇片中人們更喜歡鞏俐主演的電影而不是章子怡主演的。這里的導(dǎo)演和影片類型就構(gòu)成了這條規(guī)則的上下文。本文提出的用戶偏好是由一系列條件偏好規(guī)則構(gòu)成的，這些規(guī)則要滿足穩(wěn)定性和簡(jiǎn)潔性：所謂穩(wěn)定性是指規(guī)則與大量的用戶偏好吻合，與少量的不一致；簡(jiǎn)潔性是指生成的偏好規(guī)則集盡可能地小。

圖1 影片數(shù)據(jù)庫及偏好數(shù)據(jù)庫Fig. 1 Movie database and preference database

偏好規(guī)則的挖掘通過關(guān)聯(lián)規(guī)則實(shí)現(xiàn)。盡管關(guān)聯(lián)規(guī)則是挖掘算法中的基本方法之一，但是它的改進(jìn)方法有很多，本文將改進(jìn)的關(guān)聯(lián)規(guī)則算法MaxClique用于條件偏好挖掘(Conditional Preference Mining, CPM)算法中來挖掘用戶偏好規(guī)則。

1 相關(guān)工作

挖掘具有條件偏好的偏好規(guī)則引起了眾多專家學(xué)者的興趣。目前一些主要的研究工作包括:開發(fā)偏好建模推理框架的研究, 為個(gè)性化數(shù)據(jù)庫應(yīng)用提供說明性和應(yīng)用性很強(qiáng)的偏好查詢語言。然而專注于偏好規(guī)則抽取的工作不多。偏好抽取就是讓用戶知道在一個(gè)數(shù)據(jù)庫中什么是他們的偏好并且通過較低的成本獲取這些偏好。提取用戶偏好代表性的研究方法可以分為以下兩類：

1)通過一個(gè)查詢界面輸入用戶偏好。這種情況下用戶偏好的表達(dá)受到了很大的限制。用戶偏好只能用簡(jiǎn)單模糊詞標(biāo)記元組或?qū)傩缘姆绞奖磉_(dá)，而且用戶要參與到反饋的過程中，如果用戶真的能夠準(zhǔn)確地表達(dá)自己的偏好，也就不需要偏好挖掘了，所以通過這種方式獲取用戶的偏好很困難[3]。

2)用挖掘算法獲取用戶潛在的偏好。一般情況下，偏好受各種因素的影響，用戶無法準(zhǔn)確地表達(dá)自己的偏好[3]。隨著數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則技術(shù)的日益成熟，利用關(guān)聯(lián)規(guī)則從用戶的歷史記錄中挖掘隱式用戶偏好，抽取一系列具有簡(jiǎn)潔性和穩(wěn)定性的偏好規(guī)則成為目前的研究熱點(diǎn)。文獻(xiàn)[4]使用了用戶喜歡與不喜歡這樣的語義表達(dá)幫助個(gè)性化查詢,對(duì)上文考慮不多。文獻(xiàn)[5]是利用貝葉斯網(wǎng)絡(luò)(Bayesian Network, BN)結(jié)合上下文挖掘偏好，計(jì)算量較為復(fù)雜。文獻(xiàn)[6]將偏好公式嵌入到關(guān)系代數(shù)SQL(Structured Query Language)中，其優(yōu)點(diǎn)是查詢速度快。文獻(xiàn)[7]中提到的條件偏好查詢使用規(guī)則集挖掘偏好，并對(duì)規(guī)則集的top-k條規(guī)則進(jìn)行了評(píng)估。文獻(xiàn)[8]提出了基于上下文的偏好挖掘，針對(duì)不同數(shù)據(jù)源產(chǎn)生的偏好規(guī)則可能出現(xiàn)重復(fù)和矛盾的現(xiàn)象，建立離線先驗(yàn)組存放具有代表性的偏好規(guī)則。文獻(xiàn)[9]介紹了集格理論可用于搜索空間的壓縮,對(duì)本文的研究有一定的啟示作用。文獻(xiàn)[10]通過分析消費(fèi)者的瀏覽頻率、瀏覽時(shí)間、連接路徑以及路徑深度作為用戶偏好商品的權(quán)重，并結(jié)合雙向關(guān)聯(lián)規(guī)則理論挖掘具有相互依賴關(guān)系的商品，計(jì)算消費(fèi)者對(duì)商品的偏好程度。但是沒有考慮上下文對(duì)消費(fèi)者偏好的影響。文獻(xiàn)[11]給出了基于上下文的數(shù)據(jù)庫查詢規(guī)則排序算法，提出了上下文偏好模型。文獻(xiàn)[12]給出了一種利用普適計(jì)算技術(shù)進(jìn)行上下文感知的數(shù)據(jù)庫查詢系統(tǒng)，但是需要偏好規(guī)則樣本集。文獻(xiàn)[13]則將上下文感知用于移動(dòng)用戶的偏好挖掘中，討論了上下文獨(dú)立和非獨(dú)立條件下的兩種偏好挖掘方法。文獻(xiàn)[14]提出按屬性排序挖掘偏好的方法。文獻(xiàn)[15]是在電影數(shù)據(jù)集中設(shè)計(jì)的一個(gè)推薦系統(tǒng)，利用的是電影導(dǎo)演和演員提供的信息而不是用戶的評(píng)級(jí)，對(duì)于用戶偏好的挖掘顯然有誤差。

偏好規(guī)則一般是通過關(guān)聯(lián)規(guī)則或改進(jìn)的關(guān)聯(lián)規(guī)則挖掘出來的。類關(guān)聯(lián)規(guī)則算法(Class Association Rule, CAR)[16]是一種專注于挖掘特殊子集的關(guān)聯(lián)規(guī)則算法，目標(biāo)是在數(shù)據(jù)庫中找出一組規(guī)則進(jìn)行精確分類?；趧澐值乃惴╗17]將數(shù)據(jù)劃分成內(nèi)存能處理的塊，第一次掃描數(shù)據(jù)庫產(chǎn)生局部頻繁集，第二次掃描數(shù)據(jù)庫形成全局頻繁項(xiàng)集，缺點(diǎn)是會(huì)產(chǎn)生部分假頻繁項(xiàng)集。文獻(xiàn)[18]提出了一種基于抽樣的關(guān)聯(lián)規(guī)則抽取算法。文獻(xiàn)[19]對(duì)基于抽樣的關(guān)聯(lián)規(guī)則算法的有效性進(jìn)行了分析。CMAR(Classification based on Multiple Class-Association Rules)算法[20]是一種基于多關(guān)聯(lián)規(guī)則的分類算法，該方法拓展了頻繁模式挖掘方法，有效地挖掘大型數(shù)據(jù)庫。

目前盡管有大量的研究工作致力于用戶偏好的表達(dá)和處理，但是這些用戶偏好很難應(yīng)用到實(shí)際中, 因?yàn)樵诓樵兘Y(jié)果和算法執(zhí)行效率上每種方法都存在自己的不足。本文在挖掘算法中采用生成最大團(tuán)的圖模型算法，旨在減少系統(tǒng)內(nèi)存的占用，壓縮數(shù)據(jù)集的掃描次數(shù)。在此基礎(chǔ)上結(jié)合上下文(條件)，提出了CPM算法用于挖掘偏好規(guī)則，從而能得出用戶的偏好。這一方法提高了偏好規(guī)則的產(chǎn)生效率和偏好的準(zhǔn)確性。

2 上下文偏好

2.1 上下文偏好規(guī)則定義

設(shè)I為項(xiàng)目集合，X是I的子集，即X?I，事務(wù)數(shù)據(jù)庫D是I的多項(xiàng)集，每個(gè)項(xiàng)集是數(shù)據(jù)庫的一個(gè)元組，如圖1(a)中的一行。偏好數(shù)據(jù)庫P?D×D是成對(duì)事務(wù)，每條記錄代表用戶的一個(gè)偏好，如：〈t,u〉∈P，意味著，與u相比用戶更偏好t。偏好數(shù)據(jù)庫和事務(wù)數(shù)據(jù)庫的聯(lián)系如圖2所示。

圖2 偏好數(shù)據(jù)庫與事務(wù)數(shù)據(jù)庫聯(lián)系Fig. 2 Relation of preference database and transaction database

定義1 上下文偏好。i+?i-|X，X?I，i-和i+是I-X中的項(xiàng)集，稱為上下文偏好規(guī)則。如：D?E|AB表示在出現(xiàn)上下文AB時(shí)，相對(duì)于E，用戶更加偏好D。偏好規(guī)則R=i+?i-|X所關(guān)聯(lián)的偏好數(shù)據(jù)庫元組t?Ru，由如下方式來構(gòu)造：

(X∪{i+}?t)∧(X∪{i-} ?u)∧

(i-?t)∧(i+?u)

例如偏好規(guī)則D?E|A所關(guān)聯(lián)到的一個(gè)元組為：ACD?ABCE，它表示當(dāng)出現(xiàn)A時(shí)，用戶對(duì)CD的偏好優(yōu)于對(duì)BCE。

定義2 偏好規(guī)則的覆蓋集。設(shè)agree(R,P)={〈t,u〉∈P|t?Ru}，表示R滿足P中的成對(duì)集合〈t,u〉，即用戶相對(duì)u更偏好t。設(shè)contradition(R,P)={〈t,u〉∈P|u?Rt}表示偏好規(guī)則R，滿足成對(duì)集合〈t,u〉∈P，表明用戶相對(duì)于t更偏好u，則覆蓋集記作：

cov(R,P)=agree(R,P)∪contradition(R,P)

2.2 上下文規(guī)則的支持度、可信度和最小偏好規(guī)則

定義3 偏好規(guī)則的支持度。一條上下文偏好規(guī)則R在偏好數(shù)據(jù)庫P中的支持度描述如下：

sup(R,P)=|agree(R,P)| / |P|

如：上下文關(guān)聯(lián)規(guī)則D?E|A與圖1(b)中的p1，p2相匹配，D?E|B與p2相匹配，前者的支持度為sup(D?E|A,P)=|{p1,p2}| / |P|=2/5=0.4；而后者的支持度sup(D?E|B,P)=|{p2}|/|P|=1/5=0.2。支持度反映了一個(gè)上下文關(guān)聯(lián)規(guī)則R對(duì)偏好數(shù)據(jù)庫中元組的匹配程度，同時(shí)也反映了一條上下文偏好規(guī)則的興趣度。顯然，規(guī)則D?E|A比規(guī)則D?E|B更有趣。

定義4 可信度。 一條上下文偏好規(guī)則R對(duì)應(yīng)于偏好數(shù)據(jù)庫P的可信度描述如下：

conf(R,P)=|agree(R,P)| / |cov(R,P)|

如：conf(D?E|A,P)=2/2=1；conf(D?E| ?,P)=2/3。

可信度用來衡量一個(gè)上下文偏好規(guī)則與用戶偏好相悖的程度，就這點(diǎn)而言，D?E|A比D?E| ?更有價(jià)值。如果一條上下文偏好規(guī)則R的支持度超過某一指定值即閾值(用min_sup表示)稱為頻繁關(guān)聯(lián)規(guī)則。如果一條頻繁關(guān)聯(lián)規(guī)則的可信度超過某一指定值即閾值(min_conf)，稱為強(qiáng)關(guān)聯(lián)規(guī)則?？衫弥С侄乳撝岛涂尚哦乳撝颠M(jìn)行剪枝即去掉非頻繁項(xiàng)。圖1中D?E|B和D?E|AB具有相同的支持度和可信度，希望保留上下文更短的規(guī)則，即最小的上下文規(guī)則。本文將采用可擴(kuò)展的關(guān)聯(lián)規(guī)則方法進(jìn)行頻繁規(guī)則的挖掘，第3章將描述這一問題。

定義6 代價(jià)函數(shù)。給定偏好數(shù)據(jù)集p，上下文偏好規(guī)則集Π，與p關(guān)聯(lián)的Π代價(jià)函數(shù)即

Cost(Π,p)=(|pcover(Π,p)| +

|contradict(Π,p)|) / |p|

直觀來看，用戶偏好集Π的代價(jià)函數(shù)表示偏好數(shù)據(jù)庫p中的偏好沒有被Π中的任何一條規(guī)則覆蓋或者與Π中的部分規(guī)則相反的偏好在p中所占的百分比。按照這一定義，用戶偏好的穩(wěn)定性是指Cost函數(shù)的值最小。若某一偏好數(shù)據(jù)庫上p的偏好規(guī)則為R，Π?R滿足簡(jiǎn)潔性和代價(jià)最小，稱Π是與p關(guān)聯(lián)的用戶偏好。本文第4章會(huì)有相應(yīng)的算法。

3 可擴(kuò)展關(guān)聯(lián)規(guī)則算法

可擴(kuò)展的關(guān)聯(lián)規(guī)則算法是一種發(fā)現(xiàn)頻繁項(xiàng)集的高效算法，主要是利用頻繁項(xiàng)集的結(jié)構(gòu)性質(zhì)實(shí)現(xiàn)快速查找。采用的方法是將項(xiàng)目集分解成小的獨(dú)立的子集格從而組成一個(gè)子集格搜索空間，可在內(nèi)存空間中完成搜索，可高效地確定長(zhǎng)頻繁項(xiàng)集及其子集，即可完成一般規(guī)模的數(shù)據(jù)集處理，對(duì)大數(shù)據(jù)集也有效，因此稱為可擴(kuò)展的關(guān)聯(lián)規(guī)則算法。它是對(duì)傳統(tǒng)關(guān)聯(lián)規(guī)則作拓展與改進(jìn)。本文所用的最大團(tuán)方法就是這種方法。

3.1 集格理論

關(guān)于一些集格理論的術(shù)語，文獻(xiàn)[8]中有很好的敘述。現(xiàn)在回顧一下主要的內(nèi)容。

定義7 集格。L在有限的交、并集合的操作中是閉合的，稱之為集格。(L;?)是由子集關(guān)系?定義的偏序集格。X∨Y=X∪Y且X∧Y=X∪Y。A(L)表示L原子集。

引理1 所有頻繁集的子集都是頻繁的，非頻繁項(xiàng)的超集都是非頻繁的。在自底向上的搜索頻繁項(xiàng)集的過程中，這是一個(gè)有力的剪枝策略。

引理2 最大頻繁項(xiàng)集唯一決定了所有頻繁項(xiàng)集。

引理3 對(duì)于一個(gè)有限的布爾集格L， 若x∈L，x=∨{y∈A(L) |y≤x}，元素是以原子集的子集的并的形式給出的。

3.2 基于前序的類

定義8 等價(jià)關(guān)系。令P是一個(gè)集合，一種在P上的等價(jià)關(guān)系是一種二元關(guān)系 ≡，若X、Y、Z∈P，這種等價(jià)關(guān)系滿足：

1)自反性。X≡X。

2)對(duì)稱性。若X≡Y，則Y≡X。

3)傳遞性。若X≡Y,Y≡Z，則X≡Z。

這種等價(jià)關(guān)系將集合P分成不相交的子集，稱作等價(jià)類。一個(gè)等價(jià)類的元素X∈P以[X]={Y∈P|X≡Y}的形式給出。定義一個(gè)等價(jià)前綴函數(shù)：

p：P(L)×N→P(L)

函數(shù)p(X,K)=X[1:K]，K是X的前綴長(zhǎng)度，集格P(L)上的等價(jià)關(guān)系θk定義如下：

?X,Y∈P(L),X≡θkY?p(X,k)=p(Y,k)

兩個(gè)項(xiàng)集若享有一個(gè)公共的長(zhǎng)度為k的前綴，它們?cè)谝粋€(gè)類中，θk稱為基于前綴的等價(jià)關(guān)系。

引理5 所有θk包含的等價(jià)類[X]θk是P(L)的子集格。

任意的[X]θ1是一個(gè)含有它本身原子的一個(gè)布爾集格。設(shè)[A]θ1的原子集是{AC,AD,AT,AW}，通過引理3和引理4的應(yīng)用可求出所有類的項(xiàng)目集的支持度。應(yīng)當(dāng)特別注意的是必須自底向上處理等價(jià)類，按字典順序的逆序，即處理[W]之后處理[T]，然后是[D]，[C]，[A]，這樣才能保證在剪枝的過程中所有子集的信息都是可靠的。應(yīng)用這一方法，可以遞歸地分解不能一次納入內(nèi)存的等價(jià)類，使其能被獨(dú)立地解決且可以在反字典的順序中進(jìn)行剪枝。

3.3 最大團(tuán)方法生成更小的類

定義9 偽等價(jià)關(guān)系。令P為一個(gè)集合，≡表示P上的一種二元關(guān)系，稱為偽等價(jià)關(guān)系，對(duì)所有X、Y∈P，滿足：

1)自反性。X≡X。

2)對(duì)稱性。若X≡Y，則Y≡X。

這種偽等價(jià)關(guān)系將P分成可能重疊的子集，稱為偽等價(jià)類。

定義10 最大團(tuán)。如果一張圖的所有頂點(diǎn)之間均有連線，稱其為完全圖。完全圖的子圖叫作團(tuán)。令FK表示頻繁K項(xiàng)集的集合，定義一張K關(guān)聯(lián)圖，以GK=(V,E)的形式給出，頂點(diǎn)集V={X|∈F1}，邊集E={(X,Y)|X,Y∈V且?Z∈F(k+1)，X,Y∈Z}，令MK表示GK的最大團(tuán)的集合，圖3展示了F2所示的關(guān)聯(lián)圖G1，若頻繁二項(xiàng)集為：{12,13,14,15,16,17,18,23,25,27,28,34,35,36,45,46,56,58,68,78}，其中最大團(tuán)M1={1235,1258,1287,13456,1568}。

圖3 前綴類和最大團(tuán)類Fig. 3 Prefix classes and MaxClique classes

定義一種基于冪集格P(L)的偽等價(jià)關(guān)系φk。?X，Y∈P(L)，X≡φkY? ?C∈Mk同時(shí)有X,Y∈C且p(X,k)=p(Y,k)。這說明X,Y是相關(guān)的，它們同為一個(gè)最大團(tuán)的子集，并且共享長(zhǎng)度為k的公共前綴，φk為基于最大團(tuán)的偽等價(jià)關(guān)系。

引理6 由偽等價(jià)關(guān)系φk生成的偽等價(jià)類[X]φk是冪集P(L)的子集格。

引理7 令Nk表示基于最大團(tuán)關(guān)系φk生成的偽等價(jià)類的集合，由φk生成的偽等價(jià)類[Y]φk是某些由前綴關(guān)系θk生成的偽等價(jià)類[Y]θk的子集。從另一方面來說，[X]θk是一組偽等價(jià)類ψ的并集，記作[X]θk=∪{[Z]φk|Z∈ψ?Nk}。

用φk來取代θk可以生成更小的集格。這些小集格對(duì)內(nèi)存的需求更少。從圖3中可以看出基于前綴的類[1]={12345678}，包含了所有的項(xiàng)；而基于最大團(tuán)的類[1]={1235,1258,1278,13456,1568}比基于前綴的類小。最大團(tuán)生成算法對(duì)稀疏的K階關(guān)聯(lián)圖會(huì)產(chǎn)生效果，對(duì)稠密圖則不可行。

定義11 覆蓋集合。對(duì)于類[x]，y∈[x]，稱y覆蓋了[x]的子集，記為cov(y)=[y]∩[x]。對(duì)于每個(gè)類C，首先確定它的覆蓋集合：{y∈C|cov(y) ≠ ?且對(duì)于任意z∈C，z

算法1 覆蓋集生成算法Gencov。

輸入 電影數(shù)據(jù)庫；

輸出 所有類的覆蓋集。

1)

for alltag[i]∈AllTagdo

2)

for alltag[j]∈AllTagdo

3)

if (tag[i]≠tag[j] ∧IsFrequent(tag[i],tag[j]))

4)

insert(ver[i].CoveringSet,j);

5)

end

6)

end

算法1中將不同的電影標(biāo)簽作為一類，存儲(chǔ)在向量ver中，步驟1)和步驟2)針對(duì)所有的電影標(biāo)簽進(jìn)行頻繁集的搜索，步驟4)生成所有類的覆蓋集。

算法2 最大團(tuán)生成算法Genmax。

輸入 電影數(shù)據(jù)集；

輸出 每一類的最大團(tuán)。

1)

Gencov(ver);

2)

foreachi:N→1 do

3)

ver[i].CliqList=?;

4)

for allx∈ver[i].CoveringSetdo

5)

for allc∈ver[x].CliqListdo

6)

M=c∩ver[i].CoveringSet;

7)

if (!M.empty)

8)

M=M∪[i];

9)

if(Not ExistX‖Y∈ver[i].CliqList,X?Y‖Y?X)

10)

insert(M,ver[i].CliqList);

11)

endif

12)

endfor

13)

endfor

14)

endfor

算法中的ver是一個(gè)向量，它的最大容量為N即電影標(biāo)簽的總數(shù)量，步驟1)中調(diào)用算法1,產(chǎn)生所有的覆蓋集，步驟5)～8)描述了最大團(tuán)的生成過程。

算法3 所有團(tuán)的生成算法Genall。

輸入 每一類的最大團(tuán)；

輸出 所有的團(tuán)。

1)

allCliq=?;

2)

foreachi:1→Ndo

3)

forallcliq∈ver[i].CliqList

4)

forallsubCliqofcliq

5)

if (Not ExistCliq∈allCliq==subCliq)

6)

insert(subCliq,allCliq);

7)

endif

8) endfor

9) endfor

10)

endfor

算法中allCliq是一個(gè)用于存儲(chǔ)所有團(tuán)的集合，步驟2)～6)描述了利用所有類的最大團(tuán)分解為不同的子團(tuán)的過程，值得注意的是，所有的這些子團(tuán)即為所有團(tuán)。

4 挖掘偏好規(guī)則算法

4.1 偏好規(guī)則挖掘算法

為了保證規(guī)則的簡(jiǎn)潔性，通過減少深度優(yōu)先搜索解空間的剪枝方法來達(dá)到這一目的。

引理8 剪枝標(biāo)準(zhǔn)。如果一個(gè)上下文偏好規(guī)則i+?i-|X是非頻繁且非最小化的，則任何規(guī)則i+?i-|Y(X是Y的前綴)都是非頻繁且不是最小的上下文偏好規(guī)則。

算法4 用戶偏好規(guī)則挖掘算法CPM。

輸入 電影數(shù)據(jù)庫，偏好數(shù)據(jù)庫，最小支持度閾值minsuppt,最小可信度閾值minconf；

輸出 偏好規(guī)則集。

1)

rules=?;

2)

Genall(Genmax());

3)

for allCliq1∈allCliqdo

4)

for allCliq2∈allCliqdo

5)

flag=0;

6)

if (Cliq1.length==Cliq2.length)

7)

for (k=1;k≤NumOfTag;k++) do

8)

if (Cliq1.tag[k] ≠Cliq2.tag[k])flag++;

9)

endif

10)

endfor

11)

endif

12)

if (flag==1)

13)

suppt1=suppt(Cliq1,Cliq2);

14)

suppt2=suppt(Cliq2,Cliq1);

15)

if(suppt1>minsuppt&&suppt1/(suppt1+suppt2)>

minconf)

16)

insert(rules,Cliq1,Cliq2);

17)

endif

18)

endif

19)

endfor

20)

endfor

21)

returnrules

NumOfallCliq是所有團(tuán)的數(shù)目, 標(biāo)記量flag表示兩個(gè)團(tuán)是否符合規(guī)則交叉的條件，算法步驟7)描述了長(zhǎng)度相等且只有一項(xiàng)不等。步驟3)～14)，描述了如何判斷兩個(gè)團(tuán)符合交叉生成規(guī)則的條件的過程，算法步驟15)～21)則描述了對(duì)兩個(gè)滿足交叉條件的團(tuán)進(jìn)行支持度判斷以及生成規(guī)則的過程。由算法得知，根據(jù)其前綴上下文，一個(gè)最小前綴上下文規(guī)則是最小的。前綴最小是有約束的最小。用深度優(yōu)先的方法可以相對(duì)容易地獲得最小前綴規(guī)則集合。

4.2 頻繁項(xiàng)集搜索策略

1)自底向上的搜索。

自底向上的搜索是基于等價(jià)關(guān)系θk，采用遞歸的策略將類分解為更小的類。等價(jià)類格可以由深度優(yōu)先搜索和廣度優(yōu)先搜索策略生成。

假如原子集為{A,C,D,T,W}由廣度優(yōu)先搜索生成的類為 {[AC],[AT],[AW]}，繼續(xù)往下生成的類應(yīng)該是{[ACT],[ATW],[ACW]}，最后是[ACTW]。計(jì)算任何項(xiàng)集的支持度，只需要簡(jiǎn)單地把前一階段生成的它的兩個(gè)子集做項(xiàng)目列表的交運(yùn)算就可以了。算法輸入的是集格S中原子項(xiàng)通過對(duì)不同的成對(duì)項(xiàng)做交集來產(chǎn)生頻繁項(xiàng)，并通過遞歸的方法產(chǎn)生出某一階段的頻繁項(xiàng)集，并將上一階段重復(fù)的項(xiàng)集刪除。

算法5 CONTENUM算法。

輸入 偏好數(shù)據(jù)庫P，前綴為X的規(guī)則;

輸出 偏好規(guī)則集S。

1)

S=?

2)

for alli∈Cdo

3)

s12=supp(i1?i2|X∪{i},P)

4)

s21=supp(i2?i1|X∪{i},P)

5)

if ((s12≥σ)∨(s21≥σ))∧

((s21

((s12

6)

if ((s12≥σ)∧(s12/(s12+s21)≥κ)

thenS=S∪{i1?i2|X∪{i}}

7)

if ((s21 ≥σ)∧(s21 / (s12+s21) ≥κ)

thenS=S∪{i2?i1|X∪{i}}

8)

S=S∪CONTENUM((i1,i2),X∪{i},

{c∈C|i

9)

end if

10)

end for

11)

returnS

2)自頂向下的搜索。

自頂向下的搜索方法從集格的最頂層元素開始，如果頂層元素為K項(xiàng)集，則需要進(jìn)行K輪的交集運(yùn)算。這種策略的優(yōu)勢(shì)是如果最大元素相當(dāng)長(zhǎng)，可以避免計(jì)算它的子集的支持度。搜索從頂層開始，如果頂層項(xiàng)集是頻繁的，算法結(jié)束；否則進(jìn)行下一階段k-1項(xiàng)的判斷，直到所有的最小頻繁項(xiàng)被找到為止。算法構(gòu)造的過程中可采用哈希表，記錄存儲(chǔ)非頻繁項(xiàng)集，避免重復(fù)檢索。自頂向下的搜索策略只需要將項(xiàng)目列表存入內(nèi)存即可。

5 實(shí)驗(yàn)結(jié)果及分析

本章將用實(shí)驗(yàn)評(píng)價(jià)CPM算法在抽取上下文偏好規(guī)則中的表現(xiàn)。5.1節(jié)描述了實(shí)驗(yàn)中所使用的真實(shí)的數(shù)據(jù)集。在此基礎(chǔ)上描述了不同類型的實(shí)驗(yàn)結(jié)果。5.2節(jié)的實(shí)驗(yàn)主要用于評(píng)價(jià)CPM算法在抽取有趣條件偏好規(guī)則中的表現(xiàn)。5.3節(jié)對(duì)用最大團(tuán)算法挖掘頻繁集與傳統(tǒng)的Aprori算法以及CONTENUM算法在挖掘效率上進(jìn)行了對(duì)比。所有的實(shí)驗(yàn)程序用C++完成。所有實(shí)驗(yàn)在計(jì)算機(jī)上運(yùn)行通過，計(jì)算機(jī)為Windows操作系統(tǒng)，8 GB內(nèi)存，CPU為i7-4710hq，4核心8線程。

5.1 實(shí)驗(yàn)使用的數(shù)據(jù)集

在本節(jié)的中實(shí)驗(yàn)采用的第1個(gè)真實(shí)數(shù)據(jù)集來源于www.movielens.org。數(shù)據(jù)集由71 567個(gè)用戶對(duì)65 133部電影的10 000 054個(gè)評(píng)分(評(píng)分的范圍為1～5分)，每個(gè)用戶至少標(biāo)記了20部電影，每部電影的屬性描述包括類型、導(dǎo)演、年份、主演等。第2個(gè)數(shù)據(jù)集為last.fm數(shù)據(jù)集，包含1 892個(gè)用戶對(duì)17 632個(gè)音樂家作品的92 834條播放信息，用戶共對(duì)音樂家添加了186 479個(gè)標(biāo)簽(含11 946個(gè)不重復(fù)的標(biāo)簽)。

在電影實(shí)驗(yàn)數(shù)據(jù)集中提取了所有的用戶的評(píng)分?jǐn)?shù)據(jù)。用于比較CPM算法和基于Apriori的算法[21]以及CONTENUM算法對(duì)偏好規(guī)則的抽取效率。在表1中，可以明顯地發(fā)現(xiàn)數(shù)據(jù)集的主要特征，即每個(gè)用戶的ID以及每個(gè)用戶評(píng)價(jià)的電影數(shù)目(電影數(shù)據(jù)集D)，每一部被評(píng)價(jià)的電影的不同特征(屬性值集合L)和由該數(shù)據(jù)集產(chǎn)生的偏好(兩部電影若評(píng)分之差超過一個(gè)閾值則認(rèn)為用戶對(duì)這兩部電影存在偏好)構(gòu)成的成對(duì)的電影偏好(偏好數(shù)據(jù)集P)。

表1 真實(shí)世界的電影偏好數(shù)據(jù)集Tab. 1 Real world preference dataset over movies

用不同規(guī)模的數(shù)據(jù)集訓(xùn)練CPM算法，從而發(fā)現(xiàn)算法的效率差異是極為重要的實(shí)驗(yàn)環(huán)節(jié)，可以通過修改評(píng)分差的閾值來簡(jiǎn)單地生成不同規(guī)模的偏好數(shù)據(jù)集。

5.2 電影數(shù)據(jù)集中的偏好規(guī)則抽取

圖4的(a)和(b)中展示了隨著支持度和可信度的逐漸增加，CPM算法從所有用戶的數(shù)據(jù)集中提取偏好規(guī)則的數(shù)目會(huì)隨著支持度和可信度的增加而不斷減少。當(dāng)最小可信度接近1時(shí)，提取到的規(guī)則數(shù)目急劇下降，這是由于實(shí)驗(yàn)采用的數(shù)據(jù)集極為龐大，很難保證在極高的可信度下規(guī)則不被噪聲數(shù)據(jù)影響。

圖4 支持度和可信度變化時(shí)的規(guī)則數(shù)目和執(zhí)行時(shí)間Fig. 4 Numer of rules and execution time according to variation of confidence and support

圖4的(c)中描述了CPM算法在0.1%到1%的最小支持度閾值(對(duì)應(yīng)三種不同的最小可信度)下的執(zhí)行時(shí)間。從圖中可以看出，最小可信度閾值并不是影響CPM算法執(zhí)行時(shí)間的主要因素，這是因?yàn)镃PM算法基于最小支持度生成候選上下文前綴，通過候選上下文的交叉運(yùn)算來生成規(guī)則，而當(dāng)候選上下文前綴的數(shù)目確定后，算法所需執(zhí)行的時(shí)間便僅與數(shù)據(jù)集的規(guī)模有關(guān)。

通過 CPM 挖掘得到的偏好規(guī)則(其中最小支持度=0.1%)，如表2所示，本文中按支持度列出了前10條偏好規(guī)則, 這些偏好規(guī)則是從400萬條電影偏好數(shù)據(jù)庫中發(fā)現(xiàn)的。例如，規(guī)則顯示了用戶普遍不太偏好動(dòng)作電影(規(guī)則1，2，3，5，9)，規(guī)則4表明在驚險(xiǎn)類的電影中用戶普遍偏好犯罪類型的影片而不喜歡恐怖片；規(guī)則6則顯示了用戶比起紀(jì)錄片更喜歡探險(xiǎn)類的影片；規(guī)則7說明了同樣是喜劇類電影，用戶更喜歡犯罪類型電影，而不是奇幻類電影。規(guī)則8中顯示用戶更喜歡驚險(xiǎn)類電影中的動(dòng)作片而不是喜劇片，在魔幻類電影中，用戶更喜歡正劇而不是喜劇。

表2 挖掘出的偏好規(guī)則Tab. 2 Preference rules discovered from database

圖5采用了一個(gè)固定的支持度閾值K(即用規(guī)則的最小出現(xiàn)次數(shù)代替占數(shù)據(jù)集的最小比例)，展示了在不同K值下，從所有偏好數(shù)據(jù)集中挖掘出的上下文長(zhǎng)度不同的規(guī)則(在不同長(zhǎng)度上下文約束下)以及占所有規(guī)則的比例(最小可信度為0.5)。

圖5 不同長(zhǎng)度上下文的偏好規(guī)則占比Fig. 5 Proportion of preference rules with different length of context

從圖5的實(shí)驗(yàn)結(jié)果中可以看出，所有的規(guī)則基本集中在上下文長(zhǎng)度為0到4的區(qū)間上。當(dāng)K=10時(shí)，76.6%的規(guī)則的上下文長(zhǎng)度為1和2，上下文長(zhǎng)度為0的規(guī)則僅占7.1%; 而當(dāng)K=5 000時(shí)，上下文長(zhǎng)度為1和2的規(guī)則占比為77%，但不存在上下文長(zhǎng)度為4的規(guī)則，上下文長(zhǎng)度為0的規(guī)則占比提升至17.7%。值得注意的是，隨著K值的不斷提高，長(zhǎng)上下文規(guī)則的比例不斷減小，當(dāng)K=20 000時(shí)，規(guī)則的類型減少到僅有兩種(上下文長(zhǎng)度為0和上下文長(zhǎng)度為1的規(guī)則)，其中上下文長(zhǎng)度為0的規(guī)則占比76.9%。這一結(jié)果的出現(xiàn)是十分自然的，這是CPM算法挖掘規(guī)則的特性，同時(shí)說明大部分長(zhǎng)上下文規(guī)則都是在低出現(xiàn)次數(shù)下產(chǎn)生的冗余規(guī)則，也進(jìn)一步地說明最短上下文規(guī)則是最具有簡(jiǎn)潔性和穩(wěn)定性的。

5.3 相關(guān)算法的比較

5.3.1 Movielens數(shù)據(jù)集

圖6(a)比較了CPM算法和基于Apriori的算法以及CONTENUM算法在固定的最小支持度(0.6%)和最小可信度(0.75)下從不同規(guī)模的偏好數(shù)據(jù)庫中提取規(guī)則所花費(fèi)的時(shí)間。

圖6 在Movielens數(shù)據(jù)集下各算法的執(zhí)行時(shí)間Fig. 6 Execute time of different algorithm on Movielens dataset

隨著數(shù)據(jù)集的規(guī)模的增大，基于Apriori的算法所提取規(guī)則耗費(fèi)的時(shí)間以指數(shù)形式增長(zhǎng)，這是由于基于Apriori的算法需要大量的數(shù)據(jù)庫掃描，同時(shí)隨著數(shù)據(jù)集的規(guī)模增大，基于Apriori的算法生成了更多的候選上下文前綴，這加劇了偏好數(shù)據(jù)庫的規(guī)模對(duì)算法執(zhí)行時(shí)間的影響。而CONTENUM算法在數(shù)據(jù)庫規(guī)模增大的情況下，時(shí)間開銷呈線性增長(zhǎng)，數(shù)據(jù)庫規(guī)模較為巨大的情況下，算法消耗的時(shí)間甚至逼近CPM算法，這是由于CONTENUM算法不預(yù)先生成候選的上下文前綴，而采用基于短上下文規(guī)則擴(kuò)展的方式。

基于最大團(tuán)的算法優(yōu)于以上兩種算法，這是因?yàn)镃PM算法采用基于最大團(tuán)的混合搜索的方式生成上下文前綴，這種方式不同于Apriori算法請(qǐng)求大量的數(shù)據(jù)庫掃描，只需要兩次數(shù)據(jù)庫掃描即可生成候選的上下文前綴，從而快速通過上下文前綴交叉運(yùn)算生成可能存在的規(guī)則。

圖6(a)和(c)描述了在相同的偏好數(shù)據(jù)庫的規(guī)模下，不同的支持度閾值和可信度閾值對(duì)算法運(yùn)行時(shí)間的影響。基于Apriori的算法隨著最小支持度閾值的提升執(zhí)行時(shí)間明顯縮短，而CPM算法則幾乎沒有受到影響(見圖(b))，這是因?yàn)樯缮舷挛囊?guī)則前綴的過程僅占時(shí)間開銷的極小的一部分，故即便使用混合搜索進(jìn)行剪枝也難以提升性能，而基于Apriori的算法則受益于此，大幅提升算法的性能(但時(shí)間開銷仍為CPM算法的6倍和CONTENUM算法的4倍以上)。CONTENUM算法隨著支持度和可信度的提高，算法的執(zhí)行時(shí)間均有較大比例的減少，這是因?yàn)樽缘紫蛏系乃惴▋H依賴高于支持度和可信度的規(guī)則進(jìn)行遞歸挖掘。在最小可信度閾值高于0.76時(shí)，CONTENUM算法甚至優(yōu)于CPM算法，這一結(jié)果很好地吻合了當(dāng)支持度和可信度高于某個(gè)閾值后，規(guī)則大量集中在較短的上下文前綴的類型上。CONTENUM算法沒有生成頻繁二項(xiàng)集的過程，當(dāng)規(guī)則僅有長(zhǎng)度為0或長(zhǎng)度為1的上下文前綴時(shí)，它的效率非常高。

5.3.2 Last.fm數(shù)據(jù)集

三種算法在Last.fm上的比較結(jié)果與其在Movielens上的結(jié)論基本一致。需要注意的是，圖7(a)中所有的算法的執(zhí)行時(shí)間都有所增加，原因是Last.fm所提供的數(shù)據(jù)在一條條目下具有更多的標(biāo)簽，且標(biāo)簽的種類更為豐富。圖7(b)和(c)比較了不同最小支持度閾值和不同最小可信度閾值下各算法的執(zhí)行時(shí)間，無論是Apriori算法還是CONTENUM算法的執(zhí)行時(shí)間都有較大的增加，但CPM算法的執(zhí)行時(shí)間變化不大。其中Aprior算法的時(shí)間增加得最為明顯，這是由于Apriori算法生成上下文前綴的時(shí)間呈指數(shù)增長(zhǎng)。CONTENUM算法的時(shí)間開銷的增長(zhǎng)也值得關(guān)注，CONTENUM算法基于自底向上的方式生成上下文，在這種長(zhǎng)前綴且低重復(fù)的狀況下其剪枝的效率下降極為明顯。而CPM算法，只匹配條件符合的團(tuán)，比在短前綴有較多重復(fù)的情況下更加高效。

圖7 在Last.fm數(shù)據(jù)集下各算法的執(zhí)行時(shí)間Fig. 7 Execute time of different algorithm on Last.fm dataset

6 結(jié)語

本文提出了偏好規(guī)則挖掘算法CPM，用于從數(shù)據(jù)庫中挖掘用戶偏好，并在真實(shí)世界電影用戶偏好集上進(jìn)行了一系列實(shí)驗(yàn)，實(shí)驗(yàn)證明本文算法是高效的。實(shí)驗(yàn)得到的條件偏好規(guī)則建立在上下文的基礎(chǔ)上，以可讀的用戶偏好規(guī)則的形式呈現(xiàn)。

在個(gè)性化的查詢領(lǐng)域中，偏好挖掘技術(shù)將變得越來越重要，可以把從用戶偏好樣本中抽取的偏好模型存入知識(shí)庫中，這些模型可以滿足用戶通過SQL語句進(jìn)行的個(gè)性化查詢，現(xiàn)已有很多文獻(xiàn)中都提到了用可擴(kuò)展的SQL即帶有用戶偏好查詢操作的SQL語言來進(jìn)行個(gè)性化查詢。

當(dāng)然在電子商務(wù)普遍應(yīng)用的推薦系統(tǒng)的發(fā)展過程中，偏好挖掘的技術(shù)也是必不可少的。實(shí)際上隨著被推薦商品的數(shù)量急劇增長(zhǎng)，傳統(tǒng)推薦算法的思想即基于由其他用戶提供的對(duì)商品的評(píng)價(jià)與用戶對(duì)購買商品評(píng)價(jià)之間的相似性計(jì)算，越來越受到可擴(kuò)展性的挑戰(zhàn)。偏好技術(shù)的發(fā)展，使得以簡(jiǎn)潔偏好形式出現(xiàn)的用戶偏好的自動(dòng)推理變得更有意義，有望解決可擴(kuò)展性的問題。

下一步將研究如何利用評(píng)測(cè)規(guī)則對(duì)挖掘出的偏好規(guī)則進(jìn)行過濾；對(duì)用戶偏好的評(píng)價(jià)要能跳出一般的布爾判斷；嘗試建立以偏好挖掘算法為核心的偏好挖掘框架模型。

References)

[1] ZAKI M J. Scalable algorithms for association mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2000,12(3):372-390.

[2] 張志宏, 寇紀(jì)淞, 陳富贊, 等. 基于遺傳算法的顧客購買行為特征提取[J]. 模式識(shí)別與人工智能, 2010, 23(2): 256-266) (ZHANG Z H, KOU J S, CHEN F Z, et al. Feature extraction of customer purchase behavior based on genetic algorithm[J]. Pattern Recognition and ArtifIcial Intelligence, 2010, 23(2): 256-266.)

[3] AMO S, DIALLO M S, DIOP C T, et al. Contextual preference mining for user profile construction [J]. Information Systems, 2015,49(C):182-199.

[4] HOLLAND S, ESTER M, KIEBLING W. Preference mining: a novel approach on mining user preferences for personalized applications[C]// Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer, 2003: 204-216.

[5] AMO S D, MARCOS L P, ALVES G, et al. Mining user contextual preferences[J]. Journal of Information and Data Management, 2013,4(1):37-46.

[6] CHOMICKI J. Preference formulas in relational queries[J]. ACM Transactions on Database System, 2003, 28(4): 427-466.

[7] PEREIRA F S F, AMO S D. Evaluation of conditional preference queries[J]. Journal of Information and Data Management, 2010,1(3):521-536.

[8] AGRAWAL R, RANTZAU R, TERZI E. Context-sensitive ranking[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data. New York: ACM, 2006:383-394.

[9] DAVEY B A, PRIESTLEY H A. Introduction to Lattices and Order[M]. Cambridge: Cambridge University Press, 2002:1277-1286.

[10] 劉玫蓮, 劉同存, 肖吉軍. 基于雙向關(guān)聯(lián)規(guī)則的網(wǎng)絡(luò)消費(fèi)者偏好挖掘研究[J]. 微電子與計(jì)算機(jī), 2013,3(3): 21-26.(LIU M L, LIU T C, XIAO J J, Web consumer preference mining based on bidirectional association rules[J]. Microelectronics and Computer, 2013, 3(3): 21-26.)

[11] 孟祥福,馬宗民,李昕,等. 基于上下文偏好的數(shù)據(jù)庫查詢結(jié)果Top-K排序方法[J]．計(jì)算機(jī)學(xué)報(bào), 2014,37(9): 1986-1998.(MENG X F, MA Z M, LI X, et al. A Top-K query results approach based on contextual preferences for Web database[J]. Chinese Journal of Computers, 2014,37(9): 1986-1998.)

[12] AMO S D, DIALLO M S, DIOP C T, et al. Mining contextual preference rules for building user profiles[C]// Proceedings of the 14th International Conference Data Warehousing and Knowledge Discovery. Berlin: Springer, 2012, 7448: 229-242.

[13] ZHU H, CHEN E, YU K, et al. Mining personal context-aware preferences for mobile users[C]// Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 1212-1217.

[14] DEMBCZYNSK K, KOTLOWSK W, SLOWINSKI R. Learning of Rule Ensembles for Multiple Attribute Ranking Problems[M]. Berlin: Springer, 2011: 217-247.

[15] CHOI S M, KO S K, HAN Y S. A movie recommendation algorithm based on genre correlations[J]. Expert Systems with Applications, 2012, 39(9): 8079-8085.

[16] LIU B, HSU W, MAY. Integrating classification and association rule mining[EB/OL].[2016- 11- 20]. http://kckckc.myweb.hinet.net/paper/Integrating_Classification_and_Association_Rule_Mining.pdf.

[17] SAVASERE A, OMIECINSKI E, NAVATHE S B. An efficient algorithm for mining association rules in large databases[EB/OL].[2016- 11- 20]. http://omega.sp.susu.ru/books/acm_sigmod/vol1/is5/VLDB95/P432.PDF.

[18] TOIVONEN H. Sampling large databases for association rules[C]// Proceedings of the 22nd International Conference on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann Publishers, 1996:134-145.

[19] ZAKI M J, PARTHASARATHY S, LI W, et al. Evaluation of sampling for data mining of association rules[C]// Proceedings of the 7th International Workshop on Research Issues in Data Engineering. Washington, DC: IEEE Computer Society, 1997: 42-50.

[20] LI W, HAN J, PEI J. CMAR: Accurate and efficient classification based on multiple class-association rules[C]// Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2001: 369-376.

[21] AGRAWAL R, MANNILA H, SRIKANT R. Fast discovery of association rules[J].Advances in Knowledge Discovery and Data Mining, 1996, 32(3): 307-328.

This work is partially supported by the National Natural Science Foundation of China (61572419, 61572418，61403328).

TANZheng, born in 1968, M. S., associate professor. His research interests include data mining, natural language processing.

LIUJinglei, born in 1970, M. S., associate professor. His research interests include artificial intelligence, theoretical computer science.

YUHang, born in 1998. His research interests include data mining, randomized algorithm.

ConditionalpreferenceminingbasedonMaxClique

TAN Zheng, LIU JingLei*, YU Hang

(SchoolofComputerandControlEngineering,YantaiUniversity,YantaiShandong264005,China)

In order to solve the problem that conditional constraints (context constraints) for personalized queries in database were not fully considered, a constraint model was proposed where the contexti+?i-|Xmeans that the user prefersi+thani-based on the constraint of contextX. Association rules mining algorithm based on MaxClique was used to obtain user preferences, and Conditional Preference Mining (CPM) algorithm combined with context obtained preference rules was proposed to obtain user preferences. The experimental results show that the context preference mining model has strong preference expression ability. At the same time, under the different parameters of minimum support, minimum confidence and data scale, the experimental results of preferences mining algorithm of CPM compared with Apriori algorithm and CONTENUM algorithm show that the proposed CPM algorithm can obviously improve the generation efficiency of user preferences.

MaxClique;association rule;preference database;conditional preference rule;preference mining

2017- 05- 16;

2017- 06- 07。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572419，61572418，61403328)。

譚征(1968—)，男，山東乳山人，副教授，碩士，主要研究方向：數(shù)據(jù)挖掘、自然語言處理； 劉驚雷(1970—)，男，山西臨猗人，副教授，碩士，CCF會(huì)員，主要研究方向：人工智能、理論計(jì)算機(jī)科學(xué)； 余航(1998—)，男，江西上饒人，主要研究方向：數(shù)據(jù)挖掘、隨機(jī)化算法。

1001- 9081(2017)11- 3107- 08

10.11772/j.issn.1001- 9081.2017.11.3107

(*通信作者電子郵箱jinglei_liu@ sina.com)

TP311

A