基于密度劃分的數據存儲方法與技術

趙會群，李春良

(北方工業大學 計算機學院，北京 100144)

0 引 言

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

1 密度區域劃分算法研究

1.1 密度區域劃分算法

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

Input：

Data：待處理原始數據集

R：滾球半徑

MinThreShold：滾球2R區域密度閾值參數

Output：高密度數據集

算法Pseudo Code：

(1)初始化數據集目標點為unvisited；

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

(3)Do

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

(5)計算p點2R-領域內部屬性為unvisited點個數num及其構成的領域面積Area；

(6)依據num與Area值計算p點領域區域密度，p-ThreShold=num/Area；

(7)Ifp-ThreShold>=MinThreShold；

(8) 初始化包含P點R-領域屬性為unvisited點的密度區域E，并將其內部點集屬性修改為visited；

(9) ForEachEs密度區域E’；

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

(11) Ifp’2R-領域、E’區域存在交集；

(12) 將E、E’進行數據合并；

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

(14)Else

(15) 更新p點2R領域內所有p’屬性為visited；

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

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

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

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

圖1 矢量圖

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

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

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

圖2 釘群

圖3 邊界點F

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

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

極坐標排序，如圖4所示。

圖4 極坐標排序

算法詳細介紹如下：

Input：

Data：待處理數據集

R：滾圓半徑

Output：區域邊界鏈boundary

算法Pseudo Code：

(1)初始化邊界鏈boundary；

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

(3)Do

(4)If boundary size 等于1

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

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

(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-領域點集E；

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

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

2 實驗分析

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

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

2.1 GPS數據壓縮存儲

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

表1 車輛行駛軌跡數據字段

2.1.1 車輛軌跡GPS數據分析與壓縮

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

圖5 高密度區域

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

圖6 去除重復數據

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

表2 密度區域數據樣例

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

圖7 時間值分布

2.1.2 車輛軌跡GPS數據的恢復

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

完整數據，如圖8所示。

圖8 完整數據

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

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

圖9 射線法

2.2 路由表數據壓縮存儲

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

2.2.1 路由數據介紹

互聯網中通信兩端在進行交互時，其大概率需跨局域網進行交互，此時需要進行傳輸路徑擇優選擇，路由其扮演的是跨局域網交互傳輸路徑選擇與描述角色(具體由AS自治系統(autonomous system)構成了此跨局域網傳輸路徑)，本文采用的路由信息數據就是多個AS系統之間嚴格遵循網關協議連接形成的一條條路由跳轉路徑數據信息。數據格式見表3。

表3 路由數據

2.2.2 路由數據分析及高密度區域挖掘

采用無向圖的方式將彼此存在跳轉關系的AS系統進行雙向連接，更為直觀地展現AS系統之間的交互關系，如圖10所示。

圖10 AS無向圖

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

圖11 AS跳轉路徑

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

2.2.3 路由數據高密度子網區域數據壓縮存儲與恢復

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

采集局域高密集子網區域中的AS系統編號，進行根據編號在區域內出現的頻率進行自然排序構建AS編號矩陣，在密集區域中(見表3)，對每一對跳轉路徑在矩陣中進行尋址，用自然數標記此跳轉路徑在矩陣中的位置，進行占位替換。表4為處理后的壓縮文件文件。數據恢復時，構建矩陣模型，依據壓縮文件中記錄的占位符等信息讀取在矩陣中位置信息，進行AS系統編號恢復，進而恢復整個局域高密集子網區域。

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

2.3 性能分析

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

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

表5 GPS數據

表6 路由數據

3 結束語

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