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

裴梧延，張琳

（上海海事大學信息工程學院，上?！?01306）

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

裴梧延，張琳

（上海海事大學信息工程學院，上海201306）

0　引言

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

1　基本概念

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

對于兩個實體元素A，B，用sim（A，B）表示A，B之間的概念相似度，形式上，概念相似度計算應滿足［1］：

（1）概念結點之間的相似度的值為［0，1］區間中的一個實數，即sim（A，B）∈［0，1］；

（2）如果兩個概念結點完全相似的，則其概念相似度為1，即sim（A，B）=1當且僅當A=B；

（3）如果兩個概念結點沒有任何共同特征，那么其概念相似度為0，即sim（A，B）=0；

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

定義2［3］：一個二元組（A，B）稱為一個形式概念結點，A哿G，B哿M。其中，A為形式概念（A，B）的外延，B為形式概念（A，B）的內涵。

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

2　傳統的基于概念格的概念相似度計算模型

概念結點之間的對象和屬性的相似度計算可以用距離來衡量，如果兩個概念結點之間的距離越大，則表示兩個概念結點之間的相同的對象和屬性個數就越少，即概念相似度就越?。环粗?，如果兩個概念結點之間的距離越小，則表示兩個概念結點之間的相同的對象和屬性個數就越多，即概念相似度就越大。所以兩個概念結點，（A1，B1），（A2，B2）的概念相似度計算公式［3］如下：

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

3　改進的概念格中屬性間的概念相似度計算方法

在傳統的概念相似度計算中，把每個屬性都看成同等地位，所以只計算屬性個數，但是在實際應用中，每個屬性之間還是多多少少會有一些聯系的，例如保險層次結構，如圖1所示［5］，所以本文針對屬性之間的相似度進行改進，應用到對象-屬性相似度計算中。

圖1　關于保險的屬性的層次結構

基于信息內容的概念相似度計算是根據使用概念結點之間所包含的相同的信息內容來計算其概念相似度，也就是說對兩個概念結點屬性間的語義相似度進行計算。

概念結點c屬于概念集合C，c的語義信息內容定義［5］為：

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

而針對信息內容的概念語義相似度計算是：

其中，概念結點Z是兩個屬性概念結點X和Y的最近共同祖先結點。

在層次結構中一個概念結點跟它的祖先概念結點相比較的概念相似度是高于祖先概念結點跟其子孫概念結點相比較的概念相似度。也就是說：

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

其中，Depth（m）表示的是概念結點m在概念格的層次結構中所在的層次，即深度。Depth（m）=Depth （parent（m））+1。假設根結點的深度為1，且Depth （parent（m））是m的父結點的深度。因此，在概念格中，對概念屬性之間的語義相似度計算是：

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

其中，調節因子α=0.5。

4　算法計算流程及實驗分析

假設從兩個知識庫中選擇一個領域，實驗步驟如下：

（1）對知識庫中的本體進行預處理，形成一個形式背景，包含對象集A和屬性集B。

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

（3）對形式背景下的所有屬性進行預處理，形成一個層次結構的屬性樹，再計算屬性之間的屬性相似度simAttr（X，Y）。

（4）計算兩個概念的對象相似度，計算出兩個概念具有的相同的對象個數、總對象個數、相同屬性個數、總屬性個數，若兩個概念結點沒有相同屬性，以及兩個概念的所有屬性的平均相似度。

（5）對比幾種對象-屬性相似度計算，得出結論。

實例中的“歐洲城市”形式背景來源于文獻［7］。在這個歐洲城市的形式背景中，共給出了七個著名的歐洲城市：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），它所構成的形式背景構造結果如表1所示。

表1　關于歐洲城市一個簡單的形式背景

例如：利用傳統計算方法計算

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

這是因為在實際應用過程中，（Arc）、（Bea）、（Met）、（Eur）、（Riv）、（Ski）這些屬性，不是單獨存在的，它們之間具有一定的聯系，具有一些相同的屬性因子，能夠構成一個城市背景的樹狀結構圖 （如圖2所示），所以能充分利用本文中的屬性間的計算方法。

圖2　城市屬性的樹狀結構圖

例如根據本文的屬性間的關系計算屬性Bea、Ski，我們假設屬性Bea和屬性Ski的最近共同祖先結點＜建設信息＞為＜Z＞：

計算過程中，找50個本領域專家和研究者們，分別對兩個概念相似度進行主觀判斷，并且求出其平均值，再按照傳統方法與本文方法，分別進行計算，最后發現，本文的計算方法更接近人的主觀判斷。計算結果如表2所示。

表2　計算結果比較

5　結語

在現實生活中概念是通過概念的內涵和外延之間的關系描述的，在計算概念之間的相似度是應該盡可能與人的主觀意念相接近，因此本文提出的一種關于信息內容影響和不對稱性影響的語義相似度計算為屬性相似度的計算方法，并與傳統的對象相似度計算相結合，得出新的概念對象-屬性相似度計算方法，在一定程度上提高了在概念格中概念結點相似度計算的準確率。

［1］張忠平，田淑霞，劉洪強.一種綜合的本體相似度計算方法［J］.計算機科學，2008

［2］李沖，曹吉鳴，馬騰.基于形式概念分析的項目成員綜合相似度計算［J］.同濟大學學報，2014

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

［4］張素蘭.加權概念格理論與應用［M］.北京：科學出版社，2013

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

［6］張小紅.基于概念格理論的語義相似度模型研究及驗證［J］.鄭州大學學報，2011

［7］姚佳岷，楊思春.改進的本體概念相似度計算模型［J］.計算機應用，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-），女，吉林延吉人，碩士研究生，研究方向為計算機系統應用、本體與知識工程

2015-04-20

2015-05-14

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

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

張琳（1973-），女，河南信陽人，博士，副教授，研究方向為港航信息化技術、智能信息處理、信息檢索、本體與知識工程等

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.