基于內(nèi)容的概念格近似自相似度度量

摘要：根據(jù)基于內(nèi)容的概念格圖形的近似自相似性，給出了用戶自定義基塊和劃分細(xì)度的近似自相似度度量方法，在此基礎(chǔ)上又提出確定關(guān)鍵子塊的近似自相似度度量方法，最后分別用這兩種方法對(duì)概念格圖形的近似自相似性進(jìn)行分析，并提出了概念格近似自相似度度量的應(yīng)用方向。

關(guān)鍵詞：概念格；分形；近似自相似；基塊；關(guān)鍵子塊

0 引言

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

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

本文試圖通過分析概念格圖形的特征，提出概念格圖形的近似自相似特性，并給出基于子塊的概念格圖形的近似自相似度度量方法；在此基礎(chǔ)上，介紹了具體的軟件實(shí)現(xiàn)原型和計(jì)算結(jié)果；最后對(duì)兩種方法的特點(diǎn)進(jìn)行了分析。

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

概念格圖形的一種表示方法是線圖表示法，這種表示形式生動(dòng)、簡(jiǎn)潔地體現(xiàn)了概念之間的泛化和特化關(guān)系。在線圖表示中，一個(gè)節(jié)點(diǎn)代表著一個(gè)概念，一條邊代表與之相連的兩個(gè)節(jié)點(diǎn)之間的偏序關(guān)系。每個(gè)概念又是由一類具有相同對(duì)象的屬性集和這些對(duì)象(也可以是具有相同屬性的對(duì)象集和這些屬性)組成的一個(gè)二元組；由此，對(duì)于每個(gè)具體的線圖而言，其內(nèi)部的各個(gè)節(jié)點(diǎn)組成的組，即概念組之間在內(nèi)容上存在著很大的相似特性，也就是說概念格局部與局部之間在內(nèi)容上存在著一定的相似特性。同理，我們對(duì)線圖進(jìn)行適當(dāng)?shù)膭澐郑?jīng)分析發(fā)現(xiàn)，在內(nèi)容上，各個(gè)子塊之間也存在著一定的相似性，并且各個(gè)子塊內(nèi)部同樣存在著一定自相似性，而概念節(jié)點(diǎn)的個(gè)數(shù)與內(nèi)容就成了度量線圖近似自相似特性的標(biāo)準(zhǔn)；如果再對(duì)線圖的每條邊附上一個(gè)恰當(dāng)?shù)臋?quán)值，并且這個(gè)權(quán)值能夠正確反映兩個(gè)概念之間在內(nèi)容上的相似關(guān)系，那么，邊也可以成為度量?jī)蓚€(gè)概念之間相似性的依據(jù)。根據(jù)這些特征，我們提出了分析概念格圖形的近似自相似度的兩種方法：一種是基于用戶自定義基塊和劃分細(xì)度的概念格圖形的近似自相似度度量方法；另一種是基于確定關(guān)鍵子塊的概念格圖形的近似自相似度度量方法。

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

從嚴(yán)格意義上來講，概念格圖形并不是完全自相似特性的圖形結(jié)構(gòu)，只是具有近似自相似特性，因此，我們不能用傳統(tǒng)的分析分形圖的一些參數(shù)或函數(shù)，例如自相似維數(shù)，仿射變換等對(duì)概念格圖形進(jìn)行定量分析。本文根據(jù)概念格自身的基于內(nèi)容的近似自相似特性，提出了基于用戶自定義基塊和劃分細(xì)度的近似自相似度度量方法，以及基于確定關(guān)鍵子塊的近似自相似度度量方法。

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

如果要計(jì)算具有一定規(guī)模的概念格圖形的近似自相似度，一種方法就是對(duì)該圖形進(jìn)行劃分，并以其中的一個(gè)子塊為基塊來提取圖形的特征值進(jìn)行分析。實(shí)際上，用戶一般只對(duì)其中的某一類或某幾類對(duì)象或者屬性感興趣，即他們關(guān)注的只是具有這些對(duì)象或者屬性的子概念集?；诖耍疚陌褍?nèi)容上的相似性作為概念格圖形的一個(gè)特征值，并以此作為劃分依據(jù)；為了增加圖形的整體近似自相似度，允許劃分時(shí)各個(gè)子塊之間有重疊的概念節(jié)點(diǎn)和邊。

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

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

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

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

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

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

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

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

2．2確定關(guān)鍵子塊的近似自相似度度量方法

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

(1)將概念格圖形轉(zhuǎn)化為一個(gè)帶權(quán)的有向無環(huán)圖，其中分別將頂節(jié)點(diǎn)(外延最大或內(nèi)涵最大)和底節(jié)點(diǎn)(內(nèi)涵最大或外延最大)作為該有向無環(huán)圖的起點(diǎn)和終點(diǎn)，有向無環(huán)圖的方向?yàn)楦拍罟?jié)點(diǎn)集中的概念，節(jié)點(diǎn)的上界指向該概念節(jié)點(diǎn)，而該概念節(jié)點(diǎn)指向概念節(jié)點(diǎn)的下界；

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

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

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

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

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

3 軟件實(shí)現(xiàn)

本文提出的兩種方法均用C#語(yǔ)言實(shí)現(xiàn)。用戶自定義基塊與劃分細(xì)度的近似自相似度度量方法的操作步驟如下：

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

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

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

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

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

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

輸入：具體概念格圖形的對(duì)象集和概念集以及概念之間的偏序關(guān)系。

輸出：(1)存在偏序關(guān)系的各個(gè)概念節(jié)點(diǎn)之間的權(quán)重信息；

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

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

根據(jù)圖1中給出的整體概念格圖形，分別以基于用戶自定義基塊與劃分細(xì)度的概念格圖形的近似自相似度度量方法和基于確定關(guān)鍵子塊的概念格圖形的近似自相似度度量方法求解該概念格圖形的整體自相似度。從測(cè)試結(jié)果可以看出，采用基于用戶自定義基塊和劃分細(xì)度的方法得到的結(jié)果會(huì)因?yàn)橛脩暨x擇的基塊和劃分細(xì)度的不同而不同：當(dāng)用戶以對(duì)象1所對(duì)應(yīng)子塊為基塊，劃分細(xì)度為1時(shí)，整體自相似度為39％．用戶以對(duì)象8所對(duì)應(yīng)子塊為基塊，劃分細(xì)度為1時(shí)，整體自相似度為40％。而采用基于確定關(guān)鍵子塊的方法時(shí)，得到的結(jié)果是0％～40％。

4 結(jié)束語(yǔ)

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

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

在實(shí)際應(yīng)用中，可以將兩種方法綜合使用。例如在利用概念格形式顯示的信息分類中，用戶可以采用用戶自定義基塊和劃分細(xì)度的近似自相似度度量方法，根據(jù)自己的標(biāo)準(zhǔn)來衡量所關(guān)注內(nèi)容的結(jié)構(gòu)和布局；也可以采用確定關(guān)鍵子塊的近似自相似度度量方法度量信息分類的合理性等。