一種對半結構化文檔集進行文本挖掘的方法

《一種對半結構化文檔集進行文本挖掘的方法》是北京北大方正技術研究院有限公司、北京大學計算機科學技術研究所於2002年8月29日申請的專利，該專利的申請號為021290458，申請公布號為CN1399228，公布日為2003年2月26日，發明人是楊建武、陳曉鷗、吳於茜、萬小軍、王選、陳堃銶。該發明屬於智慧型信息處理技術。

《一種對半結構化文檔集進行文本挖掘的方法》針對2002年8月以前的文本挖掘處理半結構化文檔集存在的挖掘效果差的缺陷，提出了一種針對半結構化文檔的結構連結向量模型的挖掘方法。它能夠綜合利用半結構化文檔中的字詞信息、結構信息與連結信息，並以統一的數學模型進行表示。採用該模型對半結構化文檔集進行文本挖掘，由於充分的利用了半結構化文檔中的結構信息與連結信息，挖掘效果大幅度改進。

2013年10月，《一種對半結構化文檔集進行文本挖掘的方法》獲得第十五屆中國專利優秀獎。

（概述圖為《一種對半結構化文檔集進行文本挖掘的方法》摘要附圖）

基本介紹

• 中文名：一種對半結構化文檔集進行文本挖掘的方法
• 類別：發明專利
• 公布號：CN1399228
• 公布日：2003年2月26日
• 申請號：021290458
• 申請日：2002年8月29日
• 申請人：北京北大方正技術研究院有限公司、北京大學計算機科學技術研究所
• 地址：北京市海淀區上地五街九號方正大廈
• 發明人：楊建武、陳曉鷗、吳於茜、萬小軍、王選、陳堃銶
• 分類號：G06N7/00、G06F17/21
• 專利代理機構：北京英賽嘉華智慧財產權代理有限責任公司
• 代理人：田明、陳宇萱

專利背景

隨著網際網路的迅速發展，HTML、XML等半結構化文檔大量出現，半結構化文檔既不同於無結構的純文本文檔也不同於結構規整的關係資料庫中的數據。如何從這樣大量的文檔中快速有效地獲得人們所需要的文檔以及如何發現這些文檔中的隱含的規律便是人們所面臨的問題。對半結構化文檔集進行分析挖掘就是用來解決這些技術問題的方法。

截至2002年8月，對半結構化文檔的挖掘主要有兩類方法：一類是將半結構化文檔視為無結構的純文本文檔，採用傳統的文本挖掘方法對半結構化文檔進行文本挖掘；另一類是根據半結構化文檔的新特徵提出新的挖掘方法。在傳統的文本挖掘中，將文檔作為無結構的數據，以詞條為單位進行處理，提出並被套用的文檔模型包括：布爾模型、機率模型、向量空間模型。採用這些模型對半結構化文檔集進行挖掘時，挖掘效果並不理想，因為半結構化文檔的結構信息與連結信息沒有被利用。2000年，D. Guillaume等人在文章《XML文檔聚類》（DamienGuillume and Fionn Murtagh Clustering of XML documents.Computer Physics Communications（127）2000.215~227） 中公開了一種XML文檔聚類技術，他們將XML文檔中的元素作為節點，文檔中XLINK作為邊，構造拓撲圖，通過給拓撲圖的邊賦予不同的權重，採用邊剪下最小原理對拓撲圖進行分割，從而實現對XML文檔的聚類。2000年JeongheeYi等人在美國波斯頓的數據挖掘國際會議上（Jeonghee Yi，Neel Sundaresan.A Classifier for Semi-StructuredDocuments.KDD2000，Boston，MA USA）公開了一種利用半結構化文檔的結構信息對文檔向量空間模型進行擴展的向量模型，將文檔元素用嵌套定義的向量進行描述，並給出了基於該擴展模型利用機率統計進行文檔分類的算法。這些技術中，僅使用了半結構化文檔的部分信息，沒有充分利用半結構化文檔中的信息以便獲得好的文本挖掘效果，更沒有形成統一的數學模型。

發明內容

專利目的

針對2002年8月以前技術中存在的問題，《一種對半結構化文檔集進行文本挖掘的方法》的目的是利用半結構化文檔的特點，提出一個數學模型，以及基於該模型對半結構化文檔集進行文本挖掘的方法。該方法對半結構化文檔中的字詞信息、結構信息、連結信息採用統一-的數學模型進行描述，利用這一方法對半結構化文檔進行文本挖掘，可以大大提高挖掘效果。

技術方案

《一種對半結構化文檔集進行文本挖掘的方法》包括以下步驟：

第一、讀入文檔，並對文檔進行結構分析，分別判斷文檔各節點是否在結構樹中已存在，如果結構樹中還沒有該節點信息，則需要給結構樹添加該節點信息，並給節點一個唯一標識號；

第二、如果當前分析的節點包含子節點，則繼續分析其第一個子節點，直到不包含子節點的數據節點；如果當前節點為數據節點，則對數據節點的文欄位進行分詞，並根據所處的節點位置，形成結構向量的一個分量；

第三、如果該文欄位包含連結信息，則讀入其連結資源，並獲取其連結資源的結構向量；

第四、分析器繼續找其下一個兄弟節點進行分析，如果已不存在下一個兄弟節點則向上層回溯，找其父節點的下一個兄弟節點，直到文檔分析結束；

第五、將這一過程中的所有結構向量的分量組合成為該文檔的結構向量，將連結資源的結構向量拼合成當前文檔的連結向量，最後形成當前文檔的結構連結資源，輸入到挖掘模組，進行文本的挖掘分析。

有益效果

《一種對半結構化文檔集進行文本挖掘的方法》的效果在於針對了半結構化文檔的特點，提出一種新的對半結構化文本挖掘的方法。該方法能有效地利用半結構化文檔中的字詞信息、結構信息與連結信息，並以統一的數學模型進行表示，從而大大提高了挖掘的效果，該方法可廣泛套用於智慧型信息處理領域。

附圖說明

圖1是《一種對半結構化文檔集進行文本挖掘的方法》的流程圖；

圖2是文檔結構樹示意圖；

圖3是抽象的文檔結構樹示意圖。

權利要求

1.《一種對半結構化文檔集進行文本挖掘的方法》包括以下步驟：

第一、讀入文檔，並對文檔進行結構分析，分別判斷文檔各節點是否在結構樹中已存在， 如果結構樹中還沒有該節點信息，則需要給結構樹添加該節點信息，並給節點一個唯一標識號；

第二、如果當前分析的節點包含子節點，則繼續分析其第一個子節點，直到不包含子節點的數據節點；如果當前節點為數據節點，則對數據節點的文欄位進行分詞，並根據所處的節點位置，形成結構向量的一一個分量；

第三、如果該文欄位包含連結信息，則讀入其連結資源，並獲取其連結資源的結構向量；

第四、分析器繼續找其下一個兄弟節點進行分析，如果已不存在下一個兄弟節點則向上層回溯，找其父節點的下一個兄弟節點，直到文檔分析結束；

第五、將這一過程中的所有結構向量的分量組合成為該文檔的結構向量，將連結資源的結構向量拼合成當前文檔的連結向量，最後形成當前文檔的結構連結資源，輸入到挖掘模組，進行文本的挖掘分析。

實施方式

下面結合附圖對《一種對半結構化文檔集進行文本挖掘的方法》作進一步地描述。文中選用了中國百科術語資料庫中的部分術語詞條文檔作為實施例數據，每個術語詞條文檔是一個半結構化XML文檔。

第一、如圖1所示，首先需要讀入文檔，並對文檔進行結構分析，如圖2所示。分別判斷文檔各節點是否在結構樹中已存在，如果結構樹中還沒有該節點信息，則需要給結構樹添加該節點信息，並給節點一個唯一標示號，如圖3所示。

第二、如果當前分析的節點包含子節點，則繼續分析其第一個子節點，直到不包含子節點的數據節點；如果當前節點為數據節點，對數據節點的文欄位進行分詞，並根據所處的節點位置，形成結構向量的一個分量；

第三、如果該文欄位包含連結信息，則讀入其連結資源，並獲取其連結資源的結構向量；

第四、分析器繼續找其下一個兄弟節點進行分析，如果已不存在下一個兄弟節點則向上層回溯，找其父節點的下一個兄弟節點，直到文檔分析結束；

第五、將這一過程中的所有結構向量分支組合成為該文檔的結構向量，將連結資源的結構向量拼合成當前文檔的連結資源，最後形成當前文檔的結構連結資源，輸入到K-Means聚類模組（數據挖掘模組的一種），進行文本的挖掘分析。

為了驗證該發明的有效性，採用基於2002年8月以前向量空間模型TFIDF與該發明提出的基於結構連結向量模型SLVM的方法進行了對比試驗。聚類質量的評價算法採用由Bjorner Larsen等人提出的Fmeasure算法，其F值越接近1，表明聚類效果越好。試驗結果如表1所示。

實驗表明：採用傳統的方法，其F值落在0.65~0.73之間；而採用該發明提出的方法，由於充分利用了文檔中的結構信息與連結信息，聚類結果的F值提高到0.82~0.86.

表1聚類對比實驗結果

	基於向量空間模型TFIDF			基於結構連結向量模型
Mi	Nj	M（ni，j）	M（F（i，j）	Nj	M（ni，j）	M（F（i，j））
63	60	37	0.602	59	52	0.852
76	69	53	0.731	71	62	0.844
82	88	62	0.729	89	79	0.924
86	87	68	0.786	86	74	0.860
73	67	49	0.7	70	60	0.839
61	78	41	0.59	69	53	0.815
45	45	32	0.711	42	37	0.851
54	63	38	0.65	58	41	0.732
66	74	52	0.743	71	58	0.847
38	28	20	0.606	35	31	0.849
76	68	53	0.736	72	64	0.865
42	35	23	0.597	40	32	0.780
	F=0.69			F=0.84

榮譽表彰

2013年10月，《一種對半結構化文檔集進行文本挖掘的方法》獲得第十五屆中國專利優秀獎。