軌跡流數(shù)據(jù)清洗及附加語(yǔ)義信息的方法研究

(云南財(cái)經(jīng)大學(xué) 云南 昆明 650000)

一、流數(shù)據(jù)清洗的背景

數(shù)據(jù)清洗是數(shù)據(jù)挖掘的第一步，其質(zhì)量結(jié)果直接關(guān)系到模型效果和最終結(jié)論。流數(shù)據(jù)清洗的任務(wù)是為了解決流數(shù)據(jù)中的“臟數(shù)據(jù)”：噪聲數(shù)據(jù)和重復(fù)值[8]、缺失值[9]和異常值[10]。清洗流數(shù)據(jù)一般采用以下幾種方法：基于規(guī)則約束的流數(shù)據(jù)清洗[1]、基于統(tǒng)計(jì)方法的流數(shù)據(jù)清洗[2]和基于統(tǒng)計(jì)的數(shù)據(jù)清洗方法[3]。

現(xiàn)如今在流數(shù)據(jù)清洗方面還是存在一定的不足：沒有考慮到清洗后的數(shù)據(jù)保存問題，清洗后的流數(shù)據(jù)體積任然較大且保存代價(jià)較高；清洗完的數(shù)據(jù)沒有附著語(yǔ)義信息，在用戶的角度來看依舊是復(fù)雜的。在這樣的情況下，對(duì)流數(shù)據(jù)清洗進(jìn)行研究是必要的，在壓縮數(shù)據(jù)體積的同時(shí)保證數(shù)據(jù)的質(zhì)量、清洗完的數(shù)據(jù)附帶了語(yǔ)義信息能提高數(shù)據(jù)挖掘算法的效率，這是有意義也是有價(jià)值的。國(guó)內(nèi)外針對(duì)數(shù)據(jù)清洗的相關(guān)文獻(xiàn)并不是很多，針對(duì)流數(shù)據(jù)清洗的文獻(xiàn)更是少之又少。普遍都是一份數(shù)據(jù)對(duì)應(yīng)一種清洗方法，沒有適用于某一類或者某幾類數(shù)據(jù)的清洗方法。本研究提出的方法，是將軌跡研究中提取停點(diǎn)和移動(dòng)的方法用于流數(shù)據(jù)的清洗上，幫助修復(fù)異常值、補(bǔ)充缺失值和剔除冗余值，從而達(dá)到數(shù)據(jù)清洗的目的；清洗完的數(shù)據(jù)具備了語(yǔ)義信息，初步的行為動(dòng)態(tài)分析不需要依賴數(shù)據(jù)挖掘算法。該方法可適用于多種數(shù)據(jù)，可以為日后的相關(guān)研究提供一些參考。

在實(shí)際應(yīng)用中壓縮數(shù)據(jù)的體積有利于降低數(shù)據(jù)保存的成本，并且在此基礎(chǔ)上盡可能的保證信息的完整，有利于實(shí)現(xiàn)多次訪問、挖掘數(shù)據(jù)，從而提煉出更多的有用價(jià)值。更好的進(jìn)行缺失值估計(jì)、異常值修復(fù)在一些對(duì)數(shù)據(jù)完整性要求很高的應(yīng)用中是極其重要的[7]，為此進(jìn)行流數(shù)據(jù)清洗方法的研究也是必要的。數(shù)據(jù)清洗是數(shù)據(jù)挖掘的第一步，為更好的幫助用戶運(yùn)用這些數(shù)據(jù)，以一種更直觀的形式展現(xiàn)的數(shù)據(jù)會(huì)有助于用戶的理解。擬提出的方法在上述應(yīng)用層面會(huì)有一個(gè)良好的效果，為后續(xù)數(shù)據(jù)挖掘奠定基礎(chǔ)。

二、語(yǔ)義信息抽取的背景

軌跡數(shù)據(jù)和地理數(shù)據(jù)在空間上是重疊的，為準(zhǔn)確的分析軌跡數(shù)據(jù)，使其更直觀明了，通常會(huì)從地理信息中抽取出相對(duì)應(yīng)的語(yǔ)義信息進(jìn)行附著。Brakatsoulas S等人指出軌跡數(shù)據(jù)的分析包括空間，非空間和軌跡數(shù)據(jù)的整合。其中整合與具體的應(yīng)用場(chǎng)景是相結(jié)合的，需提前指定與軌跡分析相關(guān)的空間特征類型(例如，旅館，旅游地點(diǎn))[4]。Alvares L O等指出一些軌跡數(shù)據(jù)分析研究存在的問題便是缺乏語(yǔ)義信息的分析，為獲得更多有價(jià)值的信息需要依靠更復(fù)雜的查詢，如數(shù)據(jù)挖掘算法[5]。但在現(xiàn)實(shí)情況中，數(shù)據(jù)中的移動(dòng)行為等問題需要通過結(jié)合軌跡和它們的語(yǔ)義信息來回答。Bogorny V等向我們展示了在不添加語(yǔ)義信息和添加語(yǔ)義信息兩種情況下同一個(gè)查詢的結(jié)果。實(shí)驗(yàn)表明在沒有語(yǔ)義的軌跡中，軌跡與相關(guān)地理信息對(duì)象的關(guān)系需要進(jìn)行多次的重復(fù)計(jì)算，效率較低[6]。而添加了抽取到的語(yǔ)義信息的軌跡在可視化圖表中可清晰看出客戶的行為動(dòng)態(tài)，無需再次查找計(jì)算。

三、軌跡流數(shù)據(jù)清洗及附加語(yǔ)義信息的方法

(一)研究目標(biāo)

研究提出一種新的使用于軌跡流數(shù)據(jù)的清洗方法以達(dá)到以下幾點(diǎn)要求：

1.有效壓縮清洗后的數(shù)據(jù)體積，降低數(shù)據(jù)保存成本。

2.清洗完成的數(shù)據(jù)需附帶語(yǔ)義信息，可初步直觀明了的看出軌跡動(dòng)態(tài)及數(shù)據(jù)熱點(diǎn)。

3.以上兩點(diǎn)皆可以以圖表的形式展現(xiàn)出來該方法的優(yōu)勢(shì)性和實(shí)用性。

(二)主要內(nèi)容

現(xiàn)有研究并不能完全做到及時(shí)抓取流數(shù)據(jù)的有效信息，為降低數(shù)據(jù)保存的成本，本研究采用一種具有壓縮效果的方法，實(shí)驗(yàn)于真實(shí)的商場(chǎng)室內(nèi)軌跡流數(shù)據(jù)集，可有效減少數(shù)據(jù)體積并且在一定程度上保護(hù)了有效數(shù)據(jù)不被丟失，可有效保存數(shù)據(jù)。

數(shù)據(jù)清洗是對(duì)數(shù)據(jù)進(jìn)行重新審查和校驗(yàn)的過程，其任務(wù)是過濾那些不符合要求的數(shù)據(jù)。在本研究所用的商場(chǎng)軌跡流數(shù)據(jù)中，用戶的停留等行為會(huì)使得采集到的數(shù)據(jù)存在噪聲和重復(fù)值。本研究提出一種數(shù)據(jù)清洗方法，用于將軌跡數(shù)據(jù)和與應(yīng)用相關(guān)的地理信息進(jìn)行整合，從而去除噪聲及重復(fù)值。

缺失值估計(jì)在一些對(duì)數(shù)據(jù)完整性要求很高的應(yīng)用中是極其重要的。然而，當(dāng)前缺失值填充的算法主要針對(duì)整體修復(fù)，不適用于流數(shù)據(jù)，或者針對(duì)某領(lǐng)域數(shù)據(jù)無法推廣使用，且計(jì)算復(fù)雜性過高。目前尚無較好的適用于流數(shù)據(jù)的缺失值填充算法提出。據(jù)此本研究擬設(shè)計(jì)適用于流數(shù)據(jù)的缺失值填充及異常值修復(fù)的算法。

語(yǔ)義信息提取是對(duì)軌跡進(jìn)行一種語(yǔ)義補(bǔ)充，它表明原始軌跡可以進(jìn)一步的被劃分為語(yǔ)義片段，每個(gè)語(yǔ)義片段由它的開始時(shí)刻和結(jié)束時(shí)刻以及標(biāo)識(shí)這個(gè)片段的定義標(biāo)識(shí)值所表示。本研究所用到的語(yǔ)義，表示了地理空間特征類型(如超市，酒店，旅游景點(diǎn)等)，區(qū)別于傳統(tǒng)的流數(shù)據(jù)清洗方式，擬提出了一種流數(shù)據(jù)清洗方法，用于向數(shù)據(jù)添加語(yǔ)義信息，以便于在應(yīng)用領(lǐng)域中可以更直觀的進(jìn)行數(shù)據(jù)分析，幫助理解數(shù)據(jù)。

(三)研究方案

1.使用合適的圖像識(shí)別算法來識(shí)別商場(chǎng)地圖像素，將每個(gè)商店覆蓋的所有像素點(diǎn)放到各自的集合里。

2.針對(duì)輸入的軌跡流數(shù)據(jù)，使用SMOT算法提取停點(diǎn)和移動(dòng)。

停點(diǎn)：候選停點(diǎn)C定義為表示閉合的多邊形，它是真實(shí)平面中各地理坐標(biāo)的投影，是最小持續(xù)時(shí)間，是正實(shí)數(shù)。

移動(dòng)：在T的兩個(gè)停點(diǎn)之間的最大連續(xù)子軌跡;在T的起點(diǎn)和T的第一個(gè)停點(diǎn)之間的最大連續(xù)子軌跡;T的最后一個(gè)停點(diǎn)與終點(diǎn)之間的最大連續(xù)子軌跡T;如果T沒有停點(diǎn)，那就是軌跡T本身；這四種情形被定義為移動(dòng)。

SMOT算法思想：驗(yàn)證軌跡T的每個(gè)點(diǎn)是否與的幾何形狀相交。在肯定的情況下，查看交叉的持續(xù)時(shí)間是否大于等于給定的閾值。如果滿足上述條件，則將相交的候選停點(diǎn)視為停點(diǎn)，并記錄該停點(diǎn)。

3.判斷提取的停點(diǎn)和移動(dòng)是否屬于某商店像素點(diǎn)集合，如果是，則判斷該停點(diǎn)和移動(dòng)在這個(gè)商店里。并依據(jù)已經(jīng)確定的停點(diǎn)和移動(dòng)刪除噪點(diǎn)和重復(fù)點(diǎn)、修復(fù)異常值以及填補(bǔ)缺失值。

4.為清洗完成的數(shù)據(jù)附上語(yǔ)義信息，得到語(yǔ)義軌跡數(shù)據(jù)集。用其他的清洗方法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行清洗，比較驗(yàn)證算法的性能優(yōu)勢(shì)。

四、結(jié)束語(yǔ)

流數(shù)據(jù)有一個(gè)十分明顯的特點(diǎn)，那就是體積過于龐大。受存儲(chǔ)空間的限制，流數(shù)據(jù)在產(chǎn)生后必須及時(shí)有效的對(duì)信息進(jìn)行抓取，避免有效信息的丟失。但現(xiàn)有研究并不能完全做到及時(shí)抓取有效信息，為降低數(shù)據(jù)保存的成本，本文采用了一種具有壓縮效果的方法，可有效減少數(shù)據(jù)體積并且在一定程度上保護(hù)了有效數(shù)據(jù)不被丟失，可有效保存數(shù)據(jù)。經(jīng)過實(shí)驗(yàn)證明使用本文提出的方法清洗數(shù)據(jù)得到了較好的實(shí)驗(yàn)結(jié)果，數(shù)據(jù)體積成功壓縮且有價(jià)值的數(shù)據(jù)也被成功的保存下來，附著語(yǔ)義信息的數(shù)據(jù)可以被直觀明了的表現(xiàn)出來。但是由于流數(shù)據(jù)的特殊性質(zhì)，在方法效率上本文提出的方法還有著很大的不足。該方法運(yùn)行時(shí)間較長(zhǎng)且對(duì)存儲(chǔ)空間也有一定的要求，今后工作的方向?qū)⒅τ诖瞬蛔阒帯?/p>