1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
    大数据与数据科学 栏目所有文章列表
    (按年度、期号倒序)
        一年内发表的文章 |  两年内 |  三年内 |  全部
    Please wait a minute...
    1. 基于ISE算法的分布式ETL任务调度策略研究
    王卓昊, 杨冬菊, 徐晨阳
    计算机科学    2019, 46 (12): 1-7.   https://doi.org/10.11896/jsjkx.190100023
    摘要 (447)   PDF (1988KB) (862)  
    随着数据仓库的规模不断扩大,数据集成下的ETL(Extraction-Transformation-Loading)任务也随之增多,单机调度显然已经不能满足当下繁多复杂的ETL任务调度。针对ETL任务调度如何提高效率、缩短关键任务等待时间、提升资源利用率等问题,构建了一套分布式ETL任务调度框架,该框架由调度器和若干执行器组成,通过任务预处理、任务调度分配、任务执行3个阶段来完成ETL任务调度。在任务预处理阶段,对ETL任务建立权重模型,并根据权重确定调度优先级。在任务调度分配阶段,调度器根据各个执行器节点的性能及负载情况来约束执行器节点的选择,并设计贪心平衡(Greedy Balance,GB)算法来进行ETL任务执行请求的分发,使执行器节点的负载相对均衡。在任务执行阶段,通过高响应比优先(Highest Response Ratio Next,HRRN)算法确定执行器节点队列下任务的执行优先级。实验结果表明,分布式ETL任务调度框架及相应的一体化调度执行( Integrated Scheduling Execution,ISE)算法能够有效提高集群资源的利用率,缩短任务调度的执行时间。
    参考文献 | 相关文章 | 多维度评价
    2. AdaBoostRS:高维不平衡数据学习的集成整合
    杨平安, 林亚平, 祝团飞
    计算机科学    2019, 46 (12): 8-12.   https://doi.org/10.11896/jsjkx.180901813
    摘要 (310)   PDF (1341KB) (655)  
    机器学习中类不平衡分布问题包含了不同类之间数据样本的偏差分布,导致学习过程更偏向于多数类。而高维数据的稀疏性使得分类的偏差更加明显,因此对于高维不平衡数据,维度灾难与类不平衡分布这两个挑战性问题相互叠加在一起,使得解决高维不平衡问题变得更为困难。针对这一问题,文中提出结合随机子空间和SMOTE过采样技术的AdaBoost集成方法(AdaBoost ensemble of Random subspace and SMOTE,AdaBoostRS)来处理高维不平衡数据的分类。具体地,AdaBoostRS通过随机子空间选取部分特征来训练每个分类器,以增加分类样本的多样性和降低高维数据的维度,然后通过SMOTE方法对降维数据的少数类进行线性插值,以解决类不平衡问题。基于8个高维不平衡的标准时间序列数据集进行实验,结果表明,以F-measure、G-mean与AUC 3个性能指标来进行评判,AdaBoostRS优于传统的集成学习方法。
    参考文献 | 相关文章 | 多维度评价
    3. 基于列存储的大数据采样查询处理
    齐文, 鲍玉斌, 宋杰
    计算机科学    2019, 46 (12): 13-19.   https://doi.org/10.11896/jsjkx.190500155
    摘要 (281)   PDF (2881KB) (602)  
    大数据时代的到来给传统的数据查询带来了性能挑战,即使查询算法有着O(n)的线性复杂度,但当n极大时其时间开销也难以满足用户需求。在很多实际应用中,人们并不需要精确的查询结果,但要求在给定时间内完成查询,因此可适当牺牲查询精度以满足性能约束。采样查询通过约简查询范围来提高查询性能,现有的采样方法多针对特定的算法和特定的应用场景,缺乏大数据环境下一般性的采样查询方法以及保证性能和精度的研究。文中研究大数据环境下列存储的采样查询处理,从数据划分和数据采样两方面改进大数据的查询效率。提出了基于加速比和势分布的采样方法,其支持各类采样算法,实现了分布式环境下采样查询的随机性保证、性能保证和近似性评价,并兼容了精确查询。该方法可以快速应用到已有大量数据的列存储中,具备良好的扩展性和可维护性。以Top-K为查询用例的实验结果证明,在不同数据量、不同数据分布和不同采样算法下,实际采样率与给定采样率的误差低于2%,查询准确度 (Accuracy) 稳定,方差在0.10和0.12之间,因此提出的基于段势的数据划分的采样效率高于平均划分和线性划分。
    参考文献 | 相关文章 | 多维度评价
    4. 基于节点连接模式相关性的链接预测方法
    单娜, 李龙杰, 刘昱阳, 陈晓云
    计算机科学    2019, 46 (12): 20-25.   https://doi.org/10.11896/jsjkx.190700057
    摘要 (274)   PDF (3147KB) (520)  
    作为复杂网络分析中的一个研究热点,链接预测在许多领域中都有重要的应用价值,得到了广泛的关注。使用网络中的已知结构信息来计算未连接的节点对之间的相似性,进而评估其存在链接的可能性是目前最常用的方法。不同网络具有不同的结构特征,节点之间的特征对链接的形成具有重要影响。为了提高链接预测的性能,文中定义了节点的连接模式,并基于节点连接模式的相关性(Correlation of Nodes’ Connecting Patterns,CNCP)设计了一个新的链接预测模型。该模型将CNCP与基本相似性指标相结合,通过综合节点的相似性与节点连接模式的相关性进行链接预测。文中将CNCP与CN(Common Neighbors),RA(Resource Allocation),AA(Adamic-Adar)及PA(Preferential Attachment)4个相似性指标相结合,提出了CNCP-CN,CNCP-RA,CNCP-AA和CNCP-PA 4个新的链接预测指标。在6个真实数据集上的实验结果表明,所提方法在AUC和Precision 2个评价标准上的性能优于对比方法。
    参考文献 | 相关文章 | 多维度评价
    5. 基于密度约束的对比模式挖掘
    柴欣, 高一寒, 武优西, 刘靖宇
    计算机科学    2019, 46 (12): 26-30.   https://doi.org/10.11896/jsjkx.181202289
    摘要 (228)   PDF (1925KB) (330)  
    序列模式挖掘是从序列数据中发现用户感兴趣的模式。对比模式挖掘是其中的一类挖掘方法,其特点是在两类或多类别的序列库中找到特征信息,在实际的生活和生产中应用十分广泛。随着数据规模的不断增加,算法的挖掘效率显得尤为重要,但是当前对比模式挖掘仍存在挖掘速度太慢的问题。为了快速挖掘满足密度约束和间隙约束的对比模式,文中提出了一种近似求解算法ADMD(Approximately Distinguishing Patterns Mining Based on Density Constraint),该算法在模式的挖掘过程中允许存在小部分的模式丢失,从而换取挖掘速度的大幅提升。该算法采用网树的特殊结构来计算模式的支持数;采用模式拼接的方式来生成候选模式;采用预判式剪枝策略对模式进行剪枝,以避免大量冗余模式的生成。但由于在剪枝过程中可能会剪掉一部分非冗余模式,造成挖掘结果并非完备,因此该算法是一种近似求解算法。在ADMD算法的基础上,通过在剪枝策略中设定参数k的方式来得到ADMD-k算法,该算法可以通过设定k的取值来调整剪枝程度,从而在挖掘效率和准确率方面取得平衡。最后在真实的蛋白质数据集上将所提算法与其他算法从挖掘的对比模式数量和挖掘速度方面进行对比实验。实验结果表明,在k=1.5的情况下,所提算法仅用不到原来13%的时间,就可以挖掘到99%以上的模式,具有近似度高、速度快的特点。
    参考文献 | 相关文章 | 多维度评价
    6. HMRF半监督近似核k-means算法
    贾洪杰, 王良君, 宋和平
    计算机科学    2019, 46 (12): 31-37.   https://doi.org/10.11896/jsjkx.190600159
    摘要 (235)   PDF (1258KB) (327)  
    信息技术的发展催生了海量数据。聚类有助于发现数据的内在联系,从中挖掘有价值的信息。在对数据进行分析时,容易获得一些关于数据的背景知识,使用这些有限的先验信息指导聚类,可以显著改善聚类的结果。基于隐马尔可夫随机场(Hidden Markov Random Fields,HMRF)的半监督聚类使用成对约束作为监督信息,虽然在很多应用场景中有较好的聚类效果,但是其时间和空间复杂度很高,无法满足大规模数据处理的需要。针对该问题,文中首先分析了HMRF半监督聚类与核k-means的数学联系,使用矩阵的迹将两者的目标函数统一起来;然后,为了降低HMRF半监督聚类的复杂度,提出HMRF半监督近似核k-means算法(HMRF semi-supervised Approximate Kernel K-Means,HMRF-AKKM),通过采样构造近似核矩阵,使用近似核k-means优化聚类的目标函数;最后,在基准数据集上将HMRF-AKKM算法与相关的聚类算法进行对比,分析不同算法在实验中的聚类表现。实验结果表明,在相同的聚类任务上,HMRF-AKKM算法与原始的HMRF半监督聚类具有类似的聚类质量,但是HMRF-AKKM算法的聚类时间更短,说明HMRF-AKKM算法继承了HMRF半监督聚类与近似核k-means的优点。该算法一方面可以充分利用成对约束信息改善聚类质量,另一方面通过采样和矩阵近似提高了聚类效率,而且聚类质量和聚类效率可以通过调节采样比例和成对约束数量来平衡。因此,所提出的HMRF-AKKM算法具有良好的可扩展性,适合处理大规模非线性数据的聚类问题。
    参考文献 | 相关文章 | 多维度评价
    7. 一种基于Q-sample的局部相似连接并行算法
    王晓霞, 孙德才
    计算机科学    2019, 46 (12): 38-44.   https://doi.org/10.11896/jsjkx.190100240
    摘要 (158)   PDF (1890KB) (359)  
    局部相似连接能快速找出数据集间的局部相似记录对,是基因序列比对、剽窃检测和数据清洗等研究领域的基本操作。文中主要研究基于MapReduce框架的并行相似连接技术,提出了一种基于Q-sample的局部相似连接算法,解决了局部相似连接的定位问题。该算法采用了过滤验证二阶段模式:在过滤阶段,所提算法使用Q-sample分割方案拆分字符串集,在不丢失任何匹配的基础上生成了高质量的子串,抛弃了大量的无关字符串对;在验证阶段,所提算法优化了LS-Join算法的双向扩展验证方法,通过去除冗余匹配、合并连续匹配和合并非连续匹配等技术提高了算法的验证效率。通过实验对比了不同数据集和编辑距离参数下算法的性能表现,结果显示所提算法在大数据集上的局部相似连接速度快于当前的优秀算法LS-Join。理论分析和实验结果证明,所提算法的相关技术提高了局部相似的连接性能。
    参考文献 | 相关文章 | 多维度评价
    8. 带偏置的信号传播的随机游走的社团检测算法
    尹欣红, 赵世燕, 陈晓云
    计算机科学    2019, 46 (12): 45-55.   https://doi.org/10.11896/jsjkx.190700051
    摘要 (168)   PDF (4377KB) (397)  
    复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的功能模块有助于深层探究复杂网络的内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,很多研究者对社团检测进行了研究,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,通过模拟随机游走的过程,结合信号传播过程中随着传播距离的增大,信号量会缓慢衰减的思想,提出了一种带偏置的信号传播机制的随机游走的社团检测算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑到信号的衰减,为每条边设置偏置,对信号传播过程进行限定。通过模拟信号的传播,将网络的每个顶点作为信号源来重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证该方法的性能,在10个实际网络数据集以及不同规模的人工合成网络上进行实验。实验结果充分证明,所提算法能够从网络中提取出高质量的社团结构,从而有效地为社团检测领域提供依据。
    参考文献 | 相关文章 | 多维度评价
    9. 基于多关系社交网络的协同过滤推荐算法
    宾晟, 孙更新
    计算机科学    2019, 46 (12): 56-62.   https://doi.org/10.11896/jsjkx.181102189
    摘要 (199)   PDF (1743KB) (1074)  
    推荐系统是大数据中最常见的应用之一,传统的协同过滤推荐算法直接基于用户-项目评分矩阵,对于海量的用户和商品数据,算法的执行效率将会显著降低。针对这一问题,提出了一种基于多关系社交网络的协同过滤推荐算法。该算法利用信息传播方法对基于多子网复合复杂网络模型构建的多关系社交网络进行社团结构划分,从而将相似度接近的用户划分到一个社团中,进而在社团内部选择用户的k-近邻集合来构建用户-项目评分矩阵,然后利用协同过滤算法进行推荐,从而实现了在不降低推荐准确率的前提下提升推荐算法的执行效率。在真实数据集Epi-nions上,将所提算法与传统的协同过滤推荐算法进行对比。实验结果表明,所提算法具有较高的推荐效率和准确率,特别是对于海量数据,推荐算法的执行时间缩短到原有的1/10。
    参考文献 | 相关文章 | 多维度评价
    10. 基于社区发现的兴趣点推荐
    龚卫华, 沈松
    计算机科学    2019, 46 (12): 63-68.   https://doi.org/10.11896/jsjkx.190400440
    摘要 (224)   PDF (2002KB) (511)  
    近年来,LBSN(Location-based Social Networks)作为一种典型的异质信息网络越来越受到大众的关注。针对LBSN中用户签到信息十分稀疏的情况,文中提出了一种基于社区发现的兴趣点推荐算法CBR(Community-Based Recommendation)。该算法首先在社交媒体层上计算目标用户与聚类后的兴趣主题簇的相似度;其次通过兴趣主题簇与地理位置簇之间的关联矩阵R计算用户在地理位置簇上的隶属度;然后进一步融合用户的社交关系,从而得到用户对各个兴趣点的偏好分数;最后按照兴趣点的分数进行排序,以实现Top-k推荐。实验结果表明,该算法可以明显提高兴趣点的推荐质量。
    参考文献 | 相关文章 | 多维度评价
    首页 | 前页| 后页 | 尾页 第1页 共4页 共36条记录