基于ALCIF描述邏輯的Web頁面聚類

富豪，鄧立國(guó)

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

在Web 頁面聚類過程中為了能有效處理標(biāo)簽內(nèi)容以及標(biāo)簽內(nèi)容之間的聯(lián)系，選用ALCIF 描述邏輯表示方法來對(duì)Web 頁面信息進(jìn)行抽取與存儲(chǔ)，并對(duì)抽取到的知識(shí)內(nèi)容進(jìn)行約減，從而實(shí)現(xiàn)對(duì)Web 文檔的降維，以此節(jié)約聚類時(shí)間。最后用實(shí)驗(yàn)證明這種知識(shí)表示方法對(duì)于Web 頁面聚類的有效性。

Web 頁面聚類；ALCIF 描述邏輯；K-means

0 引言

國(guó)外描述邏輯的發(fā)展由描述邏輯工作組進(jìn)行推進(jìn)，最近兩年從描述邏輯工作組的特邀報(bào)告及其所展示的成果來看，描述邏輯的重點(diǎn)始終在本體研究和語義網(wǎng)上面?？偟膩砜疵枋鲞壿嫷拇蟛糠盅芯窟€處在理論方面，Renata Wassermann 博士使用描述邏輯在OWL上進(jìn)行實(shí)踐，拉近了描述邏輯理論和實(shí)踐的距離。國(guó)內(nèi)對(duì)于描述邏輯的研究有申宇銘教授的文獻(xiàn)[8]，提出了???模型關(guān)系并給出表達(dá)定理，提高了描述邏輯的表達(dá)能力。除此之外張富博士在文獻(xiàn)[9]中實(shí)現(xiàn)了一個(gè)原型工具，能夠自動(dòng)將XML 轉(zhuǎn)化成本體，然后利用這些本體進(jìn)行XML 知識(shí)的推理。

隨著十幾年來互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)頁數(shù)量也開始激增，根據(jù)我國(guó)最新的《41 次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》來看，我國(guó)的網(wǎng)站數(shù)量已經(jīng)達(dá)到了533 萬個(gè)[1]，如何快速又準(zhǔn)確地返回搜索結(jié)果給搜索引擎帶來不小挑戰(zhàn)。

描述邏輯是知識(shí)表示語言的一種統(tǒng)稱，具體有多種形式，其中ALC 是最基本也是最簡(jiǎn)單的描述邏輯形式。ALC 有很多的變型，包括，ALCF、ALCN、ALCIF、ALCIQ 等，其具體推理復(fù)雜性可參考文獻(xiàn)[2]。另外SROIQ、??、DL-Lite 等也屬于描述邏輯，其中W3C 所推薦的OWL2 的直接語義是根據(jù)SROIQ 擴(kuò)展而來。目前由于本體語言（Ontology Language）的發(fā)展和Web本體語言（OWL）的廣泛使用，描述邏輯及其各種推理算法也得以快速發(fā)展和廣泛使用。本文根據(jù)Web 頁面數(shù)據(jù)的半結(jié)構(gòu)化特點(diǎn)采用ALCIF 描述邏輯對(duì)數(shù)據(jù)知識(shí)進(jìn)行表示。

Web 頁面內(nèi)容雖然包含多種多樣的數(shù)據(jù)，如聲音、文字、視頻等，但是具有一定的標(biāo)簽結(jié)構(gòu)，標(biāo)簽里面含有結(jié)構(gòu)信息，而且兩個(gè)對(duì)應(yīng)的段落標(biāo)簽之間含有文本內(nèi)容信息，傳統(tǒng)的聚類技術(shù)大多采用抽取標(biāo)簽里的數(shù)據(jù)信息進(jìn)行聚類，例如DOM 解析樹的方法和SAX 方法都忽略了段落標(biāo)簽里面的文本內(nèi)容信息，在這種方法下進(jìn)行文檔相似度度量顯然存在一定問題。本文提出的基于ALCIF 描述邏輯的Web 頁面信息表示方法能夠全面考慮HTML 標(biāo)簽結(jié)構(gòu)信息和文檔內(nèi)容信息，對(duì)于保留各項(xiàng)細(xì)節(jié)方面有很大優(yōu)勢(shì)。

本文提出的基于描述邏輯的Web 頁面聚類方式，在保證速度的同時(shí)，由于使用了描述邏輯使得聚類結(jié)果也更加準(zhǔn)確，同時(shí)聚類結(jié)果的可解釋性也得到提高。

1 描述邏輯

1.1 描述邏輯概念及應(yīng)用

描述邏輯是基于概念的知識(shí)表示方法，是一階謂詞邏輯的一個(gè)可判定子集，與一階謂詞相比，描述邏輯可讀性更好[3]。Attributive Language with Complements（簡(jiǎn)稱ALC）是基本的描述邏輯，本文采用的ALCIF 描述邏輯在ALC 的基礎(chǔ)上增加了角色反（Role Inverse）和功能角色（Functionality Role）。

描述邏輯廣泛應(yīng)用于知識(shí)表示、語義網(wǎng)（Semantic Web）、推理機(jī)以及人工智能等領(lǐng)域。

1.2 ALCIF描述邏輯知識(shí)庫

為了便于知識(shí)表示和理解，以及考慮到XML 在Web 中扮演的關(guān)鍵角色，采用XML Schema 表示方法對(duì)Web 頁面進(jìn)行結(jié)構(gòu)和內(nèi)容表示。這一過程所使用的描述邏輯定理如下：

（1）（?-）I={＜x，y ＞|＜y，x ＞ ∈ ?I} （角色反）

（2）（C?D）I=CI∩DI（交）

（3）（C?D）I=CI∪DI（并）

（4）（?C）I=ΔICI（否）

（5）（??.C）I={a|?b.＜a，b ＞∈?I并且b∈CI} （存在限定）

（6）（??.C）I={a|?a.＜a，b ＞∈?I并且b∈CI} （全稱限定）

描述邏輯為概念和角色的結(jié)合，兩者由構(gòu)造子經(jīng)簡(jiǎn)單的概念和角色來構(gòu)造復(fù)雜的概念和角色，概念對(duì)應(yīng)于邏輯中的一元謂詞，角色對(duì)應(yīng)于二元謂詞，構(gòu)造子決定語言的表達(dá)能力，表達(dá)能力越強(qiáng)，相應(yīng)對(duì)的構(gòu)造子越復(fù)雜。在描述邏輯中，每個(gè)句子對(duì)應(yīng)一個(gè)邏輯表達(dá)式。

Web 頁面也稱為HTML 頁面，其包含內(nèi)容豐富，因此具有一定復(fù)雜性。為了將HTML 的結(jié)構(gòu)和內(nèi)容都保留下來，在數(shù)據(jù)抽取的時(shí)候使用了XML 格式文件的XSD（XML Schema Definition）文件定義思想。通過XSD 這一結(jié)構(gòu)來組織HTML 頁面內(nèi)容。一個(gè).xsd 文件截圖如圖1 所示。

圖1 XML Schema代碼片段截圖

使用描述邏輯進(jìn)行推理所基于的知識(shí)庫里包含兩種子庫，一種是TBox，包含了HTML 的各種術(shù)語即標(biāo)簽名稱，另一種是ABox，所包含HTML 的具體屬性斷言。知識(shí)庫表示為К=＜TBox，ABox＞。TBox 是一個(gè)有限集合，TBox 通過概念描述的定義構(gòu)造，里面包含術(shù)語知識(shí)TBox 通常由具有有限個(gè)包含關(guān)系的數(shù)學(xué)結(jié)構(gòu)集合表示。

代碼1：HTML 的TBox。

將圖1中的HTML代碼與所對(duì)應(yīng)的ABox 模型里面包含的是擴(kuò)展知識(shí)是這樣的，這種擴(kuò)展知識(shí)通常也稱作斷言知識(shí)如代碼2：一個(gè)HTML 的ABox 模型S'（與代碼1 對(duì)應(yīng)）。

知識(shí)庫К被表示為ABox 集合（代碼2）和TBox 集合（代碼1）兩種形式，需要注意的是這里的ABox 和TBox 集合里面的元素未被全部列舉出。

2 基于知識(shí)庫模型的數(shù)據(jù)抽取

HTML 標(biāo)簽知識(shí)庫通過ABox 模型S'建立，并在描述邏輯知識(shí)庫中存儲(chǔ)了模式表示的實(shí)例，現(xiàn)在就可以使用描述邏輯推理來對(duì)XML 模式表示進(jìn)行推斷。下面將HTML 對(duì)應(yīng)到知識(shí)庫過程進(jìn)行正確性驗(yàn)證，如圖2 所示。在這一過程中知識(shí)庫被不斷擴(kuò)展，以適應(yīng)XML Schema 帶來的數(shù)據(jù)增量式拓展。

使用Python 工具對(duì)HTML 數(shù)據(jù)內(nèi)容進(jìn)行抽取，抽取的內(nèi)容包含頁面名稱、標(biāo)簽名稱還有其它標(biāo)簽里的文本內(nèi)容，如title 標(biāo)簽、字號(hào)標(biāo)簽里的內(nèi)容以及段落標(biāo)簽p 里的全部?jī)?nèi)容，尤其段落標(biāo)簽p 可能包含了大段的文本內(nèi)容。再用描述邏輯知識(shí)庫對(duì)大段的文本內(nèi)容進(jìn)行縮減形成若干個(gè)屬性，通過XML Schema 將標(biāo)簽數(shù)據(jù)聯(lián)系起來。

根據(jù)HTML 文件知識(shí)庫的表示方法，將HTML 文檔內(nèi)容按照ABox 進(jìn)行組織。組織后的HTML 文檔中P 標(biāo)簽里面的文本內(nèi)容由TBox 驗(yàn)證其中的包含關(guān)系將文本內(nèi)容進(jìn)行縮減。然后將抽取文本保存在文本文件中。將文本內(nèi)容映射到知識(shí)庫中時(shí)，得到一個(gè)文檔的特征概念集合T={t1，t2，t3，…，tn}，經(jīng)過TBox 包含關(guān)系處理后得到的是一個(gè)簡(jiǎn)化的概念集合T’，這一過程會(huì)極大地降低文本數(shù)據(jù)維度。在第4 部分直接對(duì)這些HTML 文件進(jìn)行相似度計(jì)算。

在HTML 網(wǎng)頁中title 標(biāo)簽和某些文本內(nèi)容相互聯(lián)系，可能是和文件內(nèi)的，也可能和其他文件有所關(guān)聯(lián)，嘗試著使用描述邏輯找出其中的關(guān)系。例如大學(xué)里Jon Damon Reese 教授的個(gè)人主頁，嘗試找出里面J D Reese 教課的課程名，然后有哪些學(xué)生選了J D Reese的課，從而建立一種關(guān)聯(lián)關(guān)系并在聚類中考慮到這種關(guān)系。

3 文檔向量與相似度計(jì)算

在第3 部分進(jìn)行了HTML 文檔內(nèi)容提取，并將抽取的數(shù)據(jù)內(nèi)容保存在知識(shí)庫中。通過特征項(xiàng)與知識(shí)庫進(jìn)行匹配化簡(jiǎn)，得到一個(gè)新的向量T’{t1，t2，t3，…，tm}（m≤n）。

傳統(tǒng)的VSM 模型將文本空間看做一個(gè)有一組正交詞條表示對(duì)的向量空間，其中每個(gè)文本表示的規(guī)范化特征向量V（d）=（t1，w1（d）;t2，w2（d）;…tn，wn（d）），tn為詞條項(xiàng)，wn（d）是tn在d 中的權(quán)重。TF-IDF 是一種常用的詞條權(quán)重確定方法。這里不考慮同一文件中詞出現(xiàn)的先后順序和頻率，即要求同一ti不重復(fù)出現(xiàn)，這時(shí)可以把t1，t2，…，tn看作一個(gè)具有n 維的坐標(biāo)系，將權(quán)重wn（d）看作坐標(biāo)值，這樣一個(gè)文檔就被表示為一個(gè)n 維的坐標(biāo)向量。V（d）=（w1，w2，…，wn）稱作文本d 的向量空間模型。其中每個(gè)詞條的權(quán)重計(jì)算如下：

其中D 是HTML 文檔集，d 表示任意一個(gè)HTML文檔，t 為一個(gè)文檔中的詞，tf（d，t）為詞t 在文檔d 中出現(xiàn)的頻率，|D|為文檔集的總數(shù)，tf（t）為詞t 在HTML 文檔集中出現(xiàn)的次數(shù)，那么tfidf（d，t）就表示詞t 在文檔d中的權(quán)重。

由于需要匹配知識(shí)庫，從而判斷包含關(guān)系，進(jìn)而縮減一個(gè)文檔的維度。因此會(huì)得到一個(gè)新的權(quán)重計(jì)算公式：

其中nwi為概念c 在表示文檔di時(shí)的權(quán)重，twk為匹配知識(shí)庫前根據(jù)TF-IDF 計(jì)算得到的權(quán)重，其中r 為：

通過新的權(quán)重計(jì)算公式可以得到一個(gè)文本的語義表示模型，每一個(gè)HTML 文本可以表示成V（d）=（nw1，nw2，…，nwn），若存在包含關(guān)系則V（d）=（nw1，nw2，…，nwm）。

向量計(jì)算公式參數(shù)設(shè)置如下：

tfidf_vectorizer = TfidfVectorizer（max_df=0.7，max_features=200000，

min_df=0.1，stop_words='english'，

use_idf=True，tokenizer=tokenize_and_stem，ngram_range=（1，3））

4 K-means算法

使用傳統(tǒng)的K-means 算法需要先確定聚類點(diǎn)的數(shù)目，雖然不符合聚類的不確定性特點(diǎn)，而且K-means 算法初始簇中心點(diǎn)的選擇具有較大隨機(jī)性，但是由于K-means 算法的易用性以及可在大數(shù)據(jù)級(jí)上應(yīng)用而被廣泛接受。K-means 算法的隨機(jī)性可能導(dǎo)致最終的聚類結(jié)果不穩(wěn)定，兩次運(yùn)行結(jié)果存在差異，針對(duì)這一點(diǎn)指定同一個(gè)聚類初始簇中心即可完美解決。王勇等在聚類之前對(duì)數(shù)據(jù)進(jìn)行分層以此來獲得聚類數(shù)量的上限，快速確定聚類范圍解決了K-means 聚類算法無法確定最佳聚類數(shù)目的問題[5]。邵倫等通過將樣本數(shù)據(jù)映射多維網(wǎng)格中，然后將樣本數(shù)最多的網(wǎng)格作為聚類過程中的初始網(wǎng)格然后進(jìn)行K-means 聚類，這種方法很大程度上解決了容易陷入最優(yōu)解的問題[6]。本文則選用K-means++算法在初始簇聚類中心點(diǎn)的選擇上給與了優(yōu)化。

4.1 算法的基本思路

K-means++算法在簇中心點(diǎn)的初始化過程中的基本原則是各個(gè)簇中心點(diǎn)間的相互距離盡可能遠(yuǎn)，這樣能在一定程度上解決聚類過程中隨機(jī)初始各個(gè)簇中心點(diǎn)所帶來的弊端。算法首先隨機(jī)選取一個(gè)數(shù)據(jù)（n=1）點(diǎn)作為第一個(gè)聚類初始點(diǎn)，其次選取距離前n 個(gè)數(shù)據(jù)點(diǎn)較遠(yuǎn)的數(shù)據(jù)點(diǎn)為第n+1 個(gè)初始簇中心點(diǎn)，計(jì)算樣本與聚類中心點(diǎn)距離為[7]：

4.2 算法流程

輸入：數(shù)據(jù)集T，簇?cái)?shù)量K。

輸出：劃分為k 個(gè)簇的數(shù)據(jù)集T。

算法過程描述：

（1）從T 中隨機(jī)選擇一個(gè)數(shù)據(jù)點(diǎn)作為第一個(gè)簇中心點(diǎn)；

（2）選擇樣本與簇中心點(diǎn)距離較遠(yuǎn)的點(diǎn)作為下一個(gè)簇中心點(diǎn)；

（3）重復(fù)（2）直到K 個(gè)簇初始中心點(diǎn)都被確定；

（4）使用K-means 算法計(jì)算調(diào)整簇中心點(diǎn)的位置；

（5）輸出具有K 個(gè)簇的數(shù)據(jù)集T。

5 實(shí)驗(yàn)環(huán)境及結(jié)果

實(shí)驗(yàn)硬件條件是處理器是英特爾酷睿i5-4200U，硬盤用的東芝5400 轉(zhuǎn)的500G 機(jī)械硬盤，內(nèi)存為海力士4+8G 的DDR3L，內(nèi)存頻率為1600MHZ。軟件上使用Python 3.6 版本，數(shù)據(jù)集采用的是WebKB。

聚類之前使用Tidy 對(duì)數(shù)據(jù)集進(jìn)行了規(guī)范化處理，提取XML 的XSD，然后根據(jù)謂詞邏輯中包含思想用Gensim 的Word2Vec 訓(xùn)練詞向量，對(duì)標(biāo)簽關(guān)系進(jìn)行學(xué)習(xí)，形成特定的模型。之后使用算法結(jié)合得到的模型對(duì)WebKB 數(shù)據(jù)集進(jìn)行聚類，聚類時(shí)也能更好地解釋W(xué)eb 頁面聚類結(jié)果，當(dāng)K=8 時(shí)聚類結(jié)果如圖3 所示。

圖3 Python實(shí)驗(yàn)截圖

6 結(jié)語

本文提出的在Web 頁面聚類中使用ALCIF 描述邏輯的方法對(duì)HTML 標(biāo)簽結(jié)構(gòu)關(guān)系進(jìn)行聯(lián)系，根據(jù)TBox 文本知識(shí)表示方法可以降低HTML 的數(shù)據(jù)維度，通過實(shí)驗(yàn)證明將描述邏輯用于Web 文檔的知識(shí)表示從而精簡(jiǎn)文檔構(gòu)造語義聯(lián)系并發(fā)現(xiàn)其中的關(guān)聯(lián)關(guān)系是合理且有效的。未來的工作是考慮將運(yùn)算規(guī)則引入到描述邏輯關(guān)系中，使得P 標(biāo)簽內(nèi)的大量文本一些復(fù)雜的邏輯能夠進(jìn)行約減，從而幫助Web 數(shù)據(jù)降低維度，節(jié)省聚類時(shí)間。