论文部分内容阅读
摘要：文章以获得最佳特征分类效果为前提，针对ReliefF算法和蚁群算法，对其在特征基因选择中的运用展开了分析，从而确定了这两种方法对于特征分类的重要意义。
关键词：ReliefF；蚁群算法；特征基因选择方法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）32-0199-02
在确定特种基因选择方法时，一般会运用蚁群算法、ReliefF算法。其中，蚂蚁算法主要用于组合优化问题求解的元启发式方法，体现了非常强的健壮性、回馈控制、Agent系统等优势，此外，蚂蚁算法本身所体现的贪心策略、随机策略也在原来的基础上提高了全局搜索水平。通常在微阵列数据当中，经常出现标记错误或者类别标签错误的样品，这时便可以运用蚁群算法，利用不同特征的冗余性组织分析，将以上相关问题合理解决。Relief算法则是一种非常经典的Filter 方法，也是一种非常普及、高效率的维数约简法。Relief算法中包含了Relief、Relief和ReliefF，ReliefF更多使用与多分类、数据不足、噪声等问题的求解。Relief 算法的时间复杂程度比较低，使用时也不需要分类精度这种评价函数，然而因为该算法是以特征权重算法为基础，所以在选择特征时只是提升与标签相关的特征权重值，将权重值低特征予以剔除，这样一来就无法剔除冗余特征。基于此，下文出于对以上两种算法优良性能的考虑，以此为前提分析了特种基因的选择方法。
1 Relief 算法与特征基因选择方法结合
Relief算法在实际应用中是一种效率非常高的 Filter 算法，按照特征的重要程度，对其进行排序，以超出指定阈值的特征当做特征子集。在训练集中可以确定Relief的任意样本R，针对所有样本都有2个最近邻，分别来自于同类样本H和异类样本M[1]。如果选择的样本R和样本H在训练集当中出现与特征A相关的差异，那么特征A便会被赋予比较低的权重。样本R和M在训练集中发生关于特征A的差异，那么特征A便会被赋予比较高的权重。由此一来，特征A可以通过Relief 对权重W[A]进行更新，
即
W[A]=W[A]-diff（A，R，H）/m diff（A，R，M）/m （1）
在公式（1）中，m為随机抽样个数，diff函数代表给定函数2个样本差异。对 W[A]进行计算时，要使用m对其进行归一化处理，确保权重值在-1～1之间。
一旦特征属性是标称属性，这时对于diff（A，Ix，Iy）的计算需要按照如下公式进行：
[diff（A，Ix，Iy）=0；value（A，Ix）value（A，Iy）I；otherwise] （2）
一旦特征属性是数值属性时，这时对于diff（A，Ix，Iy）的计算需要按照如下公式计算：
[diff（A，Ix，Iy）=|value（A，Ix）-value（A，Iy）|max（A）-min（A）] （3）
如果在计算时使用传统的算法，那么会将计算局限在二分类问题中，也无法对数据缺失、噪声等问题进行很好的解决。早在20世纪末，便已经有专家将Relief算法进行了拓展，并且在原来的基础上提出了ReliefF算法，将以上提出的一系列问题全部解决。ReliefF算法将所有样本同类的k个最近邻差异值、其余异类k个最近邻差异值进行平均，以此来解决数据内噪声带来的影响。选择最近邻样本数主要体现的是ReliefF、Relief二者的基本差异，保证了ReliefF算法本身所具有的鲁棒性。
为了将数据缺失这一问题予以解决，相关专家对原有的diff（A，Ix，Iy）函数进行了优化，优化之后的函数可以有效计算出属性缺失值。如果样本Ix存在缺失值，那么diff（A，Ix，Iy）的计算则是如下形式：
[diff（A，Ix，Iy）=1-P（value（A，Iy）|class（Ix））] （4）
如果样本Ix与样本Iy均含有缺失值，那么diff（A，Ix，Iy）函数计算则要按照如下形式进行：
[diff（A，Ix，Iy）=|-V#value（A）P（V|class（Ix））×P（V|class（A，Iy）））] （5）
在公式（5）中，V代表全部样本内特征A的数值，ReliefF算法描述算法具体表现为如下算法1模式：
算法1
输入：训练集D，迭代次数m，最近邻样本数k。
输出：特征权重向量W。
初始化特征权重：
for i=1 to m
从D当中选择一个随机样本Ri；
For each classC=class（Ri）；
确定一个和Ri同类的k个最近邻样本，即Hj；
For each classC≠class（Ri）；
确定一个和Ri不同类的k个最近邻样本，即Mj（C）；
For A：I to All feature；
[W[A]=W[A]j=1kdiff（A，Ri，Hj）/mk]
[ C≠class（Ri）pi（C）1-p（class（Ri））j=ikdiff（A，Ri，Mj（C））/mk]
每次ReliefF在D中随机选择样本Ri，随后在从相同类别样本内确定k个最近邻样本，即Hj，在所有和Ri不同类样本内k个最近邻样本Mj（C），再对权重进行更新，反复进行上述流程，m次之后便可以完成权重排序，选择低权重的特征。
2 蚂蚁算法与特征基因选择方法结合
2.1 蚂蚁算法
专家在观察蚂蚁觅食的过程中发现，蚂蚁前进途中会在之前行走的路途中放射一种化学物质，即信息素，其余蚂蚁会按照道路上释放信息素浓度的不同，寻找自己行走的路线，在之前的基础上释放出更多信息素[2]。如果一条道路蚂蚁数量多，那么则证明信息素多，便会吸引更多的蚂蚁，通过这种方式来确定食物、巢穴之间的最短路途。由此可以证明，尽管一只蚂蚁的力量小，但是集合所有蚂蚁却能发挥出无穷的力量[3]。 在20世纪末，比利时的专家克罗尼和多里格等人便通过对蚁群的研究確定了从起点到终点最近的路径。在基因全集中放置m只蚂蚁，蚂蚁需要走过所有基因，再利用蚁群之间的合作确定最终是否选择这一基因。在试验过程中，每个基因都被视为一个结点，两个相邻结点之间都有2条路线，即0，1。蚂蚁需要路过所有结点，并且在行进的过程中选择一个路径，一旦蚂蚁选择路径1，那么代表这一基因被选择，0则没有被选择。假设其中一个路径{1，0，1，0，1}代表第1个、3个、5个基因，将其确定为特征基因，那么基因2和基因4则表示没有被选择。当m只蚂蚁经过了所有路径之后，便可以获得m个基因子集。蚂蚁之间利用信息素展开合作，路径上的信息素浓度高，针对的路径被选率则越高。一旦蚂蚁到了指定食物处，便要通过一些方法评估特征子集，以此确定一个最佳特征基因子集。
2.2 设置参数与算法描述
在以上分析的蚂蚁算法模型当中，其中还存在几个亟待解决的问题：其一，信息素初始值设置与更新[4]；其二，路径被选概率设置；其三，特征子集质量评估。在路径1中，信息素初始浓度通过基因i，并且在决策属性D重要程度的基础上进行了定义，即SGF（i，C，D）；将路径0中信息素浓度设置为1，如此一来便可以提高该路径被选几率，对特征子集长度进行合理控制，从而加快算法收敛速度，使运算效率更高。
通过路径选择概率结构模式为：
[Pkij（t）=τijkjτij] （6）
在公式（6）中，[τij]是第i个基因第j条路径信息素浓度，k则是j可能取值。当完成迭代之后，这对全部路径中信息素浓度需要进行更新，具体如公式（7）所示：
[τi（t 1）=（1-η）×τi（t） Δτi（t）] （7）
在公式（7）中，[η]是信息素蒸发因子，对自然环境下蚂蚁分泌信息素挥发之后使其浓度不断变淡的成效，[Δτi（t）]是信息素增量，具体如公式（8）所示：
[Δτi（t）=1/（θ×L（k） （1-θ）×γ（k））-1），psthway∈S0，pathway?S] （8）
在上述公式（8）中，L（k）代表蚂蚁k收集的特征子集长度，也就是在路径1中数量。[γ（k）]是决策属性对于这一特征子集所呈现的依赖度[5]。[θ]∈（0，1）的作用是对特征子集长度、性能进行控制。为了将计算量简化，使其能够有效区别不同路径中信息素浓度，S一般取前10%蚂蚁所针对路径。通常L（k）数值越小，[γ（k）]数值就越大，这时则代表新素增量大，即蚂蚁选择该条路径的几率越大，如此一来特征子集便会快速实现距离最短、决策属性依赖度最大的发展目标[6]。一旦蚂蚁找到了食物，便会将特征子集属性依赖度和长度进行结合，以此完成特征子集质量的评估，具体定义为：
[ε（S=n/（θ×L（S） （1-θ）×（γ（S））-1）] （9）
在公式（9）中，n是数据集基因数。在评价函数的基础上，可以确定决策属性依赖度最大、最短的特征基因子集。
3 结果分析
为了对ReliefF和蚁群算法的特征基因选择性能进行评估，下面重点以实际基因数据集的方式进行验证，并分析最终结果。
如下表1是结肠和白血病数据集，其中白血病数据集中样本数量共75个，其中有45个急性淋巴白血病样本，30个急性骨髓白血病样本，所有样本中都有7215个基因。结肠数据集中共有63个样本，其中肿瘤样本30个，正常结肠组织样本33个，所有样本中都有2005个基因。
通过计算机、编译软件、分类器进行试验。蚂蚁数量m=50，最大迭代次数Wmax=50，蒸发因子[η]=0.5，参数[θ]=0.2。通过一系列分析以及建模解析，可以确定白血病数据集分类准确率是85.2%，结肠数据集分类准确率是84.6%。最后使用ReliefF算法和蚁群算法选择最佳特征基因子集，并对分类效果进行观察，可以确定的是，白血病数据集特征子集规模为10，结肠数据集特征子集规模为7，分类准确率都达到了最高。
4 结束语
综上所述，使用ReliefF算法和蚁群算法进行的特征基因选择，能够有效提升分类准确率，并且获得最佳的特征基因组合，这为今后相关工作的进行提供了有效的参考。
参考文献：
[1] 魏峻.基于全局和声搜索算法的特征基因选择方法[J].内蒙古师范大学学报：自然科学版，2015，44（03）：372-379.
[2] 刘建华，杨建国，刘华平，等.基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报，2015，46（09）：18-27.
[3] 王立国，魏芳洁.结合遗传算法和蚁群算法的高光谱图像波段选择[J].中国图象图形学报，2013，18（02）：235-242.
[4] 吴华锋，陈信强，毛奇凰，等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报，2013，34（04）：165-170.
[5] 万晓凤，胡伟，方武义，等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用，2014，50（18）：63-66.
[6] 李丽，李霞，郭政，等.两种过滤特征基因选择算法的有效性研究[J].生命科学研究，2013（4）：369-373 376.
关键词：ReliefF；蚁群算法；特征基因选择方法
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）32-0199-02
在确定特种基因选择方法时，一般会运用蚁群算法、ReliefF算法。其中，蚂蚁算法主要用于组合优化问题求解的元启发式方法，体现了非常强的健壮性、回馈控制、Agent系统等优势，此外，蚂蚁算法本身所体现的贪心策略、随机策略也在原来的基础上提高了全局搜索水平。通常在微阵列数据当中，经常出现标记错误或者类别标签错误的样品，这时便可以运用蚁群算法，利用不同特征的冗余性组织分析，将以上相关问题合理解决。Relief算法则是一种非常经典的Filter 方法，也是一种非常普及、高效率的维数约简法。Relief算法中包含了Relief、Relief和ReliefF，ReliefF更多使用与多分类、数据不足、噪声等问题的求解。Relief 算法的时间复杂程度比较低，使用时也不需要分类精度这种评价函数，然而因为该算法是以特征权重算法为基础，所以在选择特征时只是提升与标签相关的特征权重值，将权重值低特征予以剔除，这样一来就无法剔除冗余特征。基于此，下文出于对以上两种算法优良性能的考虑，以此为前提分析了特种基因的选择方法。
1 Relief 算法与特征基因选择方法结合
Relief算法在实际应用中是一种效率非常高的 Filter 算法，按照特征的重要程度，对其进行排序，以超出指定阈值的特征当做特征子集。在训练集中可以确定Relief的任意样本R，针对所有样本都有2个最近邻，分别来自于同类样本H和异类样本M[1]。如果选择的样本R和样本H在训练集当中出现与特征A相关的差异，那么特征A便会被赋予比较低的权重。样本R和M在训练集中发生关于特征A的差异，那么特征A便会被赋予比较高的权重。由此一来，特征A可以通过Relief 对权重W[A]进行更新，
即
W[A]=W[A]-diff（A，R，H）/m diff（A，R，M）/m （1）
在公式（1）中，m為随机抽样个数，diff函数代表给定函数2个样本差异。对 W[A]进行计算时，要使用m对其进行归一化处理，确保权重值在-1～1之间。
一旦特征属性是标称属性，这时对于diff（A，Ix，Iy）的计算需要按照如下公式进行：
[diff（A，Ix，Iy）=0；value（A，Ix）value（A，Iy）I；otherwise] （2）
一旦特征属性是数值属性时，这时对于diff（A，Ix，Iy）的计算需要按照如下公式计算：
[diff（A，Ix，Iy）=|value（A，Ix）-value（A，Iy）|max（A）-min（A）] （3）
如果在计算时使用传统的算法，那么会将计算局限在二分类问题中，也无法对数据缺失、噪声等问题进行很好的解决。早在20世纪末，便已经有专家将Relief算法进行了拓展，并且在原来的基础上提出了ReliefF算法，将以上提出的一系列问题全部解决。ReliefF算法将所有样本同类的k个最近邻差异值、其余异类k个最近邻差异值进行平均，以此来解决数据内噪声带来的影响。选择最近邻样本数主要体现的是ReliefF、Relief二者的基本差异，保证了ReliefF算法本身所具有的鲁棒性。
为了将数据缺失这一问题予以解决，相关专家对原有的diff（A，Ix，Iy）函数进行了优化，优化之后的函数可以有效计算出属性缺失值。如果样本Ix存在缺失值，那么diff（A，Ix，Iy）的计算则是如下形式：
[diff（A，Ix，Iy）=1-P（value（A，Iy）|class（Ix））] （4）
如果样本Ix与样本Iy均含有缺失值，那么diff（A，Ix，Iy）函数计算则要按照如下形式进行：
[diff（A，Ix，Iy）=|-V#value（A）P（V|class（Ix））×P（V|class（A，Iy）））] （5）
在公式（5）中，V代表全部样本内特征A的数值，ReliefF算法描述算法具体表现为如下算法1模式：
算法1
输入：训练集D，迭代次数m，最近邻样本数k。
输出：特征权重向量W。
初始化特征权重：
for i=1 to m
从D当中选择一个随机样本Ri；
For each classC=class（Ri）；
确定一个和Ri同类的k个最近邻样本，即Hj；
For each classC≠class（Ri）；
确定一个和Ri不同类的k个最近邻样本，即Mj（C）；
For A：I to All feature；
[W[A]=W[A]j=1kdiff（A，Ri，Hj）/mk]
[ C≠class（Ri）pi（C）1-p（class（Ri））j=ikdiff（A，Ri，Mj（C））/mk]
每次ReliefF在D中随机选择样本Ri，随后在从相同类别样本内确定k个最近邻样本，即Hj，在所有和Ri不同类样本内k个最近邻样本Mj（C），再对权重进行更新，反复进行上述流程，m次之后便可以完成权重排序，选择低权重的特征。
2 蚂蚁算法与特征基因选择方法结合
2.1 蚂蚁算法
专家在观察蚂蚁觅食的过程中发现，蚂蚁前进途中会在之前行走的路途中放射一种化学物质，即信息素，其余蚂蚁会按照道路上释放信息素浓度的不同，寻找自己行走的路线，在之前的基础上释放出更多信息素[2]。如果一条道路蚂蚁数量多，那么则证明信息素多，便会吸引更多的蚂蚁，通过这种方式来确定食物、巢穴之间的最短路途。由此可以证明，尽管一只蚂蚁的力量小，但是集合所有蚂蚁却能发挥出无穷的力量[3]。 在20世纪末，比利时的专家克罗尼和多里格等人便通过对蚁群的研究確定了从起点到终点最近的路径。在基因全集中放置m只蚂蚁，蚂蚁需要走过所有基因，再利用蚁群之间的合作确定最终是否选择这一基因。在试验过程中，每个基因都被视为一个结点，两个相邻结点之间都有2条路线，即0，1。蚂蚁需要路过所有结点，并且在行进的过程中选择一个路径，一旦蚂蚁选择路径1，那么代表这一基因被选择，0则没有被选择。假设其中一个路径{1，0，1，0，1}代表第1个、3个、5个基因，将其确定为特征基因，那么基因2和基因4则表示没有被选择。当m只蚂蚁经过了所有路径之后，便可以获得m个基因子集。蚂蚁之间利用信息素展开合作，路径上的信息素浓度高，针对的路径被选率则越高。一旦蚂蚁到了指定食物处，便要通过一些方法评估特征子集，以此确定一个最佳特征基因子集。
2.2 设置参数与算法描述
在以上分析的蚂蚁算法模型当中，其中还存在几个亟待解决的问题：其一，信息素初始值设置与更新[4]；其二，路径被选概率设置；其三，特征子集质量评估。在路径1中，信息素初始浓度通过基因i，并且在决策属性D重要程度的基础上进行了定义，即SGF（i，C，D）；将路径0中信息素浓度设置为1，如此一来便可以提高该路径被选几率，对特征子集长度进行合理控制，从而加快算法收敛速度，使运算效率更高。
通过路径选择概率结构模式为：
[Pkij（t）=τijkjτij] （6）
在公式（6）中，[τij]是第i个基因第j条路径信息素浓度，k则是j可能取值。当完成迭代之后，这对全部路径中信息素浓度需要进行更新，具体如公式（7）所示：
[τi（t 1）=（1-η）×τi（t） Δτi（t）] （7）
在公式（7）中，[η]是信息素蒸发因子，对自然环境下蚂蚁分泌信息素挥发之后使其浓度不断变淡的成效，[Δτi（t）]是信息素增量，具体如公式（8）所示：
[Δτi（t）=1/（θ×L（k） （1-θ）×γ（k））-1），psthway∈S0，pathway?S] （8）
在上述公式（8）中，L（k）代表蚂蚁k收集的特征子集长度，也就是在路径1中数量。[γ（k）]是决策属性对于这一特征子集所呈现的依赖度[5]。[θ]∈（0，1）的作用是对特征子集长度、性能进行控制。为了将计算量简化，使其能够有效区别不同路径中信息素浓度，S一般取前10%蚂蚁所针对路径。通常L（k）数值越小，[γ（k）]数值就越大，这时则代表新素增量大，即蚂蚁选择该条路径的几率越大，如此一来特征子集便会快速实现距离最短、决策属性依赖度最大的发展目标[6]。一旦蚂蚁找到了食物，便会将特征子集属性依赖度和长度进行结合，以此完成特征子集质量的评估，具体定义为：
[ε（S=n/（θ×L（S） （1-θ）×（γ（S））-1）] （9）
在公式（9）中，n是数据集基因数。在评价函数的基础上，可以确定决策属性依赖度最大、最短的特征基因子集。
3 结果分析
为了对ReliefF和蚁群算法的特征基因选择性能进行评估，下面重点以实际基因数据集的方式进行验证，并分析最终结果。
如下表1是结肠和白血病数据集，其中白血病数据集中样本数量共75个，其中有45个急性淋巴白血病样本，30个急性骨髓白血病样本，所有样本中都有7215个基因。结肠数据集中共有63个样本，其中肿瘤样本30个，正常结肠组织样本33个，所有样本中都有2005个基因。
通过计算机、编译软件、分类器进行试验。蚂蚁数量m=50，最大迭代次数Wmax=50，蒸发因子[η]=0.5，参数[θ]=0.2。通过一系列分析以及建模解析，可以确定白血病数据集分类准确率是85.2%，结肠数据集分类准确率是84.6%。最后使用ReliefF算法和蚁群算法选择最佳特征基因子集，并对分类效果进行观察，可以确定的是，白血病数据集特征子集规模为10，结肠数据集特征子集规模为7，分类准确率都达到了最高。
4 结束语
综上所述，使用ReliefF算法和蚁群算法进行的特征基因选择，能够有效提升分类准确率，并且获得最佳的特征基因组合，这为今后相关工作的进行提供了有效的参考。
参考文献：
[1] 魏峻.基于全局和声搜索算法的特征基因选择方法[J].内蒙古师范大学学报：自然科学版，2015，44（03）：372-379.
[2] 刘建华，杨建国，刘华平，等.基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报，2015，46（09）：18-27.
[3] 王立国，魏芳洁.结合遗传算法和蚁群算法的高光谱图像波段选择[J].中国图象图形学报，2013，18（02）：235-242.
[4] 吴华锋，陈信强，毛奇凰，等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报，2013，34（04）：165-170.
[5] 万晓凤，胡伟，方武义，等.基于改进蚁群算法的机器人路径规划研究[J].计算机工程与应用，2014，50（18）：63-66.
[6] 李丽，李霞，郭政，等.两种过滤特征基因选择算法的有效性研究[J].生命科学研究，2013（4）：369-373 376.