基于随机数三角阵映射的高维大数据二分聚类初始中心高效鲁棒生成算法

Bisecting K-means算法通过使用一组初始中心对分割簇，得到多个二分聚类结果，然后从中选优以减轻局部最优收敛问题对算法性能的不良影响。然而，现有的随机采样初始中心对生成方法存在效率低、稳定性差、缺失值等不同问题，难以胜任大数据聚类场景。针对这些问题，该文首先创建出了初始中心对组合三角阵和初始中心对编号三角阵，然后通过建立两矩阵中元素及元素位置间的若干映射，从而实现了一种从随机整数集合中生成二分聚类初始中心对的线性复杂度算法。理论分析与实验结果均表明，该方法的时间效率及效率稳定性均明显优于常用的随机采样方法，特别适用于高维大数据聚类场景。

An Efficient and Robust Algorithm to Generate Initial Center of Bisecting K-means for High-dimensional Big Data Based on Random Integer Triangular Matrix Mappings

The algorithm of Bisecting K-means obtains multiple clustering results by using a set of initial center pairs to segment a cluster, and then selects the best from them to mitigate the adverse effect of the local optimal convergence on the performance of the algorithm. However, the current methods of random sampling to generate initial center pairs for Bisecting K-means have some problems, such as low efficiency, poor stability, missing values and so on, which are not competent for big data clustering. In order to solve these problems, firstly the lower triangular matrix composed by the pairs of initial centers and the lower triangular matrix composed by serial numbers of the pairs of initial centers are created. Then, by establishing several mappings between the elements and their positions in the two matrices, a linear complexity algorithm is proposed to generate initial center pairs from the set of random integers. Both theoretical analysis and experimental results show that the time efficiency and efficiency stability of this method are significantly better than the current methods of random sampling, so it is particularly suitable for these scenarios of high-dimensional big data clustering.