Back to results
US 12,613,921 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.
Claims17
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 cooccurrence 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, wherein at each of a plurality of hierarchy levels, each detected cluster has a respective modularity score exceeding a corresponding minimum modularity threshold;
- transforming, using the processor, a first cluster of the plurality of clusters into a second cluster by iteratively (i) determining betweenness centrality scores for nodes of the first cluster, and (ii) removing a node of the first cluster, the node of the first cluster having a betweenness centrality score that is a maximum of betweenness centrality scores of remaining nodes in the first cluster, until (iii) a pruning stop criterion is satisfied;
- 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;
- computing, using the processor, a centroid of the one of the plurality of third clusters;
- and
- identifying, using the processor, a representation of the taxon node representing the one of the plurality of third clusters based on proximity of the centroid to nodes of the one of the plurality of third clusters.
6 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, using the processor, a community detection algorithm to the graph to detect a plurality of clusters of nodes of the graph, wherein at each of a plurality of hierarchy levels, each detected cluster has a respective modularity score exceeding a corresponding minimum modularity threshold;
- transforming, using the processor, a first cluster of the plurality of clusters into a second cluster by iteratively (i) determining betweenness centrality scores for nodes of the first cluster, and (ii) removing a node of the first cluster, the node of the first cluster having a betweenness centrality score that is a maximum of betweenness centrality scores of remaining nodes in the first cluster, until (iii) a pruning stop criterion is satisfied;
- 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;
- computing, using the processor, a centroid of the one of the plurality of third clusters;
- and
- identifying, using the processor, a representation of the taxon node representing the one of the plurality of third clusters based on proximity of the centroid to nodes of the one of the plurality of third clusters.
8 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, using the processor, a community detection algorithm to the graph to detect a plurality of clusters of nodes of the graph, wherein at each of a plurality of hierarchy levels, each detected cluster has a respective modularity score exceeding a corresponding minimum modularity threshold;
- transforming, using the processor, a first cluster of the plurality of clusters into a second cluster by iteratively (i) determining betweenness centrality scores for nodes of the first cluster, and (ii) removing a node of the first cluster, the node of the first cluster having a betweenness centrality score that is a maximum of betweenness centrality scores of remaining nodes in the first cluster, until (iii) a pruning stop criterion is satisfied;
- 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;
- computing, using the processor, a centroid of the one of the plurality of third clusters;
- and
- identifying, using the processor, a representation of the taxon node representing the one of the plurality of third clusters based on proximity of the centroid to nodes of the one of the plurality of third clusters.
6 more elements
Dependencies are inferred from the claim text.