力導(dǎo)向布局算法的數(shù)據(jù)可視化優(yōu)化方法

王藝洋，黃 濤

（1.武漢郵電科學(xué)研究院研究生院，湖北 武漢 430074；2.武漢眾智數(shù)字技術(shù)有限公司，湖北武漢 430074）

在信息時(shí)代的生產(chǎn)生活中，數(shù)據(jù)可視化技術(shù)在 越來(lái)越多的領(lǐng)域有了實(shí)際應(yīng)用場(chǎng)景。數(shù)據(jù)可視化技術(shù)是通過(guò)布局算法，將抽象的數(shù)據(jù)變?yōu)閳D像進(jìn)行展示[1]。數(shù)據(jù)之間清晰的關(guān)聯(lián)關(guān)系，可以增強(qiáng)人們?cè)陂喿x數(shù)據(jù)時(shí)的觀感?？梢暬夹g(shù)可以幫助人們?cè)诨ヂ?lián)網(wǎng)時(shí)代提升對(duì)信息的認(rèn)知程度，結(jié)合人的視覺(jué)和學(xué)習(xí)認(rèn)知能力，提高人們對(duì)信息的挖掘和分析能力，從而提高信息利用率[2-4]。當(dāng)前各類(lèi)可視化技術(shù)都取得了一定的進(jìn)展[5-8]，但隨著各類(lèi)數(shù)據(jù)變得復(fù)雜化和多樣化，可視化算法要考慮更多的影響因素。文中通過(guò)研究多種力布局算法的改進(jìn)方法[9-11]，根據(jù)模擬退火原理，擬采用退火公式，對(duì)節(jié)點(diǎn)偏差與迭代次數(shù)進(jìn)行關(guān)系映射，在力布局算法的基礎(chǔ)上將兩者的關(guān)系映射融入到節(jié)點(diǎn)位置的布局過(guò)程中，實(shí)現(xiàn)對(duì)算法的改進(jìn)，提高可視化性能，降低最小節(jié)點(diǎn)偏差。通過(guò)與傳統(tǒng)力布局算法的對(duì)比進(jìn)行改進(jìn)思想的驗(yàn)證。

1 相關(guān)技術(shù)

1.1 D3.js

D3.js 作為當(dāng)前主流的可視化庫(kù)之一，被很多表格插件所使用[12]。D3.js 可以將任意的數(shù)據(jù)綁定到DOM上，然后在DOM 中完成對(duì)數(shù)據(jù)驅(qū)動(dòng)的轉(zhuǎn)換?？梢栽诳梢暬瘞?kù)的基礎(chǔ)上，使用數(shù)組建立一個(gè)HTML表格，在網(wǎng)頁(yè)中與元素進(jìn)行交互。

將所有功能都涵蓋進(jìn)自身的框架中并不是D3.js的宗旨所在，它解決問(wèn)題的核心手段是通過(guò)將數(shù)據(jù)和DOM 綁定，把數(shù)據(jù)和HTML 結(jié)構(gòu)或者SVG 文檔對(duì)應(yīng)起來(lái)，利用數(shù)據(jù)驅(qū)動(dòng)文檔的變化，打破數(shù)據(jù)展現(xiàn)的局限性。D3.js 依靠海量的函數(shù)進(jìn)行數(shù)據(jù)處理和物理計(jì)算，相較于echarts 等其他主流的可視化工具，D3.js 的功能覆蓋更加廣泛，操作DOM 也更加方便，而且D3.js 處理速度很快，大型數(shù)據(jù)集交互與動(dòng)畫(huà)的動(dòng)態(tài)行為都可以通過(guò)D3.js 來(lái)實(shí)現(xiàn)。

1.2 力導(dǎo)向布局算法

最早的力導(dǎo)向布局相關(guān)算法在1984 年由Peter Dades 提出，算法以自然界中電子之間的直接互相作用為原理[13]。在力導(dǎo)向布局算法中，各節(jié)點(diǎn)和連線的位置是通過(guò)斥力和引力的作用下不斷更新的，在力的作用下節(jié)點(diǎn)經(jīng)過(guò)不斷位移之后趨于平衡，節(jié)點(diǎn)位置逐漸穩(wěn)定，不再發(fā)生相對(duì)位移，能量隨著位移不斷消耗，最終趨于零，以此使各節(jié)點(diǎn)間達(dá)到一種物理狀態(tài)的平衡。

力導(dǎo)向布局算法是繪制一般網(wǎng)狀結(jié)構(gòu)的常用方法[14]。該算法以力導(dǎo)向模型作為基礎(chǔ)，利用圖的結(jié)構(gòu)計(jì)算圖形的層次，而無(wú)需對(duì)上下文信息再進(jìn)行分析處理。力導(dǎo)向繪圖可以用于展示關(guān)系圖的結(jié)點(diǎn)之間的關(guān)系，將結(jié)點(diǎn)分布到畫(huà)布上的合理位置，比如描述企業(yè)之間的關(guān)系、社交網(wǎng)絡(luò)中的人際關(guān)系等[15]。

力導(dǎo)向布局算法中的引力與斥力的計(jì)算公式分別如式（1）和（2）所示：

式（1）中，d為兩節(jié)點(diǎn)之間的笛卡爾距離；K是調(diào)節(jié)全局節(jié)點(diǎn)之間的斥力常量；符號(hào)“-”表示斥力的表征方向。

式（2）中，d同為節(jié)點(diǎn)之間的笛卡爾距離；H為彈簧力的倔強(qiáng)系數(shù)；Li為第i層的默認(rèn)彈簧長(zhǎng)度，且Li/Li+1=I，即第i層和第i+1 層的邊長(zhǎng)比值為一個(gè)固定常數(shù)I。

1.3 模擬退火算法原理

模擬退火算法由Metropolis 提出，1983年，S.Kirkpatrick 等人為了進(jìn)行組合優(yōu)化將其引入到計(jì)算機(jī)領(lǐng)域。模擬退火算法是基于Monte-Carlo 迭代求解策略的一種隨機(jī)尋優(yōu)算法[16]。其思想理論來(lái)自于物理學(xué)中的退火過(guò)程，先將固體加溫至充分高，接著令其徐徐冷卻，在加溫過(guò)程中，固體內(nèi)部粒子的內(nèi)能會(huì)升高，并進(jìn)行無(wú)序運(yùn)動(dòng)，而在冷卻過(guò)程中內(nèi)能減少，粒子運(yùn)動(dòng)趨于有序，最后當(dāng)溫度變?yōu)槠胶鈶B(tài)時(shí)達(dá)到基態(tài)，此時(shí)內(nèi)能最小。模擬退火算法就是從一個(gè)初始的高溫出發(fā)，隨著溫度參數(shù)的下降，利用概率突降特性尋找函數(shù)的最優(yōu)解。文中利用模擬退火的概率性突跳尋求最優(yōu)解的思想，在力布局算法迭代過(guò)程中引入退火公式，使節(jié)點(diǎn)偏差跳出局部最優(yōu)，從而尋找全局最優(yōu)節(jié)點(diǎn)偏差。

2 改進(jìn)的力布局算法

2.1 節(jié)點(diǎn)偏差與迭代關(guān)系映射

在力導(dǎo)向布局算法中，形成的初始布局里節(jié)點(diǎn)位置是隨機(jī)分布的，并在不斷的迭代過(guò)程中，以一定的速度更新節(jié)點(diǎn)坐標(biāo)，并在引力與斥力的不斷作用下，形成最終的布局效果。在對(duì)力導(dǎo)向布局算法的研究中發(fā)現(xiàn)，在節(jié)點(diǎn)數(shù)較少的情況下，迭代停止前，已經(jīng)達(dá)到良好的布局效果；在節(jié)點(diǎn)數(shù)較多的情況下，迭代停止時(shí)還未達(dá)到較好的布局效果，因此如果可以動(dòng)態(tài)地調(diào)整迭代次數(shù)，則對(duì)布局效果可以起到優(yōu)化作用。

文中在遵循布點(diǎn)算法美學(xué)標(biāo)準(zhǔn)的基礎(chǔ)上，采用節(jié)點(diǎn)偏差作為布局效果的評(píng)價(jià)參數(shù)，將節(jié)點(diǎn)偏差與迭代次數(shù)形成關(guān)系映射，整合到力導(dǎo)向布局算法中，在布局過(guò)程中，采用節(jié)點(diǎn)偏差值作為退火參數(shù)決定迭代的進(jìn)行。美學(xué)標(biāo)準(zhǔn)中最佳分布距離和節(jié)點(diǎn)偏差表示分別如式（3）和（4）所示：

式（3）中，Acr 為整個(gè)畫(huà)布的面積，Nnode表示當(dāng)前節(jié)點(diǎn)數(shù)，distance 表示最佳節(jié)點(diǎn)距離。

式（4）中，Dx,i和Dx,i+1分別表示當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的x軸坐標(biāo)，Dy,i和Dy,i+1分別表示當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的y軸坐標(biāo)。

通過(guò)計(jì)算可以將得到的所有節(jié)點(diǎn)之間的節(jié)點(diǎn)偏差組成一個(gè)節(jié)點(diǎn)偏差集合，即d=(d1,2,d1,3,…,d1,i+1,…,di,i+1)，并得到最小節(jié)點(diǎn)偏差dmin。利用模擬退火算法原理對(duì)節(jié)點(diǎn)偏差與迭代次數(shù)進(jìn)行關(guān)系映射，具體公式如式（5）所示：

式（5）中，p表示進(jìn)行迭代的概率，其取值范圍是(0,1)；exp 表示自然指數(shù)；T是模擬退火算法的初始溫度；dmin,new表示當(dāng)次迭代的最小節(jié)點(diǎn)偏差；dmin,old表示上次迭代的最小節(jié)點(diǎn)偏差。

若此次節(jié)點(diǎn)移動(dòng)后的最小節(jié)點(diǎn)偏差優(yōu)于上次，則接受此次移動(dòng)；反之則以一定的概率p接受此次移動(dòng)，且概率p隨著迭代次數(shù)的增加逐漸降低。p的值越小，表明如果進(jìn)行下一次迭代，則出現(xiàn)更小節(jié)點(diǎn)偏差值的概率越低。

2.2 改進(jìn)算法流程描述

改進(jìn)算法的數(shù)據(jù)可視化流程如圖1 所示。

圖1 可視化流程圖

輸入：各節(jié)點(diǎn)初始位置坐標(biāo)、畫(huà)布面積。

輸出：各節(jié)點(diǎn)最終位置坐標(biāo)、數(shù)據(jù)布局圖。

1）對(duì)輸入的各節(jié)點(diǎn)坐標(biāo)數(shù)據(jù)進(jìn)行初步計(jì)算，得到初始化布局，根據(jù)式（3）得到最佳分布距離；

2）通過(guò)力布局算法開(kāi)始迭代，節(jié)點(diǎn)在引力與斥力的作用下，布局位置開(kāi)始改變；

3）每次迭代完成后更新節(jié)點(diǎn)的位置，并且根據(jù)式（4）得到最小節(jié)點(diǎn)偏差；

4）將最小節(jié)點(diǎn)偏差代入式（5）中進(jìn)行迭代概率的計(jì)算；

5）當(dāng)?shù)螖?shù)達(dá)到閾值或式（5）中得到的概率p＜Random(0,1)時(shí)，跳出布局算法，得到最終的數(shù)據(jù)布局圖。迭代次數(shù)閾值設(shè)為500 次。

3 實(shí)驗(yàn)分析

3.1 布局的美學(xué)標(biāo)準(zhǔn)

圖布局就是將當(dāng)前節(jié)點(diǎn)的位置與目標(biāo)節(jié)點(diǎn)通過(guò)連線連接起來(lái)進(jìn)行展示。將復(fù)雜的數(shù)據(jù)形成易于觀察的可視化布局并不簡(jiǎn)單。清晰可觀的展示數(shù)據(jù)和圖的結(jié)構(gòu)，并且展示和操作過(guò)程流暢，是當(dāng)前圖的布局算法研究的重心所在。對(duì)于這些要求，圖布局有一套美學(xué)標(biāo)準(zhǔn)，用來(lái)衡量一個(gè)圖布局算法的可視化效果優(yōu)良，具體有四個(gè)原則。

1）交叉邊線最小原則：過(guò)于繁雜的交叉邊線會(huì)影響圖的清晰度，繪圖時(shí)應(yīng)盡量減少相互交叉邊的數(shù)量；

2）直線原則：邊線應(yīng)該盡量為直線，避免出現(xiàn)曲線、直線共存的現(xiàn)象，同時(shí)單個(gè)節(jié)點(diǎn)的邊線數(shù)盡可能不要超過(guò)節(jié)點(diǎn)數(shù)；

3）對(duì)稱(chēng)性原則：繪制中心節(jié)點(diǎn)網(wǎng)絡(luò)時(shí)，將具有相同結(jié)構(gòu)的子節(jié)點(diǎn)圍繞中心節(jié)點(diǎn)進(jìn)行平衡布局；

4）節(jié)點(diǎn)集中原則：節(jié)點(diǎn)分布不能過(guò)于分散，盡量多個(gè)節(jié)點(diǎn)集中在中心節(jié)點(diǎn)附近。

3.2 實(shí)驗(yàn)結(jié)果和分析

3.2.1 可視化效果對(duì)比

實(shí)驗(yàn)采用D3.js 可視化工具進(jìn)行數(shù)據(jù)可視化的實(shí)現(xiàn)，為了更加清晰地對(duì)可視化效果進(jìn)行對(duì)比，選取的實(shí)驗(yàn)節(jié)點(diǎn)數(shù)量為500，模擬退火初始溫度T設(shè)為畫(huà)布邊長(zhǎng)的一半。傳統(tǒng)力布局算法和改進(jìn)算法的可視化效果分別如圖2 和圖3 所示。

圖2 傳統(tǒng)力導(dǎo)向布局算法可視化效果

圖3 改進(jìn)算法可視化效果

由圖2 可以看出，傳統(tǒng)力導(dǎo)向布局效果相近節(jié)點(diǎn)與節(jié)點(diǎn)之間距離過(guò)近，沒(méi)有完全展開(kāi)，呈現(xiàn)效果不飽滿，多條連線之間存在相互交叉，節(jié)點(diǎn)與連線布局比較雜亂。而在圖3中，中心節(jié)點(diǎn)與子節(jié)點(diǎn)之間連線指向比較清晰，子節(jié)點(diǎn)排列飽滿，呈對(duì)稱(chēng)分布，相互間隔一定距離。改進(jìn)算法后的布局效果有了明顯的提升，大部分節(jié)點(diǎn)與連線都對(duì)稱(chēng)分布，交叉線有明顯減少，對(duì)于各個(gè)節(jié)點(diǎn)之間的關(guān)系有了明確直觀的展示，證明了考慮節(jié)點(diǎn)偏差對(duì)迭代次數(shù)的影響后，布局效果能夠更加符合數(shù)據(jù)可視化的美學(xué)標(biāo)準(zhǔn)。

3.2.2 最小節(jié)點(diǎn)偏差對(duì)比

在對(duì)不同節(jié)點(diǎn)數(shù)的情況下，計(jì)算改進(jìn)力布局算法和傳統(tǒng)力布局算法的最小節(jié)點(diǎn)偏差值，模擬退火初始溫度T為畫(huà)布邊長(zhǎng)的一半，對(duì)比實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 最小節(jié)點(diǎn)偏差對(duì)比

由圖4 可知，傳統(tǒng)力布局算法和改進(jìn)力布局算法的最小節(jié)點(diǎn)偏差都隨著節(jié)點(diǎn)數(shù)的增加而降低，并且改進(jìn)算法的最小節(jié)點(diǎn)偏差均小于傳統(tǒng)力布局算法的最小節(jié)點(diǎn)偏差，證明了改進(jìn)算法相比傳統(tǒng)力布局算法的節(jié)點(diǎn)偏差更小，更加符合美學(xué)標(biāo)準(zhǔn)，也證明了利用節(jié)點(diǎn)偏差-迭代次數(shù)關(guān)系映射來(lái)控制數(shù)據(jù)可視化過(guò)程能夠有效提高布局效果。

4 結(jié)論

力布局算法的優(yōu)化方法基于傳統(tǒng)力布局算法的可視化效果問(wèn)題所在，利用布局算法的美學(xué)標(biāo)準(zhǔn)來(lái)對(duì)節(jié)點(diǎn)偏差進(jìn)行計(jì)算，在迭代過(guò)程中不斷進(jìn)行節(jié)點(diǎn)偏差的計(jì)算，并結(jié)合退火公式，使其以一定的概率跳出當(dāng)前的循環(huán)并輸出布局的最優(yōu)解。經(jīng)過(guò)與傳統(tǒng)力布局算法的對(duì)比實(shí)驗(yàn)表明，改進(jìn)算法的可視化效果有明顯的提升，并且節(jié)點(diǎn)偏差值更小，布局更符合美學(xué)標(biāo)準(zhǔn)，印證了節(jié)點(diǎn)偏差值可以有效反映出可視化布局的效果，利用節(jié)點(diǎn)偏差來(lái)控制迭代的進(jìn)行可以對(duì)力布局算法進(jìn)行優(yōu)化改進(jìn)。

由于迭代過(guò)程中加入了節(jié)點(diǎn)偏差的計(jì)算和節(jié)點(diǎn)初始位置的隨機(jī)性，改進(jìn)算法的執(zhí)行時(shí)間相對(duì)來(lái)說(shuō)有所增加且實(shí)驗(yàn)結(jié)果可能有所偏差，因此在后續(xù)的研究工作中需要對(duì)以上不足進(jìn)行改進(jìn)。