劉卓 徐斌
蘇州科技學院電子與信息工程學院 江蘇 215011
自20世紀80年代以來,隨著Internet技術的高速發(fā)展,信息化的浪潮席卷全球,社會的每個角落都有了數(shù)字化信息的身影。其中尤其以Web頁數(shù)量最為龐大,并且大約以每4至 6 個月翻一倍的速度增加。巨量的 Web頁在為我們提供了海量的信息同時,又給我們提出了新的挑戰(zhàn),即如何從這些浩瀚的Web頁信息中快捷準確地得到我們想要的信息。自然我們不能夠采用人工的方式完成這項任務,借助于計算機采用數(shù)據(jù)挖掘的方法是目前廣泛使用的技術。
數(shù)據(jù)挖掘(data mining)習慣上又稱為數(shù)據(jù)庫中知識發(fā)現(xiàn)(Knowledge Discovery in Database, KDD),簡單的說就是利用計算機,從浩瀚如海的信息資源中找出真正具有價值的信息。數(shù)據(jù)挖掘可以按以下不同角度分類:從挖掘的數(shù)據(jù)源分類,一般可以分為關系數(shù)據(jù)庫、事務數(shù)據(jù)庫、空間數(shù)據(jù)庫、時間數(shù)據(jù)庫、面向對象數(shù)據(jù)庫、文本數(shù)據(jù)庫、多媒體數(shù)據(jù)庫、主動數(shù)據(jù)庫、Internet信息庫挖掘等。從挖掘出的知識分類,一般情況下,數(shù)據(jù)挖掘可以分為關聯(lián)規(guī)則、特征規(guī)則、分類規(guī)則、聚類規(guī)則、序列模式、數(shù)據(jù)綜合和概括、總結規(guī)則 、趨勢分析、偏差分析、模式分析、孤立點分析挖掘等。按照挖掘所采用的技術分類,數(shù)據(jù)挖掘一般可以分為統(tǒng)計分析方法,遺傳算法、粗糙集方法、決策樹、人工神經(jīng)網(wǎng)絡、模糊邏輯、規(guī)則歸納、聚類分析、模式識別、最鄰接技術、可視化技術挖掘等。Web挖掘就是數(shù)據(jù)挖掘方法中的一種,它是指從大量Web文檔的集合C中發(fā)現(xiàn)隱含的模式p。如果將C 看作輸入,將p看作輸出,那么Web挖掘的過程就是從輸入到輸出的一個映射N: C→p。按照挖掘對象的不同,Web挖掘又可以分為兩類:內容挖掘和結構挖掘。內容挖掘指的是從Web文檔的內容信息中抽取知識,結構挖掘指的是從 Web文檔的結構信息中推導知識。Web內容挖掘又分為對文本文檔(包括 text,HTML 等格式)和多媒體文檔(包括image,audio,video 等媒體類型)的挖掘。Web 文本挖掘可以對Web上大量文檔集合的內容進行總結、分類、聚類、關聯(lián)分析,以及利用 Web 文檔進行趨勢預測等。本文所探討的對象為針對于Web文本文檔的挖掘。
聚類是根據(jù)個體所滿足的屬性對個體域進行剖分,把屬性相同或相近的個體劃歸為同一個“概念類”的過程,它是機器學習領域中的一個重要研究方向。文檔聚類的目標即使將文檔聚集成類,使得類與類之間的相似度盡量的小,而類內的相似度盡量的大。處理聚類問題,主要有以下幾種方法:統(tǒng)計方法、機器學習方法、神經(jīng)網(wǎng)絡方法和面向數(shù)據(jù)庫的方法等。
聚類算法一般分為分割聚類法和分層聚類法。分割聚類算法通過一個評價函數(shù)把數(shù)據(jù)集分割為K個部分,需要K作為輸入?yún)?shù)。典型的分割聚類算法有 K-means 算法、K-medoids 算法、CLARANS 算法;分層聚類是由不同層次的分割聚類組成,層次之間的分割具有嵌套的關系,不需要K作為輸入?yún)?shù)。典型的分層聚類算法是 BIRCH算法、DBSCAN算法和CURE算法。目前,使用聚類方法自動建立文檔的類別過程通常如下所示:
(1)輸入多篇無類別標識的文本。
(2)借助詞典對這些文本進行分詞處理。
(3)提取每一個文本的特征向量。
(4)利用文本的特征向量,使用聚類算法進行類別組合計算。
(5)人工為每個得到的文本類別建立類別標識。
本文采用分層聚類法并結合了改進的特征詞權重計算等方法,進行了無類別文檔集合的劃分處理。具體算法如下:輸入:無文本類別標識的文本集輸出:標識了類別的訓練文本集(1)文本分詞處理。
(2)統(tǒng)計詞頻,完成非完整詞串取舍,提取出文本文檔中的關鍵詞。
(3)公式(1)計算詞的特征值。
(4)按照詞的特征值使用插入排序算法遞增排序,并從排好序的詞集中提取前M個詞作為當前文檔的特征詞,從而得到每一個文檔的特征向量di(i=1,2,3,……,n)。
(5)di看作是一個具有單個成員的類Ci={di},從而構成了該文檔集合的一個聚類C(n)={c1,c2,……,cn}。
(6)用公式(2)計算C中每對類(ci,cj)之間的相似度。
(7)選取具有最大相似度的類對,并將其合并為一個新的類,從而構成該文檔集合的一個新的聚類 C(n-1)={c1,c2,……,cn-1}。
(8)如果n!=1,轉到步驟3。
(9)對各個類文檔進行人工建立標號。算法說明:
其中:P為位置加權系數(shù),Q為受限語義加權系數(shù),L為Wi的長度,Ti為在文檔中出現(xiàn)的頻率,S為總文檔數(shù),SD為在其中出現(xiàn)至少一次的文檔的數(shù)目。
其中:n為文檔 dx與 dy共同所有的特征詞個數(shù),|dx|文檔dx中特征詞總數(shù),|dy|文檔dy中特征詞總數(shù),txk為向量dx第k維值。
本文對文本挖掘中所使用的層次聚類分析方法進行了探討,通過以上聚類算法的分析處理,我們可以在一定范圍內完成對各類訓練文本庫的建立。但是針對于公式中參數(shù)的選取還需要進一步的研究,以便在更大范圍內完成訓練語料庫的建立。
[1] 鄒臘梅,肖基毅,龔向堅.Web 文本挖掘技術研究.情報雜志.2007.
[2] 王繼成,潘金貴,張福炎.Web 文本挖掘技術研究.計算機研究與發(fā)展.1999.
[3] J.Han,Micheline,Kamber,Data,Mining:Concepts and Tchniques.San Mateo,CA:Morgan Kaufmann.2000.
[4] 張紅云,石陽,馬垣.數(shù)據(jù)挖掘中聚類算法比較研究.鞍山鋼鐵學院學報.2001.
[5] 于琨,糜仲春,蔡慶生.可應用與互聯(lián)網(wǎng)的自學習中文關鍵詞抽取算法.中國科學技術大學報.2002.
[6] 顧立帆,王永成.聯(lián)想樹分析方法及其在無詞庫中文自動標引中的應用.情報學報.1992.
[7] 何新貴,彭甫陽.中文文本的關鍵詞自動抽取和模糊分類.中文信息學報.1998.
[8] 羅三定,陸文彥,王浩,賈維嘉.基于概念的文本類別特征提起與文本模糊匹配.計算機工程與應用.2002.
[9] 孫麗華,張積東,李靜梅.一種改進的 KNN 方法及其在文本分類中的應用.應用技術. 2002.