Adaptive encoding-based evolutionary approach for Chinese document clustering

Junxian Chen, Yue‐Jiao Gong, Wei–Neng Chen, Xiaolin XiaoComplex 2022 · DOI

Abstract

Document clustering has long been an important research direction in intelligent system. When being applied to process Chinese documents, new challenges were posted since it is infeasible to directly split the Chinese documents using the whitespace character. Moreover, many Chinese document clustering algorithms require prior knowledge of the cluster number, which is impractical to know in real-world applications. Considering these problems, we propose a general Chinese document clustering framework, where the main clustering task is fulfilled with an adaptive encoding-based evolutionary approach. Specifically, the adaptive encoding scheme is proposed to automatically learn the cluster number, and novel crossover and mutation operators are designed to fit this scheme. In addition, a single step of K-means is incorporated to conduct a joint global and local search, enhancing the overall exploitation ability. The experiments on benchmark datasets demonstrate the superiority of the proposed method in both the efficiency and the clustering precision.

Introduction

Document clustering is a fundamental task in natural language processing (NLP), aimed at grouping similar texts into coherent topics without prior labeling. However, Chinese document clustering presents unique challenges. Unlike English, Chinese lacks explicit word boundaries (whitespace), necessitating sophisticated segmentation. Furthermore, most traditional clustering methods, such as $K$-means, require the number of clusters ($K$) to be predefined—a significant limitation in real-world applications where the number of topics is unknown.

To address these issues, this paper introduces the Adaptive Encoding-based Evolutionary Approach (AEEA). This framework automates the determination of the optimal cluster count while maintaining high clustering precision through a hybrid search strategy.

Proposed Methodology

The AEEA framework follows a multi-stage pipeline designed to handle the complexities of Chinese text and the dynamic nature of cluster discovery. The process begins with preprocessing, where the 'Jieba' library is used for word segmentation. Documents are then transformed into mathematical vectors using the Vector Space Model (VSM) with TF-IDF weighting. To manage the high dimensionality typical of text data, Principal Component Analysis (PCA) is applied, retaining 90% of the variance.

Adaptive Encoding

The core of AEEA is its adaptive encoding scheme. Unlike standard Evolutionary Algorithms (EAs) that use fixed-length chromosomes, AEEA allows each individual in the population to represent a different number of cluster centers.

Adaptive encoding scheme for cluster centroids

This flexibility enables the algorithm to explore various values of $K$ simultaneously, allowing the population to converge on the "ground truth" $K$ without human intervention.

Subspace Swapping Crossover

To support this adaptive scheme, the authors developed a Subspace Swapping Crossover operator. Traditional crossover often fails when individuals have different lengths, leading to "cross-dimension learning errors" where cluster centers are moved in incorrect directions in the feature space.

Illustration of correct vs. wrong learning directions in crossover

AEEA solves this by identifying a spatial "hypersphere" in the feature space and swapping only the cluster centers within that region. This preserves geometric relationships and ensures the learning direction remains accurate, pulling centroids toward their logical counterparts in other individuals.

To balance global exploration with local exploitation, AEEA incorporates a Hybrid Search mechanism. After the evolutionary operators are applied, the algorithm performs a single iteration of $K$-means. This "fine-tuning" step pulls evolved centroids toward the actual centers of data point density, significantly improving convergence speed and accuracy without the overhead of a full $K$-means run.

Experimental Evaluation

The performance of AEEA was evaluated using five datasets from the Fudan corpus, ranging from 600 to 4,500 documents across 3 to 12 categories. AEEA demonstrated clear superiority over five competing algorithms, including standard $K$-means and advanced PSO-based hybrids.

Key results include:

  • High Precision: AEEA achieved an average F-score of 84.00%, outperforming the next best method (KSI-H-K) by over 6%.
  • Robustness: Performance remained stable even as dataset complexity and the number of categories increased, whereas competitors saw performance drops.
  • Statistical Significance: Wilcoxon rank-sum tests ($p < 0.05$) confirmed the significance of these improvements across all benchmarks.

Conclusion

AEEA provides a robust, automated solution for Chinese document clustering by effectively evolving the number of clusters and optimizing their positions. While highly effective with Cosine distance, future work could explore adapting the framework for non-spherical cluster shapes and improving its resilience to noisy data or outliers.

Summary updated

Abstract

Abstract Document clustering has long been an important research direction in intelligent system. When being applied to process Chinese documents, new challenges were posted since it is infeasible to directly split the Chinese documents using the whitespace character. Moreover, many Chinese document clustering algorithms require prior knowledge of the cluster number, which is impractical to know in real-world applications. Considering these problems, we propose a general Chinese document clustering framework, where the main clustering task is fulfilled with an adaptive encoding-based evolutionary approach. Specifically, the adaptive encoding scheme is proposed to automatically learn the cluster number, and novel crossover and mutation operators are designed to fit this scheme. In addition, a single step of K -means is incorporated to conduct a joint global and local search, enhancing the overall exploitation ability. The experiments on benchmark datasets demonstrate the superiority of the proposed method in both the efficiency and the clustering precision.
BibTeX
@inproceedings{chen2022adaptive,
  author = {Junxian Chen and Yue‐Jiao Gong and Wei–Neng Chen and Xiaolin Xiao},
  title = {{Adaptive encoding-based evolutionary approach for Chinese document clustering}},
  booktitle = {Complex},
  year = {2022},
  doi = {10.1007/s40747-022-00934-z},
}
Figure