A New Algorithm for Arabic Document Clustering Utilizing Maximal Wordsets

Arabic is a Semitic language. It is most often spoken in nations where the majority of the population is Muslim. It is also the language of the "AL-Quran AL-Kareem," the Muslims’ holy book. Over 400 million people speak Arabic as their first language, and over 250 million speak it as their second language, and it is recognized as the official tongue of states in North Africa and the Middle East [1]. Traditional, Modern Standard Arabic (MSA), and dialects are the three main categories of Arabic.

The Arabic language presents unique challenges for document clustering tasks compared to languages with simpler structures. Notably, the Arabic script lacks inherent vowel markings, leading to ambiguity. Additionally, Arabic morphology features complex derivational prefixes and suffixes that significantly alter word meaning. These characteristics necessitate specialized preprocessing techniques like disambiguation and stemming to overcome these challenges during document preparation [2, 3]. Document clustering plays a crucial role in data mining and information retrieval, especially for the vast and ever-growing volume of Arabic documents online. By grouping documents based on thematic similarity, clustering facilitates efficient navigation and analysis of these information resources. Effective clustering of Arabic documents is essential for various applications, including information retrieval, text mining, automatic document categorization and user review analysis [4].

Document clustering is an unsupervised machine learning process that groups documents based on similarities by eliminating the intra-similarity among documents in one group and increasing the inter-similarity properties among different groups. This process does not require class labels for the documents [5]. A challenging task in data and text mining is identifying hidden, important, and possible patterns in the document [6]. The most difficult problems in document clustering can be summed up as coping with massive data quantities, high dimensionality, and low retrieval precision.

Dealing with large data volumes, high dimensionality, and low retrieval precision can be summed up as the most challenging issues when dealing with document clustering [7]. Arabic documents are now readily available online in a variety of formats, making it difficult to organize them without the aid of a computer. The clustering of Arabic-language documents has recently attracted the attention of researchers.

To depict the connection between data points and the clusters they belong to, hierarchical clustering creates a structure like a tree. Each data point is initially clustered separately and iteratively merging smaller clusters into bigger clusters when the stopping criteria is satisfied. Hierarchical clustering comes in two forms: agglomerative (bottom-up) and divisive (top-down).

Partitional clustering divides the data into a predetermined number of distinct, non-overlapping clusters. It aims to keep the distances between the data points and the cluster centroids as small as possible. K-means and K-medoids are two common partitional clustering algorithms. While density-based clustering, creates clusters by locating regions with a high data point density. A cluster is defined as a dense zone surrounded by a sparse region. This type of clustering is helpful in detecting clusters of arbitrary forms. DBSCAN and HDBSCAN are examples of this type of clustering algorithms [8].

Association rule mining (ARM) [9] is a data mining technique that is used to discover potential hidden patterns among data. Apriori and FP-Growth are the most widely used algorithms for extracting all frequent itemsets (FI) and frequent patterns in datasets, respectively [10]. To extract FI from large transactions, the Apriori approach is widely utilized. It works on the assumption that all FI subsets must also be frequent. It continuously counts the support of items and item combinations that can be utilized within a transaction and eliminating any sets that go below a user-defined threshold and by integrating sets from the previous iteration and validating them against the transaction, candidate frequent itemsets are created. Despite being easy to comprehend and utilize, the Apriori technique can be computationally expensive for massive transactions and demands several database searches. On the other hand, the FP-Growth approach is scalable and utilized to mine frequent item sets in large datasets. The algorithm stores the frequent item sets in a tree-like data structure known as the FP-tree. The itemsets are encoded in the tree after a single run over the dataset to generate it, making it fast and quick to mine the common itemsets by utilizing depth-first search to traverse the tree.  In order to decrease the size of the tree and improve the algorithm's scalability and performance, the divide-and-conquer strategy and pruning techniques are used. FP-Growth has been shown to be faster than traditional frequent item set mining algorithms, such as Apriori, and is widely used in data mining and machine learning applications.

The conventional frequent itemsets mining algorithms are computationally extensive and generate voluminous sets of items. Therefore, maximal frequent itemsets (MFI) approach is undertaken to overcome the forementioned problems by significantly reducing the search space. Various algorithms were proposed for mining MFI, such as MAFIA [11], FPmax algorithm [12], MaxMining [13], GenMax [14], and MIMA [15, 16] which dedicated to mine textual MFI from Arabic documents.

Document clustering plays a vital role in organizing and analyzing vast collections of Arabic text data. However, the unique characteristics of the Arabic language, such as the lack of inherent vowel markings and complex morphology, pose significant challenges for traditional clustering techniques. This paper proposes a novel algorithm to Arabic document clustering that addresses these challenges and offers promising accuracy.

Our key contribution lies in leveraging Maximal Frequent Word Sequences (MFWSs) for Arabic document clustering. By employing the FPMax algorithm, we extract the most prominent recurring sequences of words within the documents. These MFWSs capture the thematic content of documents more effectively compared to individual words, as they account for the inherent structure and context of the Arabic language.

The remainder of this paper is organized as follows; the second section examines previous studies that have used maximally frequent item sets for document clustering. The proposed approach is thoroughly explained in Section 3 with an example, and the experiments and findings are covered in Section 4. The conclusion is demonstrated in the final section.

The Maximal Frequent Wordset-Based Arabic Document Clustering System (MFW-ADC) is presented in this paper. MFW leverages the FPMax algorithm to extract informative MFWs from Arabic documents. These MFWs capture the thematic content and inherent structure of the language, enabling effective document clustering. The model comprises three modules: preprocessing, dimensionality reduction and MFW mining, and clustering (as shown in Figure 1). These modules are described in detail in the subsequent sections.

1.png

Figure 1. System architecture

3.1 Preprocessing module

Document preprocessing is a crucial step in natural language analysis, ensuring trustworthy and reproducible textual data. It comprises four stages: tokenization, normalization, punctuation and stopword removal, and stemming. Tokenization divides a document into separate words. Normalization converts letters into one form, while special characters and stopword removal reduce data dimensionality and improve analysis accuracy. Stemming generates a morphological variant of the base word, ensuring the same root word is considered the same entity. In Arabic, several stemming algorithms have been developed, such as Tashapheen, Khoja [22], Light Stemmer [23], etc., to achieve optimal results. The algorithm is depicted in Algorithm 1. Table 1 shows an explanation of the variables, symbols, and functions used in the proposed algorithms.

Table 1. Variables and functions explanation

3.2 Dimension reduction and wordsets mining module

This module comprises two steps: dimension reduction and wordset mining. Dimension reduction is accomplished in two stages. The first phase is done by representing the preprocessed documents using TF/IDF approach and the second stage is accomplished by utilizingthe FPmax algorithm to extract the MFWs according to the provided minimum support.

TF/IDF is one of the best metrics used to show how significant a word is to a document in a dataset. Two factors are considered when calculating TF/IDF: word frequency (how many times a word appears in a specific document) and the inverse document frequency (how often this word appears in all document in the dataset). This technique optimizes frequent, rare words in a document to highlight discriminative features, ensuring the content is understood while excluding irrelevant or common words. Eqs. (1) and (2) show how to calculate TF-IDF.

${IDF}(w)=\log \left(N / n \_w\right)$                      (1)

$T F-{IDF}(w, d)=T F(w, d) * {IDF}(w)$                     (2)

where, TF(w,d) is the frequency of word w in document d (i.e., the number of times word w appears in document d) and IDF(w) is the inverse document frequency of word w, N is the total number of documents in the corpus, and n_w is the number of documents in the corpus that contain word w.

Our dataset consists of Arabic documents. Each document is identified by a unique document identifierDID and a list of preprocessed words (wordlist). To reduce the data complexity, Fpmax algorithm [12] is used to discover the most frequent word patterns (MFWs) within the documents. This technique relies on two key parameters: minimum support and maximum wordset length. Adjusting these parameters helps in reducing the data dimentionality while still obtaining the crucial inormation from the documents. This will enhance the clustering effeciency and accuracy. The algorithm used is shown in Algorithm 2.

3.3 Clustering module

This module outlines four key steps: primary clustering, merging equal clusters, hard clustering, and final clustering, which are detailed in the following subsections.

3.3.1 Primary clustering

Initial clusters are created using the Fpmax algorithm's MFWs, with words as labels. The best-fit clusters are determined using similarity functions such as Euclidean distance, cosine similarity, Manhattan distance, overlap, and Jaccard index, as represented by Eqs. (3) to (7). The length of the cluster’s label, i.e., MFW’s length, will be added to the similarity function. The purpose of adding this factor is to assign the document to the most similar and largest clusters. The process of determining initial clusters is illustrated in algorithm 3.

$d(d, m f w) {sqrt}\left({sum}\left(\left(d_i-m f w_i\right)^2\right)\right)+|m f w|$         (3）

$\cos (\theta)=((d * m f w) /\|d\| *\|m f w\|)+|m f w|$         (4）

$d(d, m f w)=\sum\left|d_i-m f w_i\right|+|m f w|$         (5）

${Overlap}(D, m f w)=\left|\frac{|D\,  \cap \, m f w|}{\min (|D|, \mid m f w) \mid}\right|+|m f w|$         (6）

$J(D, m f w)=\left\lceil\frac{|D \, \cap \, m f w|}{|D\, \cup \, m f w|}\right]+|m f w|$         (7）

3.3.2 Merging equal clusters

It's worthy to mention that, after identifying the initial clusters, it is possible to identify numerous clusters with similar DID sets. After that, these clusters can be combined using the approach illustrated in Algorithm 4.

3.3.3 Hard clustering

The proposed algorithm uses hard clustering to assign documents to specific clusters based on their similarity. This process calculates the percentage of belonging between documents and MFWs, retaining the highest-percentage-related document and removing the lowest-percentage-related document. The cluster with significant support can incorporate a document when competing with other clusters. The algorithm utilized for hard clustering implementation is depicted in algorithm 5.

3.3.4 Final clustering

The final step involves merging clusters (MFWs) from previous stages to create final clusters. The desired number of clusters is specified, and the clusters are merged with the most similar one based on their similarity value. One of the measures described in Section 3.2 is used to calculate the similarities between the MFWs. The length of the MFW is a significant factor that ensures a cluster will be merged with the longest and most similar one. The employed algorithm is depicted in algorithm 6.

3.4 Illustrative example

Suppose we have the following dataset:

Dataset = [[G, I], [F, E, G, I, A], [H, A, D, C, E, G, F], [B, I, F], [H, B, E, F], [H, F], [C, D, H, G]], where A, B, C, D, E, F, G, H, and I represent preprocessed words in the document dataset.

By applying Algorithm 2 that was mentioned in the previous section with a minimum support of 0.2, the mined MFWs and their corresponding DID support values are shown in Table 2.

Table 2. Mined MFWs

When algorithm 3 is applied to the mined MFWs, the initial clusters obtained are shown in Table 3.

Table 3. Initial clusters

From Table 3, we can see that document 2 is assigned to two clusters (cluster 1 and cluster 3), and we can also find two equal clusters, i.e., two clusters contain document 3. By applying algorithms 4 and 5 for merging equal clusters and hard clustering, respectively, we obtain Table 4.

Table 4. Merging and hard clustering

By determining the number of clusters to 3, the final clustering process is depicted in Table 5.

Table 5. Final clustering