Sergio Luján-Mora, Enrique Medina. Proceedings of the 3rd International Conference on Enterprise Information Systems (ICEIS 2001), p. 199-206: ICEIS Press, Setúbal (Portugal), July 7-10 2001.
A data warehouse is a repository of data formed of a collection of data extracted from different and possible heterogeneous sources (e.g., databases or files). One of the main problems in integrating databases into a common repository is the possible inconsistency of the values stored in them, i.e., the very same term may have different values, due to misspelling, a permuted word order, spelling variants and so on. In this paper, we present an automatic method for reducing inconsistency found in existing databases, and thus, improving data quality. All the values that refer to a same term are clustered by measuring their degree of similarity. The clustered values can be assigned to a common value that, in principle, could substitute the original values. Thus, the values are uniformed. The method we propose provides good results with a considerably low error rate.
Keywords: Data cleaning, Data integration, Data warehouses
Data warehouses (DW) are used for the decision support process, which manages huge volumes of data. A DW is a repository of integrated data from distributed, autonomous, and possibly heterogeneous sources (Inmon, 1992).
Data cleaning (cleansing) is the process of removing errors and resolving inconsistencies in source data before loading them into a common repository. The aim of data cleaning, which is especially required when integrating heterogeneous data sources, is improving data quality (Rahm, 2000).
DW are populated by the data flowing from source systems such as operational files and transactional databases. In DW, data cleaning is a major part of the so-called ETL (Extraction, Transformation and Loading) process (Chaudhuri, 1997).
Furthermore, data quality is one of the fundamentals of success in the DW environment. The discovery of incorrect data weakens the end users' confidence in the data even if the unit of data that is incorrect is minimum.
Thus, if the information contained in database instances is inconsistent (i.e., if a given term appears with different values because several denominations exist, or because it is misspelled), it will produce incorrect or misleading results. The erroneous results could lead us to wrong business decisions.
The problem of the inconsistency found in the values stored in databases may have three principal causes:
The remainder of the paper is structured as follows: Section 2 outlines the origin of the problem and the possible causes that give rise to the different variants that appear for the same term; Section 3 introduces our method for reducing inconsistency found in existing databases: identifying similar values concerning the same real world entity; Section 4 explains the core of our study and details the technical aspects of our method; Section 5 provides an evaluation of the method; and finally, our conclusions are presented in Section 6.
After analysing several databases with information both in Spanish and in English, we have noticed that the different values that appear for a given term are due to a combination of the following eight causes:
There has been great interest in studying the quality of the information stored in databases for a long time ((Motro, 1998), (O’Neill, 1988), (O’Neill, 1989)), and diverse methods have been developed for the reduction of the inconsistency found in databases ((Hernández, 1998), (Monge, 1997)).
The method we propose in this paper improves our previous works (Luján-Mora, 2000b) that were developed from French’s automatic creation of authority files for bibliographical catalogues ((French, 1997a), (French, 1997b)). We have added new distances, developed different evaluation measures and employed a different clustering algorithm. These improvements result in a better performance of the method.
Our algorithm resolves all the problems detailed in Section 2, except the fifth and the eighth, which depend on how different the two strings that represent the same term are. The method that we propose can be divided into six steps:
In this section, technical aspects of our method are described. We start by introducing a previous processing for obtaining better results in Section 4.1. Section 4.2 describes how the similarity between two strings is considered. Section 4.3 presents the algorithm itself and finally, Section 4.4 explains the last step of the method, i.e., checking that the obtained clusters are correct.
The strings undergo a previous processing to obtain better results from the clustering. The objective of this processing is to avoid the three first causes of the appearance of different forms for the same term (see Section 2.1.): i.e., accents, lower-case/upper-case and abbreviations. The accents are eliminated, the string is converted to lower-case and the abbreviations are expanded.
The similarity between any two strings must be evaluated. There are several similarity measures; in our research, we employ five measures: Levenshtein distance (LD), invariant distance from word position (IDWP), a modified version of the previous distance (MIDWP), Jaccard’s coefficient (JC), and the minimum of the four previous measures (CSM).
The edit distance or Levenshtein distance (LD) (Levenshtein, 1966) has been traditionally used in approximate-string searching and spelling-error detection and correction. The LD of strings x and y is defined as the minimal number of simple editing operations that are required to transform x into y. The simple editing operations considered are: the insertion of a character, the deletion of a character, and the substitution of one character with another. In our method, we have taken a unitary cost function for all the operations and for all of the characters. The LD of two strings m and n in length, respectively, can be calculated by a dynamic programming algorithm (Hirschberg, 1997). The algorithm requires ?(mn) time and space.
If two strings contain the same words (variant forms of the same term) but with a permuted word order, the LD will not permit their clustering. To solve this problem, we introduce another distance that we call the invariant distance from word position (IDWP) (Luján-Mora, 2000a). It is based on the approximate word matching referred to in (French, 1997b). To calculate the IDWP of two strings, they are broken up into words (we consider a word to be any succession of digits and letters of the Spanish alphabet). The idea is to pair off the words so that the sum of the LD is minimised. If the strings contain different numbers of words, the cost of each word in excess is the length of the word.
We also use a modified IDWP (MIDWP). We add a new matching condition: if two strings fulfil Equation 1, we assume they match perfectly (in that case, we consider their LD is zero).
The last similarity measure we have employed is the Jaccard’s coefficient (JC) (Rijsbergen, 1979), the ratio of the matching words in x and y to all the words in x and y:
where X is the set of words of the string x and Y the set of words of y.
In order to compare the above-mentioned measures, we need the JC subtracted from one (1 – JC). Besides, the LD, IDWP, and MIDWP are divided by the length of the longest string. Thus, all the measures obtain a similarity value from 0 (x and y are the same string) to 1 (x and y are totally different).
Finally, we also combine the four previous similarity measures (combined similarity measure, CSM): we choose the minimum of the four similarity measures for every pair of strings.
The goal of clustering is to find similarity between strings and cluster them together based on a threshold of similarity between the strings.
In previous works ((French, 1997a), (French, 1997b), (Luján-Mora, 2000b)), the clustering algorithm employed is basically the leader algorithm (Hartigan, 1975). This algorithm is chosen as opposed to more elaborate algorithms (e.g. k-means algorithm, Fisher algorithm) because they are slower and the number of clusters is unknown. The leader algorithm is very fast, requiring only one pass through the data, but it has several negative properties: the partition is not invariant under reordering of the cases, the first clusters are always larger than the later ones and the final number of clusters depends on the threshold values. This is due to the very algorithm: the comparison between a new string and the existing clusters is made only until a cluster that meets the condition is found, without considering the possibility that a better value of the criteria is met later, for another cluster.
The clustering algorithm we propose in Table 1 resolves the previous problem: it uses a centroid method and the comparison for every string is made with all the existing clusters for the time being.
The algorithm chooses the strings, from greater to smaller frequency of appearance, since it assumes that the most frequent strings have a greater probability of being correct, and thus, they are taken as being representative of the rest. As seen in Table 1, it depends on one parameter ? (threshold). The algorithm makes one pass through the strings, assigning each string to the cluster whose centroid is closer and close enough (distance between the string and the centroid lower than ?) and making a new cluster for cases that are not close enough to any existing centroid. The distance D is calculated using one of the similarity measures explained in Section 4.2.The centroid of a cluster must be recalculated every time a new string is assigned to the cluster. The centroid is chosen to minimise the sum-of-squares criterion:
where n is the number of strings assigned to the cluster and C is the centroid of the cluster.
The final step of the method consists of checking the obtained clusters and detecting possible errors to correct them. In the original database, the strings of a cluster are replaced by its centroid (it represents its cluster). Therefore, all variants of a term are put together under a single form. Thus, in searches, data calculations and decision processes, final users will be confident that they have located all values relating to the required term.
We have used three files for evaluating our method. They contain data from three different databases with inconsistency problems: files A and B contain information in Spanish, while file C in English.
The method has been implemented in C and C++, running in Linux.
Table 2 gives a description of these three files. The optimal number of clusters (ONC) indicates the number of handcrafted clusters. The three last columns contain the number of single strings (not duplicated) with and without the expansion of abbreviations, and the rate of reduction (on expanding the abbreviations, the number of single strings is reduced, since duplicates are removed). We have done all the tests with (W) and without (WO) expansion of abbreviations.
We have developed a coefficient (consistency index) that permits the evaluation of the complexity of a cluster: the greater the value of the coefficient is, the more different the strings that form the cluster are. A null value indicates that the cluster contains only one string. The consistency index (CI) of a cluster of n strings is defined as:
The file consistency index (FCI) of a file that contains m clusters is defined as the average of the consistency indexes of all the existing clusters in the file:
The FCI of the files A, B and C are shown in Table 3. As the FCI is an average, the table also shows the standard deviation. It is obvious that the clusters of file B are more complex than those of file A and C. In all cases, however, the FCI is reduced when expanding the abbreviations, since the discrepancies between the strings of a given cluster tend to diminish. With respect to file C, the reduction of FCI when the abbreviations are expanded is minimum, because the reduction of strings is not appreciable: only 0.8% versus 38.0% (file A) and 7.8% (file B), as it is shown in Table 2.
We have evaluated the quality of the produced clusters when our method is applied by using four measures that are obtained by comparing the clusters produced by our method with the optimal clusters:
NC and NCC versus Threshold for File A with (W) and without (WO) expansion of abbreviations, using the CSM, are plotted in Figure 1. The expansion of abbreviations diminishes NC and increases NCC.
As we have already mentioned, the clustering algorithm depends on one parameter (?). We have done all the tests on setting its value from 0.0 to 0.599, in 0.001 steps.
We compare the performance of the five similarity measures. The result of the experiments using files A and C are shown in Tables 4, 5, 6 and 7. The tables show the highest precision rate and the corresponding error obtained in each file when the LD, IDWP, MIDWP and JC are used. The corresponding threshold (?) also appears.
Note that the expansion of abbreviations improves the precision and diminishes the error. Moreover, the best precision, with a lower error, is obtained at a lower threshold.
As you can see in Table 6, File A obtains the higher precision (89.1%) when the MIDWP with the expansion of abbreviations is employed. However, as seen in Table 7, File C obtains it (89.4%) when the JC without the expansion of abbreviations is used.
Table 8 shows highest precision and the corresponding error obtained for files A, B, and C when the CSM is employed. Files A and C have better precision than file B because their clusters are less complex: files A and C have a FCI around 0.3, whereas file B has a FCI of 1.7 (WO) and 1.1 (W).
In Table 9, we show the precision and error obtained in our previous works (Luján-Mora, 2000b). The test files A, B and C are the same of this paper. If this table is compared to Table 8, you can see the new method achieves better results: the precision increases and the error keeps very similar values or even diminish.
We compare the effect of the expansion of abbreviations in Figure 2. It shows Precision versus Threshold for File A with (W) and without (WO) expansion of abbreviations using the CSM. It is seen that the expansion of abbreviations produces the maximum precision (90%) at a threshold of 0.15. From a threshold of 0.25, the expansion of abbreviations does not influence the precision as observed in the figure.
Figure 3 shows Precision versus Threshold for File C without expansion of abbreviations using different similarity measures. The JC obtains the maximum value (90%). All the measures, except the JC, have a similar behaviour: they start at the same level (75%), rise until 85% and then plunge until 20%. However, the JC remains steady over 75% for all the threshold values.
Finally, from Figure 4 it can be again seen that the expansion of abbreviations influences the precision at a low threshold, but from a threshold of 0.25, the influence is imperceptible (the behaviour is very similar to Figure 2). Also, note that there is not error when the threshold is lower than 0.15.
In a DW, data is gathered from a variety of different sources. Removing errors and inconsistencies from data being imported into a DW is critical, because incorrect data will have a negative impact on the effective use of this data.
This paper has discussed techniques for improving data quality by clustering different values that refer to the same term and replacing them with a unique form. Therefore, we have presented an automatic method for reducing on the inconsistency found in existing databases. The method we have proposed achieves successful results with a considerably low error rate, although it does no eliminate the need to review the clusters obtained.
The expansion of abbreviations improves on the results in most cases, but we have detected some cases in which it actually makes the results worse. In addition, we have seen that the combined use of four similarity measures (Levenshtein distance, invariant distance from word position, modified IDWP, and Jaccard’s coefficient) normally obtains the best performance.
The final number of clusters strongly depends on the threshold value fixed by the user. A very small threshold (conservative) will produce a large number of small clusters, meanwhile a very large (aggressive) one will produce a small number of large clusters. Based on the data obtained in our research, we propose the use of a threshold between 0.1 and 0.25.
We are currently developing a graphical user interface to allow the user to control the data cleaning activity through parameters and a spreadsheet-like interface. As the proposed method is time-consuming, we are also considering to evaluate the impact of removing stop words (conjunctions, prepositions, articles and so on: words that contain little meaning) both in precision and time.
We would like to thank Juan Carlos Trujillo for helpful comments and support in the final version of the paper.