软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2019年第03期杂志 文档列表

软件学报杂志智能数据管理与分析技术专刊

智能数据管理与分析技术专刊前言495-497

摘要：数据管理与智能计算的深度融合已经成为大数据时代顺利前行的迫切需求.智能数据管理旨在“为数据增添智能”,是数据科学与技术的重要基石,更是大数据产业蓬勃发展的关键支撑.一方面,将新一代人工智能方法应用于先进数据管理技术,尝试探索和突破智能数据管理与分析的理论体系、技术方法及系统平台,已经成为数据管理领域的新兴研究方向;另一方面,研发面向人工智能的数据库基础软件。

大规模RDF图数据上高效率分布式查询处理498-514

摘要：知识图谱是智能数据的主要表现形式,随着知识图谱领域的不断发展,大量的智能图数据以资源描述框架(resource description framework,简称RDF)形式出来.RDF 图上的SPARQL 查询语义对应于图同态,是一个NP-完全问题.因此,如何使用分布式方法在大规模RDF 图上有效回答SPARQL 查询是一个富有挑战性的问题.目前已有研究使用MapReduce 计算模型处理大规模RDF 数据,但其将SPARQL 查询拆分成单个的查询子句,没有考虑RDF 数据的丰富语义和自身的图特性,导致MapReduce 迭代次数过多.首先,利用RDF 数据内嵌的语义和结构信息作为启发式信息,将查询图分解为星形的集合,可以在更少次迭代内得到查询结果.同时,分解算法给出中间结果较少的星形匹配顺序,基于此顺序,每轮MapReduce 操作通过连接操作匹配一个新的星形,直至产生最终的答案.最后,在标准合成数据集WatDiv 和真实数据集DBpedia 上进行大量的实验评估.实验结果表明:所提基于星形分解的分布式SPARQL BGP 匹配算法能够高效回答查询,查询时间比SHARD和S2X算法的查询时间平均提高一个数量级,且优化算法的查询时间与基本算法相比缩短了49.63%~78.71%.

基于规则的最短路径查询算法515-536

摘要：最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard 问题.目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.

基于角色发现的动态信息网络结构演化分析537-551

摘要：动态信息网络是当前复杂网络领域中极具挑战的新问题之一,对其动态的演化过程进行研究,有助于分析网络结构、理解网络特性、发现网络中潜在的信息及演化规律,具有重要的理论意义与应用价值.基于网络结构本身量化表示的复杂性以及网络演化时序、复杂、多变的挑战,使用角色来量化动态网络的结构,并对模型进行分析,给出了两种角色解释的方法;在角色发现的基础上,将动态网络结构预测问题转换为可以表示结构特征的角色预测问题,通过向量自回归的方法,以历史网络角色分布矩阵作为训练数据构建模型,预测未来时刻网络可能的角色分布情况,提出了基于潜在角色的动态网络结构预测方法LR-DNSP(latent role based dynamic network structureprediction).该方法克服了已有基于转移矩阵方法忽略历史信息的不足,并且考虑了多个预测目标之间可能存在的相互关系.实验结果表明,提出的LR-DNSP 方法具有更准确的预测效果.

复杂条件下的社区搜索方法552-572

摘要：社区搜索旨在寻找包含给定节点集的社区,能够快速获取个性化的社区信息.针对现有社区搜索算法难以满足复杂搜索条件的现状,提出条件社区搜索这一新问题.解决该问题有助于对社交网络进行智能分析,在复杂搜索条件下为用户提供更好的社区结果.首先,基于布尔表达式,给出条件社区搜索问题的形式化定义,可有效表达给定节点不能出现在社区内以及给定节点中至少有一个出现在社区内的要求.接着,提出解决条件社区搜索问题的通用框架,包括对搜索条件进行简化、根据简化后的搜索条件进行多次单项条件社区搜索、合并各单项条件社区搜索的结果等主要步骤.同时,提出“社区搜索+过滤”的方法和给点加权的方法来进行单项条件社区搜索.最后,真实数据集上的大量实验结果表明所提方法的正确性和有效性.

基于事件的社交网络上的双边偏好稳态规划573-588

摘要：在基于事件的社交网络中,一个经典的问题是为用户规划其感兴趣的事件.现有的工作仅仅考虑用户的喜好,仅从用户的角度出发,为其安排尽可能感兴趣的事件来参加.然而,从事件主办者的角度出发,他们亦希望为事件安排的用户尽可能有更大的影响力,用户的可靠性尽可能高,以保障事件能够顺利开展,并取得预期的效果.本质上来说,基于事件的社交网络上的规划问题是一个双向选择的问题,而现有的所有工作均未从用户和事件的双边偏好考虑问题.因此,提出一种双边偏好稳态规划问题来解决这种双向选择问题.该问题首次提出,因此现有工作中未有相关算法可供解决该问题.对比之前只考虑用户偏好的规划,在考虑用户和事件双边偏好时,面临着问题更复杂、约束条件更多的困难.因此,提出两种基础算法和一种改进算法来高效、高质量地解决这个问题,并用大量的实验验证所提出算法的高效性和有效性.

基于时效规则的数据修复方法589-603

摘要：数据时效性是影响数据质量的重要因素,可靠的数据时效性对数据检索的精确度、数据分析结论的可信性起到关键作用.数据时效不精确、数据过时等现象给大数据应用带来诸多问题,很大程度上影响着数据价值的发挥.对于缺失了时间戳或者时间不准确的数据,精确恢复其时间戳是困难的,但可以依据一定的规则对其时间先后顺序进行还原恢复,满足数据清洗及各类应用需求.在数据时效性应用需求分析的基础上,首先明确了属性的时效规则相关概念,对属性的时效规则等进行了形式化定义;然后提出了基于图模型的时效规则发现以及数据时序修复算法;随后,对相关算法进行了实现,并在真实数据集上对算法运行效率、修复正确率等进行了测试,分析了影响算法修复数据正确率的一些影响因素,对算法进行了较为全面的分析评价.实验结果表明,算法具有较高的执行效率和较好的时效修复效果.

劣质数据上代价敏感决策树的建立604-619

摘要：代价敏感决策树是以最小化误分类代价和测试代价为目标的一种决策树.目前,随着数据量急剧增长,劣质数据的出现也愈发频繁.在建立代价敏感决策树时,训练数据集中的劣质数据会对分裂属性的选择和决策树结点的划分造成一定的影响.因此在进行分类任务前,需要提前对数据进行劣质数据清洗.然而在实际应用中,由于数据清洗工作所需要的时间和金钱代价往往很高,许多用户给出了自己可接受的数据清洗代价最大值,并要求将数据清洗的代价控制在这一阈值内.因此除了误分类代价和测试代价以外,劣质数据的清洗代价也是代价敏感决策树建立过程中的一个重要因素.然而,现有代价敏感决策树建立的相关研究没有考虑数据质量问题.为了弥补这一空缺,着眼于研究劣质数据上代价敏感决策树的建立问题.针对该问题,提出了3种融合数据清洗算法的代价敏感决策树建立方法,并通过实验证明了所提出方法的有效性.

两两比较模型的Why-not问题解释及排序620-647

摘要：由于数据缺失,数据库用户通常无法获得查询结果中的预期答案.它被称为“Why-not问题”,即“为什么预期的元组不会出现在结果中”.现有的方法通过列举可能的元组值来解释Why-not问题.枚举所给出解释的数量往往太大,无法由用户探索.完整性约束,如函数依赖,被用来排除不合格的解释.然而,许多属性在简化后解释中仅仅表示为变量,用户可能仍然无法理解.由于数据稀疏性,许多不合理的解释也会被推荐给用户.提出通过研究元组间两两比较关系,从而对Why-not问题的解释进行排序的方法.首先,重新定义为什么Why-not问题解释的形式没有变量,以便于用户理解;其次,对元组中的相等/不相等关系进行表示,提出在{0,1}表示的元组对的基础上学习统计模型,从而解决直接在原始数据上学习所带来的稀疏性问题,许多模型可以被用来推断概率,包括统计分布、分类和回归;最后,根据推断的概率对解释进行评价和排序.实验结果证明:利用统计、分类和回归方法计算两两关系概率分布的方法,可以为用户寻找Why-not问题的解释并返回较为高质量的解释.

差分隐私的数据流关键模式挖掘方法648-666

摘要：频繁模式挖掘是数据挖掘的重要任务之一,在数据流上挖掘简洁的关键模式比频繁模式更有优势,因为关键模式既可以避免频繁模式里包含的冗余信息以减少内存存储空间,又可以高效无损地提取频繁模式.但是由于相邻时间戳的统计信息可以作为背景知识增强攻击者的推理能力,所以从包含个人信息的数据流中挖掘关键模式比静态场景下更容易泄露隐私.分析指出了数据流关键模式挖掘的隐私泄露问题及原理,并提出了一种满足差分隐私的数据流关键模式挖掘算法DP-CPM,该算法在每个时间戳设计一种两阶段机制:差异计算阶段和噪音挖掘阶段.该机制既考虑了隐私和数据效用之间的权衡,又考虑了挖掘时间和维护开销之间的权衡.为了提高数据流中连续时的数据效用性,在第1 阶段通过计算差异来决定当前时间戳是返回低噪音统计值还是精确的近似统计值.如果是返回低噪音统计值,算法进入噪音挖掘阶段.在噪音挖掘阶段,首先通过判断查询集筛选出关键模式候选集,然后通过给筛选出的候选集里的模式支持度加入服从拉普拉斯分布的随机噪音,得到最终的噪音支持度.最后,给出了严格的理论分析和大量的实验,表明DP-CPM 算法的有效性和执行效率.

基于网格耦合的数据流聚类667-683

摘要：随着越来越多的应用程序产生数据流,数据流聚类分析的研究受到了广泛关注.基于网格的聚类通过将数据流映射到网格结构中形成数据概要,进而对概要进行聚类.这种方法通常具有较高的效率,但是每个网格独立处理,没有考虑网格之间的相互影响,因此聚类质量有待提高.在聚类过程中不再独立处理网格,而是考虑了网格之间的耦合关系,提出了一种基于网格耦合的数据流聚类算法.网格的耦合更加准确地表达了数据之间的相关性,从而提高了聚类的质量.在合成和真实数据流上的实验结果表明,所提算法具有较高的聚类质量和效率.

分布式异构数据库数据同步工具684-699

摘要：一般而言,读写分离技术可以解决当前大数据环境下的读写速度失配的部分问题,但是现有的读写分离技术主要是针对同构数据库的解决方案.由于存储结构的不一致,由行式存储数据库和列式存储数据库构成的异构分布式数据库系统相较于同构分布式数据库系统在数据同步的过程中就会面临格式转换、同步速度不匹配等诸多难题.提出了基于MySQL 二进制日志(Binlog)进行SQL 还原的方法TD-Reduction,设计并实现了Binlog 解析器BinParser 和Binlog 还原器BinReducer,它们可以基于Mixed 格式的Binlog,针对不同的事件(event)进行日志的解析,并依据相应的规则进行还原,生成可执行的SQL 语句.综合以上技术,实现了一款分布式数据库数据同步工具Cynomys.在实验环境中,Cynomys 表现出较好的性能.该方法适用于所有具有类似Binlog 机制的其他异构数据库之间进行数据同步.

面向通用模型的高可用性步态周期分析方法700-717

摘要：步态数据分析是模式识别、数据挖掘与智能数据分析领域中的一个重要研究方向.对步态数据进行分析并求解步态周期段,是该领域的一个核心课题,其中,以波峰波谷识别、步态模板匹配、利用信号处理基本方法为主.这些方法尽管已取得了一定条件下的应用,但大多需要预知步态数目、步态模板数据等基本信息,其可用性受限.针对这一问题,提出一种结合了波峰波谷检测与阈值空间的高可用性步态周期分析方法,通过自动求解预估值并构建自适应区间,根据通用步态模型对缺乏上述信息的未知步态数据进行切分与分析,能够更便利准确地求解步态周期数据.同时也提出了一种过滤不相关数据的方法,用于过滤测试数据头尾的部分不相关数据.该方法与朴素快速傅里叶方法和本领域3类最新典型方法进行了对比,实验结果显示:在所有样本中,该方法的步态周期段求解准确度最高,使步态数据的分析与处理更贴合实际情况.

CNN多位置穿戴式传感器人体活动识别718-737

摘要：随着人工智能的发展和可穿戴传感器设备的普及,基于传感器数据的人体活动识别(human activityrecognition,简称HAR)得到了广泛关注,且具有巨大的应用价值.抽取良好判别力的特征,是提高HAR 准确率的关键因素.利用卷积神经网络(convolutional neural networks,简称CNN)无需领域知识抽取原始数据良好特征的特点,针对现有基于传感器的HAR 忽略三轴向传感器单一轴向多位置数据空间依赖性的不足,提出了两种动作图片构建方法T-2D 和M-2D,构建多位置单轴传感器动作图片和非三轴传感器动作图片;进而提出了卷积网络模型T-2DCNN 和M-2DCNN,抽取三组单一轴向动作图片的时空依赖性和非三轴传感器的时间依赖性,并将卷积得到的特征拼接为高层次特征用于分类;为了优化网络结构,减少卷积层训练参数数量,进一步提出了基于参数共享的卷积网络模型.在公开数据集上与现有的工作进行对比实验,默认参数情况下,该方法在公开数据集OPPORTUNITY 和SKODA 中F1 最大提升值分别为6.68%和1.09%;从传感器数量变化和单类识别准确性角度验证了模型的有效性;且基于共享参数模型,在保持识别效果的同时减少了训练参数.

改进的SSD航拍目标检测方法738-758

摘要：近年来,无人机技术的快速发展使得无人机地面目标检测技术成为计算机视觉领域的重要研究方向,无人机在军事侦察、交通管制等场景中具有普遍的应用价值.针对无人机场景下目标分辨率低、尺度变化大、相机快速运动、目标遮挡和光照变化等问题,提出一种基于残差网络的航拍目标检测算法.在SSD(single shot multiboxdetector)目标检测算法的基础上,用表征能力更强的残差网络进行基准网络的替换,用残差学习降低网络训练难度,提高目标检测精度;引入跳跃连接机制降低提取特征的冗余度,解决层数增加出现的性能退化问题.同时,针对SSD目标检测算法存在的目标重复检测和小样本漏检问题,提出一种基于特征融合的航拍目标检测算法.算法引入不同分类层的特征融合机制,把网络结构中低层视觉特征与高层语义特征有机地结合在一起.实验结果表明,算法在检测准确性和实时性方面均具有较好的表现.

面向交通流量预测的多组件时空图卷积网络759-769

摘要：流量预测一直是交通领域研究者和实践者关注的热点问题.流量数据具有高度的非线性和复杂性,对其进行精准预测具有很大的挑战,现有的预测方法大多不能很好地捕获数据的时空相关性.提出一种新颖的基于深度学习的多组件时空图卷积网络(MCSTGCN),以解决交通流量预测问题.MCSTGCN 通过3 个组件分别建模流量数据的近期、日周期、周周期特性,每个组件同时利用空间维图卷积和时间维卷积有效捕获交通数据的时空相关性.在美国加利福尼亚州高速公路流量公开数据集上进行了实验,结果表明,MCSTGCN 模型的预测效果优于现有的预测方法.

时空依赖的城市道路旅行时间预测770-783

摘要：城市道路的旅行时间预测,对于路径规划以及交通管理至关重要.尽管旅行时间预测会受路段依赖、时空相关性以及其他因素的影响,但现有的方法并未考虑如何结合外部因素进行建模,因而可能会有引入错误信息、路段建模时忽略上下游路段间的依赖关系等问题,导致预测精度较差.鉴于此,提出了两阶段的旅行时间预测框架:首先,使用Skip-Gram模型对轨迹数据地图匹配后的路段序列进行编码,将其映射为低维向量,通过该编码方式避免引入错误信息的同时保留了路段间的上下游依赖信息.随后,基于路段编码模式整合天气、日期等外部因素,设计了基于深度神经网络的城市道路旅行时间预测模型.基于真实出租车轨迹数据集的对比实验结果表明,所提方法比对比算法具有更高的预测精度.

面向高维特征和多分类的分布式梯度提升树784-798

摘要：梯度提升树算法由于其高准确率和可解释性,被广泛地应用于分类、回归、排序等各类问题.随着数据规模的爆炸式增长,分布式梯度提升树算法成为研究热点.虽然目前已有一系列分布式梯度提升树算法的实现,但是它们在高维特征和多分类任务上性能较差,原因是它们采用的数据并行策略需要传输梯度直方图,而高维特征和多分类情况下梯度直方图的传输成为性能瓶颈.针对这个问题,研究更加适合高维特征和多分类的梯度提升树的并行策略,具有重要的意义和价值.首先比较了数据并行与特征并行策略,从理论上证明特征并行更加适合高维和多分类场景.根据理论分析的结果,提出了一种特征并行的分布式梯度提升树算法FP-GBDT.FP-GBDT 设计了一种高效的分布式数据集转置算法,将原本按行切分的数据集转换为按列切分的数据表征;在建立梯度直方图时,FP-GBDT 使用一种稀疏感知的方法来加快梯度直方图的建立;在分裂树节点时,FP-GBDT设计了一种比特图压缩的方法来传输数据样本的位置信息,从而减少通信开销.通过详尽的实验,对比了不同并行策略下分布式梯度提升树算法的性能,首先验证了FP-GBDT 提出的多种优化方法的有效性;然后比较了FP-GBDT 与XGBoost 的性能,在多个数据集上验证了FP-GBDT 在高维特征和多分类场景下的有效性,取得了最高6 倍的性能提升.