趙會(huì)群,李春良
(北方工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100144)
在傳統(tǒng)的數(shù)據(jù)壓縮研究領(lǐng)域中,依據(jù)壓縮處理后數(shù)據(jù)是否可以完全恢復(fù),將壓縮算法分為無(wú)損與有損壓縮兩種方式[1]。無(wú)損壓縮又大體分為以LZW為代表的基于字典結(jié)構(gòu)的壓縮算法[2-6]和以Huffman編碼為代表的基于統(tǒng)計(jì)的壓縮算法[8,9]。無(wú)論是LZW還是Huffman編碼在實(shí)際操作中都存在較大局限性,如LZW局限于原始數(shù)據(jù)集中重復(fù)字符或字符串出現(xiàn)的次數(shù),數(shù)據(jù)字典結(jié)構(gòu)的大小等。從去除數(shù)據(jù)源中重復(fù)信息的角度來(lái)說(shuō),LZW與Huffman的處理角度都是篩選出數(shù)據(jù)源中重復(fù)字符(字符串)進(jìn)行擦除降低冗余度操作,而在數(shù)據(jù)源中,由重復(fù)字符串及相同信息含義的重傳數(shù)據(jù)所組成的密集信息區(qū)域,針對(duì)此種情況,本文開辟新的思路,參考挖掘中的聚類思想[10],根據(jù)密度分散的不同進(jìn)行有效劃分,提出數(shù)據(jù)源中的密集信息區(qū)域,并對(duì)其進(jìn)行統(tǒng)一擦除操作,去除其中具有重復(fù)屬性的數(shù)據(jù),只保留可以描述當(dāng)時(shí)原高密度區(qū)域“場(chǎng)景”信息的少量數(shù)據(jù),以達(dá)到數(shù)據(jù)壓縮的目的。
篩選數(shù)據(jù)源高密度數(shù)據(jù)區(qū)域,其本質(zhì)為是把數(shù)據(jù)源中的每一個(gè)數(shù)據(jù)視作一個(gè)數(shù)據(jù)對(duì)象,通過(guò)不斷的迭代匹配將屬性高度相近的對(duì)象化為到不同區(qū)域(子集)的過(guò)程。關(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ù)時(shí),其算法表現(xiàn)會(huì)呈現(xiàn)無(wú)法精準(zhǔn)進(jìn)行區(qū)域劃分,劃分后的區(qū)域特征呈現(xiàn)相近,并且在處理過(guò)程中存在無(wú)用重復(fù)操作。為了更為快捷有效劃分出數(shù)據(jù)源中的高密度區(qū)域,本文借助區(qū)域面積與“濃度”的概念集合傳統(tǒng)的聚類思想,改進(jìn)算法,用數(shù)據(jù)源中單位面積內(nèi)樣本點(diǎn)的個(gè)數(shù)對(duì)數(shù)據(jù)源數(shù)據(jù)密度分布進(jìn)行精準(zhǔn)刻畫,并且規(guī)避了傳統(tǒng)做法中對(duì)每一個(gè)樣本點(diǎn)進(jìn)行便利判斷的冗余操作,算法具體步驟詳細(xì)介紹如下:
Input:
Data:待處理原始數(shù)據(jù)集
R:滾球半徑
MinThreShold:滾球2R區(qū)域密度閾值參數(shù)
Output:高密度數(shù)據(jù)集
算法Pseudo Code:
(1)初始化數(shù)據(jù)集目標(biāo)點(diǎn)為unvisited;
(2)初始化高密度數(shù)據(jù)集合Es;
(3)Do
(4)從unvisited數(shù)據(jù)集中隨機(jī)選擇數(shù)據(jù)點(diǎn)p,并將其屬性修改為visited;
(5)計(jì)算p點(diǎn)2R-領(lǐng)域內(nèi)部屬性為unvisited點(diǎn)個(gè)數(shù)num及其構(gòu)成的領(lǐng)域面積Area;
(6)依據(jù)num與Area值計(jì)算p點(diǎn)領(lǐng)域區(qū)域密度,p-ThreShold=num/Area;
(7)Ifp-ThreShold>=MinThreShold;
(8) 初始化包含P點(diǎn)R-領(lǐng)域?qū)傩詾閡nvisited點(diǎn)的密度區(qū)域E,并將其內(nèi)部點(diǎn)集屬性修改為visited;
(9) ForEachEs密度區(qū)域E’;
(10) ForEach 密度區(qū)域E點(diǎn)p’;
(11) Ifp’2R-領(lǐng)域、E’區(qū)域存在交集;
(12) 將E、E’進(jìn)行數(shù)據(jù)合并;
(13) ElseE歸入Es密度區(qū)域集合中;
(14)Else
(15) 更新p點(diǎn)2R領(lǐng)域內(nèi)所有p’屬性為visited;
(16)Until原始數(shù)據(jù)中數(shù)據(jù)點(diǎn)p均為visited;
下面給出密度區(qū)域劃分算法中計(jì)算區(qū)域面積Area的詳細(xì)過(guò)程:①借助滾球法獲取區(qū)域的邊界信息(點(diǎn)集構(gòu)成的區(qū)域邊界鏈);②依據(jù)獲取的區(qū)域邊界信息借助矢量積求解區(qū)域面積。
通常做法為先通過(guò)耳切法等[14]將不規(guī)則多邊形進(jìn)行三角劃分,分割成n個(gè)大小各異的三角形,通過(guò)累加分割后的各個(gè)三角形的面積得到最后的多邊形面積。其缺點(diǎn)是隨著邊界點(diǎn)的增加,會(huì)增長(zhǎng)三角劃分的復(fù)雜度,計(jì)算過(guò)程亦會(huì)非常繁瑣。為了簡(jiǎn)化操作快速獲取任意多邊形的面積,本文采取先對(duì)多邊形Ω建立矢量圖,如圖1所示,對(duì)相鄰的兩個(gè)邊界點(diǎn)所組成的有向矢量三角形根據(jù)矢量外積計(jì)算其矢量面積,最后累加所有矢量三角形面積值,從而求出整個(gè)多邊形面積。具體多邊形面積計(jì)算公式推導(dǎo)過(guò)程請(qǐng)參見參考文獻(xiàn)[15]。
圖1 矢量圖
處理求解多邊形邊界點(diǎn)問題掃描法、MelKman等算法是常用的算法,其特點(diǎn)是簡(jiǎn)潔快速,缺點(diǎn)也十分突出,其主要用來(lái)處理凸包邊界點(diǎn)求解,而對(duì)于求解任意形狀的簇包其算法表現(xiàn)過(guò)于粗糙,誤差較大,無(wú)法取得理想邊界點(diǎn)效果。在本文提出的算法中,精準(zhǔn)獲取區(qū)域邊界鏈?zhǔn)呛诵膯栴},因此,本文提出一種獲取任意簇包邊界點(diǎn)算法:滾球法。
核心思想是用一個(gè)初始值為R的矢量圓從區(qū)域的初始點(diǎn)不斷迭代滾動(dòng),每次滾動(dòng)在區(qū)域中首次觸碰的數(shù)據(jù)點(diǎn)視作該區(qū)域下一邊界點(diǎn),當(dāng)矢量圓再次回到初始點(diǎn)時(shí)視作迭代滾動(dòng)完成,該區(qū)域的邊界點(diǎn)集由矢量圓在迭代滾動(dòng)過(guò)程中觸碰的所有數(shù)據(jù)點(diǎn)所構(gòu)成。
圖2 釘群
圖3 邊界點(diǎn)F
極坐標(biāo)排序:對(duì)點(diǎn)集中的點(diǎn)建立以起點(diǎn)O和初始方向n的逆時(shí)針排序的新點(diǎn)集。
向量叉積:其結(jié)果可以用以描述的為兩個(gè)向量的相對(duì)關(guān)系,以為向量a、b為例,計(jì)算公式為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軸方向最小值點(diǎn)p作為邊界鏈初始點(diǎn),并加入邊界鏈boundary中;
(3)Do
(4)If boundary size 等于1
(5) 初始化邊界點(diǎn)p點(diǎn)2R-領(lǐng)域點(diǎn)集E;
(6) 采用p點(diǎn)-X軸方向作為極坐標(biāo)排序所需的基準(zhǔn)向量,對(duì)點(diǎn)集E中的點(diǎn)進(jìn)行極坐標(biāo)排序;
(7) ForEach 點(diǎn)集E中點(diǎn)p’;
(8) 以pp’為弦作圓O;
(9) If 圓O點(diǎn)集、點(diǎn)集E不存在交集;
(10) 點(diǎn)p’作為下一邊界點(diǎn)歸入boundary中;
(11)Else boundary size 大于 1;
(12) ForEach有向邊界鏈boundary
(13) 獲取最后歸入邊界鏈boundary中的點(diǎn)p、p’;
(14) 初始化邊界點(diǎn)p點(diǎn)2R-領(lǐng)域點(diǎn)集E;
(15) 以pp’方向?yàn)榛鶞?zhǔn)向量,對(duì)點(diǎn)集E重復(fù)(6)-(10)操作;
(16)Until無(wú)下一邊界點(diǎn) or 下一邊界點(diǎn)為初始邊界點(diǎn)p;
在上文中,給出了針對(duì)降低數(shù)據(jù)冗余度,解決數(shù)據(jù)源中帶有重復(fù)性質(zhì)的數(shù)據(jù)比例過(guò)高的問題本文的解決方案,并給出了對(duì)應(yīng)的密度區(qū)域劃分算法的思想與具體步驟。下面對(duì)本文提出的算法結(jié)合具體的案例,對(duì)其實(shí)際可行性做更為詳細(xì)的論證。
為了更為全面的驗(yàn)證其對(duì)不同數(shù)據(jù)都能實(shí)現(xiàn)有效的壓縮存儲(chǔ),本文采用了GSP地理信息數(shù)據(jù)與路由表兩種數(shù)據(jù)屬性截然不同的數(shù)據(jù)源。GPS數(shù)據(jù)源為現(xiàn)實(shí)車輛行駛軌跡真實(shí)數(shù)據(jù),其數(shù)據(jù)屬性表現(xiàn)為會(huì)自主呈現(xiàn)出聚集效應(yīng),是符合本文思想的理想數(shù)據(jù);路由數(shù)據(jù)的數(shù)據(jù)屬性則會(huì)呈現(xiàn)出傳統(tǒng)壓縮算法更善于處理的大量重復(fù)字符(字符串)。兩種數(shù)據(jù)理論都可采用本文提出的密度區(qū)域劃分?jǐn)?shù)據(jù)壓縮策略進(jìn)行高效壓縮存儲(chǔ)。
本文第一個(gè)實(shí)驗(yàn)驗(yàn)證采用的是出租車車輛軌跡數(shù)據(jù),對(duì)市區(qū)一萬(wàn)多輛出租車(源自微軟亞洲研究院)7天的車輛行使軌跡GPS數(shù)據(jù),以每輛車為單位,每5 s采集一次GPS地理位置信息,最終形成的車輛GPS行為軌跡信息,以時(shí)間作為橫軸坐標(biāo)參考,呈現(xiàn)出線性分布。具體數(shù)據(jù)見表1,包含了車輛的ID號(hào)(不是車牌號(hào))、行駛的日期、時(shí)間、車輛經(jīng)緯度信息。
表1 車輛行駛軌跡數(shù)據(jù)字段
2.1.1 車輛軌跡GPS數(shù)據(jù)分析與壓縮
按天為基本單位,使用本文密度區(qū)域劃分算法對(duì)數(shù)據(jù)集做處理,將數(shù)據(jù)集中車輛GPS信息高度密集的區(qū)域從原始數(shù)據(jù)集中進(jìn)行抽離,形成孤立的密集區(qū)。如圖5中密集區(qū)域所示,每一個(gè)密集區(qū)其代表的是實(shí)際含義為車輛高頻率聚集疊加,內(nèi)部車輛軌跡信息高度重復(fù)。
圖5 高密度區(qū)域
針對(duì)抽離的高密度區(qū),內(nèi)部大量重復(fù)的車輛GPS軌跡信息對(duì)描述此區(qū)域高密度特性而言是沒有必要重復(fù)存儲(chǔ)的,是對(duì)寶貴的存儲(chǔ)空間的浪費(fèi)。因此,基于本文去除密集區(qū)域重復(fù)信息的思想,對(duì)此密集區(qū),利用本文提出的算法,只保留可以反饋密集區(qū)基本樣貌信息的臨界數(shù)據(jù),舍棄內(nèi)部重復(fù)疊加的車輛GPS信息,減小對(duì)存儲(chǔ)空間的壓力。如圖6所示。
圖6 去除重復(fù)數(shù)據(jù)
針對(duì)每一個(gè)劃分出的高密度區(qū)域,只對(duì)其保存根據(jù)本文算法得到的邊界鏈與區(qū)域中心數(shù)據(jù),和區(qū)域內(nèi)部的時(shí)間散列數(shù)據(jù)(去除內(nèi)部重復(fù)GPS數(shù)據(jù)后,區(qū)域內(nèi)的時(shí)間值變化失去線性規(guī)律),基于基本統(tǒng)計(jì)的車輛ID信息(即車輛ID疊加重復(fù)的次數(shù)),最終壓縮處理后的數(shù)據(jù)存儲(chǔ)格式見表2。
表2 密度區(qū)域數(shù)據(jù)樣例
時(shí)間值分布,如圖7所示。
圖7 時(shí)間值分布
2.1.2 車輛軌跡GPS數(shù)據(jù)的恢復(fù)
數(shù)據(jù)恢復(fù)時(shí),基于密集區(qū)高度密集特性,可采用近似于均勻分布的數(shù)據(jù)散列方式,圍繞保留的區(qū)域中心,在區(qū)域邊界內(nèi)散列鋪滿整個(gè)區(qū)域,復(fù)原密集區(qū)數(shù)據(jù)樣貌。具體方式,借助射線法判斷復(fù)原的GPS數(shù)據(jù)是否在邊界鏈內(nèi),利用保留的車輛ID、車輛ID疊加次數(shù)、區(qū)域內(nèi)車輛部行駛時(shí)間信息,進(jìn)行數(shù)據(jù)拼接,還原車輛完成軌跡GPS信息,進(jìn)而真實(shí)還原整個(gè)抽離的密集區(qū)車輛信息疊加分布信息。
完整數(shù)據(jù),如圖8所示。
圖8 完整數(shù)據(jù)
2.1.3 空間點(diǎn)與任意不規(guī)則多邊形位置判定
判定點(diǎn)與任意不規(guī)則多邊形的位置關(guān)系有多種方式,其中射線法是行為有效最為簡(jiǎn)單直接的一種校驗(yàn)方法。其通過(guò)將待校驗(yàn)的點(diǎn)分別向兩側(cè)做水平射線,分別判斷左右射線與不規(guī)則多邊形交集信息,如圖9所示,兩側(cè)射線均與此多邊形存在奇數(shù)個(gè)交點(diǎn),則說(shuō)此點(diǎn)位于多邊形內(nèi)部。
圖9 射線法
本文第二個(gè)實(shí)驗(yàn)采用美國(guó)俄勒岡大學(xué)路由查看項(xiàng)目部分路由數(shù)據(jù)作為數(shù)據(jù)源。
2.2.1 路由數(shù)據(jù)介紹
互聯(lián)網(wǎng)中通信兩端在進(jìn)行交互時(shí),其大概率需跨局域網(wǎng)進(jìn)行交互,此時(shí)需要進(jìn)行傳輸路徑擇優(yōu)選擇,路由其扮演的是跨局域網(wǎng)交互傳輸路徑選擇與描述角色(具體由AS自治系統(tǒng)(autonomous system)構(gòu)成了此跨局域網(wǎng)傳輸路徑),本文采用的路由信息數(shù)據(jù)就是多個(gè)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ū)域挖掘
采用無(wú)向圖的方式將彼此存在跳轉(zhuǎn)關(guān)系的AS系統(tǒng)進(jìn)行雙向連接,更為直觀地展現(xiàn)AS系統(tǒng)之間的交互關(guān)系,如圖10所示。
圖10 AS無(wú)向圖
互聯(lián)網(wǎng)中每秒都存在著極高頻率的交互動(dòng)作,而AS系統(tǒng)是有限的,任意相鄰的兩個(gè)AS系統(tǒng)之間都在進(jìn)行極高頻率的重復(fù)跳轉(zhuǎn),其在數(shù)據(jù)源中的表現(xiàn)為某一條跳轉(zhuǎn)路徑以極高的頻率被重復(fù)存儲(chǔ)。以下圖為例,17974-7713跳轉(zhuǎn)路徑存儲(chǔ)了3503次,路徑3549-3356AS跳轉(zhuǎn)路徑存儲(chǔ)了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ū)域劃分算法,在操作過(guò)程中,將路由數(shù)據(jù)集中的跳轉(zhuǎn)路徑視為一個(gè)二維點(diǎn),則可將整個(gè)路由數(shù)據(jù)集視為類似車輛GPS性質(zhì)的二維點(diǎn)集數(shù)據(jù)包,初始面積值取1,將原始數(shù)據(jù)集中大量存在的由眾多高頻率AS系統(tǒng)構(gòu)成的局域高密集子網(wǎng)區(qū)域進(jìn)行抽離。根據(jù)數(shù)據(jù)表現(xiàn),每個(gè)抽離的局域高密集子網(wǎng)區(qū)域具備以下特點(diǎn):①局域高密集子網(wǎng)區(qū)域AS跳轉(zhuǎn)路徑重復(fù)率極高;②局域高密集子網(wǎng)區(qū)域AS系統(tǒng)個(gè)數(shù)數(shù)量不高,表現(xiàn)為AS無(wú)向圖結(jié)構(gòu)不復(fù)雜;③每個(gè)AS系統(tǒng)編號(hào)都由16 bite組成,基于此構(gòu)建的AS系統(tǒng)跳轉(zhuǎn)路徑更長(zhǎng)。
2.2.3 路由數(shù)據(jù)高密度子網(wǎng)區(qū)域數(shù)據(jù)壓縮存儲(chǔ)與恢復(fù)
從數(shù)據(jù)存儲(chǔ)的角度進(jìn)行分析,針對(duì)抽離出的局域高密集子網(wǎng)區(qū)域中的跳轉(zhuǎn)路徑進(jìn)行無(wú)條件完全存儲(chǔ),可視為是對(duì)存儲(chǔ)空間的浪費(fèi)。由于AS自治系統(tǒng)編號(hào)具有唯一性的特性,在對(duì)抽離出的局域高密集子網(wǎng)區(qū)域進(jìn)行壓縮存儲(chǔ)時(shí),其內(nèi)部的AS系統(tǒng)編號(hào)不可直接進(jìn)行模糊擦除,因此,對(duì)每一個(gè)局域高密集子網(wǎng)區(qū)域建立由其內(nèi)部AS系統(tǒng)編號(hào)構(gòu)建的矩陣,借用占位符的概念,利用密集區(qū)域內(nèi)部跳轉(zhuǎn)路徑在矩陣中的位置信息進(jìn)行占位替換,減小整個(gè)密集區(qū)的重新信息,減小對(duì)存儲(chǔ)空間的壓力。
采集局域高密集子網(wǎng)區(qū)域中的AS系統(tǒng)編號(hào),進(jìn)行根據(jù)編號(hào)在區(qū)域內(nèi)出現(xiàn)的頻率進(jìn)行自然排序構(gòu)建AS編號(hào)矩陣,在密集區(qū)域中(見表3),對(duì)每一對(duì)跳轉(zhuǎn)路徑在矩陣中進(jìn)行尋址,用自然數(shù)標(biāo)記此跳轉(zhuǎn)路徑在矩陣中的位置,進(jìn)行占位替換。表4為處理后的壓縮文件文件。數(shù)據(jù)恢復(fù)時(shí),構(gòu)建矩陣模型,依據(jù)壓縮文件中記錄的占位符等信息讀取在矩陣中位置信息,進(jìn)行AS系統(tǒng)編號(hào)恢復(fù),進(jìn)而恢復(fù)整個(gè)局域高密集子網(wǎng)區(qū)域。
表4 壓縮后的路由存儲(chǔ)文件
數(shù)據(jù)壓縮的性能指標(biāo)主要是壓縮率與壓縮速度,針對(duì)于本文所采用的兩種測(cè)試數(shù)據(jù)集本身都不足夠大的情況,這里主要討論壓縮率。壓縮率的計(jì)算公式如下。在數(shù)值上,壓縮率越小代表算法的壓縮性能越好
對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析(見表5和表6),從整體上來(lái)看,基于本文提出的數(shù)據(jù)壓縮策略下的密度區(qū)域劃分算法相較傳統(tǒng)的LZW算法在壓縮率上表現(xiàn)更好,尤其是GPS測(cè)量地理信息數(shù)據(jù)更能體現(xiàn)文本的思想,不僅局限于去除重復(fù)的車輛ID、日期等重復(fù)字符(字符串),更去除了篩選出的高密度區(qū)域中具有重復(fù)屬性的數(shù)據(jù),相較之下路由表數(shù)據(jù)由于無(wú)法像GPS數(shù)據(jù)完全去除篩選出的高密度區(qū)域中重復(fù)屬性數(shù)據(jù),壓縮率有所降低。結(jié)合兩種數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明,相較于傳統(tǒng)的數(shù)據(jù)壓縮算法,本文提出的數(shù)據(jù)壓縮策略對(duì)數(shù)據(jù)的靈活性更高,數(shù)據(jù)適用性更好。
表5 GPS數(shù)據(jù)
表6 路由數(shù)據(jù)
本文通過(guò)對(duì)現(xiàn)有的數(shù)據(jù)壓縮存儲(chǔ)策略的分析,提出一種基于密度區(qū)域劃分,挖掘原始數(shù)據(jù)中高密度區(qū)域,去除高密度區(qū)域中包含的重復(fù)性質(zhì)數(shù)據(jù),以達(dá)到降低數(shù)據(jù)冗余度實(shí)現(xiàn)數(shù)據(jù)源壓縮的目的。給出針對(duì)各種數(shù)據(jù)具有普適性的數(shù)據(jù)密度區(qū)域劃分算法,以提取數(shù)據(jù)中的高密度區(qū)域。并選取了GPS地理信息與路由表兩種數(shù)據(jù)屬性完全不同數(shù)據(jù)源對(duì)本文提出的算法進(jìn)行了驗(yàn)證。實(shí)現(xiàn)結(jié)果不僅驗(yàn)證了算法的可靠性和壓縮策略的可行性與有效性,更進(jìn)一步表明了本文提出的數(shù)據(jù)壓縮策略相對(duì)于傳統(tǒng)的數(shù)據(jù)壓縮策略在壓縮率與數(shù)據(jù)適用性上更具優(yōu)勢(shì),更加靈活。