王蒙湘，李芳芳，谷 峪，于 戈

東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院 計算機(jī)科學(xué)系，沈陽 110819

交互式數(shù)據(jù)探索綜述*

王蒙湘，李芳芳，谷 峪，于 戈+

東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院 計算機(jī)科學(xué)系，沈陽 110819

大規(guī)模數(shù)據(jù)集已經(jīng)超過TB和PB級，現(xiàn)有的技術(shù)可以收集和存儲大量的信息。雖然數(shù)據(jù)庫管理系統(tǒng)一直在不斷提高提供復(fù)雜的多種數(shù)據(jù)管理的能力，但是管理查詢工具并不能滿足大數(shù)據(jù)的需求，如何精準(zhǔn)理解和探索這些大規(guī)模數(shù)據(jù)集仍然是一個巨大的挑戰(zhàn)。交互式數(shù)據(jù)探索（interactive data exploration，IDE）的關(guān)注點(diǎn)是強(qiáng)調(diào)交互、探索和發(fā)現(xiàn)，能讓用戶從海量的數(shù)據(jù)中用最小的代價更精確地找到他們需要的信息。首先對交互式數(shù)據(jù)探索及其應(yīng)用背景進(jìn)行了介紹，總結(jié)了通用的探索模型和IDE的特點(diǎn)，分析了交互式數(shù)據(jù)探索中的查詢推薦技術(shù)和查詢結(jié)果優(yōu)化技術(shù)的現(xiàn)狀；隨后分別對IDE原型系統(tǒng)進(jìn)行了分析和比較；最后給出了關(guān)于交互式數(shù)據(jù)探索技術(shù)的總結(jié)和展望。

交互式數(shù)據(jù)探索；查詢推薦；查詢結(jié)果優(yōu)化；用戶反饋；機(jī)器學(xué)習(xí)

1 引言

目前，隨著大數(shù)據(jù)研究的興起，數(shù)據(jù)探索這種探索數(shù)據(jù)價值的方式，引起了人們的關(guān)注[1]。數(shù)據(jù)探索在某些領(lǐng)域也被稱為探索式搜索。2014年，數(shù)據(jù)庫領(lǐng)域頂級會議SIGMOD針對數(shù)據(jù)探索舉辦了首次研討會[2]，相關(guān)專家從多個角度對數(shù)據(jù)探索的重要性和必要性進(jìn)行了討論。而交互式數(shù)據(jù)探索（interactive data exploration，IDE）目前還沒有統(tǒng)一的定義。通常來說，交互式數(shù)據(jù)探索是指用戶在不十分明確自己查詢輸入的前提下，系統(tǒng)通過列舉樣例、協(xié)同過濾、機(jī)器學(xué)習(xí)等技術(shù)和方式與用戶進(jìn)行交互和反饋，從而逐漸接近用戶的真實查詢意圖，最終提供給用戶與其查詢意圖最匹配的查詢結(jié)果或返回相應(yīng)的查詢語句。IDE的應(yīng)用已經(jīng)涉及到科學(xué)計算、財務(wù)分析、循證醫(yī)學(xué)和基因組學(xué)等領(lǐng)域[2]，并且有效的IDE會以前所未有的速度增加數(shù)據(jù)的采集。IDE在根本上是應(yīng)對一個不精確的最終目標(biāo)的多步驟、非線性的過程。例如，在數(shù)據(jù)驅(qū)動的科學(xué)發(fā)現(xiàn)過程中，常常需要非專業(yè)用戶通過IDE迭代地與系統(tǒng)進(jìn)行交互，從非確定形式的數(shù)據(jù)集中確定用戶感興趣的模式。如果要充分利用復(fù)雜大型數(shù)據(jù)集，用戶將需要一個“專家助理”，能夠有效地引導(dǎo)用戶瀏覽數(shù)據(jù)空間。

交互式數(shù)據(jù)探索[3]是一組多樣的發(fā)現(xiàn)式應(yīng)用程序的關(guān)鍵因素。在這些應(yīng)用程序中，數(shù)據(jù)發(fā)現(xiàn)是一個非常特別的交互過程，其交互式性能應(yīng)該支持在線查詢處理，這是不斷更新分析和探索的關(guān)鍵。幫助用戶在數(shù)據(jù)空間進(jìn)行簡單的導(dǎo)航，允許用戶很容易地表達(dá)出形式化的探索查詢序列，即：自動生成“查詢會話”，查詢會話很少來自用戶的輸入或提供建議，甚至用戶無需精確表達(dá)自己的興趣數(shù)據(jù)，便可以利用用戶的興趣、目標(biāo)，并與數(shù)據(jù)庫交互后，生成模型，顯示用戶感興趣的部分?jǐn)?shù)據(jù)。IDE可以很容易地成為高度勞動資源密集型的過程。因此，需要一種支持這些用戶參與的應(yīng)用程序，來幫助他們在數(shù)據(jù)中導(dǎo)航，找到用戶感興趣的對象。

2 交互式數(shù)據(jù)探索概述

交互式數(shù)據(jù)探索系統(tǒng)的模型如圖1所示。首先，給定一個數(shù)據(jù)庫D，在數(shù)據(jù)庫中提取包含m個樣本的初始數(shù)據(jù)集S(x1,x2,…,xm)。假設(shè)用戶已經(jīng)決定探索n個屬性（n個屬性中可以包含相關(guān)屬性和不相關(guān)屬性），每個樣本xi由d個屬性描述，每個樣本xi= (xi1,xi2,…,xid)是d維樣本空間X中的一個向量，xi∈X，其中xij表示xi在第j個屬性上的取值，d為樣本xi的維數(shù)。加入用戶相關(guān)性反饋，系統(tǒng)進(jìn)行迭代式處理過程，開始數(shù)據(jù)探索。用戶的相關(guān)性反饋要求按屬性將數(shù)據(jù)分類，用戶標(biāo)記的第i個樣本記為(xi,yi),其中yi∈Y是樣本xi的標(biāo)記，Y是所有標(biāo)記的集合或輸出空間。標(biāo)記樣本后，訓(xùn)練分類模型，建立用戶感興趣的模型M。建立起用戶模型后，對給出的查詢進(jìn)行查詢推薦和查詢結(jié)果優(yōu)化。當(dāng)達(dá)到一個令人滿意相關(guān)對象集合或者當(dāng)他不希望標(biāo)記更多樣本時，用戶顯式地終止該過程時，指導(dǎo)處理過程完成。最后，在一個SQL查詢表達(dá)式中將用戶模型轉(zhuǎn)變成最終的分類模型（數(shù)據(jù)提取查詢）。

Fig.1 Model of interactive data exploration system圖1 交互式數(shù)據(jù)探索系統(tǒng)模型

IDE的典型應(yīng)用有循證醫(yī)學(xué)EBM（evidencebased medicine）[2]，一門遵循證據(jù)的醫(yī)學(xué)。它的核心思想是在醫(yī)療決策中將臨床證據(jù)、個人經(jīng)驗與患者的實際狀況和意愿三者相結(jié)合。EBM運(yùn)用最新、最有力的科技信息，指導(dǎo)臨床醫(yī)生采用最適宜的診斷方法、最精確的愈后估計和最安全有效的治療方法來診治病人。其核心是要求醫(yī)生在疾病診治過程中以當(dāng)前全世界大樣本隨機(jī)對照實驗（randomized control test，RCT）的結(jié)果為證據(jù)。這樣的應(yīng)用程序通常涉及系統(tǒng)的評價，全面評估收集的證據(jù)后，給定一個定義明確的問題，如對死亡率的影響，給藥和不給藥情況下3小時內(nèi)癥狀。而關(guān)于內(nèi)容方面，專家可以判斷給定的臨床實驗是否感興趣（如檢查參數(shù)值、疾病的種類、病人年齡等），專家可以對確切的屬性沒有先驗知識，而是制定一個查詢來收集所有相關(guān)的臨床實驗。

又如在科學(xué)方面的應(yīng)用。在分析天體物理學(xué)的觀察時，也遇到過類似的情況：科學(xué)家可能無法精確地表達(dá)自己的感興趣數(shù)據(jù)；相反，他們可能想要瀏覽的一個子空間數(shù)據(jù)集（對應(yīng)天空的一個區(qū)域），找到感興趣的對象，也可能希望看到幾件樣本，提供是或者不是的反饋意見，期望系統(tǒng)找到更多類似對象。

3 交互式數(shù)據(jù)探索的特點(diǎn)

傳統(tǒng)的Web數(shù)據(jù)探索查詢或以Google、Baidu為代表的搜索引擎，雖然具有基于關(guān)鍵字、通用性等特點(diǎn)，但其局限性和缺點(diǎn)在信息爆炸的時代顯得尤其明顯。例如，基于內(nèi)容過濾的方法，可以根據(jù)用戶以前的興趣來推測用戶以后的興趣，但不能為用戶發(fā)現(xiàn)新的感興趣的資源，只能發(fā)現(xiàn)與用戶已有興趣相似的資源。又如基于協(xié)作過濾方法的優(yōu)點(diǎn)是能為用戶發(fā)現(xiàn)新的感興趣的信息，但難以解決稀疏性和可擴(kuò)展性的問題。

交互式數(shù)據(jù)探索的特點(diǎn)可概括為三方面。

3.1 查詢動態(tài)性

在交互式數(shù)據(jù)探索中，查詢動態(tài)性可體現(xiàn)在兩方面：一是輸入數(shù)據(jù)動態(tài)性[3]。在數(shù)據(jù)探索開始時，要求用戶加入到與系統(tǒng)的“對話”，通過用戶反饋，作為輸入數(shù)據(jù)，捕獲用戶的偏好，多次迭代后形成初步的用戶模型。二是數(shù)據(jù)信息的動態(tài)性。在探索中加入用戶反饋后，數(shù)據(jù)信息是實時更新的，形成了信息循環(huán)，通過查詢結(jié)果優(yōu)化給出的查詢結(jié)果不再單純是基于關(guān)鍵字的內(nèi)容，也許會偏離初始的輸入，但一定是用戶感興趣的內(nèi)容。

3.2 交互反饋性

交互式數(shù)據(jù)探索的查詢動態(tài)性和交互反饋性是相輔相成的。交互反饋性體現(xiàn)在系統(tǒng)可以根據(jù)用戶的行為動態(tài)地調(diào)整查詢，準(zhǔn)確預(yù)測數(shù)據(jù)，給出匹配用戶興趣的集合，為用戶提供更精準(zhǔn)的、個性化的查詢結(jié)果。例如，AIDE[4]系統(tǒng)中，在發(fā)現(xiàn)相關(guān)的對象階段，依靠用戶的相關(guān)性反饋將數(shù)據(jù)分類，確定抽樣區(qū)域，以提高標(biāo)記樣本的精度，這樣使得下一步空間探索中查詢結(jié)果優(yōu)化的范圍更精確。

3.3 學(xué)習(xí)主動性

在交互式數(shù)據(jù)探索中，引入學(xué)習(xí)主動性，可以提高數(shù)據(jù)探索的效率和準(zhǔn)確性。將機(jī)器學(xué)習(xí)的方法應(yīng)用于數(shù)據(jù)探索的各個階段[2]。例如，自動化交互式數(shù)據(jù)探索框架[5]通過學(xué)習(xí)用戶感興趣的數(shù)據(jù)區(qū)域，自動“引導(dǎo)”用戶。用戶參與以及與系統(tǒng)的“對話”顯示用戶的興趣，同時在后臺系統(tǒng)自動制定流程，收集數(shù)據(jù)，查詢匹配用戶的興趣。又如，可以應(yīng)用主動學(xué)習(xí)，最大化模型的準(zhǔn)確性同時將最小化樣本的數(shù)量顯示給用戶；分類算法[6]可用于建立用戶興趣模型和信息檢索；基于偏移感知的聚類方法[6]可用于處理傾斜屬性和確定抽樣區(qū)域等。

4 交互式數(shù)據(jù)探索研究技術(shù)現(xiàn)狀

基于交互式數(shù)據(jù)探索的框架設(shè)計，以及交互式數(shù)據(jù)探索的上述特點(diǎn)，交互式數(shù)據(jù)探索對信息的獲取也是通過查詢來實現(xiàn)的。因為目標(biāo)不確定是交互式數(shù)據(jù)探索的重要特點(diǎn)，所以查詢層需要提供更多的功能支持交互層。相關(guān)研究主要從查詢推薦和查詢結(jié)果優(yōu)化方面展開。

4.1 交互式數(shù)據(jù)探索的查詢推薦

在過去的幾十年里，雖然數(shù)據(jù)庫管理系統(tǒng)（database management sysem，DBMS）進(jìn)化提供復(fù)雜的多種數(shù)據(jù)管理能力，但管理查詢工具相對大數(shù)據(jù)來說都較為原始。原因之一是查詢通常是通過應(yīng)用程序輸出。調(diào)試成功一次后，可多次重復(fù)使用。隨著交互方式發(fā)生變化，科學(xué)家在諸如生物學(xué)、物理學(xué)、天文學(xué)、地球科學(xué)等領(lǐng)域需要收集、存儲、檢索、探索和分析大量的數(shù)據(jù)，他們需要可以提出探索性分析數(shù)據(jù)查詢的能力。在這些新的背景下，數(shù)據(jù)管理系統(tǒng)必須提供強(qiáng)大的查詢管理功能，經(jīng)過查詢推薦和對查詢結(jié)果優(yōu)化來改進(jìn)技術(shù)，從而能完成從查詢?yōu)g覽到自動查詢建議的實現(xiàn)。

現(xiàn)有的查詢推薦技術(shù)已有很多改進(jìn)方案，在交互式數(shù)據(jù)探索方面可以借鑒，下面簡要介紹幾種較成熟的推薦技術(shù)。目前推薦系統(tǒng)可分為4類，即基于內(nèi)容的推薦、基于協(xié)同過濾的推薦、基于知識的推薦、組合推薦。

4.1.1 基于內(nèi)容的推薦

基于內(nèi)容的推薦方法是指根據(jù)用戶已選擇的項目，推薦其他類似屬性的項目，是一種基于項目間相似性推薦方法。系統(tǒng)基于用戶所評價對象的特征，學(xué)習(xí)用戶興趣模型，從而判斷用戶資料與候選推薦項目之間的匹配度。其優(yōu)點(diǎn)在于用戶獨(dú)立性，不需要依賴其他用戶的評價信息，只需根據(jù)新項目的特征及活動用戶概貌即可完成推薦。缺點(diǎn)在于內(nèi)容局限性，對圖形、視頻等內(nèi)容特征難以提取的格式會影響推薦結(jié)果；無法區(qū)分內(nèi)容質(zhì)量的高低；推薦內(nèi)容有限。典型的基于內(nèi)容的推薦系統(tǒng)有：Kompan提出的新聞推薦系統(tǒng)[7]，麻省理工大學(xué)的Lieberman開發(fā)的Letizia系統(tǒng)[8]，Mladenic提出的PersonalWebWatcher[9]，加利福尼亞大學(xué)的Billsus推出的Syskill&Webert系統(tǒng)[10]等。

4.1.2 基于協(xié)同過濾的推薦

傳統(tǒng)的協(xié)同過濾推薦算法的原理是利用用戶的歷史喜好信息來計算用戶之間的距離，然后利用目標(biāo)用戶的“最近鄰居”對商品評價的加權(quán)評價值來預(yù)測目標(biāo)用戶對特定商品的喜好程度，系統(tǒng)根據(jù)此喜好程度來對目標(biāo)用戶進(jìn)行推薦。優(yōu)點(diǎn)是對推薦對象沒有特殊的要求，能處理非結(jié)構(gòu)化的復(fù)雜對象。比如在文獻(xiàn)[11]中，提出一個支持關(guān)系數(shù)據(jù)庫交互式探索的查詢推薦框架QueRIE（query recommendations for interactive database exploration），如圖2所示。采用user-item矩陣方法生成建議。用戶之間的相似性可以表示為查詢或片段之間的相似性。系統(tǒng)中使用可視化查詢接口，確保系統(tǒng)為數(shù)據(jù)庫的活躍用戶生成實時推薦，并設(shè)計了一種壓縮矩陣的方法，加快相似性的計算。

Fig.2 Architecture of QueRIE圖2 QueRIE體系結(jié)構(gòu)

隨著電子商務(wù)用戶、商品規(guī)模的劇增，基于協(xié)同過濾的推薦受到了一些因素的制約，比如準(zhǔn)確性、稀疏性、可擴(kuò)展性和冷啟動等問題。在這種情況下，許多研究人員提出了基于協(xié)同過濾的改進(jìn)算法，改進(jìn)算法主要體現(xiàn)在與聚類、貝葉斯、維數(shù)約簡等技術(shù)的結(jié)合。

（1）結(jié)合聚類技術(shù)。鄧愛林等人[12]根據(jù)用戶對項目評分的相似性進(jìn)行聚類，從而只需要在與目標(biāo)項目最相似的若干個聚類中就能尋找到目標(biāo)項目中大部分的最近鄰。Ranshid等人[13]聚類生成每個聚類的代理用戶，基于目標(biāo)用戶的相似代理用戶進(jìn)行推薦。George等人[14]采用co-clustering算法構(gòu)建了一個動態(tài)框架，有效解決了實時性問題，同時并行處理用戶和項目，提高了系統(tǒng)的可擴(kuò)展性。結(jié)合聚類技術(shù)的推薦雖然可以采用離線方式建立模型以確保實時性，但聚類的缺點(diǎn)是無論是用戶或是項目，分在一個類后就不能出現(xiàn)在其他類中（而實際上用戶的興趣是廣泛的），從而導(dǎo)致推薦的質(zhì)量不高。

（2）結(jié)合貝葉斯技術(shù)。孟憲福等人[15]根據(jù)用戶的偏好對項目進(jìn)行分類，其實驗表明隨著評分?jǐn)?shù)據(jù)的增加，數(shù)據(jù)稀疏度在一定程度上增加，但可以提高推薦的精度。趙永梅等人[16]采用動態(tài)貝葉斯網(wǎng)，不斷學(xué)習(xí)更新推薦模型，提高了模型的適應(yīng)性，其推薦結(jié)果更加滿足客戶的需求。貝葉斯技術(shù)可以利用訓(xùn)練集創(chuàng)建相應(yīng)的模型，緩解數(shù)據(jù)稀疏性問題，但是由于用戶和項目的不斷增加，需要定期重建模型，并且訓(xùn)練模型的成本高。

（3）結(jié)合維數(shù)約簡技術(shù)。Paterek[17]使用奇異值分解，將用戶-評分矩陣分解得到與其最接近的低階矩陣，提高了可擴(kuò)展性，并有效緩解了同義性問題。李慧等人[18]利用維數(shù)約簡技術(shù)對評分矩陣進(jìn)行優(yōu)化，采用分類近似質(zhì)量計算用戶間的相似性并形成最近鄰居，從而降低數(shù)據(jù)稀疏性和提高最近鄰尋找準(zhǔn)確性。結(jié)合維數(shù)約簡技術(shù)的優(yōu)點(diǎn)是提高了推薦系統(tǒng)的可擴(kuò)展性，一定程度上緩解了數(shù)據(jù)稀疏問題，但缺點(diǎn)是降維會導(dǎo)致信息損失。

4.1.3 基于知識的推薦

基于知識的推薦（knowledge based recommendation）[19]在某種程度上可以看成是一種推理（inference）技術(shù)[20]。它不是建立在用戶需要和偏好基礎(chǔ)上進(jìn)行推薦，而是針對特定領(lǐng)域制定規(guī)則（rule）來進(jìn)行推理。艾磊等人[21]建立了基于有限狀態(tài)機(jī)（finite state machine，F(xiàn)SM）的用戶交互模型。根據(jù)所推薦物品的特征建立用戶交互行為的有限狀態(tài)機(jī)模型，通過求解有限狀態(tài)機(jī)模型的有效路徑，生成用戶的個性化需求和偏好。譚紅葉等人[22]提出了一種基于知識脈絡(luò)的科技論文推薦方法，利用文本中關(guān)鍵詞之間的同義關(guān)系、上下文關(guān)系構(gòu)建成知識脈絡(luò)，結(jié)合基于內(nèi)容過濾的方法為作者進(jìn)行科技論文推薦?；谥R的推薦方法的核心內(nèi)容來自于兩個方面，即領(lǐng)域知識的聚集和用戶需求的獲取。對于不同的應(yīng)用領(lǐng)域，領(lǐng)域知識的聚集規(guī)則和實例分類方法存在較大差異，因此這類推薦不存在普遍的適用性，只適用于特定的應(yīng)用領(lǐng)域。

4.1.4 組合推薦

組合推薦（hybrid recommendation）相對于獨(dú)立的推薦系統(tǒng)具有更高的推薦準(zhǔn)確率。組合推薦[23]通過組合后應(yīng)能避免或彌補(bǔ)各自推薦技術(shù)的弱點(diǎn)。推薦技術(shù)組合方式的不同會帶來不同的推薦結(jié)果，Robin Burke提出了7種組合策略：加權(quán)（weighted）、變換（switching）、混合（mixed）、層疊（cascade）、特征組合（feature combination）、特征擴(kuò)充（feature augmentation）、元級別（meta level）。例如，馬建威等人[24]提出了一種基于混合推薦和隱馬爾科夫模型（hidden Markov model，HMM）的服務(wù)推薦方法，在云環(huán)境下，根據(jù)對基于內(nèi)容的過濾和協(xié)同過濾方法進(jìn)行改進(jìn)，并基于隱馬爾科夫模型提出一種冗余服務(wù)消解策略，在推薦的準(zhǔn)確性和時效性等方面都有較大提升。李程等人[25]提出一種混合型并行推薦算法，利用基于用戶的方法劃定出定量的鄰居范圍，保證了推薦的個性化，同時利用基于項目的協(xié)同過濾算法進(jìn)行推薦，最終根據(jù)綜合因素調(diào)整評分預(yù)測方法得出符合實際的推薦結(jié)果，有效地提高了推薦系統(tǒng)的有效性。

4.1.5 各類推薦方法對比

每一類推薦方法都有其各自的優(yōu)點(diǎn)和缺點(diǎn)，針對不同的數(shù)據(jù)類型，推薦效果也有所不同。如在基于內(nèi)容的推薦方法中，對于特征提取的方法很難應(yīng)用于媒體數(shù)據(jù)等非結(jié)構(gòu)化數(shù)據(jù)。隨后發(fā)展的協(xié)同過濾技術(shù)，在一定程度上解決了推薦結(jié)果不豐富等問題，但這種技術(shù)大部分應(yīng)用于單一應(yīng)用系統(tǒng)數(shù)據(jù)源，并且它是基于大量歷史數(shù)據(jù)集進(jìn)行的推薦，因而存在稀疏性、準(zhǔn)確性等問題?；谥R的推薦雖然不存在冷啟動和稀疏性問題，但對知識的建模存在困難。組合推薦策略由于各種組合方式差異較大，不在此討論。幾種推薦方法的優(yōu)缺點(diǎn)對比如表1所示。

4.2 查詢結(jié)果優(yōu)化

查詢推薦在傳統(tǒng)的搜索引擎中得到了充分的運(yùn)用，上文也對較成熟的推薦技術(shù)做了總結(jié)。若當(dāng)前給出的查詢推薦結(jié)果不能滿足用戶的意圖，用戶會進(jìn)行下一輪查詢，但用戶往往對數(shù)據(jù)缺乏了解，因而需要對查詢結(jié)果進(jìn)行優(yōu)化、重構(gòu)和抽取等工作。交互式數(shù)據(jù)查詢的查詢結(jié)果優(yōu)化是整個交互式數(shù)據(jù)探索的關(guān)鍵，直接影響數(shù)據(jù)探索的效果。

在查詢結(jié)果優(yōu)化方面，主要關(guān)注如何處理空結(jié)果查詢處理和多結(jié)果查詢處理兩個方面。

空結(jié)果查詢：當(dāng)查詢條件太嚴(yán)格時，探索的答案可能為空。在這種情況下，用戶希望系統(tǒng)給出的選擇是近似匹配元組的排名列表，而無需指定排序函數(shù)便可捕獲較為接近的查詢。

多結(jié)果查詢：當(dāng)查詢條件寬松時，探索的答案會對應(yīng)很多元組。在這種情況下，用戶希望系統(tǒng)可以自動選擇排序，并且返回的元組能有最好的匹配結(jié)果。

處理多結(jié)果查詢問題的典型解決方案是利用得分函數(shù)和只返回Top-k排名結(jié)果[26-27]。這種方法的主要問題是對得分函數(shù)的規(guī)定，可能不是現(xiàn)成的。此外，Top-k查詢處理通常是執(zhí)行單個表，優(yōu)化Top-k查詢連接是一個具有挑戰(zhàn)性的問題[28]。在解決多結(jié)果查詢時，文獻(xiàn)[29]使用了一個交互式查詢優(yōu)化框架，其查詢優(yōu)化關(guān)鍵是在查詢結(jié)果上提煉SQL查詢來滿足基數(shù)限制。其中包含通過用戶反饋捕獲用戶的偏好，在數(shù)值范圍內(nèi)的等式謂詞和分類屬性上處理查詢，并且通過添加支持分類的謂詞引入用戶的偏好。

Table 1 Comparison of typical recommendation algorithms表1 典型推薦算法的對比

有很多研究通過檢測或者放寬查詢條件解決空結(jié)果查詢問題。Agrawal等人介紹了一種利用排名算法的方法[30]。Luo提出了一種利用從以往查詢收集的歷史信息檢測空結(jié)果查詢的方法[31]，但使用物化視圖匹配的方法不能通用地推廣到其他問題上。同樣，Koudas等人的方法是基于窗口語義計算一組最接近原始查詢的結(jié)果[32]，放寬空查詢中的查詢條件。但該方法需要昂貴的框架來計算結(jié)果的大小，并且不能提供有保證的松弛條件策略。Fontoura等人的方法是采用基于查詢分解的多個層次分類法的文本文檔檢索模型[33]。在多個分類的情況下，可以選擇多個問題同時放寬查詢條件的策略，以避免條件松弛過度產(chǎn)生額外的匹配。隨后，人們更關(guān)注有針對性的測試性查詢，在多個中間子表達(dá)式中滿足基數(shù)約束的條件下，利用抽樣和空間剪技術(shù)快速生成測試查詢所需的屬性[34-35]。

在對查詢結(jié)果的重構(gòu)和抽取方面，為了讓用戶更加直觀地獲取所需要的信息，系統(tǒng)需要將返回的結(jié)果進(jìn)行重構(gòu)和抽取，以更加結(jié)構(gòu)化的方式展示給用戶。Tran等人[36]發(fā)現(xiàn)有些用戶很難將他們的信息需求抽象成查詢，但當(dāng)他們獲取到一些有關(guān)信息之后，可以順利重構(gòu)查詢。MobEx[37]是一個基于移動設(shè)備的數(shù)據(jù)探索系統(tǒng)，該系統(tǒng)通過Web端結(jié)果獲取頁面信息后，采用信息抽取的方式將文本信息以圖的形式展現(xiàn)給用戶。類似的系統(tǒng)還有微軟的人立方。Hippalus系統(tǒng)[38]通過分析返回結(jié)果，將內(nèi)容以多級層次的形式展現(xiàn)給用戶，用戶可以通過篩選層次以及分類來快速定位到他們所需要的信息。

5 交互式數(shù)據(jù)探索原型系統(tǒng)對比

近年來，已經(jīng)存在很多原型系統(tǒng)針對交互式數(shù)據(jù)探索進(jìn)行處理，包括YmalDB系統(tǒng)[39]、DICE系統(tǒng)[40]、SciBORQ系統(tǒng)[41]、Blink系統(tǒng)[42]、Charles系統(tǒng)[43]、AIDE系統(tǒng)[5]、SnapToQuery[44]系統(tǒng)。這些系統(tǒng)從不同的方面提出了不同的探索技術(shù)。

5.1 YmalDB系統(tǒng)

YmalDB系統(tǒng)[39]的目標(biāo)是協(xié)助用戶在數(shù)據(jù)庫中探索，增強(qiáng)數(shù)據(jù)庫系統(tǒng)的推薦功能。對于每個用戶查詢的結(jié)果，YmalDB將計算并提供用戶興趣以外的結(jié)果稱為Ymal[39]（即You may also like）結(jié)果（即與原來的結(jié)果高度相關(guān)的查詢）。計算這些結(jié)果時，使用的是用戶認(rèn)為與其興趣最匹配的屬性值集合（Fa-Sets）。Ymal采用基于存儲?-CRF的頻率估計方法，探索數(shù)據(jù)庫搜索結(jié)果建議[39,45]。雖然Ymal給出的結(jié)果可能不屬于用戶原始查詢的結(jié)果，但有可能是他們感興趣的，這就允許用戶獲得他們可能還未意識到的但確實感興趣的信息。YmalDB的系統(tǒng)架構(gòu)如圖3所示。

5.2 DICE系統(tǒng)

DICE[40]（distributed and interactive cube exploration）是一個分布式系統(tǒng)，使用一種面向會話的數(shù)據(jù)立方體模型進(jìn)行探索，可以為用戶提供交互式的特定精度標(biāo)準(zhǔn)的體驗。DICE的框架結(jié)合了3個概念：數(shù)據(jù)立方體的多面探索、查詢推測和在數(shù)據(jù)子集查詢。使用查詢推測技術(shù)和在線數(shù)據(jù)抽樣技術(shù)，確?？焖?、交互式多維數(shù)據(jù)集探索能夠物化整個數(shù)據(jù)立方體。但在可接受的延遲范圍內(nèi)應(yīng)該限制這樣的設(shè)置，因為一個完全物化的多維數(shù)據(jù)集是原始數(shù)據(jù)集的好幾倍，通常大于可用內(nèi)存。因此，一個常用的方法是離線計算樣本數(shù)據(jù)[42,46-47]，但這種方法不能適應(yīng)底層數(shù)據(jù)的變化。DICE提供的技術(shù)可以在需要的情況下離線采樣。

Fig.3 Architecture of YmalDB圖3 YmalDB體系結(jié)構(gòu)

Fig.4 DICE approach圖4 DICE方法

DICE方法如圖4所示。允許在低延遲前端上具有可調(diào)采樣率，將UI的操作翻譯成在數(shù)據(jù)立方體上的遍歷查詢。查詢執(zhí)行的主體部分在分布式節(jié)點(diǎn)上。在DICE方法中，主節(jié)點(diǎn)管理包括會話狀態(tài)、推測查詢和結(jié)果聚合三部分。對于每個查詢，查詢分發(fā)到每個從節(jié)點(diǎn)。每個從節(jié)點(diǎn)的結(jié)果隨后聚合，計算誤差范圍，并返回給用戶。

5.3 SciBORQ系統(tǒng)

查詢巨大的數(shù)據(jù)庫需要相當(dāng)大的計算集群，在理想情況下，最初的查詢應(yīng)該使用盡可能少的資源進(jìn)行交互。SciBORQ[41]的思路是：在任何給定的時間內(nèi)，只將一部分主要屬性的數(shù)據(jù)作為一個特定的查詢對象。這部分?jǐn)?shù)據(jù)通過特別的查詢結(jié)果優(yōu)化的迭代過程成為查詢對象。通過數(shù)據(jù)操縱來滿足科學(xué)發(fā)現(xiàn)的要求，保證查詢的執(zhí)行時間。此外，誤差的嚴(yán)格上限需要滿足科學(xué)使用的要求，這樣查詢結(jié)果能夠可靠地用來測試假設(shè)。

傳統(tǒng)的近似查詢應(yīng)答和在線聚合方法不能使系統(tǒng)滿足完全控制資源消耗和精確查詢結(jié)果的要求。SciBORQ是一種數(shù)據(jù)探索型科學(xué)數(shù)據(jù)倉庫體系結(jié)構(gòu)，它可以精確控制執(zhí)行時間，提高查詢應(yīng)答的質(zhì)量。在SciBORQ中，將一種獲得用戶感興趣的多個數(shù)據(jù)樣本的抽樣方法稱為印象（impression）。印象不同于以往的抽樣方法，它偏向科學(xué)數(shù)據(jù)探索的興趣點(diǎn)，這種偏差抽樣很有價值，可以在更多感興趣的區(qū)域進(jìn)行數(shù)據(jù)采樣。SciBORQ的獨(dú)特之處在于其多層的架構(gòu)方法，重新優(yōu)化可以保證所需的誤差范圍，即使它們偏離相關(guān)性。SciBORQ最終目標(biāo)是把科學(xué)數(shù)據(jù)探索和發(fā)現(xiàn)過程構(gòu)成一個完整的系統(tǒng)，在嚴(yán)格的誤差范圍和預(yù)定義的時間框架內(nèi)產(chǎn)生高質(zhì)量的結(jié)果。

5.4 BlinkDB系統(tǒng)

BlinkDB[42]是一個用于在海量數(shù)據(jù)上運(yùn)行交互式SQL查詢的大規(guī)模并行查詢引擎，其數(shù)據(jù)探索的側(cè)重點(diǎn)在于允許用戶通過權(quán)衡數(shù)據(jù)精度來提升查詢響應(yīng)時間，其數(shù)據(jù)的精度被控制在允許的誤差范圍內(nèi)。為了達(dá)到這個目標(biāo)，BlinkDB使用兩個核心思想：一個是自適應(yīng)優(yōu)化框架，從原始數(shù)據(jù)隨著時間的推移建立并維護(hù)一組多維樣本；另一個是動態(tài)樣本選擇策略，選擇一個適當(dāng)大小的且基于查詢的實例，以提高準(zhǔn)確性或達(dá)到響應(yīng)時間需求。

BlinkDB利用大規(guī)模并行復(fù)雜處理框架可以優(yōu)化交互式應(yīng)答大量的數(shù)據(jù)。BlinkDB支持SPJA（selection，projection，join，aggregate）方式SQL查詢。聚合查詢可以標(biāo)記誤差或最大執(zhí)行時間約束。Blink-DB的總體體系結(jié)構(gòu)如圖5所示，BlinkDB添加了兩個主要組件：（1）組件創(chuàng)建和維護(hù)樣本；（2）用組件預(yù)測查詢響應(yīng)時間和準(zhǔn)確性，選擇一個最好的樣本滿足給定的約束條件。這樣可以使其依賴于運(yùn)行時樣本選擇與統(tǒng)計誤差，確保提供實時的應(yīng)答。

Fig.5 Architecture of BlinkDB圖5 BlinkDB體系結(jié)構(gòu)

5.5 Charles系統(tǒng)

Charles系統(tǒng)[43]解決的核心問題是如何將查詢空間與給定的數(shù)據(jù)庫相關(guān)聯(lián)。查詢空間被認(rèn)為是由連接謂詞組成的，Charles系統(tǒng)引入分段描述語言（segmentation description language，SDL）來描述這些謂詞，使得用戶可以深刻理解描述集，并為用戶提供了進(jìn)一步探索的方向。Charles系統(tǒng)從幾個方面來查詢一組用戶提供的元組。每個餅形圖代表一組查詢，數(shù)據(jù)庫切成不相交的部分稱之為分割。Charles的目標(biāo)是分離和描述大量的數(shù)據(jù)交互，并提出算法HB-cuts（hierarchical-binary分割），將數(shù)據(jù)集分為可能同樣寬的塊。Charles在MonetDB系統(tǒng)的環(huán)境下，簡化了代碼的可移植性。

5.6 AIDE系統(tǒng)

AIDE[5]（automatic user navigation system for inter-active data exploration）是一種支持IDE的自動化用戶導(dǎo)航系統(tǒng)，可以自動學(xué)習(xí)用戶的興趣，對這些興趣相關(guān)的數(shù)據(jù)進(jìn)行探索。該系統(tǒng)數(shù)據(jù)探索的側(cè)重點(diǎn)在于依靠用戶的反饋提供查詢建議，專注于收集樣本，理解用戶的興趣。AIDE依賴一個主動式學(xué)習(xí)模型，反復(fù)迭代地請求用戶的反饋[4]，設(shè)計一定策略，有選擇地收集數(shù)據(jù)樣本。AIDE將機(jī)器學(xué)習(xí)、數(shù)據(jù)探索和樣本采集技術(shù)相結(jié)合，提供了一個高精度預(yù)測用戶興趣與交互性能的線性模式[48]。簡而言之，用戶參與“對話”，系統(tǒng)通過描述一組數(shù)據(jù)樣本作為他相關(guān)或不相關(guān)的興趣。將用戶反饋數(shù)據(jù)逐步納入系統(tǒng)，用于逐步提高其有效性，最終生成一個用戶模型，準(zhǔn)確預(yù)測數(shù)據(jù)匹配用戶興趣結(jié)果的集合。

AIDE工作流程框架是如圖6所示。首先，用戶提出了樣本數(shù)據(jù)庫對象（初始的樣本采集），要求按特征使用CART決策樹方法[6]將探索任務(wù)分為相關(guān)與不相關(guān)的樣本。假設(shè)有一個二元無噪音的關(guān)聯(lián)系統(tǒng)，用戶可以知道一個數(shù)據(jù)對象與他是否相關(guān)，這個分類在下一個迭代中不能修改。當(dāng)用戶提供反饋時，系統(tǒng)迭代地指導(dǎo)處理過程，標(biāo)記樣本，用分類算法訓(xùn)練分類模型，描述用戶興趣。例如：系統(tǒng)預(yù)測的相關(guān)用戶的臨床實驗是基于目前收集到的反饋（數(shù)據(jù)分類）。對象屬性的分類模型可以使用任何子集描述用戶的興趣。當(dāng)前用戶模型來確定抽樣區(qū)域（空間探索），從數(shù)據(jù)庫中獲取下一個樣本集（樣本提取）。新標(biāo)簽對象合并已標(biāo)記樣本集，構(gòu)建一個新的分類模型。當(dāng)達(dá)到一定條件，如達(dá)到一個令人滿意相關(guān)對象的集合或者當(dāng)他不希望標(biāo)記更多樣本時，用戶顯式地終止指導(dǎo)過程。最后，AIDE在一個查詢表達(dá)式中“翻譯”成分類模型（數(shù)據(jù)提取查詢）。這個查詢將檢索對象特征作為相關(guān)的用戶模型（查詢公式）。

Fig.6 Framework ofAIDE圖6 AIDE的框架結(jié)構(gòu)

5.7 SnapToQuery系統(tǒng)

SnapToQuery[44]是一種基于Snapping技術(shù)[49-50]的反饋機(jī)制，通過“快照”用戶可能感興趣的查詢，指導(dǎo)用戶在查詢規(guī)范過程中提供互動反饋。這些預(yù)期的查詢可以從現(xiàn)有的查詢?nèi)罩净驈臄?shù)據(jù)本身提取。為了在大型數(shù)據(jù)集提供交互式響應(yīng)時間，SnapToQuery在快照查詢時提出兩個數(shù)據(jù)簡化技術(shù)。一種是Naive方法，主要思想是聚合，用分割空間的方式代替分割大型數(shù)據(jù)集的方式。另一種是Data Contour方法，處理低維數(shù)據(jù)集查詢時，采用邊緣檢測方法和基于網(wǎng)格的聚類方法；處理高維數(shù)據(jù)集查詢時，采用KMeans+直方圖的方法。

SnapToQuery系統(tǒng)的整體架構(gòu)如圖7所示。系統(tǒng)的后端應(yīng)用Naive方法和Data Contour方法對數(shù)據(jù)集進(jìn)行了簡化，在前端增加了可視化的基于鏈接的可調(diào)節(jié)直方圖[51]。用戶可以通過操作滑塊條，在3個設(shè)備（鼠標(biāo)、平板電腦、跳躍運(yùn)動）上發(fā)布范圍查詢，隨后SnapToQuery系統(tǒng)在查詢規(guī)范內(nèi)進(jìn)行快照查詢。

Fig.7 Overall architecture of SnapToQuery圖7 SnapToQuery的整體構(gòu)架

5.8 系統(tǒng)對比

針對上述系統(tǒng)，從系統(tǒng)的側(cè)重點(diǎn)、缺點(diǎn)和使用的主要技術(shù)等層面對各個交互式數(shù)據(jù)探索的原型系統(tǒng)進(jìn)行了對比。比如YmalDB系統(tǒng)[39]是對關(guān)系數(shù)據(jù)庫查詢結(jié)果進(jìn)行分析，推薦出用戶可能感興趣屬性值對的組合，引導(dǎo)用戶進(jìn)一步探索數(shù)據(jù)庫中的數(shù)據(jù)。其側(cè)重點(diǎn)是信息推薦。SciBORQ系統(tǒng)[41]依靠嚴(yán)格的層次數(shù)據(jù)庫樣本，支持在嚴(yán)格的查詢執(zhí)行時間內(nèi)進(jìn)行科學(xué)探索查詢，進(jìn)而快速返回查詢結(jié)果以提高交互性能。而AIDE系統(tǒng)[5]依靠用戶的反饋提供查詢建議，專注于收集樣本，提高系統(tǒng)理解用戶的興趣的能力。其側(cè)重點(diǎn)通過用戶反饋對數(shù)據(jù)分類，從而提高交互性能。由于各個系統(tǒng)的側(cè)重點(diǎn)不同，實驗數(shù)據(jù)集不同，這里對系統(tǒng)的準(zhǔn)確性和效率不做討論。各個系統(tǒng)的對比如表2所示。

6 研究展望

數(shù)據(jù)探索已經(jīng)成為研究熱點(diǎn)，然而將數(shù)據(jù)探索與用戶反饋機(jī)制和機(jī)器學(xué)習(xí)結(jié)合起來依然存在諸多不足，面臨著諸多挑戰(zhàn)，有很多需要進(jìn)一步研究的內(nèi)容。

（1）用戶與系統(tǒng)的交互方式

面對結(jié)構(gòu)復(fù)雜、規(guī)模龐大的數(shù)據(jù)庫，用戶通常難以明確自己的信息需求并通過簡單的查詢檢索到理想的數(shù)據(jù)。在沒有歷史數(shù)據(jù)或歷史數(shù)據(jù)較少的條件下，交互式數(shù)據(jù)探索系統(tǒng)的冷啟動問題會成為解決最終結(jié)果準(zhǔn)確性的關(guān)鍵。目前，交互式數(shù)據(jù)探索中大部分應(yīng)用的反饋機(jī)制是建立在二元無噪音的關(guān)聯(lián)系統(tǒng)[5]，但為了讓系統(tǒng)能收集到更精確的反饋信息，未來研究可考慮提供用戶在數(shù)據(jù)探索反饋信息時輸入帶有不確定度的信息，如允許用戶選擇“有點(diǎn)像”、“更像了”、“完全不是”等這樣的選項來對結(jié)果作判定，并使用更多的主動學(xué)習(xí)模型，如貝葉斯模型、深度學(xué)習(xí)策略等，來解決系統(tǒng)冷啟動問題。

交互界面是用戶與系統(tǒng)直接對話的平臺，在交互式數(shù)據(jù)探索系統(tǒng)中，需要良好的交互層以協(xié)助用戶更準(zhǔn)確地表達(dá)和獲取信息需求。在交互層設(shè)計的環(huán)節(jié)上，應(yīng)根據(jù)應(yīng)用層的不同需求進(jìn)行個性化的設(shè)計，其設(shè)計的好壞直接影響到系統(tǒng)的易用性。未來研究可考慮結(jié)合AR（augmented reality）技術(shù)實現(xiàn)用戶與系統(tǒng)的交互，建立基于時間樹AR交互數(shù)據(jù)的用戶注意力模型，捕捉用戶信息，預(yù)測用戶的下一步搜索。另外，對探索結(jié)果進(jìn)行可視化也是需要研究的內(nèi)容之一。目前可視化技術(shù)與交互式數(shù)據(jù)探索的結(jié)合不深入，應(yīng)針對不同數(shù)據(jù)的特點(diǎn)，對探索的結(jié)果可視化，展示查詢結(jié)果與數(shù)據(jù)之間的關(guān)聯(lián)。

（2）數(shù)據(jù)處理

隨著數(shù)據(jù)規(guī)模和復(fù)雜性的增加，用戶的查詢意圖很容易被淹沒在數(shù)據(jù)中。由于數(shù)據(jù)集的大小從幾十到幾百萬億字節(jié)不等，而且每個科學(xué)領(lǐng)域中的非結(jié)構(gòu)化數(shù)據(jù)有一個約定的分類，用戶很難對數(shù)據(jù)集進(jìn)行理解和探索。在大規(guī)模數(shù)據(jù)集中，快速將各種數(shù)據(jù)進(jìn)行抽取實體、自動地整理與挖掘以及支持小規(guī)模數(shù)據(jù)量的分析，是數(shù)據(jù)處理面對的挑戰(zhàn)。未來研究可考慮利用數(shù)據(jù)預(yù)?。╠ata prefetching）的方法和查詢近似（query approximation）技術(shù)相結(jié)合，在用戶可接受的誤差范圍內(nèi)，犧牲部分精度，快速返回近似結(jié)果。

Table 2 Comparison of prototype systems of interactive data exploration表2 交互式數(shù)據(jù)探索的原型系統(tǒng)對比

（3）查詢構(gòu)建

在交互式數(shù)據(jù)探索中，提高查詢的準(zhǔn)確性，勢必要增加樣本標(biāo)簽的數(shù)量，用戶提供的樣本標(biāo)簽越多，得到的查詢結(jié)果越準(zhǔn)確，但這會降低數(shù)據(jù)探索的效率。此挑戰(zhàn)在于要根據(jù)不同的應(yīng)用環(huán)境和用戶需求，權(quán)衡收集所有相關(guān)的信息量與減少返回數(shù)據(jù)量之間的關(guān)系。未來研究可考慮采用查詢主題擴(kuò)展的方法，在給出少量樣本數(shù)據(jù)的同時，滿足用戶關(guān)注的更多主題。比如利用多屬性效用函數(shù)在給定時間內(nèi)，將一部分主要屬性的數(shù)據(jù)作為一個特定的查詢對象，構(gòu)建查詢以保證查詢的執(zhí)行時間。其次，交互式數(shù)據(jù)探索對信息的需求是多樣變化的，需要通過多輪交互模式達(dá)到學(xué)習(xí)和調(diào)研的目的。如果當(dāng)前的查詢不滿足用戶的需求，用戶會進(jìn)行再一次的查詢操作，但由于用戶對探索的目標(biāo)是模糊不確定的，缺乏對探索數(shù)據(jù)的了解，需要交互式數(shù)據(jù)探索系統(tǒng)支持用戶快速重構(gòu)查詢。未來研究可考慮結(jié)合最近的查詢結(jié)果，并且聯(lián)系之前的查詢條件，在用戶當(dāng)前查詢的基礎(chǔ)上加上限制條件，幫助用戶逐步地構(gòu)建準(zhǔn)確的查詢。

7 總結(jié)與展望

本文基于交互式數(shù)據(jù)探索的應(yīng)用背景，對其進(jìn)行了簡要介紹，總結(jié)了探索模型，分析出交互式數(shù)據(jù)探索具有查詢動態(tài)性、交互反饋性、學(xué)習(xí)主動性三大特點(diǎn)；總結(jié)了IDE中的查詢推薦技術(shù)，重點(diǎn)介紹了基于協(xié)同過濾技術(shù)提出的交互式推薦框架；總結(jié)了出現(xiàn)空結(jié)果查詢和多結(jié)果查詢情況下的查詢優(yōu)化技術(shù)；對IDE原型系統(tǒng)進(jìn)行了分析和比較。交互式數(shù)據(jù)探索是個新興的重要課題，目前正處于高速發(fā)展階段，雖然有很多相關(guān)領(lǐng)域的研究成果可以借鑒，但仍有大量問題需要解決。隨著知識庫數(shù)量和數(shù)據(jù)規(guī)模的不斷增加，將會有更多的系統(tǒng)涌現(xiàn)出來，為用戶與系統(tǒng)構(gòu)建一個主動學(xué)習(xí)的交互式平臺，并推動大數(shù)據(jù)應(yīng)用不斷發(fā)展。

[1]Marchionini G.Exploratory search:from finding to understanding[J].Communications of theACM,2006,49(4):41-46.

[2]Koutrika G,Lakshmanan L V S,Riedewald M,et al.Report on the first international workshop on exploratory search in databases and the Web(ExploreDB 2014)[J].ACM SIGMOD Record,2014,43(2):49-52.

[3]Dimitriadou K,Papaemmanouil O,Diao Yanlei.Explore-byexample:an automatic query steering framework for interactive data exploration[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Snowbird,USA,Jun 22-27,2014.New York:ACM,2014: 517-528.

[4]Dimitriadou K,Papaemmanouil O,Diao Yanlei.Interactive data exploration based on user relevance feedback[C]//Proceedings of the 2014 IEEE 30th International Conference on Data Engineering Workshops,Chicago,USA,Mar 31-Apr 4,2014.Piscataway,USA:IEEE,2014:292-295.

[5]Diao Yanlei,Dimitriadou K,Li Zhan,et al.AIDE:an automatic user navigation system for interactive data exploration[J].Proceedings of the VLDB Endowment,2015,8 (12):1964-1967.

[6]Trendowicz A,Jeffery R.Classification and regression trees [M]//Software Project Effort Estimation.Springer International Publishing,2014:1174-1176.

[7]Kompan M,Bieliková M.Content-based news recommendation[C]//Proceedings of the 2010 International Conference on E-Commerce and Web Technologies,Bilbao,Spain, Sep 1-3,2010.Berlin,Heidelberg:Springer,2010:61-72.

[8]Lieberman H.Letizia:an agent that assists Web browsing [C]//Proceedings of the 14th International Joint Conference on Artificial Intelligence,Montréal Québec,Canada,Aug 20-25,1995.San Francisco,USA:Morgan Kaufmann Pub-lishers Inc,1995:924-929.

[9]Mladenic D.Personal WebWatcher:design and implementation[R].Department of Intelligent Systems,Stefan Institute, 1996.

[10]Pazzani M,Muramatsu J,Billsus D.Syskill&Webert:identifying interesting Web sites[C]//Proceedings of the 13th National Conference on Artificial Intelligence,Portland, USA,Aug 4-5,1996.Palo Alto,USA:AAAI Press,1996: 54-61.

[11]Chatzopoulou G,Eirinaki M,Polyzotis N.Query recommendations for interactive database exploration[C]//LNCS 5566:Proceedings of the 21st International Conference on Scientific and Statistical Database Management,New Orleans,USA,Jun 2-4,2009.Berlin,Heidelberg:Springer, 2009:3-18.

[12]Deng Ailin,Zuo Ziye,Zhu Yangyong.Collaborative filtering recommendation algorithm based on item clustering[J]. Mini-Micro Systems,2004,25(9):1665-1670.

[13]Rashid A M,Lam S K,Karypis G,et al.ClustKNN:a highly scalable hybrid model-&memory-based CF algorithm[C]// Proceedings of the 8th International Workshop on Knowledge Discovery on the Web,Philadelphia,USA,Aug 20-23,2006.New York:ACM,2006.

[14]George T,Merugu S.A scalable collaborative filtering framework based on co-clustering[C]//Proceedings of the 5th IEEE International Conference on Data Mining,Houston,USA,Nov 27-30,2005.Piscataway,USA:IEEE,2005: 625-628.

[15]Meng Xianfu,Chen Li.The collaborative filtering recommendation mechanism based on Bayesian theory[J].Journal of ComputerApplications,2009,29(10):2733-2735.

[16]Zhao Yongmei,Ren Dayong,Zhang Hongmei,et al.An approach to collaborative filtering recommendation based on HMM and DBN[J].Science Technology&Engineering, 2011,11(9):2012-2016.

[17]Paterek A.Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of the 2007 KDD Cup&Workshop,San Jose,USA,Aug 12,2007. New York:ACM,2007:39-42.

[18]Li Hui,Hu Yun,Li Cunhua,et al.Personalization recommendation algorithm based on nearest neighbor relation[J]. Computer Engineering and Applications,2012,48(36):205-209.

[19]Middleton S E,Shadbolt N R,De Roure D C.Ontological user profiling in recommender systems[J].ACM Transactions on Information Systems,2004,22(1):54-88.

[20]Xu Hailing,Wu Xiao,Li Xiaodong,et al.Comparison study of Internet recommendation system[J].Journal of Software, 2009,20(2):350-362.

[21]Ai Lei,Zhao Hui.A user interaction model for knowledgebased recommender system[J].Software Guide,2015,14 (3):15-17.

[22]Tan Hongye,Yao Yilu,Liang Yinghong.Knowledge veinbased recommendation of academic papers[J].Journal of Shandong University:Natural Science,2016,51(5):94-101.

[23]Yoshii K,Goto M,Komatani K,et al.An efficient hybrid music recommender system using an incrementally trainable probabilistic generative model[J].IEEE Transactions on Audio Speech&Language Processing,2008,16(2):435-447.

[24]Ma Jianwei,Chen Honghui,Stephan R-M.Based on the hybrid recommendation and hidden Markov models of service recommendation method[J].Journal of Zhongnan University: Science and Technology,2016,47(1):82-90.

[25]Li Cheng,Cao Han,Shi Jun.Hybrid recommendation algorithm based on MapReduce and its application[J].Journal of Computer Technology and Development,2016,26(4): 74-77.

[26]Fagin R,Lotem A,Naor M.Optimal aggregation algorithms for middleware[J].Journal of Computer&System Sciences,2002,66(4):614-656.

[27]Chaudhuri S,Das G,Hristidis V,et al.Probabilistic ranking of database query results[C]//Proceedings of the 30th International Conference on Very Large Data Bases,Toronto, Canada,Aug 31-Sep 3,2004:888-899.

[28]Ilyas I F,Aref W G,Elmagarmid A K.Supporting top-k, join queries in relational databases[C]//Proceedings of the 29th International Conference on Very Large Data Bases, Berlin,Germany,SEP 9-12,2003:754-765.

[29]Mishra C,Koudas N.Interactive query refinement[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology, Saint Petersburg,Russia,Mar 24-26,2009.New York:ACM, 2009:862-873.

[30]Agrawal S,Chaudhuri S,Das G,et al.Automated rankingof database query results[C]//Proceedings of the 1st Biennial Conference on Innovative Data Systems Research,Asilomar,USA,Jan 5-8,2003:888-899.

[31]Luo Gang.Efficient detection of empty-result queries[C]// Proceedings of the 32nd International Conference on Very Large Data Bases,Seoul,Sep 12-15,2006.New York:ACM, 2006:1015-1025.

[32]Koudas N,Li C,Tung A K H,et al.Relaxing join and selection queries[C]//Proceedings of the 32nd International Conference on Very Large Data Bases,Seoul,Sep 12-15,2006. New York:ACM,2006:199-210.

[33]Fontoura M,Josifovski V,Kumar R,et al.Relaxation in text search using taxonomies[J].Proceedings of the VLDB Endowment,2010,1(1):672-683.

[34]Bruno N,Chaudhuri S,Thomas D.Generating queries with cardinality constraints for DBMS testing[J].IEEE Transactions on Knowledge&Data Engineering,2006,18(12): 1721-1725.

[35]Mishra C,Koudas N,Zuzarte C.Generating targeted queries for database testing[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, Vancouver,Canada,Jun 9-12,2008.New York:ACM,2008: 499-510.

[36]Tran Q T,Chan C Y,Parthasarathy S.Query by output[C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data,Providence,USA,Jun 29-Jul 2,2009.New York:ACM,2009:535-548.

[37]Neumann G,Schmeier S.MobEx:a system for exploratory search on the mobile Web[C]//Communications in Computer and Information Science 358:Proceedings of the 4th International Conference on Agents and Artificial Intelligence, Vilamoura,Portugal,Feb 6-8,2012.Berlin,Heidelberg: Springer,2012:116-130.

[38]Tzitzikas Y,Papadakos P.Hippalus—a preference enriched faceted exploratory system[J].Language,2014:167-172.

[39]Drosou M,Pitoura E.YmalDB:a result-driven recommendation system for databases[C]//Proceedings of the 16th International Conference on Extending Database Technology, Genoa,Italy,Mar 18-22,2013.New York:ACM,2013: 725-728.

[40]Kamat N,Jayachandran P,Tunga K,et al.Distributed and interactive cube exploration[C]//Proceedings of the 30th IEEE International Conference on Data Engineering,Chicago, USA,Mar 31-Apr 4,2014.Washington:IEEE Computer Society,2014:472-483.

[41]Sidirourgos L,Kersten M,Boncz P.SciBORQ:scientific data management with bounds on runtime and quality[C]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research,Asilomar,USA,Jan 9-12,2011:296-301.

[42]Agarwal S,Iyer A P,Panda A,et al.Blink and it's done:interactive queries on very large data[J].Proceedings of the VLDB Endowment,2012,5(12):1902-1905.

[43]Sellam T,Kersten M L.Meet Charles:big data query advisor [C]//Proceedings of the 6th Biennial Conference on Innovative Data Systems Research,Asilomar,USA,Jan 6-9,2013.

[44]Jiang Lilong,Nandi A.SnapToQuery:providing interactive feedback during exploratory query specification[J].Proceedings of the VLDB Endowment,2015,8(11):1250-1261.

[45]Drosou M,Pitoura E.ReDRIVE:result-driven database exploration through recommendations[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28,2011. New York:ACM,2011:1547-1552.

[46]Wang Fan,Agrawal G.Effective stratification for low selectivity queries on deep Web data sources[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28,2011. New York:ACM,2011:1455-1464.

[47]Chaudhuri S,Das G,Narasayya V.Optimized stratified sampling for approximate query processing[J].ACM Transactions on Database Systems,2007,32(2):2198-2216.

[48]Query patroller[EB/OL].[2016-05-10].http://www.ibm.com/ software/data/db2/querypatroller/.

[49]Eick S G,Wills G J.High interaction graphics[J].European Journal of Operational Research,1995,81(3):445-459.

[50]Baudisch P,Cutrell E,Hinckley K,et al.Snap-and-go:helping users align objects without the modality of traditional snapping[C]//Proceedings of the 2005 Conference on Human Factors in Computing Systems,Portland,USA,Apr 2-7,2005. New York:ACM,2005:301-310.

[51]Fernquist J,Shoemaker G,Booth K S.“Oh Snap”—helping users align digital objects on touch interfaces[C]//Proceedings of the 13th IFIP TC International Conference on Human-Computer Interaction,Lisbon,Portugal,Sep 5-9,2011.Berlin,Heidelberg:Springer,2011:338-355.

附中文參考文獻(xiàn)：

[12]鄧愛林,左子葉,朱揚(yáng)勇.基于項目聚類的協(xié)同過濾推薦算法[J].小型微型計算機(jī)系統(tǒng),2004,25(9):1665-1670.

[15]孟憲福,陳莉.基于貝葉斯理論的協(xié)同過濾推薦算法[J].計算機(jī)應(yīng)用,2009,29(10):2733-2735.

[16]趙永梅,任大勇,張紅梅,等.用動態(tài)貝葉斯網(wǎng)絡(luò)構(gòu)建協(xié)同過濾推薦的新方法[J].科學(xué)技術(shù)與工程,2011,11(9): 2012-2016.

[18]李慧,胡云,李存華,等.基于近鄰關(guān)系的個性化推薦算法研究[J].計算機(jī)工程與應(yīng)用,2012,48(36):205-209.

[20]許海玲,吳瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報,2009,20(2):350-362.

[21]艾磊,趙輝.基于知識的推薦系統(tǒng)用戶交互模型研究[J].軟件導(dǎo)刊,2015,14(3):15-17.

[22]譚紅葉,要一璐,梁穎紅.基于知識脈絡(luò)的科技論文推薦[J].山東大學(xué)學(xué)報:理學(xué)版,2016,51(5):94-101.

[24]馬建威,陳洪輝,Stephan R-M.基于混合推薦和隱馬爾科夫模型的服務(wù)推薦方法[J].中南大學(xué)學(xué)報:自然科學(xué)版, 2016,47(1):82-90.

[25]李程,曹菡,師軍.基于MapReduce的混合推薦算法及應(yīng)用[J].計算機(jī)技術(shù)與發(fā)展,2016,26(4):74-77.

WANG Mengxiang was born in 1991.She is an M.S.candidate at Northeastern University,and the member of CCF.Her research interests include database system and machine learning,etc.

王蒙湘（1991—），女，內(nèi)蒙古赤峰人，東北大學(xué)碩士研究生，CCF會員，主要研究領(lǐng)域為數(shù)據(jù)庫系統(tǒng)，機(jī)器學(xué)習(xí)等。

LI Fangfang was born in 1977.She received the Ph.D.degree in computer science from Northeastern University in 2009.Now she is a lecturer at Northeastern University,and the member of CCF.Her research interests include database and data management of CPS,etc.

李芳芳（1977—），女，黑龍江哈爾濱人，2009年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)計算機(jī)科學(xué)與工程學(xué)院講師，CCF會員，主要研究領(lǐng)域為數(shù)據(jù)庫，CPS數(shù)據(jù)管理等。

GU Yu was born in 1981.He received the Ph.D.degree in computer science from Northeastern University in 2010. Now he is a professor and Ph.D.supervisor at Northeastern University,the member of ACM,and the senior member of CCF.His research interests include distributed computing and big data analysis,etc.

谷峪（1981—），男，遼寧鞍山人，2010年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)計算機(jī)科學(xué)與工程學(xué)院教授、博士生導(dǎo)師，ACM會員，CCF高級會員，主要研究領(lǐng)域為分布式計算，大數(shù)據(jù)分析等。

YU Ge was born in 1962.He received the M.S.degree in computer science from Northeastern University in 1986, and Ph.D.degree in computer science from Kyushu University of Japan in 1996.Now he is a professor and Ph.D. supervisor at Northeastern University,and the member of ACM and IEEE,and the senior member of CCF.His research interests include database theory and technology,distributed system,parallel computing and cloud computing,etc.

于戈（1962—），男，遼寧大連人，1986年于東北大學(xué)獲得碩士學(xué)位，1996年于日本九州大學(xué)獲得計算機(jī)工學(xué)博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，中國計算機(jī)學(xué)會理事，ACM、IEEE會員，CCF高級會員，主要研究領(lǐng)域為數(shù)據(jù)庫理論，分布式系統(tǒng)，并行計算，云計算等。

Survey on Interactive Data Exploration*

WANG Mengxiang,LI fangfang,GU Yu,YU Ge+
Department of Computer Science,College of Computer Science and Engineering,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:yuge@mail.neu.edu.cn

Large data sets have exceeded the scale of terabytes and petabytes,and existing techniques can collect and store massive information.While database management systems have been constantly improved to offer a variety of complex data management capabilities,but the query tools cannot satisfy the needs of large data,so how to precisely understand and explore the massive data set remains a huge challenge.The focus of interactive data exploration(IDE) is to emphasize interaction,exploration and discovery.Users will accurately find the information they need with the minimum cost in the vast amounts of data.Firstly,this paper introduces the IDE and its application background,summarizes the general model and features of IDE,and analyzes the present situation of the query technology and the optimization techniques for query results.Furthermore,this paper analyzes and compares IDE prototype systems respectively.Finally,this paper summarizes and forecasts the techniques of IDE.

interactive data exploration;query recommendation;optimization for query results;user feedback;machine learning

10.3778/j.issn.1673-9418.1606010

A

：TP315

*The National Natural Science Foundation of China under Grant No.61272180(國家自然科學(xué)基金);the Fundamental Research Funds for the Central Universities of China under Grant No.N161604005(中央高校基本科研業(yè)務(wù)費(fèi)專項資金).

Received 2016-06,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.004.html

WANG Mengxiang,LI fangfang,GU Yu,et al.Survey on interactive data exploration.Journal of Frontiers of Computer Science and Technology,2017,11(2)：171-184.