Affiliations: [a] Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan | [b] Department of Computer Science and Information Engineering, Chung Hua University, Hsinchu, Taiwan | [c] Department of Multimedia and Game Science, Yu Da University of Science and Technology, Miaoli County, Taiwan
Correspondence:
[*]
Corresponding author: Judy C.R. Tseng, Department of Computer Science and Information Engineering, Chung Hua University, Hsinchu, Taiwan. Tel.: +886 989 090 565; Fax: +886 3 518 6417; E-mail: [email protected].
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.
Keywords: Linear text segmentation, hierarchical agglomerative clustering, discrete particle swarm optimization, natural language processing
