Extract meta concepts through co-occurrences analysis and graph theory.

During The Christmas period I had finally the chance to read some papers about probabilistic latent semantic and its applications in auto classification and indexing.

The main concept behind “latent semantic” lays on the assumption that words that occurs close in the text are related to the same semantic construct.

Based on this principle the LSA (and partially also the PLSA ) builds a matrix to keep track of the co-occurrences of the words in text, and it assign a score to these co-occurrences considering the distribution in the corpus as well.

Often TF-IDF score is used to rank the words.

Anyway, I was wondering if this techniques could be useful also to extract key concepts from the text.

Basically I thought: “in LSA we consider some statistics over the co-occurrences, so: why not consider the link among the co-occurrences as well?”.

So what I did is the following (be aware that is not the formal implementation of LSA!):

1. Filter and take the base form of the words as usual.
2. Build the multidimensional sparse matrix of the co-occurrences;
3. I calculated for each instance the frequency to find it in the corpus;
4. I calculated for each instance the frequency to find it in the doc;
5. I weighted such TF-IDF considering also the distance among the co-occurrences.

In this way we are able to rank all co-occurrences and set a threshold to discard items having low rank.

In the last step I built a graph where I linked the co-occurrences.

As you can see in the following examples, the graphs are initially pretty complex, and to refine the results, I applied filter based on the number of connected components in the graph.

The below examples are representing the concepts extracted by the first three chapters of the books “The Media in the Network Society, author: Gustavo Cardoso” Available at http://ebooksgo.org/computer/networksecurity.pdf

Meta - concepts (unfiltered) extracted from "Introduction" chapter.

Meta - concepts (unfiltered) extracted from "Introduction" chapter.

The arrows, help to identify correct direction to read the "meta concepts". Of course is still required a bit of efforts to identify the underlying semantic but after a quick reading of the original source is easy convince oneself that this representation fits pretty good with the content.

Below the outcomes for the first chapter:

Unfiltered meta concepts for the first chapter

Filtered meta concepts for the first chapter

And, here you are the the second chapter:

Unfiltered meta concepts for the second chapter

Filtered meta concepts for the second chapter

I'm sure that there is room to big improvements of this rough method, for instance assigning the ranks of the co-occurrencies with more sophisticated ways respect the usual TF-IDF (like using centrality based measures, or considering cosine distances).

Are these constructs also useful to classify text?

…we will see the answer in the next post J.

Stay tuned

cristian

Features Reduction part 2: C 5 vs PCA - Road Map

In the last post I showed how reduce the complexity (dimension) of the problem through PCA algorithm.
I mentioned that PCA works well under the condition that the data set has homogenous density.
Are we in this scenario?
I analyzed our data set to verify how the points are distributed; to do that I used the first three components suggested by PCA for the classes having TOPICS = "GOLD" and "GRAIN".
To highlight better the density I soiled the 3D coordinates with a weak gaussian noise just to avoid the presence of coincident points. Here you are the results:

In green "GRAIN" class, in violet "GOLD" class. Both soiled with weak gaussian noise.

As you can see both the data set are pretty much heterogenous! So the enthusiasm sprung from the higher reduction of PCA is maybe too much optimistic!
A countercheck of this quantitative analysis is provided by the second feature reduction algorithm we are testing: C 5.

A C 5 decision tree is constructed using GainRatio. GainRatio is a measure incorporating entropy. Entropy measures how unordered the data set is. Further details about C.5 are available at Quinlan's website: http://www.rulequest.com. 

An Extremely interesting book about Entropy application is  the famous "Cover - Thomas":

Elements of Information Theory, 2nd Edition

Thomas M. Cover, Joy A. Thomas

C 5  is really easy to manage. In the default version you don't need to tune parameters, even if a lot of configurations are available to improve the accuracy. An interesting feature (by my prospective) is the boosting mode. ... but we will discuss about that in the next time...

I wrote a wrapper in Mathematica to:

•  prepare the configurations files (.name file and .data) ;
• adapt the data set from LIBSVM format to C5 format;
• to display the tree output.

Contact me if you desire the notebook.

Let's show the output of C 5 using the default setting:

The Decision Tree returned by C 5
The leaves (depicted with red triangles) represent the class assigned by the algo for this decision path.
A = "GOLD", B= "GRAIN", C= "OIL".
The left members of the node inequalities  represent the feature number.

The above Tree represents  the Decision paths for a data set composed by the Three classes having TOPICS = "GOLD","GRAIN","OIL". 
To build the vector I used the TF DF feature set of the class "GOLD".
(in the next post I gonna explain why I'm building vectors of class X using feature set of the class Y :) ).
As you can see in the graph , only few features have been used: 

  

Notice that C 5 returns different features respect PCA algo! Moreover it suggests us to use only 7 features: it is an amazing complexity reduction!!
I used C 5 just to analyze the important features, but C 5 is itself a classifier! In the below image the classification accuracy for the mentioned classes.

So C 5 gives us a set of rules to classify documents belonging to three different classes (the rules are depicted by the tree paths from the "start" node to each leaf) with an overall error rate less than 15%.
Is it a good result? Apparently yes, but ...if you have a look to the class "GRAIN" (B) the results are not so brilliant!!.
Don't worry we will see how to improve dramatically these accuracy.
At this point we have discussed about many algorithms, techniques and data set.
So where we are, and where we gonna go?

Auto classification Road Map

Guys, Stay Tuned.

cristian

Build the vectors and Feature Reduction

Part I: building the vectors
In the former post we have created a features set for the class GOLD, now we show how use this features set to build the vectors to feed the svm.
The Features set is the fingerprint that characterizes the document class.
To build the vectors, you have to follow the same parsing and filtering process used to extract the features.
As described in the previous post,  from the original file, you have to follow the below steps:

• Split the words of the file;
• Remove the words having Length <= 2;
• Remove the stopWords
• Take the "root" of the word (e.g. Large from Larger)

On the filtered file just obtained, you can build every sort of statistic to associate to each word of the filtered file a score.

For our purpose the simple frequency could be enough.

 The last step is to associate to each word of the filtered file the score just calculated with the score associated to each word of the features set.

This step is illustrated in the below illustration:

"FT score" stands for Feature set score, < . , . > stands for a linear operator.
Notice that a vector assumes 0 value when the filtered file doesn't contain occurrences for the specific feature.
The grey box is the final Real Number vector. 

As you can see the vector has the same dimension of the Feature Set, in this case (built using TF-DF) it has dimension equal closed to 1000.

In a enterprise environment it could be a bottleneck in terms of computational capabilities, this due to the strict relation between vector dimension and time complexity to classify.

Part II: reducing the dimension
How can we reduce the dimension of the problem to speed up the entire classification process?
There are different methods,  the first I would show is the Principal Component Analysis (PCA).
As usual, I'm not going to enter in technical and theoretical issues: there are thousands websites, tutorial and paper  where you can find every sort of details on that.
Just to have an overview, PCA provides the most important linear components in a set of data. It is based on the concept of eigenvectors and eigenvalues : M.x = λ x where λ is the eigenvalue and x is the eigenvector.
PCA has two great features:

1. it is completely unparameterized;
2. it is extremely easy to implement; 

In Mathematica the implementation takes no more than 4-5 rows code:

the variable matrix is the dataset having whatever Dimension

Basically you standardize the data (to have mean = 0),  you compute the covariance matrix, and on that you extract the eigenvalues and eigenvectors.
The position of eigenvectors having higher eigenvalues are the the component most relevant: the components relevant are the features most important to classify the documents with a minimum loss of accuracy!
Just to understand the role played by eigenvectors consider  the following multivariate gaussian data set:

Data set gaussian distributed

The principal components are well represented by the red vectors:

Principal Components for the above data set 

Nevertheless, PCA is not useful in data having different density, and before to discard components (features) from your data set, I suggest to analyze the density!

What happens in our classes? 

I computed the PCA for the GOLD class, but the question  now is "What is the minimum threshold to discriminate the important components against the negligible features?   

...Sometimes a simple "logPlot" helps the analyst:

The blu arrow represent the discontinuity point for the eigenvalues 

As shown above, around at the component number 82, there is a discontinuity: after this point the magnitude of the eigenvalue is negligible. Here you are the threshold! 

Remark

The vectors have been built using the sorted Feature Set list (see the previous post).

and the criteria to sort was based on the TF- DF (or TF IDF, or ...): from the most important from TF DF prospective to the less important.

The graph above provides us a sort of countercheck of the goodness of the criteria chosen to select the features, because there is a perfect correspondence among the weight assigned with TF DF and the eigenvalues (notice the monotonicity of the graph)!

So for the GOLD class, we will consider only the first 82 components.

As you can see we used PCA in two different ways:

1) to countercheck our features extraction method

2) to reduce the complexity of the problem from 1000 to 82.

In the next post, we will see another algorithm of feature reduction: C4.5.

...We are now introducing many different approaches to play with the data, in the next post I'll show you the graph of experiments we are doing to keep track of every results and to chose the best strategy.

as usual: stay tuned

cristian