欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:153 2730 2358
邮箱:910330594@QQ.COM

Q Q:
910330594
网址:http://www.17winner.com
工作时间:
9:00-24:00  

博士论文
当前位置:首页 > 博士论文
海量不完整数据的核心数据选择问题的研究
来源:一起赢论文网     日期:2017-12-01     浏览数:888     【 字体:

 40卷 计算机学报 Vol.402017论文在线出版号No.54 CHINESEJOURNALOFCOMPUTERS OnlinePublishingNo.54———————————————本课题得到国家自然科学基金(No.61632010,61502116,61370217,U1509216),科技部重点研发计划(No. 2016YFB1000703)资助. 刘永楠(通讯作者),男,1986年生,博士研究生,主要研究领域为数据质量、数据完整性.E-mail:cellsi2011@gmail.com. 李建中,男,1950年生,教授,博士生导师,中国计算机学会(CCF)会员,主要研究领域为数据库、无线传感器网络. 高宏,女,1966年生,教授,博士生导师,中国计算机学会(CCF)会员,主要研究领域为数据库、无线传感器网络.海量不完整数据的核心数据选择问题的研究刘永楠李建中高宏(哈尔滨工业大学计算机科学与技术学院, 哈尔滨150001)摘要 在大数据时代,越来越多的带有缺失值的数据需要处理,数据不完整因而成为一种常见的数据质量问题。不完整的数据给大数据的查询、挖掘和分析带来了困难。在某些情况下,数据中的很多缺失值是无法被确定的。只能根据用户的需求,在不完整的数据上选择一部分用户感兴趣的核心数据集合,来提高不完整数据的可用性。完整度较高,规模较小,在用户感兴趣的属性上给出更多完整信息的核心数据集合,能够支持高效的查询处理,提高查询结果的准确性和完整性。本文形式化了核心数据选择问题,证明了这是一个NP-完全问题。由于需要同时优化核心数据集合的完整度,集合的规模,以及对于感兴趣属性的覆盖性这三个目标,现有的基于集合覆盖问题的方法无法解决本文中提出的问题。本文提出了一个采用贪心策略,具有理论保证的近似核心数据选择算法ACSACS首先判断当前的数据集合是否存在一个满足覆盖性要求的子集合。当这样的子集合存在时,ACS尽量选择完整的元组来组成核心数据集合,当使用完整元组无法满足覆盖性的要求时,ACS选择较少的不完整元组。ACS通过限制选择的次数来获得一个集合大小的上界是运行次数常数倍的子集合,并且保证了对于感兴趣的属性的覆盖比例。通过理论分析可知,ACS能够在近似线性的时间内,找到一个大小至多在最优解大小对数因子内的近似核心数据集合,其中被覆盖的感兴趣的属性的比例至少为(1-1/e),包含的不完整元组的个数至多为给定的核心数据集合的大小,其中e是自然对数的底数。通过在DBLPNBA球员信息这两个真实数据集合上的实验,表明了所提出的算法ACS的有效性和高效性,通过在规模更大的合成数据上的实验,表明了ACS的良好的扩展性。关键词 数据质量;数据完整性;不完整数据;核心数据选择;近似算法中图法分类号TP311论文引用格式:刘永楠,李建中,高宏, 海量不完整数据的核心数据选择问题的研究,2017,Vol.40,在线出版号No.54LiuYong-Nan,Li Jian-Zhong,GaoHong,ResearchonCore-SetsSelectiononMassiveIncompleteData, 2017, Vol.40,OnlinePublishingNo.54ResearchonCore-SetsSelectiononMassiveIncompleteDataLIUYong-Nan LIJian-Zhong GAOHong(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)Abstract Inthebigdataera, moreandmoredatawithmissingvaluesaretobehandled, whichmakesdataincompletenessbeacommonproblemofdataquality.Incompletedatabringschallengestoquerying,miningandanalyzingonmassivedata. Insomescenarios,manymissingvaluescannotbedetermined.Accordingtoausersrequirement, onlyasubsetofentiredatasetwithmissingvalues, calledcore-set, hastobeselectedtoimprovethedatausabilityof theentireincompletedataset. Withhigher datacompleteness, smaller size, andmorecomplete informationonattributes of auser's interest, core-sets cansupport efficient queryprocessingandprovidemoreaccurateandcompleteanswerstoqueries.Core-setsselectionproblemisformalizedinthispaper,网络出版时间:2017-05-06 12:13:45网络出版地址:http://kns.cnki.net/kcms/detail/11.1826.TP.20170506.1213.006.html2 计算机学报 2017andsuchproblemisproventobeNP-Complete.Becausetherearethreeobjectstobeoptimizedatthesametime:thecore-setscompleteness, sizeandcoverageonattributesofausersinterest, existingmethodsbasedonsetcover problemscannot solvethecore-setsselectionproblemproposedinthispaper. Anapproximatecore-setselectionalgorithmwiththeoretical guaranteebasedongreedy, calledACS, is proposedinthis paper. TheproposedalgorithmACSfirstlydetermineswhetherornot thereisasubset oftheentiredatasetwithrequiredcoverageontheattributesof ausersinterest. If suchsubsetssatisfyingrequirement oncoverageexist, ACSselectstuplescontainingcompletevaluesasmanyaspossibletoobtainanapproximatecore-set.But ifrequiredcoveragecannotbesatisfiedbyonlytuplescontainingcompletevalues,ACSwill selectafewtuplescontainingmissingvaluestocovertheremainingattributes,butthenumberofsuchtuplecontainingmissingvaluesissmall.Thenumber of selectionsinACSislimitedsuchthatACScanobtainasubset of tuplesofwhichthesizeisboundedbyaconstant factor of thenumber of theselections, andtheratioof attributesof ausersinterestcoveredisguaranteedaswell.Bytheoreticalanalysis,withinnearlylineartime,ACScanselectanapproximatecore-setofsizewithinthelogarithmfactortotheoptimalsize,wheretheratioofattributesofinterestcoveredisat least (1-1/e), withincompletetuplesof at most thesizeof therequiredcore-set, whereeisthebaseof thenatural logarithm. Experimental resultsconductedontworeal-worlddatasetsofDBLPandNBAplayersshoweffectivenessandefficiencyoftheproposedalgorithmACS, andexperimental resultsonsyntheticdatasetswithlargerscaleshowscalabilityofACS.Keywords dataquality;datacompleteness;incompletedata;core-setsselection;approximatealgorithms1引言高速增长的大数据给了人们更多认识世界,发现知识的机会。随之而来的数据质量问题也日益凸显,给大数据的使用和分析带来了困难[1]。有报告显示,在世界顶级的公司中也有超过25%的重要数据是不准确的[2],每年给美国商业造成了6千亿的损失[3]。数据质量问题已经是一个数据科学家面临的基本问题1。不完整数据是常见的低质量的数据,它给很多问题的算法设计带来了挑战[47]。由于信息更新不及时[8],抽取算法的错误[4]等原因,很多应用面对的数据都包含不完整信息,比如影片的打分数据[6]。某些应用中,用户往往只需要有限个对象,比如向用户推荐某些商品[9],或者从众多工人中选择一些合适某项工作的团队[10,11]。对于这类查询,由于某些空值无法填充,因此只能选择完整度较高,用户感兴趣的元组作为查询结果,返回给用户。下面通过一个例子来说明。1ForBig-DataScientists, JanitorWorkIsKeyHurdletoInsights- TheNew York Times.http://www.nytimes.com/2014/08/18/technology/for-big-data-scientists-hurdle-to-insights-is-janitor-work.html.(Accessedon06/02/2016)1. 1中给出了电影信息关系的部分属性和部分元组,其中包含了电影的名字,上映的时间,导演的姓名,观众对电影的评分,从第5列开始给出了电影包含的题材。关系中的空白的部分可以视为缺失值,其中某些空值可以填充比如《谍影重重5》的导演的姓名,而有些空值无法填充,比如《谍影重重5》不是儿童题材的影片。如果用户要求选择3部电影,其中要包含爱情、剧情、惊悚、儿童、商业、动作题材。那么,A1={捉妖记,使徒行者,谍影重重5}A2={捉妖记,使徒行者,湄公河行动}A3={捉妖记,谍影重重5,湄公河行动},都可以作为查询结果返回给用户。可以发现集合AC1={捉妖记,谍影重重5}AC2={捉妖记,湄公河行动}包含的元组覆盖了用户指定的感兴趣的属性,并且其大小没有超过用户给定的大小限制(3部)。但是,为了能够提供较为完整的信息,除了指定的属性集合外,应该尽可能少的包含含有空值的元组。因此,AC2包含了较AC1更为完整的元组,AC2可以看作一个能够回答用户查询的核心数据集合。可以发现,如果能高效地选择核心数据集合AC2,就能快速地响应用户的查询。论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 31 电影信息关系核心数据集合有很多用途。1)通过核心数据集合可以判断,现有的数据集合是否包含了感兴趣的属性的信息,可以以此来判断现有的数据集合的完整程度,作为衡量数据质量的一个指标。因为如果无法选择一个类似于例子1中的AC2这样的核心数据集合,那么用户指定的属性是无法被完全覆盖的,或者很难有一个完整度较高的查询结果。2)可以为后续的操作提供完整度高,规模小的初始集合。由于核心数据集合规模较小,使得一些操作可以高效地进行;同时核心数据集合覆盖了用户感兴趣的属性的集合,这个集合往往包含更少的空值,可以提供利于计算的有效信息。比如,可以根据历史查询信息,找到用户最近喜欢查询哪些类型的影片,然后在核心数据集合上运行推荐算法,来进一步选出满足用户喜好的影片,或者直接回答某些计算密集型的查询[6],免去了对于大量不在结果集合中的不完整数据的处理,从而提高了效率。类似的,可以通过指定必备的技能集合,来缩小候选人集合的规模,来高效地求解队伍组建问题[10,11]。如何从海量的不完整数据中抽取这样的核心数据集合,是本文所研究的问题。将数据根据用户要求划分,来回答用户的查询,已经有了一些研究结果,但是这些方法都存在不同的缺点,下面分别进行说明。通过核心数据来快速地回答某些查询[12,13],广泛地应用于计算几何和机器学习领域。然而这些方法都针对数值型数据,无法应用于推荐系统等包含分类属性的数据中。建立索引[14]和近似查询[15, 16]可以提高计算的效率。由于没有将数据按照完整程度进行区分,完整度低的元组一方面无法提供有效的信息,进而导致近似结果产生较大的误差;另一方面浪费了计算的资源。文献[17]分析了数据中错误类型,文献[18]给出了近似结果的误差分析。但是这些方法都没有给出选择高质量数据的方法。通过数据摘要[19, 20]和数据压缩方法能提供简洁的数据表示方式,减少了需要处理数据的规模,但是,如果直接用于计算通常需要额外的计算代价,来获得数据的特性[21]。而且进行变换后,数据的特性有很多损失,多数只能回答聚集操作[16,22],无法支持某些基于属性值的特点进行的分析,例如group-by操作[23]。如例1所示,核心数据的选择问题扩展了集合覆盖问题[24],以及最大覆盖问题[25,26],因此这两个问题的现有方法和结论无法直接应用于核心数据选择问题。文献[27]考虑了同本文相似的问题,但是,它研究的问题假设总能找到一条元组覆盖所有的属性,在实际的问题中,这个假设不一定能被满足,尤其是在不完整数据上。此外,它提出的算法的性能依赖于参数的选择,而且无法通过简单地扩展,支持不完整数据上的核心数据选择,更详细的讨论参见相关工作部分,以及实验对比部分。为了高效地选择包含用户感兴趣属性的较为完整的数据,解决已有方法的问题,本文研究了核心数据的性质,分析了核心数据选择问题的时间复杂性,证明了这是一个NP-完全问题;提出了具有质量保证的近似算法,通过理论分析可知,这个算法能够在近似线性的时间内,抽取覆盖用户感兴趣属性总数一定比例的核心数据集合。本文的主要贡献如下:1. 形式化了不完整数据上的核心数据选择问题,分析了核心数据选择问题的计算复杂性,并证明了这是一个NP-完全问题。2. 提出了一个有误差保证的高效的核心数据抽取算法。当用户给定包含N条元组的数据集合,感兴趣的属性的大小是n,要求至少覆盖这些属性的比例是θ时,近似算法能在O(Nnlnn)的时间内,输出一个同优化解的大小比值在O(lnn)内的近似核心数据集合,这个集合至少覆盖了(11/e)θn的感兴趣的属性,其中e是自然对数的底数。3. 通过在NBA数据集合和DBLP数据集合上的大量实验结果,表明了所提出的算法能够在较短的时间内,在不完整数据上抽取满足覆盖要求的近似核心数据。通过在合成数据上的实验结果,说明了本文提出的近似方法具有良好的扩展性,能够在海量不完整数据上高效地抽取近似核心数据集合。本文的组织结构如下:在第二部分,给出了核心数据选择问题的形式化定义,并给出了这个问题的时间复杂性的分析结果以及证明;在第三部分,给出近似核心数据的选择算法ACS,对算法的理论分析和改进的策略;在第四部分,给出了近似算法4 计算机学报 2017年在真实数据集合以及合成数据集合上的实验结果以及分析。在第五部分,综述了相关的研究工作。第六部分给出了结论。2问题的定义和复杂性2.1 核心数据选择问题的形式化定义给定属性集合Att={Aj}1jm,感兴趣的属性集合AIAtt,数据集合T是定义在Att上的关系数据集合,其中若一条元组tT中至少一个不属于AI的属性值为空值,则称t是一条“不完整元组”,否则称为“完整元组”。如果t在属性Ai上的属性值不是空值,并且AiAI,则称t覆盖了属性Ai,元组t覆盖的属性是其覆盖的所有的属性的并集,表示为Ben(t)。元组集合T’覆盖的属性集合,是其中所有元组覆盖的属性的并集,即Ben(T)=tTBen(t)。根据上面的定义,下面给出核心数据集合选择问题的形式化定义。定义1.(核心数据选择问题)输入:定义在属性集合Att上的关系数据集合D,感兴趣的属性集合AIAtt,正整数k,实数θ∈(0,1]。输出:至多k条元组的集合TCD,要求TCD中包含不完整元组的数目最少,并且|Ben(TCD)|≥θ|AI|2.2 核心数据选择问题的时间复杂性由于需要同时优化集合大小,覆盖性和不完整元组的个数,因此核心数据集合的选择问题是一个很难的问题,其时间复杂性由下面的定理给出。定理1. 核心数据选择问题是NP-完全的。证明. 容易知道,可以猜测一个原始数据集合的子集作为核心数据集合,并在多项式时间内验证其中元组的数目,对于感兴趣属性集合的覆盖程度,以及包含的不完整元组的个数是否符合条件,因此核心数据选择问题在NP中。下面给出一个从集合覆盖问题的多项式时间的规约方法来证明核心数据选择问题的复杂性。给定一个集合覆盖问题的实例P={US},其中U是一个元素的集合U={a1,a2,...,an},以及由U中元素的某些子集合组成的集合S={Si| Si2U},即S2U,其中2U表示集合U的幂集合。集合覆盖问题是要寻找一个最小的由S中元素组成的子集合,使得这个子集合中的元素的并集能够覆盖U中所有的元素。设核心数据选择问题的实例是C={D,AI,k,θ},其中D是给定的数据集合,AI是感兴趣的属性的集合,k是核数据中包含元组数目的上限,θ是至少覆盖的感兴趣的属性的比例。下面给出一个从集合覆盖问题的实例P到核心数据选择问题的实例C的规约方法fD中的属性包含两个部分,一个部分是U中全部的元素,另一个部分是属性M,即D中的属性集合是Att(D)=U{M}。指定感兴趣的属性集合AI=Att(D),指定需要覆盖的比例θ=|U|/(|U|+1) =n/(n+1),核数据集合大小的上限k=|S|。下面给出D中元组的具体形式:对于S中的每个集合Si,向D中插入一条元组ti,如果U中的元素ajSi中,那么对应的ti的属性aj的属性值为1,表示这个属性值是完整的。ti的属性M的值是空值,属性值为0,将其余的非1的属性值都视为空值,将其属性值设为0。可以知道,上面的规约f在多项式时间内可以完成。可以发现,由于AI 指定了D中的除了M外所有属性,且所有的元组在属性M上的值都是空值,因此D中的元组都是不完整的。下面证明核心数据选择问题的实例C的一个解,与集合覆盖问题的实例P的一个解的对应关系,即利用上面的规约f,当给定一个C的解的实例S(C)后,可以得到一个P的解的实例S(P),反之亦然。1.(S(P)S(C))。当给定一个集合覆盖问题的解的实例S(P)时,由于S(P)已经指定了一个S的子集合,由规约f中建立数据集合的方法可以知道,S中的每一个集合Si都对应了一个D中的元组ti,在解集中的每一个集合Sj也对应了一个D中的元组tj,因此,S(P)中的每个子集合对应的元组集合,就指定了一个D中元组的集合S(C)。由于S(P)已经覆盖了所有的U中的元素,相应的,S(C)也覆盖了D中除了M以外的所有的属性,即S(C)覆盖的属性的比例是|Att(D)\{M}|/|Att(D)| =n/(n+1),显然S(C)的大小与S(P)的大小相同,不超过|S| =k,并且D中的元组都是不完整的,所以S(C)是核心数据选择问题的一个解。2.(S(C)S(P))。当给定一个核心数据集合选择问题的解的实例S(C)时,根据对核心数据的要求,S(C)已经覆盖了至少n/(n+1)AI中的属性,由于AIM属性在所有的元组上都是空值,无法被覆盖,所以,S(C)一定覆盖了除了M以外的所有属性,即全部的U中元素对应的属性。由规约f的论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 5过程可以知道,每条S(C)中的元组tj,对应一个S中的集合Sj,因此,S(C)中的元组也指定了S的一个子集合S(P),由于S(C)覆盖了全部的U中元素对应的属性,因此,由规约f可以知道,S(P)覆盖了U中的全部元素。由于S(C)的大小没有超过k=|S|,因此,S(P)S的一个子集,即S(P)是集合覆盖问题的一个解。证毕.3核心数据选择问题的近似算法通过前面的定理可以知道,核心数据选择问题是一个NP-完全问题。因此,需要设计一个高效率的近似算法来选择一个近似的核心数据集合。为了得到一个高效率的近似算法,需要放松核心数据选择问题的三个优化目标。采用同最大覆盖问题[25]相似的思想,我们设计了近似核心数据选择算法ACSACS采用贪心的策略,当用户指定感兴趣属性个数后,放松对不完整元组数目的限制,选择比最优解多一些的近似核心数据集合,能够保证至少覆盖(11/e)的比例。在这一部分中,在3.1给出近似核心数据选择算法ACS,在3.2分析这个算法,并给出算法的时间复杂性分析结果和对近似结果的质量分析,在3.3给出对于算法的改进的策略。3.1 近似核心数据选择算法ACS在下面的描述中,A表示完整的元组集合,B表示不完整的元组集合。算法的直观思想是,尽可能地从A集合选择元组,来减少不完整元组的个数。如果通过选择A集合中的元组,已经能够满足覆盖要求,就不必使用B集合中的元组,否则,用A集合的元组尽可能的覆盖后,再选择B集合中的元组。算法1给出核心数据集合近似选择算法,扫描一遍A集合,得到A集合能够覆盖的元素集合R0,即能够覆盖感兴趣的属性的数目。再扫描一遍B集合,得到B集合能够覆盖的元素集合R1,如果|R0| +|R1| <(11/e)θn,说明即使全部选择这些元组,也无法完成指定比例的覆盖,因此返回“无法完成”。否则,在A集合执行贪心的集合覆盖[25],即每次选择覆盖剩余AI属性个数最多的元组,如果两条元组覆盖的个数相同,任意选择一条,然后从AI中去掉已经被覆盖的属性,共执行(ln((11/e)θn)+1)次,每次选择k条,期间如果已经覆盖完成就提前终止。如果A集合完成后,覆盖的元素个数小于(11/e)θn,那么在B集合执行贪心的集合覆盖一次,共选择k条元组,如果能提前达到覆盖要求,就提前终止。在近似核心数据选择算法ACS中,假设每次的选择都能覆盖尽可能多的元素,在大数据背景下,由于数据是丰富的,具有覆盖相同感兴趣属性的元组是充足的,这一假设能够被满足,比如很多用户都看过类似的电影[6],很多员工有相似的技能[11]。如果最优解能用k条元组覆盖要求的感兴趣属性的个数,那么,接下来每次需要覆盖的属性个数,一定也可以被k条元组覆盖。算法1. 近似核心数据选择算法ACS.输入:定义在属性集合Att上的关系数据集合T,其中|T|=N,感兴趣的属性集合AIAtt|AI|=n, 正整数k,实数0<θ≤1。输出:近似核心数据集合TCD1. TCDϕ;2. 扫描一遍A集合,得到A集合能够覆盖的元素集合R0;3. 扫描一遍B集合,得到B集合能够覆盖的元素集合R1;4. IF|R0| +|R1|<(11/e)θnTHEN5. RETURN“无法完成”;6. ELSE7. //先在A集合上进行选择8. FORi1TO(ln((11/e)θn)+1)DO9. FORj1TOkDO10. ejGreedySetCover(A,AI);11. AIAI\{Ben(ej)}12. TCDTCDej;13. IFCoverage(TCD)(11/e)θnTHEN14. RETURNTCD;15. ENDIF16. ENDFOR17. ENDFOR18. //再在B集合上进行选择19. FORj1TOkDO20. ej GreedySetCover(B,AI);21. AIAI\{Ben(ej)}22. TCDTCDej;23. IFCoverage(TCD)(11/e)θnTHEN24. RETURNTCD;25. ENDIF26. ENDFOR27. ENDIF28. RETURNTCD;6 计算机学报 20173.2 近似核心数据选择算法ACS的分析由于衡量近似核心数据选择算法的优劣涉及四个目标:时间复杂性,核心数据集合的大小,核心数据集合包含不完整元组的个数,核心数据集合覆盖AI中属性的个数,因此,从这4个方面分别给出分析,分析的结果由下面的定理给出。定理2. 近似算法能够在O(Nnlnn)时间内选择O(lnn)k条元组,至少覆盖(11/e)θn个感兴趣的属性,得到的近似核心数据集合的不完整元组的个数与最优个数的比值不超过k。其中,n是感兴趣的属性的数目,N是元组的总数。证明.下面分4个方面给出分析,来证明上面的定理。以下证明中假设最优解能够根据用户的需求,最多用k条元组完成对AI中指定比例属性的覆盖。(ACS的时间复杂性)用NA表示A集合中元组的数目,NB表示B集合中元组的数目。首先,每次在A集合上进行贪心的集合覆盖,选择覆盖剩余属性个数最多的元组,这一步在O(NAn)时间内可以完成,每次贪心选择要选择k条元组,总共进行(ln((11/e)n)+1)次,因此,在完整元组集合上的操作在O(kNAn(ln((11/e)n)+1))内,即O(kNAnlnn))可以完成。然后,如果还需要在B集合上执行一次大小为k的贪心选择,也可以在O(kNBn)的时间内完成。由于NANB都不会超过N。因此,近似算法可以在O(Nnlnn)内完成。(核心数据集合的大小)如果最优解只用A集合可以完成核心数据的选择,那么,近似算法也一定只用A集合完成核心数据的选择,因为在最坏的情况下,ACS选择的元组已经覆盖了A中元组能够覆盖的所有属性。因此近似核心数据集合的大小与最优解的大小的比值就是运行的次数,即(ln((11/e)θn)+1)=O(lnn)。如果最优解需要用B集合完成,那么,优化解至少引入一条不完整的元组。如果这样,一定是因为某些没有被覆盖的属性被某条B中的元组覆盖,那么,因为近似算法采用贪心的方法,也一定选中了这条。否则,最优解至少需要在B集合中选择2条元组,最多用k条元组,而近似算法最多用k(ln((11/e)θn)+1+1)条。因此,近似比是O(lnn)。因此,由于用户指定了最多使用k条元组来完成核心数据的选择,如果最优算法在k条元组内就能完成核心数据的选择,近似算法需要用k(ln((11/e)θn)+1+1)条,即kO(lnn)条。(核心数据集合中不完整元组的个数)如果最优解只用A集合中的元组完成,那么近似算法也同样只选择了A集合中的元组,因此,近似算法选择的元组也都是完整的。如果最优解用k条元组完成了覆盖,其中包含了B集合中的元组。那么,按照近似算法,当A中的元组无法满足覆盖要求时,在B中最多选择k条元组,那么,近似算法的不完整元组的个数就是k,而最优解是选择了B中元组的至少一条,因此,近似比不超过k。(覆盖的AI中属性的个数)按照近似算法,在A集合上执行贪心的集合覆盖,如果已知A集合能够覆盖|R0|的属性,那么,进行一次覆盖之后,可以覆盖的属性个数记为M1,应该满足M1(11/e)|R0|[25],因此,经过一次覆盖之后,剩余的属性不超过|R0|/e,同理,再次覆盖之后,剩余的属性不超过|R0|/e2,那么经过l次之后,剩余的属性不超过|R0|/el。假设l次之后已经剩余至多一个属性了,那么|R0|/el1,因此有lln(|R0|),即最多经过(l+1)次就能完成全部属性的覆盖。如果设置要覆盖的比例为(11/e),即需要覆盖(11/e)θn的属性,如果只用A集合就能完成,应该有|R0| (11/e)θn,所以,带入上面的式子,最多经过(ln((11/e)θn)+1)次,就能完成预计的覆盖要求。如果只用A集合无法完成,那么就应该有|R0|(11/e)θn,所以,带入上面的式子,最多经过(ln((11/e)θn)+1) 次,已经覆盖了所有的A中的元素,剩下的就只能从B中选择。在最坏的情况下,A集合只能覆盖i个属性,其中0i<θn,那么,B集合可以覆盖剩余的(θni)个元素,那么同理,经过p次之后,应该满足至少覆盖了(11/ep) 比例的属性,即应该有(θni)(11/ep)+i(11/e)θn,假设θni,即采用B集合能够完成覆盖。那么满足pln((θni)/θn)+1,那么,由于ln((θni)/θn)<ln(θn/θn)=ln1=0,所以p至少为1即可,即只需在B集合中进行一次大小为k的贪心集合覆盖即可,因为最优解最多用k条元组就可以覆盖全部属性。证毕.如定理2给出的,在某些数据集合上,近似算法可能选择超过k条元组的近似核心数据集合,最多会选择O(lnn)k条元组。这是因为,为了降低核论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 7心数据集合中不完整元组的数目,需要尽可能地从A集合中进行选择。为了覆盖至少(11/e)θn的感兴趣属性,可能需要多次从A集合进行选择,来覆盖新的感兴趣属性,由于每次选择k条元组,这样就会导致选择的近似核心数据集合的规模超过k,但是正如分析中所指出的,超出的比例不会太多,是以O(lnn)为上界的。达到上界时,A集合所能覆盖的感兴趣属性已经都被覆盖了,利用了最多O(lnn)k的元组。近似算法ACS通过多次在A集合中进行选择,虽然增加了输出的核心数据的规模,但是能够使得感兴趣属性更多地被完整元组所覆盖。在实验4.3节的E部分,通过实验说明了ACS输出的近似核心数据规模虽然较大,但是其中包含的不完整元组的个数较少。3.3 近似算法的改进策略在这一部分中,讨论对算法ACS的改进策略,主要考虑三个问题:1. 选择的近似核心数据的规模小于给定的大小时,是否需要继续添加元组。2. 是否可以在整个数据集合上贪心地进行选择,而不是像本文的算法ACS,先在完整的元组中进行选择,然后在不完整的元组中进行选择。3. 如果用户需要在同一个属性上,需要多个不同的值,如何修改本文提出的算法,修改后是否仍然具有质量保证。对于第一个问题,如果数据的完整度比较高,或者用户给定的感兴趣的属性集合比较容易被满足时。往往(近似)核心数据的大小会小于用户给定的大小,此时需要不同的策略来将结果返回给用户。比如,可以直接给用户返回现有的集合,并告知AI集合中的大部分属性已经被覆盖。或者,继续按照贪心的方式选择覆盖AI中覆盖比例高的元组,直至达到用户设定的大小,这样可以在已经覆盖的属性上面提供更多的候选值给用户,对于有序关系的数值类属性,可以便于用户进一步进行选择,但是对于两个属性值无法比较大小的类别属性,用户可能需要参考额外的信息进行选择。对于第二个问题,本文的选择策略是,尽可能选择完整的元组,除非完整的元组无法满足覆盖要求。如果不区分完整元组集合以及不完整元组集合,整体进行贪心选择,也能够达到至少(11/e)的对最优解的覆盖比例[25],但是,这样往往无法保证选择较少的不完整元组,可能使得选出的结果集合,无法为用户或者后续的操作提供高质量的候选集合,影响后续操作的效果和效率。对于第三个问题,用户指定在某个属性上需要提供多个不同的值,方便用户进行未来的选择。可以在代码中添加一个计数器,控制这个属性被覆盖的次数。将计数器的初始值设为用户指定的个数,每被覆盖一次,计数器的数值减一,只有计数器数值为零,才认为这个属性被覆盖。但是,这样就要求,这个属性一定被覆盖,因为近似算法选择的核心数据集合只保证能够覆盖指定个数的属性,并没有指定某一个属性一定被覆盖。因为在每一轮进行贪心选择的时候,无法保证这个用户指定的属性,一定被覆盖剩余属性最多的元组所覆盖。可以采取一种保守的策略,当每次进行贪心选择的时候,如果两条元组覆盖的剩余属性的个数相同,优先选择覆盖了较多指定个数的属性的元组,如果包含的这样的属性的个数相同,那么任意选择一条。这样修改后,运行一次近似算法ACS仍能具有原来的覆盖属性的个数,近似核心数据大小,以及不完整元组的个数较少的保证。然后,统计这次的选择结果中对用户指定了个数的属性的覆盖情况,根据覆盖的个数,可以选择是否再次运行算法,再次运行前,将已经覆盖的属性和相应的计数器进行更新。但是,需要运行多少次能够达到用户满意的覆盖程度,无法进行估计,与实际的数据的特性有关。在4.2节的D部分,通过多次运行ACS的方式,探索了选出的核心数据集合对指定的属性的覆盖次数。4性能评价在这一部分中,通过在真实数据集合和合成数据集合上的实验来分析所提出的近似算法的有效性和性能。根据核心数据选择问题的定义,通过实验来分析所提出的近似算法的时间效率,输出的近似核心数据集合的大小,对感兴趣属性的覆盖比例,以及所包含的不完整元组的个数。4.1 实验设置我们用C++语言编写了近似算法ACS的代码。实验中进行对比的Baseline算法是文献[27]中的算法CMCCWSC,采用C++编写了代码。实验在一台联想台式机上执行,机器的配置是64Windows7SP1 旗舰版操作系统,83.40GHzi7-3770CoreCPU32GB内存,500G机械硬盘。每个设置的参数下,运行10次近似算法,下面报告的运行时间是平均时间。8 计算机学报 2017A. 数据集合(NBA数据集合)为了模拟队伍组建问题,采用NBA球员信息集合,并以此为基础生成了合成的数据集合。NBA球员数据集合来自于NBA球员信息网站2,包含了从1946年到2014年的NBA球队和球员信息,表中包含了24个属性:球员的编号、球员的名字、赛季的名字、球员的年龄、球队的简称、球队所在的联盟、参加的比赛的数目、赛季的得分、球队参加的赛季、队伍所在的联盟、球队的名称、球队的教练的名字、球队成立的时间、球队解散的时间(或者到现在)、球队的存在的时间、球队参加的比赛次数、球队获胜的次数、球队失败的次数、球队获得冠军的次数、体育场的主场球队的名字、体育场的起止使用年、体育场的名称、体育场的所在地、体育场的容量。(DBLP数据集合)为了模拟队伍组建问题,采用DBLP中的会议论文信息集合,并以此为基础生成了合成的数据集合。DBLP会议论文信息来自于DBLP网站3,包含了截至到20167月的全部的会议论文信息,表中包含了8个属性:论文的编号,论文的作者,论文的题目,论文的发表时间,论文集的名字,交叉链接的键值,出版商的名字,论文集的编辑的名字。两个真实数据集合的统计信息如表1所示:表1 真实数据集合统计信息数据集合 属性个数 元组个数NBA数据集合 24 19197DBLP数据集合 8 1819273(合成数据集合)为了探究所提出的算法,在具有不同的完整度以及元组个数的集合上的性能,我们在真实的NBA集合中以0.2的概率,随机地将属性值设为空值,然后将每条元组按照一定倍数进行扩增,每条元组以0.8的概率加入生成的数据集合。此外,为了分析更多属性和更多不完整属性值对近似算法的影响,在合成数据中加入了更多的属性,这些属性所包含的属性值以0.6的概率为空值,具体的参数会在下面的每个实验设置中详细说明。B. 评价指标为了评估所提出的近似算法的有效性和效率,关注4个方面的实验效果:1)近似算法运行的时间,2http://www.basketball-reference.com3http://dblp.dagstuhl.de/xml/release/是否在可以容忍的范围内;2)所选择的近似核心数据集合的大小,是否没有过多地超出所要求的大小;3)对感兴趣的集合的覆盖比例,是否至少达到了近似算法预期的比例;4)包含的不完整元组的个数,是否尽可能得少。在下面的实验中,我们将变化不同的参数,分别报告在真实数据和合成数据上的实验结果,观察上面的4个指标的满足情况。4.2 在真实数据上的实验结果为了研究本文提出的算法的有效性和效率,我们在真实的NBA数据集合和DBLP数据集合上模拟队伍组建问题,观察上面的4个指标的被满足情况。其中,NBA数据集合中,不完整属性值占全部属性值的比例是12.3%,而DBLP数据集合中这个比例是8.2%A. k的变化的影响在这组实验中,通过改变用户要求的核心数据的大小k,观察上面4个指标的满足程度。实验中,在NBA数据集合中,随机选择15个用户感兴趣的属性作为AI,在DBLP数据集合中,随机选择6个用户感兴趣的属性作为AI,覆盖比例θ设置为0.9k5变化到20。实验的结果如图2和图3所示,其中横坐标给出了k的大小,纵坐标给出了算法运行的时间。图2 NBA数据集合上k的变化对运行时间的影响对于本文提出的算法ACS,通过在得到的近似核心数据计算上面的4个指标,可知这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如在NBA数据集合上,当用户要求k等于5时,近似算法选择了4条元组已经能够覆盖全部的15个属性。可以根据不同的策略,再选择1条元组,改进已有的选择结果,完成核心数据的选择。即使数据中包含很多的空值,选出的论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 94条元组都是完整的,共消耗0.112秒。而在DBLP数据集合上,当用户要求k等于5时,近似算法也选择了4条元组已经能够覆盖全部的6个属性。可以根据不同的策略,再选择1条元组,完成核心数据的选择。DBLP数据集合的完整度较高,选出的4条元组都是完整的,共消耗0.084秒。通过图2和图3可以发现,虽然两个Baseline算法CMC和算法CWSC都能够满足4个指标,但是它们消耗了更多的时间,其中算法CMC所消耗的时间最多,因为算法需要多次尝试来猜测一个近似解,由于给定的k值不同,多次尝试需要消耗更多的时间。图3 DBLP数据集合上k的变化对运行时间的影响通过图2和图3可以发现,近似算法能够高效地选择近似的核心数据集合,即使两个数据集合完整度有一定差距,还是能够找到满足覆盖比例的近似核心数据集合,并且随着k的变化,时间消耗的变化在很小的范围内波动。主要原因是某些元组的完整属性值很多,因此一旦被选中,就能使得选择很快被完成,即使k给出的值很大,也可以提前结束选择过程。B. θ的变化的影响在这组实验中,通过改变用户要求的覆盖比例θ,观察上面4个指标的满足程度。在实验中,在NBA数据集合上随机选择15个用户感兴趣的属性作为AI,在DBLP数据集合中,随机选择6个用户感兴趣的属性作为AI,用户指定的核心数据的大小k设为10,θ从0.6变化到1.0。实验结果如图4和图5所示,其中横坐标给出了θ的大小,纵坐标给出了算法运行的时间。对于本文的算法ACS,通过在得到的近似核心数据计算上面的4个指标,可知这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如在NBA数据集合上,当用户要求θ等于0.8时,近似算法选择了8条元组已经能够覆盖15AI中的属性。可以根据不同的策略,再选择2条元组,改进已有的选择结果,完成核心数据的选择。即使数据中包含很多的空值,选出的8条元组都是完整的,共消耗0.111秒。在DBLP数据集合上,当用户要求θ等于0.8时,近似算法选择了7条元组已经能够覆盖6AI中的属性。可以根据不同的策略,再选择3条元组,改进已有的选图4 NBA数据集合上θ的变化对运行时间的影响图5 DBLP数据集合上θ的变化对运行时间的影响择结果,完成核心数据的选择。在完整度较高的DBLP数据集合上,选出的7条元组都是完整的,共消耗0.085秒。通过图4和图5可以发现,虽然两个Baseline算法CMC和算法CWSC都能够满足4个指标,但是它们消耗了更多的时间,其中算法CMC所消耗的时间最多,因为算法需要多次迭代来猜测一个近似解。虽然θ不断变化,但是由于DBLP中的元组比较完整,因此容易找到满足条件的核心数据集合,因此整体来看在DBLP数据集合上消耗的时间10 计算机学报 2017年较小。通过图4和图5发现,近似算法能够高效地选择近似的核心数据集合,θ的变化没有引起较大的时间消耗的波动。主要原因是某些元组的完整属性值很多,因此一旦被选中,能够很快达到用户指定的覆盖要求,由于近似算法发现满足比例就提前了,因此选择往往很快就完成了。C. AI的变化的影响在这组实验中,通过改变用户感兴趣的属性集合AI,观察上面4个指标的满足程度。在实验中,在指定AI的个数后,随机选择感兴趣的属性。用户指定的核心数据的大小k10,用户指定的覆盖比例θ设置为0.9AI的大小从4个变化到8个。实验结果如图6和图7所示,其中横坐标给出了AI的大小,纵坐标给出了算法运行的时间。图6 NBA数据集合上AI的变化对运行时间的影响图7 DBLP数据集合上AI的变化对运行时间的影响对于本文的算法ACS,通过在得到的近似核心数据计算上面的4个指标,这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如NBA数据集合上,当用户给出AI的大小为7时,近似算法选择了6条元组已经能够覆盖7AI中的属性。可以根据不同的策略,再选择4条元组,改进已有的选择结果,完成核心数据的选择。即使数据中包含很多的空值,选出的6条元组都是完整的,共消耗0.113秒。在DBLP数据集合上,当用户要求AI大小为7时,近似算法选择了6条元组已经能够覆盖7AI 中的属性。可以根据不同的策略,再选择4条元组,改进已有的选择结果,完成核心数据的选择。在完整属性值较多的DBLP数据集合上,选出的6条元组都是完整的,共消耗0.085秒。通过图6和图7可以发现,虽然两个Baseline算法CMC和算法CWSC都能够满足4个指标,但是它们消耗了更多的时间,其中算法CMC所消耗的时间最多,因为算法需要多次迭代来猜测一个近似解。虽然AI不断变化,但是由于DBLP中的元组比较完整,因此容易找到能够覆盖足够数目的AI中的属性的核心数据集合,因此整体来看在DBLP数据集合上消耗的时间较小。通过图6和图7可知,近似算法能够高效地选择近似的核心数据集合,虽然AI有不同的变化,引起较小的时间消耗的波动,在可以接受的范围内。主要原因是某些元组完整度较高,可以较多的覆盖AI中指定的属性,因此,一旦被选中,可以使得选择很快完成。D. 指定某个AI属性的个数在这组实验中,通过6次运行算法来查看所选择的AI属性被覆盖的次数。在实验中,随机选择8个用户感兴趣的属性作为AI,覆盖比例设置为0.9k设为10。实验结果如图8和图9,其中横坐标是8个属性的编号,纵坐标给出了在6次运行后,每个属性被覆盖的个数。图8 NBA数据集合上对AI中属性的覆盖次数通过图8和图9可以发现,指定AI中的属性后,论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 11每次运行都会选择一些被覆盖的属性。由于ACS在选择满足覆盖比例的属性后就会提前终止,因此,对各个属性的覆盖次数并不相同,同时覆盖的次数也由数据集合本身的性质决定。可以发现在图8中对第6个属性仅仅覆盖了2次,而对第一个属性覆盖了6次。整体来看,由于DBLP数据的完整程度比较高,因此对属性的覆盖次数很多,NBA数据集合较不完整,特别某些属性空值很多,因此不是对每个属性都覆盖了很多次。图9 DBLP数据集合上对AI中属性的覆盖次数正如3.3节的第三点改进策略所分析的,由于ACS要保证每次选择时覆盖一定比例的属性,并不能一定覆盖某个属性,同时由于数据集合本身的原因,无法直接保证某个属性被覆盖的次数。但是,可以通过多次运行的方式来对某些属性多次覆盖,来达到用户的要求。E. 真实数据集合实验结果总结在真实数据上的实验中,本文提出的算法ACS能够根据不同的用户需求,高效地选择近似的核心数据。ACS能够满足4个评价指标,并且不同的参数变化没有引起性能上太大的波动。通过上面的实验图可以发现,ACS的性能要优于2Baseline算法CMCCWSC,其中CMC算法通过试探的方式来进行近似核心数据的选择,因此在某些情况下,多次的试探会极大地增加选择的时间,导致性能会有所降低。4.3 在合成数据上的实验结果为了研究本文提出的算法的效率,以及选择的近似核心数据集合的质量,我们在合成的NBA数据集合上模拟队伍组建问题,观察上面的4个指标的被满足情况。由于DBLP数据集合的实验结果类似,并且同NBA数据集合都是合成的集合,因此我们在这部分只给出在合成的NBA数据集合上的实验结果。为了更好的观察我们提出的算法的效率,下面的前三组实验在同一个合成的NBA数据集合上进行,之后的两组实验观察不同的元组总数的影响时,采用不同的合成数据集合。前三组实验所使用的合成的数据集合包含了74个属性,6910080条元组,大小为2.31GA. k的变化的影响在这组实验中,通过改变用户要求的核心数据的大小k,观察上面4个指标的满足程度。在实验中,随机选择8个用户感兴趣的属性作为AI,覆盖比例设置为0.9k5变化到20。实验结果如图10所示,其中横坐标给出了k的大小,纵坐标给出了算法运行的时间。图10 NBA合成数据集合上k的变化对运行时间的影响通过在得到的近似核心数据计算上面的4个指标,这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如当用户要求k等于5时,近似算法选择了2条元组已经能够覆盖全部的8个属性。可以根据不同的策略,再选择3条元组,改进已有的选择结果,完成核心数据的选择。由于数据集合中包含很多的空值,完整的元组对AI的覆盖比例很低,因此选择的都是不完整的元组,共消耗83.27秒。可以发现,近似算法能够高效地选择近似的核心数据集合,随着k的变化,时间消耗的变化在可以容忍的范围内。虽然在合成数据集合中加入了很多空值,但是由于AI属性的指定具有随机性,并且给定的个数比较小,而且合成的某些元组仍然可以覆盖多数的AI属性,因此选择的过程较快。B. θ的变化的影响在这组实验中,通过改变用户要求的覆盖比例θ,观察上面4个指标的满足程度。在实验中,随机选择8个用户感兴趣的属性作为AI,用户指定的核心数据的大小k设为10,θ从0.6变化到1.0。实验结果如图11所示,其中横坐标给出了θ的大小,12 计算机学报 2017年纵坐标给出了算法运行的时间。通过在得到的近似核心数据计算上面的4个指标,这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如当用户要求θ等于0.8时,近似算法选择了4条元组已经能够覆盖7AI中的属性,而近似算法只需覆盖5个属性就可以了。可以根据不同的策略,再选择6条元组,改进已有的选择结果,完成核心数据的选择。由于数据集合中包含很多的空值,选出的4条元组都是不完整的,共消耗78.31秒。图11 NBA合成数据集合上θ的变化对运行时间的影响可以发现,近似算法能够高效地选择近似的核心数据集合,θ的变化,没有引起较大的时间消耗的波动。在这组实验中,由于加入了额外的属性,很多的元组都是不完整的,但是也有着比较高的对AI的覆盖率,因此虽然θ在变化,但是实际需要覆盖的个数变化不大,因此选中4条覆盖率较高的元组后,选择就完成了。C. AI的变化的影响在这组实验中,通过改变用户感兴趣的属性集合AI,观察上面4个指标的满足程度。在实验中,在指定AI的个数后,随机选择感兴趣的属性。用户指定的核心数据的大小k设为10,用户指定的覆盖比例θ设置为0.9AI的大小从6个变化到15个。实验结果如图12所示,其中横坐标给出了AI的大小,纵坐标给出了算法运行的时间。通过在得到的近似核心数据计算上面的4个指标,这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如当用户要求AI大小为11时,近似算法选择了8条元组已经能够覆盖10AI中的属性,而近似算法只需覆盖7个属性就可以了。可以根据不同的策略,再选择2条元组,改进已有的选择结果,完成核心数据的选择。由于数据集合中包含很多的空值,选出的8条元组都是不完整的,共消耗80.34秒。可以发现,近似算法能够高效地选择近似的核心数据集合,AI的变化,引起较小的时间消耗的波动,在可以接受的范围内。在这组实验中,AI变化比较大,因此需要较多次的贪心选择来完成,但是由于仍然有完整度较高的元组,能够很快的覆盖AI中的属性,因此消耗的时间,并没有比之前的实验增多太多。图12 NBA合成数据集合上AI的变化对运行时间的影响D. 元组的总数的变化的影响在这组实验中,通过改变数据集合大小,观察上面4个指标的满足程度。在实验中,随机选择8个属性作为感兴趣的属性集合AI,用户指定的核心数据的大小k设为10,用户指定的覆盖比例θ设置为0.9。通过设置每条元组的扩增倍数Aug,然后按照前面描述的方式修改和加入元组得到数据集合。扩增倍数Aug500变化到4000,根据前面的生成方式,修改后的元组以0.8的概率加入到数据集合中。用于实验的文件的统计信息如表2所示,实验结果如图13所示,其中横坐标给出了Aug的大小,纵坐标给出了算法运行的时间。表2 真实数据集合统计信息Aug元组数目文件大小(G)500 7677760 2.571000 15354711 5.151500 23033674 7.732000 30714519 10.302500 38388546 12.803000 46073100 15.403500 53758446 18.004000 61431065 20.60论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 13通过在得到的近似核心数据计算上面的4个指标,这4个指标都能够被满足。所选择的近似核心数据的大小在所要求大小范围内,比如当扩增倍数为500时,近似算法选择了6条元组已经能够覆盖7AI中的属性,而近似算法只需覆盖5个属性就可以了。可以根据不同的策略,再选择4条元组,完成核心数据的选择。由于数据集合中包含很多的空值,以及AI属性集合的指定,选出的6条元组都是不完整的,共消耗了86.165秒。图13 NBA合成数据集合上数据规模对运行时间的影响可以发现,近似算法能够高效地选择近似的核心数据集合。虽然给定的AI集合的个数比较小,可以很快地被覆盖,但是由于元组的数目不断增多,因此每次贪心选择需要处理更多的属性和元组,因此时间消耗总体成上升趋势,但是由于当给定AI集合时,近似算法的时间复杂性主要与元组的大小近似成线性关系,因此所消耗的时间的增长近似成线性,说明本文提出的算法具有良好的扩展性。E. 陌生数据集合上的核心数据集合的选择对于一个陌生的数据集合,用户可能无法给出一个较好的核心数据集合的大小,那么选出的近似核心数据可能无法满足上面的4个指标。在这组实验中,通过改变用户要求的核心数据的大小k,观察算法选择的核心数据的大小以及覆盖指定的AI中的属性的个数,以及算法的运行时间。在实验中,表3 3个算法的时间消耗kCMC消耗时间(s)CWSC消耗时间(s)ACS消耗时间(s)1 431.242 1.113 1.0952 432.125 1.109 1.1193 433.485 1.109 1.1234 131.602 1.110 1.1235 87.921 43.930 1.1266 87.826 43.897 1.1247 87.789 43.972 1.1248 87.831 44.892 1.1269 87.961 44.767 1.1254 3个算法选出的核心数据集合覆盖的属性的个数kCMC覆盖个数CWSC覆盖个数ACS覆盖个数1 1 0 42 2 0 63 3 0 64 7 0 65 7 0 66 7 0 67 7 0 68 7 0 69 7 9 65 3个算法选出的核心数据集合的大小kCMC核心数据集合大小CWSC核心数据集合大小ACS核心数据集合大小1 1 0 42 2 0 63 3 0 64 7 0 65 7 0 66 7 0 67 7 0 68 7 0 69 7 9 6指定9个用户感兴趣的属性作为AI,覆盖比例θ设置为1k1变化到9。在原有的NBA数据集合的基础上对每条元组扩增10次,对每个属性值以0.2的概率引入空值,产生的关系含有191970条元组,实验结果见表3,表4和表5。通过表3整体来看,算法CMC所用的时间最长,CWSC所用的时间次之,本文所提出的算ACS14 计算机学报 2017年所用的时间最短。通过表4整体来看,CMC算法在开始的时候没有达到6个属性的覆盖要求,从k超过3时可以达到要求;CWSC只有k9的时候所选出的近似核心数据才能达到覆盖的要求,并且全部覆盖了9个指定的属性;本文提出的算法ACS只有k1时无法达到覆盖要求,此后选出的近似核心数据集合一直可以达到至少覆盖6个属性的要求。通过表5整体来看,CMC所选出的核心数据集合的大小在k不超过3时,能够满足指定的大小,此后选出的近似核心数据集合的大小不变,从超出指定的大小到在指定的大小以内;CWSC除了k9时能够选出满足大小的核心数据集合外,其余情况一直无法选出核心数据集合。下面从算法角度进行分析。CMC算法具有理论上的覆盖指定属性的比例的保证,但是需要估计近似解的总的权值,只有估计到了这个权值,才能达到这个理论上的保证。由于CMC算法采用试探的方法来猜测近似解的总的权值,并尝试在指定的大小内分层地贪心地选择可能的组合。因此,每试探一次新的权值,就会枚举可能情况,虽然采用了分层的方式,过滤掉了很多不可能的情况,但是仍然需要大量的尝试。因此,在k不超过3时,CMC会进行多次尝试新的权值,由于数据本身的特点,核心数据集合大小在3以下时,无法满足覆盖条件,因此即使经历了很多的尝试,CMC仍然无法选择一个满足覆盖要求的核心数据集合,却消耗了大量的时间。当k超过3时,由于CMC认为完整的元组的权值是0,因此可以尽量放到核心数据集合里面,因此选出了7条元组的核心数据集合,能够覆盖7AI中的属性,因此,CMC较快速地选择7条元组后就不再进行选择,但是这样的核心数据集合在k456时是不符合用户指定的大小的。CWSC是一个快速的贪心式的核心数据选择算法,它没有理论上覆盖属性的个数的保证。算法为了快速选择核心数据,要求每条元组都要满足一定比例的覆盖率,即在用户给定的k以内,一定能完成覆盖。因此,由于数据集合中的单条元组对指定属性集合的覆盖比例较低,因此CWSC简单计算后遍终止了,返回了“无法选择”来提示用户,等待用户给出一个合适的k值,因此虽然CMC能在较短的时间内终止并给出提示,但是并没有选出一个近似核心数据集合,并且对于如何设置k值,也没有给出建议。因此,只有用户给出了k9时,CWSC才快速地选择了一个近似核心数据集合,并覆盖率所有的属性。本文提出的算法ACSk1时,无法选择满足覆盖要求的近似核心数据集合,只能尽可能的选择更多的完整元组来覆盖给定的属性,这里选择了4条完整元组来进行覆盖。当k25时,ACS会尽量选择完整的元组来覆盖指定的属性,而每一次尝试都最多选择k条元组,因此选择的核心数据集合的大小会多于用户给定的大小,但是正如定理2给出的,选出的元组不会太多,有一个上界,并且选择的都是完整的元组。因此,可以认为ACS对用户给定的k有一个修正作用,会在用户面对一个陌生的数据集合,无法确定核心数据集合大小时,给出一定的参考,并且会尽量选择完整的元组。同时,如定理2所给出的,ACS在覆盖指定的属性的比例上有理论上的保证,因此除了k1时,ACS都能够高效地选出一个满足理论分析结果的近似核心数据集合。为了进一步比较算法性能上的差异,对这个数据集合的每条元组进行了一定倍数的扩充,表6给出了在不同扩充倍数下的时间消耗,可以看出,正如前面的分析,面对陌生的数据,CMCCWSC的时间消耗增长很快,而本文的算法ACS时间消耗增长不是很快。其中扩充1000倍时,CMCCWSC的时间消耗太久,没有准确测量。表6 3个算法在不同扩充倍数下的时间消耗扩充倍数CMC消耗时间(s)CWSC消耗时间(s)ACS消耗时间(s)10 227.47 57.749 1.593100 26486.90 6622.870 15.9631000 360000+ 360000+ 187.4625相关工作在缩减参与计算的数据量,从而提高计算的效率方面,已经有了很多的研究结果,主要的思想有数据摘要,数据压缩,索引方法和基于样本的近似计算方法。数据摘要[19,20]和数据压缩方法能提供简洁的数据表示方式,但是,如果直接用于计算通常需要额外的计算代价,来获得数据的某些具体的属性值[21]。文献[14]研究了通过索引支持高效率的计算的方法。文献[19]介绍了用于大数据的数据摘要方法。文献[20]提出的方法将属性按照语义进行合并,得到层次的摘要结果。文献[23]提出了在样本论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 15中尽可能地保留原始数据的特点的抽样方法,但是,如果直接应用在不完整数据上,抽取的方法无法保证样本的完整程度。以上方法都没有考虑在不完整数据上进行计算时,如何减少信息缺失给查询结果的完整性带来的误差。选择核心数据来近似回答用户查询的思想来自于文献[12]。文献[13]研究了可以合并的核心数据的选择方法,同时考虑了覆盖性和多样性两个目标。文献[22]研究了来自传感器网络的数据中的支配数据的选择问题。但是,文中的方法去掉了大部分数据之间的差异,只能支持某些种类的查询。本文要选择的核心数据集合要同时优化覆盖性,包含不完整元组的个数,以及结果集合的大小三个目标。之前大部分工作,在完整的数据集合上进行选择,用代价表示不同数据的特点,同类数据虽然特点不一样,仍然可以混用;但是,本文要面对的数据是两类数据,即完整数据和不完整数据。需要通过控制在核心数据中的不完整元组的个数,来尽量减少信息缺失。之前的大部分工作,要么考虑覆盖性和代价,要么考虑覆盖性和结果集合大小,因此,不能直接用来解决本文所研究的问题,比如,加权的集合覆盖问题[24],研究的是在给定覆盖性下的代价优化问题;最大覆盖问题[25]研究的是,在固定结果集合大小时,如何优化覆盖率;而带有预算的最大覆盖问题[26],是在给定代价时,如何优化覆盖率。文献[27]研究了类似于本文的问题,即具有结果大小约束下的加权集合覆盖问题,给出了两个启发式策略,以及优化的方法。但是,它的研究的数据仍是同一类有不同特点(权值) 的数据,而本文研究的是完整的和不完整的两类数据,如果选择较多的不完整数据,那么会造成更多的信息丢失,因此,要尽量避免选择不完整的数据。此外,文献[27]假设总有一条元组能覆盖所有情况;文中的方法需要选择一个合适的迭代步长,来保证得到一个较好的近似比,但是这个步长通常很难选取;而且当待处理的元组带来的增益很分散时,文中给出的启发式算法所需要的迭代轮数是不可控制的。6结论本文研究了海量不完整数据的核心数据选择问题,证明了这个问题是一个NP-完全问题。基于贪心的策略,本文提出了一个具有质量保证的近似核心数据选择算法,并讨论了在不同的应用条件下的改进策略。通过不同数据集合上的实验表明,所提出的近似算法能够高效地选择一个高质量的近似核心数据集合,用来回答查询或者为后续的操作提供支持,所提出的近似算法具有良好的可扩展性。参考文献[1] Saha B, Srivastava D. Data quality: The other face of big data//Proceedings of the2014IEEE30thInternational ConferenceonDataEngineering.Chicago,USA,2014:1294-1297.[2] SwartzN. Gartnerwarnsfirmsof'dirtydata'. InformationManagementJournal,2007,41(3):6-7.[3] EckersonWW. Datawarehousingspecial report: Dataqualityandthebottomline.ApplicationDevelopmentTrends,2002,(5):1-9.[4] DongXL, GabrilovichE, MurphyK, et al. Knowledge-basedtrust:Estimating the trustworthiness of web sources. Proceedings of theVLDBEndowment,2015,8(9):938-949.[5] Li X,DongXL, LyonsK, et al. TruthFindingontheDeepWeb: IstheProblemSolved?. Proceedings of the VLDB Endowment, 2012,6(2):97108.[6] KhalefaME, Mokbel MF, Levandoski JJ. Skylinequeryprocessingforincompletedata//Proceedingsof2008IEEEInternationalConferenceonDataEngineering.Cancún,México,2008:556-565.[7] Miao X, Gao Y, Zheng B, et al. Top-k Dominating Queries onIncomplete Data.IEEE Transactions on Knowledge and DataEngineering,2016,28(1):252266.[8] Razniewski S, Nutt W. Completeness of queries over incompletedatabases.ProceedingsoftheVLDBEndowment,2011,4(11):749760.[9] Deng T, Fan W, Geerts F. On the complexity of packagerecommendationproblems. SIAMJournal onComputing, 2013, 42(5):1940-1986.[10] BasuRoyS, LakshmananLV, LiuR. FromGroupRecommendationsto Group Formation//Proceedings of the 2015 ACMInternationalConference on Management of Data. Melbourne, Australia.2015:16031616.[11] Lappas T, Liu K, Terzi E. Finding a Teamof Experts in SocialNeworks//Proceedings of the 15thACMInternational Conference onKnowledgeDiscoveryandDataMining.Paris,France,2009:467476.[12] Agarwal PK, Har-PeledS, VaradarajanKR. ApproximatingExtentMeasuresofPoints.JournaloftheACM,2004,51(4):606635.[13] IndykP, Mahabadi S, MahdianM, et al. ComposableCore-sets forDiversityandCoverageMaximization//Proceedings of the33rdACM16 计算机学报 2017SIGMOD-SIGACT-SIGART Symposiumon Principles of DatabaseSystems. Utah,USA,2014:100108.[14] PirkH,ManegoldS,KerstenM.Wastenot...Efficientco-processingofrelational data//Proceedings of the 2014 IEEE 30th InternationalConferenceonDataEngineering. Chicago,USA,2014:508519.[15] Potti N, Patel J M. DAQ: a newparadigmfor approximate queryprocessing.ProceedingsoftheVLDBEndowment,2015,8(9):898909.[16] Agarwal S, Mozafari B, Panda A, et al. BlinkDB: queries withbounded errors and bounded response times on very largedata//Proceedings of the8thACMEuropeanConferenceonComputerSystems. Prague,CzechRepublic2013:2942.[17] WangX, DongXL, MeliouA. DataX-Ray: ADiagnosticTool forDataErrors//Proceedingsofthe2015ACMInternational ConferenceonManagementofData.Melbourne,Australia,2015:12311245.[18] Agarwal S, MilnerH, KleinerA, et al. Knowingwhenyourewrong:building fast and reliable approximate query processingsystems//Proceedings of the 2014ACMinternational conference onManagementofdata.Utah,USA,2014:481492.[19] CormodeG,GarofalakisM,HaasPJ,etal.Synopsesformassivedata:Samples, histograms, wavelets, sketches. Foundations andTrends inDatabases,2012,4(13):1294.[20] SelçukCandanK, CaoH, Qi Y, et al. AlphaSum: Size-constrainedTable Summarization Using Value Lattices//Proceedings of the 12thInternational ConferenceonExtendingDatabaseTechnology:AdvancesinDatabaseTechnology. Saint-Petersburg,Russia,2009:96107.[21] GranadosA, KoroutchevK, deBorjaRodriguezF. DiscoveringDataSet Nature through Algorithmic Clustering Based on StringCompression. IEEETransactionsonKnowledgeandDataEngineering,2015,27(3):699711.[22] ChengS,CaiZ,LiJ, etal.Drawingdominantdatasetfrombigsensorydata in wireless sensor networks//Proceedings of the 2015 IEEEConferenceonComputer Communications. HongKong, China, 2015:531-539.[23] Acharya S, Gibbons PB, Poosala V. Congressional samples forapproximate answeringof group-byqueries. ACMSIGMODRecord,2000,29(2):487-498.[24] Chvatal V. A greedy heuristic for the set-covering problem.Mathematicsofoperationsresearch,1979,4(3):233235.[25] HochbaumDS, Pathria A. Analysis of the greedy approach inproblems of maximumk-coverage. Naval Research Logistics, 1998,45(6):615-627.[26] Khuller S, Moss A, Naor J S. The budgeted maximumcoverageproblem.InformationProcessingLetters,1999,70(1):39-45.[27] Golab L, Korn F, Li F, et al. Size-constrained weighted setcover//Proceedingsof the2015IEEEInternational ConferenceonDataEngineering.Seoul,SouthKorea,2015:879-890.论文在线出版号No.54 刘永楠等:海量不完整数据的核心数据选择问题的研究 17LIUYong-Nan, born in 1986, Ph. D.candidate. His researchinterests includedataqualityanddatacompleteness.LIJian-Zhong,bornin1950,professor,Ph.D.supervisor.Hisresearch interests include databases and wireless sensornetworks.GAOHong, bornin1966, professor, Ph. D. supervisor. Herresearch interests include databases and wireless sensornetworks.BackgroundDataqualityisaheatedresearchdirectioninthebigdataera, which has been investigated extensively in differentperspectives. Incomplete data is a ubiquitous issue in dataquality, whichbrings challenges toalgorithms for querying,mining and analyzing. Incomplete data seriously reduceusabilityofdatainrealapplications.Selecting a subset of a users interest fromentireincompletedataset isaneffectiveandefficient mechanismtoimprove usability of incomplete data. Most prior work onselecting core-sets focuses on sampling numeric values forapproximate aggregation queries, obtaining synopses orconstructing histograms, which cannot handle categoricalvalues and may lose many features of entire data. Usingtraditional methodsbasedonset cover, tuplescoveringsomeattributesofausersinterest areselected, but theremaybetoomanytuples for auser for further considerationor follow-upoperations. In this paper, we investigate the problemofselectingcore-setswithsizeconstrainedfromincompletedatagivenattributesofausersinterest. SuchproblemisprovedtobeNP-Complete.Therefore,wedesignanapproximatecore-setselection algorithmbased on greedy, calledACS, which isproposedinthis paper. TheproposedalgorithmACSselectstuplescontainingcompletevaluesasmanyaspossibletoobtainan approximate core-set, and the number of selections islimitedtoobtainasubset of tupleswithsizelimited, andtheratioofattributesofinterest coveredisguaranteedaswell. Bytheoretical analysis, withinnearlylinear time, ACScanselectanapproximatecore-set of sizewithinthelogarithmfactor totheoptimalsize,wheretheratioofattributesofinterestcoveredisat least (1-1/e),withincompletetuplesofatmost thesizeofthe required core-set, where e is the base of the naturallogarithm. Experimental results conductedontworeal-worlddatasets of DBLPandNBAplayers showeffectiveness andefficiencyof theproposedalgorithmACS, andexperimentalresultsonsyntheticdatasetswithlarger scaleshowscalabilityofACS.To obtain an approximate core-set with highcompleteness, the algorithm mainly selects tuples fromcomplete tuples as many as possible tocover attributes ofinterest.Buttheremaystillbeattributesofinterestnotcovered.Thenthe algorithmhas toselect incomplete tuples, but thenumber is strictly limited. Since the coverage can beguaranteed theoretically, the algorithmcan return a goodapproximatecore-setforfurtheruse.Thisworkissupportedinpart bytheKeyResearchandDevelopment Plan of National Ministry of Science andTechnologyunder grant No. 2016YFB1000703, andtheKeyProgramoftheNational Natural ScienceFoundationofChinaunderGrantNo.61632010,61502116,61370217,U1509216.

[返回]
上一篇:基于CART 与SLOPEONE 的服务质量预测算法
下一篇:多层自适应模块化神经网络结构设计