Method of clustering multi-dimensional related data in a computer database by combining the two verticles of a graph connected by an edge having the highest score

• US 5,706,503 A
• Filed: 05/18/1994
• Issued: 01/06/1998
• Est. Priority Date: 05/18/1994
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Dunn, Linnea A., Smartt, Brian E., Poppen, Richard F., Derose, Frank J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/245,690
• Time in Patent Office: 1,329 Days
• Field of Search: 395/600, 395/700, 395/603, 395/611, 395/613, 395/614, 395/776, 395/779, 395/605
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of clustering multi-dimensional related data performed by identifying features from a collection of data, each of said features being represented by a vertex, selecting pairs of features that it is desirable to cluster together, connecting the pair of vertices representing every selected pair of features by an edge, assigning a score to every edge according to a predetermined formula, selecting an edge having the highest score, creating a new vertex by merging the vertices connected by the selected edge, creating new edges between the new vertex and the vertices previously connected to the merged vertices, and repeating this procedure until every edge has a predetermined score.

Claims

1. A method of clustering multi-dimensional related data in a computer database, said computer database including a set of data records, each data record storing information about an object of interest, comprising the steps of:

a. establishing a vertex for every object of interest in said computer database so as to provide a graph comprising a plurality of vertices, each vertex representing a cluster;

b. connecting selected pairs of said plurality of vertices with edges;

c. calculating, on a computer, a score for the edges connecting the vertices, the score being a measure of how desirable it is to combine the vertices associated therewith;

d. selecting two vertices connected with an edge having the best score;

e. combining the two vertices by combining the clusters represented by the two vertices;

f. creating a new merged vertex and edges and calculating on a computer a new score for the new edges;

g. repeating steps (d) through (f) until a predetermined terminating condition is reached; and

h. storing remaining clusters in a computer readable medium.

2. A method according to claim 1 wherein said steps of establishing a vertex and connecting selected pairs comprise the steps of:

i) identifying features corresponding to areas and line segments on a two dimensional surface;

j) creating a separate vertex for each identified area and line segment; and

k) creating an edge from the vertex corresponding to each identified area to the vertex corresponding to each identified line segment bounding the area.

3. A method according to claim 1 wherein:

said step of establishing a vertex comprises the step of identifying features corresponding to areas and line segments on a two dimensional surface; and

said step of calculating a score comprises the step of selectively assigning a score which is;

i) equal to an area of a box bounding a first cluster plus an area of a box bounding a second cluster minus the area of a box bounding a combination of said first and second clusters, if said combination has a data record below a predetermined maximum size, or

ii) equal to negative infinity (-∞

) if said combination'"'"'s data record is equal to or above said predetermined maximum size.

4. A method according to claim 1 wherein said step of calculating a score comprises the step of selectively assigning a score which is equal to a sum of the scores of edges which a newly created edge replaces.

5. A method according to claim 1, further comprising the step of:

generating and maintaining a list of vertices in which there is listed for each vertex the score of a best edge connected to that vertex and the other vertex to which that best edge connects.

6. A method according to claim 5, wherein the step of generating and maintaining a list of vertices comprises the step of sorting said list by score.

7. A method according to claim 1, further comprising the steps of repeating steps (c) through (g).

8. A method according to claim 7, wherein each repetition of said steps (c) and (f) includes using a different method of scoring the edges.

9. A method according to claim 8 wherein said step (g) comprises a different and greater predetermined terminating condition with each repetition of steps (c) through (g).

10. A method according to claim 1, further comprising the step of identifying pairs of vertices not yet connected by an edge that it is desirable to combine and connecting each such pair of vertices with an edge during each repetition of steps (d) through (f).

11. A method according to claim 1, wherein the data being clustered is geographic map data.

12. A method according to claim 1, further comprising the step of suppressing vertices and associated edges representing objects for which there is no desire to maintain data in the database so as to leave a plurality of vertices representing features for which data is present in the database.

13. A method according to claim 1, wherein said predetermined terminating condition of step (g) is reached at when any further combining of clusters would exceed a predefined limit.

14. A method of clustering multi-dimensional related data in a computer data base, said computer database including a set of data records, each data record storing information about an object of interest, comprising the steps of:

creating a vertex for at least a subset of objects of interest in said computer database, each of said vertices representing a cluster;

connecting pairs of vertices with edges, each edge connecting two vertices;

calculating a score for the edges connecting the vertices using a computer, the score being a measure of how desirable it is to combine the vertices associated therewith;

selecting one edge having a score indicating a high desirability to combine said two vertices connected by said one edge;

combining the clusters represented by the two vertices connected by said one edge, the combination resulting in a new cluster;

creating a new merged vertex representing the new cluster;

connecting the new merged vertex and at least one preexisting vertex with one or more new edges;

calculating a new score for the one or more new edges; and

storing remaining clusters in a computer readable medium.

15. A method according to claim 14, wherein:

the step of creating a vertex for at least a subset includes the step of identifying features corresponding to areas and line segments on a two dimensional surface and creating a separate vertex for each identified area and line segment; and

the step of connecting pairs includes the step of creating an edge from the vertex corresponding to each identified area to the vertex corresponding to each identified line segment bounding the area.

16. A method according to claim 14, wherein:

the step of calculating a score includes the step of selectively assigning a score which is equal to;

i) the area of a box bounding a first cluster plus the area of a box bounding a second cluster minus the area of a box bounding the a combination of the first and second clusters, if the combination has a data record below a predetermined maximum size, or

ii) negative infinity (-∞

) if the combination'"'"'s data record is equal to or above the predetermined maximum size.

17. A method according to claim 14, further including the steps of:

removing at least one vertex, said one vertex connected to one or more other vertices by one or more edges;

removing said one or more edges; and

connecting each of the one or more other vertices to at least another of the one or more other vertices.

18. A computer readable storage medium having computer readable code embodied on said computer readable storage medium, said computer readable code for clustering multi-dimensional related data in a computer database, said computer database including a set of data records, each data record storing information about an object of interest, said computer readable code comprising:

first program code, said first program code establishes a vertex for at least a subset of objects of interest in said computer database, each of said vertices representing a cluster;

second program code, said second program code connects selected pairs of said vertices with edges, each edge connecting two vertices;

third program code, said third program code calculates a score for the edges connecting the vertices, the score being a measure of how desirable it is to combine the vertices associated therewith;

fourth program code, said fourth program code selects two vertices connected with one edge having a score indicating a high desirability to combine the two vertices;

fifth program code, said fifth program code combines the selected two vertices including combining the clusters represented by the selected two vertices;

sixth program code, said sixth program code creates a new merged vertex and edges and calculates a new score for the new edges; and

seventh program code, said seventh program code stores remaining clusters in a computer readable medium.

19. A computer readable storage medium according to claim 18, wherein:

said first program code identifies features corresponding to areas and line segments on a two dimensional surface and creates a separate vertex for each identified area and line segment; and

said second program code creates an edge from the vertex corresponding to each identified area to the vertex corresponding to each identified line segment bounding the area.

20. A computer readable storage medium according to claim 19, wherein:

said third program code selectively assigns a score which is equal to;

i) an area of a box bounding a first cluster plus an area of a box bounding a second cluster minus an area of a box bounding a combination of the first and second clusters, if the combination has a data record below a predetermined maximum size, or

ii) negative infinity (-∞

) if the combination'"'"'s data record is equal to or above the predetermined maximum size.

21. A computer readable storage medium according to claim 18, wherein:

said third program code selectively assigns a score which is equal to a sum of the scores of edges which a newly created edge replaces.

22. A computer readable storage medium according to claim 18, further including:

eighth program code, said eighth program code;

removes at least one vertex, the one vertex connected to one or more other vertices by one or more edges;

removes the one or more edges; and

connects each of the one or more other vertices to at least another of the one or more other vertices.