Programmed medium for clustering large databases

Claim 2

A computer based method of clustering related data in a computer database, said computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) establishing a cluster for every data point in said computer database, said data points being representative points of said cluster; b) calculating a distance between said representative points of every cluster; c) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; d) calculating a mean of said representative points for said merged cluster; e) selecting a number of scattered data points from said representative points of said merged cluster, said scattered data points representing a shape of said merged cluster; f) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; g) repeating steps b) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.

Claim 3

The method of claim 1 wherein the step of calculating a distance between said representative points is performed by an Euclidean distance metric.

Claim 4

The method of claim 1 wherein the step of calculating a distance between said representative points is performed by a Manhattan distance metric.

Claim 5

The method of claim 1 wherein the step of selecting a number of scattered data points from said representative points of said merged cluster comprises the steps of: e1) selecting a point from said representative points of said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; e2) selecting a point from said representative points of said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and e3) repeating step e2) until a desired number of scattered data points is obtained.

Claim 6

The method of claim 1 wherein the shrinking of said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 7

The method of claim 5 wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 8

The method of claim 1 wherein the predetermined termination condition is a obtaining a desired number of clusters.

Claim 9

The method of claim 1 wherein the number of scattered points selected is more than 10.

Claim 10

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; c) calculating a distance between said representative points of every cluster; d) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; e) calculating a mean of said representative points for said merged cluster; f) selecting a number of scattered points from said representative points of said merged cluster, said scattered data points representing an extent of said merged cluster; g) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; h) repeating steps c) through g) until a predetermined termination condition is met; and i) storing clusters which remain after step h) in a computer readable medium.

Claim 11

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; c) calculating a distance between said representative points of every cluster; d) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; e) calculating a mean of said representative points for said merged cluster; f) selecting a number of scattered points from said representative points of said merged cluster, said scattered data points representing an extent of said merged cluster; g) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; h) repeating steps c) through g) until a predetermined termination condition is met; and i) storing clusters which remain after step h) in a computer readable medium.

Claim 12

The method of claim 9 wherein said random set of data points has a size determined by Chernoff bounds.

Claim 13

The method of claim 9 further comprising the step of: j) assigning a cluster label to said data points not included in said random set of said data points.

Claim 14

The method of claim 9 wherein the step of calculating a distance between said representative points is performed by an Euclidean distance metric.

Claim 15

The method of claim 9 wherein the step of calculating a distance between said representative points is performed by a Manhattan distance metric.

Claim 16

The method of claim 9 wherein the step of selecting a number of scattered data points from said representative points of said merged cluster comprises the steps of: f1) selecting a point from said representative points of said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; f2) selecting a point from said representative points of said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and f3) repeating step f2) until a desired number of scattered data points is obtained.

Claim 17

The method of claim 9 wherein the shrinking of said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 18

The method of claim 15 wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 19

The method of claim 9 wherein the predetermined termination condition is obtaining a desired number of clusters.

Claim 20

The method of claim 9 wherein the number of scattered points selected is more than 10.

Claim 21

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 22

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 23

The method of claim 19 further comprising the step of: t) assigning a cluster label to said data points not included in said random set of said data points.

Claim 24

The method of claim 19 wherein the steps of calculating a distance between said representative points is performed by an Euclidean distance metric.

Claim 25

The method of claim 19 wherein the steps of calculating a distance between said representative points is performed by a Manhattan distance metric.

Claim 26

The method of claim 19 wherein the step of selecting a number of scattered data points from said merged cluster comprises the steps of: p1) selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; p2) selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and p3) repeating step p2) until a desired number of scattered data points is obtained.

Claim 27

The method of claim 19 wherein the shrinking of said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 28

The method of claim 24 wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 29

The method of claim 19 wherein the step of clustering said partitioned random set of data points is terminated when a final number of partial clusters equals a reduction constant.

Claim 30

The method of claim 26 wherein the reduction constant is 3.

Claim 31

The method of claim 19 wherein the step of clustering said partitioned random set of data points is terminated when a distance between a pair of partial clusters to be merged have increased above a predetermined threshold.

Claim 32

The method of claim 19 wherein said random set of data points is partitioned into 50 or less partitions.

Claim 33

The method of claim 19 wherein the step of clustering said partial clusters is terminated when a desired number of clusters are obtained.

Claim 34

The method of claim 19 wherein the number of scattered points selected is more than 10.

Claim 35

A computer based method of clustering related data in a large computer database while removing outliers from said data, said large computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster, said scattered data points representing an extent of said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) eliminating partial clusters comprised of outliers; l) clustering said partial clusters, said clustering comprising the steps of: m) establishing a cluster for said representative points of said partial clusters; n) calculating a distance between representative points of every cluster; o) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; p) calculating a mean of said representative points for said merged cluster; q) selecting a number of scattered data points from said merged cluster, said scattered data points representing an extent of said merged cluster; r) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; s) repeating steps n) through r) until a predetermined termination condition is met; and t) storing clusters which remain after step s) in a computer readable medium.

Claim 36

A computer based method of clustering related data in a large computer database while removing outliers from said data, said large computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster, said scattered data points representing an extent of said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) eliminating partial clusters comprised of outliers; l) clustering said partial clusters, said clustering comprising the steps of: m) establishing a cluster for said representative points of said partial clusters; n) calculating a distance between representative points of every cluster; o) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; p) calculating a mean of said representative points for said merged cluster; q) selecting a number of scattered data points from said merged cluster, said scattered data points representing an extent of said merged cluster; r) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; s) repeating steps n) through r) until a predetermined termination condition is met; and t) storing clusters which remain after step s) in a computer readable medium.

Claim 37

The method of claim 32 further comprising the step of: u) assigning a cluster label to said data points not included in said random set of said data points.

Claim 38

The method of claim 32 wherein the steps of calculating a distance between said representative points is performed by an Euclidean distance metric.

Claim 39

The method of claim 32 wherein the steps of calculating a distance between said representative points is performed by a Manhattan distance metric.

Claim 40

The method of claim 32 wherein the step of selecting a number of scattered data points from said merged cluster comprises the steps of: q1) selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; q2) selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and q3) repeating step q2) until a desired number of scattered data points is obtained.

Claim 41

The method of claim 32 wherein the shrinking of said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 42

The method of claim 37 wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 43

The method of claim 32 wherein the step of clustering said partitioned random set of data points is terminated when a final number of partial clusters equals a reduction constant.

Claim 44

The method of claim 39 wherein the reduction constant is 3.

Claim 45

The method of claim 32 wherein the step of clustering said partitioned random set of data points is terminated when a distance between a pair of partial clusters to be merged have increased above a predetermined threshold.

Claim 46

The method of claim 32 wherein said random set of data points is partitioned into 50 or less partitions.

Claim 47

The method of claim 32 wherein the step of eliminating partial clusters comprised of outliers is performed by eliminating partial clusters comprised of fewer than 3 representative points.

Claim 48

The method of claim 32 wherein the step of clustering said partial clusters is terminated when a desired number of clusters is obtained.

Claim 49

The method of claim 32 wherein the number of scattered points selected is more than 10.

Claim 50

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a computer database, said clustering method comprises the steps of: a) establishing a cluster for every data point in said computer database, said data points being representative points of said cluster; b) calculating a distance between said representative points of every cluster; c) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; d) calculating a mean of said representative points for said merged cluster; e) selecting a number of scattered data points from said representative points of said merged cluster, said scattered data points representing a shape of said merged cluster; f) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; g) repeating steps b) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.

Claim 51

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a computer database, said clustering method comprises the steps of: a) establishing a cluster for every data point in said computer database, said data points being representative points of said cluster; b) calculating a distance between said representative points of every cluster; c) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; d) calculating a mean of said representative points for said merged cluster; e) selecting a number of scattered data points from said representative points of said merged cluster, said scattered data points representing a shape of said merged cluster; f) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; g) repeating steps b) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.

Claim 52

The computer readable storage medium of claim 46, wherein the clustering method performs the step of calculating a distance between said representative points by an Euclidean distance metric.

Claim 53

The computer readable storage medium of claim 46, wherein the step of selecting a number of scattered data points from said representative points of said merged cluster of said clustering method comprises the steps of: e1) selecting a point from said representative points of said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; e2) selecting a point from said representative points of said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and e3) repeating step e2) until a desired number of scattered data points is obtained.

Claim 54

The computer readable storage medium of claim 46, wherein the clustering method performs the step of shrinking said number of scattered points by multiplying said number of scattered points by a shrinking fraction.

Claim 55

The computer readable storage medium of claim 49, wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 56

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large computer database, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; c) calculating a distance between said representative points of every cluster; d) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; e) calculating a mean of said representative points for said merged cluster; f) selecting a number of scattered points from said representative points of said merged cluster, said scattered data points representing a shape of said merged cluster; g) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; h) repeating steps c) through g) until a predetermined termination condition is met; and i) storing clusters which remain after step h) in a computer readable medium.

Claim 57

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large computer database, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; c) calculating a distance between said representative points of every cluster; d) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; e) calculating a mean of said representative points for said merged cluster; f) selecting a number of scattered points from said representative points of said merged cluster, said scattered data points representing a shape of said merged cluster; g) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; h) repeating steps c) through g) until a predetermined termination condition is met; and i) storing clusters which remain after step h) in a computer readable medium.

Claim 58

The computer readable storage medium of claim 51, wherein the clustering method determines a size of said random set of data points by Chernoff bounds.

Claim 59

The computer readable storage medium of claim 51, wherein the clustering method further comprises the step of: j) assigning a cluster label to said data points not included in said random set of said data points.

Claim 60

The computer readable storage medium of claim 51, wherein the step of selecting a number of scattered data points from said representative points of said merged cluster of said clustering method comprises the steps of: f1) selecting a point from said representative points of said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; f2) selecting a point from said representative points of said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and f3) repeating step f2) until a desired number of scattered data points is obtained.

Claim 61

The computer readable storage medium of claim 51, wherein the predetermined termination condition of the clustering method is obtaining a desired number of clusters.

Claim 62

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large computer database, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 63

A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large computer database, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 64

The computer readable storage medium of claim 56, wherein the clustering method further comprises the step of: t) assigning a cluster label to said data points not included in said random set of said data points.

Claim 65

The computer readable storage medium of claim 56 wherein the step of selecting a number of scattered data points said merged cluster of said clustering method comprises the steps of: p1) selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; p2) selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point; and p3) repeating step p2) until a desired number of scattered data points is obtained.

Claim 66

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; means for partitioning said random set of data points; means for clustering said partitioned random set of data points, said clustering means comprising: means for establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; means for calculating a distance between said representative points of every partial cluster; means for merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; means for calculating a mean of said representative points for said merged partial cluster; means for selecting a number of scattered data points from said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; means for establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; means for eliminating partial clusters comprised of outliers; means for clustering said partial clusters, said clustering means comprising: means for establishing a cluster for said representative points of said partial clusters; means for calculating a distance between representative points of every cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 67

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; means for partitioning said random set of data points; means for clustering said partitioned random set of data points, said clustering means comprising: means for establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; means for calculating a distance between said representative points of every partial cluster; means for merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; means for calculating a mean of said representative points for said merged partial cluster; means for selecting a number of scattered data points from said merged partial cluster, said scattered data points representing a shape of said merged partial cluster; means for establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; means for eliminating partial clusters comprised of outliers; means for clustering said partial clusters, said clustering means comprising: means for establishing a cluster for said representative points of said partial clusters; means for calculating a distance between representative points of every cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 68

The programmed computer database system of claim 59, further comprising means for assigning a cluster label to said data points not included in said random set of said data points.

Claim 69

The programmed computer database system of claim 59, wherein the means for selecting a number of scattered data points from said merged cluster comprises: means for selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; and means for selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point.

Claim 70

The programmed computer database system of claim 59, wherein the means for shrinking said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 71

The programmed computer database system of claim 62, wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 72

A programmed computer database clustering system comprising: means for establishing a cluster for every data point in a computer database stored on a computer readable medium, said data points being representative points of said clusters; means for calculating a distance between said representative points of every partial cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 73

A programmed computer database clustering system comprising: means for establishing a cluster for every data point in a computer database stored on a computer readable medium, said data points being representative points of said clusters; means for calculating a distance between said representative points of every partial cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 74

The programmed computer database system of claim 64, wherein the means for selecting a number of scattered data points from said merged cluster comprises: means for selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; and means for selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point.

Claim 75

The programmed computer database system of claim 64, wherein the means for shrinking said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 76

The programmed computer database system of claim 66, wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 77

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; means for establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; means for calculating a distance between said representative points of every cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 78

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; means for establishing a cluster for said random set of data points, said random set of data points being representative points of said cluster; means for calculating a distance between said representative points of every cluster; means for merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; means for calculating a mean of said representative points for said merged cluster; means for selecting a number of scattered data points from said merged cluster, said scattered data points representing a shape of said merged cluster; means for establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; and means for storing clusters which remain in a computer readable medium.

Claim 79

The programmed computer database system of claim 68, further comprising means for assigning a cluster label to said data points not included in said random set of said data points.

Claim 80

The programmed computer database system of claim 68, wherein the means for selecting a number of scattered data points from said merged cluster comprises: means for selecting a point from said merged cluster that is furthest away from the mean of said merged cluster to be a scattered data point; and means for selecting a point from said merged cluster that is furthest away from previously selected scattered data points to be a scattered data point.

Claim 81

The programmed computer database system of claim 68, wherein the means for shrinking said number of scattered points is performed by multiplying said number of scattered points by a shrinking fraction.

Claim 82

The programmed computer database system of claim 71, wherein the shrinking fraction is selected from a range of 0.2 to 0.7.

Claim 83

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until either a final number of partial clusters equals a reduction constant or a distance between a pair of partial clusters to be merged has increased above a predetermined threshold; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 84

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until either a final number of partial clusters equals a reduction constant or a distance between a pair of partial clusters to be merged has increased above a predetermined threshold; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a predetermined termination condition is met; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 85

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a desired number of clusters is obtained; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 86

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, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until a predetermined termination condition is met; k) clustering said partial clusters, said clustering comprising the steps of: l) establishing a cluster for said representative points of said partial clusters; m) calculating a distance between representative points of every cluster; n) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; o) calculating a mean of said representative points for said merged cluster; p) selecting a number of scattered data points from said merged cluster; q) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; r) repeating steps m) through q) for said merged pair of clusters until a desired number of clusters is obtained; and s) storing clusters which remain after step r) in a computer readable medium.

Claim 87

A computer based method of clustering related data in a large computer database while removing outliers from said data, said large computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until either a final number of partial clusters equals a reduction constant or a distance between a pair of partial clusters to be merged has increased above a predetermined threshold; k) eliminating partial clusters comprised of outliers; l) clustering said partial clusters, said clustering comprising the steps of: m) establishing a cluster for said representative points of said partial clusters; n) calculating a distance between representative points of every cluster; o) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; p) calculating a mean of said representative points for said merged cluster; q) selecting a number of scattered data points from said merged cluster; r) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; s) repeating steps n) through r) until a predetermined termination condition is met; and t) storing clusters which remain after step s) in a computer readable medium.

Claim 88

A computer based method of clustering related data in a large computer database while removing outliers from said data, said large computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) partitioning said random set of data points; c) clustering said partitioned random set of data points, said clustering comprising the steps of: d) establishing a partial cluster for said partitioned random set of data points, said partitioned random set of data points being representative points of said partial cluster; e) calculating a distance between said representative points of every partial cluster; f) merging a pair of partial clusters having a closest pair of representative points into a merged partial cluster, said merged partial cluster having representative points; g) calculating a mean of said representative points for said merged partial cluster; h) selecting a number of scattered data points from said merged partial cluster; i) establishing a new set of representative points for said merged partial cluster by shrinking said number of scattered points toward the mean of said merged partial cluster; j) repeating steps e) through i) until either a final number of partial clusters equals a reduction constant or a distance between a pair of partial clusters to be merged has increased above a predetermined threshold; k) eliminating partial clusters comprised of outliers; l) clustering said partial clusters, said clustering comprising the steps of: m) establishing a cluster for said representative points of said partial clusters; n) calculating a distance between representative points of every cluster; o) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; p) calculating a mean of said representative points for said merged cluster; q) selecting a number of scattered data points from said merged cluster; r) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; s) repeating steps n) through r) until a predetermined termination condition is met; and t) storing clusters which remain after step s) in a computer readable medium.

Claim 89

A computer based method of clustering related data in a computer database, said computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) establishing a cluster for every data point in said computer database, said data points being representative points of said cluster; b) calculating a distance between said representative points of every cluster; c) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; d) calculating a mean of said representative points for said merged cluster; e) selecting a number of scattered data points from said representative points of said merged cluster; f) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; g) repeating steps b) through f) until a desired number of clusters is obtained; and h) storing clusters which remain after step g) in a computer readable medium.

Claim 90

A computer based method of clustering related data in a computer database, said computer database stored on a computer readable medium and including a set of data points, the method comprising the steps of: a) establishing a cluster for every data point in said computer database, said data points being representative points of said cluster; b) calculating a distance between said representative points of every cluster; c) merging a pair of clusters having a closest pair of representative points into a merged cluster, said merged cluster having representative points; d) calculating a mean of said representative points for said merged cluster; e) selecting a number of scattered data points from said representative points of said merged cluster; f) establishing a new set of representative points for said merged cluster by shrinking said number of scattered points toward the mean of said merged cluster; g) repeating steps b) through f) until a desired number of clusters is obtained; and h) storing clusters which remain after step g) in a computer readable medium.