Back to results
US 11,886,515 B2Granted
Hierarchical clustering on graphs for taxonomy extraction and applications thereof
AssigneeThomson Reuters Enterprise Centre GmbH
InventorsNikolai Nefedov, David von Rickenbach
Life of this patent
Estimating the term…
Abstract
Aspects of the present disclosure provide systems, methods, apparatus, and computer-readable storage media for extracting taxonomies based on hierarchical clustering on graphs related to a corpus of documents and using said taxonomies for classifying and labeling documents. The hierarchical clustering of graphs include the adaptive pruning of nodes at each hierarchy based on betweenness centrality of nodes to form clusters that have modularity score exceeding a minimum modularity threshold.
Claims19
A method, comprising:
- generating, using a processor, a similarity matrix or a co-occurrence matrix for a corpus of documents;
- applying, using the processor, a clustering algorithm to the similarity matrix or the co-occurrence matrix to generate a graph corresponding to the corpus of documents;
- applying, using the processor, a community detection algorithm to the graph to detect a plurality of clusters of nodes of the graph, the plurality of clusters having a first modularity score exceeding a minimum modularity threshold;
- for a first cluster of the plurality of clusters, iteratively removing, using the processor, a node of the first cluster to transform the first cluster into a second cluster based on a pruning stop criterion, wherein the removed node has associated therewith a betweenness centrality that is a maximum of betweenness centralities of remaining nodes of the second cluster;
- applying, using the processor, the community detection algorithm to the second cluster to identify a plurality of third clusters of the second cluster, the plurality of third clusters having a second modularity score exceeding the minimum modularity threshold;
- presenting, using the processor, the plurality of third clusters as a taxon graph composed of taxon nodes each representing one of the plurality of third clusters;
- receiving, at the processor, a first document for labeling;
- defining, using the processor, a first probability distribution associated with the first document and second probability distributions associated with the taxon nodes;
- and
- extracting a label from the taxon nodes for labeling the first document based on a statistical distance between the first probability distribution and the second probability distributions.
7 more elements
A system, comprising:
- a processor;
- and
- a memory device coupled to the processor and including instructions that, when executed by the processor, configure the processor to perform operations comprising:
- generating a similarity matrix or a co-occurrence matrix for a corpus of documents;
- applying a clustering algorithm to the similarity matrix or the co-occurrence matrix to generate a graph corresponding to the corpus of documents;
- applying a community detection algorithm to the graph to detect a plurality of clusters of nodes of the graph, the plurality of clusters having a first modularity score exceeding a minimum modularity threshold;
- for a first cluster of the plurality of clusters, iteratively removing a node of the first cluster to transform the first cluster into a second cluster based on a pruning stop criterion, wherein the removed node has associated therewith a betweenness centrality that is a maximum of betweenness centralities of remaining nodes of the second cluster;
- applying, using the processor, the community detection algorithm to the second cluster to identify a plurality of third clusters of the second cluster, the plurality of third clusters having a second modularity score exceeding the minimum modularity threshold;
- presenting, using the processor, the plurality of third clusters as a taxon graph composed of taxon nodes each representing one of the plurality of third clusters;
- receiving, at the processor, a first document for labeling;
- defining, using the processor, a first probability distribution associated with the first document and second probability distributions associated with the taxon nodes;
- and
- extracting a label from the taxon nodes for labeling the first document based on a statistical distance between the first probability distribution and the second probability distributions.
10 more elements
A non-transitory computer-readable medium (CRM) in which a program is stored for causing a computer to perform operations comprising:
- generating a similarity matrix or a co-occurrence matrix for a corpus of documents;
- applying a clustering algorithm to the similarity matrix or the co-occurrence matrix to generate a graph corresponding to the corpus of documents;
- applying a community detection algorithm to the graph to detect a plurality of clusters of nodes of the graph, the plurality of clusters having a first modularity score exceeding a minimum modularity threshold, respectively;
- for a first cluster of the plurality of clusters, iteratively removing a node of the first cluster to transform the first cluster into a second cluster based on a pruning stop criterion, wherein the removed node has associated therewith a betweenness centrality that is a maximum of betweenness centralities of remaining nodes of the second cluster;
- applying, using a processor, the community detection algorithm to the second cluster to identify a plurality of third clusters of the second cluster, the plurality of third clusters having a second modularity score exceeding the minimum modularity threshold;
- presenting, using the processor, the plurality of third clusters as a taxon graph composed of taxon nodes each representing one of the plurality of third clusters;
- receiving, at the processor, a first document for labeling;
- defining, using the processor, a first probability distribution associated with the first document and second probability distributions associated with the taxon nodes;
- and
- extracting a label from the taxon nodes for labeling the first document based on a statistical distance between the first probability distribution and the second probability distributions.
7 more elements
Dependencies are inferred from the claim text.