黃治國(guó)，張?zhí)煳?/p>

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

基于極大團(tuán)的不完備系統(tǒng)規(guī)則獲取方法

黃治國(guó)，張?zhí)煳?/p>

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

針對(duì)不完備決策系統(tǒng)的規(guī)則提取問(wèn)題，提出一種基于極大團(tuán)的不完備系統(tǒng)規(guī)則獲取方法。引入圖中極大團(tuán)概念定義相容塊構(gòu)造范式，將其等價(jià)轉(zhuǎn)換為極小析取范式后得到不完備系統(tǒng)全體極大相容塊，收集每一相容塊最全描述即可生成極大相容塊最全描述系統(tǒng)，進(jìn)而為最全描述系統(tǒng)中的每一對(duì)象構(gòu)造決策分辨范式得到與該對(duì)象對(duì)應(yīng)的全體可信關(guān)聯(lián)規(guī)則。該方法具有2個(gè)特點(diǎn)：針對(duì)系統(tǒng)中每一基本信息粒自動(dòng)生成基準(zhǔn)置信參數(shù)，避免了預(yù)設(shè)固定參數(shù)而遺漏置信度小于此參數(shù)的部分有用規(guī)則；將決策分辨范式等價(jià)變換為其極小析取范式，避免了采用特定順序選擇屬性而遺漏部分有用規(guī)則。將該算法應(yīng)用于某保險(xiǎn)公司私家車客戶車險(xiǎn)數(shù)據(jù)和UCI不完備數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析說(shuō)明了該算法的分類預(yù)測(cè)性能。

極大團(tuán)；極大相容塊；范式轉(zhuǎn)換；規(guī)則挖掘

0 引 言

粗糙集理論在知識(shí)發(fā)現(xiàn)與決策支持領(lǐng)域得到許多成功應(yīng)用[1-2]，但經(jīng)典粗糙集理論建立在嚴(yán)格的等價(jià)關(guān)系基礎(chǔ)之上[3]，而實(shí)際應(yīng)用中因數(shù)據(jù)測(cè)量誤差及獲取限制等諸多原因使得現(xiàn)實(shí)數(shù)據(jù)集常存在部分對(duì)象屬性值缺失情形[4]。經(jīng)典粗糙集模型難以體現(xiàn)不完備系統(tǒng)數(shù)據(jù)特征，且對(duì)噪音數(shù)據(jù)處理過(guò)于敏感，為使粗糙集理論能夠適應(yīng)不完備信息系統(tǒng)處理，必須對(duì)經(jīng)典粗糙集模型加以拓展[5]，因此，近年來(lái)面向不完備信息系統(tǒng)的模型拓展及其應(yīng)用逐漸成為粗糙集領(lǐng)域的一個(gè)研究熱點(diǎn)。

文獻(xiàn)[6]針對(duì)不完備系統(tǒng)首次設(shè)計(jì)容差關(guān)系拓展處理模型，并以該擴(kuò)充模型為基礎(chǔ)定義了極大相容塊概念。極大相容塊是不完備系統(tǒng)的基本信息粒單元，對(duì)于不完備系統(tǒng)規(guī)則挖掘及決策推理具有重要意義[7]。文獻(xiàn)[8]從極大相容塊出發(fā)探討了不完備系統(tǒng)的數(shù)據(jù)約簡(jiǎn)方法，但并未給出具體的處理流程。文獻(xiàn)[9]依據(jù)條件極大隸屬?zèng)Q策處理噪音數(shù)據(jù)，挖掘全體潛在有用模式，但該方法僅考慮了決策系統(tǒng)的完備情形。因此，針對(duì)不完備系統(tǒng)研究有效的規(guī)則提取方法,仍是目前不完備系統(tǒng)應(yīng)用的重要問(wèn)題。

MLEM2(modified learning from examples module, version 2)算法能夠從不完備決策系統(tǒng)中挖掘規(guī)則，該算法是現(xiàn)今較典型的不完備系統(tǒng)規(guī)則獲取算法[10]。文獻(xiàn)[11]引入屬性序概念，設(shè)計(jì)了一種基于屬性序的不完備系統(tǒng)規(guī)則獲取算法，并與MLEM2算法作了實(shí)驗(yàn)結(jié)果對(duì)比分析。

本文基于容差關(guān)系與極大團(tuán)概念定義相容塊構(gòu)造范式計(jì)算不完備系統(tǒng)的全體極大相容塊，將其轉(zhuǎn)化為最全描述得到極大相容塊最全描述系統(tǒng)，進(jìn)而在此基礎(chǔ)上設(shè)計(jì)了一種面向不完備系統(tǒng)的規(guī)則獲取算法，將該算法應(yīng)用于某保險(xiǎn)公司私家車客戶車險(xiǎn)不完備數(shù)據(jù)集，取得了較穩(wěn)定的分類預(yù)測(cè)性能。進(jìn)一步將本文算法應(yīng)用于UCI數(shù)據(jù)集，與文獻(xiàn)[10-11]進(jìn)行比較，實(shí)驗(yàn)結(jié)果與分析說(shuō)明了該算法的分類預(yù)測(cè)性能。

1 不完備系統(tǒng)與極大相容塊

給定決策系統(tǒng)DS=，其中，U={x1,…,xn}為非空有限論域；A=C∪D為非空有限屬性集，C和D分別為條件屬性和決策屬性；V=∪a∈AVa，Va為屬性a的值域；f:U×A→V為映射函數(shù)使得f(xi,a)∈Va(xi∈U,a∈A)。若系統(tǒng)中存在某些對(duì)象的屬性值缺失情形(通常缺失值用“*”表示)，則稱其為不完備決策系統(tǒng)(incomplete decision system, IDS)。

將IDS中的缺失值“*”看作值域V中特定取值，可計(jì)算得到論域U關(guān)于條件屬性集C導(dǎo)致的條件等價(jià)類商集U/C={X1,…,X|U/C|}和U關(guān)于決策屬性集D導(dǎo)致的決策等價(jià)類商集U/D={Y1,…,Y|U/D|}

定義1 ?Xi∈U/C(1≤i≤|U/C|)的決策向量定義為

(1)

決策向量表現(xiàn)為條件等價(jià)類關(guān)于決策等價(jià)類的條件概率分布，各概率分布之和為1。

定義2[6]給定不完備決策系統(tǒng)IDS=，屬性集R(R?A)上的容差關(guān)系定義為TOR(R)={∈U×U: ?a∈R→f(u,a)=f(v,a)∨f(u,a)=*∨f(v,a)=*}。

容差關(guān)系TOR(R)是論域U上的二元關(guān)系，該關(guān)系滿足自反性、對(duì)稱性，但不滿足傳遞性。

定義3 給定不完備決策系統(tǒng)IDS=，?x∈U的容差塊T(x)定義為T(x)={u:(u∈U)∧(?a∈C→f(u,a)=f(x,a)∨f(u,a)=*)}；若?T′(x)?T(x)使得?u,v∈T′(x)→u∈T(v)∧v∈T(u)成立，且?T″(x)?T′(x)使得T″(x)滿足此特征，則稱T′(x)為IDS的極大相容塊。

2 基于極大團(tuán)的不完備系統(tǒng)規(guī)則獲取方法

文獻(xiàn)[12]研究圖中有關(guān)極大團(tuán)特性，給出了轉(zhuǎn)換分辨函數(shù)表達(dá)式約束求取圖中極大團(tuán)的有效方法。決策系統(tǒng)中對(duì)象與圖中頂點(diǎn)一一對(duì)應(yīng)，而系統(tǒng)中極大相容塊與圖中極大團(tuán)一一映射，故可借鑒文獻(xiàn)[12]中方法求取系統(tǒng)的全體極大相容塊。同時(shí)，在決策系統(tǒng)中，各條件等價(jià)類中對(duì)象間不可分辨，因此針對(duì)不完備決策系統(tǒng)生成簡(jiǎn)化不完備決策系統(tǒng)，然后在此基礎(chǔ)上計(jì)算極大相容塊，可有效減少對(duì)象間比較次數(shù)，從而降低時(shí)空開(kāi)銷。

定義4 IDS的簡(jiǎn)化不完備決策系統(tǒng)定義為sim(IDS)=，其中，V′=∪a∈C∪D′Va，f′為信息函數(shù)使得f′(Xi,a)∈Va(Xi∈U/C,a∈C)，D′為決策向量屬性且f′(Xi,D′)=DV(Xi)。

定義5 給定簡(jiǎn)化不完備決策系統(tǒng)sim(IDS)，?Xi∈U/C的容差塊T(Xi)定義為T(Xi)={u:(u∈U/C)∧(?a∈C→f′(u,a)=f′(Xi,a)∨f′(u,a)=*)}；其極大相容塊分辨范式定義為DF(Xi)=∧{(Xi∨Xj):Xi,Xj∈T(Xi)∧(Xi?T(Xj) ∨Xj?T(Xi))}。

考慮簡(jiǎn)化不完備決策系統(tǒng)sim(IDS)中的每一對(duì)象Xi∈U/C的極大相容塊分辨范式DF(Xi)的情形：若DF(Xi)=?，則其容差塊T(Xi)即為一極大相容塊；否則，將極大相容塊分辨范式DF(Xi)等價(jià)轉(zhuǎn)換為其極小析取范式DF′(Xi)=(∧Q1)∨…∨(∧Qh)，其中，Qj?T(Xi)，若Qj={Xk,Xm,Xl}則∧Qj=Xk∧Xm∧Xl，包含于T(Xi)的極大相容塊即為MCB(Xi)={{T(Xi)-Q1},…,{T(Xi)-Qh}}，決策系統(tǒng)的全體極大相容塊即為MCB(sim(IDS))=∪{MCB(Xi):Xi∈U/C}。

在獲取決策系統(tǒng)全體極大相容塊后，將每一極大相容塊轉(zhuǎn)換為其最全描述(即針對(duì)每一“*”取值屬性判斷該塊中是否存在其他對(duì)象在該屬性有取值，若存在則以該取值替代，否則仍取值為“*”)，收集每一極大相容塊最全描述即得到極大相容塊最全描述決策系統(tǒng)DES(MCB(sim(IDS)))。

定義6 給定不完備決策系統(tǒng)IDS=及其極大相容塊最全描述決策系統(tǒng)DES(MCB(sim(IDS)))，?z∈DES(MCB(sim(IDS)))關(guān)于原不完備決策系統(tǒng)IDS的容差塊CB(z)定義為CB(z)={y:y∈U∧(?a∈C→f(y,a)=f′(z,a)∨f(y,a)=*)}，其決策向量定義為

(2)

對(duì)?z∈DES(MCB(sim(IDS)))計(jì)算其最大隸屬?zèng)Q策M(jìn)D(z)={Di:f′(z,D′)[i]=max(f′(z,D′))}，其中，f′(z,D′)[i]為極大相容塊z的決策向量的第i維；若z的最大隸屬?zèng)Q策僅有第i維一個(gè)，則生成決策分辨范式DF(z)=∧{(∨R):(R?C)∧(z′∈DES(MCB(sim(IDS))))∧(f′(z,D′)[i]>f′(z′,D′)[i])∧(?a∈R→(f′(z,a)≠*∧f′(z′,a)≠*∧f′(z,a)≠f′(z′,a)))}，轉(zhuǎn)換決策分辨范式DF(z)為等價(jià)的極小析取范式DF′(z)=(∧R1)∨…∨(∧Rk)，Rj?C(1≤j≤k)，針對(duì)每一Rj生成其對(duì)應(yīng)規(guī)則RULj=f′(z,Rj)→max(f′(z,D′)；若z的最大隸屬?zèng)Q策包含多個(gè)，則針對(duì)每一最大隸屬?zèng)Q策按上述流程得到對(duì)應(yīng)規(guī)則。運(yùn)用此思想生成不完備決策系統(tǒng)全體規(guī)則的算法描述見(jiàn)算法1。

算法1 基于極大團(tuán)的不完備系統(tǒng)規(guī)則獲取方法

輸入：不完備決策系統(tǒng)IDS=

輸出：關(guān)聯(lián)規(guī)則集RUL

步驟1 決策系統(tǒng)極大相容塊集置空MCB=?，規(guī)則集置空RUL=?；

步驟2 將缺失值“*”看作值域中特定取值，針對(duì)IDS生成其簡(jiǎn)化不完備決策系統(tǒng)sim(IDS)=；

步驟3 對(duì)?u∈sim(IDS)計(jì)算T(u)；

步驟4 對(duì)?u∈sim(IDS)生成其極大相容塊分辨范式DF(u)；

步驟5 對(duì)?u∈sim(IDS)將DF(u)轉(zhuǎn)換為其等價(jià)極小析取范式DF′(u)=(∧Q1)∨…∨(∧Qh)收集與u相關(guān)的極大相容塊，即MCB=MCB∪{{T(Xi)-Q1},…,{T(Xi)-Qh}}；

步驟6 對(duì)每一極大相容塊生成其最全描述，收集每一極大相容塊最全描述即得到極大相容塊最全描述決策系統(tǒng)DES(MCB(sim(IDS)))；

步驟7 對(duì)?z∈DES(MCB(sim(IDS)))計(jì)算其關(guān)于原不完備決策系統(tǒng)IDS的容差塊CB(z)={y:y∈U∧(?a∈C→f(y,a)=f′(z,a)∨f(y,a)=*)}，其決策向量DV(z)=<|CB(z)∩Y1|/|CB(z)|,… ,|CB(z)∩Y|U/D||/|CB(z)|>；

步驟8 對(duì)?z∈DES(MCB(sim(IDS)))生成其關(guān)聯(lián)規(guī)則

1)對(duì)?z∈DES(MCB(sim(IDS)))計(jì)算其最大決策M(jìn)D(z)={Di:f′(z,D′)[i]=max(f′(z,D′))}；

2)對(duì)?z∈DES(MCB(sim(IDS)))生成決策分辨范式DF(z)=∧{(∨R):(R?C)∧(z′∈DES(MCB(sim(IDS))))∧(f′(z,D′)[i]>f′(z′,D′)[i])∧(?a∈R→(f′(z,a)≠*∧f′(z′,a)≠*∧f′(z,a)≠f′(z′,a)))}；

3)將DF(z)轉(zhuǎn)換為等價(jià)的極小析取范式DF′(z)=(∧R1)∨…∨(∧Rk)；

4)針對(duì)每一Rj生成其對(duì)應(yīng)規(guī)則RULj=f′(z,Rj)→max(f′(z,D′)，并入關(guān)聯(lián)規(guī)則集RUL=RUL∪RULj；

算法1步驟1的時(shí)間復(fù)雜度為O(1)；步驟2需求取U/C與U/D，其時(shí)間復(fù)雜度為O(|C||U|2)，且需針對(duì)每一等價(jià)類Xi計(jì)算其決策向量時(shí)間復(fù)雜度為O(|U||U/D|)，因此，步驟2整體時(shí)間復(fù)雜度為O(|C||U|2)；步驟3時(shí)間復(fù)雜度為O(|C|·|U/C|2)；步驟4的時(shí)間復(fù)雜度最壞情況下不超過(guò)O(|U/C|3)；步驟5中將DF(u)轉(zhuǎn)換為DF′(u)作為基本操作，其時(shí)間復(fù)雜度為O(|U/C|)；通常情況下|U|?|U/C|，因此，步驟1—步驟5的整體時(shí)間復(fù)雜度為O(|C||U|2)。

令P=|DES(MCB(sim(IDS)))|，則步驟6時(shí)間復(fù)雜度最壞情況下不超過(guò)O(P|C||U/C|)；步驟7計(jì)算容差塊時(shí)間復(fù)雜度為O(P|C||U|)，且需計(jì)算各容差塊的決策向量時(shí)間復(fù)雜度不超過(guò)O(P|U|·|U/D|)，通常情況下|P|<<|U|且|U/C|<<|U|∧|U/D|<<|U|，故步驟7整體時(shí)間復(fù)雜度不超過(guò)O(|C||U|2)。

步驟8中1)部分的時(shí)間復(fù)雜度為O(P|U/D|)，步驟8中2)部分的時(shí)間復(fù)雜度為O(P2|C|)；步驟8中3)部分為一次基本操作，其時(shí)間復(fù)雜度為O(1)；步驟8中4)部分的時(shí)間復(fù)雜度為O(k)；通常情況下|k|?|P|，因此，步驟8的整體時(shí)間復(fù)雜度為O(P2|C|)。

綜上所述，算法1的整體時(shí)間復(fù)雜度為O(|C|·|U|2)。

3 實(shí)驗(yàn)結(jié)果及分析

為進(jìn)一步驗(yàn)證本文所提出算法，本節(jié)將算法1應(yīng)用于某保險(xiǎn)公司私家車客戶車險(xiǎn)不完備數(shù)據(jù)集(*代表缺失值)，數(shù)據(jù)集形式如表1所示。設(shè)置數(shù)據(jù)離散化區(qū)間為年齡≤30，30<年齡≤45，年齡>45對(duì)應(yīng)離散化值分別為1，2，3；車齡≤1，1<車齡≤4，車齡>4對(duì)應(yīng)離散化值分別為1，2，3；新車購(gòu)置價(jià)≤80 000，80 000<新車購(gòu)置價(jià)≤140 000，新車購(gòu)置價(jià)>140 000對(duì)應(yīng)離散化值分別為1，2，3；在司時(shí)間≤380，380<在司時(shí)間≤740，在司時(shí)間>740對(duì)應(yīng)離散化值分別為1，2，3；簽單保費(fèi)≤3 000，3 000<簽單保費(fèi)≤5 000，簽單保費(fèi)>5 000對(duì)應(yīng)離散化值分別為1，2，3。令{a0,a1,a2,a3,a4}代表?xiàng)l件屬性“性別，年齡，車齡，新車購(gòu)置價(jià)，在司時(shí)間”，vdn5l55代表決策屬性“簽單保費(fèi)”。

將算法1應(yīng)用于私家車客戶車險(xiǎn)數(shù)據(jù)集，得到與之對(duì)應(yīng)的全體規(guī)則集。以下針對(duì)各決策值僅選取前件較短(即泛化能力較強(qiáng))的若干規(guī)則解釋其實(shí)際含義。其中，規(guī)則置信度為決策系統(tǒng)中匹配此規(guī)則的對(duì)象數(shù)目與匹配此規(guī)則前件的對(duì)象數(shù)目的比值；支持度為決策系統(tǒng)中匹配此規(guī)則對(duì)象集在整個(gè)論域中所占的比例；覆蓋度為決策系統(tǒng)中匹配此規(guī)則的對(duì)象數(shù)目與匹配此規(guī)則后件的對(duì)象數(shù)目的比值。決策“CLASS=1”，“CLASS=2”，“CLASS=3”的全體規(guī)則分別如表2—表4所示。

表1 車險(xiǎn)不完備數(shù)據(jù)集

表2中規(guī)則1表明，“車齡” (即購(gòu)車時(shí)間)高“新車購(gòu)置價(jià)”低時(shí)，客戶“簽單保費(fèi)”趨向于低，其置信度為74.37%；規(guī)則2表明，“車齡”高“在司時(shí)間”低時(shí)，客戶“簽單保費(fèi)”趨向于低，其置信度為64.73%。

表2 決策“CLASS=1”的全體規(guī)則

表3中規(guī)則1表明，“車齡” (即購(gòu)車時(shí)間)中“新車購(gòu)置價(jià)”中時(shí)，客戶“簽單保費(fèi)”趨向于中，其置信度為80.60%；規(guī)則2表明，“車齡”低“新車購(gòu)置價(jià)”低時(shí)，客戶“簽單保費(fèi)”趨向于中，其置信度為72.10%；規(guī)則3表明，“車齡”低“新車購(gòu)置價(jià)”中時(shí)，客戶“簽單保費(fèi)”趨向于中，其置信度為70.95%；規(guī)則4表明，“年齡”高“新車購(gòu)置價(jià)”中時(shí)，客戶“簽單保費(fèi)”趨向于中，其置信度為68%。

表3 決策“CLASS=2”的全體規(guī)則

表4中規(guī)則前件至少為3個(gè)條件屬性，相對(duì)于其他決策而言其支持度已大大降低，此處僅選擇支持度較高的幾條加以解釋。表4中規(guī)則1表明，“車齡” (即購(gòu)車時(shí)間)低“新車購(gòu)置價(jià)”高“在司時(shí)間”低時(shí)，客戶“簽單保費(fèi)”趨向于高，其置信度為75.65%；規(guī)則2表明，“年齡”高“車齡”低“新車購(gòu)置價(jià)”高時(shí)，客戶“簽單保費(fèi)”趨向于高，其置信度為71.95%；規(guī)則3表明，“性別”女“車齡”低“新車購(gòu)置價(jià)”高時(shí)，客戶“簽單保費(fèi)”趨向于高，其置信度為76.02%；規(guī)則4表明，“年齡”中“車齡”低“新車購(gòu)置價(jià)”高時(shí)，客戶“簽單保費(fèi)”趨向于高，其置信度為76.50%。

表4 決策“CLASS=3”的全體規(guī)則

將車險(xiǎn)數(shù)據(jù)集前1/3記錄作為訓(xùn)練集運(yùn)行算法1生成不完備系統(tǒng)可信關(guān)聯(lián)規(guī)則集，剩下數(shù)據(jù)分為5組測(cè)試集，按文獻(xiàn)[9]中匹配與沖突處理策略得到分類匹配，結(jié)果如表5所示。

表5 車險(xiǎn)數(shù)據(jù)集分類匹配結(jié)果

由表5可知，待識(shí)樣本僅匹配規(guī)則集中一條規(guī)則(即單匹配情形)的比率較高，均保持在60%左右；當(dāng)待識(shí)樣本匹配多條規(guī)則(即多匹配情形)，其分類匹配的正確率均遠(yuǎn)大于分類錯(cuò)誤比率，說(shuō)明多匹配時(shí)的決策推理具有較好效果；待識(shí)樣本不與規(guī)則集中任一規(guī)則相匹配(即無(wú)匹配情形)的情形所占比率較低，均在0.5%以下，表明算法獲得的規(guī)則集具有較強(qiáng)泛化能力；數(shù)據(jù)的總體分類測(cè)試匹配準(zhǔn)確率均保持在67%左右，說(shuō)明本算法對(duì)于此現(xiàn)實(shí)應(yīng)用數(shù)據(jù)集具有較為穩(wěn)定的分類預(yù)測(cè)性能。

表6給出了文獻(xiàn)[10]算法、文獻(xiàn)[11]算法和本文算法分別應(yīng)用于不完備數(shù)據(jù)集post-operative，Hepatitis，Voting-Records上的分類識(shí)別率實(shí)驗(yàn)結(jié)果對(duì)比。表6表明，本文算法在不完備數(shù)據(jù)集post-operative，Hepatitis，Voting-Records上的分類識(shí)別率均遠(yuǎn)高于MLEM2算法與文獻(xiàn)[11]中算法，主要有2個(gè)方面原因：①本文算法會(huì)針對(duì)不完備系統(tǒng)中每一基本信息粒自動(dòng)設(shè)置基準(zhǔn)置信參數(shù)，而不是預(yù)先設(shè)置固定的置信參數(shù)來(lái)挖掘規(guī)則，如此則可避免遺漏置信度小于固定參數(shù)的部分有用規(guī)則；②本文算法能針對(duì)系統(tǒng)中每一基本信息粒搜索其前件組合，挖掘具有極大泛化能力的全體潛在有用規(guī)則，避免了采用啟發(fā)式方法或某些特定順序選擇屬性而遺漏部分有用規(guī)則。

表6 分類識(shí)別率結(jié)果比較

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

針對(duì)不完備系統(tǒng)設(shè)計(jì)有效的規(guī)則獲取方法是不完備系統(tǒng)數(shù)據(jù)處理的重要問(wèn)題，為此，本文借鑒圖中極大團(tuán)概念，基于粗糙集容差關(guān)系定義相容塊構(gòu)造范式計(jì)算不完備系統(tǒng)的全體極大相容塊，生成極大相容塊最全描述系統(tǒng)，進(jìn)而在此基礎(chǔ)上設(shè)計(jì)了一種基于極大團(tuán)的不完備系統(tǒng)規(guī)則獲取算法，并將該算法應(yīng)用于某保險(xiǎn)公司私家車客戶車險(xiǎn)不完備數(shù)據(jù)集，得到了一些可解釋的規(guī)則集，實(shí)驗(yàn)結(jié)果與數(shù)據(jù)分析說(shuō)明了該算法的分類預(yù)測(cè)性能。

[1] PAWLAK Z. Rough sets[J]. International Journal of Information and Computer Science,1982,11(5):314-356.

[2] SKOWRON A, PAWLAK Z. Rudiments of rough sets[J]. Information Sciences, 2007,177(1): 3-27.

[3] 黃記林,管延勇,沈建廷. 幾類相容粗糙集模型的研究[J]. 計(jì)算機(jī)科學(xué)與探索,2015,9(6): 740-746. HUANG Jilin, GUAN Yanyong, SHEN Jianting. Research on various types of tolerance rough set models[J]. Journal of Frontiers of Computer Science and Technology, 2015,9(6):740-746.

[4] 鞠恒榮,馬興斌,楊習(xí)貝,等. 不完備信息系統(tǒng)中測(cè)試代價(jià)敏感的可變精度分類粗糙集[J].智能系統(tǒng)學(xué)報(bào), 2014,9( 2) : 219-223. JU Hengrong, MA Xingbin, YANG Xibei, et al. Test-cost-sensitie based variable precision classification rough set in incomplete information system[J]. CAAI Transactions on Intelligent Systems, 2014,9( 2) : 219-223.

[5] 許韋,吳陳,楊習(xí)貝. 基于容差關(guān)系的不完備可變精度多粒度粗糙集[J]. 計(jì)算機(jī)應(yīng)用研究,2013,30(6):1712-1715. XU Wei, WU Chen, YANG Xibei. Incomplete variable precision multi-granulation rough sets based on tolerance relation[J]. Application Research of Computers,2013, 30(6): 1712-1715.

[6] KRYSZKIEWICZ M. Rough set approach to incomplete information system[J]. Information Sciences, 1998, 112(1):39-49.

[7] LEUNG Y, WU W, ZHANG W. Knowledge acquisition in incomplete information systems: A rough set approach[J]. European Journal of Operational Research, 2006,168(1):164-180.

[8] QIAN Y, LIANG J, LI D, et al. Approximation Reduction in Inconsistent Incomplete Decision Tables[J]. Knowledge- Based Systems, 2010,23(5):427-433.

[9] 黃治國(guó),王淼. 基于決策矩陣的可信關(guān)聯(lián)規(guī)則挖掘方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2014,35(8):2890-2895.

HUANG Zhiguo, WANG Miao. Decision matrix-based method for mining credible association rule[J]. Computer Engineering and Design,2014,35(8): 2890-2895.

[10] GRZYMALA J W. Date with Missing Attribute Values: Generalization of Indiscernibility Relation and Rule Induction[J]. Transactions on Rough Sets, 2004,31(1):78-95.

[11] GUAN L, HU F, HAN F. A rule induction algorithm in incomplete decision table based on attribute order[J]. Journal of Intelligent & Fuzzy Systems, 2016,30(2):961-969.

[12] 黃治國(guó),李娜. 基于分辨函數(shù)的極大團(tuán)搜索算法[J]. 計(jì)算機(jī)科學(xué),2014,41(4):248-251. HUANG Zhiguo, LI Na. Discernibility function-based algorithm for finding all maximal cliques[J]. Computer Science,2014, 41(4):248-251.

(編輯：張 誠(chéng))

Maximal clique-based method for acquiring association rules in incomplete system

HUANG Zhiguo, ZHANG Tianwu

(School of Computer Science, Henan University of Engineering, Zhengzhou 451191, P.R. China)

Aiming at solving the problem of rule acquisition in incomplete system, an effective algorithm based on maximal clique is proposed for getting association rules. The conception of maximal clique theory in the graph is introduced to define the normal form for constructing consistent block; all maximal consistent blocks are collected by transforming the normal form, then the most complete description system of the maximal consistent block is generated; the decision discernible normal form is constructed for each object in the most complete description system, and all credible association rules corresponding to each object is acquired eventually. This method has two characteristics: the benchmark confidence parameter is generated for each basic information granule automatically, which would avoid omitting available rules with the confidence level less than the fixed preset parameter; the decision discernible normal form is transformed to its minimal disjunctive form equivalently, which would avoid omitting available rules due to selecting the attribute in a particular order. Finally, this algorithm is applied to incomplete data set of UCI and auto insurance data, and the experiment results show the performance of this algorithm on classifying prediction.

maximal clique; maximal consistent block; normal form transformation; rule mining

10.3979/j.issn.1673-825X.2017.02.021

2016-03-22

2016-07-25 通訊作者：黃治國(guó) huangzg2020@139.com

河南省科技攻關(guān)計(jì)劃項(xiàng)目(142102210401)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目資助計(jì)劃(17A520027)；鄭州市科技攻關(guān)計(jì)劃項(xiàng)目(141PPTGG374)；河南工程學(xué)院博士基金資助項(xiàng)目(D2013003)

Foundation Items：The Planning and Development Project of Henan Province(142102210401); The Key Project of Science Research for Higher Education in Henan Province(17A520027); The Science and technology project in Zhengzhou(141PPTGG374); The Doctor Foundation in Henan University of Engineering(D2013003)

TP301.6

A

1673-825X(2017)02-0279-06

黃治國(guó)(1978-)，男，湖南臨湘人，副教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘、智能計(jì)算。E-mail:huangzg2020@139.com。

張?zhí)煳?1973-)，男，河南新鄉(xiāng)人，副教授，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)挖掘。E-mail:xxzhtw@163.com。