蒙祖強(qiáng)，周石泉，黃柏雄

(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，南寧 530004)

1 概述

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

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

本文指出范式轉(zhuǎn)化與約簡(jiǎn)計(jì)算之間的關(guān)系，導(dǎo)出范式轉(zhuǎn)化的并行模型，由此提出基于多線程技術(shù)的析取范式生成算法，并通過(guò)實(shí)驗(yàn)對(duì)本文算法進(jìn)行有效性驗(yàn)證。

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

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

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

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

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

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

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

表1 決策系統(tǒng)

先構(gòu)建其分辨矩陣，然后構(gòu)造其分辨函數(shù)，結(jié)果如下：

將以合取范式表示的分辨函數(shù)轉(zhuǎn)化為析取范式：

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

3 范式轉(zhuǎn)化的并行模型

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

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

對(duì)于合取范式，由于合取運(yùn)算滿足結(jié)合律和交換律，因此可以對(duì)析取項(xiàng)進(jìn)行任意的組合，然后對(duì)各組合同時(shí)進(jìn)行合取分配運(yùn)算，所得的結(jié)果都是一樣的。這為轉(zhuǎn)化的并行化操作提供了理論基礎(chǔ)。

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

圖1 析取范式轉(zhuǎn)化的并行模型

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

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

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

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

根據(jù)以上分析，并考慮到合取范式到析取范式的轉(zhuǎn)化是計(jì)算一個(gè)信息系統(tǒng)所有約簡(jiǎn)的關(guān)鍵，同時(shí)也是最耗時(shí)的過(guò)程，因此，下面只給出合取范式到析取范式轉(zhuǎn)化的算法，該算法是利用多線程技術(shù)來(lái)實(shí)現(xiàn)圖1所示的并行模型。

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

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

輸出 極小的析取范式

Step1 對(duì)F(S)充分運(yùn)用吸收律，將之轉(zhuǎn)化為極小的合取范式，結(jié)果保存在結(jié)構(gòu)體數(shù)組Q[]中。

Step2 將Q[]中的子析取范式分成ThreadN個(gè)組，然后啟動(dòng) ThreadN個(gè)線程，并行執(zhí)行對(duì)這 ThreadN個(gè)組的析取范式轉(zhuǎn)化 //ThreadN表示最大線程數(shù)。

Step3 對(duì)Q進(jìn)行縮小和排序，并進(jìn)行首尾組合。

Step5 當(dāng)Step4中的線程都執(zhí)行結(jié)束后，對(duì)當(dāng)前的Q進(jìn)行縮小和排序 //這時(shí)pQ約縮減為原來(lái)的1/2。

Step6 如果這時(shí) pQ等于 1，則轉(zhuǎn) Step7，否則對(duì) Q進(jìn)行首尾組合，然后轉(zhuǎn)Step4。

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

5 實(shí)驗(yàn)分析

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

表2 隨機(jī)生成的合取范式基本信息

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

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

表3 析取范式基本信息

在表3中，“A”的意義同表2；“D”代表產(chǎn)生的析取范式的長(zhǎng)度(合取項(xiàng)的個(gè)數(shù)，即約簡(jiǎn)的個(gè)數(shù))；“E”代表析取范式中合取項(xiàng)的平均長(zhǎng)度(即約簡(jiǎn)的平均長(zhǎng)度)。

圖2 算法運(yùn)行時(shí)間

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

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

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

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

[2]王國(guó)胤, 姚一豫, 于 洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào), 2009, 32(7): 1229-1246.

[3]徐章艷, 劉作鵬, 楊炳儒.一個(gè)復(fù)雜度為 max(O(|C||U|),O(|C|2|U/C|))的快速屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào), 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分明矩陣的快速約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué), 2005, 32(4): 42-44.

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

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

[9]李 斌, 李海玉, 孫延君.多核計(jì)算機(jī)上的并行計(jì)算[J].電腦編程技巧與維護(hù), 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.