SVG中數(shù)據(jù)挖掘與應(yīng)用

陳少英

（廈門海洋職業(yè)技術(shù)學(xué)院 福建省廈門市 361012）

SVG 是由W3C 組織發(fā)布的一種基于XML 的二維矢量圖形和矢量點(diǎn)陣混合圖形的可擴(kuò)展標(biāo)記語言。其具有下載瀏覽速度快、動(dòng)態(tài)、開放、便捷的圖形定位與檢索、良好的可交互性等優(yōu)點(diǎn)，使其能更適用于不同系統(tǒng)間的圖形系統(tǒng)交換。

在SVG 的圖形系統(tǒng)數(shù)據(jù)服務(wù)端，圖元?jiǎng)討B(tài)數(shù)據(jù)的描述信息準(zhǔn)確與否，會(huì)影響服務(wù)端的解析效率。在SVG 圖形庫龐大的情況下，提高服務(wù)器端對(duì)動(dòng)態(tài)數(shù)據(jù)的特征提取及數(shù)據(jù)挖掘、對(duì)動(dòng)態(tài)數(shù)據(jù)描述信息的解析就尤為重要。

1 數(shù)據(jù)解析

SVG 圖形系統(tǒng)使用請(qǐng)求路由器MapDispatichServlet 來解析輸入請(qǐng)求，并將請(qǐng)求分發(fā)到相對(duì)應(yīng)的對(duì)象進(jìn)行處理。MapDispatichServlet 分別實(shí)現(xiàn)doGet()方法和doPost()方法。doGet方法解析用戶的請(qǐng)求，從輸入中得到要取得地圖的名稱，從緩沖器中取得地圖的SVG 文件，輸出XML 格式的SVG 文件。同樣地，doPost 方法解析用戶的請(qǐng)求，按照地圖名稱取得SVG 地圖，并根據(jù)請(qǐng)求格式的不同區(qū)分為SOAP 請(qǐng)求和普通的表單POST 請(qǐng)求，最后組成XML 文件輸出。

SXW 格式解析器負(fù)責(zé)處理由SuperMap Deskpro 地圖編輯軟件產(chǎn)生的空間SXW 文件的解析，未來要考慮處理MapInfo、ArcMap等生成的工作空間文件。它提供外部所需的圖層元素值，其中包括一個(gè)外部接口類（主類/驅(qū)動(dòng)類）：MapConfig；兩個(gè)內(nèi)部調(diào)用類：LayerBuffer，Parser；一個(gè)數(shù)據(jù)LayerBean，如圖1所示。外部程序只能調(diào)用MapConfig 類，提供了兩個(gè)入口，getValue 方法它返回的圖層元素值為一個(gè)數(shù)據(jù)LaerBean，外部程序需要實(shí)例化該數(shù)據(jù)LayerBean。doParser 提供SXW 文檔解析，外部程序首先應(yīng)當(dāng)調(diào)用該方法，驅(qū)動(dòng)子系統(tǒng)解析SXW 文件，并返回true。

其中，圖形配置模塊MapConfig 中的getValue 用于獲取Layer數(shù)據(jù)Bean，doParser 用于設(shè)置文件路徑，檢查文件是否存在，并調(diào)用緩存處理模塊LayerBuffer 驅(qū)動(dòng)XML 文件的解析。緩存處理模塊LayerBuffer 中的getLayerValue 用于對(duì)解析出來的數(shù)據(jù)Bean 存儲(chǔ)到HashMap。XML 文件解析模塊Parser 中的getDocument 用于生成XML 文檔解析器，生成Document 對(duì)象，elementParse 用于解析XML 文檔元素生成Bean，dec2Hex 用于將十進(jìn)制轉(zhuǎn)換成十六進(jìn)制。

圖1：SXW 類圖框架

圖形數(shù)據(jù)解析完畢，接著需要裝載SVG 地圖。通過loadSVGMap 函數(shù)先讀出地圖的基本信息跟SVG 內(nèi)容，并按照每條基本信息構(gòu)造SVG 的名稱，并將其作為索引寫入svgMap 哈希表內(nèi)，也將相對(duì)應(yīng)內(nèi)容寫入svgMap 的內(nèi)容中。接著doParser 調(diào)用緩存處理模塊驅(qū)動(dòng)XML 文件的解析，數(shù)據(jù)緩存器自行維護(hù)一塊緩存數(shù)據(jù)，采用名稱—內(nèi)容方式存儲(chǔ)數(shù)據(jù)。數(shù)據(jù)緩存器在服務(wù)器啟動(dòng)時(shí)自動(dòng)建立唯一實(shí)例，并從Oracle 數(shù)據(jù)庫中的緩存數(shù)據(jù)存儲(chǔ)表中讀入所有數(shù)據(jù)。調(diào)用方傳入數(shù)據(jù)名稱，緩存器負(fù)責(zé)從緩存區(qū)中讀取相對(duì)應(yīng)的數(shù)據(jù)，并以byte 數(shù)組方式返回請(qǐng)求的內(nèi)容。如果請(qǐng)求的數(shù)據(jù)不在緩存區(qū)中，調(diào)用方可以從數(shù)據(jù)庫中讀取相應(yīng)內(nèi)容，并將讀出的內(nèi)容寫入到緩存器中，以便下次調(diào)用的時(shí)候可以提高性能。數(shù)據(jù)緩存器不負(fù)責(zé)讀取請(qǐng)求的解析，不負(fù)責(zé)訪問數(shù)據(jù)庫，僅僅用于查找、匹配、讀取、寫入數(shù)據(jù)。

圖2：canopy 算法概念圖

圖3：canopy 算法流程圖

調(diào)用Parser.elementParse 解析XML 文檔元素生成Bean。使用compose 函數(shù)進(jìn)行組裝，從結(jié)果集中取出所有的SXW 文件名、province、city、Datalink 值，建立mapConfig，使用doParser() 方法傳入SXW 文件名，設(shè)置LayerInfo，按照對(duì)應(yīng)的Datalink 取得Wing_LayerInfo 表中LayerInfo 的其他值，設(shè)置對(duì)應(yīng)的LayerInfo 類中的各個(gè)值，按照查詢出的列數(shù)和行數(shù)進(jìn)行雙循環(huán)，查詢出Wing_BlockInfo 中對(duì)應(yīng)的各個(gè)塊的內(nèi)容，構(gòu)造BlockInfo，并將其傳入svgFactory，svgFactory 返回SVG 內(nèi)容，完成組裝。

2 K-means算法數(shù)據(jù)挖掘

在SXW 文件解析過程中，要對(duì)所有的SVG 圖形圖像元素及屬性進(jìn)行特征提取和數(shù)據(jù)挖掘，以提高整個(gè)系統(tǒng)查詢的效率和準(zhǔn)確度?？梢圆捎肒-means 算法來進(jìn)行基于劃分的聚類方法的數(shù)據(jù)挖掘。

其算法過程如下：

（1）從N 個(gè)SXW 解析文件隨機(jī)選取K 個(gè)SXW 解析文作為質(zhì)心。

（2）對(duì)剩余的每個(gè)文件測量其到每個(gè)質(zhì)心的距離，并把它歸到最近的質(zhì)心的類。

（3）重新計(jì)算已經(jīng)得到的各個(gè)類的質(zhì)心。

（4）循環(huán)重復(fù)2～3 步直至新的質(zhì)心與原來質(zhì)心相等或小于指定閾值，算法結(jié)束。

具體實(shí)現(xiàn)如下：

（1）輸入k,data[n]； 選擇k 個(gè)初始中心點(diǎn)，例如

c[0]=data[0],…c[k-1]=data[k-1]；

（2）對(duì)于data[0]….data[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標(biāo)記為i；

（3）對(duì)于所有標(biāo)記為i 點(diǎn)，重新計(jì)算c[i]=；

（4）重復(fù)2、3 步，直到所有c[i]值的變化小于給定閾值。

當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)就終止算法。針對(duì)不一樣的距離度量，目標(biāo)函數(shù)是會(huì)有差別的。當(dāng)采用歐幾里得方法計(jì)算距離度量時(shí)，目標(biāo)函數(shù)一般通常采用最小化對(duì)象到其簇質(zhì)心的距離的平方和，如下：

當(dāng)采用余弦相似度時(shí)，目標(biāo)函數(shù)一般為最大化對(duì)象到其簇質(zhì)心的余弦相似度和，如下：

K-menas 算法試圖找到使平均誤差準(zhǔn)則函數(shù)最小的簇。若潛在的簇是凸形狀的，那么簇間的區(qū)別就會(huì)比較明顯，而且若簇大小相近時(shí)，那么使用K-menas 算法的聚類結(jié)果比較理想。K-menas 算法的優(yōu)點(diǎn)在于算法時(shí)間復(fù)雜度O（tKmn）和樣本數(shù)量線性是相關(guān)的，因此，當(dāng)在處理大數(shù)據(jù)集時(shí)，該算法高效、伸縮性較好。但其不足在于該算法要事先確定簇?cái)?shù) K，同時(shí)對(duì)初始聚類中心、“噪聲”、孤立點(diǎn)敏感，因此，該方法不適合非凸面形狀的簇或大小差別很大的簇。

3 使用Canopy 聚類算法改進(jìn)數(shù)據(jù)挖掘

當(dāng)數(shù)據(jù)的條目很多、數(shù)據(jù)向量其維度很大、包含多個(gè)屬性，或者在進(jìn)行數(shù)據(jù)挖掘時(shí)無法事先就判定應(yīng)該聚成多少類，無法進(jìn)行K值的設(shè)定時(shí)，就要采取另外的途徑，改進(jìn)聚類算法，采用Canopy算法。

3.1 Canopy算法的主要思想

Canopy 算法把數(shù)據(jù)挖掘分為兩個(gè)階段，具體來說，階段一，使用一個(gè)簡單粗糙的距離計(jì)算方法來產(chǎn)生具有一定數(shù)量的可重疊的子集，設(shè)定一個(gè)距離閾值，當(dāng)計(jì)算的距離小于這個(gè)閾值的時(shí)候，就把數(shù)據(jù)向量歸到此子集，也就是canopy。每個(gè)數(shù)據(jù)向量有可能存在于多個(gè)canopy 里面，每個(gè)數(shù)據(jù)向量至少要包含于一個(gè)canopy 中。同一個(gè)canopy 中的樣本數(shù)據(jù)向量彼此間還是存在相似性，有可能被分為同一個(gè)類。由于距離計(jì)算方式是粗糙的，因此不能夠保證性能（計(jì)算精確度）。但是通過允許存在可疊加的canopy 和設(shè)定一個(gè)較大的距離閾值，在某些情況下可以保證該算法的性能。

3.2 創(chuàng)建Canopy算法

創(chuàng)建一個(gè)普通的canopy 算法的概念圖與簡單步驟，如圖2所示。

（1）從SVG 元素工廠生成相應(yīng)數(shù)據(jù)庫表的SVG 元素，獲取對(duì)應(yīng)的SVG 元素?cái)?shù)組。原始數(shù)據(jù)集合列表按照一定的規(guī)則進(jìn)行排序，初始距離閾值為T1、T2，且T1＞T2。T1、T2 的設(shè)定可以根據(jù)用戶的需要，或者使用交叉驗(yàn)證獲得。

（2）在數(shù)據(jù)集合列表中隨機(jī)挑選一個(gè)數(shù)據(jù)向量A，運(yùn)用粗糙距離計(jì)算方式計(jì)算A 與列表中其他數(shù)據(jù)向量之間的距離d。

（3）根據(jù)第2 步中的距離d，把d 小于T1 的樣本數(shù)據(jù)向量劃到一個(gè)canopy 子集中，同時(shí)把d 小于T2 的樣本數(shù)據(jù)向量從候選中心向量名單，也就是數(shù)據(jù)集合列表中移除。

（4）重復(fù)第2、3 步，直到數(shù)據(jù)集合列表為空，算法結(jié)束。

創(chuàng)建canopy 算法的流程圖如圖3所示。

階段二，可以在階段一的基礎(chǔ)上應(yīng)用傳統(tǒng)聚類數(shù)據(jù)挖掘算法，比如貪婪凝聚聚類算法、K 均值聚類算法，當(dāng)然，這些算法使用的距離計(jì)算方式是精準(zhǔn)的距離計(jì)算方式。但是因?yàn)橹挥?jì)算了同一個(gè)canopy 中的數(shù)據(jù)向量之間的距離，而沒有計(jì)算不在同一個(gè)canopy的數(shù)據(jù)向量之間的距離，所以假定它們之間的距離為無窮大。例如，若所有的數(shù)據(jù)都簡單歸入同一個(gè)canopy，那么階段二的聚類挖掘就會(huì)退化成傳統(tǒng)的具有高計(jì)算量的聚類算法了。但是，如果canopy不是那么大，且它們之間的重疊不是很多，那么代價(jià)很大的距離計(jì)算就會(huì)減少，同時(shí)用于分類的大量計(jì)算也可以省去。進(jìn)一步來說，如果把Canopy 算法加入到傳統(tǒng)的聚類挖掘算法中，那么算法既可以保證性能，即精確度，又可以增加計(jì)算效率，即減少計(jì)算時(shí)間。

Canopy 算法的優(yōu)勢在于先進(jìn)行數(shù)據(jù)預(yù)處理，在數(shù)據(jù)預(yù)處理中，使用粗糙距離計(jì)算方法將數(shù)據(jù)分到幾個(gè)可重疊的子集中，再而只需計(jì)算在同一個(gè)重疊子集中的數(shù)據(jù)向量，以此來減少數(shù)據(jù)計(jì)算量。

3.3 Canopy算法實(shí)施

使用Canopy 算法對(duì)SVG 向量數(shù)據(jù)進(jìn)行聚類分析，涉及到以下幾個(gè)過程：

（1）將SXW 序列文件進(jìn)行向量化轉(zhuǎn)換。使用sequence2TFVectors 方法將信息轉(zhuǎn)換為＜詞ID，詞頻＞的向量形式，每一個(gè)詞ID 就代表了一個(gè)變量的坐標(biāo)，而這個(gè)詞ID 對(duì)應(yīng)的詞頻即為該變量值，每一個(gè)詞組成的位置信息則轉(zhuǎn)換為了一個(gè)稀疏變量，SXW 序列文件便轉(zhuǎn)換為了稀疏矩陣。

Input 用于輸入的序列文件路徑，analyzerClass 是使用的Lucene 解析器，Output 指具體的輸出目錄。

（2）運(yùn)行canopy 算法初始化聚類重心。使用canopy 算法API對(duì)向量化后的文件初始化聚類中心。這里CanopyDriver 方法需要設(shè)置的三個(gè)重要參數(shù)為距離選擇，以及閾值T1，T2 的取值。這里選擇的是適合文本分析的余弦距離公式，比如T1 為0.6，T2 為0.4。

（3）運(yùn)行kmeans 算法對(duì)SVG 信息進(jìn)行聚類。在運(yùn)行完了canopy 方法后，便要進(jìn)行kmeans 算法，利用canopy 生成的結(jié)果作為初始聚類中心，由于此時(shí)聚類中心數(shù)已經(jīng)確定，則不需要設(shè)置k值，最終的聚類數(shù)會(huì)根據(jù)收斂閾值變化而變化。

其中涉及到重要的參數(shù)設(shè)置，收斂閾值為 0.3，迭代次數(shù)為100。

（4）調(diào)用ClusterDumper 類將最終的聚類結(jié)果轉(zhuǎn)換為可以讀懂的信息，由于聚類結(jié)果是序列文件，而且是以詞ID 的形式出現(xiàn)的，因此需要將在文本向量化過程中生成的dictionary 文件關(guān)聯(lián)至該方法。

（5）利用dump 接口對(duì)聚類結(jié)果進(jìn)行解析。執(zhí)行完第3 個(gè)過程后，生成了一個(gè)序列文件保存結(jié)果，這個(gè)序列文件的key 為進(jìn)行比較的兩組向量的ID 信息，value 為這兩組向量的距離。我們只需要通過SequenceFile.Reader 將距離信息讀出，然后進(jìn)行排序，即能得到最終結(jié)果。

4 結(jié)論

基于 SVG 的圖形系統(tǒng)結(jié)合了基于圖像內(nèi)容和基于圖像特征的挖掘檢索與應(yīng)用，在 SVG 圖形庫非常龐大的情況下，從SVG 圖形基本信息的 XML 文件中采用K-means 和Canopy 算法進(jìn)行聚類數(shù)據(jù)挖掘，包括文本向量處理部分的參數(shù)設(shè)置、Canopy 與K-means算法的收斂閾值參數(shù)設(shè)置，以及向量相似度算法的距離度量選擇，為提高檢索、解析速度提供了一種方法。