Mathematics: Special Issue "Big Data: Multidimensional Design and Modeling"
Sergio Luján-Mora, Manuel Palomar. Proceedings 2001 International Database Engineering and Applications Symposium (IDEAS 2001), p. 209-218: IEEE Computer Society, Grenoble (France), July 16-18 2001. https://doi.org/10.1109/IDEAS.2001.938087
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 be substituted for the original values. We evaluate four different similarity measures for clustering with and without expansion of abbreviations. The method we propose may work well in practice but it is time-consuming. In order to reduce this problem, we remove stop words for speeding up the clustering.
More information: Reducing Inconsistency in Integrating Data from Different Sources
Information fusion is the process of integration and interpretation of data from different sources in order to derive information of a new quality. Integrating databases into a common repository has become a research topic for many years. Information fusion is a very complex problem, and is relevant in several fields, such as Data Re-engineering, Data Warehouse, Web Information Systems, E-commerce, Scientific Databases, etc. The problem of inconsistency has also lately been a focus of interest in the area of Data warehouses (DW) as a DW is a repository of integrated information from distributed, autonomous, and possibly heteroge-neous. sources.
Traditional search systems work by matching the term that is being searched with the values stored in the corresponding database. If the information contained in databases is inconsistent (i.e., if a given term appears with different values because several denominations exist, or because it is misspelled), a search using a given value will not provide all the available information about the term. On the other hand, DW are used for decision making, and incorrect or misleading data will produce wrong business decisions.
In Figure 1, we present an example to show the aim of our proposal. Let us suppose that we have different databases (particularly, different relational tables) and the sources have different criteria for representing values in affiliation names. For example, with reference to the affiliation of researchers who work at the University of Alicante, we may easily find that there are different values for this university: “Universidad de Alicante” or “Universidad Alicante” (in Spanish) and “Alicante University” (in English).
Data cleaning, also called data cleansing or scrubbing, deals with detecting and removing errors and inconsistencies from data in order to improve the. quality of data . Rahm distinguish between “single-source and multi-source problems and between schema-and instance-related problems” Our paper discusses the problem of the inconsistency found in the values stored in databases (instance level, i.e., data values, not attribute names). We have detected two 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; Section 4 explains the core of our study and details the technical as-pects of our method; Section 5 provides an evaluation of the method; and finally, our conclusions and work in progress 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 eleven causes (lexical discrepancies):
There has been great interest in studying the quality of the information stored in databases for a long time , , , , and diverse methods have been developed for data cleaning , , , , ,  and, in particular, for the reduction of the inconsistency found in databases , , , , .
The method we propose in this paper improves our previous work , ,  that were developed from French's automatic creation of authority files for bibliographical catalogues , . 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 four last causes, which depend on how different the two strings that represent the same term arc. The method that we propose can be divided into six steps  (the improvements presented in this paper affect the second and fourth step):
In this section. technical aspects of our method are de-scribed. We start by introducing a pre-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 pre-processing to obtain better results from’ the clustering. The objective of this preprocessing is to avoid the three first causes of the appearance of different forms for the same term (see Section 2): 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.
For identifying and expanding abbreviations, we use a dictionary of abbreviations to look up an abbreviation and provide an expansion. Obviously, this method is not perfect and it does not avoid getting a wrong answer in ambiguous cases (looking up something that is not really an abbreviation, or not looking up something that is).
Furthermore, the stop words are removed from strings. This is done by comparing the input string with a stop list of words which are to be removed. The list of stop words include closed-class words such as articles, prepositions, con-junctions, etc., together with auxiliary words and common words with little meaning. Obviously, every language has a different stop list.
The Similarity between any two strings must be evalu-ated. There are several similarity measures; in our previous work , , , we have employed 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). In our previos research; we have carried out many experiments and the LD bas-at-tained the worst results. Because. of that, we have only used the remaining similarity measures in the experiments presented in this paper.
The edit distance or Levenshtein distance (LD)  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: insert a character, delete of a character, and substitute a 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 . 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) . It is based on the 'approximate word matching referred to in , . 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 unpaired word 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 Jac-card's coefficient (JC) , 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 Ie 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. Inrelated work , , , the clustering algorithm employed is basically the leader algorithm . This algorithm is chosen as opposed to more elaborate algorithms (e.g., k-means.algorithm, Fisher algorithm) because the more elaborate algorithms 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 and the first clusters are always larger than the Iater ones. This is intrinsic to the 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 Figure 2 resolves the first-clusters-larger problem: it uses a centroid method and the comparison for-every-string is made with all the existinz clusters for the time being.
The algorithm chooses the strings, from greatest to smallest 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 Figure. 2 it depends on one parameter a (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 (this value is used as a quality measure of the centroid):
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 visual checking the obtained clusters and detecting possible errors to correct them (the method achieves successful results, although it does not eliminate the utility of reviewing the clusters ob-tained). In the original database, the strings ora cluster are replaced by its centroid (it represents its cluster). Therefore, almost all variants of a term are put together under a single form.
We have used four files for evaluating our method. They contain data from four different databases with inconsistency problems: files A, B, and D contain information in Spanish, while file C in English. The method has been implemented in C and C++, running in Linux.
TABLE 1 gives a description of these four files. The optimal number of clusters (ONC) indicates the number of handcrafted clusters. The three last columns contain the number of single strings with (W) and without (WO) 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 and without the expansion of abbreviations.
The amount of duplication of a file is measured by the duplication factor (DF) , which indicates how many duplicates (textual or not textual) of each record appear in the file, on the average. Table 2 shows the DF and the standard deviation (SD) of the four files. It also shows the reduction (Red.) of the DF when the abbreviations are expanded.
The DF shows how many duplicates of each record exist, but it does not indicates if the duplicates look like each other or not. 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 for hand-generated clusters of the files A, B, C, and D is shown in Table 2. As the FCI is an average, the table also shows the standard deviation (SD). It is obvious ‘that the clusters of file B are more complex than those’ of files A, C, and D. 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), 7.8% (file B), and 13.5% (file D) as it is shown in Table 1.
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 (ONC):
Here we study the effectiveness of our method on real data. 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 four similarity measures: invariant distance from word position (IDWP), modified IDWP (MIDWP), Jaccard's coefficient (JC); and combined similarity measure (CSM). The result of the experiments using the four files and removing stop words are shown in Tables 3, 4, 5, and 6. The tables show the highest precision rate and the corresponding error obtained in each file without (WO) and with (W) the expansion of abbreviations. The corresponding threshold (α) also appears.
Note that the expansion of abbreviations improves the precision and diminishes the error in all cases (except file C). Besides, the best precision, with a lower error, is obtained at a lower threshold when the abbreviations are expanded.
As you can see in Tables 3, 4, 6 the highest precision is obtained for a threshold between 0.1 and 0.3. However, the JC (Table 5) needs a threshold near 0.5 for the highest precision.
On the other hand, as you can see in Table 6, File A and B obtain the best precision (89.1% and 76.0% respectively) when the CSM with the expansion of abbreviations. is employed. However, as seen in Table 5, File C obtains it (85.9%) when the JC without the expansion of abbreviations is used. Finally, File D obtains the best precision (75.2%) with the MIDWP (Table 4) and the expansion of abbreviations. The similarity measure that produces the best results varies from a file to another.
In Table 7 (column Previous work), we show the highest precision an error obtained in our previous work (without removing stop words) , . The corresponding threshold (α) also appears. The test files A, B, C, and D are the same as in this paper.
Table 7 also summarizes Tables 3, 4, 5, and 6 (column Current work). files A and C have better precision than files Band D because their clusters are less complex (see DF and FCI in Table 2). Surprisingly, removing stop words does not improve clustering quality. Moreover, the precision diminishes even 4 units in some cases.
Figures 3 and 4 compare precision and error obtained in our previous and current work, The left graph in Figure 3 shows the dependency of precision from the threshold (α) for all four files when the combined similarity measure (CSM), with expansion of abbreviations, and without removing stop words is applied (the graph obtained without expansion of abbreviations is very similar to this one). The four curves (files) have a similar shape, with a peak between 0.1 and 0.25.
Figure 3 also shows the effect of varying the threshold (α) in the error, The, right graph compares the error, for all four files when the combined similarity measure (CSM) with expansion of abbreviations is applied. The error is insignificant when the threshold is under 0.15. For a threshold under 0.35, the error is below 15%.
Finally, Figure 4 displays precision (left) and error (right) achieved with' thc combined similarity measure (CSM) and expansion of abbreviations, The shape of these two graphs is very similar to Figure 3: the precision keeps very similar and the error increases slightly for a threshold greater than 0.3. When the results obtained ‘with the other’ similarity measures (IDWP, MIDWP, and JC) are plotted, the graphs also present a similar shape.
The threshold that obtains the best precision is certainly difficult to determine, because it varies from a data set to another one. But Table 7 and Figures 3 and 4 insinuate a value between 0.1 and 0.3.
Table 8 shows a time comparison between previous work (without removing stop words) and current work (removing stop words). Notice that in all cases, removing stop words speeds up the process, because the length of the strings di-minishes. Therefore, there are great time savings in removing stops words with a little impact in precision.
Referential integrity provided by relational database management systems prevents users or applications from entering inconsistent data. Databases with an inadequate design may suffer data redundancy and inconsistency. On the other hand, there is an increasing need to integrate data and provide a uniform view of data. This paper has discussed techniques for improving data quality by using clustering to find different values that refer to the same term and replacing all values in a cluster with a unique form. So, we have presented an automatic method for reducing the inconsistency found in existing databases. Our method clusters strings based on their proximity to the existing clusters: the distance between a cluster and a string is determined as the difference between the centroid of the cluster and the string.
The method. we have proposed achieves successful results with a considerably low error rate, although it does not eliminate the utility of reviewing the clusters obtained. On the other hand, the method is time-consuming. We remove stop words for speeding up the clustering, but the precision only diminishes slightly.
The final number of clusters and the effectiveness of the method strongly depends on the threshold value fixed by the user. The threshold lets the user adjust the behavior of the method: a very small threshold (conservative) will produce a large number of small clusters and a decrease in the number of matching values that should be clustered, meanwhile a very large (aggressive) one will produce a small number of large clusters and an increase in the number of falsely matched values. Based on the data obtained in our research, we propose the use of a threshold between 0.1 and 0.3.
Our first contribution is an algorithm that is domain-independent and language-independent. Previous related work deals with special cases of the field matching problem (customer addresses, census records, bibliographic databases, etc.). The second contribution is the use of two methods for evaluating the similarity between two strings: the invariant distance from word position, derived from the Levenshtein distance, and the combined similarity measure. Last but not least, we present the 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.
Currently, we are working on improving the algorithm in order to cluster the multilingual values. We are applying dictionaries and other techniques relating to natural language processing.
We are also planning to investigate other heterogeneity problems: record matching (merge/purge problem) and schema level conflicts (attribute naming conflicts, format heterogeneity, and so on).
We would like to thank Juan Carlos Trujillo for helpful comments. We also want to thank the anonymous reviewers for their comments which helped us to improve this paper.
More information: Reducing Inconsistency in Integrating Data from Different Sources