Calculation of similarity between two entities is a key step in several data mining processes. While there are several common similarity measures for continuous data, there is little work for categorical data. Most approaches are purely datadriven and don't consider the inherent dependencies of complex domains such as geological structures, phylogenetics, etc. We propose two new similarity measures that take into account semantic information to calculate the similarity between two categorical values. Semantic information is represented as a hierarchy extracted from an ontology or a domain taxonomy. The first approach calculates semantic similarity by combining the data-driven approach with the hierarchy imposed on the possible categorical values. The second approach ignores the data and uses only the hierarchy to calculate semantic similarity. We apply our methods to a specific complex data mining task in the oil and gas industry: reservoir analogue identification. The two proposed measures are compared to existing data-based measures.
The context of this work is the combination of data-based (statistical) methods with knowledge-based methods in data science. In many disciplines, there is a considerable body of domain knowledge available, while data sets may not always be large enough to support machine learning of complex relationships. In this work, we look specifically at similarity measures (or equivalently distance measures), which lie at the core of a number of machine learning tasks such as clustering, outlier identification and classification (k-NN). We concentrate on entities described by categorical data, feature values taken from a finite set of possible values with no inherent order. The domain knowledge we wish to incorporate is given in the form of hierarchies that can be extracted from domain ontologies, standard classifications, etc.
There is a variety of suitable metrics to quantify similarity for numerical data such as Euclidean or Manhattan distance (Esposito et al. 2000). These methods are not directly applicable to non-numerical data. However, defining sensible metrics for categorical attributes is challenging.
The most common approach in machine learning
algorithms for handling categorical data is one-hot
encoding
In a supervised learning approach, the distance (x; y)
between two categorical values can be defined using value
distance matrix
For unsupervised learning, the hamming distance is used
and similarity is defined as a matching measure that assigns
1 if both values are identical, and 0 otherwise
To improve on these, frequency-based similarity measures have been proposed that take the frequency distribution of different attribute values into account. These measures are data-driven and hence are dependent on certain data characteristics such as the size of data, number of attributes, number of values for each attribute and distribution of frequency of each value. While data-driven measures perform well on simple datasets, these measures are unable to take into account semantic relationships and often don’t perform well on complex datasets with hidden domain dependencies. Moreover, a concept of similarity that is based solely on how often values occur in the data cannot be expected to give reasonable results in all cases. Using frequencies seems more like a ‘last straw’ when frequencies are the only distinguishing feature between categorical values.
In this paper, we propose an alternative way to measure similarity for categorical data in an unsupervised setting. We combine a frequency-based measure with explicitly represented domain knowledge given in the form of a hierarchy on attribute values, and we also consider a measure that is based purely on the hierarchy, without taking frequencies into account.
Section 2 describes the related work. Section 3 explains the problem formulation and proposed algorithm. Section 4 presents the dataset and evaluation by comparing with existing algorithms.
2
The surveys
For unsupervised learning, various techniques have been
proposed
The simplest similarity measure used is known as
overlap measure
Lin proposed a similarity framework based on
information theory
Das and Mannila’s research is based on the key point that
attribute value similarity is related to other attributes
Document or sentence similarity is considered the
basic task for many natural language processing(NLP)
engines such as information retrieval, query answering, and
text summarization. Semantic-based methods use
information from dictionaries (WordNet) to find relatedness between
two terms. Classic methods in NLP are based on the
shortest path measure
However, the techniques mentioned above are not directly suitable for categorical features. In an NLP setting, there are many terms in a complete sentence or document, that provide the neighborhood context and aid understanding the semantics. Furthermore, NLP tasks are constrained by the sentence structures and grammar of a particular language such as the ordering of subject, verb, noun, etc. However, categorical features are represented by single domain terms with no obvious representation of neighborhood or the context that explains the semantic similarity. The main focus here is to define semantic similarity between categorical terms based on the characteristics extracted from domain knowledge.
In this section, we first discuss a toy example to identify the drawbacks of frequency-based similarity approaches. Further, we provide an overview of metric properties and semantic similarity to establish the foundation of the proposed similarity measure.
We analyze the problems in existing work and inherent challenges associated with categorical data based on the toy dataset in Table 1. The dataset consists of candidates’ profiles and we wish to retrieve matching candidates for a given job advertisement.
Many of the data-driven similarity measures consider two
values of a given categorical attribute to be similar if both
have similar frequency distributions. For instance, the OF
similarity measure for values of an attribute is calculated as
follows
User ID (1) where f (x) is the number of occurrences of the attribute value x and N represents the total number of observations in the data set. Similarity between pairs ‘Computer Programmer’ and ‘HR Manager’ and ‘Computer Programmer’ and ‘Software Developer’ based on equation 1 is calculated as: OF (Comp. Programmer; HR Manager) = 0:64 OF (Comp. Programmer; Soft. Developer) = 0:44
These numbers would indicate that the Programmer is more similar to HR Managers than to Developers. However, based on the evaluation of semantic evidence observed in a knowledge source (such as an ontology or a standard classification) shown in Table 2, it is evident that computer programmers and software developers perform the same work activities and tasks hence having a greater semantic similarity.
Semantic similarity can be made explicit in different ways, and one of the prominent ways is through hierarchies, which we will use in this paper. Section 3.1 explains in detail the formal definition of hierarchies. 3.1
Our similarity measures are based on a given hierarchical structure of the value range of categorical features. Formally, we assume that the categorical values for each feature form a finite, partially ordered set (poset). A poset is an ordered pair of binary relation v defined over a set S, such that (v; S) satisfies the following properties: Let x; y; z 2 S, • Reflexivity: x v x • Antisymmetry: if x v y and y v x, then x = y • Transitivity: if x v y and y v z, then x v z If a v b, we call b an ancestor of a. The intention of a v b is that b is in some way more general, broader, etc. than a. E.g., for the occupations in Fig. 1, TopExecutives v ManagementOccupations; for data about geographic areas, we could have Oslo v Norway v Europe.
If domain knowledge is given in the form of an ontology, in some cases (depending on the modeling style), the relation v will correspond to parts of the is-a subclass relation of the ontology, but in others it won’t. E.g. it doesn’t make sense to consider Norway a sub-class or sub-concept of Europe, but it still makes sense to consider a hierarchy of geographic regions.
A value c 2 S is called a lowest common ancestor of two node values a 2 S and b 2 S if c 2 S is the lowest (i.e. deepest) node that has both a 2 S and b 2 S as descendants. It is the first shared ancestor of a and b located farthest from the root. In a hierarchy two values have a lowest common ancestor denoted as a t b. A value is called a leaf value if it is not the ancestor of any other value.
In this paper, we add a restriction to our hierarchies by only considering mono-hierarchies: we assume that there is some root value r in the hierarchy, such that a v r for all a 2 S, and that all values except the root have exactly one direct ancestor. In other words, the hierarchy is tree-shaped. 3.2
Semantic similarity refers to similarity based on meaning
or semantic content as opposed to form
Is-a relationships in a concept hierarchy encompass formal classification, properties and relations between concepts and data. This provides us with a common understanding of the structure of a domain, explicit domain assumptions and reuse of domain knowledge. In order to achieve interpretable and good quality results in machine learning models, it is vital to take this information into account. This intuition motivates us to link the notion of similarity based on is-a relationships with the similarity measures for categorical data. We develop a framework to use is-a relationships extracted from a concept hierarchy to quantify semantic similarity and propose a distance measure for categorical data. 3.3
In this paper, we propose two techniques for measuring
similarity based on domain knowledge, extracted as the concept
hierarchy. First, we present a framework for calculating
semantic similarity using information content and concept
hierarchy by modifying Resnik’s idea
Further, we are interested in computing global semantic similarity in a multi-dimensional setting where we have several hierarchy-structured features. We define the global similarity between two data objects X and Y in a d-dimensional where (xi; yi) corresponds to similarity between two values x and y in the i-th dimension and wi is the weight associated with each dimension. The following section presents both frameworks for calculating semantic based similarity (xi; yi).
approach is based on a modification of Resnik’s idea
In order to formulate the semantic similarity of two given
categorical values, the key intuition is to find the common
information in both values. This information is represented by
the lowest common ancestor in the hierarchy that subsumes
both values
For the given dataset, we can map the ‘Occupation’ attribute to the O*net taxonomy1(Fig. 1) by placing all the values at the corresponding leaf nodes in the occupation hierarchy whereas intermediate nodes represent the lowest common ancestors for given pairs. In Fig. 12,‘Computer Programmer’ and ‘Software Developer’ are both subsumed by the lowest common ancestor ‘Computer Occupations’, whereas the lowest common ancestor that subsumes the concept ‘HR Manager’ and ’Computer Programmer’ is ‘Occupation’(root node of the occupation hierarchy). Hence, taking into account the lowest common ancestor, we expect that the similarity between Computer Programmer and Software Developer to be significantly greater than the similarity between the Computer Programmer and HR Developer.
Our intuition about the concept of semantic similarity is that for two categorical values x and y that share lowest common ancestor c, farthest from the root node, are always considered to be more semantically similar than to two categorical values x and z that share lowest common ancestor c0 close to root node. In addition, identical values should have a maximum similarity of 1.
In order to formulate the semantic similarity of values
based on the lowest common ancestor, we use the idea of
associating probabilities with the values
For categorical data, we can find the information content I of the lowest common ancestor c by finding the information content of all the leaf values subsumed by c in the hierarchy.
I(c) = log
X n2 leaf (c) p(n) where leaf (c) is the set of all leaf values in x 2 S such that x v c. The probability of leaf values may be estimated by the relative frequency.3
frequency (n) p(n) = (4)
N where N is the number of samples.
Based on the above definitions, we formulate information content based semantic similarity(ICS) between two categorical values x and y as
Sim(x; y) = (1
I(xty) max(I(xty)) if x = y: else if x 6= y where I(xty) denotes the information content of the lowest common ancestor of x and y, calculated by using equation 3 and max(I(xty) represents the maximum information content of all given pair of leaves and is used for normalization. Hierarchy-based Semantic Similarity(HS) As explained earlier, the main intuition of semantic similarity is based on the idea that any two values having the lowest common ancestor close to leaf nodes, should have high similarity and vice versa. Hence, we quantify semantic similarity by considering the level of the lowest common ancestor in the hierarchy. The level of a node is defined by 1+ the number of connections between the node and the root4. Greater the level of the lowest common ancestor of any given pair of values in the hierarchy, more similar the values are. We formulate the similarity as,
Sim(x; y) = 1 d level(x[y) if x = y: else if x 6= y (6) 3Probabilities may also be known from other sources, for instance known priors for the specific domain.
4Level starts from 1 and the level of the root is 1 (3) (5) Where 0 < < 1 is a fixed decay parameter, level(n) is the distance of n from the root in the hierarchy, and d = maxn2X level(n) is the maximum depth of the hierarchy.
The main advantage of equation 6 is that the calculation of semantic similarity no longer requires any input from training data such as information content. Once the concept hierarchy is formalized, we can measure the similarity between any two values including the categorical values not observed in the training data.
Below, we explain how to perform evaluation of the proposed techniques.
4
In this section, we compare the ICSD and HDM approaches to other similarity measures for the identification of reservoir analogues of a target reservoir, given a dataset of known reservoirs. This use-case is further explained in Section 4.2 below. 4.1
The following four state-of-the-art similarity/distance
measures are compared with the proposed techniques:
Occurrence Frequency (OF)
We compare the performance of the different similarity measures in a recommendation scenario: given a query item, we compute its similarity to each item in the ‘training’ dataset using Equation 2, and determine the top k items with highest similarity.
For our evaluation, we do this for all of the different similarity measures, and compare the outcome to a fixed ‘gold standard’ list of items to determine the average precision.
For our experimental evaluation, we have chosen reservoir analogues (explained in the section below): a complex task in the Oil and Gas industry. To the best of our knowledge, there exists no standard machine learning system for solving this use case. The common industrial practice to date is to conduct a manual analysis by human experts. 4.2
In the Oil and Gas Industry, during the exploration phase,
analogous reservoirs are used to study reservoirs that lack
critical information. Any reservoir with a deficit of critical
information is known as a “target reservoir”, and
“analogous reservoirs” are ones expected to have similar
characteristics.
Usually, a technical evaluation team must analyze various data types – seismic, well logs, test, and cores – in order to make the first approximation of analogous reservoirs. Due to a lack of resources and time constraints, the first approximation is usually the neighboring reservoirs to provide an estimate of the fluid and rock properties of the target reservoir. A single analogue is mostly used because it is in the same geographic region or basin. This is risky however, since it does not always give sufficient information to characterize a new prospect. Furthermore, it becomes a tedious task for new target reservoirs where no neighboring reservoir exists.
Limited efforts have been made to identify analogues
based on machine learning
The main source of information used in this evaluation is the dataset of reservoirs licensed by IHS5. It comprises a total of 43000 reservoirs and various properties/attributes associated with each reservoir. According to domain experts, only a few key parameters are known during the initial stage of
reservoir identification. Hence for our analysis of retrieving similar reservoirs, we use the following set of key parameters/attributes identified by domain experts. • Depositional Environment • Lithology • Age • Geographical Location • Structural Setting
Detailed definitions of these parameters are described in the section below. 4.4
This section explains the process of standardizing the semantic information used in the calculation of similarity. Due to data confidentiality, we only explain two attributes ‘Age’ and ‘Lithology.’ Reservoir Age: A geologic age is a subdivision of geologic time that divides an epoch into smaller parts. A succession of rock strata laid down in a single age on the geologic timescale is a stage. The geological time has been divided into eras, periods and epochs. The named divisions of the geological time are based on fossil evidence. Fig. 2 shows a part of an ontology developed to show how geological times are organized into Erathem, Period, Epoch and Age.
Note that age can also be given on a linear scale, e.g. in millions of years. However, the characteristics of rocks deposited in different geologic eras, periods, and epochs differ so much that their position in the hierarchy is a much better indicator of similarity than the numerical difference in age. Lithology: The lithology of a rock unit is a description of its physical characteristics visible at outcrop, in hand or core samples or with low magnification microscopies, such as color, texture, grain size, or composition. There is no standard ontology for lithology. With the help of geologists, we develop an ontology that considers all the categorical values occurring in data and groups them based on similar physical characteristics. In Fig. 3, we show a part of this ontology. 4.5
The main challenge associated with the given data is a large number of categorical values associated with each attribute. For the attribute ‘Age,’ there are about 250 unique values. These values are not standardized. Hence, there are instances where the same category exists in the dataset with various names. Furthermore, most of the age values are unofficial names, which are used only in a few specific areas of the world. With the help of geological experts, we replaced these unofficial names by standard domain names.
For the attribute ‘Depositional Environment,’ there are 32 unique values occurring in the given data set. Some categorical values are merged together based on the same geological properties identified by domain experts.
In the original data set, there are 1731 categories of the attribute ‘Lithology.’ The raw values of lithology contain abbreviations for the same lithology, unofficial lithology names, and combinations of various lithologies. These categories are replaced with the standard names and combinations are replaced with only primary lithology, which leads to 228 unique categories.
Outliers are extreme values that deviate from other observations on data, they may indicate variability in measurement, experimental errors or a novelty. In order to avoid the disastrous effect on the results of the statistical analysis, a step is added to identify, analyze and delete outliers in the dataset. In this step, for every attribute, we remove the values that don’t confirm with standard domain names.
After cleaning the data, the comparative evaluation between ICS, HS and existing similarity algorithms is conducted. For the given task, we will evaluate the similarity measure on two main objectives. • Retrieving top 15 similar analogues to the target reservoir. • Producing the result in a ranked order such that the first retrieved analogue corresponds to the most similar reservoir to the target reservoir.
Mean Average Precision (MAP) is the mostly commonly
used evaluation metric in information retrieval and object
detection
Precision =
TruePositive
TruePositive + FalsePositive
Based on Equation 8, recommender system Precision (P) is defined as,
P = # of our recommendations that are relevant
# of items we recommended
For evaluating the performance of recommender systems, we are only interested in recommending top-N items to the user. Usually, the higher the number of relevant recommendations at the top, the more positive is the impression of the users. Therefore, it is sensible to compute precision and recall metrics in the first N items instead of all the items. Thus the precision at a cutoff k is introduced in order to evaluate ranking, where k is an integer that is set by the user to match the objective of the top-N recommendations. Average precision at cutoff k, is the average of all precisions in the places where a recommendation is a true positive and is defined as follows:
K
i=1 1 XK P (i) Rel(i) where K represents the top K recommendations for the given query q and Rel(i) shows the relevance of the recommendation. Rel(i) is 1 if the recommended item was relevant(true positive) otherwise 0.
Usually, the performance of a recommendation system is calculated by considering a set of queries. Therefore, given (7) (8) (9) (10) (11) where APq @K is calculated by using Equation 10 4.7
There is no standard way to evaluate similarity measures
for semantic similarity. Resnik uses human expert
similarity ranking to judge similarity
After acquiring the gold dataset, we perform an
experimental evaluation to compare the performance of the
proposed techniques with three existing similarity measures
(OF
In order to penalize poor estimations, we are using Average Precision (e Equation 10) as a quality criterion for evaluation of similarity between reservoirs. For this metric, a higher value corresponds to better results. Table 3, shows the experimental result of each similarity measure separately for each target reservoir 6.
As shown in table 3, ICS and HS measures outperform
the data-driven similarity measures for both selected
reservoirs. For the target reservoirs, ’Snorre’ and ’Snohvit’, the
6Similarity measure proposed by Lin
It is important to note that results obtained using ICS and HS are not directly comparable with the gold set provided by human experts. In order to produce a gold set, human experts take into account the geological history of the current basin, analysis of geological time periods and overall processes of formation of reservoir rocks. Furthermore, they also use conceptual facies models, reservoir simulation models, core samples and well logs for selecting appropriate analogues. In contrast to this, our experimental evaluation of the proposed technique is based only on a limited part of this information. Achieving 63% precision in this scenario highlights the fact that it is highly remarkable to correctly retrieve analogues in the top 15 recommendations based only on hierarchy-based semantic measure.
5
Computing similarity measure in an unsupervised setting is a complex task. In this paper, we propose a method based on domain information extracted in the form of is-a links from a concept hierarchy. The experimental results in the previous section, show that by using domain information, the results are significantly better than the traditional methods of finding similarity only based on frequency match/mismatch. In our current work, we approach the problem by considering the lowest common ancestor in the concept hierarchy by considering mono-hierarchies only and in an unsupervised setting. In the future, we want to extend the notion of similarity for categorical data in a supervised setting for complex use cases such as mortality prediction in the medical domain. Furthermore, the idea can be extended to find similarity for categorical data in poly-hierarchies (i.e. not treeshaped).