基于內容的概念格近似自相似度度量

摘要：根據基于內容的概念格圖形的近似自相似性，給出了用戶自定義基塊和劃分細度的近似自相似度度量方法，在此基礎上又提出確定關鍵子塊的近似自相似度度量方法，最后分別用這兩種方法對概念格圖形的近似自相似性進行分析，并提出了概念格近似自相似度度量的應用方向。

關鍵詞：概念格；分形；近似自相似；基塊；關鍵子塊

0 引言

概念格作為一種支持數據分析的有效工具，迅速發展起來。但是在以后的一段時間內，對概念格的研究只是停留在概念格的建造算法和一般性的應用，對體現概念之間的泛化和特化關系的圖形特性的探討沒有突破性進展。近年來，雖然也有一部分學者把注意力轉向了概念格圖形的研究，不過，也僅停留在對給定概念集的可視化布局以及概念格圖形之間的相似比較上。近來，如何利用一種合適的數學工具對概念格圖形自身的特性進行分析，逐漸成為一個令人關注的問題。

與此同時，IBM公司研究中心物理部研究員暨哈佛大學數學系教授曼德勃羅(Benoit B.mandelbrot)在1982年出版了著名的專著《自然界的分形幾何學》，標志著分形理論初步形成。從此，作為非線性科學中的一個前沿課題，分形數學迅速發展起來，并成為分析數學界研究不規則幾何圖形問題的有力工具；尤其是“分形”的定義，突出了分形的自相似性，反映了自然界中廣泛存在的一類物質的基本屬性：局部與局部，局部與整體在形態、功能、時間、空間以及內容等方面具有統計意義或近似的自相似性。

本文試圖通過分析概念格圖形的特征，提出概念格圖形的近似自相似特性，并給出基于子塊的概念格圖形的近似自相似度度量方法；在此基礎上，介紹了具體的軟件實現原型和計算結果；最后對兩種方法的特點進行了分析。

1 概念格圖形近似自相似特性

概念格圖形的一種表示方法是線圖表示法，這種表示形式生動、簡潔地體現了概念之間的泛化和特化關系。在線圖表示中，一個節點代表著一個概念，一條邊代表與之相連的兩個節點之間的偏序關系。每個概念又是由一類具有相同對象的屬性集和這些對象(也可以是具有相同屬性的對象集和這些屬性)組成的一個二元組；由此，對于每個具體的線圖而言，其內部的各個節點組成的組，即概念組之間在內容上存在著很大的相似特性，也就是說概念格局部與局部之間在內容上存在著一定的相似特性。同理，我們對線圖進行適當的劃分，經分析發現，在內容上，各個子塊之間也存在著一定的相似性，并且各個子塊內部同樣存在著一定自相似性，而概念節點的個數與內容就成了度量線圖近似自相似特性的標準；如果再對線圖的每條邊附上一個恰當的權值，并且這個權值能夠正確反映兩個概念之間在內容上的相似關系，那么，邊也可以成為度量兩個概念之間相似性的依據。根據這些特征，我們提出了分析概念格圖形的近似自相似度的兩種方法：一種是基于用戶自定義基塊和劃分細度的概念格圖形的近似自相似度度量方法；另一種是基于確定關鍵子塊的概念格圖形的近似自相似度度量方法。

2 概念格圖形近似自相似特性的度量方法

從嚴格意義上來講，概念格圖形并不是完全自相似特性的圖形結構，只是具有近似自相似特性，因此，我們不能用傳統的分析分形圖的一些參數或函數，例如自相似維數，仿射變換等對概念格圖形進行定量分析。本文根據概念格自身的基于內容的近似自相似特性，提出了基于用戶自定義基塊和劃分細度的近似自相似度度量方法，以及基于確定關鍵子塊的近似自相似度度量方法。

2．1用戶自定義基塊和劃分細度的近似自相似度度量方法

如果要計算具有一定規模的概念格圖形的近似自相似度，一種方法就是對該圖形進行劃分，并以其中的一個子塊為基塊來提取圖形的特征值進行分析。實際上，用戶一般只對其中的某一類或某幾類對象或者屬性感興趣，即他們關注的只是具有這些對象或者屬性的子概念集。基于此，本文把內容上的相似性作為概念格圖形的一個特征值，并以此作為劃分依據；為了增加圖形的整體近似自相似度，允許劃分時各個子塊之間有重疊的概念節點和邊。

不同的用戶可能對關注內容要求的精確程度不一樣，如果將概念格圖形的劃分細度固定，將會給用戶帶來不便。因此，本方法將概念格圖形的劃分細度交給了用戶，即用戶可以根據需要自定義劃分細度。例如，—個用戶只關心與—個對象相關的概念節點，那么該用戶就可以要求概念格圖形的劃分細度為1；如果另—個用戶關心的對象個數為n，那么該用戶就可以要求概念格圖形的劃分細度為n(n>1)。如果給定的概念格中對象的總個數為m，那么n的取值范圍就是(0，m)；通過測試發現，這樣劃分以后，基于某一對象的子塊可能具有一定的相似性。例如，圖2就是利用基于內容的劃分細度為1的方法對圖l給出的概念格圖形進行劃分后得到的部分子塊。從圖中可以看出，對象l所對應的子塊被包含于對象2所對應的子塊之中，對象3所對應的子塊與對象5所對應的子塊在結構上非常相似。如果我們繼續劃分下去，可以看到更多的相關信息。

基塊的選擇，也是求解概念格圖形的近似自相似度的關鍵問題。所以，選擇基塊時需要全面考慮劃分問題和整個方法的構造設計。本文所提出的用戶自定義基塊和劃分細度的概念格圖形的近似自相似度度量方法是以用戶需求作為主導思想的，為了和劃分以及整體設計保持一致，基塊的選擇仍然由用戶來決定，即用戶在確定劃分細度的同時就可以確定出整個概念格圖形的基塊。

對于已經劃分好，并且確定了基塊的概念格圖形，我們采用整體近似自相似度(記作Self-similarity)和局部相似度(記作Sub-similarity)來對給定的概念格圖形進行定量分析。假定給定的概念格圖形中的概念節點中，對象的最大數目是m，則可以對Self-similarity和Sub-similarity進行如下定義：

(1)Self-similarity始終是大于0、小于等于1的實數。

(2)如果用戶自定義的劃分細度為(0，m)之間的—個整數值k，那么按照各個子塊進行兩兩比較，求出局部的相似度Sub-similarity是與子塊的節點個數以及概念的外延和內涵相關的，因此可以定義任意兩個子塊之間的局部相似度Sub-similarity為：

其中m₁≥k，m₂≥k分別表示子塊a，b中概念節點的個數；n表示兩個子格中相同概念節點的個數；MAX(S_i)是指子塊a(b)中的節點與b(a)中的節點相比得到的最大相似度；f(a，b)指子塊a，b之間的相似度。然后按照加權求平均的方法來確定最終Self-similarity：

其中d≤m-k為按照用戶的選擇所確定的子塊個數；a_i指第i個子塊，在這里指基塊；b_j指第j個子塊(i，j≥0)；f(a，b)指a_i，b_j兩個子塊的局部相似性，即a_i這個子塊與b_j子塊相比得到的相似度；w_i指a_i和b_j這兩個子塊在整個概念格圖形中所占的權重；S(A)指概念格A的整體近似自相似度。

(3)如果用戶自定義的劃分細度為m，那么Self-similarity等于1。

2．2確定關鍵子塊的近似自相似度度量方法

如果要對一個事物進行定性分析，必須要找出該事物不隨外界變化而變化的那一部分特征并加以分析。因此，采用哪種方法以及如何找出這種特征就成為定性分析的一個關鍵問題。具體到概念格圖形的近似自相似度度量這個問題，利用用戶自定義基塊和劃分細度的方法來度量概念格圖形的近似自相似度，雖然具有很大的靈活性，但是缺少一個固定的標準，因此在基于確定關鍵子塊的概念格圖形的近似自相似度度量方法中，我們利用模擬關鍵路徑算法來確定一個概念格圖形的“關鍵子塊”，將其作為自相似度度量的基塊。并在此基礎上確定給定概念格圖形的近似自相似度范圍。算法的主要思想如下：

(1)將概念格圖形轉化為一個帶權的有向無環圖，其中分別將頂節點(外延最大或內涵最大)和底節點(內涵最大或外延最大)作為該有向無環圖的起點和終點，有向無環圖的方向為概念節點集中的概念，節點的上界指向該概念節點，而該概念節點指向概念節點的下界；

(2)如果兩概念節點之間存在偏序關系，那么將這兩概念節點的外延(或者內涵)集合中具有的相同元素個數加1作為這兩個概念節點所確定的邊上的權值，用以衡量這兩個概念節點之間基于內容的相似度；

(3)自上而下求出給定概念格圖形中每個概念節點的基于內容的最大相似度，然后自下而上逆向求出每個概念節點的基于內容的最小相似度；

(4)最大相似度與最小相似度相同的概念節點以及他們之間的偏序關系所構成的子塊就是與整個概念格圖形相似度最大的子塊，即要求解的概念格圖形的關鍵子塊。

確定了概念格圖形的關鍵子塊，就可以求出基于關鍵子塊的概念格圖形的整體近似自相似度。本文利用求平均的方法求出關鍵子塊中每兩個概念節點之間的平均相似度作為該關鍵子塊的近似自相似度(記作key-Self-similarity)；由于關鍵子塊是基于內容的與整個概念格圖形相似度最大的子塊，因此將關鍵子塊的近似自相似度作為整個概念格圖形自相似度的最大值，即該概念格圖形的整體近似自相似度Self-similarity的取值范圍是(0，key-Self-similarity]。

基于確定關鍵子塊的概念格圖形的近似自相似度度量方法雖然只是給出了概念格圖形的近似自相似度范圍，但是，與第一種基于用戶自定義基塊和劃分細度的概念格圖形的近似自相似度度量方法相比，卻具有更好的可靠陛。我們還可以使用相同的思想，對概念格圖形的非關鍵子塊部分求解次關鍵子塊，然后在確定次關鍵子塊的近似自相似度的基礎上逐步求精，直至得到最終的概念格圖形的整體近似自相似度。

3 軟件實現

本文提出的兩種方法均用C#語言實現。用戶自定義基塊與劃分細度的近似自相似度度量方法的操作步驟如下：

輸入：(1)具體概念格圖形的對象集和概念集；

(2)用戶選擇感興趣的子塊作為基塊；

(3)選定與基塊相比較的子塊。

輸出：(1)基塊與所選子塊之間的局部相似性；

(2)概念格圖形的整體近似自相似度。

確定關鍵子塊的近似自相似度度量方法的操作步驟如下：

輸入：具體概念格圖形的對象集和概念集以及概念之間的偏序關系。

輸出：(1)存在偏序關系的各個概念節點之間的權重信息；

(2)概念格圖形的關鍵子塊；

(3)概念格圖形的整體近似自相似度范圍。

根據圖1中給出的整體概念格圖形，分別以基于用戶自定義基塊與劃分細度的概念格圖形的近似自相似度度量方法和基于確定關鍵子塊的概念格圖形的近似自相似度度量方法求解該概念格圖形的整體自相似度。從測試結果可以看出，采用基于用戶自定義基塊和劃分細度的方法得到的結果會因為用戶選擇的基塊和劃分細度的不同而不同：當用戶以對象1所對應子塊為基塊，劃分細度為1時，整體自相似度為39％．用戶以對象8所對應子塊為基塊，劃分細度為1時，整體自相似度為40％。而采用基于確定關鍵子塊的方法時，得到的結果是0％～40％。

4 結束語

本文通過分析概念格圖形，提出了概念格圖形的近似自相似特征，并且給出了度量概念格圖形的近似自相似度的方法——一用戶自定義基塊和劃分細度的度量方法，以及定性分析概念格圖形的近似自相似度的方法——確定關鍵子塊的度量方法。

用戶自定義基塊和劃分細度的近似自相似度度量方法的主要設計思想是充分利用人機交互功能來解決劃分難題，利用該方法求概念格的近似自相似度的優點是操作比較靈活，即用戶可以根據不同的需求，自行選擇不同的基塊和劃分的細度。確定關鍵子塊的近似自相似度度量方法雖然不能直接計算出給定概念格圖形的近似自相似度，但是可以精確地求出給定概念格圖形的近似自相似度的范圍。

在實際應用中，可以將兩種方法綜合使用。例如在利用概念格形式顯示的信息分類中，用戶可以采用用戶自定義基塊和劃分細度的近似自相似度度量方法，根據自己的標準來衡量所關注內容的結構和布局；也可以采用確定關鍵子塊的近似自相似度度量方法度量信息分類的合理性等。