Hierarchical clustering on graphs for taxonomy extraction and applications thereof
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.
1. 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.
2. The method of claim 1 , further comprising:
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.
3. The method of claim 1 , wherein the statistical distance is a Kullback-Leibler (KL) divergence or a Jensen-Shannon (JS) divergence.
4. The method of claim 1 , wherein the clustering algorithm includes a probabilistic latent semantic analysis (pLSA), a latent Dirichlet allocation (LDA), a multilayer graph clustering algorithm, or a combination thereof.
5. The method of claim 1 , wherein the community detection algorithm includes a random walk-based algorithm formulated to compute the first modularity score.
6. The method of claim 5 , wherein:
the plurality of clusters correspond to one of a sequence of hierarchical partitions of the nodes of the graph identified by the random walk-based algorithm; and
the first modularity score is a maximum of modularity scores of the sequence of hierarchical partitions of the nodes of the graph.
7. The method of claim 1 , wherein the first modularity score is computed based on Girvan-Newman algorithm.
8. The method of claim 7 , wherein:
the plurality of clusters correspond to one of a sequence of hierarchical partitions of the nodes of the graph identified by the Girvan-Newman algorithm; and
the first modularity score is a maximum of modularity scores of the sequence of hierarchical partitions of the nodes of the graph.
9. The method of claim 1 , wherein:
the pruning stop criterion includes a size of the second cluster attaining a resolution limit of the second cluster; and
the iteratively removing includes ceasing to iteratively remove the node of the first cluster when the size of the second cluster attains a resolution limit of the second cluster.
10. The method of claim 1 , wherein the corpus of documents comprises a set of legal documents.
11. The method of claim 10 , further comprising:
searching the set of legal documents based on labels extracted from the taxon nodes; and
outputting a set of search results that includes one or more legal documents of the set of legal documents in response to the searching.
12. 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.
13. The system of claim 12 , wherein:
the pruning stop criterion includes a size of the second cluster attaining a resolution limit of the second cluster; and
the iteratively removing includes ceasing to iteratively remove the node of the first cluster when the size of the second cluster attains a resolution limit of the second cluster.
14. The system of claim 12 , wherein the corpus of documents comprises a set of legal documents.
15. The system of claim 14 , the operations further comprising:
searching the set of legal documents based on labels extracted from the taxon nodes; and
outputting a set of search results that includes one or more legal documents of the set of legal documents in response to the searching.
16. 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.
17. The non-transitory CRM of claim 16 , wherein:
the pruning stop criterion includes a size of the second cluster attaining a resolution limit of the second cluster; and
the iteratively removing includes ceasing to iteratively remove the node of the first cluster when the size of the second cluster attains a resolution limit of the second cluster.
18. The non-transitory CRM of claim 16 , wherein the corpus of documents comprises a set of legal documents.
19. The non-transitory CRM of claim 18 , the operations further comprising:
searching the set of legal documents based on labels extracted from the taxon nodes; and
outputting a set of search results that includes one or more legal documents of the set of legal documents in response to the searching.