Hierarchical ant clustering and foraging

Abstract

A clustering method yields a searchable hierarchy to speed retrieval, and can function dynamically with a changing document population. Nodes of the hierarchy climb up and down the emerging hierarchy based on locally sensed information. Like previous ant clustering algorithms, the inventive process is dynamic, decentralized, and anytime. Unlike them, it yields a hierarchical structure. For simplicity, and reflecting our initial application in the domain of textual information, the items being clustered are documents, but the principles may be applied to any collection of data items.

1 . A computer-implemented clustering algorithm that functions dynamically with changing data to yield a searchable hierarchy. 
     
     
         2 . The clustering algorithm of  claim 1 , further being decentralized. 
     
     
         3 . The clustering algorithm of  claim 1 , further being any-time. 
     
     
         4 . The clustering algorithm of  claim 1 , wherein the data includes documents. 
     
     
         5 . The clustering algorithm of  claim 1 , wherein the nodes of the hierarchy climb up and down the emerging hierarchy based on locally sensed information. 
     
     
         6 . A process for clustering a set of data elements associated with a data population into a hierarchy, comprising the steps of:
 adapting to changes in a data population being clustered; and   measuring the similarity among data elements without the need to restart the process.   
     
     
         7 . A process for clustering a set of data elements into a hierarchy, wherein:
 the similarity among the data elements subsumed under any node of the hierarchy increases as one moves from the root of the hierarchy.   
     
     
         8 . The process of  claim 7 , including the steps of:
 promoting a child node of the active node to become a sibling of the active node, and merging two children of the active node into a single node.   
     
     
         9 . The process of  claim 7 , including the step of:
 accessing results while it is running; and   yielding useful approximate clusters soon after it is started and improving their quality as the process continues to run.   
     
     
         10 . The process of  claim 7 , including the step of parallel execution across multiple computer processors. 
     
     
         11 . The process of  claim 7 , including a node-based summary supporting homogeneity estimates. 
     
     
         12 . The process of  claim 11 , wherein the node-based summary is based on sums of vectors representing individual data elements. 
     
     
         13 . The process of  claim 11 , wherein the node-based summary is based on mutual information statistics across the data elements. 
     
     
         14 . The process of  claim 11 , in which a node's decision to compute is deterministic. 
     
     
         15 . The process of  claim 11 , in which a node's decision to compute is stochastic. 
     
     
         16 . The process of  claim 11 , in which all of a node's children are considered in selecting candidates for promoting and merging. 
     
     
         17 . The process of  claim 11 , in which a randomly chosen subset of a node's children are considered in selecting candidates for promoting and merging. 
     
     
         18 . The process of  claim 7 , in which the decision to promote a child is based on some combination of the relative homogeneity of the node and its children, the contribution of the children to the node's homogeneity, and the branching factors of the node and its parent and children.