孫桂利,張繼福

(太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院,太原030024)

分類是數(shù)據(jù)挖掘和模式識別等領(lǐng)域中重要的研究內(nèi)容之一,利用訓(xùn)練數(shù)據(jù)生成關(guān)于類別的描述,即把給定的數(shù)據(jù)對象映射到某個類,可用于數(shù)據(jù)對象的分類和預(yù)測,具有廣泛應(yīng)用價值。

目前,常用的分類提取算法有:決策樹方法,貝葉斯分類法,遺傳算法,粗糙集和概念格等方法[1]。決策樹方法是通過掃描決策樹發(fā)現(xiàn)分類知識,適用大規(guī)模的數(shù)據(jù)處理,主要優(yōu)點是描述簡單,分類速度快。如J.R.Quinlan提出的ID3算法[2];貝葉斯分類法是利用概率統(tǒng)計知識進(jìn)行分類的算法,優(yōu)點是它可以預(yù)測類成員關(guān)系的可能性,缺點是由于其假設(shè)在實際情況下經(jīng)常不成立,因而分類準(zhǔn)確性就會下降。如NB(Native Bayes)[3];遺傳算法優(yōu)點是具有隱含的并行性,可以和許多方法結(jié)合。缺點是收斂于局部和較早收斂問題,而且相對比較復(fù)雜;粗糙集其優(yōu)點是直接從給定問題出發(fā),通過不可分辨關(guān)系和不可分辨類來確定問題的近似域,從而找出內(nèi)在規(guī)律,其算法簡單,其缺點是很難直接處理連續(xù)的屬性,如王匡[4]等人提出的決策表約簡;概念格是數(shù)據(jù)分析及分類知識提取的一種有效工具,具有完備性、直觀性等特點。胡可云[5]等給出了一般概念格的規(guī)則提取方法,其主要原理是依據(jù)格結(jié)點的直接泛化來產(chǎn)生相應(yīng)的規(guī)則;王浩[6]等給出了基于量化概念格的規(guī)則的一種提取方法,提出的量化的相對約簡格減少了大規(guī)模的概念格的存儲復(fù)雜度,改算法生成的結(jié)果同時剔除了冗余的分類規(guī)則;張繼福[7]等依據(jù)約束概念格[8]結(jié)點外延與訓(xùn)練樣本數(shù)據(jù)集等價劃分之間的關(guān)系,引入外延支持度和劃分支持度的概念,提出了一種基于約束概念格的分類規(guī)則提取方法,具有較高的分類效率和正確率。冀英偉[14]等提出了一種基于謂詞邏輯的分類規(guī)則約簡方法,消除了冗余規(guī)則,提高了效率。王瑋[15]等提出了一種基于網(wǎng)格的概念格分布式構(gòu)造方法,為其在大規(guī)模數(shù)據(jù)集上的應(yīng)用提供了一種新思路。

目前,在概念格研究中,假定組成概念格的內(nèi)涵重要性同等重要,沒有考慮構(gòu)成內(nèi)涵屬性重要性的差別,形成的概念格結(jié)點中包含很多冗余結(jié)點,提取分類規(guī)則效率低。為此,張繼福[9-11]等人提出了一種新的概念格:加權(quán)概念格及其構(gòu)造方法,加權(quán)概念格是針對屬性(項目)重要程度的不同,通過引入內(nèi)涵權(quán)值而形成的一種格結(jié)構(gòu),有效地減低了概念格的存儲空間和建格時間。頻繁加權(quán)概念格是在加權(quán)概念格的基礎(chǔ)上通過引入虛結(jié)點,生成頻繁結(jié)點和虛結(jié)點的格結(jié)構(gòu),是一個完全格[11]。由于該格結(jié)構(gòu)僅生成滿足用戶最小權(quán)值閾值的結(jié)點,具有構(gòu)造時空復(fù)雜性低的特點。由于頻繁加權(quán)概念格構(gòu)造中,設(shè)置了概念內(nèi)涵的最小權(quán)值閾值,只有滿足了最小閾值的頻繁結(jié)點和虛結(jié)點才生出,結(jié)點本身就是人們感興趣的,而不感興趣的已經(jīng)被去除掉,也就保證了提取出的知識也就是人們感興趣的,有價值的。本文采用頻繁加權(quán)概念格作為分類規(guī)則提取工具,給出了一種新的加權(quán)分類規(guī)則的提取算法。該算法采用加權(quán)外延支持度來度量結(jié)點外延個數(shù)過少且重要程度較低的噪聲數(shù)據(jù)。最后,利用恒星光譜數(shù)據(jù)作為形式背景,實驗驗證了該算法有較高的分類正確率。

1 概念格與加權(quán)概念格

設(shè)K=(D,C,I,W)為一個形式背景,其中:對象集D={t1,t2,…,tn},屬性集C={C1,C2,…,Cm},I?D ×C,W={w1,w2,…,wm}為C中單屬性權(quán)值集合,wi∈W標(biāo)識了屬性Ci的重要程度(0≤wi≤1)。參照文獻(xiàn)[9-11],其相關(guān)定義和概念描述如下:

在形式背景K中,(A1,B1)和(A2,B2)是任意的兩個形式概念,如果(A1,B1)≤ (A2,B2)?B2?B1(A1A2),則由K中的所有概念以及概念之間的偏序關(guān)系I可構(gòu)成了一個完全格,則其稱為一般概念格,可表示為 ＜L(D,C,I),≤＞.設(shè)hw=(A,B,w)為K上的任一個三元組,且A?D,B?C,w為屬性集B的權(quán)值且0≦w≤1,并滿足如下映射關(guān)系:

(1)f(A)={c∈ C|?d ∈ A,〈d,n〉 ∈ I};

(2)g(B)={d ∈ D|?c∈ B,〈d,n〉 ∈ I}

如果三元組hw=(A,B,w)滿足最大擴展性,即f(A)=B,g(B)=A,則稱hw為K上的一個加權(quán)概念 。設(shè)h1=(A1,B1,w1)、h2=(A2,B2,w2)是K構(gòu)造的任意加權(quán)概念,如果B2?B1(A1?A2),則稱h1是h2的子孫結(jié)點,h2是h1的祖先結(jié)點,記為h1≤h2,其中:≤稱為概念的“層次序”。如果不存在h3=(A3,B3,w3)使得h1≤h3≤h2,則稱h1是h2的子結(jié)點,記h1的所有子結(jié)點集合為Child(h1),加權(quán)概念h2是 h1的父結(jié)點,記 h2的所有父結(jié)點集合為Parent(h2)。K中所有加權(quán)概念及這種序組成的集合稱為加權(quán)概念格 ＜L(D,C,I,W),≤＞.設(shè)內(nèi)涵重要性最小閾值(權(quán)值閾值)為 θmin(0≤θmin≤1),對于K上的任意加權(quán)概念hw=(A,B,w),若w≥θmin,hw稱為頻繁加權(quán)概念;若w ＜θmin,稱為非頻繁加權(quán)概念。

設(shè) ＜L(D,C,I,W),≤＞由K構(gòu)造的任意加權(quán)概念格,設(shè)sup=(D,f(D),w1)為L(D,C,I,W)的最頂結(jié)點,Inf=(g(C),C,w2)為L(D,C,I,W)的最底結(jié)點,則對于任意非頻繁重要結(jié)點hw=(A,B,w)且hw≠sup,hw≠Inf:

(1)若Parent(hw)(Child(hw))中只有一個結(jié)點sup(Inf),則hw稱為次頂概念(次底概念);

(2)若Parent(hw)(Child(hw))中沒有sup(Inf),且Parent(hw)(Child(hw))中全為或不全為次頂概念(次底概念),同時 Parent(hw)(Child(hw))中頻繁加權(quán)概念數(shù)不小于2個,則稱hw為父虛概念(子虛概念);如果hw既是父虛概念,同時又是子虛概念,則稱hw為虛概念(結(jié)點),定義虛概念hw的權(quán)值為 -1,否則稱是非虛概念(結(jié)點)。

如果其概念格中每個加權(quán)概念均為頻繁加權(quán)概念或虛概念,則稱該加權(quán)概念格為頻繁加權(quán)概念格 ＜Lf(D,C,I,W),≤ ＞.

2 基于加權(quán)概念格的分類規(guī)則提取

分類規(guī)則提取就是找出從給定數(shù)據(jù)集D(D={t1,t2,…,tn})到類別屬性值的集合C(C={C1,C2,…,Cm})的映射。對于某個待分析的數(shù)據(jù)集D,其類別屬性值是固定的m個,從這個特性方面考慮,可以把數(shù)據(jù)集分成m個等價劃分,記為D1,D2,…,Dm,這時對于每某個記錄ti,如果ti中的重要部分從屬于Dj,則也就是找到對應(yīng)的分類Cj,得到分類規(guī)則。

設(shè)頻繁加權(quán)概念格的形式背景K =(D,C,I,W),對于任意頻繁加權(quán)概念格結(jié)點均可記為三元組(A,B,w),其中:A?D是對象集合,B?C是屬性集合,w為屬性B的權(quán)值。對于頻繁加權(quán)概念格,任意結(jié)點都是人們感興趣的頻繁結(jié)點或虛結(jié)點,從分類規(guī)則提取的角度來講,用戶希望提取出的規(guī)則應(yīng)該是使用頻率較高的且內(nèi)涵是重要的。但現(xiàn)實生活中,往往出現(xiàn)情況是規(guī)則較重要但使用頻率非常低,或者規(guī)則一般重要但是使用頻率較高。重要程度和使用頻率兩者結(jié)合可以很好的解決這種問題,重要性一般且使用頻率頻率較低的分類規(guī)則就可看成是無意義規(guī)則,而高于這個限度的規(guī)則視為有意義規(guī)則。結(jié)合頻繁加權(quán)概念格可知:格結(jié)點的內(nèi)涵的權(quán)值的意義就代表著重要程度;格結(jié)點的外延個數(shù)就是其內(nèi)涵所包含的數(shù)據(jù)對相個數(shù)較少,從中提取出的分類的規(guī)則使用頻率就低。

定義1 設(shè)(A,B,w)為頻繁加權(quán)概念格中的任意結(jié)點,格結(jié)點的加權(quán)外延支持度定義為E=w*|A|/|U|,其中:|A|為結(jié)點外延包含對象的個數(shù),|U|為總記錄的條數(shù)。

對于任意頻繁加權(quán)概念格結(jié)點,加權(quán)外延支持度E表示的是格結(jié)點的內(nèi)涵的重要程度同其外延中的數(shù)據(jù)對象在形式背景中出現(xiàn)概率的兩者結(jié)合。E越高代表從B中提取的分類規(guī)則很重要且能夠?qū)^多數(shù)據(jù)對象進(jìn)行分類,即:實用性越強,這樣所提取出的規(guī)則對于用戶是非常有意義的。如果E非常低,則實用性非常低,所提取出的規(guī)則使用頻率很低或重要性不夠,這樣的格結(jié)點可視為無用規(guī)則或噪聲。所以,可設(shè)定加權(quán)外延支持度閾值Emin,大于Emin的被認(rèn)為滿足實用性,從而可有效的減少噪聲,滿足用戶的要求。另一方面,在A滿足外延加權(quán)支持度大于Emin情況下,在提取分類規(guī)則時,肯定會碰到格結(jié)點中的外延對象所對應(yīng)的類別屬性屬于多種類別屬性的情況。對于這樣的格結(jié)點,判斷其屬于哪種類別屬性非常重要,由于各個類別屬性的權(quán)值不同,同時外延對象屬于不同類別屬性的概率也是不同的。為便于下一步確定分類規(guī)則的分類屬性取值。對于任意結(jié)點的外延對象可能屬于不同的類別屬性,可以從兩個方面考慮:

當(dāng)A?Di時,任意結(jié)點的外延完全從屬于某個劃分Di,則A中對象的所對應(yīng)分類屬性值一定是Di所對應(yīng)的分類屬性值Ci(1≤i≤m),則可提取出分類規(guī)則B→Ci;

當(dāng)A?Di且A∩Di=Φ,任意結(jié)點的外延不完全從屬于某個劃分Di,A中對象的分類屬性值不一定是Di所對應(yīng)的分類屬性值Ci(i=1,…,m),這里可以定義A中對象從屬于各類別屬性的概率,可定義為劃分度Pj,Pj是滿足內(nèi)涵B且屬于Ci的對象的個數(shù)同結(jié)點外延包含對象的個數(shù)的比值。其中一定能找到最大的劃分度Pj,表示滿足內(nèi)涵B且屬于Cj的對象個數(shù)最多,但它不能直接選取其作為可提取的規(guī)則,因為內(nèi)涵的重要性是不同的,滿足對象的最多的但是不是最重要的、不是人們所需要的規(guī)則。同理,只取內(nèi)涵最重要的同樣不能作為選取分類規(guī)則的標(biāo)準(zhǔn)。人們最想要的是權(quán)重和劃分支持度同樣高的。這也是頻繁加權(quán)概念格的重要意義所在,所以,這里引入重要性概念,作為判別依據(jù)。

定義2 對于頻繁加權(quán)概念格中的任意結(jié)點(A,B,w),如果 ?g∈A,g∈Cj(1≤j≤m),wg為Cj對應(yīng)的權(quán)值,M=A∩Cj,H=|M|*wg為A中對象的分類屬性值取Cj的重要性。

A中數(shù)據(jù)對象的分類屬性屬于不同的類別屬性,劃分支持度描述了其屬于不同類別屬性的概率,劃分支持度大的權(quán)重反而小的所對應(yīng)的規(guī)則并不是我們所需要的。而權(quán)重大劃分支持度小的準(zhǔn)確性不高。所以兩者綜合考慮才能選取最適當(dāng)?shù)囊?guī)則。

定理1 對于頻繁加權(quán)概念格中的任意結(jié)點(A,B,w),存在 g∈A,g∈Ci(1≤i≤m),如果A中任意一個k∈A,k∈Cj(1≤j≤m),都有Hg=|M|*wg＞Hk=|N|*wk,其中M=A∩Ci,N=A∩ Cj,wg為Ci對應(yīng)的權(quán)值,wk為Cj對應(yīng)的權(quán)值,則此結(jié)點分類規(guī)則為B→Ci.

證明 對于任意結(jié)點(A,B,w),存在g∈A,g∈Ci,由定義2可知,A中對象的分類屬性值取Ci的重要性為Hg=|M|*wg.而任意一個k∈A,k∈Cj的分類屬性值取Cj的重要性Hk=|N|*wk.如果Hg＞Hk,也就是Hg是A中對象的分類屬性取值重要性最大的。即可得出結(jié)論:此結(jié)點分類規(guī)則為B→Ci.

由定理1可知,A中數(shù)據(jù)對象屬于不同的類別屬性時,分別求取其分類屬性值為Ci的重要性,選取重要性最大的那個類別屬性,提取分類規(guī)則B→ti,選取的分類屬性準(zhǔn)確性就高。

3 基于加權(quán)概念格的分類規(guī)則提取算法

綜上所述,從頻繁加權(quán)概念格中提取分類規(guī)則的基本思想是自頂向下逐個掃描每個結(jié)點,在結(jié)點的加強外延支持度大于Emin情況下,當(dāng)結(jié)點外延包含于某個數(shù)據(jù)集等價劃分時,直接提取規(guī)則,當(dāng)結(jié)點外延不包含于某個數(shù)據(jù)集等價劃分時,判斷其屬于某個類別屬性的重要性,選取重要性最大的作為分類規(guī)則的分類屬性。其算法描述如下:

算法:頻繁加權(quán)概念格分類算法CRAAFWCL(Classification rule acquisition algorithm based on Fre-quent Weighted concept lattice)

輸入:頻繁加權(quán)概念格k,加權(quán)外延支持度閾值Emin

輸出:分類規(guī)則集rule

//總對象個數(shù)為N;同分類屬性的m個不同取值可分為m個等價劃分(D1,D2…Dm)

該算法根據(jù)加權(quán)外延支持度采用自頂向下計算每個頻繁加權(quán)概念格結(jié)點,判斷其外延與等價劃分的關(guān)系,如果外延包含于某等價劃分Gi,直接提取規(guī)則,否則計算其外延與Gi相交的關(guān)系,有交集的計算占據(jù)的比例乘以對應(yīng)的權(quán)值得到它對應(yīng)得比重,從中選擇最大的值P對應(yīng)得規(guī)則,進(jìn)而提取分類規(guī)則,然后繼續(xù)掃描其他結(jié)點。算法掃描每個結(jié)點的時間復(fù)雜度是O(n),每個結(jié)點外延A與Gi交運算時間復(fù)雜度為O(m),每個結(jié)點提取分類規(guī)則復(fù)雜度為O(m2)。因此,次算法時間復(fù)雜度為O(m2*n)。

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

實驗環(huán)境:CPU:Pentium(R)D-3.0G CPU,內(nèi)存:512M,操作系統(tǒng):Windows XP SP3,數(shù)據(jù)庫:ORACLE9i,采用Microsoft Visual Studio C++2008實現(xiàn)了頻繁加權(quán)概念格分類算法CRAAFWCL。此恒星光譜數(shù)據(jù)是利用國家天文臺提供的,分類屬性取恒星的7個類型,頻繁加權(quán)概念格的形式背景通過以下預(yù)處理構(gòu)成:①選取200個的波長作為條件屬性集,②每一波長處依據(jù)流量和峰寬把其離散化為13中數(shù)一作為條件屬性。其中:一半作為訓(xùn)練集,一半作為測試集。參考文獻(xiàn)[11,13],采用歸一化的信息熵做為單屬性內(nèi)涵的權(quán)值,用戶也可以自己設(shè)定權(quán)值,而多屬性內(nèi)涵的權(quán)值采用算術(shù)平均權(quán)值的方法。

表1 分類規(guī)則測試1Tab.1 Test 1 of classification rule(權(quán)值閾值 θmin=0.01,恒星光譜個數(shù) =4 000條)

表2 分類規(guī)則測試2Tab.2 Test 2 of classification rule(外延加權(quán)支持度Emin=0.002 2,恒星光譜個數(shù)=4 000條)

外延加權(quán)支持代表著所提取規(guī)則的使用頻率和內(nèi)涵重要程度,從表1中可以看出,其取值對分類規(guī)則的提前具有很大的影響,隨著外延加權(quán)支持度閾值的逐漸增加,其所提取的規(guī)則內(nèi)涵越重要,使用頻率越高,但是滿足條件能提取的規(guī)則逐漸減少,其正確率也逐漸減少,所以選取適當(dāng)?shù)募訖?quán)外延支持度閾值就非常的重要,要選取能滿足用戶對提取的規(guī)則時使用頻率較高的且內(nèi)涵是重要的最低要求,從而保證所提取分類規(guī)則的正確率。從表2和表3中可以看出,隨著數(shù)據(jù)集的數(shù)據(jù)量的逐步增加,生成的概念格結(jié)點也同樣的增多,同樣提取出的分類規(guī)則也就越多。但人們一般只希望對重要屬性感興趣,頻繁加權(quán)概念格引入虛結(jié)點,生成頻繁結(jié)點和虛結(jié)點的格結(jié)構(gòu),由于該格結(jié)構(gòu)僅生成滿足用戶權(quán)值閾值的結(jié)點,所以其構(gòu)造時間和存儲空間大大縮短。加權(quán)閾值設(shè)置就可把人們關(guān)心的數(shù)據(jù)給提取出來,從表中看到,隨著權(quán)值閾值設(shè)置的提高,生成的頻繁加權(quán)概念格的結(jié)點有一個下降的變化趨勢,即隨著權(quán)值閾值設(shè)置的升高,滿足條件的頻繁加權(quán)概念格結(jié)點也逐步減少,所提取的分類規(guī)則數(shù)也逐漸減少,因此權(quán)值閾值的設(shè)置對系統(tǒng)有很大的影響,隨著數(shù)據(jù)量的增加,生成的結(jié)點增多,所產(chǎn)生的分類規(guī)則也多,所用的時間也就增多。由此可見,隨著適當(dāng)?shù)臋?quán)值閾值設(shè)置,滿足權(quán)值閾值的結(jié)點數(shù)減少,相應(yīng)地頻繁結(jié)點和虛結(jié)點的總個數(shù)不斷下降,構(gòu)造格的時空復(fù)雜性越低,因此所提取的規(guī)則的效率也就相應(yīng)的提高。

表3 分類規(guī)則測試3Tab.3 Test 3 of classification rule(權(quán)值閾值θmin=0.01,外延加權(quán)支持度Emin=0.002 2)

5 結(jié)束語

頻繁加權(quán)概念格是針對屬性的重要程度的一個完全格,該格結(jié)構(gòu)具有構(gòu)造時空復(fù)雜性低且提取的知識的實用性強的特點。本文采用頻繁加權(quán)概念格作為分類規(guī)則提取工具,通過引入加權(quán)外延支持度的概念,給出了一種新的加權(quán)分類規(guī)則的提取算法CRAAFWCL。該算法計算加權(quán)外延支持度作為提取分類規(guī)則的重要依據(jù)來提取分類規(guī)則。最后利用國家天文臺提供的恒星光譜數(shù)據(jù),實驗驗證了該算法具有較高的分類效果。

[1]Jiawei Han.數(shù)據(jù)挖掘概念與技術(shù)[M].2版.范明,譯.北京:機械工業(yè)出版社,2004.

[2]Quinlan J R.Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[3]Friedman N,Geiger D,Goldszmidt M,Bayesian network classifier[J].Machine Learning,1997,29(1):131-163.

[4]王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機學(xué)報,2002,25(7):759-766.

[5]王志海,胡可云,胡學(xué)鋼.概念格上提取規(guī)則的一般算法與漸進(jìn)式算法[J].計算機學(xué)報,1999,22(l):66-70.

[6]王浩,胡學(xué)鋼,趙文兵.基于量化相對約簡格的分類規(guī)則發(fā)現(xiàn)[J].復(fù)旦大學(xué)學(xué)報,2004,43(5):761-765.

[7]張繼福,馬洋.一種基于約束概念格的恒星光譜數(shù)據(jù)自動分類方法[J].光譜學(xué)與光譜分析,2010,30(2):559-562.

[8]張繼福,張素蘭,胡立華.約束概念格及其構(gòu)造方法[J].智能系統(tǒng)學(xué)報,2006,2(1):31-38.

[9]張繼福,張素蘭,鄭鏈.加權(quán)概念格及其漸進(jìn)式構(gòu)造[J].模式識別與人工智能,2005,18(2):171-176.

[10]張素蘭,張繼福,高愫邡.加權(quán)概念格的漸進(jìn)式構(gòu)造及其關(guān)聯(lián)規(guī)則提取[J].計算機工程與應(yīng)用,2005,41(7):173-178.

[11]王欣欣,張繼福,張素蘭.一種頻繁加權(quán)概念格的批處理構(gòu)造算法[J].模式識別與人工智能,2010,23(5):77-81.

[12]胡可云,陸玉昌,石純一.基于概念格的分類和關(guān)聯(lián)規(guī)則的集成挖掘方法[J].軟件學(xué)報,2000,11(11):1478-1484.

[13]張素蘭,郭平,張繼福.基于信息熵和偏差的加權(quán)概念格內(nèi)涵權(quán)值獲取[J].北京理工大學(xué)學(xué)報,2011,31(1):59-63.

[14]冀英偉,楊海峰,張繼福.一種基于謂詞邏輯的分類規(guī)則約簡方法[J].太原科技大學(xué)學(xué)報,2010,31(1):59-64.

[15]王瑋,張繼福.一種基于網(wǎng)格的概念格分布式構(gòu)造方法[J].太原科技大學(xué)學(xué)報,2010,31(3):197-201.