基于模糊形式背景的概念格屬性約簡算法研究

王璨，于茜，林波，寧濤

（1.大連科技學(xué)院信息科學(xué)學(xué)院，遼寧大連116052；2.大連交通大學(xué)軟件學(xué)院，遼寧大連116045）

基于模糊形式背景的概念格屬性約簡算法研究

王璨1，于茜1，林波1，寧濤2

（1.大連科技學(xué)院信息科學(xué)學(xué)院，遼寧大連116052；2.大連交通大學(xué)軟件學(xué)院，遼寧大連116045）

隨著形式背景中數(shù)據(jù)的增多，概念數(shù)量會急劇增加。概念格的屬性約簡在保持形式背景所有概念的外延集不變的前提下，尋找極小屬性子集，使概念格表示的知識變得更簡單，也使得決策問題得以簡化。本文主要研究了模糊形式背景的屬性約簡，通過設(shè)定閾值將模糊形式背景轉(zhuǎn)換為經(jīng)典形式背景，引入可約元及屬性約簡集的構(gòu)成，提出了屬性約簡算法，討論了算法的時間復(fù)雜度。通過實(shí)例分析，對于屬性個數(shù)小于對象個數(shù)的形式背景，文中提出的算法更有效。

概念格；屬性約簡；可約元；模糊形式背景；閾值

形式概念分析［1_2］作為一種數(shù)據(jù)處理的有效工具，已被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域.隨著形式背景中數(shù)據(jù)的增多，基于模糊形式背景的概念數(shù)量會急劇增加。因此計算信息系統(tǒng)的核心并建立有效的屬性約簡算法成為研究的熱點(diǎn).目前，主要的研究方向有兩個：基于粗糙集的知識約簡［3_6］和概念格的屬性約簡［7_9］。

概念格屬性約簡理論［10_12］是在保持形式背景中所有概念的外延集不變的前提下，尋找極小屬性子集，該屬性子集依然能夠完全確定形式背景上的原有概念，并保持它們之間原有的層次結(jié)構(gòu)關(guān)系。李進(jìn)金等人［13］，通過引入交式可約元的概念，提出了一種形式背景屬性約簡的新方法；張文修等人［14］給出了概念格約簡的判定定理，引入了形式背景的可辨識屬性矩陣。王霞等人［15］主要研究了基于不可約元的概念格的屬性約簡以及屬性約簡集的構(gòu)造，提出了一種概念格的屬性約簡方法，都具有很高的參考價值。

本文分為5部分：第一部分介紹了概念格的相關(guān)理論；第二部分引入了可約元及屬性約簡集的判定定理；第三部分提出了屬性約簡算法及核心程序并分析了算法的時間復(fù)雜度；第四部分分析了實(shí)驗(yàn)結(jié)果，證明本文提出的算法更有效；最后，得出了結(jié)論并討論了開放性問題。

1　概念格理論

模糊形式背景被記為一個三元組（X，Y，I），其中X是有限的對象集，Y是有限的屬性集，I?X×Y是一個模糊關(guān)系，I（x，y）∈［0，1］。

例如：I（x，y）=0.9，表示對象x∈Y具有屬性y∈Y的程度是0.9。令A(yù)?X，B?Y，A*和B*的定義如下：

A*是對象集A共同具有的屬性集，B*是共同具有屬性集B的對象集?！碅，B〉是一個概念當(dāng)且僅當(dāng)A=B*且B=A*。

偏序關(guān)系（≤）可以描述概念間的等級結(jié)構(gòu)。〈A1，B1〉和〈A2，B2〉是形式背景（X，Y，I）下的兩個概念，〈A1，B1〉≤〈A2，B2〉當(dāng)且僅當(dāng)A1?A2或B1?B2。

概念格［16_17］是偏序集，概念格中的每個元素?fù)碛凶钚∩辖绾妥畲笙陆??；谛问奖尘埃╔，Y，I）的概念格記為：L（I）=（（X，Y，I），≤）。

2　屬性約簡與屬性特征

定義1［13］：對于概念格L（I）=（X，Y，I），≤），?〈A，B〉∈L（I），?〈C，D〉∈L（I1），使A=C，則稱L（I1）細(xì)于L（I）。

若L（I1）細(xì)于L（I）且L（I）細(xì)于L（I1），則L（I1）與L（I）同構(gòu)，記為L（I1）?L（I）。

定義2：令（X，Y，I）為形式背景，若存在屬性集E?Y使得L（IE）?L（I）。則稱E為形式背景的協(xié)調(diào)集，進(jìn)一步地?e∈E，滿足L（IE_e）與L（I）不同構(gòu)，則稱E是形式背景的約簡，所有的約簡集記為Ei。

定義3：對于b∈Y，若?E?Y，b?E，使b*=∩e*（e∈E），則稱b為可約元。

形式背景中的屬性可以分為三類：

（1）核心屬性：C∩Ei，其屬于每個約簡。

（2）相對必要屬性：J=∪Ei_∩Ei，其屬于某些約簡但不屬于每個約簡。

（3）不必要屬性：K=Y_∪Ei，其不屬于任一約簡.

定義4［13］.設(shè)（X，Y，I）為形式背景，等價關(guān)系R的定義如下：

基于等價關(guān)系R可以得到Y(jié)的一個劃分，Y/R=｛［a］R

由定義4可知，去掉等價類為單元素集的屬性a后，a*可能會消失，若a*消失，則a為核心屬性，否則若a*可以被保留，則a為不必要屬性。所以等價類為單元素集的屬性為核心屬性或不必要屬性.等價類不是單元素集的屬性可能是相對必要屬性等價類或不必要屬性。C，J，K構(gòu)成Y的一個劃分。

引理1：在等價關(guān)系R下，相對必要屬性的劃分為J/R=｛Ji為該形式背景下的約簡集，則

定理1：C和J為形式背景下的核心屬性集和相對必要屬性集，?E?Y，E是形式背景的約簡集當(dāng)且僅當(dāng)

證明詳見文獻(xiàn)［15］。

3　屬性約簡算法

3.1屬性約簡算法

現(xiàn)根據(jù)前面的論述，給出屬性約簡算法：

1）對于任意一個模糊形式背景，設(shè)定閾值α，將模糊形式背景轉(zhuǎn)換為經(jīng)典形式背景；

2）定義數(shù)組k［Y］，存放各屬性非零元素的個數(shù)，求a*，存入指針數(shù)組*p［Y］；

3）將等價類為單元素集的屬性下標(biāo)存入數(shù)組cd［Y］，如果a*=b*，則將a，b的下標(biāo)存入指針數(shù)組*r［Y］，最后如果r［i］非空，i存入數(shù)組cd［Y］；

4）循環(huán)比較k［i］＜k［j］的兩列，如果j*?i*，將j存入G（i），i= 1，…，Y；

5）求可約元，如果i*=G*（i），則返回可約元的下標(biāo)i；

6）輸出約簡集，首先輸出數(shù)組cd［Y］，其中的元素或?yàn)楹诵膶傩曰驗(yàn)榭杉s元，其次依次輸出各相對必要屬性等價類r［i］。

3.2核心程序

算法核心程序如下：

4　實(shí)例分析

例1模糊形式背景如表1所示，可以將閾值設(shè)置成0.7，0.5，0.3等，將模糊形式背景中I（x，y）≥α的值轉(zhuǎn)換為1，可以得到不同的經(jīng)典形式背景，相應(yīng)也會得到不同的概念格，但都會導(dǎo)致一定程度的信息損失，詳見文獻(xiàn)［16］。為了最大程度地減少信息的損失，本文將閾值α設(shè)為0，將I（x，y）＞0的值轉(zhuǎn)換為1，轉(zhuǎn)換后的形式背景見表2，生成的概念格如圖1所示。

表1　模糊形式背景

表2　轉(zhuǎn)換后的形式背景

表3　基于形式背景的概念

圖1　概念格

a*=b*=｛2，3｝，c*=｛3，5｝，d*=｛1，5｝，e*=｛1，4｝，f*=｛3｝.

G（f）=｛a，c｝，G*（f）=a*∩c*=f*，所以f為不必要屬性；

G（e）=G（d）=G（c）=G（a）=?，所以核心屬性為c，d，e，相對必要屬性為a，b。

因此可以得到兩個約簡集：E1=｛a，c，d，e｝，E2=｛b，c，d，e｝.

表4　實(shí)驗(yàn)結(jié)果

5　結(jié)論

本文首先通過設(shè)定閾值將模糊形式背景轉(zhuǎn)換為經(jīng)典形式背景，引入可約元的定義及約簡集的構(gòu)成，提出了屬性約簡算法，討論了算法的時間復(fù)雜度，借助一維數(shù)組、二維數(shù)組、指針數(shù)組等存儲結(jié)構(gòu)，巧妙地設(shè)置循環(huán)控制條件，算法的時間復(fù)雜度雖然空間復(fù)雜度提高了，但算法的執(zhí)行效率也得到了極大地提高.最后通過實(shí)例分析，對于屬性個數(shù)小于對象個數(shù)的形式背景，本文提出的算法更有效。

本文還討論了輸出各相對必要屬性組合的復(fù)雜度，但只得出了復(fù)雜度的取值范圍。開放性問題如設(shè)計更有效的屬性輸出算法及更合理的閾值設(shè)置方法等。

區(qū)間值信息系統(tǒng)和集值信息系統(tǒng)的屬性約簡也是本文進(jìn)一步的研究方向。

［1］宋笑雪，張文修.形式概念分析與集值信息系統(tǒng)［J］.計算機(jī)科學(xué)，2007，34（11）：129_131.

［2］LI Li_feng，ZHANG Jian_ke.Attribute reduction in fuzzy concept 1attices based on the T imp1ication［J］.Know1edge_ Based Systems，2010（23）：497_503.

［3］張文修，仇國芳.基于粗糙集的不確定決策［M］.北京：清華大學(xué)出版社，2005：75_100.

［4］寧濤，郭晨，陳榮，等.一種動態(tài)車輛路徑問題解決策略仿真研究［J］.系統(tǒng)仿真學(xué)報，2015（12）：74_79.

［5］周秀秀，李建卓.基于粗糙集理論的面向?qū)傩愿拍罡駝討B(tài)壓縮［J］.計算機(jī)科學(xué)，2013，40（11）：137_139.

［6］張文修，仇國芳，吳偉志.粗糙集屬性約簡的一般理論［J］.中國科學(xué)E輯：信息科學(xué)，2005，35（12）：1304_1313.

［7］Tao NiNG，Chen Guo，Rong Chen.A Nove1 Method for Dynamic Vehic1e Routing Prob1em［J］.The Open Cybernetics& systemic journa1，2015，9（15）：1_5.

［8］Yuan Bo，Ying Baosheng，Xie Hao.Job Shop Schedu1ing Based on Genetic A1gorithm under Uncertain Condition［J］. Modern Manufacturing Engineering，2012（10）：52_56.

［9］寧濤.混合量子算法在車輛路徑問題中應(yīng)用的研究［D］.大連：大連海事大學(xué)，2013.

［10］寧濤，陳榮，郭晨，等.一種基于雙鏈量子編碼的動態(tài)車輛路徑問題解決策略［J］.運(yùn)籌學(xué)學(xué)報，2015，19（2）：72_83.

［11］WANGCan，YUXi，XUChun_ming，eta1.Researchon Computing the Covers of a Given Concept［C］//Xipeng Xu，App1ied Mechanics and Materia1s，Switzer1and：Ran Chen，2013：496_500.

［12］Gong Xi.Construction，reduction of concept 1attice and the app1ication of FCA［D］.2008，25_34.

［13］李進(jìn)金，張燕蘭，吳偉志等.形式背景與協(xié)調(diào)決策形式背景屬性約簡與概念格生成［J］.計算機(jī)學(xué)報，2014，37（8）：1768_1772.

［14］張文修，魏玲，祁建軍.概念格的屬性約簡理論與方法［J］.中國科學(xué)E輯：信息科學(xué)，2005，35（6）：628_639.

［15］王霞，張文修.概念格的屬性約簡與屬性特征［J］.計算機(jī)工程與應(yīng)用，2008，44（12）：1_4.

［16］WANG Can，YU Xi.Research on se1ecting a sub1attice based on L_contex［C］//App1ied Mechanics and Materia1s，2013，（2）：543_547.

［17］WANG Can，YU Xi.Research on Attribute Reduction Based on L_context［C］//2014：450_455.

Research on algorlthm of attrlbute reductlon of concePt lattlce based on L-context

WANG Can1，YU Xi1，LIN Bo1，NING Tao2
（1.Institute of Information Science，Dalian Institute of Science and Technology，Dalian 116052，China；2.Institute of Software，Dalian Jiaotong University，Dalian 116045，China）

As the size of data tab1e grows，the concepts generated become 1arger in number.Making sure the set of extent remaining unchanged，the purpose of attribute reduction of concept 1attice is to find out minimum subsets of attributes and make know1edge presented by concept 1attice simp1er，decision prob1em simp1ified as we11.This paper main1y studies on attribute reduction based on L_context，converts L_context to c1assica1 context by setting thresho1d，introduces reducib1e e1ement and constitution of attribute reduction set，proposes an a1gorithm of attribute reduction and discusses the time comp1exity.Experimenta1 resu1ts show that a1gorithm proposed in this paper is more effective with attributes 1ess than objects.

concept 1attticej attribute reductionj reducib1e e1ementj L_contextj thresho1d

TN919.5

A

1674_6236（2016）10_0017_04

2016_01_09稿件編號：201601058

國家自然科學(xué)基金（61173034；61272171）；遼寧省教育廳一般項(xiàng)目（L2014183；L2015105）；大連科技學(xué)院科學(xué)研究一般項(xiàng)目（KYZ1416）

王璨（1985—），女，遼寧大連人，碩士，講師。研究方向：管理優(yōu)化與計算機(jī)推理。