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

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

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

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

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

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

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

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

0 引 言

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

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

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

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

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)中存在某些對象的屬性值缺失情形(通常缺失值用“*”表示)，則稱其為不完備決策系統(tǒng)(incomplete decision system, IDS)。

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

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

(1)

決策向量表現(xiàn)為條件等價類關(guān)于決策等價類的條件概率分布，各概率分布之和為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)系滿足自反性、對稱性，但不滿足傳遞性。

定義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)中對象與圖中頂點一一對應(yīng)，而系統(tǒng)中極大相容塊與圖中極大團(tuán)一一映射，故可借鑒文獻(xiàn)[12]中方法求取系統(tǒng)的全體極大相容塊。同時，在決策系統(tǒng)中，各條件等價類中對象間不可分辨，因此針對不完備決策系統(tǒng)生成簡化不完備決策系統(tǒng)，然后在此基礎(chǔ)上計算極大相容塊，可有效減少對象間比較次數(shù)，從而降低時空開銷。

定義4 IDS的簡化不完備決策系統(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 給定簡化不完備決策系統(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))}。

考慮簡化不完備決策系統(tǒng)sim(IDS)中的每一對象Xi∈U/C的極大相容塊分辨范式DF(Xi)的情形：若DF(Xi)=?，則其容差塊T(Xi)即為一極大相容塊；否則，將極大相容塊分辨范式DF(Xi)等價轉(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)換為其最全描述(即針對每一“*”取值屬性判斷該塊中是否存在其他對象在該屬性有取值，若存在則以該取值替代，否則仍取值為“*”)，收集每一極大相容塊最全描述即得到極大相容塊最全描述決策系統(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)

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

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

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

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

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

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

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

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

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

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

步驟7 對?z∈DES(MCB(sim(IDS)))計算其關(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 對?z∈DES(MCB(sim(IDS)))生成其關(guān)聯(lián)規(guī)則

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

2)對?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)換為等價的極小析取范式DF′(z)=(∧R1)∨…∨(∧Rk)；

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

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

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

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

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

3 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[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ī)科學(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)中測試代價敏感的可變精度分類粗糙集[J].智能系統(tǒng)學(xué)報, 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ī)應(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ān)聯(lián)規(guī)則挖掘方法[J]. 計算機(jī)工程與設(shè)計,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] 黃治國,李娜. 基于分辨函數(shù)的極大團(tuán)搜索算法[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.

(編輯：張 誠)

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 通訊作者：黃治國 huangzg2020@139.com

河南省科技攻關(guān)計劃項目(142102210401)；河南省高等學(xué)校重點科研項目資助計劃(17A520027)；鄭州市科技攻關(guān)計劃項目(141PPTGG374)；河南工程學(xué)院博士基金資助項目(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

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

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