劉　真，周文暉

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

?

多元關(guān)系的超圖可視表達(dá)與分析

劉真，周文暉

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

摘要：蓬勃發(fā)展的社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)、關(guān)系型數(shù)據(jù)庫(kù)和生物醫(yī)學(xué)等應(yīng)用領(lǐng)域帶來海量數(shù)據(jù)，其中數(shù)據(jù)對(duì)象之間存在錯(cuò)綜復(fù)雜的關(guān)聯(lián).傳統(tǒng)信息可視化領(lǐng)域表達(dá)二元關(guān)系的圖已經(jīng)不能表達(dá)這些復(fù)雜關(guān)聯(lián)，越來越多研究發(fā)現(xiàn)表達(dá)多元關(guān)系的超圖能更好地挖掘信息中隱藏的內(nèi)在聯(lián)系和模式.針對(duì)多元實(shí)體關(guān)系，提出兩種超圖可視化方法：海塞圖和關(guān)聯(lián)矩陣.其中超圖海塞圖方法通過在超圖交閉半格上構(gòu)建層次化海塞圖進(jìn)行可視化；超圖矩陣可視化將超圖表示成關(guān)聯(lián)矩陣、超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣.通過從Medline在線數(shù)據(jù)庫(kù)上挖掘多元關(guān)系的肺癌超圖數(shù)據(jù)分析和驗(yàn)證上述方法的有效性.

關(guān)鍵詞：超圖；交閉半格；海賽圖；關(guān)聯(lián)矩陣

0引言

基于超圖的多元關(guān)系可視化研究在國(guó)際上尚處于起步階段.現(xiàn)有的研究工作在表達(dá)超圖時(shí)，通常都把頂點(diǎn)表達(dá)為平面中的頂點(diǎn)或者區(qū)域，例如斯坦納樹、平面中的閉曲線、細(xì)分面片和頂點(diǎn)等[4].超圖表示方法包括文氏圖、Zykov、二分圖和細(xì)分畫法等[4-5].文獻(xiàn)[6]研究固定圖布局的單超邊嵌入方法，主要給出在避免頂點(diǎn)遮擋情況下，利用能量方法對(duì)超邊進(jìn)行路徑選擇和布局.Basak等研究超圖可視化技術(shù)線集合(LineSet)，線集合是一個(gè)連接所有的集合元素的曲線[7].他們利用線集合分別展示在地圖上顯示飯店的目錄和社交網(wǎng)絡(luò)的社區(qū).現(xiàn)有的超圖可視化方法主要存在以下問題：第一，大多數(shù)只簡(jiǎn)單展示超邊和頂點(diǎn)包含關(guān)系，沒有展示可能存在的各種潛在信息；第二，超圖規(guī)模的增加導(dǎo)致視覺復(fù)雜度高和易讀性差；第三，普遍缺乏用戶交互.本文提出了海塞圖可視化和矩陣可視化兩種多元關(guān)系的超圖的可視設(shè)計(jì)與交互方法，并通過肺癌實(shí)例數(shù)據(jù)對(duì)方法進(jìn)行驗(yàn)證.

1超圖的海塞圖可視化

已有超圖可視化技術(shù)大多都參照?qǐng)D(Graph)可視化方法，可視化超圖的拓?fù)湫再|(zhì)或者幾何結(jié)構(gòu)，很少研究多元關(guān)系的交叉重合以及潛在關(guān)系.超圖中超邊之間的交集代表它們的共同頂點(diǎn)，這些共同頂點(diǎn)在超圖往往起著關(guān)鍵作用.海塞圖[8]是一種有限偏序集傳遞約簡(jiǎn)的表達(dá)方式.每一個(gè)有限偏序集都可以用海塞圖來簡(jiǎn)潔直觀的表達(dá)其中的關(guān)系.海塞圖中的每個(gè)頂點(diǎn)代表偏序集中的一個(gè)元素，根據(jù)元素之間關(guān)系將元素排列在不同的層次上，并且僅在有直接關(guān)系的元素之間連線.所謂有直接關(guān)系是指不存在第三個(gè)元素，使得原來兩個(gè)元素之間的關(guān)系可以通過第三個(gè)元素進(jìn)行傳遞.文獻(xiàn)[9]基于海塞圖解決社交網(wǎng)絡(luò)照片的標(biāo)注、組織以及可視化問題.該方法中用海塞圖作為標(biāo)注過照片的結(jié)構(gòu)，通過在標(biāo)注的過程中直接識(shí)別新照片中的人物，將新照片拖到海塞圖中找到包含相應(yīng)人物的照片上完成標(biāo)注.文獻(xiàn)[10]利用海塞圖非常客觀和直觀地實(shí)現(xiàn)2008年奧運(yùn)會(huì)前十名國(guó)家的排名.本文超圖海賽圖可視化是對(duì)超圖的多元關(guān)系，特別關(guān)系的交叉重疊、頂點(diǎn)共同出現(xiàn)以及關(guān)鍵頂點(diǎn)探索的有效方法.

1.1交閉半格

超邊是頂點(diǎn)的集合，對(duì)超邊兩兩進(jìn)行求交運(yùn)算可以得到新的頂點(diǎn)集合.對(duì)這些新產(chǎn)生的頂點(diǎn)集合和超邊進(jìn)行迭代求交運(yùn)算，最后可以得到交閉的結(jié)構(gòu).它是一個(gè)包含關(guān)系的偏序集，稱為超圖的交閉半格.下文將詳細(xì)介紹用海塞圖來可視化超圖的交閉半格.

1.2可視表達(dá)

如圖1(a)所示，海塞圖可視化是一種采用弧形的彩虹布局的層次化可視設(shè)計(jì).概覽視圖分為超邊層、新關(guān)系層和關(guān)鍵頂點(diǎn)層，其中超邊層表示超圖中的超邊.3個(gè)層次用橢圓、棱形或者矩形表示頂點(diǎn)，連線表示頂點(diǎn)之間的直接包含關(guān)系并且根據(jù)超邊規(guī)?；蛘哌B線數(shù)編碼其顏色和寬度.新關(guān)系層代表交閉半格中通過求交得到的新的頂點(diǎn)集合.因?yàn)樾玛P(guān)系之間也存在交集，所以新關(guān)系層一般會(huì)包含多個(gè)等級(jí)，從上到下表示越來越緊密的新關(guān)系.根據(jù)新關(guān)系的規(guī)模、等級(jí)以及關(guān)聯(lián)程度進(jìn)行大小或者顏色的編碼，直觀展示其大小、緊密程度和其在超圖中的重要性.關(guān)鍵頂點(diǎn)層是指交閉半格中求交得到的單個(gè)頂點(diǎn)，它表示出現(xiàn)在超邊里的重要頂點(diǎn).關(guān)鍵頂點(diǎn)層位于可視化的最下方，對(duì)超圖的連通性有重要影響.根據(jù)其出現(xiàn)的次數(shù)進(jìn)行顏色或者大小的編碼，以區(qū)分它們?cè)诔瑘D中的重要性.

1.3交互設(shè)計(jì)

海塞圖可視化的交互基于概覽加細(xì)節(jié)的原則進(jìn)行設(shè)計(jì)，并且支持不同層次可視元素的選擇、拖拽、高亮等操作以及整個(gè)概覽視圖的縮放、平移等.超圖海塞圖可視化示意圖如圖1所示.如圖1中(b)、(c)和(d)所示，可以對(duì)概覽視圖中的元素進(jìn)行3種類型的交互.交互1是對(duì)超邊ABCD的交互，概覽視圖高亮它關(guān)聯(lián)的關(guān)系網(wǎng)絡(luò)，圖1(b)顯示這個(gè)關(guān)系網(wǎng)絡(luò)的詳細(xì)信息.交互2是對(duì)超邊ABCD引出的新關(guān)系BCD的進(jìn)一步交互，概覽視圖中也會(huì)高亮出其關(guān)聯(lián)的關(guān)系網(wǎng)絡(luò).從圖1(d)可以看出，它是由超邊ABCD和BCDE求交而得，BCD和其它新關(guān)系衍生出新關(guān)系BC和CD.交互3是對(duì)關(guān)鍵頂點(diǎn)C的交互.同樣概覽視圖高亮出該頂點(diǎn)關(guān)聯(lián)的局部海塞圖結(jié)構(gòu)，圖1(c)詳細(xì)顯示局部信息.這種交互方式不僅詳細(xì)展示內(nèi)容信息，而且很好地展示超圖中元素關(guān)系的結(jié)構(gòu)信息.

2超圖的關(guān)聯(lián)矩陣可視化

上述超圖的海塞圖可視化方法要求數(shù)據(jù)規(guī)模不能太大，因此本節(jié)提出超圖的矩陣可視化方法.矩陣可視化不僅能從宏觀上可視化超圖的關(guān)系模式，還能適合于更大規(guī)模的超圖.

2.1矩陣描述

類似于圖的鄰接矩陣，每個(gè)超圖都有一個(gè)關(guān)聯(lián)矩陣.超圖關(guān)聯(lián)矩陣的每行代表一個(gè)超邊，每列代表一個(gè)頂點(diǎn)(反之亦可).如果某個(gè)超邊包含某個(gè)頂點(diǎn)，則在該超邊所在行和頂點(diǎn)所在列交點(diǎn)處的數(shù)值為1，否則為0.和圖的鄰接矩陣不同的是，超圖的關(guān)聯(lián)矩陣一般情況下不是對(duì)稱矩陣，并且大多數(shù)情況下都不是方陣.文獻(xiàn)[11]提到可以對(duì)統(tǒng)計(jì)圖表的樣本和屬性分別進(jìn)行相關(guān)性分析.如圖2所示，可以對(duì)超圖關(guān)聯(lián)矩陣的行向量和列向量分別兩兩相關(guān)性得到超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣.

圖1　超圖海塞圖可視化示意圖

圖2　矩陣表示

2.2可視表達(dá)

如圖3所示，矩陣可視化包括3個(gè)矩陣、統(tǒng)計(jì)圖和交互細(xì)節(jié)的展示.這3個(gè)矩陣分別是圖2(a)中標(biāo)出的超圖關(guān)聯(lián)矩陣、超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣.可視化布局要保證超圖關(guān)聯(lián)矩陣的行和超邊關(guān)系矩陣的行對(duì)齊，超圖關(guān)聯(lián)矩陣的列和頂點(diǎn)關(guān)系矩陣的列對(duì)齊.如果3個(gè)矩陣數(shù)值相差較大，使用不同的顏色庫(kù)編碼這3個(gè)矩陣數(shù)值.超圖關(guān)聯(lián)矩陣是1個(gè)二值矩陣，它展示超邊和頂點(diǎn)之間的包含從屬關(guān)系.超邊關(guān)系矩陣描述的是超邊之間的關(guān)系，根據(jù)顏色編碼其數(shù)值大小，顏色越深代表相應(yīng)超邊之間的相似性越高.頂點(diǎn)關(guān)系矩陣描述的是頂點(diǎn)之間的關(guān)系.根據(jù)顏色來編碼其數(shù)值大小，顏色越深代表相應(yīng)頂點(diǎn)之間的常見性越高.超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣都是對(duì)稱矩陣，可以使用現(xiàn)有的重排算法對(duì)其進(jìn)行矩陣重排[11].

圖3　超圖矩陣可視化示意圖

2.3交互設(shè)計(jì)

超圖矩陣可視化的交互主要包括概覽加細(xì)節(jié)的自頂向下的交互方式，具體如下：

1)對(duì)超圖關(guān)聯(lián)矩陣的元素進(jìn)行交互(如圖3(b)、(d)交互2).超圖關(guān)聯(lián)矩陣高亮出該元素所關(guān)聯(lián)的超邊(行)和頂點(diǎn)(列)，并且超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣也相應(yīng)的高亮出相應(yīng)的行和列，并且細(xì)節(jié)視圖顯示關(guān)注的超邊和頂點(diǎn)信息.

2)對(duì)超邊關(guān)系矩陣上元素進(jìn)行交互(如圖3(b)、(d)交互3).超邊關(guān)系矩陣高亮出該元素所關(guān)聯(lián)的行和列，超圖關(guān)聯(lián)矩陣中也高亮出相應(yīng)的兩個(gè)超邊行并且細(xì)節(jié)視圖顯示兩個(gè)超邊的詳細(xì)信息.

3)對(duì)頂點(diǎn)關(guān)系矩陣的元素進(jìn)行交互(如圖3(b)、(d)交互1).頂點(diǎn)關(guān)系矩陣高亮出該元素所關(guān)聯(lián)的行和列，超圖關(guān)聯(lián)矩陣中也高亮出相應(yīng)的兩個(gè)頂點(diǎn)列并且細(xì)節(jié)視圖顯示兩個(gè)頂點(diǎn)的信息.

4)矩陣重排交互.如圖3(a)、(b)選擇交互選項(xiàng)中的矩陣重排選項(xiàng)，可以分別對(duì)超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣用不同的算法完成重排，超圖關(guān)聯(lián)矩陣的行和列會(huì)相應(yīng)地同步重排.

5)統(tǒng)計(jì)圖交互.如圖3(c)選擇交互選項(xiàng)中的統(tǒng)計(jì)圖選項(xiàng)，可以分別對(duì)統(tǒng)計(jì)超邊和頂點(diǎn)并且統(tǒng)計(jì)圖會(huì)隨著超圖關(guān)聯(lián)矩陣的重排而同步變化.

3案例分析

文獻(xiàn)[1]介紹從Medline在線數(shù)據(jù)庫(kù)上挖掘多元關(guān)系的方法，并給出關(guān)于肺癌的挖掘結(jié)果.結(jié)果包含168個(gè)三元關(guān)系，包括疾病、器官、藥物、化學(xué)物質(zhì)和路徑等生物實(shí)體之間的關(guān)聯(lián)，并且每個(gè)關(guān)系都帶有權(quán)重.如果把每個(gè)三元關(guān)系當(dāng)做一個(gè)超邊，那么這個(gè)的挖掘結(jié)果就是一個(gè)關(guān)于肺癌的超圖數(shù)據(jù).本文對(duì)該數(shù)據(jù)進(jìn)行如下可視分析：

1)為了對(duì)這些數(shù)據(jù)中的重點(diǎn)關(guān)系進(jìn)行分析，本文過濾出了30個(gè)最重要的關(guān)系.

2)如圖4(a)所示，首先使用矩陣可視化從宏觀上對(duì)其進(jìn)行展示.我們可以發(fā)現(xiàn)經(jīng)過重排的超邊關(guān)系矩陣和頂點(diǎn)關(guān)系矩陣中均存在3個(gè)明顯分塊.如圖4(a)、(c)所示，通過對(duì)超圖關(guān)聯(lián)矩陣中的元素mlh1+msh2+p53: mlh1(mlh1，msh2和p53均為生物實(shí)體，mlh1+msh2+p53為三元關(guān)系，下文類似)進(jìn)行交互以及統(tǒng)計(jì)圖分析，發(fā)現(xiàn)頂點(diǎn)mlh1在這個(gè)超圖中占據(jù)著比較重要的位置.

3)接著使用海塞圖對(duì)數(shù)據(jù)進(jìn)行可視化.如圖4(a)、(b)對(duì)關(guān)鍵頂點(diǎn)mlh1以及5(d)多元關(guān)系mlh1+msh2+p53的交互，可以發(fā)現(xiàn)mlh1所關(guān)聯(lián)的關(guān)系網(wǎng)絡(luò)占據(jù)半個(gè)超圖網(wǎng)絡(luò)，mlh1+msh2+p53包含不出現(xiàn)在新關(guān)系層中的關(guān)鍵頂點(diǎn)p53等.

文獻(xiàn)[12]將多元關(guān)系抽象為頂點(diǎn)，對(duì)異構(gòu)夠的頂點(diǎn)數(shù)據(jù)進(jìn)行整體力引導(dǎo)，將頂點(diǎn)分散到整個(gè)布局平面上減少交叉重疊.它還通過一系列交互操作探索骨生物數(shù)據(jù)之間的直接和潛在關(guān)系.與其利用頂點(diǎn)鏈接法表示超圖的鏡像點(diǎn)探索方式相對(duì)比，本文能夠通過不斷的交互和可視感知，用戶對(duì)超圖數(shù)據(jù)中的各種關(guān)系有一個(gè)清晰全面的認(rèn)識(shí).實(shí)驗(yàn)結(jié)果證明海塞圖和矩陣方法相結(jié)合的方法不但挖掘出更多生物實(shí)體之間的關(guān)聯(lián)，而且可以發(fā)現(xiàn)其中的關(guān)鍵頂點(diǎn).因此該方法可以很好地幫助生物學(xué)家分析這些關(guān)系，并對(duì)假設(shè)進(jìn)行直觀的檢驗(yàn).

4總結(jié)與展望

本文對(duì)表達(dá)多元關(guān)系的超圖數(shù)據(jù)可視化和分析進(jìn)行探索.但是隨著超圖規(guī)模的增加，視覺復(fù)雜度和易讀性較差問題是面臨的挑戰(zhàn).超圖的應(yīng)用領(lǐng)域廣泛，如何賦予超圖在應(yīng)用領(lǐng)域的實(shí)際意義也是一個(gè)值得進(jìn)一步研究的問題.無論是實(shí)體—數(shù)據(jù)關(guān)系的變換還是映射方式，或者結(jié)點(diǎn)—超邊的布局算法，亦或者是超圖的圖簡(jiǎn)化算法和交互，以及超圖數(shù)據(jù)的可視分析都是將來超圖的研究方向.將來的工作中本文作者將面向我國(guó)的發(fā)展需求，提出在此方面繼續(xù)開展深入研究.通過提供有效的大規(guī)模超圖數(shù)據(jù)可視化方法，能夠面向領(lǐng)域應(yīng)用提供強(qiáng)大的可視分析工具，提高人民對(duì)數(shù)據(jù)的理解和分析能力，對(duì)相關(guān)科學(xué)研究、工程實(shí)踐和社會(huì)生活都有積極的意義.

參考文獻(xiàn)

[1]MUKHOPADHYAY S, PALAKAL M, MADDU K. Multi-way association extraction and visualization from biological text documents using hyper-graphs: applications to genetic association studies for diseases[J]. Artificial intelligence in medicine,2010,49(3):145-154.

[2]范偉,李曉明.物聯(lián)網(wǎng)數(shù)據(jù)特性對(duì)建模和數(shù)據(jù)挖掘的挑戰(zhàn)[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊,2010,6(9):38-43.

[3]BERGE C. Hypergraphs [M]. Amsterdam: North Holland,1989:1-2.

[4]KAUFAMNN M, KREVELD M V, SPECKMANN B. Subdivision Drawings of Hypergraphs[M]// Graph Drawing. Berlin: Springer Berlin Heidelberg,2008:396-407.

[5]BRANDES U, CORNELSEN S, PAMPEL B, et al. Path-based Supports for Hypergraphs [J]. Journal of Discrete Algorithms,2012,14:248-261.

[6]JUNGHANS M.Visualization of Hyperedges in Fixed Graph Layouts[D].Cottbus: Brandenburg University of Technology Cottbus,2008:29-54.

[7]ALPER B, RICHE N H, RAMOS G, et al. Design study of linesets, a novel set visualization technique[J]. Visualization and Computer Graphics, IEEE Transactions on,2011,17(12):2259-2267.

[8]GANTER B, WILLE R. Formal Concept Analysis：Mathematical Foundations[M]. Berlin: Springer,1999:1-10.

[9]CRAMPES M, OLIVEIRA-KUMAR D, RANEZ S, et al. Visualizing social photos on a hasse diagram for eliciting relations and indexing new photos[J]. Visualization and Computer Graphics, IEEE Transactions on,2009,15(6):985-992.

[10]SIMON T. Hasse diagram of the 2008 Olympic medal table [EB/OL]. [2015-12-04]. http://tartarus.org/simon/2008-olympics-hasse/.

[11]CHEN C H.Generalized association plots: information visualization via iteratively generated correlation matrices [J]. Statistica Sinica,2002,12(1):7-29.

[12]夏菁,劉真,胡越琦,等.基于超圖的骨生物數(shù)據(jù)可視化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011,23(12):2040-2045.

DOI：10.13954/j.cnki.hdu.2016.03.012

收稿日期：2016-02-19

基金項(xiàng)目：浙江省自然科學(xué)基金資助項(xiàng)目(LQ12F02003)

作者簡(jiǎn)介：劉真(1977-)，女，山東泰安人，講師，信息可視化與可視分析.

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2016)03-0057-06

Visualizing and Analyzing Multivariate Data Relationship Based on Hypergraph

LIU Zhen, ZHOU Wenhui

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：The vigorous development of social network, internet of things, relational database and biomedical application field has brought huge amounts of data, which has complex relationship with each other. Traditional information visualization can’t express these complex relationships through binary relation graph. More and more research has found that multi-relational hypergraph expression can mine information hidden in the inherent relation and model better. For multivariate entity relationship, this paper presents mainly two hypergraph visualization methods: Hasse diagram and matrix. We construct and visualize hierarchical Hasse diagram based on intersection closure semi lattice of hypergraph. Moreover, we extend hypergraph incidence matrix to hyperedge relation matrix and node relation matrix to visualize various relations in a moderate size hypergraph. Finally experiment results demonstrate that our method is efficient through analyzing the multivariate relation of the lung cancer hypergraph data from Medline online database.

Key words：hypergraph; intersection closure semi lattice; Hasse diagram; incidence matrix