基于改進(jìn)的n-gram模型的URL分類算法研究

駱 聰，周 城

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

0 引 言

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

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

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

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

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

2 URL和n-gram模型

2.1 URL

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

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

2.2 n-gram模型

n-gram模型[8]是自然語言處理中常用的一種語言模型，該模型基于這樣一種假設(shè)，第n個詞的出現(xiàn)只與前面n-1個詞相關(guān)，而與其他任何詞都不相關(guān)，整個句子的概率就是各個詞出現(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在訓(xùn)練集中出現(xiàn)的次數(shù)。

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

(2)

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

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

3 基于改進(jìn)n-gram模型的URL分類

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

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

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

counttotal(str)=counthostname(str)+

countpath(str)×weightpath

(3)

其中，weightpath>1。

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

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

4 實驗結(jié)果與分析

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

實驗是在Windows7操作系統(tǒng)的環(huán)境下，利用JetBrains PyCharm 2017和Microsoft Visual C++ 6.0等軟件，通過Python和C++語言實現(xiàn)的。其中URL的預(yù)處理是通過Python編程實現(xiàn)的，子串?dāng)?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個頁面。在每個類別中，訓(xùn)練集的數(shù)量占四分之三，測試集的數(shù)量占四分之一。

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

4.2 實驗結(jié)果

4.2.1 weightpath的選擇

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

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

4.2.2 n的選擇

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

表1 在不同weightpath下得到的實驗結(jié)果

圖1 在不同的weightpath下各項評價標(biāo)準(zhǔn)的平均值

n3456查準(zhǔn)率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下得到的各項評價標(biāo)準(zhǔn)的平均值繪成折線圖，如圖2所示，可以發(fā)現(xiàn)當(dāng)n=4時網(wǎng)頁分類的準(zhǔn)確性要略好于n為其他值的時候。

圖2 在不同的n下各項評價標(biāo)準(zhǔn)的平均值

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

4.2.3 改進(jìn)前后網(wǎng)頁分類準(zhǔn)確性對比

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

表3 4次實驗改進(jìn)后的F1值

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

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

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

表4 4次實驗改進(jìn)后的F1值

輪次1234平均值改進(jìn)前訓(xùn)練時間/s0.5510.5630.5460.5690.557改進(jìn)后訓(xùn)練時間/s0.5020.5090.4960.5110.505

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

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

5 結(jié)束語

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

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