大规模层次分类中的候选类别搜索

大规模层次分类问题研究如何将互联网上的网页文档准确地分到类别层次中的各个类别.因为类别层次规模巨大,通常可以达到数千甚至数万个类别,严重影响了分类性能.对此,已有研究通过搜索待分类文档在类别层次中的候选类别对文档进行分类,但结果表明候选类别搜索成为了其中瓶颈.文中首先对候选搜索问题的计算复杂性进行了分析,证明了该问题是NP难的,接下来提出了一个基于贪心策略的启发式候选搜索算法,并且证明了该贪心策略在求解过程中是一个局部最优选择.作者采用DMOZ目录中的简体中文网页数据进行了实验论证,实验结果显示,相比已有算法,文中提出的候选类别搜索算法在候选类别搜索的准确率上提高了大约7.5%.

新的结构化测试数据自动生成方法

针对模拟退火算法,遗传算法应用于测试数据的自动生成的局限性,提出了一种基于GEMGA(基因表达散乱遗传算法)的结构化测试数据的自动生成的方法。讨论了路径的选择,提出了将控制流图与数据流图结合起来生成测试路径,通过TriType的分析结果说明了该方法的可行性。根据得到的测试路径将GEMGA应用到测试数据的自动生成,TriType的实验结果表明,GEMGA能生成更高质量的数据,并适用于较大规模的程序。

相容关系的最大相容类的生成算法

集合A上的二元关系R称做相容关系,如果它是自反的、对称的。若B是集合A的非空子集,且B中的任意两个元素都有相容关系R,则称集合B为相容关系R的相容类。不能真包含在任何相容类中的相容类即为最大相容类。文章研究了生成相容关系的最大相容类所需要的理论,设计了生成相容关系的最大相容类的实用算法——优化广度优先搜索。

一种基于Hadoop的高效空间拓扑关系判定方法

考虑到互联网数据的海量规模,采用传统方法的空间拓扑关系判定已远超出当前系统的处理能力。以分层法和二分查找法为基础提出了一种判定海量地理坐标与给定区域空间拓扑关系的高效判定算法,并结合Hadoop/Hive平台对算法进行优化。实验结果表明该方法可高效实现对海量空间数据的拓扑关系判定,并在算法精度上具有与ESRI传统算法相媲美的结果。

基于层次的草图检索框架

手绘草图是人类最自然的人机交互方式,在笔式计算模式下手绘草图将得到越来越多的应用,手绘草图的检索也成为一个新的课题。一幅草图可以包括手写的注释、符号、文档中的评注等。将手绘草图存储到数据库中,供用户检索使用将非常有意义。提出了一种对草图进行简化并按草图的层次进行匹配的检索方法;该方法先对草图中的阴影区域或由复杂笔划组成的区域进行自动探测,然后将其简化为一个超笔划。在匹配阶段,将不同特征空间上的相似度与基于层次的相似度合并即为最后的相似度;然后将具有最高相似度的结果集返回给用户。