基于主成分分析和K-Modes蟻群聚類的本體映射方法

葉 霞 許飛翔 曹軍博 王 馨

1(火箭軍工程大學作戰保障學院 陜西 西安 710025)2(馬里蘭大學巴爾的摩校區信息系統學院 馬里蘭州 巴爾的摩 21250)

0 引 言

指揮信息系統在作戰部隊中的廣泛運用，產生了大量的測試與評估數據，由于不同單位建立的指標體系存在差異，相同的概念經常被使用不同的指標進行描述，導致測試與評估數據在共享和集成上存在較大困難。隨著語義網絡和本體技術的不斷發展，本體集成可以有效解決此問題，將格式異構的測試數據轉換為局部本體，建立統一的全局指標本體樹[1]，從而實現指揮信息系統測試評估數據的有效集成。在本體之間架起語義映射的橋梁，完成由局部本體到全局本體的映射技術已經成為當前研究的熱點和難點問題。

1 相關研究

目前的本體映射[2]方法主要有基于規則的本體映射方法、基于語義網的本體映射方法和基于機器學習的本體映射方法。基于規則的本體映射主要是通過人為定義規則發現本體概念之間的映射關系，比如“如果兩個概念的屬性全部一致，那么可以在兩個概念之間建立映射關系”等規則。Kedzia等[3]提出了基于規則的方法將plWordNet映射到SUMO本體上，使用專家定義的規則識別可能的映射關系，然后語言專家進行手動檢查。姚香菊等[4]提出了由專家建立的規則學習庫的映射系統，實現批量本體概念映射關系的發現。

基于語義網的本體映射主要有基于Hownet、WordNet,以及中文概念辭書CCD等現有的語義網絡進行相應節點的映射，潘有能等[5]以WordNet為基礎，從語義網絡中獲取概念的語義和結構關系，完成概念的映射。Schadd等[6]提出將本體概念與其對應的WordNet條目進行耦合的改進方法，通過創建表示不同本體概念和WordNet條目的獨立虛擬文檔，并根據它們的文檔相似性對它們進行耦合，實現本體概念的映射。Elhadad等[7]提出一種基于WordNet的本體論方法，使用向量空間模型表示文本，通過WordNet計算元素級本體概念之間的語義相似性，完成本體映射的關鍵性工作，提高本體映射準確率。

基于機器學習的本體映射方法主要是將本體映射問題轉化為聚類、分類或者最優化問題，采用機器學習中監督學習、半監督學習或無監督學習的算法實現映射。Shao等[8]提出的RiMOM方法將映射發現問題轉化為風險最小化問題，利用貝葉斯決策理論去發現映射關系，有效地提高了本體映射結果的精度。Cheng等[9]提出基于最小生成樹聚類算法的本體映射策略，對參與映射概念的候選對象進行篩選，使用系統信息熵來監督聚類，取得較好映射效果。Yin等[10]提出了一種基于詞與上下文相似性分類的方法，將本體樹的節點分為分類節點和概念節點，依賴于本體的樹結構，完成本體概念之間的映射。

總體而言，單純依靠規則和語義網絡進行本體概念映射關系的發現逐漸暴露出費時費力、準確率不高的缺陷，基于機器學習的方法逐漸成為提高本體映射效率和質量的有效途徑。因此，本文提出基于PCA和KMACC的本體映射模型，采用基于主成分分析法的相似度綜合計算模型計算本體概念相似度，提高本體概念相似度計算的精度，運用改進的K-Modes蟻群聚類算法進行映射的發現，有效地提升本體映射的準確率和效率。

2 方法設計

2.1 基于PCA的本體概念相似度綜合計算模型

2.1.1基于信息內容的相似度計算

基于本體概念信息內容的相似度計算需要考慮到概念對最近公共父節點的信息量，孫麗莉等[11]提出還需考慮到概念對本身的信息量，他們所提出的計算式為：

(1)

式中：M(C1,C2)表示概念對C1和C2在本體樹中的最近鄰公共父節點；I(C1)和I(C2)分別表示概念C1和C2包含的信息量。信息量的計算式為：

(2)

式中：N(C)為概念C在訓練樣本中出現的次數；N為訓練樣本的總數。

2.1.2基于語義距離的相似度計算

基于本體概念語義距離相似度計算的經典方法是通過計算兩個概念之間的幾何距離來計算語義距離。這里的幾何距離是取概念對到最近公共父節點的路徑和來計算的，計算式為：

(3)

式中：Dis(C1,C2)=L(C1,M(C1,C2)+L(C2,M(C1,C2))，L(C1,M(C1,C2))表示概念C1到C1與C2的最近公共父節點的最短路徑，L(C2,M(C1,C2))表示概念C2到C1與C2的最近公共父節點的最短路徑。

影響概念語義距離的因素還有很多，Leacock等[12]提出的改進方法主要思想是除了考慮概念對之間的最短路徑外，還考慮了其所處本體樹的最大深度，同時考慮到兩個概念最近公共父節點在本體樹中的深度。綜合以上研究，給出基于本體概念語義距離的相似度計算式為：

(4)

式中：P(M(C1,C2),C1)表示概念對C1和C2最近公共父節點在概念C1所在本體樹中的深度；max(P(C1))表示概念C1所處本體樹的最大深度。

2.1.3基于概念屬性的相似度計算

基于本體概念屬性的相似度計算主要考慮能夠表明概念特征的屬性共有程度，早期的研究主要依據計算概念對所共有的屬性個數來計算屬性相似度，公共屬性個數越多，則相似度越大。張賢坤等[13]提出屬性信息包含屬性名稱、屬性數據類型和屬性值三個要素，需要綜合計算屬性相似度，算法更為科學，因此直接引用此計算模型進行概念屬性的相似度計算。其中屬性名稱和數據類型都是字符串形式，以字符串相似度計算方法計算，本文使用余弦距離計算法。模型中設概念C1和C2的屬性分別為p和q，則屬性p和q的相似度計算式為：

Simpq(p,q)=ω1×sim(pname,qname)+

ω2×sim(pdatatype,qdatatype)+ω3×sim(pvalue,qvalue)

(5)

式中：ω1、ω2和ω3為權重參數且ω1+ω2+ω3=1；sim(pname,qname)表示屬性名稱相似度值；sim(pdatatype,qdatatype)表示屬性數據類型相似度值；sim(pvalue,qvalue)表示屬性值相似度值。當概念C1和C2共計算出m個Simpq(C1,C2)時，設每個屬性對的權重為ωk，則C1和C2基于本體概念屬性的相似度計算式為：

(6)

2.1.4相似度矩陣構建

Y=(yi1,yi2,…,yi3)Ti=1,2,…,n

(7)

2.1.5基于PCA的相似度綜合計算模型

PCA[14]是一種多元統計方法，相比于傳統人為確定權重的方式，PCA可以較為準確地計算出各因素對綜合計算值的貢獻程度。在本文的模型中，只有基于信息內容、語義距離、概念屬性這三個子因素，因此都確定為主成分，根據專家評價結果對相似度矩陣Y進行主成分分析，計算出各主成分的貢獻率為γ1、γ2、γ3，確定權值便可得概念對C1和C2的綜合相似度計算式為：

Sim(C1,C2)=γ1Sim1(C1,C2)+γ2Sim2(C1,C2)+

γ3Sim3(C1,C2)

(8)

基于PCA的本體概念相似度綜合計算模型框圖如圖1所示。

圖1 基于PCA的本體概念相似度綜合計算模型

2.2 改進的K-Modes蟻群聚類算法

2.2.1K-Modes聚類算法

聚類分析[15]是指將實體對象或者抽象對象的集合分組為由相似對象組成的多個類的分析過程，傳統的聚類分析采用歐氏距離或者編輯距離來判斷兩個對象的相異性，實現對數值型和文本型數據的聚類，采用的距離計算方法不同對聚類的效果有很大的影響，直接影響本體映射的效果。本文定義本體概念相似度Sim(C1,C2)的倒數為兩個本體概念的距離，實現本體概念的聚類，以提高本體概念聚類的精度。本體映射中多個本體的概念存在差異時，樣本集合中概念出現的次數越多，意味著此概念更具有代表性，因此將各簇之中的眾數設定為聚類中心，即目標本體概念，實現映射時將其他概念直接由聚類目標本體概念代替，實現本體概念的映射。因此本文提出基于眾數的聚類方法發現映射關系，即K-Modes聚類算法，其思想如下：設集合中共有m個對象，從集合中隨機選擇k個對象，按照預先設定的聚類個數k，將它們設定為聚類中心。然后計算所有對象到這些聚類中心的距離，按照距離最近原則將所有對象聚到各個簇中，接著使用頻次法將聚類中心設定為各簇中的眾數對象，重復計算、選取，定義目標函數：

(9)

W是一個m×k的{0,1}矩陣；wil=1表示第i個對象被劃分到第l類中；Z={z1,z2,…,zk},zl(1≤l≤k)是第l類的中心。聚類迭代，直到目標函數F(W,Z)達到最小，不再發生變化為止。

在使用K-Modes聚類算法時，初始聚類中心的選擇對聚類結果的影響較大，同時K-Modes聚類算法對孤立的數據點比較敏感，容易陷入局部最優，對算法性能產生一定的影響。本文利用K-Modes聚類算法簡單、易操作和運行速度快的特點，對樣本數據進行初始聚類，得到具有一定聚類特征的中間數據。

2.2.2蟻群聚類算法

螞蟻在覓食的時候會釋放一種特殊的分泌物——信息素。它們在尋找食物的路徑選擇中，一開始是隨機地挑選一條可行的路徑，同時會釋放出和該條路徑的長度相關的信息素。當這條路徑走得越遠，信息的釋放就會越來越少。大量的螞蟻在完成尋找食物這個活動的過程中，通向食物的路徑被越來越多的螞蟻走過，因此在這些路徑上存在大量的信息素，后來的螞蟻再次覓食時便會選擇信息素多的路徑，同時給這條路徑釋放更多的信息素，這就形成了一個正反饋機制，這種正反饋機制被有效地用來解決路徑尋優問題。而蟻群覓食的活動過程不僅僅是一個路徑尋優問題，還可以抽象成聚類問題，基于螞蟻覓食行為的聚類方法最早是由Deneubourg等[16]提出，近年來得到了廣泛的發展和應用。

基于蟻群算法覓食原理的聚類算法思路如下：隨機選取一個本體概念Ci作為螞蟻遍歷的起始位置，這只螞蟻根據式(3)或者隨機產生一個隨機值，當該隨機值小于預先設置的閾值s時則將其分配到聚類中心Xj的位置，此時螞蟻就在數據對象Ci到聚類中心Xj的路徑上留下信息素τij。螞蟻選擇聚類中心Xj的概率計算式為：

(10)

(11)

隨著螞蟻的移動，路徑上的信息素不斷揮發，信息素更新計算式表示為：

(12)

式中：ρ表示信息素的揮發系數；Q表示一個正常數。

在迭代初期，由于信息素較少，蟻群聚類算法的收斂速度比較緩慢，所以與K-Modes聚類算法相結合，將數據進行預處理，得到一個聚類雛形，再結合蟻群聚類算法進行聚類，提高聚類結果的準確性。

2.2.3KMACC算法

為解決傳統聚類易收斂于非全局最優及早熟問題，本文將K-Modes聚類算法與蟻群聚類算法相結合并加以改進，提出KMACC算法，應用于本體概念的映射發現中，有效提高了聚類的精度和效率。KMACC算法的流程如圖2所示。

圖2 KMACC算法流程圖

算法具體步驟為：

Step1從本體概念集合中隨機選擇一個本體概念作為第一個類別中心X1。

Step2對于樣本集合中每一個本體概念Ci，計算與上一個剛被選擇成為類別中心的本體概念之間的距離。

Step3距離較大的樣本，被選取作為新的類別中心的概率比較大。

Step4重復Step2和Step3直到k個初始的類別中心被選出。

Step5對每一個本體概念計算與k個類別中心的距離，找到距離最小的Xj后，將該本體概念添加到Xj所在的樣本集合中。

Step6計算得到的k個類別的樣本集合中本體概念的眾數，將這些眾數樣本作為新的k個類別中心。

Step7重復Step5和Step6，滿足迭代次數或者類別中心不再變化時，得到處理后的聚類中心和簇。

Step8對于每個數據對象Ci到相應的聚類中心Xj分配初始不同的信息素τij，其中簇中各樣本到聚類中心的路徑上的信息素多于到其他聚類中心路徑上的信息素。

Step9初始化信息素揮發系數ρ、正常數Q、分配閾值s、螞蟻數n。

Step10隨機產生p∈(0,1)，當隨機數p

Step12所有螞蟻完成一次遍歷后，按照式(12)進行信息素更新，進行迭代。

Step13達到設定的迭代次數t或者S值不再減小時，算法終止，輸出最優聚類結果。

2.3 基于PCA和KMACC的本體映射方法

基于PCA和KMACC的本體映射方法如圖3所示。首先將多個本體樹的本體概念抽取出來放入集合中，采用基于PCA的本體概念相似度計算綜合模型本體概念間的距離，利用K-Modes蟻群聚類算法實現本體概念的聚類，發現映射關系，并將目標本體設定為各簇中出現頻次最多的本體概念，建立映射關系，最后利用基于規則的本體映射修正策略[17]修正映射中出現的偏差，完成映射。

圖3 基于PCA和KMACC的本體映射

3 實 驗

3.1 實驗數據集與實驗設計

為了評估本文模型和算法的有效性，從不同單位建立的指揮信息系統測試評估指標體系中挑選50個指標體系轉換成的本體模型，共計832個本體概念，進行基于機器學習多策略的本體映射實驗。

本文共設計了三個實驗，實驗1對比基于PCA的本體概念相似度計算模型與基于樹結構的相似度計算算法[18]、基于概念屬性的相似度計算算法的效果，選取具有專家評價的140組本體概念對作為訓練樣本，選取10組作為測試樣本；實驗2測試不同聚類中心數的設定對本體聚類映射效果的影響，測試取0到40時本體映射的效果；實驗3對比基于PCA和KMACC的本體映射方法與基于Hownet映射的映射方法、RiMOM方法、基于信息熵聚類的映射方法在50個本體數據上的映射效果并計算算法運行時間。

本文所有實驗基于PC環境，實驗系統配置為Intel Core i7、8 GB內存、Windows 8.1操作系統、Python 3.7環境。

3.2 評價方法

本體概念相似度計算結果通常引入Pearson相關系數[19]進行評價，比較測試樣本所計算出來的相似度與專家評價數據的一致性。Pearson相關系數計算式為：

(13)

表1 Pearson相關系數強度

本體映射對于準確率有較高的要求，查全率R(Recall)與查準率P(Precision)是用來評價本體映射結果質量的重要指標[20]。其中查全率又稱為完整性，代表映射過程中已經找到的正確結果占所有正確結果的比例。R=1意味著所有正確的映射結果都已經找到。查準率表示所有映射的結果中，正確的映射結果所占的比例，P=1意味著所有找到的映射結果都是正確的。最后使用準確率F1值來綜合評價映射的效果，F1定義為：

(14)

3.3 實驗結果與分析

表2為實驗1中三種算法的相似度計算結果與專家評價數據的Pearson相關系數?？梢钥闯?，基于PCA的相似度綜合計算結果與專家評價結果之間的Pearson相關系數最大，達到極強相關；基于樹結構和基于概念屬性的相似度計算結果與專家評價結果之間的Pearson相關系數較小，都處于中等程度相關。實驗結果表明，基于PCA的本體概念相似度綜合計算模型在本文數據集上具有較好的計算效果，可以較為準確地計算出本體概念之間的距離，提高本體概念聚類算法的精度。

表2 三種算法計算結果的Pearson相關系數

圖4為實驗2中K-Modes聚類算法選取不同聚類中心個數k時，映射結果的準確率F1值。可以看出，當聚類中心數較少或者較多時都會影響映射的查全率和查準率。在本文數據集上，本體概念聚類映射的效果在k取19和20時達到最好，說明可以大致將本體概念劃分為19或20個類別，將所有概念聚集到這19或20個類別時，可以較好地完成本體的映射，實驗3中k值取為19。

圖4 本體映射準確率F1與聚類中心個數的關系

圖5為實驗3中基于Hownet的映射算法、RiMOM算法、基于信息熵聚類的映射方法，以及基于PCA和KMACC的本體映射方法在本文數據集上的映射效果?？梢钥闯觯贖ownet的映射方法的查準率較高，但是查全率較低，而RiMOM方法在查準率上存在一定的差距，基于信息熵聚類的本體映射方法在查全率和查準率上都存在較大差距。實驗結果表明，本文提出的基于PCA和KMACC算法的本體映射在查全率和查準率上都取得了較好的效果。

圖5 四種不同方法的映射效果

4 結 語

本文研究一種主成分分析和K-Modes蟻群聚類的本體映射方法。在基于PCA的本體概念相似度綜合計算模型計算本體概念相似度的基礎上，提出K-Modes蟻群聚類算法，實現批量本體概念映射關系的發現，有效提高了映射的準確性。實驗結果表明，相比于基于Hownet的映射方法、RiMOM算法和基于信息熵聚類的本體映射方法，本文方法具有較高的查全率和查準率。下一步的工作主要是增強算法對不同樣本的適應性，完成大量的指揮信息系統測試評估指標的映射和集成。