蒙特卡洛快投影聚类算法.docVIP

蒙特卡洛快速投影聚类算法 Cecilia M. Procopiuc AT＆T研究实验室 弗伦翰公园, NJ 07932 magda@ Pankaj K. Agarwal 计算机科学系 杜克大学 达勒姆, NC 27708 pankaj@ Michael Jones 三菱电机研究实验室 剑桥，MA 02139 mjones@ T. M. Murali 生物信息学计划 波士顿大学波士顿，MA 02215pankaj@ murali@ 摘要 我们为最佳投影集群的概念，提出了一个数学公式，从自然的要求出发，在子空间上的点密度。这使我们能够制定一个蒙特卡罗算法迭代计算射影簇。我们证明了计算集群是高概率的好。我们实施了该算法的修改后的版本，使用的启发式加快计算。我们大量的实验表明，该方法是明显比以前的方法更准确。特别是，我们用我们的技术，建立一个分类，在杂乱的图像旋转的人脸检测。 1. 投影聚类 聚类是一种广泛使用的技术进行数据挖掘，索引和分类。在过去几年中提出许多切实可行的方法CLARANS，BIRCH，DBSCAN和CURE，都是“全维”，在某种意义上说，他们给予同等重视所有的尺寸计算两点之间的距离时。虽然这种方法已被证明成功的低维数据集，其准确性和/或效率的增加显着高维空间（见一个很好的分析和讨论）。这一业绩恶化的原因是所谓的维数灾难。最近的研究表明，中度到高维空间（数十或数百个尺寸），一个完整的立体的距离往往是??无关紧要的，作为一个点最远的邻居预计将几乎接近其近邻。 如主成分分析方法（PCA），减少突出的一个子空间上的所有信息的损失降到最低点，使数据的维数。在这个子空间，然后用一个标准的聚类方法。但是，PCA不处理好这些情况时，不同子集点在于不同的低维子空间。例如在图1（a），任何企图以减少维数中的所有重要的信息丢失点结果，这样的手段全维的聚类技术是不可能发现数据中的三种模式。 图1：（a）三个子空间的格局;（b）盒对应的射影簇 认识到需要在降低数据维数为增加灵活性，最近的数据库研究提出计算射影簇，这点是密切相关的一些子空间组合在一起。而不是整个数据集上的一个单一的子空间投影，这些方法的项目及其相关子空间，通常是从另一个群集的子空间是不同的每个群集。投影聚类算法已成功地用于索引，以及适度的高维数据中的模式发现。 所有这些以前的办法是分区的方法，即他们到k集群和离群集划分的数据，并反复提高聚类质量。然而，没有正式的定义是什么构成一个最佳的k-聚类，并有没有输出质量上的保证。与大多数分区方法，这些方法也受到用户提供数字集群?的内在需要。这问题是不太严重，在索引应用的选择k的驱动以外的考虑，如所需的树k的扇出，小的变化不会影响到指数表现的一个重要方式。然而，当我们的目标是发现数据中的模式，甚至增加或减少1可以产生非常不同的输出。在这种情况下，集群方法必须与不同的k值称为几次，直到输出被视为不够“准确”（就一个质量的衡量标准，或由一个人类专家）。 我们的贡献。在本文中，我们对最佳投影集群的概念提出了一个数学的定义，从自然的要求出发，在子空间上的点密度。这使我们能够开发蒙特卡罗算法计算，具有较高的概率，一个最佳的投射群集的一个很好的近似值。我们称我们的算法是DOC，基于密度的最优投影聚类。 基于密度的方法已被使用之前，无论是全维聚类[10]，或枚举所有密集的子空间中的数据区域[3]。然而，这些方法依赖的维指数，主要是由于这一事实，他们使用定期电网，以便找到并连接密集区。有关的网格，在一般情况下，在维数的指数。为了缓解这一问题，最近的一项技术，称为OptiGrid[9]采用不规则网格确定超平面通过密度小的地区，以计算密集成群。由于我们是在射影簇感兴趣，我们采取略有不同的看法，我们需要在每个群集只有在其相应的子空间密集。正如我们将看到在下一节中，我们的密度条件仅指点，给定长度的间隔内的项目，不作任何点分布的假设。在我们的实验中，我们使用各种子空间分布产生的综合数据，并表明我们的算法维持对所有集合的高精度。 与全球划分的迭代的聚类。一旦我们有一个有效的方法产生可证明良好的射影簇，我们在一个贪婪的态度遍历算法，直到满足一些终止条件。在每次迭代中，我们计算了在目前的点集的最佳集群的近似。终止条件可以定义一个以上的方式，例如：一个点的一定比例已聚集;或已计算的集群用户指定的号码;或集群的质量措施减少太多。因此，分区方法相比，用户不需要指定的集群?除非他想。这允许更灵活地调整特定的应用程序使用它的算法。 此外，我们可以要求集群是不相交的，或允许他们有共同点。在第一种情况下，聚集点被淘汰，从随后的集群计算。在第二种情况下，聚集点没有消除，我们简单的检查，我们不会产生两次相同的群集。在实验中，我们讨论从图像处理的应用中，我们发现重叠集群，