一種高效的分辨函數范式轉換算法

摘 要:基于分辨矩陣獲取一個決策表所有約簡的過程實質上是一個將分辨函數從合取范式轉換為析取范式的過程，其效率對于屬性約簡算法性能至關重要。依據人工范式轉換的運行機制，充分利用合取運算和析取運算的吸收率，并借助隊列結構，提出了一種面向分辨函數的范式轉換算法。該算法易于理解，實現簡便。仿真實驗表明算法能夠高效地完成范式轉換。

關鍵詞:粗糙集; 分辨函數; 合取范式; 析取范式

中圖分類號:TP181 文獻標志碼:A

文章編號:1001-3695(2010)03-0879-04

doi:10.3969/j.issn.1001-3695.2010.03.019

High-efficient algorithm for normal form conversion ofdiscernibility function

ZHANG De-dong， LI Ren-pu， ZHAO Yong-sheng

(School of Computer Science Technology， Ludong University， Yantai Shandong 264025， China)

Abstract:The process obtaining all reducts of a decision table based on discernibility matrix is virtually a process transforming a discernibility function from conjunction normal form to disjunction normal form， and the transformation efficiency plays an important role in the performance of attribute reduction algorithm. Through making the best of the absorptivity of conjunction operation and disjunction operation， based on the mechanism of artificial normal form conversion， proposed an algorithm transforming a discernibility function from conjunction normal form to disjunction normal form with virtue of queue framework. This algorithm was easy to understand and to realize. And the simulative experiments show that it is very efficient to accomplish normal form conversion.

Key words:rough sets; discernibility function; conjunction normal form; disjunction normal form

粗糙集理論[1]是一種處理不精確、不確定性數據的數學方法。經過二十多年的快速發展， 該理論在數據挖掘、人工智能、模式識別等領域獲得了廣泛的應用[2]。粗糙集理論中屬性約簡方法大致可以分為兩種:a)通過計算屬性的重要性來獲取約簡[3，4];b)通過Skowron等人[5]分辨矩陣求得約簡。其中基于符號推理的分辨矩陣方法可以方便地獲取決策表的所有約簡，而且約簡過程簡單明了，因此在約簡算法的設計中被廣泛采用[6~8] 。在應用分辨矩陣時，為了獲得所有約簡，必須實現分辨函數的合取范式向析取范式的轉換。然而，目前對于分辨函數合取范式到析取范式轉換的具體實現算法的研究較少。實際應用中一般采用人工轉換的方法或基于機器的全局搜索方法，不過當屬性個數和合取范式析取項的數量較多時這兩種方法的轉換效率比較低下，使得范式轉換效率成為屬性約簡算法的瓶頸問題。

Skowron等人已證明基于分辨矩陣計算一個決策表的所有約簡的時間復雜度是指數級[5]。盡管無法改變該類方法的時間復雜度，但相關研究[9，10]表明通過設計合理的范式轉換算法仍然可以在一定屬性個數的閾值內有效地降低算法的運行時間，實現快速的范式轉換。文獻[9]提出了一個矩陣轉換的直接搜索方法，分析了分辨矩陣與析取范式之間的關系，不過算法的實現比較復雜，且在運行的過程中會產生很多的冗余數據，影響了算法的執行效率。文獻[10]基于二分法技術給出了一個范式轉換方法，但是并沒有給出算法的具體實現。

為最大化減少冗余數據，提高范式轉換的效率，本文充分運用合取和析取運算的吸收率，借助隊列結構，提出了一個模擬人工范式轉換的算法。算法原理簡單，易于實現，UCI數據和不同數據規模上的大量仿真實驗表明算法是高效可行的。

1 分辨矩陣和分辨函數

一個決策表可表示為T=(U，C∪g0gggggg，f)。其中:U={x1，x2，…，xn}為決策表的對象集合;C={C1，C2，…，Ck}是條件屬性集合;d是決策屬性;f為對象到屬性值的映射函數。表1是一個決策表。

表1 決策表

UC1C2C3C4dUC1C2C3C4d

x110211x421102

x212002x521211

x302210

對于決策表而言，分辨矩陣用來記錄決策值不同的兩個對象的可區分條件屬性。一個決策表的分辨矩陣是一個n×n對稱矩陣，記為M。對于x，y∈U，其矩陣元素mx，y由式(1)定義。

mx，y={a∈C|fa(x)≠fa(y) and

fd(x)≠fd(y)}

otherwise(1)

以下是對應于表1決策表的分辨矩陣。

分辨函數F是一個合取范式，可由分辨矩陣直接得到，其形式由式(2)定義，其每一子項對應分辨矩陣中的每個矩陣元素。

F=∧{∨mi，j|mi，j≠};i， j=1，2，…，n(2)

式(3)為由分辨矩陣構成的并經過約簡后的分辨函數合取范式。

F=(C1∨C2)∧(C3∨C4)(3)

經過范式轉換，可以得到分辨函數的析取范式，其每一子項對應一個決策表約簡。式(4)即為式(3)經過范式轉換后得到的對應析取范式。

F=(C1∧C3)∨(C1∧C4)∨(C2∧C3)∨(C2∧C4)(4)

由式 (4)可知表1決策表共有四個約簡，分別是{C1， C3}，{C1，C4}，{C2，C3}和{C2，C4}。

2 范式轉換算法

在基于機器的范式轉換方法中，常用的是全局搜索[9]算法。這種算法通過搜索所有可能的屬性組合，來獲取合取范式的析取范式，是一種窮舉的方法，在數據規模較大時，此方法是比較低效的。

文獻[9]通過分析合取矩陣與析取矩陣之間的聯系， 發現了合取矩陣中每個非零元素在析取矩陣中的分布規律。基于這種分布規律，提出了范式轉換的一個直接搜索算法。為了討論方便，本文簡稱為算法Z。由于算法Z只是組合合取矩陣中的非零元素，與全局搜索算法相比，算法Z舍棄了很多的冗余計算，大大降低了范式轉換的時間量。然而，對比人工范式轉換的方法，筆者發現算法Z仍有較大的改進空間。

2.1 算法思想

人工轉換合取范式為析取范式時，一般每轉換完合取范式的一個析取項，都會對已求得的計算結果根據合取運算和析取運算的吸收率進行約簡，以便于簡化下一步的計算。這種約簡機制會使得最后獲取的析取范式的合取項個數并不等于文獻[9]所示的合取矩陣中所有行非零元素個數的乘積， 但是由于算法Z是通過預先計算出合取矩陣中每個非零元素的分布函數，然后根據分布函數來產生析取矩陣，在范式的轉換過程中，無法進行約簡，從而導致算法Z的輸出結果中存在大量冗余的合取項，降低了算法的執行效率。

借鑒人工范式轉換的思想，構造了一個線性的、由前到后的轉換合取范式為析取范式的算法。首先把合取范式的第一個析取項轉換為析取范式;然后連接合取范式中剩余的析取項，在轉換完一個析取項后根據合取析取運算的吸收率進行約簡以消除所有的冗余項，約簡后的結果再作為新的運算對象參加下一步的運算，直到計算完所有的析取項;最后的結果即為與合取范式對應的析取范式。

例如，對于合取范式F=(C1∨C2)∧(C2∨C4)∧(C3∨C4)，首先轉換前兩個析取項(C1∨C2)∧(C2∨C4)，計算得(C1∧C2)∨(C1∧C4)∨(C2∧C2)∨(C2∧C4)，經約簡得C2∨(C1∧C4)，下一步把剛求得的結果作為一個析取范式與剩下的析取項(C3∨C4)進行連接，計算得(C2∧C3)∨(C2∧C4)∨(C1∧C3∧C4)∨(C1∧C4∧C4)，經約簡得(C1∧C4)∨(C2∧C3)∨(C2∧C4)，此即為與F=(C1∨C2)∧(C3∨C4)∧(C2∨C4)對應的合取范式。

為了便于算法的描述和設計，本文使用矩陣來表示一個范式，矩陣的列數為|C|+1，即條件屬性的個數加1。

對于合取范式，其每個析取項構成一個矩陣行，每行的第1位記錄析取項中包含的條件屬性的個數，后面的|C|個位對應各條件屬性。如果析取項包含某個條件屬性，則矩陣行對應屬性位為1，否則為0。由合取范式構造的矩陣稱為合取矩陣。

同理，依據析取范式構造析取矩陣。易知范式矩陣中每行第1位的值即為該行中其他位為1的個數，記錄該值便于根據析取、合取運算的吸收率約簡范式矩陣。例如，式(3)對應的合取范式矩陣為2 1 1 0 02 0 0 1 1式(4)對應的析取范式矩陣為2 1 0 1 02 1 0 0 12 0 1 1 02 0 1 0 1

2.2 算法的實現

根據人工轉換范式的特點，借助隊列結構，設計算法如下:

算法Q

輸入:合取矩陣CM。

輸出:析取矩陣DM。

(a)初始化兩個隊列Q1和Q2為空，初始化一個計數器count，初值0。

(b)把合取矩陣CM以每行作為一個隊列元素輸入到隊列Q1，然后約簡Q1。

(c)從Q1中退出一個隊列元素P，把隊列元素P 中對應屬性位的m個1拆分為m個隊列元素，其第1位均設為1，其他屬性位中僅有一個設為1，其他屬性位都為0。然后將這m個隊列元素入隊列Q2，令count = m。

(d)如果Q1為空，轉(g);否則退出隊頭元素Q1_head。

(e)如果count為0，約簡Q2，并用count記錄Q2中的元素個數，轉(d);否則從Q2中退出隊頭元素Q2_head，令count--;

(f)若掃描完Q1_head的所有屬性位轉(e);否則令temp=Q2_head，把Q1_head中值為1 的屬性位與temp的相應屬性位進行或運算，并在temp的第1位記錄運算后1的個數，把temp入隊列Q2，轉(f)。

(g)輸出Q2到矩陣DM。

算法分析:算法Q由兩個基本的操作構成，即約簡運算和或運算。約簡運算的時間復雜度為O(∑Mi=2|C|×|C|i)=O(|C|M+1);或運算的時間復雜度為O(|C|M)，因此算法Q的時間復雜度為O(|C|M)。 空間復雜度為O(|C|×M)。其中:|C|為條件屬性個數;M為合取范式的析取項個數。

2.3 一個示例

下面用文獻[9]中合取矩陣R來演示算法Q的操作步驟。合取矩陣R如下:

1 0 1 0 0 0 0 01 0 0 0 1 0 0 02 0 0 1 0 0 1 02 1 0 0 0 0 0 12 0 0 0 0 0 1 1

它代表的合取范式為

F=C2∧C4∧(C3∨C6)∧(C1∨C7)∧(C6∨C7)

a)初始化，執行算法Q的(a)和(b)得到

Q1:1 0 1 0 0 0 0 01 0 0 0 1 0 0 02 0 0 1 0 0 1 02 1 0 0 0 0 0 12 0 0 0 0 0 1 1 Q2:||

b)從Q1中退出隊頭元素，執行算法Q的(c)得到

Q1:1 0 0 0 1 0 0 02 0 0 1 0 0 1 02 1 0 0 0 0 0 12 0 0 0 0 0 1 1 Q2:|1 0 1 0 0 0 0 0 |

c)Q1不空，執行算法Q的(d)~(f)得

d)Q1為空，執行算法Q的(g)，輸出R的析取矩陣為

4 0 1 1 1 0 0 14 1 1 0 1 0 1 04 0 1 0 1 0 1 1

轉換后得到F的析取范式為

(C2∧C3∧C4∧C7)∨(C1∧C2∧C4∧C6)∨(C2∧C4∧C6∧C7)

3 實驗

為了測試本文所提算法Q的性能，筆者設計了三組實驗，其目的分別如下:

a)實驗1是為了比較算法Q和算法Z[9]在不同數據上的各項性能;

b)實驗2是為了觀察當合取范式的析取項個數變化而屬性個數不變時，算法Q各項性能指標的變化規律;

c)實驗3是為了觀察當合取范式的析取項個數和屬性個數同時變化時，算法Q各項性能參數的變化規律。

實驗數據包含三個UCI數據庫數據以及隨機生成的由0和1組成的矩陣數據(不失一般性，因為分辨矩陣中的每個矩陣元素可以轉換為一個0、1矩陣行，且隨著隨機產生的矩陣規模的增加，隨機矩陣最終會覆蓋由分辨矩陣轉換成的0、1矩陣)。隨機生成的每個矩陣代表一個不包含計數位的合取矩陣， 即矩陣列代表屬性個數、矩陣行代表合取范式的析取項個數，矩陣的計數位在程序初始化時計算。 算法用VC 6.0實現，CPU為Pentium4 2.4 GHz， 內存為768 MB。

3.1 實驗1

為了比較算法Q和算法Z的各項性能參數，首先在UCI數據 letter、led24、zoo上對兩個算法作了比較。表2描述了三個數據的基本特征。實驗結果如表3所示。

表2 UCI數據描述

UCI數據對象個數條件屬性個數

letter14 99916

led243 20024

zoo10116

表3 UCI數據上的性能比較

數據

算法Z算法Q

運算時間/ms約簡前/后合取項個數運算時間/ms約簡前/后合取項個數

zoo1 304.821.16×107/682.8868/68

led24-1.71×1027/120.3312/12

letter-2.87×1028/342.0634/34

然后在合取矩陣R和隨機生成的模式分別為8×8，8×10，8×12的合取矩陣上分別運行兩種算法。實驗結果如表4所示。

表4 隨機數據上的性能比較

數據模式

算法Z算法Q

運算時間/ms約簡前/后合取項個數運算時間/ms約簡前/后合取項個數

矩陣R3.628/32.473/3

8×8385.041 728/92.629/9

8×107 061.3227 000/343.8334/34

8×1258 269.40210 000/444.2144/44

由表3知，算法Z在三組數據上分別產生了1.16×107，1.71×1027，2.87×1028個合取項，約簡后的合取項分別為68、12、34;由表5知，算法Z在四組數據上分別產生了8、1 728、27 000、210 000個合取項，約簡后的合取項個數分別為3、9、34、44，這說明算法Z產生的合取項個數中真正非冗余合取項只占很少的比重。正是因為算法Z在轉換過程中要處理大量的冗余數據，所以導致了算法Z較低的時間效率，以至于在led24和letter兩個數據上， 算法Z不能夠在可接受的時間內完成范式轉換。而算法Q由于在轉換完一個析取項后要進行一次約簡合取項的操作， 降低了后續轉換操作的計算量，從而在各類數據上的運行效率均明顯高于算法Z，且隨著數據規模的增大，該效率優勢更加明顯。

3.2 實驗2

為了觀察當合取范式的析取項個數變化而屬性個數不變時算法Q的各項性能指標，本文選擇了8個合取矩陣作為實驗數據，它們的屬性個數都是16，它們的析取項個數分別為100、200、400、600、800、1 000、4 000、10 000。

實驗結果如表5所示。通過表5可以看到，對16個屬性進行隨機組合構成合取矩陣，當矩陣行數即分辨函數合取范式的析取項個數在600~800時，算法的運算時間達到最大值，同時范式轉換后析取范式的合取項個數也達到最大值;當矩陣行數大于800后，其運算時間呈遞減趨勢。出現這種現象的原因是:由于算法Q中約簡機制的存在，當矩陣行數增加到某個極限值后，各行之間相互約簡的可能性也在增加，這反而使得非冗余析取項個數減少，從而使得算法Q運行時的初始數據被大大地消減了，進而使得算法Q的運算時間在矩陣行數大于某個值后會逐漸減少。

表5 算法Q的性能指標

數據模式運算時間/ms產生的合取項個數數據模式運算時間/ms產生的合取項個數

100×166 877.7696800×1662 131.11 021

200×1623 433.18971 000×163 890.7888

400×1633 670.49834 000×163 310.6357

600×1654 722.41 07510 000×16780.4195

由此可推知，假設固定條件屬性的個數，決策表分辨矩陣中非冗余析取項個數存在一個極大值，算法Q在此處獲得運算時間的最大值。在達到最大值后，決策表規模的增大反而會減少其分辨矩陣中析取項的個數。事實上，當用所有的屬性組合構造一個分辨矩陣后，會發現約簡后獲得的析取項個數正好等于全部條件屬性的個數，其對應的約簡是所有條件屬性組成的集合。

3.3 實驗3

由于算法Q的時間復雜度取決于兩個參數:條件屬性的個數、合取范式中的析取項個數，為觀察在兩個參數同時變化時算法Q的各項性能指標，本文選擇25×14、50×16、75×18、100×20四個合取矩陣作為實驗數據。實驗結果如表6所示。

表6 算法Q的性能指標

數據模式運算時間/ms產生的合取項個數數據模式運算時間/ms產生的合取項個數

25×146414875×1852 7471 432

50×161 602480100×20651 3803 597

從表6可以看出，隨著條件屬性的個數和合取范式中析取項個數的增加，算法Q的運算時間量也以更大的增長率增加，這與算法Q的時間復雜度是指數級的相關。同時也看到，當屬性個數和析取項個數增加時，合取項的個數也增加得很快，這也說明算法產生的合取項個數與算法的運行時間之間存在直接的聯系。

4 結束語

盡管范式轉換算法的時間復雜度是指數級的，但是仍然可以通過設計合理實用的轉換算法來獲得高效的轉換效率，以快速地獲取決策表所有約簡。本文通過模擬人工范式轉換的原理，基于隊列結構，提出了一個基于直接搜索的分辨函數范式轉換算法，UCI數據和仿真數據上的仿真實驗顯示算法是有效可行的。應該指出的是，盡管本文算法在一定數據規模(如屬性個數不是很多時)內可以高效地進行范式轉換，但在屬性個數較多時其實用性將大大降低，此時采用啟發式的屬性約簡算法是一種現實的選擇。

參考文獻:

[1]PAWLAK Z. Rough set[J]. International Journal of Computer and Information Sciences， 1982，11(5):341-356.

[2]PAWLAK Z. Rough sets and intelligent data analysis[J]. Information Sciences， 2002，147(1-4):1-12.

[3]徐章艷. 一個復雜度為max(O(|C||U|)，O(|C|~2|U/C|))的快速屬性約簡算法[J]. 計算機學報， 2006，29(3):391-399.

[4]王國胤，于洪，楊大春. 基于條件信息熵的決策表約簡[J]. 計算機學報， 2002，25(7):759-766.

[5]SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems[M]//SLOWINSKI R. Intelligent decision support: handbook of applications and advance of the rough sets theory.[S.l.]: Kluwer Academic Publishers， 1992: 331-362.

[6]KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information Science， 1998，112(1-4): 39-49.

[7]楊明. 一種基于改進差別矩陣的屬性約簡增量式更新算法[J]. 計算機學報， 2007，30(5):815-822.

[8]周創德， 田衛東. 基于約束函數的差別矩陣及其求核算法[J]. 計算機工程， 2008，34(15):60-63.

[9]趙榮泳，張浩，李翠玲，等. 粗糙集理論中分辨函數的析取范式生成算法[J]. 計算機工程， 2006，32(2):183-185.

[10]王元珍，裴小兵. 基于Skowron分明矩陣的快速約簡算法[J]. 計算機科學， 2005，32(4):42-44.

(上接第873頁)

遺傳算子設計合理，可以確保繼承父代的優良特性和保持種群的多樣性，從而能夠較快找到理想解。

4 結束語

回收品質量、數量和拆卸過程中的不確定性使得再制造生產中工件的加工路徑具有顯著的可變性特點。為此，本文提出了一種可變長工序編碼方法，設計了相應的異常染色體的識別、重構方法以及遺傳算子的實現方法。這種改進的遺傳算法在參數矩陣的指導下，可以實現隨機工序數目和隨機工序順序情況下再制造生產調度問題的優化求解，仿真實驗證明了該算法的有效性和可行性。

參考文獻:

[1]LUND R T. Remanufacturing[J]. Technology Review， 1984， 87(2): 18-23.

[2]JAYARAMAN V. Production planning for closed-loop supply chains with product recovery and reuse: an analytical approach[J]. International Journal of Production Research， 2006，44(5): 981-998.

[3]Jr GUIDE V D R， JAYARAMAN V， LINTON J D. Building contingency planning for closed-loop supply chains with product recovery[J]. Journal of Operations Management， 2003，21(3):259-279.

[4]楊曉梅， 曾建潮. 基于主動調度的編碼方法及其在JSP中的應用[J]. 系統工程理論與實踐， 2004，24(6): 55-60.

[5]閆利軍， 李宗斌， 衛軍胡， 等. 一種新的混合優化算法及其在車間調度中的應用[J]. 自動化學報， 2008， 34(5): 604-608.

[6]王萬良， 吳啟迪， 宋毅. 基于求解作業車間調度問題的改進自適應遺傳算法[J]. 系統工程理論與實踐， 2004，24(2): 58-62.

[7]朱海平，邵新宇，張國軍. 不確定信息條件下的車間調度策略研究[J]. 計算機集成制造系統， 2006，12(10): 1637-1642.

[8]喬威， 王冰， 孫潔. 用遺傳算法求解一類不確定性作業車間調度問題[J]. 計算機集成制造系統， 2007，13(12): 2452-2455， 2468.

[9]張維存， 鄭丕諤， 吳曉丹. 蟻群遺傳算法求解能力約束的柔性作業車間調度問題[J]. 計算機集成制造系統， 2007，13(2): 333-337， 362.

[10]WU Chun-guo， XING X L， LEE H P， et al. Genetic algorithm application on the job shop scheduling problem[C]//Proc of the 3rd International Conference on Machine Learning and Cybernetics. Shanghai:[s.n.]， 2004: 2102-2106.

[11]王凌. 車間調度及其遺傳算法[M]. 北京: 清華大學出版社， 2003.