駱 聰，周 城

(江南計算技術研究所，江蘇 無錫 214083)

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡上的信息量獲得了爆炸性增長[1]。為了方便用戶從海量網(wǎng)頁中快速找到感興趣的信息，準確的網(wǎng)頁分類成為越來越棘手的問題。網(wǎng)頁分類在構建主題爬蟲、搜索引擎?zhèn)€性化排序和搜索引擎的目錄導航等方面發(fā)揮著至關重要的作用[2]。

文中提出將改進的n-gram模型用于網(wǎng)頁分類。首先簡要介紹了國內外的相關研究，然后介紹了URL和n-gram模型，接著提出了基于改進n-gram模型的URL分類算法，最后通過實驗進行了相關驗證。

1 URL分類研究現(xiàn)狀

傳統(tǒng)的網(wǎng)頁分類技術大都參考文本分類技術，從網(wǎng)頁正文、超鏈接結構和錨文本等網(wǎng)頁內容中抽取有效的特征用于網(wǎng)頁分類[3]。但是在主題爬蟲中，在下載網(wǎng)頁之前就需要判斷該URL代表的網(wǎng)頁所屬的主題。此外當網(wǎng)頁內容隱藏在圖片中，網(wǎng)頁內容信息就無法獲取[4]。在這些情況下，基于內容分析的網(wǎng)頁分類技術作用十分有限，于是基于URL分析的網(wǎng)頁分類技術逐漸成為了研究熱點。

Kan M Y等[5]將URL劃分為有意義的塊，提取成分特征、序列特征和正交特征，然后使用最大熵模型進行分類，在某些場景下該方法的性能接近當前最新的基于內容分析的網(wǎng)頁分類方法。Rajalakshmi R等[6]提出僅從網(wǎng)頁URL中提取基于n-gram模型的字符特征，然后使用支持向量機和最大熵分類器進行分類，取得了較好的效果。Inma Hernández等[7]提出了CALA算法，該算法基于Patricia樹結構，樹的每個節(jié)點表示前綴，對其使用通配符泛化后，從根節(jié)點到葉子節(jié)點就可以得到一條URL模式。在建立一系列URL模式之后，只需要將網(wǎng)頁URL與模式匹配來進行分類。

2 URL和n-gram模型

2.1 URL

URL(uniform resource locator，統(tǒng)一資源定位符)是每個網(wǎng)絡資源統(tǒng)一的并且在網(wǎng)上唯一的地址。URL的語法格式為：protocol://hostname[:port]/path[;parameters][?query][#fragment]。其中帶方括號[]的為可選項。Protocol(協(xié)議)用于指定使用的傳輸協(xié)議。Hostname(主機名)指存放資源的服務器的域名系統(tǒng)DNS主機名或者IP地址。Port(端口號)為整數(shù)，省略時使用方案的默認端口。Path(路徑)由零或多個/符號隔開的字符串，表示主機上一個目錄或文件地址。Parameters(參數(shù))用于指定特殊參數(shù)的可選項。Query(查詢)可選，用于給動態(tài)網(wǎng)頁傳遞參數(shù)。Fragment(信息片段)用于指定網(wǎng)絡資源中的片斷。

網(wǎng)頁URL雖然只是一串相對較短的文本，但是它也攜帶了一些和網(wǎng)頁內容相關的有效信息，目前已經(jīng)廣泛應用于Web挖掘的眾多領域，所以有必要充分利用網(wǎng)頁URL信息來進行網(wǎng)頁分類。

2.2 n-gram模型

n-gram模型[8]是自然語言處理中常用的一種語言模型，該模型基于這樣一種假設，第n個詞的出現(xiàn)只與前面n-1個詞相關，而與其他任何詞都不相關，整個句子的概率就是各個詞出現(xiàn)的概率的乘積。對于句子S=W1W2…Wk，它的概率可以表示為：

P(S)=P(W1W2…Wk)=P(W1)·P(W2|W1)·…·P(Wk|Wk-n+1…Wk-1)=

(1)

其中,C(Wi-n+1…Wi-1Wi)表示n元對Wi-n+1…Wi-1Wi在訓練集中出現(xiàn)的次數(shù)。

n-gram模型中存在數(shù)據(jù)稀疏問題[9]，即部分n元對在訓練集中沒有出現(xiàn)過，導致較多參數(shù)為0。這個問題可以通過數(shù)據(jù)平滑技術來解決，典型的數(shù)據(jù)平滑算法有加法平滑、Good-Turing平滑、Katz平滑、插值平滑等等[10]。文中采用最簡單的加一平滑算法，保證每個n元對至少出現(xiàn)一次，使用加一平滑算法后，概率就可以表示為：

(2)

其中，V為訓練集中所有n元對的個數(shù)。

進行網(wǎng)頁分類時，特征選取是一個極其重要的環(huán)節(jié)[11]。進行URL特征提取時，傳統(tǒng)的URL切分方法是遇到非字母數(shù)字字符時把URL進行分割。顯然這種分割方法過于粗略，對于字符串內部的關鍵詞就無法提取出來，所以最后網(wǎng)頁分類的準確性往往不理想。文中借鑒n-gram模型的思想進行URL的特征提取，但與一般自然語言處理過程將詞作為基本單位不同，文中將字符作為基本單位，對URL進行了進一步的分割。

3 基于改進n-gram模型的URL分類

傳統(tǒng)的基于n-gram模型的URL分類算法認為所有URL字段在進行網(wǎng)頁分類時的區(qū)分能力相同。但通過查看網(wǎng)頁URL格式說明，可以發(fā)現(xiàn)真正有區(qū)分能力的是hostname(主機名)和path(路徑)這兩個字段，而其他字段對于網(wǎng)頁分類的貢獻程度幾乎可以忽略不計。此外，由于path字段用來表示主機上的一個目錄或文件地址，而根據(jù)個人習慣可知，為了便于尋找，在存儲文件時往往將存儲路徑命名為與文件內容或主題相關的名字。例如，由“D:游戲英雄聯(lián)盟”這個路徑可知，該目錄下的文件與游戲主題相關。所以基于上述考慮，文中僅把URL的hostname和path這兩個字段用于構建n-gram模型，并且為path字段賦予更高的權重weightpath。

黎斌[12]使用n-gram模型對URL進行分類時對每個類別分別建立一個n-gram模型，然后由所有n-gram模型共同組成分類器。在此基礎上，文中對n-gram模型進行改進，在建立模型時考慮字段權重，提出基于改進的n-gram模型的URL分類算法，以提升網(wǎng)頁分類的準確性。

訓練階段，將訓練集中的URL按預先設定的類別分類，然后統(tǒng)計每個類別中n元子串和n-1元子串的數(shù)量。對于字符串str，若其在hostname字段和path字段出現(xiàn)的次數(shù)分別為counthostname(str)和countpath(str)，那么在改進后的n-gram模型中，該字符串出現(xiàn)的總次數(shù)應為：

counttotal(str)=counthostname(str)+

countpath(str)×weightpath

(3)

其中，weightpath>1。

測試階段，假設預先設定K個類別，提取測試集中URL的n元子串，然后根據(jù)式2并結合訓練集中子串的統(tǒng)計情況，逐一計算測試集中的URL在各個類別下的概率P1,P2,…,PK。如果Pi(1≤i≤K)為其中的最大值，那么可以認為i對應的類別即為該URL所屬的類別。

基于改進的n-gram模型在剔除大量噪聲數(shù)據(jù)的同時，也為具有高區(qū)分能力的字段賦予更高的權重。將結合字段權重的n-gram模型用于URL分類，不僅可以提高算法效率，也有助于網(wǎng)頁分類準確性的提升。

4 實驗結果與分析

4.1 實驗環(huán)境與數(shù)據(jù)集說明

實驗是在Windows7操作系統(tǒng)的環(huán)境下，利用JetBrains PyCharm 2017和Microsoft Visual C++ 6.0等軟件，通過Python和C++語言實現(xiàn)的。其中URL的預處理是通過Python編程實現(xiàn)的，子串數(shù)量的統(tǒng)計和概率的計算是通過C++編程實現(xiàn)的。

WebKB數(shù)據(jù)集中共包含8 282個頁面，經(jīng)過人工分類為以下7個類別：Course、Department、Faculty、Other、Project、Staff和Student。實驗中使用了該數(shù)據(jù)集的一部分，其中Course類別共208個頁面，F(xiàn)aculty類別共152個頁面，Project類別共80個頁面，Student類別共552個頁面。在每個類別中，訓練集的數(shù)量占四分之三，測試集的數(shù)量占四分之一。

借鑒文本分類中通常使用的評價標準查準率(precision)、查全率(recall)和F1值(F1score)對實驗中網(wǎng)頁分類的結果進行評價。

4.2 實驗結果

4.2.1 weightpath的選擇

在進行網(wǎng)頁分類時，由于path字段比hostname字段更具有區(qū)分能力，所以設定weightpath>1。但是當weightpath的值太大時，會嚴重削弱hostname字段的分類能力，所以有必要對weightpath的值進行選取。設定n=3，然后通過調整weightpath的大小進行實驗，得到每一類的查準率、查全率和F1值，如表1所示。

將在不同weightpath下得到的各項評價標準的平均值繪成折線圖，如圖1所示，可以發(fā)現(xiàn)當weightpath=1.5時更加合適，此時網(wǎng)頁分類的準確性較高。

4.2.2 n的選擇

使用n-gram模型時，n太大太小都會影響分類的準確性，因此合理地選擇n就顯得尤為重要。根據(jù)前面的實驗結果，設定weightpath=1.5，然后通過調整n的大小進行實驗，最后得到每一類的查準率、查全率和F1值，如表2所示。

表1 在不同weightpath下得到的實驗結果

圖1 在不同的weightpath下各項評價標準的平均值

n3456查準率Course0.810 80.909 00.882 40.857 1Faculty0.818 20.607 10.548 40.485 7Project0.733 30.750 00.631 50.578 9Student0.747 10.777 80.792 70.805 0平均值0.777 40.761 00.713 80.681 7查全率Course0.576 90.576 90.576 90.576 9Faculty0.473 70.447 40.447 40.447 4Project0.550 00.600 00.600 00.550 0Student0.942 00.963 80.942 00.927 5平均值0.635 70.647 00.641 60.625 5F1Course0.674 10.705 80.697 70.689 6Faculty0.600 00.515 20.492 80.465 8Project0.628 60.666 70.615 30.564 1Student0.833 30.860 90.860 90.861 9平均值0.684 00.687 20.666 70.645 3

將在不同的n下得到的各項評價標準的平均值繪成折線圖，如圖2所示，可以發(fā)現(xiàn)當n=4時網(wǎng)頁分類的準確性要略好于n為其他值的時候。

圖2 在不同的n下各項評價標準的平均值

綜合上述實驗結果可知，當weightpath=1.5，n=4時，改進后的n-gram模型性能較優(yōu)，此時網(wǎng)頁分類的準確性要優(yōu)于其他時候。所以在后續(xù)的改進前后性能對比環(huán)節(jié)，將使用這兩個值作為參數(shù)進行實驗。

4.2.3 改進前后網(wǎng)頁分類準確性對比

為保證模型的可靠性，將實驗數(shù)據(jù)集中的每一類都隨機分為4份，然后讓這4份數(shù)據(jù)的其中1份輪流充當測試集，另外3份作為訓練集。設定weightpath=1.5，n=4，得到4次實驗改進后的F1值，如表3所示。

表3 4次實驗改進后的F1值

通過對4次實驗的結果求平均值可知，改進后的F1值為66.71%，比文獻[12]中得到的59.23%提升了12.63%。

4.2.4 改進前后網(wǎng)頁分類效率對比

由于改進前后的差異主要體現(xiàn)在URL預處理和子串數(shù)量統(tǒng)計上，所以根據(jù)訓練時間這個指標進行網(wǎng)頁分類效率的對比。4次實驗改進前后的訓練時間如表4所示。

表4 4次實驗改進后的F1值

輪次1234平均值改進前訓練時間/s0.5510.5630.5460.5690.557改進后訓練時間/s0.5020.5090.4960.5110.505

通過對4次實驗的結果求平均值可知，改進后n-gram模型的平均訓練時間為0.505 s，比改進前的0.557 s減少了9.34%。

上述實驗證明了將改進后的n-gram模型用于網(wǎng)頁分類的可行性，并且綜合實驗結果可知，改進后網(wǎng)頁分類準確性和算法效率都有一定的提升。

5 結束語

考慮到網(wǎng)頁URL各個字段對于網(wǎng)頁分類的區(qū)分能力不同，在此基礎上改進n-gram模型，提出基于改進的n-gram模型的URL分類算法。實驗結果證明，該算法改善了分類準確性和算法效率。

在未來的研究中，將探索該模型用于中文網(wǎng)頁URL分類的可行性。并且考慮到網(wǎng)頁URL能夠提供的信息有限，試圖結合基于內容分析的網(wǎng)頁分類技術，并采用深度學習[13-15]方法，挖掘更深層次的特征，以提升網(wǎng)頁分類的準確性。