# US 2003/0217335 A1 · System and method for automatically discovering a hierarchy of concepts from a corpus of documents

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0217335 A1
- Document ID: US20030217335A1
- Status: Published application
- Kind: A1
- Application number: 10/150,795
- Filed: 2002-05-17
- Published: 2003-11-20
- Earliest claimed: 2002-05-17
- Assignees: Verity AG
- Inventors: Christina Yip Chung; Jinhui Liu; Alpha Luk; Jianchang Mao; Sumit Taank; Vamsi Vutukuru
- Web page: https://patentgrep.com/patent/US20030217335A1

## CPC

- G06F 40/30: Semantic analysis
- G06F 16/313: {Selection or weighting of terms for indexing}
- G06F 16/355: Creation or modification of classes or clusters
- Y10S 707/99937: Sorting
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

The invention is a method, system and computer program for automatically discovering concepts from a corpus of documents and automatically generating a labeled concept hierarchy. The method involves extraction of signatures from the corpus of documents. The similarity between signatures is computed using a statistical measure. The frequency distribution of signatures is refined to alleviate any inaccuracy in the similarity measure. The signatures are also disambiguated to address the polysemy problem. The similarity measure is recomputed based on the refined frequency distribution and disambiguated signatures. The recomputed similarity measure reflects actual similarity between signatures. The recomputed similarity measure is then used for clustering related signatures. The signatures are clustered to generate concepts and concepts are arranged in a concept hierarchy. The concept hierarchy automatically generates query for a particular concept and retrieves relevant documents associated with the concept.

## Claims

### Claim 1

A method for automatically discovering a hierarchy of concepts from a corpus of documents, the concept hierarchy organizes concepts into multiple levels of abstraction, the method comprising:
a. extracting signatures from the corpus of documents;
b. identifying similarity between signatures;
c. hierarchically clustering related signatures to generate concepts and hierarchically clustering concepts thus generated, whereby hierarchical clustering obtains a concept hierarchy;
d. labeling the concepts organized in the concept hierarchy; and
e. creating an interface for the concept hierarchy generated.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein the step of extracting signatures comprises:
a. parsing the documents in the corpus for speech tagging and sentence structure analysis;
b. extracting signatures representing content of the documents; and
c. indexing the extracted signatures.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein the step of identifying similarity between signatures comprises:
a. representing signatures using distribution of signatures in the corpus of documents;
b. computing similarity measure between signatures;
c. refining distribution of signatures in the corpus of documents;
d. re-computing similarity measure between signatures based on the refined distribution; and
e. identifying related signatures using the re-computed similarity measure.

### Claim 4 (depends on 3)

The method as recited in claim 3, wherein the step of computing similarity measure uses a modified Kullback—Leibner distance.

### Claim 5 (depends on 3)

The method as recited in claim 3, wherein the step of computing similarity measure uses a mutual—information statistic.

### Claim 6 (depends on 3)

The method as recited in claim 3, wherein the step of refining distribution of signatures comprises:
a. refining co-occurrence frequency distribution of signatures in the corpus of documents; and
b. disambiguating signatures with a high occurrence frequency to account for the possibility of multiple senses for a signature.

### Claim 7 (depends on 6)

The method as recited in claim 6, wherein the step of refining the co-occurrence frequency comprises:
a. computing a smoothing parameter using the conditional probability of pairs of signatures; and
b. adding, at every iteration, the smoothing parameter to co-occurrence frequency of all the pairs of signatures.

### Claim 8 (depends on 6)

The method as recited in claim 6, wherein the step of disambiguating signatures comprises:
a. choosing ambiguous signatures;
b. computing distinct senses for chosen signatures;
c. representing a sense as the frequency distribution of it's constituent signatures;
d. decomposing the frequency distribution of disambiguated signature according to the number of senses computed corresponding to the disambiguated signature;
e. adding the decomposed frequency distribution to the senses computed;
f. adjusting frequency distribution of the signatures constituting a given sense;
g. re-computing sense for a pair of signatures based on the adjusted frequency distribution; and
h. recursively repeating steps f and g for a predefined number of iterations.

### Claim 9 (depends on 1)

The method as recited in claim 1, wherein the step of hierarchically clustering comprises:
a. measuring connectivity between signatures based on the similarity measure between signatures;
b. clustering signatures with highest connectivity, a cluster of signatures representing a concept;
c. measuring connectivity between at least two individual clusters of signatures;
d. measuring compactness of the individual cluster of signatures;
e. merging at least two individual clusters of signatures based on their connectivity; the merged clusters forming a parent cluster; and
f. recursively repeating steps c, d and e till the number of merged clusters reaches a predefined number

### Claim 10 (depends on 1)

The method as recited in claim 1, wherein the step of hierarchically clustering uses a binary partitioning algorithm for clustering.

### Claim 11 (depends on 1)

The method as recited in claim 1, wherein one or more of the steps is embodied in a hardware chip.

### Claim 12

A system for automatically discovering a hierarchy of concepts from a corpus of documents, the concept hierarchy organizes concepts into multiple levels of abstraction, the system comprising:
a. means for extracting signatures from the corpus of documents;
b. means for identifying similarity between signatures;
c. means for hierarchically clustering related signatures to generate concepts and hierarchically clustering concepts thus generated, whereby hierarchical clustering obtains a concept hierarchy;
d. means for labeling concepts organized in the concept hierarchy; and
e. means for creating an interface for the concept hierarchy.

### Claim 13 (depends on 12)

The system as recited in claim 12, wherein the means for extracting signatures comprises:
a. means for parsing the documents in the corpus for speech tagging and sentence structure analysis;
b. means for extracting signatures representing content of the documents;
c. means for indexing the extracted signatures.

### Claim 14 (depends on 12)

The system as recited in claim 12, wherein the means for identifying similarity between signatures comprises:
a. means for representing signatures using the distribution of signatures in the corpus of documents;
b. means for computing similarity measure between signatures;
c. means for refining distribution of signatures in the corpus of documents;
d. means for re-computing similarity measure of signatures based on the refined distribution; and
e. means for identifying related signatures using the re-computed measure of similarity.

### Claim 15 (depends on 14)

The system as recited in claim 14, wherein the means for computing similarity uses a modified Kullback—Leibner distance.

### Claim 16 (depends on 14)

The system as recited in claim 14, wherein the means for computing the similarity measure between signatures uses mutual-information measure.

### Claim 17 (depends on 14)

The system as recited in claim 14, wherein the means for refining distribution of signatures comprises:
a. means for refining co-occurrence frequency distribution of signatures in the corpus of documents; and
b. means for disambiguating signatures with a high occurrence frequency to account for the possibility of multiple senses for a signature.

### Claim 18 (depends on 17)

The system as recited in claim 17, wherein the means for refining co-occurrence frequency comprises:
a. means for computing a smoothing parameter using conditional probability of the pair of signatures; and
b. means for adding, at every iteration, the smoothing parameter to the co-occurrence frequency of all the pairs of signatures.

### Claim 19 (depends on 17)

The system as recited in claim 17, wherein the means for disambiguating signatures comprises:
a. means for choosing ambiguous signatures;
b. means for computing distinct senses for a signature;
c. means for representing a sense as the frequency distribution of it's constituent signatures;
d. means for decomposing the frequency distribution of disambiguated signature according to the number of senses computed corresponding to the disambiguated signature;
e. means for adding the decomposed frequency distribution to the senses computed;
f. means for adjusting frequency distribution of the signatures constituting a given sense;
g. means for re-computing sense for a pair of signatures based on the adjusted frequency distribution; and
h. means for recursively repeating steps f and g for a predefined number of iterations.

### Claim 20 (depends on 12)

The system as recited in claim 12, wherein the means for hierarchically clustering comprises:
a. measuring connectivity between signatures based on the similarity measure between the signatures;
b. clustering signatures with highest connectivity, a cluster of signatures representing a concept;
c. measuring connectivity between at least two individual clusters of signatures;
d. measuring compactness of the individual cluster of signatures;
e. merging at least two individual clusters of signatures based on their connectivity; the merged clusters forming a parent cluster; and
f. recursively repeating steps c, d and e till the number of merged clusters reaches a predefined value.

### Claim 21 (depends on 12)

The method as recited in claim 12, wherein the means for hierarchically clustering uses a binary partitioning algorithm for clustering.

### Claim 22 (depends on 12)

The system as recited in claim 12, wherein the means for creating an interface for the automatically generated concept hierarchy has a means for searching of concepts in the concept hierarchy.

### Claim 23 (depends on 12)

The system as recited in claim 12, wherein the means for creating an interface for the automatically generated concept hierarchy has a means for editing the concept hierarchy.

### Claim 24 (depends on 12)

The system as recited in claim 12, wherein the means for creating an interface for the automatically generated concept hierarchy has a means for automatically generating a query that allows a user to automatically retrieve documents related to a concept in the concept hierarchy.

### Claim 25 (depends on 12)

The system as recited in claim 12, wherein the system is embodied in a computer program.
