论文部分内容阅读
摘 要： 遗传算法目前在特征向量选取中扮演着重要角色。由于其具有并行、自适应强等诸多优点，广泛受到多个领域的关注。本文首先对遗传算法、谱聚类等基础知识进行概述，其次介绍遗传算法的三个重要过程遗传、变异及交叉算子。最后给出遗传算法进行特征选择的步骤。为研究谱聚类算法中，使用遗传算法进行特征选择提供学习参考。
关键词： 谱聚类 特征向量选择 遗传算法
1.简介
目前特征选择方法有很多，如模拟退火算法、遗传算法等。其中，遗传算法作为一种组合的优化算法，不是对单个特征进行优劣划分，而是对一个可能特征子集进行考核评价，能够保证所选特征子集的组合达到最优，省去各特征之间的相关性这一繁琐工作；另外，遗传算法具有并行性、自適应性、领域无关性等诸多特点，能够很好地处理高维的特征集。故而遗传算法可有效应用于特征选择中，在很多领域都得到成功应用。
谱聚类中前K个最大的特征向量并不总能检测得出真实的模式识别问题的数据结构。所以，特征向量的选取变得很有必要。特征向量选取方式有许多种，如基于熵排列的方法、使用遗传算法的特征向量选取方法和多套特征向量选取方法等。而特征向量排列列表中有两种选择策略。一是在排列列表中直接选取前K个特征向量，且这K个特征向量是谱聚类中最重要的特征向量。第二种特征向量选取策略是在排列列表中的前Km（Km>K）的特征向量中寻找合适的特征向量组合。通过这种策略得到的特征向量组合能够反映出原始数据的结构，能得到令人满意的聚类结果。研究特征向量的选择对谱聚类很有必要。我们应该根据特征向量提供的信息量的多少估计其对聚类的重要性，并选择合适的特征向量组合进行谱聚类。
2.遗传算法
遗传算法GA作为一种实用的最佳选择方法，是一种鲁棒性搜索方法。不需要知道很多信息就可以在大空间和难以理解的空间中实现有效搜索。在每一代中，三个最基本操作即繁殖复制、交叉和变异，它们在保证个体数目不变的情况下生成一个新的群体。
GA算法的搜索空间为V 子集中的所有列。在编码设计中，每个颜色提代表一个特征向量组合。一个染色体是一个包含Km个基因的位串。串中的每个基因只包含0和1。若第j位为1，则第j个特征向量被选中。否则，对应特征向量被忽略。另外，繁殖、交叉和变异算子按如下分别被定义如下：
繁殖：该算子基于适者生存的原则。设种群A={a ，a ，…，a }，每个个体都有自己的最大适应度f（a ），且在新的代数中均有自己大量的复制i（k）。例如，在轮盘赌选择法中，具有高适应度值的第i个个体被赋予一个对应比例的很高的繁殖概率。一旦一个个体再次重现，则在下代中，就得到了一个新种群（k）={i（k），i=1，2，…，m}。
交叉算子：在交叉算子中，个体之间通过概率决策交换信息。多点交叉是一种常用的交叉方法，为最佳个体提供了多个杂交几率。对于多点交叉，随机选取一个尚未复制的p交叉位置，并按降序排列。一串连续的交叉点之间的基因在双亲之间交换以生成两个新的后代。
变异：当第i个个体的第j个位置被选中，变异算子仅将状态从0变为1或者相反改变。当具有一个很高变异概率的遗传算法GA退化到一个随机搜索时，变异应当是一个非常低的概率算子。
3.使用遗产算法的间接特征向量选取
输入：取自原始数据集X={x ，x ，…，x }的训练集合；所有特征向量的排列列表的前Km个特征向量组成的矩阵V∈R 。
输出：最佳的特征向量组合ec
（1）在V中提取训练数据对应的那部分特征向量，并使用V ∈R 标记，tn为训练数据的个数。
（2）产生随机种群A（0）={a （0），a （0），…，a （0）}，并设置迭代次数k=0。
（3）只使用V 中a （k）的特征向量构造出矩阵U ∈R 。使用式（6）计算出种群对应的适应度f（a （k））（1≤i≤m）。
（4）直到一个满足一个合适的迭代次数时终止。当满足当前的种群被认为是最佳种群，则转入步骤（6）。否则执行下一步。
（5）再繁殖复制，交叉和变异产生新的染色体，k=k 1，转入步骤（3）执行。
（6）从最佳种群中选择最好的个体，并将得到的高适应度值作为最佳的特征向量组合ec 。
遗传算法GA中所用的符号表示如下：Ga为GA的最大迭代次数，ps为种群大小，Prob？摇m和Prob？摇c分别为变异概率和交叉概率。该算法的计算复杂度主要包括编码、繁殖复制、交叉、变异和适应度计算。在GA的每次迭代，繁殖复制、交叉和变异的复杂度分别为O（ps）、O（ps×Proc？摇m）和O（ps×Proc？摇c）。我们使用2路归并排序作为适应度排序的算法，它的复杂度是O（ps×log ps）。因此，文中整个的GA时间复杂度为Ga（O（ps ps×Proc？摇m ps×Proc？摇c） O（ps×log ps））。
4.结论
本文介绍了一种使用遗传算法进行特征向量选取的方法。首先对遗传算法及谱聚类基础知识进行简要介绍。而后对遗传算法的三个主要过程进行描述，包括遗传、交叉及变异。第三部分对使用遗传算法进行特征向量选取进行介绍，并分析算法执行的时空复杂度。遗传算法改善了传统方法对大规模复杂数据进行特征选取的局限性。但由于遗传算法中群体的大小、交叉、变异概率均是实验参数，很难确定，加上获得的结果不一定是最优解，因此遗传算法用于特征选择有待改进。最后遗传算法作为一种组合优化方法，为解决实际问题提供了不少帮助，该算法势必在未来发挥更为重要的价值，应用前景将更广阔。
参考文献：
[1]Zhao F，Jiao L C，Liu H Q，et al.Spectral clustering with eigenvector selection based on entropy ranking[J].Neurocomputing，2010，73（10）：1704-1717.
关键词： 谱聚类 特征向量选择 遗传算法
1.简介
目前特征选择方法有很多，如模拟退火算法、遗传算法等。其中，遗传算法作为一种组合的优化算法，不是对单个特征进行优劣划分，而是对一个可能特征子集进行考核评价，能够保证所选特征子集的组合达到最优，省去各特征之间的相关性这一繁琐工作；另外，遗传算法具有并行性、自適应性、领域无关性等诸多特点，能够很好地处理高维的特征集。故而遗传算法可有效应用于特征选择中，在很多领域都得到成功应用。
谱聚类中前K个最大的特征向量并不总能检测得出真实的模式识别问题的数据结构。所以，特征向量的选取变得很有必要。特征向量选取方式有许多种，如基于熵排列的方法、使用遗传算法的特征向量选取方法和多套特征向量选取方法等。而特征向量排列列表中有两种选择策略。一是在排列列表中直接选取前K个特征向量，且这K个特征向量是谱聚类中最重要的特征向量。第二种特征向量选取策略是在排列列表中的前Km（Km>K）的特征向量中寻找合适的特征向量组合。通过这种策略得到的特征向量组合能够反映出原始数据的结构，能得到令人满意的聚类结果。研究特征向量的选择对谱聚类很有必要。我们应该根据特征向量提供的信息量的多少估计其对聚类的重要性，并选择合适的特征向量组合进行谱聚类。
2.遗传算法
遗传算法GA作为一种实用的最佳选择方法，是一种鲁棒性搜索方法。不需要知道很多信息就可以在大空间和难以理解的空间中实现有效搜索。在每一代中，三个最基本操作即繁殖复制、交叉和变异，它们在保证个体数目不变的情况下生成一个新的群体。
GA算法的搜索空间为V 子集中的所有列。在编码设计中，每个颜色提代表一个特征向量组合。一个染色体是一个包含Km个基因的位串。串中的每个基因只包含0和1。若第j位为1，则第j个特征向量被选中。否则，对应特征向量被忽略。另外，繁殖、交叉和变异算子按如下分别被定义如下：
繁殖：该算子基于适者生存的原则。设种群A={a ，a ，…，a }，每个个体都有自己的最大适应度f（a ），且在新的代数中均有自己大量的复制i（k）。例如，在轮盘赌选择法中，具有高适应度值的第i个个体被赋予一个对应比例的很高的繁殖概率。一旦一个个体再次重现，则在下代中，就得到了一个新种群（k）={i（k），i=1，2，…，m}。
交叉算子：在交叉算子中，个体之间通过概率决策交换信息。多点交叉是一种常用的交叉方法，为最佳个体提供了多个杂交几率。对于多点交叉，随机选取一个尚未复制的p交叉位置，并按降序排列。一串连续的交叉点之间的基因在双亲之间交换以生成两个新的后代。
变异：当第i个个体的第j个位置被选中，变异算子仅将状态从0变为1或者相反改变。当具有一个很高变异概率的遗传算法GA退化到一个随机搜索时，变异应当是一个非常低的概率算子。
3.使用遗产算法的间接特征向量选取
输入：取自原始数据集X={x ，x ，…，x }的训练集合；所有特征向量的排列列表的前Km个特征向量组成的矩阵V∈R 。
输出：最佳的特征向量组合ec
（1）在V中提取训练数据对应的那部分特征向量，并使用V ∈R 标记，tn为训练数据的个数。
（2）产生随机种群A（0）={a （0），a （0），…，a （0）}，并设置迭代次数k=0。
（3）只使用V 中a （k）的特征向量构造出矩阵U ∈R 。使用式（6）计算出种群对应的适应度f（a （k））（1≤i≤m）。
（4）直到一个满足一个合适的迭代次数时终止。当满足当前的种群被认为是最佳种群，则转入步骤（6）。否则执行下一步。
（5）再繁殖复制，交叉和变异产生新的染色体，k=k 1，转入步骤（3）执行。
（6）从最佳种群中选择最好的个体，并将得到的高适应度值作为最佳的特征向量组合ec 。
遗传算法GA中所用的符号表示如下：Ga为GA的最大迭代次数，ps为种群大小，Prob？摇m和Prob？摇c分别为变异概率和交叉概率。该算法的计算复杂度主要包括编码、繁殖复制、交叉、变异和适应度计算。在GA的每次迭代，繁殖复制、交叉和变异的复杂度分别为O（ps）、O（ps×Proc？摇m）和O（ps×Proc？摇c）。我们使用2路归并排序作为适应度排序的算法，它的复杂度是O（ps×log ps）。因此，文中整个的GA时间复杂度为Ga（O（ps ps×Proc？摇m ps×Proc？摇c） O（ps×log ps））。
4.结论
本文介绍了一种使用遗传算法进行特征向量选取的方法。首先对遗传算法及谱聚类基础知识进行简要介绍。而后对遗传算法的三个主要过程进行描述，包括遗传、交叉及变异。第三部分对使用遗传算法进行特征向量选取进行介绍，并分析算法执行的时空复杂度。遗传算法改善了传统方法对大规模复杂数据进行特征选取的局限性。但由于遗传算法中群体的大小、交叉、变异概率均是实验参数，很难确定，加上获得的结果不一定是最优解，因此遗传算法用于特征选择有待改进。最后遗传算法作为一种组合优化方法，为解决实际问题提供了不少帮助，该算法势必在未来发挥更为重要的价值，应用前景将更广阔。
参考文献：
[1]Zhao F，Jiao L C，Liu H Q，et al.Spectral clustering with eigenvector selection based on entropy ranking[J].Neurocomputing，2010，73（10）：1704-1717.