\section*{Graphical Abstract (Optional)}






















\title{DCDistance: A Supervised Text Document Feature extraction based on class labels}

\author{Charles Henrique Porto Ferreira\\
Debora Maria Rossi de Medeiros\\
Fabricio Olivetti de Franca} 

\maketitle
  




\begin{abstract}
Text Mining is a field that aims at extracting information from textual data. One of the challenges of such field of study comes from the pre-processing stage in which a vector (and structured) representation should be extracted from unstructured data. The common extraction creates large and sparse vectors representing the importance of each term to a document. As such, this usually leads to the curse-of-dimensionality that plagues most machine learning algorithms. To cope with this issue, in this paper we propose a new supervised feature extraction and reduction algorithm, named DCDistance, that creates features based on the distance between a document to a representative of each class label. As such, the proposed technique can reduce the features set in more than $99\%$ of the original set. Additionally, this algorithm was also capable of improving the classification accuracy over a set of benchmark datasets when compared to traditional and state-of-the-art features selection algorithms.
\end{abstract}






\section{Introduction}


Many interesting datasets are acquired from textual information such as products review, social network posts, text articles, e-mails, etc. For this reason, Text Mining is an extensively researched topic in Computer Science.

The main goal of Text Mining is to automatically extract information and knowledge from text documents~\citep{book:witten2016dataMining}. Some common tasks associated with Text Mining are classification algorithms (i.e., topic extraction, sentiment analysis, subject)~\citep{KUMAR2016128}, data clustering (i.e., plagiarism detection, summarization)~\cite{WANG201726}, regression analysis (i.e., recommender systems)~\cite{AGUILAR2017147}. Each of these tasks has its own particularities, specific challenges and applications.

There are many Machine Learning algorithms available to perform these tasks, many of them expect that the input is represented as a vector. As such, an important step for Text Mining is the feature extraction and, as we will highlight next, also the feature selection. 

A common approach is the document vectorization as a bag-of-features~\citep{manning2008introduction} in which a document $i$ is first tokenized, usually by words, and a vector $t_i$ is created with each element corresponding to a token. The value of an element $t_{i,j}$ is defined by:

\begin{equation*}
    t_{i,j} = \left\{\begin{matrix}
 w_{i,j} & \text{ if the token } j \text{is present in document } i\\
 0 & \text{ otherwise}
\end{matrix}\right.,
\end{equation*}

\noindent where $w_{i,j}$ is a weighting of the token $j$ in document $i$.

As one may notice, this can potentially lead to very sparse and high-dimensional vectors due to the diversity of tokens in a corpus.

This can be a problem to many Machine Learning algorithms that suffer from the curse-of-the-dimensionality~\citep{book:1643328} and can also increase the computational costs unnecessarily.

As such, different algorithms were proposed in the literature in order to reduce the dimensionality of the features set while either improving the accuracy of the task or minimizing the impact on the accuracy value.





Specifically for the classification task, some of these algorithms use a ranking method to select the most suitable features, also known as filter methods~\citep{article:Rehman20153670,Stanczyk:2014:FSD:2728712}. Another group of algorithms use a classification algorithm to verify efficiency of a set of features. This method is called wrapper~\citep{Stanczyk:2014:FSD:2728712}. 

One disadvantage of the current pre-processing algorithms is the amount of time required to perform the computation of the feature importance or transformation. It is noticed that a significant amount of time of creating a Machine Learning model for Text Mining corresponds to the pre-processing stage~\citep{MUNKOVA20131198}. Another common disadvantage is related to the number of generated or selected features, that is usually a parameter of the algorithm, thus requiring a fine-tuning to find a compromise between dimensionality and accuracy.

In order to alleviate these problems, in this paper, we propose the DCDistance algorithm. This algorithm extract features solely based on the distance between text documents and representative points of each label. 

Simply put, for a dataset with $k$ distinct labels, this algorithm will create a representation for each document as a $k$-dimensional vector $d_i$ with each element $d_{i,j}$ representing the distance of document $i$ to class $j$.

As a result, DCDistance is capable of reducing the dimension of Bag-of-Words representation in more than $99\%$ of the original size. Also, since this representation contains supervised information regarding the class labels, it often helped to improve the classification accuracy for some of the tested datasets when compared to the application of the original features and some other feature reduction techniques.

The remainder of this paper has the following structure. Section \ref{sec:feature_selection_and_extraction} will present some core concepts together with a selection of the most recent work related to this paper. Section \ref{sec:document_class_distance} will present the proposed algorithm in details. Section \ref{sec:experiments} describes the experiments performed to assess the performance of our proposal and the results are presented in Section~\ref{sec:results}. Finally, some final remarks and summary of the obtained results are given in Section~\ref{sec:conclusion_and_future_work}.


\section{Feature Selection and Extraction}\label{sec:feature_selection_and_extraction}

The extraction and further selection of the features play an important role during pre-processing of text documents since they can reduce noise and sparsity which often improves the model accuracy of the task at hand.

Feature selection techniques select a subset of the original features set, choosing the $k$ most relevant features according to a given criteria. For example, two common criteria are the Information Gain of a feature~\citep{Forman20031289} and the Chi-Squared~\citep{manning2008introduction}.

Information Gain measures the amount of information that a feature can provide when used to discriminate between classes. Similarly, the Chi-Squared evaluates the degree of dependency between a feature and a label. The greater the Chi square's score, the greater the dependence of the feature and that specific label.  

Feature extraction techniques, on the other hand, are applied to the original set of features in order to generate a new and more informative set. The objective of these techniques is that the transformed feature space becomes easier to separate by the traditional classification algorithms. 
\subsection{Recent Work}

\cite{UYSAL201682} proposed a feature selection approach named Improved Global Feature Selection(IGFSS) which combine Global Feature Selection(GFS) techniques~\citep{Guyon:2003:IVF:944919.944968} with Local Feature Selection(LFS) techniques~\citep{TasCi:2013:CTF:2479984.2480039}. A GFS algorithm is a filter selection approach that ranks the features w.r.t. the entire dataset and then select the top $k$ features. The Information Gain and Chi-Squared, explained above, are both examples of GFS.

The LFS algorithms rank the features w.r.t. the classes of the dataset, thus, each feature receive a rank based on each class. With this information, it is possible to assign a label to each feature. Odds Ratio~\citep{manning2008introduction,Forman20031289} and Correlation Coefficient are examples of LFS.

The authors argued that the classical GFS techniques not select enough features that belong to each class of the dataset, so they proposed to select an equal number of features from each class using the information acquired with the GFS and LFS approaches. This technique was compared with some classical GFS techniques such as IG, DFS~\citep{Uysal:2012:NPF:2396898.2397010} and Gini Index~\citep{Shang:2007:NFS:1223505.1223633} and overcame them in all of the four tested benchmarks.

\cite{AGNIHOTRI2017268} proposed a feature selection algorithm similar to \cite{UYSAL201682} using GFS and LFS to select features distributed among the classes. However, they argued that an equal number of features per class may not be reasonable because of the imbalance found in class distributions in many datasets. Instead, they select a number of features proportional to the number of samples belonging to each class. This technique was compared with IG, Mutual Information, Gain Ratio, DFS and the state-of-the-art IGFSS. The results showed significant improvements regarding F-micro and F-macro classification.

\section{Document-Class Distance}\label{sec:document_class_distance}

The main contribution of this paper is the proposal of a feature extraction algorithm that compacts the dimensionality of the dataset while maintaining discriminative power for classification tasks.

Basically, a vector of the same size of the number of distinct labels represents each text document. So, the element $d_{i,j}$ represents the distance from the $i$-th text document to a representative vector of the $j$-th class.

The algorithm, named DCDistance, is depicted in Alg.~\ref{alg:dcdistance} and explained further in the following paragraphs.

\begin{algorithm}[ht!]
  \SetKwFunction{vectorize}{vectorize}\SetKwFunction{sum}{sum}\SetKwFunction{filter}{filter}\SetKwFunction{dist}{dist}
  \SetKwFunction{stoplistRemoval}{stoplistRemoval}
  \SetKwFunction{porterStemming}{porterStemming}
  \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
  \Input{train and test text documents $D_{train}$ and $D_{test}$, set of labels $Y_{train}$ and number of distinct labels $k$.}
\Output{vectorial representation $V'_{train}, V'_{test}$}
\BlankLine

\stoplistRemoval{$D_{train}$}\;
\porterStemming{$D_{train}$}\;
$V_{train} \leftarrow$ \vectorize{$D_{train}$}\;
$V_{test} \leftarrow$ \vectorize{$D_{test}$}\;
\For{$i = 1 \dots k$}{
    $Vd[i] \leftarrow$ \sum{\filter{$y==i, (V_{train},Y_{train})$}}\;
}

\For{$i = 1 \dots |V_{train}|$}{
   $V'_{train}[i] \leftarrow$ [\dist{$V_{train}[i]$, Vd$[j]$} $\mid j \leftarrow 1 \dots k$]\;
}
\For{$i = 1 \dots |V_{test}|$}{
   $V'_{test}[i] \leftarrow$ [\dist{$V_{test}[i]$, Vd$[j]$} $\mid j \leftarrow 1 \dots k$]\;
}
\Return $V'_{train}, V'_{test}$\;
\caption{DCDistance algorithm.}
\label{alg:dcdistance}
\end{algorithm}

The algorithm starts with the application of any vectorization algorithm on the corpus data. For example, a Bag-of-Words with TF-IDF weighting. After that, the vectors of the documents corresponding to each label are summed up generating a representative vector of this particular class. Finally, the new vector representation for each document is created by calculating the distance between this document and each representative vector.

Notice that the $dist$ function can be any distance applicable into a multi-dimensional numerical vector. The summing of the representative vectors works as an aggregation of the information contained in each document vector. Also, it should be noticed that the representative vectors are built without the test data information.


Regarding the computational complexity, after the vectorization step, the algorithm performs $O(n \cdot d)$  + $O(p \cdot d)$ operations, with $n$ as the number of documents of the training set, $p$ as the number of documents from the test set and $d$ the dimension of the feature vector generated by the vectorization. The new vector space is created with $O(m \cdot k \cdot d)$ operations, with $m = n+p$ the total number of documents and $k$ the number of distinct class labels. As such, the overall complexity is proportional to $O(m \cdot k \cdot d)$.

\section{Experiments}\label{sec:experiments}

In order to assess whether this representation retains enough information for classification tasks, we have devised an experimentation pipeline as depicted in Fig.~\ref{fig:fluxograma}. In short, we first apply some common pre-processing steps to the text documents such as English stopword removal and Porter Stemming Algorithm~\citep{article:porter1980algorithm}. After that, we tokenized each document and generated a vector representation weighted by TF-IDF such that every position in the vector represents a token from the corpus, and the value of the $i$-th token to the $j$-th document is calculated by:

\begin{equation}
TF-IDF(t_i,d_j) = \\ \left\{\begin{matrix}
f(t_i,d_j) \cdot \log{\frac{N}{|\{d \in D : t_i \in d|\}}}, & \text{if } t_i \in d_j  \\
0, & \text{otherwise}
\end{matrix}\right.,
\end{equation}

\noindent where $f(t,d)$ measures the frequency of a term $t$ in document $d$ and $D$ is the set of all documents.

After that, we have performed a $10$-fold cross-validation in the vectorized dataset and for each combination of train and test we have applied the DCDistance feature extraction algorithm and the others baselines feature selection algorithm as described on algorithm \ref{alg:featureSelection}, thus generating $10$ different train and test transformed data. 

For each one of the training data, we have applied the classifications algorithms Support Vector Machine (SVM)~\citep{weiss2015fundamentals}, $k$-Nearest Neighbors (kNN)~\citep{weiss2015fundamentals} and Random Forest (RF)~\citep{GENUER201728}, all fitted on the training set and evaluated on the test set. 

To measure the performance, we will present the mean classification accuracy, micro-F1 and macro-F1 results on the test data. We compared the results with the TF-IDF vectorization applied to four feature selection algorithms: Information Gain and Chi-squared, IGFSS and VGFSS.

\begin{algorithm}[ht!]
  \SetKwFunction{vectorize}{vectorize}\SetKwFunction{sum}{sum}\SetKwFunction{filter}{filter}
  \SetKwFunction{stoplistRemoval}{stoplistRemoval}
  \SetKwFunction{porterStemming}{porterStemming}
  \SetKwFunction{applyFeatureSelectTechnique}{applyFeatureSelectTechnique}
  \SetKwFunction{selectFeatures}{selectFeatures}
  \SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
  \Input{train and test text documents $D_{train}$ and $D_{test}$}
\BlankLine

\stoplistRemoval{$D_{train}$}\;
\porterStemming{$D_{train}$}\;
$V_{train} \leftarrow$ \vectorize{$D_{train}$}\;
$V_{test} \leftarrow$ \vectorize{$D_{test}$}\;
\applyFeatureSelectTechnique{$V_{train}$}\;
\selectFeatures{$V_{train}$}\;
\selectFeatures{$V_{test}$}\;
\caption{Feature selection process.}
\label{alg:featureSelection}
\end{algorithm}

\begin{figure}[htb]
\resizebox{\columnwidth}{!}{
  \includegraphics{fluxograma.pdf}}
  \caption{Flowchart of the proposed technique. Step 2 and 3 are exemplified with $V_{train}$ to generate $V'_{train}$, but they must be done, again, with $V_{test}$ to generate $V'_{test}$, as showed on \autoref{alg:dcdistance}}
  \label{fig:fluxograma}
\end{figure}

Since these feature selection algorithms require the number of features to be selected as a parameter, we have tested four different input parameters: i) the same number of features created by DCDistance; ii) $20\%$ of the number of features of the vectorized representation; iii) $40\%$ of the number of features of the vectorized representation; iv) $60\%$ of the number of features of the vectorized representation. In the results tables and plots they were labeled as IG1/Chi1/IGFSS1/VGFSS1, IG2/Chi2/IGFSS2/VGFSS2, IG3/Chi3/IGFSS3/VGFSS3, and IG4/Chi4/IGFSS4/VGFSS4, respectively. We parameterized IGFSS using DFS as GFS and Odds Ratio as LFS. VGFSS was parameterized with DFS as GFS and max of IG, GI, DFS and GR as LFS. The tests were performed on four different benchmark datasets from the literature, with their features summarized in Tab.~\ref{tab:datasets}:

\begin{itemize}

\item \textbf{Reuters-21578:} a well know dataset used in text mining applications (\cite{article:Rehman20153670}). We are using the Apte' split of this dataset provided by \cite{site:corpus_reuter_21578}. This division chooses the ten classes with the largest number of texts.

\item \textbf{20Newsgroup:} a corpus containing $7,532$ documents and $65,981$ distinct words extracted from $20$ different newsgroups, with each one representing a different class. This dataset version is available on \cite{site:20newsgroup} web page. We worked only with "by date" version and used the test set as the whole dataset, i.e., divided the test set into test and training set.

\item \textbf{SCY-Genes:} a dataset collected by~\cite{med04,med05} with the abstracts of scientific papers about the genes of \emph{Saccharomyces Cerevisiae}. The documents are classified according to the type of gene studied.

\item \textbf{SCY-Cluster:} the same as the previous corpus but with documents classified by the studied biological function~\citep{med04,med05}.

\end{itemize}


\begin{table}[htb]
  \caption{Characteristics of the benchmark datasets used during the experiments. Words pp. are the number of words after pre-processing stage and Desv. pad is the standard  deviation  of the number of texts within each class}
  \label{tab:datasets}
  \centering
  \resizebox{\columnwidth}{!}{
  \begin{tabular}{llllll}
    \toprule
      \textbf{Datasets}     & \textbf{Classes}  & \textbf{Docs}   & \textbf{Words}  & \textbf{Words pp.} & \textbf{Desv.pad}    \\
      \midrule  
      Reuters-21578 &   10     & 2787    & 13005  & 9041      & 325.37     \\
      20NewsGroup   &   20     & 7532    & 65981  & 50030     & 37.75      \\
      SCY-Genes     &   7      & 1114    & 9128   & 5963      & 56.21      \\
      SCY-Cluster   &   7      & 1655    & 11273  & 7630      & 158.81     \\
    \bottomrule
  \end{tabular}
  }
\end{table}


Regarding the hyper-parameters of the classifiers, SVM parameters were chosen after a MultiSearch algorithm\footnote{\url{https://github.com/fracpete/multisearch-weka-package}} performed on the training set by choosing the kernel between Polynomial and RBF, the degree for the polynomial kernel values ranging from 1 to 5 and for the RBF kernel, the gamma value raging from -4 to 1, and the C parameter tested within fixed value 1. For the k-NN we have tested the parameter k ranging from $1$ to $15$

The best parameters obtained for the training data was achieved with polynomial kernel with degree $5$ for the Euclidean distance, RBF kernel with gamma set to $10$ for the cosine distance and polynomial kernel with degree $1$ for the IG, CHI, IGFSS and VGFSS, in all cases $C = 1$. The $k$-NN algorithm achieved the best results with $k = 5$ and Euclidean distance.


\section{Results}\label{sec:results}

\begin{figure*}[tb]
  \centering
  \resizebox{\textwidth}{!}{
  \includegraphics[]{acertos_SVM.pdf}
  }
  \caption{Results achieved with the DCDistance technique applied with the SVM classifier. The ``Accuracy'' axis represents the accuracy of the classification and  the ``Features'' axis represents the resulting percentage of features.}
  \label{fig:graphs_DCD_SVM}
\end{figure*}

\begin{figure*}[tb]
  \centering
  \resizebox{\textwidth}{!}{
  \includegraphics[]{acertos_RandomForest.pdf}
  }
  \caption{Results achieved with the DCDistance technique applied with the Random Forest classifier. The ``Accuracy'' axis represents the accuracy of the classification and  the ``Features'' axis represents the resulting percentage of features.}
  \label{fig:graphs_DCD_RF}
\end{figure*}

\begin{figure*}[tb]
  \centering
  \resizebox{\textwidth}{!}{
  \includegraphics[]{acertos_KNN.pdf}
  }
  \caption{Results achieved with the DCDistance technique applied with the KNN classifier. The ``Accuracy'' axis represents the accuracy of the classification and  the ``Features'' axis represents the resulting percentage of features.}
  \label{fig:graphs_DCD_KNN}
\end{figure*}

\input{resultsReuter}
\input{resultsNews}
\input{resultsGenes}
\input{resultsCluster}

The results obtained with our experiments are summarized on Tables \ref{tab:results_reuter}-\ref{tab:results_cluster}. The \emph{Red.} column represents the percentage of feature reduction obtained with the number of features described on column \emph{Feat.} compared with the total number of features before pre-processing. The best results are marked in bold. 

The first thing to notice from these tables is that DCD.C obtained overall better results than DCD.E for the Reuters and Newsgroups (Tables \ref{tab:results_reuter} and \ref{tab:results_news}) datasets. This is the expected behavior since the representative vectors are created as a sum of other vectors which implies that the intention is to capture a given direction close to most documents of the corresponding class. As such, the Cosine similarity is more compatible with this intuition.

On the other hand, for the Genes and Clusters datasets (Tables \ref{tab:results_genes} and \ref{tab:results_cluster}), the Euclidean distance performed better than the Cosine similarity, the reason why should be investigated.

Comparing to the other approaches, the DCD obtained the best results with the only exception of the combination of Random Forest with $20\%$ of the features selected by VGFSS. Despite that, both DCD versions achieved a very close result but with a much higher dimensionality reduction.

Finally, we can see that the application of DCD renders a much better result than the use of the original features set, thus indicating that the transformed features capture the information regarding the different classes.

In Figures \ref{fig:graphs_DCD_SVM}-\ref{fig:graphs_DCD_KNN} we can see the compromise between accuracy and reduction achieved by each combination of algorithm, parameters, and dataset. These figures highlight the interesting property of DCD of maximizing both the reduction and accuracy for the classification task.

Tables \ref{tab:words_reuter}-\ref{tab:words_cluster} give a detailed analysis of each representative vectors from all datasets used. In this tables were gathered the top 10 words with the highest intensity of each class. Observing Table \ref{tab:words_reuter}, referring to the dataset News, we noticed that many words could characterize the class that the representative vector expresses. For example, some of the words that have the highest intensity in the sci space class are space, orbit, mission, planet, earth, moon. Notice that these words have a certain relation to the class of their representative vector. We can observe the same pattern when we look at Table \ref{tab:words_reuter} which has the top 10 words of  Reuter dataset. This analysis is critical because it shows that representative vectors can capture the words that have the greatest and least contribution within a class, allowing to explore several unique characteristics of each class.

The relationship of the most significant words with class names representation is not very clear in Genes and Cluster datasets (Tables \ref{tab:words_genes} and \ref{tab:words_cluster}) because the class names do not express common words of the language. On the other hand, we can use the representative vectors to try to extract a name that best defines that class.

\input{words_reuter}
\input{words_news}
\input{words_genes}
\input{words_cluster}

\section{Conclusion and Future Work}\label{sec:conclusion_and_future_work}


In this paper, we have proposed a new feature extraction algorithm, called DCDistance, that reduces the number of features to the number of distinct class labels of the dataset.

This algorithm simply creates representative vectors as the sum of training vectors grouped by each class and then uses these vectors to create a distance vector with each element being the distance of a document to a representative vector.

Since the features set is reduced to the number of class labels, this algorithm creates a reduction of more than $99\%$ of the original feature set. With a proper choice of data structures, this algorithm can be implemented with a linear complexity w.r.t. the number of documents.

The experimental results compared DCDistance against four other techniques and, also, the use of the original set of features. The results showed that the proposed algorithm outperforms each of the contenders by maximizing both the reduction of the features set and the accuracy of the machine learning model.

By observing the words corresponding to the features with the highest values in the representative vectors, we perceived a high correlation with the topics pertaining to the class. This property allows exploring other applications for these attributes, such as summarization or model interpretability.

For future research, we will explore other forms of aggregation to create the representative vectors and different distance metrics. And, as mentioned, we will also explore the interpretability induced by these representative vectors.


\section*{Acknowledgments}


\bibliographystyle{model2-names}








