US 6,567,936 B1 · Data clustering using error-tolerant frequent item sets

Abstract

A generalization of frequent item sets to error-tolerant frequent item sets (ETF) is disclosed, together with its application in data clustering using error-tolerant frequent item sets to either build clusters or as an initialization technique for standard clustering algorithms. Efficient feasible computational algorithms for computing ETF's from very large databases is presented. In one embodiment, a method determines a plurality of weak ETF's, which are strongly tolerant of errors, and determines a plurality of strong ETF's therefrom, which are less tolerant of errors. The resulting clusters can be used as an initial model for a standard clustering approach, or may themselves be used as the end clusters. In one embodiment, the data covered by the strong clusters is removed from the data, and the process is repeated, until no more weak clusters can be found. Te invention includes methods for constructing ETF's from more general data types: data sets that include categorical discrete, continuous, and binary attributes.

Claims54

Dependent claims

A computer-implemented method for clustering a database of data organized into records and dimensions comprising:

determining a plurality of weak ETF's among the data of the database, the weak ETF's tolerant of errors therein;
and,
determining a plurality of strong ETF's among the plurality of weak ETF's, the strong ETF's less tolerant of errors therein as compared to the weak ETF's.

A machine-readable medium having instructions stored thereon for execution by a processor to perform a method for clustering a database reducible to binary data organized into records and dimensions comprising:

determining a plurality of weak clusters among the data of the database, each weak cluster comprising a set of records and a set of defining dimensions such that at least a predetermined minimum number threshold of records is included within the set of records, and a fraction of values unequal to a predetermined value occurring over the set of records over the set of defining dimensions is not greater than a predetermined maximum error threshold;
and,
determining a plurality of strong clusters among the plurality of weak clusters, each strong cluster comprising a set of records and a set of defining dimensions such that at least a predetermined minimum number threshold of records is included within the set of records, and a fraction of values unequal to a predetermined value occurring for each record over the set of defining dimensions is not greater than a predetermined maximum error threshold.

Dependencies are inferred from the claim text.

Data clustering using error-tolerant frequent item sets

Life of this patent

Data clustering using error-tolerant frequent item sets

Life of this patent

Abstract

Claims54