A hybrid linear text segmentation algorithm using hierarchical agglomerative clustering and discrete particle swarm optimization

Abstract

Linear text segmentation plays an important role in many natural language processing tasks. Many algorithms have been proposed and shown to improve the performance of linear text segmentation. However, the previous studies often suffer from either lower segmentation accuracy or higher computational complexity. Moreover, parameter setting is another critical problem in some algorithms. Although manual assignment is an approach to solve this problem, it may increase the user's burden, and the parameters provided may not always be suitable to reflect the real metadata of a text. In this paper, a hybrid algorithm, TSHAC-DPSO, is proposed to tackle these problems. A novel linear Text Segmentation algorithm based on Hierarchical Agglomerative Clustering (TSHAC) is proposed to rapidly generate a satisfactory solution without an auxiliary knowledge base, parameter setting, or user involvement; then an efficient evolutional algorithm, Discrete Particle Swarm Optimization (DPSO), is adopted to generate the global optimal solution by refining the solution created by TSHAC. TSHAC-DPSO fully utilizes the merits of both algorithms which not only improve the accuracy of linear text segmentation, but also make the execution more efficient and flexible. The experimental results show that TSHAC-DPSO provides comparable segmentation accuracy with several well-known linear text segmentation algorithms.