Unprecedented Rough Sets Model for Arabic Document Clustering

Text mining [1, 2] refers to discovering hidden, significant, unknown patterns in written text or documents. It is a variant of data mining [3] with the difference that data mining deals with structured formats, while text mining can deal with semi-structured and unstructured formats [4]. Summarization, information extraction, clustering, association rule mining, and question answering are some of the text mining technologies used in the mining process to analyze, understand, and even create text.

Compared to languages with simpler patterns, Arabic poses particular difficulty of document grouping tasks. Interestingly, there is ambiguity in Arabic writing since it lacks natural vowel marks. Arabic morphology also includes intricate derivational prefixes and suffixes’ that profoundly change the meaning of the words to overcome these obstacles during the document preparation, specific preprocessing techniques like stemming and disambiguation are required. In data mining and information retrieval, document clustering is essential, particularly given the enormous and constantly expanding number of Arabic texts available online. Clustering making it easier to navigate and analyze the information resources efficiently by organizing documents in groups according to themes that they share [5].

Clustering is an unsupervised task [6] that aims to find the most similar objects or structures without predefined knowledge of the target of these objects. Document or text clustering is an interesting research area [7]. It is one of the text mining tools [4] that manages documents into a significant number of clusters by grouping the most similar documents into one coherent cluster by decreasing the intra-distance among documents and making the inter-distance among other dissimilar ones as large as possible.

Clustering algorithms can be categorized as traditional or modern. Traditional algorithms are further divided into several categories, such as partitional, hierarchical, and fuzzy theory-based approaches. Conversely, modern clustering techniques may utilize kernels, ensembles, or swarm intelligence. For detailed information about clustering algorithms, a comprehensive study was presented by Ezugwu et al. [8].

In 1982, Pawlak introduced the concept of rough set theory (RST) [9-11], a framework for handling ambiguous, inaccurate, incompatible, and doubtful knowledge. RST has been successfully applied in various fields of artificial intelligence. For instance, it assists in feature selection [12, 13] by determining relevant features from a corpus and discerning their significance. It is also used in classification and clustering [14], grouping objects according to discernible patterns in the data, and in decision support systems [15], where it helps analyze vague or imprecise data. Additionally, RST is utilized in the medical field to aid in disease diagnosis, classify diseases, and prognosticate patient outcomes by analyzing medical data [16].

The key reasons for using RST for handling imprecise and uncertain data are its simplicity and intuitive model for analyzing complex data. The resulting analyses of the RST model are interpretable and helpful in decision-making, besides its robustness to noise and missing data, hence it is applicable for real-life applications. Moreover, using RST in data analysis does not require extra information about the knowledge, such as the probabilities in the statistics or the degree of membership in the fuzzy set [17].

RST assumes that we have a finite set of objects called the universe of discourse, which we will denote by the symbol (Ω) and X is a subset of Ω. RST uses the equivalence relation, the indiscernibility relation R, $R \subseteq \Omega \times \Omega$. It identifies attributes that can distinguish between objects in a dataset. For a given set of objects, let say X which it is a subset of Ω, the discernibility relation identifies which attributes can separate them into disjoint equivalence classes. This relation should satisfy the reflective, symmetric and transitive properties and it is important to define the upper and the lower approximations. Two objects a, b ϵ Ω are said to be indiscernible in R if a R b. The indiscernibility relation is expressed in Eq. (1).

$\operatorname{IND}(X)=\left\{(a, b) \mid(a, b) \in \Omega^2, \forall_{x \in X}(x(a)=x(b))\right\}$        (1)

Each concept in this universe is associated with some knowledge. So, any concept in this universe of discourse can be represented as a subset X of Ω. The basic notions of the RST concept are that each set X can be approximated by a pair of disjoint sets: the lower and upper approximations. The lower approximation L refers to the set of objects that definitely belong to X, while the upper approximation U is the set of objects that may belong to X. The boundary region B is the difference between the upper and lower approximations. Below is the mathematical definition of these approximations [9, 10].

$L(X)=\left\{a \in \Omega:[a]_R \subseteq X\right\}$       (2)

$U(X)=\left\{a \in \Omega:[a]_R \cap X \neq \varnothing\right\}$     (3)

$B(X)=U(X)-L(X)$    (4)

where, $[a]_R$ means the equivalence class of a.

The knowledge that describes the universe of discourse is represented as an information table, IT [18]. It consists of a group of objects characterized by a combination of features. The IT is defined by the quadruple, which is defined in Eq. (5).

$I T=\left\{\Omega, T,\left\{V_t \mid t \in T\right\},\left\{I_t \mid t \in T\right\}\right\}$    (5)

where, $\Omega$ is a finite, none empty set of objects, $T$ is none empty set of attributes, $V_t$ a non-empty set of values which is subset of T and $I_t$ is a function, $I_t: \Omega \times V_t$.

Let’s explore a dataset of cars that have three different features: buying price (low, high), luggage bot size (big, small), and safety (very high, high, low) as presented in Table 1. Our aim is to decide whether the care is acceptable (yes) or unacceptable (no) based on these features.

Table 1. Cars’ dataset

From car dataset c1, c2 and c5 are indiscernible with respect to Price feature, c3 and c3 are indiscernible with respect to Luggage and Acceptable features and c2 and c5 are indiscernible with respect Price, Luggage and Safety features. So, Luggage feature creates two equivalence classes {c1, c3, c4, c6} and {c2, c5} while, features Price and Safety generates five equivalence classes {c1}, {c2, c5}, {c3}, {c4] and {c6 and so on the equivalence classes can be generated from any subset of features.

Car cannot be scribed in term of features Price, Luggage, and Safety since c2 is acceptable while, c5 is not and they are indistinguishable with regard to these features. Therefore, c2 and c5 are boundary line and in such a situation they cannot be appropriately classified based on information at hand. The remaining cars c1, c2, and c3 can be certainly categorized as acceptable cars in term of Price, Luggage and Safety and c4 is certainly unacceptable car. So, the lower approximation of the acceptable cars is, $L(X)=\{c 1, c 3, c 6\}$, while the upper approximation, the care that may be classified as acceptable is, $U(X)=\{c 1, c 2, c 3, c 5, c 6\}$ meanwhile the boundary region is, $B(X)=\{c 2, c 5\}$.

A discernibility matrix $D(I T)$, is an essential tool of RST used to represent the discernibility relation between features. The matrix element indicates whether two features are discernible or indiscernible to each other based on the given dataset. The discernibility relation plays crucial role in constructing this matrix. The discernibility matrix's main goal is to determine an object's discernibility relations according to its properties.

Arabic language is increasingly spoken last few years. According to the Statista statistics website (www.statista.com\statistics), more than 270 million people speak Arabic, and as a consequence, the number of web contents written in Arabic is potentially increasing. Diverse features, such as various morphologies, orthography, structural features, unique linguistics, different word meanings, and more uncountable features of Arabic, are considered key challenges in Arabic document clustering (ADC) [19-21].

The contribution of this paper is to cluster Arabic documents using an unprecedented adapted rough set model. The model is based on creating the feature table for the manipulated data, measuring the similarities among documents depending on the properties of rough sets, and then using these similarities in the clustering process. The results achieved by this model of 85% for CNN and 85% for OSAC offer a promising contribution in the field of ANLP.

The rest of this paper is managed as follows: the related works covers works that made on Arabic document clustering. The proposed model is described in detail in Methodology. Meanwhile, the results and discussion examine the results that we obtain. The main contribution and the future works demonstrate in conclusion.

In this paper, we suggest an unprecedented model for clustering Arabic documents based on rough set theory. As a preliminary step, the dataset is prepared by removing unnecessary and noisy data. The prepared information is then utilized as a key input for the extracted feature table that will be used to describe the universe of discourse. Afterwards, the similarity among documents is measured by calculating the distance matrix. And the last step is utilizing the distance matrix in the clustering process. The model design is shown in Figure 1. The model includes four stages:

1. Dataset preprocessing and Encoding

2. Extracted feature table

3. Construction of weighted distance graph WDD

4. Document clustering

1.png

Figure 1. Overall system design

The model’s stages are explained in the following sub-sections.

3.1 Dataset preprocessing and document representation

Two public and well-known datasets, CNN and OSAC, were used to assess the suggested model [29]. The CNN dataset was collected from the CNN Arabic website and consists of more than 4000 documents divided into six classes (business, history, entertainment, Middle East news, sport, and world news). On the other hand, the OSAC dataset was assembled from diverse Arabic internet sources and has over 22000 articles spread across ten classes (economics, history, entertainment, education and family, religion and fatwa, sport, health, astronomy, law, stories, and cooking recipes).

Preprocessing data is an important step for machine learning techniques since the raw data may contain meaningless, noisy, and non-useful data, and it is also in a non-readable format. So preprocessing is done in a format that is acceptable to the technique used. It includes tokenizing data, refining it, and purifying it from punctuation and stop-words, and then the root of each word is extracted in the stemming step. The datasets are cleaned from unimportant words such as punctuation and stop-words that do not affect the clustering and stemmed using Tashaphyne stemmer, which is an open-source project available at Tashaphyne PyPI. After that, it was saved to the CSV file. Algorithm 1 shows the preprocessing phase.

The refined data is then encoded using either TF/IDF or counter vectorizer (CV) encoding techniques. TF/IDF is a technique to represent a document, it contributes to dimension reduction. This technique is one of the best encoding methods that are employed to calculate the token’s weight in the dataset. Token frequency (token counts in a document) and inverse article frequency (token’s count in all dataset’s articles) the two crucial elements taken into account while determining TF/IDF values. The significant tokens are considered by this technique by maximizing their weight when these tokens are rare for the whole dataset but significant to understand the document.

$\operatorname{IDF}(t)=\log \left(N / n_{-} t\right)$     (6)

$T F(t, d)-I D F(t, d)=T F(t, d) * I D F(t)$         (7)

where TF(t,d) is the frequency of token in document d (i.e., the number of times token t in a document d) and IDF(t) is the inverse document frequency of the token t, N is the total number of documents in the dataset, and n_t is the total dataset documents that contain the token t.

The CV technique depends on token occurrences in the dataset. It transforms a document into a set of numerical values depending on the tokens’ frequencies. This technique deals with a document as distinct tokens, ignoring their order in the documents, so the tokens will be represented as a bag of tokens.

Both methods lessen the effects of high-dimensional feature space while capturing the syntactic and semantic information presented in the dataset. These encoding strategies help provide a compact but beneficial representation of documents by detecting discrimination and meaningful tokens. And this will answer the research’s first question.

3.2 Extracted feature table (FT)

The extracted FT is a quadruple model that represents uncertain and vague knowledge. This table is mathematically represented as Eq. (8).

$F T=\left\{\Omega, T,\left\{V_t \mid t \in T\right\},\left\{I_t \mid t \in T\right\}\right\}$    (8)

where, $\Omega=\left\{d_1, d_2, \ldots, d_n\right\}$ defines the finite non-empty set of documents, $T=\left\{T_1, T_2, \ldots, T_n\right\}$ is a non-empty set of discriminative documents' tokens. $V_t$ is a non-empty set of values $t \in T, I_t: \Omega \rightarrow V_t$ is a function that links a document of $\Omega$ to only one value in $V_t$.

Each row of FT corresponds to a document and each column signifies and significant discriminative document token identified during the encoding process. The cell’s value indicates the relation between a specific document and that particular token. This relationship is determined by Eq. (9).

$F T_{i j}=\left\{\begin{array}{l}1 \quad \text { if } t \in T \wedge t \in d_i \\ -1 \quad \text { otherwise. }\end{array}\right.$    (9)

for $i=1, \ldots, n$

$n=|\Omega|$, and $j=1,2, \ldots, m$ where $\mathrm{m}=|T|$. Once all the values in the FT are set, each document gets transformed into a vector of 1 s and -1 s. This transformed table becomes a crucial input for the next step, where it forms the basis for creating the distance matrix. Algorithm 2 presents the process of constructing the extracted feature table.

3.3 Construction of weighted distance graph

The discernibility matrix is an instrumental tool that plays essential role in feature selection that helps in data analytics and discover patterns or similarities for identifying of clusters or groups within documents. It can be viewed as a distance matrix or similarity matrix. It aids in identifying essential tokens that assists in documents differentiation while disregarding superfluous or extraneous ones. It assists to distinguish the documents that are similar to one another and those that can be distinct from one another. It assists in identifying essential symbols that support document differentiation while disregarding unnecessary or extraneous ones. It helps to distinguish between texts that are distinct from one another and those that are similar to one another. Additionally, by identifying discernibility relations, it aids in reducing the complexity of data.

The discernibility matrix of the set of documents is populated according Eq. (10).

$\begin{gathered}D_{i j}=\left\{t \in T: t\left(d_i\right) \neq t\left(d_j\right)\right\} \\ \text { for } i, j=1, \ldots . ., n \text { and } n=|\Omega|\end{gathered}$       (10)

$\Omega$ is the dataset space, $t$ is a specific token of the whole discriminative token- T, $d_i$, $d_j$ are i^th and j^th documents respectively.

The weighted distance graph construction is based on the FT that was extracted in the previous section. The graph nodes refer to the documents and the weighted arcs represent the similarities between documents. The arcs weights are calculated according to Algorithm 3. By constructing the distance graph where weighted edges represent the similarities between documents, this research identifies the model’s ability to discover the hidden patterns in the dataset documents and find the semantic relationship among them depending on the available information. This answers the second question of the research.

3.4 Documents clustering

The distance matrix (DM) is an adjacency matrix of weighted graph G, where the set of nodes N is the set of documents and the arcs represent the relation "Document D_i bears resemblance to Document D_j to the extent of S."

We can obtain the similarities among documents in the dataset once the matrix has been filled up. For example, the similarity between the i^th and j^th documents in the dataset is indicated by the value at DM_ij.

The distance matrix is used in the next phase of the proposed method to organize the documents into groups according to their degree of similarity and the specified number of the clusters.

Determining the number of the closest document to each document is an experimental task based on trial and error. At first, we start by selecting it according to the number of desired clusters, i.e., when the desired number of clusters is 6, then the model will select the six closest documents from the similarity matrix. Next, we choose 10% of the maximum features determined by TF/IDF when encoding the documents and gradually increase this value. After multiple implementations, we found that the best number of the chosen closest document depends on the number of clusters and the size of the dataset. After selecting the n closest documents with their similarities, the initial clusters will be formulated and will be equal to the total number of documents in the dataset, and the distance matrix size will be D×n instead of D×D, where D is the total number of documents in the dataset and n is the number of the closest documents.

Clustering starts by pruning the resulting clusters after determining the n closest document. It is worthy to mention that after eliminating the size of distance matrix, multiple clusters with identical documents will emerge. At this point, these clusters will be combined into a single cluster. Subsequently, the model begins to hard-cluster documents, allocating each document to a particular cluster.

In order to retain the document in the cluster with the highest similarity values, hard clustering involves removing duplicate documents from several clusters based on their respective similarity values. If a document is assigned to many clusters with identical similarity values, it will remain in the first cluster. This process will be repeated until the desired number of clusters is achieved in the clustering.

The proposed model is applied to two datasets (CNN and OSAC) and repeated for different TF/IDF and CV maximum feature values.

3.5 Illustrative example

Consider the following synthetic dataset presented in Table 3.

After data preprocessing stage, the discriminative tokens of the dataset will be presented in the Token list as follows:

Tokens= ['برلم'، 'جرء'، 'جرح'، 'جلس'، 'شفف'، 'علج'، 'عمل'، 'قنن'، 'لمز'، 'مثل'، 'مرض'، 'نتخب'، 'نزف'].

According to these words, the feature table will be extracted using algorithm 2. Table 4 depicts the extracted feature table.

Based on Table 3 the similarity among documents will be calculated and the weighted distance graph is calculated according to algorithm 3. The graph is then represented as an adjacency matrix of weighted graph G, where the set of nodes N is the set of documents and the arcs represent the relation "Document D_i bears resemblance to Document D_j to the extent of S." Consider Figure 2 which elucidates the similarity among the documents. Table 5 shows the similarity matrix.

Table 3. Synthetic dataset

Table 4. Extracted FT

Table 5. Similarity matrix

2.png

Figure 2. Weighted distance graph

Table 6. Closest documents with similarities

Table 7. Pruning clusters

Table 8. Merging identical clusters

Table 9. Final clusters

After the distance matrix is constructed, the clustering process starts: sorting the distance matrix and determine the number of clusters (clus_no) and the number of the closest documents (close_doc). Let us choose clus_no=2 and close_doc=3. Table 6 represents the closest documents with their similarities.

By applying the proposed clustering process, the clusters are pruned, the identical clusters will be merged, and finally, the sub-clusters will be merged with the closest one. The clustering process is shown in Tables 7-9.