基于逆向匹配的電子商務網站實體模板半自動構建方法

傅 彥，徐昭邦，夏虎，周俊臨

(電子科技大學 計算機科學與工程學院 互聯網科學中心，四川 成都 611731)

?

基于逆向匹配的電子商務網站實體模板半自動構建方法

傅 彥，徐昭邦，夏虎，周俊臨

(電子科技大學 計算機科學與工程學院 互聯網科學中心，四川 成都 611731)

Web頁面中的主題信息一般分布比較集中，可利用網頁的這一特性進行網頁主題信息的自動提取。網頁源代碼中的HTML標簽不規范，使得正向匹配難以生成嵌套結構準確的DOM樹，該文提出一種通過逆向匹配的方法，構建完整的網頁源代碼DOM樹。通過對DOM樹進行剪枝，刪除無關節點，對保留下來的信息塊的節點標簽進行人工選擇與唯一性判定，從而生成提取模板。該方法能夠實現對電子商務網站源網頁中的主題信息進行提取，是一種半自動、通用的方法，可用于信息檢索系統中的信息采集。

逆向匹配；DOM樹；模板構建；信息提取

1 引言

隨著網絡技術和數據庫技術的飛速發展，網絡上的信息量越來越大，越來越多的人選擇從網上獲取自己需要的信息，其中也包括網上購物。電子商務網站上包含了大量信息，用戶可以通過這些網頁獲取商品的主題、參數等信息，但其中的商品網頁大多屬于深層網絡[1]，不便于被傳統的搜索引擎檢索。

電子商務網站的實體模板是用于提取目標網頁中的商品主題和參數等信息的提取框架。通過逆向匹配構建商品源網頁的DOM樹，再對同一電子商務網站的多個商品網頁的DOM樹進行比較，刪除其中的網頁模板信息，然后通過人工選擇所需提取的部分并進行唯一性判定，從而構建實體提取模板。實驗表明，該方法可以準確的提取出所需要的信息，并且在同一網站具有通用性。通過構建多個電子商務網站的實體提取模板，進而對其中的大量商品網頁的信息進行批量提取，生成購物搜索系統，用戶通過查詢，可以非常方便地獲取所需查詢商品的主題和參數信息。并且可以對多個電子商務網站的同一商品進行比較，優化購物環境。

2 相關研究

在電子商務信息網站信息提取領域，已經有了大量的研究工作，但大部分是通過構建靜態抽取規則(靜態模板)[2]或者通過分析源代碼獲得目標信息的路徑[3]進行規則提取，而自動與半自動的構建方法也通常只適合新聞網頁，對于電子商務網站的提取結果準確率較低，這是因為新聞網頁基本都含有大量文字內容信息，易于與旁邊的廣告、推薦等無關信息區分開來，而電子商務網站的信息則分布較亂，并且不同的電子商務網站對于商品主題、參數等信息的組織不盡相同，難于將目標信息與旁邊的無關信息區分開來。

周炘[2]等人通過分析網頁源代碼，制定了針對特定電子商務網站的靜態提取模板。侯明燕[3]等人提出了基于網頁信息定位的數據抽取技術，首先構建源網頁的DOM樹，然后經過分析找到目標信息所在的位置和路徑信息，通過從根節點到目標信息節點的路徑提取出目標信息。這兩種方法能夠得到較高的準確率，但缺乏通用性，并且當網頁改版時，靜態提取模板和路徑信息都有可能會失效。

王琦[4]等人提出了STU-DOM樹模型，對源網頁構建具有語義信息的DOM樹，在STU-DOM樹中，每個具有語義屬性的節點，即STU節點，都具有兩個語義屬性： 塊內鏈接數和非鏈接文字數，通過比較兩個語義屬性的值進行判定局部相關度和上下文相關度，但這種方法只能對新聞、財經、e國等文字信息比較集中的網頁進行提取，對于京東商城，亞馬遜商城等結構復雜的電子商務網站沒有較好的提取效果。

通過分析各個電子商務網站多個網頁的源代碼，發現在同一個網站中，絕大部分網頁的源代碼是由相同模板生成的，而每個網頁的模板信息是相同且與特定商品的主題與參數等信息不相關，相對于本文要提取的目標信息屬于無關信息，應該刪除。本文提出了一種半自動構建電子商務網站提取模板的方法，通過比較同一電子商務網站的多個源網頁的DOM樹，刪除其中相同的部分，再對每個子樹中的鏈接數與非鏈接文字數進行比較，達到對DOM樹進行剪枝的效果，然后通過人工選擇目標信息，對目標信息所在位置的上下界進行唯一性判定，從而構建提取模板，是一種半自動、通用的方法。

3 算法綜述

3.1 逆向匹配構建DOM樹 定義： DOM(document object model)文檔對象模型，是W3C組織推薦的處理可擴展置標語言的標準編程接口。HTML文檔被解析后轉化為DOM樹，使文檔的結構更加清晰。通過對DOM樹節點的判斷與剪枝，可以方便地對無關信息進行刪除和修改。

由于網頁的HTML代碼的語法要求不嚴格，在HTML中，如果上下文清楚地顯示出段落或者列表鍵在何處結尾，那么就可以省略

或者之類的結束標記。這給正向匹配構建DOM樹構成了障礙，導致無法準確判定各個HTML標簽的嵌套結構，而通過逆向匹配識別HTML標簽則可以構建完整的DOM樹，因此本文提出了一種通過逆向匹配構建DOM樹的方法。

1) 首先讀取HTML文檔為字符串形式。

2) 依次識別HTML標簽，即等，忽略HTML文檔注釋<！-- -->，將識別到的標簽依次存入棧stack1中，當讀取的標簽為開始標簽時，如，則直接入棧stack1。(整個HTML文檔初步解析以后，棧stack1中保存著此HTML文檔的所有標簽，棧stack2中保存著相對應的屬性和文本信息。)

3) 將棧stack1中的標簽依次取出，若當前取出的標簽為結束標簽，則直接存入棧stack3和棧stack0中，若當前取出的標簽為開始標簽，則將其加上“/”前綴后與stack0的棧頂字符串比較，若兩字符串相等，則彈出棧stack0的棧頂元素，并且將從stack1中取出的那個開始標簽加入棧stack3中，若此開始標簽加上“/”前綴后與棧stack0的棧頂字符串不等價，則說明此開始標簽在原HTML文檔沒有匹配的結束標簽，故應將其補全，即將此開始標簽加上“/”前綴后構成的結束標簽加入棧stack3中，然后將此開始標簽加入棧stack3中。依此規則將棧stack1中的標簽全部轉存如棧stack3中。

4) 將棧stack2中的屬性和文本信息全部轉存入棧stack4中。(此時，棧stack3中保存的信息為原棧stack1中補全后的逆序，而棧stack4中為原棧stack2中信息的逆序。)

5) 從棧stack3中取出一個棧頂元素，必定為開始標簽，以此標簽作為所要構建的DOM樹的根節點標簽，并同時將此根節點入棧stack5，即棧stack5中存的是DOM樹的節點；在stack4中取出兩個字符串作為根節點的屬性信息和文本信息，以當前構建節點的子樹形式表示。

6) 依次從棧stack3中取出棧頂元素，若此元素為開始標簽，則以此標簽作為棧stack5中棧頂節點的子節點，并在棧stack4中取出兩個字符串作為剛建立的子節點的屬性信息和文本信息，以子樹形式表示；若從棧stack3中取出的棧頂元素為結束標簽，則從棧stack5中彈出一個節點，表明此節點不再有子節點。依次規律直到棧stack3為空為止。

7) 構建好DOM樹后，由于之前用空串代替了缺省的屬性和文本信息，所以，若構建出的DOM樹的節點中有空串屬性或文本，則刪除該屬性或文本。

此時，構建DOM樹完畢，可以通過將其存為XML文件以可視化。一個簡單的示例及其構建的DOM樹如表1所示。

表1 構建DOM樹結果示例

其中構建的DOM樹運用了前綴編碼[5]，以唯一標示每個節點。

3.2 剪枝算法

剪枝算法是在保留需要提取的信息的前提下刪除無關節點的過程。本算法通過比較同一網站的多個商品網頁的DOM樹，剪去其中相同的子樹，達到刪除大量無關節點的目的。同時通過采用鏈接數和非鏈接文字數兩個語義信息進行輔助剪枝，進而最大化地刪除無關節點，以方便人工選擇。

本文需要提取的電子商務網站(以京東商城為例)的商品網頁信息如圖1、圖2所示。

圖1 電子商務網站主題信息

圖2 電子商務網站參數信息

每次從同一電子商務網站取出n個不同商品的網頁，記為Y={y1，y2，……，yn}；對它們分別構建DOM樹： D={d1，d2，……，dn}；將d2～dn依次與d1比較(保存d1的副本，以用于唯一性判定)，若葉子節點中的屬性與文本信息都相同，則剪去該葉子節點，若非葉子節點中的屬性與文本信息都相同，且它的子節點都已被剪枝，則剪去該非葉子節點。當整個DOM樹比較完畢時，則原商品網頁中的模板信息已被剪枝。

圖3中黑色部分表示DOM樹中與其他DOM樹相同的部分，通過比較剪枝，刪除了這部分節點，得到右圖為剪枝后的結果。

圖3 對DOM樹剪枝示例

本文采用信息提取算法[4]進行輔助剪枝，對其中的閾值進行重新測試，以達到較高的覆蓋率。該算法提出運用鏈接數和非連接文字數兩個語義信息進行計算局部相關度和上下文相關度，通過確定局部相關度閾值和上下文相關度閾值進行判斷節點與主題的相關性，進而達到剪枝的效果，通過兩次剪枝，可將剪枝率最大化，從而方便人工選擇。

3.3 人工選擇與唯一性判定

通過剪枝算法進行剪枝后，DOM樹中已經刪除了大量無關信息，通過進行人工選擇與唯一性判定可增強目標信息提取的準確性。

首先制定一個人工選擇界面，將剪枝后的DOM樹中的葉子節點放入預選區；然后人工選擇目標信息，程序自動記錄所選葉子節點的編碼；在之前保存的d1的副本中查找所選編碼的葉子節點；確定目標葉子節點的上下界，并在網頁源代碼y1中進行唯一性判定，直到找到唯一的上下界為止；保存上下界信息，以用于構建提取模板。

3.4 構建模板

通過上下界的唯一性判定后，可以構建XML文件形式的提取模板，其中存儲了每段目標信息的上下界，通過讀取此XML文件，可以從相應于此模板的電子商務網站中的各個商品網頁中提取出目標信息，其中還包含了許多HTML標簽，所以還需有一個去除HTML標簽的程序對提取結果進行修正。

一個京東商城模板構建結果如表2所示。

表2 模板構建結果示例

4 實驗結果

爬取京東商城、亞馬遜商城、淘寶網等網站的各類商品網頁源代碼，分別構建網頁的DOM樹，每次比較2～8個網頁DOM樹(即n取2～8)，對于每個n值重復50次取平均值，比較剪枝效果，確定最好的n值，然后運用不同的局部相關性閾值與上下文相關度閾值進行測試。

圖4展示了固定上下文相關度為10時，剪枝率和覆蓋率隨局部相關度的變化情況。隨著局部相關度的增大，剪枝率不斷增大，而覆蓋率在局部相關度大于2時不再為100%；圖5展示了固定局部相關度為2時剪枝率和覆蓋率隨上下文相關度的變化情況。隨著上下文相關度的增大，剪枝率不斷增大，但覆蓋率在局部相關度大于10時不再為100%。

圖4 固定上下文相關度為10時剪枝率和覆蓋率隨局部相關度變化表

圖5 固定局部相關度為2時剪枝率和覆蓋率隨上下文相關度變化表

為了保證模板提取的準確率，剪枝結果的覆蓋率必須保證為100%，以確保能最后保留主題和參數信息，通過圖4、圖5可以看出，上下文相關度取10，局部相關度取2在京東商城網站上能獲得最好的結果，而通過對亞馬遜和淘寶等網站的測試，這兩個值也能得到覆蓋率為100%，如表3所示。

表3 對三個電子商務網站的商品網頁的DOM樹剪枝結果(局部相關度取2，上下文相關度取10)

來源網站剪枝率/%覆蓋率/%京東 82．25100亞馬遜44．87100淘寶 63．09100

其中，剪枝率表示剪去的DOM樹節點占整個DOM樹的平均比例；覆蓋率表示剪枝結束后剩下的DOM樹節點中目標信息占所有應提取的目標信息的比例。

實驗表明，每次比較的網頁數n取4，局部相關度閾值取2，上下文相關度閾值取10，最小長度值取1時能得到最好的剪枝結果，并且在各個網站中具有較高的通用性。

本方法與同領域的其他方法相比，優于周炘等人和侯明燕等人的方法，不需要對目標網站的商品網頁進行深入分析，只需選擇所要提取的目標信息就可自動構建模板；對于結構復雜的電子商務網站的信息提取，優于王琦等人的方法，能夠準確的提取出目標信息。

5 總結與展望

在電子商務網站的商品網頁信息提取領域，人工編寫抽取規則能得到很高的準確率，但需要在網頁每次改版以及有新的電子商務網站出現時進行配置模板，本文的方法在保證較高的準確率的條件下減少了大量人工參與工作，簡化了提取過程。

在剪枝算法中，充分利用了同一電子商務網站中的商品網頁均有相同模板生成的特點，大量提高了剪枝率，為人工選擇減少了大量工作。但是一個商品網頁的源代碼相對于人工操作比較龐大，即使達到現在的剪枝率，剩下的DOM樹也依然較大，尋找提高剪枝率的辦法，能為人工選擇提供方便。另外當能把所有無關信息都進行剪枝時，可實現模板的自動構建。

[1] 楊曉琴，鞠時光，曹慶皇等.面向Deep Web數據自動抽取的模板生成方法[J].計算機應用，2010，27(1)： 200-203.

[2] 周炘.面向電子商務網站的深度搜索與信息抽取研究[D].江西： 江西師范大學軟件學院碩士學位論文，2011.

[3] 侯明燕.基于網頁信息定位的數據抽取技術的研究[D].廣東： 暨南大學碩士學位論文，2011.

[4] 王琦，唐世渭，楊冬青等.基于DOM樹的網頁主題信息自動提取[J].計算機研究與發展，2004，41(10)： 1786-1792.

[5] Beyer K, Viglas S D, Tatarinov I, et al. Storing and querying ordered XML using a relational database system[C]//Proceedings of the 2002 ACM SIGMOD International Conference, 2002: 204-215.

傅彥(1962—)，碩士，教授，博士生導師，主要研究領域為數據挖掘。E?mail：fuyan@uestc．edu．cn徐昭邦(1991—)，碩士研究生，主要研究領域為數據挖掘。E?mail：xzhaobang@163．com夏虎(1981—)，博士，助理研究員，主要研究領域為數據挖掘、復雜網絡。E?mail：xiahu@uestc．edu．cn

全國第十四屆計算語言學會議(CCL 2015)及第三屆基于自然標注大數據的自然語言處理

國際學術研討會(NLP-NABD 2015)聯合征稿啟事

“第十四屆全國計算語言學學術會議”(The Fourteenth China National Conference on Computational Linguistics, CCL 2015)將于2015 年11月13日—14日在廣東外語外貿大學舉行。作為國內最大的自然語言處理專家學者的社團組織——中國中文信息學會(CIPS)的旗艦會議，全國計算語言學會議從1991年開始每兩年舉辦一次，從 2013 年開始每年舉辦一次，經過 20 余年的發展歷程，已形成了十分廣泛的學術影響，成為國內自然語言處理領域權威性最高、口碑最好、規模最大(2014年參會人數超過了 400 名)的學術會議。CCL 著重于中國境內各類語言的計算處理，為研討和傳播計算語言學最新的學術和技術成果提供了高水平的深入交流平臺。

CCL 2015征集各類與漢語和中國少數民族語言相關的計算語言學方面的原創研究和應用論文。論文包括但不限于以下內容：

· 語言處理的認知建模和心理語言學

· 篇章、共指和語用學

· 評測方法

· 語言資源和標注

· 詞匯語義學和詞匯本體論

· 大規模知識獲取和推理

· 機器翻譯

· 多語言自然語言處理

· 自然語言處理應用

· 社交媒體中的自然語言處理

· 命名實體識別與鏈接

· 開放領域的問答系統

· 語義學

· 情感分析、意見挖掘與文本分類

· 社會計算

· 語音識別與合成

· 自然語言處理的統計與機器學習方法

· 文本摘要和生成

· 句法分析與網頁分析

· 詞性標注和組塊分析

· 文本蘊含·文本挖掘、開放域信息抽取與網頁機器閱讀

· 互聯網信息檢索

· 資源稀缺的自然語言處理

· 分詞

· 詞義消歧

· 多模態處理

· 醫學自然語言處理CCL 2015同時接受中文和英文投稿。錄用的稿件分為兩類：口頭報告(Oral)和海報張貼(Poster)。被錄用的Oral 中文稿件將在中國自然語言處理領域最具影響力的期刊《中文信息學報》發表，但作者必須根據會議和期刊的審稿意見進行 相應修改，《中文信息學報》對未完成修改的稿件保留不予發表的權利。被錄用的Poster 中文稿件將推薦至其他計算機類中國科技核心期刊(中國科學技術信息研究所制定) 。部分期刊會要求再審，通過后方能發表。被錄用的英文稿件將由 Springer Lecture Notes in Artificial Intelligence (LNAI)出版。

“第三屆基于自然標注大數據的自然語言處理國際學術研討會”(The Third International Symposium on Natural Language Processing based on Naturally Annotated Big Data, NLP-NABD 2015)將與CCL 2015同時召開。NLP-NABD涵蓋了前面列舉的所有自然語言處理的研究內容，尤其關注在大數據時代自然語言處理的前沿方法和技術。這里所謂的“自然標注”是指由互聯網用戶根據其自身目的(而不是出于自然語言處理研究的目的) 對各種互聯網資源進行的“不自覺”的手工標注，計算語言學家們可以將這些標注自覺地和系統性地應用在自然語言處理的各種研究中。典型的例子是，標點符號有助于詞邊界的識別，社交媒體中的社會標簽

也有助于關鍵詞抽取，而維基百科中的條目類別信息則可以為文本分類提供幫助。在這些例子中，“自然標注”都是以顯式的形式出現的，但在很多情況下，也可以以隱式的形式出現，如短語“Beijing and other cities”“cities such as Beijing”中所蘊含的兩個模式“cities such as NOUN”“NOUN and other cities” 就是一種隱式的“自然標注”，可用于抽取常識知識 ISA(NOUN, city)。NLP-NABD 2015 聚焦國內外在此方向上的各種前沿研究進展，如：如何在自然標注大數據上有效進行大規模無監督/半監督機器學習(如深度學習)，如何將學習到的資源、模型和已有的手工標注的核心資源和核心語言計算模型結合起來，等等。NLP-NABD 2015 受到國家973 計劃項目“面向三元空間的互聯網中文信息處理理論與方法”(編號：2014CB340500)資助支持。

NLP-NABD 2015 針對世界各種語言的研究(不僅限于中文)，只接受英文投稿。錄用稿件將與CCL 2015錄用的英文論文一起由Springer發表于LNAI系列上。

CCL 2015 和 NLP-NABD 2015 的中文投稿不超過 10 頁，英文投稿不超過 12頁 。 中文投稿的格式請參照中文信息學報的投稿指南(http://www.cipsc.org.cn/jsip/tougao.php)，英文投稿的格式請參照Springer的投稿指南(http://www.springer.de/comp/lncs/authors.html)。Springer會將LNAI出版的論文提交給EI以申請進入其檢索。根據Springer以往的經驗，論文獲得EI收錄的機會相當高。2013年和2014年CCL和NLP-NABD錄取的英文稿件全部被EI收錄。更多關于LNAI索引的信息請參閱： http://www.springer.com/computer/lncs?SGWID=0-164-6-1068921-0。

自2014年起，CCL和NLP-NABD開始設立最佳論文獎，對高質量中文和英文稿件分別予以獎勵。CCL 2015和NLP-NABD 2015將設立兩項最佳論文獎，由程序委員會負責評選。其中，“CCL 2015 最佳論文獎”用于獎勵中文信息處理方面的優秀中文論文，“NLP-NABD 2015最佳論文獎”用于獎勵大數據環境下自然語言處理方面的優秀英文論文。程序委員會將為每篇獲獎論文頒發 3000 元人民幣獎金和獲獎證書。

CCL 2015 和 NLP-NABD 2015 時間表：

· 論文投稿的截止日期：2015年6月1日

· 錄用通知發出日期：2015年7月26日

· 最終版提交日期：2015年8月10日

投稿信息：本次會議將采用雙盲審稿，所以作者姓名和單位不可以出現在投稿的論文中，作者的自引不可采用“我們提出…”，而是用“作者名字提出…”。所有稿件要求以 PDF 文件形式通過 START 系統提交，提交網址為https://www.softconf.com/e/ccl2015/。

關于平行投稿政策：本次會議允許作者將同一稿件同時投向自然語言處理領域的頂級國際會議(如EMNLP 2015)，只要該國際會議也有類似的平行投稿政策。在投稿時，必須注明該稿件同時投至此類會議。作者在接收到錄用通知后，必須在最終版提交日期(2015 年8月10日)之前告知程序委員會是否在本次會議發表。一旦確定，必須撤回在其他會議的稿件。本次會議不接收任何與已經公開發表的論文完全相同或者高度重合的稿件。

Reverse Match Based Semi-automatic Entity Template Extraction for E-commerce Websites

FU Yan, XU Zhaobang, XIA Hu, ZHOU Junlin

(Web Sciences Center, School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu, Sichuan 611731, China)

Generally, the distribution of the subject information in the Web page is centralized .Therefore，we can utilize this characteristics of Web page to extract the subject information automatically. Due to the fact that the HTML label in the page source code is not well qualified, it is difficult to construct a DOM tree with accurate structure through the forward matching. This article presents a new method which applies the reverse matching to construct a complete DOM tree. By deleting the insignificant node the DOM tree, we can select from the remained information node labels manually to finalize the templeaterdeciden if they are unique. This is a general and semi- automatic method, and experiments on the e-commerce webpages are reported in this paper.

reverse matching; DOM tree; template extraction; information extraction

1003-0077(2015)02-0157-06

2013-04-08 定稿日期： 2013-07-11

國家自然科學基金(61103109，11105024，61003231)，中央高校基本科研業務費(ZYGX2011J057，ZYGX2012J071，ZYGX2012J085)，四川省科技項目(2010HH0002，2011GZ0106，20112Z0001, 2012RZ0002, 2012RZ0003)，高等學校博士學科點專項科研基金(20120185120017)

TP391

A