Extract Meta Concepts Through Co-occurrences Analysis and Graph Theory.

January 13, 2012
103 Views
During the Christmas period I finally had 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 occur closely in the text are related to the same semantic construct.

During the Christmas period I finally had 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 occur closely 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 assigns 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 filtering 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 it still required a bit of effort to identify the underlying semantic, but after a quick reading of the original source it is easy to 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 for big improvements of this rough method, for instance assigning the ranks of the co-occurrencies with more sophisticated ways that 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