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

張 崟,何振峰

(福州大學 數學與計算機科學學院,福州 350108)

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

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

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

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

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

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

1 FSSD 算法簡介

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

1.1 特征子集選擇

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

1.2 FSSD 算法

在FSSD 算法中,子群s是子群集合S=ext[D]={ext(d)|d∈D}的任何子集,模式d∈D提供了對子群的描述.模式結構是三元組(G,(D,?),δ)形式,G是樣本集,D是模式集,?是偏序關系,模式集D的模式通過偏序關系 ?從最普通限制到最嚴格限制進行排序,即c?d?ext(d)?ext(c),表示模式d覆蓋的子群是模式c覆蓋的子群的子集.δ將樣本映射到最嚴格模式上,例如:δ(g)是樣本g的最嚴格模式,稱為閉合間隔模式,只要修改模式 δ (g),至少會丟棄一個樣本.與模式結構相關的兩個映射:(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帶來的質量增益可以表示為:

與式(2)對應的嚴格樂觀估計:

FSSD 算法框架如算法1.

(G,An,k)算法1.FSSD(G,An) k輸入:數據集,子群數量S輸出:子群集S=?GS=GGS 1),//是當前樣本集|S|＜k 2) while GS ? δ s*ccS(ext(int(s*)))3) 在模式結構(,(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為空和當前樣本集GS為G;第2)行和第4)行是控制迭代次數,當|S|=k或者最大增益小于0 時,算法終止并返回子群集S;在每次迭代過程中,第3)行是在未覆蓋樣本集GS的模式結構(GS,(D,?),δ)中選擇最大化增益WRA ccS(ext(int(s*)))的子群s*,由于s*?GS但不一定s*∈S,所以通過映射關系使得ext(int(s*))∈S,在尋找子群s*過程中,使用嚴格樂觀估計式(7)進行剪枝,從而縮小搜索空間;在第5)行中更新子群集S和當前樣本集GS,ext(int(s*)) 添加到子群集S并且將s*從當前樣本集GS中去除.

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

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

2.1 集成方法

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

圖1 異構集成特征選擇

2.2 特征選擇器

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

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

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

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

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

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

2.3 組合方式

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

2.4 算法

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

算法2.FSSD++算法(G,A) kn輸入:數據集,子群數量,特征子集大小S輸出:子群集1) for h=1 to H //H 個特征選擇器Rankh 2)=第h 個特征選擇器獲得特征集A的排名3) end for 4) for j=1 to J //組合所有特征排名,J是特征集A的數量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) 對 進行二次排序,先按排名從小到大排序,再按特征域數量從小到大排序A′′n= A′′10) 從 中取前n 個特征(G,tA′′n,k)11) FSSD

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

3 實驗與分析

3.1 實驗數據集

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

表1 UCI的7 個數據集以及NHANES的1 個數據集

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

3.2 實驗參數

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

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

3.3 實驗分析

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

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

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

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

在文獻[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的數量占自我報告聽力損失總數量的比,即對于WE4FA＞25 dB或者WEHFA＞35 dB,自我報告聽力損失的陽性預測值,n(class=Yes)是自我報告聽力損失總數量.與FSSD 算法相比,FSSD++算法挖掘自我報告聽力損失的陽性預測值更高,WE4FA＞25 dB 或者WEHFA＞35 dB的人數也更多,因為FSSD++算法的特征子集包含4 kHz,4 kHz 聽力下降是導致自我報告聽力損失的重要因素,所以FSSD++算法挖掘自我報告聽力損失人群在4 kHz的聽力損失比較高,WE4FA＞25 dB 或者WEHFA＞35 dB的人數就增多,自我報告聽力損失的陽性預測值也就變高.

4 總結與展望

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