1、第 卷第 期重庆邮电大学学报（自然科学版）年 月 （）：结合邻域信息和标记相关性的在线多标记流特征选择算法收稿日期：修订日期：通讯作者：林耀进 基金项目：国家自然科学基金面上项目（）；福建省自然科学基金重点项目（）：（）；（）包丰浩，林耀进，李育林，毛 煜，（闽南师范大学 计算机学院，福建 漳州；闽南师范大学 数据科学与智能应用福建省高等学校重点实验室，福建 漳州）摘 要：现有大多数多标记流特征选择算法在进行特征选择时，往往忽略标记间的相关性，易导致算法预测精度的下降。为解决这一问题，提出一种结合邻域信息和标记相关性的在线多标记流特征选择算法；定义自适应邻域关系解决邻域粗糙集的粒度选择问题，将
2、其推广到多标记学习中；利用互信息计算标记间的相关性得到标记权重；通过邻域粗糙集和标记权重评估特征和标记间的相关性，并设计特征在线重要度分析、在线相关性分析和在线冗余度分析 种指标，以实现在线评价动态候选特征。在 组多标记数据集以及 个评价指标上的实验结果表明，所提算法综合性能较优。关键词：流特征；特征选择；邻域粗糙集；标记相关性；多标记学习中图分类号：文献标志码：文章编号：（），（，；，）：，：；引 言近年来，在线多标记流特征选择算法已在实际任务中得到了广泛应用，如微博热搜榜上的热点实时更新、实时过滤网络垃圾邮件以及对天气情况变化的实时监测。在这些应用场景中，数据经常有以下特点：一个样本通常与
3、多个类别标记相关联，并且数据的特征空间呈现出高维性和动态性。众所周知，特征空间的高维性会带来数据存储容量较大、学习性能低等问题，而特征动态性使得特征空间具有未知性和演化性的特点。例如，在 社交网络服务平台上，训练样本的特征空间时刻发生变化，当一个热门话题出现时，总是伴随着一组新的特征。因此，如何对多标记和流特征应用场景中的数据集进行学习建模具有实际价值。目前，多标记特征选择算法可分为静态和动态两类。静态的多标记特征选择算法是指在多标记数据的特征空间或标记空间固定不变前提下进行的特征选择。代表性算法有多标记朴素贝叶斯分类的特征选择（，）算法、依赖度最大化的多标记维数约简（，）算法和用于多标记特征
4、选择的（，）算法。动态多标记特征选择算法是指数据的特征空间会随时间不断变化，特征以动态流的方式逐个到达，分析到达的每个特征并进行特征选择。如 等提出基于邻域粗糙集的多标记在线流特征选择（，）算法；等对于特征成组动态出现的情况，利用邻域互信息评估特征组的重要性，提出在线多标记组特征选择（，）算法。目前，动态多标记特征选择算法只关注多标记环境下的标记和特征间的联系，忽略标记间的相关性。在多标记学习中，标记间是互相依赖和影响的，通常存在着共生与互斥的关系。例如，图像若被标记为“仙人掌”和“骆驼”，那么很有可能也被标记为“沙漠”。即可根据标记相关性从已知标记推测对象的未知标记。标记为“蓝天”和“白云”
5、的视频剪辑往往出现在同一帧，而其中往往不会有“雨伞”的出现。即可根据标记相关性从已知标记排除一些对象的未知标记。因此，利用标记相关性对提高多标记特征选择算法性能具有重要意义。基于此，本文提出结合邻域信息和标记相关性的在线多标记流特征选择（，）算法。首先，基于标记间的相关性生成加权无向图，利用互信息计算每个标记的权重。其次，基于邻域关系 重新定义邻域粗糙集的依赖度，用于在线评估每个新到达特征与每个标记间的重要性，选出当前具有最佳预测能力的特征子集。最后，在 组常用数据集上的实验结果显示，与现有的多标记特征选择算法相比，所提算法在各个方面均取得较优的效果。相关知识 邻域粗糙集邻域粗糙集广泛用于复杂
6、数据的特征选择与分析学习，本节简要介绍邻域粗糙集的相关定义。定义 给定一个决策系统，表示非空有限的样本集合，用以描述样本的条件属性集合，和决策属性，。其中，条件属性集合为每个样本所具有的特征，决策属性表示样本标记。如果邻域之间的固定距离以某个 值决定，则称，为一个邻域决策系统。定义 和特征子集，则样本 对于 的邻域（）被定义为（），（，）（）（）式中：（）是样本 的 邻域集，邻域的大小取决于阈值；表示距离度量函数，通常距离度量函数 用欧氏距离进行表示。定义 在一个邻域决策系统 ，中，为决策属性 到 对于样本的分类集合。（）是由 在特征子集（）下的邻域粒化。基于特征子集 关于决策属性，的上、下近
7、似定义为 （）（）式中：（），；（），。也被称为决策的正域，由（）表示，重 庆 邮 电 大 学 学 报（自然科学版）第 卷其正域越大，则特征的区分能力越强。定义 在一个邻域决策系统 ，中，则 对 的依赖度可以表示为（）（）（）（）式中：（）表示其正域数量；表示所有样本的数量。显然，（），若（），则称 是完全依赖于特征子集。定义 在一个邻域决策系统 ，中，若 满足（）（）；，（）（）。则称特征子集 是 的一个约简。条件是要保证特征子集和特征集合 的依赖度相等；条件表示特征子集中没有任何多余的特征。因此，最优特征子集应与整个特征集合具有相同或相似的区分能力。由此启发，基于依赖函数给出重要度的定义如
8、下。定义 在一个邻域决策系统 ，中，对特征子集 的重要度可以定义为（，）（）（）（）互信息互信息是度量 个变量相关性的重要工具，其定义如下。定义 给定随机变量 和，则 和 之间的互信息定义为（；）（，）（）（）（）（；），当 与 统计独立时等号成立，此时 与 没有任何相关性。结合邻域信息和标记相关性的在线多标记流特征选择算法模型 标记权重的计算互信息被认为是计算标记之间相关性的有效度量。本文在构建标记间的加权无向图基础上利用互信息计算每个标记的权重。定义 给定训练集 （，）（，），其中，是训练集样本的数量；，是样本空间；，是具有 个标记类别的标记空间，（，）是标记空间中任意 个标记。根据（）式
9、，这 个标记之间的相关程度计算表达式为（；）（，）（）（）（）（）式中，和 表示样本 和 在标记 和标记 下的值。定义 给定一个标记类别集合，基于标记间的关联程度可计算出标记的权重。权重越大，表示该标记相对于其他标记更重要。标记权重的计算公式为（）（）（）（）（，）（）（）（）式中：（）和（）分别表示标记 和 的权重；（，）表示标记间的相关程度，可由（）式计算得出；表示阻尼系数，设为；（）表示除标记 之外的所有标记，所有标记的权重初始值设为 ，是标记的类别个数；（）表示标记 和其余所有标记之间的互信息总和，表示为（）（，）（）再分别将各个标记所得权重除以总和，得到各个标记最终的权重。为了更好地
10、理解算法，本文用一个具有 个样本和 个标记的具体样例说明标记权重的计算过程，标记集如表 所示。表 标记集示例 样本根据（）式计算出各个标记之间的互信息，每一列和每一行对应相应的标记。由于并不要需要使用到 个相同标记之间的互信息，所以矩阵的对角线为，所得的关系矩阵为（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（）第 期 包丰浩，等：结合邻域信息和标记相关性的在线多标记流特征选择算法这里给出（，）的计算过程为（；）（，）（）（）（，）（）（）（，）（）（）（，）（）（）（）根据（）式，计算关系矩阵中的（，），由（）式得到关系矩阵为 （）然后计算标记权重，以（）为例，根据
11、（）式，计算式为（）（）（）（，）（）（）（，）（）（）（，）（）（）（，）（）（）)（）同理，根据（）式，即可得到 的标记权重，结果如表 所示。表 标记权重 多标记邻域粒度的计算如何为每个样本设置邻域粒度是邻域粗糙集的重要研究内容。为了避免粒度选择问题，本文引入 设置邻域的大小，并推广到多标记学习中。根据其他样本相对目标对象的距离自动选择每个目标对象的邻域实例个数。关于 的定义如下。定义 给定样本集合，和特征集合 ，。使（），表示 周围的所有样本，（，）切割成 块长度均为 的区域。若 和 的距离大于，则称为 和 之间的，可以表示为（，）。给出 在特征子集上 的自适应邻域定义为（），（）（）式
12、中，（，）是 至 之间的第 个。定义 给定一个样本集合，标记集合 ，对于，是 在标记 的决策属性个数，是标记 下的决策属性 到 的样本子集。（）是样本 在特征子集 的邻域，则特征子集在标记 下的正域表示为（）（），（）关于在标记 下依赖度的计算可以使用定义 的公式，即（）（）（）本文给出一个利用 计算依赖度的实例方便读者理解。样本数据集如表 所示，其中，是在特征 和标记 下的样本集。表 样本数据集 样本以计算 在标记 下的依赖度为例，为得到精准的数据处理结果，首先其对其做归一化处理，结果如表 所示。首先计算各个样本距离 的距离，（，），（，），（，），（，），（，），将其按从近到远进行排序，使
13、（），。重 庆 邮 电 大 学 学 报（自然科学版）第 卷由（）（），易得（，），根据（）式，则（，）是 至 之间的第 个。所以在 前的样本集合为 的邻域，即（），。则按照上述计算方法，依次可得（），（），（），（），（），（）由于（），（）的 都为，（）和（）的 都为，则根据（）式，有（），（）根据（）式，即得（）（）（）表 归一化处理结果 样本 结合邻域信息和标记相关性的在线多标记流特征选择算法 在本节中，本文提出一个在线多标记特征选择框架，该框架分为 个阶段：在线重要性分析、在线相关性分析和在线冗余性分析。在线重要性分析为评估新到达特征相对于已选特征的重要性，根据定义 定义 给出在多标记
14、特征选择中的相应定义。定义 给定一个样本集合，标记集合 ，和标记的权重集合（）。（）根据定义 和定义 得出，表示的是特征子集 标记 下的依赖度，其中，则关于标记集合 对于特征子集 的依赖度可以定义为（）（）（）（）（）式中，（）反映特征子集关于标记集合 的预测能力。定义 给定一个标记集合，是在 时刻挑选的最佳特征子集，是在 时刻到达的新特征。若将 加入特征子集中，使特征子集的依赖度增加，则意味着 是重要的，给出关于特征 对已选特征子集 重要度的定义，表示为（，）（）（）（）若特征 相对已选的特征子集的重要度越大，则该特征的描述能力就越好。假设（，），那么特征 对已选特征就是多余的。其他情况下，
15、对当前已选特征子集都有积极作用，则特征 加入已选特征子集中。在线相关性分析在这一小节中，引入在线相关性分析，对重要度为 的特征进行重新评估。定义 假设 是已选的特征子集，是在时刻到达的新特征。给定一个阈值（），若（），则认为特征 对于已选特征子集是相关的，对其进行在线冗余分析，否则丢弃该特征。在线冗余性分析定义 假设 是已选的特征子集，是新到的特征。若使（，），则说明 相对于 是冗余的，则进行冗余更新。定义 假设新到的特征 相对于 中的是冗余的。对 个特征进行依赖度计算，若（）（），则（）加入已选特征子集中，把从特征子集中丢弃。否则直接丢弃特征，已选特征子集不变。算法步骤基于在线重要性分析、在
16、线相关性分析和在线冗余性分析 个阶段，本文提出一个新的多标记在线流特征选择 算法，算法步骤如下。算法 算法输入：标记集合，样本集合，相关系数（），在 时刻到达的特征 以及已选特征子集；输出：时刻选择的最佳特征子集。根据定义，定义 计算每个标记的权重得到（）；获取在 时刻到达的特征 在线重要性分析 第 期 包丰浩，等：结合邻域信息和标记相关性的在线多标记流特征选择算法 根据定义 定义 计算依赖度（）；（）；I0丢弃特征 并返回步骤；I1 I2 I3 根据定义 计算重要度（，）；I4 （，）I5 ，并返回步骤；I6 I7 在线相关性分析I8 （）I9 丢弃特征 并返回步骤；2021 在线冗余性分析22 23 （，）（）（）24 丢弃特征 并返回步骤；25 26 （，）（）（）27 ；28 ；29 30 31 32 33 34 直到没有新的特征流入返回。算法 的主要步骤：根据（）（）式计算出每个标记的权重，在 时刻流入一个新的特征，步骤进入在线重要性分析阶段，判断已选特征子集是否为空，若为空，则计算新特征 的依赖度，若大于，则加入特征子集中，否则直接丢弃该特征。若已选特征子集不为空，则当特征
