A Fast and Flexible Clustering Algorithm Using Binary Discretization
A Fast and Flexible Clustering Algorithm Using Binary Discretization
复制标题
DOI：
10.1109/icdm.2011.9
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
M. Sugiyama;Akihiro Yamamoto
中科院分区：
文献类型：
--
作者：
M. Sugiyama;Akihiro Yamamoto
我们在本文中提出了一种新的多元数据聚类算法。该算法称为 BOOL（面向二进制编码的聚类），可以检测任意形状的聚类并且具有噪声容忍性。 BOOL 使用两步过程处理数据：首先将数据点离散化并表示为二进制字，然后通过使用这种表示形式聚集较小的簇来迭代构建簇。后一步是通过对此类二进制表示进行排序来以线性复杂度执行的，与其他技术相比，这会带来显着的加速。实验表明，BOOL 比 K 均值更快，比两种可以检测任意形状的非凸簇的最先进算法快约两到三个数量级。我们还表明，BOOL 的结果对参数的变化具有鲁棒性，而已知大多数任意形状簇的算法对此类变化过于敏感。 BOOL 鲁棒性的关键是通过提高离散化的准确性而自动引入的簇的层次结构。
We present in this paper a new clustering algorithm for multivariate data. This algorithm, called BOOL (Binary coding Oriented clustering), can detect arbitrarily shaped clusters and is noise tolerant. BOOL handles data using a two-step procedure: data points are first discretized and represented as binary words, clusters are then iteratively constructed by agglomerating smaller clusters using this representation. This latter step is carried out with linear complexity by sorting such binary representations, which results in dramatic speedups when compared with other techniques. Experiments show that BOOL is faster than K-means, and about two to three orders of magnitude faster than two state-of-the-art algorithms that can detect non-convex clusters of arbitrary shapes. We also show that BOOL's results are robust to changes in parameters, whereas most algorithms for arbitrarily shaped clusters are known to be overly sensitive to such changes. The key to the robustness of BOOL is the hierarchical structure of clusters that is introduced automatically by increasing the accuracy of the discretization.