基于数据摘要的流式子模优化算法研究_王怡.pdf

电子设计工程Electronic Design Engineering第31卷Vol.31第4期No.42023年2月Feb.2023收稿日期：2021-10-31稿件编号：202110156基金项目：国家自然科学基金资助项目（61828601）；山西省重点研发计划项目（201903D321003）作者简介：王 怡（1997），女，山西长治人，硕士研究生。研究方向：人工智能，机器学习。当前，数据摘要逐渐成为机器学习的研究热点。然而数据摘要算法被证明在性别、种族和民族等敏感属性方面存在偏见1-2，尤其在教育、招聘、银行和司法系统等领域中3-5，所引起的公平性问题6得到了广泛的关注。对于上述问题，该文引入流式子模最大化算法7，在此基础上改进算法约束，考虑数据项的组成性，在每组中选取指定范围内的元素构成具有代表性的子集，从而使提取出的子集更具有公平性和多样性。1基于公平约束的流式子模算法1.1拟阵约束下的流式子模最大化模型在很多情况下，考虑算法的稳定性以及成本等问题，通常采用拟阵约束下的流式子模优化模型8-10。定义1：假设V表示原有数据集中n个元素的集基于数据摘要的流式子模优化算法研究王 怡1，常 青1，王耀力1，郝慧琴2（1.太原理工大学 信息与计算机学院，山西 晋中 030600；2.中国电信股份有限公司山西分公司，山西太原 030000）摘要：针对如何从数据中提取出公平摘要的问题，文中采用流式子模最大化方法来解决该问题，并对其算法进行改进，提出一种公平约束下的流式子模最大化算法。该算法根据摘要的个数以及数据属性范围设置上下界构成公平约束，能够确保提取出代表性子集涵盖原始数据集的所有属性范围。仿真结果表明，该文算法与其他流式子模最大化算法相比，不仅时间复杂度减少了8.6%以上，而且在不同数据集下都能保证数据摘要结果的公平性与多样性。关键词：数据汇总；子模优化；公平约束；流算法；多样性中图分类号：TP391文献标识码：A文章编号：1674-6236（2023）04-0016-05DOI：10.14022/j.issn1674-6236.2023.04.004Research of streaming submodular optimization algorithm based ondata summarizationWANG Yi1，CHANG Qing1，WANG Yaoli1，HAO Huiqin2（1.College of Information and Computer，Taiyuan University of Technology，Jinzhong 030600，China；2.Shanxi Branch of China Telecom Co.，Ltd.，Taiyuan 030000，China）Abstract:Aiming at the problem of how to extract fair summarization from data，this paper adopts thestreaming submodular maximization method to solve it，improves the algorithm，and proposes astreaming submodular maximization algorithm with fairness constraint.By setting the upper and lowerbounds according to the number of summarization and the range of data attributes，the algorithm canguarantee that the representative subset covers all the range of attributes of the original data set.Throughsimulation experiments，it is concluded thatcompared with other streaming submodular maximizationalgorithms，the proposed algorithm not only reduces the time complexity by more than 8.6%，but alsoensures the fairness and diversity of data summarization results under different data sets.Keywords:data summarization；submodular optimization；fair constraints；streaming algorithm；diversity-16合，V1Vm是V的一个分划，即V=mi=1Vi,ViVj=,ij。d1,d2,dm是m个非负整数，k为基数约束，S为最优子集。记:L=SV:|S|k,|SVi|di（1）则(V,L)是定义在V上的拟阵，称为分划拟阵。在分划拟阵约束下的流式子模最大化模型可表示为：maxSV,|S|Lf(S)（2）1.2改进后的约束公平约束鉴于上述拟阵约束得到的集合S，当原始数据集合V中含有某些如年龄、性别、种族等特定属性时，会造成对某些特定属性数据的代表性不足或者过强，无法保证集合S的公平性与多样性。为了使选取出的集合S能够公平代表原始数据集合V，对上述拟阵约束进行改进，提出了一种公平约束。该文借鉴文献11-14有关公平的思想，要求获得的解集S与数据某些特定属性(如种族、性别)相平衡，提出流式子模最大化下的公平约束，定义如下：假定给定的数据集V是有颜色的，即给每个元素赋予一种颜色。对于颜色c=1,2,C，用Vc表示颜色c的元素集合，则V=Cc=1Vc,VcVb=,cb,b=1,2,C。对于每种颜色c，提取后的解集S必须包含每个颜色c的元素个数在指定的下界lc和上界uc之间。设kZ是一个全局基数约束，该公平约束表示为：F=SV:Sk,|SVc|lc,uc（3）则基于该公平约束下的流式子模最大化模型为:maxSV,SFf(S)（4）由公平约束的定义可知，S满足以下条件：SVc|uc,c=1Cmax(|SVc|,lc)k（5）该文将满足上述条件的S表示为“可扩展”的。2公平约束下的流式子模算法2.1公平约束下的流式子模最大化算法文献8提出的拟阵约束子模优化算法 A(MSM算法)是目前性能最好的拟阵子模优化算法，但该算法未考虑公平问题。因此该文基于 MSM 算法进行改进，提出公平约束下的流式子模算法(FSM 算法)，步骤如下：1）FSM算法通过运行A来构造一个近似最大化f的解集SA。SA必定满足上界，同时，对于每种颜色c，并行收集一个大小为|Bc|=lc的备份集Bc。2）若SA不满足其下界，则将SA扩展为一个可行的解决方案S，即对于每一种颜色c，如果|SAVc|lc，则从Bc中添加lc-|SAVc|个元素来满足下界。FSM算法伪代码如下：算法1：FSM算法Input：Ground setV,MatroidM:(V,L),parameterlcMSM算法SABcfor every arriving elementeof colorcdow(e)f(SAe)-f(SA)ifSA+eMthenSASA+eelseUeSA:SA+e-eMeargmineUw(e)f(SA+e-e)f(SA)施加公平约束：if|Bc|lcthenBcBc+eSAsolution of algorithm MSMSSAaugmented with elements in setsBcreturnS2.2算法可行性分析当去掉公平约束F中的下界约束|SVc|lc时，剩下的约束将会与式（1）相同，得到一个拟阵。然而在该拟阵约束下的流式子模最大化算法A得到的解可能会违反下界约束。为了兼顾下界约束，该文算法通过从A并行流中收集备份元素来扩大解决方案，使之成为一个可行的解决方案。然而，仅仅扩大解决方案来满足下界约束，可能会违反全局基数约束|S|k。正确的约束是解决方案具有式（5）的条件：“可扩展”到一个可行集。为了说明该文所提出的算法能有效地找到可行解，需要证明符合公平约束的V的可扩展子集的集合F仍然能构成一个拟阵。下面给出公平约束符合拟阵约束性质的证明。定义2：若F?2V是V的所有可扩展子集的集族，那么F?是一个拟阵。证明如下：若F?是拟阵，必然满足以下公理：设B包含拟阵F?中的所有极大集。则B满足以下两个公理：B。王 怡，等基于数据摘要的流式子模优化算法研究-17电子设计工程 2023年第4期如果B1,B2B和xB1B2，则存在yB2B1，使得B1-x+yB（向下封闭性）。这些公理表明向下封闭性的 B（集合的所有子集）是一个拟阵。但是，B的向下封闭性等于F?，因为V的任何子集只要能推广到一个可行解，也能推广到一个极大可行解。因此，只需要证明公理和公理。公 理 的 证 明 只 需 假 设F?，即 可 得 到B。对于公理：已知B1,B2B,xB1B2,设c是x的颜色，一种简单的情况是当B2B1包含某个元素yVc，那么B1-x+y中每种颜色的元素数与B1相同，因此B1-x+y也在B中。现 在 假 设 另 一 种 情 况，即VcB2B1-x。那么有：uc-1|Vc(B1-x)|VcB2|lc（6）则必定存在另一种颜色d，颜色d中B2比B1有更多的元素，否则B2+x是可行的，与B2的极大性相矛盾。认为选择任意元素yVd(B2B1)可以得到一个极大可行解：B1-x+yB。对于颜色c，由式（6）可知，已经满足其上下界。对于颜色d，B1-x显然满足其下界，又因为|Vd()B1-x+y=|VdB1+1|VdB2|Vd，其 上 界 也 已 经 满 足。而 由 于|B1-x+y=|B1k，因此全局上界也已经满足。已知F?中的任意极大集具有相同的大小，即min(k,cmin(uc,|Vc)，也就是说B1-x+y已经和B1的元素个数相同，它也是一个极大基。3仿真实验与分析3.1实验概述该文讨论的是公平约束下的数据摘要问题，为此通过以下指标来进行对比实验：1）使用函数效用值和时间复杂度（运行时间）来衡量算法的性能。2）将违反公平的次数error(S)=cCmax|SVc-uc,lc-|SVc,0定义为衡量公平的标准，总和项的每一项是依靠违反上界和下界元素的个数来量化的。3）查看不同算法每个分组的选取元素的个数来衡量提取数据的多样性。实 验 所 采 用 的 效 用 函 数 为f(S)=M-vVmineSd(v,e)。其中，d(v,e)=v-e22，M=nmaxx,yVd(v,e)，V为数据集中的所有数据之和，其个数为n。此外，平均每个分组提取到的元素为k/t，其中t表示分组的个数，根据该实验数据集的分组个数，设置上界uc=0.2k与下界lc=0.1k，以确保每个分组包含子集的10%20%。在很多应用中，比如电影推荐15-16、图形检测17等，感兴趣的是从庞大的数据集中提取出的部分集合与原始数据集相似，涵盖想要的所有的属性。为了评估该文算法 FSM 的可使用性，选用了两种 不 同 的 数 据 集，第 一 种 数 据 集 为 公 共 数 据 集Cencus1990，其中含有一些可能导致算法偏见的属性（如年龄、身高、体重、性别、种族等），该实验选用该数据中的 50 060条记录，希望从该数据集中提取到能够涵盖原始数据集的所有年龄段的子集。该实验根据年龄将数据分为六组：0,29、30,39、40,49、50,59、60,69、70+，各个年龄段的记录数分别如下：1 379、18 093、15 354、8 210、6 521、503。第二种数据集是从吕梁山山脉观测得到的森林覆盖类型数据，该数据集共包含 8 种可燃物林木类型：华北落叶松（1）、云杉（2）、白桦（3）、山杨（4）、辽