• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于BSO-OS算法的兩階高維數(shù)據(jù)特征選擇

    2020-04-24 02:25:48田浩楠
    計算機工程與設(shè)計 2020年3期
    關(guān)鍵詞:高維特征選擇子集

    田浩楠,周 暉

    (南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)

    0 引 言

    隨著云計算和大數(shù)據(jù)的迅速發(fā)展,海量數(shù)據(jù)不斷呈現(xiàn),數(shù)據(jù)維度不斷增加[1]。特征選擇從給定特征集合中選取相關(guān)特征子集,以降低數(shù)據(jù)維度、簡化學(xué)習(xí)模型、加速學(xué)習(xí)過程[2,3]。

    高維數(shù)據(jù)的搜索空間遠大于一般數(shù)據(jù),其特征選擇非常困難[4]。群集智能(swarm intelligence, SI)搜索能力強、魯棒性好,而被應(yīng)用于高維數(shù)據(jù)特征選擇。文獻[5,6]將位置更新與變異機制以及模糊規(guī)則引入二進制PSO(binary particle swarm optimization, BPSO)算法以搜索特征子集。文獻[7]采用PSO算法搜索特征子集,該算法引入新的局部搜索機制和重置gbest機制以提高搜索能力。文獻[8,9]將PSO算法和過濾式方法相結(jié)合來選取特征子集。文獻[10]提出一種兩階方法,首先采用F統(tǒng)計量選擇特征,然后使用BPSO算法在這些特征中選取最優(yōu)特征子集。

    然而,上述方法存在以下不足:其一,僅采用群集智能選取的特征子集特征數(shù)量多,且運行效率差;其二,采用群集智能和過濾式方法相結(jié)合選取特征子集,雖然取得良好效果,但沒有考慮多特征間的冗余性;其三,兩階方法的第1階段所選特征數(shù)量需人工指定。

    針對上述問題,提出基于BSO-OS(brain storm optimization in objective space)的兩階高維數(shù)據(jù)特征選擇算法(two-stage feature selection algorithm for high-dimensional data based on BSO-OS, BSFS)。首先,針對高維數(shù)據(jù)特征選擇問題設(shè)計BSO-OS算法,并采用BSO-OS算法搜索分類性能較好、特征數(shù)量較少的特征子集;然后,采用快速近似聯(lián)合互信息(fast approximate joint mutual information, FAMIR)對上述所選特征子集中分類精度最高的特征子集進行特征排序,去除冗余、不相關(guān)特征。在6個高維數(shù)據(jù)集上進行實驗,結(jié)果驗證了所提算法的有效性。

    1 BSO-OS算法

    BSO(brain storm optimization)是一種新的群集智能算法[11]。該算法模擬人類創(chuàng)造性解決問題的思路和過程,是一種很有潛力的群集智能算法。而BSO-OS算法使用簡單分類操作代替BSO算法中的聚類算法,特別適用于解決高維問題[12]。

    BSO-OS算法中,新解是對所選解加上高斯隨機值而生成,如式(1)所示

    (1)

    (3)

    其中, logsig() 是S型對數(shù)傳遞函數(shù),T為最大迭代次數(shù),t為當(dāng)前迭代次數(shù),k用來改變logsig() 的斜率, rand() 產(chǎn)生(0,1)間的隨機值。

    然而BSO-OS算法適用于連續(xù)函數(shù)優(yōu)化,而特征選擇是組合優(yōu)化問題,根據(jù)高維數(shù)據(jù)特征選擇的特點設(shè)計BSO-OS算法。

    (1)個體初始化:每一個個體表示一個所選特征子集,個體初始化為:Xi=[x1,…,xi,…,xn], 其中Xi表示第i個個體,n為特征數(shù)量,xi為隨機產(chǎn)生的(0,1)間的值表示選擇第i個特征的概率。使用式(4)對個體每個維度進行離散化

    (4)

    (2)個體更新:使用式(1)對個體進行更新,對更新后的個體的每個維度使用式(5)進行離散化

    (5)

    其中, sig() 是S型傳遞函數(shù), rand() 產(chǎn)生(0,1)間的隨機值。

    (3)擾動更新:BSO-OS算法中,擾動更新過程僅改變一個維度的值,這在個體維度很高時并不適用。因此,本文在擾動更新時改變特征數(shù)量1%個維度的值,其值改變?nèi)缡?6)所示

    (6)

    2 FAMIR

    基于信息準則的方法中,推薦使用聯(lián)合互信息(joint mutual information,JMI)[13],JMI計算公式為

    (7)

    其中,F(xiàn)i是候選特征,F(xiàn)j是已選特征,S是已選特征集合,Y是類標簽。

    然而JMI計算復(fù)雜度是特征數(shù)量的二次方,這限制其在高維數(shù)據(jù)中的應(yīng)用。針對上述問題,文獻[14]提出JMI快速近似算法即FAMIR,以加速JMI計算。該方法主要思想是對每項I(Fi,Fj;Y) 計算上下界,利用其上下界近似求其值。上界計算公式為

    (8)

    其中,Q={I(Fi,Fj),I(Fi,Y),I(Fj,Y)}。

    下界計算公式為

    (9)

    因此I(Fi,Fj;Y) 近似計算為

    I(Fi,Fj;Y)=β1L(Fi,Fj;Y)+β2U(Fi,Fj;Y)+β0

    (10)

    其中,β0、β1、β2為參數(shù)。

    計算候選特征Fi的JMI值時,首先計算前λ項I(Fi,Fj;Y) 的值及其上下界(λ一般取特征數(shù)量的5%),然后采用最小二乘法計算每一個β參數(shù)。在隨后每項I(Fi,Fj;Y) 計算中使用式(10)近似計算以達到加速目的。

    3 BSFS算法

    群集智能由于搜索能力強、魯棒性好而在高維數(shù)據(jù)特征選擇中得到應(yīng)用,但僅采用群集智能搜索的特征子集特征數(shù)量多,而過濾式方法能有效去除不相關(guān)和冗余特征,因而提出將群集智能和過濾式方法相結(jié)合的BSFS算法。

    3.1 適應(yīng)度函數(shù)

    個體迭代更新過程中,個體優(yōu)劣是由適應(yīng)度函數(shù)決定。采用式(11)所示適應(yīng)度函數(shù)對特征子集進行計算,其中μ為加權(quán)系數(shù)

    fitness=μ×balanced_accuracy+(1-μ)×distance

    (11)

    其中

    (12)

    其中,n是不同類的數(shù)量,TPi是類i中被正確分類的樣本數(shù)量, |Si| 是類i的樣本總數(shù)。計算算法產(chǎn)生的候選特征子集的分類性能時采用K近鄰算法(K-nearest neighbor,KNN)。

    其中

    (13)

    其中

    (14)

    (15)

    Dis(Vi,Vj) 用于度量向量Vi和Vj之間的距離,采用向量Vi和Vj之間,對應(yīng)維度值相同的數(shù)量除以向量維度的值作為距離值。Db是每個樣本與不同類中最近樣本之間距離的平均值,Dw表示相同類中每個樣本與最遠樣本之間距離的平均值, |S| 是樣本總數(shù)。

    3.2 算法實現(xiàn)

    BSFS算法包括兩個階段:首先采用BSO-OS算法搜索特征子集,再對上述所選特征子集中分類精度最高的特征子集使用FAMIR。BSO-OS算法的具體過程如圖1所示,算法中采用式(11)所示適應(yīng)度函數(shù)對所選特征子集進行計算。

    圖1 BSO-OS算法的具體過程

    4 實驗設(shè)置和結(jié)果分析

    4.1 數(shù)據(jù)集

    為了測試所提算法性能,采用6個高維基因表達數(shù)據(jù)集,數(shù)據(jù)集信息見表1,數(shù)據(jù)集可從以下網(wǎng)址下載:http://www.gems-system.org。表1中第5列表示具有最少樣本的類其樣本占總樣本的百分比,第6列表示具有最多樣本的類其樣本占總樣本的百分比。

    從表1可見,相比特征數(shù)量,數(shù)據(jù)集樣本很少,且具有最多樣本的類和具有最少樣本的類,其樣本百分比差異很大。這些因素導(dǎo)致高維數(shù)據(jù)集的特征選擇非常困難。

    4.2 實驗配置和參數(shù)設(shè)置

    實驗中,采用k=3的KNN算法。計算分類精度時,使用十折交叉驗證,其中一折用作測試集,其余用作訓(xùn)練集,最后分類精度取10次測試集上的平均。對于每個數(shù)據(jù)集,進行30次獨立運行。考慮到計算和存儲資源,將個體數(shù)量n限制為150。實驗中,BSO-OS算法參數(shù)設(shè)置見表2。

    4.3 實驗結(jié)果與分析

    本文使用式(11)所示適應(yīng)度函數(shù),其中參數(shù)μ的取值會影響B(tài)SO-OS算法所選特征子集的性能,為選取更好μ值,首先比較μ取不同值,即μ取0.5、0.6、0.7、0.8、0.9和1.0時,BSO-OS算法所選特征子集的性能,結(jié)果見表3。

    在表3中,首先比較每個數(shù)據(jù)集上μ取不同值時所選特征子集的平均精度和平均特征數(shù)量,若平均精度越高同

    表1 實驗所用數(shù)據(jù)集

    表2 實驗參數(shù)值

    表3 μ取不同值時的實驗結(jié)果

    時平均特征數(shù)量越少,則對應(yīng)μ值越好。但是僅通過平均精度和平均特征數(shù)量有時很難區(qū)分不同μ值的優(yōu)劣,因此表3添加最好精度一列,該列表示所選特征子集中獲得的最好分類精度,同時給出該精度對應(yīng)特征子集的特征數(shù)量。添加該列進行比較的原因是第2階段僅對第1階段所選分類精度最高的特征子集使用FAMIR。若通過平均精度和平均特征數(shù)量不能區(qū)分μ值優(yōu)劣,則比較所選特征子集的最好分類精度,最好分類精度越高則對應(yīng)μ值越好。每個數(shù)據(jù)集的最好μ值已用粗體標出。從表3可見,μ取0.7時在6個數(shù)據(jù)集的4個上獲得最好結(jié)果,μ取0.8時在6個數(shù)據(jù)集的兩個上獲得最好結(jié)果。為方便起見,所有數(shù)據(jù)集取相同μ值,因此,下列所有實驗取μ=0.7。

    表4給出所提算法的實驗結(jié)果。其中“Full”表示使用數(shù)據(jù)集的所有特征,“BSO-OS”表示第1階段采用BSO-OS算法選擇的特征子集中分類精度最高的特征子集,“BSFS”表示所提算法的最終結(jié)果。從表4可見,所提算法在全部數(shù)據(jù)集相比原始數(shù)據(jù)集選出很少特征,同時所選特征子集的分類精度都有提高。在Prostate_Tumor數(shù)據(jù)集,所選特征子集的特征數(shù)量只有原始數(shù)據(jù)集的2.2%,但分類精度卻提高10.6%。除9_Tumors數(shù)據(jù)集,在其余數(shù)據(jù)集,所選特征子集的特征數(shù)量都不超過原始數(shù)據(jù)集的10%,同時分類精度都有提高。在11_Tumors數(shù)據(jù)集,分類精度提高11.2%,但特征數(shù)量只有原始數(shù)據(jù)集的4.9%。圖2給出所提算法在每個數(shù)據(jù)集所選特征子集的分類精度隨特征數(shù)量的變化,其中橫坐標表示所選特征子集的特征數(shù)量,縱坐標表示所選特征子集的分類精度。表4還可看出,所提算法中每階算法的有效性,采用BSO-OS算法選出的特征子集相比原始數(shù)據(jù)集具有較少特征,同時特征子集的分類精度都有提高,在Leukemia2數(shù)據(jù)集,BSO-OS算法選出的特征子集的特征數(shù)量只有原始數(shù)據(jù)集的10.8%,但分類精度提高9.4%。對BSO-OS算法選出的特征子集使用FAMIR算法后,可以得到特征數(shù)量更少的特征子集,同時特征子集的分類精度都有提高。在Prostate_Tumor數(shù)據(jù)集,使用FAMIR算法后,特征子集的特征數(shù)量減少92.0%,但分類精度略有提高。

    表4 所提算法的實驗結(jié)果

    圖2 所選特征子集的分類精度隨特征數(shù)量的變化

    本文將BSO-OS算法應(yīng)用于高維數(shù)據(jù)特征選擇,為驗證其有效性,與標準BPSO算法的實驗結(jié)果進行比較,結(jié)果見表5。從表5可見,在全部數(shù)據(jù)集,采用BSO-OS算法選出的特征子集的平均分類精度和平均特征數(shù)量都優(yōu)于BPSO算法選出的特征子集。在Lung_Cancer數(shù)據(jù)集,BSO-OS算法選出的特征子集的平均特征數(shù)量只有BPSO算法的46.3%,但平均分類精度卻提高2.0%。在9_Tumors數(shù)據(jù)集,BSO-OS算法比BPSO算法選出的特征子集的平均分類精度高11.1%,但平均特征數(shù)量卻只有BPSO算法的65.1%。同時,將BSO-OS算法與BPSO算法的運行時間進行比較,結(jié)果如圖3所示,該圖中運行時間指的是平均每輪的運行時間。從圖3可見,在全部數(shù)據(jù)集,BSO-OS算法的運行效率都優(yōu)于BPSO算法,其運行時間分別只有 BPSO 算法的51%,72%,63%,54%,62%,63%。

    為進一步驗證所提算法的有效性,分別與一階方法(PSO-LSSU)[8]和兩階方法(CDMC)[10]所選特征子集中分類精度最高的特征子集進行比較。表6給出所提算法與PSO-LSSU和CDMC在6個數(shù)據(jù)集的實驗結(jié)果。為與CDMC進行公平比較,在表6的第4行給出所提算法得到與CDMC分類精度相似時的特征子集的特征數(shù)量和分類精度,正如“BSFS(*)”一行所示。

    從表6可見,與PSO-LSSU的結(jié)果相比,在全部數(shù)據(jù)集,所提算法所選特征子集的特征數(shù)量和分類精度都優(yōu)于PSO-LSSU所選特征子集。與CDMC的結(jié)果相比,在6個數(shù)據(jù)集的4個上所提算法所選特征子集的特征數(shù)量和分類精度優(yōu)于CDMC所選特征子集,在Prostate_Tumor數(shù)據(jù)集,在分類精度略高的情況下,所提算法所選特征子集的特征數(shù)量只有CDMC所選特征子集特征數(shù)量的5.2%。在Leukemia2數(shù)據(jù)集具有與CDMC相似的性能,僅在9_Tumors數(shù)據(jù)集的性能略差于CDMC。

    表5 BSO-OS和BPSO的對比結(jié)果

    圖3 BSO-OS與BPSO運行時間對比

    圖4給出3種方法各自的運行時間,其中運行時間指的是平均每輪的運行時間。為公平比較,分別將CDMC第1階段和所提算法第2階段的運行時間平均到每輪運行時間中。從圖4可見,所提算法在全部數(shù)據(jù)集的運行效率優(yōu)于PSO-LSSU,與CDMC的運行效率相比,所提算法在6個數(shù)據(jù)集的3個上運行效率占優(yōu),在Lung_Cancer數(shù)據(jù)集具有類似的運行效率,在Leukemia2和Prostate_Tumor數(shù)據(jù)集,運行效率略差。

    5 結(jié)束語

    針對高維數(shù)據(jù)特征選擇問題,將BSO-OS和FAMIR算法相結(jié)合,提出一種兩階特征選擇算法BSFS。實驗結(jié)果表明:所提算法能有效實現(xiàn)BSO-OS和FAMIR兩者的優(yōu)勢互補,在第1階段,BSO-OS算法在高維數(shù)據(jù)特征選擇中具有更好的搜索能力和運行效率;在第2階段,F(xiàn)AMIR算法能有效去除特征子集中的不相關(guān)和冗余特征。整個算法分類精度高,同時具有良好的運行效率。

    表6 BSFS與PSO-LSSU和CDMC的對比結(jié)果

    圖4 3種方法運行時間對比

    猜你喜歡
    高維特征選擇子集
    由一道有關(guān)集合的子集個數(shù)題引發(fā)的思考
    拓撲空間中緊致子集的性質(zhì)研究
    關(guān)于奇數(shù)階二元子集的分離序列
    一種改進的GP-CLIQUE自適應(yīng)高維子空間聚類算法
    基于加權(quán)自學(xué)習(xí)散列的高維數(shù)據(jù)最近鄰查詢算法
    Kmeans 應(yīng)用與特征選擇
    電子制作(2017年23期)2017-02-02 07:17:06
    聯(lián)合互信息水下目標特征選擇算法
    一般非齊次非線性擴散方程的等價變換和高維不變子空間
    每一次愛情都只是愛情的子集
    都市麗人(2015年4期)2015-03-20 13:33:22
    高維Kramers系統(tǒng)離出點的分布問題
    文山县| 白河县| 庄浪县| 连平县| 桃园县| 莒南县| 赤壁市| 米泉市| 江川县| 安平县| 五家渠市| 宁都县| 永安市| 遂昌县| 法库县| 金华市| 淮滨县| 乌拉特后旗| 福贡县| 丽水市| 江山市| 宜章县| 潜山县| 周至县| 姚安县| 建水县| 望江县| 阜康市| 青浦区| 龙井市| 岑巩县| 道孚县| 织金县| 凌源市| 彰武县| 府谷县| 安仁县| 榆社县| 新干县| 广南县| 凉城县|