模式識別中的特征提取研究-

1、技術(shù)創(chuàng)新中文核心期刊微計(jì)算機(jī)信息(測控自動化2008年第24卷第1-1期360元/年郵局訂閱號:82-946現(xiàn)場總線技術(shù)應(yīng)用200例模式識別模式識別中的特征提取研究Research on Feature Selection in Pattern Matching(1.南昌大學(xué);2.江西師范大學(xué)曾慶鵬1吳水秀2王明文2ZENG QINGPENG WU SHUIXIU WANG MINGWEN摘要:特征提取是模式識別中的關(guān)鍵技術(shù)之一,本文提出了一種基于改進(jìn)ReliefF 算法的主成分特征提取方法,通過該方法進(jìn)行主特征特征提取可以有效降維,大大減輕了后續(xù)的分類器的工作量,同時(shí)也有助于提高分類器的分類

2、精度。關(guān)鍵詞:模式識別;特征提取;主成分分析中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A Abstract:Feature Selection is one of key technologies in Pattern Matching,a method of principal feature selection based on reforma-tive algorithm ReliefF is presented in this paper,using this method to select the principal feature will reduce the dimensionali

3、ty sig-nificantly,and the computing cost of the classify program can be decreased ,at the same time,the precision of the classify program can be increased.Key words:Pattern Matching,Feature Selection,Principal Component Analysis文章編號:1008-0570(200801-1-0220-02概述主成分分析是特征提取中很常用的一種變換方法,該方法通過使用變換后的幾個(gè)主要的成

4、分來代替原始的特征信息,變換后的主成分之間是相互獨(dú)立的,并且每個(gè)主成分都是變換前所有特征的一個(gè)線性組合。如果用變換后的所有主成分來代替原始的特征信息,一般沒有信息的損失,因此被廣泛應(yīng)用到模式匹配的相關(guān)領(lǐng)域中。但很多情況下,通常選擇少數(shù)幾個(gè)包含大部分原始特征信息的主要成分來代替原始的特征信息,這樣做雖然損失了部分特征信息,但可以使用更少的特征變量來代替原始的較多的特征變量,這樣可以大大減輕后續(xù)分類器的計(jì)算量,同時(shí)對提高分類器的性能也是有幫助的。本文提出了一種基于改進(jìn)ReliefF 算法的主特征提取方法。1ReliefF 算法及其實(shí)現(xiàn)ReliefF 算法的主要思想是:根據(jù)屬性值在區(qū)分相互靠近的樣本

5、實(shí)例的能力上來對屬性的質(zhì)量進(jìn)行評價(jià),首先隨機(jī)地從訓(xùn)練數(shù)據(jù)中選擇一個(gè)樣本實(shí)例R,然后在訓(xùn)練數(shù)據(jù)中找出和樣本實(shí)例R 在同一類中的k 個(gè)最近鄰的樣本實(shí)例,把這k 個(gè)樣本實(shí)例稱作Nhits,然后在訓(xùn)練數(shù)據(jù)中分別找出和樣本實(shí)例R 不在同一個(gè)類中的k 個(gè)最近鄰的樣本實(shí)例,把這些k 個(gè)樣本實(shí)例稱作Nmisses,每個(gè)屬性A 的權(quán)重的更新依賴于隨機(jī)選擇的樣本實(shí)例R 、和R 在同一類呂的k 個(gè)近鄰NHits 以及和R 不在同一類中的若干個(gè)k 個(gè)近鄰Nmisses,在屬性權(quán)重的更新公式中所有的NHits 和NMisses 的貢獻(xiàn)是經(jīng)過平均的。改進(jìn)后的ReliefF 算法如下:set all weights WA:

6、=0.0;for i:=1to m do beginrandomly select an instance R i ;find k nearest hits H j ;for each class class(R i dofrom class C find k nearest misses M j (C ;for A:=1to a do;end;其中diff(A,I 1,I 2函數(shù)計(jì)算屬性A 與實(shí)例I 1和I 2的區(qū)分度,其初始值定義如式(1:(1迭代計(jì)算如式(2:(22主成分選擇設(shè)X 1,X 2,X p 為p 個(gè)隨機(jī)變量,記X=(X 1,X 2,X p T ,令為X 的協(xié)方差矩陣,進(jìn)行式(3

7、的線性變換:(3可以得到:顯然我們希望Y 1是X 1,X 2,X p 的所有線性函數(shù)中方差最大的,此處限制a 1為單位向量,即有,這樣可以使得達(dá)到最大,此時(shí)就稱Y 1為第一主成分。如果第一主成分所包含的信息還不夠多,不足以代表原始的p 個(gè)變量,就要考慮使用Y 2、Y 3、Y 4等,一般來說,X 的第i 主成分指:在限制條件和下尋找a i ,使得達(dá)到最大。曾慶鵬:講師碩士基金項(xiàng)目:國家自然科學(xué)基金(60663007220- 郵局訂閱號:82-946360元/年技術(shù)創(chuàng)新模式識別PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注3基于主成分分析的特征提取基于前面介紹的原理,下面給出基于主成分分析的特征

8、提取方法的具體過程。第一步:去除無關(guān)特征變量。利用ReliefF 算法去掉原始特征中那些與分類不相關(guān)的特征。經(jīng)過第一步處理后得到的數(shù)據(jù)矩陣為式(4:(4其中,X n ×p 表示一個(gè)n 行p 列的一個(gè)矩陣。代表n 個(gè)樣本實(shí)例,并且每個(gè)樣本實(shí)例是p 維的。x ij 表示第j 人特征變量在第i 個(gè)樣本實(shí)例上的觀測值,X j 代表第j 個(gè)特征變量的觀測向量,I i 代表第i 個(gè)樣本實(shí)例的觀測向量。第二步:數(shù)據(jù)規(guī)一化處理。將矩陣X n ×p 轉(zhuǎn)換為矩陣Z n ×p ,變換公式為式(5:(5其中,x j 代表矩陣X n ×p 中第j 列(第j 個(gè)特征變量的均值,代表

9、矩陣X n ×p 中第j 個(gè)特征的標(biāo)準(zhǔn)差。第三步:進(jìn)行主成分變換。先計(jì)算矩陣Z n ×p 的協(xié)方差矩陣,然后計(jì)算協(xié)方差矩陣的特征值和特征向量,特征值從大到小依次為。相應(yīng)的特征向量為。接著選擇出合適數(shù)量的特征向量并構(gòu)成變換矩陣U,最終得到變換后的數(shù)據(jù)矩陣Y 即:顯然,Y 是n 行d 列的矩陣,y ij 表示在變換后的特征空間中第j 個(gè)特征變量在第i 個(gè)樣本實(shí)例上的值。Y j 代表在變換后的特征空間中第j 個(gè)特征向量,也就是變換后的第j 主成分。S i 代表在變換后的特征空間中第i 個(gè)實(shí)例向量。還可以看出,變換前數(shù)據(jù)矩陣的大小為n ×p,變換后的數(shù)據(jù)矩陣大小為n &#

10、215;d,又因?yàn)閐 p,所以在相同的樣本實(shí)例的情況下,變換后的數(shù)據(jù)矩陣的特征維數(shù)小于等于變換前的數(shù)據(jù)矩陣的特征維數(shù)。4實(shí)驗(yàn)及總結(jié)實(shí)驗(yàn)數(shù)據(jù)采用1999年KDD 入侵檢測競賽的標(biāo)準(zhǔn)數(shù)據(jù)集的部分?jǐn)?shù)據(jù),實(shí)驗(yàn)結(jié)果如表(1所示:表(1主成分分析結(jié)果由表可以看出,變換后的第一主成分貢獻(xiàn)率達(dá)到28.625%,第二主成分貢獻(xiàn)率達(dá)到16.671%,事實(shí)上,前10個(gè)主成分貢獻(xiàn)率達(dá)到86.304%,這就是說,可以用10個(gè)主成分的數(shù)據(jù)信息來描述出變換前的20維特征數(shù)據(jù)的變化狀態(tài)。將20個(gè)特征變量降維成10個(gè)主成分,大大減輕了后續(xù)的分類器的工作量,同時(shí)也有助于提高分類器的分類精度。本文作者創(chuàng)新點(diǎn)在于利用改進(jìn)的Relie

11、fF 算法進(jìn)行主成分特征提取并取得較好的實(shí)驗(yàn)效果,該算法可用于模式識別領(lǐng)域。參考文獻(xiàn)4Robnik Sikonjia.Speeding up Relief algorithm with k-d tree.Proceedings of Electrotehnical and Computer Science Conference (ERK98.:137-140.5陳德釗,多元數(shù)據(jù)處理M,化學(xué)工業(yè)出版社,北京:1984.4作者簡介:曾慶鵬(1974-,男,江西吉水人,講師,碩士,研究方向:網(wǎng)絡(luò)與信息安全;吳水秀(1975-,女,江西南豐人,講師,碩士,研究方向:信息系統(tǒng);王明文(1965-,男,江

12、西南康人,教授,博士,研究方向:信息檢索,文本分類。Biography:Zeng Qing-peng(1974-,male,han,Jiangxi Province,NanChang University,Master degree,Major in computer application,Research area:network and information security.Wu Shui-xiu(1975-,female,han,Jiangxi Province,Jiangxi Normal University,Master degree,Major in computer ap

13、plication,Research area:information system.Wang Ming-wen (1965-,male,han,Jiangxi Province,Jiangxi Normal University,Doctor degree,Major in computer application,Research area:information Retrieval,text classify .(330031江西南昌南昌大學(xué)信息工程學(xué)院曾慶鵬(330027江西南昌江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院吳水秀王明文(School of Information Engineering ,NanChang University,NanChang 330031,ChinaZeng Qingpeng(College of Computer Information and Engineering ,Jiangxi Normal University ,NanChang 33