Computing and applying order statistics for data preparation

Provided are techniques for generating order statistics and error bounds. For each of multiple, distributed data sources, a finite number of data bins are created for each field in that data source. Data values in each of the multiple, distributed data sources are processed to generate basic summaries for each of the data bins in a single pass of the data values. The data bins from each of the multiple, distributed data sources are sorted. One or more approximate order statistics are computed for a data set by accumulating counts from a number of the sorted data bins. Lower and upper error bounds are provided for each of the computed one or more approximate order statistics, wherein the lower and upper error bounds are values delimiting an interval containing a true value of an order statistic.

FIELD

Embodiments of the invention relate to computing and applying order statistics for data preparation.

BACKGROUND

Pervasiveness and quantity of electronic data available today in all areas of human endeavor call for new approaches in order to extract timely insights and actionable information based on the very large data sets encountered in practice. In addition to sheer data volume, research analysts face methodological challenges when encountering poorly described or irregular data, such as continuous data with non-normal data distribution.

Computation of order statistics and statistical data distributions, along with the other field summaries, is an important part of robust assessment of data properties, as well as, data preparation for further analyses. These summaries are useful in supporting data preparation and diagnostics features, such as outlier detection, histograms, and box plots that are based on order statistics and statistical data distribution. Moreover, non-normal data usually require transformation to normality for exploratory analysis and in preparation for modeling.

The cost of computing order statistics, statistical distributions, and straightening transformations is prohibitive for large and distributed data sets using available computation techniques. It requires either storage of impermissible amounts of data in the main computer memory or multiple data passes. Neither approach is efficient for processing of large distributed data sets. This is in contrast to available computation techniques for simple summaries, such as means or standard deviations, that are computed in a single data pass with modest memory storage requirements.

Some available computation techniques make the data ready for model building without the need for prior knowledge of the statistical concepts involved. Such available computation techniques do not support computation on distributed data sources and are inefficient for very large data sets requiring multiple data passes to accomplish several data transformation steps sequentially.

Some conventional approaches focus on computing quantiles with precision in a specified quantile range. Quantiles may be described as data values taken at regular intervals from a cumulative distribution function of a random variable. Dividing ordered data into q essentially equal-sized data subsets is the motivation for q-quantiles; the quantiles are the data values marking the boundaries between consecutive subsets. Put another way, the k-th q-quantile marks the boundary at the k/q fraction of the ranked data values and there are q−1 of the q-quantiles, one for each integer k satisfying 0<k<q. Here, a more general φ−quantile specification, where φ is a real number with 0≦φ≦1, is used, and the φ−quantile marks the boundary at the φ fraction of the ranked data values. When queried for a φ−quantile whose se precise value is x, these conventional approaches return an element y that is guaranteed to be in the [φ−ε, φ+ε] quantile range. On the other hand, there are no guarantees for the precision of y in terms of the x itself. As a result, there can be uncontrolled errors in the location of the computed approximate order statistics, thus invalidating location-based statistical analysis. Moreover, the important information on the tails of the statistical distribution and their possible anomalies may be lost.

SUMMARY

Provided are a method, computer program product, and system for generating order statistics and error bounds. For each of multiple, distributed data sources, a finite number of data bins are created for each field in that data source. Data values in each of the multiple, distributed data sources are processed to generate basic summaries for each of the data bins in a single pass of the data values. The data bins from each of the multiple, distributed data sources are sorted. One or more approximate order statistics are computed for a data set by accumulating counts from a number of the sorted data bins. Lower and upper error bounds are provided for each of the computed one or more approximate order statistics, wherein the lower and upper error bounds are values delimiting an interval containing a true value of an order statistic.

DETAILED DESCRIPTION

Characteristics are as Follows:

Service Models are as Follows:

Deployment Models are as Follows:

Thus, in certain embodiments, software, implementing statistics computing and application in accordance with embodiments described herein, is provided as a service in a cloud environment.

FIG. 4illustrates a computing environment in accordance with certain embodiments. A computing device400includes a statistics engine410for computing and applying robust statistics for data preparation. The statistics engine410includes a data summary component420, a data preparation component422, and a transformation component424. The computing device400also includes univariate data summaries430, transformation rules and metadata432, transformed data, statistics, and metadata434, basic summaries436, final summaries438, and memory440. The computing device400is coupled to a data store450, which stores data460.

The memory440may be described as a collection of memory reserved for intermediate computations in all fields. The memory440may include caches442and/or buffers444. In certain embodiments, there is one cache442per each numeric field and one buffer444per each string field.

Univariate data summaries430encompass all summaries. Univariate data summaries430are based on the whole dataset and include order statistics, statistical data distributions and other descriptive statistics, such as mean, variance, skewness, etc. The basic summaries436in each data bin (e.g., referenced in blocks702a, . . . ,702nofFIG. 7A) are different from the univariate data summaries430and include the lower and upper bounds, count, and mean. Thus, basic summaries are used with reference to the data bins, and univariate data summaries are used with reference to the whole dataset.

The statistics engine410computes univariate data summaries430(such as order statistics, statistical data distributions, and other descriptive statistics) for each field in very large and distributed data sources. Data values for each field are aggregated into a finite-sized list of data bins based on their location. Basic summaries436(such as count, mean, minimum, and maximum) are maintained for each data bin, while the data values are discarded. These basic summaries436are further aggregated when merging data bins from different data sources of the distributed data. This approach uses a single data pass and is scalable since only a limited amount of memory is used per field. Final summaries438provide approximate order statistics with limited location errors, their deterministic error bounds, as well as, approximate statistical data distribution for each field. The summaries for categorical fields having a limited number of distinct values are exact. The computed approximate order statistics are of interest in data analysis because they realistically summarize the distribution of data and are less sensitive to outlying data values than the simple summaries (such as mean or variance).

The computed univariate data summaries430are used as inputs for the data preparation component422for generating statistical distribution plots, transformation rules for outlier detection, missing data handling, and distribution straightening transformations. In order to transform distributions to symmetry, certain embodiments use Box-Cox power transformations providing a continuum of transformation functions through an estimable parameter. The statistics engine410introduces a new approach based on the computed approximate order statistics to estimate the power transformation parameter. This approach provides a transformation insensitive to extreme values and it has no additional data access for obtaining the robust transformation rule.

Thus, the statistics engine410delivers univariate data summaries430and transformation rules and metadata432for robust data assessment and preparation.

Order statistics depict the features of original data and are mostly insensitive to extreme values. Computing the data preparation transformations based on the small number of approximate order statistics is more efficient than using a large volume of the original data. The statistics engine410generates scalable and robust univariate data summaries430in a single data pass, performs metadata discovery or conformance rule checking to guarantee measurement level specification, and generates data preparation rules based on the approximate order statistics. Also, the transformation component424executes generated transformation rules dynamically, while the data is read by the subsequent analytic components. The statistics engine410serves as the fundamental module for evaluating data quality and supporting exploratory data analysis and predictive modeling.

FIG. 5illustrates, in a flow diagram, operations to compute and apply robust statistics for data preparation in accordance with certain embodiments. Control begins at block500with the data summary component420receiving input data460. In block502, the data summary component420uses the input data460to generate one or more univariate data summaries430. In block504, the data preparation component422uses the one or more univariate data summaries430to generate one or more transformation rules and metadata432. In block506, the transformation component424uses the one or more transformation rules and metadata432to generate transformed data, statistics, and metadata434. From block506, processing may continue to blocks508and/or510. In block508, data exploration is performed by some analytic engine using the transformed data, statistics, and metadata434. In block510, predictive modeling is performed by some analytic engine using the transformed data, statistics, and metadata434.

Data Summary Component

A metadata specification may be described as a specification of various properties for each field in the data set. Given a new data set with an undefined or an incomplete analytic metadata specification, the data summary component420executes the initial data pass for the purpose of generating univariate data summaries430. This data pass produces approximate field distributions and order statistics that provide univariate statistics and support generating appropriate metadata specifications. This data pass is for the new data sets and the results remain available for any subsequent analyses.

The prior information requirement should be minimized for large and distributed data sources because extracting basic metadata information from them can be very expensive. The only information stored is the storage type of each data field: numeric or string. The data summary component420performs computation that consists of dispatching operations to each data source, stream computation in each data source, and a final consolidation stage.

Computation for a Numeric Field

For a numeric field, the dispatching operation parses computation requirements from an application, constructs the content and order of the computations, and dispatches the content and order of the computations to each data source.

When performing stream computation in each data source, the data summary component420treats the local data as a stream data source. The data values of each numeric field are aggregated into a list of data bins (“bin lists”). Each data bin represents a cluster of data values that specifies the smallest and the largest values, as well as, the count and the mean of the data values within that data bin. All counts in the data bins are weighted when appropriate. The data bins do not store the data values. After the data bin lists for the given field from different data sources are created, the data bin lists are combined together. In certain embodiments, the combined data bin list is sorted by the ascending order of the lower bounds of the data bins.

Order statistics (such as median, quartiles or percentiles) may be approximated from the combined data bin list without sorting the original field data values. Deterministic error bounds are provided for each of the one or more order statistics, and it can be proved that the true value of the related order statistic is within the estimated error bounds. The width of each data bin is maintained within limits bounded by the range of the data divided by the number of data bins per data source. The errors with their bounds can be controlled by the user through specifying the limit on the number of data bins. A larger number of data bins will result in smaller errors. The term “smaller” refers to the size of the error (i.e., the distance from the true values). The bounds on the error size become smaller with the larger number of data bins. Moreover, the achieved accuracy may be better due to the procedure exploiting larger gaps in the range of data values. That is, data bins are not necessarily adjacent, and larger gaps in data values are preserved as gaps between data bins. This results in tighter error bounds than calculated directly from the field range and the number of data bins. Thus, with embodiments, the maximal location errors are limited.

The data summary component420creates the data bin list for the field in each data source, and then estimates the error bounds based on the combined data bin list. Error bounds are based on the observed data values, and the size of the data bin list for each data source can be fixed in advance. The error bounds are deterministic and provide overall accuracy for the computed approximate order statistics.

Each data bin list is empty at the beginning of the data pass. New data values are added as new data bins containing a single data value, where lower bound, upper bound, and the mean are all equal. If a new data value falls between the lower and the upper bound of an existing data bin, the count and the mean for that data bin are updated with the data value.

As additional data values arrive, the size of the data bin list will reach a given threshold designed to conserve the memory usage. In this case, the data summary component420merges some of data bins to keep the size of the data bin list limited. Instead of performing merge whenever a new data bin is created, the data summary component420caches (i.e., stores in a cache442in memory440) the new data bins to a temporary data bin list until the number of data bins in the cache442reaches a given size threshold. The data summary component420performs the merging procedure on the combined data bin list and the temporary data bin list in the cache442.

Each pair of data bins that have the least distance between their means are merged together repeatedly until the threshold size of the data bin list is reached. When data bins are merged, the counts and the means are aggregated from the contributing data bins. The lower bound is set to the smaller of the two former lower bounds, while the upper bound is set to the larger of the two former upper bounds. An additional criterion for merging data bins is that width of the newly formed data bin should be less than twice the range divided by the number of data bins active for merging. This ensures that the final estimates have limited error bounds.

When merging the data bins, the first and the last S data bins are not involved in finding the nearest data bin pairs. S may be described as a specified constant that does not vary with the size of the data. Therefore, the S smallest values and the S largest values are preserved as potential outliers for a later data preparation. This feature preserves an accurate representation of the two tails of data distribution.

FIG. 6illustrates in a flow diagram, operations for stream computation in each data source in accordance with certain embodiments.FIG. 6is formed byFIGS. 6A,6B, and6C. Control begins at block600with the data summary component420receiving input data from one data source. In block602, the data summary component420determining whether, in the input data, there is a new data value to be processed. The new data value represents a new data value for a field. If so, processing continues to block604, otherwise, processing continues to block614(FIG. 6C).

In block604, the data summary component420determines whether the new data value falls into an existing data bin. If so, processing continues to block606, otherwise, processing continues to block608.

In block606, the data summary component420updates the count and the mean for this data bin. From block606, processing returns to block602(FIG. 6A).

In block608, the data summary component420creates an additional data bin for the single new data value in the cache442.

In block610, the data summary component420determines whether the cache442is full. If so, processing continues to block612, otherwise, processing returns to block602(FIG. 6A).

In block612, the data summary component420merges data bins with single data values each in the cache442with the existing data bins. From block612, processing continues to block602(FIG. 6A).

From block602, if there is no new data value to be processed in the input data, processing continues to block614. In block614, the data summary component420merges additional data bins with single data values each in the cache442with existing data bins. In block616, the data summary component420outputs a data bin list for the data source with the bounds, counts, and means for each data bin.

Once each data source is processed in accordance with the processing ofFIG. 6, specified quantiles are computed in a final consolidation stage. The count of every data bin from each data source is accumulated in the ascending order of the data bins' lower bounds until the accumulated count exceeds the count corresponding to the desired quantile. The estimated quantile value is the mean of the last accumulated data bin. The lower error bound of the estimated order statistics is the lower bound of the last accumulated data bin, and the upper error bound of the estimated order statistics is the largest upper bound of all the accumulated data bins. For example, the approximate median can be found by accumulating the counts of all data bins in ascending order of lower bounds until the accumulated count is larger than 50 percent of the total count. The approximate median equals the mean of the last accumulated data bin. The lower bound of the last accumulated data bin and the largest upper bound of all the accumulated data bins are the lower and the upper error bounds for the approximate median, respectively.

FIG. 7illustrates, in a flow diagram, operations for computing approximate order statistics and error bounds from distributed data sources in accordance with certain embodiments.FIG. 7is formed byFIGS. 7A and 7B. For each data source1, . . . , N, the data summary component420receives input data from a single data source (block700a, . . . ,700n), creates a data bin list from the singe data source with basic summaries436(block702a, . . . ,702n), and outputs a data bin list with the basic summaries436(block704a, . . . ,704n). The basic summaries436include the lower and upper bounds, counts, and means for each data bin list. That is, blocks700a, . . . , n,702a, . . . ,702n, and704a, . . . ,704nrepresent the processing ofFIG. 6for each data source.

In blocks706-712, the data bin lists and basic summaries436of each data source are combined. In block706, the data summary component420collects and sorts (i.e., orders) data bins. In block708, the data summary component420accumulates counts from a sufficient number of sorted (i.e., ordered) data bins. In certain embodiments, the term “sufficient” refers to the accumulated counts exceeding the counts corresponding to desired quantiles. In block710, the data summary component420computes approximate order statistics and error bounds based on the accumulated counts. In block712, the data summary component420outputs the approximate order statistics and error bounds for the overall data from all of the data sources, wherein the lower and upper error bounds are values delimiting the interval containing the true value of an order statistic for each computed approximate order statistic. In particular, the upper and lower bounds are provided along with each computed approximate order statistic. The true value lies in the interval between the lower and upper bound and, therefore, within limited distance from the computed approximate order statistic.

Computation for a String Field

For a string field, the dispatching operation parses computation requirements from an application, constructs the content and order of the computations, and dispatches the content and order of the computations to each data source.

Stream computation in each data source treats the local data as a stream data source.

In certain embodiments, a buffer444in memory440containing distinct values with corresponding count is maintained for each string field. If a given data string value is found in the buffer444, its count is updated accordingly. Otherwise, a new distinct value is added to the buffer444and its frequency is set to the case weight. Once the buffer444contains M distinct string values, the new distinct values are no longer added into the buffer444, and all the other string values are counted as a single group. M is set large enough to preserve the string field information and it also depends on the available memory.

In the final consolidation stage, the frequencies for the same distinct string value from all the data sources are added together, and the distinct string values with the largest L counts are selected to represent this field. If any of the contributing buffers444contains M distinct values, the final computed counts provide the lower bounds for the actual counts.

Data Preparation Component

To gain the metadata information and assure its validity, the data preparation component422generates appropriate metadata specifications based on the univariate data summaries430obtained from the data summary component420. These specifications are either produced by applying the metadata discovery rules when no metadata information is available from the data source or updated by applying conformance rules when metadata is available but possibly mis-specified. Numeric field storage type can be specified as either integer or real.

The data preparation component422also implements various features after metadata specification, such as outlier detection and handling, missing value handling, Box-Cox transformation (which transforms distributions to symmetry), etc. These features use the approximate order statistics from the data summary component420, as well as, the metadata specifications as input. Their output contains transformation rules for creating new fields. Using the approximate order statistics has two merits: (1) no additional data pass is required which saves time, especially for the very large data sets; and (2) it makes the transformations more robust against the extreme values in data.

Embodiments use the computed approximate order statistics in Box-Cox transformation. Specifically, the Box-Cox transformation function based on the original data yi, i=1, . . . , N, is specified as follows:

g⁡(yi,λ)={((yi-c)λ-1)λλ≠0ln⁡(yi-c)λ=0
where c=min(y)−1 and λ is the transformation parameter which is selected by grid search over a finite set [a, b] with increments to maximize the log-likelihood function:

L⁡(λ)=-N2⁢ln⁡[N-1N⁢(sd⁡(g⁡(λ)))2]+(λ-1)⁢∑i=1N⁢ln⁡(yi-c),
where sd(g(λ)) is the standard deviation of Box-Cox transformation of y values.

Embodiments use approximate order statistics instead of the original data to estimate the transformation parameter λ by a grid search with the maximum log-likelihood value, i.e., replace yi, i=1, . . . , N, in the above log-likelihood function with percentiles, pi, i=0, 1, . . . , 100, where piis the ithpercentile value so p0is the minimum and p100is the maximum. Then the original data yi, i=1, . . . . , N, are transformed by the Box-Cox transformation function. Embodiments avoid one data pass and improve speed of the Box-Cox transformation as 101 values may be used no matter how large the data set is. Moreover, experiments indicate the estimated transformation parameter, which is the transformation rule, based on the percentiles is close to that based on the original data.

FIG. 8illustrates, in a flow diagram, operations for generating transformation rules and metadata in accordance with certain embodiments. Control begins at block800with the data preparation component422receiving univariate data summaries430. In block802, the data preparation component422obtains one or more metadata specifications by applying the metadata discovery rules when no metadata information is available from the data source or updated by applying conformance rules when metadata is available but possibly mis-specified. That is, in block802, the data preparation component422performs metadata discovery and conformance rule checking From block802, processing continues to blocks804,806, and808.

In block804, the data preparation component422handles outliers based on approximate order statistics. In block806, the data preparation component422handles missing values based on approximate order statistics. In block808, the data preparation component422performs Box-Cox transformation based on approximate order statistics. From blocks804,806, and808, processing continues to block810.

In block810, the data preparation component422outputs transformation rules and metadata.

Transformation Component

The transformation component424executes any transformations generated by the data preparation component422and passes the corresponding values to other data consuming components for data exploration and predictive modeling. The scalable and distributed mechanism for executing the data transformations is processing the data in a distributed file system. The transformation component424generates values for the new variables specified by the transformation rules. Both the original and the transformed fields are presented as data to the subsequent analytic components. No additional data passes are necessary for generating the transformed values since the transformation rules are record-based and can be executed concurrently with data reading required for the input to the modeling components.

The transformation component424completes the flexible system of extracting robust statistics from the original data, creating appropriate transformation rules, and executing them on an as needed basis.

Thus, the statistics engine410provides a solution for delivering summaries and transformation rules needed for robust data assessment and preparation. The statistics engine410computes univariate data summaries430, including robust order statistics and statistical distributions, for analysis of irregular, large and distributed data sources. The statistics engine410computes approximate order statistics with limited location errors and their deterministic error bounds. Moreover, the statistics engine410generates the data transformations for data exploration and data preparation for modeling based on the acquired robust summaries. The statistics engine410is useful for an increasing number of large and distributed data source installations found in business, government, and industry.

The statistics engine410calculates approximate order statistics in a single data pass, with limited location error bounds. Also, the statistics engine calculates the Box-Cox transformation parameter based on the computed approximate order statistics, rather than on the original data.

The statistics engine410approximates the order statistics for each field in a single data pass from distributed data by creating data bins for each distributed data source, collecting data bins from all distributed data sources, sorting the data bins, and calculating approximate order statistics by accumulating counts from a sufficient number of ordered data bins. The statistics engine410reports deterministic error bounds for each approximate order statistic, and the errors with their bounds can be controlled through specifying the limit on the number of data bins as the larger number of data bins will result in smaller errors.

The statistics engine410uses a predefined number of data bins for each data source without making any assumptions about data, while the boundaries of the data bins are dynamically adjusted. The statistics engine410creates a set of data bins for each field and for each data source such that only a small number of basic summaries436are maintained for each data bin.

The statistics engine410is able to extract robust statistics from the original data and create appropriate transformation rules in a single data pass and deliver statistics transformation rules for data exploration and predictive modeling. In particular, the statistics engine410creates a limited, finite number of data bins for each field and for each distributed data source such that only a small number of basic summaries436are maintained for each data bin; collects data bins from each distributed data source and sorts them; calculates approximate order statistics for the overall data set by accumulating counts from a sufficient number of ordered data bins; provides error bounds which are values delimiting the interval containing the true value of an order statistic for each computed approximate order statistic; discovers or verifies metadata properties based on the computed summary statistics; applies the computed approximate order statistics to generate data transformation rules for outlier and missing value handling; calculates power transformation parameters for Box-Cox transformation using the computed approximate order statistics; and generates the corresponding transformation rule.

The statistics engine410also creates a set of data bins for each distributed data source by: generating a data bin of zero width for each of the predetermined number of the initial data values; adding further data values to the existing data bins and updating basic summaries436when any new point values can be placed within the existing data bin bounds; creating preset number of additional data bins for the points whose values cannot be placed within any of the existing data bin bounds; setting the approximation bound proportional to the range of the values divided by the predetermined number of data bins; and merging the additional data bins with the existing data bins in batches by adjusting the data bin summaries to reflect the merged data bins when number of data bins exceeds a preset threshold and ensuring that the closest data bins are merged first and that width of the merged data bins does not exceed the approximation bound.

Additional Embodiment Details

The code implementing the described operations may further be implemented in hardware logic or circuitry (e.g., an integrated circuit chip, Programmable Gate Array (PGA), Application Specific Integrated Circuit (ASIC), etc. The hardware logic may be coupled to a processor to perform operations.