基于规则的标注算法

《基于规则的标注算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于规则的标注算法背景最大化标注（TheLabel-NumberMaximizationProblem）Findamaximumsubsetofthefeatures,andforeachofthesefeaturesalabelfromitssetofcandidates,suchthatnotwolabelsoverlap在待标记对象集合中找到一个最大的子集，这些点标注位置没有任何重叠困难性它是个NP-hard。很难在线性时间内找到解。退而求其次，通常求得一个可接受的较优解即可。一个特殊情况，在所有对象都可以标注下的情况，可以转化成2sat算法，能

2、够快速求得解。但这个方法不太通用。常用的算法更具每次运算结果是否一致，分为确定性算法和非确定性算法确定性算法（deterministicalgorithms）贪心算法（Greedyalgorithm）非确定性算法（Non-deterministicalgorithms）模拟退火算法（SimulatedAnnealing）遗传算法（GeneticAlgorithm）贪心算法的效率较高，但效果不是特别理想。模拟退火算法和遗传算法的效果较好，但需要较多次运算。前期试验过模拟退火算法，效果不错，但性能不太理想。新的算法最近发现一个基于规则的启发式算法,参考《T

3、hreeRulesSufficeforGoodLabelPlacement》。整体效果比退火算法差一点，当比贪心算法强不少，效率在可以接受范围。算法分成两个阶段。第一阶段采用三个规则，尽可能的标注。这一阶段保证是最优的标注。第二阶段采用启发式方法去除冲突。并使用三个规则进行标注。这个阶段并没办法保证结果最优，除非找到一个最优的冲突移除方法。三个规则规则1如果点p有一个候选标注位置pi.和其它标注位置没有任何冲突，则pi就是点p的标注位置，删去点9的其它候选标注位置:有一个为候选位置空，就放在那里规则2如果点p有一个候选标注位置pi，pi只和点q的某一个

4、候选标注位置qk冲突，而点q有一个候选标注位置qj（j!=k）只和点p的某一个候选位置pl（l!=i）重叠，则pi和qj分别为点p和q的标注位置，删去点p和点q的其他候选标注位置。P有一个候选位置和q一个候选位置冲突q有一个候选位置和p一个候选位置冲突规则3如果点p只剩下一个候选标注位置pi，和pi重叠的候选标注位置形成了一个小集团（集团内的候选标注位置相互冲突），则pi为点p的标注位置，删去所有和pi冲突的候选标注位置。P只剩下一个候选位置，就放在这里。消除和他有冲突的候选位置这三个规则可以保证是最优解。证明可参考《ThreeRulesSuffice

5、forGoodLabelPlacement》伪代码实现第一阶段对所有点使用规则123判断。（当满足规则后，邻居需要重新判断）第二阶段启发式消除冲突算法无法保证最优while还有相交的候选位置Dof=最多候选位置的待标注对象删除f中冲突最多的获选位置c对和c有冲突邻居使用规则123判断end实验初始状态第一阶段4满足规则1然后3满足规则15和6满足规则27满足规则3然后8满足规则1第二阶段只考虑剩余部分消除冲突消除候选位置最多，冲突最多的位置规则1生效消除冲突三规则不起作用，接着消冲突规则1生效最终结果效率第一阶段每个对象都需要判断一次，生效后没个邻居都

6、要判断一次时间在O（n+k）。n为对象数，k为冲突对数。第二阶段和冲突对是线性关系。效果权重问题待标注对象有权重。规则三附加条件p是集团中权值最高的标注位置有权重，右边好于左边。规则一附加条件pi是p中权值最高的位置规则二附加条件pi和qj是结果得分最大的对消除冲突的原则就选权值最低的对象冲突最多的位置参考ImprovingMapnikwithLabelPlacementAlgorithmsThreeRulesSufficeforGoodLabelPlacement