程玉勝，胡 飛，程百球

(安慶師范學院 計算機與信息學院，安徽 安慶 246133)

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

程玉勝，胡 飛，程百球

(安慶師范學院 計算機與信息學院，安徽 安慶 246133)

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

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

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

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

1 EP模式分類

1.1EP模式基本概念

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

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

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

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

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

表1 EP模式的事例

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

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

broad)(RING_NUMBER=one)}，

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

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

close),(VEIL_COLOR=white)}，

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

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

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

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

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

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

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

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

PREP算法的主要步驟：

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

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

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

步驟3 隨機確定D1中的一個樣本X；

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

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

(1)

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

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

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

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

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

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

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

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

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

agg＿score(S,C)=

(2)

(3)

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

圖2 PREP分類算法流程

3 實驗結(jié)果及析

3.1 實驗結(jié)果

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

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

表3 CAEP和PREP實驗對比

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

3.2 實驗結(jié)果分析

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

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

4 結(jié)束語

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

[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]. 經(jīng)濟研究導刊, 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]. 鄭州: 鄭州大學, 2006.

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

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

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

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

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

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

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

[16]陸景輝. 基于信息理論的特征選擇算法研究[D]. 北京: 北京交通大學, 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

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

時間：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

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