Data clustering using error-tolerant frequent item sets

[0002] This invention relates generally to the clustering of very large data sets, such as transactional, categorical, and binary data, and more particularly to such clustering using error-tolerant frequent item sets.

[0003] With the advent of the Internet, and especially electronic commerce (“e-commerce”) over the Internet, the use of data analysis tools, such as data mining, has increased. In e-commerce and other Internet and non-Internet applications, databases are generated and maintained that have large amounts of information, so that they can be analyzed, or “mined,” to learn additional information regarding customers, users, products, etc. That is, data analysis tools provide for leveraging the data already contained in databases to learn new insights regarding the data by uncovering patterns, relationships, or correlations.

[0004] A common data analysis operation is data clustering, which is also known within the art as database segmentation or data segmentation. Clustering targets finding groups of records such that members of each cluster are more similar to records within the cluster than they are to records in other clusters. Clustering allows for frequent item sets within the data to be detected once the clusters are discovered. Frequent items sets are sets of items (combinations of attributes of entities or records) that occur with significant frequency in the data, Finding such frequent groups, such as groups of users, groups of purchasers, etc., instead of focusing on just the items themselves (products or web pages) allows for new insights to be obtained from the data. For example, a purchaser who has purchased items X and Y may also be predicted as likely to purchase item Z, based on other purchasers who have purchased items X and Y also having had purchased item Z. Thus, a retailer knowing this information may be compelled directly advertise item Z to this purchaser, or perhaps make a special offer or customized coupon for it, or even discount one of the items and hope to make margin on the other correlated items in the cluster.

[0005] Many clustering approaches, such as the Expectation Maximization (EM) or the K-Means approaches known within the art, typically require an initial specification of the full clustering model. The initial specification may be randomly selected or generated by some other means. Once this initial model is specified, the approaches iteratively refine the initial model to maximize the fit of the clustering model to the data. A drawback to such approaches, however, is that the function measuring the fit of the clustering model to the data has many locally optimal solutions that are globally sub-optimal. The clustering approach can only guarantee convergence to a locally optimal solution, and not a globally optimal solution. Hence, many other better solutions may be missed simply because the initial model was not good enough. Thus, the initial model selection plays a large role in determining the quality of the solution obtained.

[0006] Usually the number of local solutions is very large when fitting databases of even modest size to a model. Many of the local solutions are often unsatisfactory. For example, when clustering high-dimensional sparse databases—that is, databases where each record (e.g. customer) only specifies values for a very small subset of all possible attributes or items (e.g. products). For example, of 100,000 products available in the store, each customer (record) usually purchases only 5 or 6 items. Another example is web browsing: out of millions of possible pages on the web, a typical user only visits a tiny fraction of them.—In such a situation, there may exist many local clustering solutions that have empty clusters, which are clusters containing no records of data. Another property that makes the clustering problem difficult is skewed distributions over the items (attributes): a predetermined item dominates most items of the databases, such that variance therefrom is infrequent. When the frequency of items drops off geometrically, e.g. frequency of item i is proportional to 1/i, the data is said to obey a Zipf distribution. The Zipf distribution is a skewed distribution and is observed in web-browsing data, product-purchasing data, text-data keyword count data, and many other sparse data bases in practice.

[0007] Given the above difficulties, a common approach within the prior art is to search for good clustering solutions by re-running the clustering approach from many different random initial cluster models, in the hope of finding a good solution. However, there are no guarantees, nor probabilistic arguments, that a good clustering solution will be found without employing methods exponential in running time. These methods are infeasible to apply to large databases. Even re-running the clustering approach from many different initial cluster models is computationally prohibitive for large-scale databases. For example, given a database of even modest size, the time required for running a clustering approach from a single initial clustering model can take hours or even days. Applying the approach from many different randomly selected initial clustering models can thus take many days. And again, there is no guarantee that a good solution will be found.

[0008] For this and other reasons, therefore, there is a need for the present invention.

[0009] The invention relates to data clustering using error-tolerant frequent item sets (denoted as ETF's). In one embodiment, a method first determines a plurality of weak error-tolerant frequent item sets, which are strongly tolerant of errors, and then determines a plurality of strong error-tolerant frequent item sets (ETF's) therefrom, which are less tolerant of errors. The resulting error-tolerant frequent item sets can be used as an initial model for a standard clustering approach such as the EM approach, or may themselves be used as the end clusters. Furthermore, in one embodiment, the data covered by the strong ETF's is removed from the data, and the process is repeated, until no more weak ETF's can be found therein. The data can be binary, categorical, or continuous data.

[0010] Embodiments of the invention provide for advantages not found within the prior art. Traditional frequent item sets are defined to be exact: they are supported only by the data records that have all the items appearing in the frequent item set. Efficient algorithms for discovering frequent item sets rely on this definition. The definition of frequent item sets is generalized herein to Error-Tolerant Frequent Item sets (ETF) and an efficient algorithm is provided for computing them over very large databases. Relaxing the error tolerance of ETF's has been determined not only to lead to more general summaries of the data than traditional frequent item sets, but also to lead to initial clustering solutions that are much better than known methods for selecting initial clustering solutions. This in turn dramatically reduces the computational resources necessary to obtain improved clustering solutions. Furthermore, the chance of converging to a clustering solution with empty clusters has been found to be significantly reduced—an important problem to avoid, while measures quantifying the fit of the clustering model to the data have been found to be maximized.

[0011] The invention includes computer-implemented methods, machine-readable media, computerized systems, and computers of varying scopes. Other aspects, embodiments and advantages of the invention, beyond those described here, will become apparent by reading the detailed description and with reference to the drawings.

[0012] FIG. 1 is a diagram of an operating environment in conjunction with which embodiments of the invention can be practiced;

[0013] FIG. 2 is a diagram showing a representative set of binary transactional data in conjunction with which embodiments of the invention can be practiced;

[0014] FIG. 3 is a table of data showing a weak and a strong ETF's therein, according to an embodiment of the invention;

[0015] FIG. 4 is a flowchart of approaches to find weak and strong clusters within data of a database, according to varying embodiments of the invention;

[0016] FIG. 5 is a table of categorical discrete data in conjunction with which embodiments of the invention may be practiced; and,

[0017] FIG. 6 is a table of binary data that is the result of transformation of the categorical discrete data of FIG. 5 thereto, in accordance with an embodiment of the invention.

[0018] In the following detailed description of exemplary embodiments of the invention, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration specific exemplary embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical, electrical and other changes may be made without departing from the spirit or scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

[0019] Some portions of the detailed descriptions which follow are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated.

[0020] It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like. It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as processing or computing or calculating or determining or displaying or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0021] Operating Environment

[0022] Referring to FIG. 1, a diagram of the hardware and operating environment in conjunction with which embodiments of the invention may be practiced is shown. The description of FIG. 1 is intended to provide a brief, general description of suitable computer hardware and a suitable computing environment in conjunction with which the invention may be implemented. Although not required, the invention is described in the general context of computer-executable instructions, such as program modules, being executed by a computer, such as a personal computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types.

[0023] Moreover, those skilled in the art will appreciate that the invention may be practiced with other computer system configurations, including hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PC's, minicomputers, mainframe computers, and the like. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

[0024] The exemplary hardware and operating environment of FIG. 1 for implementing the invention includes a general purpose computing device in the form of a computer 20, including a processing unit 21, a system memory 22, and a system bus 23 that operatively couples various system components include the system memory to the processing unit 21. There may be only one or there may be more than one processing unit 21, such that the processor of computer 20 comprises a single central-processing unit (CPU), or a plurality of processing units, commonly referred to as a parallel processing environment. The computer 20 may be a conventional computer, a distributed computer, or any other type of computer; the invention is not so limited.

[0025] The system bus 23 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory may also be referred to as simply the memory, and includes read only memory (ROM) 24 and random access memory (RAM) 25. A basic input/output system (BIOS) 26, containing the basic routines that help to transfer information between elements within the computer 20, such as during start-up, is stored in ROM 24. The computer 20 further includes a hard disk drive 27 for reading from and writing to a hard disk, not shown, a magnetic disk drive 28 for reading from or writing to a removable magnetic disk 29, and an optical disk drive 30 for reading from or writing to a removable optical disk 31 such as a CD ROM or other optical media.

[0026] The hard disk drive 27, magnetic disk drive 28, and optical disk drive 30 are connected to the system bus 23 by a hard disk drive interface 32, a magnetic disk drive interface 33, and an optical disk drive interface 34, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for the computer 20. It should be appreciated by those skilled in the art that any type of computer-readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read only memories (ROMs), and the like, may be used in the exemplary operating environment.

[0027] A number of program modules may be stored on the hard disk, magnetic disk 29, optical disk 31, ROM 24, or RAM 25, including an operating system 35, one or more application programs 36, other program modules 37, and program data 38. A user may enter commands and information into the personal computer 20 through input devices such as a keyboard 40 and pointing device 42. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 21 through a serial port interface 46 that is coupled to the system bus, but may be connected by other interfaces, such as a parallel port, game port, or a universal serial bus (USB). A monitor 47 or other type of display device is also connected to the system bus 23 via an interface, such as a video adapter 48. In addition to the monitor, computers typically include other peripheral output devices (not shown), such as speakers and printers.

[0028] The computer 20 may operate in a networked environment using logical connections to one or more remote computers, such as remote computer 49. These logical connections are achieved by a communication device coupled to or a part of the computer 20; the invention is not limited to a particular type of communications device. The remote computer 49 may be another computer, a server, a router, a network PC, a client, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 20, although only a memory storage device 50 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local-area network (LAN) 51 and a wide-area network (WAN) 52. Such networking environments are commonplace in office networks, enterprise-wide computer networks, intranets and the Internal, which are all types of networks.

[0029] When used in a LAN-networking environment, the computer 20 is connected to the local network 51 through a network interface or adapter 53, which is one type of communications device. When used in a WAN-networking environment, the computer 20 typically includes a modem 54, a type of communications device, or any other type of communications device for establishing communications over the wide area network 52, such as the Internet. The modem 54, which may be internal or external, is connected to the system bus 23 via the serial port interface 46. In a networked environment, program modules depicted relative to the personal computer 20, or portions thereof, may be stored in the remote memory storage device. It is appreciated that the network connections shown are exemplary and other means of and communications devices for establishing a communications link between the computers may be used.

[0030] (Transactional or Sparse) Binary Data

[0031] In this section of the detailed description, transactional (sparse) binary data is described, in conjunction with which embodiments of the invention may be practiced. It is noted, however, that the invention is not limited to application to transactional binary data. In other embodiments, categorical discrete data, and continuous data, are amenable to embodiments of the invention, as is described in a later section of the detailed description.

[0032] Referring to FIG. 2, a diagram of transactional binary data in conjunction with which embodiments of the invention may be practiced is shown. The data 206 is organized in a chart 200, with rows 202 and columns 204. Each row, also referred to as a record, in the example of diagram of FIG. 2 corresponds to a user, such as users 1 . . . n. In general, the term user, entity, row, or records is used to represent a collection of transactions pertaining to a single entity. These could be products bought by a shopper, in which case the record consists of the collection of all products purchased by a particular shopper. In general the semantics of a row in the binary data table need not be that of users. Each column is referred to as a dimension. In the example of FIG. 2, each column corresponds to a product, such as products 1 . . . m. But, in general the semantics of a column in the binary table need not be that of products. Each entry within the data 206, also referred to as each item within the data 206, corresponds to whether the user has purchased the particular product, and is a binary value, where 1 corresponds to the user having purchased the particular product, and 0 corresponds to the user not having purchased the particular product. Thus, I23 corresponds to whether user 2 has purchased product 3, In2 corresponds to whether user n has purchased item 2, I1m corresponds to whether user 1 has purchased item m, and Inm corresponds to whether user n has purchased item m.

[0033] The data 206 is referred to as sparse, because most items have the value 0, indicating the fact that for any particular user, the user has likely not purchased a given product in the example. The data 206 is binary in that each item can have either the value 0 or the value 1. The data 206 is transactional in that the data was acquired by logging transactions of users' purchasing activity over a given period of time. It is noted that the particular correspondence of the rows 202 to users, and of the columns 204 to products, is for representative example purposes only, and does not represent a limitation on the invention itself. For example, the columns 204 in other embodiment could represent web in pages that the users have viewed. In general, the rows 202 and the columns 204 can refer to any type of features. The columns 204 are interchangeably referred to herein as dimensions. Furthermore, it is noted that in large databases, the values n for the number of rows 202 can be quite large, approaching hundreds of thousands to tens of millions or more. And m for the number of columns 204 can be quite large, approaching the tens and the hundreds of thousands, if not more.

[0034] A cluster over the data 206 is defined generally as a set of dimensions, referred to as the defining dimensions, where a predetermined value, such as 1 or 0, appears with high probability over a subset of the records (rows). Typically the “distinguished value” is ‘1’. Determining the clusters for the data 206 is referred to as clustering of the data 206, or segmentation of the data 206. Where n and m are large, utilizing prior art clustering techniques generally results in finding many empty clusters—that is, clusters that have no data records (equivalently, rows of the data table) associated with them. A phenomenon equivalent to finding empty clusters is to have some clusters converge on identical or near-identical centroids (parameters). In this case, none of the clusters may seem empty, but in effect they are redundant. Furthermore, prior art clustering techniques generally are time-intensive, and can take hours to days to run for a large data set. Embodiments of the invention relate to finding clusters in significantly less time, with significantly greater opportunity of finding non-empty clusters that are different from each other. Embodiments of the invention can be used as an initial input to prior art clustering techniques, or can be used on their own to find clusters within data. A cluster is also referred to herein as a frequent item set, which are items within the data 206 that frequently occur together within a transaction.

[0035] Prior art definitions of a “cluster” typically include a summary of the data records belonging to the cluster (i.e. the “members” of the cluster) and a criterion used to assign data records to a cluster. In typical clustering algorithms, the membership is one cluster per record. Probabilistic approaches to clustering require a statistical model of the data associated with each cluster. In this invention, the concept of error-tolerant frequent item sets (ETF) is used to summarize the members of a cluster. Specifically, the ETF represents the following cluster summary: the records belonging to a cluster defined by an ETF having defining dimensions DD have (approximately) the same attribute values over the defining dimensions DD. The ETF says nothing about non-defining dimensions, in contrast to usual clustering methodologies where a cluster specifies a complete distribution on all dimensions. Even distance-based clustering methods, such as K-means, base the distance on all dimensions. ETF's are defined and described by their defining dimensions only. They also admit overlap between clusters. The criteria used to assign a data record to a cluster is based on observing the attribute values for the data record over DD and if these values are “similar” to the ETF, then the record is a member of the cluster defined by the ETF (specific embodiments of this membership criteria are given below).

[0036] Let I be the set of all items. Before defining the error tolerant frequent item set, ε is defined as a value between 0 and 1, representing the allowable error. Furthermore, κ is defined as a value between 0 and 1 that denotes the proportion of data records that “support” an ETF. An error-tolerant frequent itemset (ETF) is defined as follows: an item set E⊂I is an error-tolerant item set having error ε and support κ with respect to a database D having n transactions if there exists at least κ·n transactions in which the probability of observing a 1 (the “distinguished value” that indicates an event occurred) over the item set is not less than 1−ε. Note that even though the definition only references the defining dimensions (in contrast to clustering which usually refers to all dimensions), it can be viewed as defining a group of records that contain a “vertical” slice that satisfies the definition of the ETF. Note that ETF existence is not tied to a specific set of records (as is the case for frequent item sets), but rather as long as enough records exist to satisfy the requirement. Hence the support set is not necessarily unique for ETF's, in contrast to traditional Frequent Item sets methods. By defining a membership function to go along with a set of ETF's, clusters can be based on ETF's.

[0037] When attempting to cluster large binary-valued databases, prior art techniques are often plagued by finding many empty clusters (clusters having no members) and clusters which are the same (2 or more clusters have near-identical parameters, hence describe the same set of records) and are redundant. Embodiments of the invention can be used as an initial input to prior art clustering techniques, or can be used on their own to find clusters within data. The methods of this invention help prior art clustering ethods reach better solutions when initialized using the methods presented in this invention.

[0038] Weak and Strong Error-Tolerant Frequent Item Sets (ETF's)

[0039] In this section of the detailed description, weak and strong ETF's, as these terms are used herein, are described. In general, embodiments of the invention introduce error-tolerant frequent item sets—that is, ETF's—which are collections of data columns that are more tolerant of errors therewithin as compared to standard frequent item sets as typically known within the art. From a mathematical perspective, an error-tolerant item set E⊂I is defined as having error ε (value between 0 and 1) and support κ (value between 0 and 1) with respect to a database D having n transactions if there exists at least κ·n transactions in which the probability of observing a 1 (the “distinguished value”) over the item set is not less than 1−ε. In particular, two types of error-tolerant frequent item sets are utilized, referred to as weak and strong ETF's. Standard frequent item sets can be viewed as a special case of the ETF generalization presented in this invention. They represent the special case when ε=0.

[0040] A weak ETF is strongly tolerant of errors therein. More specifically, in one embodiment of the invention, a weak ETF is defined as a set of records R and a set of defining dimensions DD, such that R contains at least a predetermined number of records, referred to as minSupport number of records (e.g. minSupport=κ·n), where the fraction values not equal to the predetermined or distinguished value (i.e. errors), over the set of records R over the identified defining dimensions DD is not greater than a predetermined percentage, referred to as maxError (e.g. maxError=ε) (equivalently, the fraction of values equal to the predetermined or distinguished value (i.e. non-errors), over the set of records R over the defining dimensions DD is not less than 1−maxError). In other words, a weak ETF includes a set of records and a set of defining dimensions such that at least a predetermined minimum number threshold of records (minSupport) is included within the set of records, and a fraction of errors (values not equal to the predetermined or distinguished value (either 0 or 1)) occurring over the set of records over the set of defining dimensions is not greater than a predetermined maximum error threshold (maxError). From a mathematical perspective, a weak ETF is defined as a set of items, called defining dimensions DD⊂I, such that there exists a subset of transactions R⊂T, |R|≧κ·n transactions and, $\frac{\sum _{x\in R}\sum _{d\in DD}d\left(x\right)}{\left|R\right|·\left|DD\right|}\ge \left(1-ϵ\right).$

[0041] Here the value of d(x) is “1” when dimension (column) d of record (row) x is equal to the predetermined or distinguished value of interest. A strong ETF is weakly tolerant of errors therein. More specifically, in one embodiment of the invention, a strong ETF is defined as a set of records R and a set of defining dimensions DD, such that R contains at least a predetermined number of records, referred to as minSupport number of records, where, for each of these records, the fraction of errors (values not equal to the predetermined or distinguished value), over the defining dimensions DD is not greater than a predetermined error percentage, referred to as maxError. In other words, a strong cluster includes a set of records and a set of defining dimensions such that at least a predetermined minimum number threshold of records (minSupport) is included within the set of records, and a fraction of errors for each record over the set of defining dimensions is not greater than a predetermined maximum error threshold (maxError). From a mathematical perspective, a strong ETF is defined as a set of items, called defining dimensions DD⊂I, such that there exists a subset of transactions R⊂T consisting of at least κ·n transactions and, for each of r∈R, the fraction of items in DD which are present (value for items in DD having the predetermined or distinguished value) in r is at least 1−ε.

[0042] The predetermined or distinguished value as used in the above definitions is typically 1 (a value that indicated that an event occurred as opposed to not occurred—e.g. 1 might indicates a customer bought a product, while 0 or NULL indicates she has not). That is, the data set is typically sparse such that most of the items are typically 0. Therefore, it is noted that the weak definition requires that a sub-matrix within a data set, where the sub-matrix is defined by the records in R and the columns in DD, be mostly 1's, with the fraction of 0's not greater than MaxError. For the strong definition, each record within R must be mostly 1's, with the fraction of 0's (over the defining dimensions) not greater than MaxError. Thus, a strong ETF satisfies the weak definition, but not vice-versa. In one embodiment, for both weak and strong ETF's, the set DD is referred to as defining the ETF, where minSupport is referred to as the support threshold, and MaxError the error threshold. Furthermore, a set of defining dimensions DD is referred to as maximal if and only if DD defines an ETF and no superset of DD defines an ETF.

[0043] An example is illustrative in showing the definitions of weak and strong ETF's. Referring to the table of FIG. 3, where the support threshold is 25% and the error threshold is 20%, the columns [12345] are a strong ETF, particularly a maximal strong ETF; the columns [1234] are also a strong ETF, but a non-maximal strong ETF, since the columns [12345] are a superset of the columns [1234]; and, the columns [6789] are a weak ETF, particularly a maximal weak ETF, but are not a strong ETF.

[0044] As is described in the next section of the detailed description, embodiments of the invention find strong ETF's within data sets. These strong ETF's can be used as the initial starting point for prior art clustering techniques to further refine them, or, they can be used as the clusters of the data set themselves. The weak ETF's are particularly used to assist in finding strong ETF's.

[0045] Finding ETF's According to Varying Embodiments of the Invention

[0046] In this section of the detailed description, manners by which ETF's are found according to varying embodiments of the invention are described. The description is made in conjunction with the flowchart of FIG. 4. In particular, 400, 402, 404, 406, 408, 410, 412, 414, and 416 represent a first approach to find ETF's, according to an embodiment of the invention. 418 added to the first approach represents a second approach to find ETF's, according to an embodiment of the invention. 420 added to the second approach represents a third approach to find ETF's, according to an embodiment of the invention. The flowchart of FIG. 4 is now described in detail.

[0047] From the starting point in 400, the method proceeds to 402, where ETF seeds are selected, or picked. In particular, a data set is scanned, and all dimensions where the number of occurrences of 1's is at least minSupport times (1−maxError) are selected. At this stage, dimensions are considered that have a global count of “1” near minSupport by a margin defined by the amount of error that will be tolerated (i.e. 1-maxError). These dimensions are referred to as high support dimensions, and their indices are stored in an array referred to as highSupport. Each high support column is treated as a set to be grown into a potential cluster. Another array, referred to as candidate ETF's, is created to track the ETF's being grown. Each of its elements is a list of dimensions representing a ETF that has been grown so far, initialized to the seeds. From a mathematical perspective, 402 can be described as finding all dimensions d_iwhere the global count of 1's is at least κn(1−ε). The term κn denotes minSupport, n is the total number of rows in the data table and ε is the tolerated maxError. Each of these dimensions forms a singleton set {d_i} which defines a weak ETF; each of these singleton sets is referred to as a seed. A counter i is set to 1.

[0048] If there are no such weak ETF seeds, then the method proceeds from 404 to 406, where it is finished. Otherwise, the method proceeds from 404 to 408, where all the seeds are grown into weak ETF's in parallel. That is, the seeds are grown while maintaining the definition of a weak ETF's. In one embodiment, the ETF's are grown as is now described. For each element c in candidate ETF's, the following approach is used to grow the element by one dimension:

[0049] It is noted that this approach only requires one pass over the data.

[0050] That is, given a set of m candidate dimensions, their eligibility to be defining dimensions for a weak ETF's can be tested with one pass over the data. While scanning the data, m+1 counters C₀, C₁, . . . , C_mare maintained, where C_ikeeps track of the number of records that have i “1”s out of m candidate dimensions, i=0,1,2, . . . , m. From these counters, the maximum t is found such that $\sum _{i=t}^m{C}_i\ge \kappa ·n,$

[0051] where n is the total number of records in the database. With this t value, let $C_t^{\prime }=\sum _{i=t}^m{C}_i-\kappa ·n.$

[0052] Define $\delta =\frac{\left(\sum _{i=t+1}^m\left(m-i\right)C_i\right)+\left(m-t\right)\left(C_t-C_t^{\prime }\right)}{\kappa ·n·m}.$

[0053] Then, the m candidate dimensions are eligible to be defining dimensions for a weak ETF if and only if δ≦ε, and δ is referred to as the error rate of this weak ETF.

[0054] The above algorithm is actually doing the following: it ranks all rows based on the number of “1”s out of m candidate dimensions, picks the top κn rows, and checks the probability δ of “0”s occurring among the κn rows over m candidate dimensions. Such ranking ensures that, if we picked any other set of κn rows, the probability of “0”s occurring among those rows over m candidate dimensions would be at least as big as δ. Therefore, if δ>ε, no weak ETF exists. If δ≦ε, these κn rows and m dimensions form a weak ETF, so a weak ETF exists.

[0055] It is noted that the probability of “0”s along a particular dimension d within the weak ETF may also be desired to be known. To do this, the above approach is augmented by keeping an extra set of m+1 counters Z₀, Z₁, . . . , Z_m, where Z₁keeps track of how many 0's there are in this particular dimension d, over those data points that have i 1's out of m candidate dimensions. These counters, together with the other counters C₀, C₁, . . . , C_m, can be updated in the same pass over the database. Then, the probability of 0's along dimension d within the weak ETF is approximately the fraction: $\frac{\left(\sum _{i=t+1}^m{Z}_i\right)+\max \left(0,Z_t-C_t^{\prime }\right)}{\kappa ·n}.$

[0056] Thus, in 408, for every seed that contains i dimensions, it is grown by adding a dimension to it so that the new seed still defines a weak ETF. If one or more such dimensions can be found, only one of them is kept. If the weak ETF's cannot be grown further, then the method proceeds from 410 to 412. Otherwise, 408 is repeated, incrementing i by 1, until the weak ETF's cannot be grown further.

[0057] In 412, the candidate (weak) ETF's are pruned, and duplicates are removed. Duplicate ETF's can exist because the ETF's are grown from different seeds, such that two ETF's may ultimately grow to the same candidate ETF. In one embodiment, the candidate ETF's are pruned, and duplicates are removed, according to the following approach:

[0058] As used in the above approach, the chi-square statistic in one embodiment is the following:

[0059] Thus, 400, 402, 404, 406, 408, 410 and 412 of FIG. 4 are used to determine the weak ETF's among the data of a database, where the weak ETF's are strongly tolerant of errors. Specifically, in 402, ETF seeds—single dimensions within the data—are selected, and in 408 and 410, they are each grown into a weak ETF. The ETF seeds are such that each includes at least a predetermined number of records—minSupport—of the data of the database that has a value of 1 (the predetermined or distinguished value) for that dimension. The seeds are grown into weak ETF's dimension by dimension, such that a dimension is added to a seed if it satisfies a predetermined criterion for weak ETF's; that is, if adding the dimension to the seed maintains a weak ETF. Thus, the weak ETF criterion is in one embodiment whether the fraction of 0's occur for the dimension to be added that is not greater than the maximum error threshold. The pruning in 412 then prunes the high-support ETF's from the weak ETF's that have been grown which have random dimensions (discovered, for instance if the Chi-Squared statistic has a rather small value).

[0060] Next, in 414 and 416, the strong ETF's are obtained from the weak ETF's. First, in 414, each record within the data set, also referred to as each data point, is associated with at most one candidate (weak) ETF's, using a strong ETF criterion. This can be accomplished in one embodiment by:

[0061] Next, in 416, the ETF's associated with fewer than minSupport records are removed. In other words, only those ETF's that are strong ETF's remain after 414 and 416, and more specifically, only the maximal strong ETF's.

[0062] Thus, 414 and 416 are used to determine the strong ETF's among the data of a database from the weak ETF's, where the strong ETF's are weakly (less) tolerant of errors as compared to the weak ETF's. This is accomplished in 414 and 416 first by setting the strong ETF's to the weak ETF's (that is, the strong ETF's will be determined from the weak ETF's, and thus are a priori set to the weak ETF's before determining them), assigning each record of the data of the database to no more than one of the strong ETF's upon determining that the record satisfies a predetermined criterion for strong ETF's (in 414), and then removing low-support ETF's (in 416). The predetermined criterion in one embodiment is whether the fraction of 0's occurring for the record over a set of defining dimensions is not greater than a predetermined maximum error threshold.

[0063] The resulting strong ETF's can in one embodiment be deemed as the clusters of the database. However, in another embodiment, further processing is performed.

[0064] Specifically, in 418 statistics are collected over all dimensions over the records associated with the strong ETF's that have been determined through 416, and these ETF's are used as an initial model for a traditional clustering technique that is known within the art—for example, the Expectation Maximization (EM) approach known within the art. The resulting ETF's from 418 can then also be deemed in this embodiment as the clusters of the database. Thus, in 418, the strong ETF's as determined through 416 are refined using a different clustering approach, such as EM. In one embodiment, where the EM approach is used as the different clustering approach, statistics are collected as follows:

[0065] In still another embodiment, further processing is performed to obtained the clusters of the database. Specifically, in 420, all records—that is, all data points—covered by the clusters determined through 418 are removed from the database. The method then proceeds back to 402, to select new ETF seeds from the remaining data, and the method continues until in some iteration no more seeds are available, in which case the method ends at 406. That is, the method is repeated until one additional weak ETF seed cannot be found. The removal in 420 of records is accomplished by concluding that a record is covered by a (strong) ETF upon determining that a fraction of 0's occurring for the record over the set of defining dimensions is not greater than the predetermined maximum error threshold.

[0066] In another embodiment, the strong ETF's computed by the method are kept as clusters and the set of data points not covered by any of these strong ETF's are then separately clustered into K groups in a standard fashion. The final clustering of the database is obtained by merging the cluster descriptions from the strong ETF's and the clusters found by a standard clustering algorithm applied to data not fitting the strong ETF's.

[0067] It is noted that methods according to varying embodiments of the invention can be constructed by performing one or more of 400, 402, 404, 406, 408, 410, 412, 414, 416, 418 and 420 of FIG. 4. In some embodiments, the methods are computer-implemented. The computer-implemented methods can be realized at least in part as one or more programs running on a computer—that is, as a program executed from a computer-readable medium such as a memory by a processor of a computer, such as the computer shown in and described in conjunction with FIG. 1. The programs are desirably storable on a machine-readable medium such as a floppy disk or a CD-ROM, for distribution and installation and execution on another computer.

[0068] The approach described in this section of the detailed description for determining the clusters of data of a database has been found to be much quicker than prior art clustering approaches, and, furthermore, has been found to result in non-empty cluster sets significantly more than prior art approaches result in such non-empty clusters. As has already been described, embodiments of the invention are not limited to any particular type of data on which the clustering approaches thereof are used. In some embodiments, the clustering approach is useful for applications including data mining, data analysis in general, data visualization, sampling, indexing, prediction, and compression. Specific applications in data mining including marketing, fraud detection (in credit cards, banking, and telecommunications), customer retention and chum minimization (in all sorts of services including airlines, telecommunication services, internet services, and web information services in general), direct marketing on the web and live marketing in electronic commerce.

[0069] Embodiments of the invention are also amenable to changes to the basic approach described in conjunction with FIG. 4 in this section of the detailed description. For example, in one modification, 414 and 416 of FIG. 4 are modified such that each data point is associated with more than one ETF candidate. A data point can be “split” and a fraction of that data point is assigned to each of the matching candidate ETF's. Splitting can happen either by: (1) splitting equally among matching ETF's; or, (2) assigning more weight to ETF's that match more (e.g., weights proportional to the number of matching dimensions, or assign weights inversely proportional to the number of violating dimensions). A dimension is matching if the data point has the dimension appearing in it and in the ETF. A dimension is violating if it appears in the ETF but not in the data point, or vice versa. As another example, in another modification, 402 of FIG. 4 is modified such that, instead of treating each high-support dimension as a seed, each high-support dimension pair (i.e. two dimensions where the number of occurrences of two 1's is at least minSupport) is treated as an initial seed.

[0070] Non-Binary Data Sets

[0071] As described in the preceding sections of the detailed description, the approach used to find ETF's is applicable to data sets that are binary. In this section of the detailed description, the manner by which non-binary data sets can be converted to binary data sets for use with embodiments of the invention is described. Specifically, non-binary data sets that can be converted include categorical discrete data sets, and continuous data sets.

[0072] A data set can be thought of as containing attributes (items, or dimensions) d₁, d₂, . . . , d_m, where attribute d_itakes values from the domain {NULL, v_i1, v_i2, . . . , v_it}. Thus, binary attributes can be thought of as taking values from the domain {NULL, 1}. As before, sparse datasets are emphasized, where most of the entries have NULL values. Let I be the set of all attributes, and T be the set of all transactions in the dataset. Let n be the total number of transactions. Given support threshold κ and error threshold ε, Error-Tolerant Frequent Item Sets (ETF's) for binary data is defined in the preceding sections of the detailed description as follows. A strong ETF includes a set of items, called defining dimensions DD⊂I, such that there exists a subset of transactions R⊂T consisting of at least κ·n transactions and, for each of r∈R, the fraction of items in DD which are present (have the predetermined or distinguished value) in r is at least 1−ε.

[0073] For categorical data, conversely, strong ETF's are specifically divided into three classes. A class-1 strong ETF includes a set of (attribute, value) pairs, such that there exists a subset of transactions R⊂T consisting of at least κ·n transactions and, for each of r∈R, the fraction of these (attribute, value) pairs that are present in r is at least 1−ε. A class-2 strong ETF includes a set of (attribute, value range) pairs, such that there exists a subset of transactions R⊂T consisting of at least κ·n transactions and, for each of r∈R, the fraction of these (attribute, value range) pairs that are represented in r is at least 1−ε. A “value range” is an interval of attribute values. An (attribute, value range) pair is represented in r if and only if r contains an entry for the given attribute, whose value falls into the given value range. This definition is applicable only to data sets having attribute values can be ordered so that “value range” can be defined. A class-3 strong ETF consists of a set of (attribute, value set) pairs, such that there exists a subset of transactions R⊂T consisting of at least κ·n transactions and, for each of r∈R, the fraction of these (attribute, value set) pairs that are represented in r is at least 1−ε. A “value set” is a set of attribute values. An (attribute, value set) pair is represented in r if and only if r contains an entry for the given attribute, whose value falls into the given value set. Hereafter, a class-n ETF refers to either a class-1, class-2, or class-3 strong ETF (i.e., where n equals 1, 2, or 3).

[0074] An example is shown in the table of FIG. 5. With κ=40% and ε=0%, {(Apple, 1), (Orange, 3)} is a class-1 strong ETF. {(Apple, [1 . . . 2]), (Banana, [2 . . . 5])} is a class-2 strong ETF. {(Banana, [1,2,4,5]), (Cola, [1,2])} is a class-3 strong ETF.

[0075] Therefore, in one embodiment, to find ETF's in a categorical data set, the data set is transformed into a binary one and the approach described in preceding sections of the detailed description for finding ETF's is then performed on it. In particular, three different kinds of transformations from categorical data to binary data are presented, in order to accommodate the three ETF definitions above. It is assumed that each attribute d_ihas domain {NULL, v_i1, v_i2, . . . , v_it,}. The values corresponding to v_ijdo not need to be counts (i.e. discrete and ordered), but can be strictly unordered such as “brown”, “black” and “blonde” for an attribute “hair color”. Note that in this case, discovery of Class-1 ETF's (attribute-value pairs) and Class-3 ETF's (attribute-{values set} pairs) can be accomplished since neither of these assumes an ordering over the values {NULL, v_i1, v_i2, . . . , v_it}. For Class-2 ETF's, an ordering must be assumed over the values {NULL, v_i1, v_i2, . . . , v_it}. Class-2 ETF's can be discovered over count-values and continuous values that have been discretized.

[0076] What is referred to as a plain transformation is performed to find Class-1 ETF's. Each old attribute d_iwith domain {NULL, v_i1, v_i2, . . . , v_it} is transformed into t_inew binary attributes D_i1, D_i2, . . . , D_it, each with domain {NULL, 1}. For each row in the data, the new attribute D_ijis set to 1 if and only if the old attribute d_ihas value v_ij. For the example table of FIG. 5, the data set after the transformation is shown in the table of FIG. 6, where “A”, “O”, “B”, “C” and “M” stand for “Apple”, “Orange”, “Banana”, “Cola” and “Milk”, respectively.

[0077] What is referred to as an interval transformation is performed to find Class-2 ETF's. For each old attribute d_iwith domain { NULL, v_i1, v_i2, . . . , v_it} and for every possible interval [v_ij. . . v_ik], create a new binary attribute with domain {NULL, 1}. For each row in the data, the new attribute is set to 1 if and only if the corresponding old attribute has value that falls into the corresponding interval. For the example table of FIG. 5, the dataset after transformation has the following 31 binary attributes: Apple 1, Apple 2, Apple 3, Apple 1 . . . 2, Apple 2 . . . 3, Apple 1 . . . 3, Orange 1, Orange 2, Orange 3, Orange 1 . . . 2, Orange 2 . . . 3, Orange 1 . . . 3, Banana 1, Banana 2, Banana 3, Banana 4, Banana 5, Banana 1 . . . 2, Banana 2 . . . 3, Banana 3 . . . 4, Banana 4 . . . 5, Banana 1 . . . 3, Banana 2 . . . 4, Banana 3 . . . 5, Banana 1 . . . 4, Banana 2 . . . 5, Banana 1 . . . 5, Cola 1, Cola 2, Cola 1 . . . 2, Milk 1.

[0078] Finally, what is referred to as a subset transformation is performed to find Class-3 ETF's. For each old attribute d_iwith domain {NULL, v_{i1, vi2}, . . . , v_it,} and for every non-empty subset of {v_i1, v_i2, . . . , v_it}, create a new binary attribute with domain {NULL, 1}. For each row in the data, the new attribute is set to 1 if and only if the corresponding old attribute has value that falls into the corresponding subset. For the example table of FIG. 5, the dataset after transformation has a total of 49 binary attributes: 7 attributes for Apple, 7 attributes for Orange, 31 attributes for Banana, 3 attributes for Cola and 1 attribute for Milk. The ETF-finding approach of embodiments of the invention as described in the preceding sections of the detailed description will then produce error-tolerant frequent item sets of classes 1-3 as have been defined herein. That is, either class-1, class-2 or class-3 ETF's can be set as the “strong ETF's” that are found by the approach that has previously been described. That is, the previous definition for strong ETF's can be substituted by the definition for one of class-1, class-2, or class-3 ETF's, to find either the class-1, class-2, or class-3 ETF's within the data.

[0079] For continuous data, the data is mapped to discrete/ordered data by application of one of a number of discretization approaches known within the art. For instance, consider the continuous-valued attribute “Salary” with minimum value 10 K and maximum value 200 K. Suppose there are 3 people in a database of 5000 employees, where person 1 has a salary of 15 K, person 2 has a salary of 22 K, and person 3 has a salary of 121 K. A discretization routine can then be applied to this attribute, such that the output may be that the range 10 K to 200 K is segmented as follows: [10 K, 21 K], [22 K, 50 K], [51 K, 143 K], [144 K, 200 K]. Then the Salary values for the 3 people above are mapped to: person 1 having Salary in [10 K, 21 K], person 2 having Salary in [22 K, 50 K], and person 3 having salary-in [51 K, 143 K]. In general, the number of intervals for the discretization approach to find (and the algorithm finds good ranges) can be specified, or in another embodiment, the method can determine a best number of intervals and ranges.

[0080] Still using the salary example, once this discretization has been performed, Salary now has 4 possible values which are ordered: [10 K, 21 K], [22 K, 50 K], [51 K, 143 K], [144 K, 200 K]. In addition, it is supposed that the majority of the people in the database have salary in the range [10 K, 21 K], such that this range can be referred to as “NULL,” such that Class-1 ETF's, or Class-2 ETF's, or Class-3 ETF's over this data, as has been described. Thus, for continuous data sets, the data is divided into ranges so that it becomes, in effect, categorical discrete data, which can then be transformed into binary data, as has already been described.

[0081] Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that any arrangement which is calculated to achieve the same purpose may be substituted for the specific embodiments shown. This application is intended to cover any adaptations or variations of the present invention. Therefore, it is manifestly intended that this invention be limited only by the claims and equivalents thereof.