% This is "Informatical_clustering.tex" Final Version  June 2016
% Author: Quang Vu Bui, Karim Sayadi, Marc Bui
% articles to Informatical Journal format
% Article for special issue for Informatica Journal extended from SOICT 2015 Conference, 3-5 December, 2015, Hue city, Vietnam 
% Revisions:  01 July 2016



\documentclass[11pt,twoside]{article}
\usepackage{Informat}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{amsmath,amssymb}
\usetikzlibrary{arrows}
\tikzstyle{block}=[draw opacity=0.7,line width=1.4cm]
% For every picture that defines or uses external nodes, you'll have to
% apply the 'remember picture' style. To avoid some typing, we'll apply
% the style to all pictures.
\tikzstyle{every picture}+=[remember picture]
\usepackage{algorithm,algpseudocode}
\usetikzlibrary{bayesnet}
\usepackage{color}
\usepackage{balance}


%%%%%%%%%%% Fin partie boxes %%%%%%%%%%%%%%%%%%%%%%%%

% By default all math in TikZ nodes are set in inline mode. Change this to
% displaystyle so that we don't get small fractions.
\everymath{\displaystyle}
\usetikzlibrary{bayesnet}
\newtheorem{mydef}{Definition}
\newtheorem{mypropo}{Proposition}

\begin{document}
  \title{A Multi-Criteria Document Clustering Method Based on Topic Modeling and Pseudoclosure Function}
   \author{Quang Vu Bui \\
      Hue University of Sciences, Vietnam and CHArt Laboratory EA 4004, EPHE, Paris, France\\
      E-mail:  quang-vu.bui@etu.ephe.fr \\
      \AndAuthor
      Karim Sayadi \\
      Sorbonne University, UPMC Univ Paris 06 and CHArt Laboratory EA 4004, EPHE, Paris, France\\
      karim.sayadi@upmc.fr \\
      \AndAuthor
      Marc Bui\\
      EPHE and UP8 Univ Paris 08 and CHArt Laboratory EA 4004, Paris, France\\
      marc.bui@ephe.sorbonne.fr}
      
%  \titleodd{Title of the\ldots}
%  \authoreven{N. SurnameofAuthor1 et al.}
  \keywords{Pretopology, pseudoclosure, clustering, k-means, Latent Dirichlet Allocation, Topic Modeling, Gibbs Sampling.}
  \received{July 01, 2016}

  \abstract{We address in this work the problem of document clustering. Our contribution proposes a novel unsupervised clustering method based on the structural analysis of the latent semantic space. Each document in the space is a vector of probabilities that represents a distribution of topics. The document membership to a cluster is computed taking into account two criteria: the major topic in the document (qualitative criterion) and the distance measure between the vectors of probabilities (quantitative criterion). We perform a structural analysis on the latent semantic space using the Pretopology theory that allows us to investigate the role of the number of clusters and the chosen centroids, in the similarity between the computed clusters. We have applied our method to Twitter data and showed the accuracy of our results compared to a random choice number of clusters.}
 
  \abstractSi{}

  \maketitle

\section{Introduction}
%Motivation
Classifying a set of documents is a standard problem addressed in machine learning and statistical natural language processing \cite{Manning2009}. Text-based classification (also known as text categorization) examines the computer-readable ASCII text and investigates linguistic properties to categorize the text.
When considered as a machine learning problem, it is also called statistical Natural Language Processing (NLP) \cite{Manning2009}. In this task, a text is assigned to one or more predefined class labels (i.e category) through a specific process in which a classifier is built, trained on a set of features and then applied to label future incoming texts. Given the labels, the task is performed within the supervised learning framework. Several Machine Learning algorithms have been applied to text classification (see \cite{aggarwal2012survey} for a survey): Rocchio's Algorithm, N-Nearest Neighbors, Naive Bayes, Decision tree, Support Vector Machine (SVM).

Text-based features are typically extracted from the so-called word space model that uses distributional statistics to generate high-dimensional vector spaces. Each document is represented as a vector of word occurrences. The set of documents is represented by a high-dimensional sparse matrix. In the absence of predefined labels, the task is referred as a clustering task and is performed within the unsupervised learning framework. Given a set of keywords, one can use the angle between the vectors as a measure of similarity between the documents. Depending on the algorithm, different measures are used. Nevertheless, this approach suffers from the curse of dimensionality because of the sparse matrix that represents the textual data. One of the possible solutions is to represent the text as a set of topics and use the topics as an input for a clustering algorithm.

To group the documents based on their semantic content, the topics need to be extracted.
This can be done using one of the following three methods. 
(i) LSA \cite{landauer_solution_1997} (Latent Semantic Analysis) uses the Singular Value Decomposition methods to decompose high-dimensional sparse matrix to three matrices: one matrix that relates words to topics, another one that relates topics to documents and a diagonal matrix of singular value.
(ii) Probabilistic LSA \cite{Hofmann:1999:PLS:312624.312649}  is a probabilistic model that treats the data as a set of observations coming from a generative model.
The generative model includes hidden variables representing the probability distribution of the words in the topics and the probability distribution of the topics in the words. 
(iii) Latent Dirichlet Allocation \cite{Blei:2003:LDA:944919.944937} (LDA) is a Bayesian extension of probabilistic LSA. It defines a complete generative model with a uniform prior and full Bayesian estimator. 

LDA gives us three latent variables after computing the posterior distribution of the model; the topic assignment, the distribution of words in each topic and the distribution of the topics in each document. Having the distribution of topics in documents, we can use it as the input for clustering algorithms such as k-means, hierarchical clustering. 

K-means uses a distance measure to group a set of data points within a predefined random number of clusters. Thus, to perform a fine-grained analysis of the clustering process we need to control the number of clusters and the distance measure. The Pretopology theory \cite{belmandt_basics} offers a framework to work with categorical data, to establish a multi-criteria distance for measuring the similarity between the documents and to  build a process to structure the space \cite{Largeron2002169} and infer the number of clusters for k-means. We can then tackle the problem of clustering a set of documents by defining a family of binary relationships on the topic-based contents of the documents. The documents are not only grouped together using a measure of similarity but also using the pseudoclosure function built from a family of binary relationships between the different hidden semantic contents (i.e topics).

The idea of using Pretopology theory for k-means clustering has been proposed by \cite{le_new}. In this paper, the authors proposed the method to find automatically a number $k$ of clusters and $k$ centroids for $k$-means clustering by results from structural analysis of minimal closed subsets algorithm \cite{Largeron2002169} and also proposed to use pseudoclosure distance constructed from the relationships family to examine the similarity measure for both numeric and categorical data. The authors illustrated the method with a toy example about the toxic diffusion between 16 geographical areas using only one relationship. 

For the problem of classification, the authors of this work \cite{ahat_halshs00642761} built a vector space with Latent Semantic Analysis (LSA) and used the pseudoclosure function from Pretopological theory to compare all the cosine values between the studied documents represented by vectors and the documents in the labeled categories. A document is added to a labeled categories if it has a maximum cosine value.

Our work differs from the work of \cite{ahat_halshs00642761} and extends the method proposed in \cite{le_new} with two directions: first, we exploited this idea in document clustering and integrated structural information from LDA using the pretopological concepts of pseudoclosure and minimal closed subsets introduced in \cite{Largeron2002169}. Second, we showed that Pretopology theory can apply to multi-criteria clustering by defining the pseudo distance built from multi-relationships. In our paper, we clustered documents by using two criteria: one based on the major topic of document (qualitative criterion) and the other based on Hellinger distance (quantitative criterion). The clustering is based on these two criteria but not on multicriteria optimization \cite{Ferligoj1992} for clustering algorithms.Our application on Twitter data also proposed a method to construct a network from the multi-relations network by choosing the set of relations and then applying strong or weak Pretopology.

We present our approach in a method that we named the Method of Clustering Documents using Pretopology and Topic Modeling (MCPTM). MCPTM organizes a set of unstructured entities in a number of clusters based on multiple relationships between each two entities. Our method discovers the topics expressed by the documents, tracks changes step by step over time, expresses similarity based on multiple criteria and provides both quantitative and qualitative measures for the analysis of the document.
\subsection{Contributions}
The contributions of this paper are as follows.
\begin{enumerate}
\item We propose a new method to cluster text documents using Pretopology and Topic Modeling. 
\item We investigate the role of the number of clusters inferred by our analysis of the documents and the role of the centroids in the similarity between the computed clusters.
\item We conducted experiments with different distances measures and show that the distance measure that we introduced is competitive. 
\end{enumerate}
\subsection{Outline}
The article is organized as follows: Section 2, 3 present some basic concepts such as Latent Dirichlet Allocation (Section 2) and the Pretopology theory (Section 3), Section 4 explains our approach by describing at a high level the different parts of our algorithm. In Section 5, we apply our algorithm to a corpus consisting of microblogging posts from Twitter.com. We  conclude our work in Section 6 by presenting the obtained results.
\section{Topic Modeling}

Topic Modeling is a method for analyzing large quantities of unlabeled data. For our purposes, a topic is a probability distribution over a collection of words and a topic model is a formal statistical relationship between a group of observed and latent (unknown) random variables that specifies a probabilistic procedure to generate the topics \cite{Blei:2003:LDA:944919.944937, Hofmann:1999:PLS:312624.312649, griffiths_finding_2004,steyvers_probabilistic_2007}. In many cases, there exists a semantic relationship between terms that have high probability within the same topic -- a phenomenon that is rooted in the word co-occurrence patterns in the text and that can be used for information retrieval and knowledge discovery in databases. 

\subsection{Latent Dirichlet Allocation}
\begin{figure}[h]
    \centering
    \begin{tikzpicture}
    
    % Define the nodes 
    \node[obs]                (w) {$w_{d,n}$};
    \node[latent, above=of w]    (z) {$z$};
    \node[latent, above=of z]  (theta) {$\pmb{\theta}_{d}$};
    \node[latent, left=1.2cm of w] (phi) {$\pmb{\phi}_{k}$};
    \node[latent, left=1.2cm of theta] (alpha) {$\alpha$};
    \node[latent, left=of phi] (beta) {$\beta$};
    
    
    
    %Connect the nodes 
    \edge {z}{w};
    \edge {theta}{z};
    \edge {phi}{w};
    \edge {alpha}{theta};
    \edge {beta}{phi};
    
    %Plates
    \plate {w} {(z)(w)} {word $n$};
    \plate {w} {(z)(w)(theta)} {document $d$};    
    \plate {phi} {(phi)} {topic $k$};
    
    \end{tikzpicture}
    \caption{Bayesian Network (BN) of Latent Dirichlet Allocation. %BN is a probabilistic graphical model where the observed variable is in gray, here, for example, the $w_{d,n}$ word $n$ in the document $d$. The plates represent the occurrences of the variables or the pattern.
    }
\end{figure}
Latent Dirichlet Allocation (LDA) by Blei et al. \cite{Blei:2003:LDA:944919.944937} is a generative probabilistic model for collections of grouped discrete data. Each group is described as a random mixture over a set of latent topics where each topic is a discrete distribution over the vocabulary collection. LDA is applicable to any corpus of grouped discrete data. In our work we refer to the standard Natural Language Processing (NLP) use case where a corpus is a collection of documents, and the discrete data are represented by the occurrence of words. 

LDA is a probabilistic model for unsupervised learning, it can be seen as a Bayesian extension of the probabilistic Latent Semantic Analysis (pLSA) \cite{Hofmann:1999:PLS:312624.312649}. More precisely, LDA defines a complete generative model which is a full Bayesian estimator with a uniform prior while pLSA provides a Maximum Likelihood (ML) or Maximum a Posterior (MAP) estimator. For more technical details we refer to the work of Gregor Heinrich \cite{Heinrich04parameterestimation}. The generative model of LDA is described with the probabilistic graphical model \cite{Koller:2009:PGM:1795555} in Fig. 1.  

In this LDA model, different documents $d$ have different topic proportions $\theta_{d}$. In each position in the document, a topic $z$ is then selected from the topic proportion $\theta_{d}$. Finally, a word is picked from all vocabularies based on their probabilities $\phi_{k}$ in that topic $z$. $\theta_{d}$ and $\phi_{k}$ are two Dirichlet distributions with $\alpha$ and $\beta$ as hyperparameters. We assume symmetric Dirichlet priors with $\alpha$ and $\beta$ having a single value. 

The hyperparameters specify the nature of the priors on $\theta_{d}$ and $\phi_{k}$. The hyperparameter $\alpha$ can be interpreted as a prior observation count of the number of times a topic $z$ is sampled in document $d$ \cite{steyvers_probabilistic_2007}. The hyper hyperparameter $\beta$ can be interpreted as a prior observation count on the number of times words $w$ are sampled from a topic $z$  \cite{steyvers_probabilistic_2007}. 
%The generative process for a document collection D under the LDA model is as follows:
%\begin{hlevel}{Latent Dirichlet Allocation}
%\begin{enumerate}
%\item For $k = 1,\ldots,K$:
%\begin{itemize}
%    \item[(a)]  $\phi^{(k)} \sim Dirichlet(\beta)$
%\end{itemize}
%\item For each document $d \in D$:
%\begin{itemize}
%    \item[(a)]  $\theta_d \sim Dirichlet(\alpha)$
%    \item[(b)]  For each word $w_i \in d$:
%    \begin{itemize}
%        \item[ i.]     $z_i \sim Multinomial(\theta_d)$
%        \item[ ii.]     $w_i \sim Multinomial(\phi^{(z_i)})$
%    \end{itemize}
%\end{itemize}
%\end{enumerate}
%\end{hlevel}

The advantage of the LDA model is that interpreting at the topic level instead of the word level allows us to gain more insights into the meaningful structure of documents since noise can be suppressed by the clustering process of words into topics. Consequently, we can use the topic proportion in order to organize, search, and classify a collection of documents more effectively.
\subsection{Inference with Gibbs sampling}

In this subsection, we specify a topic model procedure based on the Latent Dirichlet Allocation (LDA) and Gibbs Sampling.

The key problem in Topic Modeling is posterior inference. This refers to reversing the defined generative process and learning the posterior distributions of the latent variables in the model given the observed data. In LDA, this amounts solving the following equation:
\begin{equation}
    p(\theta,\phi,z|w,\alpha,\beta)=\frac{p(\theta,\phi,z,w|\alpha,\beta)}{p(w|\alpha,\beta)}
\end{equation}
Unfortunately, this distribution is intractable to compute \cite{Heinrich04parameterestimation}. The normalization factor in particular, $p(w|\alpha,\beta)$, cannot be computed exactly. However, there are a number of approximate inference techniques available that we can apply to the problem including variational inference (as used in the original LDA paper \cite{Blei:2003:LDA:944919.944937}) and Gibbs Sampling that we shall use.


%Gibbs Sampling is one member of a family of algorithms from the Markov Chain Monte Carlo (MCMC). The MCMC algorithms aim to construct a Markov chain that has the target posterior distribution as its stationary distribution. In other words, after a number of iterations of stepping through the chain, the samples from the distribution should converge to desired close sample from the posterior. Gibbs Sampling is based on sampling from conditional distributions of the variables of the posterior. 

%For example, to sample x from the joint distribution $p(x) = p(x_1,\ldots, x_m)$, where there is no closed form solution for p(x), but a representation for the conditional distributions is available, using Gibbs Sampling one would perform
%the following:
%\begin{hlevel}{Gibbs Sampling}
%    
%    \hskip 0.1cm 1. Randomly initialize each $x_i$
%    
%    \hskip 0.1cm 2.    For $t = 1,\ldots,T:$
%    
%    \hskip 0.3cm 2.1. $x_{1}^{t+1} \sim p(x_1 \mid x_{2}^{(t)},x_{3}^{(t)} \ldots,x_{m}^{(t)})$
%
%    \hskip 0.3cm 2.2. $x_{2}^{t+1} \sim p(x_2 \mid x_{1}^{(t+1)},x_{3}^{(t)} \ldots,x_{m}^{(t)})$
%
%    \hskip 0.3cm 2.m. $x_{m}^{t+1} \sim p(x_m \mid x_{1}^{(t+1)},x_{2}^{(t+1)} \ldots,x_{m-1}^{(t+1)})$        
%\end{hlevel}
%This procedure is repeated a number of times until the samples begin to converge to what would be sampled from the true distribution. While convergence is theoretically guaranteed with Gibbs Sampling, there is no way of knowing how many iterations are required to reach the stationary distribution. Therefore, diagnosing convergence is a real problem with the Gibbs Sampling approximate inference method. However, in practice it is quite powerful and has fairly good performance. Typically, an acceptable estimation of convergence can be obtained by calculating the log-likelihood or even, in some situations, by inspection of the posteriors.

For LDA, we are interested in the proportions of the topic in a document represented by the latent variable $\theta_d$, the topic-word distributions $\phi^{(z)}$, and the topic index assignments for each word $z_i$. While conditional distributions - and therefore an LDA Gibbs Sampling algorithm - can be derived for each of these latent variables, we note that both $\theta_d$ and $\phi^{(z)}$ can be calculated using just the topic index assignments $z_i$ (i.e. z is a sufficient statistic for both these distributions). Therefore, a simpler algorithm can be used if we integrate out the multinomial parameters and simply sample $z_i$. This is called a collapsed Gibbs sampler \cite{griffiths_finding_2004,steyvers_probabilistic_2007}.

The collapsed Gibbs sampler for LDA needs to compute the probability of a topic z being assigned to a word $w_i$, given all other topic assignments to all other words. Somewhat more formally, we are interested in computing the following posterior up to a constant:
\begin{equation}
    p(z_i\mid z_{-i},\alpha,\beta,w)
\end{equation}
where $z_{-i}$ means all topic allocations except for $z_i$.

\begin{algorithm}
           \caption{The LDA Gibbs sampling algorithm. 
        \label{Algorithm1_LDAGibbsSampling}}
            \scriptsize 
                \algloop{Loop}
                \algblock{Begin}{End}
                \begin{algorithmic}[1]
                    \Require  words $ w \in $ corpus $\mathcal{D}=(d_1,d_2,\ldots,d_M)$ 
                    \Procedure{LDA-Gibbs}{$w$, $\alpha$, $\beta$, $T$}
                    \State randomly initialize z and increment counters
                    \Loop{ for each iteration}
                    \Loop{ for each word w in corpus $\mathcal{D}$}
                    \Begin
                    \State word $\gets  w[i]$
                    \State tp $\gets  z[i]$
                    \State $n_{d,tp}-=1; n_{word,tp}-=1; n_{tp}-=1$
                    \Loop{ for each topic j $\in \{0,\ldots, K-1\}$}
                    \State compute $P(z_{i} = j | z_{-i},w) $                             \State $tp \gets  sample \quad from \quad p(z | .)$
                    \State   $z[i] \gets  tp$
                    \State $n_{d,tp}+=1; n_{word,tp}+=1; n_{tp}+=1$
                    \End            
                    \State Compute  $\phi^{(z)}$
                    \State Compute  $\theta_d$
                    \State \Return $z,\phi^{(z)}, \theta_{\mathcal{D}}$ \Comment{Output}
                    \EndProcedure
                \end{algorithmic}
    \end{algorithm}
    %is used for the computation of the posterior distribution of the model. 
            %The computation will give us in the output the following : The latent document-topic proportions $\theta_{d}$, the topic-word distribution $\phi^{(z)}$, and the topic index assignments $z_{i}$ for each word. $\theta_{d}$ and $\phi^{(z)}$ are calculated using the topic assignments $z_{i}$ as it is shown in equations 11 and 12.
    Equation \ref{eq_posterior} shows how to compute the posterior distribution for topic assignment. 
    \begin{equation} \label{eq_posterior}
        P(z_{i} = j | z_{-i},w) \propto \frac{n_{-i,j}^{w_{i}} + \beta}{n_{-i,j}^{(\cdot)} + V\beta} \frac{n_{-i,j}^{d_{i}} + \alpha}{n_{-i, \cdot}^{d_{i}} + K\alpha}
    \end{equation}
    where $n_{-i,j}^{w_{i}}$ is the number of times word $w_{i}$ was related to topic $j$. $n_{-i,j}^{(\cdot)}$ is the number of times all other words were related with topic $j$. $n_{-i,j}^{d_{i}}$ is the number of times topic $j$ was related with document $d_{i}$. The number of times all other topics were related with document $d_{i}$ is annotated with $n_{-i, \cdot}^{d_{i}}$. Those notations were taken from the work of Thomas Griffiths and Mark Steyvers  \cite{griffiths_finding_2004}. 
    
    \begin{equation}\label{eq_phi} 
        \hat{\phi}_{j}^{(w)} = \frac{n_{j}^{(w)} + \beta}{n_{j}^{(\cdot)} + V\beta}
    \end{equation}
    \begin{equation}\label{eq_theta}
        \hat{\theta}_{j}^{(d)} = \frac{n_{j}^{(d)} + \alpha}{n_{\cdot}^{(d)} + K\alpha}
    \end{equation}
    Equation  \ref{eq_phi} is the Bayesian estimation of the distribution of the words in a topic. Equation \ref{eq_theta} is the estimation of the distribution of topics in a document.
    
\section{Pretopology Theory}

The Pretopology is a mathematical modeling tool for the concept of proximity. It was first developed in the field of social sciences for analyzing discrete spaces \cite{belmandt_basics}. The Pretopology establishes powerful tools for conceiving a process to structure the space and infer the number of clusters for example. This is made possible by ensuring a follow-up of the process development of dilation, alliance, adherence, closed subset and acceptability \cite{le_new,mdvicmb}.


\subsection{Pseudoclosure }
Let consider a nonempty set $E$ and $\mathcal{P}(E)$ which designates all the subsets of $E$.
\begin{mydef}
   A pseudoclosure $a(.)$ is a mapping from $\mathcal{P}(E)$ to $\mathcal{P}(E)$, which satisfies following two conditions:
    \begin{equation} 
        a(\emptyset) = \emptyset;  \forall A \subset E, A \subset a(A)  
    \end{equation}
\end{mydef}
A pretopological space  $(E,a)$ is a set $E$ endowed with a pseudoclosure function $a.()$.

Subset $a(A)$ is called the pseudoclosure of A. As $a(a(A))$ is not necessarily equal to a(A), a sequential appliance of pseudoclosure on A can be used to model expansions: $A \subset a(A) \subset a(a(A))=a^2(A) \subset \ldots \subset a^k(A)$

\begin{mydef}
    Let $(E, a)$ a pretopological space, $\forall A, A \subset E$. A is a closed subset if and only if  $a(A) = A$.    
\end{mydef}
\begin{mydef}
    Given a pretopological space $(E, a)$, call the closure of A, when it exists, the smallest closed subset of (E, a) which contains A. The closure of A is denoted by $F(A)$.
\end{mydef} 
\begin{figure}
\label{fig:closure_example}
\centering
\includegraphics[scale=0.35]{pseudoclosure_example.png}
\caption{Iterated application of the pseudoclosure map leading to the closure.}
\end{figure}

\textbf{Remark:} 
\begin{itemize}
\item $F(A)$ is the intersection of all closed subsets which contain A. In the case where (X, a) is a “general” pretopological space, the closure may not exist.
\item Closure is very important because of the information it gives about the “influence” or “reachability” of a set, meaning, for example, that a set $A$ can influence or reach elements into $F(A)$, but not further (see Figure 2).
\end{itemize}

Hence, it is necessary to build a pretopological spaces in which the closure always exists. $V$-type pretopological spaces are the most interesting cases.

\begin{mydef}
    A Pretopology space $(E,a)$ is called $\mathcal{V}$-type space if and only if
    \begin{equation} 
        \forall A \subset E, \forall B \subset E, (A \subset B) \Rightarrow (a(A) \subset a(B)) 
    \end{equation}
\end{mydef}
\begin{mypropo}
    In any pretopological space of type $V$, given a subset $A$ of $E$, the closure of $A$ always exists.
\end{mypropo}

The other reason why we use the spaces of type $V$ is that we can build them from a family of reflexive binary relations on the finite set $E$. That thus makes it possible to take various points of view (various relations) expressed in a qualitative way to determine the pretopological structure placed on $E$. So, it can be applied on multi-criteria clustering or multi-relations networks. 

\subsection{Pretopology and binary relationships}

Suppose we have a family $(R_i)_{i=1,\ldots,n}$ of binary reflexive
relationships on a finite set E. Let us consider $\forall i =1,2,\ldots,n, \forall x \in E, V_i(x)$  defined by:
\begin{equation} 
    V_i(x) = \{ y \in E | x \, R_i \, y \}
\end{equation}

Then, the pseudoclosure $a_s(.)$ is defined by:  
\begin{equation} \label{eq:aAstrong}
    a_{s}(A) = \{ x \in E | \forall i=1,2,\ldots, n, V_i(x) \cap A \neq \emptyset \} 
\end{equation}

Pretopology defined on $E$ by $a_s(.)$  using the intersection operator is called the strong Pretopology induced by the family $(R_i)_{i=1,\ldots,n}$.

Similarly, we can define weak Pretopology from ${a_w}(.)$ by using the union operator: 

\begin{equation} \label{eq:aAweak}
    a_{w}(A) = \{ x \in E | \exists i=1,2,\ldots, n, V_i(x) \cap A \neq \emptyset \} 
\end{equation}

\begin{mypropo}
    $a_s(.)$ and $a_w(.)$ determine on $E$ a pretopological structure and the spaces $(E,a_s)$, $(E,a_w)$ are of $V$-type.
\end{mypropo}

\subsection{Minimal closed subsets}
We denote $\mathcal{F}_e$ as the family of elementary closed subsets, the set of closures of each singleton $\{x\}$ of $P(E)$. So in a $V$-type pretopological space, we get: 
\begin{itemize}
\item[-] $\forall x \in E, \exists F_x:$ closure of $\{x\}$. 
\item[-] $\mathcal{F}_e=\{F_x|x \in E\}$
\end{itemize}

\begin{mydef}
    $F_{min}$ is called a minimal closed subset if and only
    if $F_{min}$ is a minimal element for inclusion in $\mathcal{F}_e$.
\end{mydef}
We denote $\mathcal{F}_m=\{F_{m_j},j=1,2,\ldots,k\}$, the family of minimal closed subsets, the set of minimal closed subsets in $\mathcal{F}_e$. 

\section{Our Approach}

In our approach, we build The Method of Clustering Documents using Pretopology and Topic Modeling (MCPTM)  which clusters documents via Topic Modeling and pseudoclosure. MCPTM can be built by: 
\begin{enumerate}
\item Defining the topic-distribution of each document $d_i$ in corpus $\mathcal{D}$ by document structure analysis using LDA.
\item Defining two binary relationships: $R_{MTP}$ based on major topic and $R_{d_H}$ based on Hellinger distance. 
\item Building the pseudoclosure function from two binary relationships $R_{MTP},R_{d_H}$.
\item Building the pseudoclosure distance from pseudoclosure function.
\item Determining initial parameters for the k-means algorithm from results of minimal closed subsets.
\item Using the \emph{k-means} algorithm to cluster sets of documents with initial parameters from the result of minimal closed subsets, the pseudoclosure distance to compute the distance between two objects and the inter-pseudoclosure distance to re-compute the new centroids.
\end{enumerate}

\subsection{Document structure analysis by LDA}
A term-document matrix is given as an input to LDA and it outputs two matrices:
\begin{itemize}
\item The document-topic distribution matrix $\theta$.
\item The topic-term distribution matrix $\phi$.
\end{itemize}
The topic-term distribution matrix $\phi \in \mathbf{R}^{K \times V}$ consists of $K$ rows, where the \textit{$i$}-th row $\phi_i \in \mathbf{R}^V$ is the word distribution of topic \textit{$i$}. The terms with high $\phi_{ij}$ values indicate that they are the representative terms of topic \textit{$i$}. Therefore, by looking at such terms one can grasp the meaning of each topic without looking at the individual documents in the cluster.

In a similar way, the document-topics distributions matrix $\theta \in \mathbf{R}^{M \times K}$ consists of $M$ rows, where the \textit{$i$}-th row $\theta_i \in \mathbf{R}^K$ is the topic distribution for document \textit{$i$}. A high probability value of $\theta_{ij}$ indicates that document \textit{$i$} is closely related to topic \textit{$j$}. In addition, documents with low $\theta_{ij}$ values over all the topics are noisy documents that belong to none of the topics. Therefore, by looking at the $\theta_{ij}$ values, one can understand how closely the document is related to the topic. 

\subsection{Defining binary relationships} 

By using LDA, each document may be characterized by its topic distribution and also be labeled by the topic with the highest probability. In this subsection, we use this information to define the relations between two documents based on the way we consider the "similarity" between them. 

\subsubsection{Based on major topic}
Firstly, based on the label information, we can consider connecting the documents if they have the same label. However, in some cases such as noisy documents, the probability of label topic is very small and it is not really good if we use this label to represent a document. Hence, we just use the label information if its probability is higher than threshold $p_0$. We define the major topic of each document as: 

\begin{mydef}
    $MTP(d_i)$ is the major topic of document $d_i$ if $MTP(d_i)$ is the topic with highest probability in the topic distribution of document $d_i$ and this probability is greater than threshold $p_0$, $p_0 \geq 1/K$, K is the number of topic.\\
    $MTP(d_i)=\{k | \theta_{ik}=max_j \theta_{ij} \quad and \quad \theta_{ik} \geq p_0\}$.
\end{mydef}

Considering two documents $d_{m}$,$d_{n}$ with their major topic $MTP(d_{m})$, $MTP(d_{n})$, we see that document $d_{m}$ is close to document $d_{n}$ if they have the same major topic. So, we proposed a definition of binary relationship  $R_{MTP}$ of two documents  based on their major topic as: 

\begin{mydef}
    Document $d_{m}$  has binary relationship $R_{MTP}$  with document $d_{n}$  if $d_{m}$ and $d_{n}$ have the same major topic.
\end{mydef}

\subsubsection{Based on Hellinger distance}
Secondly, we can use the topic distributions of documents to define the relation based the similarity between two real number vectors or two probability distributions. If we consider a probability distribution as a vector, we can choose some distances or similarity measures related to the vector distance such as Euclidean distance, Cosine Similarity, Jaccard Coefficient, Pearson Correlation Coefficient, etc. But, it is better if we choose distances or similarity measures related to the probability distribution such as Kullback-Leibler Divergence, Bhattacharyya distance, Hellinger distance, etc. We choose the Hellinger distance because it is a metric for measuring the deviation between two probability distributions, easily to compute and especially limited in $[0,1]$. 

\begin{mydef}
\label{def:hellinger}
    For two discrete probability distributions $P=(p_1, \ldots, p_k)$ and $Q=(q_1, \ldots, q_k)$, their Hellinger distance is defined as
    \begin{equation}
    d_H(P, Q) = \frac{1}{\sqrt{2}} \; \sqrt{\sum_{i=1}^k (\sqrt{p_i} - \sqrt{q_i})^2},
    \end{equation}
\end{mydef}
The Hellinger distance is directly related to the Euclidean norm of the difference of the square root vectors, i.e.
\begin{equation*}
d_H(P, Q) = \frac{1}{\sqrt{2}} \; \bigl\|\sqrt{P} - \sqrt{Q} \bigr\|_2 .
\end{equation*}

The Hellinger distance satisfies the inequality of $0 \leq d_H \leq 1$. This distance is a metric for measuring the deviation between two probability distributions. The distance is 0 when $P=Q$. Disjoint $P$ and $Q$ shows the maximum distance of 1. 

The lower the value of the Hellinger distance, the smaller the deviation between two probability distributions. So, we can use the Hellinger distance to measure the similarity between two documents $d_{m}$,$d_{n}$. We then define the binary relationship $R_{d_{H}}$ between two documents as:   
\begin{mydef}
    Document $d_{m}$  has binary relationship $R_{d_{H}}$  with document $d_n$  if $d_H(d_m,d_n) \leq d_0, 0\leq d_0 \leq 1$, $d_0$ is the accepted threshold.
\end{mydef}

\subsection{Building pseudoclosure function}

Based on two binary relationships $R_{MTP}$ and  $R_{d_H}$, we can build the neighborhood basis (see. Algorithm \ref{Algorithm2_BasisNeighborhood}) and then build the pseudoclosures (see Algorithm  
\ref{Algorithm3_pseudoclosure}) for strong (with intersection operator) and weak (with union operator) Pretopology. 

\begin{algorithm}
        \caption{Neighborhood Basis Using Topic Modeling.}\label{Algorithm2_BasisNeighborhood}
            \scriptsize
                \algloop{Loop}
                \algblock{Begin}{End}
                \algloopdefx{If}[1]{\textbf{If} #1 \textbf{then}}
                \begin{algorithmic}[1]
                    \Require  document-topic distribution matrix $ \theta$, corpus $\mathcal{D}$ 
                    \Require $R_{MTP},R_{d_H} $: family of relations.
                    \Procedure{Neighborhood-TM}{$\mathcal{D},\theta,R_{MTP},R_{d_H}$} 
                    \Loop{ for each relation $R_i \in \{R_{MTP},R_{d_H}\} $}
                    \Loop{ for each document $d_m \in \mathcal{D}$} 
                    \Loop{ for each document $d_n \in \mathcal{D}$} 
                    
                    \If{$R_i(d_m,d_n)$}
                    \State $B_i[d_m].append(d_n)$
                    
                    \State \Return  $B=[B_1,B_2]$ \Comment{Output}
                    \EndProcedure
                \end{algorithmic}
    \end{algorithm}
    
    \begin{algorithm}
                \caption{Pseudoclosure using Topic Modeling.}\label{Algorithm3_pseudoclosure}
                \scriptsize
                    \algloop{Loop}
                    \algblock{Begin}{End}
                    \algloopdefx{If}[1]{\textbf{If} #1 \textbf{then}}
                    \begin{algorithmic}[1]
                        \Require $B=(B_1,B_2),\mathcal{D}=\{d_1,\ldots,d_M\}$ 
                        \Procedure{pseudoclosure}{$A,B,\mathcal{D}$}
                        \State aA=A 
                        \Loop{ for each document $d_n \in \mathcal{D}$}
                        \If {$(A \cap B_1[d_n] \neq \emptyset \quad or \quad A \cap B_2[d_n] \neq \emptyset)$}
                        \State $aA.append(d_n)$
                        \State \Return $aA$ \Comment{Ouput}
                        \EndProcedure
                    \end{algorithmic}
        \end{algorithm}

\subsection{Building pseudoclosure distance}
In standard \emph{k-means}, the centroid of a cluster is the average point in the multidimensional space. Its coordinates are the arithmetic mean for each dimension separately over all the points in the cluster which are not effective with categorical data analysis. On the other hand, the pseudoclosure distance is used to examine the similarity using both numeric and categorical data. Therefore, it can contribute to improving the classification with k-means. 
\begin{mydef}
\label{def:pseudoD}
    We define  $\delta(A,B)$ pseudoclosure distance between two subsets A and B of a finite set E: 
    \begin{itemize}
        \item[] $k_0= \min( \min\{k | A \subset a^k(B)\}, \infty )$ 
        \item[] $k_1= \min( \min\{k | B \subset a^k(A)\}, \infty)$ 
        \item[] $\delta(A,B) = \min(k_0,k_1)$ 
    \end{itemize}
    where  $a^{k}(.) = a^{k-1}(a(.))$ 
\end{mydef}
\begin{mydef}
\label{def:pseudoDint}
    We call $D_A(x)$ interior-pseudo-distance of a point x in a set A: 
    \begin{equation*}
    D_A(x)=\frac{1}{|A|}\sum_{y \in A}\delta(x,y).
    \end{equation*}
\end{mydef}

In case where $A$ and $B$ are reduced to one element $x$ and $y$, we get the distance $\delta(x,y)$. For clustering documents with k-means algorithm, we use the pseudoclosure distance $\delta(x,y)$ to compute distance between two documents (each document represented by its topic distribution is a point $x \in E$) and the interior-pseudo-distance $D_A(x)$ to compute centroid of $A$ ($x_0$ is chosen as centroid of $A$ if $D_A(x_0)=min_{x \in A}D_A(x)$). 

\subsection{Structure analysis with minimal closed subsets}
The two limits of the standard \emph{k-means} algorithm are the number of clusters which must be predetermined and the randomness in the choice of the initial centroids of the clusters. Pretopology theory gives a good solution to omit these limits by using the result from minimal closed subsets. The algorithm to compute minimal closed subset is presented in algorithm \ref{Algorithm4_minimal_closed_subset}. 

\begin{algorithm}
\caption{Minimal closed subsets algorithm.}\label{Algorithm4_minimal_closed_subset}
    \scriptsize
            \algloop{Loop}
            \algblock{Begin}{End}
            \algloopdefx{If}[1]{\textbf{If} #1 \textbf{then}}
            \begin{algorithmic}[1]
                \Require corpus $\mathcal{D}$, pseudoclosure $aA()$ 
                \Procedure{minimal-closed-subsets}{$\mathcal{D}, aA()$}
                    \State compute family of elementary closed subsets $\mathcal{F}_e$ 
                    \State $\mathcal{F}_m=\emptyset$
                    \Loop { until $\mathcal{F}_e = \emptyset$}
                        \Begin
                            \State Choose $F \subset \mathcal{F}_e$
                            \State $\mathcal{F}_e=\mathcal{F}_e - F$
                    
                            \State minimal = True
                            \State  $\mathcal{F}=\mathcal{F}_e$
                    
                            \Loop { until $\mathcal{F} = \emptyset$ and  not minimal}
                                \Begin
                                \State Choose  $G \in \mathcal{F} $
                                \If {$G \subset F$}
                                \State minimal=False
                                \State Else \If {$F \subset G$}
                                \State $\mathcal{F}_e = \mathcal{F}_e -\{G\}$
                                \State $\mathcal{F}=\mathcal{F}-G$
                                \End
                    \End
                \If {minimal =True  $ \&\& F \notin \mathcal{F}_m$}
                \State $\mathcal{F}_m=\mathcal{F}_m \cup F$
                \State \Return $\mathcal{F}_m$ \Comment{Ouput}
                \EndProcedure
            \end{algorithmic}

\end{algorithm} 

By performing the minimal closed subset algorithm, we get the family of minimal closed subsets. This family, by definition, characterizes the structure underlying the data set $E$. So, the number of minimal closed subsets is a quite important parameter: it gives us the number of clusters to use in the \emph{k-means} algorithm. Moreover, the initial centroids for starting the \emph{k-means} process can be determined by using the interior-pseudo-distance for each minimal closed subset $F_{m_j} \in \mathcal{F}_m$ ($x_0$ is chosen as centroid of $F_{m_j}$ if $D_{F_{m_j}}(x_0)=min_{x \in F_{m_j}}D_{F_{m_j}}(x)$).

\subsection{MCPTM algorithm}
In this subsection, we present The Method of Clustering Documents using Pretopology and Topic Modeling (MCPTM)  which clusters documents via the Topic Modeling and pseudoclosure. At first, an LDA Topic Modeling is learned on the documents to achieve topic-document distributions. The major topic and Hellinger probability distance are used to define relations between documents and these relations are used to define a pretopological space which can be employed to get preliminarily clusters of a corpus and determine the number of clusters. After that, k-means clustering algorithm is used to cluster the documents data with pseudodistance and inter-pseudodistance. The MCPTM algorithm is presented in algorithm \ref{Algorithm5_MCPTM}. 

\begin{algorithm}
    \caption{The MCPTM algorithm: clustering documents using Pretopology and Topic Modeling.}\label{Algorithm5_MCPTM}
    \scriptsize
    \begin{algorithmic}[1]
        \Require  $\mathcal{D}$: corpus from set of documents 
        \Procedure{MCPTM}{$\mathcal{D}$}
        \State $\theta_{\mathcal{D}} \gets$ LDA-GIBBS($\mathcal{D}$, $\alpha$, $\beta$, $T$)
        \State $B \gets$ NEIGHBORHOOD-TM($\mathcal{D},\theta_{\mathcal{D}}$, $R_{MTP}$, $R_{d_H}$)
        \State $aA \gets$ pseudoCLOSURE($B$)
        \State $\mathcal{F}_m \gets$ MIMINAL-CLOSED-SUBSETS($\mathcal{D}$, $aA()$)
        \State $k = |\mathcal{F}_m|$: number of clusters 
        \State $ M = \{m_i\},_{i=1,\ldots,k}, m_i = Centroid(F_{m_i})$
        \While {clusters centroids changed}
        \For {each x $\in E-M$}
        \State compute $\delta(x,m_i),i=1,\ldots,k $
        \State   find $m_0$ with $\delta(x,m_0) = min \delta(x,m_i)_{i=1,\ldots,k}$
        \State $F_{m_0}=F_{m_0} \cup \{x\}$
        \EndFor 
        \State Recompute clusters centroids M.
        \EndWhile
        
        \State \Return {$Clusters=\{F_1,F_2,\ldots,F_k\}$} \Comment{Output}
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\subsection{Implementation in python of the library AMEUR}    
In this part, we briefly present our \textit{AMEUR} library written in python. \textit{AMEUR} is a project connecting the tools that come from the framework of Pretopology, Topic Modeling, multi-relations networks analysis and semantic relationship. The library is composed of the following modules: \emph{Pretopology}, \emph{topicmodeling} and \emph{nlp}.
                
The \emph{Pretopology} module implements the functions described in section III. The implementation of the Pretopology in the \textit{AMEUR} library allows us to ensures the follow-up of step-by-step processes like dilatation, alliance, pseudoclosure, closure, family of minimal closed subsets, MCPTM and acceptability in multi-relations networks. 
                
The \emph{topicmodeling} module implements generative models like the Latent Dirichlet Allocation, LDA Gibbs Sampling that allows us to capture the relationships between discrete data. This module is used within the \textit{AMEUR} library for querying purposes e.g to retrieve a set of documents that are relevant to a query document or to cluster a set of documents given a latent topic query. These computations of these queries are ensured by the connection between the \emph{topicmodeling} module and the \emph{Pretopology} module. 
                
The \emph{nlp} (natural language processing) module implements the necessary functions for getting unstructured text data of different sources from web pages or social medias and preparing them as proper inputs for the algorithms implemented in other modules of the library. 
                
\section{Application and Evaluation}

\begin{table*}[!t]
    \scriptsize
    \caption{Words - Topic distribution $\phi$  and the related users from the $\theta$ distribution}
    \label{table_words_topic}
    \centering
    %\begin{tabular}{|p{1.1cm}|p{0.5cm}||p{1.7cm}|p{0.3cm}|p{0.5cm}|}
    \begin{tabular}{lllll}
        \hline
        \multicolumn{5}{c}{\bfseries Topic 3}\\
        \hline
        \bfseries Words & \bfseries Prob. & \bfseries Users & \bfseries ID &\bfseries Prob.\\
        \hline
        paris & 0.008 & GStephanopoulos & 42 & 0.697\\
        
        charliehebdo & 0.006 & camanpour & 23 & 0.694\\
        
        interview & 0.006 & AriMelber & 12 & 0.504\\
        
        charlie & 0.005 & andersoncooper & 7 & 0.457\\
        
        attack & 0.005 & brianstelter & 20 & 0.397 \\
        
        warisover & 0.004 & yokoono & 131 & 0.362\\
        
        french & 0.004 & piersmorgan & 96 & 0.348\\
        
        today & 0.004 & maddow & 72 & 0.314\\
        
        news & 0.004 & BuzzFeedBen & 21 & 0.249\\
        
        police & 0.003 & MichaelSteele & 81 & 0.244\\
        \hline
    \end{tabular}
    \begin{tabular}{lllll}
        \hline
        \multicolumn{5}{c}{\bfseries Topic 10}\\
        \hline
        \bfseries Words & \bfseries Prob. & \bfseries Users & \bfseries ID &\bfseries Prob.\\
        \hline
        ces & 0.010 & bxchen & 22 & 0.505\\
        
        people & 0.007 & randizuckerberg & 102 & 0.477\\
        
        news & 0.006 & NextTechBlog & 88 & 0.402\\
        
        media & 0.006 & lheron & 71 & 0.355\\ 
        
        tech & 0.006 & LanceUlanoff  & 68 & 0.339\\
        
        apple & 0.006 & MarcusWohlsen & 74 & 0.339\\
        
        facebook & 0.005 & marissamayer & 76 & 0.334\\
        
        yahoo & 0.005 & harrymccracken & 43 & 0.264\\
        
        app & 0.005 & dens & 33 & 0.209\\
        
        google & 0.004 & nickbilton & 89 & 0.204\\
        \hline
    \end{tabular}
%    \begin{tabular}{|c|c|}
%        \hline
%        \multicolumn{2}{|c|}{\bfseries Topic 16}\\
%        \hline
%        \bfseries Words & \bfseries Prob.\\ %& \bfseries Users & \bfseries ID &\bfseries Prob.\\
%        \hline %\hline
%        god & 0.012 \\ %& Pontifex & 99 & 0.647\\
%        \hline
%        love & 0.009\\ %& - & -& -\\
%        \hline
%        life & 0.007\\ % & - & -& -\\
%        \hline
%        people & 0.006\\ % & - & -& -\\
%        \hline
%        give & 0.005\\ % & - & - &-\\
%        \hline
%        true & 0.005 \\ %& - & - &-\\
%        \hline
%        world & 0.005\\ % & - & - &-\\
%        \hline
%        lord & 0.004 \\ %& - & - &-\\
%        \hline
%        jesus & 0.004 \\ %& - & - &-\\
%        \hline
%        work & 0.004 \\ %& - & - &-\\
%        \hline
%    \end{tabular}
%    \begin{tabular}{|c|c|}
%        \hline
%        \multicolumn{2}{|c|}{\bfseries Topic 18}\\
%        \hline
%        \bfseries Words & \bfseries Prob.\\ %& \bfseries Users & \bfseries ID &\bfseries Prob.\\
%        \hline %\hline
%        love & 0.031 \\ %& Pontifex & 99 & 0.647\\
%        \hline
%        great & 0.016\\ %& - & -& -\\
%        \hline
%        happy & 0.014\\ % & - & -& -\\
%        \hline
%        day & 0.014\\ % & - & -& -\\
%        \hline
%        book & 0.011\\ % & - & - &-\\
%        \hline
%        time & 0.009 \\ %& - & - &-\\
%        \hline
%        hope & 0.009\\ % & - & - &-\\
%        \hline
%        good & 0.007 \\ %& - & - &-\\
%        \hline
%        today & 0.007 \\ %& - & - &-\\
%        \hline
%        birthday & 0.006 \\ %& - & - &-\\
%        \hline
%    \end{tabular}
\end{table*}

\begin{table*}[!t]
    \scriptsize
    \caption{Topics - document  distribution  $\theta$  }
    \label{table_topic_doc_dis}
    \centering
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 02}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        10 & 0.090\\
        
        16 & 0.072\\
        
        12 & 0.065\\
        
        18 & 0.064\\ 
        
        0 & 0.058\\
        \hline
    \end{tabular}
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 12}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        3 & 0.504\\
        
        19 & 0.039\\
        
        10 & 0.036\\
        
        15 & 0.035\\ 
        
        13 & 0.032\\
        \hline
    \end{tabular}
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 22}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        10 & 0.506\\
        
        3 & 0.036\\
        
        19 & 0.034\\
        
        14 & 0.031\\ 
        
        4 & 0.03\\
        \hline
    \end{tabular}
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 53}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        17 & 0.733\\
        
        1 & 0.017\\
        
        18 & 0.016\\
        
        13 & 0.016\\ 
        
        11 & 0.015\\
        \hline
    \end{tabular}
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 75}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        19 & 0.526\\
        
        2 & 0.029\\
        
        3 & 0.029\\
        
        5 & 0.028\\ 
        
        105 & 0.028\\
        \hline
    \end{tabular}
    \begin{tabular}{ll}
        \hline
        \multicolumn{2}{c}{\bfseries User ID 83}\\
        \hline
        \bfseries Topic &\bfseries Prob.\\
        \hline
        8 & 0.249\\
        
        0 & 0.084\\
        
        11 & 0.06\\
        
        7 & 0.045\\ 
        
        12 & 0.043\\
        \hline
    \end{tabular}
%    \begin{tabular}{|c|c|}
%        \hline
%        \multicolumn{2}{|c|}{\bfseries User ID 115}\\
%        \hline
%        \bfseries Topic &\bfseries Prob.\\
%        \hline\hline
%        18 & 0.151\\
%        \hline
%        6 & 0.060\\
%        \hline
%        11 & 0.060\\
%        \hline
%        0 & 0.058\\ 
%        \hline
%        9 & 0.054\\
%        \hline
%    \end{tabular}
%    \begin{tabular}{|c|c|}
%        \hline
%        \multicolumn{2}{|c|}{\bfseries User ID 132}\\
%        \hline
%        \bfseries Topic &\bfseries Prob.\\
%        \hline\hline
%        0 & 0.144\\
%        \hline
%        16 & 0.076\\
%        \hline
%        12 & 0.070\\
%        \hline
%        18 & 0.057\\ 
%        \hline
%        15 & 0.050\\
%        \hline
%    \end{tabular}
\end{table*}

The microblogging service Twitter has become one of the major micro-blogging websites, where people can create and exchange content with a large audience. In this section, we apply the MCPTM algorithm for clustering a set of users around their interests. We have targeted 133 users and gathered their tweets in 133 documents. We have cleaned them and run the \emph{LDA Gibbs Sampling} algorithm to define the topics distribution of each document and words distribution of each topic. We have used then, the \emph{MCPTM} algorithm to automatically detect the different communities for clustering users. We present in the following, the latter steps in more details. 
\subsection{Data collection}
Twitter is a micro-blogging social media website that provides a platform for the users to post or exchange text messages of 140 characters. Twitter provides an API that allows easy access to anyone to retrieve at most a $1\%$ sample of all the data by providing some parameters. In spite of the $1\%$ restriction, we are able to collect large data sets that contain enough text information for Topic Modeling as shown in \cite{morstatter_is_2013}. 
%We choose the parameters user ID to collect the tweets of a particular user with a public account (e.g. the president of the united states Obama, the pop singer Justin Timberlake, the star of the talk shows Oprah, etc. )
                
The data set contains tweets from the 133 most famous and most followed public accounts. We have chosen these accounts because they are characterized by the heterogeneity of the tweets they posts. The followers that they aim to reach comes from different interest areas (i.e. politics, technology, sports, art, etc..). We used the API provided by Twitter to collect the messages of 140 characters between January and February 2015. We gathered all the tweets from a user into a document.  
\subsection{Data pre-processing}                
Social media data and mainly Twitter data is highly unstructured: typos, bad grammar, the presence of unwanted content, for example, humans expressions (happy, sad, excited, ...), URLs, stop words (the, a, there, ...). To get good insights and to build better algorithms it is essential to play with clean data. The pre-processing step gets the textual data clean and ready as input for the MCPTM algorithm. %The data cleaning comes in several steps (see Fig.9). 
                
%The tweets (a text of 140 characters) usually contains a lot of HTML entities like \&lt; \&gt; \&amp the first step is to get rid of these entities by using the python library \emph{HTMLParser} which convert these entities to standard HTML tags. The second step consist of decoding the data in a standard encoding format e.g. UTF-8 encoding is widely accepted. 
%
%To avoid any disambiguation in the text it is better to maintain a proper structure of the text with a free grammar context. Therefore, the third step consist of converting all the apostrophes into standard lexicons e.g \{('s: is); ('re : are); ('ll : will); ...\}. The MCPTM algorithm analysis the data at a word level we need then to remove the commonly occurring words by creating a long list of those words usually called stop-words. In the remaining steps, we remove punctuations, common words for human expressions and replace the slang words by their actual meaning. Finally, we get rid of the URLs in the tweets. 
                
%We can do most of these steps with the Natural Language Toolkit (NLTK) using the programming language Python. We choose to develop our own toolkit that we incorporated in our \textit{AMEUR} package to get more flexibility with the chooses function and the defined lists and dictionary for cleaning the data. We introduce the \textit{AMEUR} package in the next subsection. 
                
\subsection{Topic Modeling results}

\begin{table}[!t]
    \scriptsize
    
    \caption{Classifying documents based on their major topic}
    \label{table_major_topic}
    \centering
\begin{tabular}{lll}
    \hline  \bf Major Topic& $ \bf prob \geq 0.3$ &  $\bf 0.15 < prob <0.3$  \\ 
    \hline  Topic 0&112,85,104  & - \\ 
      Topic 1&44,129,114 &61  \\ 
      Topic 2&101,108,91  &90  \\ 
      Topic 3&42,23,12,7,20, & 21,81,93,10 \\ 
                 & 131,96,72 & \\
      Topic 4&125,36,123,0  & - \\ 
      Topic 5&82,126  & 62 \\ 
      Topic 6&127,37,26  &92  \\ 
      Topic 7&118,106,32  &70,4  \\ 
      Topic 8&113  &83,55,59  \\ 
      Topic 9&67,122  &111,100  \\ 
      Topic 10&22,102,88,71,74,& 43,89,33,65 \\ 
                   & 68,76 & \\
      Topic 11&54,51,121  &29,94  \\ 
      Topic 12&50  &12  \\ 
      Topic 13&16,35  &38  \\ 
      Topic 14&31,98  & - \\ 
      Topic 15&66,73,34,  &48  \\ 
      Topic 16&99  &-  \\ 
      Topic 17&53,30  &-  \\ 
      Topic 18&47,128,1,124,5  &78,115  \\ 
      Topic 19&14,80,39,75,18,103  &-  \\
    \hline  None &  \multicolumn{2}{c}{\bfseries  remaining users (probability $< 0.15$)}  \\
    \hline 
\end{tabular}
\end{table} 

After collecting and pre-processing data, we obtained data with 133 documents, 158,578 words in the corpus which averages 1,192 words per document and 29,104 different words in the vocabulary. We run LDA Gibbs Sampling from algorithm  \ref{Algorithm1_LDAGibbsSampling} and received the output with two matrices: the document-topic distribution matrix $\theta$ and the distribution of terms in topics represented by the matrix $\phi$. We present in Table \ref{table_words_topic} two topics from the list of 20 topics that we have computed with our LDA implementation. A topic is presented with a distribution of words. For each topic, we have a list of users. Each user is identified with an ID from 0 to 132 and is associated with a topic by an order of probabilities. The two lists of probabilities in topic 3, 10  are extracted respectively from $\theta$ and $\phi$ distributions. The topic 3 and topic 10 are of particular interest due to the important number of users that are related to them. Topic 3 is about the terrorist attack that happened in Paris and topic 10 is about the international Consumer Electronics Show (CES). Both events happened at the same time that we collected our data from Twitter. We note that we have more users for these topics than from other ones. We can conclude that these topics can be considered as hot topics at this moment. 
                
Due to the lack of space, we could not present in details all the topics with their distribution of words and all topic distributions of documents. Therefore, we presented six topic distributions $\theta_i$ (sorted by probability) of six users in the table \ref{table_topic_doc_dis}. A high probability value of $\theta_{ij}$ indicates that document i is closely related to topic j. Hence, user ID 12 is closely related to topic 3, user ID 22 closely related to topic 10, etc. In addition, documents with low $\theta_{ij}$ values over all the topics are noisy documents that belong to none of the topics. So, there is no major topic in user ID 02 (the max probability $< 0.15$). 

We show in Table \ref{table_major_topic} clusters of documents based on their major topics in two levels with their probabilities. The documents with the highest probability less than 0.15 are considered noisy documents and clustered in the same cluster.  

%We present in the next subsection the results of the clustering algorithm that we have developed in our article.             
\subsection{Results from the k-means algorithm using Hellinger distance}
After receiving the document-topic distribution matrix $\theta$ from LDA Gibbs Sampling, we used the k-means algorithm with Hellinger distance to cluster users. The table \ref{table_Hellinger_Cluster} presents the result from the k-means algorithm using Hellinger distance with a number of clusters k=13 and random centroids. Based on the mean value of each cluster, we defined the major topic related to the clusters and attached these values in the table.  We notice that different choices of initial seed sets can result in very different final partitions.
\begin{table}[h]
    \scriptsize

    \caption{\label{table_Hellinger_Cluster} Result from k-means algorithm using Hellinger distance}
    \centering
\begin{tabular}{lll}
    \hline  \bf Cluster& \bf Users  & \bf Major Topic \\ 
    \hline
      1&67, 111, 122  & TP 9 (0.423) \\ 
      2&34, 48, 66, 73  &TP 15 (0.315)  \\ 
      3&10, 22, 33, 43, 65, 68, & TP 10 (0.305)\\
      & 71, 74, 76, 88, 89, 98, & \\ 
      & 102  &  \\
      4&26, 92  &TP 6 (0.268)  \\ 
      5&16, 35, 44, 90, 91, 101,  & TP 2 (0.238) \\
      & 108, 114, 129  &  \\ 
      6&4, 32, 70, 106, 118  &TP 7 (0.345)  \\ 
      7&37, 127  &TP 6 (0.580)  \\ 
      8&14, 18, 39, 75, 80, 103  &TP 19 (0.531)  \\ 
      9&1, 5, 47, 78, 124, 128  &TP 18 (0.453)  \\ 
      10&30, 53  &TP 17 (0.711)  \\ 
      11&7, 12, 20, 21, 23, 42, 72, & TP 3 (0.409)\\
      &  81, 93, 96, 131  &  \\ 
      12&0, 31, 36, 82, 123, 125  &TP 4 (0.310)  \\ 
      13& remaining users  & None  \\ 
    \hline 
\end{tabular}     
\end{table}    

\subsection{Results from the MCPTM algorithm}
\begin{figure}[t!]
    \centering
    \includegraphics[width=0.9\linewidth]{H015-M015}
    \caption{Network for 133 users with two relationships based on Hellinger distance ($distance \leq 0.15$) and Major topic (probability $\geq 0.15$).}
    \label{fig:H015-M015}
\end{figure}
After getting the results (e.g table \ref{table_topic_doc_dis}) from our LDA implementation, we defined two relations between two docements, the first based on their major topic $R_{MTP}$ and the second based their Hellinger distance $R_{d_H}$. We then built the weak pseudoclosure with these relations and applied it to compute pseudoclosure distance and the minimal closed subsets. With this pseudoclosure distance, we can use the MCPTM algorithm to cluster sets of users with multi-relationships. 

\begin{table*}[t]
\scriptsize    
    \caption{\label{table_MCPTM_Cluster} Result from k-means algorithm using Hellinger distance and MCPTM}
    \centering
    \begin{tabular}{lllll}
        \hline
        & \multicolumn{2}{c}{\bfseries K-means \& Hellinger} & \multicolumn{2}{c}{\bfseries MCPTM Algorithm}\\
        
        \bfseries Cluster&\bfseries Users&\bfseries Topic&\bfseries Users&\bfseries Topic\\
        \hline 
        1 &0,36,123,125 &TP 4 (0.457) &0,36,123,125&TP 4 \\
        
        2 &4,32,70,10,118 &TP 7 (0.345)&4,32,70,10,118&TP 7\\
        
        3 &14,18,39,75,80,103&TP 19 (0.531)&14,18,39,75,80,103&TP 19\\
        
        4 &26,37,92,127&TP 6 (0.424)&26,37,92,127&TP 6\\
        
        5 &29,51,54,94,121&TP 11 (0.345)&29,51,54,94,121&TP 11\\
        
        6 &30,53&TP 17 (0.711)&30,53&TP 17\\
        
        7 &31&TP 14 (0.726)&31,98&TP 14\\
        
        8&34,48,66,73&TP 15 (0.315)&34,48,66,73&TP 15\\
        
        9&44,61,114,129&TP 1 (0.413)&44,61,114,129&TP 1\\
        
        10&85,104,112&TP 0 (0.436)&85,104,112&TP 0\\
        
        11&67,90,91,101,108&TP 2 (0.407)&90,91,101,108&TP 2 \\
        
        12&99&TP 16 (0.647)&99&TP 16 \\
        
        13&remaining users&None&remaining users&None\\
        \hline
    \end{tabular}
\end{table*}                

\begin{figure}[h!]
    \centering
    \includegraphics[width=0.4\textwidth]{minimalclosedsubset}
    \caption{Number of elements of Minimal closed subsets with difference thresholds $p_0$ for $R_{MTP}$ and $d_0$ for $R_{d_H}$.}
    \label{fig:minimalclosedsubset}
\end{figure}
Figure \ref{fig:minimalclosedsubset} shows the number of elements of minimal closed subsets with different thresholds $p_0$ for $R_{MTP}$ and $d_0$ for $R_{d_H}$. We used this information to choose the number of clusters. For this example, we chose $p_0 = 0.15$ and $d_0=0.15$ i.e user $i$ connects with user $j$ if they have the same major topic (with probability $ \geq 0.15$) or the Hellinger distance $d_H(\theta_i,\theta_j) \leq 0.15$. From the network (figure \ref{fig:H015-M015}) for 133 users built from the weak pseudoclosure, we chose the number of clusters $k=13$ since the network has 13 connected components (each component represents an element of the minimal closed subset). We used inter-pseudoslosure distance to compute initial centroids and received the result: $$\{0,52,4,14,26,29,30,31,34,44,85,90,99\}$$

Table \ref{table_MCPTM_Cluster} presents the results of the MCPTM algorithm and the \emph{k-means} algorithm using Hellinger distance. We notice that there is almost no difference between the results from two methods when using the number of clusters k and initial centroids above.

We saw that the largest connected component in the users network (fig. \ref{fig:H015-M015}) has many nodes with weak ties. This component represents the cluster 13  with 89 elements. It contains the 8 remaining topics that were nonsignificant or contains noisy documents without major topics. Hence, we used the \emph{k-means} algorithm with Hellinger distance for clustering this group with number of clusters $k=9$, centroids: 
$$\{23,82,113,67,22,50,16,47,2\}$$ 
and showed the result in the table \ref{MCPTM_Cluster2}.
\begin{table}[h]
    \scriptsize
    \caption{\label{MCPTM_Cluster2} Result from k-means algorithm using Hellinger distance for cluster 13 (89 users)}
    \centering
    \begin{tabular}{lll}
        \hline  \bf Cluster & \bf Users  & \bf Major Topic \\ 
        \hline  13.1&7, 12, 20, 21, 23, 42, 72, & TP 3 ( 0.409) \\ 
                 & 81, 93, 96, 131  & \\
          13.2&62, 77, 82, 126  &TP 5 (0.339)  \\ 
          13.3&27, 55, 59, 83, 113  &TP 8 (0.218)  \\ 
          13.4&67, 111, 122  &TP 9 (0.422)  \\ 
          13.5&22, 33, 43, 65, 68, 71, 74, 76, &TP 10 (0.330)  \\ 
                 & 88, 89, 102  & \\
          13.6&50 &TP 12 (0.499)  \\ 
          13.7&16, 35 &TP 13 (0.576)  \\ 
          13.8&1, 5, 47, 78, 124, 128 &TP 18 (0.453)  \\ 
          13.9& remaining users  & None  \\ 
        \hline 
    \end{tabular}     
\end{table}                    

\subsection{Evaluation}
\begin{table*}[t]
\scriptsize
    \caption{\label{Clustering_similarity} The results of the clustering similarity for K-means with different distance measures. The abbreviation  E stands for Euclidean distance, H for Hellinger distance (see definition \ref{def:hellinger}) and P for the pseudoclosure distance (see definition \ref{def:pseudoD} and \ref{def:pseudoDint}).}
    \centering
        \begin{tabular}{lllllllllllll}
    %\begin{tabular}{lclclclclc|c|c|c|c|c|}
        \hline
& \multicolumn{3}{c}{\bfseries Same algorithm}&\multicolumn{3}{c}{\bfseries Same centroids} &\multicolumn{3}{c}{\bfseries Different centroids}&\multicolumn{3}{c}{\bfseries Inter-pseudo centroids}\\        
        
        \bfseries k&\bfseries E &\bfseries H &\bfseries P&\bfseries E vs H&\bfseries E vs P&\bfseries H vs P&\bfseries E vs H &\bfseries E vs P &\bfseries H vs P&\bfseries E vs H &\bfseries E vs P &\bfseries H vs P\\
        \hline 
5 & 0.423 & 0.454 & 0.381 & 0.838 & 0.623 & 0.631 & 0.434 & 0.373 & 0.383 & - & - & -\\ 

9 & 0.487 & 0.544 & 0.423 & 0.831 & 0.665 & 0.684 & 0.495 & 0.383 &0.447& - & - & -\\ 
\hline
13 & 0.567 & 0.598 & 0.405 & 0.855 & 0.615 & 0.633 & 0.546 & 0.445 & 0.469& \bf0.949 & \bf0.922 & \bf0.946\\ 
\hline
17 & 0.645 & 0.658 & 0.419 & 0.861 & 0.630 & 0.641 & 0.641 & 0.493 & 0.518& - & - & -\\ 

21 & 0.676 & 0.707 & 0.445 & 0.880 & 0.581 & 0.604 & 0.687 & 0.478 & 0.491& - & - & -\\ 
 
25 & 0.736 & 0.720 & 0.452 & 0.856 & 0.583 & 0.613 & 0.715 & 0.519 & 0.540& - & - & -\\ 

29 & 0.723 & 0.714 & 0.442 & 0.864 & 0.578 & 0.600 & 0.684 & 0.4885 & 0.511& - & - & -\\ 
\hline
\bf mean &  0.608 & 0.628 & 0.423 &  0.855 &  0.611 & 0.629 & 0.600 & 0.454 & 0.480& \bf 0.949 & \bf0.922 & \bf0.946\\         
        
    \hline     
    \end{tabular}
    %\end{tabular}{lclclclclc|c|c|}
\end{table*}

In this part of the article, we conducted an evaluation of our algorithm  by comparing similarity measure of MCPTM (using the pseudocloseure distance with information from results of minimal closed subsets) and k-means with random choice.  The evaluation is performed as follows: we firstly discovered the similarity measure of k-means using three distances: Euclidean distance, Hellinger distance and pseudoclosure distance; we then compared similarity measures among three distances  and the similarity measure when we use the number of clusters and the initial centroids from the result of minimal closed subsets. We used the similarity measure proposed by \cite{torres_similarity_2009} to calculate the similarity between two clusterings of the same dataset produced by two different algorithms, or even the same K-means algorithm.  This measure allows us to compare different sets of clusters without reference to external knowledge and is called internal quality measure. 

\subsubsection{Similarity measure}
To identify a suitable tool and algorithm for clustering that produces the best clustering solutions, it becomes necessary to have a method for comparing the different results in the produced clusters. To this matter, we used in this article the method proposed by \cite{torres_similarity_2009}.    
    
To measure the "similarity" of two sets of clusters, we define a simple formula here: Let $C = \{C_1, C_2, \ldots, C_m \} $ and $D = \{D_1, D_2, \ldots, D_n \}$ be the results of two clustering algorithms on the same data set. Assume $C$ and $D$ are "hard" or exclusive clustering algorithms where clusters produced are pair-wise disjoint, i.e., each pattern from the dataset belongs to exactly one cluster. Then the similarity matrix for $C$ and $D$ is an $m \times n$ matrix $S_{C,D}$.
\begin{equation}
S_{C,D}=
\begin{bmatrix}
    S_{11}       & S_{12} & S_{13} & \dots & S_{1n} \\
    S_{21}       & S_{22} & S_{23} & \dots & S_{2n} \\
   \dots &  \dots & \dots&  \dots& \dots\\
    S_{m1}       & S_{m2} & S_{m3} & \dots & S_{mn}\\
\end{bmatrix}
\end{equation}

where $S_{ij} = \frac{p}{q}$, which is Jaccard's Similarity Coefficient  with $p$ being the size of the intersection and $q$ being the size of the union of cluster sets $C_i$ and $D_j$. The similarity of clustering $C$ and clustering $D$ is then defined as
\begin{equation}
Sim(C,D) =\frac{\sum_{1\leq i \leq m, 1\leq i \leq m} S_{ij}}{\max(m,n)}
\end{equation}
        
\subsubsection{Discussion}

\begin{figure}[h!]
 \centering
 \includegraphics[scale=0.32]{sameInitial}
 \caption{Illustration of the similarity measure where we have the same initial centroids. The appreviation E stands for Euclidean distance, H for Hellinger distance an P for the pseudoclosure distance.}
 \label{fig:sameInitial}
 \end{figure}
We have compared the similarity measure between three k-means algorithms with different initializations of the centroids and different numbers of clusters $k$. We plotted the similarity measure between the clusters computed with the three \emph{k-means} algorithms with the same initial centroid in Figure \ref{fig:sameInitial} and the three k-means algorithms with different initial centroids in Figure \ref{fig:DInitial}. 
\begin{figure}[h!]
 \centering
 \includegraphics[scale=0.32]{DInitial}
 \caption{Illustration of the similarity measure where we have diffirent initial centroids. The appreviation E stands for Euclidean distance, H for Hellinger distance an P for the pseudoclosure distance.}
  \label{fig:DInitial}
 \end{figure}
  
We notice that in the both figures, the Euclidean Distance and the Hellinger distance have higher similarity measure. This is due to the fact that both distances are similar. In Figure \ref{fig:sameInitial}, we see a big gap between the clusters of Euclidean distance, Hellinger distance and the clusters from Pseuoclosure distance. This gap is closing in Figure \ref{fig:DInitial} and starts opening again from $k=17$. With a different initial centroids the pseudoclosure distance closed the gap between the k-means algorithms using Euclidean and Hellinger distance. But, when $ k > 13$, the number of closed subsets, the gap between the pseudoclosure and the other distances starts opening again. In table \ref{Clustering_similarity} where we applied the same algorithm twice, the similarity measure between two clusters results from k-means is low for all three distances: Euclidean, Hellinger, pseudoclosure distance.  The different choices of initial centroids can result in very different final partitions. 

For k-means, choosing the initial centroids is very important. Our algorithm MCPTM offers a way to compute the centroids based on the analysis of the space of data (in this case text). When we use the centroids computed from the results of minimal closed subsets that we present in Table \ref{table_MCPTM_Cluster}, we have the higher similarity: 0,949 for Euclidean vs Hellinger; 0,922 for Euclidean vs pseudocloure and 0,946 for Hellinger vs pseudoclosure. It means that the results from k-means using the centroids  $\{0,52,4,14,26,29,30,31,34,44,85,90,99\}$ is very similar with all three distances Euclidean, Hellinger, pseudoclosure. We can conclude that the result that we obtained from our MCPTM algorithm is a good result for clustering with this Twitter dataset. 

\section{Conclusion}
The major finding in this article is that the number of clusters and the chosen criterias for grouping the document is closely tied to the with the accuracy of the clustering results. The method presented here can be considered as a pipeline where we associate Latent Dirichlet Allocation (LDA) and pseudoclosure function. LDA is used to estimate the topic-distribution of each document in corpus and the pseudoclosure function to connect documents with multi-relations built from their major topics or Hellinger distance. With this method both quantitative data and categorical data are used, allowing us to have multi-criteria clustering. We have presented our contribution by applying it on microblogging posts and have obtained good results. In future works, we want to test these results on large scale and more conventional benchmark datasets. And we intend also to parallelize the developed algorithms. 

\bibliographystyle{abbrv}
\bibliography{bib_SOICT}

\newpage

\textbf{Appendix}

List of Notations:
%\begin{table}

\begin{tabular}{l|l}
     Notation &  Meaning\\
     \hline
     $K$ & number of topics \\
     $V$ & number of words in the vocabulary\\
     $M$ & number of documents\\
     $M$ & number of documents\\
     $\mathcal{D}$ & corpus\\
     $\phi_{j=1,\ldots,K}$ & distribution of words in topic j\\
     $\theta_{d=1,\ldots,M}$ & distribution of topics in document d\\
     $a(A)$ & pseudoclosure of A\\
     $F(A)$ & closure of A\\
     $\mathcal{F}_e$ & family of elementary closed subset\\
     $\mathcal{F}_m$ & family of minimal closed subset\\
     $\delta(A,B)$ & pseudodistance between A,B \\
     $D_A(x)$ & interior-pseudodistance of x in A \\
     $MTP(d)$ & major topic of document d\\
     $d_H(P,Q)$ & Hellinger distance between $P, Q$\\
     $R_{MTP}$ & relationships based on major topic\\
     $R_{d_H}$ & relationships based on Hellinger distance\\
     $k$ & number of clusters\\
\end{tabular}
%\end{table}
%\nocite{*}
\end{document}