基于三支决策的数据流主动学习分类研究.pdf

第 卷 第 期 年 月天 津理工大学学报 .收稿日期:修订日期:基金项目:安徽省自然科学研究重大项目()安徽省高校自然科学研究重点项目()安徽省高校自然科学研究项目():/基于三支决策的数据流主动学习分类研究李京阳刘三民张匡燕(安徽工程大学 计算机与信息学院 安徽 芜湖 安徽信息工程学院 计算机与软件工程学院 安徽 芜湖)摘要:针对概念漂移的数据流环境中样本标注难度大的问题 结合主动学习模型提出一种分区域的三支决策主动标注方法 将数据流样本空间划分为正域、负域和边界域 个区域 对不同区域数据的样本采用相应的主动标注策略 通过主动学习 挑选出各区域最具代表性和信息量的样本进行标注 完成分类模型的训练和更新 研究表明:三支决策主动标注方法在少量样本标注的情况下能获得较高的准确率 且具备一定的抗噪能力关键词:主动学习 数据流 三支决策 概念漂移中图分类号:文献标识码:文章编号:()():.:.:随着应用需求推动和技术不断发展 数据以流的形式在各行业不断产生 从数据流中挖掘有价值的信息 成为亟待解决的问题在学术界 许多学者正致力于数据流分类挖掘方面的研究 重点关注数据流中概念漂移和样本标注等问题 文献 利用滑动窗口和相异性度量的数据标注算法 提出一种集成的数据流分类框架 通过聚类分布的差异 处理数据流中的概念漂移问题 文献 设计了一种有监督自适应增量聚类算法 数据以块的形式进行聚类 对数据流中存在的异常点进行检测与剔除 文献 提出一种考虑概念漂移的数据流增量聚类方法 以监督的方式对数据流进行自天津理工大学学报第 卷 第 期动聚类 基于质心权值和预定义衰减率的概念漂移检测准则 剔除或忽略过时的聚类 虽然监督学习在静态数据流与动态数据流分类中已取得较多研究成果但在真实情况下 对数据流中样本进行标注费时费力 因此 基于主动学习方法解决动态数据流中样本标注成为有效方法之一 文献 设计了一种有效将概念漂移检测、主动学习和自适应模型更新结合的具有概念漂移的自适应增量分类的主动学习方法 对未标注的样本进行概念漂移程度检测 并按照概念漂移程度计算样本标注选择概率 文献 提出一种新的基于混合标注策略的漂移数据流在线主动学习集成框架 并由一个长期稳定的分类器和多个动态分类器组成的集成分类器设置标签阈值的不确定策略和随机策略的主动学习算法 可优先查询最不确定的样本进行标注 以减少标注成本 文献 提出一种新的基于集成算法的主动学习方法 在标签查询过程中 从分类器池中选择最优的分类器 获得一个有效的自适应主动学习过程 以应对数据流中的概念漂移问题 文献 提出一种用于数据流自适应分类的集成主动学习方法 将主动学习策略与边界点和离群点检测方法相结合 有选择性地挑选检测已发生概念漂移的数据样本 文献 提出一种基于双查询策略和艾宾浩斯记忆认知定律的主动学习框架 在辨别和处理噪声样本 使用新概念替换过时样本基础上 按照局部密度和不确定性标注最具代表性样本综上可知 针对发生概念漂移的数据流中无标签或少标签的问题 采用主动学习方法具有显著的优势 在主动学习过程中挑选最具代表性的样本交由专家进行标注较为关键 文中结合具有概念漂移的数据流场景 设计出面向数据流分类的三支决策主动学习()算法 以解决相关问题 基础知识 基本概念为便于描述 对数据流和概念漂移进行符号化定义 若数据流 其中 ()表示时刻 ()的样本实例 为类值()为 中所包含的类别数 概念漂移是指数据流中样本产生的联合概率分布()随着时间变化而发生变化 即()()根据变化的形式不同 概念漂移分为 种常见类型:突变式、渐变式、增量式和重现式 三支决策三支决策是 提出的一种求解不确定问题理论 在二支决策基础上增加了延迟决策 当信息不足以支撑接受也不足以支撑拒绝时采用延迟决策 避免二支决策所引起的不必要代价 其初始目的是为粗糙集理论中的 个分类区域(即正域、负域和边界域)提供合理的决策语义解释 为实现三支决策引入实例的评价函数 ()也称决策函数 其值称为决策状态值 状态值的大小反映实例的好坏程度再引入阈值 和 根据决策状态值和阈值将实例划分为 个区域 三支决策定义如下:在给定的非空实数样本集 给定评价函数 ()则当 ()时 实例 被划分至负域 基于三支决策的数据流主动学习 文中基于上述三支决策概念 对数据流样本空间进行划分 设计样本选择策略 实现主动式学习 面向数据流环境的三支决策主动学习框架基于三支决策的数据流主动学习的目的是在分类中使用少量的标签样本实现分类挖掘模型的训练和更新 结合主动学习框架和数据流分类挖掘的需求 给出基于三支决策的数据流主动学习框架 如图 所示 使用少量的样本作为初始训练集 学习一个初始分类模型 设置一个缓存实例集 以便对数据流进行批处理 当 中样本个数满足要求后 使用初始分类模型 对 中的所有样本计算信息熵通过设置参数 和 将 实例集划分成 个不相交的实例集:正域()、边界域()和负域()按照不同的选样策略处理 个实例集 并对样本标注 然后更新分类模型 年 月李京阳 等:基于三支决策的数据流主动学习分类研究图 基于三支决策的数据流主动学习 基于三支决策的数据流主动学习采样是将样本的不确定性作为样本价值的评估标准 对不确定性较低且容易分类的正域()采用随机抽样的方法选择少量样本 以保证采样的全面性 对位于不确定性中间的边界域()样本代表性采用 方法选择价值最大的簇中心点 对不确定性大 且难以准确分类的负域()采用 方法剔除异常点后对所有样本进行采样 基于三支决策的数据流主动学习方法建立基于三支决策的数据流主动学习分类方法目的是在数据流分类过程中根据实例的不确定性大小 将实例划分不同的域 在不同域中分别采用有效的采样策略挑选最具价值性的样本 对不同域的样本分别进行处理 样本区域划分设置批处理缓存实例集 当 样本集满足一定数量要求后 加入三支决策方法 设置一对阈值()在评价函数()下将 中的样本 划分至 个不相交的区域:(正域)、(边界域)和 (负域)则:当()时 样本 被划分至负域 记作 属于 不同域样本的处理()处理 (正域)的样本 对正域内的样本 通过分类模型计算出其不确定性较小 可认为该类样本能被准确进行分类 为保证采样的全面性 对该类样本采用随机采样策略 选择其中的少量样本交给专家进行标注 以更新分类器()处理 (边界域)的样本 对边界域内的样本 实例的不确定性将位于中间区域 但如某样本周围有较多的样本 即高密度区域 通过聚类算法分到的同类样本具备相同类别的假设 则通过挑选聚类中心点 该样本具有高代表性 有效且有用对其进行标注有利于该样本及周边相同类别样本的分类 从而提高分类器的性能 边界域的处理采用 方法来挑选中心点样本()处理 (负域)的样本 负域中的样本不确定性较大 其内部除可能存在概念漂移情况外还存在异常点和噪声样本 为减少非概念漂移样本引起的采样结果偏差 采用 方法 将去除负域内异常点后的全部样本集合交给专家进行标注 该方法的优势是基于密度的方法 且算法收敛速度快综上 通过对数据流划分不同区域进行相应处理 整个处理过程选择数据流中信息量大和代表性强的样本进行标注 从理论上可缓解采样偏差的问题 信息熵主动学习中 样本选择的标准主要有以下几种:不确定性标准、版本空间缩减标准和误差缩减标准其中 不确定性标准是目前适用性最广 研究最为充分的一种方法样本的不确定性是指模型对样本分类信息熵的大小衡量 即:信息熵高 则分类模型分类错误的可能性大 反之 分类模型分类错误的可能性小 文中采用分类模型 对数据流样本计算信息熵 对未知样本 进行预测 针对数据流中的样本信息熵计天津理工大学学报第 卷 第 期算式如下:()()式中:为样本 共 类 为分类模型计算样本第 类的后验概率 算法描述结合上述内容 提出基于三支决策的数据流主动学习算法为:输入:数据流 批处理大小 决策阈值 输出:样本标注个数和准确率训练初始分类模型 对实例集 置空 数据流 实例依次添加到实例集 中 使用式()计算样本 的信息熵()()()()且()()()利用随机采样策略对 中所有实例进行处理挑选少量样本交专家标注 同时标注样本数累加/正域样本选择 利用 方法处理 挑选聚类簇中心点进行标注 并对标注样本数累加/边界域样本选择 利用 方法处理 检测异常点或噪声点并剔除 对剩余样本进行标注 标注样本数累加/负域样本选择 对 选择的样本进行标注 用于更新分类器 清空 个样本集 仿真试验及结果分析 数据集选取为验证所提算法的有效性 分别采用合成数据集:径向基函数()数据集、流 集 成 算 法()数据集和超平面数据集 以及真实数据集:森林覆盖数据集和电力数据集完成对比试验 合成数据集和真实数据集均来自大规模在线分析开源平台()和对应网站合成数据集中 数据集用来模拟渐变式概念漂移数据 由 生成 数据生成过程中 质心变化的速度设置为 数据集代表突变式概念漂移的合成数据 数据集被划分为具有不同概念的块 在每个块中 分类函数为 的样本为正类 否则为负类真实数据集中 森林覆盖数据集包含位于科罗拉多州北部罗斯福国家森林的 个较宽区域内的森林覆盖类型信息 用于描述 种森林覆盖类型 是数据流分类领域中使用最广泛的数据之一 包含 个实例 有 个属性和 个目标类 电力数据集是另一种广泛使用的数据集 来自澳大利亚新南威尔士州电力市场 数据集包含 个实例 类标记表示这一天相对过去 移动平均值的价格变化(上升或下降)所有试验数据集的特征信息、类别信息和概念漂移类型如表 所示表 试验数据集 数据集类型 数据集名称特征数实例数类别数概念漂移类型合成数据集 渐变式 突变式超平面 增量式真实数据集森林覆盖 未知电力 未知所有试验均在 环境中进行 取前 个样本训练初始模型 采用先测试后训练的方法来测试模型 并在过程中记录分类准确率来表示模型好坏 批处理实例集 大小为 使用 作为初始学习器 根据多次试验结果可知 针对不同数据集 和 取值不相同 且多次试验结果表明:的取值对试验的整体效果影响较大 年 月李京阳 等:基于三支决策的数据流主动学习分类研究多次试验后取最优经验值:数据集()数据集()超平面数据集()森林覆盖数据集()电力数据集()仿真结果分析 算法有效性验证文中对提出的基于三支决策的数据流主动式学习方法的有效性进行测试 将 与传统的监督式学习方法进行对比 验证在使用少量样本标注的情况下也可取得较好的分类准确率 监督学习模型中采用 ()和 ()两种增量式机器学习算法 均已集成在 平台 相关参数均使用默认的参数设置 算法对比分类效果如表 所示表 算法对比分类效果 数据集准确率/准确率/准确率/(标注率/)()()超平面 ()森林覆盖 ()电力 ()由表 可知 算法在不同的概念漂移数据集中 选择少量标签样本可让分类模型达到与全标注监督学习相近的结果 说明所设计的标注策略是可行的能挑选出有价值的样本进行标注学习 在数据集 中 只需 左右的标签样本即可让分类模型达到全标注条件下相近的分类准确率 在数据集 中 算法使用 左右标签样本 其分类准确率均高于算法 和 的分类准确率 此时 算法全监督学习算法的效果更好 在超平面数据集中 算法在使用 左右的标签样本时 准确率为 与 算法在完全标注率的 有相当的分类准确率 且比 算法的准确率 要高 在森林覆盖数据集中 在 的标签率情况下 其分类准确率为 高出 算法的分类准确率 在电力数据集中使用 的标签时 其分类准确率为 高出 算法的分类准确率 结合表 可知 在试验数据集中 标注样本量增加到 时 分类准确率提高不明显 由此可说明基于三支决策的数据流主动学习方法可将数据流进行空间划分 仅挑选各空间少量的样本即可代表数据集中的关键样本 在标注后进行更新的情况下 可达到与完全标注算法相当的分类准确率 验证了文中提出方法的有效性 抗噪声能力验证为验证文中算法具有一定的抗噪声能力 向 数据集和超平面数据集中分别加入 的随机类噪声模拟噪声环境 将试验 中相同的方案分别在两组噪声数据集上进行比较 试验数据如图 和图 所示 图 为 和 在加入不同比例噪声的 数据集的结果 在低于 比例噪声的 数据集中 的分类准确率比 和 的分类准确率均高 随着噪声比例的增加 的分类准确率一直比 的分类准确率高 在超平面数据集中 与 和 的分类准确率和噪声比例的比较如图 所示 虽然 出现准确率比 和 的准确率较低的情况但仍能一直与 和 保持相当的分类准确率图 在含不同噪声比例的 数据集中各算法的分类准确率 图 在含不同噪声比例的超平面数据集中各算法的分类准确率 天津理工大学学报第 卷 第 期结合图 和图 的试验结果可看出 在随着噪声比例不断提高的数据集中 算法的分类准确率下降速度较为平缓 且能有效区分噪声数据 使分类模型保持较高的分类准确率 说明文中提出的算法具备一定的抗噪性 结论 数据流分类因其存在概念漂移和噪声等特点而变得复杂 在真实应用中 获取标注样本不仅代价高且困难 文中提出面向数据流的主动学习分类方法 基于信息熵计算数据流中实例样本的不确定性 结合三支决策方法设置决策阈值 将实例划分成不同的样本空间域 并分别对不同域的样本进行相应的处理 通过选择最具代表性和信息量的少量样本进行标注 从而解决数据流样本标注难题 由试验结果可知 算法可在使用少量标注样本更新模型的情况下 与监督式学习分类模型有相当的分类准确率参 考 文 献 .:.():.文益民 刘帅 缪裕青 等.概念漂移数据流半监督分类综述.软件学报 ():.:.:.():./:./():.():./():.张银芳 于洪 王国胤 等.一种用于数据流自适应分类的主动学习方法.南京大学学报:自然科学版 ():.():.周胜 刘三民.基于迁移学习的数据流分类研究综述.天津理工大学学报 ():.:.徐健锋 辛朋 薛国泽 等.面向概念漂移集成分类的三支决策优化方法 .郑州大学学报:理学版 ():.胡峰 张苗 于洪.基于三支决策的主动学习方法.控制与决策 ():.陈丙杰 王晓晔 常飞.噪声数据流的分类方法.天津理工大学学报 ():.李南.基于聚类假设的数据流分类算法.模式识别与人工智能 ():.杨文柱 田潇潇 王思乐 等.主动学习算法研究进展 .河 北 大 学 学 报:自 然 科 学 版 ():.孙艳歌 王志海 原继东 等.基于信息熵的数据流自适应集成分类算法.中国科学技术大学学报 ():.作者简介:李京阳()男 硕士研究生 研究方向:数据挖掘、主动学习等:刘三民(通信作者)()男 教授 博士 研究方向:机器学习、数据挖掘等: