# An Ontology-Based Recommender System with an Application to the Star Trek Television Franchise
## 2 Materials and Methods
### Item Similarity
#### 2.2.3 Ontology-Based Similarity Functions  
In computer science, an ontology is a semantic organization of entities describing a particular domain [44]. The simplest kind of ontology is a tree with root node \(\phi\), which represents the most general entity. The structure extends down from the root node to other more specific entities related by the _is-a_ relation. Formally, an ontology, \(O\), is a tuple, (\(E\phi\),\(p\)), where \(E\) is a set of entities, \(\phi\) is the root entity having \(\phi\in E\), and \(p\) is the parent entity function \(p:E\to E\), defined in such a way that each entity has an unique an non-cyclical path to \(\phi\). A semantic similarity function on \(O\) is a function that computes pairwise similarities between entities [45]. Let \(t\) and \(u\) be entities in \(O\). Most of these functions are built from the following primitives:  
\(d\): The maximum number of steps from any entity to \(\phi\). \(m\): The maximum number of steps between any pair of entities. \(depth_{t}\): The number of steps from entity \(t\) to \(\phi\). \(path_{t,u}\): The number of steps from entity \(t\) to entity \(u\). \(LCS_{t,n}\): The least common subsumer of \(t\) and \(u\) (i.e., their deepest common ancestor). \(IC_{t}\): The _information content_ (IC) of entity \(t\) as proposed by [PERSON] et al. [46]. \(IC\) is a measure of the informativeness of an entity in a hierarchy obtained from statistics gathered from a corpus. In our scenario, the corpus is a collection of items, each of which is represented by a set of features associated with entities in an ontology. Thus, the \(IC\) of an entity \(t\) is defined as \(IC_{t}=-\log P(t)\), where \(P(t)\) is the probability of \(t\) in the corpus. For instance, assume the corpus of items to be a set of TV episodes whose features are themes from a theme ontology. In addition, assume the following path of theme entities in an is-a chain: \"wedding ceremony\" \(\rightarrow\) \"ceremony\" \(\rightarrow\) \"event\" \(\rightarrow\phi\). The probability \(P(t)\) of an entity \(t\) is the ratio between its number of occurrences \(f_{t}\) and the total number of entity occurrences in the corpus \(M\). Each occurrence of the theme \"wedding ceremony\" increases the counting up the hierarchy until \(\phi\) is reached. Therefore, \(P(\phi)=1\) and \(IC_{\phi}=0\). The IC scores agree with the information theoretical principle that events having low probability are highly informative and vice versa. Figure 1 illustrates the primitives in the computation of ontology-based similarity functions. There are several mathematical expressions that combine these primitives to produce similarity functions. We consider the following representative similarity functions:  
\[S_{t,s}^{\text{PATH}}=\frac{1}{path_{t,s}+1} S_{t,s}^{\text{WUP}}=\frac{2\cdot depth_{LCS_{t,s}}}{ depth_{t}+depth_{s}} \tag{7}\] \[S_{t,s}^{\text{RES}}=\frac{IC_{LCS_{t,s}}}{c_{2}} S_{t,s}^{\text{LCM}}=-\log\left(\frac{path_{t,s}}{2d}\right)\cdot \frac{1}{c_{1}}\] \[S_{t,s}^{\text{LUM}}=\frac{2\cdot IC_{LCS_{t,s}}}{IC_{t}+IC_{s}} S_{t,s}^{\text{LCM}}=\frac{1}{c_{3}\cdot(IC_{t}+IC_{s}-2\cdot IC _{LCS_{t,s}})}.\]  
The function \(S_{t,s}^{\text{PATH}}\) is a commonly used conversion of \(path_{t,s}\) to a similarity score in the unit interval. [PERSON] and [PERSON]'s \(S_{t,s}^{\text{LCH}}\) function adjusts the inverse of \(path_{t,s}\) to account for the total depth of the ontology [47]. [PERSON] and [PERSON]'s \(S_{t,s}^{\text{WUP}}\) function relates the depths in the ontology representing the commonalities between \(t\) and \(s\) with the Dice coefficient by their least common subsumer [48]. Analogously, [PERSON]'s measure uses ICs instead of depths with the same coefficient [49]. [PERSON]'s function \(S_{t,s}^{\text{RES}}\) simply uses the IC of \(LCS_{t,s}\)[46]. Finally, [PERSON] and [PERSON]'s function \(S_{t,s}^{\text{LCN}}\) is a different formulation of [PERSON]'s using the same arguments.