高麗峰，高麗萍，李夢(mèng)穎

一種對(duì)移動(dòng)Web訪問(wèn)日志中層次數(shù)據(jù)的提取方法

高麗峰1，高麗萍2，李夢(mèng)穎1

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；2.北京南瑞智芯微電子科技有限公司，昌平102200）

提出一種基于可視分析的層次數(shù)據(jù)提取方法，實(shí)現(xiàn)對(duì)移動(dòng)Web訪問(wèn)日志中層次數(shù)據(jù)的精確高效提取。通過(guò)數(shù)據(jù)樣本建立數(shù)據(jù)字典，確保沒(méi)有信息遺漏，并根據(jù)字典統(tǒng)計(jì)樣本并記錄相關(guān)數(shù)據(jù)，建立數(shù)據(jù)網(wǎng)絡(luò)權(quán)重圖。可視化該網(wǎng)絡(luò)，并以可視分析的方法確定數(shù)據(jù)間的層次結(jié)構(gòu)，并以此構(gòu)建數(shù)據(jù)層次結(jié)構(gòu)有向圖，結(jié)合結(jié)點(diǎn)權(quán)重進(jìn)行拓?fù)渑判?，使用得到的拓?fù)湫蛄懈聰?shù)據(jù)字典。將待提取日志與數(shù)據(jù)字典中的關(guān)鍵詞依次進(jìn)行正則匹配，并保存提取結(jié)果。對(duì)移動(dòng)Web訪問(wèn)日志中User-Agent域中的瀏覽器信息進(jìn)行數(shù)據(jù)提取，實(shí)驗(yàn)表明該方法能夠很好地確定層次數(shù)據(jù)間的層次關(guān)系，實(shí)現(xiàn)數(shù)據(jù)的精確提取。

數(shù)據(jù)提取；可視分析；層次數(shù)據(jù)；移動(dòng)Web訪問(wèn)日志；User-Agent

四川省科技廳項(xiàng)目（No.2013GZ0015）

0　引言

隨著大數(shù)據(jù)的迅速發(fā)展，日志文件得到越來(lái)越多人的青睞。通過(guò)對(duì)日志文件的分析，可以挖掘出用戶的若干行為，統(tǒng)計(jì)分析用戶的愛好、習(xí)慣等屬性，以及這些屬性的地域性、時(shí)域性等。從而可以幫助開發(fā)者針對(duì)用戶喜好開發(fā)對(duì)應(yīng)的軟件，使得生活更便捷；幫助設(shè)備提供者設(shè)計(jì)更多人性化的設(shè)施。

日志文件有如下特點(diǎn)：實(shí)時(shí)性，日志文件隨著用戶訪問(wèn)不斷產(chǎn)生，存在明顯的時(shí)空局域性；異構(gòu)性，日志文件結(jié)構(gòu)不規(guī)范，數(shù)據(jù)多呈半結(jié)構(gòu)化或無(wú)結(jié)構(gòu)；高內(nèi)涵，日志文件包含用戶一次訪問(wèn)以及所使用設(shè)備的所有相關(guān)信息。此外，移動(dòng)Web訪問(wèn)日志文件的屬性相對(duì)更多，主要表現(xiàn)在IP、User-Agent等域。該域中，涉及到移動(dòng)訪問(wèn)設(shè)備的品牌、操作系統(tǒng)，以及瀏覽器等信息。

然而，一些域中的一條記錄可能會(huì)出現(xiàn)代表某一屬性的若干字段；這些同時(shí)出現(xiàn)的字段相互聯(lián)系，又有一定的從屬關(guān)系；真正代表該記錄該屬性的字段只有其中一個(gè)。我們定義有從屬關(guān)系的同一屬性數(shù)據(jù)為層次數(shù)據(jù)，而如何從這些層次數(shù)據(jù)中提取出具有代表性的數(shù)據(jù)這一問(wèn)題亟待解決。其中典型代表就是User-Agent域中瀏覽器數(shù)據(jù)的提取。通過(guò)移動(dòng)Web訪問(wèn)日志中的User-Agent域來(lái)精確識(shí)別移動(dòng)設(shè)備，尤其是明晰該設(shè)備使用的瀏覽器，對(duì)于網(wǎng)頁(yè)適配、市場(chǎng)調(diào)研等具有重要意義。瀏覽器信息提取需要考慮：若干瀏覽器使用同一個(gè)搜索引擎；雙核瀏覽器的開發(fā)使得同一個(gè)瀏覽器可能在不同情況下對(duì)應(yīng)不同的搜索引擎；為了更好的兼容性，瀏覽器之間經(jīng)常相互偽裝，使得在一條User-Agent域中往往會(huì)出現(xiàn)多個(gè)瀏覽器信息。

基于上述分析，對(duì)于層次數(shù)據(jù)（如User-Agent域中瀏覽器信息）的提取難點(diǎn)在于確定數(shù)據(jù)（瀏覽器）間的層次結(jié)構(gòu)及提取順序。本文提出基于可視分析的層級(jí)數(shù)據(jù)提取方法來(lái)解決上述問(wèn)題，該方法同樣適應(yīng)其他領(lǐng)域?qū)哟螖?shù)據(jù)的提取。首先，統(tǒng)計(jì)樣本中所有字段信息，建立相關(guān)數(shù)據(jù)字典；其次，通過(guò)數(shù)據(jù)字典對(duì)樣本數(shù)據(jù)進(jìn)行重新提取，并記錄數(shù)據(jù)間的相關(guān)關(guān)系和出現(xiàn)頻次，生成對(duì)應(yīng)的網(wǎng)絡(luò)權(quán)重圖，即可視分析模型；再次，對(duì)網(wǎng)絡(luò)權(quán)重圖進(jìn)行分析，完成數(shù)據(jù)層級(jí)結(jié)構(gòu)有向圖；結(jié)合權(quán)重，對(duì)數(shù)據(jù)層級(jí)結(jié)構(gòu)有向圖進(jìn)行拓?fù)渑判?，以最終排序結(jié)構(gòu)更新數(shù)據(jù)字典；最后，將要提取記錄與數(shù)據(jù)字典依次對(duì)應(yīng)，進(jìn)行數(shù)據(jù)提取。

1　相關(guān)工作

本文以層次數(shù)據(jù)——User-Agent域中瀏覽器信息的提取為例，介紹對(duì)移動(dòng)Web訪問(wèn)日志中層次數(shù)據(jù)的提取方法，即基于可視分析的層次數(shù)據(jù)提取方法。本節(jié)主要對(duì)User-Agent、數(shù)據(jù)提取、可視分析背景知識(shí)進(jìn)行介紹。

1.1User-Agent

User Agent，即用戶代理，簡(jiǎn)稱UA，是HTTP協(xié)議中的一部分，屬于頭域的組成部分[1~2]。它是一個(gè)特殊字符串頭，是一種向訪問(wèn)網(wǎng)站提供訪問(wèn)者所使用的瀏覽器類型及版本、操作系統(tǒng)及版本、瀏覽器內(nèi)核等信息的標(biāo)識(shí)。瀏覽器的UA字串的標(biāo)準(zhǔn)格式[3]：瀏覽器標(biāo)識(shí)（操作系統(tǒng)標(biāo)識(shí);加密等級(jí)標(biāo)識(shí);瀏覽器語(yǔ)言）渲染引擎標(biāo)識(shí)版本信息。移動(dòng)Web訪問(wèn)日志文件中的User-Agent域，還包括了使用設(shè)備的品牌以及相關(guān)型號(hào)等信息，如下：

MQQBrowser/2.8（Nokia5235;SymbianOS/9.1Series60/ 3.0）

MQQBrowser/2.8：瀏覽器類型及版本；

（Nokia5235;SymbianOS/9.1 Series60/3.0）：該瀏覽器運(yùn)行系統(tǒng)的詳細(xì)信息，包括設(shè)備品牌及其型號(hào)、操作系統(tǒng)及其型號(hào)

User-Agent還可以進(jìn)行偽裝，如下程序，導(dǎo)致當(dāng)前User-Agent比較混亂，這對(duì)于瀏覽器的識(shí)別以及提取相關(guān)數(shù)據(jù)提出了挑戰(zhàn)。

Mozilla/5.0（Windows;U;Windows NT 5.2;en-US）AppleWebKit/534.10（KHTML,like Gecko）Chrome/8.0.558.0 Safari/534.10

Mozilla/5.0：用以指示與Mozilla排版引擎的兼容性

（Windows;U;Windows NT 5.2;en-US）：瀏覽器所運(yùn)行于的系統(tǒng)詳細(xì)信息

AppleWebKit/534.10：瀏覽器所使用的平臺(tái)（即搜索引擎及其版本號(hào)）

（KHTML,like Gecko）：瀏覽器平臺(tái)的細(xì)節(jié)（即希望得到為KHTML編寫的網(wǎng)頁(yè)，同時(shí)“像Gecko”那樣的）

Chrome/8.0.558.0：瀏覽器及其版本號(hào)

Safari/534.10：偽裝為Safari瀏覽器，以增加兼容性

1.2數(shù)據(jù)提取

數(shù)據(jù)提取是大多數(shù)計(jì)算機(jī)工作的基礎(chǔ)，包括數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等。數(shù)據(jù)來(lái)源范圍廣泛，但現(xiàn)在更多集中于電子信息，包括電子病歷[4]、網(wǎng)頁(yè)等[5]，而提取工具[6]以及提取方法也層出不窮，如DEBy[7]、FiVaTech[8]、CTVS[9]、ViDE[10]等。而大多數(shù)提取方法都是針對(duì)固定格式或者標(biāo)準(zhǔn)格式文件中的數(shù)據(jù)進(jìn)行提取的，例如HTML文檔、XML文件、JSON文件等。在進(jìn)行數(shù)據(jù)提取的過(guò)程中，需要結(jié)合文本標(biāo)簽或者特定的結(jié)構(gòu)格式，如果數(shù)據(jù)文件存在缺項(xiàng)、漏項(xiàng)的現(xiàn)象，則在提取過(guò)程中通過(guò)建立DOM tree，或者Hidden Markov Model[11]來(lái)解決。

移動(dòng)終端Web訪問(wèn)日志文件不是標(biāo)準(zhǔn)的HTML文件，沒(méi)有定義相關(guān)標(biāo)簽，而且數(shù)據(jù)信息是雜糅在一起，沒(méi)有明確的界限和順序，同時(shí)還有噪聲，使得數(shù)據(jù)文件不能很好地轉(zhuǎn)化為XML文件，因此上述方法并不能適用。此外，User-Agent域中的信息還存在各種兼容現(xiàn)象，對(duì)數(shù)據(jù)提取提出了更大的挑戰(zhàn)。

本文通過(guò)建立數(shù)據(jù)字典，獨(dú)立于程序之外，方便隨時(shí)修改，能夠更好地適應(yīng)市場(chǎng)需求。同時(shí)通過(guò)可視分析將數(shù)據(jù)間的層次結(jié)構(gòu)確定下來(lái)，則能夠解決瀏覽器偽裝等問(wèn)題。

1.3可視化與可視分析

可視化，即使用圖像來(lái)進(jìn)行信息交流[12]，其目的是洞悉蘊(yùn)含在數(shù)據(jù)中的現(xiàn)象和規(guī)律，較傳統(tǒng)方式更加直觀?？梢暬夹g(shù)可以很好地表示層次和網(wǎng)絡(luò)數(shù)據(jù)，其中關(guān)鍵是圖的繪制，常用的布點(diǎn)算法有經(jīng)典的力導(dǎo)引算法，如彈簧模型[13]、KK算法[14]、FR算法[15]、ODL[16~17]算法等，以及多尺度布局算法[18]。

網(wǎng)絡(luò)可視化作為一類重要的信息可視化技術(shù)，充分利用人類視覺(jué)感知系統(tǒng)，將網(wǎng)絡(luò)數(shù)據(jù)以圖形化方式展示出來(lái)，快速直觀地解釋及概覽網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)，可以輔助用戶認(rèn)識(shí)網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)，以挖掘隱藏在網(wǎng)絡(luò)內(nèi)部的有價(jià)值信息。

可視分析是信息可視化與科學(xué)可視化領(lǐng)域發(fā)展的產(chǎn)物，它借助于人類直覺(jué)的藝術(shù)和科學(xué)的數(shù)學(xué)推導(dǎo)，使用交互式用戶界面進(jìn)行模式挖掘、知識(shí)發(fā)現(xiàn)，以及分析推理等[19]?？梢暦治黾夹g(shù)為我們數(shù)據(jù)提供了一種直觀有效的方法，它將復(fù)雜的數(shù)據(jù)通過(guò)可視化的方式直觀地展示出來(lái)，并支持對(duì)結(jié)果的交互式篩選和瀏覽等操作，從而對(duì)數(shù)據(jù)進(jìn)行進(jìn)一步分析。

目前，可視分析已在天氣預(yù)報(bào)、數(shù)字城市、金融安全、社會(huì)網(wǎng)絡(luò)等國(guó)民經(jīng)濟(jì)和國(guó)防安全的各個(gè)領(lǐng)域得到應(yīng)用，如移動(dòng)日志文件的可視分析[20]，城市交通數(shù)據(jù)的可視分析[21~22]，蛋白質(zhì)相互作用的可視分析[23]等。

2　層次數(shù)據(jù)提取

每當(dāng)移動(dòng)終端訪問(wèn)網(wǎng)絡(luò)的時(shí)候，Web服務(wù)器都會(huì)將該終端的相關(guān)信息進(jìn)行記錄，以類似超文本傳輸協(xié)議的文本格式進(jìn)行存儲(chǔ)，形成Web訪問(wèn)日志，如下程序。其中，每條記錄以代表時(shí)間的長(zhǎng)整型數(shù)字開始，包含若干的域，且每條記錄域的個(gè)數(shù)和種類都不相同，可見移動(dòng)Web訪問(wèn)日志文件數(shù)據(jù)呈非結(jié)構(gòu)化。

1333967945[10.99.29.15:2157-〉10.99.192.13:2158] 10.138.150.32-〉10.0.0.172

GET/comm/v2/result.jsp?sid=AeJBkJkfNNG5_0KWIOb5v -CE&activeId=12&aId=5678&answer=1 HTTP/1.1

accept:application/vnd.wap.xhtml+xml,application/xml, text/vnd.wap.wml,text/html,application/xhtml+xml,image/jpeg;q= 0.5,image/png;q=0.5,image/gif;q=0.5,image/*;q=0.6,video/*,audio/*,*/*;q=0.6

user-agent:MQQBrowser/3.1/Adr（Linux;U;2.1-update1; zh-cn;GT-I5503 Build/ERE27;240*320）

referer:http://sq8.3g.qq.com/comm/v2/result.jsp?sid=Ae-JBkJkfNNG5_0KWIOb5v-CE&activeId=12&aId=5582&answer= 3

cookie:sd_userid=48481328000295684;sd_cookie_crttime=1328000295684;qq_mb_adv_special=-344946998| 1328187419173;pt=2;mtt_cache_ck=20120215191046; stock_uin=wi+MQ0+2xt47xQXiDr0YnyZ6ECM2EYfG;3g_last-LoginQq=907995;3g_csp=1333254835;info_lau=907995; appsd_mid=1904;softdown_mid=1904;match_mid=-1;softdown_pid=14;g_ut=2;info_index_att=1;icfa=content_rela;

其中User-Agent域中包含移動(dòng)終端設(shè)備品牌及型號(hào)、終端操作系統(tǒng)詳細(xì)信息，以及該次訪問(wèn)使用的瀏覽器及其細(xì)節(jié)。

數(shù)據(jù)提取主要包含4個(gè)模塊，分別為：①建立數(shù)據(jù)字典，形成數(shù)據(jù)網(wǎng)絡(luò)；②實(shí)現(xiàn)可視分析模型，辨析數(shù)據(jù)層次結(jié)構(gòu)；③結(jié)合權(quán)重進(jìn)行拓?fù)渑判?，更新?shù)據(jù)字典；④根據(jù)數(shù)據(jù)字典從日志文件中進(jìn)行數(shù)據(jù)提取，并將提取結(jié)果保存。處理流程如圖1所示，其中前三個(gè)模塊是數(shù)據(jù)提取的前期過(guò)程，也是重要組成部分。

圖1　數(shù)據(jù)提取流程

2.1構(gòu)建數(shù)據(jù)網(wǎng)絡(luò)

為了提取User-Agent域中的瀏覽器數(shù)據(jù)，需要建立關(guān)于瀏覽器信息的數(shù)據(jù)字典，數(shù)據(jù)字典獨(dú)立于程序之外，可以方便修改，能夠更好地適應(yīng)瀏覽器市場(chǎng)變化，具有更好的魯棒性。數(shù)據(jù)字典的建立和數(shù)據(jù)網(wǎng)絡(luò)的形成步驟如下：

（1）隨機(jī)收集足夠的移動(dòng)Web訪問(wèn)日志文件中的User-Agent域，形成User-Agent樣本數(shù)據(jù)，如下程序：

Mozilla/5.0（Linux;U;Android 2.3.7;zh-cn;HTC Wildfire S Build/GRI40）UC AppleWebKit/530+（KHTML,like Gecko）Mobile Safari/530

JUC（Linux;U;2.3.4;zh-cn;GN205;480*800）UCWEB7.9.3.103/139/32702

5233/SymbianOS/9.1 Series60/3.0

MQQBrowser/2.8（Nokia5250;SymbianOS/9.1Series60/ 3.0）

MAUI WAP Browser

Nokia2010/2.0（11.21）Profile/MIDP-2.1 Configuration/ CLDC-1.1

E63/SymbianOS/9.1 Series60/3.0

Mozilla/4.0（compatible;MSIE 6.0;Windows NT 5.1）

Lenovo-P50/S045 LMP/LML Release/2010.03.08 Profile/ MIDP2.0 Configuration/CLDC1.1

（2）提取樣本數(shù)據(jù)中的瀏覽器信息，并將提取到的信息寫入數(shù)據(jù)字典，具體過(guò)程如下：

Input:sample file of User-Agent

Output:data dictionary of browser

while（（record=sample.readLine（））!=null）{

//the sample file is not scanned over and the current lineis marked as record

if（（b instanceof browser）&&（record.contains（b））&&（!Dictionary.contains（b）））{

//there is some information about browser in record while it is not in the dictionary

dictionary.add（b）;

}

}

（3）依據(jù)數(shù)據(jù)字典，對(duì)樣本數(shù)據(jù)中的每一條記錄進(jìn)行重新提取，如表1所示。

表1　User-Agent域中瀏覽器信息統(tǒng)計(jì)表

將出現(xiàn)的瀏覽器作為結(jié)點(diǎn)n，將出現(xiàn)在同一條記錄中的點(diǎn)（n1，n2，…，nm）連線作為邊（e12，e13，…，e1m，e23，…，e（m-1）m），將其出現(xiàn)的次數(shù)映射成邊的權(quán)重w，建立數(shù)據(jù)網(wǎng)絡(luò)鄰接表T，如表1所示。瀏覽器的頻次是指在樣本中該瀏覽器出現(xiàn)的次數(shù)t；邊數(shù)指的是從該點(diǎn)出發(fā)有多少條邊，也就是和該瀏覽器有兼容等關(guān)系的瀏覽器的個(gè)數(shù)；邊的權(quán)重指的是該條邊出現(xiàn)的次數(shù)。

2.2辨析數(shù)據(jù)層次結(jié)構(gòu)

（1）數(shù)據(jù)網(wǎng)絡(luò)可視化

根據(jù)生成的網(wǎng)絡(luò)鄰接表，使用圓形布局生成網(wǎng)絡(luò)可視化視圖，如圖2（a）所示。圓形布局實(shí)現(xiàn)簡(jiǎn)單，能夠體現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)間的層次關(guān)系，但是對(duì)于其他網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征表現(xiàn)力度不強(qiáng)，適合我們初步觀察層次數(shù)據(jù)結(jié)構(gòu)。將邊的粗細(xì)映射成邊的權(quán)重，由于邊的權(quán)重變化范圍為1≤w≤527277，因此采用分段映射。在882193條邊中，出現(xiàn)4次以下的邊總共有23條，這些邊被認(rèn)為是噪聲點(diǎn)，去掉后如圖2（b）所示，可初窺其層次結(jié)構(gòu)。

（2）可視分析數(shù)據(jù)層次關(guān)系

在圖2中存在一些孤立的點(diǎn)，即度為0的結(jié)點(diǎn)，這些點(diǎn)所代表的瀏覽器與其他瀏覽器并無(wú)兼容關(guān)系，可以直接提取；考察分布在圓形外圍的結(jié)點(diǎn)，這些結(jié)點(diǎn)度為1，而且確實(shí)是剩余結(jié)點(diǎn)中層次最低的點(diǎn)，可以去掉。隨著點(diǎn)的減少，層次布局逐漸顯示其優(yōu)勢(shì)，可以更方便地觀察數(shù)據(jù)間的層次結(jié)構(gòu)，整個(gè)層次關(guān)系的分析類似于“拓?fù)渑判颉?，但?dāng)前的數(shù)據(jù)網(wǎng)絡(luò)圖是無(wú)向的，而且有環(huán)存在，這個(gè)過(guò)程需要人工干預(yù)，將層次低的點(diǎn)依次去掉，如圖3所示。在倒數(shù)第二步判斷中，由于safari出現(xiàn)次數(shù)t（nsafari）=765384，t（esafari-msie）=13，t（nsafari）·t（esafari-msie），因此我們認(rèn)為esafari-msie為噪聲，忽略不計(jì)，同時(shí)，eopera-maui-wapbrowser做類似處理。數(shù)據(jù)層次關(guān)系分析完畢。

圖2　數(shù)據(jù)網(wǎng)絡(luò)圖展示

表2　數(shù)據(jù)網(wǎng)絡(luò)鄰接表（部分）

圖3　數(shù)據(jù)層次關(guān)系可視分析

2.3更新數(shù)據(jù)字典

將已知的層次關(guān)系結(jié)構(gòu)繪制成有向的層次結(jié)構(gòu)網(wǎng)絡(luò)圖，如圖4所示。其中從上往下代表層次由低到高，并將瀏覽器出現(xiàn)的次數(shù)t映射其顏色透明度。此時(shí)對(duì)整個(gè)網(wǎng)絡(luò)圖進(jìn)行拓?fù)渑判?，?yōu)先選取出現(xiàn)頻次高的結(jié)點(diǎn)，這樣使得拓?fù)湫蛄兄蓄l次高的結(jié)點(diǎn)在前，頻次低的結(jié)點(diǎn)在后，可以在之后的數(shù)據(jù)提取中有效提升提取效率。

使用排序好的拓?fù)湫蛄懈聰?shù)據(jù)字典，作為后續(xù)數(shù)據(jù)提取的依據(jù)，如圖5所示。

圖4　層次結(jié)構(gòu)有向圖

圖5　拓?fù)渑判蚪Y(jié)構(gòu)

2.4保存提取結(jié)構(gòu)

從數(shù)據(jù)字典中讀取拓?fù)渑判蚪Y(jié)果，依次取字典中的元素與待提取的日志文件中User-Agent域進(jìn)行正則匹配，當(dāng)匹配成功時(shí)，即返回當(dāng)前關(guān)鍵詞，即所需提取結(jié)果，將該結(jié)果保存到數(shù)據(jù)庫(kù)中，如圖6所示。對(duì)于提取不成功的字段，我們將在統(tǒng)一分析后，丟棄或者更新數(shù)據(jù)字典，這在之前的工作中著重介紹，本文不再贅述。

3　實(shí)驗(yàn)結(jié)果

根據(jù)更新的數(shù)據(jù)字典，能夠較為精確地對(duì)User-A-gent域中的瀏覽器信息進(jìn)行提取，如表3所示。

圖6　數(shù)據(jù)提取過(guò)程

表3　數(shù)據(jù)提取結(jié)果展示

觀察表3，在第一條記錄中，User-Agent域中出現(xiàn)表示瀏覽器信息的關(guān)鍵字有UC、Safari，通過(guò)本文的提取方法，則能夠?qū)?shù)據(jù)層次結(jié)構(gòu)中較低層次的UC提取到，結(jié)果為ucweb。其他例子同樣很好地證明了該方法的實(shí)用性。

如果僅僅辨析數(shù)據(jù)間的層次結(jié)構(gòu)，而不進(jìn)行根據(jù)權(quán)重設(shè)定優(yōu)先級(jí)的拓?fù)渑判?，直接更新?shù)據(jù)字典，數(shù)據(jù)提取結(jié)果仍然正確，但是效率較低。通過(guò)實(shí)驗(yàn)，相同任務(wù)下，經(jīng)過(guò)帶權(quán)重的拓?fù)渑判蚝髷?shù)據(jù)提取時(shí)間為未排序時(shí)提取時(shí)間的90.6%。

4　結(jié)語(yǔ)

針對(duì)移動(dòng)終端設(shè)備眾多，參數(shù)、性能各異，對(duì)網(wǎng)頁(yè)配置等帶來(lái)的困難，本文提出了一種基于可視分析的層次數(shù)據(jù)提取方法。該方法提取移動(dòng)Web訪問(wèn)日志樣本文件中所有相關(guān)數(shù)據(jù)，將數(shù)據(jù)關(guān)系以可視化的形式展示出來(lái)，通過(guò)一系列交互對(duì)數(shù)據(jù)進(jìn)行拓?fù)渑判?，其中人工干預(yù)排序過(guò)程，包括網(wǎng)絡(luò)去環(huán)、特殊指定等。同時(shí)在排序過(guò)程中記錄每層的數(shù)據(jù)，排序結(jié)束后，將記錄的數(shù)據(jù)構(gòu)建層次結(jié)構(gòu)有向圖，并根據(jù)對(duì)應(yīng)的權(quán)重進(jìn)行拓?fù)渑判?，以所得的排序結(jié)果更新數(shù)據(jù)字典，并以該數(shù)據(jù)字典為依據(jù)進(jìn)行數(shù)據(jù)提取。

對(duì)移動(dòng)Web訪問(wèn)日志進(jìn)行數(shù)據(jù)提取，結(jié)果表明該方法可以很好地解決User-Agent域中瀏覽器信息的兼容問(wèn)題。

在未來(lái)工作中，將在現(xiàn)在提取方法上進(jìn)行擴(kuò)展，完成對(duì)層次數(shù)據(jù)提取的可視分析系統(tǒng)，將數(shù)據(jù)字典的建立、數(shù)據(jù)層次辨析、數(shù)據(jù)提取結(jié)合起來(lái)，對(duì)該類數(shù)據(jù)進(jìn)行一次性提取，并將其作為開源平臺(tái)，服務(wù)更多的人群。

[1]J.Rosenberg,H.Schulzrinne,G.Camarillo,A.Johnston,J.Peterson,R.Sparks,et al.,"SIP:Session Initiation Protocol,"RFC 3261, Internet Engineering Task Force，2002

[2]C.Lindsey.Netnews Article Format,2009

[3]R.Fielding,J.Gettys,J.Mogul,H.Frystyk,L.Masinter,P.Leach,et al..Rfc 2616,Hypertext Transfer Protocol-HTTP/1.1,1999.URL http://www.rfc.net/rfc2616.html,2009.

[4]M.Martinell,J.St?lhammar,J.Hallqvist.Automated Data Extraction-A Feasible Way to Construct Patient Registers of Primary Care Utilization.Upsala Journal of Medical Sciences,2012，117：52~56

[5]G.Shi and K.Barker.Thematic Data Extraction from Web for GIS and Applications.in Spatial Data Mining and Geographical Knowledge Services（ICSDM）,2011 IEEE International Conference on,2011：273~278

[6]A.H.Laender,B.A.Ribeiro-Neto,A.S.da Silva,J.S.Teixeira.A Brief Survey of Web Data Extraction Tools.ACM Sigmod Record, 2002，31：84~93

[7]A.H.Laender,B.Ribeiro-Neto,A.S.da Silva.DEByE-Data Extraction by Example.Data&Knowledge Engineering,2002，40：121-154

[8]M.Kayed，C.H.Chang.FiVaTech:Page-Level Web Data Extraction from Template Pages.Knowledge and Data Engineering,IEEE Transactions on，2010：249~263

[9]W.Su,J.Wang,F.H.Lochovsky,Y.Liu.Combining Tag and Value Similarity for Data Extraction and Alignment.Knowledge andData Engineering,IEEE Transactions on,2012，24：1186~1200

[10]W.Liu,X.Meng,W.Meng.Vide:A Vision-Based Approach for Deep Web Data Extraction.Knowledge and Data Engineering,IEEE!Transactionson,2010，22：447~460

[11]劉亞清，陳榮.基于隱馬爾可夫模型的Web信息抽取.計(jì)算機(jī)工程,2009,35

[12]M.Ward,G.Grinstein,D.Keim,Interactive Data Visualization:Foundations,Techniques,and Applications:AK Peters,Ltd.,2010

[13]E.P.A Heuristic for Graph Drawing.Congressus Nutnerantiunt，1984，42：149~160

[14]T.Kamada，S.Kawai.An Algorithm for Drawing General Undirected Graphs.Information Processing Letters,1989，31：7~15

[15]T.M.Fruchterman，E.M.Reingold.Graph Drawing by Force-Directed Placement.Software:Practice and Experience,1991，21：1129~1164

[16]D.-M.Chan,K.S.Chua,C.Leckie,A.Parhar.Visualisation of Power-Law Network Topologies.in Networks,2003.ICON2003.The 11th IEEE International Conference on,2003：69~74

[17]C.Walshaw.A Multilevel Algorithm for Force-Directed Graph Drawing.in Graph Drawing,2001：171~182

[18]J.B.Kruskal.Nonmetric Multidimensional Scaling:a Numerical Method.Psychometrika,1964，29：115~129

[19]J.Thomas，P.C.Wong.Visual Analytics,IEEE Computer Graphics and Applications,2004，24：0020~21

[20]T.Liang,Y.Cao,M.Zhu,B.Zhou,M.Li,Q.Gan.A Mobile Log Data Analysis System Based on Multidimensional Data Visualization.in Database Systems for Advanced Applications,2014：543~546

[21]H.Guo,Z.Wang,B.Yu,H.Zhao,X.Yuan.TripVista:Triple Perspective Visual Trajectory Analytics and Its Application on Microscopic Traffic Data at a Road Intersection.in Pacific Visualization Symposium（PacificVis）,2011 IEEE,2011:163~170 [22]Z.Wang,M.Lu,X.Yuan,J.Zhang,H.v.d.Wetering.Visual Traffic Jam Analysis Based on Trajectory Data.Visualization and Computer Graphics,IEEE Transactions on,2013，19：2159~2168,2013

[23]S.Barlowe,Y.Liu,J.Yang,D.R.Livesay,D.J.Jacobs,J.Mottonen,et al..WaveMap:Interactively Discovering Features From Protein Flexibility Matrices Using Wavelet‐based Visual Analytics,"in Computer Graphics Forum,2011:1001~1010

Data Extraction;Visual Analysis;Hierarchical Data;Mobile Web Access Log;User-Agent

An Extraction Method of Hierarchical Data in Mobile Web Access Log

GAO Li-feng1，GAO Li-ping2，LI Meng-ying1

（1.School of Computer Science,Sichuan University,Chengdu 610064；2.Beijing Nari Smartchip Microelectronics Company Limited,Beijing 102200）

Proposes an effective extraction method for hierarchical data in mobile Web access log files based on visual analysis.Builds a data dictionary to ensure that no information is missing.Records the correlations and frequency of data to build a weighted network from the sample file based on the data dictionary.Visualizes the network,which accelerates the analysis about the hierarchical structure.Following the analyzing result,hierarchical structure digraph grows and topological sequence with weight priority can be gained to update the data dictionary.Saves data,which is extracted from the log files with the updated date dictionary by regex matching.The experimental results show that the proposed method can address the following goals:analyzing the hierarchical structure among hierarchical data;effective extraction for mobile Web access log;can be popularized in other hierarchical data.

1007-1423（2015）12-0047-07

10.3969/j.issn.1007-1423.2015.12.011

高麗峰（1988-），女，碩士研究生，研究方向?yàn)榭梢暬⒖梢暦治?、?shù)據(jù)挖掘

高麗萍（1982-），女，河北人，碩士，中級(jí)工程師，研究方向?yàn)殡娏ο禂?shù)數(shù)據(jù)分析、嵌入式開發(fā)

李夢(mèng)穎（1987-），女，河北人，碩士，學(xué)生，研究方向?yàn)樾畔⒖梢暬?/p>

2015-03-17

2015-04-15