基于屬性相似度在概念格的概念相似度計(jì)算方法

裴梧延，張琳

（上海海事大學(xué)信息工程學(xué)院，上海　201306）

基于屬性相似度在概念格的概念相似度計(jì)算方法

裴梧延，張琳

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

本體（Ontology）這一概念最初起源于哲學(xué)領(lǐng)域。本體作為知識組織的重要手段具有聲明、函數(shù)、概念、屬性、公理、實(shí)例等6個(gè)要素。領(lǐng)域本體和形式化概念分析都是對概念的屬性、對象類型、關(guān)系上進(jìn)行總結(jié)分析的。形式化概念分析又稱為概念格，是由德國的Wille教授提出的，概念格的每一個(gè)概念結(jié)點(diǎn)都是一個(gè)形式化概念，由內(nèi)涵（屬性集）和外延（擁有該屬性集的對象集）兩部分組成。概念格實(shí)際上是說明內(nèi)涵（屬性）與外延（對象）之間的關(guān)系，是概念內(nèi)涵和外延的統(tǒng)一，其相應(yīng)的Hasse圖實(shí)現(xiàn)了對形式概念的可視化，反映了一種概念層次結(jié)構(gòu)。這種通過形式概念分析的概念語義相似度是知識背景下，在對象和屬性之間尋找相似性特征，目前已經(jīng)被廣泛地應(yīng)用在文獻(xiàn)檢索（信息檢索）、數(shù)字圖書館、數(shù)據(jù)挖掘、軟件工程、知識發(fā)現(xiàn)等一些領(lǐng)域。

1　基本概念

概念的相似度說明的是兩個(gè)概念具有的相同屬性的程度，如果兩個(gè)實(shí)體概念所擁有的相同屬性越多，則說明它們的概念相似度越高，同樣對于兩個(gè)概念的某一個(gè)特定的屬性，其擁有越多的相同屬性值，這兩個(gè)屬性就越相似，其概念相似度也就越高。

對于兩個(gè)實(shí)體元素A，B，用sim（A，B）表示A，B之間的概念相似度，形式上，概念相似度計(jì)算應(yīng)滿足［1］：

（1）概念結(jié)點(diǎn)之間的相似度的值為［0，1］區(qū)間中的一個(gè)實(shí)數(shù)，即sim（A，B）∈［0，1］；

（2）如果兩個(gè)概念結(jié)點(diǎn)完全相似的，則其概念相似度為1，即sim（A，B）=1當(dāng)且僅當(dāng)A=B；

（3）如果兩個(gè)概念結(jié)點(diǎn)沒有任何共同特征，那么其概念相似度為0，即sim（A，B）=0；

定義1［2］：在形式概念分析中，一個(gè)形式背景定義為三元組K=｛G，M，I｝，其中G是對象集，M是屬性集，I是二元關(guān)系，｛g，m｝∈I或gIm表示對象g具有屬性m。

定義2［3］：一個(gè)二元組（A，B）稱為一個(gè)形式概念結(jié)點(diǎn)，A哿G，B哿M。其中，A為形式概念（A，B）的外延，B為形式概念（A，B）的內(nèi)涵。

定義3［4］：設(shè)形式背景為K=｛G，M，I｝，假設(shè)，（A1，B1），（A2，B2）∈L（K），如果A1哿A2或者B2哿B1，記為（A1，B1）≤（A2，B2），意思是 （A1，B1）是（A2，B2）的子概念。顯然L（K）關(guān)于“≤”構(gòu)成一個(gè)格，是由形式背景K中的所有概念及概念之間的偏序關(guān)系構(gòu)成了一個(gè)完備格，稱為概念格。

2　傳統(tǒng)的基于概念格的概念相似度計(jì)算模型

概念結(jié)點(diǎn)之間的對象和屬性的相似度計(jì)算可以用距離來衡量，如果兩個(gè)概念結(jié)點(diǎn)之間的距離越大，則表示兩個(gè)概念結(jié)點(diǎn)之間的相同的對象和屬性個(gè)數(shù)就越少，即概念相似度就越小；反之，如果兩個(gè)概念結(jié)點(diǎn)之間的距離越小，則表示兩個(gè)概念結(jié)點(diǎn)之間的相同的對象和屬性個(gè)數(shù)就越多，即概念相似度就越大。所以兩個(gè)概念結(jié)點(diǎn)，（A1，B1），（A2，B2）的概念相似度計(jì)算公式［3］如下：

其中，m=max（|A1|，|A2|），n=max（|B1|，|B2|），α+β= 1，根據(jù)概念格的對偶原理，概念結(jié)點(diǎn)的對象和屬性具有相同的地位，所以α=β=0.5。

3　改進(jìn)的概念格中屬性間的概念相似度計(jì)算方法

在傳統(tǒng)的概念相似度計(jì)算中，把每個(gè)屬性都看成同等地位，所以只計(jì)算屬性個(gè)數(shù)，但是在實(shí)際應(yīng)用中，每個(gè)屬性之間還是多多少少會(huì)有一些聯(lián)系的，例如保險(xiǎn)層次結(jié)構(gòu)，如圖1所示［5］，所以本文針對屬性之間的相似度進(jìn)行改進(jìn)，應(yīng)用到對象-屬性相似度計(jì)算中。

圖1　關(guān)于保險(xiǎn)的屬性的層次結(jié)構(gòu)

基于信息內(nèi)容的概念相似度計(jì)算是根據(jù)使用概念結(jié)點(diǎn)之間所包含的相同的信息內(nèi)容來計(jì)算其概念相似度，也就是說對兩個(gè)概念結(jié)點(diǎn)屬性間的語義相似度進(jìn)行計(jì)算。

概念結(jié)點(diǎn)c屬于概念集合C，c的語義信息內(nèi)容定義［5］為：

其中，L（c）和S（c）分別表示屬性概念層次結(jié)構(gòu)中概念結(jié)點(diǎn)c以下的概念結(jié)點(diǎn)集合和概念結(jié)點(diǎn)c以上概念結(jié)點(diǎn)集合。信息內(nèi)容值是隨著概念結(jié)點(diǎn)在層次結(jié)構(gòu)中具體細(xì)化程度的增加而遞增的。概念結(jié)點(diǎn)的語義信息內(nèi)容是和它在層次結(jié)構(gòu)中包含的祖先概念結(jié)點(diǎn)個(gè)數(shù)成正比的，也就是說從概念結(jié)點(diǎn)c到根結(jié)點(diǎn)的路程中所包含的所有概念結(jié)點(diǎn)數(shù)量越多，它的信息含量就越大；與此概念結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹上的葉子結(jié)點(diǎn)成反比的，也就是說子樹上葉子結(jié)點(diǎn)越多，概念結(jié)點(diǎn)所具有的信息內(nèi)容是這些葉子結(jié)點(diǎn)的共有信息，所以所含信息量就越少。Max_L則表示層次結(jié)構(gòu)中根節(jié)點(diǎn)下的所有葉子結(jié)點(diǎn)個(gè)數(shù)，信息內(nèi)容值是隨著概念在層次結(jié)構(gòu)中信息具體細(xì)化的程度增加而遞增。

而針對信息內(nèi)容的概念語義相似度計(jì)算是：

其中，概念結(jié)點(diǎn)Z是兩個(gè)屬性概念結(jié)點(diǎn)X和Y的最近共同祖先結(jié)點(diǎn)。

在層次結(jié)構(gòu)中一個(gè)概念結(jié)點(diǎn)跟它的祖先概念結(jié)點(diǎn)相比較的概念相似度是高于祖先概念結(jié)點(diǎn)跟其子孫概念結(jié)點(diǎn)相比較的概念相似度。也就是說：

所以針對屬性概念結(jié)點(diǎn)之間語義相似度不對稱性，本文要加入不對稱因子：

其中，Depth（m）表示的是概念結(jié)點(diǎn)m在概念格的層次結(jié)構(gòu)中所在的層次，即深度。Depth（m）=Depth （parent（m））+1。假設(shè)根結(jié)點(diǎn)的深度為1，且Depth （parent（m））是m的父結(jié)點(diǎn)的深度。因此，在概念格中，對概念屬性之間的語義相似度計(jì)算是：

因此，概念格中的概念的對象-屬性相似度計(jì)算方法為：

其中，調(diào)節(jié)因子α=0.5。

4　算法計(jì)算流程及實(shí)驗(yàn)分析

假設(shè)從兩個(gè)知識庫中選擇一個(gè)領(lǐng)域，實(shí)驗(yàn)步驟如下：

（1）對知識庫中的本體進(jìn)行預(yù)處理，形成一個(gè)形式背景，包含對象集A和屬性集B。

（2）針對形式背景，使用概念格的構(gòu)造軟件Con-Exp構(gòu)造概念格。

（3）對形式背景下的所有屬性進(jìn)行預(yù)處理，形成一個(gè)層次結(jié)構(gòu)的屬性樹，再計(jì)算屬性之間的屬性相似度simAttr（X，Y）。

（4）計(jì)算兩個(gè)概念的對象相似度，計(jì)算出兩個(gè)概念具有的相同的對象個(gè)數(shù)、總對象個(gè)數(shù)、相同屬性個(gè)數(shù)、總屬性個(gè)數(shù)，若兩個(gè)概念結(jié)點(diǎn)沒有相同屬性，以及兩個(gè)概念的所有屬性的平均相似度。

（5）對比幾種對象-屬性相似度計(jì)算，得出結(jié)論。

實(shí)例中的“歐洲城市”形式背景來源于文獻(xiàn)［7］。在這個(gè)歐洲城市的形式背景中，共給出了七個(gè)著名的歐洲城市：Athens（A）、Courmayeur（C）、Innsbruck（I）、London（L）、Paris（P）、Reykjavik（Re）、Rome（Ro）。以及這些城市所具有屬性Archeological-site（Arc）、Beach（Bea）、Metropolis（Met）、Euro（Eur）、River（Riv）、Skiing-area （Ski），它所構(gòu)成的形式背景構(gòu)造結(jié)果如表1所示。

表1　關(guān)于歐洲城市一個(gè)簡單的形式背景

例如：利用傳統(tǒng)計(jì)算方法計(jì)算

它的意思是一個(gè)人可能之前去過（L，P，Ro）兩個(gè)城市，所以此游客可能對（Met，Riv）旅游信息感興趣，另一個(gè)游客可能去過（C，I，Re）三個(gè)城市，所以此游客可能對（Ski）感興趣，那么按照公式得出，這兩個(gè)游客之間是沒有任何相似性的，可是這種說法是不對的，根據(jù)形式背景，這兩個(gè)游客去過的地方都會(huì)有（Eur），所以他們之間還是有一定的相似性的。

這是因?yàn)樵趯?shí)際應(yīng)用過程中，（Arc）、（Bea）、（Met）、（Eur）、（Riv）、（Ski）這些屬性，不是單獨(dú)存在的，它們之間具有一定的聯(lián)系，具有一些相同的屬性因子，能夠構(gòu)成一個(gè)城市背景的樹狀結(jié)構(gòu)圖 （如圖2所示），所以能充分利用本文中的屬性間的計(jì)算方法。

圖2　城市屬性的樹狀結(jié)構(gòu)圖

例如根據(jù)本文的屬性間的關(guān)系計(jì)算屬性Bea、Ski，我們假設(shè)屬性Bea和屬性Ski的最近共同祖先結(jié)點(diǎn)＜建設(shè)信息＞為＜Z＞：

計(jì)算過程中，找50個(gè)本領(lǐng)域?qū)＜液脱芯空邆儯謩e對兩個(gè)概念相似度進(jìn)行主觀判斷，并且求出其平均值，再按照傳統(tǒng)方法與本文方法，分別進(jìn)行計(jì)算，最后發(fā)現(xiàn)，本文的計(jì)算方法更接近人的主觀判斷。計(jì)算結(jié)果如表2所示。

表2　計(jì)算結(jié)果比較

5　結(jié)語

在現(xiàn)實(shí)生活中概念是通過概念的內(nèi)涵和外延之間的關(guān)系描述的，在計(jì)算概念之間的相似度是應(yīng)該盡可能與人的主觀意念相接近，因此本文提出的一種關(guān)于信息內(nèi)容影響和不對稱性影響的語義相似度計(jì)算為屬性相似度的計(jì)算方法，并與傳統(tǒng)的對象相似度計(jì)算相結(jié)合，得出新的概念對象-屬性相似度計(jì)算方法，在一定程度上提高了在概念格中概念結(jié)點(diǎn)相似度計(jì)算的準(zhǔn)確率。

［1］張忠平，田淑霞，劉洪強(qiáng).一種綜合的本體相似度計(jì)算方法［J］.計(jì)算機(jī)科學(xué)，2008

［2］李沖，曹吉鳴，馬騰.基于形式概念分析的項(xiàng)目成員綜合相似度計(jì)算［J］.同濟(jì)大學(xué)學(xué)報(bào)，2014

［3］智慧來，智東杰，劉宗田.基于概念格的概念相似度計(jì)算［J］.計(jì)算機(jī)科學(xué)，2008

［4］張素蘭.加權(quán)概念格理論與應(yīng)用［M］.北京：科學(xué)出版社，2013

［5］黃宏濤，程清杰，萬慶生，黃少濱.基于語義信息內(nèi)容的FCA概念相似度計(jì)算方法［J］.計(jì)算機(jī)應(yīng)用研究，2014

［6］張小紅.基于概念格理論的語義相似度模型研究及驗(yàn)證［J］.鄭州大學(xué)學(xué)報(bào)，2011

［7］姚佳岷，楊思春.改進(jìn)的本體概念相似度計(jì)算模型［J］.計(jì)算機(jī)應(yīng)用，2013

Formal Concept Analysis of Concept；Similarity Calculation；Object-Attribute Similarity Calculation

Concept Similarity Calculation Method of Concept Lattice Based on Attribute Similarity

PEI Wu-yan，ZHANG Lin
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）17-0010-04

10.3969/j.issn.1007-1423.2015.17.002

裴梧延（1990-），女，吉林延吉人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)系統(tǒng)應(yīng)用、本體與知識工程

2015-04-20

2015-05-14

針對概念形式分析的概念相似度計(jì)算過程中，在傳統(tǒng)的計(jì)算方法上，針對屬性相似度計(jì)算中增加信息內(nèi)容影響和不對稱因子的影響，得到改進(jìn)的屬性相似度計(jì)算方法，并通過實(shí)驗(yàn)證明，在形式背景中的對象-屬性相似度計(jì)算結(jié)果更為接近人的主觀判斷，說明該方法確實(shí)有效。

概念形式化分析；概念相似度計(jì)算；對象-屬性相似度計(jì)算

張琳（1973-），女，河南信陽人，博士，副教授，研究方向?yàn)楦酆叫畔⒒夹g(shù)、智能信息處理、信息檢索、本體與知識工程等

According to the formal concept of analysis of the concept similarity calculation process，based on the traditional calculation method，increases the influence of the information content and asymmetry factor to the attribute similarity calculation，the improved calculation method gets attribute similarity，and the experimental results prove that the similarity of object-attribute calculation in the form of the background of the formal concept analysis of concept calculating result is more closer to the subjective judgment people，shows that the method is effective.