李存燕

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

0 引言

分類數(shù)據(jù)是取值不連貫、沒(méi)有次序關(guān)系的數(shù)據(jù)，屬于統(tǒng)計(jì)數(shù)據(jù)的一種，可以反映事物的類別，例如人屬于一種分類數(shù)據(jù)，可以按照性別分為男、女兩類。對(duì)分類數(shù)據(jù)進(jìn)行預(yù)處理，例如排序，聚類等可以改善可視化效果，用來(lái)確定相同屬性的相似之處和不同屬性之間的關(guān)系。

可視化技術(shù)對(duì)大型多維數(shù)據(jù)集的分析和探索變得越來(lái)越重要[1-2]。雖然大量的工作已經(jīng)解決了數(shù)字?jǐn)?shù)據(jù)的可視化問(wèn)題，但是許多領(lǐng)域都需要對(duì)大量的分類數(shù)據(jù)進(jìn)行可視化。目前，研究者已經(jīng)針對(duì)多個(gè)領(lǐng)域的數(shù)據(jù)進(jìn)行了可視化技術(shù)的研究。例如人口普查數(shù)據(jù)中的城市名稱和本文研究對(duì)象網(wǎng)絡(luò)管理數(shù)據(jù)中的告警名稱、產(chǎn)生告警設(shè)備編號(hào)等，只是與數(shù)值數(shù)據(jù)不同的是，分類值沒(méi)有順序。常用的可視化技術(shù)例如散點(diǎn)圖和平行坐標(biāo)圖等，分類值需要映射到坐標(biāo)軸上（例如產(chǎn)生告警設(shè)備編號(hào)），處理后按照一定規(guī)則排序的數(shù)據(jù)可以極大地提高可視化的質(zhì)量。

1 排序分類數(shù)據(jù)的算法

排序分類數(shù)據(jù)的算法分為三個(gè)步驟：

第一步，使分類數(shù)據(jù)形成自然聚類，這個(gè)階段需要使用領(lǐng)域知識(shí)進(jìn)行分組，例如將接近同樣的時(shí)間發(fā)出相似事件的設(shè)備作為一組。這樣構(gòu)造的一個(gè)重要含義是使得一個(gè)分類值可能屬于多個(gè)分組。

第二步，給第一步發(fā)現(xiàn)的聚類排序。這應(yīng)該由最小化沖突，或者最大化的解決潛在沖突來(lái)完成。這個(gè)優(yōu)化問(wèn)題能夠更進(jìn)一步的轉(zhuǎn)化為一個(gè)圖形問(wèn)題。例如聚類 C1 包含 D1，D3，D4，D5，D6 六個(gè)主機(jī)，C2 包含D1，D2，D3，D7 四個(gè)主機(jī)，C3 包含 D1，D4，D5，D8 四個(gè)主機(jī)，則C1和C2沖突的數(shù)量為2（D1，D3），C1和C3沖突的數(shù)量為3（D1，D4，D5）,C2和C3沖突的數(shù)量為 1（D1）。如圖1所示，在這張圖中，節(jié)點(diǎn)代表聚類，權(quán)重說(shuō)明聚類間潛在沖突的數(shù)量。聚類排序?yàn)榱俗畲蠡慕鉀Q潛在沖突，找到一個(gè)路徑恰好遍歷每個(gè)節(jié)點(diǎn)并最大化遍歷弧的總和，是一樣的。這是一個(gè)Hamilton[3]路徑問(wèn)題，一個(gè)完全NP問(wèn)題，有很多啟發(fā)式的算法被用于解決這個(gè)問(wèn)題，我們用一個(gè)簡(jiǎn)單的貪心算法。

第三步，給每個(gè)聚類的主機(jī)排序。這是直接希望排序相鄰聚類的分類值來(lái)消除所有兩個(gè)聚類間的潛在的沖突。

算法的假設(shè)條件為：排序分類數(shù)據(jù)能夠改善可視化的效果，以至于能夠更好的研究分析大型、復(fù)雜的數(shù)據(jù)。

●算法輸入：一個(gè)告警數(shù)據(jù)（Excel）

●算法的主要步驟：

圖2 算法流程

●算法輸出：用來(lái)構(gòu)造Y軸的設(shè)備號(hào)的排序

●平行坐標(biāo)軸排序分類數(shù)據(jù)的算法主要思想

平行坐標(biāo)軸排序分類數(shù)據(jù)的算法的主要思想繼承了散點(diǎn)圖排序分類數(shù)據(jù)算法的主要思想。除了第一步不同外，兩個(gè)算法的思想跟步驟都基本相同。平行坐標(biāo)軸排序分類數(shù)據(jù)的第一步是把基于兩個(gè)值的關(guān)聯(lián)規(guī)則聚類成一個(gè)屬性。例如，A,B主機(jī)都發(fā)射了相同的事件類型，則A,B主機(jī)被聚為一類。這種方法一個(gè)主機(jī)也可能同時(shí)屬于多個(gè)聚類。

2 可視化

數(shù)據(jù)的可視化是展示實(shí)驗(yàn)結(jié)果的最后一步，它負(fù)責(zé)呈現(xiàn)工作效果、是與客戶交流的關(guān)鍵[4]。為了銜接項(xiàng)目組成員在前面所做的工作，我們的任務(wù)是尋找合適的可視化工具，借此分別用散點(diǎn)圖和平行坐標(biāo)圖來(lái)展示原始數(shù)據(jù)與通過(guò)算法分組排序后的數(shù)據(jù)。

通過(guò)調(diào)研，發(fā)現(xiàn)大部分工具功能缺乏，例如魔方，無(wú)法進(jìn)行平行坐標(biāo)圖的繪制；一部分工具例如raw只能支持在線進(jìn)行可視化，無(wú)法滿足可視化要求；一部分工具比如iCharts，是需要腳本語(yǔ)言進(jìn)行調(diào)用，將其嵌入到網(wǎng)站開(kāi)發(fā)代碼中。通過(guò)比較，選擇Tableau和Xdat對(duì)實(shí)驗(yàn)數(shù)據(jù)結(jié)果進(jìn)行可視化。Tableau是用于畫散點(diǎn)圖的工具，十分靈活，可視化圖案美觀清晰，能夠自主調(diào)節(jié)X軸和Y軸順序。Xdat是用于畫平行坐標(biāo)圖的工具，它是個(gè)開(kāi)源工具，使用簡(jiǎn)單。缺點(diǎn)是不能自主調(diào)節(jié)X軸和Y軸順序。

散點(diǎn)圖和平行坐標(biāo)圖的可視化流程如圖3所示。

圖3 散點(diǎn)圖和平行坐標(biāo)圖的可視化流程

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

（1）實(shí)驗(yàn)?zāi)繕?biāo)

驗(yàn)證排序分類數(shù)據(jù)改善可視化效果。

（2）實(shí)驗(yàn)對(duì)象（網(wǎng)絡(luò)和數(shù)據(jù)仿真）

實(shí)驗(yàn)對(duì)象為根據(jù)數(shù)據(jù)描述制造的仿真數(shù)據(jù)，部分?jǐn)?shù)據(jù)如表1所示：

表1 部分仿真數(shù)據(jù)

（3）實(shí)驗(yàn)預(yù)期結(jié)果

對(duì)仿真數(shù)據(jù)進(jìn)行排序處理后的可視化效果明顯優(yōu)于未進(jìn)行排序處理前的可視化效果，①找到某個(gè)屬性中相同值的分組；②找到不同屬性值之間的關(guān)系。

（4）實(shí)驗(yàn)步驟設(shè)計(jì)

第一步，構(gòu)造分類值的自然聚類，實(shí)現(xiàn)步驟如下：

每臺(tái)設(shè)備需要配備3人及1臺(tái)運(yùn)輸切縫用水三輪車，每天切縫80m，折合成本5.75元/m。通過(guò)對(duì)比分析節(jié)省總成本38.88萬(wàn)元，速度快2.5倍。

①讀取Excel實(shí)驗(yàn)數(shù)據(jù)

②按照時(shí)間段給數(shù)據(jù)分組，例如6秒內(nèi)的數(shù)據(jù)分為一個(gè)組

>一共有幾個(gè)分組（幾個(gè)節(jié)點(diǎn)）

>每個(gè)分組里面的主機(jī)號(hào)（重復(fù)的忽略）

>根據(jù)節(jié)點(diǎn)兩兩之間重復(fù)的主機(jī)號(hào)，確定權(quán)重

關(guān)鍵代碼如下：

//獲取指定的兩個(gè)參數(shù)之間的權(quán)重

③列出每個(gè)節(jié)點(diǎn)與其他每個(gè)節(jié)點(diǎn)的權(quán)重，輸出矩陣

利用Hamilton算法寫出程序，將矩陣輸入后得到聚類的排序

第三步，給每個(gè)聚類內(nèi)部的主機(jī)排序[5]，希望可以消除兩個(gè)聚類間的潛在沖突，實(shí)現(xiàn)步驟如下：

h1,h2為自然聚類得到的分組 a1,2為h1，h2中相同主機(jī)號(hào)的集合

a）對(duì)h1-a1,2中的值進(jìn)行排序，使其序列處于h2中這些對(duì)應(yīng)值之前

b）對(duì)h2-a1,2中的絕對(duì)值值進(jìn)行排序，使其序列處于h2中對(duì)應(yīng)值之后

c）在h2-a1,2和h1-a1,2之間選定a1,2的位置

d）用h2-a1,2和h1-a1,2，絕對(duì)值循環(huán)排列

關(guān)鍵代碼如下：

（5）實(shí)驗(yàn)中間結(jié)果展示

經(jīng)過(guò)編碼測(cè)試，排序分類數(shù)據(jù)的結(jié)果如下圖所示：

第一步，分類值自然聚類的實(shí)驗(yàn)結(jié)果如圖4所示：

圖4 分類值得自然聚類結(jié)果

第二步，給第一步得到的自然聚類排序的結(jié)果如圖5所示：

圖5 對(duì)自然聚類排序的結(jié)果

第三步：給每個(gè)聚類內(nèi)部的主機(jī)排序的結(jié)果如圖6所示：

圖6 聚類內(nèi)部的主機(jī)排序的結(jié)果

（6）可視化效果

對(duì)分類數(shù)據(jù)排好序后，使用畫散點(diǎn)圖的工具Tab?leau，按照分類結(jié)果調(diào)節(jié)Y軸，然后倒入仿真數(shù)據(jù)得到可視化結(jié)果，如下圖所示：

●散點(diǎn)圖繪制實(shí)例如圖7和8所示。

圖7 排序前的可視化圖

4 可視化結(jié)果分析

觀察實(shí)驗(yàn)得到的排序前后的可視化效果圖，發(fā)現(xiàn)經(jīng)過(guò)處理后平行坐標(biāo)軸的可視化效果更佳，達(dá)到了預(yù)期找到不同屬性值之間的關(guān)系的效果。從圖9處理后的平行坐標(biāo)軸可視化圖可以明顯觀察到大多數(shù)other類的告警都是由設(shè)備D1產(chǎn)生的，error7_alarm3到er?ror7_alarm48的告警基本都是由設(shè)備D9產(chǎn)生的等，該結(jié)果可用于告警預(yù)測(cè)，或者當(dāng)網(wǎng)絡(luò)發(fā)生告警時(shí)進(jìn)行根因分析、定位等。

圖8 排序后的可視化圖

●平行坐標(biāo)軸繪制實(shí)例如圖9所示：

圖9 處理前的可視化圖

圖10 處理后的可視化圖

散點(diǎn)圖的可視化效果改善不夠明顯，分析有如下原因：①實(shí)驗(yàn)使用的是根據(jù)數(shù)據(jù)描述制造的仿真數(shù)據(jù)，數(shù)據(jù)本身相當(dāng)于經(jīng)過(guò)了預(yù)處理后的數(shù)據(jù)，所示實(shí)驗(yàn)結(jié)果不理想；②實(shí)驗(yàn)數(shù)據(jù)量太少，改善效果不夠明顯。下一步考慮采取增大數(shù)據(jù)量或者采用真實(shí)數(shù)據(jù)等方法，以期獲得更優(yōu)的實(shí)驗(yàn)效果。

參考文獻(xiàn)：

[1]Ahlberg C,Wistrand E.IVEE:an Information Visualization and Exploration Environment[M].CiteSeer,1995.

[2]Ankerst M,Berchtold S,Keim D A.Similarity Clustering of Dimensions for an Enhanced Visualization of Multidimensional Data[C].Information Visualization,1998.Proceedings.IEEE Symposium on.IEEE,1998:52-60,153.

[3]蔡延光,張新政,錢積新,孫優(yōu)賢.邊賦權(quán)森林ω-路劃分的 O（n）算法[J].軟件學(xué)報(bào),2003（05）:897-903.

[4]沈漢威,張小龍,陳為,袁曉如,王文成.可視化及可視分析專題前言[J].軟件學(xué)報(bào),2016,27（05）:1059-1060.

[5]Ma S,Hellerstein J L.Ordering Categorical Data to Improve Visualization[J].Proceedings of the IEEE Information Visualization Symposium Late Breaking Hot Topics,1999.