一種通用論壇信息提取方法

劉 銳,譚文韜,付園斌,王 紅,3

1(山東師范大學(xué) 信息科學(xué)與工程學(xué)院,濟(jì)南 250014)2(山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室,濟(jì)南 250014)3(山東師范大學(xué) 生命科學(xué)研究院,濟(jì)南 250014)

1 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展,人們?cè)诨ヂ?lián)網(wǎng)中進(jìn)行交流的方式也在不斷增多,互聯(lián)網(wǎng)論壇從網(wǎng)絡(luò)開始推廣普及之時(shí)起便已成為人們?cè)诰W(wǎng)絡(luò)中交流和分享經(jīng)驗(yàn)的主要平臺(tái).據(jù)文獻(xiàn)[1]的中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心發(fā)布的第38次《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示,截至2016年6月,中國(guó)互聯(lián)網(wǎng)論壇和BBS用戶達(dá)1.08億人,占網(wǎng)民總量的15.2%.然而在當(dāng)下的網(wǎng)絡(luò)論壇中,以廣告為主的各類無關(guān)信息充斥在論壇中,這些網(wǎng)頁噪聲對(duì)信息檢索和用戶體驗(yàn)都會(huì)帶來極大的不便.因此,如何有效消除網(wǎng)頁噪聲,提取出論壇主題帖正文內(nèi)容,依然是當(dāng)下研究的重要課題之一.傳統(tǒng)的基于文本密度的正文提取方法[2-4]沒有充分考慮到網(wǎng)頁中噪聲的影響,將網(wǎng)頁源碼中文本的長(zhǎng)度作為判別正文的依據(jù),使得其算法難以被有效應(yīng)用到正文內(nèi)容長(zhǎng)度跨度大,網(wǎng)頁噪聲與網(wǎng)頁正文混雜交錯(cuò)的網(wǎng)絡(luò)論壇中.

為了系統(tǒng)地解決網(wǎng)絡(luò)論壇主題帖正文提取的問題,本文從主題帖頁面識(shí)別和主題帖正文提取兩個(gè)方面入手,分別進(jìn)行解決.兩種方法均是對(duì)數(shù)據(jù)集中的樣本數(shù)據(jù)進(jìn)行處理,利用解析所得的規(guī)則完成后續(xù)分類和提取步驟,保障準(zhǔn)確度和執(zhí)行效率.實(shí)驗(yàn)表明:本文定義的網(wǎng)址相異度函數(shù)適合描述網(wǎng)址間的差異程度;USC方法與KSF方法均具有極強(qiáng)的通用性,適合大規(guī)模提取;兩種方法在準(zhǔn)確度上均明顯優(yōu)于傳統(tǒng)方法,且易于擴(kuò)展和自定義.

本文其余章節(jié)安排如下:第二節(jié)介紹信息提取領(lǐng)域的相關(guān)工作進(jìn)展,第三節(jié)對(duì)兩種方法進(jìn)行理論介紹和闡釋,第四節(jié)驗(yàn)證實(shí)驗(yàn)的結(jié)果和分析,第五節(jié)是本文的總結(jié)和對(duì)未來研究方向的展望.

2 相關(guān)工作

在學(xué)術(shù)領(lǐng)域,對(duì)網(wǎng)頁進(jìn)行分類已經(jīng)有諸多方法.文獻(xiàn)[5]根據(jù)語義結(jié)構(gòu)對(duì)XML網(wǎng)址進(jìn)行分類,在實(shí)驗(yàn)中可以達(dá)到較高的準(zhǔn)確率;文獻(xiàn)[6]使用遺傳算法,以網(wǎng)頁標(biāo)簽和屬性為分類特征,對(duì)網(wǎng)頁進(jìn)行分類;文獻(xiàn)[7]基于網(wǎng)址結(jié)構(gòu)對(duì)網(wǎng)頁進(jìn)行分類,為本文USC方法的提出提供了靈感.文獻(xiàn)[8]利用上下文特征,使用支持向量機(jī)對(duì)網(wǎng)頁進(jìn)行分類,是一種經(jīng)典的網(wǎng)頁分類方法.文獻(xiàn)[9]使用蟻群算法優(yōu)選網(wǎng)頁特征,并用樸素貝葉斯、KNN等算法根據(jù)優(yōu)選的特征進(jìn)行分類,以提高分類的準(zhǔn)確度和執(zhí)行速度.文獻(xiàn)[10]將向量機(jī)和無監(jiān)督聚類優(yōu)勢(shì)互補(bǔ),旨在解決向量機(jī)效率低和無監(jiān)督聚類準(zhǔn)確度低的問題.

在正文提取方面,前人也已有諸多突出的成果:文獻(xiàn)[11]提出一種針對(duì)微博的正文提取方法,并以推特為例進(jìn)行了實(shí)驗(yàn).文獻(xiàn)[3]使用DOM節(jié)點(diǎn)的文本密度為標(biāo)準(zhǔn)進(jìn)行正文提取,該方法便捷且高效.文獻(xiàn)[2]則在此基礎(chǔ)上,提出針對(duì)短正文網(wǎng)頁的正文提取方法,其提取正文的方法仍然為文本密度.除了文本密度方法外,文獻(xiàn)[12]提出根據(jù)網(wǎng)頁結(jié)構(gòu)和文本特征進(jìn)行正文提取的方法,文獻(xiàn)[13]則使用布局相似性作為依據(jù)進(jìn)行提取,然而這些方法在處理短正文時(shí)也存在一定缺陷.

總體而言,傳統(tǒng)的網(wǎng)頁分類更多傾向于內(nèi)容特征方法,而正文提取則以文本密度為基本思想.內(nèi)容特征的優(yōu)點(diǎn)是易于分離出不同網(wǎng)頁的個(gè)性與共性,為分類提供依據(jù),且這些特征不易受主觀因素影響,而缺點(diǎn)是內(nèi)容特征自身的選擇易受主觀影響,且分類結(jié)果易受選擇的結(jié)果影響,缺乏通用性和指導(dǎo)依據(jù).而文本密度方法優(yōu)點(diǎn)是簡(jiǎn)單高效,具有一定通用性,但缺點(diǎn)是完全忽略了網(wǎng)頁中正文的語義因素,容易受到長(zhǎng)度較高的噪聲影響,且難以應(yīng)用到正文較短,結(jié)構(gòu)復(fù)雜的論壇之中.

3 通用論壇正文提取

3.1 網(wǎng)頁結(jié)構(gòu)化聚類方法

在主題帖頁面識(shí)別部分,本文提出了一種基于網(wǎng)址結(jié)構(gòu)的聚類方法USC.在該方法中,首先根據(jù)分隔符將網(wǎng)址劃分為若干部分,隨后使用聚類算法將網(wǎng)址劃分到不同簇中,篩選出主題帖所在的簇,以此提取出所有主題帖頁面的網(wǎng)址.USC方法使用基于網(wǎng)址結(jié)構(gòu)運(yùn)作,而不對(duì)網(wǎng)頁內(nèi)容直接進(jìn)行處理,相比傳統(tǒng)方法更具有針對(duì)性,且在性能上也略勝一籌.

3.1.1 網(wǎng)址結(jié)構(gòu)特征

統(tǒng)一資源定位符(Universal Resource Locator,URL),俗稱網(wǎng)址,是用于唯一定位互聯(lián)網(wǎng)上網(wǎng)絡(luò)資源的一種表示方法,其主要由傳輸協(xié)議、服務(wù)器、端口號(hào)、路徑、查詢、片段六部分組成.隸屬于同一論壇的網(wǎng)頁,除了協(xié)議、服務(wù)器名和端口號(hào)完全相同外,在路徑和查詢部分也有一定的相似之處,如共用的文件夾,共用的附加參數(shù)等等.USC從網(wǎng)址中提取若干結(jié)構(gòu)特征和內(nèi)容特征,以描述該網(wǎng)址,進(jìn)而反映出網(wǎng)址指向的網(wǎng)頁所屬的類別.

論壇中的各類網(wǎng)頁根據(jù)其生成方式的差異可以被劃分為動(dòng)態(tài)網(wǎng)頁,靜態(tài)網(wǎng)頁,偽靜態(tài)網(wǎng)頁三種類別.三類網(wǎng)頁在網(wǎng)址結(jié)構(gòu)上有著各自的特征:

動(dòng)態(tài)網(wǎng)頁:動(dòng)態(tài)網(wǎng)頁的網(wǎng)址中會(huì)包含“?”,其后的內(nèi)容為向服務(wù)器提交的參數(shù)列表,該部分由若干以“&”符號(hào)連接的鍵值對(duì)組成.

靜態(tài)網(wǎng)頁:靜態(tài)網(wǎng)頁不需要查詢部分.但為便于分類和查找,網(wǎng)頁文件往往會(huì)被放置在特定的文件夾中,故網(wǎng)址中會(huì)包含較長(zhǎng)的路徑部分.

偽靜態(tài)網(wǎng)頁:偽靜態(tài)網(wǎng)頁的網(wǎng)址結(jié)構(gòu)既不含查詢部分,且路徑部分也相對(duì)較短,但由于實(shí)質(zhì)是將動(dòng)態(tài)網(wǎng)頁的網(wǎng)址進(jìn)行重寫,所以路徑部分往往會(huì)包含各種分隔符號(hào).

由上面的說明可以得出,同一論壇下的各類網(wǎng)頁,在網(wǎng)址結(jié)構(gòu)上也會(huì)有諸多相似.為此本文引入網(wǎng)址的結(jié)構(gòu)向量,該向量對(duì)網(wǎng)址進(jìn)行定量表示,對(duì)網(wǎng)址中不同位置的結(jié)構(gòu)塊按其內(nèi)容類別(文本或數(shù)字)和內(nèi)容進(jìn)行編碼.

定義1.網(wǎng)址的結(jié)構(gòu)向量.一個(gè)結(jié)構(gòu)向量由若干結(jié)構(gòu)塊編號(hào)元組組成,二者的定義分別為:

p(u,i)=(t(u,i),v(u,i))

(1)

S(u)={p(u,i)|i=1,2,…,N}

(2)

其中u為網(wǎng)址,i指網(wǎng)址中第i個(gè)結(jié)構(gòu)塊,t(u,i)為類別編號(hào),v(u,i)為值編號(hào),p(u,i)為結(jié)構(gòu)塊編號(hào)元組;N為總結(jié)構(gòu)塊數(shù),S為結(jié)構(gòu)向量.

一個(gè)結(jié)構(gòu)塊即為被分隔符號(hào)包圍的一段字符串,在為網(wǎng)址u的第i個(gè)結(jié)構(gòu)塊進(jìn)行編號(hào)時(shí),首先為其類別進(jìn)行編號(hào),當(dāng)該結(jié)構(gòu)塊的類型(包括空值)為首次出現(xiàn)時(shí),為其賦予新的編號(hào),否則沿用已經(jīng)為該類型分配的編號(hào);對(duì)值分配編號(hào)時(shí)類似,若該結(jié)構(gòu)塊的值(包括空值)為首次出現(xiàn)時(shí),賦予新的編號(hào),否則沿用既有編號(hào).N的值取數(shù)據(jù)集中擁有最多結(jié)構(gòu)塊的網(wǎng)址u的結(jié)構(gòu)塊數(shù).若某網(wǎng)址的結(jié)構(gòu)塊數(shù)不足N,則不足的部分以空值的編號(hào)補(bǔ)齊.此外,當(dāng)對(duì)同一論壇提取的網(wǎng)頁構(gòu)造結(jié)構(gòu)向量時(shí),可以忽略其傳輸協(xié)議和域名部分.

在上述定義下,若有如下5條 網(wǎng)址在數(shù)據(jù)集中:

1.http://example.com/query.php?id=001&grade=100

2.http://example.com/query.php?id=001&grade=99

3.http://example.com/query.php?id=002&grade=100

4.http://example.com/query.php?id=002&grade=99

5.http://example.com/query.php?id=003

分別簡(jiǎn)記為u1到u5,類型編號(hào)如表1所示.

表1 類型編號(hào)

Table 1 Type numbers

編號(hào)類型0(空值)1純字母2純數(shù)字

對(duì)值編號(hào)如表2所示.

表2 值編號(hào)

Table 2 Value numbers

編號(hào)值編號(hào)值編號(hào)值0(空值)400180021Query5grade90032php61003id799

則對(duì)上述網(wǎng)址分別構(gòu)造結(jié)構(gòu)向量為:

S(u1)=[(1,1),(1,2),(1,3),(2,4),(1,5),(2,6)]

S(u2)=[(1,1),(1,2),(1,3),(2,4),(1,5),(2,7)]

S(u3)=[(1,1),(1,2),(1,3),(2,8),(1,5),(2,6)]

S(u4)=[(1,1),(1,2),(1,3),(2,8),(1,5),(2,7)]

S(u5)=[(1,1),(1,2),(1,3),(2,9),(0,0),(0,0)]

在對(duì)上述網(wǎng)址構(gòu)造結(jié)構(gòu)向量時(shí),由于其均隸屬于同一域名,故統(tǒng)一忽略域名部分,從路徑部分開始構(gòu)造.每次讀取一條網(wǎng)址,分別查找對(duì)應(yīng)的結(jié)構(gòu)塊的類型和值的編號(hào),若找到則采用現(xiàn)有編號(hào),否則在編號(hào)表中添加新的編號(hào).

定義2.網(wǎng)址之間的相異度.如下所示:

Ns(um,un)=min{i|p(um,i)≠p(un,i)}

(3)

(4)

其中um,un代表不同的網(wǎng)址,p(u,i)與N的定義為定義1中的定義,D(um,un)為網(wǎng)址um和un的相異度.

Ns(um,un)是要找到最小的i,使得兩個(gè)網(wǎng)址在位置i的結(jié)構(gòu)塊不同.如此定義可防止當(dāng)兩個(gè)網(wǎng)址完全不同和僅第一個(gè)結(jié)構(gòu)塊相同時(shí)相異度相等的情況.

目錄結(jié)構(gòu)是典型的樹形結(jié)構(gòu),上級(jí)目錄的差異會(huì)在后續(xù)層級(jí)中不斷被擴(kuò)大,因而對(duì)高層目錄級(jí)賦予較高權(quán)值,他們體現(xiàn)為階乘中較大的乘數(shù).當(dāng)其產(chǎn)生差異時(shí),后續(xù)子目錄會(huì)進(jìn)一步擴(kuò)大這種差異,故采用乘法連接不同層級(jí).

在上述定義下,若有如下三個(gè)結(jié)構(gòu)向量:

S(u1)=[(1,1),(1,2),(1,3),(1,4),(1,5)]

S(u2)=[(1,1),(1,2),(1,3),(1,1),(1,2)]

S(u3)=[(1,1),(2,2),(1,3),(1,4),(1,5)]

則對(duì)于u1和u2,其從第4個(gè)結(jié)構(gòu)塊開始不同,故Ns(u1,u2)=4,D(u1,u2)=5!/4!=5;而對(duì)于u1和u3,雖然僅有第2維不同,但由于其為第一組不同的,所以Ns(u1,u3)=2,D(u1,u3)=5!/2!=60.

3.1.2 KNN-PDC聚類

本文以KNN-PDC聚類[14]為例,介紹聚類算法在USC方法中的應(yīng)用.KNN-PDC聚類是PDC聚類[15]的一種改進(jìn).PDC聚類利用簇中心局部密度較高和不同簇中心距離較遠(yuǎn)兩條假設(shè),分別求取每個(gè)點(diǎn)的局部密度和到另一個(gè)密度更高的點(diǎn)的距離,以此確定簇中心.KNN-PDC聚類在此基礎(chǔ)上利用樣本點(diǎn)的K近鄰信息,統(tǒng)一了DPC聚類的局部密度定義,擺脫了DPC算法受截?cái)嗑嚯x影響較大的缺點(diǎn)[14].

在KNN-PDC聚類中,簇中心的確定依賴于樣本i局部密度ρi和局部密度大于i且離i最近的樣本點(diǎn)距離δi,下面,我們給出二者的定義.

定義3.局部密度ρi和局部密度大于i且離i最近的樣本點(diǎn)距離δi.公式如下所示:

(5)

(6)

其中,KNN(i)代表點(diǎn)i的K近鄰集合,dij為點(diǎn)i與點(diǎn)j之間的距離.K近鄰集合中的點(diǎn)到i的距離越近,則ρi值越高,局部密度越大.δi則當(dāng)比i局部密度大的最近的點(diǎn)離i較遠(yuǎn)時(shí)δi較大.

如下是KNN-PDC聚類的主要流程.

Algorithm1KNN-PDCClusteringInputpoints：distancefunctionisavailableInputK：numberofneighborsOutputclusters：resultclusters1：procedureClustering(points，K)2： foralliinpointsdo3： //KNN(i)指點(diǎn)i的K近鄰點(diǎn)集4： ρi←sumofdistancetopointsinKNN(i)5： δi←mindistancetopointjwhereρj>ρi6： endfor7： DecisionGraph←scatterplotofeachδiandρi8： //更高的ρi和δi意味著更可能是族中心9： centers←pointsinDecisionGraphw/highρiandδi10： clusters←BFS(points，centers，K)11： returnclusters12：endprocedure

在上述流程中,用到了尋找各簇中心的K近鄰點(diǎn)的函數(shù)BFS,該函數(shù)的流程如算法2所示.

Algorithm2BreadthFirstSearchInputpoints：distancefunctionisavailableInputcenters：centerswithhighρiandδiInputK：numberofneighborsOutputclusters：resultclusters1：procedureBFS(points，centers，K)2： clusters←Array3： forallcincentersdo4： allocatecandKNN(c)toanemptycluster5： Queue．push(KNN(c))6： WhileQueue．isEmpty()=Falsedo7： q←Queue．pop()8： forallrinKNN(q)do9： //KNN?DPC判斷隸屬關(guān)系的條件10： ifrhasnotbeenallocatedanddqr≤mean({drj|j∈KNN(r)})then11： allocatertoclusterwithcenterc12： Qucue．push(r)13： endif14： endfor15： endwhile16： endfor17： returnclusters18：endprocedure

通過如上算法,可以將輸入的所有網(wǎng)頁劃分為若干簇,以便進(jìn)行后續(xù)處理.此外,由于主題帖網(wǎng)址大多具有極高的結(jié)構(gòu)相似性,因而本文中沒有考慮對(duì)離群點(diǎn)的處理,如有相關(guān)需求,可進(jìn)一步參考文獻(xiàn)[14].

3.1.3 網(wǎng)址解析模塊

為了能夠快速對(duì)大量的網(wǎng)址進(jìn)行類別篩選,同時(shí)為了適應(yīng)分布式計(jì)算的要求,我們需要將分類后的結(jié)果進(jìn)行解析.本文給出了較為通用的解析器定義,通過對(duì)給定網(wǎng)頁各結(jié)構(gòu)塊的排列方式,內(nèi)容加以限定,進(jìn)而得到網(wǎng)址的解析器.下面,我們將給出其公式定義.

定義4.解析其模塊r(i)和解析器R.其公式如下:

r(i)=(t(i),v(i))

(7)

R={r(i)|i=1,2,…,N}

(8)

其中t為類別集合,描述所有待解析網(wǎng)址定位置的結(jié)構(gòu)塊類型,v為與t中元素對(duì)應(yīng)的值集合,描述所有待解析網(wǎng)址子特定位置的結(jié)構(gòu)塊值,r為對(duì)應(yīng)于特定位置的結(jié)構(gòu)塊的規(guī)則元組,R為對(duì)所有網(wǎng)址的解析器.

在使用時(shí),解析器和網(wǎng)址結(jié)構(gòu)向量類似,不同處在于解析器中每個(gè)位置可能存放多個(gè)編號(hào)值,使用時(shí)采用令網(wǎng)址相異度最小的組合方式,與普通網(wǎng)址計(jì)算相異度.

3.1.4 結(jié)構(gòu)化聚類流程

上文中分別介紹了結(jié)構(gòu)向量,網(wǎng)址相異度,KNN-DPC聚類和解析器的有關(guān)內(nèi)容,該小節(jié)將結(jié)合前述內(nèi)容,介紹USC方法的完整流程.在網(wǎng)頁類型識(shí)別的過程中,往往需要對(duì)從同一論壇獲取的大量網(wǎng)頁同時(shí)進(jìn)行處理,這并不要求對(duì)所有網(wǎng)頁都進(jìn)行聚類等操作,而是先對(duì)少量網(wǎng)頁進(jìn)行解析,將解析所得規(guī)則應(yīng)用于其他頁面,以此快速完成對(duì)所有頁面的分類,也便于利用集群進(jìn)行分布式處理.上述方法的偽代碼表示如算法3所示.

Algorithm3URLs′StructureClusteringInputurls：urlsfromsingleforumInputK：numberofneighborsOutputtopics：urlsoftopicpages1：procedureUSC(urls，K)2： samples←randomurlsinurls3： a←specifiedtopicpageurlinsamples4： //類別有如動(dòng)態(tài)網(wǎng)頁、偽靜態(tài)網(wǎng)頁等5： samples←sampleswithsametypeofa6： vectors←structurevectorsofallurls7： clusters←Clustering(vectors，K)8： topics←clustertowhichabelongs9： //根據(jù)主題帖網(wǎng)址構(gòu)造解析器10： Rule←resolverulefromtopics11： topics←topicurlsidentifiedbyRule12： returntopics13：endprocedure

3.2 關(guān)鍵字打分篩選方法

在主題帖正文提取部分,本文提出關(guān)鍵詞打分篩選方法(Keyword Scoring Filter,KSF).在該方法中,需要使用特定方法確定詞條關(guān)鍵程度,我們以詞頻-逆向文件頻率(TF-IDF)方法為例,來介紹KSF方法的主要思想和算法流程.

首先,根據(jù)停用詞庫(kù)排除無關(guān)文本,其后根據(jù)TF-IDF值找出文本關(guān)鍵詞,接著對(duì)關(guān)鍵詞出現(xiàn)的區(qū)域進(jìn)行打分,解析得到得分最高的區(qū)域,對(duì)其他網(wǎng)頁采用解析得到的規(guī)則直接進(jìn)行正文提取.采用這種方法,不僅提升了主題帖正文提取的準(zhǔn)確率和運(yùn)行效率,同時(shí)可以獲得適用于其他頁面的通用解析規(guī)則,以簡(jiǎn)化后續(xù)的對(duì)于同一論壇的提取工作.

3.2.1 TF-IDF統(tǒng)計(jì)方法

TF-IDF統(tǒng)計(jì)方法是一種用于信息檢索和文本加權(quán)的技術(shù),常用于評(píng)估某一詞條在一個(gè)語料庫(kù)中的一份文件中的重要程度.詞條的重要性隨著其在文件中出現(xiàn)的次數(shù)上升而上升,隨著其在語料庫(kù)中出現(xiàn)的次數(shù)上升而下降.

詞頻(Term Frequency,TF)的計(jì)算是該方法的第一個(gè)步驟,表示一詞條在當(dāng)前文件中出現(xiàn)的頻率,其計(jì)算公式如下:

(9)

其中,F為語料庫(kù)中所有文件的集合,f∈F為文件,w為詞條,N(f,w)為詞條w在文件f中出現(xiàn)的次數(shù).

當(dāng)一個(gè)詞條在文件中多次出現(xiàn),如在計(jì)算機(jī)類文章中頻繁出現(xiàn)“分布式”,則我們有理由認(rèn)為該詞條在該文章中重要性較高.體現(xiàn)到TF值中,則會(huì)被賦予較高的值.

逆向文件頻率(Inverse Document Frequency,IDF)是該方法的第二步,該指標(biāo)體現(xiàn)一個(gè)詞條在所有文件中出現(xiàn)的普遍程度,其公式如下:

(10)

其中,P(f,w)為詞條出現(xiàn)函數(shù),當(dāng)詞條w出現(xiàn)在文件f中時(shí),值為1,否則為0,分母部分+1是為了防止詞條w在語料庫(kù)中沒有出現(xiàn)過,導(dǎo)致分母為0的情況發(fā)生.

當(dāng)一個(gè)詞條在多個(gè)文件中頻繁出現(xiàn),如在各類文件中都大量出現(xiàn)的“的”字,則我們有理由認(rèn)為該詞條在整個(gè)語料庫(kù)中重要性較低.體現(xiàn)到IDF值中,也就會(huì)導(dǎo)致分母值上升,使得IDF值下降.

結(jié)合上述二者,最終可以根據(jù)以下公式得到詞條w在文件f中相對(duì)于整個(gè)語料庫(kù)F的重要度.

W(f,w)=TF(f,w)×IDF(f,w)

(11)

其中W為詞條w的重要度,該重要度體現(xiàn)了詞條在文章中的突出程度和語料庫(kù)中普遍程度二者的調(diào)和,傾向于選擇在文件中真正突出的詞條,而排除掉因行文需要而大量出現(xiàn)的常用字詞.

3.2.2 打分評(píng)價(jià)方法

在利用上文中的TF-IDF方法對(duì)文本重要度進(jìn)行加權(quán)的過程中,難免會(huì)遇到異常頁面,如無人回復(fù)的冷門帖,含有大量圖片而缺乏文字的圖片帖等等,這些噪聲的存在可能會(huì)對(duì)主題帖關(guān)鍵詞提取造成誤導(dǎo),使得無法得到正確的提取規(guī)則,進(jìn)而使得對(duì)所有頁面的正文提取全部出錯(cuò).為預(yù)防這類問題,本文基于正文出現(xiàn)頻率大于噪聲出現(xiàn)頻率的假設(shè),采用打分評(píng)價(jià)方法對(duì)每個(gè)網(wǎng)頁反饋的結(jié)果進(jìn)行評(píng)估,依照得分高低決定采用哪一個(gè)結(jié)果作為最終的輸出.其偽代碼流程如算法4所示.

除了可以將算法4應(yīng)用到對(duì)每個(gè)網(wǎng)頁返回結(jié)果的評(píng)估中外,還可以將其應(yīng)用到對(duì)單一網(wǎng)頁內(nèi)正文位置的判別中,其基本流程與上述流程類似,故不再贅述.

Algorithm4ScoringInputobjs：candidatesgroupOutputresult：resultsgroup1：procedureScoring(objs)2： scorcs←Map3： forallobjinabjsdo4： scores[obj]．value←scores[obj]．value+15： endfor6： result←objsinscoreswithhighestscore7： returnresult8：endprocedure

3.2.3 關(guān)鍵字打分篩選流程

上文中分別介紹了TF-IDF統(tǒng)計(jì)方法和打分評(píng)價(jià)方法,下面將兩種算法結(jié)合,加以部分優(yōu)化步驟,構(gòu)成從主題帖頁面中提取出主題帖正文的完整算法.

首先,從所有網(wǎng)頁中抽取部分網(wǎng)頁作為樣本;然后,初步清理樣本網(wǎng)頁中的噪聲并剔除重復(fù)樣本;接著,對(duì)樣本網(wǎng)頁中的文本進(jìn)行分詞并計(jì)算權(quán)重;再后,對(duì)詞條隸屬網(wǎng)頁元素打分;最后,借助打分結(jié)果構(gòu)造解析規(guī)則,利用打分結(jié)果對(duì)其他網(wǎng)頁提取正文.其偽代碼流程描述如算法5所示.

Algorithm5KeywordScoringFilterInputhtmls：sourcecodeofwebpagesOutputcontent：contentextractedfromwebpages1：procedureKSF(htmls)2： samples←randomwebpagesinhtmls3： results←Array4： forallhtmlinsamplesdo5： lince←htmlw/otagsorirrelevantcontents6： //規(guī)則包括停用規(guī)則、相似規(guī)則等7： removelinessatisfyingRules8： words←splitlinesbyword9： locs←Array10： forallwordinwordsdo11： word．weight←TF?IDFvalueofword12： locs．a(chǎn)dd(locationswherewordappears)13： endfor14： //需要的位置而非關(guān)鍵詞本身15： results．a(chǎn)dd(SCORING(locs))16： endfor17： //根據(jù)打分結(jié)果構(gòu)造提取規(guī)則18： ExtractRule←obtainedfromScoring(results)19： returncontentextractedbyExtractRule20：endprocedure

在算法5中,涉及到了停用規(guī)則,內(nèi)容相似規(guī)則,提取規(guī)則三種規(guī)則,這三類規(guī)則的具體實(shí)現(xiàn)可以根據(jù)用戶自身需求自行定義.停用規(guī)則是當(dāng)單一行內(nèi)的文本滿足特定條件時(shí),該行文本會(huì)被視噪聲而被去除,常用的停用規(guī)則有根據(jù)停用詞庫(kù)匹配,設(shè)定文本長(zhǎng)度閾值,是否存在特定文本結(jié)構(gòu)等.內(nèi)容相似規(guī)則用于判斷兩部分內(nèi)容是否由網(wǎng)頁模板生成,而非用戶所寫,若時(shí)是則將其去除,常見的生成內(nèi)容如回帖發(fā)表日期,用戶個(gè)人信息欄,“只看樓主”等論壇操作按鈕,等等,為了辨別這些內(nèi)容,可以選擇每行文本的開頭數(shù)個(gè)字符作為鍵,若鍵相同則視為模板生成.提取規(guī)則用于精確表示需要進(jìn)行提取的位置,選用的方法必須能夠恰好涵蓋所有正確的位置,通常選用代碼中標(biāo)簽的class屬性值.

4 實(shí)驗(yàn)與分析

4.1 結(jié)構(gòu)化聚類

相比傳統(tǒng)分類方法,USC并不直接對(duì)所有網(wǎng)頁進(jìn)行分類,而是從所有網(wǎng)頁中抽取部分樣本作為訓(xùn)練數(shù)據(jù),根據(jù)分類結(jié)果構(gòu)造解析器,再利用解析器對(duì)剩余網(wǎng)頁進(jìn)行解析,因而最終的分類結(jié)果在很大程度上取決于解析器,構(gòu)造解析器的規(guī)則中,除直接使用結(jié)構(gòu)向量外,也可使用正則表達(dá)式以提升程序的通用性.本文實(shí)驗(yàn)中為便于描述,解析器將仍然使用結(jié)構(gòu)向量.

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

我們利用網(wǎng)絡(luò)爬蟲在互聯(lián)網(wǎng)上隨機(jī)爬取了若干網(wǎng)頁,經(jīng)過人工去除非論壇網(wǎng)頁、廣告頁等無關(guān)網(wǎng)頁,剩余有效網(wǎng)頁數(shù)13346,其中主題帖網(wǎng)頁數(shù)5888,在所有有效網(wǎng)頁中,Discuz!論壇頁面11822,獨(dú)立論壇頁面數(shù)1524.這些頁面來自不同領(lǐng)域不同話題的論壇,具有一定的代表性.

4.1.2 評(píng)價(jià)指標(biāo)

在信息提取領(lǐng)域,通用的評(píng)價(jià)指標(biāo)是召回率R,準(zhǔn)確率P和F值.三者的計(jì)算公式分為:

(12)

(13)

(14)

其中,Net為提取主題帖數(shù),Nt為主題帖網(wǎng)址數(shù),Ne為提取數(shù).一般而言,提取結(jié)果的優(yōu)劣由F值進(jìn)行評(píng)估,其值越高,效果越好.

4.1.3 結(jié)果分析

本部分實(shí)驗(yàn)主要是與文獻(xiàn)[16]所采用的基于DOM樹的網(wǎng)頁聚類算法相比較,在同樣的數(shù)據(jù)集下,二者的運(yùn)行結(jié)果分別如表3和表4所示.

在此次實(shí)驗(yàn)中,我們根據(jù)預(yù)實(shí)驗(yàn)的結(jié)果對(duì)K值進(jìn)行了微調(diào),以維持較高的準(zhǔn)確率,盡管可能會(huì)有部分壇的由于網(wǎng)址結(jié)構(gòu)過于單一而導(dǎo)致本應(yīng)同類別的網(wǎng)址被劃分到不同類別中,使得召回率降低,但對(duì)于一般的網(wǎng)站,基本可以維持較高的召回率,同時(shí)也使得準(zhǔn)確率得到保證,確保構(gòu)造的解析器中不會(huì)將噪聲網(wǎng)址包含在內(nèi).

將表3和表4中的數(shù)據(jù)繪制為折線圖,其結(jié)果如圖1,圖2,圖3所示.

綜合實(shí)驗(yàn)結(jié)果,可以看出USC方法中的聚類部分具有如下優(yōu)點(diǎn):

1.準(zhǔn)確度高,構(gòu)造解析器的簇中不含任何噪聲,確保使用解析器進(jìn)行大規(guī)模提取時(shí)的正確性.

2.適應(yīng)性強(qiáng),對(duì)各類論壇均有較高的召回率,確保擁有足夠的樣本數(shù)據(jù)構(gòu)造解析器并使得解析器可以提取到更多符合要求的網(wǎng)頁網(wǎng)址.

表3 USC聚類結(jié)果

Table 3 Result of clustering in USC

序號(hào)網(wǎng)址數(shù)主題帖網(wǎng)址數(shù)提取數(shù)提取主題帖數(shù)召回率/%準(zhǔn)確率/%F值/%1522287287287100．00100．00100．00276221421121198．60100．0099．293481202202202100．00100．00100．00436813112812897．71100．0098．8451102671671671100．00100．00100．00662729128228296．91100．0098．43763320119819898．51100．0099．25883145544944998．68100．0099．34948721019019090．48100．0095．0010859282282282100．00100．00100．00

表4 文獻(xiàn)[16]的聚類結(jié)果

Table 4 Result of clustering in reference [16]

序號(hào)網(wǎng)址數(shù)主題帖網(wǎng)址數(shù)提取數(shù)提取主題帖數(shù)召回率/%準(zhǔn)確率/%F值/%152228723023082．58100．0090．462762214808038．19100．0055．273481202909048．67100．0065．474368131505043．09100．0060．225110267153053079．93100．0088．85662729121021075．52100．0086．05763320113013064．86100．0078．69883145539039087．04100．0093．079487210210210100．00100．00100．001085928219019069．73100．0082．17

4.2 關(guān)鍵字打分

KSF方法采用語義分割和TF-IDF加權(quán)方法提取出網(wǎng)頁文本部分的關(guān)鍵詞,對(duì)關(guān)鍵詞所在位置進(jìn)行打分,構(gòu)造出解析規(guī)則,故能否從網(wǎng)頁中正確提取到主題帖的正文信息取決于解析規(guī)則的構(gòu)造情況.本實(shí)驗(yàn)中需要的對(duì)文本進(jìn)行進(jìn)行分詞,為簡(jiǎn)化實(shí)驗(yàn)流程,實(shí)驗(yàn)中的分詞程序?qū)⑹褂瞄_源的分詞程序包jieba.下面,本實(shí)驗(yàn)將對(duì)使用KSF方法構(gòu)造解析規(guī)則的過程進(jìn)行評(píng)估.

圖1 召回率Fig.1 Recall value

4.2.1 實(shí)驗(yàn)數(shù)據(jù)

我們利用網(wǎng)絡(luò)爬蟲,在每個(gè)網(wǎng)絡(luò)論壇中爬取若干論壇頁面,去除非主題帖頁面后,所有論壇剩余主題帖頁面數(shù)總計(jì)為3417,每次從同一論壇的頁面中隨機(jī)抽取5個(gè)頁面進(jìn)行訓(xùn)練,根據(jù)解析所得規(guī)則判斷是否正確分離出所需內(nèi)容,每個(gè)論壇將重復(fù)進(jìn)行10次實(shí)驗(yàn).

圖2 準(zhǔn)確率Fig.2 Precision value

圖3 F值Fig.3 F value

4.2.2 評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)重在檢驗(yàn)解析規(guī)則的正確性,為簡(jiǎn)化處理,以標(biāo)簽class屬性值作為解析規(guī)則,故評(píng)價(jià)指標(biāo)為解析所得class屬性值恰為論壇正文區(qū)標(biāo)簽class屬性值的比例和程序用時(shí).

4.2.3 結(jié)果分析

這一部分實(shí)驗(yàn)我們使用文獻(xiàn)[2]中的SCEED算法作為對(duì)照實(shí)驗(yàn),實(shí)驗(yàn)的結(jié)果如表5和表6所示.

表5 正文提取算法綜合對(duì)比

Table 5 Brief comparison between KSF and SCEED

算法名稱準(zhǔn)確率/%平均用時(shí)/sKSF90．7728．24SCEED72．3127．43

在用時(shí)方面,KSF算法相比SCEED算法要慢,進(jìn)行中文分詞需要讀取中文數(shù)據(jù)庫(kù),并對(duì)字符串序列進(jìn)行劃分和匹配.SCEED方法沒有這些步驟,因而速度相對(duì)較快,但準(zhǔn)確率較差.

綜合實(shí)驗(yàn)數(shù)據(jù),KSF方法具有以下特點(diǎn):

1.魯棒性較強(qiáng),在有較多噪聲的主題帖頁面中仍可正常進(jìn)行解析工作.

2.通用性強(qiáng),解析出的規(guī)則可以應(yīng)用于同論壇內(nèi)的所有主題帖頁面.

3.效率高,對(duì)一般論壇中單一網(wǎng)頁的解析速度視內(nèi)容量從2秒到9秒不等.

表6 正文提取算法效果對(duì)比

Table 6 Detailed comparison between KSF and SCEED

序號(hào)正確數(shù)/個(gè)平均用時(shí)/sKSFSCEEDKSFSCEED1101028．6139．33210844．0233．4737038．8034．6749109．627．4758537．3134．41691025．5222．547101021．5322．418101012．1411．8699318．2916．05108611．9817．101110104．613．351210618．2519．48138696．4694．41

5 總結(jié)與展望

本文首先提出了網(wǎng)址的結(jié)構(gòu)向量表示法,使得對(duì)網(wǎng)址的處理可以采用類似向量的的方法進(jìn)行,此外還給出網(wǎng)址相異度函數(shù)的定義,這是一種結(jié)合目錄結(jié)構(gòu)特性的相異度計(jì)算方法,可以將其推廣應(yīng)用到更多目錄結(jié)構(gòu)的表示中.此外,本文第二節(jié)提出的基于網(wǎng)址結(jié)構(gòu)的聚類方法USC是對(duì)傳統(tǒng)論壇網(wǎng)頁分類方法的改進(jìn),該方法充分利用網(wǎng)絡(luò)論壇在網(wǎng)址結(jié)構(gòu)上的相似性和結(jié)構(gòu)化特性,無需讀取網(wǎng)頁內(nèi)容,即可對(duì)同論壇下的網(wǎng)頁直接進(jìn)行分類,同時(shí)兼顧性能與質(zhì)量.最后,本文結(jié)合語義分詞技術(shù),TF-IDF加權(quán)統(tǒng)計(jì)方法,打分評(píng)估方法提出的關(guān)鍵詞打分篩選方法,可以快速對(duì)論壇中的網(wǎng)頁解析出通用的提取規(guī)則,應(yīng)用于后期大規(guī)模正文提取中,以滿足持久化信息提取的需求.

本文在使用KNN-DPC進(jìn)行聚類時(shí),雖然可以通過決策圖直觀地選出簇中心,然而仍然缺乏一種適合于所有情況的自動(dòng)化簇中心選擇方法,在接下來的工作中將通過曲線分析尋找自動(dòng)確定簇?cái)?shù)的方法.此外,本文中為便于描述而采用較為簡(jiǎn)單的解析規(guī)則,在實(shí)際應(yīng)用過程中,除可替換為正則表達(dá)式,還可根據(jù)需求完全自定義解析規(guī)則的行駛,如何合理構(gòu)造具有較強(qiáng)魯棒性的解析規(guī)則,仍是一個(gè)亟待研究的問題.