張 蘊,葉玉琪,許高建*

(1.安徽農(nóng)業(yè)大學(xué) 信息與計算機學(xué)院,安徽 合肥 230036;2.中國科技大學(xué) 研究生院 科學(xué)島分院,安徽 合肥 230036)

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展和普及,網(wǎng)絡(luò)資源不斷增加,面對海量數(shù)據(jù),如何進行組織管理和維護已經(jīng)成為科研領(lǐng)域廣泛關(guān)注的問題,于是本體的概念被提了出來。它作為一種能在語義和知識層次上表示信息系統(tǒng)的概念模型,在很多方面已經(jīng)得到普遍的應(yīng)用,如知識工程、自然語言處理、智能信息集成、Internet智能信息獲取以及知識管理等[1]。對于眾多的領(lǐng)域知識來說,獲取本體結(jié)構(gòu)中的重要概念都有著重要的意義。

目前,對于復(fù)雜網(wǎng)絡(luò)節(jié)點重要性的研究,國內(nèi)外研究人員都采取了不同的方法,分別提出了節(jié)點重要度的不同度量指標,這些方法與指標本質(zhì)上都是以圖論為基礎(chǔ),主要可以分為以下兩大類:(1)從節(jié)點的顯著性衡量節(jié)點的重要性,主要的衡量參數(shù)有度、介數(shù)、接近度以及特征向量指標等;(2)通過網(wǎng)絡(luò)的連通度來判斷節(jié)點的重要程度,即通過刪除或者收縮某一節(jié)點對整個網(wǎng)絡(luò)造成的影響程度來度量節(jié)點的重要性，對網(wǎng)絡(luò)造成的影響程度也可以用一些網(wǎng)絡(luò)特有的指標來表示,比如連通度、聚集度等[3]。其中比較典型的有:文獻[5]提出的介數(shù)指標,能很好地反映一個節(jié)點在整個網(wǎng)絡(luò)中的影響力;陳靜等提出了基于節(jié)點接近度與節(jié)點領(lǐng)域關(guān)鍵度的評價方法[6];任卓明等提出了基于度與集聚系數(shù)的節(jié)點重要性評估方法,該方法只能度量局部網(wǎng)絡(luò)的節(jié)點重要性。

本文首先在概述復(fù)雜網(wǎng)絡(luò)相關(guān)理論的基礎(chǔ)之上,提出了基于度、集聚系數(shù)以及接近度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性評價方法；然后基于復(fù)雜網(wǎng)絡(luò)與本體結(jié)構(gòu)的相似性理論[8],以茶樹蟲害本體為例,應(yīng)用該評價方法提取本體中的重要概念,這一提取結(jié)果對茶樹蟲害本體中的害蟲防治以及茶樹生態(tài)環(huán)境保護有著重大意義。

1 重要概念的概述

1.1 本體的定義

本體的定義來源自哲學(xué)領(lǐng)域,簡單來說,本體就是在某一知識領(lǐng)域內(nèi)的一套概念以及概念之間關(guān)系的集合。它的組成有:類、個體、屬性以及關(guān)系。其中類表示的是具有相同特征的個體的集合,對應(yīng)在本體的拓撲結(jié)構(gòu)中就是各個分層結(jié)構(gòu)的樹的根。而個體就是某一個類的成員。本體結(jié)構(gòu)中的屬性可以分為兩種：對象屬性和數(shù)據(jù)屬性。對象屬性連接的是兩個個體,而數(shù)據(jù)屬性是一個個體獨有的屬性。本體中的關(guān)系包括類與類的關(guān)系、類與個體的關(guān)系以及個體與個體的關(guān)系。關(guān)系可以用一個“主謂賓”的三元組來表示，比如:“羊吃草”表示的是一個關(guān)系,其中“吃”是數(shù)據(jù)屬性,它連接“羊”和“草”這兩個個體；而在關(guān)系“草是綠色的”中,“綠色的”就是數(shù)據(jù)屬性,它是“草”這個個體獨有的屬性。

1.2 本體結(jié)構(gòu)中重要概念的定義

由本體定義可知,本體結(jié)構(gòu)由類、個體、屬性以及關(guān)系組成。本體中的概念是指個體以及它所包含的所有屬性和關(guān)系的集合。這與復(fù)雜網(wǎng)絡(luò)中的概念定義是相符的。與復(fù)雜網(wǎng)絡(luò)類似,本體中的個體也有不同重要度之分,重要個體就是在本體中與其他個體聯(lián)系最多的個體,處于本體結(jié)構(gòu)的要害位置。本體中的重要概念就是指該本體知識領(lǐng)域內(nèi)的重要個體以及它所包含的所有屬性和關(guān)系的集合。找到并提取本體結(jié)構(gòu)中的重要概念在現(xiàn)實世界中有著重大意義。

2 基于度、集聚系數(shù)以及接近度的重要概念

基于以上理論基礎(chǔ),本文提出了一種新的節(jié)點重要性評價方法,該方法基于度、集聚系數(shù)以及接近度這3個衡量參數(shù),下面詳細介紹它的實現(xiàn)過程。

2.1 符號與定義

該方法針對的是無向無權(quán)的復(fù)雜網(wǎng)絡(luò),這與本體也是相吻合的。復(fù)雜網(wǎng)絡(luò)可以用G=表示,假設(shè)G有n個節(jié)點和m條邊,則用V=(v1,v2,...,vi,...,vn)表示G的節(jié)點集,用E=(e1,e2,...,ej,...,em)表示邊的集合;A=[aij]有n行n列,表示G的鄰接矩陣,aij=1表示節(jié)點vi與節(jié)點vj直接相連,否則aij=0。

定義1:節(jié)點度表示的是與該節(jié)點直接相連的邊的數(shù)量。節(jié)點vi的度表示為:

則節(jié)點度與鄰居度之和可以表示為:

上式中Ti表示節(jié)點vi的鄰居節(jié)點的集合。

定義2：集聚系數(shù)描述的是節(jié)點的鄰居節(jié)點之間互為鄰居的比例[10]。集聚系數(shù)針對的是節(jié)點度大于2的節(jié)點。節(jié)點vi的集聚系數(shù)表示為：

上式中ri表示在節(jié)點vi的相鄰節(jié)點之間互為鄰居的個數(shù)。

定義3：鄰居聯(lián)系度gi反映節(jié)點鄰居之間的聯(lián)系，用下式計算：

上式中：Ai代表節(jié)點vi的集聚系數(shù);si為節(jié)點度與鄰居度之和。

定義4：節(jié)點局部重度pi反映兩個變量綜合的結(jié)果,也就是反映節(jié)點vi在局部范圍內(nèi)的重要性，用下式計算：

定義5:節(jié)點接近度Ci通過下式[3]計算：

上式中dij表示節(jié)點vi與節(jié)點vj之間最短路徑的長度。

定義6:節(jié)點重要度qi反映節(jié)點vi在復(fù)雜網(wǎng)絡(luò)中的重要程度，用下式[11]計算：

qi=piCi

2.2 實例分析

對圖1所示的網(wǎng)絡(luò)拓撲圖采用不同的方法分別計算各節(jié)點的重要度,結(jié)果見表1。

圖1 某網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖

節(jié)點編號不同方法計算的節(jié)點重要度度接近度節(jié)點收縮法度與集聚系數(shù)法本文的方法120.04550.29670.32230.0258220.04550.29670.32230.0258340.06250.64840.84410.0565410.04350.14600.65760.0130520.06670.45790.81880.0569630.06250.52530.73740.0518720.04760.34070.32230.0270830.05000.52530.68360.0390910.03700.19620.61740.0060

對表1中的結(jié)果進行分析，由表2可知,不同方法的評價結(jié)果顯然有很大差別。

度:存在很多度值相同的節(jié)點,無法細分它們的重要性,且無法正確評價橋節(jié)點(節(jié)點5)的重要性。

接近度:排序結(jié)果基本正確,但是對于節(jié)點3和節(jié)點6的判斷有點不足,從網(wǎng)絡(luò)拓撲結(jié)構(gòu)來看,節(jié)點3和節(jié)點6的重要性不是完全一樣的。

節(jié)點收縮法:對節(jié)點5的判斷不夠準確。

度與集聚系數(shù)法:最大的缺點就是對末梢節(jié)點的判斷不準確,比如節(jié)點4和節(jié)點9,它們的重要性應(yīng)該是最低的,可是該方法的結(jié)果顯示重要性最低的節(jié)點是節(jié)點1和節(jié)點2,這顯然不夠準確;此外，該方法對節(jié)點3和節(jié)點5的判斷也存在一些不足。

本文的方法:評價結(jié)果是與實際情況相符的。對于圖1的網(wǎng)絡(luò)拓撲結(jié)構(gòu)來說,節(jié)點5是一個橋節(jié)點,應(yīng)該是最重要的；節(jié)點3和節(jié)點6的重要性次之，因為節(jié)點3是在左邊的局部范圍內(nèi)的核心節(jié)點,節(jié)點6是在右邊的局部范圍內(nèi)的重要節(jié)點,不過這兩個節(jié)點的重要性存在細微差別；節(jié)點8和節(jié)點7的重要性更次一些；而對于節(jié)點1和節(jié)點2,它們的重要度應(yīng)該是一致的,比末梢節(jié)點4和9的略高；雖然節(jié)點4、9同為末梢節(jié)點,但顯然它們的重要性并不相同,因為它們的鄰居節(jié)點的重要性是不一樣的,這與前文所說的特征向量的思想是一致的。

表2 不同方法的評價結(jié)果分析

在以上采用的5種方法中,本文提出的基于度、集聚系數(shù)以及接近度的方法得出的節(jié)點重要性排序與實際情況是相符的,很好地證實了該方法的有效性。該模型的時間復(fù)雜度主要取決于接近度Ci的計算,接近度Ci只需計算出各節(jié)點對之間最短路徑的長度即可,不用記錄每條最短路徑經(jīng)過的節(jié)點,所以該方法的復(fù)雜度明顯比介數(shù)等方法的復(fù)雜度低,適用于大的復(fù)雜網(wǎng)絡(luò)的計算。

3 本體結(jié)構(gòu)中重要概念的提取

本文以茶樹蟲害本體為研究對象,應(yīng)用基于度、集聚系數(shù)以及接近度的節(jié)點評估方法對本體中的個體重要性進行評價,分析評價結(jié)果,提取合理的重要概念。

3.1 對茶樹蟲害本體的預(yù)處理

由茶樹蟲害本體的網(wǎng)絡(luò)拓撲圖(圖2)可知,該本體結(jié)構(gòu)大致可以劃分為茶樹部位、茶區(qū)以及茶樹害蟲這3個社團。

對茶樹蟲害本體的預(yù)處理在eclipse中進行，通過Jena API讀取本體里的類和個體以及屬性、關(guān)系,最終得到茶樹蟲害本體一共有565個類、793個個體、3651個關(guān)系、33個對象屬性以及22個數(shù)據(jù)屬性(圖3)。

根據(jù)該本體的預(yù)處理結(jié)果建立與之對應(yīng)的鄰接矩陣。本體中的類和個體相當于復(fù)雜網(wǎng)絡(luò)里面的節(jié)點,關(guān)系則相當于邊。鄰接矩陣中的1表示其行列坐標對應(yīng)的兩個節(jié)點之間存在關(guān)系,0則表示沒有關(guān)系。這樣就能得到茶樹蟲害本體結(jié)構(gòu)對應(yīng)的鄰接矩陣(圖4)。

圖2 茶樹蟲害本體的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

圖3 茶樹蟲害本體的預(yù)處理結(jié)果

3.2 獲取本體中的重要概念

將本體網(wǎng)絡(luò)的鄰接矩陣導(dǎo)入節(jié)點重要性評估模型,得出本體中各節(jié)點的重要度評價指標q[12]。由于本體中的重要概念指的是重要個體以及它所包含的所有屬性和關(guān)系,所以在進行重要度評估時,本文只對個體評價其重要性,最終的結(jié)果如圖5所示。

從圖5中可以看出,q值排在前14的個體都是茶區(qū),q值緊接其后的都是茶樹害蟲。該結(jié)果表明,將所有個體的重要性放在一起進行評估是不合理的,因為根據(jù)本體的拓撲結(jié)構(gòu)很容易得出茶樹害蟲與茶區(qū)屬于兩個社團,不能進行重要性的比較。簡言之:不能片面地認為“江蘇”的重要性比“大蓑蛾”高,雖然從圖5中來看“江蘇”的q值比“大蓑蛾”高。綜上所述,該結(jié)果對評價個體的重要性不具備太大的現(xiàn)實意義,所以本文將對茶樹蟲害本體中的茶樹部位、茶區(qū)以及茶樹害蟲這3個社團內(nèi)的個體分別進行重要性評價。值得注意的是,茶樹蟲害本體中的個體并不是全部在這3個社團內(nèi)的,但是從拓撲結(jié)構(gòu)可以明顯看出,茶樹部位、茶區(qū)以及茶樹害蟲可以看成3個不同的社團,而這3個社團的個體重要性評估對茶樹蟲害本體有著很大的現(xiàn)實意義,所以本文只針對這3個社團內(nèi)的個體進行分析。

圖4 茶樹蟲害本體結(jié)構(gòu)的鄰接矩陣

由圖6～圖8可以得出如下結(jié)論:在茶樹部位社團內(nèi),最重要的個體是“葉”;在茶區(qū)社團內(nèi),最重要的個體是“湖南”;在茶樹害蟲社團內(nèi),最重要的個體是“大蓑蛾”。

圖5 本體中個體的q值按降序排序

圖6 茶樹部位社團

獲取上述3個最重要個體對應(yīng)的概念,即本體中的重要概念,結(jié)果如圖9～圖11所示。

3.3 結(jié)果與分析

根據(jù)以上重要性評價以及重要概念提取的結(jié)果,我們可以清楚看到,“湖南”茶區(qū)的茶樹害蟲最多,“葉”是最易受茶樹害蟲傷害的部位,而在所有茶樹害蟲里面,“大蓑蛾”的分布最廣。在了解這些信息之后,我們就能夠有針對性地采取相關(guān)措施。比如,對湖南的茶區(qū),應(yīng)該對其進行大力度的茶樹害蟲防治工作;對茶樹的葉片,要采取特殊的保護預(yù)防措施,防止其被害蟲傷害;而對于大蓑蛾,要首先對其進行有效防治,因為在所有害蟲里面,它的重要性指標表現(xiàn)最高。

圖7 茶區(qū)社團

圖8 茶樹害蟲社團

圖9 “湖南”對應(yīng)的概念

圖10 “葉”對應(yīng)的概念

圖11 “大蓑蛾”對應(yīng)的概念

4 結(jié)束語

從本體結(jié)構(gòu)中獲取到的重要概念對該領(lǐng)域采取相應(yīng)舉措起著指導(dǎo)性的作用,所以本研究對任一本體知識領(lǐng)域都有著重要的現(xiàn)實意義,且對本體知識領(lǐng)域的管理與操作有很大的幫助。本文的局限性在于研究的茶樹蟲害本體是手動構(gòu)建的,關(guān)系不夠健全,所以可能會導(dǎo)致結(jié)果有細微的誤差。今后將在關(guān)系健全、結(jié)構(gòu)龐大的本體上進行進一步的探索與研究。