# US 2018/0025008 A1 · Systems and methods for homogeneous entity grouping

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

- Number: US 2018/0025008 A1
- Document ID: US20180025008A1
- Status: Published application
- Kind: A1
- Application number: 15/215,492
- Filed: 2016-07-20
- Published: 2018-01-25
- Earliest claimed: 2016-07-20
- Assignees: Baidu USA LLC
- Applicants: Baidu USA, LLC
- Inventors: Shulong Tan; Hongliang Fei; Yi Zhen; Yu Cao; Bocong Liu; Chaochun Liu; Richard Chun Ching Wang; Dawen Zhou; Wei Fan
- Web page: https://patentgrep.com/patent/US20180025008A1

## CPC

- G06F 16/355: Creation or modification of classes or clusters
- G06F 16/3331: Query processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods are disclosed to identify entities that have a similar meaning, and may, in embodiments, be grouped into entity groups for knowledge base construction. In embodiments, the entity relations of similarity or non-similarity for an entity pair are predicted as a binary relationship. In embodiments, the prediction may be based upon similarity score between the entities and the entity features, which features are constructed using an entity feature or representation model. In embodiments, the prediction may be an iterative process involving minimum human checking and existing knowledge update. In embodiments, one or more entity groups are formed using graph search from the predicted entity pairs. In embodiments, a group centroid entity may be selected to represent each group based on one or more factors, such as its generality or popularity.

## Claims

### Claim 1

A computer-implemented method to group synonymous entities among a set of homogeneous entities, based on their semantics, the method comprising:
determining a similarity scores between each two entities within the entity dictionary;
identifying, using prior knowledge, a plurality of similar entity pairs from an entity dictionary, the entity dictionary comprising a set of terms to be determined whether they have similar meanings;
using large scale text data to construct entity features constrained by the similar entity pairs;
for each similar entity pair, predicting entity relations between the entities using the constructed entity features and the determined similarity scores, the prediction being a binary prediction of positive relation or non-positive relation, the positive relation being defined as related relation between the entities;
in responsive to one criterion of one or more criteria not being met, sampling some predicted entity relations for verification, using verification results to update the prior knowledge and re-identify similar entity pairs, and re-predicting entity relations based at least on the re-identified similar entity pairs;
in responsive to one or more criteria being met, output the entity pairs with positive relation predictions; and
grouping the output entity pairs into one or more entity groups, each entity group comprising, for all entities in the group, all entity pairs that have a positive entity relationship.

### Claim 2 (depends on 1)

The method of claim 1 wherein the one or more criteria comprise an iteration number requirement and an iterative prediction change requirement.

### Claim 3 (depends on 2)

The method of claim 2 wherein the iteration number requirement requires more than one iteration, the iterative prediction change requirement requires the difference between entity relation predictions under current iteration and previous iteration is less than a threshold value.

### Claim 4 (depends on 1)

The method of claim 1 wherein the entity relations sampling is a random sampling process.

### Claim 5 (depends on 1)

The method of claim 1 wherein the verification for the sampled predicted entity relations is done by human checking.

### Claim 6 (depends on 1)

The method of claim 1 wherein grouping the homogenous entity pairs further comprising selecting a group centroid for each homogenous entity group.

### Claim 7 (depends on 6)

The method of claim 6 wherein the group centroid is selected as the most popular entity in a data set among the plurality of entities.

### Claim 8 (depends on 6)

The method of claim 6 wherein the one or more entity groups are grouped using graph search.

### Claim 9

A computer-implemented method for identifying similar entities, the method comprising:
[a] constructing entity features, using an entity feature constructor, for each entity of a plurality of entities based on prior knowledge and large scale text data;
[b] predicting, using an entity relation predictor, an entity relation for whether two entities within each one of a plurality of entity pairs share a similar meaning based at least on the constructed features;
[c] on a first iteration, randomly sampling some entity pairs for entity relations verification and verifying if the entity relation for each randomly sampled entity pair is correct;
[d] using the verified entity relations to update the prior knowledge;
[e] re-constructing entity features using the updated prior knowledge;
[f] re-predicting entity relations using the re-constructed entity features;
[g] iterating steps [d], [e], and [f] until a difference in an entity relations error measure between a first set of entity pairs and their corresponding entity relations for a current iteration and a second set of entity pairs and their corresponding entity relations from a prior iteration is less than a threshold; and
[h] outputting each entity pair from the plurality of entity pairs that have an entity relation that indicates that the entities in the entity pair have a similar meaning.

### Claim 10 (depends on 9)

The method of claim 9 further comprising:
[i] forming one or more entity groups from the outputted entity pairs, each entity group comprising, for all entities in the group, all entity pairs from the outputted entity pairs that have an entity relation that indicates that the entities in the entity pair have a similar meaning; and
[j] selecting, using a group centroid selector, a representation entity as a group centroid for each entity group.

### Claim 11 (depends on 10)

The method of claim 10 wherein the entity relation prediction for whether two entities share same meaning is based on mapped vectors of the two entities and a similarity score between the two entities.

### Claim 12 (depends on 11)

The method of claim 11 wherein the similarity score between the two entities is determined from a string level similarity between the two entities.

### Claim 13 (depends on 9)

The method of claim 9 wherein the step of verifying is performed by human verification.

### Claim 14 (depends on 9)

The method of claim 9 wherein the entity pairs are grouped using graph searching to separate the entities into at least one cluster of connected entities, each cluster of connected entities being an entity group.

### Claim 15 (depends on 9)

The method of claim 9 wherein the group centroid is selected as the most popular entity in a data set among the plurality of entities with the group.

### Claim 16 (depends on 9)

The method of claim 9 wherein the one or more entity groups are grouped using graph search.

### Claim 17

A non-transitory computer-readable medium or media comprising one or more sequences of instructions which, when executed by one or more processors, causes the steps to be performed comprising:
identifying, using an existing knowledge, a plurality of similar entity pairs from an entity dictionary;
determining a similarity score between any two entities within the entity dictionary;
constructing features in vectors in the entity dictionary for each entity, the identified plurality similar entity pairs being used for construction constraints;
predicting the entity relations between two entities based on at least the constructed features and the similarity scores, the prediction being a prediction of whether two entities as a related entity pair or not related entity pair;
outputting related entity pairs after the prediction;
grouping the related entity pairs as one or more entity groups, each entity group comprising, for all entities in the group, all related entity pairs; and
selecting a group centroid for each entity group.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium or media of claim 17 whether the prediction the entity relation is implemented using a supervised classification approach or a unsupervised clustering approach.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium or media of claim 18 wherein the prediction the entity relation under the supervised classification approach or a unsupervised clustering approach is an iterative process.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium or media of claim 19 wherein in the iterative process, some predicted entity relations are randomly sampled in each iteration for verification, the verified results are used for re-predicting entity relations until one or more criteria being met.