基于GPU的多级聚类 (GPU-Based Multilevel Clustering)

在许多应用尤其是数据分析中,我们经常会遇到大规模数据集聚类的任务,在大的多边形表面网格问题中,这个任务显得更为重要,因为目前的3D模型采集系统提供多达上百万种的表面模型。在聚类问题中,通常最常用到的两种方法是k-means聚类算法和分层方法,然而这两种方法都有一些缺点,这会严重影响他们的性能。这篇文章提出了一种在GPU上单独实施的针对网格聚类的框架。这种框架主要的算法元素是基于边界的查询,它的主要算法优势是多极方面内在地解决了初始化问题,由此提供了具有鲁棒性和高质量的聚类结果,其次,这种算法适用于任何全局数据结构。

figure2

 图1. 基于边界的聚类步骤

这种基于边界的聚类方法可以有效减少优化过程中所需的能量计算,如图1所示,初始时,针对给定数量的几个聚类,使用随机方法为每个聚类给定一个起始点,之后逐渐增加边界环直到整个模型被填满,在优化过程中,应用基于边界的聚类优化算法来最小化配置所需的能量,直到收敛或者达到一个确定的迭代次数。

figure4

图2. 重新分配点集Q到一个更近的聚类所需检查的2D案例

在优化方面,这篇论文在经典k-means算法的基础上提出了一种新的算法,叫做Local Neighbors K-Means。假设有一个拥有m个离散点的集合Q,用这种方法把这个集合分成k个聚类就意味着属于某个聚类的点用某种能量测量的话距离这个聚类要比任何其它聚类都近,现在假设初始时已经有了一种可能不是最近的分配方法,根据这种算法就需要把他们重新分配。如图2所示,图中绿色的箭头指向必须检查的聚类,红色的线表示当前点集的分配方法,蓝色箭头指向相邻聚类。

figure1

图3. 一个基于边界的聚类的优化步骤的例子

在GPU操作细节中,全部聚类过程都是在GPU上进行的,可以把在CPU和GPU之间转移数据的耗费减少到最小,这里的操作基于OpenGL,可以轻易和高效地集成全部聚类算法。数据结构如图3所示。顶部是网格和相应的faceID,底部是RGBA的face信息结构,每个结构包括聚类ID和三个相邻聚类的ID,从b图到e图是初始的聚类增长过程,f图和g图是基于边界的优化过程。

figure5

图4. 一个针对15个聚类的CVD结构的初始和网格聚类后的结果

图4是一种聚类后的结果,我们可以看到,比起a图和c图的初始结构,b图和d图的聚类结果让我们看到了非常优秀的聚类优化成果,比如初始左腿上的绿色部分,在优化后转移到了背后,这说明哪怕初始时非常糟糕,基于边界的算法也可以执行的非常好,并且还可以看到,结果有着非常好的对称性,这说明优化会得到一个很好的视觉质量。

这篇论文提出的算法是一种广泛适用的新的多层级聚类技术,它是用并行算法来论证的,并且结合了局部相邻检测,这种分层技术的优化和并行算法构想的结合生成了一种新型的多级聚类方法。

[1] Iurie Chiosa and Andreas Kolb. (2011). GPU-Based Multilevel Clustering. Visualization and Computer Graphics, IEEE Transactions on, 17(2), 132-145.

评论关闭。