蒙祖強，周石泉，黃柏雄

(廣西大學計算機與電子信息學院，南寧 530004)

1 概述

Rough集理論[1]經過30年的發(fā)展，在模式識別、圖像處理和數據挖掘等領域已發(fā)揮重要的作用[2]。屬性約簡是Rough集理論的核心內容之一，目前大量的研究工作主要集中在屬性約簡方面。屬性約簡主要有2種方法，一種是通過數據依賴性分析來計算屬性的重要性，然后由此計算滿足特定需求的約簡[3-4]，這是一種相對成熟的方法，其復雜度已經降低至線性復雜度；另一種方法是通過創(chuàng)建分辨矩陣來構建分辨函數，然后將分辨函數轉化為析取范式，從而求取所有的約簡[5]。后者的優(yōu)點是：其設計過程簡單明了，便于編程實現，且可以求取一個信息系統(tǒng)的所有約簡，因而被廣泛采用。但目前其指數級的時間復雜度[5]仍然未能得到根本性的降低，因而不適用于海量數據的約簡。這主要是因為將分辨函數從合取范式轉化到析取范式的過程中存在組合爆炸問題。目前，仍然沒有解決這種組合爆炸的有效方法，通常是從局部上采取一些改進措施，在一定程度上降低這種復雜度。例如，文獻[6]提出基于二分法技術的范式轉化方法，在一定程度上降低計算復雜度。文獻[7]給出了一種矩陣轉換的直接搜索方法，但在轉化過程中沒有充分地利用吸收律，導致產生大量的冗余項，影響了算法效率。文獻[8]提出一種模擬人工轉換的范式轉換算法，該算法的實現過程簡單明了，但它未能有效吸收二分法技術的設計思想來進一步降低其計算復雜度，其效率可進一步提高。

由于合取范式中的合取運算是滿足結合律和交換律的，因此可以對合取范式中的析取式進行分組，然后對各組并行進行析取范式轉化，接著進行分組、再進行并行析取范式轉化，直到獲得最終的析取范式。顯然，這是一種并行計算模式。同時由于當前多核計算機以其獨有的優(yōu)勢[9]，日益受到用戶的青睞，多核CPU電腦的出現已經十分普遍，而單線程的程序難以充分發(fā)揮多核CPU的功能。因此，在多核CPU環(huán)境下，基于上述的并行模式用多線程技術來加快析取范式的轉化就顯得十分有意義。

本文指出范式轉化與約簡計算之間的關系，導出范式轉化的并行模型，由此提出基于多線程技術的析取范式生成算法，并通過實驗對本文算法進行有效性驗證。

2 信息系統(tǒng)和分辨函數

在Rough集理論中，信息系統(tǒng)是數據的邏輯表示方式。一個信息系統(tǒng)(Information System, IS)可表示為四元組：IS=a∈A。其中，U是論域，表示非空有限對象(樣本)的集合；A是非空有限屬性的集合；Va是對象在屬性a∈A上所有可能取值的集合(即a的值域)；fa: U→Va是論域U到值Va上的映射，稱為信息函數(information function)。在不引起混淆的情況下，a∈A可簡寫為。如果屬性集A分為2個不相交的部分：條件屬性集C和決策屬性集D，即A=C∪D、C∩D=φ，則稱為決策系統(tǒng)(Decision System, DS)。不失一般性，本文假設D=acsigmw，即D僅有一個決策屬性組成。

對于一般的信息系統(tǒng)而言，分辨矩陣中的元素mij是表示能區(qū)分對象xi和xj的所有屬性的集合；對于決策系統(tǒng)而言，元素 mij也表示能區(qū)分對象 xi和xj的所有屬性的集合，但其前提是對象 xi和 xj的決策值不同，即fd(xi)≠fd(xi)，否則令mij=φ。具體地，假定U={x1, x2, …, xn}，對于給定的信息系統(tǒng)IS=，其分辨矩陣M(IS)=(mij)n×n定義如下：

對于給定的決策系統(tǒng)DS=，其分辨矩陣M(DS)=(mij)n×n定義如下：

其中，i,j∈{1,2,…,n}。

元素mij中的任一屬性都可以區(qū)分對象xi和xj，因此，這些屬性之間的關系是或的關系(析取)，而元素mij之間的關系是與的關系(合取)。這樣，可以構造如下的合取范式：F(S)=∧(∨mij), mij≠φ。其中，∨mij表示由 mij中的所有屬性構成的析取式，所有這樣的析取式的合取便是 F(S)。F(S)是一個合取范式，稱為F(S)為信息系統(tǒng)或決策系統(tǒng)的分辨函數，S表示IS或DS。當將F(S)從合取范式轉化為析取范式，便得到對應系統(tǒng)的所有約簡[5]。顯然，不管是信息系統(tǒng)還是決策系統(tǒng)，它們的分辨函數并無本質上的區(qū)別。

考慮如表1所示的決策系統(tǒng)DS=[10]，其中，U={x1, x2, …, x7}；C={a, b, c, d, e}；D={P}。

表1 決策系統(tǒng)

先構建其分辨矩陣，然后構造其分辨函數，結果如下：

將以合取范式表示的分辨函數轉化為析取范式：

由此可知，該決策系統(tǒng)的所有約簡包括：{a, b,e}，{a, d, e}，{b, c, d}，{b, c, e}。

3 范式轉化的并行模型

合取范式是由若干個簡單析取式通過合取聯(lián)結詞連接而成的邏輯公式。將這種簡單析取式簡稱為析取項；析取項中屬性的個數稱為析取項的長度；析取項的個數稱為合取范式的長度；如果對一個合取范式已經充分應用了吸收律，則該合取范式是極小的合取范式。對于析取范式，也可以平行地定義相應的概念：合取項，合取項的長度，析取范式的長度，極小的析取范式。

由此可見，程序在掃描數據集時可直接生成以合取范式表示的分辨函數，而不需要生成分辨矩陣。問題的關鍵是，如何將以合取范式表示的分辨函數高效地轉化為析取范式。這種轉化過程遇到最大的困難就是組合爆炸問題。但是，在創(chuàng)建分辨函數和析取范式轉化時充分應用吸收律，可以大幅度降低析取項和合取項的數量。當然，吸收律的應用并不能從根本上解決組合爆炸問題，而只能從局部上提高算法的效率。

對于合取范式，由于合取運算滿足結合律和交換律，因此可以對析取項進行任意的組合，然后對各組合同時進行合取分配運算，所得的結果都是一樣的。這為轉化的并行化操作提供了理論基礎。

一般地，假設在掃描數據集后得到的極小合取范式具有形式：I1∧I2∧…∧In。然后按照結合律和交換律，對這n個析取項進行分組，假設得到m個組，并對各組進行并行運算，之后各組都是子析取范式。為方便討論起見，假設 m=2k，即 m為 2的k次冪，k為一正整數。這樣將該合取范式并行轉化為極小析取范式的計算模型可以用圖1表示。

圖1 析取范式轉化的并行模型

在圖1中，各層上的每個結點代表一個邏輯運算單元及其運算結果(子析取范式)。除了第 0層上的結點表示對最初的各分組進行運算及其結果以外，其他層上的結點都是表示對其2個孩子結點的運算及其結果。為了有效實施同步控制，約定：同一層上的結點可以并行執(zhí)行運算，且當前層上的結點都運算完后下一層上的結點才能開始進行運算。這樣同一層上各結點的負載平衡就顯得特別重要。通過計算2個子析取范式的長度的乘積來估計結點的負載程度，從而決定結點的組合。也就是說，結點的組合不是基于結點相鄰的原則，而是根據負載平衡的原則進行。

4 基于多線程技術的析取范式生成算法

并行模型的實現需要并行環(huán)境。但如果沒有真正的并行環(huán)境，可以利用現在電腦普遍提供的多核CPU環(huán)境來實現該并行模型。Windows操作系統(tǒng)雖然能夠自動在多核上分配計算任務，但這種分配操作主要是基于線程的，線程是CPU的調度單位。因此，需要將計算任務分為若干個線程的計算，這樣才能充分利用多核CPU提供的資源，實現一定程度上的并行計算。

基于上述考慮，在圖1的并行模型中，每個結點的計算任務就可以用一個線程來完成，即一個結點對應一個線程，一旦計算結束就銷毀線程。線程之間沒有直接通信，但所有線程都共享一個結構體數組，該結構體數組存放著各個時期計算形成的子析取范式所在內存塊的首地址和該子析取范式的長度。多個線程可同時訪問該數組的不同元素。假設該結構體數組為 Q[]，Q[i].addr表示當前第 i+1個子析取范式所在內存塊的首地址，Q[i].size表示當前第 i+1個子析取范式的長度。在一個線程執(zhí)行對第i+1個子析取范式和第 j+1個子析取范式的邏輯分配和吸收運算后，會得到一個新的子析取范式，將它所在內存塊的首地址和它的長度分別存放到Q[i].addr和 Q[i].size中，而 Q[j].addr和 Q[j].size分別置為 NULL和 0。當并行模型中當前層上的結點對應的線程都執(zhí)行結束以后，刪除 Q[i].addr為NULL的結構體并按照Q[i].size的大小對Q[]中的元素進行升序排列，這2個操作分別稱為Q的縮小和排序。在對當前的Q進行縮小和排序后，假設其長度 pQ；然后對當前的子析取范式進行下列的組合(稱為首尾組合)：(Q[0].addr, Q[pQ–1].addr)，(Q[1].addr,Q[pQ–2].addr)，(Q[2].addr, Q[pQ–3].addr)，…，(Q[p Q/2–1].addr, Q[pQ–p Q/2].addr)。這樣的組合是出于實現負載平衡的需要。當然，這不是最佳的負載平衡方案。但如果過多地追求負載平衡，可能會大量增加計算時間。因此，暫且采用這種相對簡單的負載平衡解決方法。

根據以上分析，并考慮到合取范式到析取范式的轉化是計算一個信息系統(tǒng)所有約簡的關鍵，同時也是最耗時的過程，因此，下面只給出合取范式到析取范式轉化的算法，該算法是利用多線程技術來實現圖1所示的并行模型。

基于多線程技術的析取范式生成算法如下：

輸入 以合取范式表示的分辨函數F(S)

輸出 極小的析取范式

Step1 對F(S)充分運用吸收律，將之轉化為極小的合取范式，結果保存在結構體數組Q[]中。

Step2 將Q[]中的子析取范式分成ThreadN個組，然后啟動 ThreadN個線程，并行執(zhí)行對這 ThreadN個組的析取范式轉化 //ThreadN表示最大線程數。

Step3 對Q進行縮小和排序，并進行首尾組合。

Step5 當Step4中的線程都執(zhí)行結束后，對當前的Q進行縮小和排序 //這時pQ約縮減為原來的1/2。

Step6 如果這時 pQ等于 1，則轉 Step7，否則對 Q進行首尾組合，然后轉Step4。

Step7 返回Q[0].addr所表示的析取范式。

5 實驗分析

為驗證基于多線程技術的析取范式生成算法(記為算法1)的性能，做了相關的實驗對比和分析。首先，將算法1中的線程去掉，改用函數來代替線程完成相應的功能。這樣，算法 1的循環(huán)部分(Step4～Step6)就變?yōu)榇袌?zhí)行，由此修改得到的算法記為算法2。在實驗中，一共隨機生成11條不同的合取范式，合取范式的長度從 150～250(間隔為10，如表2所示)，可能出現的屬性一共有20個。

表2 隨機生成的合取范式基本信息

在表2中，“A”代表合取范式的長度(析取項的個數)；“B”代表合取范式中屬性出現的總次數；“C”代表合取范式中析取項的平均長度(各析取項平均包含的屬性個數)，即C=B/A。

實驗是在 Rentium Dual-Core CPU(雙核 CPU)、主頻2.7 GHz、2 GB內存的機器上完成，操作系統(tǒng)是Windows XP。算法1中的參數ThreadN被設置為100。算法1和算法2執(zhí)行后分別產生相同的結果，表3列出了這些析取范式的基本信息。但它們的運行時間的變化趨勢卻有明顯差別，如圖2所示。

表3 析取范式基本信息

在表3中，“A”的意義同表2；“D”代表產生的析取范式的長度(合取項的個數，即約簡的個數)；“E”代表析取范式中合取項的平均長度(即約簡的平均長度)。

圖2 算法運行時間

從圖2可以看出，當合取范式長度比較小時，2種算法的運行時間的差別并不大，但隨著合取范式長度的增加，這種差別就越來越明顯。究其原因，認為當合取范式的長度增加時，就有更多的線程參與運算，從而提高算法1的執(zhí)行效率。這說明當合取范式中析取項的個數比較大時，算法1在執(zhí)行效率上會明顯優(yōu)于算法2，這時應該選擇算法1。對于實際決策系統(tǒng)來說，其分辨函數的長度一般都比較大，而且算法1只利用了當前電腦普遍配置的多核CPU環(huán)境，因此，算法1在工程應用中具有明顯的實際意義。

6 結束語

基于Skowron矩陣計算信息系統(tǒng)所有約簡是一個 NP難問題。本文雖然不能從根本上解決這個問題，但利用當前電腦普遍提供的多核CPU環(huán)境和多線程技術，設計了基于多線程技術的析取范式生成算法，可以在局部上進一步提高析取范式的轉化效率，這在實驗中得到了有效的驗證。由于本文算法只需在當前普遍使用的多核CPU電腦上運行，因此具有一定的推廣價值和應用前景。

[1]Pawlak Z.Rough Set[J].International Journal of Computer and Information Sciences, 1982, 11(5): 341- 356.

[2]王國胤, 姚一豫, 于 洪.粗糙集理論與應用研究綜述[J].計算機學報, 2009, 32(7): 1229-1246.

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

[4]Meng Zhuqiang, Shi Zhongzhi.A Fast Approach to Attribute Reduction in Incomplete Decision Systems with Tolerance Relation-based Rough Sets[J].Information Sciences, 2009, 179(6): 2774-2793.

[5]Skowron A, Rauszer C.The Discernibility Matrices and Functions in Information Systems[M]//Slowinski R.Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht,Netherlands: Kluwer Academic, 1992: 331-362.

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

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

[8]張德棟, 李仁璞, 趙永升.一種高效的分辨函數范式轉換算法[J].計算機應用研究, 2010, 27(3): 879-882.

[9]李 斌, 李海玉, 孫延君.多核計算機上的并行計算[J].電腦編程技巧與維護, 2011, (18): 57-59.

[10]Zhao Kai, Wang Jue.A Reduction Algorithm Meeting Users’ Requirements[J].Journal of Computer Science and Technology, 2002, 17(5): 578-593.