一种改进的粒子群微学习单元特征选择算法

冯耀武，张月琴，陈 健

(太原理工大学 信息与计算机学院，山西 晋中 030600)

1 引 言

高速度与快节奏的社会把我们推进到“微”时代，从微信、微博到微视频，进而发展到与学习相关的微课堂，“微”己融入我们生活的方方面面.充斥于网络的各种“微资源”的存在，让人们可以把工作闲暇、等人、还有坐车等零碎时间用于基于微资源的自主学习.另一方面，社会的发展使知识更新周期不断缩短，这要求人们持续更新知识来增强适应能力.在上述背景下，微学习应运而生.微学习通过提供精短的微学习单元，让学习者可以无时无处，利用零散的时间进行学习，为学习者带来了极大便利.为此，以MOOC(Massive Open Online Course)为代表的各种微学习教育平台迅速发展，并在全世界得到普及.

迅速增长的微学习资源在给学习者带来便利的同时，学习内容的更新速度也越来越快，同一时刻更新的规模也越来越大[1]，从而导致信息过载等问题.借助聚类算法对微学习单元进行处理，将帮助学习者获得适合自己的学习资源，提高学习效率.微学习资源的多源异构特征决定了其存在维度高及冗余大等特点，对聚类带来不利影响，从而影响聚类的准确性，同时也会对算法的性能带来影响.为提高微学习单元聚类的准确性，对微学习资源的聚类数据进行特征选择，以优化特征子集进而提高微学习单元的聚类准确性.特征选择作为一种降维方法，能选择出具有代表性的特征集合用于聚类，从而实现降低冗余和噪声的目的.

为解决上述问题，本研究提出一种改进的粒子群微学习单元特征选择算法.该算法具有以下特点：1)把特征冗余和特征代表性作为评价微学习单元特征子集的指标，通过剔除冗余特征属性，选取有效的特征属性，帮助提高微学习单元的聚类准确率；2)利用互信息构造适应度函数，以无监督方式实现在微学习单元类标记信息缺乏或者不完全的情况下的特征选取；3)通过自适应突变概率策略，改善算法早熟问题.实验表明，与已有的特征选择算法相比，提案算法收敛速度和求解精度都显著提升.

2 相关理论

2.1 特征选择

基于一定的评价准则选择适合的特征子集是特征选择的目的.定义D为一个m×n的数据集，其中Z为该数据集的特征属性集合，X是D的一个候选特征子集,J(X)为评价特征子集X有效性的函数.特征选择问题如公式(1)所示:

J(Z)=maxX⊆NJ(X)

(1)

换句话说，特征选择的目的是选择一部分能够代表包含特征集合大部分信息的特征子集，采用该特征子集进行聚类分类等能够获得与原始特征集合相同或者更好的效果.特征选择通常有4个步骤：子集生成、特征子集评价、停止准则、验证过程.一般流程如图1所示[2].

图1 特征选择流程图Fig.1 Feature selection flow chart

对于由n个特征属性构成的数据集，所有可能的候选特征子集总共有2n-1种情况.因此特征选择也是一个NP困难(Non-deterministic Polynomial-Time Hardness)[3].将特征子集生成过程视为寻优过程，通过一定的搜索策略生成待评估的特征子集，然后对候选子集通过评价函数进行评估并与前面迭代中筛选出的最优特征子集作比较，如果新的子集在该评估准则上有更好表现，就把该子集作为最优的特征集合.然后在后续迭代中重复特征子生成和特征子集评估的步骤到停止条件满足，最后在测试数据集和真实数据集上对提取的特征子集的有效性进行验证.

特征选择作为一种有效的降维方法，目前在数据挖掘中的分类、聚类、关联规则和回归等问题中已经被广泛应用[4].经典的特征选择方法，例如最大方差法和LapScore[5]是根据每个特征独立计算的分数来选择排名靠前的特征.这些方法未考虑特征间的相关性，因而在涉及相关性的源数据时，所选择的特征子集的聚类准确性仍有待提高.Nie等提出的跟踪比率(Trace Ratio)[6]和Yang等提出的无监督判别特征选择(UDFS)[7]首先检测数据的结构特征，然后直接选择那些能够最好地保留原始数据封闭结构的特征.Trace Ratio会包含选择冗余特征而UDFS算法的学习模型往往过于严格[8].

目前因为启发式搜索算法的自身优势，它在特征选择问题上收到广泛关注.特征选择的过程可以视作是一个求解组合优化问题的过程，因此启发式算法可以用来解决大数据环境下特征选择问题.遗传算法已成功应用于嵌入式特征选择，但其计算量大，容易过早陷入局部最优.其它算法例如蚁群优化算法、人工蜂群算法和粒子群优化算法等均被应用于特征选择.在这些算法中粒子群算法因其求解速度快、计算成本低、寻优能力强等特点而备受青睐.Wang[9]等人提出了一种基于粗糙集的粒子群特征选择算法来，该研究认为基于粒子群的特征选择算法能够有效地解决特征子集选择问题.

2.2 互信息

对于有监督的特征选择而言，可通过对特征和类标签间的相关性计算进行特征选择.然而，在无监督的问题中，没有可以直接使用的类别标签.因此，需要一种方法来评估特征是否满足选择条件.借助标准互信息构造粒子群适应度函数，可以评估两个特征之间的相关程度.两个特征之间的相关程度越高，它们之间的标准互信息就越大.

假设F={f1,f2,…,fd}为原始数据集下的特征集合，Y={yi1,yi2,…,yin}是第i个特征fi的对应特征值，fi的标准互信息计算如公式(2)所示.

(2)

其中MI=(f1,f2)是特征fi和fj的互信息，见公式(3)：

(3)

其中H(fi)和H(fj)分别为特征项fi和fj的信息熵，见公式(4)：

H(fi)=-∑p(yij)log2p(yij)

(4)

可知互信息在特征选择中可看作已知特征fi的信息对于特征fj的不确定性的减少量，即两者共有的信息量.从信息论的角度来看，互信息特征选择方法由于其能够量化的表示特征间的相关关系已被广泛应用于特征选择算法中[10].

2.3 粒子群算法

粒子群算法是Kennedy等人于1995年开发的一种基于种群的随机优化技术，其灵感来自于鸟群觅食等动物的群体行为[11].粒子群算法通常用于解决组合优化问题.其算法描述为：

设存在一个D维的目标搜索空间，m个粒子组成一个种群，其中第i(i={1，2，…，m} )个粒子表示一个D维向量Xi={xi1，xi2，…，xid}.第i个粒子在目标搜索空间的位置是xi.每个粒子所对应的位置视为一个候选解，将xi带入到适应度评价函数中，计算其适应度值.每个粒子i有一个速度控制其飞行的方向和距离，Vi={vi1，vi2，…，vid}也是一个D维向量.第i个粒子寻优过程中得到的最优位置记为pb，整个粒子群当前迭代为止搜索到的最佳位置记为pg粒子速度和位置的更新如公式(5)、公式(6)所示:

Vidt+1=uVidt+c1r1(pb-Xidt)+c2r2(pg-Xidt)

(5)

Xidt+1=Xidt+=Vidt

(6)

其中，d={1，2，…，D}，i={1，2，…，m}，m为种群规模;c1和c2为加速常数;r1和r2为[0,1]之间的任意随机数,t表示粒子迭代次数.

为了优化粒子群算法在离散数据集上的处理，1997年Eberhart等人对粒子群算法进行改进并提出二进制粒子群算法(Binary Particle Swarm Optimization，BPSO)，以此来处理离散数据的全局优化问题.在BPSO算法中，粒子的位置Xi，是用二进制的字符串表示(10110011).粒子的位置更新如公式(7)所示：

(7)

其中，s(·)是s型函数，通过sigmoid函数对速度进行处理，从而确定每个粒子的二进制位置，r3为[0，1]的随机值.

此外，Kennedy等人[12]对粒子群算法作了进一步优化，删除传统粒子群算法的速度向量和相应的控制参数，提出了一种基于高斯采样的粒子位置更新方法，称为骨干粒子群算法(Bare Bones Particle Swarm Optimization，BBPSO).具体粒子更新如公式(8)所示：

(8)

与传统的粒子群算法相比，BBPSO减少了速度分量和c1和c2为加速常数的使用，所以更紧凑、更实用.

粒子群优化是一种相对较新的进化算法，具有全局搜索、实现简洁、收敛速度快等优点.到目前为止，研究人员已经提出了多种不同的改进算法，并将其应用于解决各种实际问题.王等[13]提出了一种带有二维扰动和自适应学习因子的粒子群算法，改善算法容易陷入早熟的问题.Wang等人[14]提出了一种基于马尔可夫毯和粒子群算法的无监督特征选择算法，该算法首先利用最大熵原理剔除不相关特征，然后将粒子群算法和马尔可夫毯相结合，去除冗余特征.Abualigah等[15]利用粒子群优化算法进行特征选择，提高了文本聚类的有效性.

3 改进的骨干粒子群算法的特征选择方案

针对已有研究成果及存在的问题，本研究提出一种改进的骨干粒子群算法，用于微学习单元的特征选择.首先，利用互信息构造粒子群算法的适应度函数，以此评价粒子位置所对应的特征子集的效果.针对原算法中粒子位置在迭代过程中的变异概率为固定值，且没有充分利用适应度函数所提供的信息，在算法后期存在收敛速度变慢，易于陷入局部最优值等问题.本研究通过粒子适应值动态调整算法变异概率大小来平衡粒子的全局寻优能力和局部寻优能力，进而提高算法的执行效率.

3.1 粒子编码

本文所采用实数编码的策略，而不是利用sigmoid函数进行转换.利用特征集合中每个特征被选中的概率值进行编码，多个编码概率值组成一个粒子.对于d个特征的数据集而言，编码后每个粒子的值可以表示为公式(9)：

Xi=(xi,1,xi,2,…,xi,d),i=1,2,3,…,|s|

(9)

式中|s|为粒子种群大小，xi,j表示特征集合中第j个特征被选中的概率.定义一个阈值0.5，用来区分当前粒子的位置所对应的特征是否被选择，当xi,j≥0.5时，表示该特征被选择；否则，该特征未被选中.

3.2 适应度函数

传统的基于粒子群算法的特征选择方法中的适应度函数通常是根据类别标签计算特征子集的准确率来构造的，而利用最大平均互信息构造适应度函数作为候选特征集合的评价函数，无需用到类别标签，适用于无监督的特征选择，适应度值得计算分为两个部分，分别考虑了所选特征冗余度度量fit1和特征子集的代表性度量fit2来评价粒子的适应度.冗余度如公式(10)所示：

(10)

其中，SF是当前粒子位置所确定的候选特征子集，max _NMI(fi)为SF集合中的特征fj(i≠j)与fi的最大互信息值，其中最大标准互信息如公式(11)所示：

max_NMI(fi)=max{NMI(fi,fj)|fj∈SF,f≠fj}

(11)

可知fit1的值越小，SF集合的冗余度越小.特征代表性如公式(12)所示：

(12)

其中NSF为冗余特征集合，fmin为SF集合中距离NSF中特征fi最近的特征.可知fit2越大，则SF集合的代表性越强.然后将fit1和fit2进行整合，构造粒子群的适应度函数，整合后的适应度函数fit如公式(13)所示：

(13)

α，β为缩放参数.可知fit越小，所选特征子集的代表性越强，冗余度越低.

3.3 自适应粒子群突变策略

经典的骨干粒子群算法，以固定的粒子群突变概率进行随机搜索(公式(8)中为固定值0.5).当突变概率设定较大时粒子有较强的全局搜索能力，但是寻优过程容易出现震荡，稳定性较差.当突变概率阈值设定太小时，粒子有较强的局部寻优搜索能力，但是容易收敛到局部最优解，此时算法的搜索速度慢、求解精度低.针对此问题，需根据不同阶段的寻优效果，适应性调整粒子突变概率值大小，处理好全局搜索能力与寻优精度之间的关系.突变概率阈值的设定，对粒子群算法的执行效率有显著影响.PSO算法具有较强的随机性，事先确定的突变概率或者突变概率的变化都难以有效应对寻优过程中的随机性.因此，本文提出一种适应性突变概率策略，通过迭代过程中粒子的适应度值变化信息来适应性调整突变概率mu的大小.第t代粒子的平均适应度值Mt的计算，如公式(14)所示：

(14)

式中:n表示种群中粒子数量;fiti(t)表示第i个粒子迭代到第t代的适应度值.本文是针对适应度值最小化的求解，粒子群的平均适应值的相对变化率见公式(15).

(15)

当变化率k较大时，代表粒子群还未收敛，说明此时突变概率在搜索寻优空间中搜索能力较强，对突变概率进行适应性增加，能够增强粒子群的开发能力，减少算法迭代前期的执行次数，提升算法性能.当k变化率较小时，说明此时寻优空间相对突变概率较为复杂，难以找到更优极值，因此可以适应性地减小突变概率值，增加粒子群在寻优空间中的局部搜索能力，提高粒子的寻优精度，而不至于因为突变概率值太大而跳过最优解.这样根据上一次的迭代结果反馈，动态调整当前迭代中的粒子突变概率，具有更好的自适应性.因此，本文提出的突变概率调整如公式(16)所示：

(16)

公式(16)中：mut表示粒子在第t代时的突变概率，γ和δ为突变概率变化大小的调节参数，γ用来调节公式中ln(1+k)的变化幅度，δ用来调节ek的变化幅度.因为在寻优过程中k值的变化幅度较大，故在增加突变概率时使用自然对数，在减小突变概率时使用e作为指数，能够有效降低其变化幅度，从而使mut+1的变化更平滑.同时给出k的最大值与最小值，让突变概率在一定范围内变化，从而避免突变概率过大或者太小的问题.改进后的粒子位置更新如公式(17)所示：

(17)

从公式(16)可知，在k值比较大时，算法的粒子突变概率越大，全局搜索能力越强，从而粒子可以在较大范围内进行粗搜索，可以较快搜索到全局最优的邻域；当k值较小时，粒子在最优值附近移动，对应的粒子突变概率变小，局部寻优能力也越强.算法演化为局部的精确搜索，可以更精确地搜索极值.

3.4 算法流程

基于以上基本原理和改进方法，提出微学习单元特征选择选择算法，本文算法的流程图如图2所示.

图2 基于改进粒子群算法的特征选择模型Fig.2 Feature selection model based on improved particle swarm optimization

算法1.自适应突变概率的骨干粒子群特征选择算法

输入：预处理后的微学习单元数据.

输出：微学习单元特征子集.

1.Init：粒子群种群D，大小N，迭代最大次数Maxgen，缩放参数α、β，γ、δ；，初始化粒子群的位置xij以及粒子群局部最优值Pbest；粒子群全局最优值Gbest值;

2.计算粒子群全局最优值

While(i

if(1≥k≥0.01)

按照国家要求划定了生态保护红线，对东洞庭、西洞庭、南洞庭3处国际重要湿地，4处国家级自然保护区，22个国家湿地公园，11处国家级水产种质资源保护区等实施了最严格的保护，湿地保护率达76.04%，重点推进了自然保护区杨树清理、违规采砂打击、内湖保护等工作。通过努力，洞庭湖区湿地自然保护区核心区7.99万亩杨树全面清理到位，清理采砂运砂船800多只，所有采砂船集中停放，自然保护区全面实施禁采。同时，坚持“活水”“清水”相结合，实施了四口水系、沅江片区等六大片区河湖联通工程，使江、湖、河自然水力联系恢复畅通，有效提升了区域环境容量。

突变概率mu保持不变(公式(16));

else if(k>1‖k≤0.01)

get缩放参数γ、δ;

根据公式(16)更新突变概率mut;

calculate:xij粒子位置(公式(17)),

get缩放参数α、β；

每个粒子的适应度值fit(i)(公式(13));

Gbest′=Pbestmin;//Gbest′为当前迭代中的全局最优值

if(Gbest′

Gbest=Gbest′;

else

Gbest值保持不变;

End While

3.通过Gbest求得对应的特征子集.

4.output:被选择的特征子集

5.结束处理

4 实验与结果分析

在本节中，通过一系列实验来验证提案算法的有效性.本文首先在5个测试数据集进行特征选择，并进行聚类测试，然后，通过在真实的微学习单元数数据集下进行对比实验，进一步验证提案算法的有效性和准确性.所有实验在主频为2.8GHz CPU和8G内存的工作站上完成，实验环境所在操作系统为Windows7，用Matlab语言在MATLAB2018a环境下实现本文特征选择算法.

4.1 数据介绍

本文先在5个测试数据集上验证本文特征选择算法的有效性，测试数据集为Wine数据集、人脸图像数据集Jaff和Orl，声呐数据集Sonar，心脏数据集Statlog.其中包括多种类型的数据集，特征数目最少13，最多为1024.这些数据集的详细信息如表1所示.

表1 数据集信息Table 1 Data set information

表2 微学习单元数据Table 2 Micro-learning unit data

然后，在3个微学习单元数据集上选择进行聚类测，实验数据集为自主搭建的edx学习平台中搜集的数据集.将一个视频对应题目，简介等元数据作为一个微学习单元数据集.本文采用向量空间模型来表示微学习单元，用TF-IDF权重计算方法计算特征项的权重.表2为不同领域的3个微学习单元数据集预处理后的数据信息.

4.2 微学习单元数据预处理

本文采用的微学习单元数据集为英文文本，是基于Python3.6利用NLTK库进行微学习单元数据集的预处理的过程.通过预处理将微学习单元数据集规范化,主要过程为：

1)文本分词.本文利用Python已有工具NLTK库中的word_tokenize()方法，将文本中的每个词独立的提取出来从而将文本拆解成词语单元，分词通过NLTK正则表达式实现.

2)停用词去除.文本经过分词处理之后，针对微学习单元中每一个单词，对照停用词表，过滤停用词表中的单词.同时去除非英文字符，消除冠词、连词等一些无意义无作用的词，减少数据占用空间，也避免为后续特征选择带来的干扰.停用词库使用NTLK自带的停用词库.

3)词形还原.通过词形还原把数据集中任意形式的词汇还原为一般形式.获得的词的原型，能够承载一定意义.词形还原是通过NLTK库中的lemmatization()算法实现.

4)微学习单元表示.通过向量空间模型对微学习单元进行表示.在表示模型中，首先用m×n的关键词矩阵表示微学习单元.m表示微学习单元个数，n表示特征项出现的频次.然后通过TF-IDF权重计算方法重新计算特征项的权重.通过CountVectorizer方法将微学习单元中的词语转换为词频矩阵.通过TfidfTransformer统计每个词语的TF-IDF值.

对数据集D1进行预处理后的数据如表3所示，在此基础上进行特征选择实验.

4.3 实验设置

为了验证本文所提出的算法的有效性和优越性，将本文算法产生的特征子集与原始特征集合、其它4中无监督特征选择方法所确定的特征子集进行聚类比较.其它无监督特征选择算法有：

a)多聚类特征选择(MCFS)，该方法首先使用谱嵌入对数据进行聚类分析，然后通过l1范数正则回归模型进行特征选择，选择的特征尽可能地保持数据的多聚类结构.

b)无监督判别特征选择方法(UDFS)同时利用了局部判别信息和特征相关性进行特征选择图.

c)鲁棒非监督特征选择(RUFS)，该方法通过局部学习正则化正交非负矩阵分解并联合l2，1范数最小化进行鲁棒的特征学习.

d)LapScore，它选择那些最能保持局部流形结构的特征.

这些算法表现出较好的特征选择性能，将提案算法与之进行比较，能够在一定程度上说明本文所提出的算法有效性和相对于其他特征选择算法优越性.

对比算法中的近邻参数k均设置为5，算法聚类数目设置为各数据集的类别数.MCFS聚类迭代次数是20次.RUFS算法中向量之间的相似性采用余弦相似性，UDFS算法的正则化参数设置为0.1.记录不同类型算法的聚类准确率.

表3 预处理后部分数据Table 3 Partial data after preprocessing

本文算法的具体参数设置为：参考文献[16]中，种群规模应设置为特征数/20且不超过300，本文中种群规模N=50.通过多次实验，种群初始突变概率mu=0.7，mumax=0.7，最小mumin=0.1时，提案算法可以获得较好的实验效果，最大迭代数Maxgen=500可以保证算法收敛.通过分析迭代过程中适应度值的变化过程，并参考文献[17]中相关参数设置，其实验表明设置参数α=0.8、β=0.2、γ=1、δ=0.3时在基准测试函数上有良好的收敛性能.

4.4 结果分析与比较

表4是5个测试数据集下的实验结果.本文从聚类准确率和特征个数两个方面对不同算法进行评价.表中记录了了不同特征选择算法通过k-means聚类，效果最好的特征子集中的特征个数及相应特征子集下的聚类准确率值.用粗体标出了不同算法对应的表现最佳的聚类准确率.用下划线标出不同算法中特征个数最少的特征.在Orl数据集上，可以看到，对于所有的5个不同类型的数据集，本文所提出的改进算法在Orl、Wine、Statlog、Sonar数据集上都有最高的准确率，在Jaffe数据上的表现，RUFS算法略优于提案算法，但是提案算法所确定的特征个数在122时可以得到与RUFS算法所提取的300个特征相当的聚类准确率.另外且在Orl、Jaffe、Sonar数据集上提案算法得到的特征个数最少.因此，本文算法能够选择较少的特征，但对应的聚类性能并未大幅度地下降，反而在大部分数据集上的聚类精度获得显著提升.MCFS、UDFS、RUFS使用所有的特征估计数据的基本结构.但是在现实世界中，冗余和噪声特性是不可避免的，这也是我们需要特征选择的原因，使用所有特征进行学习数据的结构也会受到这些冗余和噪声特征的污染，从而降低特征选择的性能.

表5为不同算法在D1、D2、D3为不同领域的3个微学习单元数据集下的对比，每个数据集中有5类样本对不同算法得到的微学习单元特征子集通过k-means算法进行聚类.可以直观的观察到，本文算法得到的3个微学习单元特征子集进行聚类都有最高的准确率，并且在D1和D2数据集上，提案算法所确定的特征个数也最少；在D3 数据集下提取算法所确定的特征个数虽然略高于UDFS算法，但是本文算法的聚类准确率明显高于UDFS算法.因此，在微学习单元数据集上的实验结果表明本文算法能够选出对微学习单元聚类有效的特征.

表4 测试数据集准确率对比Table 4 Accuracy comparison of test data sets

表5 微学习单元数据集下准确率对比Table 5 Comparison of accuracy in microlearning unit dataset

图3是本文添加自适应突变概率前后算法在微学习单元数据集D1、D2、D3上的适应度值曲线，其虚线fitness′表示添加适应性策略前，实线fitness表示添加策略后.由图3可看出，添加自适应突变概率策略后，算法能够成功跳出局部最优解，收敛到更小的适应度值.在算法迭代前期，适应度值下降较快，算法迭代到后期时曲线时相对平滑.说明迭代前期本文算法对搜索空间有较高的开发率，在迭代后期本文算法有较高的搜索精度.

图3 微学习单元数据集上适应度值变化曲线Fig.3 Change curve of fitness value on micro-learning unit dataset

5 结 语

为提高微学习单元聚类效果，本文提出了一种基于适应性突变概率的骨干粒子群特征选择算法，从适应函数构造，适应性突变概率策略等两个方面进行改进.通过对5个公开测试数据集和3个微学习单元数据集进行实验对比，可发现本文所提出的算法在对微学习单元进行特征选择后聚类效果与原始特征集相比有明显提高，且优与LapScore、MCFS、UDFS、RUFS等特征选择算法.其中加入适应性突变概率策略后能够摆脱局部最优值的干扰，收敛到更小的适应度值，可以获得更好的特征子集.然而，本文提出的适应调整突变概率的粒子群优化算法尚未完全解决算法会陷入局部最优的问题，如何更有效地平衡算法的全局寻优能力和局部寻优能力还有待于进一步的研究.