# Approximate Matching of Textual Domain Attributes for Information Source Integration

Andreas Koeller

Dept. of Computer Science
Montclair State University
1 Normal Ave, Montclair, NJ, USA
koellera@mail.montclair.edu

Vinay Keelara

Dept. of Computer Science
Montclair State University
1 Normal Ave, Montclair, NJ, USA
vinay_keelara@yahoo.com

## ABSTRACT

A key problem in the integration of information sources is the identification of related attributes or objects across independent sources. Inferring such meta-information from source data (rather than a-priori available meta-data, such as attribute names) is sometimes possible. For example, existing algorithms attempt to integrate information sources by finding patterns such as Inclusion Dependencies (INDs) across them. However, INDs are based on exact set inclusion and are thus very strict patterns that rarely hold across independent real-world databases.

We propose two error-tolerant measures, termed Similarity Score and Distribution Score, that help identify related attributes across two independent databases, based on similarities in their data. Those measures specifically address the problem of identifying semantic relationships between textual attributes of databases that have few or no equal values.

We also present implementations of those measures and some experimental results.

## 1. INTRODUCTION

The explosion in the number of data sources on the web and the proliferation of a wide variety of diverse databases has demonstrated the wide variations in the representation of real world entities across data sources. These variations or discrepancies in the representation of the same or related real world entities can arise from the different formats used to store the data, differences in syntax, differences in schema or just the autonomy of the sources of information (and the fact that data is entered by humans).

In any large organization, different parts of the organization may use different systems to produce and store their data. This may be because of lack of co-ordination, different rates of adopting new technology or because of mergers and acquisitions, in which the new organization inherits the data of the original entities. It will now have to ac-

cess information from multiple original data sets as well as consolidate them so as to eliminate duplication. However the original data sets may not be immediately compatible with each other because the data may be stored in different DBMS, in different formats and schemas.

Many organizations now also collect or correlate their data from autonomous sources within the organization as well as from external sources, to perform data warehousing, mining and statistical analysis. All these applications rely on correct information about database relationships to perform their tasks.

Correlations between the data are typically based on common domains or ontologies or existence of a global domain across the sources. If such meta information is lacking, incomplete, or wrong, it can help to detect relationships between sources from the source data, rather than schema. While schema-based matching is performed semi-automatically, and significant human input is often necessary, data comparisons have the potential to be executed entirely by algorithms, leading to increased efficiency and potentially new applications in the area of data integration.

This paper addresses the issue of comparing two independent databases (i.e., collections of data objects, each of which has a number of attributes), and discovering sets of related attributes between them. The approach takes into account that data is rarely perfect, that data objects representing the same real-world entity usually do not have equal values, and also tolerates missing or faulty data. It relies on the assumption that data is primarily stored in textual form and that related data objects show at least some textual similarity. At the basic level, it makes use of the well-known TF-IDF score for text comparisons, integrating this score into the novel measures of Similarity Score and Distribution Score. While the first score measures relatedness between attributes without duplicates, the second score explicitly takes duplicate values in attributes into account. In combination, the two scores give a measure of relatedness of attributes, in the sense that a high Similarity (or Distribution) Score between two attributes suggests that those two attributes likely refer to the same real-world entity type.

Furthermore, our scores are defined on sets of attributes, which enables us to compare entire relations and identify sets of related attributes between them. This procedure is akin to the process of inferring functional dependencies [2] or inclusion dependencies [5] solely from database data, but goes beyond those exact patterns. Instead, our scores give degrees of confidence in the relationship between attributes,

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA
Copyright 2005 ACM 1-59593-160-0/05/06 ...$5.00.
making them appropriate for real-world, noisy data.

This paper is organized as follows: Section 2 reviews background material on the related concept of inclusion dependencies, as well as the TF-IDF text comparison metric. Section 3 defines the Similarity and Distribution Scores for pairs of individual attributes and also introduces an algorithm to apply those scores to sets of attributes. Section 4 gives a very brief algorithmic analysis, and Section 5 provides some experimental results on effectiveness of our scores and the efficiency of their computation. Section 6 reviews related work and Section 7 gives conclusions and outlook.

# 2. BACKGROUND

## 2.1 Schema Matching

Schema matching, that is the identification of semantically related schema elements across independent databases, is an important task that should be automated as much as possible. Two basic approaches exist [22]. In *schema-only matching*, database fields related to each other are identified based only on the schema of the data sources considered. This matching may be implemented for example through linguistic means on schema element names or through constraint matching (e.g., in the ARTEMIS/MOMIS project [3]). In the second approach, *instance-based matching*, one considers the properties of the data contained in the database fields to conclude that two fields are related. Some important instance-based matching projects are SemInt [19] and LSD [10]. Some recent works in database integration involve a combination of both schema level and instance level matching. The *Corpus-based schema matcher* [12] incorporates this approach. A paper by Kang and Naughton [14] proposes an approach at instance-based matching measuring entropy and mutual information across attributes.

A promising direction for instance-based matching is the discovery of *Inclusion Dependencies* (INDs) between databases [16, 9].

DEFINITION 1 (INCLUSION DEPENDENCY). Assume two relations *R* and *S*. An Inclusion Dependency is a rule of the form

$$R[\bar{X}] \subseteq S[\bar{Y}]$$

between a set $\bar{X}$ of attributes from *R* and a set $\bar{Y}$ of attributes from *S*, with $|\bar{X}| = |\bar{Y}|$ (i.e., with the same number of attributes in each set).

If an inclusion dependency (IND) of substantial size is true between two tables *R* and *S*, those relations can be considered related to each other. INDs represent subset-patterns across relations <fnref n="1" />, which might span multiple attributes. For example, a foreign key constraint between two relations implies an inclusion dependency between the key and foreign key attributes. However, INDs represent *exact* subsets across two relations and are unlikely to be true in real-world data integration scenarios. INDs cannot model slight variations in the representation of data or data extents that overlap only partially.

IND discovery algorithms [16, 9] usually work bottom-up, first discovering INDs between individual attributes, then

between pairs of attributes, and so on. While basic levelwise algorithms akin to the *A-priori* strategy used in association rule mining have been proposed [8], the problem's exponential nature requires more complex algorithms [16, 9] as well as heuristic approaches [17]. In general, the discovery of IND (and other) relationships by comparing the values of the fields of the database is a very complex process, and the problem is NP-hard as a function of the number of attributes in the two relations (since there are $2^k$ possibly related sets of attributes between two relations with *k* attributes) [5].

While INDs are defined mainly for relational databases, the concepts apply to all data models that have the basic concept of *attribute*.

## 2.2 Approximate Matching of Textual Data

<table><caption>Table R</caption><thead><tr><th>X1</th><th>X2</th></tr></thead><tbody><tr><td>SQL Server</td><td>Microsoft Labs</td></tr><tr><td>Office</td><td>Microsoft Marketing</td></tr><tr><td>Magic Broom</td><td>American Inc Marketing Research Labs</td></tr><tr><td>Telephone</td><td>ATT Inc</td></tr><tr><td>Pentium</td><td>Intel Research Labs</td></tr><tr><td>Wireless Mouse</td><td>Microsoft Inc</td></tr><tr><td>Relational DB</td><td>Oracle Labs</td></tr><tr><td>Free Phone Plan</td><td>SBC Inc and SBC Telecom</td></tr><tr><td>Personal Computer</td><td>IBM Research and Marketing</td></tr><tr><td>Passenger Airplane</td><td>Boeing Inc</td></tr><tr><td>Wireless Phone</td><td>ATT Research and ATT Telecom</td></tr></tbody></table>

<table><caption>Table S</caption><thead><tr><th>Y1</th><th>Y2</th></tr></thead><tbody><tr><td>Wireless Telephone</td><td>ATT Telecom Research</td></tr><tr><td>SQL Server DB</td><td>Microsoft Research</td></tr><tr><td>The Pentium Processor</td><td>Intel Research Facilities</td></tr><tr><td>DB Technology</td><td>Oracle Research Labs</td></tr><tr><td>DB Technology</td><td>Foxpro International Inc</td></tr><tr><td>The Magic Broom</td><td>American Marketing Research</td></tr><tr><td>Almost Free Phone Plan</td><td>SBC Telecom and Labs</td></tr><tr><td>Calculator Technology</td><td>Texas Instruments Labs</td></tr><tr><td>Airplane</td><td>Boeing Corp</td></tr><tr><td>Personal Computer Technology</td><td>IBM Inc Marketing</td></tr><tr><td>Broom</td><td>American Marketing Research</td></tr></tbody></table>

<caption>Figure 1: Two tables with Related Data</caption>

To motivate the need for a relaxation of the strict Inclusion Dependency idea, consider two attributes from two different relations, as shown in Fig. 1.

Even though neither of these two sets is a subset of the other, the data in the first table is clearly related to the data in the second table when matching attribute $X1$ to $Y1$ and $X2$ to $Y2$, i.e., $R[X1, X2] \approx S[Y1, Y2]$. Algorithms trying to find inclusion dependencies across such databases [16, 9] will fail to detect relationships in this case.

To approach this problem, we adapt results from the Information Retrieval domain. A useful tool from that domain to measure similarity between texts is the TF-IDF (Term Frequency/Inverse Document Frequency) metric [23].

<footnote n="1">¹Note that INDs are not symmetric, i.e., $R[\bar{X}] \subseteq S[\bar{Y}]$ does not imply $S[\bar{Y}] \subseteq R[\bar{X}]$</footnote>
This metric is defined on a collection of documents, each of which consists of words. In the relational database domain, documents correspond to individual values in a relational attribute. This metric would then apply primarily to attributes in textual domains, whose values can be broken down into words.

The TF-IDF metric defines a distance between individual strings based on the frequency of their words within the string and within the collection of documents (values) in the database [6]. Let C be a collection of documents (corresponding to an attribute in the database domain), and T the dictionary of C (i.e., the union of all words used in all documents of C). Then, for each word $t \in T$, we define $C_t$ to be the subset of C whose documents (values) contain the word t. For each document $c \in C$, we also define a corresponding document vector $v_c \in \mathbb{R}^{|T|}$, whose components $v_{c,t}$ each correspond to a term $t \in T$. Then, with $TF_{c,t}$ as the count of t in c and $IDF_t = \frac{|C_t|}{|C|}$, the TF-IDF score of a component $v_{c,t} \in v_c$ can be defined [6] as

$$v_{c,t} = \begin{cases} (\log(TF_{c,t}) + 1) \cdot \log(IDF_t) & \text{if } TF_{c,t} \ge 1 \\ 0 & \text{otherwise.} \end{cases}$$

Each vector $v_c$ formed from such components is then normalized to unit length. The TF-IDF distance between two documents $c_1$ and $c_2$ is now defined as the dot-product² between the corresponding unit-length document vectors

$$\delta(c_1, c_2) = v_{c_1} \cdot v_{c_2}.$$

The intuition behind this definition is that the angle between two vectors (whose cosine is computed by the dot product) is a measure of similarity between documents. Lower angles (i.e., higher TF-IDF values) mean higher similarity. This metric emphasizes common words between the documents, and similarities in the relative frequencies of such words. Furthermore, due to the IDF component in the IF-IDF score, it weighs rare terms more heavily than frequent terms. This is justified since so-called function words (prepositions, articles, conjunctions) usually carry less "meaning" than the less frequent nouns and verbs. Similar documents therefore are those that share many important terms. Two more observations are that documents with distinct sets of words are considered unequal (since their vectors' dot-product is 0) and that the order of the words in the documents is ignored.

# 3. DISCOVERING DATABASE SIMILARITIES

In this work, we combine the idea of database integration through instance matching with the idea of textual similarity metrics to define measures and algorithms for the integration of databases with textual attributes.

## 3.1 Measuring Similarity of Attributes

In our approach to integration of heterogeneous databases, we assume that many domains describing real world entity types in databases are natural language text. Taking this further, we see that any textual data within the relations of the database can be seen as a set of individual name

$$^2\bar{a} \cdot \bar{b} = \sum_{0 \le i < |a|} a_i b_i \quad \text{for unit length vectors.}$$

constants (also represented in natural language text) which correspond to entities in the real world.

In this scenario, only in very rare cases can we rely on the equality of tuples or attributes to identify similar relations. Therefore, we relax the requirement of value equality and now define the concept of similarity as follows.

**DEFINITION 2 (SIMILARITY).** Assume two relations R and S. The similarity of two tuples $x \in R$ and $y \in S$ is a measure of confidence in the co-reference between them. Two tuples are said to be co-referent if they refer to or are mapped from the same real world entity. We denote similarity of two tuples x and y by $sim(x, y)$, with $0 \le sim(x, y) \le 1$. A similarity of 1 means certain co-reference, whereas a similarity of 0 means unrelated semantics of x and y. For a given threshold c, x and y are called similar if $sim(x, y) > c$, denoted by $x \approx y$.

Determining co-reference simply from data is not always possible, since textual data typically does not carry enough information to decide co-reference (i.e., while "AT&T Research" is probably co-referent with "AT&T Labs", the values "Microsoft Research" and "Microsoft Office" certainly are not co-referent).

In this paper, we use the TF-IDF score for two documents as the similarity score for two tuples.

**DEFINITION 3 ((VALUE) SIMILARITY SCORE).** Assume two attributes X and Y across two databases. The similarity score between two values $x \in X$ and $y \in Y$ is defined as

$$\mathrm{sim}(x, y) \equiv \delta(x, y)$$

The document collection as used in the TF-IDF score is defined as the concatenation of X and Y, i.e., as a (multi)set containing all values of X and all values of Y, possibly with duplicates. In particular, the size of the document collection C is $|C| = |X| + |Y|$. The dictionary T is defined by all distinct terms in all values in C.

We now extend the notion of similarity to attributes:

**DEFINITION 4 (ATTRIBUTE SIMILARITY).** Assume two relations R and S. The similarity between an attribute X from R and an attribute Y from S is a measure of confidence in the co-reference between them. Analogously to value similarity, we denote attribute similarity by $sim(X, Y)$, with $0 \le sim(X, Y) \le 1$.

We now discuss meaningful ways of computing attribute similarity, i.e., establishing a similarity measure that predicts co-reference of attributes.

## 3.2 Computing Attribute Similarity through Value Similarity

In order to compute attribute similarity, we combine individual value similarity scores. We begin by defining a vector carrying information about attribute similarity, using value similarity as defined above.

**DEFINITION 5 (ATTRIBUTE SIMILARITY VECTOR).** Assume two attributes X and Y from two relations R and S. Without loss of generality, furthermore assume that $|R| \le |S|$. Temporarily fix some order of the tuples in X, for example $x_0, x_1, \dots, x_{|R|-1}$.
<figure><img src="image_66.png" /><figcaption>Figure 2: Similar attributes with different degrees of relatedness</figcaption></figure>

The components of the attribute similarity vector $V_{X,Y} \in \mathbb{R}^{|R|}$ are then defined as $v_i = \max_{y \in Y}(\text{sim}(x_i, y))$ with $0 \le i < |R|$. That is, for each value (tuple) in attribute X, the vector contains the best (highest) similarity score with any value (tuple) in Y.

Note that all components of this vector are numbers between 0 and 1. A simple measure for attribute similarity can now easily be defined as the average value of the attribute similarity vector's components:

**DEFINITION 6 (SIMILARITY SCORE).** The similarity between two attributes X and Y is defined as

$$ \text{sim}(X, Y) = \frac{\sum_{v \in V_{X,Y}} v}{\dim(V_{X,Y})} $$

where $\dim(V)$ is the number of components in vector V.

**Example** With the data as given in Fig. 1, the similarity scores between each pair of attributes are:

<table><thead><tr><th></th><th>X1</th><th>X2</th><th>Y1</th><th>Y2</th></tr></thead><tbody><tr><th>X1</th><td>1</td><td>0</td><td>0.591</td><td>0</td></tr><tr><th>X2</th><td></td><td>1</td><td>0</td><td>0.712</td></tr><tr><th>Y1</th><td></td><td></td><td>1</td><td>0</td></tr><tr><th>Y2</th><td></td><td></td><td></td><td>1</td></tr></tbody></table>

This table gives the values for $\text{sim}(X, Y)$ where the attribute X is taken from the smaller relation compared to attribute Y, as required in the definition. □

In the absence of duplicate values in the attributes compared, the similarity score gives a good first indication of the attributes' relatedness.

## 3.3 Relationships between Non-Key Attributes

This paper focuses on inclusion-dependency-like approximate relationships between databases. Such patterns often include individual attribute pairs with duplicate values. Consider the example in Fig. 2.

While both A and B are subsets of the attribute C (in the “relational” sense of the term subset, i.e, after removal of duplicates), intuitively, attribute B, rather than attribute A, has a greater degree of similarity with attribute C. For example, the fact that in attribute B company names repeat but in attribute A there are no duplicates probably means they are used in different contexts (and therefore have different semantics). However, the similarity score as defined

above will not capture this difference as is it 1 for all pairings of attributes A, B, and C.

The higher similarity of A to C can be captured by comparing the *value distributions* of the attributes, rather than simply comparing their values. Therefore, we define the concept of *Approximate Bag Inclusion* for attributes, based on the principles of bag (multi-set) semantics [1]. The concept of set membership is extended in bag semantics to *element multiplicities*, denoted by $\mu$. For example, in the multi-set $A = \{1, 1, 2, 3\}$, $\mu(A, 1) = 2$ and $\mu(A, 5) = 0$. Set membership is naturally defined as $a \in A \iff \mu(A, a) \ge 1$. A bag A is included in a bag B if $\forall a \in A: \mu(A, a) \le \mu(B, a)$.

We adapt this definition to our domain of approximate attribute matching to obtain a *Distribution Score* for the comparison of attributes containing duplicates, based on their value distribution.

First, we define an *approximate multiplicity* accounting for the fact that we do not expect to find exact inclusion of tuples across our source relations, followed by the definition of a distance measure between such attributes.

**DEFINITION 7 (APPROXIMATE MULTIPLICITY).** Assume an attribute X from relation R, an attribute Y from relation S, and a tuple x ∈ X. R and S could be the same relation and X and Y could be the same attribute. The approximate multiplicity of x in Y, denoted by $\tilde{\mu}(Y, x)$ is then defined as the number of tuples y ∈ Y for which $\text{sim}(x, y) \ge c$, with c some constant between 0 and 1.

In our experiments, we empirically found appropriate values of the similarity parameter c to be 0.95 if $X \neq Y$ and 0.995 if $X = Y$, reflecting the expectation that values within the same relation are more likely to be identical if they are co-referent, since they are controlled by the same data entry process.

Rather than counting exact duplicates, this method identifies a number of tuples in attribute Y that are similar to a given tuple x from an attribute X. If $X = Y$, the number of similar tuples to a given x in its own attribute is computed. Recall that when computing TF-IDF scores across attributes in distinct relations R and S, the dictionary T of terms is the union of the individual dictionaries, and the document collection C is the concatenation of the two attributes.

This definition of multiplicity is heuristic and does not imply an exact classification. In particular, clusters of “similar tuples” can overlap, i.e., tuples can be part of multiple clusters, such that the sum of all multiplicities of tuples in a relation could be substantially higher than the number of tuples in that relation.

**DEFINITION 8 (ATTRIBUTE DISTRIBUTION VECTOR).** Assume two attributes X and Y from two relations R and S. Without loss of generality, furthermore assume that $|R| \le |S|$. Temporarily fix some order of the tuples in X, for example $x_0, x_1, \dots, x_{|R|-1}$.

Now, for each $x_i \in X$ use the value similarity scores to compute $\max_{y \in Y}(\text{sim}(x_i, y))$ and record the tuple $y \in Y$ for which this maximum was obtained. In the case of duplicate tuples y with the maximum score, use a random such tuple.

The components of the attribute distribution vector $D_{X,Y} \in \mathbb{R}^{|R|}$ are then defined as

$$ d_i = \begin{cases} \frac{\tilde{\mu}(X, x_i)}{\tilde{\mu}(Y, x_i)} & \text{if } \tilde{\mu}(X, x_i) \le \tilde{\mu}(Y, x_i) \\ 0 & \text{otherwise} \end{cases} $$
That is, the distribution score reflects how many duplicates of a value exist in one attribute, relative to the duplicates of its best-matching related value in another attribute. With this definition, the components of the distribution vector are between 0 and 1, and are higher if the multiplicity of a tuple in relation *R* approaches the multiplicity of the corresponding tuple in *S* (if there is any). If the multiplicity of a tuple in *R* exceeds the multiplicity of its corresponding tuple or if there is no corresponding tuple, the value of the component is 0. This definition reflects the traditional definition of “bag inclusion” (which we use as an analogy to Inclusion Dependencies) and also captures the notion that similar value distributions suggest a higher degree of similarity (i.e., more evidence for co-reference) between attributes than distinct counts. Note that for any *x*<sub>*i*</sub> that has duplicates in *X*, the corresponding value *d*<sub>*i*</sub> appears multiple times in *D*<sub>*X*,*Y*</sub>.

We now use this distribution vector to define a distribution score:

DEFINITION 9 (DISTRIBUTION SCORE). The distribution score between two attributes X and Y is defined as

$$ \text{dis}(X, Y) = \frac{\sum_{v \in D_{X,Y}} v}{\dim(D_{X,Y})} $$

where $\dim(V)$ is the number of components in vector V.

Note that with this definition, the fact that frequent values $x_i$ from *X* are represented multiple times in $D_{X,Y}$ gives higher weight to those values in the distribution score. This is meaningful since values that appear often in a non-key attribute are probably more important to that attribute, such that their impact on the total score should be higher.

*Example In the data from Fig. 2, similarity scores across each pair of columns are all 1, since the basic data values are identical. The distribution scores are as follows:*

<table><thead><tr><th></th><th>A</th><th>B</th><th>C</th></tr></thead><tbody><tr><th>A</th><td>1</td><td>3/4</td><td>3/4</td></tr><tr><th>B</th><td></td><td>1</td><td>1</td></tr><tr><th>C</th><td></td><td></td><td>1</td></tr></tbody></table>

*Those scores suggest that attributes B and C are closely related, while attribute A is not as closely related to either B or C. □*

Analogously to the definition of the similarity score, a high distribution score between two attributes (i.e., close to 1) suggests high confidence in co-reference between them.

## 3.4 Discovery across Multiple Attributes

The similarity score and distribution score can be used to estimate the probability that two attributes across two relations are *co-referent*, i.e., refer to the same real-world entity. However, if comparing entire relations, each with multiple attributes, it is also interesting to determine whether there are *sets* of attributes across the relations that are *co-referent*. This notion is also inspired by the Inclusion Dependency concept.

The process of discovering multi-attribute relationships between two relations *R* and *S* is carried out in two phases. In the *first phase* we exhaustively compare single attributes from each relation using similarity scores and distribution scores. Analogously to the procedure determining Attribute

Distribution Vectors, we compute distribution scores for each pair of attributes and for each attribute *X* from *R* find the attribute *Y* in *S* with the highest distribution score relative to *X*.

We then attempt to merge the individual attributes to form multi-attribute patterns. For example, when merging two attributes $X_1$ and $X_2$ from *R*, for each tuple $t \in R$, we “union” the (textual domain) values $t[X_1]$ and $t[X_2]$, obtaining a new, virtual attribute $X_{1,2}$. We merge the corresponding attributes in *S* and then compute the distribution score between those two new attributes.

Note that due to the way the TF-IDF scores are defined, we can incrementally compute the TF-IDF scores of the merged attribute values from the TF-IDF scores of the individual values, without the need for new database queries.

We merge attributes in decreasing order of their individual distribution scores, stopping when the distribution score of the merged set of attributes falls below a threshold.

Note that this is a greedy algorithm, which does not guarantee an optimal solution. However, this simple strategy showed very good results in our experiments.

# 4. ALGORITHMIC ANALYSIS

A simple algorithmic analysis follows. Assume two relations *R* and *S*, with *att*<sub>*R*</sub> and *att*<sub>*S*</sub> the number of attributes in *R* and *S*, respectively. Furthermore, let *T* be the dictionary of all terms in the union of all (textual domain) attributes in *R* and *S*.

The most time-consuming procedures are the computation of TF-IDF scores, which requires accessing each tuple in each table once, and computation of the similarity and distribution scores, which compares each tuple in *R* with each tuple in *S*. Each individual comparison of two tuples requires multiplying their TF-IDF vectors. While those vectors are conceptually very long (they have $|T|$ elements), they are also very sparse (since each individual document contains only a fraction of all dictionary words), such that time- and space-efficient storage is possible, for example by only storing non-zero components of the vectors. We may assume an average *k* for the number of distinct words in a value in a relation.

The time complexity for computing individual similarity and distribution scores is then in $O(k \cdot |R| \cdot |S|)$, while the algorithm to compare two entire relations runs in $O(k \cdot att_R \cdot att_S \cdot |R| \cdot |S|)$.

The largest data structures in this environment are the arrays storing individual TF-IDF scores. Their unoptimized size is $|R| \cdot |T|$ and $|S| \cdot |T|$ floating point values, respectively, although as mentioned above, those are sparse arrays and sparse matrix storage can be used. Our algorithms in their current form rely on the ability to store those structures in memory.

# 5. EXPERIMENTS

## 5.1 Experimental Setup

Algorithms to compute the Similarity Score and Distribution Score were implemented in Java over relational databases. The testing environment for all our experiments consisted of two machines; one 2.5-GHz Pentium-4 Windows based machine with 2 GB memory running Java 1.4.2 and one 4 Processor 1.2-MHz Sun Fire 880 system with 8 GB
memory running various relational database servers.

Test data was obtained from the UC Irvine KDD Archive (kdd.ics.uci.edu), and the US Census 2000 archives (ftp://ftp2.census.gov/census_2000/datasets). The datasets (converted into relational tables) are:

**Movies:** This dataset contains a list of movie names. There is information on actors, casts, directors, rating and remakes etc. Outside of the key fields, missing values and duplicates are common in this dataset. We have used different projections of this relation, to carry out our experiments.

**Census:** This dataset contains a variety of census data. It consists of about a 1000 tuples and 41 attributes. The dataset is mainly used to test the performance of the algorithms.

From these datasets we generated overlapping subsets, partly through random sampling and partly through selections.

## 5.2 Experiment 1: Behavior of Distribution Score—Effect of Non-distinct Values

The purpose of this experiment is to determine the effect that non-distinct values (duplicates) in a relation have on the behavior of the distribution score. The average distribution scores obtained in each case will determine whether two relations can be integrated. The algorithm is run on two relations R and S, derived from the Movies dataset. R consists of movie names. For each tuple in R, there is exactly one tuple in S that shares all “meaningful” terms (i.e. terms with high TF-IDF scores), but has a few additional “functional words” (i.e. terms with low TF-IDF scores). The three cases considered are

* All the values in the two relations are distinct.

* There are a few tuples with a random number of duplicates.

* There are very few distinct tuples, with each distinct tuple having a large number of duplicates.

In each of the cases we generate a subset of the relation R, denoted by $R'$, through sampling. The size of the subset $R'$ varied from 100% to 5% of the original relation. This procedure ensures that the *similarity scores* for each of the following experiments are exactly 1.

**Case 1:** The results of the initial case, where all the values are distinct, are shown in Fig. 3. Since every value of the original Movies relation does exist in relation S, it is detected as a good approximate match by the similarity algorithm despite the presence of other function words. Furthermore, every tuple present in relation R and relation S is distinct, i.e., they have no duplicates. Recall that the distribution score measures the number of duplicates for each tuple in R vs the number of duplicates for the “best matching” tuple in S (see Sec. 3.3). Hence, no matter what the sample size or the tuples present in R, the distribution scores for all the tuples will always be equal to 1. Consequently, the distribution score for the entire relation (the average of the individual distribution scores) will also always be equal to 1. We can then conclude that when all the tuples in a relation are distinct, a high similarity score alone is sufficient to detect the inclusion between the two relations.

**Case 2:** In this experiment, we wanted to verify the hypothesis that distribution score more accurately measures

<figure><img src="image_67.png" /><figcaption>Figure 3: Distribution Scores for relations with no duplicate tuples</figcaption></figure>

“integrability” than similarity score. For this purpose we create a table S with many duplicates and randomly sampled a table R from it. We expect that even if R is small the similarity score will still be high (since all tuples in R still have matches in S), but that the distribution score decreases since the number of duplicates in R now differs from the number of duplicates in S.

The distribution scores of the all tuples without duplicates in R will always be equal to 1 in all the samples, however the distribution scores of the non-distinct tuples will be less than 1 since they now have fewer duplicates of each tuple. Hence the distribution scores of these tuples will tend to decrease as the sample size decreases.

<figure><img src="image_68.png" /><figcaption>Figure 4: Distribution Scores for relations with the presence of duplicate tuples</figcaption></figure>

As seen in Fig. 4, the distribution score for the entire relation tends to decrease gradually as the sample size decreases, until a certain sample size is reached (sample size of about 35% for the dataset considered). At this point the scores start to decrease sharply. This is because of two reasons. The sample sizes are now so small that it is less likely that distinct tuples from the original relation (which would produce distribution scores of 1) are included in R. The small sample sizes also mean that non-distinct tuples of S that
are included in *R* have very few or no duplicates within the sample, leading to lower scores.

This illustrates the fact that even though as in the previous case, every tuple of any sample of *S*, i.e. any *r* ∈ *R*, will have a good approximate match in *S*, this alone will not give us a good indication of whether the relations can be integrated, since the attributes' value distributions may be different. The use of the distribution score helps in determining if the attributes may be co-referent.

*Case 3:* In this instance the relations *S* are formed by a projection on the Rating attribute of the Movies dataset (a textual domain attribute), and relation *R* is obtained by randomly sampling it. There are only four distinct tuples in the relations, with a large number of duplicates for each tuple. This experiment has been carried out to further emphasize the differences between the results of the similarity score and the distribution score.

<figure><img src="image_69.png" /><figcaption>**Figure 5:** Comparison of Distribution and Similarity scores for relations with low number of distinct tuples.</figcaption></figure>

The results for different samples on relation *R* are depicted in Fig. 5. Since every value of relation *R* exists in relation *S*, all the tuples in any subset of *R* of any size will always have a good similarity score. However, the distribution scores decrease steadily as the sample size decreases, because the subsets of *R* will show value distributions less and less similar, with respect to relation *S*. We see that samples *R'* of a sample size of 50% of *S* or less are no longer considered co-referent by our measure, since the distribution of values in relation *R'* no longer matches the distribution in *S*. This is not reflected by the similarity score at all.

## 5.3 Experiment 2: Behavior of the Distribution Score in the Presence of Noise due to Unrelated Tuples.

In this experiment we verify the hypothesis that the Distribution Score tolerates noise produced by tuples that do not find good approximate matches, i.e. tuples with low score in the Similarity Score Vector, much better than existing algorithms.

For this experiment we created a relation *R* from the Movies dataset. The relation *S* is obtained by removing the desired percentage of tuples from *R* for each of the test cases considered, ensuring that not all tuples in the “smaller” relation

find matches in the “larger” relation *S*. The comparison is then carried out between a subset sampled from *R*, denoted by *R'*, and relation *S*.

<figure><img src="image_70.png" /><figcaption>**Figure 6:** Effect of noise produced by unrelated tuples</figcaption></figure>

We have considered four test cases. In the initial test (*Test 1*), about 10% of the values in *R* do not find good approximate matches in relation *S*. This number is progressively increased with each test. In *Test 2* 15%, in *Test 3* 20% and finally in *Test 4* almost 50% of the tuples in *R* do not find matches in relation *S*. The experiments are performed on subsets of *R* of varying sample sizes in each of the test cases.

We see from results shown in Fig. 6 that the Distribution Score is still high (close to 1), indicating co-reference (and thus “integrability”) of the two relations at 10% noise level. As we increase the noise level to 15% and then 20% although the distribution scores decrease correspondingly, the scores are still high enough for the two relations to be considered related. However at 50% noise level there is a significant drop in the distribution scores as indicated by plot for *Test 4* compared to the score obtained for 10% noise level in *Test 1*. Hence at a 50% noise level the relations can no longer be considered related.

This supports our hypothesis that the Distribution Score helps to identify related attributes in noisy relations. As seen from the results of the experiment it detects relationships among database relations at noise levels of up to 20%. Recall here that there is no need for a single tuple to exist in both relations, since TF-IDF scores are used for all comparisons. Rather, the algorithm is tolerant to non-matching data values that have *high* relative TF-IDF scores, as well as to noisy data, i.e., tuples in *R* that do not even have high TF-IDF scores with any data in *S*.

The distribution score drops (i.e., suggests lack of co-reference) only at noise levels of almost 50%. This also represents a successful application of the measure, since a very high number of mismatches between the tuples of two relations may indicate that the relations are mapping different real world entities and hence cannot be integrated.

## 5.4 Experiment 3: Effect of Data Size on Performance

This experiment has been performed to study the relationship between the sizes of the relations considered and the performance of the similarity detection algorithm developed in the dissertation. The experiments have been carried
out in two phases, corresponding to the two phases of multi-attribute pattern discovery outlined in Sec. 3.4. In the first phase we test the performance of the algorithm by varying the tuple sizes of the relations considered. In the second phase the performance of the algorithm is tested by varying number of attributes in the underlying relations.

We have used a projection on a single attribute of the Census dataset to experiment on the first phase (i.e., single attribute comparison). This relation has twenty distinct values. The subsets and superset of this relation were formed by sampling and duplicating the values of the original projection. The results are as shown in Fig. 7.

<figure><img src="image_71.png" /><figcaption>**Figure 7:** Complexity of Distribution Algorithm with respect to the Number of tuples in the relations</figcaption></figure>

In the dataset considered the number of unique terms in both the relations are constant. Fig. 7 shows that the runtime of the algorithm increases as a quadratic function of sizes of the relations considered ($r^2$ = 0.9988). We increase the sizes of both $|R|$ and $|S|$ by the same ratio to obtain each data point. Since an increase in the size of the relations means an increase in the number of tuples in both the underlying relations, we can conclude that the runtime of the algorithm increases as a linear function of the number of tuples in each of the two individual underlying relations, i.e., as a quadratic function of the sum of the relation sizes.

In implementing the second phase of the discovery (merging attribute for discovery of multi-attribute relationships) we have used subsets formed by projections on the Census dataset. This dataset originally has 41 attributes. The number of attributes considered therefore varies from 1 to 41. The number of tuples in the dataset is 1000 and remains a constant in all the subsets. The results of the experiment are shown in Fig. 8.

Again, the increase in the runtime of the algorithm vs the increase in the size of the relations follows an almost quadratic function ($r^2$ = 0.9581). Since an increase in the size of the relations now means an increase in the number of attributes in both the underlying relations, we can conclude that the runtime of the algorithm increases as a linear function of the number of attributes in each of the two individual underlying relations. The curve is not perfectly quadratic, and the correlation is weaker than in the previous case because of the effect the number of distinct terms has on the runtime. In the dataset considered, the number of distinct

terms is not a constant.

<figure><img src="image_72.png" /><figcaption>**Figure 8:** Complexity of Distribution Algorithm with respect to the Number of Attributes in the relations</figcaption></figure>

## 6. RELATED WORK

The integration of heterogeneous databases is essential in the face of the wide variety of diverse databases currently being used. The problem of finding patterns in databases, and the problem of integrating databases through discovery of schema mappings have both been widely studied [3, 19, 10, 12].

A prominent example for an schema-based matching project is Artemis/MOMIS [3], which attempts to integrate schemas based on attribute name equality, related attribute domains, attribute name synonyms and hypernyms in a schema element hierarchy, and matching of schema sub-structures.

The LSD project [10] integrates a number of different techniques for the discovery of related schema elements. Among those techniques are attribute name similarity measures and instance-driven technique based on attribute or domain values. The LSD project does use a WHIRL-based [6] nearest-neighbor metric for attribute values which, like our Similarity scores, also builds upon the IF-IDF scores. However in LSD, this metric is implemented through a machine-learning algorithm [7], requiring the use of a training set, which is not needed in our work.

Casanova, Fagin & Papadimitriou [5] give a definition of the inclusion dependency problem, prove that it is PSPACE complete, and propose a fundamental axiomatization of IND inference. Mitchell [21]) developed inference rules to derive inclusion dependencies from existing inclusion dependencies and functional dependencies.

de Marchi and Petit [9] as well as Koeller and Rundensteiner [16] have done the most recent work in using the concept of Inclusion Dependency discovery for the integration of databases. Both papers propose algorithms for the detection of inclusion dependency patterns across databases. However, neither paper deals with noise or non-matching values. More recent work [17] addresses the exponential nature of the IND discovery problem by proposing complexity-reducing heuristics, but also does not address the problem of non-equality at the data value level.

Bell and Brockhausen [2], Huhtala et al. [13], Knobbe and Adriaans [15] and Savnik and Flach [11] have contributed
solutions on problems of discovery of functional dependencies in databases. Furthermore, some authors, such as Lim and Harrison [20] or Wei and Chen [25] address the topic of discovering functional-dependency-like patterns that are almost true. This topic is related to our approximate inclusion dependency discovery. However, functional dependencies are a special case of inclusion dependencies, in which the “right” side of the dependency is a key in its table, i.e., contains no duplicates. The IND discovery problem is more general, such that functional dependency discovery algorithms are not usable for inclusion dependency discovery.

Work on discovery of similarities in databases is not limited to Inclusion Dependency Discovery. Larson et al. [18] propose a theory of attribute equivalence in databases, based on the domains, the minimal and maximal values of the attribute, and constraints imposed by the database. However they do not examine the data inside the attributes further, making their proposal very sensitive to the availability and correctness of database constraints, as well as the availability of either global or common domains.

Kang and Naughton [14] propose an instance-based technique of examining statistical characteristics of data (specifically, mutual information content of attributes) to identify dependency relationships between data in the attributes of independent tables. This approach is related to ours, but requires equality of entire data values in each attribute, rather than looking at individual words as in our work.

Bilenko and Mooney [4], propose learnable text similarity metrics, to aid in duplicate detection. This approach is unrelated to the duplicate detection mechanism in this paper. It deals mainly with differences in the spelling of text being compared. This feature could in the future be integrated with our similarity measures to increase their applicability.

Schallehn, Sattler, and Saake [24], present an algorithm for data integration, by proposing variants of the SQL grouping and join operators. In fact the authors present an approach that is also based on the concepts of similarity and duplicate detection. However, to determine similarity the authors depend upon *similarity predicates*, which are application specific and user defined. This approach assumes availability of extensive and accurate knowledge about the contents of the tables being considered. This is an assumption we do not make in our work, taking into consideration the real-world applicability of our algorithms.

# 7. CONCLUSION AND FUTURE WORK

In this paper we have proposed two measures, called *Similarity Score* and *Distribution Score* to solve some problems of data integration of heterogeneous databases. With this approach it is now possible to detect similarities from data in databases even in the presence of a large amount of “noise” in the contents of the database.

The implementation of approximate matching of textual domain attributes addresses the problem of differences in the representation of real world entities in database systems. The application of the distribution score for the integration of databases shifts the focus from discovering Inclusion Dependencies which are defined to be set inclusions, to satisfying more “fuzzy” patterns. Hence, we move away from a binary result (i.e., whether two sets of attributes are related or not), to providing a score that reflects our degree of confidence that attributes are related, i.e., that their relations can be integrated.

The algorithms implemented have a linear runtime with respect to the sizes of the databases as well as the number of attributes in the databases, making them applicable for integration of large database systems and preserving their relevancy for real world applications. The good runtime is largely due to the fact that introducing the similarity and distribution scores for attributes enables us to define a greedy attribute matching algorithm as opposed to an enumeration strategy that is necessary for detection of exact inclusion dependencies.

While the algorithms provided in this paper advance the mechanisms for integration of databases, additional work is necessary before a deployment in the real world can occur. Some of the improvements that are required are

* Handling data types other than strings such as dates, numbers

* Reduction of sensitivity to variations in spelling

* Increasing the efficiency of the algorithms by reducing runtime

* A more comprehensive treatment of value distributions, beyond simple duplicate counts. Mechanisms such as $\chi^2$ independence tests or Kang/Naughton's [14] mutual information content approach might strengthen our results.

# 8. REFERENCES

[1] J. Albert. Algebraic properties of bag data types. In *International Conference on Very Large Data Bases*, pages 211–219, 1991.

[2] S. Bell and P. Brockhausen. Discovery of data dependencies in relational databases. In Y. Kodratoff, G. Nakhaeizadeh, and C. Taylor, editors, *ML-Net Familiarization Workshop*, 1995.

[3] S. Bergamaschi, S. Castano, M. Vincini, and D. Beneventano. Semantic integration of heterogeneous information sources. *Data and Knowledge Engineering*, 36(3):215–249, 2001.

[4] M. Bilenko and R. J. Mooney. Employing trainable string similarity metrics for information integration. In *Proc. of IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03)*, pages 67–72, Acapulco, Mexico, 2003.

[5] M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion dependencies and their interaction with functional dependencies. In *Proceedings of ACM Conference on Principles of Database Systems (PODS)*, pages 171–176, 1982.

[6] W. W. Cohen. Integration of heterogeneous databases without common domains using queries based on textual similarity. *SIGMOD Record*, 27(2):201–213, 1998.

[7] W. W. Cohen and H. Hirsh. Joins that generalize: Text classification using WHIRL. In *Proc. of 4th Intl. Conf. on Knowl. Discovery and Data Mining (KDD)*, page 1998, New York, August 169–173.

[8] F. de Marchi, S. Lopes, and J.-M. Petit. Efficient algorithms for mining inclusion dependencies. In *Proceedings of International Conference on Extending Database Technology (EDBT)*, pages 464–476, 2002.
[9] F. de Marchi and J.-M. Petit. Zigzag: A new algorithm for mining large inclusion dependencies in databases. In *3rd Intl. Conf. on Data Mining*, pages 27–34, Melbourne, Florida, November 2003. IEEE.

[10] A. Doan, P. Domingos, and A. Halevy. Learning source description for data integration. In *Proceedings of the Third International Workshop on the Web and Databases (WebDB)*, pages 81–86, Dallas, 2000.

[11] P. A. Flach and I. Savnik. Database dependency discovery: a machine learning approach. *AI Communications*, 12(3):139–160, November 1999.

[12] A. Halevy and J. Madhavan. Corpus-based knowledge representation. In *Proc. of 18th Intl. Joint Conf. on Artificial Intelligence (IJCAI'03)*, pages 1567–1572, Acapulco, Mexico, 2003. Morgan Kaufman.

[13] Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen. Efficient discovery of functional and approximate dependencies using partitions. In *Proceedings of IEEE International Conference on Data Engineering*, pages 392–401, 1998.

[14] J. Kang and J. F. Naughton. On schema matching with opaque column names and data values. *Proceedings of SIGMOD*, pages 205–216, 2003.

[15] A. J. Knobbe and P. W. Adriaans. Discovering foreign key relations in relational databases. In R. Trappl, editor, *Proceedings of the Thirteenth European Meeting on Cybernetics and Systems Research*, volume 2, pages 961–966, Vienna, Austria, 1996. Austrian Soc. Cybernetic Studies, Vienna, Austria.

[16] A. Koeller and E. A. Rundensteiner. Discovery of high-dimensional inclusion dependencies. In *Proceedings of IEEE International Conference on Data Engineering*, pages 683–685, Bangalore, India, 2003. IEEE.

[17] A. Koeller and E. A. Rundensteiner. Heuristic strategies for Inclusion Dependency discovery. In *Proc. of 3rd Intl. Conf. on Ontologies, Databases, and Applications of Semantics (ODBASE'04)*, volume 3290–3291 of LNCS, pages 891–908, Larnaca, Cyprus, 2004. Springer.

[18] J. A. Larson, S. B. Navathe, and R. Elmasri. A theory of attribute equivalence in databases with application to schema integration. *IEEE Transactions on Software Engineering*, 15(4):449–463, April 1989.

[19] W. Li and C. Clifton. SemInt: A tool for identifying attribute correspondences in heterogeneous databases using neural networks. *Data and Knowledge Engineering*, 33(1):49–84, 2000.

[20] W. Lim and J. Harrison. Discovery of constraints from data for information system reverse engineering. In *Proc. of Australian Software Engineering Conference (ASWEC '97)*, Sydney, Australia, Sep 28–Oct 2 1997.

[21] J. C. Mitchell. Inference rules for functional and inclusion dependencies. In *Proceedings of ACM Symposium on Principles of Database Systems*, pages 58–69, Atlanta, Georgia, 21–23 March 1983.

[22] E. Rahm and P. A. Bernstein. A survey of approaches to automatic schema matching. *VLDB Journal: Very Large Data Bases*, 10(4):334–350, 2001.

[23] G. Salton. *Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer*. Adison Wesley, New York, 1989.

[24] E. Schallehn, K.-U. Sattler, and G. Saake. Efficient similarity-based operations for data integration. *Data and Knowledge Engineering*, 48(3):361–387, 2004.

[25] Q. Wei and G. Chen. Efficient discovery of functional dependencies with degrees of satisfaction. *Intelligent Systems*, 19(11):1089–1110, September 2004.
# Clustering Mixed Numerical and Low Quality Categorical Data: Significance Metrics on a Yeast Example

Bill Andreopoulos

Department of Computer
Science, York University,
Toronto, Canada, M3J1P3

billa@cs.yorku.ca

Aijun An

Department of Computer
Science, York University,
Toronto, Canada, M3J1P3

aan@cs.yorku.ca

Xiaogang Wang

Department of Mathematics and
Statistics, York University, Toronto,
Canada, M3J1P3

stevenw@mathstat.yorku.ca

## ABSTRACT

We present the M-BILCOM algorithm for clustering mixed numerical and categorical data sets, in which the categorical attribute values (CAs) are not certain to be correct and have associated confidence values (CVs) from 0.0 to 1.0 to represent their certainty of correctness. M-BILCOM performs bi-level clustering of mixed data sets resembling a Bayesian process. We have applied M-BILCOM to yeast data sets in which the CAs were perturbed randomly and CVs were assigned indicating the confidence of correctness of the CAs. On such mixed data sets M-BILCOM outperforms other clustering algorithms, such as AutoClass. We have applied M-BILCOM to real numerical data sets from gene expression studies on yeast, incorporating CAs representing Gene Ontology annotations on the genes and CVs representing Gene Ontology Evidence Codes on the CAs. We apply novel significance metrics to the CAs in resulting clusters, to extract the most significant CAs based on their frequencies and their CVs in the cluster. For genomic data sets, we use the most significant CAs in a cluster to predict gene function.

## 1. INTRODUCTION

Clustering aims to partition a set of objects into clusters, so that objects with similar characteristics are clustered together and different clusters contain objects with dissimilar characteristics. A high quality clustering tool produces clusters with high intra-class similarity between objects and low inter-class similarity between objects [11, 13, 15, 17]. Many numerical data sets have CAs associated with them, but not all CAs are certain to be correct. For many of these data sets CVs can be extracted on the CAs, representing the certainty about the CAs' correctness [8, 20].

We designed the M-BILCOM clustering tool for numerical data sets that incorporates in the clustering process CAs and CVs indicating the confidence that the CAs are correct. M-BILCOM was mainly inspired by numerical gene expression data sets from DNA microarray studies, where CAs and CVs can be derived from Gene Ontology annotations and Evidence Codes [4-10, 12, 14, 21-22]. One of the main advantages of this algorithm is that it offers the opportunity to apply novel significance metrics for spotting the most significant CAs in a cluster when analyzing the

results [3]. In genomic data sets, our significance metrics allow significant CAs to be extracted from a cluster based on their CVs and their frequencies and to be used for predicting the functions of other genes in the cluster. This provides a different insight for predicting gene function by giving the 'full picture' of the data set, because the significant CAs are extracted from genes that may have been appended to the cluster on the basis of numerical or categorical similarity or both.

This approach offers several advantages over other approaches:

* Our clustering algorithm may cluster data sets where all genes have numerical attribute values but not all genes have CAs. Each CA has a CV associated - a real number between 0.0 and 1.0 - indicating our confidence about its correctness.

* During the clustering process, this method starts from CAs and CVs at the lower level and then moves to numerical clustering at a higher level. The CAs and CVs are actually used in the clustering process, instead of just annotating the clusters afterwards [1, 3]. The method of Wu et al. as applied previously to high-throughput biological data, starts from the numerical clustering, then adds CAs at a higher level and finally CVs are calculated (P-values) [25].

* During the clustering process, objects having CAs with high confidence to be correct, get clustered by emphasizing more the categorical similarity and less the numerical similarity. On the other hand, objects having CAs with low confidence to be correct get clustered by emphasizing more the numerical similarity [1].

* Our clustering algorithm allows us to define significance metrics indicating the significance of a CA in a cluster. Such metrics are calculated on the basis of how frequently a CA appears in a cluster as well as how strongly the CVs support the CA's correctness in that cluster [3].

* For genomic data sets CVs can be derived from GO evidence codes to point out the most reliable CAs to be used for gene functional prediction purposes [8, 12]. This is in contrast to previous methods, where CVs were calculated at the end to indicate the reliability of a CA's belonging to a cluster [25].

Section 2 describes the k-Modes clustering algorithm. Section 3 discusses the M-BILCOM clustering algorithm, which is a combination of MULICsoft and BILCOM. Section 4 proposes two significance metrics for the CAs in the resulting clusters and discusses their utility for gene functional prediction on a real yeast data set. Sections 5 and 6 describe the results for applying M-BILCOM to highly noisy yeast data sets and its ability to reproduce the correct cluster structure. Sections 7 and 8 discuss implications of the significance metrics for biologists and gene functional prediction. Finally, Section 9 concludes the paper.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA.

Copyright 2005 ACM 1-59593-160-0/05/06 $5.00.
## 2. BACKGROUND ON K-MODES

k-Modes is a clustering algorithm that deals with categorical data only [18,19]. The k-Modes clustering algorithm requires the user to specify from the beginning the number of clusters to be produced and the algorithm builds and refines the specified number of clusters. Each cluster has a mode associated with it. Assuming that the objects in the data set are described by *m* categorical attributes, the mode of a cluster is a vector $Q=\{q_1, q_2, ..., q_m\}$ where $q_i$ is the most frequent value for the *i*th attribute in the cluster of objects.

Given a data set and the number of clusters *k*, the k-Modes algorithm clusters the set as follows:

1. Select initial *k* modes for *k* clusters.

2. For each object *X*

a. Calculate the similarity between object *X* and the modes of all clusters.

b. Insert object *X* into the cluster *c* whose mode is the most similar to object *X*.

c. Update the mode of cluster *c*.

3. Retest the similarity of objects against the current modes. If an object is found to be closer to the mode of another cluster rather than its own cluster, reallocate the object to that cluster and update the modes of both clusters.

4. Repeat 3 until no or few objects change clusters after a full cycle test of all the objects.

A similarity metric is needed to choose the closest cluster to an object by computing the similarity between the cluster's mode and the object. Let $X=\{x_1, x_2, ..., x_m\}$ be an object, where $x_i$ is the value for the *i*th attribute, and $Q=\{q_1, q_2, ..., q_m\}$ be the mode of a cluster. The similarity between *X* and *Q* can be defined as:

$$ 
\begin{gathered}
\text{similarity}(X, Q) = \sum_{i=1}^{m} \delta(x_i, q_i) \\
\text{where } \delta(x_i, q_i) = \begin{cases} 1 & (x_i = q_i); \\ 0 & (x_i \neq q_i). \end{cases}
\end{gathered}
$$

Given the similarity measure and *k*, the clustering result produced by the k-Modes algorithm on a set of data depends on the initial modes and the ordering of the objects presented to k-Modes. In [18] two methods for selecting the initial modes are discussed and compared.

In the descriptions that follow we assume that *C* represents the total number of clusters and we use *c* to index the clusters. We assume that *m* represents the number of attributes in an object of the data set and *N* represents the number of objects in the data set.

## 3. THE M-BILCOM CLUSTERING ALGORITHM

M-BILCOM is a combination of MULICsoft [2] and BILCOM [1]. The basic idea of our algorithm is to do clustering at two levels, where the first level clustering imposes an underlying framework for the second level clustering, thus simulating a Bayesian prior as described in [1]. The categorical similarity is emphasized at the first level and the numerical similarity at the second level. The level one clusters are given as input to level two and the level two clusters are the output of the clustering process. The process looks as in Figure 1. As shown, both level one and level two involve the same number of clusters, four in this example. The level two clusters consist of subclusters. Data object

A was assigned to different level one and level two clusters, because the numerical similarity at the second level was stronger than the categorical similarity at the first level. Thus, in the case of Figure 1 the following relationship holds for object A:

$$ \text{categorical\_similarity}(A, \text{cluster2}) + \text{numerical\_similarity}(A, \text{cluster2}) > $$

$$ \text{categorical\_similarity}(A, \text{cluster3}) + \text{numerical\_similarity}(A, \text{cluster3}) $$

On the other hand, data object *B* was assigned to the same clusters in both levels one and two, because both numerical and categorical similarity supported this classification. Thus, this algorithm considers both categorical and numerical similarity of a data object to the clusters to which it may be allocated.

<figure><img src="image_73.png" /><figcaption>Figure 1. Overview of M-BILCOM clustering.</figcaption></figure>

We emphasize that different types of data are used at levels one and two. At the first level the categorical data used represent something that has been observed to be true about the data set objects before the experiment takes place. For example the data at the first level might look as follows: Class:LIVE; SEX:male; STEROID:yes; FATIGUE:no; ANOREXIA:no. At the second level, on the other hand, the numerical data used represent the results of an experiment involving the data set objects. For example the data at the second level might look as follows: BILIRUBIN:0.39; ALBUMIN:2.1; PROTIME:10.

Our clustering method has the following requirements:

1. The coherence of each cluster should be maximized, considering both the numerical and categorical similarity of the objects.

2. Only the objects with highest categorical similarity to a cluster should form the basis for clustering at the first level.

3. The results of the first level clustering – which is the prior for the process – should not exert an overly strong effect on the second level, so that the second level clustering can escape a poor prior.

4. It should be possible to form a flexible number of clusters.

5. The similarity formula for comparing a mode to an object should increase an object's likelihood to be attached to a cluster as many CAs match the mode and as the CVs of those CAs increase.

We combined MULICsoft [2] and BILCOM [1] into an advanced clustering algorithm named M-BILCOM. This algorithm is similar to BILCOM [1], except that at the first level it also considers weights between 0.0 and 1.0 on the CAs – which we refer to as confidence values or CVs. This combined algorithm is especially useful in cases where the CAs have been perturbed and a CV between 0.0 and 1.0 has been assigned to each CA to indicate the certainty of correctness. Alternatively, M-BILCOM could be used on biological yeast data sets – such as SGD – where the certainty of correctness that exists on current knowledge is expressed as GO evidence codes [8, 12, 20].
## 3.1 First Level Clustering: MULICsoft

At the first level, clustering is performed using MULICsoft<fnref n="1" /> which has a special similarity metric that incorporates CVs in the clustering process. MULICsoft is an extension of the k-Modes clustering algorithm for categorical data sets [18]. MULICsoft clusters only a subset of the data set objects. The number of clusters resulting from this level equals the final number of clusters desired, as illustrated in Figures 1 and 2.

The purpose of MULICsoft is to maximize the following similarity formula at each iteration, while ensuring that all objects may eventually be inserted in clusters:

$$similarity(object_n, mode_n)$$

where *object_n* is the nth object in the data set to be clustered and *mode_n* is the mode of the cluster to which *object_n* is classified.

MULICsoft starts by reading all objects from the input file and storing them in a linked list *S*. The first object is inserted in a new cluster, the cluster's mode is set equal to the object's CAs and the object is removed from *S*. Then, it iterates over all objects that have not been classified in a cluster yet, to find the closest cluster. The closest cluster is determined for each unclassified object by comparing all clusters' modes with the object. The similarity between a mode and an object is determined using a special variation of the k-Modes similarity metric [2,18] that incorporates CVs in the clustering process and is described in Section 3.1.1.

The variable *φ* is maintained to indicate how strong the similarity has to be between an object and the closest cluster's mode for the object to be inserted in the cluster – initially *φ* equals 0, meaning that the similarity has to be very strong between an object and the closest cluster's mode. If the number of different CAs between the object and the closest cluster's mode are greater than *φ*, then, the object is inserted in a new cluster on its own and the cluster's mode is set equal to the object's CAs. If the number of different CAs between the object and the closest cluster's mode are less than or equal to *φ*, then, the object is inserted in the closest cluster and the mode is updated.

At the end of each iteration, all clusters with size one are removed, so their objects will be re-clustered at the next iteration. Thus, the clusters that persist are those containing at least two objects for which the required similarity can be found. Objects belonging to clusters with size greater than one are removed from the linked list of objects *S*, so those objects are not re-clustered.

At the end of each iteration, if no objects have been placed in clusters of size greater than one, then, the variable *φ* is incremented to represent how many CAs are allowed to differ next time. Thus, at the next iteration it will be more flexible and eventually more objects will be placed in clusters. Eventually, all objects will be given the opportunity to be placed in clusters, even if the closest cluster is not so similar. The iterative process may stop when all objects have been placed in clusters of size greater than one, or when *φ* is greater than a user-specified *threshold*.

The MULICsoft algorithm gives the opportunity for all objects to be eventually placed in clusters, because *φ* may continue increasing until all objects are classified. Even if, in the extreme case, an object with *m* CAs has only one or zero CAs similar to the mode of the closest cluster, it can be classified when *φ* = *m*−1 or *φ* = *m*, respectively.

Figure 2 illustrates the results of MULICsoft. Each cluster consists of many different "layers" of objects. The layer of an object represents how strong the object's similarity was to the

mode of the cluster when the object was inserted. The cluster's layer in which an object is inserted depends on the value of *φ*. Thus, lower layers have a lower coherence – defined as the average similarity between all pairs of objects in that layer - and correspond to higher values of *φ* and to a more flexible similarity criterion for insertion. MULICsoft starts by inserting as many objects as possible at higher layers and then moves to lower layers, creating them as the need arises. If little similarity exists between an object and its closest cluster, the object will be inserted in a lower layer.

If an unclassified object has equal similarity to the modes of the two (or more) closest clusters, then the algorithm tries to resolve this 'tie' by comparing the object to the mode of the top layer of each of these clusters – the top layer of a cluster may be layer 0 or 1 or 2 and so on. Each cluster's top layer's mode was stored by MULICsoft when the cluster was created, so it does not need to be recomputed. If the object has equal similarity to the modes of the top layer of all of its closest clusters, the object is assigned to the cluster with the highest bottom layer. If all clusters have the same bottom layer then the object is assigned to the first cluster, since there is insufficient data for selecting the best cluster.

<figure><img src="image_74.png" /><figcaption>Figure 2. MULICsoft results. Each cluster consists of one or more different layers representing different similarities of the objects attached to the cluster.</figcaption></figure>

The runtime complexity of MULICsoft is $O(N^2)$, where *N* represents the number of objects in the data set [2]. In most of our trials the runtime was less than 1 second.

The question remains of which objects to be clustered at the first level of M-BILCOM. The first level objects are those whose comparison to the mode of the closest cluster yields a result that is greater than or equal to a threshold *minimum_modeSimilarity*. The rest of the objects are used at the second level, as described in Section 3.2. For this purpose, the user can specify a maximum value for *φ* - a value of *m*-minimum_modeSimilarity, where *m* is the total number of categorical attributes in an object. When *φ* exceeds this value, any remaining objects are held for consideration instead in the second level. The reason we choose to insert in the first level clusters just the objects whose similarity to the closest mode yields a value higher than a threshold *minimum_modeSimilarity* is because the objects that yield a low similarity to the closest mode are more likely to be inserted in the wrong cluster, as we show in [1,2]. Thus, the objects whose classification in clusters based on categorical similarity is not reliable enough, are clustered in the second level instead, where the numerical similarity of objects to second level clusters is more influential.

<footnote n="1">¹ http://www.cs.yorku.ca/~billa/MULIC/</footnote>
### 3.1.1 The MULICsoft Similarity Metric

All CAs in an object have "weights" or CVs in the range 0.0 to 1.0 associated with them. We represent the ith weight of an object as $w_i$, the ith CA of object o as $o_i$ and the ith value of mode $\mu$ as $\mu_i$. The similarity metric used in MULICsoft for computing the similarity between a mode $\mu$ and an object o considers both the CAs and their weights. Our similarity metric amplifies the object positions having high weights, at pairs of CAs between an object o and a mode $\mu$ that have identical values.

$$similarity(o, \mu) = \sum_{i=1}^{m} \frac{6 - (4 \times w_i)}{5 - (4 \times w_i)} \times \sigma(o_i, \mu_i)$$

$$\text{where } \sigma(o_i, \mu_i) = \begin{cases} 1 & (o_i = \mu_i); \\ 0 & (o_i \neq \mu_i). \end{cases}$$

This similarity metric gives more importance to high weights (1.0) than low weights (0.1) at categorical attributes with identical values between the object and the mode.

Figure 3 shows that our similarity formula for comparing a mode to an object increases an object's likelihood to be attached to a cluster as many CAs match the cluster's mode and as the weights on those CAs increase. Each object in this example has 10 CAs and "weights" (or CVs). Figure 3 shows that an object will be much more likely to be assigned to a cluster if all CAs match the mode with high weights of 1.0, than if all CAs match the mode with medium weights of 0.5, than if all CAs match the mode with low weights of 0.1, than if 1 CA matches the mode with a high weight, than if 1 CA matches the mode with a low weight.

<figure><img src="image_75.png" /><figcaption>Figure 3. The function surface of similarity, using values for the weights between 0.0 and 1.0 as described previously.</figcaption></figure>

### 3.1.2 Dealing with Outliers

MULICsoft can, eventually, put all the objects in clusters. When $\phi$ equals the number of attributes $m$, an unclassified object can be inserted in the lowest layer $m$ of any existing cluster. This is undesirable if the object is an outlier and has little similarity with any cluster. The user can disallow this situation from happening, by specifying a threshold for $\phi$ that is less than the number of CAs $m$, so, when this threshold is reached any remaining objects are not classified and are treated as outliers. As discussed in [2] for clustering of software systems, the overall quality of the results often improves by treating the lowest-layer objects as outliers.

## 3.2 Second Level Clustering: BILCOM

The first level result is the input to the second level. The second level clusters all of the data set objects, including the objects clustered at the first level. The second level uses numerical data type similarity and the first level result as a prior. The second level clustering consists of 5 steps, whose rationale is to simulate maximizing the numerator of the Bayesian equation, as discussed in Section 3.1. The second level result is the output of the BILCOM process.

**Step 1.** One object in each first level cluster is set as a seed, while all the rest of the objects in the cluster are set as centers. The seed is an object that is at the top layer of the cluster – ideally in layer 0. The reason we choose for seed a top layer object is that the most influential objects at the second level should be those that have the minimum average distance to all other objects in the first level cluster. The MULIC paper [2] showed that objects at the top layer have a smaller average distance to all other cluster objects than lower level objects do.

If the top layer of a cluster is layer 0 then we have no difficulty in choosing the seed since all objects have the same CAs. If the top layer of a cluster is not layer 0 and it contains more than one object, then we choose the seed by comparing all top layer objects to the cluster's mode to find the closest object. If this does not resolve the ambiguity then we compare all top layer objects to the cluster's top layer mode – which was stored by MULIC when the cluster was created - to find the closest object. If all top layer objects have the same similarities to modes then we assign the seed to be the first top layer object, since there is insufficient information for choosing the best seed.

**Step 2.** Each seed and center is inserted in a new second level subcluster. The output of this step is a set of subclusters, referred to as seed-containing or center-containing subclusters, whose number equals the number of objects clustered at the first level.

**Step 3.** Each object that did not participate at the first level is inserted into the second level subcluster containing the most numerically similar seed or center. Numerical similarity for Steps 3-5 is determined by the Pearson correlation coefficient or the Shrinkage-based similarity metric introduced by Cherepinsky et al [9].

**Step 4.** Each center-containing subcluster is merged with its most numerically similar seed-containing subcluster. The most numerically similar seed-containing subcluster is found using our version of the ROCK goodness measure [14] that is evaluated between the center-containing subcluster in question and all seed-containing subclusters:

$$G(C_i, C_j) = \frac{\text{link}[C_i, C_j]}{\text{size}(C_i) \times \text{size}(C_j)}$$

$\text{link}[C_i, C_j]$ stores the number of cross links between subclusters $C_i$ and $C_j$, by evaluating $\Sigma(o_q \in C_i, o_r \in C_j)$ $\text{link}(o_q, o_r)$. $\text{link}(o_q, o_r)$ is a boolean value specifying whether a link exists between objects $o_q$ and $o_r$. A link is set between two objects if the objects' numerical similarity is higher than a value minimumNumericalSimilarity. The rationale for using a variation of ROCK's goodness measure for this step is that the link-based approach of ROCK adopts a global approach to the clustering problem, by capturing the global information about neighboring objects between clusters. It has been shown to be more robust than methods that adopt a local approach to clustering, like hierarchical clustering [14].

**Step 5.** The loop below refines the step 4 subcluster merges. All variables take real values in the range 0.0-1.0.
```pascal
repeat {
  foreach (center-containing_subcluster)
    if
      (numerical_similarity_of_center_subcluster_to_1st-
       level_seed_cluster) *
      categorical_similarity_of_center_to_seed_of_1st_le
      vel_cluster >
      numerical_similarity_of_center_subcluster_to_its_n
      umerically_similar_2nd_level_cluster) *
      categorical_similarity_of_center_to_seed_of_its_nu
      merically_similar_2nd_level_cluster)
        merge center-containing_subcluster
to seed-containing_subcluster from 1st_level;
} until (no center-containing_subcluster changes);
```

The variable:

```
categorical_similarity_of_center_to_seed_of_1st_le
vel_cluster
```

represents the *categorical* similarity of the center *c* of a subcluster *C* to the seed *s*, such that *c* and *s* were in the same first level cluster.

The variable:

```
categorical_similarity_of_center_to_seed_of_its_nu
    merically_similar_2nd_level_cluster
```

represents the *categorical* similarity of the center *c* of a subcluster *C* to the seed of *C*'s most numerically similar seed-containing subcluster *N* determined in step 4. The categorical similarity is computed as follows, where *wc*<sub>*i*</sub> is the *i*th weight of the center and *ws*<sub>*i*</sub> is the *i*th weight of the seed:

$$ 
\text{similarity}(\text{center}, \text{seed}) = \frac{\sum_{i=1}^{m} wc_i \times ws_i \times \sigma(\text{center}, \text{seed}_i)}{m} \\
\text{where } \sigma(\text{center}_i, \text{seed}_i) = 1 \text{ if center}_i = \text{seed}_i, 0 \text{ otherwise.}
$$

The variables:

```
numerical_similarity_of_center_subcluster_to_1st_1
    vel_seed_cluster
```

```
numerical_similarity_of_center_subcluster_to_its_n
    umerically_similar_2nd_level_cluster
```

represent the *numerical* similarity of a subcluster *C* containing center *c* to the cluster containing seed *s*, such that *c* and *s* were in the same first level cluster, and to the cluster containing *C*'s most numerically similar seed-containing subcluster *N* determined in step 4, respectively. These similarities include the subclusters that were merged to the clusters in previous iterations of the loop.

<figure><img src="image_76.png" /><figcaption>Figure 4. Steps 4 and 5 of second level of BILCOM clustering.</figcaption></figure>

According to this loop, a subcluster *C* containing center *c* is attracted to the subcluster *S* containing seed *s*, such that *c* and *s* were in the same first level cluster. The attraction is stronger if there is high categorical similarity between *c* and *s* and lower if

there is low categorical similarity between *c* and *s*. The subclusters *C* and *S* get merged if both the categorical similarity between *c* and *s* and numerical similarity between *C* and *S* are high enough. If *c* is not categorically similar enough to *s*, then, *C* should be likely to remain merged with its most numerically similar seed-containing subcluster *N* determined in step 4. Figure 4 shows steps 4 and 5.

We have done tests to show that BILCOM is able to escape a *poor prior* – for instance, if a center *c* was inserted in a first level cluster with weak similarity to the cluster mode, or if the similarity to the mode was erroneously high enough, or if *c* had wrong CAs with low confidence to be correct. The categorical similarity between the center *c* and the seed *s*, such that *c* and *s* were in the same first level cluster, is likely to return a low value when the prior is poor. In this case, the subcluster *C* containing center *c* will be likely to remain merged with its most numerically similar seed-containing subcluster *N* determined in step 4, instead of the subcluster *S* containing the seed *s*. Thus, the prior can be escaped and the data can be clustered correctly. In this case, *C* will not be merged to *S*, unless their numerical similarity is very high.

On the other hand, if the subcluster *C* containing center *c* is merged to the subcluster *S* containing the seed *s*, such that *c* and *s* were in the same first level cluster, then *C* must be numerically similar enough to *S*. This way we ensure that if a subcluster *C* is merged to the subcluster *S* that is suggested by the results of the first level clustering, the numerical similarity between *C* and *S* is high enough to support the merging.

The reason why the inequality comparison in step 5 considers the seeds of clusters, instead of the cluster modes, is that by considering similarity to seeds we are effectively giving the objects a *second chance* to reorganize and to escape their first level clustering, if the first level clustering was weak. Since the first level clustering was based on comparisons to modes that often yield wrong results and, therefore, objects may be attached to wrong clusters, the comparison in step 5 allows the similarities to be reconsidered. We showed in [2] that objects in the top layers 0 and 1 such as seeds have a higher average similarity to all other cluster objects than do lower layer objects.

# 4. TWO METHODS FOR IDENTIFYING SIGNIFICANT CAs IN A CLUSTER

This section first describes the real yeast data on which we applied the M-BILCOM clustering algorithm. Then, it presents two significance metrics (SMs) for determining the significance of a CA in a cluster and for supporting gene functional prediction.

## 4.1 Description of Real Yeast Data Sets

This algorithm is designed with the goal of applying it to numerical data sets for which some CAs exist and the confidence that the CAs are correct varies. We used numerical data derived from gene expression studies on the yeast *Saccharomyces cerevisiae*. These data sets were produced at Stanford to study the yeast cell cycle across time and under various experimental conditions and are available from the SGD database [9, 23]. When clustering this data set, we consider each gene to be a 'data object'. The data set contained 6,200 objects.

We represented CAs on a gene in terms of Gene Ontology (GO) and GOSlim annotations. GO is a dynamically controlled vocabulary that can be applied to many organisms, even as knowledge of gene and protein roles in cells is changing. GO is
organized along the categories of molecular function, biological process and cellular location [12]. GOSlim are GO annotations that represent high level knowledge on genes and are also organized along the categories of function, process and location. Most of the GO and GOSlim annotations on the yeast genes exist in the publicly accessible SGD database, along with GO evidence codes [8, 12, 20]. We created six pools of CAs for each gene and each pool contained GO annotations of a specific type. Three pools contained GO annotations for molecular function, biological process and cellular location of a gene. The other three pools contained GOSlim annotations for each GO annotation.

We attached CVs to the CAs to represent the confidence that the corresponding CA is correct. CVs are real numbers between 0.0 and 1.0, assigned to the CAs of a gene. Besides indicating the confidence that a CA is correct, the CVs on a gene also specify how strongly the gene's CAs should influence the clustering process. The CVs are also used in the significance metrics that we define below. We determined the CVs by using GO evidence codes. GO evidence codes symbolize the evidence that exists for any particular GO or GOSlim annotation [12].

GO evidence codes can be thought of in a loose hierarchy from strong evidence to weak evidence. For example, 'TAS' means 'Traceable Author Statement', while 'NAS' means 'Non-traceable Author Statement' [9]. We assigned a numerical CV to each of the GO evidence codes based on its location in the hierarchy, as shown in Figure 5. Section 7 discusses our justifications. NR and ND are set to 0.0, because they are used for annotations of 'unknown', so the CAs should not have an effect on the clustering process. In certain DBs (Swiss-prot-human) only 3 of these evidence codes are commonly used and the most commonly used one is TAS, which is at the top of the hierarchy, meaning that strong evidence exists [20]. We combined the CAs, CVs and gene expression data using Perl.

A CV primarily depends on whether the CA refers to something that has been *observed* to be true, as opposed to something that is just *believed* to be true. For example, a CA of a "cancerous tissue" refers to an observed phenomenon with a high CV, while a CA of a "non-cancerous tissue" refers to something that is just believed to be true, as the tissue might turn out later to be cancerous.

## 4.2 First SM: M-values that Consider P1-values and CVs are Assigned to Cluster CAs

Given a resulting cluster, we assigned a P1-value to each CA in the cluster; the term 'P1-value' was derived from the statistical 'P-value'. A P1-value measures whether a cluster contains a CA of a particular type more frequently than would be expected by chance [25]. A P1-value close to 0.0 indicates a frequent occurrence of the CA in the cluster, while a P1-value close to 1.0 its seldom occurrence. We multiplied the resulting P1-value with the reciprocal of the average of all CVs assigned to the CA in the cluster, 1/avg(CV), thus resulting in what we call an *M-value*. M-values allow us to take into consideration the probability that a particular CA occurs in the cluster more frequently than expected by chance, in addition to our confidence that the CA is correct in the cluster. For CAs that occur only once or twice in a cluster, a high P1-value results with an avg(CV) trivial to estimate.

<figure><img src="image_77.png" /></figure>

## 4.3 Second SM: The Significance of a Second Level Subcluster's Classification in a Cluster

This significance metric was inspired by the loop of step 5 that refines the subclusters composing a larger second level cluster, as shown in Section 3.2. Specifically, each subcluster was assigned a significance number by evaluating a formula that considers both categorical (CAsimilarity) and numerical (NAsimilarity) similarity of the subcluster to the larger second level cluster:

$$ (weight1*CAsimilarity) + (weight2*NAsimilarity) $$

The CAsimilarity for a subcluster is computed by evaluating a categorical variation of ROCK's goodness measure [16] between the subcluster and its larger cluster and multiplying the result by the percentage of genes in the subcluster that were assigned to it on the basis of categorical similarity (see Section 3.2 step 3). The NAsimilarity for a subcluster is computed similarly, by evaluating a numerical variation of ROCK's goodness measure [16] between the subcluster and its larger cluster and multiplying the result by the percentage of genes in the subcluster that were assigned to it on the basis of numerical similarity (see step 3). We set weight2 in our trials to be higher than weight1, to ensure proper consideration of the numerical similarity of a subcluster.

The subclusters in an overall second level cluster for which the above metric yields the highest values are used for functional prediction by identifying and extracting the most significant genes' CAs in the cluster with highest avg(CV)s.

When a subcluster is placed in a larger second level cluster on the basis of high CA similarity (0.5-1.0) – regardless of whether it was assigned there at the beginning of the clustering process or joined it later - this is a factor that increases the significance. The NAsimilarity on the subcluster might be either high or low:

- high (0.5-1.0) in which case the significance of its membership is increased, because both CAs and NAs support the gene's classification in the cluster.

- low (0.1-0.4) in which case the significance of its membership is decreased, because CAs support the gene's classification in the cluster but NAs do not.

When a subcluster is placed in a larger second level cluster on the basis of low CA similarity (0.0-0.4) – regardless of whether it was assigned there at the beginning of the clustering process or joined it later - this is a factor that decreases the significance. The NAsimilarity on the subcluster is:

- always high (0.7-1.0). However, since the CA similarity is low the significance of its membership is decreased because NAs support the gene's classification in the cluster but CAs do not.

## 4.4 Functional Prediction for Uncharacterized Genes

Both of the above significance metrics (SM) were used for functional prediction of genes. Section 7 discusses our tests.

The M-values were used for functional prediction by taking for each cluster the CAs with the lowest M-values for molecular function, biological process, cellular location and for the GOSlim terms. Then, we applied these CAs to genes in the cluster having CAs labeled as 'Unknown'. Therefore, the CAs with the lowest M-values in a cluster were used to predict cellular roles of genes.

The second SM was used for functional prediction by identifying the subcluster with the highest significance in a larger second level cluster and identifying its genes' CAs with highest avg(CV)s in the cluster, as these were the most significant ones. Then, we applied the extracted CAs to other genes in the cluster having CAs labeled as 'Unknown'. Therefore, the CAs belonging
to the subcluster that had the highest significance were used to predict cellular roles of genes.

## 5. EXPERIMENTS ON YEAST DATA

We have validated M-BILCOM on mixed numerical and categorical yeast data. We used the yeast data sets shown in Table 1, having mixed categorical and numerical attribute values [7, 9]. However, we perturbed the CAs randomly and assigned statistical confidence values based on the probability that an attribute was perturbed or not. Tests and results are described below.

We represented CAs on a gene in terms of Gene Ontology (GO) - see Section 4. CAs were perturbed and the attribute values in the data set were assigned CVs between 0.1 and 1.0. For this purpose, for each CA we generated a *limit* in a range from 0.1 to 1.0 and, then, generated a random number *ρ* from 0.0 to 1.0. If *ρ* exceeded the *limit*, then we perturbed the CA by assigning it a value taken randomly from the set of possible values for that CA. The CV for the CA was set equal to the *limit* regardless of whether it was actually perturbed or not. This simulates the uncertainty that exists on current knowledge and that is expressed in SGD as GO evidence codes [8, 12, 20]. All attribute values on all objects were assigned a CV between 0.1 and 1.0 and objects whose CAs had lower CVs were more likely to have been perturbed than objects whose attribute values had higher CVs.

The yeast microorganism performs a constant cell-cycle. The yeast cell-cycle gene expression program is regulated by the nine known cell-cycle transcriptional activators, that control the flow from one stage of the cell-cycle to the next [7]. This serial regulation of transcriptional activators together with various functional properties suggests a way of partitioning cell-cycle genes into nine clusters, each one characterized by a group of transcriptional activators working together and their functions [7]. Table 1 shows our hypothesis about how the genes should be correctly grouped by transcriptional activators and cell-cycle functions. For instance, group 2 is characterized by the activators Swi6 and Mbp1 and the function involving DNA replication and repair at the juncture of G1 and S stages.

<table><caption>Table 1. Genes in the data set of Cherepinsky et al. [7] grouped by functions. This is our hypothesis about the correct clustering results.</caption><thead><tr><th>Group</th><th>Activators</th><th>Genes</th><th>Functions</th></tr></thead><tbody><tr><td>1</td><td>Swi4, Swi6</td><td>CLN1, CLN2, GIC1, MSB2, RSR1, BUD9, MNN1, OCH1, EXG1, KRE6, CWP1</td><td>Budding</td></tr><tr><td>2</td><td>Swi6, Mbp1</td><td>CLB5, CLB6, RNR1, RAD27, CDC21, DUN1, RAD51, CDC45, MCM2</td><td>DNA replication and repair</td></tr><tr><td>3</td><td>Swi4, Swi6</td><td>HTB1, HTB2, HTA1, HTA2, HTA3, HHO1</td><td>Chromatin</td></tr><tr><td>4</td><td>Fkh1</td><td>HHF1, HHT1, TEL2, ARP7</td><td>Chromatin</td></tr><tr><td>5</td><td>Fkh1</td><td>TEM1</td><td>Mitosis control</td></tr><tr><td>6</td><td>Ndd1, Fkh2, Mcm1</td><td>CLB2, ACE2, SWI5, CDC20</td><td>Mitosis control</td></tr><tr><td>7</td><td>Ace2, Swi5</td><td>CTS1, EGT2</td><td>Cytokinesis</td></tr></tbody></table>

<table><tr><td>8</td><td>Mcm1</td><td>MCM3, MCM6, CDC6, CDC46</td><td>Prereplicati on complex formation</td></tr><tr><td>9</td><td>Mcm1</td><td>STE2, FAR1</td><td>Mating</td></tr></table>

Cherepinsky et al. [7] defined a notation to represent the resulting cluster sets and a scoring function to aid in their comparison. Each cluster set is written as:

$$ \{x \to \{\{y_1, z_1\}, \{y_2, z_2\}, \dots, \{y_{n_x}, z_{n_x}\}\}\}_{x=1}^{\text{# of groups}} $$
where *x* denotes the group number as described in Table 1, *n*<sub>x</sub> is the number of clusters the members of group *x* appear in, and for each cluster *j* ∈ {1, ..., *n*<sub>x</sub>} there are *y*<sub>j</sub> genes from group *x* and *z*<sub>j</sub> genes from other groups in Table 1. A value of * for *z*<sub>j</sub> denotes that cluster *j* contains additional genes, although none of them are cell-cycle genes. The cluster set can then be scored as follows:

$$ \begin{aligned} \text{FP}(\gamma) &= \frac{1}{2} \sum_{x} \sum_{y_j \cdot z_j}^{n_x} \\ \text{FN}(\gamma) &= \sum_{x} \sum_{\substack{1 \le j < k \le n_x \\ 1 \le j \le k \le n_x}} y_j \cdot y_k \\ \text{Error score}(\gamma) &= \frac{\text{FP}(\gamma) + \text{FN}(\gamma)}{2} \end{aligned} $$

We have compared the error rates of M-BILCOM to those of AutoClass [24] and BILCOM [1] applied to the “perturbed” yeast data set. First, we applied AutoClass [24] to the mixed categorical and numerical yeast data set. Table 2 shows the results.

<table><caption>Table 2. Clustering results of AutoClass.</caption><thead><tr><th>Cluster</th><th>Genes</th></tr></thead><tbody><tr><td>1</td><td>CLN1, CLN2, GIC1, GIC2, MSB2, RSR1, BUD9, MNN1, OCH1, EXG1, KRE6, CWP1, CLB5, CLB6, RAD51, CDC45, HTB1, HTA2, HHO1, TEL2</td></tr><tr><td>2</td><td>ARP7, TEM1, CLB2, ACE2, SWI5, CDC20, CTS1, EGT2, MCM3, MCM6, CDC6, CDC46, STE2</td></tr><tr><td>3</td><td>RNR1, RAD27, CDC21, DUN1, MCM2, HTB2, HTA1, HHF1, HHT1, FAR1</td></tr></tbody></table>

Given the hypothesis in Table 1 and the set of AutoClass results shown in Table 2, the resulting clusters with the error score can be written as follows, according to the error rate introduced by Cherepinsky et al. [7]:

```
{1->{\{11,9\}},
2->{\{4,16\},{5,5}},
3->{\{3,17\},{2,8}},
4->{\{1,19\},{1,12},{2,8}},
5->{\{1,12\}},
6->{\{4,9\}},
7->{\{2,11\}},
8->{\{4,9\}},
9->{\{1,12\},{1,9}}
}.
FP = 265
FN = 32
Error = 297
```

We have also applied BILCOM [1] to the mixed categorical and numerical yeast data set. Table 3 shows the results.

<table><caption>Table 3. Clustering results of BILCOM using as numerical similarity metric between objects the Pearson Correlation Coefficient [7] and a max value for φ of 7.</caption><thead><tr><th>Cluster</th><th>Genes</th></tr></thead><tbody><tr><td>1</td><td>RSR1, HHT1, ARP7, BUD9, CTS1</td></tr><tr><td>2</td><td>KRE6, CWP1</td></tr><tr><td>3</td><td>RNR1, CDC45, MCM3, CDC46, MCM2</td></tr><tr><td>4</td><td>EXG1, EGT2</td></tr><tr><td>5</td><td>MCM6, CDC6</td></tr><tr><td>6</td><td>HHF1, HTB2, HTA2</td></tr><tr><td>7</td><td>HTB1, HTA1, HHO1</td></tr></tbody></table>
<table><tr><td>8</td><td>GIC1, TEL2, GIC2, MSB2</td></tr><tr><td>9</td><td>FAR1, STE2, ACE2, SWI5, TEM1</td></tr><tr><td>10</td><td>RAD27, CDC21, DUN1</td></tr><tr><td>11</td><td>CLN2, RAD51, MNN1, CLN1, CLB6, OCH1, CLB5, CLB2, CDC20</td></tr></table>

Given the hypothesis in Table 1 and the set of BILCOM results shown in Table 3, the resulting clusters with the error score can be written as follows, according to the error rate introduced by Cherepinsky et al. [7]:

<table><tr><td>{1->{4,4},{1,3},{1,1},{2,1},{2,0}},</td><td>FP = 49</td></tr><tr><td>2->{3,0},{3,2},{3,5}},</td><td>FN = 47+13+24</td></tr><tr><td>3->{3,0},{2,1}},</td><td>Error = 133</td></tr><tr><td>4->{2,3},{1,2},{1,4}},</td><td></td></tr><tr><td>5->{1,4}},</td><td></td></tr><tr><td>6->{2,3},{2,7}},</td><td></td></tr><tr><td>7->{1,4},{1,1}},</td><td></td></tr><tr><td>8->{2,0},{2,3}},</td><td></td></tr><tr><td>9->{2,3}} .</td><td></td></tr></table>

We have also applied M-BILCOM to the mixed categorical and numerical yeast data set. Table 4 shows the results.

<table><caption>**Table 4. Clustering results of M-BILCOM using as numerical similarity metric between 2 objects the Pearson Correlation Coefficient [7] and a max value for φ of 7.**</caption><thead><tr><th>Cluster</th><th>Genes</th></tr></thead><tbody><tr><td>1</td><td>RSR1, BUD9, CTS1</td></tr><tr><td>2</td><td>KRE6, ARP7, HHT1, CWP1</td></tr><tr><td>3</td><td>RNR1, CDC45, MCM3, STE2, CDC46, MCM2</td></tr><tr><td>4</td><td>EXG1, EGT2</td></tr><tr><td>5</td><td>MCM6, TEM1, CDC6</td></tr><tr><td>6</td><td>HHF1, HTB2, HTA2</td></tr><tr><td>7</td><td>HTB1, HHO1, HTA1</td></tr><tr><td>8</td><td>GIC1, TEL2, GIC2, MSB2</td></tr><tr><td>9</td><td>FAR1, ACE2, CDC20, SWI5</td></tr><tr><td>10</td><td>RAD27, CDC21, MNN1, DUN1, RAD51</td></tr><tr><td>11</td><td>CLN2, CLN1, CLB6, CLB5, OCH1, CLB2</td></tr></tbody></table>

Given the hypothesis in Table 1 and the set of M-BILCOM results shown in Table 4, the resulting clusters with the error score can be written as follows, according to the error rate introduced by Cherepinsky et al. [7]:

<table><tr><td>{1->{3,3},{2,2},{2,1},{1,1},{2,2},{1,4}},</td><td>FP = 38</td></tr><tr><td>2->{4,1},{3,3}},</td><td>FN = 35+49</td></tr><tr><td>3->{3,0},{3,0}},</td><td>Error = 122</td></tr><tr><td>4->{2,2},{1,2},{1,3}},</td><td></td></tr><tr><td>5->{1,2}},</td><td></td></tr><tr><td>6->{3,1},{1,5}},</td><td></td></tr><tr><td>7->{1,2},{1,1}},</td><td></td></tr><tr><td>8->{2,4},{2,1}},</td><td></td></tr><tr><td>9->{1,5},{1,3}} .</td><td></td></tr></table>

The error rates are summarized in table 5 below. The M-BILCOM error rate is lower than BILCOM and AutoClass.

<table><caption>**Table 5. Comparative error rates of algorithms applied to the "perturbed" yeast data set.**</caption><thead><tr><th>Clustering Tool</th><th>Cherepinsky Error rate</th></tr></thead><tbody><tr><td>M-BILCOM</td><td>122</td></tr><tr><td>BILCOM</td><td>133</td></tr><tr><td>AutoClass</td><td>297</td></tr></tbody></table>

# 6. EXPERIMENTS ON SIMULATED DATA

We generated artificial data sets that simulate the results by Spellman et al [23] who showed that in each cluster there is a consistent pattern of numerical attribute values (NAs) that appear frequently and that different CAs are characteristic of different clusters. We used numerical data derived from gene expression studies on the yeast *Saccharomyces cerevisiae*. These data sets were produced at Stanford to study the yeast cell cycle across time and under various experimental conditions and are available from the SGD database [9, 23]. The data set contained 6,200 genes. The purpose of our simulation was to assign CAs to each gene based on the numerical gene expression data [9], in such a manner that the assignment of CAs simulates knowledge about the role of genes in the yeast cell cycle.

We assigned 6 CAs on each gene based on the NAs, representing the genes' action during cell cycle. The assignment of the CAs followed a pattern that simulates existing knowledge on the role of genes in the yeast cell cycle. The assigned CAs split the objects into a number of well-defined groups, which we attempt to retrieve using clustering; thus, a different set of attribute values had to be used for each group. This simulates the results by Spellman et al, who showed that in each cluster there is a consistent pattern of NAs that appear frequently and that different CAs are characteristic of different clusters [23]. We assigned the 6 CAs using the following strategy: (1) The first CA split the genes into cell cycle phases and has the values G1, S, G2, M, M/G1, or unknown. This CA was set for each gene based on the experimental point at which the gene reaches its peak expression level, indicating what cell cycle phase it is likely to be involved in. This simulates the cell cycle phases as they are derived by Spellman et al and the genes that are likely to be involved in each phase. (2)(3) The second and third CAs were set for each gene based on whether the gene's expression level peaks at the phase of the cell cycle at which it is active. The second CA, which can take 6 values (A,B,C,D,E,unknown), simulates an overall process like *DNA replication* or *transport of essential minerals and organic compounds across the cell membrane*. The third CA, which can take 11 values (F,G,H,I,J,K,L,M,N,O,unknown), simulates a more specific function like *DNA polymerases* or *nucleotide synthesis* or *initiation of DNA synthesis*. The purpose of the second and third CAs was to further subdivide the groups created by the first CA into subgroups. The first three CAs are influential enough to classify each gene in a cluster. Thus, the clusters that we will retrieve are based primarily on the first three CAs. (4) The fourth CA was set for each gene based on whether the gene is observed to reach its peak expression level right before the G1 stage. This CA simulates the *start of mitosis* and can take 3 values (high,low,unknown). (5) The fifth CA was set for each gene based on whether the gene is observed to reach its peak expression level at the end of the cell cycle. This CA simulates the *exit from mitosis* and can take 3 values (high,low,unknown). (6) Finally, the sixth CA was set for each gene based on whether the gene is observed to reach its peak expression level right before the S stage. This CA can take 3 values (high,low,unknown). The fourth to sixth CAs on their own may or may not classify each gene into a clear group.

Furthermore, we perturbed the CAs to simulate noise in the resulting data set. Our aim was to use M-BILCOM to retrieve the known underlying cluster structure effectively. A significant outcome of our experiments was to show that given the genes whose CAs were not perturbed in the simulation (most of which
are likely to have high CVs) a fair number of genes were assigned to the correct clusters to which they were categorically similar and were not assigned to the incorrect clusters to which they might be numerically similar. The basis for this is that most of these genes had a high confidence overall. Another significant outcome of our experiments was to show that given the genes whose CAs were perturbed in the simulation (most of which are likely to have low CVs) a fair number of genes were assigned to the correct clusters to which they were likely to be numerically similar and were not assigned to the incorrect clusters to which they were categorically similar. The basis for this is that most of these genes had a low confidence overall.

Many CAs were perturbed and the attribute values in the data set were assigned CVs between 0.1 and 1.0. For this purpose, for each CA we generated a *limit* in a range from 0.4 to 1.0 and then, generated a random number *ρ* from 0.0 to 1.0. If *ρ* exceeded the limit, then we perturbed the CA by assigning it a value taken randomly from the set of possible values for that attribute. The CV for the CA was set equal to the *limit*, regardless of whether it was actually perturbed or not. This simulates the uncertainty that exists on current knowledge and that is expressed in SGD as GO evidence codes [8, 12, 20]. In the produced data set 2,024 data objects had their original attribute values modified out of 6100. All CAs on all data objects were assigned a CV between 0.4 and 1.0 and objects with lower CVs were more likely to have been modified than objects with higher CVs.

We clustered the simulated data set into 20 clusters. This number of clusters was derived from the number of combinations of values that the first three CAs of each object can take in our simulated data and because this number of clusters allowed the algorithm to converge in a reasonable amount of time. Table 6 shows the statistics for all 20 clusters, though we ignore the results for clusters whose size was too small.

What is most noteworthy in Table 6 are clusters 8, 11, 15, because all of their data objects had their CAs modified during our simulation (see column 4). As can be seen, many of the data objects in these clusters had original values for their first 3 CAs consistent with the most representative CAs {A,B,C} for the cluster (see columns 5,6). Furthermore, all of the objects with original values for their first 3 CAs equal to the most representative CAs {A,B,C} for the cluster, were objects whose CAs had been modified during the simulation to different values (see column 7).

<table><caption>Table 6. Results for clustering the data set into 20 clusters. We do not show results for clusters whose size was too small.</caption><thead><tr><th></th><th></th><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Cluster #</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>Number of objects in the cluster</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>Most common values {A,B,C} on the objects' first 3 CAs</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>Ratio X of objects in the cluster that had CAs modified during the simulation</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td>Ratio of X that had an original CA very close to {A,B,C}</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>6</td><td>Ratio P of objects in the cluster that had an original CA very close to {A,B,C}</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7</td><td>Ratio of P that had its CAs modified during the simulation</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>8</td><td>Number of merged second level subclusters</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><tr><td>3</td><td>724</td><td>{G2,C, J}</td><td>177/724</td><td>111/177</td><td>672/724</td><td>111/672</td><td>121</td></tr><tr><td>4</td><td>317</td><td>{G1,A, F}</td><td>83/317</td><td>48/83</td><td>302/317</td><td>48/302</td><td>44</td></tr><tr><td>5</td><td>709</td><td>{S,B,H}</td><td>94/709</td><td>24/94</td><td>684/709</td><td>24/684</td><td>183</td></tr><tr><td>6</td><td>218</td><td>{M,D, M}</td><td>50/218</td><td>26/50</td><td>198/218</td><td>26/198</td><td>59</td></tr><tr><td>8</td><td>66</td><td>{MG1, E,N}</td><td>66/66</td><td>22/66</td><td>22/66</td><td>22/22</td><td>9</td></tr><tr><td>11</td><td>71</td><td>{MG1, E,N}</td><td>71/71</td><td>27/71</td><td>27/71</td><td>27/27</td><td>3</td></tr><tr><td>15</td><td>74</td><td>{MG1, E,N}</td><td>74/74</td><td>24/74</td><td>24/74</td><td>24/24</td><td>2</td></tr><tr><td>20</td><td>333</td><td>{S,B,H} and {S,B,I}</td><td>180/333</td><td>148/180</td><td>260/333</td><td>148/260</td><td>13</td></tr></table>

Another interesting result is cluster 2, in which the most prominent genes are those with the values {MG1, E, N} for their first 3 CAs. 202/1102 objects had their CAs modified to a totally different value, but were, nevertheless, assigned to the correct cluster because they had low CVs (see column 7). This shows that our algorithm can overcome a poor prior that is likely to be incorrect and can still produce correct results by using numerical clustering instead. In this cluster, from all objects assigned to it that had their CAs modified (305/1186, as shown in column 4) 202/305 had CA values of {MG1, E, N} or {MG1, E, O} (see column 5). The total cluster size was 1186 and consisted of 180 merged second level subclusters (see column 8). Four of the merged clusters contained a vast majority of objects with modified CAs. All of these clusters had a substantial portion - or a majority - of objects with original CA values of {MG1, E, N}.

# 7. VALIDATION OF PREDICTIONS

## 7.1 First Significance Metric

Our strategy for validating the accuracy of the functional predictions is to reclassify certain genes' CAs as 'Unknown' before the clustering process and we aim to predict the correct genes' cellular roles using the cluster CAs pointed out by the SM. The CAs to be set to 'Unknown' were chosen to have a high average(CV) over all their occurrences in the cluster, because these are primarily the ones that we would like to be able to predict correctly. The process described next helps us to determine how likely genes are to be assigned their correct CAs.

We iterated over the genes in the cluster with CAs labeled as 'Unknown'. To assess the effectiveness of the technique, we verified that the original CAs of these genes correlated better to the cluster CAs with low M-values - that are pointed out by our SM - than those with high M-values. This correlation signified the likelihood that the genes' CAs labeled as 'Unknown' would be assigned their original values, by using CAs with low M-values that are pointed out by our SM. A relatively large number of genes' CAs labeled as 'Unknown' should be likely to be re-assigned their original values using CAs with low M-values in the cluster, because a low M-value indicates that a CA occurs frequently amongst the cluster's genes and that a CA is likely to be correct.

We initially clustered the yeast data into 5 clusters. Table 7 describes some CAs that were pointed out in all 5 clusters by the
SM, after the CAs with the highest average(CV) in each cluster were set to 'Unknown' and the set was clustered.

<table><caption>**Table 7. CAs pointed out in 5 clusters as the most significant. The CAs pointed out in clusters 1-5 as having the lowest M-values - the most representative ones for the cluster - correlated with the CAs in the original cluster that were set to 'Unknown'**</caption><thead><tr><th>Cluster</th><th>Description</th></tr></thead><tbody><tr><td>1</td><td>vacuolar membrane, ubiquitin-specific protease, small nuclear ribonucleoprotein complex, glycolysis, 3'-5' exoribonuclease, cytosolic small ribosomal subunit, lipid particle, cytosolic large ribosomal subunit, tricarboxylic acid cycle</td></tr><tr><td>2</td><td>rRNA modification, ATP dependent RNA helicase, nuclear pore, structural molecule, small nucleolar ribonucleoprotein complex, snoRNA binding, mediator complex</td></tr><tr><td>3</td><td>cytosol, proteasome endopeptidase, non-selective vesicle fusion, translation initiation factor</td></tr><tr><td>4</td><td>transcription initiation from Pol II promoter, general RNA polymerase II transcription factor, nucleus</td></tr><tr><td>5</td><td>endoplasmic reticulum membrane, component:endoplasmic reticulum</td></tr></tbody></table>

We have also performed these tests on the yeast data producing 35 and 71 clusters. We provide a concrete example of the utility of our technique for 35 clusters, by focusing on the second cluster having 224 genes. In the original clustering, the following CAs were pointed out as having the lowest M-values: function:transcription regulator, component:nucleus, process:transport, process:cell growth and/or maintenance, process:metabolism, function:transporter, nucleus(a specific, granular annotation). We focus on the 2 most significant (representative) CAs for the cluster:

1) *component:nucleus* occurred in 160 genes in this cluster and had an average(CV) of 1.0 across all genes. Some genes with this annotation were YOR064C, YBR247C, YDR205W, YDR206W, YFR023W, YKL117W, YPR196W, YOR141C, YOL116W, YOR294W, YDR076W, YFR037C, YNL148C, YDR510W, YLR074C, YPL049C, YDL064W, YML109W, YNL016W.

2) *nucleus(a specific, granular annotation)* occurred in 82 genes in this cluster and had an average(CV) of 0.904878 across all genes. Some genes with this annotation were YBR247C, YDR205W, YDR206W, YFR023W, YKL117W, YPR196W, YOL116W, YOR294W, YDR076W, YFR037C, YNL148C, YLR074C.

In different trials we set all CAs of many genes in which these two values occurred originally to 'Unknown' and then re-clustered the data set into 35 clusters. Using the results, we were able to predict correctly that these genes should be annotated as either *component:nucleus* or *nucleus(a granular annotation)* by extracting the CAs with lowest M-values. This means that the SM predicted these genes to have their original correct CAs, after setting them to 'Unknown', re-clustering the data set and extracting the CAs with lowest M-values.

Figure 6 illustrates the results obtained for a CA with value A (component:nucleus) that initially occurred in 160 objects in the cluster. As an increasing number of occurrences of value A in the cluster were set to 'Unknown' and the set was re-clustered, the

same value A still qualified as one of the most significant values in the cluster and remained applicable to a relatively large number of objects (i.e. genes).

<figure><img src="image_78.png" /><figcaption>**Figure 6. Results for different trials of setting occurrences of 'component:nucleus' to 'Unknown' and re-clustering the set.**</figcaption></figure>

## 7.2 Second Significance Metric

Our strategy for validating the accuracy of the functional predictions was to reclassify the CAs of certain genes as 'Unknown' before the clustering process and attempt to predict the correct genes' cellular roles using the cluster CAs pointed out by the SM. The CAs set to 'Unknown' were primarily ones with a high average(CV) over all their occurrences in the cluster, because these were primarily the ones that we would like to be able to predict correctly. The process described next helped us to determine how likely genes were to be assigned their correct CAs.

We iterated over the CAs in the cluster that were labeled as 'Unknown'. To assess the effectiveness of the technique, we verified that the original CAs of these genes correlated better to the cluster CAs pointed out as having the highest significance. CAs pointed out as highly significant were ones occurring frequently across the cluster's genes with high avg(CV). This correlation signified the likelihood that the genes' CAs labeled as 'Unknown' would be re-assigned their original values, by using CAs that were pointed out by the SM. A reasonable number of genes' CAs should be likely to be assigned their original values using the CAs pointed out by the SM.

We initially clustered the yeast data into 35 clusters, each of which contained a number of smaller subclusters. The second level subclusters pointed out by the SM as significant enough were those containing genes:

1) YHR053C (SM>1; 80% of genes not having CV high enough; 23 genes total),

2) YDL179W (SM>1; 96% of genes not having CV high enough; 104 genes total),

3) YKL182W (SM>0.58; 94% of genes not having CV high enough; 210 genes total),

4) YKR075C (SM>0.44; 96% of genes not having CV high enough; 27 genes total),

5) YLR342W (SM>0.10; 91% of genes not having CV high enough; 22 genes total),

6) YMR246W (SM>0.88; 75% of genes not having CV high enough; 61 genes total),

7) YJL079C (SM>0.06; 75% of genes not having CV high enough; 4 genes total),

8) YCR005C (SM>0.58; 63% of genes not having CV high enough; 470 genes total),
9) YMR186W (SM>0.06; 50% of genes not having CV high enough; 8 genes total),

10) YBR029C (SM>1; 0% of genes not having CV high enough; 1 gene total),

The reason other subclusters yielded low significance was because a majority of their genes had high average(CV) over their CAs, so most genes were assigned on the basis of categorical similarity rather than on the basis of numerical similarity. Thus the dominant factor in the significance metric was low and the overall result was low.

We next needed to identify the CAs in these clusters with the highest average(CV) throughout the entire cluster. We identified the following CAs, for each of the subclusters listed above:

1) copper binding, avg(CV) 0.5 ; cytosol, avg(CV) 1.0

2) cell cycle, avg(CV) 0.5

3) fatty-acid synthase complex, avg(CV) 1.0 ; fatty acid biosynthesis, avg(CV) 1.0 ; vacuole (sensu Fungi), avg(CV) 0.8 ; vacuole inheritance, avg(CV) 0.8 ; thiol-disulfide exchange intermediate, avg(CV) 0.5 ; plasma membrane, avg(CV) 1.0 ; tricarboxylic acid cycle, avg(CV) 1.0

4) cytoplasm, avg(CV) 1.0

5) 1,3-beta-glucan synthase, avg(CV) 0.55

6) long-chain-fatty-acid-CoA-ligase, avg(CV) 0.55 ; lipid metabolism, avg(CV) 0.75 ; lipid particle, avg(CV) 1.0

7) nuclear membrane, avg(CV) 1.0

8) glyoxylate cycle, avg(CV) 1.0 ; peroxisomal matrix, avg(CV) 0.95 ; folic acid and derivative biosynthesis, avg(CV) 0.95 ; pantothenate biosynthesis, avg(CV) 0.8 ; allantoin catabolism, avg(CV) 0.8 ; purine nucleotide biosynthesis, avg(CV) 0.95 ; helicase, avg(CV) 0.5 ; spore wall assembly, avg(CV) 0.8 ; RAB-protein geranylgeranyltransferase, avg(CV) 0.55 ; protein amino acid geranylgeranylation, avg(CV) 1.0 ; RAB-protein geranylgeranyltransferase complex, avg(CV) 1.0

9) response to stress, avg(CV) 0.75

10) phosphatidate cytidylyltransferase, avg(CV) 1.0 ; phosphatidylserine metabolism, avg(CV) 1.0 ; mitochondrion, avg(CV) 1.0

In different trials we set the CAs of many genes in which these values originally occurred to ‘Unknown’ in each of these clusters and re-clustered the entire data set. The same values were still pointed out by the SM as highly significant in the corresponding clusters. This encouraged us to re-assign the original values to the genes whose CAs were set to ‘Unknown’, which we interpret as a success of our approach.

## 7.3 Assessment of Clustering Stability

The GO Evidence Codes (GOECs) form a loose hierarchy from strong evidence to weak evidence. The top GOECs in the hierarchy represented by ‘TAS’ and ‘IDA’ are mapped to a CV of 1.0 while the bottom GOECs ‘ND’ and ‘NR’ are mapped to 0.0. We want to show that all other GOECs falling between these extremes in the hierarchy are assigned a CV that allows objects to be partitioned the best way in the clustering process. We used the simulated yeast data set from Section 6 to determine how sensitive the final results are to changes in the spacing between the CVs.

We did a trial using GOECs from the top 3 hierarchy scales: TAS/IDI, IMP/IGI/IPI, ISS/IEP. We set a randomly chosen 1/3 of the CVs in the data set to TAS/IDI, 1/3 to IMP/IGI/IPI and 1/3 to ISS/IEP. Then we set all CVs of objects falling in 5 classes A-E in the data set to the middle GOEC of IMP/IGI/IPI. By mapping this set of GOECs to corresponding CVs of 1.0, 0.8, 0.5, the objects

belonging in classes A-E were slightly better partitioned from other objects than when mapping to CVs of 1.0, 0.9, 0.6.

Then we repeated this trial by using GOECs from the bottom 3 hierarchy scales: ISS/IEP, NAS, IEA. By mapping this set of GOECs to corresponding CVs of 0.5, 0.2, 0.1, the objects belonging in classes A-E were slightly better partitioned from other objects than when mapping to CVs of 0.5, 0.3, 0.2.

We also assess the stability of the clustering to perturbations in the data, to determine the reproducibility of the results [26, 27]. Our ‘perturbed’ data includes changes in the spacing between the CVs and different perturbations of the simulated yeast data set. We then re-cluster the perturbed data and compute indices - such as R-index and D-index [27] - to determine how much the clustering has changed. R-index measures the proportion of pairs of objects within a cluster for which the members of the pair remain together in the perturbed re-clustered data [27]. D-index measures the number of omissions and additions comparing an original cluster to a best-matching cluster in the perturbed re-clustered data [27]. The R-index values were greater than 0.97 and the D-index values were less than 4.5, for several trials involving different mappings of GOECs to CVs and different perturbations of the simulated yeast data set. This indicates high reproducibility of the clustering results.

## 8. DISCUSSION: USING SIGNIFICANCE METRICS FOR DERIVING POTENTIAL GENE FUNCTIONS

Biologists will find this method useful for deriving hints about potential functions of genes or proteins. The hints that are derived as to a gene's function can later be validated experimentally. This will save time and money from the experimentalists' side. In our experiments with the yeast cell cycle data set, the utility of the significance metrics (SMs) is especially evident from the fact that the vast majority of genes in each cluster or subcluster analyzed had all CAs set to 'Unknown' meaning that no knowledge exists. For example, when analyzing the subcluster containing YHR053C using the second SM, only 6 out of 20 genes had some kind of CA, while the other 14 genes had CAs set to 'Unknown'. Our SM could point out the most representative CAs that are likely to be applicable to the other 14 genes and these functional hints can be tested experimentally.

M-values are useful for identifying the most representative CAs in clusters with a plethora of CAs that have high CVs. M-values allow one to identify the CAs in this pool that appear frequently (with a low P1-value) so as to apply them to other genes. In our experiments with the yeast cell cycle data set we realised that although 1185 second level subclusters had been produced in total, most of those (1175 = 1185-10 subclusters) had a majority of genes with an average CV over their CAs that was considered high. These genes were assigned to the clusters on the basis of categorical rather than numerical similarity, according to step 3. M-values could be utilized on these 1175 subclusters, or could be utilized on the overall clusters produced as an end result by the algorithm (the total number of clusters was 5, 35 and 71).

The second SM applies primarily for identifying the most representative CAs in clusters with a plethora of CAs that have low CVs. The second SM allows us to identify the few CAs that have high CVs in these clusters, so as to apply them to other genes. In our experiments, only 10 second level subclusters out of 1185 in total, had a majority of genes with an average CV across their CAs that was considered low enough. These genes were
assigned to the clusters on the basis of numerical rather than
categorical similarity, according to step 3. The second SM could
be utilized on these 10 subclusters.

Future work will include justifying on a theoretical basis the
mapping of GO Evidence Codes to CVs. We will be applying this
algorithm to more gene expression data sets for organisms on
which low quality CAs exist. Furthermore, we will be developing
more significance metrics for the M-BILCOM clustering results.

9. CONCLUSION

When clustering low quality data with uncertainties about the
data's correctness, we need to develop our ability to integrate data
from various sources, including numerical data and categorical
data. Furthermore, we need to be able to claim that what we see in
a clustering analysis is more reliable or less reliable and,
therefore, may or may not be a strong basis for making decisions.
In this paper we have described the novel M-BILCOM clustering
algorithm for mixed numerical and uncertain categorical data sets
that incorporates CAs and CVs representing certainty about the
correctness of the CAs. This clustering algorithm inspired us to
define two new significance metrics for extracting from each
cluster the most significant CAs, that form a strong basis for
deriving conclusions about the CAs of other objects in the cluster.
We showed that these significance metrics can be successfully
used for finding the most significant CAs in a cluster. For
genomic data sets we applied the significant CAs to other genes in
the cluster for functional prediction. We experimented with this
clustering tool on highly noisy yeast data sets for which the
correct results were known. We showed that M-BILCOM can
reliably identify the cluster structure in simulated data sets.

10. REFERENCES

[1] Andreopoulos, B., An, A. and Wang, X. (2005) BILCOM: Bi-level Clustering of Mixed Categorical and Numerical Biological Data. Technical report CS-2005-01. York University. http://www.cs.yorku.ca/techreports/

[2] Andreopoulos, B., An, A. and Wang, X. (2004) MULIC: Multi-Layer Increasing Coherence Clustering of Categorical Data Sets. Technical report CS-2004-07. York University.

[3] Andreopoulos, B., An, A. and Wang, X. (2003) Significance Metrics for Clusters of Mixed Numerical and Categorical Yeast Data. Technical report CS-2003-12. York University.

[4] Adryan B. and Schuh R. (2004) Gene ontology-based clustering of gene expression data, Bioinformatics, Nov 2004; 20: 2851 - 2852.

[5] Ben-Dor A., Shamir R., Yakhini Z. (1999) Clustering Gene Expression Patterns. Journal of Computational Biology 6(3/4): 281-297.

[6] Brown M.P.S. Grundy W.N., Lin D., Cristianini N., Sugnet C.W., Furey T.S., Manuel A., Haussler D. Knowledge-based analysis of microarray gene expression data by using support vector machines. PNAS 97(1), 262-267, 2000.

[7] Cherepinsky V., Feng J., Rejali M. and Mishra B. (2003) Shrinkage-Based Similarity Metric for Cluster Analysis of Microarray Data. PNAS 100(17): 9668-9673.

[8] Dwight SS, Harris MA, Dolinski K, Ball CA, Binkley G, Christie KR, Fisk DG, Issel-Tarver L, Schroeder M, Sherlock G, Sethuraman A, Weng S, Botstein D, Cherry JM. (2002) Saccharomyces Genome Database provides secondary gene annotation using the Gene Ontology. *Nucleic Acids Research* 30: 69-72.

[9] Eisen, M.B. & Brown, P.O. (1999) DNA arrays for analysis of gene expression. *Methods Enzymol.* 303, 179-205.

[10] Eisen MB, Spellman PT, Brown PO, Botstein D. (1998) Cluster analysis and display of genome-wide expression patterns. *Proc Natl Acad Sci USA.* 95(25):14863-8, 1998.

[11] Fasulo D. (1999) An Analysis of Recent Work on Clustering Algorithms, Technical Report # 01-03-02, Department of Computer Science & Engineering, University of Washington.

[12] The Gene Ontology Consortium (2001). Creating the gene ontology resource: design and implementation. *Genome Research* 11: 1425-1433.

[13] Goebel, M. & Gruenwald, Le (1999). A survey of data mining and knowledge discovery software tools. *ACM SIGKDD Explorations* 1, 20-33.

[14] Golub, T. R. et al. (1999) Molecular classification of cancer: class discovery and class prediction by gene expression monitoring. *Science* 286, 531-537.

[15] Grambeier J., Rudolph A. (2002) Techniques of Cluster Algorithms in Data Mining. *Data Mining and Knowledge Discovery* 6: 303-360.

[16] Guha S., Rastogi R., Shim K. (2000). ROCK: A Robust Clustering Algorithm for Categorical Attributes. *Information Systems* 25(5): 345-366.

[17] Hartigan, J. A. (1975) Clustering algorithms. (John Wiley and Sons, New York, 1975).

[18] Huang Z. (1998) Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values. *Data Mining and Knowledge Discovery* 2(3): 283-304.

[19] Huang, Z. (1997) Clustering Large Data Sets with Mixed Numeric and Categorical Values. *Knowledge discovery and data mining: techniques and applications*. World Scientific.

[20] Lord P.W., Stevens R.D., Brass A. and Goble C.A. (2003). Investigating semantic similarity measures across the Gene Ontology: the relationship between sequence and annotation. *Bioinformatics* 19: 1275-83.

[21] Pasquier C., Girardot F., Jevardat de Fombelle K., and Christen R. (2004) THEA: Ontology driven analysis of microarray data. Bioinformatics, Nov 2004; 20: 2636 - 2643.

[22] Slonim D.K., Tamayo P., Mesirov J.P., Golub T.R., and Lander E.S. Class prediction and discovery using gene expression data. *Proceedings of the Fourth Annual Conf. on Computational Molecular Biol. (RECOMB) 2000*, 263-272.

[23] Spellman, P.T. et al. Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces Cerevisiae by microarray hybridization. Mol Biol Cell 9, 3273-97, 1998.

[24] Stutz J. and Cheeseman P. (1995) Bayesian Classification(AutoClass): Theory and results. Advances in Knowledge Discovery and Data Mining, 153-180, Menlo Park, CA, AAAI Press.

[25] Wu L.F., Hughes T.R., Davierwala A.P., Robinson M.D., Stoughton R. and Altschuler S.J. (2002). Large-scale Prediction of Saccharomyces Cerevisiae Gene Function Using Overlapping Transcriptional Clusters. *Nature Genetics* 31:255-265.

[26] Kerr MK, Churchill GA. Bootstrapping cluster analysis: assessing the reliability of conclusions from microarray experiments. Proc Natl Acad Sci USA. 2001 July; 98(16):8961-5.

[27] McShane LM, Radmacher MD, Freidlin B, Yu R, Li MC, Simon R. Methods for assessing reproducibility of clustering patterns observed in analyses of microarray data. *Bioinformatics.* 2002 Nov;18(11):1462-9.
Data Cleaning Using Belief Propagation

Fang Chu Yizhou Wang D.Stott Parker Carlo Zaniolo

University of California, Los Angeles
Computer Science Department

{fchu,wangyz,stott,zaniolo}@cs.ucla.edu

ABSTRACT

Effective data cleaning is critical in many applications where the quality of data is poor due to missing values or inaccurate values. Fortunately, a wide spectrum of applications exhibit strong dependencies between data samples, and such dependencies can be used very effectively for cleaning the data. For example, the readings of nearby sensors are generally correlated, and proteins interact with each other when performing crucial functions. We propose a data cleaning approach, based on modeling data dependencies with Markov networks. Belief propagation is used to efficiently compute the marginal or maximum posterior probabilities, so as to infer missing values or to correct errors. To illustrate the benefits and generality of the technique, we discuss its use in several applications and report on the data quality and improvements so obtained.

1. INTRODUCTION

Improving data quality is the key for the success of many
applications including data mining. This paper focuses on
two data cleaning tasks: filling in missing values and dis-
ambiguating. These two tasks can be treated in a unified
framework using belief propagation.

The observation essential to the solution is that a wide
spectrum of scenarios exhibit dependencies between data
samples. For example, the readings of nearby sensors are
generally correlated, and proteins interact with each other
when performing crucial functions. Such dependencies can
be exploited for cleaning the data. We illustrate this using
two cases.

Incomplete Data

In sensor networks, where probing has to be minimized
due to power restrictions, data is often incomplete or some-
what outdated. For popular queries such as maximum/average
sensor readings, we need a cost-efficient way to infer un-
known or out-of-date values while probing the sensors as
little as possible.

To solve this problem, we can leverage the neighborhood
relationship, since sensor readings are correlated if the sen-
sors are geographically close. Even knowledge of far-away
sensors helps, because that knowledge can be propagated
via sensors deployed in between. By exploiting sensor cor-
relation, unprobed sensors can be accurately inferred, and
thus data quality can be improved.

Inaccurate Data

An example of inaccurate data is encountered in opti-
cal character recognition (OCR), a technique that trans-
lates pictures of characters into a machine readable encod-
ing scheme. Current OCR algorithms often translate two
adjacent letters “ ff ” into a “#” sign, or incur similar
systematic errors.

In the OCR problem, the objective is not to ignore or
discard noisy input, but to disambiguate legal words from
recognition errors. The error patterns in OCR may be re-
lated to the shape of individual characters, the adjacency of
characters, or illumination and positions. It is thus possible
to correct a substantial number of errors with the knowledge
of neighboring characters.

A common characteristic of the above two scenarios is
the presence of data dependency. We propose a unified ap-
proach that infers missing values or disambiguating by ex-
ploiting this data dependency. We first model local data
dependency by means of a graphical model, and then use
*Belief Propagation* [12] for efficient inference.

In section 2, we briefly describe a special form of graphi-
cal models, *pairwise Markov network*, and how to do infer-
ence using belief propagation. Then we address the above-
mentioned examples in sections 3 and 4. Paper concludes
with related work and discussions in Section 5.

2. BELIEF PROPAGATION ON MARKOV NETWORK

Markov networks have been successfully applied to many
problems in different fields, such as artificial intelligence [7]
and image analysis [10]. In this paper, we show that they
can also provide very useful tools for data cleaning.

2.1 Markov Network

The Markov network is a type of graphical models suitable
for modeling local dependencies. The Markov property [2]
ensures that the joint probability can be factored—a criti-
cal property of Markov networks since it leads to efficient
computations.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA

Copyright 2005 ACM 1-59593-160-0 /05/06 $5.00.
In many practical problems, we are mainly interested in are pairwise relationships among the variables. For this category of problem pairwise Markov networks can be used, and the joint probability of a graph configuration can be factored into:

$$P(\{x\}, \{y\}) = \frac{1}{Z} \prod_{(i,j)} \psi_{ij}(x_i, x_j) \prod_i \phi_i(x_i, y_i) \quad (1)$$

where {$x_i$} are random variables denoted by nodes in the Markov network, {$y_i$} the evidence of the corresponding random variables, Z a normalization factor. Compatibility function $\psi_{ij}(x_i, x_j)$ captures the “internal binding” between two neighboring nodes i and j, and compatibility function $\phi_i(x_i, y_i)$ can be interpreted as “external potential” from the external field. The product over (i, j) runs over all compatible neighbors.

Solving a Markov network involves two phases:

* The learning phase, a phase that builds up the graph structure of the Markov network, and learns the two types of potential functions, $\phi(\cdot)$'s and $\psi(\cdot)$'s, from the training data.

* The inference phase, a phase that estimates the marginal posterior probabilities or the local maximum posterior probabilities for each random variable, such that the joint posterior probability is maximized.

The inference phase can be solved using a number of methods, such as simulated annealing [4], mean-field annealing [8]. These methods either take an unacceptably long time to converge, or make oversimplified assumptions such as total independence between variables. We choose to use the Belief Propagation (BP) method, which has a computation complexity proportional to the number of nodes in the network, assumes only local dependencies, and has proved to be effective on a broad range of Markov networks.

## 2.2 Inference by Belief Propagation

Belief propagation (BP) is a powerful inference tool on Markov networks. For Markov chains and Markov networks without loops, BP is an exact inference method. Even for loopy networks, BP has been successfully used in a wide range of applications [5]. We give a short description of BP in this subsection.

The BP algorithm iteratively propagates “messages” in the network. Messages are passed between neighboring nodes only, ensuring the local constraints, as shown in Figure 1. The message from node i to node j is denoted as $m_{ij}(x_j)$, which intuitively tells how likely node i thinks that node j is in state $x_j$. The message $m_{ij}(x_j)$ is a vector of the same dimensionality as $x_j$.

There are two types of message passing rules:

* SUM-product rule, that computes the marginal posterior probability.

* MAX-product rule, that computes the maximum a posteriori probability.

For discrete variables, messages are updated using the

<figure><img src="image_79.png" /><figcaption>Figure 1: Message passing in a Markov network. Messages are defined by Eqs.(2) or (3) under two types of rules, respectively.</figcaption></figure>

SUM-product rule:

$$m_{ij}^{t+1}(x_j) = \sum_{x_i} \phi_i(x_i, y_i) \psi_{ij}(x_i, x_j) \prod_{k \in N(i), k \neq j} m_{ki}^t(x_i) \quad (2)$$

or the MAX-product rule,

$$m_{ij}^{t+1}(x_j) = \max_{x_i} \phi_i(x_i, y_i) \psi_{ij}(x_i, x_j) \prod_{k \in N(i), k \neq j} m_{ki}^t(x_i) \quad (3)$$

where $m_{ki}^t(x_i)$ is the message computed in the last iteration of BP, k runs over all neighbor nodes of i except node j.

BP is an iterative algorithm. When messages converge, the final belief $b(x_i)$ is computed. With the SUM-product rule, $b(x_i)$ approximates the marginal probability $p(x_i)$, defined to be proportional to the product of the local compatibility at node i ($\phi(x_i)$), and messages coming from all neighbors of node i:

$$b_i(x_i)_{SUM} = x_i \phi_i(x_i, y_i) \prod_{j \in N(i)} m_{ji}(x_i) \quad (4)$$

where $N(i)$ is the neighboring nodes of i.

If using the MAX-product rule, $b(x_i)$ approximates the maximum a posterior probability:

$$b_i(x_i)_{MAX} = \arg \max_{x_i} \phi_i(x_i, y_i) \prod_{j \in N(i)} m_{ji}(x_i) \quad (5)$$

For more theoretical details of the belief propagation and its generalization, we refer the reader to [12].

## 3. COST-EFFICIENT SENSOR PROBING

A key research issue in sensor networks is how to minimize communication. The challenge is how to probe a small number of sensors, and to effectively infer the unprobed sensors from the known ones.

Our approach here is to model a sensor network with a pairwise Markov network, and use BP to do inference. Each sensor is represented by a random variable in the Markov network. Sensor neighborhood relationships are determined by spatial positions. For example, one can specify a distance threshold so that sensors within the range are neighbors. Neighbors are connected by edges in the network.

In the rest of this section, we study a rainfall sensornet distributed over Washington and Oregon [6]. The sensor recordings were collected during 1949-1994. We use 167 sensor stations which have collected complete recordings during that period.
## 3.1 Problem Description

Since rain is a seasonal phenomena, we split the data by week and build a Markov network for each week.

We need to design the potential functions $\phi_i(x_i, y_i)$ and $\psi_{ij}(x_i, x_j)$ in Eq. (1) in order to use belief propagation. One can use Gaussian or its variants to compute the potential functions. But, in the sensornet we study, we find that the sensor readings are overwhelmed by zeroes, while non-zero values span a wide range. Clearly Gaussian is not a good choice for modeling such skewed data. Neither are mixtures of gaussian, due to limited data. Instead, we prefer to use discrete sensor readings in the computation. The way we discretize data is given in section 3.3.

The $\phi_i$ functions should tell how likely we observe a reading $y_i$ for a given sensor $x_i$. It is natural to use the likelihood function:

$$ \phi_i(x_i, y_i) = P(y_i|x_i) \qquad (6) $$

The $\psi_i$ functions specify the dependence of sensor $x_j$'s reading on its neighbor $x_i$.

$$ \psi_{ij}(x_i, x_j) = P(x_j|x_i) \qquad (7) $$

## 3.2 Problem Formulation

We give a theoretical analysis of the problem here. As we will see shortly, the problem fits well into the maximum a posteriori (MAP) estimation on a Markov chain solvable by belief propagation.

### Objective: MAP

Let $X$ to be the collection of all underlying sensor readings, $Y$ the collection of all probed sensors. Using Bayes' rule, the joint posterior probability of $X$ given $Y$ is:

$$ P(X|Y) = \frac{P(Y|X)P(X)}{P(Y)} \qquad (8) $$

Since $P(Y)$ is a constant over all possible $X$, we can simplify this problem of maximizing the posterior probability to be maximizing the joint probability

$$ P(X, Y) = P(Y|X)P(X) \qquad (9) $$

Eq.(9) is the objective function to be maximized, which is proportional to the maximum a posteriori probability.

### Likelihood

In a Markov network, the likelihood of the readings $Y$ only depends on the variables they directly connect to:

$$ P(Y|X) = \prod_{i=1}^{m} P(y_i|x_i) \qquad (10) $$

where $m$ is the number of probed sensors.

### Prior

Priors shall be defined to capture the constraints between neighboring sensor readings. By exploiting the Markov property of the sensors, we define the prior to involve only the first order neighborhood. Thus, the prior of a sensor is proportional to the product of the compatibility between all

neighboring sensors:

$$ P(X) \propto \prod_{(i,j)} P(x_j|x_i) \qquad (11) $$

### Solvable by BP

By replacing Eqs.(10) and (11) into the objective Eq.(9), we have the joint probability to be maximized:

$$ P(X, Y) = \frac{1}{Z} \prod_{(i,j)} P(x_j|x_i) \prod_{i=1}^{N} P(y_i|x_i) \qquad (12) $$

Looking back at the $\phi_i$ and $\psi_i$ functions defined in Eqs.(6) and (7), we see that the objective function is of the form:

$$ P(X, Y) = \frac{1}{Z} \prod_{(i,j)} \psi(x_i, x_j) \prod_{i=1}^{N} \phi(x_i, y_i) \qquad (13) $$

where $Z$ is a normalizing constant.

This is exactly the form in Eq.(1), where the joint probability over the pairwise Markov network is factorized into products of localized potential functions. Therefore, it is clear that the problem can be solved by belief propagation.

## 3.3 Learning and Inference

The learning part is to find the $\phi_i$ and $\psi_i$ functions for each sensor, as defined in Eqs.(6) and (7). The learning is straight-forward. We discretize the sensor readings in the past 46 years, use the first 30 years for training and the rest 16 years for testing. In the discrete space, we simply count the frequency of each value a sensor could possibly take, which is the $\phi_i$, and the conditional frequencies of sensor values given its neighbors, which is the $\psi_i$.

We use a simple discretization with a fixed number of bins, 11 bins in our case, for each sensor. The first bin is dedicated to zeroes, which consistently counts for over 50% of the populations. The 11 bins are assigned in a way that give roughly balanced number of readings in each bin. This very simple discretization method has been shown to work well in the sensor experiments. More elaborated techniques can be used which may further boost the performance, such as histogram equalization that gives balanced bin population with adaptive bin numbers.

For inference, belief propagation does not guarantee to give the exact maximum a posteriori distribution, as there are loops in the Markov network. However, loopy belief propagation still gives satisfactory results, as we will see shortly.

## 3.4 Experimental Results

Evaluation experiments are conducted on two popular types of aggregate queries: Top-K and Average. A Top-K query asks for the K sensors with the highest values, and Average asks for the averaging value of all sensor readings. These are not only popular aggregation queries that the sensor community is interested in, but also provide a good metric for probing strategies since the exact answer requires contacting all sensors.

We design probing strategies for Top-K and Average in which sensors are picked for probing based on their local maximum a posteriori probability computed by belief propagation. For comparison purposes, we also experiment with naive probing strategies that rely solely on historic statistics.
<figure><img src="image_80.png" /><figcaption>Figure 2: Top-K recall rates vs. probing ratios. On average, BP-based approach probed 8% less, achieves 13.6% higher recall rate for raw values, and 7.7% higher recall rate for discrete values.</figcaption></figure>

*   **BP-based Top-K probing:** Initially, a small number of sensors with the highest expected readings are probed, based on historic statistics. After probing, all sensor reading expectations are updated using belief propagation. Then, top sensors are selected among the unprobed sensors, based on updated expectations. This updating-probing procedure iterates until beliefs of the network converge, or more than 25% of the sensors have been probed. The top K with the highest expectation (or known readings) are returned.

*   **Naive Top-K probing:** The top 25% sensors are probed, based on historic statistics. The top K among these probed sensors are returned.

*   **BP-based Average probing:** Initially, a small number of sensors with the largest variation are probed, based on historic statistics. After probing, all sensor reading expectations are updated using belief propagation. Then, sensors having the largest variations are selected among the unprobed sensors, based on updated expectations. This updating-probing procedure iterates until more than 25% of the sensors have been probed. Average is computed based on the final expectations and the probed readings.

*   **Naive Top-K probing:** The 25% sensors with the largest variations are probed, based on historic statistics. The average is computed based on historic expectations and the probed readings.

Top-K query results are compared in Figure 2 (a) and (b). Experimental results are obtained for each testing day, and daily results are grouped and averaged for all days that fall into the same week of year. The results shown are for K = 10, but the relative performance remains the same for other values of K. In each diagram, the bottom curve shows the probing ratio, and the top two curves show the recall rates for raw values and discrete values. Discrete recall demonstrates the effectiveness of BP, while raw recall may be of more interest for real application needs. We use the standard formula to compute recall rate. Let S denotes the top-K sensor set returned, and T the true top-K set, then:

$$Recall = \frac{|S \cap T|}{|T|}.$$

Figure 2 shows clearly that the BP-based approach outperforms the naive approach in terms of both recall rates, while requiring less probing. On average, the BP-based approach has a discrete recall of 88% and a raw recall of 78.2%, after probing only 17.5% sensors. The naive recall has a discrete recall of only 79.3%, a raw recall of only 64.6%, after probing 25% sensors.

Average query results are compared in Figure 3 (a) and (b). In each diagram, the true means and the estimated means are shown, with error bars indicating one standard deviation away from the estimation in both directions. The results are obtained on discrete sensor readings which range from 0 to 11. On average, BP-based estimation has an error of -0.75 and deviation of 0.79, while Naive estimation has an error of -1.39 and deviation of 1.35. BP-based strategy is clearly much more effective at pinpointing the most uncertain sensors for probing, thus yielding more accurate results.

## 4. SEQUENCE DATA DISAMBIGUATING

Sequences are ordered lists of elements, such as text strings, DNA sequences, or binary codes in channel transmission. This type of data often exhibits dependencies between adjacent elements. For example, there are rich dependencies embedded in English text. This sequence data can be modeled using Markov chains—a degenerate form of Markov networks.

Moreover, errors in sequence data often have neighborhood patterns. OCR discussed in Section 1 gives an example where errors are related to the shapes of characters and to their relative positions. The mutation of a nucleotide is also influenced by its nearby bases. The fact that the Markov property is satisfied by both the sequence data itself and by errors strongly suggests that belief propagation is effective for sequence data denoising. Actually for Markov chains, belief propagation is theoretically guaranteed to give exact marginal or maximum a posteriori probabilities.

In the rest of the section, we study a problem of correcting errors in noisy documents. Despite a simple problem, it exemplifies many basic characteristics in sequence data denoising.
<figure><img src="image_81.png" /><figcaption>Figure 3: Average estimation error bars, on discrete sensor readings (0–11). On average, BP-based estimation has an error of −0.75 and deviation of 0.79, while Naive estimation has an error of −1.39 and deviation of 1.35.</figcaption></figure>

## 4.1 Problem Description

A document is a text sequence consisting of characters from an alphabet, while a noisy document is the result from some recognizer with systemic errors. We split the sequence into small segments, each having n characters, and let neighboring segments overlap by m characters, m < n. We use a random variable $x_i = (x_i^{(1)}, \dots, x_i^{(n)})$ to represent each underlying clean segment i. The corresponding observed segment in the noisy document is denoted as $y_i = (y_i^{(1)}, \dots, y_i^{(n)})$. Each segment, except those that start or end the sequence, has a neighbor segment on both sides.

Now we design the potential functions $\phi_i(x_i, y_i)$ and $\psi_{ij}(x_i, x_j)$. For $\phi_i$, the definition should specify how likely we observe $y_i$ given $x_i$. A natural choice is to define $\phi_i$ to be a likelihood function

$$ \phi_i(x_i, y_i) = P(y_i|x_i) \quad (14) $$

For a short segment, we can assume independence between characters. Thus, $\phi_i$ can be written as

$$ \phi_i(x_i, y_i) = \prod_{l=1}^{n} P(y_i^{(l)}|x_i^{(l)}) \quad (15) $$

For $\psi_i$, the definition should specify how compatible two neighboring segments $x_i$ and $x_j$ are. Again, we can assume independence between the characters in the two segments, except for those in the overlapping part. Consider two overlapping characters, $x_i^{(k)}$ and $x_j^{(l)}$. If the probability is zero that $x_i^{(k)}$ will change to $x_j^{(l)}$ or vice versa, then the two segments, $x_i$ and $x_j$, are incompatible. The resulting mutation probability of the overlapping segment quantifies the compatibility of two neighboring segments. Non-adjacent segments are incompatible. Formally, we define an asymmetric $\psi_i$ function on $x_i$ and $x_j$, when $x_i$ is the left neighbor of $x_j$:

$$ \psi_{ij}(x_i, x_j) = \prod_{l=1}^{m} P(x_j^{(l)}|x_i^{(n-m+l)}) \quad (16) $$

## 4.2 Learning and Inference

The objective of the learning phase is to find the $\phi_i$ and $\psi_i$ functions. For this purpose, we build a mutation matrix $M$. Each matrix element $m(i, j)$ is the unconditional mutation probability from the i-th character to the j-th: $m(i, j) = P(ch_j|ch_i)$. This can be easily computed from the training set, which consists of pairs of clean and noisy documents.

We partition the clean document and the noisy documents in the same way. The $\phi_i$ of each pair of clean and observed segments is given in Eq.(14), and the $\psi_i$ of each pair of neighboring clean segments is given in Eq.(16).

In inference, a subproblem is to find candidate underlying segments for a given observed segment. One can enumerate all possible candidates using the mutation matrix. But this method not only can generate too many candidates, but also ignores the following valuable information from the training data: only certain combinations of segments are possible. We restrict the candidates to be the top matches among all training segments. When the number of matches is too small, we generate some extras using the transition matrix. By doing so, we actually explore the intra-segment constraints, which are fine details that the Markov chains cannot model, as they are on the scale of segments.

## 4.3 Experimental Results

We choose two CVPR conference papers on the same topic: motion modeling. Both documents are distorted, using the probabilistic mutation rules in Table 1, to form pairs that consist of a clean document and a noisy document. One pair is used to train the potential functions, while the other is used for testing. For simplicity, we change all capitals into lower-case letters, replace all punctuation marks other than commas and periods into commas, and remove all figures, tables and equations. The transformed documents belongs to an alphabet of size 38 (consisting of 26 letters, 10 digits, a comma and a period).

A variety of distortion rules are used: unconditional mutation rules and k-order conditional mutation rules, k = 1, 2, 3. (A k-order conditional mutation depends on k neighbors on either side.) To compute the potential functions, all we need to learn is a 38 by 38 mutation matrix $M$ for unconditional
<table><caption>Table 1: Distortion rules and error correction results. Columns 1 and 2 give the rule and mutation rate, column 3 the actual number of times a rule applies, and column 4 the percentage corrected by BP inference.</caption><thead><tr><th>rule</th><th>mutation prob.</th><th># errors</th><th>% corrected</th></tr></thead><tbody><tr><td>x → k</td><td>100%</td><td>56</td><td>91%</td></tr><tr><td>f → f</td><td>42%</td><td>-</td><td>-</td></tr><tr><td>f → d</td><td>30%</td><td>123</td><td>92%</td></tr><tr><td>f → z</td><td>28%</td><td>118</td><td>87%</td></tr><tr><td>th → th</td><td>48%</td><td>-</td><td>-</td></tr><tr><td>th → tn</td><td>52%</td><td>220</td><td>96%</td></tr><tr><td>se → se</td><td>36%</td><td>-</td><td>-</td></tr><tr><td>se → ue</td><td>18%</td><td>51</td><td>93%</td></tr><tr><td>se → le</td><td>25%</td><td>69</td><td>94%</td></tr><tr><td>se → ie</td><td>21%</td><td>58</td><td>95%</td></tr><tr><td>tio → tio</td><td>29%</td><td>-</td><td>-</td></tr><tr><td>tio → tho</td><td>20%</td><td>35</td><td>100%</td></tr><tr><td>tio → txo</td><td>20%</td><td>35</td><td>100%</td></tr><tr><td>tio → two</td><td>31%</td><td>57</td><td>98%</td></tr><tr><td colspan="4">total words/errors: 3459/822 overall accuracy: 94%</td></tr></tbody></table>

mutation rates only. Yet, we are able to catch and to correct most of the mutation errors, including the higher order conditional errors. The overall correction rate is 94%, and the correction rates for high-order conditional errors are even higher, as shown in Table 1.

To help give an intuitive idea about how dependencies between text segments can be used effectively for error correction, we enclose a paragraph of distorted text here, followed by the corrected version. The misspelled words are underlined.

**Distorted text:**

*introductxon*. natural scenes contain rich stochastic motion patterns which are characterized by the movement *od* a large number *od* distinguishable or indistinguishable elements, such as falling snow, *zlock* of birds, river waves, etc. *tnele* motion patterns, called *tektured*, motion temporal *tekture* and dynamic *tektures* in the literature, cannot be analyzed by *conventwonal* optical *zlow* dields and have stimulated growing interests in both graphics and vision.

**Text after disambiguating:**

*introduction*. natural scenes contain rich stochastic motion patterns which are characterized by the movement of a large number of distinguishable or indistinguishable elements, such as falling snow, *zlock* of birds, river waves, etc. *tnese* motion patterns, called textured motion, temporal texture and dynamic *tektures* in the literature, cannot be analyzed by conventional optical flow fields, and have stimulated growing interests in both graphics and vision.

## 5. RELATED WORK AND DISCUSSIONS

Techniques for improving data quality proposed in the literature have addressed a wide range of problems caused by noise and missing data. For better information retrieval from text, data is usually filtered to remove noise defined by

grammatical errors [9]. In data warehouses, there has been work on noisy class label and noisy attribute detection based on classification rules [13] [11], as well as learning from both labeled and unlabeled data by assigning pseudo-classes for the unlabeled data [1] using boosting ensembles. Most of this previous work has its own niche concerning data quality. Our work is more general in that it exploits local data constraints using Markov networks and belief propagation.

A pioneering work in sensor networks, the BBQ system [3] has studied the problem of cost-efficient probing. However, their method relies on a global multivariate Gaussian distribution. Global constraints are very strict assumptions, and are not appropriate in many practical scenarios.

The primary contribution of this paper is to propose a unified approach to filling in missing values and disambiguating, by exploiting extensive data dependencies that are present in practical problems. The techniques here proposed can be very useful for data-intensive systems, as demonstrated by our studies of real-life applications.

## 6. REFERENCES

[1] K. Bennett, A. Demiriz, and R. Maclin. Exploiting unlabeled data in ensemble methods. In Proc. of the 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, pp. 289-296, 2002.

[2] R. Chellappa and A. Jain. Markov Random Fields: Theory and Application. Academic Pr., 1993.

[3] A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In Proc. of the 30th Intl Conf. on Very Large Data Bases (VLDB 04), 2004.

[4] S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. In Science, vol. 220, no.4598, 1983.

[5] K. Murphy, Y. Weiss, and M. Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proc. Uncertainty in AI, 1999.

[6] University of Washington. http://www.jisao.washington.edu/data_sets/widmann/.

[7] J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann publishers, 1988.

[8] C. Peterson and J. Anderson. A mean-field theory learning algorithm for neural networks. In Complex Systems, vol.1, 1987.

[9] G. Salton and M. McGill. Introduction to modern information retrieval. McGraw Hill, 1983.

[10] R. Schultz and R. Stevenson. A bayesian approach to image expansion for improved definition. In IEEE Trans. Image Processing, 3(3), pp. 233-242, 1994.

[11] Y. Yang, X. Wu, and X. Zhu. Dealing with predictive-but-unpredictable attributes in noisy data sources. In Proc. of the 8th European Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD 04), 2004.

[12] J. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. In Advances in Neural Information Processing Systems (NIPS), Vol 13, pp. 689-695, 2000.

[13] X. Zhu, X. Wu, and Q. Chen. Eliminating class noise in large datasets. In Proc. of the 20th Intl Conf. Machine Learning (ICML 03), 2003.
# Data Quality Inference

Raymond K. Pon and Alfonso F. Cárdenas

UCLA Computer Science
Boelter Hall 4829
Los Angeles, CA 90095
(310) 825-1770

{rpon, cardenas}@cs.ucla.edu

## ABSTRACT

In the field of sensor networks, data integration and collaboration, and intelligence gathering efforts, information on the quality of data sources are important but are often not available. We describe a technique to rank data sources by observing and comparing their behavior (i.e., the data produced by data sources) to rank. Intuitively, our measure characterizes data sources that agree with accurate or high-quality data sources as likely accurate. Furthermore, our measure includes a temporal component that takes into account a data source's past accuracy in evaluating its current accuracy. Initial experimental results based on simulation data to support our hypothesis demonstrate high precision and recall on identifying the most accurate data sources.

## 1. INTRODUCTION

A major aspect of data provenance is the ability to track the quality of data as it is processed by various transformations, each with an associated computational or intrinsic data collection error. It is important to choose trustworthy data sources when querying over multiple data sources [1]. Users of data warehouses regard the quality of information as important and as a factor in measuring the utility of a data warehouse [2]. Furthermore, the inclusion of data quality information has an impact on decision-making and decision-support systems as well [3, 4]. Also data conflicts, occurring when heterogeneous data sources are integrated, can be resolved by considering the quality of the data sources involved [5]. The accuracy of data can also be used to rank query results as well (as opposed to the relevance of query results to the query) [6]. Clearly, this trustworthiness and quality information should be stored as part of a data item's provenance. The following is a general query in which data quality can be used to answer:

**Query 1:** *"Given many genomic databases where data has been collected by various means and institutions, find a DNA sequence that satisfies a condition C."* In this query, collections of data sets (i.e., DNA sequences) have been collected by different instruments and/or possibly derived by various and possibly multiple transformations. Each of these instruments and transformations has a different degree of reliability and error. Additionally, the data sets that are relevant to the query may be numerous, so it is necessary to rank data sets by their "quality" or

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

IQIS 2005, June 17, 2005, Baltimore, MD, USA.

Copyright 2005 ACM 1-59593-160-0/05/06 $5.00.

trustworthiness (i.e., how reliable the data sets are).

However, it is unclear as to where metadata regarding data quality comes from. User-provided ratings of data sets or sources can be used to rate the quality of data sources [1], but is clearly a subjective measure and would require large samples to get any meaningful results. Error measures can be provided by data sources providers along with data sets, but may be inaccurate, difficult to use, incomplete, or untrustworthy [7]. Thus, we describe a technique to rank data sources by observing and comparing the behavior (i.e., the data produced by data sources) to rank them in terms of their quality. Intuitively, in our measure, data sources that agree with accurate data sources are likely to be accurate. Furthermore, in our measure, data sources that have been accurate in the past are also likely to be accurate in the future. We provide some initial experimental results based on simulation data to support our hypothesis. The following subsections discuss motivations for this work and the related works. In section 2, we describe our technique for data source ranking. In section 3 and 4, we present our initial experimental results and possible roads of future research, respectively.

### 1.1 Motivation

We describe three possible application areas in which the modeling of data accuracy and trustworthiness are important.

**Application 1:** Sensor networks are becoming increasingly prevalent in observing wildlife, monitoring environmental conditions, monitoring of soldiers in the field, and the detection of harmful biological and chemical agents, with practical applications in homeland security [8]. The effectiveness of these sensor networks is highly dependent on the accuracy of the networks, which is a function of the current battery level of the device, interference, and intrinsic error in data collection. For example, in the near future, soldiers may be equipped with data capturing devices, making each soldier a sensor [9], to give field commanders current battlefield status reports. Data captured by soldiers may be conflicting and/or erroneous because of the human element involved in the data capturing process. It would be advantageous to be able to determine the more trustworthy "sensors" in capturing the current situation to filter out noisy data and to reduce the consumption of resources (e.g., manpower, time, and battery-life).

**Application 2:** In biomedical research, research facilities frequently collaborate with each other, sharing experimental data and results. In particular, comparing genome sequences from different species has become an important tool for identifying functions of genes [10]. This necessitates dynamically integrating different databases or warehousing them into a single repository. Scientists need to know how reliable the data is if they are to base their research on it. Pursuing incorrect theories cost time and
money. The obvious solution to ensure data quality is curation, but data sources are autonomous and as a result sources may provide excellent reliability in one area, but not in all data provided, and curation slows the incorporation of data. Data providers will not directly support data quality evaluations to the same degree since there is no equal motivation for them to and there are no standards in place for evaluating and comparing data quality [7]. Thus, automatic, impartial, and independent data quality evaluation would be needed.

**Application 3:** In intelligence gathering efforts, data is often collected from many heterogeneous data sources, such as satellites, human assets, transcripts, wiretaps, etc. It is obvious that each of these data sources have different degrees of quality and trust. And with the multitude of data sources to incorporate, it is currently time-consuming to sift through each of these data sources to determine which the most accurate sources are. To make the correct decisions based on the intelligence available in a timely manner, we will need an automatic means to determine accurate data sources and to be able to detect malicious or compromised data sources to prevent them from influencing decision-making processes.

## 1.2 Related Works

There has been a significant amount of work in the area of information quality, ranging from techniques in assessing information quality and accuracy to building large-scale data integration systems over heterogeneous data sources. For example, the DaQuinCIS system [11-13] is a cooperative information system where data source providers are evaluated by data source users in a peer-to-peer system. Unfortunately, such a system relies heavily on the participation of users in the review of the quality of data in the system, which may not be practical in real-life environments. Users may not reliably or consistently in evaluating data sources.

Other works have taken other approaches in modeling and capturing data quality. Some have developed data models to model data quality but rely on data quality metadata being available, such as data sources publishing such information [14-19]. Unfortunately, these approaches rely on precise and accurate metadata. However, such metadata are not always available [7] and there is no single agreed upon standard in describing data lineage. Additionally, it may be possible for malicious processes to corrupt or “spam” query results by providing false metadata.

There has also been work in methodologies in assessing of the quality of data in databases [20-23]. However, such methodologies rely on human assessment of the data, which is often time-consuming and possibly error-prone.

Previous works have assumed that the metadata regarding the quality of data is available, accurate, and unbiased, either published by the data providers themselves or provided by user-rankings of the data sources. Our contribution is that we do not assume that such metadata is available and reliable. Rather, our automated approach examines how well the data sets produced by data sources agree with one another, and infer the rankings of the data sources in terms of their accuracy. We take an approach similar to Google's PageRank [24]. Instead of evaluating the popularity of web sites by measuring how many other popular websites link to them as in PageRank's approach, we evaluate the accuracy of data sources by measuring how well other data sources agree with the data they produce. This approach is

automated, does not rely on possibly faulty and limited metadata, and does not require human assessment.

## 2. DATA SOURCE RANKING

Traditionally, the ranking of query results was based on the relevance of a user's query. However, the quality of the results could be improved if we incorporated a data quality measure in addition to their relevance to the user's query.

We wish to do following in general:

1. Rank the data sets or data sources in order of their accuracies.

2. Determine the top-k accurate data sets or data sources.

This ordering is important particularly in data integration systems, where there are numerous data sources available of varying accuracy that changes dynamically across time. Ideally, given a query, we would like to contact each data source; however, this may be prohibitively expensive if there are budget constraints such as time and network resources. Such applications can be found in sensor networks, where battery-life is limited, and intelligence-gathering efforts, where manpower and time are limited. Thus, it would be advantageous to determine the most accurate set of data sources, so that they can be contacted in answering a query. Additionally, this methodology could be used for identifying malicious or compromised data sources that are attempting to feed false information into the data integration system. We provide the following framework for ranking the accuracy or trustworthiness of data sources based on observing and comparing data source behavior without any a priori knowledge of their relative accuracies to help solve the problem. In our model, we assume that schema and data heterogeneity have been reconciled, which is beyond the scope of this work.

### 2.1 General Framework

Let $D$ be a set of data sources. A data source $d_i \in D$ generates a table $T_i^t(k, v)$ for a query $Q$ where $t$ is the time index, $k$ is the key column, and $v$ is the value column of the table. We want to derive a metric $A_i^t \in [0,1]$ that measures the relative accuracy of data source $d_i$ at time $t$ such that $A_i^t < A_j^t$ if $d_i$ is less accurate than $d_j$ at time $t$. We define such a metric as the weighted average of the previous accuracy estimate at time index $t-1$ and the accuracy estimate derived by observing the data generated by data sources in $D$:

$$A_i^t = h(t)A_i^{t-1} + (1-h(t))c(i,t) \quad (1)$$

The intuition behind $A_i^t$ is that a data source's accuracy should be a function of its past accuracy (i.e., reputation) and its current behavior. The function $h(t)$, where $0 \le h(t) \le 1$, is the historical weight function that determines the contribution of the accuracy estimate at the previous time index. The intuition behind the historical component of the accuracy measure is that a data source that has been accurate (or inaccurate) in the past should also be accurate (or inaccurate) in the near future. For simplicity, the above historical component assumes a Markovian behavior in the evolution of the data sources, where the accuracy at time $t$ is only dependent on the value at $t-1$. However, it will be interesting to see if we can improve the quality of our estimation by taking into
account a sliding window of size $w: [A_i^t, A_i^{t-1}, ..., A_i^{t-w}]$. Thus, the historical component would consist of a weighted sum of all accuracy estimates within the last $w$ time indexes, where each estimate is weighted with a decaying weight function. The decaying weight function would assign a higher weight to more recent estimates than older estimates. A sliding window version of the equation (1) would be of the following form, where $w(j, t-1)$ is the decaying weight function:

$$A_i^t = h(t) \sum_{j=t-w}^{t-1} w(j, t-1) A_i^j + (1-h(t)) c(i, t) \quad (2)$$

However, we leave this issue to future research, where we will study the most appropriate decaying weight function and the optimal sliding window size.

The cohesion function $c(i,t)$ determines the new accuracy estimate by observing data generated by data sources in $D$ at the current time index and how well each data source agrees with one another. The cohesion function $c(i,t)$ that we propose is the following:

$$c(i,t) = f(i,t) + \frac{(1-f(i,t))}{|D|-1} \sum_{d_i \in D-\{d_j\}} a(i,j,t)c(j,t) \quad (3)$$

The function $a(i,j,t)$ is the agreement function, which outputs 0 when data sources $d_i$ and $d_j$ are in strong disagreement regarding the data in $T_i^t$ and $T_j^t$, and outputs 1 when $d_i$ and $d_j$ strongly agree, and values between 0 and 1 for other levels of agreement. The intuition behind $c(i,t)$ is:

* If a data source agrees with an accurate data source, it should also be accurate.

* If a data source agrees with an inaccurate data source, it should also be inaccurate.

* A data source has a probability $f(i,t)$ of being absolutely accurate independent of any agreement/disagreement with the other data sources.

Thus, given a system of equations of $|D|$ equations and $|D|$ variables, it is possible to determine $c(i,t)$ for all $d_i \in D$. The function $f(i,t)$ is the dampening factor function (similar to that defined in Google's PageRank algorithm [24]). In addition to being the probability that a data source $d_i$ is absolutely accurate independent of its agreement with the other data sources, the function $f(i,t)$ will prevent the solution to the system of equations from consisting of entirely zeroes for all $c(i,t)$.

## 2.2 Agreement Functions

There are several possible definitions for $a(i, j, t)$, such as the *tupleOverlap* function, which measures the proportion of tuples in approximate agreement (within some allowable difference $\epsilon$) in the set of tuples whose key values are generated by both data sources $d_i$ and $d_j$:

$$tupleOverlap(i, j, t) = \frac{|T_i^t \triangleright \triangleleft T_j^t|}{|T_i^t \triangleright \triangleleft T_j^t|} \quad (4)$$

Another possible definition for $a(i,j,t)$ is the *cosineOverlap* function, which measures the complement of the cosine distance

of two sets of data over the same key values generated by $d_i$ and $d_j$:

$$\text{cosineOverlap}(i, j, t) = \frac{V(i, j, t)^T V(j, i, t)}{|V(i, j, t)| |V(j, i, t)|} \quad (5)$$

The vector $V(i,j,t)$ can be roughly defined as $V(i, j, t) = \pi_{T_i^t, T_j^t} (T_i^t \triangleright \triangleleft T_j^t)$, except it is an ordered vector in which the values stored in the vector are ordered by their corresponding key values in $T_i^t$. There is also a Euclidian-based function for $a(i, j, t)$, which we will discuss in further detail later.

Given this system of $|D|$ equations and $|D|$ variables, we can arrange the equations to the following form:

$$A(t) * C(t) = F(t) \quad (6)$$

$A(t)$ is defined as the following matrix:

$$A(t) = \frac{f(t)-1}{|D|-1} \begin{bmatrix} \frac{|D|-1}{f(t)-1} & a(1,2,t) & \cdots & a(1,|D|,t) \\ a(2,1,t) & \frac{|D|-1}{f(t)-1} & \cdots & a(2,|D|,t) \\ \vdots & \vdots & \ddots & \vdots \\ a(|D|,1,t) & a(|D|,2,t) & \cdots & \frac{|D|-1}{f(t)-1} \end{bmatrix}$$

$C(t)$ and $F(t)$ are also defined as the following matrices:

$$C(t) = \begin{bmatrix} c(1,t) \\ c(2,t) \\ \vdots \\ c(|D|,t) \end{bmatrix}, \quad F(t) = f(t) \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}$$

The solution to equation (6), $C(t)$, is a vector where each entry $C(t)_i$ estimates the accuracy of data source $d_i$. The matrix $A(t)$ can also be normalized with respect to maximum or sum of the entries in each of the rows (horizontal normalization) or in each of the columns (vertical normalization). We can horizontally normalize the matrix $A(t)$ by performing the following division on every entry $A(t)_{i,j}$ in row $i$, column $j$, except for entries where $i = j$:

$$A'(t)_{i,j} = \frac{A(t)_{i,j}}{\text{Hor}(t,i)}$$

$\text{Hor}(t,i)$ can either be the sum or the maximum value of all the entries in row $i$ excluding the entry $A(t)_{i,i}$. We can also similarly define a function $\text{Ver}(t,j)$ for vertical normalization ($A(t)_{i,j} = \frac{A(t)_{i,j}}{\text{Ver}(t,j)}$) to be either the sum or the maximum value of all entries in column $j$ excluding the entry $A(t)_{j,j}$.

Given our normalization techniques, we can now discuss in further detail the Euclidian-based function for $a(i, j, t)$ mentioned briefly before. Because Euclidian-distance is unbounded, normalization would be required to describe the amount of overlap or agreement. We define the Euclidian-based function $eOverlap$ for $a(i, j, t)$:

$$eOverlap(i, j, t) = 1 - eDist'(V(i, j, t), V(j, i, t)) \quad (7)$$

The function $eDist'$ is simply the Euclidian distance of the vectors $V(i,j,t)$ and $V(j, i, t)$, normalized in a similar manner as described above.
<figure><img src="image_82.png" /><figcaption>Figure 1: The precision and recall for identifying the top 10 most accurate data sources with (a) the Euclidian-based agreement functions, (b) the Cosine-based agreement functions, and (c) the Overlap-based agreement functions with $\epsilon = 0.1$.</figcaption></figure>

### 3. EXPERIMENTAL RESULTS

We hypothesize that the above framework can be used as a springboard in solving the general problem of identifying accurate data sources. To do so, we will need to identify adequate $h(t)$, $a(i,j,t)$, and $f(i,t)$ functions through experimentation. Our initial experiments examine the cohesion function $c(i,t)$ with a dampening factor $f$ independent of time (i.e., the probability of a data source being absolutely accurate independent of all other data sources is constant), and excluding incorporation of the historical component. As a result, the combination of equations (1) and (3) reduces to the following:

$$A'_{i} = c(i,t) = f + \frac{1-f}{n-1} \sum_{d_j \in D - \{d_i\}} a(i,j,t)c(j,t) \quad (8)$$

We implemented a Java prototype, using JAMA (Java Matrix Package) [25] for solving the system of equations, and experimented on simulation data consisting of 100 data sources, each producing 20 different tuples, each consisting of a key (of type integer) and a value (of type double). In each run, a data set, consisting of 20 keys and values randomly assigned to each key with a uniform distribution, represent the “actual” data that each data source will attempt to report. Additionally, in each run, each data source was randomly assigned positive error values according to a Gaussian distribution with an average of 0 and a standard deviation of 1.0. For each run, we ran five iterations, where each data source produced a data set, consisting of values for each key, where each value is randomly generated with a

Gaussian distribution with a standard deviation equal to that of the data source's error value and an average equal to that of the “actual” data item's value, essentially perturbing each data item's value with data source's error value. Data sources with large error values will generally generate values farther away from the “actual” value than data sources with smaller error values. We ran a total of five runs, consisting of five iterations, and averaged the results.

Figure 1 shows the precision and recall of the various agreement functions and normalizations as the dampening factor $f$ is varied. Note that the overlap-based functions are using a difference margin $\epsilon = 0.1$. The figure clearly shows that the dampening factor has very little effect in identifying the top 10 most accurate data sources. However, the figure does show that the vertical normalization with respect to the maximal value of the column yields the best performance. Additionally, the figure shows that the overlap-based functions perform the worse, with the cosine-based functions performing well and the Euclidian-based functions performing even better with a precision and recall of over 90%. The overlap-based functions suffer from having a fixed allowable difference margin that is difficult to estimate without knowing the nature of the data and the data sources a priori. The cosine-based functions perform better than the overlap-based functions because no such assumption is needed but does not accurately capture the amount of distance/overlap as Euclidian-based functions do.

To summarize, Figure 2 shows the performance of the three agreement functions with various normalizations using a fixed
<figure><img src="image_83.png" /><figcaption>Figure 2: The precision and recall for identifying the top 10, 15, 20, 25, and 50 most accurate data sources with a dampening factor of 0.5</figcaption></figure>

dampening factor of 0.5 (since current results do not definitively indicate the best value for *f*, we selected a mid-range value for *f*). The figure clearly shows that the Euclidian-based agreement function with vertical max and sum normalizations performs the best with a precision and recall of over 90%.

## 4. FUTURE WORK

One of the caveats of the current technique is that it relies on data sources reporting on the same set of data items. Often, it may be the case where data sources will report about different data items. Future study will have to be done to evaluate the current technique's effectiveness over incomplete and heterogeneous data sources. Additionally, the current technique may suffer from possibly expensive polling of all data sources. In future work, we will need to devise an efficient and intelligent sampling technique to alleviate such a problem while still preventing the staleness of estimates. One obvious possibility is to use the data gathered during a query (which is essentially free from the point of view of the quality estimator since such a cost will need to be incurred anyway to answer the query) to estimate a new relative accuracy measure than can be used for the next query. However, only data sources with high accuracy estimates will have their estimates updated and the estimates of data sources of low accuracy will become stale, since accurate data sources are the only data sources consistently being probed since they are selected to the answer the query. Thus, we will need to explore additional sampling techniques [26], such as polling for only small subsets of data from a majority of data sources, to solve this problem and to be able to associate a confidence metric in the ranking generated by our methodology.

Additionally, computing the solution to a set of $n$ $c(i,t)$ equations with $n$ variables may be computationally expensive if $n$ is very

large. Thus, we will also explore techniques to speed up this computation with an acceptable margin of error, such as using an iterative approach, using old $c(j,t-1)$ values for computing the new $c(i,t)$ value in equation (3). Figure 3 shows promising preliminary results regarding the performance of the iterative solution, indicating that we can arrive to a reasonably good estimation in very few iterations and that the dampening factor has some effect on how fast we can arrive to a solution. We use an initial estimate of $c(i,-1) = 1$ for all data sources and use the Euclidian-based agreement function with vertical sum normalization while varying the dampening factor. Future work will further explore the effect of the dampening factor.

In this preliminary study, we randomly assign error values to the

<figure><img src="image_84.png" /><figcaption>Figure 3: Performance of attaining an iterative solution using $c(i,-1) = 1$ and the Euclidian-based agreement function with vertical sum normalization.</figcaption></figure>
data sources with a Gaussian distribution. Additional research will
include further study on how well our cohesive function performs
with other probability distributions, such as uniform distributions.
We also hypothesize that such a technique can be used to
automatically identify faulty or failing data sources dynamically,
such as a sensor or an intelligence asset. We will need to
experiment with the historical component of our accuracy
measure. We will study how robust and reactive our accuracy
measure will be when the accuracy of data sources becomes
dynamic, as opposed to being static as in the case of this
preliminary study.

Although we have experimented with an overlap-based function
using a difference margin ε = 0.1 and could have used other
values for ε to see the effect on the precision and recall of
identifying the top-k most accurate data sources, the results
indicate that that the overlap-based function performs poorly
compared to the Euclidian and cosine-based functions with this
value for ε. Another value for ε would have probably been better,
but we hypothesize that the optimal ε is dependent upon the
domain application of the data. In later work, we will examine the
effect of ε when real-life data (e.g., sensor data) becomes readily
available.

Currently, our accuracy measure evaluates the accuracy of data
sources based a single domain of data (i.e., a single topic).
However, data sources may provide data for multiple domains
(i.e., multiple topics) and may be more accurate in one domain
than another. There are two possible attitudes in approaching this
problem. A “suspicious” attitude would suspect all data
(regardless of topic) provided by a data source if a data source
contradicts a more trustworthy data source. A “trusting” attitude
would only suspect a minimal set of data (i.e., data from the
contradicting topic) that contradicts a more trustworthy data
source, which is a similar attitude taken in [27]. Future research
will examine how these attitudes can be incorporated into the
overall accuracy measure.

<figure><img src="image_85.png" /><figcaption>Figure 4: Network of agreeing data sources</figcaption></figure>

We also envision that this technique can be used to identify
communities of data sources in which members of the community
share common "beliefs." In Figure 4, a graph generated with
JUNG (Java Universal Network/Graph Framework) [28]
consisting of 50 nodes, each representing a data source, are
connected by edges, whose lengths are the Euclidian-distance of
the data sets generated by the connecting nodes. It is clear from
the graph that nodes that are in high agreement with one another
are clustered very closely with each other; whereas, outliers in the
graph disagree with the cluster and can be considered as
inaccurate. Future work will include studies how clustering
techniques can be used to identify communities of data sources,
such as that from social network analysis [29].

5. CONCLUSION

We have presented an automated technique for inferring the
quality of data sources without the luxury of metadata. Our main
contribution is a framework to capture the historical accuracy of
data sources and the relationship of data sources in how well they
agree with one another (i.e., the cohesive function). Our second
contribution is a preliminary study of the cohesive function,
examining the precision and recall of identifying the top-k most
accurate data sources with various agreement functions and
normalizations. We have shown that the Euclidian-based
agreement function vertically normalized performs the best.

We have also identified several significant challenges and future
roads of research, including performance optimizations, exploring
various sampling techniques, developing robust yet reactive
accuracy estimations, and identifying communities of data
sources.

6. ACKNOWLEDGMENT

The authors would like to thank Roderick Son, from the UCLA
Medical Imaging Informatics Group, Terence Critchlow and
David Buttler from the Lawrence Livermore National Laboratory,
and the anonymous reviewers for their invaluable inspiration and
input for this work. This work is partially funded by the National
Foundation Grant # IIS 0140384.

7. REFERENCE

[1] D. Buttler, M. Coleman, T. Critchlow, R. Fileto, W. Han, C. Pu, D. Rocco, and L. Xiong, "Querying multiple bioinformatics information sources: can semantic web research help?" *SIGMOD Record*, vol. 31, pp. 59-64, 2002.

[2] A. Rudra and E. Yeo, "Issues in user perceptions of data quality and satisfaction in using a data warehouse-an Australian experience," presented at 33rd Annual Hawaii International Conference on System Sciences, 2000.

[3] I. N. Chengular-Smith, D. P. Ballou, and H. L. Pazer, "The impact of data quality information on decision making: an exploratory analysis," *IEEE Transactions on Knowledge and Data Engineering*, vol. 11, pp. 853-864, 1999.

[4] R. A. Dillard, "Using data quality measures in decision-making algorithms," *IEEE Expert*, vol. 7, pp. 63-72, 1992.

[5] F. Naumann, "From databases to information systems - information quality makes the difference," presented at the International Conference on Information Quality (IQ 2001), Cambridge, MA, 2001.

[6] M. Gertz, M. T. Ozsu, G. Saake, and K. U. Sattler, "Report on the Dagstuhl seminar: 'data quality on the web'," *SIGMOD Record*, vol. 33, pp. 127-132, 2004.
[7] T. Critchlow, L. Liu, D. Buttler, D. Rocco, and C. Pu, "Towards Automatic Discovery and Identification of Bioinformatics Web Interfaces," [Online] Available: http://sirius.cs.ucdavis.edu/Dagstuhl03/presentations/03362_CritchlowTerence.Slides.ppt, 2003.

[8] V. Kumar (editor), "Special Issue on Sensor Network Technology and Sensor Data Management," *SIGMOD Record*, vol. 32, 2003.

[9] F. Donovan, "Army to deploy hand-held devices to make every soldier into a sensor," [Online] Available: http://www.aviationnow.com/avnow/news/channel_netdefen se_story.jsp?id=news/arm04294.xml, 2004.

[10] F. S. Collins, E. D. Green, A. E. Guttmacher, and M. S. Guyer, "A vision for the future of genomics research," *Nature*, vol. 422, pp. 835-847, 2003.

[11] M. Mecella, M. Scannapieco, A. Virgillito, R. Baldoni, T. Catarci, and C. Batini, "Managing data quality in cooperative information systems," in *Lecture Notes in Computer Science* 2519, 2002, pp. 486-502.

[12] M. Scannapieco, A. Virgillito, C. Marchetti, M. Mecella, and R. Baldoni, "The DaQuinCIS architecture: a platform for exchanging and improving data quality in cooperative information systems," *Information Systems*, vol. 29, pp. 551-582, 2004.

[13] L. D. Santis, M. Scannapieco, and T. Catarci, "Trusting data quality in cooperative information systems," presented at CoopIS 2003, 2003.

[14] J. Widom, "Trio: a system for integrated management of data, accuracy, and lineage," presented at CIDR 2005, Pacific Grove, California, 2005.

[15] G. A. Mihaila, L. Raschid, and M.-E. Vidal, "Using quality of data metadata for source selection and ranking," presented at Third International Workshop on the Web and Databases, WebDB'2000, Dallax, TX, 2000.

[16] G. A. Mihaila, L. Raschid, and M.-E. Vidal, "Source selection and ranking in the websemantics architecture using quality of data metadata," *Advances in Computers*, vol. 55, pp. 87-118, 2002.

[17] M. Gertz, "Managing data quality and integrity in federated databases," presented at IFIP TC11 Working Group 11.5, Second Working Conference on Integrity and Internal Control in Information Systems: Bridging Business Requirements and Research Results, 1998.

[18] F. Naumann, J. C. Freytag, and U. Leser, "Completeness of integrated information sources," *Information Systems*, vol. 29, pp. 583-615, 2004.

[19] F. Naumann, "Quality-Driven Query Answering for Integrated Information Systems," in *Lecture Notes in Computer Science*, G. Goos, J. Hartmanis, and J. v. Leeuwen, Eds. Berlin, Germany: Springer-Verlag, 2002, pp. 166.

[20] A. Motro and I. Rakov, "Estimating the quality of databases," presented at 1996 Conference on Information Quality, Cambridge, MA, 1996.

[21] M. Bobrowski, M. Marre, and D. Yankelevich, "A homogeneous framework to measure data quality," presented at IQ 1999, Cambridge, MA, 1999.

[22] B. Pernici and M. Scannapieco, "Data quality in web information systems," presented at ER 2002, 2002.

[23] Y. W. Lee, D. M. Strong, B. K. Kahn, and R. Y. Wang, "AIMQ: a methodology for information quality assessment," *Information Systems*, vol. 29, pp. 133-146, 2004.

[24] S. Brin and L. Page, "The anatomy of a large-scale hypertextual web search engine," presented at 7th World Wide Web Conference (WWW7), 1998.

[25] J. Hicklin, C. Moler, P. Webb, R. F. Boisvert, B. Miller, R. Pozo, and K. Remington, "JAMA: Java Matrix Package," [Online] Available: http://math.nist.gov/javanumerics/jama/, 2005.

[26] J. Cho and A. Ntoulas, "Effective Change Detection using Sampling," presented at VLDB Conference, Hong Kong, China, 2002.

[27] L. Cholvy and C. Garion, "Querying several conflicting databases," presented at ECSQARU-03 Workshop Uncertainty, Incompleteness, Imprecision, and Conflict in Multiple Data Sources, Aalborg, 2003.

[28] Jung Framework Development Team, "JUNG: Java Universal Network/Graph Framework," [Online] Available: http://jung.sourceforge.net/index.html, 2005.

[29] S. Staab, P. Domingos, P. Mika, J. Golbeck, L. Ding, T. Finin, A. Joshi, A. Nowak, and R. R. Vallacher, "Social Networks Applied," *Intelligent Systems, IEEE* [see also *IEEE Expert*], vol. 20, pp. 80-93, 2005.
<figure><img src="image_86.png" /></figure>
Author Index

<table><tbody><tr><td>Al-Lawati, Ali</td><td>59</td></tr><tr><td>An, Aijun</td><td>87</td></tr><tr><td>Andreopoulos, Bill</td><td>87</td></tr><tr><td>Bugajski, Joseph</td><td>40</td></tr><tr><td>Cardenas, Alfonso F.</td><td>105</td></tr><tr><td>Chen, Zhaori</td><td>47</td></tr><tr><td>Chu, Fang</td><td>99</td></tr><tr><td>Embury, Suzanne</td><td>5</td></tr><tr><td>Garcia-Molina, Hector</td><td>1</td></tr><tr><td>Grossman, Robert L.</td><td>40</td></tr><tr><td>Hammer, Joachim</td><td>16</td></tr><tr><td>Kalashnikov, Dimitri V.</td><td>47</td></tr><tr><td>Kang, Jaewoo</td><td>69</td></tr><tr><td>Karakasidis, Alexandros</td><td>28</td></tr><tr><td>Keelara, Vinay</td><td>77</td></tr><tr><td>Koeller, Andreas</td><td>77</td></tr><tr><td>Lee, Dongwon</td><td>59, 69</td></tr></tbody></table>

<table><tbody><tr><td>Martinez, Alexandra</td><td>16</td></tr><tr><td>McDaniel, Patrick</td><td>59</td></tr><tr><td>Mehrotra, Sharad</td><td>47</td></tr><tr><td>Missier, Paolo</td><td>5</td></tr><tr><td>On, Byung-Won</td><td>69</td></tr><tr><td>Park, Sanghyun</td><td>69</td></tr><tr><td>Parker, D. Stott</td><td>99</td></tr><tr><td>Pitoura, Evaggelia</td><td>28</td></tr><tr><td>Pon, Raymond K.</td><td>105</td></tr><tr><td>Sumner, Eric</td><td>40</td></tr><tr><td>Tang, Zhao</td><td>40</td></tr><tr><td>Vassiliadis, Panos</td><td>28</td></tr><tr><td>Wang, Xiaogang</td><td>87</td></tr><tr><td>Wang, Yizhou</td><td>99</td></tr><tr><td>Winkler, William E.</td><td>3</td></tr><tr><td>Zaniolo, Carlo</td><td>99</td></tr></tbody></table>