面向高維數據PCA-ReliefF的EP模式分類算法

程玉勝，胡 飛，程百球

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

面向高維數據PCA-ReliefF的EP模式分類算法

程玉勝，胡 飛，程百球

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

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

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

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

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

1 EP模式分類

1.1EP模式基本概念

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

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

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

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

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

表1 EP模式的事例

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

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

broad)(RING_NUMBER=one)}，

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

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

close),(VEIL_COLOR=white)}，

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

1.2 EP模式分類器構造過程

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

EP模式分類器構造過程如圖1所示。

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

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

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

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

PREP算法的主要步驟：

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

步驟1 對隨機產生的訓練數據集D0進行主成分提取，將權值較大的前s個主成分存入數據集D1；

步驟2 首次將D1各特征權值歸零；

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

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

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

(1)

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

步驟7 按順序保留權值最大的前d個特征構成特征集；

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

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

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

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

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

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

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

agg＿score(S,C)=

(2)

(3)

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

圖2 PREP分類算法流程

3 實驗結果及析

3.1 實驗結果

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

表2 實驗使用的數據集描述

表3 CAEP和PREP實驗對比

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

3.2 實驗結果分析

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

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

4 結束語

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

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

[2]馬紅娟, 趙秀蘭, 孫亞萍, 等. 基于數據挖掘技術的概率統計教學研究[J]. 經濟研究導刊, 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]施萬鋒, 胡學鋼, 俞奎. 一種面向高維數據的迭代式lasso方法[J]. 計算機應用研究, 2011, 28(7): 4463-4466.

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

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

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

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

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

[15]蔣玉嬌, 王曉丹, 王文軍, 等. 一種基于PCA和ReliefF的特征選擇方法[J]. 計算機工程與應用, 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

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

時間：2016-1-5 13:01 網絡出版地址：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)。