entity set expansion python

Question

Do you know of any existing implementation in any language (preferably python) of any entity set expansion algorithms, such that the one from Google sets ? ( http://labs.google.com/sets )

I couldn't find any library implementing such algorithms and I'd like to play with some of those to see how they would perform on some specific task I would like to implement.

Any help is welcome !

Thanks a lot for your help,

Regards,

Nicolas.

Answer 1

I'm not aware of any ready to use open source libraries that implement the sort of clustering on demand of named entities provided by Google Sets. However, there are a few academic papers that describe in detail how to build similar systems, e.g.:

• Language-Independent Set Expansion of Named Entities using the Web
  Wang and Cohen, in EMNLP 2009
  Online Demo

• Bayesian Sets
  Ghahramani and Heller, in NIPS, 2005

Below is a brief summary of Wang and Cohen's method. If you do end up implementing something like this yourself, it might be good to start with their method. I suspect most people will find it more intuitive than Ghahramani and Heller's formulation.

Wang and Cohen 2009

Wang and Cohen start by describing a method for automatically constructing extraction patterns that allow them to find lists of named entities in any sort of structured document. The method looks at the prefixes and suffixes bracketing known occurrences of named entities. These prefix and suffixes are then used to identify other named entities within the same document.

To complete a clusters of entities, they build a graph consisting of the interconnections between named entities, the extraction patterns associated with them, and the documents. Using this graph and starting at the nodes for the cluster's seed entities (i.e., the initial set of entities in the set to be completed), they perform numerous random walks on the graph up to 10 steps in length. They count how many times they reach the nodes corresponding to non-seed entities. Non-seed entities with high counts can then be used to complete the cluster.