Using a data mining algorithm to generate format rules used to validate data sets

Provided are a method, system, and article of manufacture for using a data mining algorithm to generate format rules used to validate data sets. A data set has a plurality of columns and records providing data for each of the columns. Selection is received of at least one format column for which format rules are to be generated and selection is received of at least one predictor column. A format mask column is generated for each selected format column. For records in the data set, a value in the at least one format column is converted to a format mask representing a format of the value in the format column and storing the format mask in the format mask column in the record for which the format mask was generated. The at least one predictor column and the at least one format mask column are processed to generate at least one format rule. Each format rule specifies a format mask associated with at least one condition in the at least one predictor column.

BACKGROUND OF THE INVENTION

The present invention relates to a method, system, and article of manufacture for using a data mining algorithm to generate format rules used to validate data.

2. Description of the Related Art

Data records in a database may be processed by a rule evaluation engine applying data rules to determine data records that have column or field values that deviate from the values that are expected by the rules. In the current art, the user manually codes data rules by first analyzing the data visually or using a profiling tool to obtain an understanding of the pattern of a well-formed record. Next a user builds logical expressions that define a set of rules to describe the normal characteristics of records in the set. These rules are then repeatedly executed against data sets to flag records that fail the conditions specified by the data rules and report on trends in failure rates over time.

A user may use a rule editor user interface to create new data rules or modify existing rules. Rules may be expressed in a rule language, such as BASIC, Structured Query Language (SQL), Prolog, etc. The user may then save rules in a rule repository in the rule language or in a common rule format. The user may then select rules from the rule repository and a data set of records to provide to the rule evaluation engine to execute the selected rules against the selected data records to validate the data, capture the results and display the results to the user.

Developing data rules can require a significant amount of user time, effort and skill to analyze patterns in data, especially for large data sets having millions of records with hundreds of columns. Further, rules to validate the format of data in data columns may be further difficult to create because many different formats may be used to record the data, such as different formats for phone numbers, etc. Data quality tools may be used to report the existence and frequency of multiple formats for a given column. However, they provide little help to understand why several formats exist, and, for a given row in the data set, which format is the correct one. The data analyst must use the report to decide which format should be allowed and create the corresponding data rules by hand. Since there may be numerous acceptable formats for data, the resulting validation rule may be too general (e.g. phone matches(999-9999 or 999-999-9999 or 99-99-99-99)), or too restrictive (e.g. phone matches(999-999-9999)) or too complex to build, understand and maintain (e.g. if country=(‘USA’ or ‘US’ or ‘United States’) then phone matches(999-9999 or 999-999-9999 or 9-999-999-9999).

There is a need in the art to provide improved techniques for generating and using format rules to validate the format of data.

SUMMARY

Provided are a method, system, and article of manufacture for using a data mining algorithm to generate format rules used to validate data sets. A data set has a plurality of columns and records providing data for each of the columns. Selection is received of at least one format column for which format rules are to be generated and selection is received of at least one predictor column. A format mask column is generated for each selected format column. For records in the data set, a value in the at least one format column is converted to a format mask representing a format of the value in the format column and storing the format mask in the format mask column in the record for which the format mask was generated. The at least one predictor column and the at least one format mask column are processed to generate at least one format rule. Each format rule specifies a format mask associated with at least one condition in the at least one predictor column.

DETAILED DESCRIPTION

FIG. 1illustrates a computing environment in which embodiments may be implemented. A system2includes program components comprising a rule discovery module4, a rule editor user interface6, a rule evaluation user interface8, a rule repository10, and a rule evaluation engine12. The rule discovery module4includes a rule engine14including a data mining engine15and a converter20, a rule discovery user interface16, and a deviation detection user interface18. The program components in the system2, including components4,6,8,10,12,14,15,16,18, and20may comprise software components that are loaded into a computer readable memory in the system2and executed by a processor of the system2. Alternatively, groups of one or more of the components4,6,8,10,12,14,15,16,18, and20may by on different systems having different processors and memory. Yet further, the system2may comprise multiple processors or distributed processes that execute the components4,6,8,10,12,14,15,16,18, and20. The system is further coupled to a data source22that contains records and fields, where the records may have one or more fields. The data source22may be implemented in a computer readable medium, such as a storage device.

The data mining engine15may comprise data mining engines known and available in the art. The rule engine14may include one or more data mining engines15implementing one or more data mining functions/algorithms that analyze data to produce data mining models, which may be in a known format such as the Predictive Model Markup Language (PMML). The converter20analyzes the data mining models from the data mining engine15(which are not appropriate by default to solve data validation problems), extract the data validation rules, and write the data rules in a common format that can be reused by the rule evaluation engine12.

The rule discovery module4is invoked to automatically generate data rules that validate the values of data records in a table in the data source22. The data rules indicate one or more conditions for one or more predictive fields that infer within a defined confidence and support level predicted conditions of one predicted field. A predicted condition for a predicted field may specify a value, a range of values or specific values for a predicted field, e.g., age <18, salary >=40000, profession is in {a, b, c}, or other condition types known in the data mining art. These rules may then be applied to data sets to determine field values that deviate from the rules and thus may be erroneous.

The rule engine14applies a data mining engine15implementing a data mining algorithm to a data set of records to determine data rules for the data. The data mining algorithm determines rules that specify a predicted condition for fields based on one or more predictor conditions in other fields. In one embodiment, the data mining algorithm comprises an association rules algorithm. The converter20may further convert data rules in the model language of the algorithm, such as the Predictive Model Markup Language (PMML), into a common rule model language, such as a data validation language. The rule repository10may store rules in a common rule format, even if the rules were generated in different formats from different rule algorithms. The rule repository10may be implemented in a storage device coupled to the system2or the memory of the system2.

The rule discovery user interface16provides a user interface to a user that allows the user to specify parameters for the rule engine14, such as a minimum confidence level, minimum support level, minimum lift, and maximum rule length for generated rules and one or more data mining algorithms for the rule engine14to use. A confidence level indicates a minimum probability at which one or more predictor conditions from predictive fields infer the predicted condition for the predicted field, i.e., the certainty in the records that are analyzed by the rule engine14that one or more fields predict a condition in another field. A support level indicates a minimum number or percentage of records of the analyzed records that must satisfy the determined data rule. A minimum lift value may be of the form lift (A->C)=confidence(A->C)/support(C), providing a measure of interest in the rule. Lift values greater than 1.0 indicate that transactions containing A tend to contain C more often than all transactions.

The deviation detection user interface18presents to the user those records in the analyzed data set used to produce the data rules that deviate from, i.e., do not satisfy, the rules. This allows the user to review and consider the extent to which the data rules are correctly identifying erroneous data or incorrectly identifying correct records as deviant.

The rule discovery module4thus automatically determines data rules for a data set with a confidence metric that measures how strongly the rules are supported by the data sets.

The rule engine14provides the generated data rules to a rule repository10. A rule editor user interface6allows the user to edit, modify and delete the generated data rules. For instance, the user may inspect data records that deviate from the generated data rules in the deviation detection user interface18and then edit the generated rules in the rule editor user interface6based on an analysis of the deviant records and logic of the generated data rules.

The user may use the rule evaluation user interface8to select a rule or set of rules from the rule repository to execute against data sets in the data source22having records to which the selected rules apply. The selected rules are loaded from the rule repository10to a rule evaluation engine12which executes the rules against selected tables and records from the data source22, capturing results and analysis which are displayed to the user via the rule evaluation user interface8. Upon the rule evaluation engine12identifying deviant records, the evaluation engine12may apply automatic corrections to the data or present deviant records to the user to review and edit.

The user interfaces6,8,16, and18may be implemented in a graphical user interface or through a command line interface in which the user enters textual commands to control the rule engine14, rule repository10and rule evaluation engine12.

The data mining engine15may utilize a data mining association rules algorithm to generate data rules from a data set of records. An example of such an algorithm is the APRIORI algorithm or the algorithm described in U.S. Pat. No. 5,615,341. These algorithms may produce association rules models as defined in the PMML standard. An association rules model contains rules that express an association between items occurring together in a same transaction. For instance, the association algorithm may receive as an input two columns, one for the transaction identifiers (IDs) and one for the items. The association algorithm then searches for all relationships between the items, making no assumptions on the content of the analyzed items, treating them only as strings. In certain embodiments, the association algorithm may also detect the relationship between the conditions, e.g., values, of columns of a table. The data mining engine15may then assume that each row in the table is a transaction and generate one item “COL=val” for each column, which is then passed to the association algorithm. The data rules generated by data mining association rule algorithms may follow the form of—if <conditions> then <format_test>, where <format test> is an expression that tests the data format for a column. The data mining engine15using a data mining association rules algorithm may generate all data rules that satisfy the specified confidence, support level, and lift.

In certain embodiments, the rule discovery module4and rule editor user interface6may be on a separate system than the system that includes the rule evaluation engine12and rule evaluation user interface8to use the generated rules. Further, any of the components of the rule discovery module4or other components shown in the system2may be implemented on one system or in a distributed computing environment. In one embodiment, the repository10is implemented in a separate system from one or more systems including the other components.

FIG. 2illustrates an embodiment of the system2memory30including a data set32. The data set32may comprise a table having four shown columns A, B, C, and D. In one embodiment, the user may select, using the rule discovery user interface16, one or several format columns (predicted columns) and one or more condition columns (predictor columns). The user seeks to generate format rules for the format columns based on an association with the predictor columns, such that the format rules seek to predict a format of the format columns based on the conditions specified in one or more predictor columns. The user may further select one or more columns to appear in the result set. In the example ofFIG. 2, the user selects column A as the format column, column B as the predictor column, and column C as one column to additionally appear in the result set.

The rule engine14may generate a data set copy34comprising a copy of the data set that includes the format column A, predictor column B, additional column C to appear, and a format mask column A′ that includes a format mask for each record generated from the value in the format column for the record. Format mask definitions may provide a mask to represent types of character values that may be present in the format column A. For example, a format mask in the format column A may be generated from the value in the format column A by replacing each character of the value by “9” if the character is a digit, “a” if the character is a lowercase letter, “A” if an uppercase letter, and letting any other character remain unchanged. In other embodiments, other characters may be used for the mask definition to represent types of characters such that the mask definition is well-defined and indicates where digits, lowercase/uppercase letters and special characters are located. In fact not only other characters can be used but also other formats. For instance, an alternative to the suggested “999AA99aaa” format may comprise a regular expression such as “[0-9]{3}[A-Z]{2}[0-9]{2}[a-z]{3}”. The rule engine14generates association rule predict format masks based on conditions in the one or more predictor columns. The conditions in the predictor columns may comprise the form of col=val, col<val, col between val1and val2, etc. These rules may be applied by checking whether data records having a value in the predictor column specified in a format rule have a format in their format mask column that complies with the format mask specified in the rule. The format mask and predictor column conditions in the format rules may comprise a discrete value, a range of values or a regular expression defining a set of values.

FIGS. 3aand3billustrate an embodiment of operations performed by the components of the system2to generate data rules from a data set of records in the data source22. Upon initiating (at block100) rule generation operations, the rule engine14receives (at blocks102) a data set having records from which to generate rules. The rule engine14may further receive (at block104) the minimum confidence, support and lift levels and a maximum rule length from the rule discovery user interface16. The minimum confidence level, which may be specified by the user, is a confidence level that the final rules must satisfy, and may be set to a relatively high value, e.g., 90%. The data mining engine15may use low minimum confidence level that is used for generating an initial rules set to capture patterns where one condition may lead to different formats. This low minimum confidence level used by the data mining engine15to generate the initial rules to consider may be substantially lower, e.g., 5%, than the minimum confidence level specified by the user for the final rule set. This initial rules set is further processed to generate final consolidated rules, each having a confidence level that satisfies the user set minimum confidence level. This low minimum confidence level may be a predefined variable for the data mining engine15which the user does not set. The rule engine14may further receive (at block106) selection of one or more format columns for which format rules are generated, one or more predictor column(s) used to predict a format of the format column, and columns from data set to appear in a result set. The result may be generated by applying final format rules to the data set to determine records that do not have a format required or predicted by the rules. This final result set of records is presented with the additional columns of data that the user selected to appear in the result set.

In one embodiment, the rule engine14may create (at block108) a data set copy34including the selected format columns, the predictor columns and optionally selected columns to appear in result set from the data set32. The rule engine14may further generate (at block110) a format mask column into the data set copy34for each format column to predict. In an alternative embodiment, the rule engine14may perform operations directly on the data set32and include the format mask columns in the data set32, without creating a data set copy34to use. For each record in the data set copy32, the rule engine14generates (at block112) in the format column a format mask representing a format of the value in the corresponding format column and storing the format mask in the format mask column in the record for which the format mask was generated. As discussed the format mask includes a mask for each character in the format column field based on a format mask definition.

The rule engine14may then preprocess (at block114) the data before the data mining engine15extracts the data validation rules. Preprocessing the data may involve discretization, which converts values in numerical columns into a categorical range of values. Preprocessing may further involve pivoting the data records in the received data set if the data mining engine15used requires pivoted data. For instance, if the data mining engine15comprises an association rules algorithm, then the preprocessing operation may involve pivoting the table in a two columns format (transaction ID, item) where each item is “COL=value” and where the numeric values are discretized.

With respect toFIG. 3b, the data mining engine15then applies (at block116) a data mining algorithm to process the predictor columns and the format mask columns to generate at least one format rule, wherein each format rule specifies a format mask associated with at least one condition in at least one predictor column, such that the condition in the predictor column predicts the format mask. The format mask and predictor column conditions in the format rules may comprise a discrete value, a range of values or a regular expression defining a set of values. The rules may be in the PMML model format.

In one embodiment, the data mining engine15builds an association rules model with the appropriate parameters and filter conditions to configure a minimum confidence to maximize the number of possible mask format patterns captured for a particular predictor column condition. Using a low minimum confidence, lower than the minimum confidence level specified by the user for the final rule set, increases the number of rules that are initially generated to capture how values in the format column may be recorded in slightly different formats. Each slightly different format in how the value is recorded may result in a different rule in the association rules model. Building a model with low minimum confidence will capture these different variations so they can be merged later into one rule with the same condition and a confidence measure derived from the confidence of each rule. Thus, the data mining engine15provides confidence, support, and lift for each generated rule to use when determining which rules to discard. For example, a French phone number can be written as “99-99-99-99-99” or “99 99 99 99 99” or “99.99.99.99.99”. Such variations may be captured by separate rules with each having a relatively low confidence as shown below:
[country=France]=>[format=99 99 99 99 99] (15% conf)
[country=France]=>[format=99.99.99.99.99] (55% conf)
[country=France]=>[format=99-99-99-99-99] (25% conf)

The above format rules for the exemplar French phone numbers with the lower confidence variations may be combined in a later step to generate a single rule with a confidence equal to the sum of the individual rule confidence measures, such as the below rule having the combined confidence level:
[country=France]=>[format=99 99 99 99 99 or 99.99.99.99.99 or 99-99-99-99-99] (95%)

The rule engine14may remove redundant rules by determining rules having the same format mask and then remove (at block118) those format rules having one or more conditions such that the format being predicted is the same and for the same column, and the conditions of the rule to be removed, e.g., r2, are fully contained in the conditions of the rule to retain, e.g., r1. The conditions of one rule (r2) are fully contained in another rule (r1) if the condition of r2is necessarily true if the condition of r1is true. In other words a rule having the same format mask as another rule is removed if its predictive condition in the predictor column includes the predictive condition of the other rule having the same mask for the same format column. For instance if you have the 2 rules:

then rule (1) can be removed because (2) predicts the same thing in a simpler way and with a similar confidence. For instance, since Paris is in France, the first rule with the additional condition of Paris can be removed. In certain embodiments, the more complex rule, i.e., including more conditions, is only removed if the confidence level of the more complex rule is not significantly better than the simpler rule.

Further redundant rules may further be reduced or consolidated by determining (at block120) format rules having a same condition(s) for the same predictor column(s) and different format masks for the same format mask column and then merging (at block122) the determined format rules having the same predictor conditions into a merged format rule. If a rule has multiple predictor columns providing conditions, then rules are merged that have the same conditions for all the predictor columns.FIG. 4below provides an additional embodiment for merging format rules having the same predictive conditions.

The rules engine14determines (at block124) from the consolidated set of format rules qualifying rules that satisfy the specified confidence and support level conditions. The data mining engine15may further apply the qualifying rules to identify records, from the data set or a compatible data set that was processed to generate the data rules, that do not satisfy the rules, i.e., deviate from the generated rules. The deviation detection user interface18may then present the determined deviant records to the user to review. This allows the user to analyze whether the rules are appropriately identifying deviant records and to determine rules that may be needed.

The converter20may then format (at block126) the generated qualifying rules, into a common rule format and store the formatted rules in the rule repository10. For instance, the converter20may read the rules, which may be in a rule model format such as PMML, obtained by mining, extract the information contained in them and convert that to the model or language used to define the data validation rules, i.e., the common rule format. The rule editor user interface6enables (at block128) the user to review, edit, delete and modify rules in the rule repository10. The user may further use the rule editor user interface6to store (at block130) the user edited set of data rules in the rule repository10.

FIG. 4provides a further embodiment for merging format rules having the same predictor conditions, such as performed at operations120and122inFIG. 3b. Upon initiating (at block150) the operations to determine format rules to merge to consolidate the format rules, the rules engine14determines (at block152) groups of format rules having a same condition for the same predictor column(s) and different format masks for the same format mask column. For each determined group of format rules having the same condition for the predictor columns, the rule engine14performs the operations at blocks154-162. At block156, the rule engine14sums (at block156) the confidence levels for the format rules in the group. If (at block158) the summed confidence level is less than the minimum confidence level, then the format rules in the group are removed (at block160) because the combined or consolidated format rule still does not satisfy the required minimum confidence level specified by the user for a rule to be included in the validation rule set. If (at block158) the summed confidence level satisfies the minimum confidence level, then the rule engine14creates (at block162) a merged rule having the same predictor conditions and a format mask value (e.g., expression) that defines a set including all the format masks for the determined format rules.

FIG. 5illustrates an example of how the rules engine may process a data set200having seven columns. To determine how the value in the city202and country204columns may predict the format of the value in postal code column206, the user would select the predictor columns as the city202and country204columns and the format column as the postal code column206. The user may further select to include all columns in the result set except the region column208. The rules engine14may then generate a data set copy210having all the selected columns except the region column208from the starting data set200. Further, the rules engine14generates the format mask column212including masks for each postal code value in the format column206. The rules engine14using the data mining engine15then generates a final set of validation rules220using the operations ofFIGS. 3a,3b,4predicting the format mask for the postal code based on different values for the city and country predictor columns. The rules evaluation engine12may then apply the rules220to the copy data set210or other data set to produce a result set222of records that do not satisfy the validation rules220, which the user may review. Only those columns the user selected to appear are generated into the result set222, which in the example ofFIG. 5includes all columns except the region column208from the initial data set200.

With the described embodiments, a rule discovery program using a data mining engine may generate format mask rules based on a data set of records that may be used to determine whether the format of data in a selected format column in a data set is in a valid format.

Additional Embodiment Details

The described operations may be implemented as a method, apparatus or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The described operations may be implemented as code maintained in a “computer readable medium”, where a processor may read and execute the code from the computer readable medium. A computer readable medium may comprise media such as magnetic storage medium (e.g., hard disk drives, floppy disks, tape, etc.), optical storage (CD-ROMs, DVDs, optical disks, etc.), volatile and non-volatile memory devices (e.g., EEPROMs, ROMs, PROMs, RAMs, DRAMs, SRAMs, Flash Memory, firmware, programmable logic, etc.), etc. The code implementing the described operations may further be implemented in hardware logic (e.g., an integrated circuit chip, Programmable Gate Array (PGA), Application Specific Integrated Circuit (ASIC), etc.). Still further, the code implementing the described operations may be implemented in “transmission signals”, where transmission signals may propagate through space or through a transmission media, such as an optical fiber, copper wire, etc. The transmission signals in which the code or logic is encoded may further comprise a wireless signal, satellite transmission, radio waves, infrared signals, Bluetooth, etc. The transmission signals in which the code or logic is encoded is capable of being transmitted by a transmitting station and received by a receiving station, where the code or logic encoded in the transmission signal may be decoded and stored in hardware or a computer readable medium at the receiving and transmitting stations or devices. An “article of manufacture” comprises computer readable medium, hardware logic, and/or transmission signals in which code may be implemented. A device in which the code implementing the described embodiments of operations is encoded may comprise a computer readable medium or hardware logic. Of course, those skilled in the art will recognize that many modifications may be made to this configuration without departing from the scope of the present invention, and that the article of manufacture may comprise suitable information bearing medium known in the art.