屬性子集選擇算法及其推薦方法研究.pdf

1、數(shù)據(jù)挖掘領(lǐng)域存在一個(gè)重要原則GIGO（Garbage In，Garbage Out），說明挖掘知識(shí)的可靠性取決于收集數(shù)據(jù)的質(zhì)量，而影響數(shù)據(jù)質(zhì)量的一個(gè)重要因素就是用于描述數(shù)據(jù)的屬性質(zhì)量。為此研究人員常借助于屬性子集選擇（簡稱屬性選擇），通過特定策略從原始屬性集合中選擇與學(xué)習(xí)目標(biāo)密切相關(guān)的屬性子集來描述數(shù)據(jù)集。本文研究重點(diǎn)為屬性選擇算法及如何為新問題推薦合適的屬性選擇算法。
　　屬性選擇通常通過識(shí)別并刪除與學(xué)習(xí)目標(biāo)不相關(guān)的屬性和對描述

2、學(xué)習(xí)目標(biāo)而言是冗余的屬性來完成。然而屬性間交互作用也是屬性選擇過程中一個(gè)不容忽視的因素。已有研究中很少能夠在刪除不相關(guān)、冗余屬性的同時(shí)兼顧屬性間交互作用。為此本文首先提出了兩種新的基于規(guī)則挖掘的屬性選擇算法同時(shí)兼顧到上述幾點(diǎn)。
　　對于中低維度數(shù)據(jù)集，本文提出了一種基于關(guān)聯(lián)規(guī)則挖掘的屬性選擇算法 FEAST（Feature subset sElection Algorithm based aSossicaTion rule min

3、ing），該方法首先挖掘兩種帶約束的關(guān)聯(lián)規(guī)則：分類和原子型關(guān)聯(lián)規(guī)則，之后利用分類型關(guān)聯(lián)規(guī)則來刪除不相關(guān)屬性并保留屬性間交互作用，最后利用原子型關(guān)聯(lián)規(guī)則識(shí)別和刪除冗余屬性得到最終屬性子集。同時(shí)，由于支持度和置信度閾值是FEAST算法中的兩個(gè)關(guān)鍵參數(shù)，為了更好的利用FEAST算法，提出了一種基于偏最小二乘回歸的閾值預(yù)測方法來為新的數(shù)據(jù)集預(yù)測合適的參數(shù)。人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明FEAST能夠在識(shí)別不相關(guān)、冗余屬性的同時(shí)兼顧到屬性間交互作用，

4、實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明了FEAST算法在提高常用分類器Na?ve Bayes，C4.5，PART以及IB1的平均分類精度上優(yōu)于其他常用屬性選擇算法以及閾值預(yù)測方法的有效性。
　　對于高維數(shù)據(jù)集，F(xiàn)EAST算法由于高時(shí)間復(fù)雜度而不適用。為此本文提出了一種基于FOIL（First Order Inductive Leaner）規(guī)則生成方法的屬性選擇算法FRFS（FOIL Rule based F eature subset Sel

5、ection algorithm）。該算法通過在基本FOIL規(guī)則生成過程中加入約束條件來過濾冗余屬性并保留屬性間交互作用，同時(shí)通過提出的一種基于規(guī)則支持度的屬性相關(guān)性度量指標(biāo)CoverRatio來識(shí)別不相關(guān)屬性。最后在人工數(shù)據(jù)集和實(shí)際高維數(shù)據(jù)集上對FRFS的性能進(jìn)行測試，實(shí)驗(yàn)結(jié)果表明了FRFS不僅能在識(shí)別不相關(guān)、冗余屬性的同時(shí)兼顧到屬性間交互作用，而且在提高分類器Na?ve Bayes，C4.5，PART和IB1的平均分類精度上要明顯優(yōu)

6、于常用屬性選擇算法，同時(shí)相比其他屬性選擇算法在高維數(shù)據(jù)集上的運(yùn)行效率提高10倍以上。
　　盡管新屬性選擇算法或者已有算法的改進(jìn)在不斷提出，根據(jù)NFL（No Free Lunch）理論，并不存在特定屬性選擇算法適用于所有問題。對于給定屬性選擇問題，不同屬性選擇算法間存在性能差異。如何為指定問題推薦性能較優(yōu)的屬性選擇算法就顯得尤為重要。數(shù)據(jù)挖掘領(lǐng)域的元學(xué)習(xí)是一種通過分析問題特征和算法性能間關(guān)系，進(jìn)而利用這種關(guān)系為新問題選擇合適算法的方

7、法。本文將該思想用于屬性選擇算法推薦，提出了一種基于元學(xué)習(xí)的屬性選擇算法自動(dòng)推薦方法。對于指定數(shù)據(jù)集，該推薦方法首先抽取數(shù)據(jù)集特征，并根據(jù)數(shù)據(jù)集特征來計(jì)算其近鄰數(shù)據(jù)集，然后根據(jù)候選屬性選擇算法在這些近鄰數(shù)據(jù)集上的性能對候選算法進(jìn)行排序，最后將性能表現(xiàn)較優(yōu)，即排序靠前的算法推薦給該數(shù)據(jù)集。同時(shí)該推薦方法中采用了一種面向用戶的多標(biāo)準(zhǔn)度量指標(biāo)來評價(jià)屬性選擇算法性能，能兼顧到屬性選擇算法選擇子集上對應(yīng)分類器的分類精度，算法運(yùn)行時(shí)間和選擇屬性的數(shù)

8、量。最后在115實(shí)際數(shù)據(jù)集和22個(gè)不同的屬性選擇算法上對該推薦方法進(jìn)行了測試，實(shí)驗(yàn)結(jié)果表明了該方法能夠快速有效地推薦合適的屬性選擇算法，推薦命中率高達(dá)90％以上。
　　基于元學(xué)習(xí)的算法推薦方法根據(jù)元特征（即描述數(shù)據(jù)集的指標(biāo)）抽取方法和元目標(biāo)（候選算法的相對性能）表現(xiàn)形式不同可分為不同類別。已有推薦方法通常將元學(xué)習(xí)目標(biāo)看作單個(gè)算法（或單標(biāo)簽形式）或候選算法的排序，且基于算法排序的推薦方法推薦結(jié)果通常也是算法排序，并不能確定具體有幾個(gè)

9、算法可用于推薦。然而從理論和實(shí)驗(yàn)角度分析均可得出，指定數(shù)據(jù)集上合適算法存在多個(gè)，且隨著數(shù)據(jù)集不同合適算法數(shù)量不同，即元目標(biāo)看作多標(biāo)簽形式更加合理。因此本文將算法推薦看作多標(biāo)簽學(xué)習(xí)問題并提出了一種基于多標(biāo)簽學(xué)習(xí)的屬性選擇算法推薦方法。最后，通過在115實(shí)際屬性選擇數(shù)據(jù)集，5種不同數(shù)據(jù)集特征提取方法和22個(gè)屬性選擇算法上進(jìn)行實(shí)驗(yàn)，結(jié)果表明了基于多標(biāo)簽學(xué)習(xí)的推薦方法相比已有的基于算法排序和單標(biāo)簽的推薦方法能夠顯著提高不同數(shù)據(jù)特征上的平均推薦命