Method, apparatus and programmed medium for clustering databases with categorical attributes

A computer based method of clustering related data in a large computer database, said large computer database stored on a computer readable medium and including a set of data points having categorical attributes, the method comprising the steps of:

• a) selecting a random set of data points from said large computer database;
• b) determining all neighbors for every data point within said random set of data points;
• c) establishing a cluster for every data point within said random set of data points;
• d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster;
• e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster;
• f) merging a pair of clusters having the best goodness measures into a merged cluster;
• g) repeating steps d) through f) until a predetermined termination condition is met;
• and
• h) storing clusters which remain after step g) in a computer readable medium.

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a computer database, said computer database including data points having categorical attributes, said clustering method comprises the steps of:

• a) determining all neighbors for every data point within said computer database;
• b) establishing a cluster for every data point in said computer database;
• c) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster;
• d) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster;
• e) merging a pair of clusters having the best goodness measures into a merged cluster;
• f) repeating steps c) through e) until a predetermined termination condition is met;
• and
• g) storing clusters which remain after step f) in a computer readable medium.

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large database, said large database including a set of data points having categorical attributes, said clustering method comprises the steps of:

• a) selecting a random set of data points from said large computer database;
• b) determining all neighbors for every data point within said random set of data points;
• c) establishing a cluster for every data point within said random set of data points;
• d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster;
• e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster;
• f) merging a pair of clusters having the best goodness measures into a merged cluster;
• g) repeating steps d) through f) until a predetermined termination condition is met;
• and
• h) storing clusters which remain after step g) in a computer readable medium.

A programmed computer database clustering system comprising:

• means for determining all neighbors for every data point within a computer database stored on a computer readable medium, said computer database including data points having categorical attributes;
• means for establishing a cluster for every data point in said computer database;
• means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster;
• means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster;
• means for merging a pair of clusters having the best goodness measures into a merged cluster;
• means for storing clusters which remain in a computer readable medium.

A programmed computer database clustering system comprising:

• means for selecting a random set of data points from a large computer database stored on a computer readable medium, said large computer database including data points having categorical attributes;
• means for determining all neighbors for every data point within said large computer database;
• means for establishing a cluster for every data point in said computer database;
• means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster;
• means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster;
• means for merging a pair of clusters having the best goodness measures into a merged cluster;
• means for storing clusters which remain in a computer readable medium.