吳小全，李　暉，陳　梅，戴震宇

WU Xiaoquan1，2,LI Hui1，2,CHEN Mei1，2,DAI Zhenyu1，2

1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽 550025

2.貴州大學(xué) 貴州省先進(jìn)計(jì)算與醫(yī)療信息服務(wù)工程實(shí)驗(yàn)室，貴陽 550025

1.College of Computer Science and Technology,Guizhou University,Guiyang 550025,China

2.Guizhou Engineering Lab of Advanced Computing and Medical Information Services,Guizhou University,Guiyang 550025,China

1　引言

可視化通常是數(shù)據(jù)分析中一個(gè)關(guān)鍵步驟。加拿大維多利亞大學(xué)的研究人員[1]提出了可視化分析任務(wù)，包括三個(gè)主要步驟：數(shù)據(jù)屬性子集選擇、可視化展現(xiàn)模式推薦、數(shù)據(jù)和圖表映射。文獻(xiàn)[1]證明，計(jì)算出和目標(biāo)具有強(qiáng)相關(guān)性的屬性子集并為其確定合適的可視化展現(xiàn)模式是一項(xiàng)困難的技術(shù)工作。尤其是當(dāng)數(shù)據(jù)和維度數(shù)量增加時(shí)，現(xiàn)有的可視化分析系統(tǒng)[2-3]通常會(huì)面臨如下問題：

（1）多維屬性子集選擇的搜索空間不夠大?，F(xiàn)有數(shù)據(jù)分析工具在對(duì)多維數(shù)據(jù)集進(jìn)行非平凡屬性組分析時(shí)，需耗費(fèi)大量時(shí)間進(jìn)行迭代計(jì)算并構(gòu)建可視化展示模式，且這個(gè)過程通常需要人為干預(yù)和反饋，未能包含對(duì)所有重要的屬性組合的探索和評(píng)估。

（2）對(duì)分析人員的技術(shù)門檻要求較高。由于通常要求分析人員能夠針對(duì)初步分析結(jié)果做進(jìn)一步的關(guān)聯(lián)分析和探索，分析人員需具備良好的統(tǒng)計(jì)知識(shí)和編程技術(shù)素養(yǎng)，進(jìn)一步增加了應(yīng)用難度。

（3）分析過程的自動(dòng)化程度不夠高。缺乏基于用戶行為反饋的推薦模型及其展現(xiàn)模式的自動(dòng)化更新機(jī)制。

針對(duì)解決上述問題，法國(guó)里爾第二大學(xué)的研究人員設(shè)計(jì)并實(shí)現(xiàn)了基于知識(shí)庫技術(shù)實(shí)現(xiàn)可視化推薦系統(tǒng)VizAssist[4]。該系統(tǒng)為了推薦出合適的可視化圖表，在屬性選擇上充分考慮到屬性的數(shù)據(jù)類型和屬性的權(quán)重，優(yōu)先選擇權(quán)重高的屬性通過知識(shí)庫內(nèi)部已制定規(guī)則構(gòu)建可視化展現(xiàn)模式。然而在設(shè)計(jì)知識(shí)庫時(shí)，它依然存在規(guī)則有限的缺陷，導(dǎo)致部分不符合該規(guī)則的屬性無法構(gòu)建可視化展現(xiàn)模式。此外，VizAssist通過人為設(shè)置屬性的權(quán)重和屬性的數(shù)據(jù)類型來決定推薦的屬性列，這使得推薦出的數(shù)據(jù)可視化展示模式過于依賴人為初始化的設(shè)定，導(dǎo)致人為干預(yù)成為數(shù)據(jù)分析的主導(dǎo)地位，無法實(shí)現(xiàn)自動(dòng)探索和推薦。Voyager[5]是華盛頓大學(xué)的研究人員研發(fā)的可視化推薦系統(tǒng)，其為數(shù)據(jù)分析添加合適的統(tǒng)計(jì)函數(shù)，通過人機(jī)交互進(jìn)行數(shù)據(jù)探索，并將探索出的數(shù)據(jù)自動(dòng)生成可視化圖表，從而較為有效地支撐用戶進(jìn)行交互式數(shù)據(jù)導(dǎo)航。

現(xiàn)有的可視化推薦系統(tǒng)通常是通過參數(shù)設(shè)置來推薦出部分有價(jià)值的可視化展現(xiàn)模式，在一定程度上提高了推薦的準(zhǔn)確率。但大多數(shù)推薦僅僅利用靜態(tài)的初始化設(shè)置而忽略了數(shù)據(jù)本身動(dòng)態(tài)組合的特性。數(shù)據(jù)屬性之間的關(guān)聯(lián)性是數(shù)據(jù)價(jià)值的潛在表現(xiàn)。此外，現(xiàn)有可視化推薦系統(tǒng)通常引入了過多的人為判斷操作，在處理大規(guī)模復(fù)雜多維數(shù)據(jù)時(shí)，將會(huì)增加交互難度。

針對(duì)目前可視化分析領(lǐng)域存在的上述問題，本文基于屬性相關(guān)性分析策略，研究非平凡可視化推薦的度量標(biāo)準(zhǔn)，引入典型關(guān)聯(lián)算法用于解決非平凡屬性組的選擇問題。設(shè)計(jì)并實(shí)現(xiàn)了數(shù)據(jù)分析可視化推薦系統(tǒng)DRVisSys，主要技術(shù)工作如下：

（1）在非平凡屬性組選擇環(huán)節(jié)中引入屬性關(guān)聯(lián)分析技術(shù)。為了從整體考慮屬性之間的相關(guān)性，應(yīng)用典型關(guān)聯(lián)分析技術(shù)計(jì)算屬性之間的關(guān)聯(lián)系數(shù)，用典型關(guān)聯(lián)系數(shù)大小作為非平凡屬性組合的評(píng)測(cè)標(biāo)準(zhǔn)[6-7]。

（2）通過自動(dòng)構(gòu)建大量SQL語句來生成所有屬性組及屬性組對(duì)應(yīng)的數(shù)據(jù)子集。并針對(duì)大量SQL語句執(zhí)行過程中資源消耗較高的問題，提出并行執(zhí)行查詢和共享公共數(shù)據(jù)子集的技術(shù)。

（3）引入知識(shí)庫技術(shù)來構(gòu)建可視化展示模式。只需將選擇出的非平凡屬性組及對(duì)應(yīng)的數(shù)據(jù)子集作為輸入，便可自動(dòng)通過知識(shí)庫構(gòu)建出可視化展現(xiàn)模式。

（4）設(shè)計(jì)并實(shí)現(xiàn)了基于用戶反饋的可視化推薦模型的持續(xù)更新方法，可根據(jù)用戶行為迭代出更合適的展示模式[8]。

2　預(yù)備知識(shí)

2.1　非平凡屬性組評(píng)測(cè)

麻省理工學(xué)院的研究人員，在2015年提出通過計(jì)算原數(shù)據(jù)集與參考數(shù)據(jù)集之間的偏差來確定非平凡屬性組的方法[9]。該方法假設(shè)偏差值越大，屬性組成為非平凡屬性組的可能性越大。但部分特殊值可能會(huì)嚴(yán)重影響整體偏差值，從而導(dǎo)致非平凡屬性組的分析有偏差。為解決此問題，本文通過分析屬性之間相關(guān)關(guān)系來確定非平凡屬性組。為了能從整體考慮屬性之間相關(guān)關(guān)系，本文在計(jì)算過程中還引入了典型關(guān)聯(lián)分析技術(shù)。

計(jì)算屬性組的典型關(guān)聯(lián)系數(shù)時(shí)存在下述問題：當(dāng)屬性組里存在一個(gè)或者多個(gè)非數(shù)值屬性列時(shí)，無法計(jì)算非數(shù)值屬性列的關(guān)聯(lián)系數(shù)。本文根據(jù)SQL92標(biāo)準(zhǔn)將數(shù)值類型屬性歸類為度量屬性，其他屬性歸為維度屬性。在計(jì)算維度和度量的相關(guān)性時(shí)，首先按維度屬性對(duì)數(shù)據(jù)集進(jìn)行分組，然后在分組內(nèi)計(jì)算度量屬性的SUM、AVG、COUNT聚合函數(shù)值，選擇組內(nèi)任意屬性構(gòu)建屬性組并計(jì)算其相關(guān)性。

為了解決當(dāng)前可視化推薦系統(tǒng)對(duì)多維屬性子集選擇的搜索空間不夠全的問題，DRVisSys對(duì)整個(gè)屬性子集空間進(jìn)行探索[10]。對(duì)任意數(shù)據(jù)集進(jìn)行探索并生成候選屬性組時(shí)，候選屬性組的數(shù)量由數(shù)據(jù)集的維度屬性和度量屬性決定。假設(shè)數(shù)據(jù)集中有m1個(gè)維度屬性，m2個(gè)度量屬性，在生成候選屬性組時(shí)，根據(jù)各維度屬性進(jìn)行分組，計(jì)算組內(nèi)度量屬性的聚合函數(shù)值（SUM、AVG、COUNT）。然后任意從該組中選擇屬性構(gòu)建屬性組，則共計(jì)會(huì)產(chǎn)生屬性組。

2.2　基于可擴(kuò)展VKB技術(shù)的知識(shí)庫

基于VKB技術(shù)的知識(shí)庫起源于1980年的BHARAT系統(tǒng)[11-12]。2015年，VizAssist系統(tǒng)的研究人員提出基于VKB技術(shù)的知識(shí)庫構(gòu)建方法，用于簡(jiǎn)化復(fù)雜可視化模型的構(gòu)建。然而VKB技術(shù)受限于有限的規(guī)則模型，無法分析當(dāng)前知識(shí)庫內(nèi)現(xiàn)有規(guī)則之外的可視化模型。本文提出基于可擴(kuò)展VKB技術(shù)的知識(shí)庫模型，為擴(kuò)展知識(shí)庫規(guī)則定義一套擴(kuò)展機(jī)制，可通過擴(kuò)展API添加新的規(guī)則，不斷完善知識(shí)庫。這使得推薦出的可視化展示模型能夠更好地滿足需求。

2.3　符號(hào)列表

本文用符號(hào)D={d1,d2,…,dn}表示數(shù)據(jù)子集，其中每一個(gè)di由k個(gè)屬性組成{A1,A2,…,Ak} ，每個(gè)屬性的數(shù)據(jù)類型為ti，用DT表示屬性分類。下面列出了文中用到的其他符號(hào)。

VKB知識(shí)庫模型所需符號(hào)定義：

D={d1,d2,…,dn}為數(shù)據(jù)子集定義；D={A1,A2,…,Ak}為數(shù)據(jù)屬性定義；DT={Dimension,Measure}表示屬性類型，簡(jiǎn)寫為DT={dim,mea}；ti,ti∈DT表示每個(gè)屬性的數(shù)據(jù)類型；C={C1,C2,…,Cm}為每個(gè)組合的關(guān)聯(lián)系數(shù)；V={V1,V2,…,Vv}為非平凡屬性組；ρ為推薦系數(shù)；W為屬性權(quán)重值。

3　系統(tǒng)總體設(shè)計(jì)

3.1　系統(tǒng)總體結(jié)構(gòu)

DRVisSys系統(tǒng)的總體架構(gòu)如圖1所示。主要由可視化表現(xiàn)層、執(zhí)行引擎層和數(shù)據(jù)庫持久層三部分組成。

圖1　DRVisSys系統(tǒng)結(jié)構(gòu)框圖

可視化表現(xiàn)層主要分為三個(gè)模塊：（1）可視化構(gòu)建查詢語句模塊。主要通過點(diǎn)擊拖拽數(shù)據(jù)庫表字段來定義查詢條件，實(shí)現(xiàn)數(shù)據(jù)子集的生成。（2）可視化展示模式構(gòu)建模塊。在Web頁面使用Echart3.0顯示推薦可視化圖表，并實(shí)現(xiàn)了圖表數(shù)據(jù)異步加載。（3）用戶交互模塊。DRVisSys系統(tǒng)記錄和分析當(dāng)前用戶對(duì)圖表選擇偏好，異步地將該用戶行為反饋給后臺(tái)執(zhí)行引擎層。

執(zhí)行引擎層主要負(fù)責(zé)計(jì)算和生成可視化推薦模型。具體包括四部分：

（1）查詢構(gòu)建模塊。主要負(fù)責(zé)對(duì)任意屬性組合構(gòu)建查詢語句，生成對(duì)應(yīng)的數(shù)據(jù)子集。

（2）查詢優(yōu)化模塊。負(fù)責(zé)優(yōu)化（1）中查詢語句的執(zhí)行，減少整個(gè)執(zhí)行引擎中數(shù)據(jù)庫查詢延遲。在此部分，本文設(shè)計(jì)并實(shí)現(xiàn)了查詢的并行執(zhí)行機(jī)制和共享公共表達(dá)式的優(yōu)化策略。具體技術(shù)方法詳見本文4.1節(jié)。

（3）可視化推薦引擎模塊。主要負(fù)責(zé)計(jì)算出K非平凡屬性組。該模塊計(jì)算（1）中數(shù)據(jù)子集的典型關(guān)聯(lián)系數(shù)，以關(guān)聯(lián)系數(shù)排序，并選擇前K個(gè)作為非平凡屬性組。

（4）基于VKB技術(shù)的知識(shí)庫模塊。負(fù)責(zé)利用基于VKB技術(shù)的知識(shí)庫技術(shù)，為（3）中生成的非平凡屬性組構(gòu)建出合適的可視化展現(xiàn)模式。

3.2　可視化展現(xiàn)模式構(gòu)建

在DRVisSys系統(tǒng)中，針對(duì)一組非平凡的屬性組{V1,V2,…,Vv}，知識(shí)庫通常將V中的屬性類型、屬性數(shù)據(jù)值統(tǒng)計(jì)、屬性的權(quán)重等因素作為知識(shí)庫引擎構(gòu)建可視化展現(xiàn)模式時(shí)的輸入。知識(shí)庫引擎將輸入的參數(shù)結(jié)合庫中規(guī)則進(jìn)行計(jì)算，然后輸出符合知識(shí)庫中規(guī)則的可視化展現(xiàn)模式。

在本文的工作中，通過基于VKB技術(shù)的知識(shí)庫構(gòu)建可視化展示模式。本文針對(duì)不同圖表的特性構(gòu)建對(duì)應(yīng)的推薦規(guī)則。例如：柱狀圖用于展現(xiàn)多類別數(shù)據(jù)之間的差異，其特點(diǎn)如下：（1）展現(xiàn)數(shù)據(jù)可劃分多種類別且類別不能過多；（2）數(shù)據(jù)必須是兩維以上，其中至少一維是數(shù)值列；（3）數(shù)據(jù)維度不能過多，否則無法展示多類別的比較關(guān)系。系統(tǒng)根據(jù)該特點(diǎn)設(shè)計(jì)柱形圖模型規(guī)則如下：（1）輸入數(shù)據(jù)集的維度是2～5維；（2）至少存在一列數(shù)值數(shù)據(jù)，該數(shù)值類型的列用作為Y軸；（3）存在一列數(shù)據(jù)可用于分類，類別不超過30種，該列作為X軸。上述規(guī)則涉及的參數(shù)可根據(jù)需求調(diào)整。其他圖表亦根據(jù)其特性構(gòu)建相應(yīng)的規(guī)則。針對(duì)滿足多種圖表模型規(guī)則的數(shù)據(jù)，系統(tǒng)能生成多個(gè)可視化圖表，從多個(gè)角度展示數(shù)據(jù)價(jià)值。

針對(duì)上述構(gòu)建的知識(shí)庫規(guī)則，本文構(gòu)建可視化展示模式的步驟如下：（1）確定非平凡屬性組中的維度屬性和度量屬性，使用維度屬性和度量屬性生成合適的坐標(biāo)軸。（2）統(tǒng)計(jì)屬性組中的數(shù)據(jù)分布情況。通過COUNT、AVG和SUM可以了解屬性值分布及總體比例情況。（3）構(gòu)建可視化展現(xiàn)模式。將（1）、（2）中計(jì)算結(jié)果及屬性組對(duì)應(yīng)的數(shù)據(jù)集作為輸入，利用庫中規(guī)則進(jìn)行計(jì)算，將屬性組映射成對(duì)應(yīng)的可視化展現(xiàn)模式。

3.3　可視化推薦展示結(jié)果

如圖2是DRVisSys系統(tǒng)針對(duì)“病人治療費(fèi)用表”推薦出的可視化圖表。整個(gè)區(qū)域分為三部分：A區(qū)是用于對(duì)每一個(gè)可視化圖表的放大展示；B區(qū)是用于實(shí)時(shí)展示根據(jù)用戶行為反饋生成的新的可視化圖表；C區(qū)是用于顯示推薦出的所有可視化圖表。

圖2　DRVisSys推薦出的可視化展示圖表

從圖2可以看出，DRVisSys根據(jù)不同屬性集推薦出各種圖表對(duì)數(shù)據(jù)進(jìn)行展示。以（A）中的雷達(dá)圖生成為例，該圖表的構(gòu)建流程簡(jiǎn)述如下：

（1）構(gòu)建雷達(dá)圖規(guī)則模型。雷達(dá)圖是用來顯示多項(xiàng)指標(biāo)數(shù)據(jù)的數(shù)值占比情況。雷達(dá)圖的推薦規(guī)則如下：屬性維度數(shù)目3～10；任意兩項(xiàng)指標(biāo)相關(guān)系數(shù)偏差不超過0.1；數(shù)據(jù)量不超過100條。

（2）為數(shù)據(jù)集構(gòu)建可視化展現(xiàn)模式。當(dāng)前雷達(dá)圖屬性列有{ks，cwf，fyh，jcf，hyf}，將字符型屬性ks作為維度屬性，其他作為度量屬性。通過對(duì)任意屬性列的關(guān)聯(lián)系數(shù)計(jì)算，得知其關(guān)聯(lián)系數(shù)的偏差都不超過0.1。上述計(jì)算結(jié)果符合雷達(dá)圖規(guī)則，因而將該屬性組映射成雷達(dá)圖。

DRVisSys支持用戶交互。系統(tǒng)可根據(jù)用戶行為反饋，更新推薦模型。DRVisSys對(duì)當(dāng)前用戶選中可視化展示模式的偏好行為進(jìn)行分析，將相應(yīng)的屬性添加權(quán)重并重新計(jì)算出非平凡屬性組，更新當(dāng)前推薦模型，構(gòu)建新的可視化展現(xiàn)模式。相應(yīng)的結(jié)果，均在B區(qū)列出。

4　查詢優(yōu)化及主要算法設(shè)計(jì)

本章主要介紹DRVisSys系統(tǒng)的兩種查詢優(yōu)化技術(shù)，分別是并行執(zhí)行查詢技術(shù)和共享公共表達(dá)式技術(shù)[13-15]。此外，為了過濾大量的非平凡屬性組，DRVisSys引入了典型關(guān)聯(lián)算法并采用奇異值分解法求解出典型關(guān)聯(lián)系數(shù)，取TopK個(gè)屬性組定義為非平凡屬性組。

4.1　查詢優(yōu)化

4.1.1查詢的并行執(zhí)行

為了增加多維屬性子集選擇的搜索空間，DRVisSys系統(tǒng)對(duì)數(shù)據(jù)集中的所有組合進(jìn)行探索。對(duì)于數(shù)據(jù)集中有m1個(gè)維度屬性m2個(gè)度量屬性，生成的候選屬性組的數(shù)量是m1×(2m2-m2)。每個(gè)屬性組所對(duì)應(yīng)的數(shù)據(jù)子集是通過執(zhí)行一條為該屬性組特別構(gòu)建的SQL查詢語句而得到。因此，獲取各候選屬性組對(duì)應(yīng)的數(shù)據(jù)子集需要構(gòu)建并執(zhí)行大量SQL語句?？紤]到候選屬性組的數(shù)量，此過程的時(shí)間開銷極大。DRVisSys通過采用多線程并行執(zhí)行上述SQL任務(wù)的方法來提高查詢執(zhí)行效率。為了減少并行執(zhí)行過程中數(shù)據(jù)庫連接增加的問題，DRVis-Sys引入了數(shù)據(jù)庫連接池技術(shù)來實(shí)現(xiàn)數(shù)據(jù)庫連接共享，進(jìn)一步減少數(shù)據(jù)庫連接延遲。

4.1.2查詢重寫和執(zhí)行優(yōu)化

在構(gòu)建候選屬性組合時(shí)，屬性組之間存在相同屬性，即與之相對(duì)應(yīng)的SQL之間存在公共的表達(dá)式。為了減少查詢的執(zhí)行開銷，DRVisSys系統(tǒng)通過基于共享公共表達(dá)式（及其對(duì)應(yīng)的數(shù)據(jù)子集）的查詢重寫技術(shù)實(shí)現(xiàn)多個(gè)SQL查詢語句的合并。具體優(yōu)化步驟如下：

（1）合并同一屬性的不同聚合查詢。在同一分組屬性下，對(duì)所有度量屬性添加不同聚合函數(shù)（如：SUM、AVG、COUNT）。若為每個(gè)聚合函數(shù)操作構(gòu)建一個(gè)查詢語句，會(huì)造成資源浪費(fèi)。DRVisSys將類似于如下查詢(a,m,f1),(a,m,f2),…,(a,m,fi)合并，重寫成新的查詢語句 (a,m,{f1,f2,…,fi})。

（2）合并同一分組屬性的不同查詢。針對(duì)同一分組屬性下不同屬性的聚合查詢，本文采用group by分組屬性區(qū)分不同聚合查詢的結(jié)果集，將多個(gè)聚合查詢重寫成一個(gè)聚合查詢。DRVisSys系統(tǒng)將類似如下的查詢語句(a,m1,f),(a,m2,f),…,(a,mi,f)合并，重寫形成新的查詢語句(a,{m1,m2,…,mi},f)。

（3）添加分組屬性，合并具有公共子表達(dá)式的不同查詢。此外，存在一種特例：其中一條查詢語句的結(jié)果集包含另外一條查詢語句的結(jié)果集。此時(shí)，不能利用原有分組屬性區(qū)分查詢結(jié)果集，需為其添加新的分組屬性。例如：合并如下所示的Q1和Q2兩個(gè)查詢語句時(shí)，需要為其新增分組屬性G1和G2。

Q1=SELECTA，F(xiàn)（m） FROMDWHEREX=’貴州’GROUP BYA

Q2=SELECTA，F(xiàn)（m）FROMDGROUP BYA

將上述兩個(gè)查詢Q1和Q2合并，重寫成新查詢Q3：

Q3=SELECTA，F(xiàn)（m），CASE IFX=’貴州’THEN 1 ELSE 0 ENDAS G1，1AS G2FROMDGROUP BYA，G1，G2

4.2　非平凡屬性組選擇算法

為了從大量屬性組合中過濾掉大部分平凡的屬性組，本文引入CCA[16]作為非平凡屬性組的評(píng)估算法。通過CCA算法可以計(jì)算出屬性之間的關(guān)聯(lián)系數(shù)，將其作為非平凡屬性組的評(píng)估標(biāo)準(zhǔn)。但在求解典型關(guān)聯(lián)系數(shù)時(shí)，為了避免屬性組出現(xiàn)的小樣本數(shù)據(jù)可能導(dǎo)致無法計(jì)算出關(guān)聯(lián)系數(shù)的問題，DRVisSys系統(tǒng)采用奇異值分解法求解典型關(guān)聯(lián)系數(shù)。非平凡屬性組選擇算法的步驟如下。

（1）計(jì)算推薦系數(shù)。通過計(jì)算屬性組之間典型關(guān)聯(lián)系數(shù)作為推薦的系數(shù)，下面是CCA計(jì)算相關(guān)系數(shù)過程：

①設(shè)定屬性組中存在各包含n個(gè)樣本的U和V，而且U和V的維度大于1。

②計(jì)算出樣本U的方差Suu，樣本V的方差Svv，以及U和V樣本的協(xié)方差Suv。

④對(duì)矩陣M進(jìn)行奇異值分解，計(jì)算出最大的奇異值，即為所需的最大關(guān)聯(lián)系數(shù)ρ。

（2）加權(quán)推薦系數(shù)?？紤]到部分維度屬性在應(yīng)用中有著特殊的實(shí)際意義，例如：日期、姓名和部門等，本文采用層疊隱馬爾可夫算法[17]識(shí)別出此類重要屬性并為其添加權(quán)重值。該算法為每種命名實(shí)體的識(shí)別方法構(gòu)造獨(dú)有的識(shí)別模型，例如：人名識(shí)別的HMM、地名識(shí)別的HMM和機(jī)構(gòu)識(shí)別的HMM等等。當(dāng)對(duì)某一個(gè)屬性實(shí)體進(jìn)行識(shí)別時(shí)，如果屬于重要實(shí)體，設(shè)置該屬性的權(quán)重值W=1；否則，設(shè)置權(quán)重值W=0。

在選擇非平凡屬性組時(shí)考慮到部分屬性的權(quán)重值，本文引入式（1），將權(quán)重值與關(guān)聯(lián)系數(shù)相結(jié)合，重新計(jì)算推薦系數(shù)。

（3）取TopK個(gè)屬性組將加權(quán)后的推薦系數(shù)進(jìn)行排序，取前K個(gè)屬性組合作為非平凡屬性組合。推薦引擎默認(rèn)取K=15，但當(dāng)候選組合數(shù)超過15組且推薦系數(shù)ρ＞0.9，引擎會(huì)自動(dòng)添加推薦系數(shù)大于0.9的屬性組作為非平凡屬性組，其中K和ρ的值可根據(jù)需求自定義。

4.3　計(jì)算非平凡屬性組的案例

為進(jìn)一步說明非平凡屬性組的選擇算法流程，本節(jié)以“病人治療費(fèi)用表”為例進(jìn)行說明，該表共23維屬性，其中有10維維度屬性，13維度量屬性。根據(jù)2.1節(jié)中的方法構(gòu)建屬性組合及對(duì)應(yīng)數(shù)據(jù)子集，然后通過推薦算法計(jì)算出平凡屬性組，步驟如下：

（1）利用典型關(guān)聯(lián)算法計(jì)算屬性組的關(guān)聯(lián)系數(shù)，并對(duì)其進(jìn)行排序。本節(jié)取三個(gè)屬性組合進(jìn)行講解：屬性組V1={ks,cwf,hyf,fyh,jcf}，計(jì)算典型關(guān)聯(lián)系數(shù)ρ=0.94；屬性組V2={cyqtzd,hyf,cwf,fyh,jcf,xyf}，ρ=0.96；屬性組V3={ks,zyf,ts}，ρ=0.46。

（2）使用層疊馬爾可夫算法識(shí)別重要屬性并對(duì)屬性進(jìn)行加權(quán)。針對(duì)屬性組V1，通過算法識(shí)別得出ks（科室）在命名實(shí)體中屬于部門實(shí)體，屬于重要屬性且ρ＞0.6，根據(jù)式（1）重新計(jì)算出推薦系數(shù)ρ=1；針對(duì)屬性組V2識(shí)別，不屬于重要屬性，推薦系數(shù)不需修改；針對(duì)屬性組V3，識(shí)別出ks屬于重要屬性且ρ＜0.6，根據(jù)式（1）重新計(jì)算出推薦系數(shù)ρ=0.775。同理，其他屬性組以此方法計(jì)算推薦系數(shù)。

（3）對(duì)重新計(jì)算的推薦系數(shù)進(jìn)行排序，取TopK個(gè)屬性組作為非平凡屬性組，K=15。

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

對(duì)DRVisSys系統(tǒng)性能進(jìn)行評(píng)測(cè)和分析。實(shí)驗(yàn)過程中選用不同數(shù)據(jù)量、不同維度、不同記錄數(shù)的數(shù)據(jù)集進(jìn)行評(píng)估，評(píng)估指標(biāo)是DRVisSys推薦出可視化展現(xiàn)模式所需的時(shí)間開銷。測(cè)試數(shù)據(jù)包含20個(gè)不同數(shù)據(jù)集，具體數(shù)據(jù)集描述如表1所示。

表1　實(shí)驗(yàn)數(shù)據(jù)集描述

所有實(shí)驗(yàn)運(yùn)行在兩個(gè)節(jié)點(diǎn)上，分別是分析數(shù)據(jù)集的數(shù)據(jù)節(jié)點(diǎn)和推薦引擎的執(zhí)行節(jié)點(diǎn)，其中數(shù)據(jù)節(jié)點(diǎn)數(shù)量可根據(jù)實(shí)驗(yàn)要求進(jìn)行配置，執(zhí)行引擎節(jié)點(diǎn)是單節(jié)點(diǎn)。節(jié)點(diǎn)的參數(shù)配置如表2。

表2　實(shí)驗(yàn)節(jié)點(diǎn)參數(shù)配置

如圖3、圖4是系統(tǒng)在不同數(shù)據(jù)集下的性能測(cè)試結(jié)果。圖3是10萬條數(shù)據(jù)和100萬條數(shù)據(jù)在不同維度情況下的性能測(cè)試結(jié)果。實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)集記錄數(shù)相同時(shí)，隨著屬性維度的增加，系統(tǒng)執(zhí)行所需時(shí)間不斷增加。圖3中，當(dāng)維度低于50時(shí)，10萬條記錄和100萬條記錄執(zhí)行時(shí)間差較小，執(zhí)行時(shí)間在3～25 s；當(dāng)屬性維度高于50維時(shí)，執(zhí)行時(shí)間都偏高。這是由于：（1）隨著屬性維度的增加，候選屬性組合數(shù)呈指數(shù)增加。（2）隨著候選屬性組合數(shù)量的增長(zhǎng)，使構(gòu)建與候選屬性組相對(duì)應(yīng)的數(shù)據(jù)子集的CPU開銷、磁盤I/O和網(wǎng)絡(luò)傳輸開銷均顯著增加。（3）在計(jì)算出候選屬性組的推薦系數(shù)時(shí)，所需要的CPU開銷也隨著候選屬性組合數(shù)量的顯著增長(zhǎng)而增加。

圖3　10萬條和100萬條數(shù)據(jù)執(zhí)行時(shí)間

為驗(yàn)證數(shù)據(jù)量對(duì)系統(tǒng)效率的影響，對(duì)100 MB和500 MB的數(shù)據(jù)集在不同維度情況下進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如圖4所示。維度相同的情況下，500 MB數(shù)據(jù)執(zhí)行所需時(shí)間明顯長(zhǎng)于100 MB。數(shù)據(jù)量相同的情況下，維度越高，所需執(zhí)行時(shí)間越長(zhǎng)。

圖4　100 MB和500 MB數(shù)據(jù)執(zhí)行時(shí)間

圖3、圖4實(shí)驗(yàn)結(jié)果表明，該系統(tǒng)針對(duì)屬性維度低于50的數(shù)據(jù)集，通常能夠在幾十秒內(nèi)推薦出合適的可視化展示模式；系統(tǒng)針對(duì)高維度、數(shù)量大的數(shù)據(jù)集，亦能相對(duì)高效地完成推薦。

6　用戶評(píng)價(jià)實(shí)驗(yàn)

上一章驗(yàn)證DRVisSys系統(tǒng)的性能，本章邀請(qǐng)用戶使用真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，通過獲取用戶對(duì)該系統(tǒng)推薦圖表的反饋來檢驗(yàn)推薦效果。為此，該實(shí)驗(yàn)選擇10個(gè)真實(shí)數(shù)據(jù)集（包含醫(yī)療數(shù)據(jù)、金融數(shù)據(jù)、NBA球員比賽數(shù)據(jù)）。實(shí)驗(yàn)招募16名計(jì)算機(jī)學(xué)院的在校碩士生參與實(shí)驗(yàn)，參與者有從事數(shù)據(jù)分析的人員和非數(shù)據(jù)分析方向的人員。對(duì)推薦滿意度進(jìn)行對(duì)比分析，本文選擇VizAssist系統(tǒng)做實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)步驟如下：

（1）利用DRVisSys系統(tǒng)和VizAssist系統(tǒng)對(duì)10個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。兩個(gè)系統(tǒng)在對(duì)不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)時(shí)，同時(shí)對(duì)同一數(shù)據(jù)集的推薦圖表進(jìn)行對(duì)比分析，比較各系統(tǒng)的推薦效果。

（2）16位參與者為系統(tǒng)推薦的前5個(gè)圖表打分（滿分為10）。參與者在評(píng)分前，需要對(duì)當(dāng)前數(shù)據(jù)集進(jìn)行了解，從而能更好地判斷當(dāng)前推薦是否有價(jià)值、有意義，推薦圖表是否符合用戶需求。

統(tǒng)計(jì)前5個(gè)推薦可視化圖表平均評(píng)分情況，結(jié)果如表3所示。

從表3可以看出，DRVisSys系統(tǒng)的推薦效果明顯好于VizAssist系統(tǒng)。DRVisSys系統(tǒng)采用典型關(guān)聯(lián)算法整體分析屬性之間相關(guān)關(guān)系，并且采用層疊馬爾可夫算法對(duì)重要實(shí)體屬性加權(quán)。VisAssist系統(tǒng)通過屬性權(quán)重確定推薦屬性，并采用交互式遺傳算法修改屬性權(quán)重，重新生成推薦圖表。從推薦效果上看，本文中采用的算法推薦效果更好，同時(shí)也說明屬性之間關(guān)聯(lián)性是數(shù)據(jù)價(jià)值的潛在表現(xiàn)。

7　結(jié)束語

對(duì)大規(guī)模復(fù)雜多維數(shù)據(jù)進(jìn)行分析時(shí)，現(xiàn)有的可視化分析工具需要耗費(fèi)大量時(shí)間進(jìn)行反復(fù)迭代計(jì)算，并且存在對(duì)多維屬性子集探索空間不夠大，對(duì)分析人員技術(shù)門檻高和分析過程自動(dòng)化程度不夠高等問題。本文設(shè)計(jì)并實(shí)現(xiàn)了基于屬性相關(guān)性分析的可視化推薦系統(tǒng)DRVisSys，運(yùn)用典型關(guān)聯(lián)分析算法完成非平凡屬性組的選擇，并基于VKB技術(shù)的知識(shí)庫構(gòu)建合適的可視化展示模式。同時(shí)，針對(duì)執(zhí)行效率問題，引入并行執(zhí)行查詢和基于公共表達(dá)式的查詢重寫技術(shù)。實(shí)驗(yàn)結(jié)果表明，DRVisSys系統(tǒng)能快速為不同維度的數(shù)據(jù)集推薦出合適可視化展現(xiàn)模式。

表3　可視化推薦圖表評(píng)分統(tǒng)計(jì)表

參考文獻(xiàn)：

[1]Grammel L，Tory M，Storey M A.How information visualization novices construct visualizations[J].IEEE Transactions on Visualization and Computer Graphics，2010，16（6）：943-952.

[2]Mackinlay J，Hanrahan P，Stolte C.Show me：Automatic presentation for visual analysis[J].IEEE Transactions on Visualization and Computer Graphics，2007，13（6）：1137-1144.

[3]Dan M.Tableau your data!：Fast and easy visual analysis with tableau software[M].[S.l.]：Wiley Publishing，2013.

[4]Bouali F，Guettala A，Venturini G.VizAssist：An interactive user assistant for visual data mining[J].The Visual Computer，2016，32（11）：1447-1463.

[5]Wongsuphasawat K，Moritz D，Anand A，et al.Voyager：Exploratory analysis via faceted browsing of visualization recommendations[J].IEEE Transactions on Visualization and Computer Graphics，2016，22（1）：649-658.

[6]Naimi A I，Westreich D J.Big data：A revolution that will transform how we live，work，and think[J].American Journal of Epidemiology，2014，47（17）：181-183.

[7]梁吉業(yè)，馮晨嬌，宋鵬.大數(shù)據(jù)相關(guān)分析綜述[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（1）：1-18.

[8]Gotz D，Wen Z.Behavior-driven visualization recommendation[C]//Proceedings of International Conference on Intelligent User Interfaces，Sanibel Island，F(xiàn)lorida，USA，2009：315-324.

[9]Vartak M，Rahman S，Madden S，et al.SEEDB：efficient data-driven visualization recommendations to support visual analytics[J].Proceedings of the VLDB Endowment，2015，8（13）：2182-2193.

[10]Broeksema B，Telea A C，Baudel T.Visual analysis of multi-dimensional categorical data sets[C]//Proceedings of Computer Graphics Forum，2013：158-169.

[11]Gnanamgari S.Information presentation through default displays[M].[S.l.]：University of Pennsylvania，1981.

[12]Senay H，Ignatius E.A knowledge-based system for visualization design[M].[S.l.]：IEEE Computer Society Press，1994.

[13]Giannikis G，Makreshanski D，Alonso G，et al.Shared workload optimization[J].Proceedings of the VLDB Endowment，2014，7（6）：429-440.

[14]Dalvi N N，Sanghai S K，Roy P，et al.Pipelining in multi-query optimization[J].Journal of Computer and System Sciences，2003，66（4）：728-762.

[15]Sellis T K.Multiple-query optimization[J].ACM Transactions on Database Systems（TODS），1988，13（1）：23-52.

[16]Dan K.A singularly valuable decomposition：The SVD of a matrix[J].College Mathematics Journal，1996，27（1）：2-23.

[17]俞鴻魁，張華平，劉群，等.基于層疊隱馬爾可夫模型的中文命名實(shí)體識(shí)別[J].通信學(xué)報(bào)，2006，27（2）：86-94.