论文部分内容阅读
概念格理论,也叫形式概念分析(FCA),是一种有效的知识表示与知识发现的工具,已被成功应用于知识工程、机器学习、信息检索、数据挖掘、语义Web、软件工程等许多领域。要使用概念格理论分析数据,就要首先根据数据建造相应的概念格,其中的关键问题是建格算法的效率,而提高算法效率的一种有效方法是并行计算。随着硬件图形处理技术的发展,GPU的计算能力得到长足的进步,并开始作为通用计算单元使用。相对于CPU,GPU具有更高的并行性和更低的成本,这使得基于GPU的并行技术很快成为当前并行计算领域的研究热点。本文通过研究国内外建格算法的现状,对比批量式和增量式建格算法的优劣,结合现今GPU通用计算的并行优势,提出了基于GPU的合并建格算法。该算法在GPU上实现,以概念格合并为主要思想。算法首先对形式背景进行冗余处理,排除掉那些不需要进行复杂判断的数据(对象或者属性);然后根据对象或者属性的存储顺序将背景合理拆分;利用GPU的多线程机制对拆分出来的子背景进行并行建格,此处子背景建格采取的建格算法同样是基于概念格的合并思想(纵向合并);最后对这些子背景产生的概念格并行横向合并,得到原始形式背景对应的概念格。实验结果证明该算法在一定数据规模下提高了建格效率,因而是有效的。文章最后讨论了该算法可以进行优化的几个方面,包括形式背景划分和动态负载均衡等。