剪枝策略

摘要： 0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究。研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差。虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解。针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法。该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率。大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率。

摘要： 辨识不同行业的典型负荷曲线对于配售电公司的运行调度、售电决策和风险管理均有重要意义.鉴于此,提出了一种基于剪枝策略和密度峰值聚类的行业典型负荷曲线辨识方法.首先,提出了衡量负荷曲线位移变化后相似性程度的快速动态时间扭曲(FDTW)距离指标,进而提出了一种搜索FDTW距离的剪枝策略,以实现对负荷曲线间形态差异的精准高效量度.接着,提出了基于加权密度峰值快速搜索聚类算法的行业负荷用电类型划分方法以及用户行业信息错误识别方法.然后,以最小化负荷曲线簇内FDTW距离为目标,提出了基于重心平均算法的行业典型负荷曲线辨识方法.最后,以浙江省某市工商业用户为例进行验证分析,算例结果表明所提方法可以准确量度负荷曲线形态相似性,快速划分行业用电类型并有效辨识具有共同形态特征的典型负荷曲线.

摘要： 剪枝策略(pruning mechanisms)是频繁模式挖掘算法常用方法之一,通过该策略可以快速克服工业生产中可能发生的金融危机,从而最大限度地提高制造业的生产能力.现有的剪枝策略算法仅考虑每个产品的利润信息,不考虑产品的权重,所以效率低下.提出了一种新的剪枝挖掘算法.通过基于低估值的约束和组件权重的挖掘索引器进行的有效剪枝挖掘,不但考虑了利润信息,而且考虑了权重信息.实验表明,该方法能节省大量的运行时间,大幅提高挖掘效率.

摘要： 针对自动化集装箱码头自主驾驶无人跨运车(Autonomous Straddle Carrier,ASC)的车辆路径问题,提出了一种改进的分支定价算法.考虑ASC的载荷量、每个作业点的时间窗和需求量等因素,以ASC总行驶距离最短为目标建立混合整数规划模型.根据Danzig-Wolf分解原理将模型分解为主问题和子问题,设计剪枝策略缩小解搜索空间,采用脉冲算法求解定价子问题,并嵌入列生成算法不断迭代寻优.在Java中调用Cplex求解小规模和较大规模算例,通过与传统分支定界算法的对比实验,以及对定界策略的时间步长和ASC不同载荷量的灵敏度分析,验证了模型的可行性和算法的有效性.

摘要： 高效用模式挖掘用于从数据中找出对用户有用的信息.现有的高效用模式挖掘算法很多,如何选择更优的方法进行使用,是普遍存在的问题.要解决这个问题首先要了解高效用模式挖掘算法的分类,继而针对问题找出对应的算法.按照不同的角度可以划分多种不同类型的算法.从使用数据结构的类型,划分为基于树和基于效用列表的方法;从算法所需要经历的阶段,划分为一阶段和两阶段算法;还可以从算法使用的剪枝策略进行划分,如投影,保留效用,提高最小阈值等.首先对一阶段、两阶段高效用模式算法进行分析,主要分析基于树的两阶段算法和基于列表的一阶段算法.然后从是否产生候选分析基于树的高效用模式算法.最后分析高效用模式算法用到的缩减空间策略,如剪枝策略、投影技术等.通过分析得到一阶段算法在时间与空间上优于两阶段算法,不产生候选项集的算法在时间与空间上优于产生候选项集的算法,算法缩小搜索空间一般通过多种剪枝策略.

摘要： k步可达性查询用于回答图G中从顶点u到达顶点v最多k步是否存在路径,但其多用于无权图的可达性研究.针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模.运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为O(n+e)和O(n),这里n和e分别为图中顶点的数目和边的数目.该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能.最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性.

摘要： 多数基于FP-growth思想的频繁模式挖掘算法存在建树过程复杂、支持度计算繁琐的问题.针对这些问题,提出一种基于位编码链表(Bitmap-Code List,BC-List)的频繁项集挖掘算法(BC-List Frequent Itemsets Mining,BCLFIM).该算法首先采用基于位图表示的节点编码模型生成位图树(BC-tree),以BC-tree的节点信息作为数据结构通过按位运算来快速获取BC-List的节点集,避免了复杂的交集运算,提高了连接效率;其次通过使用超集等价和支持度计数剪枝策略,缩小了挖掘频繁模式的搜索空间.实验结果证明,该算法相比于FIN算法和DFIN算法具有更快的挖掘速度.

摘要： 针对随时间进化的动态社交网络展开影响最大化问题的研究,目标是基于线性阈值传播模型,挖掘影响力最大的k个种子用户,从种子用户发起传播,最大化影响传播范围.提出一种基于线性阈值模型的动态社交网络影响最大化算法(linear threshold dynamic influence maximization,LTDIM).首先,给出动态社交网络影响最大化问题的形式化定义,提出利用活边路径获取初始种集的方法;然后,分析网络的各种拓扑变化,提出种集的增量式更新方法;最后,基于节点度和影响力增量提出DP(degree pruning)和IIP(influence increment pruning)剪枝策略进一步提高时间效率.实验使用4个真实的社交网络数据,考察在8个网络快照上算法的运行时间和影响传播范围.实验结果表明,本文算法的影响传播范围接近于静态启发式算法,运行时间大幅度减少,验证了算法的时间高效性和可扩展性.

摘要： 本文参照基于短语的机器翻译系统moses,改进并实现了该系统的算法。剪枝策略将机器翻译系统的代价控制在可接受的范围内,同时,剪枝策略也是影响翻译质量的重要因素之一.与Moses实现的lazy算法不同,本文将几种剪枝策略相融合实现了一种综合的剪枝策略.以NIST02作为开发集,NIST05作为测试集,在相同参数和翻译模型下,Moses系统的bleu为23.89％,本文系统为24.09％.以该系统为基线,本文提出并实现了一种不划分边界路径的cube-pruning算法,以较小的翻译质量的损失为代价,使解码速度提高了20倍,该系统的bleu得分为23.63％。

摘要： 最大频繁项集挖掘可以广泛应用在多种重要的Web挖掘工作中.为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略.这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝.应用该策略,对MAFIA算法进行改进优化.实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原MAFIA算法提高3～5倍。

摘要： 公共交通网络下的最优路径搜索问题在实际生活中有重要的应用.特别地,用户的偏好以及偏好的权重对于路径规划和搜索也相当重要.本文提出了公共交通网络下关键词覆盖的最优路径搜索问题,并证明该问题是NP-hard.本文提出了一种A*算法来提高路径搜索效率,并提出了剪枝策略改善算法性能.本文进行实验对所提出算法与暴力算法在时间性能上做了比较,以及比较剪枝策略的时间性能验证了算法的有效性.

摘要： why-not问题是为查询结果中的缺失元组找到合理的解释解决数据库查询中的why-not问题不仅能够帮助用户更好的理解查询,而且能够帮助提高数据库的质量和可用性为了提高图数据库的可用性,提出了支持近似图查询的why-not问题解释方法该解释方法不仅阐明了为什么why-not问题没有出现在查询结果中,而且给出了一些修改初始查询图的建议,使得why-not问题能够出现在修改后的查询图的查询结果中支持近似图查询的why-not问题解释算法分两阶段完成,第一阶段利用图的星型结构表示方式,比较查询图与why-not图之间的差异,得到修改初始查询图的候选操作集,针对why-not问题数量的不同,提出了候选操作集生成基本算法和改进算法;第二阶段基于对查询图修改操作数要求最少的代价模型,对第一阶段生成的候选操作集构建回溯剪枝树,并提出三种剪枝策略执行剪枝操作,最终选取的候选操作集即为支持近似图查询的why-not问题的合理解释实验表明,本文提出的方法可以快速有效地为支持近似图查询的why-not问题提供合理解释.

摘要： 近些年,由于数据采集的不精确和数据本身的不确定性,使不确定性在位置数据中普通存在.在障碍空间中,聚类不确定数据面临新的挑战.提出了障碍空间中聚类不确定数据的OBS-UK-means算法,并提出了分别基于R树和Voronoi图的两种剪枝策略和最近距离区域的概念,大大减少了计算量.通过实验验证了OBS-UK-means算法的高效性和准确性,同时证明了剪枝策略在不损害聚类有效性的情况下,能够有效地提高聚类效率.

摘要： 随着图规模的增大,当前的大多数图聚类算法在时间和空间方面的伸缩性表现很差.一个重要发现是,许多聚类应用只需要最佳簇形成的子集合,而不是整个图中的所有簇.针对这种实际情况,提出一种剪枝策略Best Nodes(BN),找到最有可能是最佳簇组成部分的那些节点.通过实验证明,能够明显提高聚类算法的可伸缩性。

摘要： 频繁子图挖掘是各种图挖掘的基础和瓶颈，为了提高频繁子图挖掘算法的效率，在频繁闭图方法的基础上提出了一种新算法BPCG．首先使用了一种新结构表存储频繁子图集，从而不需扫描图集就可直接扩展最频繁邻接边及计算支持度阈值;然后算法又利用兄弟剪枝策略和删除局部频繁边，缩小搜索空间并减少不必要的操作．通过实验证明，算法优于其他子图挖掘算法．

摘要： FP-Max算法是一种有效的最大频繁模式挖掘算法,但它在挖掘过程中产生的候选集规模过大,需要构造和遍历大量没必要的条件FP树,因此效率低。为此提出了SMFP-Max算法,算法以FP树和对称矩阵为框架来挖掘最大频繁模式,在挖掘过程中采用了多种剪枝策略并结合自顶向下和自底向上的双向搜索策略,大大缩小了候选集规模,避免了不必要的条件FP树的产生.理论分析和实验结果表明,SMFP-Max算法是一种高效的最大频繁模式挖掘算法,具有良好的时空效率,算法性能优于FP-Max算法。

摘要： 任务调度是网格系统中的一个非常Min剪枝策略,在独立任务调度序列的解空间中进行有效搜索.与现有的Fast-Greedy,Min-Min,Max-Min和Max-Int算法相比,新的回溯算法能够获得最优的总任务的最小完成时间Makespan.

摘要： 深度神经网络模型因为性能优异,最近几年已经被广泛应用于图像识别、语音识别、自然语言处理及其他人工智能子领域,在某些领域其性能甚至超过人类水平.但是,由于深度网络参数众多,导致其具有占用空间大和运行速度慢等缺点,因此深度网络在硬件受限的终端设备上的存储和运算仍是一个很大的挑战.已经有研究表明深度网络中存在冗余,即可以删减部分参数的同时保持网络的性能不损失,基于这个事实研究人员提出了很多深度网络的压缩和加速方法,本综述从剪枝,权值共享,权值矩阵分解等三个方面对这些方法做了归纳总结.

摘要： 本发明涉及语言模型剪枝领域，尤其涉及一种基于预剪枝和联合剪枝的语言模型剪枝方法，包括通过设备预留存储空间和语言模型实际所占存储空间计算出总剪枝率；采用预剪枝方法获取语言模型结构性剪枝率和语言模型各层的非结构性剪枝率；对语言模型进行结构性剪枝和非结构性剪枝，并且通过重训练方式恢复模型精度；本发发明通过预剪枝这种剪枝率分配方式可以获取合理的语言模型结构性剪枝率和语言模型各层的非结构性剪枝率，并且联合结构性剪枝和非结构性剪枝可以对语言模型进行彻底的剪枝。

摘要： 本发明提供了一种基于平衡二叉树的集成剪枝策略，所述方法包括如下步骤：S1、基分类器集成池初始化：对大数据集进行切分形成众多子数据集，再针对每一个子数据集进行训练和测试工作，形成初始的完整分类器池；S2、构建平衡二叉树，形成最终的子集成；S3、使用保留下来的最佳子集成进行新数据样本的预测与分类。本发明解决了易产生拟合现象，难以剔除测试精度太高或太低的基分类器，泛化性能不高的技术问题。

摘要： 本发明是一种基于深度剪枝策略的关联规则挖掘方法，用于对大数据集进行关联规则挖掘。本方法借鉴了基于压缩矩阵的Apriori算法的思想，对1‑频繁项集并不按照支持度计数进行排序，而是直接按照值大小对布尔矩阵内的向量进行排序，以确定之后的频繁项集连接的相对顺序；对k‑频繁项集根据事务长度进行压缩，删掉长度小于k的事务；根据项跟位置关系对k‑频繁项集进行剪枝，对于首项为I的k‑频繁项集的前k‑1项，位置在i的项出现的次数必须大于等于k‑i。本发明相对于MTCA算法，处理时间要短很多，并且在支持度较低的情况下比Apriori标准方法节约大量的时间，从大数据集获取关联规则的效率更高。

摘要： 本发明公开一种基于剪枝策略构建卷积神经网络的遥感图像目标检测方法，该方法包括以下步骤：步骤一、对目标检测训练数据集进行预处理；步骤二、对初始网络进行预训练，获得稠密网络；步骤三、对步骤二得到的稠密网络，采用基于网络剪枝技术的稠密‑稀疏训练方式，获得训练后稀疏网络，对训练后稀疏网络采用稠密训练方式进行训练，获得精确目标分类网络；步骤四、对步骤三得到的训练后稀疏网络进行处理，并采用稀疏‑稀疏的训练方式，获得快速区域提取网络；步骤五、从目标检测测试数据集生成多尺度图像金字塔，再先后使用快速区域提取网络和精确目标分类网络进行两阶段预测，获得目标的位置和类别标签。

摘要： 一种基于快速剪枝策略的高效用序列模式的用药DDD值数据分析方法，包括以下步骤：步骤1、对整理出用药记录表和药品DDD值表，对用药记录表中每条的用药记录的数据进行预处理；步骤2、计算序列数据库中q‑项的序列权重效用值SWU；步骤3、去除序列权重效用值SWU小于阈值ξ的q‑项，得到新的s‑序列数据库；步骤4、建立q‑项集内连接效用矩阵WICUM；步骤5、建立q‑项集间连接效用矩阵BICUM；步骤6、建立数据库中每个项的效用矩阵；步骤7、建立序列模式树，得到全部的高效用序列模式，这些高效用序列模式代表不同时间段服用各种药物，各种药物间组合后累计DDD值是超出阈值的，为高累计DDD值药物组合。本发明简化了剪枝操作的复杂性并减少了数据库的扫描次数，从而提高了挖掘高效用序列模式的效率。

摘要： 本发明公开了一种基于模型参数和剪枝策略的持续学习图像识别方法及装置，方法包括：收集新增类别数据及历史类别数据；构建持续学习图像识别模型；将新增类别数据与Rehearsal策略保存的部分旧类别数据合并，组成训练数据；输入持续学习图像识别模型中，新增特征提取器和FC层；利用知识蒸馏训练持续学习图像识别模型，并使用剪枝策略去除新增特征提取器中不重要的卷积核；对新增类别数据及历史类别数据使用Rehearsal策略，保存部分类别数据；将待测试数据输入持续学习图像识别模型中进行测试，获得图像识别结果。本方法从模型参数角度，采用知识蒸馏解决了图像识别中持续学习问题，结合剪枝策略减缓模型参数量的增长速度，提高了图像识别的准确率和效率。

摘要： 本发明涉及一种基于自动化剪枝策略的青铜铭文识别方法，属于图像识别技术领域。该方法首先收集需要识别的青铜铭文图像样本，然后利用图像预处理技术对图像进行尺寸调整及归一化操作，制作成训练集和测试集。最后在基于L1范数的卷积核剪枝基础上提出一种自动化模型剪枝策略，可以在无需人工干预的情况下自动完成模型的剪枝操作，寻找最佳匹配结构。本发明可以有效减少参数量及FLOPs，提高网络运行速度，提升模型泛化能力，寻找到最适配青铜铭文数据集的网络模型。

摘要： 本申请实施例公开了确定网络模型剪枝策略的方法、装置、设备以及存储介质，涉及计算机视觉、深度学习等人工智能技术领域，具体可用于图像处理场景。该方法包括：采用针对目标硬件的网络模型的BN阈值搜索空间的配置信息，生成BN阈值搜索空间；采用BN阈值搜索空间，生成剪枝策略编码生成器；采用剪枝策略编码生成器，随机生成BN阈值编码；对BN阈值编码进行解码，得到待选BN阈值；根据对应于待选BN阈值的网络模型的剪枝精度损失，确定用于目标硬件的网络模型的目标剪枝策略，通过自动搜索的方式得到最优的BN阈值，并用BN阈值代替通道重要性对网络模型进行剪枝，进而大幅度降低网络模型的剪枝后精度损失。

摘要： 本发明提供了一种基于平衡二叉树的集成剪枝策略，所述多梯级多线船闸结构包括如下步骤：S1、基分类器集成池初始化：对大数据集进行切分形成众多子数据集，再针对每一个子数据集进行训练和测试工作，形成初始的完整分类器池；S2、构建平衡二叉树，形成最终的子集成；S3、使用保留下来的最佳子集成进行新数据样本的预测与分类。本发明解决了易产生拟合现象，难以剔除测试精度太高或太低的基分类器，泛化性能不高的技术问题。

摘要： 一种基于剪枝策略的关键性电路单元定位方法，首先，网表解析及相关量的初始化；其次，构建满足均匀非伯努利序列分布特点的输入向量；接着，利用反向深度递归搜索算法设计一种面向非关键性互连导线的剪枝方法；然后，结合SCA方法实现了电路单元关键性的度量；最后，根据所得的关键性对电路单元实施排序。本发明基于电路的应用环境，通过非关键性电路单元的裁剪，并结合SCA方法，实现了电路结构中关键性单元的有效定位。它将在电路设计的早期阶段，有望基于较小代价在较大程度上促进电路结构可靠性的改善。