張 崟,何振峰

(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,福州 350108)

子群發(fā)現(xiàn)是一種數(shù)據(jù)挖掘技術(shù),它基于給定目標(biāo)特征,挖掘不同特征間的有趣關(guān)聯(lián)[1].提取的模式通常用規(guī)則表示,規(guī)則定義為:

Cond是由一組屬性鍵值對組成,稱為規(guī)則前件;Targetvalue是目標(biāo)特征值,稱為規(guī)則后件.

盡管子群發(fā)現(xiàn)算法在過去得到了足夠的發(fā)展,但仍存在一些不足.傳統(tǒng)子群發(fā)現(xiàn)算法通常是將連續(xù)型數(shù)值數(shù)據(jù)直接離散化,導(dǎo)致了精度損失和次優(yōu)結(jié)果;并且是基于局部模式挖掘,導(dǎo)致模式集缺乏多樣性[2].對于這些問題,Millot 等人[3]提出OSMIND (optimal subgroup discovery in purely numerical data)算法,利用閉合間隔模式避免連續(xù)型數(shù)值數(shù)據(jù)離散化,但是忽略了模式集挖掘.Bosc 等人[4]提出MCTS4DM (Monte Carlo tree search for pattern mining)算法,在使用閉合間隔模式的基礎(chǔ)上,增加相似性度量函數(shù),對MCTS(Monte Carlo tree search)輸出的候選模式集進(jìn)行后處理,從而獲得多樣性的模式集,但是需要消耗大量內(nèi)存來存儲候選模式集.Belfodil 等人[5]提出FSSD 算法,使用閉合間隔模式和子群集質(zhì)量度量函數(shù),后者用來評估模式集的多樣性,同時在每次迭代過程中只存儲最優(yōu)模式,避免了消耗大量內(nèi)存.但是FSSD 算法為了減少運(yùn)行時間,選擇特征域數(shù)量少的特征子集,此特征選擇方法沒有考慮數(shù)據(jù)集中的監(jiān)督信息,屬于無監(jiān)督特征選擇,當(dāng)選擇的特征子集與目標(biāo)類不相關(guān)或弱相關(guān)時,模式集質(zhì)量下降,因此研究如何選擇FSSD 算法的特征子集具有重要意義.

特征選擇是根據(jù)某些特征選擇標(biāo)準(zhǔn)從原始特征集中獲取特征子集的過程[6].現(xiàn)有特征選擇主要用在分類、聚類上,用在子群發(fā)現(xiàn)上的研究較少.在子群發(fā)現(xiàn)上的特征選擇只找到文獻(xiàn)[7],它提出基于相關(guān)性約束的過濾式特征選擇,將特征-值對的覆蓋關(guān)系作為相關(guān)性約束,當(dāng)特征的所有特征-值對滿足相關(guān)性約束時,才被定義為不相關(guān)并且去除,在最壞的情況下,每個特征都存在一個特征-值對不滿足相關(guān)性約束,此時無法去除任何特征,同時單一的特征選擇方法生成的特征子集缺少多樣性和穩(wěn)定性[8].

分類、聚類特征選擇與子群發(fā)現(xiàn)特征選擇的原則有些不同:(1) 前者是將類和類區(qū)分開,后者是將目標(biāo)類和非目標(biāo)類區(qū)分開,在多類情況下,兩者差別比較明顯;(2) 前者需要去除不相關(guān)和冗余特征,而后者只去除不相關(guān)特征,不去除冗余特征,這點(diǎn)在醫(yī)學(xué)領(lǐng)域尤其明顯,在文獻(xiàn)[9]中,使用子群發(fā)現(xiàn)挖掘初次使用合成阿片類藥物后,出現(xiàn)不良后果的患者特征,挖掘結(jié)果認(rèn)為有慢性疼痛病史的患者,會增加藥物上癮風(fēng)險,與合成阿片類藥物處方指南相吻合.由于慢性病與疼痛病存在強(qiáng)相關(guān),如果考慮去除冗余特征,子群發(fā)現(xiàn)挖掘結(jié)果會變成有慢性病史或者疼痛病史的患者,會增加藥物上癮風(fēng)險.

為了解決FSSD 算法的特征子集選擇問題,本文引入基于ReliefF和方差分析的集成特征選擇算法,獲得具有多樣性、穩(wěn)定性以及與目標(biāo)類相關(guān)性強(qiáng)的特征子集.第2 節(jié)介紹FSSD 算法,第3 節(jié)介紹改進(jìn)的FSSD 算法,第4 節(jié)對改進(jìn)的FSSD 算法進(jìn)行實(shí)驗(yàn)并且對實(shí)驗(yàn)結(jié)果做分析,第5 節(jié)對所做的工作進(jìn)行總結(jié)和未來進(jìn)一步的研究方向.

1 FSSD 算法簡介

FSSD 算法旨在使用少量內(nèi)存和短時間內(nèi)提供多樣性的模式集[5].FSSD是基于窮舉搜索的子群發(fā)現(xiàn)算法,窮舉搜索的運(yùn)行時間與模式數(shù)量成正比,當(dāng)搜索空間很大時,運(yùn)行時間變長,所以在文獻(xiàn)[5]中,先選擇特征子集,再使用FSSD 算法來提取模式集.

1.1 特征子集選擇

在運(yùn)行FSSD 算法前,數(shù)據(jù)集的特征先按照名義型、數(shù)值型排序,再按照特征域數(shù)量從小到大排序,然后根據(jù)用戶給定的特征子集數(shù)量選擇特征子集,此特征選擇方法是為了盡可能選擇特征域數(shù)量少的特征子集,隨著特征子集的域數(shù)量減少,模式數(shù)量就減少,運(yùn)行時間就縮短.然而此方法忽視了數(shù)據(jù)集中的監(jiān)督信息,沒有考慮特征與目標(biāo)類的相關(guān)性,特征與目標(biāo)類的相關(guān)性就完全取決于數(shù)據(jù)集分布情況,當(dāng)特征子集與目標(biāo)類相關(guān)性不佳時,模式集質(zhì)量下降,當(dāng)特征子集與目標(biāo)類相關(guān)性強(qiáng)時,模式集質(zhì)量上升,模式集質(zhì)量隨著特征子集與目標(biāo)類的相關(guān)性而變化,讓模式集質(zhì)量充滿不確定性.

1.2 FSSD 算法

在FSSD 算法中,子群s是子群集合S=ext[D]={ext(d)|d∈D}的任何子集,模式d∈D提供了對子群的描述.模式結(jié)構(gòu)是三元組(G,(D,?),δ)形式,G是樣本集,D是模式集,?是偏序關(guān)系,模式集D的模式通過偏序關(guān)系 ?從最普通限制到最嚴(yán)格限制進(jìn)行排序,即c?d?ext(d)?ext(c),表示模式d覆蓋的子群是模式c覆蓋的子群的子集.δ將樣本映射到最嚴(yán)格模式上,例如:δ(g)是樣本g的最嚴(yán)格模式,稱為閉合間隔模式,只要修改模式 δ (g),至少會丟棄一個樣本.與模式結(jié)構(gòu)相關(guān)的兩個映射:(1)ext:D→?(G),ext(d)={g∈G|?d∈D,d?δ(g)},?(G)是樣本集G的冪集,ext(d)表示模式d覆蓋的子群;其中E?G,int(E)表示覆蓋樣本子集E的閉合間隔模式.

給定子群s和子群集S?S,計算子群s給S帶來的質(zhì)量增益可以表示為:

與式(2)對應(yīng)的嚴(yán)格樂觀估計:

FSSD 算法框架如算法1.

(G,An,k)算法1.FSSD(G,An) k輸入:數(shù)據(jù)集,子群數(shù)量S輸出:子群集S=?GS=GGS 1),//是當(dāng)前樣本集|S|＜k 2) while GS ? δ s*ccS(ext(int(s*)))3) 在模式結(jié)構(gòu)(,(D,),) 中尋找子群 使得增益最大WRA WRAccS(ext(int(s*)))≤0 4) if then break S=S ∪{ext(int(s*))},GS=GSs*5)6) end while

對于算法1,在第1)行中初始化子群集S為空和當(dāng)前樣本集GS為G;第2)行和第4)行是控制迭代次數(shù),當(dāng)|S|=k或者最大增益小于0 時,算法終止并返回子群集S;在每次迭代過程中,第3)行是在未覆蓋樣本集GS的模式結(jié)構(gòu)(GS,(D,?),δ)中選擇最大化增益WRA ccS(ext(int(s*)))的子群s*,由于s*?GS但不一定s*∈S,所以通過映射關(guān)系使得ext(int(s*))∈S,在尋找子群s*過程中,使用嚴(yán)格樂觀估計式(7)進(jìn)行剪枝,從而縮小搜索空間;在第5)行中更新子群集S和當(dāng)前樣本集GS,ext(int(s*)) 添加到子群集S并且將s*從當(dāng)前樣本集GS中去除.

2 基于集成特征選擇的FSSD 算法

當(dāng)FSSD 算法的特征子集與目標(biāo)類相關(guān)性不強(qiáng)時,模式集質(zhì)量下降,而單一特征選擇方法獲得的特征子集缺乏多樣性和穩(wěn)定性.為此,本文提出基于集成特征選擇的FSSD 算法,簡稱FSSD++算法.FSSD++算法通過集成ReliefF和方差分析方法獲得多樣性、穩(wěn)定性以及與目標(biāo)類相關(guān)性強(qiáng)的特征子集,再使用FSSD 算法返回高質(zhì)量子群集.在設(shè)計集成特征選擇時,需要確定以下幾個方面:(1)集成方法;(2)確定特征選擇器的返回形式和使用的特征選擇器;(3)組合方式.

2.1 集成方法

集成特征選擇的集成方法主要有兩種:同構(gòu)集成和異構(gòu)集成,如果使用相同的基本特征選擇器,稱為同構(gòu)集成,否則稱為異構(gòu)集成.在同構(gòu)集成特征選擇中,使用相同的特征選擇器和不同的數(shù)據(jù)子集,可以使用自舉法抽樣得到數(shù)據(jù)子集;在異構(gòu)集成特征選擇中,使用不同的特征選擇器和相同的數(shù)據(jù),如圖1所示.前者用于大規(guī)模數(shù)據(jù)集,通過在并行節(jié)點(diǎn)中處理數(shù)據(jù)來縮短計算時間;后者確保穩(wěn)定、魯棒的特征選擇[10],由于本文的實(shí)驗(yàn)數(shù)據(jù)集規(guī)模不大,所以采用異構(gòu)集成方法.

圖1 異構(gòu)集成特征選擇

2.2 特征選擇器

特征選擇器的返回形式分為特征子集和特征排名,特征子集是先根據(jù)預(yù)先定義的搜索策略生成特征子集,再使用最優(yōu)原則對特征子集進(jìn)行評估,最終獲得局部最優(yōu)特征子集;特征排名是根據(jù)特征相關(guān)性或者重要性返回所有特征排名,再使用閾值確定最終特征子集[10].返回特征子集的特征選擇器需要搜索所有特征子集,計算量大,為了避免此問題,本文選擇返回特征排名的特征選擇器.此外,為了縮短運(yùn)行時間和有效利用監(jiān)督信息,所選的特征選擇器還應(yīng)該是基于過濾式和監(jiān)督的特征選擇器.

本文選擇ReliefF[6]和方差分析[11]作為基本特征選擇器,它們既是返回特征排名,又是基于過濾式、監(jiān)督的特征選擇器.同時它們都是單獨(dú)評估每個特征與目標(biāo)類的相關(guān)性,并且不去除冗余特征[6,11],這與子群發(fā)現(xiàn)特征選擇原則相符合.下面具體介紹ReliefF和方差分析.

ReliefF是根據(jù)特征區(qū)分不同類別樣本的程度,對特征進(jìn)行加權(quán),它為每個特征分配一個相關(guān)權(quán)重來表示特征與目標(biāo)類的相關(guān)性.假設(shè)在n個樣本中隨機(jī)選擇l個樣本,每個特征fi的計算公式:

c是類別數(shù)量,yj是樣本xj的類別,W(j,i)是樣本xj與同類樣本和不同類樣本在特征fi上的距離之和,di(S,xj)是樣本xj與樣本集S在特征fi上的距離,H(xj,t)是樣本xj的近鄰t類 樣本集,|H(xj,t)|是H(xj,t)樣本集的數(shù)量,p(y)是y類樣本的比例.

方差分析是研究每個特征對目標(biāo)類是否產(chǎn)生顯著影響,它使用F統(tǒng)計的值作為每個特征得分,得分越高,類間特征均值差異越大,說明特征變化引起了目標(biāo)類變動.每個特征fi的計算公式:

c是類別數(shù)量,n是樣本總數(shù)量,nj是j類別的樣本數(shù)量,μij是j類樣本中特征fi的平均值,μi是全部樣本中特征fi的平均值,xkij是j類樣本中第k個樣本在特征fi上的值.

2.3 組合方式

參考文獻(xiàn)[12]中的組合方式,使用min 函數(shù)獲取每個特征在所有特征選擇器的特征排名中的最小排名,排名越小,特征越重要,重復(fù)此過程獲得所有特征的最小排名,再將所有特征的最小排名按進(jìn)行二次排序:先按排名從小到大排序,再按特征域數(shù)量從小到大排序,最后得到所有特征最終排名.假設(shè)ReliefF 返回所有特征排名Rank1,方差分析返回所有特征排名Rank2,首先獲取特征aj在所有特征選擇器的排名Rank*,j={Rank1,j,Rank2,j},然后使用min 函數(shù)獲取特征aj在所有特征選擇器的最小排名,即特征aj的最終排名min_aj=min(Rank*,j),重復(fù)此步驟直到獲得所有特征的最小排名A′={min_aj|j=1,···,J},再將排名先按從小到大排序,再按特征域數(shù)量從小到大排序得到所有特征最終排名A′′.

2.4 算法

FSSD++算法框架如算法2.

算法2.FSSD++算法(G,A) kn輸入:數(shù)據(jù)集,子群數(shù)量,特征子集大小S輸出:子群集1) for h=1 to H //H 個特征選擇器Rankh 2)=第h 個特征選擇器獲得特征集A的排名3) end for 4) for j=1 to J //組合所有特征排名,J是特征集A的數(shù)量Rank*,j={Rankh,j|h=1,···,H}5)aj,aj∈A//獲取特征 在所有特征選擇器中最小的特征排名min_a j=min(Rank*,j)6)A′=A′∪min_a j 7)8) end for A′′= A′9) 對 進(jìn)行二次排序,先按排名從小到大排序,再按特征域數(shù)量從小到大排序A′′n= A′′10) 從 中取前n 個特征(G,tA′′n,k)11) FSSD

對于算法2,在第1)-3)行中獲取每個特征選擇器返回的特征排名;在第4)-8)行中使用min 函數(shù)獲取在所有特征選擇器中每個特征的最小排名,直到獲得全部特征的最小排名A′;在第9)行中對組合排名A′先按排名升序,再按特征域數(shù)量升序獲得最終排名A′′;在第10)行中根據(jù)用戶給定數(shù)量n,從A′′中獲取前n個特征子集A′′n.

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)選擇7 個UCI 數(shù)據(jù)集和1 個NHANES (national health and nutrition examination survey)數(shù)據(jù)集,如表1所示.abalone、adult、autos、credit、dermatology、mushrooms和sonar 來自UCI 數(shù)據(jù)集,1999_2004_Audiometry 來自NHANES 數(shù)據(jù)集.

表1 UCI的7 個數(shù)據(jù)集以及NHANES的1 個數(shù)據(jù)集

NHANES是一項(xiàng)連續(xù)的橫斷面健康訪問和調(diào)查研究,旨在評估美國人民的健康和功能狀況.該研究每兩年周期收集一次數(shù)據(jù),本文重點(diǎn)分析1999-2004年參加聽力檢測和聽力問卷調(diào)查的20-69 歲人群的數(shù)據(jù),研究在自我報告聽力損失人群中,不同特征之間的關(guān)聯(lián).根據(jù)測試者編碼(SEQN) 連接聽力檢測數(shù)據(jù)(audiometry examination data)、聽力問卷數(shù)據(jù)(audiometry questionnaire data)、糖尿病數(shù)據(jù)(diabetes questionnaire data)、高血壓數(shù)據(jù)(blood pressure questionnaire data)和人口統(tǒng)計數(shù)據(jù)(demographics data)生成5 417 條數(shù)據(jù).樣本排除標(biāo)準(zhǔn)如下:(1)變量數(shù)據(jù)缺失,(2)在第1 次1 kHz和第2 次1 kHz 頻率下,聽力閾值的差值超過10 dB,(3)自我報告聽力損失程度為耳聾,(4)血糖水平介于正常和糖尿病之間的數(shù)據(jù),根據(jù)上述標(biāo)準(zhǔn)排除280 條數(shù)據(jù),最終納入5 137 條數(shù)據(jù),被命名為1999_2004_Audiometry.同時作者將自我報告聽力損失程度(good、little of trouble hearing、a lot of trouble hearing)重新分類:good 表示未自我報告聽力損失,little、a lot of trouble hearing 表示自我報告聽力損失.1999_2004_Audiometry 數(shù)據(jù)集的特征有性別、年齡、種族、國家、學(xué)歷、24 小時內(nèi)有沒有聽音樂、糖尿病、高血壓、在0.5、1、2、3、4、6、8 kHz下左右耳的聽力閾值,目標(biāo)變量是自我報告聽力損失,它的取值范圍是{Yes,No},Yes 表示自我報告聽力損失,No 表示未自我報告聽力損失.

3.2 實(shí)驗(yàn)參數(shù)

FSSD++算法實(shí)驗(yàn)選擇FSSD 算法實(shí)驗(yàn)中特征子集數(shù)量與特征總數(shù)量不同的7 個UCI 數(shù)據(jù)集,并在此基礎(chǔ)上增加1999_2004_Audiometry 數(shù)據(jù)集.特征子集數(shù)量與特征總數(shù)量相同的數(shù)據(jù)集,無法突顯出特征選擇的意義,所以在此不做實(shí)驗(yàn)對比.在FSSD++算法對比實(shí)驗(yàn)中,FSSD++算法的參數(shù)有最大規(guī)則數(shù)量k=5、特征子集數(shù)量n、最大搜索深度Depthmax=8.除了1999_2004_Audiometry 數(shù)據(jù)集的特征子集數(shù)量n=6由作者給定外,其他數(shù)據(jù)集的特征子集數(shù)量與文獻(xiàn)[5] 中FSSD 算法實(shí)驗(yàn)給定特征子集數(shù)量一致,FSSD 算法實(shí)驗(yàn)的最大規(guī)則數(shù)量k=5和最大搜索深度Depthmax=8,所以FSSD++算法實(shí)驗(yàn)也選擇此值.MCTS4DM 算法的參數(shù)除了最大規(guī)則數(shù)量k=5、特征子集數(shù)量n外,還有最大迭代次數(shù)nbiter=5 000,最大冗余maxRedundancy=0.25.每個數(shù)據(jù)集指定特征子集數(shù)量n后,表示為數(shù)據(jù)集-特征子集數(shù)量,例如:abalone-5,具體如表2所示.表2中“-”表示W(wǎng)RAcc 質(zhì)量小于0.

表2 FSSD++算法與MCTS4DM、FSSD 算法的WRAcc 對比

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

表2是FSSD++算法與FSSD 算法、MCTS4DM算法的對比實(shí)驗(yàn)結(jié)果,使用WRAcc 作為評估指標(biāo).對比FSSD++和FSSD 算法,在大部分?jǐn)?shù)據(jù)集中FSSD++提供更優(yōu)的WRAcc 質(zhì)量,除了數(shù)據(jù)集dermatology-10 提供相等WRAcc 質(zhì)量,這個結(jié)果表明使用集成特征選擇的FSSD++算法能夠提高WRAcc 質(zhì)量,驗(yàn)證了FSSD++算法的有效性.同時FSSD++和FSSD 算法都優(yōu)于MCTS4DM 算法.

表3是在自我報告聽力損失中,FSSD和FSSD++算法的特征子集和陽性預(yù)測值對比.表4對表3中特征子集進(jìn)行了具體描述,從表3可以看出,FSSD和FSSD++算法的特征子集都有DIQ010 (糖尿病)、BPQ020 (高血壓)和AUQ030 (24 小時內(nèi)有沒有聽音樂),FSSD 算法是根據(jù)特征域數(shù)量來獲取特征,而FSSD++算法是根據(jù)特征與目標(biāo)變量的相關(guān)性來獲取特征,FSSD++算法認(rèn)為自我報告聽力損失與3 kHz、4 kHz、6 kHz、糖尿病、高血壓、24 小時內(nèi)有沒有聽音樂有關(guān).文獻(xiàn)[13]驗(yàn)證了4 kHz是自我報告聽力損失最重要的個體頻率,但是目前還沒有文獻(xiàn)表明自我報告聽力損失與3 kHz、6 kHz 相關(guān),FSSD++算法為研究自我報告聽力損失的相關(guān)知識提供了新思路.文獻(xiàn)[14]和文獻(xiàn)[15]表明糖尿病和高血壓與聽力損失有關(guān),聽力損失與自我報告聽力損失存在中等一致性[16],所以糖尿病和高血壓與自我報告聽力損失有關(guān),進(jìn)一步說明FSSD++算法挖掘自我報告聽力損失人群特征的有效性.

表3 在自我報告聽力損失中FSSD和FSSD++算法的特征子集和陽性預(yù)測值對比

表4 FSSD和FSSD++算法的特征子集對比

在文獻(xiàn)[13]中聽力損失定義:在0.5、1、2、4 kHz下較差耳朵的純音平均聽力閾值＞25 dB (WE4FA＞25 dB)或者在4、6、8 kHz 下較差耳朵的純音平均聽力閾值＞35 dB (WEHFA＞35 dB).表3中n(WE4FA＞25 or WEHFA＞35)/n(class=Yes)表示模式集覆蓋人群中WE4FA＞25 dB 或者WEHFA＞35 dB的數(shù)量占自我報告聽力損失總數(shù)量的比,即對于WE4FA＞25 dB或者WEHFA＞35 dB,自我報告聽力損失的陽性預(yù)測值,n(class=Yes)是自我報告聽力損失總數(shù)量.與FSSD 算法相比,FSSD++算法挖掘自我報告聽力損失的陽性預(yù)測值更高,WE4FA＞25 dB 或者WEHFA＞35 dB的人數(shù)也更多,因?yàn)镕SSD++算法的特征子集包含4 kHz,4 kHz 聽力下降是導(dǎo)致自我報告聽力損失的重要因素,所以FSSD++算法挖掘自我報告聽力損失人群在4 kHz的聽力損失比較高,WE4FA＞25 dB 或者WEHFA＞35 dB的人數(shù)就增多,自我報告聽力損失的陽性預(yù)測值也就變高.

4 總結(jié)與展望

針對FSSD 算法選擇特征域數(shù)量較少的特征子集,導(dǎo)致模式集質(zhì)量下降的問題,提出一種基于集成特征選擇的FSSD 算法.該算法在預(yù)處理階段,根據(jù)min 函數(shù)組合ReliefF和方差分析的輸出結(jié)果,對組合結(jié)果先按排名升序,再按特征域數(shù)量升序,最后獲得前n個特征.此特征子集作為FSSD 算法的輸入?yún)?shù),從而獲取更優(yōu)的模式集.在UCI 數(shù)據(jù)集和NHANES 數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn),對比FSSD++、FSSD和MCTS4DM 算法的WRAcc;對比FSSD和FSSD++算法的自我報告聽力損失的特征子集和陽性預(yù)測值.實(shí)驗(yàn)結(jié)果表明,與MCTS4DM和FSSD 算法相比,FSSD++算法歸納的模式集WRAcc值更優(yōu);與FSSD 算法相比,FSSD++算法挖掘自我報告聽力損失人群的特征有效性和陽性預(yù)測值更高.在未來工作中將側(cè)重研究如何自適應(yīng)選擇特征數(shù)量.