分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2022-05-18 合作期刊: 《计算机应用研究》
摘要: 警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。
分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2022-04-07 合作期刊: 《计算机应用研究》
摘要: Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中,找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。本文针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与8种局部搜索算法进行精度方面的对比实验。实验结果表明WWP+WalkSAT算法有较好的性能。
分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2020-09-28 合作期刊: 《计算机应用研究》
摘要: 收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性。具有复杂结构的命题公式,信息传播算法不总收敛,为了系统地对此现象给予理论解释。借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。
分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2020-09-28 合作期刊: 《计算机应用研究》
摘要: 高效用模式挖掘(high utility pattern mining,HUPM)是近年来研究的新兴主题。效用的概念为分析人员挖掘相关项集提供了更大的灵活性,以用户的需求为出发点,从权重、值、数量和其他信息进行度量。通过分析有关HUPM最先进的方法,对其进行全面和结构化的概述。首先,通过介绍HUPM的相关概念、公式,并给出应用示例,对HUPM有更深一步的理解。针对用于挖掘不同类型HUPM的最常见和最先进的关键技术的进行分类,包括基于Apriori,基于树,基于列表,基于映射,基于垂直/水平数据格式,基于索引等方法。针对现有关键技术的用途和优缺点,进行了全面概述。然后,由于静态数据难以满足实际需要,总结了在数据流上应用的HUPM方法,主要包括基于增量方法,基于滑动窗口模型方法,基于时间衰减模型方法,基于地标模型方法等。最后,给出了现在技术的不足和改进方向,并且有针对性的提出了新的研究方法。
分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2019-04-01 合作期刊: 《计算机应用研究》
摘要: 信息传播算法求解可满足性问题时非常有效,警示传播(warning propagation,WP)算法是最为基础的信息传播算法。通过对WP算法的数学原理分析,高概率确定的部分变元与公式的骨干集合后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n, 3, m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。
分类: 计算机科学 >> 计算机科学的集成理论 提交时间: 2018-11-29 合作期刊: 《计算机应用研究》
摘要: 当前,数据流分类算法的潮流是集成分类算法,因为集成算法提供了比单分类算法更好的性能和更突出的表现。同时在现实世界的实际应用中容易部署,对概念漂移有快速的适应性和恢复性,而且在类不平衡问题的处理中也具有最佳的分类性能。详细介绍了国内外集成分类算法,对集成分类算法的两个部分(基分类器组合和动态更新集成模型)进行了详细综述,明确区分不同集成算法的优缺点,对比算法和实验数据集。并且提出进一步的研究方向和考虑的解决办法。