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

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

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

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

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

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

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

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

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

根據(jù)數(shù)字家庭技術(shù)特征和用戶的消費(fèi)特點(diǎn)，筆者提出了數(shù)字家庭服務(wù)資源關(guān)聯(lián)推薦體系。通過結(jié)合關(guān)聯(lián)規(guī)則推薦和時(shí)序關(guān)聯(lián)規(guī)則推薦兩種主要形式，以用戶交易庫和服務(wù)資源庫為主要數(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ù)資源層、離線關(guān)聯(lián)規(guī)則挖掘?qū)雍驮诰€推薦層。服務(wù)資源層主要是數(shù)字家庭系統(tǒng)所提供的各類服務(wù)資源，是進(jìn)行挖掘和推薦的基礎(chǔ)。離線關(guān)聯(lián)規(guī)則挖掘?qū)邮沁M(jìn)行規(guī)則挖掘的過程，首先采用數(shù)據(jù)倉庫技術(shù)對用戶原始消費(fèi)數(shù)據(jù)進(jìn)行預(yù)處理產(chǎn)生標(biāo)準(zhǔn)消費(fèi)數(shù)據(jù)，然后利用挖掘模塊從數(shù)據(jù)倉庫中提取相關(guān)數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘和時(shí)序關(guān)聯(lián)規(guī)則挖掘，最后將生成的規(guī)則存入關(guān)聯(lián)規(guī)則庫和時(shí)序關(guān)聯(lián)規(guī)則庫。在線推薦層是與用戶進(jìn)行實(shí)時(shí)交互，根據(jù)用戶選擇消費(fèi)的服務(wù)資源，將離線部分生成的關(guān)聯(lián)規(guī)則與數(shù)據(jù)庫中該用戶的歷史消費(fèi)數(shù)據(jù)信息進(jìn)行分析，剔除用戶已消費(fèi)過的服務(wù)資源，產(chǎn)生最終推薦，并利用數(shù)字電視終端將推薦結(jié)果推送給用戶。

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

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

在進(jìn)行(時(shí)序)關(guān)聯(lián)規(guī)則挖掘前，首先需要確定最小支持度和最小置信度兩個(gè)閾值。在Apriori算法中，支持度是對關(guān)聯(lián)規(guī)則重要性的衡量，表示該規(guī)則出現(xiàn)的頻度;置信度則是對關(guān)聯(lián)規(guī)則準(zhǔn)確度的衡量，表示該規(guī)則的有趣性。另外，針對數(shù)字家庭自身的特征，用戶一般很少一次性消費(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í)間為單位采集用戶的消費(fèi)項(xiàng)來組成事務(wù)，如以每兩天為采集單元。最后還要設(shè)定提供推薦時(shí)的TOP－N 值。

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

數(shù)字家庭關(guān)聯(lián)推薦技術(shù)所需要的數(shù)據(jù)源主要有服務(wù)資源庫和所有用戶的消費(fèi)記錄，后者包含消費(fèi)的資源ID 和消費(fèi)時(shí)間。由于涉及到多個(gè)數(shù)據(jù)源，多種數(shù)據(jù)類型，同時(shí)也面臨許多不完整的、有噪聲的和不一致的臟數(shù)據(jù)，因此在挖掘模塊進(jìn)行挖掘工作之前，系統(tǒng)還需要對源數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理的主要任務(wù)是數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)歸約。主要完成以下目標(biāo):掃描用戶消費(fèi)數(shù)據(jù)表，以每兩天為采集單元整合單用戶的消費(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)典算法，而針對該算法的一些固有缺陷與不足［8］，筆者采用基于臨時(shí)表的Apriori 改進(jìn)算法［9］，即通過將(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ī)則挖掘要輸入用戶消費(fèi)事務(wù)數(shù)據(jù)庫D;最小支持度閾值min_sup;最小置信度閾值min_conf。輸出關(guān)聯(lián)規(guī)則。

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

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

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

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

(5)掃描數(shù)據(jù)庫，找到所有支持度大于最小支持度閾值的項(xiàng)集，即頻繁k－項(xiàng)集，更新臨時(shí)數(shù)據(jù)庫表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ī)則挖掘

輸入用戶消費(fèi)服務(wù)資源的事務(wù)數(shù)據(jù)庫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ù)表。將用戶消費(fèi)的服務(wù)資源記錄轉(zhuǎn)化成形如＜Ii，Ti＞的樣式，Ii為項(xiàng)集I的第i 個(gè)消費(fèi)的資源，Ti為消費(fèi)的時(shí)間;

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

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

(4)列出該項(xiàng)集所有可能的時(shí)序關(guān)聯(lián)規(guī)則，對每一個(gè)時(shí)序關(guān)聯(lián)規(guī)則進(jì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+ +)，提取對應(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ī)則滿足最小支持度，且時(shí)間差△Ti在TL 內(nèi)的時(shí)序關(guān)聯(lián)規(guī)則。

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

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

圖2 在線推薦流程

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

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

5 結(jié)論

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

［1］ 劉建國，周濤，汪秉宏.個(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ī)則的客戶需求預(yù)測方法研究［J］. 科技和產(chǎn)業(yè)，2004，4(11):22－26.

［5］ 王磊，譚躍進(jìn). 基于聚類的快速時(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ù)測［J］.計(jì)算機(jī)工程，2009，35(22):65－67.