作者：Geppetto

前面我們介紹了特征選擇(Feature Selection，FS)與離散化數(shù)據(jù)的重要性，總覽的介紹了PSO在FS中的重要性和一些常用的方法，介紹了FS與離散化的背景，介紹本文所采用的基于熵的切割點(diǎn)和最小描述長度原則(MDLP)。今天我們來學(xué)習(xí)利用PSO來進(jìn)行離散化特征選擇的一些方法。今天我們會介紹EPSO與PPSO。

EPSO和PPSO都遵循圖一所示的基本步驟。初始化后，對粒子進(jìn)行迭代評估和更新，直到滿足停止條件為止。為了對粒子進(jìn)行評價(jià)，首先對訓(xùn)練數(shù)據(jù)進(jìn)行離散化，并根據(jù)進(jìn)化的切點(diǎn)選擇特征。然后將轉(zhuǎn)換后的數(shù)據(jù)放入學(xué)習(xí)算法中，計(jì)算出適應(yīng)度。基于這種適應(yīng)性，pbest和gbest被更新并用于更新粒子的位置。

圖一

在這兩種方法中離散化和FS步驟的工作原理是相同的。為實(shí)現(xiàn)離散化，如果特征值小于某個(gè)截點(diǎn)，則將其轉(zhuǎn)換為0；否則，它就是1。如果一個(gè)特性的所有值都轉(zhuǎn)換為相同的離散值，那么它就被認(rèn)為是一個(gè)無關(guān)的特性，因?yàn)樗荒軈^(qū)分不同類的實(shí)例。FS是通過消除這些無用的特性來完成的。在整個(gè)離散化數(shù)據(jù)的分類性能改進(jìn)的基礎(chǔ)上，對剩余的離散特征進(jìn)行了評價(jià)。

A.EPSO

EPSO的主要思想是使用BBPSO直接演化出一個(gè)可以在相應(yīng)的特征值范圍[MinF···MaxF]內(nèi)任何值的切點(diǎn)。每個(gè)粒子的位置表示一個(gè)候選解，它是一個(gè)與問題的維數(shù)相對應(yīng)的n維的實(shí)向量。圖二給出了一個(gè)粒子位置及其相應(yīng)候選解的例子。在這個(gè)例子中，粒子的第一個(gè)維度，表示第一個(gè)特性(F1)的切割點(diǎn)，需要在范圍內(nèi)有一個(gè)值[8.5,25.7]。如果一個(gè)特性F的更新點(diǎn)超出了這個(gè)范圍，它將被設(shè)置到最近的邊界。

圖二

(1)粒子初始化：由于在高維數(shù)據(jù)上的多變量離散化的搜索空間是巨大的。這意味著對于那些在初始候選方案中未被選中的特性，它們的切點(diǎn)將被設(shè)置為相應(yīng)特性的最大值。對于其他選擇的特性，它們的切點(diǎn)是使用滿足MDLP的最好的基于熵的切割點(diǎn)初始化的。原則上，它們可以根據(jù)對應(yīng)特性范圍內(nèi)的任何值進(jìn)行初始化。然而，完全隨機(jī)的初始切點(diǎn)可能導(dǎo)致收斂速度較慢。此外，特征的最佳切點(diǎn)的信息增益是其相關(guān)性的指標(biāo)。因此，具有較大信息增益的特性在初始化過程中被選擇的概率更大。

(2)粒子評價(jià)：基于粒子所產(chǎn)生的切點(diǎn)，訓(xùn)練數(shù)據(jù)轉(zhuǎn)換為離散值的新訓(xùn)練集和較少的特征數(shù)，這要?dú)w功于消除特征，其切割點(diǎn)等于最小值或最大值。例如，在圖2中，F3切割點(diǎn)等于它的最大值，F5的切點(diǎn)等于它的最小值，這兩個(gè)特征都將被丟棄。

然后根據(jù)轉(zhuǎn)換訓(xùn)練集的分類精度，對每個(gè)粒子的離散化和FS解進(jìn)行評估，通過對整個(gè)離散數(shù)據(jù)的評估，提出的方法可以對所有選定特征的分割點(diǎn)進(jìn)行評估，同時(shí)考慮特征交互。適應(yīng)度函數(shù)采用平衡分類精度，如下:

其中c是問題的類數(shù)，TPi是i類中正確識別的實(shí)例數(shù)，|Si|是類i的樣本量，所有類的權(quán)重均為1/c。

B.PPSO

在EPSO中，BBPSO可以自由地在相應(yīng)的范圍內(nèi)生成一個(gè)剪切點(diǎn)。這可能會導(dǎo)致一個(gè)巨大的搜索空間，特別是在多維數(shù)據(jù)的多變量方法中。因此，為了將搜索空間縮小到高度潛在的區(qū)域，在PPSO中，我們使用BBPSO來從每個(gè)特性的潛在斷點(diǎn)中選擇一個(gè)切點(diǎn)。潛在的切點(diǎn)是基于熵的切點(diǎn)，它們的信息增益滿足前面所講的MDLP準(zhǔn)則。每個(gè)特征可能有不同數(shù)量的可能的切割點(diǎn)，它們被計(jì)算并存儲在一個(gè)可能的切點(diǎn)表中。圖3給出了該表和粒子位置以及相應(yīng)候選方案的示例。每個(gè)粒子位置都是一個(gè)整數(shù)向量，表示所選的剪切點(diǎn)索引。因此，向量的大小等于原始特征的數(shù)量，而進(jìn)化的值需要介于1和相應(yīng)特征的潛在的切點(diǎn)數(shù)量之間。例如，在圖3中，第一個(gè)特性(F1)有兩個(gè)可能的剪切點(diǎn)，索引1和2。因此，粒子的第一個(gè)維度需要落在范圍[1,2]。如果它是2，那么切割點(diǎn)6.8被選擇來離散F1。

圖三

在更新過程中，如果一個(gè)維度的更新值不在切點(diǎn)索引范圍之外，則將其設(shè)置為0，這表明相應(yīng)的特性沒有一個(gè)好的切點(diǎn)，因此應(yīng)該被忽略。

(1)粒子初始化：每個(gè)粒子位置都被初始化為一個(gè)隨機(jī)特征子集，其中有一些被選中的特征，它們的切點(diǎn)索引與0不同。選中的特性將會將它們的切點(diǎn)索引設(shè)置為最佳MDLP剪切點(diǎn)的索引。與EPSO相似，具有較高信息增益的特性將有更高的選擇機(jī)會。

為了使PPSO通用到所有的問題，PPSO使用一個(gè)限制的大小為所有數(shù)據(jù)集。然后在進(jìn)化過程中，當(dāng)BBPSO似乎卡在局部最優(yōu)，如果當(dāng)前的gbest fitness比最后一個(gè)gbest fitness至少有10%的優(yōu)勢，BBPSO將被重新設(shè)置為更大的尺寸(縮放機(jī)制)。這個(gè)機(jī)制的目的是開始搜索小的特性子集，同時(shí)打開更大更好的功能子集的機(jī)會。

(2)粒子評估：基于每個(gè)特性的選定的切點(diǎn)索引，從潛在的切點(diǎn)表中檢索出切點(diǎn)值。然后用它來離散相應(yīng)的特征。但是，如果一個(gè)特性的進(jìn)化的剪切點(diǎn)索引為0，那么該特性就被認(rèn)為是未被選中的。因此，在圖3中，本例中沒有選擇F2和F4。

在EPSO中，分類精度被用來作為衡量每個(gè)粒子的適應(yīng)度指標(biāo)。這可能很難區(qū)分類與類之間的邊界相當(dāng)大的情況，使許多不同的模型獲得相同的精度。此外，雖然包裝器方法能夠產(chǎn)生高精度的解決方案，但過濾方法通常更快、更普遍。將這兩種方法的強(qiáng)度結(jié)合在評價(jià)函數(shù)中，有望產(chǎn)生更好的解決方案。此外，結(jié)合這兩種方法，還可以更好地區(qū)分特征子集之間的細(xì)微差別，提供更平滑的適應(yīng)度環(huán)境以方便搜索過程。然而，簡單地結(jié)合這些措施在計(jì)算上可能是不切實(shí)際的。因此，我們需要找到一種聰明的方法來組合它們，而不需要更多的運(yùn)行時(shí)間。在常用的濾波方法中，距離是一種多變量測量方法，可以對特征集的判別能力進(jìn)行評估，并將其作為KNN的基本測量方法。因此，將該方法與KNN包裝方法結(jié)合起來不會增加計(jì)算時(shí)間，因?yàn)榫嚯x測量只計(jì)算一次，但使用兩次。

適應(yīng)度函數(shù)使用兩種平衡分類精度和距離測量加權(quán)系數(shù)(μ)與測量的距離,如下所示,用于最大化之間的距離不同的類的實(shí)例(DB)和減少之間的距離相同的類的實(shí)例(DW)。DB和DW采用以下公式計(jì)算:

其中Dis(Vi, Vj)是兩個(gè)向量Vi和Vj之間的距離。在本文中，我們使用兩個(gè)二進(jìn)制向量之間的匹配或重疊的比例作為它們之間的距離。

參考文獻(xiàn)：

文章：“A New Representation in PSO for Discretization-Based Feature Selection”

作者：Binh Tran, Student Member, IEEE, Bing Xue, Member, IEEE, and Mengjie Zhang, Senior Member, IEEE

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的python特征选择pso_粒子群优化算法(PSO)之基于离散化的特征选择(FS)（三）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。