This paper reports on the refinement of the THD algorithm, developed in the OntoElect framework. This baseline THD algorithm used exact string matches for key term comparison. It has been refined by introducing an appropriate string similarity metric for grouping the terms having similar meaning and looking similar as text strings. To choose the most appropriate metric, several existing metrics have been cross-evaluated on the developed test set of multiword terms in English. The rationale for creating this test set is also presented. Further, the refined algorithm for measuring terminological difference has been cross-evaluated with the baseline THD algorithm. For this cross-evaluation, the bags of terms extracted from the TIME collection of scientific papers were used. The experiment revealed that using the refined algorithm yielded better and quicker terminological saturation, compared to the baseline.
The research presented in this paper is the part of the development of the
methodological and instrumental components for extracting representative (complete) sets of
significant terms from the representative sub-collections of textual documents having
minimal possible size. These terms are further interpreted as the required features for
engineering an ontology in a particular domain of interest. Therefore, it is assumed that the
documents in a collection cover a single and well circumscribed domain. The main
hypothesis, put forward in this work, is that a sub-collection can be considered as
representative to describe the domain, in terms of its terminological footprint, if any
additions of extra documents from the entire collection to this sub-collection do not
noticeably change this footprint. Such a sub-collection is further considered as complete and
therefore yields a representative bag of significant terms describing its domain. The
approach to assess the representativeness does so by evaluating terminological
saturation in a document (sub-)collection [
Detecting saturation is done by measuring terminological difference (thd) among the
pairs of the consecutive incrementally enlarged datasets, as described in Section 4. This
set measure is of course based on measuring differences between individual terms.
A (baseline) THD algorithm [
The remainder of the paper is structured as follows. Section 2 reviews the related work. Section 3 reports on the implementation of the chosen string similarity measures and selecting the proper term similarity thresholds for their use. Section 4 sketches out the approach of OntoElect for measuring thd and our refinement of the baseline THD algorithm. Section 5 presents the set-up and results of our evaluation experiments. Our conclusions and plans for the future work are given in Section 6. 2
The work reported in this paper aims at improving the measures of terminological
difference between the bags of terms extracted from textual documents. The improvement
is sought via the proper choice and use of existing string metrics for measuring
linguistic (dis)similarity between extracted terms, as opposed to the baseline THD algorithm
[
In the majority of approaches to ATE, e.g. [
For “unithood”, the metrics are used such as mutual information [
Linguistic Processing is organized and implemented in a very similar fashion in all
ATE methods, except some of them that also include filtering out stop words. Stop
words could be filtered out also at a cut-off step after statistical processing. So, in our
review and selection we look at the second phase of Statistical Processing only.
Statistical Processing is sometimes further split in two consecutive sub-phases of term
candidate scoring, and ranking. For term candidates scoring, reflecting its likelihood of
being a term, known methods could be distinguished by being based on (c.f. [
Perhaps the most cited paper that compares string similarity (distance) metrics is
[
The authors of [
To the best of our knowledge, none of the published techniques in ATE use text
string similarity (distance) measures to group linguistically similar terms. This is done
in the work presented in this paper. Furthermore, none of the techniques, except
OntoElect [
From the variety of metrics, mentioned above, due to the specifics of our task of the approximate comparison of short strings containing a few words, we filtered out those: (i) that require long strings or sets of strings of a considerably big size; (ii) that are computationally hard. We also tried to keep the representatives of all kinds of string metrics in our short list as much as it was possible. As a result, we formed the following list of measures to be considered for further use: Levenstein distance, Hamming distance [27], Jaro similarity, and Jaro-Winkler similarity – edit distance based syntactic measures Jaccard similarity index – a token based measure Sørensen-Dice coefficient [28] – a bi-gram comparison based measure Among those, Levenstein and Hamming distances appeared to be the least appropriate in our context due to their limitations. Levenstein returns an integer number of required edits, while the rest of the measures return normalized reals. So, it has not been clear if normalizing Levenstein would really make the result comparable to the other measures in a way to use the same term similarity threshold. Hamming is applicable only to the strings of equal lengths. So, adding spaces to the shorter string would really lower the precision of measurement. Therefore, it has finally been decided to use Jaro, Jaro-Winkler, Jaccard, and Sørencen-Dice for implementation and cross-evaluation in our work. Further, it is briefly explained how should the selected measures be computed and referred to their implementation code. After that, it is explained how term similarity thresholds have been chosen for these implemented measures.
Jaro similarity simj between two strings S1 and S2 is computed (1) as the minimal number of one character transforms to be done to the first term (string) for getting the second string in the compared pair.
0, sim j 1/ 3 ( m m | S1 | | S2 | if
m 0 m t
) otherwise , m (1) where: |S1|, |S2| are the lengths of the compared strings; m is the number of the matching characters; and t is the half of the number of transposed characters. The characters are matching if they are the same and their distance from the beginning of the string differs by no more than ⌊ (| 1|, | 2|)/2⌋ − 1. The number of matching but having different sequence order symbols is the number of transposed characters.
Jaro-Winkler similarity measure simj-w refines Jaro similarity measure simj by using a prefix scale value p which assigns better ratings to the strings that match from their beginnings for a prefix length l. Hence, for the two strings S1 and S2 it is computed as shown in (2).
simj-w = simj + l*p*(1 – simj),
(2)
where l is the length of a common prefix (up to a maximum of 4 characters); p is a
constant scaling factor for how much the similarity value is adjusted upwards for having
common prefixes (up to 0.25, otherwise the measure can become larger than 1; [
Sometimes Winkler’s prefix bonus l*p*(1 – simj) is given only to the pairs having
Jaro similarity higher that a particular threshold. This threshold is suggested [
Jaccard similarity index simja is a similarity measure for finite sets, characters in our case. It is computed, for the two strings S1 and S2, as the ratio between the cardinalities of the intersection and union of the character sets in S1 and S2 as shown in (3). sim ja ( S1 S2 ) /( S1 S2 ) (3)
Finally, Sørensen-Dice coefficient, regarded as a character string similarity measure, is computed by counting identical character bi-grams in S1 and S2 and relating these to the overall number of bi-grams in both strings – as shown in (4).
simsd 2n /( nS1 nS2 ) , (4) where: n is the no of bi-grams found in S1 and also in S2; nS1 , nS2 are the numbers of all bi-grams in S1 and S2.
The functions for all four string similarity measures have been implemented2 in
Python 3.0 and return real values within [
For the proper use of those functions it is however necessary to determine what would be a reasonable threshold to distinguish between (semantically) similar and not similar terms. For determining that, the following cases in string comparison need to be taken into account: Character strings are fully the same – Full Positives (FP). This case clearly falls into similar (the same) terms. Character strings are very different and the terms in these strings carry different semantics – Full Negatives (FN). This case is also clear and is characterized by low values of similarity measures. Character strings are partially the same and the terms in these strings carry the same or similar semantics – Partial Positives (PP).
The terms in such strings are similar, though it may not be fully clear. The following are different categories of terms that bring us about this case: words in the terms have different endings (e.g. plural/singular forms); different delimiters are used (e.g. “-”, or “–”, or “ - ”); a symbol is missing, erroneously added, or misspelled (a typo); one term is a sub-string of the other (e.g. subsuming the second); one of the strings contains unnecessary extra characters (e.g. two or three spaces instead of one, or noise). Character strings are partially the same but the terms in these strings carry different semantics – Partial Negatives (PN)
The terms in such strings are different, though it may not be fully clear. The following are the categories that bring us about this case: the terms carried by the compared strings differ by a few characters, but have different meanings (e.g. “deprecate” versus “depreciate”); the compared terms have common word(s) but fully differ in their meanings (e.g. “affect them” versus “effect them”). These false positives are the hardest case to be detected.
The test set of term pairs falling into the cases described above has been manually developed3. For each pair of terms in this test set all four string similarity measures have been computed. 2 These functions are publicly available at: https://github.com/EvaZsu/OntoElect 3 The test set and computed term similarity values are publicly available at https://github.com/EvaZsu/OntoElect/blob/master/Test-Set.xls
We have computed the average values of all four similarity measures for each category using all the test set term pairs falling into this category. The results are given in Table 1.
Term similarity thresholds have to be chosen such that full and partial negatives are regarded as not similar, but full and partial positives are regarded as similar. Hence, for the case of partial positives, the thresholds have to be chosen as minimal of all the case categories, and for the partial negatives – as the maximal of all the case categories. The values of case thresholds are shown bolded in Table 1 and provide us with the margins for relevant threshold intervals in our experiments. These intervals have been evenly split in four points as presented in Table 2. The requirements for partial positives and negatives unfortunately contradict to each other. For example, if a threshold is chosen to filter out partial negatives, also some of the partial positives will be filtered out. Therefore, subsuming that partial negatives are rare, it has been decided to use the thresholds for partial positives.
OntoElect, as a methodology, seeks for maximizing the fitness of the developed ontology regarding what the domain knowledge stakeholders think about the domain. Fitness is measured as the stakeholders’ “votes” – a measure that allows assessing the stakeholders’ commitment to the ontology under development – reflecting how well their sentiment about the requirements is met. The more votes are collected – the higher the commitment is expected to be. If a critical mass of votes is acquired (say 50%+1, which is a simple majority vote), the ontology is considered to satisfactorily meet the requirements.
Unfortunately, direct acquisition of requirements from domain experts is not very realistic as they are expensive and not really willing to do the work falling out of their core activity. So, we focus on the indirect collection of the stakeholders’ votes by extracting these from high quality and reasonably high impact documents authored by the stakeholders.
An important feature to be ensured for knowledge extraction from text collections is
that the dataset needs to be representative to cover the opinions of the domain
knowledge stakeholders satisfactorily fully. OntoElect suggests a method to measure
the terminological completeness of the document collection by analyzing the saturation
of terminological footprints of the incremental slices of the document collection [
(a) (b)
At the next step of the OntoElect workflow the bags of multi-word terms B1, B2, …, Bn are extracted from the datasets D1, D2, …, Dn, using UPM Term Extractor software [30], together with their significance (c-value) scores. Please see an example of an extracted bag of terms extracted in Fig. 1b.
At the subsequent step, every extracted bag of terms Bi, i = 1, …, n is processed as follows: Normalized scores are computed for each individual term: n-score = c-value / max(c-value) Individual term significance threshold (eps) is computed to cut off those terms that are not within the majority vote. The sum of n-scores having values above eps form the majority vote if this sum is higher that ½ of the sum of all n-scores. The cut-off at n-score < eps is done The result is saved in Ti
After this step only significant terms, whose n-scores represent the majority vote,
are retained in the bags of terms. Ti are then evaluated for saturation by measuring
pairwise terminological difference between the subsequent bags Ti and Ti+1,
i = 0, …, n-1. So far it has been done by applying the baseline THD algorithm4 [
Algorithm THD. Compute Terminological Difference between Bags of Terms Input: Ti, Ti+1 – the bags of terms with grouped similar terms.
Each term Ti.term is accompanied with its T.n-score.
Ti, Ti+1 are sorted in the descending order of T.n-score.
M – the name of the string similarity measure function to compare terms
th – the value of the term similarity threshold from within [
In fact, THD accumulates, in the thd value for the bag Ti+1, the n-score differences if there were the same terms in Ti and Ti+1. If there was no the same term in Ti, it adds the n-score of the orphan to the thd value of Ti+1. After thd has been computed, the relative terminological difference thdr receives its value as thd divided by the sum of n-scores in Ti+1.
Absolute (thd) and relative (thdr) terminological differences are computed for further assessing if Ti+1 differs from Ti more than the individual term significance threshold eps. If not, it implies that adding an increment of documents to Di for producing Di+1 did not contribute any noticeable amount of new terminology. So, the subset Di+1 of the overall document collection may have become terminologically saturated. However, to obtain more confidence about the saturation, OntoElect suggests that some 4 The baseline THD algorithm is implemented in Python and is publicly available at https://github.com/bwtgroup/SSRTDC-modules/tree/master/THD more subsequent pairs of Ti and Ti+1 are evaluated. If stable saturation is observed, then the process of looking for a minimal saturated sub-collection could be stopped.
Our task was to modify the THD algorithm in a way to allow finding not exactly the same but sufficiently similar terms by applying string similarity measures with appropriate thresholds – as explained in the previous Section 3. For that, the preparatory similar term grouping step has been introduced to avoid duplicate similarity detection.
For each of the compared bags of terms Ti and Ti+1 the similar term grouping (STG) algorithm is applied at this preparatory step – see Fig. 3. After term grouping is accomplished for both bags of terms, the refined THD algorithm (Fig 2 – rounded rectangles) is performed to compute the terminological difference between Ti and Ti+1. 5
This section reports on our evaluation of the refined THD algorithm against the baseline
THD [
The objective of our experiment was to find out if using the refined THD algorithm yields quicker and smoother terminological saturation compared to the use of the baseline THD algorithm. We were also looking at finding out which string similarity measure best fits for measuring terminological saturation.
For making the results comparable, the same datasets created from the TIME document collection – as described in Section 5.2 – has been fed into both the refined and baseline THD algorithms. We applied: (i) The refined THD – sixteen times – one per individual string similarity measure M (Section 3) and per individual term similarity threshold th (Table 3); and (ii) The baseline THD – one time
The values of: (i) the No of retained terns; (ii) absolute terminological difference (thd); and (iii) the time taken to perform term grouping by the STG algorithm (sec); were measured.
Finally, to verify if the refined THD is correct, we checked if it returns the same results as the baseline THD when the term similarity threshold is set to 1.0.
All the computations have been run on a Windows 10 64-bit PC with: Intel® Core™ 2 Duo CPU, E7400 @ 2.80 GHz; 4.0 Gb on-board memory. 5.2
TIME document collection contains the full text papers of the proceedings of the TIME Symposia series5. The domain of the collection is Time Representation and Reasoning. The publisher of these papers is IEEE. It contains all the papers published in the TIME symposia proceedings between 1994 and 2013, which are 437 full text documents. These papers have been processed manually, including their conversion to plain texts and cleaning of these texts. So, the resulting datasets were not very noisy. We have chosen the increment for generating the datasets to be 20 papers. So, based on the available texts, we have generated 22 incrementally enlarged datasets D1, D2, …, D226 using our Dataset Generator7. The chronological order of adding documents has been used. 5.3
The results of our measurements of terminological saturation (thd) are pictured in a diagrammatic form in Fig. 4. The diagrams showing the time spent by the STG algorithm for detecting and grouping similar terms, based on the chosen term similarity thresholds are in Fig. 6. The diagrams in Fig. 4 and 6 have been built using the values 5 http://time.di.unimi.it/TIME_Home.html 6 The TIME collection in plain text and the datasets generated of these texts are available at: https://www.dropbox.com/sh/64pbodb2dmpndcy/AAAzVW7aEpgW-JrXHaCEqg2Sa/ TIME?dl=0 7 The dataset generator is available at: https://github.com/bwtgroup/SSRTDC-PDF2TXT of the measurements from the four tables – one per term similarity threshold point (Min, Ave-1, Ave-2, and Max)8.
Saturation (thd) measurements reveal that the refined THD algorithm detected terminological saturation faster than the baseline THD algorithm – no matter what was the chosen term similarity measure (M) or the similarity threshold (th). If the results for different measures are compared, then it may be noted that the respective saturation curves behave differently, depending on the similarity threshold point. (a) Min term similarity thresholds
(b) Ave-1 term similarity thresholds
Overall, as it could be seen in Fig 4 (a) – (d), the use of the Sørensen-Dice measure demonstrated the least volatile behavior along the term similarity threshold points. This measure resulted in making the refined THD algorithm to detect saturation slower than the three other measures for Min, Ave-1, and Ave-2. For Max, it was as fast as Jaro and slightly slower than Jaccard and Jaro-Winker.
One more observation was that, integrally, all the implemented term similarity measures coped well with retaining important terms. These are indicated by terminology contribution peaks in the diagrams (a)-(d) of Fig. 4. It is well seen in Fig. 4(d), for the Max threshold point, that all the string similarity method curves follow the shape of the baseline THD curve quite closely. Hence, they have the peaks exactly in the same thd measurement points where the baseline has, pointing at more new significant terms. 8
The tables are not presented in the paper due to the page limit, though are publicly available at: https://github.com/EvaZsu/OntoElect. File names are Results-Alltogether-{min, ave, ave2, max}-th.xlsx
At Min, Ave-1, and Ave-2, however, the method that have been most sensitive to terminology peaks, was Sørensen-Dice. This sensitivity is also confirmed by Fig. 5. Fig. 5 pictures the proportions of the retained to all extracted terms computed at different term similarity threshold points. It is clear from Fig. 5 that Sørensen-Dice retains the biggest number of terms at all used term similarity thresholds. (a) Min term similarity thresholds
(b) Ave-1 term similarity thresholds (c) Ave-2 term similarity thresholds Legend: (d) Max term similarity thresholds Finally, it has to be noted that the introduction of string similarity measures in the computation of terminological difference (THD algorithm) increases the computational complexity of the algorithm quite substantially. Fig. 6 pictures the times (in seconds) taken by the pre-processor STG algorithm. As it could be noticed in Fig. 6(a)-(d), the times grow with the value of the term similarity threshold (th) and reach thousands of seconds for Max threshold values. It is interesting to notice that Sørensen-Dice and Jaccard are substantially more stable to the increase of th than Jaro and Jaro-Winkler. Sørensen-Dice takes, however, roughly an order of magnitude more time than Jaccard. From the other hand, Jaccard was not very sensitive to terminological peaks and retained significantly less terms than Sørensen-Dice.
To sum up, the findings are put in Table 3 to rank the evaluated string similarity measures on a scale 1 (the best) to 5 (the worst).
Probably surprisingly, Jaccard, which is the most lightweight string similarity measure (Fig. 6), demonstrated the best performance among the rest, including the baseline THD. As it was well balanced on all evaluation aspects. This balance was also good in the case of Sørensen-Dice. However, Sørensen-Dice lost to Jaccard and baseline THD as it took too much time for term grouping. Jaro and Jaro-Winkler were clear negative outliers. Therefore, at an expense of a slightly higher execution time, the THD refined by Jaccard string similarity measure is the preferred choice for measuring terminological saturation in OntoElect. 6
In this paper, we investigated if a simple string equivalence measure used in the baseline THD algorithm may be outperformed if a proper string similarity measure is used instead. For finding this out, we: (i) have chosen the four candidate measures from the broader variety of the available, based on the specifics of term comparison; (ii) developed the test set of specific term pairs to decide about term similarity thresholds for the chosen measures; (iii) implemented these measures, the algorithm for similar terms grouping (STG), and the refinement of the baseline THD algorithm; (iv) cross-evaluated the refined THD algorithm against the baseline, and also all individual measures against each other; (v) gave our recommendation about the use of the refined THD algorithm with Jaccard measure which demonstrated the most balanced performance in our experiments.
For the experiments we used the datasets generated, using our instrumental software suite, from the TIME document collection. This collection contains real scientific papers acquired from the proceedings series of the Time Representation and Reasoning Symposia.
Our future work is planned based on the results of the presented experiments and
some additional observations we made. Firstly, we would like to explore the ways to
improve the performance of the Sørensen-Dice measure implementation as its higher
computational complexity is the only flaw against the Jaccard measure implementation.
Secondly, we are interested in finding out if a similar term grouping algorithm, using a
sensitive similarity measure, like Sørensen-Dice, would be plausible for grouping
features while building feature taxonomies. This task is on the agenda for the second
(Conceptualization) phase of OntoElect [32]. Thirdly, we are keen to check if the evaluation
results on the other document collections will be similar to that presented in this paper.
To find this out we plan to repeat the same cross-evaluation experiments but on the
datasets generated from DMKD and DAC collections [
The research leading to this publication has been done in part in cooperation with the Ontology Engineering Group of the Universidad Politécnica de Madrid in frame of FP7 Marie Curie IRSES SemData project (http://www.semdata-project.eu/), grant agreement No PIRSES-GA-2013-612551. While performing this research, the first author has been a master student on the program on Computer Science and Information Technologies at Zaporizhzhia National University. The second author is funded by a PhD grant provided by Zaporizhzhia National University and the Ministry of Education and Science of Ukraine. 26. Qin, J., Wang, W., Lu, Y., Xiao, C., Lin, X.: Efficient exact edit similarity query processing with the asymmetric signature scheme. In: Proc. of the 2011 ACM SIGMOD Int Conf on Management of data, pp. 1033--1044. ACM New York, USA (2011) 27. Hamming, R. W.: Error detecting and error correcting codes. Bell System Technical Journal 29 (2), 147--160 (1950), DOI:10.1002/j.1538-7305.1950.tb00463.x. 28. Dice, Lee R.: Measures of the amount of ecologic association between species. Ecology 26 (3), 297--302 (1945), DOI:10.2307/1932409 29. Badenes-Olmedo, C., Redondo-García, J. L., Corcho, O.: Efficient clustering from distributions over topics. In: Proc. K-CAP 2017, ACM, New York, NY, USA, Article 17, 8 p. (2017), DOI: 10.1145/3148011.3148019 30. Corcho, O., Gonzalez, R., Badenes, C., Dong, F.: Repository of indexed ROs. Deliverable
No. 5.4. Dr Inventor project (2015) 31. Ermolayev, V.: OntoElecting requirements for domain ontologies. The case of time domain.
EMISA Int J of Conceptual Modeling 13(Sp. Issue), 86--109 (2018) DOI: 10.18417/emisa.si.hcm.9 32. Moiseenko, S., Ermolayev, V.: Conceptualizing and formalizing requirements for ontology engineering. In: Antoniou, G., Zholtkevych, G. (eds.) Proc. ICTERI 2018 PhD Symposium, Kyiv, Ukraine, May 14-17, CEUR-WS (2018) online – to appear