交互式數據探索綜述*

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

東北大學 計算機科學與工程學院 計算機科學系，沈陽 110819

交互式數據探索綜述*

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

東北大學 計算機科學與工程學院 計算機科學系，沈陽 110819

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

交互式數據探索；查詢推薦；查詢結果優化；用戶反饋；機器學習

1 引言

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

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

2 交互式數據探索概述

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

Fig.1 Model of interactive data exploration system圖1 交互式數據探索系統模型

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

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

3 交互式數據探索的特點

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

交互式數據探索的特點可概括為三方面。

3.1 查詢動態性

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

3.2 交互反饋性

交互式數據探索的查詢動態性和交互反饋性是相輔相成的。交互反饋性體現在系統可以根據用戶的行為動態地調整查詢，準確預測數據，給出匹配用戶興趣的集合，為用戶提供更精準的、個性化的查詢結果。例如，AIDE[4]系統中，在發現相關的對象階段，依靠用戶的相關性反饋將數據分類，確定抽樣區域，以提高標記樣本的精度，這樣使得下一步空間探索中查詢結果優化的范圍更精確。

3.3 學習主動性

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

4 交互式數據探索研究技術現狀

基于交互式數據探索的框架設計，以及交互式數據探索的上述特點，交互式數據探索對信息的獲取也是通過查詢來實現的。因為目標不確定是交互式數據探索的重要特點，所以查詢層需要提供更多的功能支持交互層。相關研究主要從查詢推薦和查詢結果優化方面展開。

4.1 交互式數據探索的查詢推薦

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

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

4.1.1 基于內容的推薦

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

4.1.2 基于協同過濾的推薦

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

Fig.2 Architecture of QueRIE圖2 QueRIE體系結構

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

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

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

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

4.1.3 基于知識的推薦

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

4.1.4 組合推薦

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

4.1.5 各類推薦方法對比

每一類推薦方法都有其各自的優點和缺點，針對不同的數據類型，推薦效果也有所不同。如在基于內容的推薦方法中，對于特征提取的方法很難應用于媒體數據等非結構化數據。隨后發展的協同過濾技術，在一定程度上解決了推薦結果不豐富等問題，但這種技術大部分應用于單一應用系統數據源，并且它是基于大量歷史數據集進行的推薦，因而存在稀疏性、準確性等問題。基于知識的推薦雖然不存在冷啟動和稀疏性問題，但對知識的建模存在困難。組合推薦策略由于各種組合方式差異較大，不在此討論。幾種推薦方法的優缺點對比如表1所示。

4.2 查詢結果優化

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

在查詢結果優化方面，主要關注如何處理空結果查詢處理和多結果查詢處理兩個方面。

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

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

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

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

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

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

5 交互式數據探索原型系統對比

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

5.1 YmalDB系統

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

5.2 DICE系統

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

Fig.3 Architecture of YmalDB圖3 YmalDB體系結構

Fig.4 DICE approach圖4 DICE方法

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

5.3 SciBORQ系統

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

傳統的近似查詢應答和在線聚合方法不能使系統滿足完全控制資源消耗和精確查詢結果的要求。SciBORQ是一種數據探索型科學數據倉庫體系結構，它可以精確控制執行時間，提高查詢應答的質量。在SciBORQ中，將一種獲得用戶感興趣的多個數據樣本的抽樣方法稱為印象（impression）。印象不同于以往的抽樣方法，它偏向科學數據探索的興趣點，這種偏差抽樣很有價值，可以在更多感興趣的區域進行數據采樣。SciBORQ的獨特之處在于其多層的架構方法，重新優化可以保證所需的誤差范圍，即使它們偏離相關性。SciBORQ最終目標是把科學數據探索和發現過程構成一個完整的系統，在嚴格的誤差范圍和預定義的時間框架內產生高質量的結果。

5.4 BlinkDB系統

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

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

Fig.5 Architecture of BlinkDB圖5 BlinkDB體系結構

5.5 Charles系統

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

5.6 AIDE系統

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

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

Fig.6 Framework ofAIDE圖6 AIDE的框架結構

5.7 SnapToQuery系統

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

SnapToQuery系統的整體架構如圖7所示。系統的后端應用Naive方法和Data Contour方法對數據集進行了簡化，在前端增加了可視化的基于鏈接的可調節直方圖[51]。用戶可以通過操作滑塊條，在3個設備（鼠標、平板電腦、跳躍運動）上發布范圍查詢，隨后SnapToQuery系統在查詢規范內進行快照查詢。

Fig.7 Overall architecture of SnapToQuery圖7 SnapToQuery的整體構架

5.8 系統對比

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

6 研究展望

數據探索已經成為研究熱點，然而將數據探索與用戶反饋機制和機器學習結合起來依然存在諸多不足，面臨著諸多挑戰，有很多需要進一步研究的內容。

（1）用戶與系統的交互方式

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

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

（2）數據處理

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

Table 2 Comparison of prototype systems of interactive data exploration表2 交互式數據探索的原型系統對比

（3）查詢構建

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

7 總結與展望

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

[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.

附中文參考文獻：

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

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

[16]趙永梅,任大勇,張紅梅,等.用動態貝葉斯網絡構建協同過濾推薦的新方法[J].科學技術與工程,2011,11(9): 2012-2016.

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

[20]許海玲,吳瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報,2009,20(2):350-362.

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

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

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

[25]李程,曹菡,師軍.基于MapReduce的混合推薦算法及應用[J].計算機技術與發展,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—），女，內蒙古赤峰人，東北大學碩士研究生，CCF會員，主要研究領域為數據庫系統，機器學習等。

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年于東北大學獲得博士學位，現為東北大學計算機科學與工程學院講師，CCF會員，主要研究領域為數據庫，CPS數據管理等。

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年于東北大學獲得博士學位，現為東北大學計算機科學與工程學院教授、博士生導師，ACM會員，CCF高級會員，主要研究領域為分布式計算，大數據分析等。

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年于東北大學獲得碩士學位，1996年于日本九州大學獲得計算機工學博士學位，現為東北大學教授、博士生導師，中國計算機學會理事，ACM、IEEE會員，CCF高級會員，主要研究領域為數據庫理論，分布式系統，并行計算，云計算等。

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(國家自然科學基金);the Fundamental Research Funds for the Central Universities of China under Grant No.N161604005(中央高校基本科研業務費專項資金).

Received 2016-06,Accepted 2016-10.

CNKI網絡優先出版: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.