集成式位置敏感聚类方法

针对常用图像聚类尤其是图像视觉聚类方法聚类速度慢、不支持增量聚类的局限，提出了集成式位置敏感聚类方法。该方法首先根据聚类有效性指标估计合适的聚类数目，然后生成多重哈希函数，并用它们对各数据点进行映射得出多重桶标记，再对数据集各桶标记进行聚类得出多个基划分，最后对多个基划分进行集成得出最终划分。实验结果表明，在准确率方面，集成式位置敏感聚类在人工数据上与k-means结合聚类集成的方法相当，在图像集上与k-means结合聚类集成的方法接近。但集成式位置敏感聚类的优点在于其聚类时间快、适合于增量聚类等。因此，集成式位置敏感聚类方法可以用于解决高维图像特征聚类问题。

数据聚类是把给定的数据集划分为多个类的无监督的过程，使得同一类内的数据点比不同类间的数据点更相似。在对高维空间中的数据集聚类时，许多算法的有效性和效率会明显降低。主要有以下几个原因，一是高维数据的内部稀疏性阻碍了这些算法性能的发挥；二是高维空间中两点距离趋于一致[1]， 因此从不相似数据中找出相似数据的难度更大；三是高维空间中的类可能存在于子空间中，不同的类可能存在于不同的子空间中[2]。图像聚类是典型的高维空间聚类，因为几乎所有图像特征的维数都很高。

因此，高维聚类的难题也存在于图像聚类中。虽然近年来出现了不少聚类算法，但他们中的许多算法在对图像聚类尤其是图像视觉聚类中的效果并不好。在视觉聚类中经常使用的仍然是k-means 算法，这或许是因为设计一个能替代k-means 的通用聚类算法确实比较困难。但是，在增量数据集上，k-means 的缺点会比较明显，因为它的聚类速度很慢，而且不支持增量聚类，运行时间会随着数据集规模的增大而急剧增长。在用于视觉词典生成的聚类中存在着多义性和同义性等问题，这就需要找出新算法。

随机映射是近年来研究较多的算法，它可以降低维数同时在一定程度上保持原有结构不变。例如， 欧式空间的n 维的点可以映射到d 维并且d 远小于n。这样的随机映射主要应用在降维[3]和快速近似最近邻搜索[4]，它的应用范围还包括信号处理[5]、异常检测[6]、聚类[7]和分类等[8] [9]。

E2LSH (Exact Euclidean Locality Sensitive Hashing) [10]是随机映射的一个特例，近年来也引起了人们更多的注意，被应用在不少领域如检索[11]、复制检测[12]等。它在用于近似最近邻检索时，在保持较高准确率的同时有着很低的运行时间，是当前近似最近邻检索的主流算法。它把高维向量映射到低维空间后，也完成了维数约减的任务。同时，相同的桶中的点比不同桶中的点更相似。因此，如果根据桶标志对数据点进行分组，也可以达到对数据点进行聚类的目的。而且，E2LSH 是一个数据无关的方法， 它在对一个点进行映射时与其它点无关，这意味着它可以方便地为一个动态数据库建立索引。类似地， 用于聚类时， 当数据集规模变化时不需要对整个数据集重新进行聚类， 只需要对变化的数据点运算即可， 也就是说它可以方便地起到动态聚类的作用，再加上它的时间优势使得它可以较好的用于增量大数据集聚类。事实上，LSH 算法的提出者已经指出LSH 可以用于快速聚类，但他没有进一步进行理论证明和实验验证。不过，Ravichandran D 已经将LSH 的欧式空间实现方案E2LSH 用于名词聚类[13]。然而，图像