程玉勝，胡 飛，程百球

(安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133)

面向高維數(shù)據(jù)PCA-ReliefF的EP模式分類算法

程玉勝，胡 飛，程百球

(安慶師范學(xué)院 計(jì)算機(jī)與信息學(xué)院，安徽 安慶 246133)

針對高維數(shù)據(jù)集，文中提出一種PREP(PCA-ReliefF for EP)算法：首先采用PCA和ReliefF算法實(shí)現(xiàn)特征降維；然后利用EP模式思想，構(gòu)造精度更高、規(guī)模更小的EP模式分類器；最后利用標(biāo)準(zhǔn)數(shù)據(jù)集對文中的方法進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明，在對高維數(shù)據(jù)進(jìn)行分類時(shí)，該方法構(gòu)造的分類器在預(yù)測精度和運(yùn)行時(shí)間上均有較大幅度的提升。

分類器；特征選擇；PCA-ReliefF；EP模式；PREP算法

分類在科研、醫(yī)學(xué)等諸多領(lǐng)域都具有廣泛的應(yīng)用。目前廣泛使用于統(tǒng)計(jì)學(xué)習(xí)[1-2]和數(shù)據(jù)挖掘等領(lǐng)域的常用分類方法大多是基于決策樹、距離或者神經(jīng)網(wǎng)絡(luò)等。隨著大數(shù)據(jù)時(shí)代的到來，傳統(tǒng)分類方法已然不再適用。Dong等人創(chuàng)造性的提出一種新興的EP模式分類算法，即初始時(shí)從項(xiàng)集出發(fā)采用類似關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法來挖掘EP模式。經(jīng)過實(shí)驗(yàn)證明，EP模式分類器在分類精度和時(shí)間性能上相比于其他分類器有很大的優(yōu)勢。但是同樣在面對高維數(shù)據(jù)時(shí)，其中的冗余數(shù)據(jù)造成了彼此之間很強(qiáng)的相關(guān)性，在挖掘過程中，不可避免的形成了對分類器產(chǎn)生負(fù)面影響的冗余模式。因此，Li等人又提出了一種改進(jìn)后的JEP-Classifier算法[3]，該算法具有很好的區(qū)分能力，能過濾不必要的EP模式，但是JEP分類器適用范圍較小，即覆蓋率偏低。于是Fan等人[4]提出了一種基本的顯露模式-eEp，能夠在確定并保留核屬性的同時(shí)，去除無關(guān)的分類模式。F.Berzal等人[5]提出了增加最小增長率差這一約束條件的ConsEPminer算法。S.Haykin[6]提出的基于邊界EP模式算法，通過操作左右邊界的變化來得到理想的EP模式，在挖掘過程中有效的避免了復(fù)雜數(shù)據(jù)帶來的冗余EP模式。H.Fan等人[7]后來提出的SJEP算法，在JEP模式的基礎(chǔ)上加入JEP模式必須滿足支持度閾值的約束條件；許洪濤[8]在對中文文本分類時(shí)，先使用特征選擇進(jìn)行有區(qū)分能力的核心屬性的提取，最后提出基于eEPs的中文文本分類方法TCEP，該方法在一定程度上緩解了維數(shù)災(zāi)難，也比較適合一般的大規(guī)模文本分類。施萬鋒等人[9-10]提出一種基于lasso的EP模式分類算法，在特征選擇時(shí)采用懲罰函數(shù)去除無用特征，有效保留重要的EP模式，但在此模式下，對超高維數(shù)據(jù)和高維小樣本數(shù)據(jù)沒有良好的分類效果，還存在較多的擬合現(xiàn)象。

針對數(shù)據(jù)維數(shù)較高、形式較為復(fù)雜的情況下，上述的方法沒有較好的性能。因此，本文基于EP模式分類器思想，提出了一種新的方法PREP：首先利用主成分分析[11-12](PrincipleComponentAnalysis，PCA)約簡存在相關(guān)性的特征，然后利用ReliefF算法[13-15]對權(quán)值較重的屬性進(jìn)行特征提取[16]，最后使用基于顯露模式(EmergingPattern，EP) 的分類器對預(yù)處理后的數(shù)據(jù)集進(jìn)行分類。該方法在保留重要屬性信息特征的同時(shí)，也能快速高效的進(jìn)行分類。

1 EP模式分類

1.1EP模式基本概念

EP模式的分類方法從關(guān)聯(lián)規(guī)則中得到啟發(fā)，從項(xiàng)集支持度和增長率的角度去決定如何分類，即當(dāng)兩個(gè)數(shù)據(jù)集中某個(gè)項(xiàng)集明顯出現(xiàn)支持度的變化時(shí)，那么該項(xiàng)集可以當(dāng)做區(qū)分不同數(shù)據(jù)集的一個(gè)核心屬性，該項(xiàng)集便具備良好的分類性能。

用{A1，A2，…,An}表示屬性集，Aj表示特征，{a1，a2，…,an}表示實(shí)例，a1，a2，…,an分別對應(yīng)于A1，A2，…,An特征的值，將其中的(Aj=aj)為一個(gè)項(xiàng)。若從邏輯上來定義，數(shù)據(jù)集D中所有項(xiàng)的集合為M,如果X中的項(xiàng)均存在于Y中，但Y中的項(xiàng)不一定都在X中找到時(shí)，便可以稱項(xiàng)集X包含于Y。

定義2 假設(shè)D′和D″分別表示兩個(gè)不同類別的數(shù)據(jù)集，用si(x)表示項(xiàng)集X在數(shù)據(jù)集Di中的支持度。項(xiàng)集X從D′到D″的增長率為

定義3 假設(shè)增長率閾值ρ>1,如果grD′→D″(X)≥ρ，那么就稱項(xiàng)集X是從D′到D″的EP模式，簡稱為D″的EP模式。

EP模式增長率的大小作為分類能力強(qiáng)弱的標(biāo)準(zhǔn)，他們之間存在著正比的關(guān)系，而支持度與該EP模式的分類范圍的關(guān)系也是如此。如表1所示。

表1 EP模式的事例

其中ρ=3。在被當(dāng)做優(yōu)秀范例的蘑菇集試驗(yàn)中，做出如下解釋：數(shù)據(jù)集由有毒蘑菇類和無毒蘑菇類組成，其中含有很多有效或者無效的EP模式。表中的數(shù)據(jù)對應(yīng)的支持度和增長率如下，

e1={(ODOR=none)，(GILL_SIZE=

broad)(RING_NUMBER=one)}，

e1在有毒類中的支持度為0，在可食用類中的支持度為63.9%，在這里可食用類和有毒類分別為目標(biāo)類和非目標(biāo)類。根據(jù)定義，e1增長率為∞，也就是可食用蘑菇類的一種EP模式。所以，根據(jù)e1挑選的蘑菇一般是可食用蘑菇。

e2={(BRUISES=no),(GILL_SPACING=

close),(VEIL_COLOR=white)}，

e2是一個(gè)有毒蘑菇類的EP模式。在可食用和有毒類蘑菇中包含有e2實(shí)例的比例分別為3.8%和 81.4%，其增長率為21.4。因而，具有e2特征的蘑菇在很大程度上是有毒的。

1.2 EP模式分類器構(gòu)造過程

對于一個(gè)給定的g維數(shù)據(jù)集D，設(shè)定合適的支持度sup和增長率ρ。在這里要說明一點(diǎn)，面對高維數(shù)據(jù)的時(shí)候，要提高算法的性能和減少運(yùn)行的時(shí)間，那么對應(yīng)的支持度要設(shè)置的比較高，而增長率可以根據(jù)實(shí)際的情況來自行調(diào)節(jié)。首先，開始掃描每一個(gè)屬性(單項(xiàng)集)，分別計(jì)算它們的支持度以及在各類之間的增長率，如果某個(gè)一項(xiàng)集(即單個(gè)屬性)對應(yīng)的支持度和增長率均大于給定的sup和ρ，那么將所有滿足該條件的一項(xiàng)集放入一個(gè)集合中。然后，再掃描由一項(xiàng)集中兩兩構(gòu)成的二項(xiàng)集，同理，當(dāng)某個(gè)二項(xiàng)集對應(yīng)的支持度和增長率也都大于sup和ρ時(shí)，將它們放入二項(xiàng)集集合中。接下來的步驟同上述一樣，項(xiàng)集數(shù)目不斷增加(最大數(shù)為g)，直到找不到滿足條件的項(xiàng)集為止。最后就是如果確定EP模式了，對于取得的各項(xiàng)集的集合，按照ρ和sup的大小從大到小進(jìn)行排序，輸出排在第一位的項(xiàng)集，即構(gòu)成最后的EP模式。

EP模式分類器構(gòu)造過程如圖1所示。

圖1EP模式分類器分類過程

2 結(jié)合PCA和ReliefF的EP模式分類算法(PREP算法)

對于高維數(shù)據(jù)的分類，首先要進(jìn)行降維處理，利用主成分分析去除冗余的屬性特征，保留核心屬性的同時(shí)完成高維空間到低維的映射，然后根據(jù)ReliefF算法思想對保留下來的屬性賦予體現(xiàn)重要程度的權(quán)值，權(quán)值的大小代表著該特征對于分類準(zhǔn)確的貢獻(xiàn)度，最后選擇特征權(quán)值最高的前d個(gè)特征構(gòu)成最后的核心特征子集。

在目標(biāo)類為兩類的情況下，如果訓(xùn)練樣本集為D={(x1,y1),(x2,y2)，…，(xn,yn)}，其中xi∈Rn，yi是xi類標(biāo)簽yi∈{-1，1}，則基于PCA-ReliefF的EP模式分類算法詳細(xì)描述如下所示。

PREP算法的主要步驟：

輸入：高維訓(xùn)練集D，迭代次數(shù)t，k個(gè)最近鄰樣本，目標(biāo)維數(shù)d，有效核心特征集合s，s>d。

步驟1 對隨機(jī)產(chǎn)生的訓(xùn)練數(shù)據(jù)集D0進(jìn)行主成分提取，將權(quán)值較大的前s個(gè)主成分存入數(shù)據(jù)集D1；

步驟2 首次將D1各特征權(quán)值歸零；

步驟3 隨機(jī)確定D1中的一個(gè)樣本X；

步驟4 分別任意選取與X同類和異類的k個(gè)近鄰，分別記為Pj和Mj(c)，其中j=1,2,…,k，c≠c(X)，c=1,2,…,C,C為樣本類別數(shù)，c(X)表示樣本所屬的類別；

步驟5 在此更新各個(gè)特征權(quán)值W(a)，權(quán)值更新公式為，

(1)

步驟6 重復(fù)執(zhí)行篩選過程t次，輸出每個(gè)特征的權(quán)值W(i)；

步驟7 按順序保留權(quán)值最大的前d個(gè)特征構(gòu)成特征集；

步驟8 采用EP模式分類。其主要步驟：

給定訓(xùn)練數(shù)據(jù)集D′(假定以最簡單的兩類問題)，給定支持度、增長率閾值。

(1)挖掘D1與D2之間相互的EP模式集E1和E2；

(2)約簡E1,E2中的EP模式；

(3)通過相應(yīng)的公式分別計(jì)算兩個(gè)類的基礎(chǔ)分；

(4)對于實(shí)例t，計(jì)算它在每個(gè)類中的規(guī)范化值norm＿score(t,Ck),將實(shí)例歸為分值最大的類。

其中，將特征a為標(biāo)準(zhǔn)量時(shí)，樣本X、Y之間的距離為d(a,X,Y)；p(c)表示第c類目標(biāo)的概率，也就是用該類目標(biāo)在數(shù)據(jù)集中的樣本總數(shù)除以總樣本總數(shù)，當(dāng)各類目標(biāo)樣本數(shù)大致相同時(shí)，p(c)=1/C；Mj(c)表示第c類目標(biāo)的第j個(gè)樣本；m和k的取值由樣本的總數(shù)量和維度數(shù)量綜合決定。待分類樣本t對每個(gè)類的規(guī)范化分norm＿score(S,C),可以按照如下公式得到：

agg＿score(S,C)=

(2)

(3)

PREP分類算法流程如圖2所示。

圖2 PREP分類算法流程

3 實(shí)驗(yàn)結(jié)果及析

3.1 實(shí)驗(yàn)結(jié)果

測試運(yùn)行環(huán)境為Windows XP操作系統(tǒng)，3.29 GHz的i3-2120 CPU，1.98 GB的內(nèi)存，編程使用JAVA語言，工具為MyEclipse。為了驗(yàn)證PREP分類算法所具有的時(shí)間優(yōu)越性和精度，本文所選取的數(shù)據(jù)集都是取自UCI數(shù)據(jù)庫，數(shù)據(jù)類別數(shù)都是兩類。如表2所示，ionsphere，madelon和lungcancer具有的樣本數(shù)分別為351，2 000和181，而屬性總數(shù)分別為34，500和12 534。在實(shí)驗(yàn)中，首先將PREP算法和CAEP算法進(jìn)行比較，比較的內(nèi)容有時(shí)間和精度，實(shí)驗(yàn)結(jié)果如表3所示。然后改變迭代的次數(shù)(k分別取值10和5，m的值取10)。為使實(shí)驗(yàn)結(jié)果有較高的可信度，實(shí)驗(yàn)的訓(xùn)練集和測試集都是隨機(jī)生成(各占總數(shù)的50%)，設(shè)置PREP和CAEP的增長率為20，最小支持度為0.005和0.01。

表2 實(shí)驗(yàn)使用的數(shù)據(jù)集描述

表3 CAEP和PREP實(shí)驗(yàn)對比

為了直觀的觀察目標(biāo)維數(shù)和閾值變化對實(shí)驗(yàn)結(jié)果的影響，實(shí)驗(yàn)中，對選取的3個(gè)測試數(shù)據(jù)集進(jìn)行了相應(yīng)結(jié)果繪制，如圖3～圖5所示。

3.2 實(shí)驗(yàn)結(jié)果分析

由表2選擇的數(shù)據(jù)集可以知道，為了體現(xiàn)算法的優(yōu)越性，使用了特征維數(shù)較高的3個(gè)數(shù)據(jù)集，由于目前大多數(shù)數(shù)據(jù)集為兩類，并且對于多類問題可以轉(zhuǎn)化為兩類問題解決，因此實(shí)驗(yàn)中選擇為兩類。對于Ionsphere數(shù)據(jù)集，CAEP算法和PREP 算法在正確率上相差不是很多，但是在運(yùn)行時(shí)間上，PREP算法時(shí)間減少了近9/10，相差很大。從Madelon，Lungcancer兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)情況看，CAEP算法已經(jīng)因?yàn)閮?nèi)存溢出或者產(chǎn)生的規(guī)則太多而不能進(jìn)行分類了，但是PREP算法在進(jìn)行了特征降維后，能夠正常的分類，在分類的正確率和時(shí)間消耗上也有不錯(cuò)的表現(xiàn)。由圖3，4，5可以看出，算法在準(zhǔn)確率和時(shí)間消耗上在一定范圍內(nèi)均表現(xiàn)出一定的波動(dòng)性。說明實(shí)驗(yàn)結(jié)果都是在k=10的情況下取得的。對k=15或者k=5也進(jìn)行了測試，發(fā)現(xiàn)k=10時(shí)，能取得令人滿意的結(jié)果。

表3的實(shí)驗(yàn)數(shù)據(jù)是在綜合考慮時(shí)間消耗和正確率的情況下取值的。總的來說，在閾值和目標(biāo)維數(shù)合適的情況下，經(jīng)過PCA-ReliefF的EP模式分類算法，在保證有效信息保留和減少運(yùn)行時(shí)間的同時(shí)，也能夠保證分類的準(zhǔn)確率。

4 結(jié)束語

針對維數(shù)較高的數(shù)據(jù)集，本文提出了一種基于PCA和ReliefF的特征選擇方法，首先去除相關(guān)性較強(qiáng)的特征互相間產(chǎn)生的干擾，然后進(jìn)行特征選擇，最后使用EP模式分類算法進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明，該算法能夠在保留住核心信息的同時(shí)，去除了冗余和互相之間相關(guān)性較強(qiáng)的特征，有效減少了運(yùn)行時(shí)間，并且在分類精度上取得了不錯(cuò)的結(jié)果，具有較好的性能。但是，對于小樣本數(shù)據(jù)或者數(shù)據(jù)維數(shù)很大的時(shí)候，算法的時(shí)間效率顯得不高或者計(jì)算量偏大，算法還存在執(zhí)行不下去的問題；另外k值選取問題，還沒能建立一個(gè)有效簡潔的標(biāo)準(zhǔn)，只能通過多次實(shí)驗(yàn)的對比而確定，不免會(huì)因?yàn)橹貜?fù)操作而帶來過多的時(shí)間消耗。這些都是下一步需研究的問題。

[1]S.Gnanapriya,R.Suganya,G.S.Devi,etal..Datamining:conceptsandtechniques[J].DataMining&KnowledgeEngineering, 2010, 26(1): 32-38.

[2]馬紅娟, 趙秀蘭, 孫亞萍, 等. 基于數(shù)據(jù)挖掘技術(shù)的概率統(tǒng)計(jì)教學(xué)研究[J]. 經(jīng)濟(jì)研究導(dǎo)刊, 2015(6): 220-222.

[3]JinyanLi,GuozhuDong,K.Ramamohanarao.Makinguseofthemostexpressivejumpingemergingpatternsforclassification[J].KnowledgeandInformationSystems, 2001, 3(2): 1-29.

[4]JinyanLi,GuozhuDong,K.Ramamohanarao.DeEPs:anewinstance-basedlazydiscoveryandclassificationsystem[J].MachineLearning, 2004, 54(2): 99-124.

[5]F.Berzal,J.C.Cubero,S.J.Maria.Ahybridclassificationmodel[J].MachineLearning, 2004, 54(1): 67-92.

[6]S.Haykin.Neuralnetworks:acomprehensivefoundation[J].ComputationSystems, 1999, 4(2): 188- 190.

[7]H.Fan,K.Ramamohanara.Fastdiscoveryandthegeneralizationofstrongjumpingemergingpatternsforbuildingcompactandaccurateclassifiers[J].IEEETransactiononKnowledgeandDataEngineering, 2006, 18(6): 721-737.

[8]許洪濤. 一種基于eEPS的中文文本自動(dòng)分類算法[D]. 鄭州: 鄭州大學(xué), 2006.

[9]施萬鋒, 胡學(xué)鋼, 俞奎. 一種面向高維數(shù)據(jù)的迭代式lasso方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(7): 4463-4466.

[10]施萬鋒, 胡學(xué)鋼, 俞奎. 一種面向高維數(shù)據(jù)的均分式lasso方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(1): 157-161.

[11]余映, 王斌, 張立明. 一種面向數(shù)據(jù)學(xué)習(xí)的快速PCA算法[J]. 模式識(shí)別與人工智能, 2009, 22(4): 567-573.

[12]唐懿芳, 鐘達(dá)夫. 主成分分析方法對數(shù)據(jù)進(jìn)行預(yù)處理[J]. 廣西師范大學(xué)學(xué)報(bào), 2002, 3(1): 223-225.

[13]張麗新, 王家廞, 趙雁南, 等. 基于Relief的組合式特征選擇[J]. 復(fù)旦學(xué)報(bào)(自然科學(xué)版), 2004, 43(5): 893-898.

[14]吳浩苗, 尹中航, 孫富春.Relief算法在筆記識(shí)別的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用, 2006, 26(1): 174-177.

[15]蔣玉嬌, 王曉丹, 王文軍, 等. 一種基于PCA和ReliefF的特征選擇方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(26): 170-172.

[16]陸景輝. 基于信息理論的特征選擇算法研究[D]. 北京: 北京交通大學(xué), 2007.

EP Pattern Classification Algorithm for High Dimensional Data Based on PCA-ReliefF Computer Engineering and Applications

CHENG Yu-sheng, HU Fei, CHENG Bai-qiu

(School of Computer and Information, Anqing Teachers College, Anqing 246133, China)

For high dimensional data sets, PREP (PCA-ReliefF for EP) algorithm is presented. Firstly, the feature dimension reduction is realized by using the PCA and ReliefF algorithm. Then, higher precision and smaller EP classifier is constructed by using the EP model of ideological construction. Finally, the method of PREP is tested by using the standard data. The results show that structured classifier constructed by this method has a great improvement in the prediction accuracy and running time for the high dimensional data.

classification model, feature selection, PCA-ReliefF, EP model, PREP algorithm

2015-04-07

程玉勝，男，安徽桐城人，博士，安慶師范學(xué)院計(jì)算機(jī)與信息學(xué)院教授，碩士生導(dǎo)師，主要從事文本挖掘、粗糙集理論等方向的研究；胡飛，男，安徽安慶人，安慶師范學(xué)院計(jì)算機(jī)與信息學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等。

時(shí)間：2016-1-5 13:01 網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160105.1301.008.html

TP182

A

1007-4260(2015)04-0028-05

10.13757/j.cnki.cn34-1150/n.2015.04.008

項(xiàng)目名稱： 安徽省高等學(xué)校自然科學(xué)基金(KJ2013A177)。