Method and system for squashing a large data set

[0002] The present invention relates to databases, and more specifically to summarizing a large data set.

[0003] Data mining attempts to find patterns and relationships among data in a large data set and predict future results based on the patterns and relationships by searching for and fitting a statistical model to the data set. One of the chief obstacles to effective data mining is the clumsiness of managing and analyzing a very large data set. The process of model searching and model fitting often requires many passes over the data. However, fitting large data sets into physical memory may be infeasible.

[0004] One approach to the problem is constructing summaries of the large data set on which to base the desired analysis. However, devising general-purpose summaries is difficult. For a particular model, such as a set of multiple regression analyses, statistical theory often suggests sufficient statistics that can be computed in a single pass over a large data file without holding the file in memory. However, the appropriate summaries or statistics depend on having the desired model fixed in advance. The problem is that constructing summaries for permitting effective data mining depends on the desired model, whereas selecting a well-fitting model first requires data mining.

[0005] A second approach to the problem is drawing a random sample of the large data set on which to base the analysis. Drawing a random sample of the large data set is easy to achieve. Analyzing the sample may take advantage of any statistical method, unrestricted by a possibly unfortunate choice of summary statistics. The biggest disadvantage of random sampling, however, is that sampling variance introduces inaccuracy.

[0006] An aspect of the present invention features techniques for representing a large data file with a condensed summary having the same format as the large data file.

[0007] In general, in a first aspect, the invention features a method for summarizing an original large data set with a representative data set. First, a first set of characteristic values describing relationships between a plurality of variables of original data elements is determined. Second, for each of the first set of characteristic values, a statistical representation over the set of original data elements is determined. The statistical representation may be an average value, a weighted average value having more weight assigned to more important or more accurate data elements, a sum of values, or moments of the data set. The statistical representation may be updated when new data elements are received. Finally, the set of representative data elements is generated so that the statistical representation of each of a second set of characteristic values over the set of representative data elements is substantially similar to the statistical representation corresponding to each of the first set of characteristic values. The second set of characteristic values describe relationships between a plurality of variables of representative data elements, similar to the first set of characteristic values. The representative data set may be generated by correlating a Taylor series approximation of the set of original data elements to a Taylor series approximation of the set of representative data elements, using a Newton-Raphson iterative scheme.

[0008] Some data sets are very large. Consequently, the invention additionally features a method for assigning original data elements to groups prior to determining the statistical representation. Original data elements having a common characteristic may be assigned to the same group, such as a common value of one or more categorical variables. The common characteristic could additionally or alternatively include a common range of values of one or more quantitative variables. The common characteristic could additionally or alternatively include the value of a statistical characteristic of a plurality of quantitative variables. In such case, the quantitative variables may need to be standardized. One method is to subtract the mean value from each variable and divide by the standard deviation. The statistical characteristic could then include a range of distances from the origin to the standardized point, and/or the value of a standardized variable relative to the values of the remaining standardized variables.

[0009] In general, in a second aspect, the invention features a method including assigning original data elements to a group, determining moments of the data elements assigned to a group, and generating representative weighted data elements having substantially similar moments as the moments of the original data elements.

[0010] In general, in a third aspect, the invention features a computer program product, including a storage device containing computer readable program code. The program code may include code for performing the above-mentioned methods.

[0011] In general, in a fourth aspect, the invention features a data structure having representative data elements. Each representative data element has a plurality of quantitative variables and an associated weight variable. The quantitative variables and the weight variable are combinable as representative weighted moments. The weighted moments are substantially similar to moments of a plurality of original data elements. There are fewer representative data elements than original data elements. The sum of the weight variables of every representative data element represents the number of original data elements.

[0012] In general, in a fifth aspect, the invention features a data processing system having a memory for storing statistical information about a set of original data elements, each original data element having a plurality of variables. The system also includes an application program for generating a data structure having a plurality of representative data elements. The representative data elements have the same variables as the original data elements, with the addition of a weight variable. Statistical information about the weighted representative data elements is substantially similar to the statistical information about the set of original data elements. There are fewer representative data elements than original data elements. The statistical information may include moments of varying order.

[0013] FIG. 1 is a block diagram of a data squashing technique;

[0014] FIG. 2 is a representation of an original large data set;

[0015] FIG. 3 is a representation of a squashed data set;

[0016] FIG. 4 is a representation of an intermediate partitioned data set;

[0017] FIG. 5 illustrates Categorical partitioning of a data set having two categorical variables and Q quantitative variables; and

[0018] FIG. 6 illustrates Hyper-Rectangles partitioning of a categorical partition of a data set having two categorical variables and three quantitative variables.

[0019] FIG. 7 shows a flowchart corresponding to the block diagram of FIG. 1.

[0020] I. Overview

[0021] A feature of data mining distinguishing it from “classical” machine learning and statistical modeling is scale. “Data squashing” addresses scale in a novel fashion by attempting to combine the best features of a pre-processed data summary and random sampling. Rather than scaling up individual machine learning and statistical modeling methods, data squashing scales down a data set. Data squashing effectively summarizes a large data set with a smaller version (often by several orders of magnitude) having the same variables as the original data set. The procedure constructs a squashed data set emulating the multivariate distribution of the larger data set more accurately than random sampling. Each element of the squashed data set has a weight, and the sum of the weights equals the number of elements in the original data set. A weighted analysis of the squashed data set using a Taylor series approximation to the likelihood function provides accurate approximations to the results that would be found from fitting almost any smooth model to the larger data set.

[0022] The data squashing methodology applies most directly to flat (row by column) data sets. However, the methodology is extendable to other representations. For purposes of description, an embodiment assumes that a large data set has a simple “flat” structure, consisting of a very large number of data elements, each having a fixed number of variables. Each row of the data set represents an individual data element, and each column of the data set represents one of the variables. The variables are either categorical or quantitative. A categorical variable represents a finite number of permissible states, generally describing a quality rather than a quantity. Examples of categorical variables include gender (male or female), or marital status (single, married, separated, divorced, or widowed). A quantitative variable represents a quantity within a range of permissible values, such as age, income or customer billing average.

[0023] Referring to FIG. 1, the data squashing procedure consists of three sequential steps. First, binning process 100 groups each of the set of data elements 102 into mutually exclusive bins 104. Categorical variables naturally induce bins, one for each possible combination of the permissible states of the categorical variables. Binning process 100 may artificially create additional bins from the quantitative variables, for example from either the quartiles of the single variables or from the use of Data-Spheres, as described in section III. Second, moment calculation process 106 calculates moments for data elements 102 in each of bins 104. Moments are the averages of the products of various combinations of variables for each data element in the data set. The number of moments calculated for the elements within a single bin depends on the desired degree of Taylor series approximation. Finally, generation process 108 generates a squashed data set 110 and associated weights for each bin. The squashed data set 110 for each bin is constructed having moments approximating those of the elements of the original set of data elements 102 falling in the bin. The individual data elements of squashed data set 110 are referred to herein as representative data elements. Each step can be viewed as an individual module with its own choice of methodology and with its own trade-offs in speed, space, and accuracy.

[0024] FIG. 7 shows a flowchart corresponding to the block diagram of FIG. 1. In particular, binning process 100 of FIG. 1 is carried out by steps 201 and 204 of the flowchart. Each data element is placed in a bin based on the states of its categorical variables at step 201 and if more data elements are to be placed in bins, as determined at step 204, step 201 is repeated for a next data element until all the data elements have been processed. Moment calculation process 106 of FIG. 1 is carried out by steps 205 and 208 of the flowchart. Moments are calculated for the data elements in a bin at step 205 and if the moments for more bins need to be calculated, as determined at step 208, step 205 is repeated for a next bin until moments for all the bins have been calculated. Generation process 108 of FIG. 1 is carried out by steps 211 and 215 of the flowchart. Based on the calculated moments, a squashed data set is calculated for a bin at step 211 and if squashed data sets for more bins need to be calculated, as determined at step 215, step 211 is repeated for a next bin until squashed data sets have been generated for all the bins, at which point the process ends at 216.

[0025] The squashed data set is smaller (by orders of magnitude) than the original data set. It preserves analysis flexibility without sacrificing accuracy due to sampling variability. A restriction on analyzing the squashed data set, compared to the methods available for analyzing the original data set, is that the analysis method or software must be capable of making use of the induced weights.

[0026] The requirement that the squashed data set summarize the large data set as accurately as possible means that for all or almost all statistical models that may be fit to the data, the result from a weighted model fit of the squashed data is nearly the same as if the same model was fit to the original data. Random sampling or a cluster analysis can create a type of “squashed” data set. For example, taking a 1% random sample of the data set (e.g., select every 100th row) and then adding a weight variable equal to 100 for every random row selected in the sample creates a smaller data set. However, such procedure creates parameter estimates that typically differ from the corresponding fall data estimates by about 10 standard errors, since standard errors of efficient estimates are inversely proportional to the square root of the sample size. The data squashing procedure described herein can significantly improve the parameter estimates. Another possible strategy for creating a smaller data set is by performing a cluster analysis on the original data set, where each element of the large data set resides in exactly one cluster. The data file could consist of the centers or means of each cluster, and the weight variable would equal the size of the corresponding cluster. However, there are two impediments to this approach. First, clustering algorithms are typically O(n²) or may require many passes over the data, rendering clustering infeasible for very large data sets. Second, replacing each cluster by a single weighted point at the cluster mean implicitly reduces the overall variance of every quantitative variable in the squashed data set and would thus tend to distort the results of most statistical models.

[0027] Data squashing can be seen as a form of lossy database compression. Recent work in database literature has examined methods for the lossy compression of databases and data cubes. However, data squashing has a somewhat different goal. Lossy data cube compression can be judged acceptable if aggregate queries over ranges of the data cube have a small error. Data squashing is acceptable if a different type of query has a small error, e.g., the fitting of statistical models. Therefore, data squashing is valuable for statistical analysis data warehouses.

[0028] The data squashing methodology of the present invention may be implemented with hardware and/or software. In one embodiment, the data squashing methodology is implemented as a data processing system, having an application program executing in the memory of a computer. The application program resides on a storage device such as a floppy disk, a CD-ROM, or the hard drive of a computer as computer readable program code.

[0029] II. Theoretical Framework For Data Squashing

[0030] Referring to FIG. 2, an embodiment assumes a large data set has a simple “flat” structure, consisting of a very large number, N, of data elements, each data element represented by a single row in the data matrix. Each data element consists of a fixed number of variables, each variable represented by a single column in the data matrix. As discussed above, the variables are either categorical or quantitative. Suppose the large data set has columns A₁, . . . . A_C, X₁, . . . , X_Q, where the A's are categorical variables and the X's are quantitative variables. Let A=A_ijand X=X_ikdenote the original N×C and N×Q data matrices of categorical and quantitative variables, respectively, where i=1, . . . , N; j=1, . . . , C; k=1, . . . , Q. Referring to FIG. 3, let B=B_ijand Y=Y_ikdenote the data matrices representing the squashed data set having M<<N rows, where i=1, . . . , M; j=1, . . . , C; k=1, . . . , Q. The squashed data set has columns B₁, . . . , B_C, Y₁, . . . , Y_Q, where the B's are categorical variables and the Y's are quantitative variables, as with the original large data set. Let w_ibe the weight assigned to row i of the squashed data set, where $\sum _{i=1}^M{w}_i=N.$

[0031] Suppose further that a statistical model is being fit to the data. That is, a modeling assumption is made that the large data set is the result of N independent draws from the probability model:

[0032] f(a₁, . . . , a_C, x₁, . . . , x_Q; θ)=Prob(A₁=a₁, . . . , A_C=a_C, X₁=x₁, . . . , X_Q=x_Q|θ)  (1)

[0033] where the function 𝑓 defines the particular model being fit and θ is a vector of parameters that are estimated from the data. For example if two variables represent a person's age and education level, respectively, θ could represent the person's income level as estimated from those two variables. A squashed version of the data should provide nearly identical analyses for a wide choice off. “Nearly identical analyses” means that the information about θ should be approximately the same for the full data set (A, X) as for the squashed data set (B, Y, w). Therefore, the product of probabilities in Equation (1) should represent approximately the same function of θ for the two possible data sets, or, in statistical terminology, the two samples should have approximately the same likelihood function. Equating the two log-likelihoods, the following requirement results: $\begin{array}{cc}\sum _{i=1}^M{w}_i\log \left(f\left(B_{\mathrm{i1}},\dots ,B_{\mathrm{iC}},Y_{\mathrm{i1}},\dots ,Y_{\mathrm{iQ}};\theta \right)\right)=\sum _{i=1}^N\log \left(f\left(A_{\mathrm{i1}},\dots ,A_{\mathrm{iC}},X_{\mathrm{i1}},\dots ,X_{\mathrm{iQ}};\theta \right)\right)& \left(2\right)\end{array}$

[0034] Assume that for every set of fixed values of A and θ, f(A, X, θ) is a relatively smooth function of (X₁, . . . , X_Q), so that log(𝑓(A₁, . . . , A_C, X₁, . . . , X_Q; θ)) can be well represented by a Taylor series in the neighborhood of any point x=(x₁, . . . , X_Q). The following approximate equality results: $\begin{array}{cc}\log \left(f\left(A_1,\dots ,A_C,X_1,\dots ,X_Q;\theta \right)\right)\cong \sum _{k=1}^K{g}_k\prod _{j=1}^Q{\left(X_j-x_j\right)}^{P_{\mathrm{kj}}}& \left(3\right)\end{array}$

[0035] In Equation (3), there are K terms in the Taylor series. The coefficients g_kdepend on (A₁, . . . , A_C), θ, and x, but not on (X₁, . . . , X_Q). The power vectors p_k1, . . . , p_kQ) are all vectors of Q nonnegative integers satisfying $\sum _j{p}_{\mathrm{kj}}\le d,$

[0036] where d is the degree of the approximation. In order to use Equation (3) to solve Equation (2), partition the space of X into a finite set of regions and partition the space (A, X) into bins where A is constant and X is confined to a single region. Suppose there are R such bins and that the large data set has N_rdata elements in bin r, where $\sum _{r=1}^R{N}_r=N.$

[0037] Likewise, assume that the squashed data set will have M_rrepresentative data elements in bin r, and that the summation $\sum _{i=1}^{M_r}{w}_i=N_r.$

[0038] Within the rth bin, the likelihood equivalence of Equation (2) can be separately enforced, which amounts to setting every B_ijequal to the corresponding constant value of A_ij, for j=1, . . . , C, and replacing M and N by M_rand N_r, respectively. Therefore, Equation (2) may be rewritten as: $\begin{array}{cc}\sum _{i=1}^{M_r}{w}_i\log \left(f\left(A_{\mathrm{i1}},\dots ,A_{\mathrm{iC}},Y_{\mathrm{i1}},\dots ,Y_{\mathrm{iQ}};\theta \right)\right)=\sum _{i=1}^{N_r}\log \left(f\left(A_{\mathrm{i1}},\dots ,A_{\mathrm{iC}},X_{\mathrm{i1}},\dots ,X_{\mathrm{iQ}};\theta \right)\right)& \left(4\right)\end{array}$

[0039] Combining Equation (3) and Equation (4), the following approximate constraints result: $\begin{array}{cc}\sum _{i=1}^{M_r}{w}_i\sum _{k=1}^K{g}_k\prod _{j=1}^Q{\left(Y_{\mathrm{ij}}-x_j\right)}^{p_{\mathrm{kj}}}=\sum _{i=1}^{N_r}\sum _{k=1}^K{g}_k\prod _{j=1}^Q{\left(X_{\mathrm{ij}}-x_j\right)}^{p_{\mathrm{kj}}}r=1,\dots ,R& \left(5\right)\end{array}$

[0040] In order for Equation (5) to hold for arbitrary functions 𝑓, and thus for arbitrary coefficients g_k, the factors multiplying each g_kmust be equated separately. This leads to the set of equations: $\begin{array}{cc}\sum _{i=1}^{M_r}{w}_i\prod _{j=1}^Q{\left(Y_{\mathrm{ij}}-x_j\right)}^{p_{\mathrm{kj}}}=\sum _{i=1}^{N_r}\prod _{j=1}^Q{\left(X_{\mathrm{ij}}-x_j\right)}^{p_{\mathrm{kj}}}r=1,\dots ,R;k=1,\dots ,K& \left(6\right)\end{array}$

[0041] Equation (6) suggests that within each bin (where the categorical variables are constant and the quantitative variables are confined to a compact region) and for each power vector (p_k1, . . . , p_kQ), the weighted mixed moment of the squashed data set should approximately equal the corresponding mixed moment of the original data set. A moment generally refers to specific statistical information derived from a single variable, whereas a “mixed” moment generally denotes specific information derived from more than one variable. For purposes of this disclosure, “moment” includes any applicable single variable moments in addition to multivariable “mixed” moments. The order of the moments calculated, d, defines the degree of approximation. For second order moments, having d=2, only means, variances and covariances are preserved within each bin. Although this would be sufficient to preserve the results of many linear statistical models such as multiple regression, such a squashed data set may be an inadequate approximation for the nonlinear models often used in data mining applications. Consequently, higher degrees of approximation may be necessary.

[0042] In the above discussion, the data sets are arranged with the categorical variables first, followed by the quantitative variables. Such arrangement is not meant as a limitation, but rather, is presented only for purposes of illustration. For example, the categorical variables and quantitative variables could be arranged in any order, or even in separate data matrices.

[0043] III. Partitioning The Data Elements Into Bins

[0044] As illustrated in FIG. 1, binning process 100 performs a first step of data squashing in the present invention, which entails partitioning the data into compact bins. Binning process 100 partitions the data elements of the large data set 102 into bins 104 of smaller data sets. The partitioning strategy should partition the data elements based on some common characteristic of the data elements. The partitioned data set contains the same set of data elements, although the data elements are reorganized to lie within their respective bins. Let p_irepresent the data element (A_i1, . . . , A_iC, X_i1, . . . , X_iQ). FIG. 4 represents a data set containing four bins derived from the original data set of FIG. 2. The first bin contains the data elements p₁to p_a, the second bin contains the data elements p_bto p_c, the third bin contains the data elements p_dto p_e, and the final bin contains the data elements p_fto p_N. The data elements may be reorganized within the data set to lie within their respective bins, as shown in FIG. 4. Alternatively, the data elements could be separated into individual data matrices for each bin. However, it is not critical how the data elements are organized, or even that the data elements are reorganized at all, provided there is some way to determine which data elements lie within which bin.

[0045] Although many different partitioning strategies are available for creating the bins, three such strategies may be particularly useful, referred to herein as “Categorical” partitioning, “Hyper-Rectangles” partitioning, and “Data-Spheres” partitioning. Categorical partitioning creates bins using only categorical variables. Hyper-Rectangles partitioning and Data-Spheres partitioning create partitions using both categorical and quantitative variables. Deciding which partitioning strategy to use is an important element of data squashing. It will have a profound effect on both the level of data reduction realized and the computational time needed for squashing the data set.

[0046] The term “bin” as used herein defines a final subset of data elements grouped together by binning process 100. The term “partition” as used herein defines a subset of data elements that binning process 100 may or may not further divide into additional subsets of data elements. Therefore, “bin” refers only to the final subset of data elements, whereas “partition” may or may not refer to a final subset of data elements.

[0047] Categorical partitioning constructs bins using some or all of the categorical variables in the data set. Each possible combination of permissible values of the categorical variables defines a single bin. For example, referring to FIG. 5, if each data element contains two categorical variables (A₁and A₂) having three states each, represented by 0, 1 and 2, respectively, Categorical partitioning creates 3²or nine bins. The first bin contains all the data elements where A_i1=0 and A_i2=0, the second bin contains all the data elements where A_i1=0 and A_i2=1, and so on. In an alternative embodiment, a bin may contain all the data elements where a categorical variable contains a subset of the permissible values. For example, a first bin could contain all the data elements where A_i1=0 or 1, and A_i2=0, a second bin could contain all the data elements where A_i1=0 or 1, and A_i2=1, and so on. Categorical variables naturally induce partitions. Therefore, Categorical partitioning may be the best approach because it does not introduce any subjective partitions in the data set which do not already exist.

[0048] Hyper-Rectangles partitioning first partitions the data elements using some or all of the categorical variables. As with Categorical partitioning, each possible combination of permissible values of the categorical variables defines a single partition. The partitions are further divided by categorizing some or all of the quantitative variables, thereby creating hyper-rectangles in the data space. Categorizing a quantitative variable entails dividing the entire range of permissible values of the variable into individual regions. For example, a quantitative variable having values ranging from 0 to 100 could be categorized by the regions r₁, r₂, r₃and r₄, where 0≦r₁<25; 25≦r₂<50; 50≦r₃<75; and 75≦r₄≦100. There is no requirement that the regions are the same size, or that each quantitative variable is categorized into the same number of regions. Therefore, each partition constructed with the categorical variables is further partitioned into bins. Within each partition, each possible combination of the different regions for each quantitative variable defines a bin, similar to Categorical partitioning.

[0049] An efficient choice of bin boundaries is often difficult to specify in advance. With a large number of regions per variable there is a tradeoff—more total bins are created giving more precision, but it results in less data reduction. Since the total number of bins grows exponentially with the number of regions per variable, it is preferable to keep the number of regions for each quantitative variable relatively low. For example, each quantitative variable may be split into 3 regions, based on the 25th and 75th percentiles. For a data set with five quantitative variables, this would create 3⁵or 243 bins. If there were also two categorical variables having three states each, as in the above example, then there would be a total of 3²×243 or 2187 bins. For example, FIG. 6 represents Hyper-Rectangles partitioning of bin 2 of FIG. 5, assuming that Q=3 quantitative variables, whereas each quantitative variable is separated into three regions. The three possible regions for each quantitative variable are represented by r₁, r₂and r₃, corresponding to the range of values equal to or below the 25th percentile of permissible values, the range of values between the 25th and 75th percentiles, and the range of values equal to or above the 75th percentile, respectively. As shown in FIG. 6, bin 2 from FIG. 5 is subdivided into 3³or 27 bins, referred to in FIG. 6 as bin 2-1, bin 2-2, . . . , bin 2-27. Bin 2-1 contains the elements where x_i1is in the lower 25th percentile of permissible values for x_i1, x_i2is in the lower 25th percentile of permissible values for x_i2, and x_i3is in the lower 25th percentile of permissible values for x_i3, and so on.

[0050] Data-Spheres partitioning first partitions the data elements using some or all of the categorical variables. As with Categorical partitioning, each possible combination of permissible values of the categorical variables defines a single partition. The partitions are further divided with one or more levels of partitions by inducing a categorical value on a set of quantitative variables based on the multivariate distribution of those variables. Data-Spheres partitioning may induce a categorical value on a set of quantitative variables in two ways. The resulting partitions are referred to as “layers” or “pyramids”, depending on the method of partitioning. Pyramids may be further partitioned into “subpyramids”, and so on.

[0051] In order to provide a meaningful multivariate distribution between quantitative variables, for each point p=(x₁, . . . , x_Q), the point is transformed into p′=(y₁, . . . , y_Q) by subtracting the center of the data set for each variable (for example, the mean) and dividing by the standard deviation. Partitioning into layers requires determining the distance of p′ from the origin for every point p′ in the data set. The origin is defined as the point (y₁=0, y₂=0, . . . , y_Q=0). Specifically, the distance of p′ from the origin={square root over (y₁²+y₂²+ . . . +y_Q²)}. The data set is then partitioned into layers by the distance of the points from the origin. Optionally, each layer may contain approximately the same number of data elements, i.e., an approximate quantiling algorithm may be used to compute the distance cutoffs.

[0052] Any number of the layers may be further partitioned into pyramids, depending on the degree of specificity desired. Informally, a pyramid consists of the set of data elements for which a particular variable of the transformed point has the greatest deviation from the origin, and in a particular direction (positive or negative). In three dimensions, a pyramid has the familiar pyramidal shape. More formally:

[0053] p′εP_i+if |y_i|>|y_j|, for y_i>0; j=1, . . . , Q; j≠i

[0054] p′εP_i−if |y_i|>|y_j|, for y_i<0; j=1, . . . , Q; j≠i

[0055] Layers and pyramids are orthogonal partitioning strategies. In combination, they define data sphere partitions. In analogy to data cubes, it is possible to roll up or drill down data sphere partitions. For example, all pyramids may be collapsed in a layer. Or, the pyramids may be further partitioned into subpyramids, creating a hyperpyramid partitioning. For example, P_i+j− represents the bin in which y_ihas the greatest deviation from the origin and y_jhas the second greatest deviation from the origin, for y_i>0 and y_j<0. In addition, each level of subpyramid may be further subdivided to reach the desired degree of specificity. For example, P_i−j−k+ represents the bin in which y_ihas the greatest deviation from the origin, y_jhas the second greatest deviation from the origin, and y_khas the third greatest deviation from the origin, for y_i<0, y_j<0 and y_k>0. In alternative embodiments, the data elements may first be divided into pyramids, and optionally further partitioned into layers.

[0056] As an example, assume that three layers are created for the point p′=(y₁, . . . , y_Q), referred to as an inner, middle and outer layer. The layers may be created so that the inner layer contains 50% of the data elements and the cutoff between the middle and outer layer is twice the distance of the inner layer cutoff. Further assume that the inner layer is not partitioned by pyramids, the middle layer is partitioned by pyramids, and the outer layer is partitioned by pyramids and subpyramids. Such partitioning scheme creates bins encompassing similar proportions of the total data space. The partitioning creates a total of 4Q²−2Q+1 bins, although many outer-layer bins may be empty. The inner layer contains only a single bin, because it is not further subdivided. The middle layer contains 2Q bins due to the pyramid partitioning. The bins are referred to as P_i+ and P_i−, for i=1, . . . , Q. Specifically the P₁₊ and P₁₋ bins contain the data elements defined by p′ where y₁'s deviation from the origin is greater than the deviation from the origin of each of the remaining variables y₂, . . . , y_Q, for y₁>0 and y₁<0, respectively. Similarly, the P₂₊ and P₂₋ bins contain the data elements defined by p′ where y₂'s deviation from the origin is greater than the deviation from the origin of each of the remaining variables y₁, y₃, . . . , y_Q, for y₂>0 and Y₂<0, respectively. Finally, the outer layer contains 4Q²−4Q bins due to the subpyramid partitioning. Each of the 2Q partitions created from the initial pyramid partitioning in the outer layer are further subdivided into 2Q−2 bins. For example, the P₁₊ partition is further subdivided into the bins P₁₊₂₊, . . . , P_1+Q+, P₁₊₂₋, . . . , P_1+Q−. Therefore, the outer layer contains 2Q(2Q−2) or 4Q²−4Q bins. Consequently, the total number of bins for the three layers is 1+2Q+4Q²−4Q=4Q²−2Q+1.

[0057] The Hyper-Rectangles and Data-Spheres partitioning techniques described above assume that the quantitative variables are partitioned within the categorical partitions. However, there is no inherent requirement for categorical partitioning. For example, some data sets may not contain categorical variables. In other situations, some analyses may work better by partitioning the quantitative variables and not the categorical variables, or by first partitioning the quantitative variables and further partitioning the quantitative partitions with categorical partitions. Other partitioning schemes could create partitions based on only some, but not all of the categorical variables. Further partitioning schemes could combine Hyper-Rectangles partitioning and Data-Spheres partitioning. The particular method of partitioning can be modified to take advantage of the memory and processing power available, in addition to the types of analyses to be performed and the format of the data. The three partitioning techniques described above should not be construed as limitations, but rather, as examples of potential partitioning techniques available.

[0058] Partitioning separates a set of data elements into different bins, thereby permitting moment calculation process 106 and generation process 108 to work with fewer data elements at a time. In alternative embodiments, however, the entire data set may be squashed as a whole, without partitioning the data elements into bins.

[0059] IV. Moment Calculations

[0060] The second step of data squashing, performed by moment calculation process 106, is calculating the sufficient statistics that will be used to create representative data elements in the squashed data set. Moment calculation process 106 calculates a set of characteristic values describing relationships between the quantitative variables of each data element. For example, for a data element having quantitative variables X₁, . . . , X_Q, characteristic values may include X₁, . . . , X_Q, X₁X₂, . . . , X₁X_Q, and so on. Moment calculation process 106 then determines a statistical representation of each characteristic value over the data set. In one embodiment, the statistical representations are moments of the quantitative variables for the elements falling in each bin 104. Moments are the averages of the products of various combinations of variables for each data element in the original data set. For example, the second order moments are represented by (X_iX_j, X_i²), where: $X_i{X}_j=\frac{1}{n}\sum _{a=1}^n{X}_{\mathrm{ai}}{X}_{\mathrm{aj}}\text{for}i=1,\dots ,Q-1;j=i+1,\dots ,Q$ $X_i^2=\frac{1}{n}\sum _{a=1}^n{X}_{\mathrm{ai}}^2\text{for}i=1,\dots ,Q$

[0061] How many and which moments to calculate depends on the particular application. Since partitioning reduces the data set into subsets, typically organizing the data elements by some common characteristic, the number of moment calculations required for each bin may be lower than would otherwise be required to approximate the data set as a whole.

[0062] In order to provide a good fit for a wide range of machine learning and statistical models, calculating the following moments on the quantitative variables is suggested (note that all of the following variables have been centered and scaled): minima and maxima, means, second order moments (X_iX_j, X_i²), third order moments (X_iX_jX_k, X_i²X_j, and X_i³), fourth order moments (X_iX_jX_kX_l, X_i²X_jX_k, X_i²X_j², X_j², X_i³X_j, and X_i⁴), and marginal fifth order moments (X_i⁵). Higher order moments may be calculated, depending on the degree of specificity required. The number of moments that are calculated determines the number of representative data elements fit to each bin. Fewer representative data elements are able to match fewer moments. Therefore, as with the partitioning procedures, the number of moments fit can be adjusted for controlling the amount of data reduction desired, and for reducing the computational complexity, if necessary. In order to match the number of moments to the number of representative data elements, the degree of freedom may be defined as df=m(Q+1), where m is the number of representative data elements in a bin. Note that df is the number of free parameters (values of w and y) that the representative data elements contain. Therefore, K≈df lowest order moments are chosen from among those listed above. The choice of how many moments to fit may be modified to fit with the particular application, and the above example should not be viewed as a restriction.

[0063] In one embodiment, the number of representative data elements within the rth bin, N_r. The M_r, depends on the corresponding number of original data elements within the rth bin, N_r. The choice of M_rdepends on how much data reduction is desired, and M_rshould increase slowly with N_r. Although somewhat arbitrary, an example is to use the formula M_r=max(1, [α log₂N_r.]), where α is a number that determines how much data reduction is achieved. As an example, compare α=0, ½, 1, and 2. When α=0, only one representative data element is used to approximate each bin, positioned at the bin mean for each variable. When α>0, the method uses more representative data elements and moments as α increases for a better-fitting squashed data set. The overall data reduction factor is thus approximately $\sum _r{N}_r/\sum _r{M}_r\approx N/\alpha \sum _r{\log }_2{N}_r.$

[0064] The partitioning procedure may vary with the number of original data elements N to increase the number of bins as N increases, thereby keeping the number of original data elements N_rand the number of representative data elements M_rin each bin relatively constant. In an alternative embodiment, M_rdoes not increase with N_r. For example, M_rmay be constant for maintaining a squashed data set having a constant size. M_rmay also have a maximum allowable value to take advantage of the processing power available.

[0065] In order to compare the three partitioning techniques described above, it may be useful to have a comparable sample size of representative data elements for comparison. Therefore, it may be necessary to fit different sets of moments for each method. As an example, all moments described above may be fit (d=4+) for Categorical partitioning, because it creates the fewest bins. Two moment strategies may be useful with the Hyper-Rectangles partitioning technique, because the number of bins increases very fast with the dimensionality. The complete Hyper-Rectangles strategy fits all first and second moments and marginal third and fourth moments (d=2+). A reduced Hyper-Rectangles strategy, which may be referred to as “Means,” fits just the first moments within each Hyper-Rectangles bin (d=1). Data-Spheres partitioning is a middle ground between the above strategies in terms of bins created. Therefore, Data-Spheres partitioning may use up to and including all third order moments (d=3).

[0066] The moment calculations have a strong advantage in data mining applications because they can be calculated sequentially. When a new set of data arrives, they can be used to update the moments without recalculating the moments for the whole set. This results because the moments are merely sums of various relationships among the variables of each data element, divided by the total number of data elements. The relevant relationships for the additional data is simply added on to the existing moment calculations, updating N_r, the number of original data elements in the corresponding bin. This is important when dealing with millions of records which are streaming in daily, since re-computing moments each time fresh data is received may be undesirable.

[0067] In alternative embodiments, statistical information other than or in addition to moments may be determined for generating the squashed data set. Any set of values describing, at least in part, relationships among the variables for each data element may be used. The statistical information of each value over the set of data elements may also be modified. One embodiment simply takes the average of each value over the data set. Another embodiment adds each of set of values together. Another embodiment calculates a weighted average for each value, assigning more weight to more important or more accurate data elements. Other embodiments may calculate more complex statistical information about each value over the set of data elements. In these embodiments, the squashed data set is generated to exhibit substantially similar statistical information as the original data set.

[0068] V. Generating Representative Data Elements and Associated Weights

[0069] The final step of data squashing, performed by generation process 108, is generating squashed data set 110, defined by the representative data elements and their associated weights. An approximate solution to Equation (6) is sought separately for each bin indexed by r. Within each bin, assume that the x_jin Equation (6) are equal to the mean of the X_ijcontained in the bin, and, by recentering the X's within each bin to have mean 0, assume that every X_j=0. Recentering the X's does not effect the equality of Equation (6), because both sides of the equation are shifted by the same amount. After the representative data elements are generated, the representative data elements are shifted back by the same amount so that they accurately represent the original data set. Therefore, for each bin r, search for an M_r×Q matrix Y and an M_r-length vector w to approximately satisfy the equations: $\begin{array}{cc}\sum _{i=1}^{M_r}{w}_i\prod _{j=1}^Q{Y}_{\mathrm{ij}}^{P_{\mathrm{kj}}}=z_{k}k=1,\dots ,K\text{where}{z}_k=\sum _{i=1}^{N_r}\prod _{j=1}^Q{X}_{\mathrm{ij}}^{p_{\mathrm{kj}}}& \left(7\right)\end{array}$

[0070] This is a system of K equations in M_r(Q+1) unknowns. The value of K depends on the number of quantitative variables, Q, and the degree of approximation, d.

[0071] For example, first order moments (X_i) lead to Q equations: $X_i\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}i=1,\dots ,Q$

[0072] Second order moments (X_iX_j, X_i²) lead to Q and Q(Q−1)/2 equations, respectively: $X_i{X}_j\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}{Y}_{\mathrm{cj}}=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}{X}_{\mathrm{cj}}$ $i=1,\dots ,Q-1;j=i+1,\dots ,Q$ $X_i^2\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}^2=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}^{2}i=1,\dots ,Q$

[0073] Third order moments (X_iX_jX_k, X_i²X_j, X_i³) lead to Q(Q−1)(Q−2)/6, Q(Q−1) and Q equations, respectively: $X_i{X}_j{X}_k\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}{Y}_{\mathrm{cj}}{Y}_{\mathrm{ck}}=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}{X}_{\mathrm{cj}}{X}_{\mathrm{ck}}$ $i=1,\dots ,Q-2;j=i+1,\dots ,Q-1;k=j+1,\dots ,Q$ $X_i^2{X}_j\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}^2{Y}_{\mathrm{cj}}=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}^2{X}_{\mathrm{cj}}$ $i=1,\dots ,Q;j=1,\dots ,Q;i\ne j$ $X_i^3\text{:}\sum _{c=1}^{M_r}{w}_c{Y}_{\mathrm{ci}}^3=\sum _{c=1}^{N_r}{X}_{\mathrm{ci}}^{3}i=1,\dots ,Q$

[0074] Equations for higher order moments follow in the same manner.

[0075] Any available method for solving the system of equations may be utilized. Even if K≦M_r(Q+1) there may often be no exact solutions to Equation (7), due to enforcement of the constraints: $\begin{array}{cc}{w}_i\ge 0;\underset{i}{\min }{X}_{\mathrm{ij}}\le Y_{\mathrm{ij}}\le \underset{i}{\max }{X}_{\mathrm{ij}}& \left(8\right)\end{array}$

[0076] Negative weights and variable values outside the ranges of variables found in the corresponding bin of the original data set are ruled out in order to ensure that the squashed data set is similar to the original data set. However, it is not necessary that the values of Y be restricted to values that occur in the corresponding X For example, if a given X_jis “number of children in the family”, and varies from 0 to 10 in the original file, the value 8.5 would be an acceptable value for Y_j, but not 10.5 or −1. If it is desired to maintain the set of actually occurring values, then the variable is made categorical (a column of A). Although the constraints help assure that the squashed data set is similar to the original data set, particular applications may eliminate some or all of the constraints, or add additional constraints.

[0077] The search for (Y, w) is treated as the search for a least squares estimate to minimize: $\begin{array}{cc}S\left(Y,w\right)=\sum _{k=1}^K{u_k\left(z_k-\sum _{i=1}^{M_r}{w}_i\prod _{j=1}^Q{Y}_{\mathrm{ij}}^{p_{\mathrm{kj}}}\right)}^2& \left(9\right)\end{array}$

[0078] In Equation (9), the positive multipliers u_kare used to ensure that the lower-order moments are approximated more accurately. Since it is trivial to scale w and each column of Y so that the moments of order 0 and 1, and the pure squares of order, are fit exactly, the corresponding values of k have u_k=1000. All the other u_ksum to 1, with moments of order 2 getting twice the value as moments of order 3, which are in turn twice as large as the u_kfor moments of order higher than 3. In addition to being centered at 0, the X's are originally scaled to have variance 1, so that moments of different orders are comparable. The above values for u_kare somewhat arbitrary and are provided only as an example. Alternative embodiments may have different values for u_k, or even eliminate u_kaltogether. Computation of the moments u_kis performed with an updating algorithm, so that the centered and scaled moments within each bin can be computed in a single pass over the large data set with a minimum of round-off error. As initial values in an iterative search, each w_iis set equal to N_r/M_r, and the Y_ijare drawn independently from a uniform distribution within their allowed ranges. Since S(Y, w) in Equation (9) is a simple polynomial function of the unknowns, it is easy to compute the required derivatives for a second-order Newton-Raphson iterative scheme. The Newton-Raphson scheme is a well-known iterative method for generating a sequence of approximations of a solution for a given equation. In an alternative embodiment, the initial values for the Y_ijare selected using a random sample of the X_ij's. Other alternative embodiments may take advantage of other initial values.

[0079] Two methods may hasten convergence. First, rather than update all M_r(Q+1) unknowns at each Newton-Raphson step, which would involve computing and working with a K×M_r(Q+1) Hessian matrix of derivatives of $\sum _{i=1}^{M_r}{w}_i\prod _{j=1}^Q{Y}_{\mathrm{ij}}^{p_{\mathrm{kj}}},$

[0080] it works well to merely update a single column of Y at a time, cycling through the columns. This requires working with only M_runknowns at a time and the derivatives of the moments involving only one variable with respect to these unknowns, leading to a Hessian matrix of size k′×M_r, where k′<K is the number of moments involving that variable. These iterations do not update the values of w. However, it is also easy to work with a single row of Y and the corresponding element of w, to update only (Q+1) unknowns at a time. In this case, the Hessian matrix is of size K×(Q+1). These partial updates allow efficient search for a minimum of Equation (9).

[0081] The second method is maintaining the constraints of Equation (8) at each update step. This is done by transforming the unknowns using a logistic transform, so that the finite range is converted to an unbounded range and out-of-bound updates are prevented. In addition, at each update the step size may be reduced if necessary to ensure that Equation (9) gets smaller at each update. There will rarely be a unique local minimum of Equation (9). However, the multiple local minima often have very similar values of S(Y, w), and will serve equally well for the purpose of creating a squashed data set. The Newton-Raphson search can be repeated with different random starting points to help assure accurate results.

[0082] VI. Computational Complexity of Data Squashing

[0083] Data squashing as described herein scales well with the number of rows in the data set, and moderately well with the number of variables. The computational burden should be separately broken down into sources due to binning process 100, moment calculation process 106, and generation process 108. Suppose there are B partitions due to categorical variables, and Q quantitative variables, with N data elements in the large data set. For purposes of determining computational complexity, assume that the data set has been pre-sorted according to the categorical partitions. The overhead for this sorting step, roughly N log(N) operations is part of every version of squashing described above. The squashing is done independently within each bin, assuming that a single bin has n data elements. Therefore, the squashing in each bin may be parallelized.

[0084] A. Cost Of Partitioning

[0085] Categorical partitioning introduces no additional cost associated with partitioning because there is no partitioning using the quantitative variables.

[0086] Hyper-Rectangles partitioning requires only a single pass over the data, because determining the bin boundaries depends only on computing the approximate quartiles of each quantitative variable, using the partitioning technique of the earlier example. The memory requirements are proportional to Q and the CPU cost is proportional to nQ. The cost of the Means strategy is the same as regular Hyper-Rectangles partitioning because the grouping is the same.

[0087] Data-Spheres partitioning requires two passes over the data to determine the data sphere bin boundaries and assign each data element to one of the 4Q²−2Q+1 bins, using the partitioning technique of the earlier example. The memory requirements are proportional to Q and the CPU cost is proportional to nQ.

[0088] B. Cost of Computing Moments

[0089] The number of moments that must be calculated depends on the number of quantitative variables Q for each data element. There are Q first order moments (X_i), one for each quantitative variable. The second order moments are (X_i², X_iX_j). (X_i²) requires Q calculations, and (X_iX_j) requires Q(Q−1)/2 calculations. The third order moments are (X_iX_jX_k, X_i²X_j, X_i³). (X_iX_jX_k) requires Q(Q−1)(Q−2)/6 calculations, (X_i²X_j) requires Q(Q−1) calculations, and (X_i³) requires Q calculations. The fourth order moments are (X_iX_jX_kX_l, X_i²X_jX_k, X_i²X_j², X_i³X_j, X_i⁴). (X_iX_jX_kX_l) requires Q(Q−1)(Q−2)(Q−3)/24 calculations, (X_i²X_jX_k) requires Q(Q−1)(Q−2)/2 calculations, (X_i²X_j²) requires Q(Q−1)/2 calculations, (X_i³X_j) requires Q(Q−1) calculations, and (X_i⁴) requires Q calculations. The marginal fifth order moments are (X_i⁵), requiring Q calculations.

[0090] Following the earlier suggestion, Categorical partitioning computes all moments up to order 4 and the marginal moments of order 5. There are K_c=5Q+3Q(Q−1)+2Q(Q−1)(Q−2)/3+Q(Q−1)(Q−2)(Q−3)/24 total moments to compute. K_cis asymptotically equivalent to Q⁴/24, but for moderate Q the lower-order terms in the expression for K_cpredominate. All moments can be computed in a single pass over the data set. Therefore, memory requirements are proportional to K_cand the CPU cost is proportional to nK_c.

[0091] Following the earlier suggestion, Hyper-Rectangles partitioning computes first order and second order moments, and marginal third order forth order moments. There are K_h=Q(Q+7)/2 moments to compute within each bin. Let H be the number of populated hyperrectangles, with H≦3^Q, assuming that each quantitative variable is split into three regions as described earlier. Alternatively, if each quantitative variable was split into L regions, then H≦L^Q. In practice, H will often be much smaller than this worst-case bound, and the ability of the Hyper-Rectangles method to scale up to large values of Q depends on how fast H grows as more variables are included. Using a one-pass algorithm, the memory requirements will be K_hH with the CPU cost proportional to nK_h. If the data are first sorted into the H quantitative partitions [costing proportional to n(Q+log(n)) in CPU], then only K_hunits of memory are needed to cumulate the moments for each bin sequentially. Computing the means pursuant to the Means strategy requires memory proportional to QH and CPU cost proportional to nQ.

[0092] Data-Spheres partitioning computes all moments up to order 3. There are K_d=3Q+3Q(Q−1)/2+Q(Q−1)(Q−2)/6 moments to compute. K_dis asymptotically equivalent to Q³/6, but for moderate Q the lower-order terms in the expression for K_dpredominate. Let D be the number of populated data sphere bins. In the Data-Spheres partitioning example described earlier, in which three layers are created with the middle layer partitioned by pyramids and the outer layer partitioned by pyramids and subpyramids, then D≦4Q²−2Q+1. Using a one-pass algorithm, the memory requirements would be K_dD, with the CPU cost proportional to nK_d.

[0093] C. Cost of Computing Representative Data Elements

[0094] If there are K moments per bin and M representative data elements to estimate, the task is to estimate M(Q+1) unknowns as the least squares solution to K equations. Within a categorical partition, the task must be repeated D or H times for the Data Sphere and Hyper-Rectangles methods, respectively. There is no dependence on n, the number of data elements in the original data set that fall in the categorical partition, except that as n increases the value of D or H may increase toward their respective bounds of 4Q²−2Q+1 and 3^Q. Also, if the number of data elements in any quantitative partition falls as low as M, there is a trivial solution to the equations found by equating the representative data elements to the original data elements.

[0095] The CPU cost of converging to an iterative solution is impossible to specify in advance and depends on the particular estimation algorithm and the data. As discussed earlier, one iteration of the above-mentioned algorithm involves Q steps that construct and process a k′×M Hessian matrix plus M other steps that construct and process a K×(Q+1) Hessian matrix. This involves O(M²K+M³+Q²K+Q³) arithmetic operations and O(MK+QK) memory units. Typically, performing about 100 such iterations for each solution provides satisfactory results.

[0096] For example, for Categorical partitioning choose M=50, and employ a general strategy of M proportional to Q². This results in O(Q⁴K_c+Q⁶+Q²K_c+Q³)=O(Q⁸) arithmetic operations since K_c=O(Q⁴). The required memory is O(Q²K_c+QK_c)=O(Q⁶). For Hyper-Rectangles partitioning, choose M=6, and employ a general strategy of M=Q+1. The estimation has to be repeated across H=O(3^Q) bins for each categorical partition. This results in O(HQ²K_h+HQ³)=O(3^QQ⁴) arithmetic operations since K_h=O(Q²). The required memory is O(QK_h+QK_h)=O(Q³). The Means strategy introduces no further cost of computing representative data elements after computing the moments. For Data-Spheres partitioning, choose M=10, and employ a general strategy of M=2Q. The estimation has to be repeated across D=O(Q²) bins for each categorical partition. This results in O(DQ²K_d+DQ³)=O(Q⁷) arithmetic operations since K_d=O(Q³). The required memory is O(QK_d+QK_d)=O(Q⁴).

[0097] D. Cost Summary

[0098] With respect to memory, all the methods and steps of the squashing technology, with the possible exception of generation process 108 when used with Categorical partitioning, are extremely economical and scale very well in both N and Q. With respect to arithmetic operations, binning process 100 and moment calculation process 106 involve an effort no more onerous than sorting and a very few passes over the data set. Generation process 108 is much more computationally intensive, but has the tremendous advantages that it is hardly affected by the size of N and can make efficient use of parallel processing.

[0099] Particular embodiments of the invention may feature one or more of the following advantages. Data squashing generates a representative data set emulating the multivariate distribution of a larger data set more accurately than random sampling. As opposed to random sampling, data squashing may be tuned to the intended analysis. Random sampling may also create problems when confidentiality is a concern, as with customer or patient records. A squashed data set, however, contains only a representation of the aggregate behavior of the large data set, not individual records themselves. Each modular piece of the data squashing procedure may be individually tuned and improved.

[0100] It should be understood that the above description is only representative of illustrative embodiments. For the convenience of the reader, the above description has focused on a representative sample of all possible embodiments, a sample that teaches the principles of the invention. The description has not attempted to exhaustively enumerate all possible variations. That alternative embodiments may not have been presented for a specific portion of the invention, or that further alternative embodiments may be available for only a portion of the above-described embodiments, is not to be considered a disclaimer of those alternative embodiments. One of ordinary skill will appreciate that many alternative embodiments that have not been specifically enumerated are within the literal scope of the following claims, and that others are equivalent.