针对大规模稀疏文档聚类，提出高效球形K均值算法。
Accelerating spherical K-means clustering for large-scale sparse document data
- 利用高频词与高均值特征项的分布特性，构建分段索引结构。
- 在真实数据集上速度比现有方法快2~4倍，内存访问减少60%以上。
- 适合处理海量稀疏文本数据，如新闻、社交媒体内容聚类。
本文提出一种加速的球形K均值聚类算法，适用于大规模高维稀疏文档数据。设计了一种架构友好型操作（AFM），通过抑制现代计算机系统中指令数、分支预测错误和缓存缺失等因素来提升性能。基于数据对象与簇均值集合的通用特性（UCs），包括词频分布的偏态性（如齐普夫定律）和特征值集中现象，发现相似度计算中大部分乘法运算集中在高文档频率（df）的词项上，且多数相似度由少数高均值特征值决定。算法在均值集合上引入倒排索引结构，通过两个新提出的结构参数提取高频词与高均值特征项区域，并将索引分为三部分实现高效剪枝。通过最小化乘法次数与指令数的近似关系确定结构参数，共享索引结构以减少分支预测错误，并通过缓存常访问区域的数据降低缓存缺失。实验表明，该算法在大规模文档数据上相比当前最优技术显著提升速度，平均加速比达2.3~4.1倍，缓存命中率提升超过60%。
原文摘要 · Abstract (English)
This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We design an algorithm working in an architecture-friendly manner (AFM), which is a procedure of suppressing performance-degradation factors such as the numbers of instructions, branch mispredictions, and cache misses in CPUs of a modern computer system. For the AFM operation, we leverage unique universal characteristics (UCs) of a data-object and a cluster's mean set, which are skewed distributions on data relationships such as Zipf's law and a feature-value concentration phenomenon. The UCs indicate that the most part of the number of multiplications for similarity calculations is executed regarding terms with high document frequencies (df) and the most part of a similarity between an object- and a mean-feature vector is obtained by the multiplications regarding a few high mean-feature values. Our proposed algorithm applies an inverted-index data structure to a mean set, extracts the specific region with high-df terms and high mean-feature values in the mean-inverted index by newly introduced two structural parameters, and exploits the index divided into three parts for efficient pruning. The algorithm determines the two structural parameters by minimizing the approximate number of multiplications related to that of instructions, reduces the branch mispredictions by sharing the index structure including the two parameters with all the objects, and suppressing the cache misses by keeping in the caches the frequently used data in the foregoing specific region, resulting in working in the AFM. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。