Tshikei: An Efficient One-Dimensional K-Means Clustering Algorithm

In the field of Natural Language Processing (NLP), the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{k}$</tex>-means clustering algorithm has wide applications, such as one-dimensional data, which such as frequency-based word frequency statistics or time-series text analysis. But <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{k}$</tex>-means has problem such as long iteration time consuming, low computational efficiency and sensitivity to initial center point selection. To So, we propose an optimized one-dimensional <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{k}$</tex>-means clustering algorithm named Tshikei, which makes full use of the sequential and continuous characteristics of one-dimensional data in text features, introduce an efficient indexing mechanism to speed up the search process,and significantly reduces the time complexity of the algorithm on the premise of ensuring the accuracy of clustering. Theoretical analysis shows that for a dataset of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{k}$</tex> clustering centers, the new algorithm is able to converge to the optimal solution in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{O}(\mathbf{n})$</tex> initialization time and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{O}(\mathbf{k})$</tex> iteration time, and discuss its equivalence with the standard <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-means algorithm in mathematics, providing strong support for the text mining task in NLP and commercial application for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{k}$</tex>-means algorithm.