# AnalyticBridge

Subscribe to Vincent Granville's Weekly Digest:

# Features Extraction: Co-occurrences and Graph clustering

In the last two post we have discussed about co - occurrences analysis to extract features  in order to classify documents and extract "meta concepts" from the corpus.
We have also noticed that this approach doesn't return better than the traditional bag of words.
I would now explore some derivation of this approach, taking advantage of the graph theory.

the graph of the co occurrences is really huge and complex, how could we reduce its complexity without big information loss?
The Kcore algorithm could help in doing that. It gives groups of vertices that are connected to at least k others.
To build it you can remove repeatedly vertices of out-degree less than k.
Below the k core components from the original graph (the k chosen here is five).

The entities extracted
Form the k-core graph we could extract the shortest path for each combination of two vertexes.
And we can compare the paths obtained with the document in the corpus to select the paths really existing in the documents (this trick of course should be applied only on the training set!).
The procedure returned 526 entities.
Here you are the longest entities extracted:
1 rice farmer reach acre
2 department say last summer
4 month pct increase
5 summer grain harvest
7 record tonne previous
8 rice farmer reach
9 cash crop include
10 high rate national
11 pay crop loan
12 cotton payment reach
13 major farm group
14 future year ago
16 total tonne intervention
17 offer  exporter issue
18 import tonne agricultural
19 bushel price  current
20 bushel corn producer
The graph clustering
Another interesting things we can do with such entities  is to isolate in the kcore graph the nodes that describe the entities and apply a clustering algorithm over the graph connections.
I decided to apply in this case as a clustering distance the "community modularity".
The clustering returns unstructured features.
Here you are the clustered graph and the unstructured features clustered:
Semantic Aggregation

Views: 438

Comment

Join AnalyticBridge

1

2

3

4

5

6

7

8

9

10