Information Technology Reference
In-Depth Information
Algorithm 5.
Relationship Detection
Input:
(
T
,
P
, threshold) Where
T
is a set of
tag
1
,tag
2
tuples ,
P
is a set of patterns
Output:
(
I
) A set of 2-tuples in form of
parent tag, child tag
1:
for all
t
i
∈ T
do
2:
for all
p
j
∈ P
do
3:
hits
1
←
#ofhitsofquerying“
t
i
.tag
1
p
j
t
i
.tag
2” as a phrase
4:
hits
2
←
#ofhitsofquerying“
t
i
.tag
2
p
j
t
i
.tag
1” as a phrase
5:
ratio
j
.F ←
hits
1
hits
2
6:
ratio
j
.R ←
hits
2
hits
1
is-a
7:
end for
8:
maximum
F
←
max(
ratio
j
.F
)overallj
9:
maximum
R
←
max(
ratio
j
.R
)overallj
10:
maximum ←
max(
maximum
F
,maximum
R
)
11:
if
((
maximum
=
maximum
F
)and(
maximum
F
≥ threshold
))
then
12:
I ← I ∪{
tag1, tag2,
is-a
}
13:
else
14:
if
((
maximum
=
maximum
R
)and(
maximum
R
≥ threshold
))
then
15:
I ← I ∪{
tag2, tag1,
is-a
}
16:
end if
17:
end if
18:
end for
19: Return
I
the two possible permutations of the tags in the pattern. E.g., given (“human”,
“body”, “'s”), the two generated queries will be “human's body” and “body's
human”. Then, the ratios for both forward and reverse occurrences direction are
calculated. It is clear that given any set of patterns for any relationship, this
algorithm can be applied. We use the following patterns from [9] to identify
is-a
relationships: (1) Pattern 1: NP
1
such as NP
2
; (2) Pattern 2: NP
1
including
NP
2
; (3) Pattern 3: NP
1
especially NP
2
.
Our
has-a
relationships are supersets of meronymy (part-of relationships),
and are not limited to the physical perspective. We consider two noun phrases
NP
1
and NP
2
to have a
relationship (with NP
1
as the parent) if one
of the following statements is true: (1) NP
2
is a part of NP
1
. E.g., “body” is
a part of “human”; or (2) NP
1
has/have NP
2
. E.g., “human” has “mind” and
“google” has “googleMaps”; or (3) NP
1
may have NP
2
. E.g., “human” may have
“disease”.
From the existing lexico-syntactic patterns mentioned in the literature such
as [4,6], we use three following patterns to detect
has-a
relationships:(1) Pattern
1: NP
1
's NP
2
; (2) Pattern 2: NP
2
of the NP
1
; (3) Pattern 3: NP
2
of NP
1
.
While patterns 1 and 2 are among the most common English patterns [6],
pattern 3 is not. However, pattern 3 can be used to detect
has-a
has-a
relationship
between tags such as the tuple
.
All patterns for a relationship are fed into a search engine. If the largest ratio
of a pattern is above a threshold, that tuple is labeled with the corresponding
relationship and added to the ontology. Algorithm 5 shows the
Coffee, Caffeine
is-a
detection
