FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

(1)

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

CLUSTERING

LAITH MOHAMMAD QASIM ABUALIGAH

UNIVERSITI SAINS MALAYSIA

2018

(2)

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

CLUSTERING

by

LAITH MOHAMMAD QASIM ABUALIGAH

Thesis submitted in fulfilment of the requirements for the degree of

Doctor of Philosphy

March 2018

(3)

ACKNOWLEDGEMENT

Beginning this Ph.D. thesis has been a life-changing experience for me and I would not have achieved it without the guidance and support of many people. I must declare many external donations from individuals who extended a helping hand throughout this study.

I am thankful to Allah SWT for giving me strength to finish this study. I am also grateful to my supervisor, Professor Dr. Ahamad Tajudin Khader from the School of Computer Sciences at Universiti Sains Malaysia, for his wise counsel, helpful advice, connected support and supervision throughout the duration of this study. I am also thankful to my co-supervisor, Dr. Mohammed Azmi Al-Betar from the Department of Information Technology, Al-Huson University College, Al-Balqa Applied University, for his assistance. I am also thankful to Dr. Essam Said Hanandeh from the Department of Computer Information System, Zarqa University, for his assistance.

My family deserves special thanks. Words cannot express how grateful I am to my father, mother, and brothers for all of the sacrifices that they have done for me. Finally, I thank all of my friends who encouraged me throughout the duration of this study.

(4)

REFERENCES ... ... ..

205 LISTOFPUBLICATIONS

(11)

LIST OF TABLES

Page

Table 3.1 Overview of the feature selection algorithms 73

Table 3.2 Overview of the text clustering algorithms 74

Table 3.2 (Cont...) Overview of the text clustering algorithms 75

Table 4.1 Terms frequency. 84

Table 4.2 Terms weight using TF-IDF. 85

Table 4.3 Terms weight using LFW. 86

Table 4.4 The text feature selection problem and optimization terms in

the genetic algorithm context. 89

the harmony search algorithm context. 91

the particle swarm optimization algorithm context. 95 Table 4.7 The text document clustering and optimization term in the krill

herd solutions context 109

Table 4.8 The parameters values for different variant of text feature

selection algorithms. 128

Table 4.9 The best configuration parameters of the TD clustering

algorithms. 129

Table 5.1 Description of document datasets that used in this research. 137 Table 5.2 Summary of experimental methods using k-mean clustering

algorithm 138

Table 5.3 Comparing the performance of the k-mean text clustering

algorithms in terms of the purity and entropy measures. 140 Table 5.4 Comparing the performance of the k-mean text clustering

algorithms in terms of the precision and recall measures. 142 Table 5.5 Comparing the performance of the k-mean text clustering

algorithms in terms of the accuracy and F-measure measures. 143

(12)

Table 5.6 The number of the best results obtained by the proposed

methods in terms of the evaluation measures over all datasets. 145 Table 5.7 The number of the best results obtained by the feature selection

algorithms (GA, HS, and PSO) in terms of the evaluation

measures over all datasets. 145

Table 5.8 Summary of the experimental using DDR to adjust the

threshold value. 148

Table 5.9 Dimension reduction ratio when threshold = 25 using DDR. 148 Table 5.10 The average ranking of k-mean clustering algorithms based on

the F-measure. i.e., lower rank value is the best method. 151 Table 5.11 Convergence scenarios of the basic krill herd algorithm (BKHA). 155 Table 5.12 The results of BKHA convergence scenarios (Scenario.(1)

through Scenario.(5)) 156

Table 5.13 The results of BKHA convergence scenarios (Scenario.(6)

Table 5.16 The versions of the proposed basic krill herd algorithms

(BKHAs) for text document clustering problem (TDCP). 160 Table 5.17 Comparing the performance of the text document clustering

algorithms along with original datasets and proposed datasets

using accuracy measure values. 162

Table 5.18 Comparing the performance of the text document clustering algorithms along with original datasets and proposed datasets

using purity measure values. 163

using entropy measure values. 163

using precision measure values. 164

using recall measure values. 164

(13)

using F-measure values. 165

Table 5.23 The best results obtained by the basic clustering algorithms in

terms of the evaluation measures over all datasets. 167 Table 5.24 Versions of the proposed modified KH algorithm. 168 Table 5.25 Comparing the performance of the text document clustering

algorithms using the average accuracy measure values. 169 Table 5.26 Comparing the performance of the text document clustering

algorithms using the average purity measure values. 169 Table 5.27 Comparing the performance of the text document clustering

algorithms using the average entropy measure values. 169 Table 5.28 Comparing the performance of the text document clustering

algorithms using the average precision measure values. 171 Table 5.29 Comparing the performance of the text document clustering

algorithms using the average recall measure values. 171 Table 5.30 Comparing the performance of the text document clustering

algorithms using the average F-measure measure values and its

ranking. 172

Table 5.31 The average ranking of the modified clustering algorithms

based on the F-measure. i.e., lower rank value is the best method. 172 Table 5.32 The best results obtained by the modified clustering algorithms

in terms of the evaluation measures over all datasets. 174

Table 5.33 Versions of the proposed hybrid KH algorithm. 175

Table 5.34 Comparing the performance of the hybrid text document

clustering algorithms using the average accuracy measure values. 176 Table 5.35 Comparing the performance of the hybrid text document

clustering algorithms using the average purity measure values. 177 Table 5.36 Comparing the performance of the hybrid text document

clustering algorithms using the average entropy measure values. 178 Table 5.37 Comparing the performance of the hybrid text document

clustering algorithms using the average precision measure values. 178 Table 5.38 Comparing the performance of the hybrid text document

clustering algorithms using the average recall measure values. 179

(14)

Table 5.39 Comparing the performance of the hybrid text document

clustering algorithms using the average F-measure values. 179 Table 5.40 The average ranking of the hybrid clustering algorithms based

on the F-measure. i.e., lower rank value is the best method. 181 Table 5.41 The best results obtained by the hybrid clustering algorithms in

terms of the evaluation measures over all datasets. 181 Table 5.42 Comparing the performance of the multi-objective hybrid text

document clustering algorithms using the average accuracy

measure values. 185

Table 5.43 Comparing the performance of the multi-objective hybrid text document clustering algorithms using the average purity

measure values. 185

Table 5.44 Comparing the performance of the multi-objective hybrid text document clustering algorithms using the average entropy

measure values. 186

Table 5.45 Comparing the performance of the multi-objective hybrid text document clustering algorithms using the average precision

measure values. 186

Table 5.46 Comparing the performance of the multi-objective hybrid text document clustering algorithms using the average recall

measure values. 186

Table 5.47 Comparing the performance of the multi-objective text document clustering algorithms using the average F-measure

values and its ranking. 187

Table 5.48 The average ranking of the multi-objective clustering algorithm based on the F-measure. i.e., lower rank value is the best method. 188 Table 5.49 The best results obtained by the multi-objective clustering

algorithm in terms of the evaluation measures over all datasets. 188 Table 5.50 Comparison results between the krill herd-based methods

according to F-measure evaluation criteria. 191

Table 5.50 (Cont...) Comparison results between the krill herd-based

methods according to F-measure evaluation criteria. 192 Table 5.51 The average ranking of the krill-based algorithms based on the

average F-measure. i.e., lower rank value is the best method. 194 Table 5.52 Significance tests of the basic KH algorithms on the original

datasets and the proposed datasets usingt-test withα<0.05.

Highlight (bold) denote that result is significantly different. 195

(15)

Table 5.53 Significance tests of the basic KH algorithms and the modified KH algorithm usingt-test withα<0.05. Highlight (bold) denote

that result is significantly different. 195

Table 5.54 Significance tests of the modified KH algorithms and the hybrid KH algorithm usingt-test withα<0.05. Highlight (bold) denote

that result is significantly different. 196

Table 5.55 Significance tests of the hybrid KH algorithms and the

multi-objective hybrid KH algorithm usingt-test withα<0.05.

Highlight (bold) denote that result is significantly different. 196

Table 5.56 Key to the comparator methods. 197

Table 5.57 Description of text document datasets that used by the

comparative methods. 198

Table 5.58 A comparison of the results obtained by MHKHA and

best-published results. 199

Table 5.58 (Cont...) A comparison of the results obtained by MHKHA and

best-published results. 200

(16)

LIST OF FIGURES

Page

Figure 1.1 Research methodology. 10

Figure 2.1 A flowchart of basic krill herd algorithm (Bolaji, Al-Betar,

Awadallah, Khader, & Abualigah, 2016). 15

Figure 2.2 A schematic represents the sensing domain around a KI (Bolaji

et al., 2016). 19

Figure 3.1 An example of the clustering search engine results by Yippy. 29

Figure 4.1 The research methodology stages 78

Figure 4.2 Sigmoid function used in binary PSO algorithm. 98

Figure 4.3 Representation of the Text Clustering Solution. 107 Figure 4.4 The flowchart of adapting basic KH algorithm to text document

clustering problem. 111

Figure 4.5 The flowchart of the modified krill herd algorithm. 115 Figure 4.6 The flowchart of the hybrid krill herd algorithm. 119 Figure 4.7 The flowchart of the multi-objective hybrid krill herd algorithm. 123

Figure 5.1 The general design of the experiments in the first stage. 134 Figure 5.2 The general design of the experiments in the second stage. 135

Figure 5.3 A snapshot of the dataset file 136

Figure 5.4 The experimental of the proposed methods in the first stage. 138 Figure 5.5 The number of features in each dataset using three feature

selection algorithms and dimension reduction techniques. 146

Figure 5.5(a) Dataset 1 146

Figure 5.5(b) Dataset 2 146

Figure 5.5(c) Dataset 3 146

Figure 5.5(d) Dataset 4 146

(17)

Figure 5.5(e) Dataset 5 146

Figure 5.5(f) Dataset 6 146

Figure 5.5(g) Dataset 7 146

Figure 5.5(h) Legend 146

Figure 5.6 Average computation time of the k-mean iteration (in second). 149 Figure 5.7 The average similarity document centroid (ASDC) values of the

basic text clustering algorithms for 20 runs plotted against 1000

iterations on seven text datasets. 166

Figure 5.8 The average similarity document centroid (ASDC) values of the text clustering using modified KH algorithms for 20 runs

plotted against 1000 iterations on seven text datasets. 173

Figure 5.9 The average similarity document centroid (ASDC) values of the text clustering using hybrid KH algorithms for 20 runs plotted

against 1000 iterations on seven text datasets. 183

(18)

Figure 5.10 The average similarity document centroid (ASDC) values of the text clustering using multi-objective hybrid KH algorithm for

20 runs plotted against 1000 iterations on seven text datasets. 189

(19)

LIST OF ABBREVIATIONS

ABC Ant Colony Optimization

ASDC Average Similarity of Documents Centroid BCO Bee Colony Optimization

BKHA Basic Krill Herd Algorithm

BPSO Binary Particle Swam Optimization

CS Cuckoo Search

DDF Detailed Document Frequency DDR Detailed Dimension Reduction

DF Document Frequency

DFTF Document Frequency with Term Frequency DR Dimension Reduction

DTF Detailed Term Frequency FE Feature Extraction FF Fitness Function FS Feature Selection GA Genetic Algorithm

HKHA Hybrid Krill Herd Algorithm

HS Harmony Search

IDF Inverse Document Frequency

KH Krill Herd

KHA Krill Herd Algorithm KHM Krill Herd Memory KI Krill Individual

LFW Length Feature Weight

MKHA Modified Krill Herd Algorithm NLP Natural Language Processing NP Non-deterministic Polynomial-time PSO Particle Swam Optimization

(20)

TC Text Clustering

TD Text Document

TDCP Text document clustering problem

TF Term Frequency

TFSP Text feature selection problem VSM Vector Space Model

WTDC Web Text Documents Clustering

(21)

PEMILIHAN FITUR DAN ALGORITMA KRILL HERD LANJUTAN UNTUK PENGKLUSTERAN DOKUMEN TEKS

ABSTRAK

Pengklusteran dokumen teks adalah satu tren baru dalam galian teks di mana dokumen- dokumen diasingkan kepada beberapa kluster yang koheren, di mana dokumen-dokumen dalam kluster yang sama adalah serupa. Dalam kajian ini, satu kaedah baru untuk me- nyelesaikan masalah pengklusteran dokumen teks dijalankan dalam dua peringkat: (i) Satu kaedah pemilihan fitur menggunakan algoritma optima kumpulan partikel dengan satu skima pemberat yang baru dan satu teknik pengurangan dimensi yang lengkap dicadangkan untuk mendapatkan satu subset baru fitur-fitur yang lebih bermaklumat dengan ruang berdimensi rendah. Subset baru ini digunakan untuk memperbaiki prestasi algoritma pengklusteran teks dalam peringkat berikutnya dan ini mengurangan masa pengiraannya. Algoritma pengklusteran min-k digunakan untuk menilai keberkesanan subset-subset yang diperolehi. (ii) Empat algoritma krill herd iaitu (a) algoritma krill herd asas, (b) algoritma krill herd yang telah diubahsuai, (c) algoritma krill herd hibrid, dan (d) algoritma hibrid pelbagai objektif krill herd, disarankan untuk menyelesaik- an masalah pengklusteran teks; algoritma ini adalah penambahbaikan lanjutan kepada versi-versi yang terdahulu. Untuk proses penilaian, tujuh set data teks penanda aras digunakan dengan pencirian dan kesukaran yang berbeza. Keputusan menunjukkan bahawa kaedah yang dicadangkan dan algoritma yang diperolehi mencapai keputusan terbaik berbanding dengan kaedah-kaedah lain yang diutarakan dalam literatur.

(22)

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT CLUSTERING

ABSTRACT

Text document (TD) clustering is a new trend in text mining in which the TDs are separated into several coherent clusters, where documents in the same cluster are similar. In this study, a new method for solving the TD clustering problem worked in the following two stages: (i) A new feature selection method using particle swarm optimization algorithm with a novel weighting scheme and a detailed dimension reduction technique are proposed to obtain a new subset of more informative features with low-dimensional space. This new subset is used to improve the performance of the text clustering (TC) algorithm in the subsequent stage and reduce its computation time. The k-mean clustering algorithm is used to evaluate the effectiveness of the obtained subsets. (ii) Four krill herd algorithms (KHAs), namely, (a) basic KHA, (b) modified KHA, (c) hybrid KHA, and (d) multi-objective hybrid KHA, are proposed to solve the TC problem; these algorithms are incremental improvements of the preceding versions. For the evaluation process, seven benchmark text datasets are used with different characterizations and complexities. Results show that the proposed methods and algorithms obtained the best results in comparison with the other comparative methods published in the literature.

(23)

CHAPTER 1 INTRODUCTION

1.1 Background

With the growth of the amount of text information on Internet web pages and modern applications, in general, interest in the text analysis area has increased to facilitate the processing of a large amount of unorganized text information (Sadeghian &

Nezamabadi-pour, 2015).

Text clustering (TC) is an efficient unsupervised learning technique used to deal with numerous text documents (TDs) without any foreknowledge of the class label of the document (Prakash, Hanumanthappa, & Mamatha, 2014). This technique partitions a set of large TDs into meaningful and coherent clusters by collating relevant (similar) documents in the same cluster based on its intrinsic characteristics (Cobos et al., 2014).

The same clusters (groups) contain relevant and similar TDs. Meanwhile, different clusters contain irrelevant and dissimilar TDs (L. M. Abualigah, Khader, & Al-Betar, 2016a).

In the modern era, clustering is an important activity because of the size of text information on Internet web pages (Oikonomakou & Vazirgiannis, 2010). Clustering is used to determine relevant TDs and facilitate TD display by groups that share the same pattern and contents (Cobos et al., 2014). The TC technique is successfully utilized in many research areas to facilitate the text analysis process, such as data mining, digital forensics analysis, and information retrieval (Forsati, Mahdavi, Shamsfard, &

(24)

Meybodi, 2013).

Vector space model (VSM) is the most common model used in TC to represent each document; in this model, each term in the TDs is a feature (word) for document representation (Salton, Wong, & Yang, 1975; Yuan, Ouyang, & Xiong, 2013). The TDs are represented by a multi-dimensional space, in which the position value of each dimension corresponds to a term frequency (TF) value. The text features generated from different text terms, even in a small document, would be represented by hundreds and/or thousands of text features. Thus, TDs will have high-dimensional informative and uninformative features (i.e., irrelevant, redundant, unevenly distributed, and noisy features). These uninformative features can be eliminated using the feature selection (FS) technique (Bharti & Singh, 2016b; L. Zheng, Diao, & Shen, 2015).

FS techniques are nondeterministic polynomial time-hard optimization methods used to determine the optimal subset of informative text features and improve the performance of the TC method while maintaining the necessary text information (Bharti

& Singh, 2016b; K.-C. Lin, Zhang, Huang, Hung, & Yen, 2016). Typically, these techniques are performed even without any foreknowledge of the class label of the document. Conventionally, these techniques are divided into three main types, namely, FS based on document frequency (DF), FS based on TF, and hybrid feature technique based on DF and TF (Y. Wang, Liu, Feng, & Zhu, 2015). Several text-based stud- ies rely on FS methods, such as TC (L. M. Abualigah, Khader, & Al-Betar, 2016b), text classification (Z. Zheng, Wu, & Srihari, 2004), and data mining (K.-C. Lin et al., 2016). Recently, metaheuristic algorithms have been successfully used in the area of text mining to solve the text document clustering problems (TDCPs) and text feature

(25)

selection problems (TFSPs) (BoussaïD, Lepagnot, & Siarry, 2013).

The application of FS techniques produces a new subset with numerous informative text features. However, the dimensionality is still high because all dimensions remain even after removing the uninformative features. The dimensional space of this subset must be reduced further to facilitate the TC process (Lu, Liang, Ye, & Cao, 2015). High-dimensional feature space has become a significant challenge to the TC domain because it increases the computational time while decreases the efficiency of TC techniques (van der MLJP & van den HH, 2009). Thus, a dimension reduction (DR) technique is necessary to produce a new low-dimensional subset of useful features (Diao, 2014; Esmin, Coelho, & Matwin, 2015; Sorzano, Vargas, & Montano, 2014a). This technique will reduce the computation time and improve the performance of the TC algorithm. The DR technique should eliminate useless text features;

eliminate unnecessary, redundant, and noisy text features; preserve intrinsic information; and significantly reduce the dimension of the text feature space (Bharti & Singh, 2014b; Raymer, Punch, Goodman, Kuhn, & Jain, 2000).

1.2 Motivation and Problem Statement

Recently, unorganized TDs on Internet web pages and modern applications have increased exponentially, and the number of Internet users in the world has exceeded three billion¹. These users face difficulties in obtaining the information that they need easily and neatly (Bharti & Singh, 2014b; U˘guz, 2011). The process of managing such a large TD is called TD clustering technique, which transforms a set of large unorganized TDs into coherent and similar groups, that is, clusters, which facilitate user

1https://en.wikipedia.org/wiki/List_of_countries_by_number_of_Internet_users

(26)

browsing and searching for information. From the literature on TC techniques, four main problems are identified and explained as follows:

First, TDs usually contain informative and uninformative text features. Uninforma- tive features can confuse and mislead the TD clustering algorithm, thereby reducing the performance of the clustering algorithm (Bharti & Singh, 2014b, 2015b). Therefore, identifying and removing these uninformative text features can improve the performance of the clustering algorithm and reduce the computation time. The main drawback of these methods is focusing only on selecting a new subset of text features that rely on the existing weighting scheme (score) (Bharti & Singh, 2016b). The current weighting scheme has certain weaknesses in evaluating the features by computing the weight score for all features equally using one main factor (i.e., term frequency). Thus, the distinction between informative and uninformative text features over the document is insufficient (Ahmad, Abu Bakar, & Yaakub, 2015; Bharti & Singh, 2016b; Cobos, León, & Mendoza, 2010a; Moayedikia, Jensen, Wiil, & Forsati, 2015). The weighted score should be more accurate to facilitate the process of the text FS technique, where it plays the main role in the FS procedure by distinguishing between TD features by providing a high score to the more informative features.

Second, the high-dimensional feature space is one of the most critical weaknesses of TDs because it influences the process of TD clustering techniques by increasing the execution time and decreasing the performance of the TD clustering algorithm (Bharti & Singh, 2014b; Nebu & Joseph, 2016). The high-dimensional feature space contains the necessary (useful) and unnecessary (useless) text features. Thus, the DR technique reduces the dimensional feature space by pruning useless text features to

(27)

improve the performance of the clustering algorithm. One of the possible ways to solve the high-dimensional feature space is the DF method. This method deals with the reduction process with fixed roles (DF of the feature) in making the decision to prune useless text features (Esmin et al., 2015; Tang, Shepherd, Milios, & Heywood, 2005; Yao, Coquery, & Lê Cao, 2012a). The fundamental premise of the DF method is impractical because the frequently occurring features are considered more important in the documents than the infrequently occurring features (Bharti & Singh, 2015b).

Third, the main advantage of the TC algorithm is its effectiveness in guarantee- ing access to the accurate clusters. Over the past few years, a large proportion of researchers in the TC domain applied metaheuristic algorithms to solve the TDCPs.

However, a major drawback of these algorithms is that it provides a good exploration of the search space at the cost of exploitation (Bharti & Singh, 2016a). Other problems are related to unsatisfactory outcomes, such as inaccurate clusters, and the behavior of the algorithms that were selected is inappropriate for the problem of the TC instances (Bharti & Singh, 2015a; Binu, 2015; Forsati, Keikha, & Shamsfard, 2015; G.-G. Wang, Gandomi, Alavi, & Deb, 2015). All available TC techniques based on metaheuristic algorithms still face these problems. Solving the TC problem using metaheuristic algorithms still need more in-depth investigation for several important reasons (Y. Guo, Li,

& Shao, 2015; Mohammed, Yusof, & Husni, 2015; J. Wang, Yuan, & Cheng, 2015).

However, these reasons can be justified by the “no free lunch” theorem (Wolpert, 2013;

Wolpert & Macready, 1997).

Fourth, the core effectiveness of the TD clustering techniques relies on the similarity and distance functions of the TC algorithm. These functions are used in making the

(28)

decision to partition the document into an appropriate cluster based on the similarity or distance value; these decisions affect the performance of the TD clustering algorithm (Rao, Ramakrishna, & Babu, 2016). Similarity and distance measurements are standard function criteria used in the TD clustering domain as an objective function. Nev- ertheless, the results of these measurements are different and lead to certain challenges because of the variance between the values of similarity and distance measures for the same document (L. M. Abualigah, Khader, & Al-Betar, 2016a; Forsati et al., 2013).

Determining the appropriate objective function to deal with the large TDs is difficult (Mukhopadhyay, Maulik, & Bandyopadhyay, 2015; Mukhopadhyay, Maulik, Bandy- opadhyay, & Coello, 2014). Multi-objective functions (multiple-criteria decision making) are currently used in several domains as an alternative technique to yield better results (George & Parthiban, 2015; Saha, Ekbal, Alok, & Spandana, 2014). How- ever, for the TD clustering technique, multiple-criteria decision making is relatively unknown.

1.3 Research Objectives

The overall aim of this study is to develop an effective TD clustering method. The main objective is to show that the improved method can outperform the other comparative methods. This research has the following objectives:

• to find the best features:

– to enhance the weight score of the terms for the text FS technique in order to improve the TD clustering;

(29)

– to improve the text FS technique for finding a new subset of more informative features to improve the TD clustering;

– to reduce the dimension of the feature space in the form of a low-dimensional subset of useful features to improve the TD clustering;

• to improve the text document clustering using krill herd algorithm:

– to increase the effectiveness of the TD clustering technique and to reduce its errors;

– to improve the global search ability and its speed of convergence;

– to enhance the quality of initial solutions obtained by the local search strategy;

– to increase the likelihood of obtaining an accurate decision (similarity value) between the document and clusters centroids in the k-mean clustering algorithm.

1.4 Contributions

After the research objectives are achieved, this study will have the following main contributions:

1. Introduced a new weighting scheme to provide a significant influence score for the informative text features within the same document. This scheme focuses on assigning a favorable term weight to facilitate the text FS technique and distin- guishes among the features of the clusters by giving a high weight to essential features in the same document.

(30)

2. Adapted metaheuristic optimization algorithms (i.e., genetic algorithm (GA), harmony search (HS), and particle swarm optimization (PSO)) to find the best features at the level of each document using a new FS method.

3. Introduced a new detailed DR technique to reduce the dimensional space of text features based on the detailed term frequency (DTF) and detailed document frequency (DDF) of each feature compatible with the size of its effect on the document. The DDF of each feature at the level of all documents is compatible with the size of its effect on the documents in partnership with its DTF value.

4. Adapted the basic krill herd algorithm (BKHA) and tuning its parameters for the text document clustering problem.

5. The modified krill herd algorithm (MKHA) to improve the global search ability.

These modifications occur during ordering of the basic KH operators where the crossover and mutation processes are invoked after updating the positions of the krill herd algorithm (KHA).

6. The hybrid krill herd algorithm with the k-mean algorithm (HKHA) as a new operator, which plays a basic role in the MKHA to improve the local search ability. Hybridization is used to enhance the capacity of the KHA for finding locally optimal solutions by taking the refining power of the k-means clustering algorithm.

7. Introduced a multi-objective function based on the local best concept for the k- mean algorithm to enhance the capacity of the KHA by achieving an accurate local search, called multi-objective hybrid krill herd algorithm (MHKHA).

(31)

1.5 Research Scope

This study covers the main TC preprocessing steps (i.e., text FS and DR techniques) and the metaheuristic algorithms (i.e., different versions of the proposed KHA) to deal with the TDCP. The methods proposed in this study are applied to a large amount of TDs as electronic pages (i.e., newsgroup documents appearing on newswires, In- ternet web pages, and hospital information), modern applications (technical reports and university data), and biomedical sciences (large biomedical datasets). Note, all the datasets used in this research have been written in English language. These TDs (datasets) are characterized by high-dimensional informative and uninformative text features (Bharti & Singh, 2014b, 2015b; L. Zheng et al., 2015). All of the proposed methods need the number of clusters as input parameter K. Determining the correct number of clusters for the given TD datasets is an important issue because the number of document clusters is an essential parameter in TC problems. Standard TD datasets with different sizes (i.e., number of documents, number of terms, and number of clusters), constraints, and complexities are used in the TC technique to evaluate the proposed methods.

1.6 Research Methodology

This section briefly discusses the stages of the research methodology, which are applied to achieve the research objectives for improving the TD clustering technique, as shown in Figure 1.1. The detailed description is provided in Chapter 4.

The first stage is modeling and adapting GA, HS, and PSO to solve the text FS problem (TFSP) with the novel weighting scheme and detailed DR technique. This

(32)

Figure 1.1: Research methodology.

stage facilitates the TC task to deal with a low-dimensional subset of informative text features, which reduce the computation time and improve the performance of the TD clustering algorithm.

The second stage is adapting the basic KH algorithm (BKHA) and tuning its parameters to solve the text DC problem (TDCP). Then, three versions of the BKHAs are modified (MKHAs) to improve the global (exploration) search ability. The three versions of the HKHA with the k-mean algorithm (MKHAs) are used to increase the performance of the TC technique by improving the local (exploitation) search ability.

These hybrid versions used the results of the k-mean algorithm as the initial solutions in KHA to ensure balance between local exploitation and global exploration. Finally, a multi-objective function is applied to obtain an accurate TC technique by combining two standard measures (i.e., cosine similarity and Euclidean distance measurements).

(33)

The multi-objective function is the primary factor used to obtain an effective clustering method by deriving an accurate similarity value between the document and the cluster centroid.

1.7 Thesis Structure

The rest of this thesis organized as follows:

Chapter 2 (Krill Herd Algorithm): This chapter discusses the principles of the KHA. The analogy between the clustering technique and the optimization terms is provided. The steps of the KHA are described in detail.

Chapter 3(Literature Review): This chapter provides an overview of the text preprocessing steps, TFSPs, and TDCPs with particular attention to TDs. This chapter also examines several methods used to deal with TFSP and TDCP. This chapter also presents a review of KHA in the areas of applications, modifications, and hybridiza- tions across many fields.

Chapter 4(Proposed Methodology): This chapter illustrates the modeling of TFSP and TDCP. This study also includes a comprehensive description of the adapted research methodology, including different weight schemes, metaheuristic algorithms for text FS, DR techniques, and KHAs for TD clustering, and the sequence of the procedures conducted.

Chapter 5(Experimental Results): This chapter shows the experiments and results of all the proposed methods and presents the comparisons of each method with the others.

(34)

Chapter 6(Conclusion and Future Work): This chapter provides the research conclusion and possible future works.

(35)

CHAPTER 2 KRILL HERD ALGORITHM

2.1 Introduction

Krill herd (KH) algorithm has a unique behavior to solve the text clustering problem.

This algorithm was introduced by Gandomi and Alavi in the year 2012 to solve global optimization functions (Gandomi & Alavi, 2012). This section presents the modeling of the basic-krill herd algorithm (KHA) for the TDCP (L. M. Abualigah, Khader, Al- Betar, & Awadallah, 2016).

2.2 Krill Herd Algorithm

Krill herd (KH) is a swarm intelligence (SI) search algorithm based on the herding behavior of krill individuals (KIs). It is a population-based approach consisting of a huge number of krill, where each krill individual (KI) moves through a multi-dimensional space to search for close food and high-density herd (swarm). In KH as optimization algorithm, positions of KIs are considered as various design variables and the distance of the KI from the food is the objective function (Gandomi & Alavi, 2012; Mandal, Roy, & Mandal, 2014). The KH algorithm is considered in three categories: (1) Evo- lutionary algorithms (2) Swarm intelligence (3) Bacterial foraging algorithm (Bolaji et al., 2016).

(36)

2.3 Why the KHA has been Chosen for Solving the TDCP

The KH is a suitable algorithm for the TC technique according to: (i) the similarities between the behavior of the KHA and the behavior of the TD clustering technique, (ii) KH algorithm obtained better results in solving many problems in comparison with others common algorithms published in the literature.

The compatibility between KHA and TC involves searching for the closest food (closest centroid) and high density groups (similar groups) (Bolaji et al., 2016). Den- sity is one of the main factors that influence the success of all the algorithms used to achieve coherence and similar groups. If documents in the same cluster are relevant, then density is high, and vice versa. If the KIs are close to the food, then density is high, and vice versa. Thus, the behavior of KIs is exactly the same as that of the TD clustering technique (both of them are a swarm).

With regard to the KHA, each KI (document) moves toward the best solution by searching for the herd (group) with high density (similar groups) and the closest food (closest centroid). These factors are used as objectives to lead each krill to an optimal herd around the food. With regard to the TC, each document moves toward the best solution by searching for the similar cluster centroid and the cluster with a high density.

Moreover, these factors are used as objectives to lead each document to an optimal cluster around the closest centroid. The relationship between the behavior of KHA and the behavior of TD clustering is considered a strong feature in applying KHA to solve the TDCP.

(37)

2.4 Krill Herd Algorithm: Procedures

Due to the nature of this research, predation disperses KIs, leads to a decrease of the average krill density and distances of the KH from the food location. This process is the initialization phase in the KH algorithm. In the natural system, the objective function of each document is supposed to be the distance or similarity from the cluster centroid. The fitness function of each candidate solution is the total distance or similarity between all documents with clusters centroid. The KH algorithm has three main motion calculation to update individual positions; then it applies the KH operators, which is inspired by the evolutionary algorithm. The procedures sequence of the basic KH algorithm is shown in Figure 2.1.

Figure 2.1: A flowchart of basic krill herd algorithm (Bolaji et al., 2016).

2.4.1 Mathematical Concept of Krill Herd Algorithm

The KH algorithm has three main steps to update the time-dependent position of each KI as follows:

(38)

• Movement induced by the presence of other KIs: only individual neighbors in the visual field that affects the KI moving.

• Foraging activity: the KIs search for food resources.

• Random diffusion: the net movement of each KI based on density regions (Gan- domi & Alavi, 2012).

Thei_thindividual position is updated by the following Lagrangian model using Eq.

(2.1).

dx_i

dt =N_i+F_i+D_i, (2.1)

where for the krill i, N_i is the motion effect of the i_th individual from other KIs.

This value is estimated from the local swarm density, a target swarm density, a repulsive swarm density, and the target direction which is effected by the best KI.F_i is the foraging motion for thei_th KI. This value estimated from the food attractiveness, food location, the foraging speed, the last foraging action or movement and the best fitness of thei_th krill so far. D_iis the physical diffusion for thei_th KI, where this value estimated from two factors: the maximum diffusion speed of the KIs and random direction (Gandomi, Talatahari, Tadbiri, & Alavi, 2013).

2.4.1(a) Movement Induced by other Krill Individuals

Movement induced is an illusion of visual perception in which a moving individual appears to move differently because of neighbors moving nearby in the visual field.

(39)

Theoretically, individuals try to keep the high density (Bolaji et al., 2016; G. Wang et al., 2014). The direction of movement induced is defined by Eq. (2.2).

N_i^new=N^maxα_i+ω_nN_i^old, (2.2)

where for krill i,N^max is the parameter for tuning the movement induced by other individuals, it is determined experimentally (see Table 5.11). α_i is estimated from the local swarm density by Eq. (2.3),ω_nis the inertia weight of the movement induced by other individuals’ in range [0, 1], andN_i^old is the last change or movement produced.

α_i=α_i^local+α_i^target, (2.3)

where, theα_i^local is the effect of the neighbors ini_th individual movement,α_i^target is the target direction effected by the j_thKI. The effect of individual neighbors can be considered as an attractive or repulsive tendency between the KIs for a local search while the normalized values can be positive or negative (Bolaji et al., 2016; Gandomi

& Alavi, 2012). Theα_i^local is calculated by Eq. (2.4).

α_i^local=

n

∑

j=1

Kb_i,jxb_i,_j, (2.4)

where, Kb_i,_j is the normalized value of the objective function vector for thei_th KI.

bx_i,_jis the normalized value of the related positions for thei_thKI. TheKb_i,j is calculated

(40)

by Eq. (2.5):

Kb_i,_j= K_i−K_j

K^worst−K^best, (2.5)

where, K_i is the objective function of i_th KI, K_j is the objective function of j_th neighbor (j=1,2, ...,n). nis the number of all KIs,K^best andK^worst are the best and worst objective function values ofi_th individual. Thexb_i,_jis calculated by Eq. (2.6).

bx_i,j= x_j−x_i x_j−x_i

+ε

, (2.6)

where, x_iis the current position,x_jis the position of j_th neighbor,||x_j−x_i||is the vector normalization, it is used for calculating the neighbors of thei_thKI by Eq. (2.7), ε is a small positive number to avoid singularities (Jensi & Jiji, 2016; Mandal et al., 2014). The sensing distance is calculated by Eq. (2.7).

de_i= 1 5n

n j=1

∑

x_i−x_j

, (2.7)

where,de_iis the sensing distance for the krilli. Note, if the distance value between two KIs is less than the current value, they are neighbors. Figure 2.2 illustrates the movement of the KIs and their neighbors.

The known target vector of each KI is the highest objective function. The effect of the best fitness on the j_th individual is calculated by Eq. (2.8). This procedure allows

(41)

Sensing Distance

Neighbor 3

Neighbor 1

Neighbor 2

Figure 2.2: A schematic represents the sensing domain around a KI (Bolaji et al., 2016).

the solution to move towards the current best solution and is calculated by Eq. (2.8).

α_i^target =C^bestKb_i,bestbx_i,best, (2.8)

where,

C^best =2

rand+ I I_max

, (2.9)

C^best is the coefficient of individuals,Kb_i,best is the best objective function of thei_th KI,bx_i,best is the best position of thei_thKI,randis a random number between [0, 1] for improving the local exploration;Iis the current iteration number;I_maxis the maximum number of iterations (Gandomi & Alavi, 2012).

(42)

2.4.1(b) Foraging Motion:

The foraging motion of KIs is estimated by two effects, namely, current food and old food location (L. M. Abualigah, Khader, Al-Betar, & Awadallah, 2016; Bolaji et al., 2016; Mandal et al., 2014). Food area or location is defined to attract KIs to the global optima possibly. The foraging motion fori_th individual is expressed by Eq. (2.10).

F_i=V_fβ_i+ω_fF_i^old, (2.10)

where, V_f is the parameter for tuning the foraging speed, it is determined experimentally (see Table 5.11), β_i is the food location of the i_th KI by Eq. (2.11), ω_f is the inertia weight of the foraging speed in range [0, 1], and F_i^old is the last foraging motion.

βi=β_i^{f ood}+β_i^best, (2.11)

where, β_i^{f ood} is the food attractiveness of thei_th KI, it is calculated by Eq. (2.12).

β_i^best is the best objective function of thei_th KI.

β_i^{f ood} =C^{f ood}Kb_{i,f ood}bx_i,_{f ood}, (2.12)

where,

(43)

C^{f ood} =2

1− I I_max

, (2.13)

Kb_{i,f ood} is the normalized value of the objective function of the i_th centroid and bx_i,_{f ood}is the normalized value of thei_thcentroid position. The center of the individual’s food for each iteration is calculated by Eq. (2.14).

x^{f ood}= ∑ⁿ_i=1_K¹_ix_i

∑ⁿ_j=1_K¹_j

, (2.14)

where, nis the number of the KIs,K_iis the objective function of thei_th KI, andx_i is thei_thposition value. The effect of the best objective function of thei_thKI is handled by using Eq. (2.15).:

β_i^best=Kb_i,ibest

bx_i,ibest, (2.15)

where,Kb_i,best is the best previous objective function of thei_th KI,bx_i,_{f ood} is the best previous visited food position of thei_thKI. The movement induced by other individuals and the forging movement decrease with the increase in the time (iterations).

2.4.1(c) Physical Diffusion:

Physical diffusion is the net movement of each KI from a region of high density to a region of low density or vice versa. The better position of the KI is the less random direction. Physical diffusion values of individuals are estimated by two effects, namely,

(44)

maximum diffusion speed (D_m) and random directional vector (δ) (L. M. Abualigah, Khader, Al-Betar, & Awadallah, 2016; Gandomi & Alavi, 2012; Jensi & Jiji, 2016;

G. Wang et al., 2014). Physical diffusion for thei_th KI is determined by Eq. (2.16).

D_i=D^max

1− I I_max

δ, (2.16)

where, D^max is the parameter for tuning the diffusion speed, it is determined experimentally (see Table 5.11), and δ refers to the array that contains random values between [-1, 1]. I is the current iteration,I_max is max number of iterations.

2.4.1(d) Updating the Krill Individuals:

The movement of thei_th KI is influenced by the other KIs, foraging motion, and physical diffusion. These factors seek to obtain the best objective function for each KI.

The foraging movement and the movement induced by other KIs include two global and two local strategies. These strategies are working in parallel to make KH a robust algorithm (Bolaji et al., 2016; Gandomi & Alavi, 2012; G. Wang et al., 2013). The individual positions updated towards the best objective function by Eq. (2.17).

x_i(I+1) =x_i(I) +∆tdx_i

dt , (2.17)

where,

(45)

∆t=C_t

n

∑

j=1

(U B_j−LB_j), (2.18)

∆tis an important and sensitive constant computed by Eq. (2.18), andnis the total number of individuals. LB_j is the lower bound, U B_j is the upper bounds of the ith variables(J=1,2, ....,n), andC_t is a constant value between [0, 2]. It works as a scale factor of the speed vector.

2.4.2 The Genetic Operators

Genetic algorithm (GA) is a stochastic meta-heuristic search method for the global solution in a large search space. This algorithm is inspired by the classical evolutionary algorithms (EA). The genetic operators encoded in a genome that performed in an unusual way that permits asexual reproduction that leads to the offspring. However, the sexual reproduction can swap and reorder chromosomes, giving birth to offspring which includes a cross breeding of genetic information from all parents. This operation is often called a crossover, which means swapping of the genetic information. To avoid premature convergence, the mutation operator is used to increase the diversity of the solutions (H. Chen, Jiang, Li, & Li, 2013; G.-G. Wang, Gandomi, & Alavi, 2014b).

Genetic operators are incorporated into the KH algorithm to improve its performance (Bolaji et al., 2016; Gandomi & Alavi, 2012).

2.4.2(a) Crossover Operator of KH Algorithm:

The crossover operator is an effective procedure for global solutions. This procedure is controlled by a probabilityCr by generating a uniformly distributed random value

(46)

between [0, 1] (G.-G. Wang, Gandomi, & Alavi, 2014b). Themthcomponent ofx_i,m is determined as the following:

x_i,m=











x_p,m, ifrand<Cr x_q,m else

(2.19)

.

Cr=0.2Kb_i,best, (2.20)

.

where, the crossover probability is determined by Eq. (2.19). pandqrefer to the two solutions which are chosen for the crossover operator, p,q∈ {1,2, ....,i−1,i+ 1, ....,n}, the Cr increases with decreasing fitness function, Kb_i,best = K_i−K^best; K_i is the objective function value of thei_th KI, andK^best is the best objective function value of thei_thKI.

2.4.2(b) Mutation Operator of KH Algorithm:

The mutation operator is an effective strategy for a global solution. This strategy is controlled by a probabilityMu(G. Wang et al., 2014). The mutation operator is determined as the following:

x_i,m=











x_gbest,m+µ(xp,m−x_q,m), ifrand<Mu

x_i,m, else

(2.21)

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

CLUSTERING

LAITH MOHAMMAD QASIM ABUALIGAH

UNIVERSITI SAINS MALAYSIA

2018

FEATURE SELECTION AND ENHANCED KRILL HERD ALGORITHM FOR TEXT DOCUMENT

CLUSTERING

LAITH MOHAMMAD QASIM ABUALIGAH

March 2018

ACKNOWLEDGEMENT

TABLE OF CONTENTS

REFERENCES ... ... ..

LIST OF TABLES

LIST OF FIGURES

LIST OF ABBREVIATIONS

CHAPTER 1 INTRODUCTION

CHAPTER 2

KRILL HERD ALGORITHM

∑

∑

∑