基于密度劃分的數(shù)據(jù)存儲方法與技術(shù)

趙會群，李春良

(北方工業(yè)大學(xué) 計算機(jī)學(xué)院，北京 100144)

0 引 言

在傳統(tǒng)的數(shù)據(jù)壓縮研究領(lǐng)域中，依據(jù)壓縮處理后數(shù)據(jù)是否可以完全恢復(fù)，將壓縮算法分為無損與有損壓縮兩種方式[1]。無損壓縮又大體分為以LZW為代表的基于字典結(jié)構(gòu)的壓縮算法[2-6]和以Huffman編碼為代表的基于統(tǒng)計的壓縮算法[8,9]。無論是LZW還是Huffman編碼在實際操作中都存在較大局限性，如LZW局限于原始數(shù)據(jù)集中重復(fù)字符或字符串出現(xiàn)的次數(shù)，數(shù)據(jù)字典結(jié)構(gòu)的大小等。從去除數(shù)據(jù)源中重復(fù)信息的角度來說，LZW與Huffman的處理角度都是篩選出數(shù)據(jù)源中重復(fù)字符(字符串)進(jìn)行擦除降低冗余度操作，而在數(shù)據(jù)源中，由重復(fù)字符串及相同信息含義的重傳數(shù)據(jù)所組成的密集信息區(qū)域，針對此種情況，本文開辟新的思路，參考挖掘中的聚類思想[10]，根據(jù)密度分散的不同進(jìn)行有效劃分，提出數(shù)據(jù)源中的密集信息區(qū)域，并對其進(jìn)行統(tǒng)一擦除操作，去除其中具有重復(fù)屬性的數(shù)據(jù)，只保留可以描述當(dāng)時原高密度區(qū)域“場景”信息的少量數(shù)據(jù)，以達(dá)到數(shù)據(jù)壓縮的目的。

1 密度區(qū)域劃分算法研究

1.1 密度區(qū)域劃分算法

篩選數(shù)據(jù)源高密度數(shù)據(jù)區(qū)域，其本質(zhì)為是把數(shù)據(jù)源中的每一個數(shù)據(jù)視作一個數(shù)據(jù)對象，通過不斷的迭代匹配將屬性高度相近的對象化為到不同區(qū)域(子集)的過程。關(guān)于如何挖掘出數(shù)據(jù)中的高密度區(qū)域，在數(shù)據(jù)挖掘領(lǐng)域，有許多基于密度的數(shù)據(jù)挖掘算法可借鑒，如DBSCAN與K-means算法等[11-13]。類似于DBSCAN傳統(tǒng)思路的聚類算法在處理數(shù)據(jù)表現(xiàn)疏散的數(shù)據(jù)時，其算法表現(xiàn)會呈現(xiàn)無法精準(zhǔn)進(jìn)行區(qū)域劃分，劃分后的區(qū)域特征呈現(xiàn)相近，并且在處理過程中存在無用重復(fù)操作。為了更為快捷有效劃分出數(shù)據(jù)源中的高密度區(qū)域，本文借助區(qū)域面積與“濃度”的概念集合傳統(tǒng)的聚類思想，改進(jìn)算法，用數(shù)據(jù)源中單位面積內(nèi)樣本點的個數(shù)對數(shù)據(jù)源數(shù)據(jù)密度分布進(jìn)行精準(zhǔn)刻畫，并且規(guī)避了傳統(tǒng)做法中對每一個樣本點進(jìn)行便利判斷的冗余操作，算法具體步驟詳細(xì)介紹如下：

Input：

Data：待處理原始數(shù)據(jù)集

R：滾球半徑

MinThreShold：滾球2R區(qū)域密度閾值參數(shù)

Output：高密度數(shù)據(jù)集

算法Pseudo Code：

(1)初始化數(shù)據(jù)集目標(biāo)點為unvisited；

(2)初始化高密度數(shù)據(jù)集合Es；

(3)Do

(4)從unvisited數(shù)據(jù)集中隨機(jī)選擇數(shù)據(jù)點p，并將其屬性修改為visited；

(5)計算p點2R-領(lǐng)域內(nèi)部屬性為unvisited點個數(shù)num及其構(gòu)成的領(lǐng)域面積Area；

(6)依據(jù)num與Area值計算p點領(lǐng)域區(qū)域密度，p-ThreShold=num/Area；

(7)Ifp-ThreShold>=MinThreShold；

(8) 初始化包含P點R-領(lǐng)域?qū)傩詾閡nvisited點的密度區(qū)域E，并將其內(nèi)部點集屬性修改為visited；

(9) ForEachEs密度區(qū)域E’；

(10) ForEach 密度區(qū)域E點p’；

(11) Ifp’2R-領(lǐng)域、E’區(qū)域存在交集；

(12) 將E、E’進(jìn)行數(shù)據(jù)合并；

(13) ElseE歸入Es密度區(qū)域集合中；

(14)Else

(15) 更新p點2R領(lǐng)域內(nèi)所有p’屬性為visited；

(16)Until原始數(shù)據(jù)中數(shù)據(jù)點p均為visited;

下面給出密度區(qū)域劃分算法中計算區(qū)域面積Area的詳細(xì)過程：①借助滾球法獲取區(qū)域的邊界信息(點集構(gòu)成的區(qū)域邊界鏈)；②依據(jù)獲取的區(qū)域邊界信息借助矢量積求解區(qū)域面積。

1.2 利用矢量積計算任意多邊形面積

通常做法為先通過耳切法等[14]將不規(guī)則多邊形進(jìn)行三角劃分，分割成n個大小各異的三角形，通過累加分割后的各個三角形的面積得到最后的多邊形面積。其缺點是隨著邊界點的增加，會增長三角劃分的復(fù)雜度，計算過程亦會非常繁瑣。為了簡化操作快速獲取任意多邊形的面積，本文采取先對多邊形Ω建立矢量圖，如圖1所示，對相鄰的兩個邊界點所組成的有向矢量三角形根據(jù)矢量外積計算其矢量面積，最后累加所有矢量三角形面積值，從而求出整個多邊形面積。具體多邊形面積計算公式推導(dǎo)過程請參見參考文獻(xiàn)[15]。

圖1 矢量圖

1.3 滾球法求解任意多邊形邊界

處理求解多邊形邊界點問題掃描法、MelKman等算法是常用的算法，其特點是簡潔快速，缺點也十分突出，其主要用來處理凸包邊界點求解，而對于求解任意形狀的簇包其算法表現(xiàn)過于粗糙，誤差較大，無法取得理想邊界點效果。在本文提出的算法中，精準(zhǔn)獲取區(qū)域邊界鏈?zhǔn)呛诵膯栴}，因此，本文提出一種獲取任意簇包邊界點算法：滾球法。

核心思想是用一個初始值為R的矢量圓從區(qū)域的初始點不斷迭代滾動，每次滾動在區(qū)域中首次觸碰的數(shù)據(jù)點視作該區(qū)域下一邊界點，當(dāng)矢量圓再次回到初始點時視作迭代滾動完成，該區(qū)域的邊界點集由矢量圓在迭代滾動過程中觸碰的所有數(shù)據(jù)點所構(gòu)成。

圖2 釘群

圖3 邊界點F

極坐標(biāo)排序：對點集中的點建立以起點O和初始方向n的逆時針排序的新點集。

向量叉積：其結(jié)果可以用以描述的為兩個向量的相對關(guān)系，以為向量a、b為例，計算公式為ax×bx+ay×by， 其結(jié)果的正負(fù)性質(zhì)可描述為正值表示向量b位于向量a的逆向位置，負(fù)值則相反。

極坐標(biāo)排序，如圖4所示。

圖4 極坐標(biāo)排序

算法詳細(xì)介紹如下：

Input：

Data：待處理數(shù)據(jù)集

R：滾圓半徑

Output：區(qū)域邊界鏈boundary

算法Pseudo Code：

(1)初始化邊界鏈boundary；

(2)取Y軸方向最小值點p作為邊界鏈初始點，并加入邊界鏈boundary中；

(3)Do

(4)If boundary size 等于1

(5) 初始化邊界點p點2R-領(lǐng)域點集E；

(6) 采用p點-X軸方向作為極坐標(biāo)排序所需的基準(zhǔn)向量，對點集E中的點進(jìn)行極坐標(biāo)排序；

(7) ForEach 點集E中點p’；

(8) 以pp’為弦作圓O；

(9) If 圓O點集、點集E不存在交集；

(10) 點p’作為下一邊界點歸入boundary中；

(11)Else boundary size 大于 1；

(12) ForEach有向邊界鏈boundary

(13) 獲取最后歸入邊界鏈boundary中的點p、p’；

(14) 初始化邊界點p點2R-領(lǐng)域點集E；

(15) 以pp’方向為基準(zhǔn)向量，對點集E重復(fù)(6)-(10)操作；

(16)Until無下一邊界點 or 下一邊界點為初始邊界點p；

2 實驗分析

在上文中，給出了針對降低數(shù)據(jù)冗余度，解決數(shù)據(jù)源中帶有重復(fù)性質(zhì)的數(shù)據(jù)比例過高的問題本文的解決方案，并給出了對應(yīng)的密度區(qū)域劃分算法的思想與具體步驟。下面對本文提出的算法結(jié)合具體的案例，對其實際可行性做更為詳細(xì)的論證。

為了更為全面的驗證其對不同數(shù)據(jù)都能實現(xiàn)有效的壓縮存儲，本文采用了GSP地理信息數(shù)據(jù)與路由表兩種數(shù)據(jù)屬性截然不同的數(shù)據(jù)源。GPS數(shù)據(jù)源為現(xiàn)實車輛行駛軌跡真實數(shù)據(jù)，其數(shù)據(jù)屬性表現(xiàn)為會自主呈現(xiàn)出聚集效應(yīng)，是符合本文思想的理想數(shù)據(jù)；路由數(shù)據(jù)的數(shù)據(jù)屬性則會呈現(xiàn)出傳統(tǒng)壓縮算法更善于處理的大量重復(fù)字符(字符串)。兩種數(shù)據(jù)理論都可采用本文提出的密度區(qū)域劃分?jǐn)?shù)據(jù)壓縮策略進(jìn)行高效壓縮存儲。

2.1 GPS數(shù)據(jù)壓縮存儲

本文第一個實驗驗證采用的是出租車車輛軌跡數(shù)據(jù)，對市區(qū)一萬多輛出租車(源自微軟亞洲研究院)7天的車輛行使軌跡GPS數(shù)據(jù)，以每輛車為單位，每5 s采集一次GPS地理位置信息，最終形成的車輛GPS行為軌跡信息，以時間作為橫軸坐標(biāo)參考，呈現(xiàn)出線性分布。具體數(shù)據(jù)見表1，包含了車輛的ID號(不是車牌號)、行駛的日期、時間、車輛經(jīng)緯度信息。

表1 車輛行駛軌跡數(shù)據(jù)字段

2.1.1 車輛軌跡GPS數(shù)據(jù)分析與壓縮

按天為基本單位，使用本文密度區(qū)域劃分算法對數(shù)據(jù)集做處理，將數(shù)據(jù)集中車輛GPS信息高度密集的區(qū)域從原始數(shù)據(jù)集中進(jìn)行抽離，形成孤立的密集區(qū)。如圖5中密集區(qū)域所示，每一個密集區(qū)其代表的是實際含義為車輛高頻率聚集疊加，內(nèi)部車輛軌跡信息高度重復(fù)。

圖5 高密度區(qū)域

針對抽離的高密度區(qū)，內(nèi)部大量重復(fù)的車輛GPS軌跡信息對描述此區(qū)域高密度特性而言是沒有必要重復(fù)存儲的，是對寶貴的存儲空間的浪費。因此，基于本文去除密集區(qū)域重復(fù)信息的思想，對此密集區(qū)，利用本文提出的算法，只保留可以反饋密集區(qū)基本樣貌信息的臨界數(shù)據(jù)，舍棄內(nèi)部重復(fù)疊加的車輛GPS信息，減小對存儲空間的壓力。如圖6所示。

圖6 去除重復(fù)數(shù)據(jù)

針對每一個劃分出的高密度區(qū)域，只對其保存根據(jù)本文算法得到的邊界鏈與區(qū)域中心數(shù)據(jù)，和區(qū)域內(nèi)部的時間散列數(shù)據(jù)(去除內(nèi)部重復(fù)GPS數(shù)據(jù)后，區(qū)域內(nèi)的時間值變化失去線性規(guī)律)，基于基本統(tǒng)計的車輛ID信息(即車輛ID疊加重復(fù)的次數(shù))，最終壓縮處理后的數(shù)據(jù)存儲格式見表2。

表2 密度區(qū)域數(shù)據(jù)樣例

時間值分布，如圖7所示。

圖7 時間值分布

2.1.2 車輛軌跡GPS數(shù)據(jù)的恢復(fù)

數(shù)據(jù)恢復(fù)時，基于密集區(qū)高度密集特性，可采用近似于均勻分布的數(shù)據(jù)散列方式，圍繞保留的區(qū)域中心，在區(qū)域邊界內(nèi)散列鋪滿整個區(qū)域，復(fù)原密集區(qū)數(shù)據(jù)樣貌。具體方式，借助射線法判斷復(fù)原的GPS數(shù)據(jù)是否在邊界鏈內(nèi)，利用保留的車輛ID、車輛ID疊加次數(shù)、區(qū)域內(nèi)車輛部行駛時間信息，進(jìn)行數(shù)據(jù)拼接，還原車輛完成軌跡GPS信息，進(jìn)而真實還原整個抽離的密集區(qū)車輛信息疊加分布信息。

完整數(shù)據(jù)，如圖8所示。

圖8 完整數(shù)據(jù)

2.1.3 空間點與任意不規(guī)則多邊形位置判定

判定點與任意不規(guī)則多邊形的位置關(guān)系有多種方式，其中射線法是行為有效最為簡單直接的一種校驗方法。其通過將待校驗的點分別向兩側(cè)做水平射線，分別判斷左右射線與不規(guī)則多邊形交集信息，如圖9所示，兩側(cè)射線均與此多邊形存在奇數(shù)個交點，則說此點位于多邊形內(nèi)部。

圖9 射線法

2.2 路由表數(shù)據(jù)壓縮存儲

本文第二個實驗采用美國俄勒岡大學(xué)路由查看項目部分路由數(shù)據(jù)作為數(shù)據(jù)源。

2.2.1 路由數(shù)據(jù)介紹

互聯(lián)網(wǎng)中通信兩端在進(jìn)行交互時，其大概率需跨局域網(wǎng)進(jìn)行交互，此時需要進(jìn)行傳輸路徑擇優(yōu)選擇，路由其扮演的是跨局域網(wǎng)交互傳輸路徑選擇與描述角色(具體由AS自治系統(tǒng)(autonomous system)構(gòu)成了此跨局域網(wǎng)傳輸路徑)，本文采用的路由信息數(shù)據(jù)就是多個AS系統(tǒng)之間嚴(yán)格遵循網(wǎng)關(guān)協(xié)議連接形成的一條條路由跳轉(zhuǎn)路徑數(shù)據(jù)信息。數(shù)據(jù)格式見表3。

表3 路由數(shù)據(jù)

2.2.2 路由數(shù)據(jù)分析及高密度區(qū)域挖掘

采用無向圖的方式將彼此存在跳轉(zhuǎn)關(guān)系的AS系統(tǒng)進(jìn)行雙向連接，更為直觀地展現(xiàn)AS系統(tǒng)之間的交互關(guān)系，如圖10所示。

圖10 AS無向圖

互聯(lián)網(wǎng)中每秒都存在著極高頻率的交互動作，而AS系統(tǒng)是有限的，任意相鄰的兩個AS系統(tǒng)之間都在進(jìn)行極高頻率的重復(fù)跳轉(zhuǎn)，其在數(shù)據(jù)源中的表現(xiàn)為某一條跳轉(zhuǎn)路徑以極高的頻率被重復(fù)存儲。以下圖為例，17974-7713跳轉(zhuǎn)路徑存儲了3503次，路徑3549-3356AS跳轉(zhuǎn)路徑存儲了403次。AS跳轉(zhuǎn)路徑，如圖11所示。

圖11 AS跳轉(zhuǎn)路徑

在原始數(shù)據(jù)中，以3549-3356為例，存在大量與此跳轉(zhuǎn)路徑具有直接交互關(guān)系的AS系統(tǒng)，這種高頻率AS系統(tǒng)跳轉(zhuǎn)路徑的聚集現(xiàn)象完全符合本文去重思想，提供了可行性依據(jù)。利用本文提出的密度區(qū)域劃分算法,在操作過程中，將路由數(shù)據(jù)集中的跳轉(zhuǎn)路徑視為一個二維點，則可將整個路由數(shù)據(jù)集視為類似車輛GPS性質(zhì)的二維點集數(shù)據(jù)包，初始面積值取1，將原始數(shù)據(jù)集中大量存在的由眾多高頻率AS系統(tǒng)構(gòu)成的局域高密集子網(wǎng)區(qū)域進(jìn)行抽離。根據(jù)數(shù)據(jù)表現(xiàn)，每個抽離的局域高密集子網(wǎng)區(qū)域具備以下特點：①局域高密集子網(wǎng)區(qū)域AS跳轉(zhuǎn)路徑重復(fù)率極高；②局域高密集子網(wǎng)區(qū)域AS系統(tǒng)個數(shù)數(shù)量不高，表現(xiàn)為AS無向圖結(jié)構(gòu)不復(fù)雜；③每個AS系統(tǒng)編號都由16 bite組成，基于此構(gòu)建的AS系統(tǒng)跳轉(zhuǎn)路徑更長。

2.2.3 路由數(shù)據(jù)高密度子網(wǎng)區(qū)域數(shù)據(jù)壓縮存儲與恢復(fù)

從數(shù)據(jù)存儲的角度進(jìn)行分析，針對抽離出的局域高密集子網(wǎng)區(qū)域中的跳轉(zhuǎn)路徑進(jìn)行無條件完全存儲，可視為是對存儲空間的浪費。由于AS自治系統(tǒng)編號具有唯一性的特性，在對抽離出的局域高密集子網(wǎng)區(qū)域進(jìn)行壓縮存儲時，其內(nèi)部的AS系統(tǒng)編號不可直接進(jìn)行模糊擦除，因此，對每一個局域高密集子網(wǎng)區(qū)域建立由其內(nèi)部AS系統(tǒng)編號構(gòu)建的矩陣，借用占位符的概念，利用密集區(qū)域內(nèi)部跳轉(zhuǎn)路徑在矩陣中的位置信息進(jìn)行占位替換，減小整個密集區(qū)的重新信息，減小對存儲空間的壓力。

采集局域高密集子網(wǎng)區(qū)域中的AS系統(tǒng)編號，進(jìn)行根據(jù)編號在區(qū)域內(nèi)出現(xiàn)的頻率進(jìn)行自然排序構(gòu)建AS編號矩陣，在密集區(qū)域中(見表3)，對每一對跳轉(zhuǎn)路徑在矩陣中進(jìn)行尋址，用自然數(shù)標(biāo)記此跳轉(zhuǎn)路徑在矩陣中的位置，進(jìn)行占位替換。表4為處理后的壓縮文件文件。數(shù)據(jù)恢復(fù)時，構(gòu)建矩陣模型，依據(jù)壓縮文件中記錄的占位符等信息讀取在矩陣中位置信息，進(jìn)行AS系統(tǒng)編號恢復(fù)，進(jìn)而恢復(fù)整個局域高密集子網(wǎng)區(qū)域。

表4 壓縮后的路由存儲文件

2.3 性能分析

數(shù)據(jù)壓縮的性能指標(biāo)主要是壓縮率與壓縮速度，針對于本文所采用的兩種測試數(shù)據(jù)集本身都不足夠大的情況，這里主要討論壓縮率。壓縮率的計算公式如下。在數(shù)值上，壓縮率越小代表算法的壓縮性能越好

對實驗結(jié)果進(jìn)行分析(見表5和表6)，從整體上來看，基于本文提出的數(shù)據(jù)壓縮策略下的密度區(qū)域劃分算法相較傳統(tǒng)的LZW算法在壓縮率上表現(xiàn)更好，尤其是GPS測量地理信息數(shù)據(jù)更能體現(xiàn)文本的思想，不僅局限于去除重復(fù)的車輛ID、日期等重復(fù)字符(字符串)，更去除了篩選出的高密度區(qū)域中具有重復(fù)屬性的數(shù)據(jù)，相較之下路由表數(shù)據(jù)由于無法像GPS數(shù)據(jù)完全去除篩選出的高密度區(qū)域中重復(fù)屬性數(shù)據(jù)，壓縮率有所降低。結(jié)合兩種數(shù)據(jù)的實驗結(jié)果表明，相較于傳統(tǒng)的數(shù)據(jù)壓縮算法，本文提出的數(shù)據(jù)壓縮策略對數(shù)據(jù)的靈活性更高，數(shù)據(jù)適用性更好。

表5 GPS數(shù)據(jù)

表6 路由數(shù)據(jù)

3 結(jié)束語

本文通過對現(xiàn)有的數(shù)據(jù)壓縮存儲策略的分析，提出一種基于密度區(qū)域劃分，挖掘原始數(shù)據(jù)中高密度區(qū)域，去除高密度區(qū)域中包含的重復(fù)性質(zhì)數(shù)據(jù)，以達(dá)到降低數(shù)據(jù)冗余度實現(xiàn)數(shù)據(jù)源壓縮的目的。給出針對各種數(shù)據(jù)具有普適性的數(shù)據(jù)密度區(qū)域劃分算法，以提取數(shù)據(jù)中的高密度區(qū)域。并選取了GPS地理信息與路由表兩種數(shù)據(jù)屬性完全不同數(shù)據(jù)源對本文提出的算法進(jìn)行了驗證。實現(xiàn)結(jié)果不僅驗證了算法的可靠性和壓縮策略的可行性與有效性，更進(jìn)一步表明了本文提出的數(shù)據(jù)壓縮策略相對于傳統(tǒng)的數(shù)據(jù)壓縮策略在壓縮率與數(shù)據(jù)適用性上更具優(yōu)勢，更加靈活。