聶規(guī)劃，游懷杰，孟 潔

(武漢理工大學(xué) 經(jīng)濟(jì)學(xué)院，湖北 武漢430070)

隨著三網(wǎng)融合進(jìn)程的不斷加快，數(shù)字家庭產(chǎn)業(yè)開(kāi)始迅猛發(fā)展。除了提供各種多媒體、物聯(lián)網(wǎng)服務(wù)外，數(shù)字家庭還提供包含數(shù)字高清交互購(gòu)物平臺(tái)、家庭社群互動(dòng)、數(shù)字家庭文化公益、數(shù)字醫(yī)療和智能監(jiān)控等在內(nèi)的諸多服務(wù)。然而，隨著數(shù)字家庭服務(wù)內(nèi)容的不斷擴(kuò)充，用戶(hù)量不斷增加，運(yùn)營(yíng)商和用戶(hù)所面對(duì)的信息量巨大，用戶(hù)要想從大量應(yīng)用服務(wù)中找到自己所需要的，或潛在感興趣的服務(wù)變得更加困難。對(duì)運(yùn)營(yíng)商來(lái)說(shuō)，如何從紛雜的信息中發(fā)現(xiàn)用戶(hù)消費(fèi)的特點(diǎn)，并為用戶(hù)提供個(gè)性化的服務(wù)以加深用戶(hù)體驗(yàn)成為其必須考慮的問(wèn)題。因此，建立一個(gè)面向數(shù)字家庭服務(wù)資源的推薦系統(tǒng)成為必然趨勢(shì)。

目前主流的推薦方法有協(xié)同過(guò)濾推薦，基于內(nèi)容的推薦和關(guān)聯(lián)規(guī)則推薦等［1］，筆者主要討論關(guān)聯(lián)規(guī)則推薦在數(shù)字家庭領(lǐng)域的應(yīng)用。關(guān)聯(lián)規(guī)則挖掘是近年來(lái)知識(shí)發(fā)現(xiàn)研究中一個(gè)很重要的課題，自1993 年AGRAWAL 等首次提出關(guān)聯(lián)規(guī)則及Apriori 算法［2］以來(lái)，出現(xiàn)了很多基于它的改進(jìn)算法，如基于劃分的方法，基于hash 的方法，基于采樣的方法和減少交易個(gè)數(shù)的方法等。此外，也有學(xué)者探索出全新的挖掘算法，以避開(kāi)Apriori 算法自身的缺陷，如HAN 等提出的FP－Growth 算法等。還有一些學(xué)者提出了某些模型，注重對(duì)所挖掘規(guī)則的價(jià)值進(jìn)行評(píng)估［3］。

當(dāng)今的互聯(lián)網(wǎng)領(lǐng)域憑借自身獲取信息全面與實(shí)時(shí)的優(yōu)勢(shì)，在關(guān)聯(lián)推薦方面已有比較成熟的應(yīng)用。如亞馬遜就提供了包括“經(jīng)常一起購(gòu)買(mǎi)的商品”，“購(gòu)買(mǎi)此商品的顧客也同時(shí)購(gòu)買(mǎi)”等卓有成效的關(guān)聯(lián)推薦;另外，京東商城、優(yōu)酷、豆瓣等也提供各自的關(guān)聯(lián)推薦服務(wù)。然而，由于數(shù)字家庭還處于發(fā)展階段，各種軟硬件技術(shù)還不夠成熟，目前很少有學(xué)者進(jìn)行數(shù)字家庭領(lǐng)域的關(guān)聯(lián)推薦研究，大部分仍停留在對(duì)互聯(lián)網(wǎng)商品、數(shù)字電視節(jié)目的推薦上。如趙宏霞等研究單一商品不同時(shí)間下需求量的關(guān)聯(lián)性［4］，王磊等研究周期性出現(xiàn)的不同商品之間的空間關(guān)聯(lián)性［5］，LAI 等提出基于云的數(shù)字電視節(jié)目推薦平臺(tái)［6］，徐江山等提出利用Rankboost 排序算法、Bayes 統(tǒng)計(jì)算法和簡(jiǎn)單統(tǒng)計(jì)算法3 種基于統(tǒng)計(jì)模型的算法實(shí)現(xiàn)數(shù)字電視用戶(hù)特征的提取與節(jié)目推薦［7］。目前，幾乎還沒(méi)有針對(duì)數(shù)字家庭領(lǐng)域的其他服務(wù)類(lèi)型進(jìn)行關(guān)聯(lián)推薦的方法研究。因此，有必要立足于數(shù)字家庭自身的技術(shù)特點(diǎn)，所提供的服務(wù)類(lèi)型和需要達(dá)到的推薦目標(biāo)等，應(yīng)用合適的關(guān)聯(lián)技術(shù)來(lái)建立面向數(shù)字家庭的關(guān)聯(lián)推薦體系。

1 數(shù)字家庭與關(guān)聯(lián)推薦技術(shù)

數(shù)字家庭因其特有的應(yīng)用技術(shù)與服務(wù)，同互聯(lián)網(wǎng)等領(lǐng)域鮮明地區(qū)分開(kāi)來(lái)，但其并不完善的用戶(hù)交互渠道也決定了在現(xiàn)階段它并不適合所有推薦技術(shù)。關(guān)聯(lián)推薦基于其共性推薦的特征，用戶(hù)的消費(fèi)記錄就是其數(shù)據(jù)源，簡(jiǎn)單易得，適合為數(shù)字家庭用戶(hù)發(fā)現(xiàn)其感興趣的服務(wù)資源。

筆者采用的關(guān)聯(lián)推薦技術(shù)主要包括兩種:關(guān)聯(lián)規(guī)則推薦和時(shí)序關(guān)聯(lián)規(guī)則推薦。前者通過(guò)對(duì)用戶(hù)消費(fèi)記錄進(jìn)行挖掘，找出經(jīng)常被一起消費(fèi)的服務(wù)資源。若大量用戶(hù)單次消費(fèi)了相同的某幾種服務(wù)資源，可能表明這幾種服務(wù)資源間存在某種關(guān)聯(lián)關(guān)系，用戶(hù)可能存在進(jìn)行一次性消費(fèi)的需要，如牛奶與面包。在數(shù)字家庭中主要考慮在數(shù)字高清交互購(gòu)物平臺(tái)中進(jìn)行應(yīng)用。后者則考慮了用戶(hù)消費(fèi)的時(shí)間先后順序，以關(guān)聯(lián)規(guī)則挖掘?yàn)榛A(chǔ)，并考慮消費(fèi)時(shí)間先后與間隔來(lái)獲得時(shí)序關(guān)聯(lián)規(guī)則，并根據(jù)規(guī)則進(jìn)行推薦。當(dāng)用戶(hù)消費(fèi)某時(shí)序規(guī)則中的第一個(gè)服務(wù)資源時(shí)，推薦系統(tǒng)則將相應(yīng)規(guī)則中的下一個(gè)或若干個(gè)服務(wù)資源推薦給用戶(hù)。比如在數(shù)字醫(yī)療中，數(shù)字家庭將提供包括電視掛號(hào)、醫(yī)院查詢(xún)、醫(yī)師介紹、醫(yī)院地圖等服務(wù)，這組服務(wù)在被使用時(shí)大多存在某種時(shí)間先后順序，這也就決定了建立基于時(shí)序關(guān)聯(lián)規(guī)則推薦的必要性。

2 數(shù)字家庭服務(wù)資源關(guān)聯(lián)推薦體系的設(shè)計(jì)

根據(jù)數(shù)字家庭技術(shù)特征和用戶(hù)的消費(fèi)特點(diǎn)，筆者提出了數(shù)字家庭服務(wù)資源關(guān)聯(lián)推薦體系。通過(guò)結(jié)合關(guān)聯(lián)規(guī)則推薦和時(shí)序關(guān)聯(lián)規(guī)則推薦兩種主要形式，以用戶(hù)交易庫(kù)和服務(wù)資源庫(kù)為主要數(shù)據(jù)源，利用相應(yīng)的挖掘技術(shù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘，并經(jīng)由推薦模塊進(jìn)行推薦資源輸出。其體系結(jié)構(gòu)如圖1 所示。

圖1 數(shù)字家庭服務(wù)資源關(guān)聯(lián)推薦系統(tǒng)體系結(jié)構(gòu)

該結(jié)構(gòu)分為3 個(gè)部分，即服務(wù)資源層、離線(xiàn)關(guān)聯(lián)規(guī)則挖掘?qū)雍驮诰€(xiàn)推薦層。服務(wù)資源層主要是數(shù)字家庭系統(tǒng)所提供的各類(lèi)服務(wù)資源，是進(jìn)行挖掘和推薦的基礎(chǔ)。離線(xiàn)關(guān)聯(lián)規(guī)則挖掘?qū)邮沁M(jìn)行規(guī)則挖掘的過(guò)程，首先采用數(shù)據(jù)倉(cāng)庫(kù)技術(shù)對(duì)用戶(hù)原始消費(fèi)數(shù)據(jù)進(jìn)行預(yù)處理產(chǎn)生標(biāo)準(zhǔn)消費(fèi)數(shù)據(jù)，然后利用挖掘模塊從數(shù)據(jù)倉(cāng)庫(kù)中提取相關(guān)數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘和時(shí)序關(guān)聯(lián)規(guī)則挖掘，最后將生成的規(guī)則存入關(guān)聯(lián)規(guī)則庫(kù)和時(shí)序關(guān)聯(lián)規(guī)則庫(kù)。在線(xiàn)推薦層是與用戶(hù)進(jìn)行實(shí)時(shí)交互，根據(jù)用戶(hù)選擇消費(fèi)的服務(wù)資源，將離線(xiàn)部分生成的關(guān)聯(lián)規(guī)則與數(shù)據(jù)庫(kù)中該用戶(hù)的歷史消費(fèi)數(shù)據(jù)信息進(jìn)行分析，剔除用戶(hù)已消費(fèi)過(guò)的服務(wù)資源，產(chǎn)生最終推薦，并利用數(shù)字電視終端將推薦結(jié)果推送給用戶(hù)。

3 離線(xiàn)關(guān)聯(lián)規(guī)則挖掘

3.1 系統(tǒng)閾值的設(shè)定

在進(jìn)行(時(shí)序)關(guān)聯(lián)規(guī)則挖掘前，首先需要確定最小支持度和最小置信度兩個(gè)閾值。在Apriori算法中，支持度是對(duì)關(guān)聯(lián)規(guī)則重要性的衡量，表示該規(guī)則出現(xiàn)的頻度;置信度則是對(duì)關(guān)聯(lián)規(guī)則準(zhǔn)確度的衡量，表示該規(guī)則的有趣性。另外，針對(duì)數(shù)字家庭自身的特征，用戶(hù)一般很少一次性消費(fèi)多項(xiàng)服務(wù)資源，而是存在一定的時(shí)間間隔，這與進(jìn)行關(guān)聯(lián)規(guī)則挖掘所需要的數(shù)據(jù)要求不符。因此，在進(jìn)行系統(tǒng)閾值設(shè)定時(shí)，需要確定一個(gè)時(shí)間閾值，以預(yù)設(shè)定的時(shí)間為單位采集用戶(hù)的消費(fèi)項(xiàng)來(lái)組成事務(wù)，如以每?jī)商鞛椴杉瘑卧Ｗ詈筮€要設(shè)定提供推薦時(shí)的TOP－N 值。

3.2 數(shù)據(jù)準(zhǔn)備

數(shù)字家庭關(guān)聯(lián)推薦技術(shù)所需要的數(shù)據(jù)源主要有服務(wù)資源庫(kù)和所有用戶(hù)的消費(fèi)記錄，后者包含消費(fèi)的資源ID 和消費(fèi)時(shí)間。由于涉及到多個(gè)數(shù)據(jù)源，多種數(shù)據(jù)類(lèi)型，同時(shí)也面臨許多不完整的、有噪聲的和不一致的臟數(shù)據(jù)，因此在挖掘模塊進(jìn)行挖掘工作之前，系統(tǒng)還需要對(duì)源數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理的主要任務(wù)是數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)歸約。主要完成以下目標(biāo):掃描用戶(hù)消費(fèi)數(shù)據(jù)表，以每?jī)商鞛椴杉瘑卧蠁斡脩?hù)的消費(fèi)項(xiàng)目，生成事務(wù)表，事務(wù)表包括唯一的ID、消費(fèi)項(xiàng)目及消費(fèi)時(shí)間;丟棄只包含一個(gè)項(xiàng)目的事務(wù);并將各事務(wù)中的消費(fèi)項(xiàng)按字典序排列。而進(jìn)行時(shí)序規(guī)則挖掘的事務(wù)則要求用一個(gè)二元組＜I，T ＞表示記錄中的每個(gè)項(xiàng)(即時(shí)序項(xiàng))，其中，I為項(xiàng)，T 為該時(shí)序項(xiàng)的時(shí)間戳，每一條記錄中的時(shí)序項(xiàng)以各自時(shí)間戳的大小進(jìn)行升序排列。

3.3 關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)是Apriori 經(jīng)典算法，而針對(duì)該算法的一些固有缺陷與不足［8］，筆者采用基于臨時(shí)表的Apriori 改進(jìn)算法［9］，即通過(guò)將(k－1)－項(xiàng)集的首項(xiàng)集加入到臨時(shí)表中，再把尾項(xiàng)與其不同的其他項(xiàng)集加入到表中，生成k－項(xiàng)集，再計(jì)算k－項(xiàng)集的頻度，若大于最小支持度，則認(rèn)定其為頻繁項(xiàng)并保存，否則刪除，依次循環(huán)，直至生成所有的頻繁項(xiàng)。算法步驟如下:

關(guān)聯(lián)規(guī)則挖掘要輸入用戶(hù)消費(fèi)事務(wù)數(shù)據(jù)庫(kù)D;最小支持度閾值min_sup;最小置信度閾值min_conf。輸出關(guān)聯(lián)規(guī)則。

(1)掃描用戶(hù)消費(fèi)事務(wù)數(shù)據(jù)庫(kù)D，計(jì)算各1－項(xiàng)集出現(xiàn)的頻次，找到所有支持度大于最小支持度閾值的項(xiàng)集，即頻繁1－項(xiàng)集;并建立臨時(shí)數(shù)據(jù)庫(kù)表D1;

(2)刪除不存在頻繁(k－1)－項(xiàng)集的事務(wù)，減少下次掃描數(shù)據(jù)庫(kù)的記錄數(shù);

(3)將頻繁(k－1)－項(xiàng)集按字典序進(jìn)行兩兩連接，產(chǎn)生候選k－項(xiàng)集;

(4)從數(shù)據(jù)庫(kù)中刪除其中僅含(k－1)項(xiàng)的項(xiàng)集，減少下次掃描數(shù)據(jù)庫(kù)的記錄數(shù);

(5)掃描數(shù)據(jù)庫(kù)，找到所有支持度大于最小支持度閾值的項(xiàng)集，即頻繁k－項(xiàng)集，更新臨時(shí)數(shù)據(jù)庫(kù)表Dk;重復(fù)步驟(2)～步驟(5);

(6)根據(jù)得到的頻繁k－項(xiàng)集建立關(guān)聯(lián)規(guī)則，形如A B，計(jì)算規(guī)則置信度，若大于最小置信度閾值，則認(rèn)定為有意義的關(guān)聯(lián)規(guī)則。

3.4 時(shí)序關(guān)聯(lián)規(guī)則挖掘

輸入用戶(hù)消費(fèi)服務(wù)資源的事務(wù)數(shù)據(jù)庫(kù)D;認(rèn)定興趣連接時(shí)間段TL;最小支持度閾值min_sup;最小置信度閾值min_conf。輸出時(shí)序關(guān)聯(lián)規(guī)則。

(1)調(diào)用預(yù)定義算法，將輸入的原始關(guān)系型數(shù)據(jù)表轉(zhuǎn)換為時(shí)序數(shù)據(jù)表。將用戶(hù)消費(fèi)的服務(wù)資源記錄轉(zhuǎn)化成形如＜Ii，Ti＞的樣式，Ii為項(xiàng)集I的第i 個(gè)消費(fèi)的資源，Ti為消費(fèi)的時(shí)間;

(2)調(diào)用Apriori 算法，對(duì)步驟(1)所生成的時(shí)序數(shù)據(jù)表進(jìn)行挖掘，找出所有支持度大于預(yù)設(shè)最小支持度閾值的頻繁項(xiàng)集;

(3)對(duì)于步驟(2)找出的頻繁項(xiàng)集，經(jīng)過(guò)數(shù)據(jù)庫(kù)掃描得到包含該項(xiàng)集的所有記錄，組成臨時(shí)數(shù)據(jù)表;

(4)列出該項(xiàng)集所有可能的時(shí)序關(guān)聯(lián)規(guī)則，對(duì)每一個(gè)時(shí)序關(guān)聯(lián)規(guī)則進(jìn)行如下操作，找到所有滿(mǎn)足最小支持度、置信度的時(shí)序關(guān)聯(lián)規(guī)則［10］。①將輸入的時(shí)序關(guān)聯(lián)規(guī)則按照“ ”符拆分為左部項(xiàng)集L和右部項(xiàng)集R;②定位到臨時(shí)數(shù)據(jù)表的第i 條記錄(i =1，i+ +)，提取對(duì)應(yīng)于項(xiàng)集L 和項(xiàng)集R 的時(shí)序項(xiàng)(集)＜L，TLi＞和＜R，TRi＞;③計(jì)算時(shí)序項(xiàng)之間的時(shí)間差:△Ti= TRi－TLi，若△Ti＞0，保存該結(jié)果，返回第②步，直至處理完臨時(shí)數(shù)據(jù)表中的所有記錄;④將所有保存的結(jié)果進(jìn)行時(shí)間規(guī)則判別運(yùn)算，輸出該時(shí)序關(guān)聯(lián)規(guī)則滿(mǎn)足最小支持度，且時(shí)間差△Ti在TL 內(nèi)的時(shí)序關(guān)聯(lián)規(guī)則。

4 在線(xiàn)推薦設(shè)計(jì)

系統(tǒng)對(duì)用戶(hù)進(jìn)行在線(xiàn)推薦時(shí)，首先提取用戶(hù)當(dāng)前消費(fèi)服務(wù)資源的ID 并遍歷規(guī)則表，找出左部項(xiàng)為該ID 的所有關(guān)聯(lián)規(guī)則，并提取相應(yīng)右部項(xiàng)的資源ID作為候選推薦集;同時(shí)識(shí)別用戶(hù)，獲取該用戶(hù)的歷史消費(fèi)記錄;然后將候選推薦集和用戶(hù)的歷史消費(fèi)記錄進(jìn)行去重操作，獲得最終的推薦集;最后將結(jié)果按置信度排序，按所設(shè)定的系統(tǒng)閾值把TOP－N 返回給用戶(hù)，其具體推薦流程如圖2 所示。

圖2 在線(xiàn)推薦流程

在數(shù)字家庭中，關(guān)聯(lián)推薦主要用于如圖3 所示的業(yè)務(wù)場(chǎng)景:①時(shí)序關(guān)聯(lián)的應(yīng)用。用戶(hù)選擇進(jìn)入“數(shù)字醫(yī)療”頻道，當(dāng)用戶(hù)點(diǎn)擊某個(gè)醫(yī)院的標(biāo)識(shí)時(shí)，系統(tǒng)可以通過(guò)由時(shí)序關(guān)聯(lián)挖掘出的有效規(guī)則進(jìn)行判斷，大部分用戶(hù)選定醫(yī)院后都會(huì)在TL 時(shí)間內(nèi)選擇電視掛號(hào)，于是系統(tǒng)自動(dòng)為用戶(hù)推送電視掛號(hào)服務(wù)，用戶(hù)可以在了解醫(yī)師情況后進(jìn)行掛號(hào)，然后按時(shí)前往醫(yī)院就醫(yī)。②電子商務(wù)應(yīng)用。用戶(hù)進(jìn)入數(shù)字高清交互購(gòu)物平臺(tái)，瀏覽各商品資源，當(dāng)用戶(hù)有意于某商品而進(jìn)入該單品瀏覽界面時(shí)，系統(tǒng)根據(jù)關(guān)聯(lián)規(guī)則挖掘出的規(guī)則庫(kù)內(nèi)容，查找與該商品規(guī)則匹配的右部項(xiàng)，并進(jìn)行推薦;在達(dá)成交易后同樣進(jìn)行一次推薦項(xiàng)的推送。

圖3 關(guān)聯(lián)推薦方法應(yīng)用的業(yè)務(wù)場(chǎng)景示例

5 結(jié)論

筆者以知識(shí)發(fā)現(xiàn)中的關(guān)聯(lián)規(guī)則挖掘理論為基礎(chǔ)，針對(duì)數(shù)字家庭的特點(diǎn)，設(shè)計(jì)了基于時(shí)序關(guān)聯(lián)規(guī)則的推薦體系。所提出的關(guān)聯(lián)關(guān)系挖掘方法能滿(mǎn)足關(guān)聯(lián)推薦服務(wù)的基本需求，達(dá)到為用戶(hù)提供關(guān)聯(lián)服務(wù)資源的基本目的，為日后建立數(shù)字家庭智能推薦系統(tǒng)提供有力的技術(shù)支撐，有助于提高數(shù)字家庭用戶(hù)的消費(fèi)體驗(yàn)。

［1］ 劉建國(guó)，周濤，汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展［J］.自然科學(xué)進(jìn)展，2009，19(1):1－15.

［2］ AGRAWAL R，IMIELINSKI T，SWAMI A. Mining association rules between sets of items in large database［C］// Proc of the 1993 ACM SIGMOD Conference.Washington:［s.n.］，1993:207－216.

［3］ ZAILANI A，TUTUT H，NORAZIAH A.Mining significant association rules from educational data using critical relative support approach ［J］. Procedia－Social and Behavioral Sciences，2011，28(1):97－101.

［4］ 趙宏霞，楊皎平，郭嗣琮.基于時(shí)序關(guān)聯(lián)規(guī)則的客戶(hù)需求預(yù)測(cè)方法研究［J］. 科技和產(chǎn)業(yè)，2004，4(11):22－26.

［5］ 王磊，譚躍進(jìn). 基于聚類(lèi)的快速時(shí)域關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法［J］.計(jì)算機(jī)仿真，2005，22(7):36－39.

［6］ LAI C F，CHANG J H，HUB C C，et al. A cloud－based program recommendation system for digital TV platforms［J］. Future Generation Computer Systems，2011，27(3):823－835.

［7］ 徐江山，盧增祥，路海明.數(shù)字電視節(jié)目推薦系統(tǒng)中的統(tǒng)計(jì)算法［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2008，48(10):1562－1564.

［8］ 張?jiān)茲?，于治樓，張化?關(guān)聯(lián)規(guī)則中頻繁項(xiàng)集高效挖掘的研究［J］. 計(jì)算機(jī)工程與應(yīng)用，2011，47(3):139－141.

［9］ 高偉峰，胡勇，胡江洪.基于臨時(shí)表的Apriori 改進(jìn)算法［J］.計(jì)算機(jī)與信息技術(shù)，2005(11):1－3.

［10］章杰鑫，張烈平.基于時(shí)序關(guān)聯(lián)規(guī)則的商品需求預(yù)測(cè)［J］.計(jì)算機(jī)工程，2009，35(22):65－67.