趙會群,李春良
(北方工業(yè)大學(xué) 計算機(jī)學(xué)院,北京 100144)
在傳統(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ù)壓縮的目的。
篩選數(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ū)域面積。
通常做法為先通過耳切法等[14]將不規(guī)則多邊形進(jìn)行三角劃分,分割成n個大小各異的三角形,通過累加分割后的各個三角形的面積得到最后的多邊形面積。其缺點是隨著邊界點的增加,會增長三角劃分的復(fù)雜度,計算過程亦會非常繁瑣。為了簡化操作快速獲取任意多邊形的面積,本文采取先對多邊形Ω建立矢量圖,如圖1所示,對相鄰的兩個邊界點所組成的有向矢量三角形根據(jù)矢量外積計算其矢量面積,最后累加所有矢量三角形面積值,從而求出整個多邊形面積。具體多邊形面積計算公式推導(dǎo)過程請參見參考文獻(xiàn)[15]。
圖1 矢量圖
處理求解多邊形邊界點問題掃描法、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;
在上文中,給出了針對降低數(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)行高效壓縮存儲。
本文第一個實驗驗證采用的是出租車車輛軌跡數(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 射線法
本文第二個實驗采用美國俄勒岡大學(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 壓縮后的路由存儲文件
數(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ù)
本文通過對現(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)勢,更加靈活。