基于规则的标注算法.docx

基于规则的标注算法背景最大化标注（The Label-Number Maximization Problem）Find a maximum subset of the features,and for each of these features a label from its set of candidates, such that no two labels overlap在待标记对象集合中找到一个最大的子集，这些点标注位置没有任何重叠困难性它是个NP-hard。很难在线性时间内找到解。退而求其次，通常求得一个可接受的较优解即可。一个特殊情况，在所有对象都可以标注下的情况，可以转化成2sat算法，能够快速求得解。但这个方法不太通用。常用的算法更具每次运算结果是否一致，分为确定性算法和非确定性算法确定性算法（deterministic algorithms）贪心算法（Greedy algorithm）非确定性算法（Non-deterministic algorithms）模拟退火算法（Simulated Annealing）遗传算法（Genetic Algorithm）贪心算法的效率较高，但效果不是特别理想。模拟退火算法和遗传算法的效果较好，但需要较多次运算。前期试验过模拟退火算法，效果不错，但性能不太理想。新的算法最近发现一个基于规则的启发式算法, 参考Three Rules Suffice for Good Label Placement。整体效果比退火算法差一点，当比贪心算法强不少，效率在可以接受范围。算法分成两个阶段。第一阶段采用三个规则，尽可能的标注。这一阶段保证是最优的标注。第二阶段采用启发式方法去除冲突。并使用三个规则进行标注。这个阶段并没办法保证结果最优，除非找到一个最优的冲突移除方法。三个规则规则1 如果点p有一个候选标注位置pi.和其它标注位置没有任何冲突，则pi就是点p的标注位置，删去点9的其它候选标注位置:有一个为候选位置空，就放在那里规则2 如果点p有一个候选标注位置pi，pi只和点q的某一个候选标注位置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只剩下一个候选位置，就放在这里。消除和他有冲突的候选位置这三个规则可以保证是最优解。证明可参考Three Rules Suffice for Good Label Placement伪代码实现第一阶段 对所有点使用规则1 2 3判断。 （当满足规则后，邻居需要重新判断）第二阶段 启发式消除冲突算法 无法保证最优while 还有相交的候选位置 Do f = 最多候选位置的待标注对象 删除f中冲突最多的获选位置c 对和c有冲突邻居 使用规则1 2 3判断end实验初始状态第一阶段4 满足规则1 然后 3 满足规则15 和6 满足规则 27 满足规则3 然后 8满足规则1第二阶段只考虑剩余部分消除冲突 消除候选位置最多，冲突最多的位置规则1生效消除冲突三规则不起作用，接着消冲突规则1生效最终结果效率第一阶段 每个对象都需要判断一次，生效后没个邻居都要判断一次时间在O（n+k）。n为对象数 ， k为冲突对数。第二阶段 和冲突对是线性关系。效果权重问题待标注对象有权重。规则三 附加条件 p是集团中权值最高的标注位置有权重，右边好于左边。规则一 附加条件 pi是p中权值最高的位置规则二 附加条件 pi 和qj是结果得分最大的对消除冲突的原则 就选权值最低的对象 冲突最多的位置参考Improv