9.2. CONTENT-BASED RECOMMENDATIONS
331
Once we have selected a predicate for a node N, we divide the items into
the two groups: those that satisfy the predicate and those that do not. For
each group, we again ﬁnd the predicate that best separates the positive and
negative examples in that group. These predicates are assigned to the children
of N. This process of dividing the examples and building children can proceed
to any number of levels. We can stop, and create a leaf, if the group of items
for a node is homogeneous; i.e., they are all positive or all negative examples.
However, we may wish to stop and create a leaf with the majority decision
for a group, even if the group contains both positive and negative examples.
The reason is that the statistical signiﬁcance of a small group may not be high
enough to rely on. For that reason a variant strategy is to create an ensemble of
decision trees, each using diﬀerent predicates, but allow the trees to be deeper
than what the available data justiﬁes.
Such trees are called overﬁtted.
To
classify an item, apply all the trees in the ensemble, and let them vote on the
outcome. We shall not consider this option here, but give a simple hypothetical
example of a decision tree.
Example 9.6 : Suppose our items are news articles, and features are the high-
TF.IDF words (keywords) in those documents. Further suppose there is a user
U who likes articles about baseball, except articles about the New York Yankees.
The row of the utility matrix for U has 1 if U has read the article and is blank if
not. We shall take the 1’s as “like” and the blanks as “doesn’t like.” Predicates
will be Boolean expressions of keywords.
Since U generally likes baseball, we might ﬁnd that the best predicate for
the root is “homerun” OR (“batter” AND “pitcher”). Items that satisfy the
predicate will tend to be positive examples (articles with 1 in the row for U in
the utility matrix), and items that fail to satisfy the predicate will tend to be
negative examples (blanks in the utility-matrix row for U). Figure 9.3 shows
the root as well as the rest of the decision tree.
Suppose that the group of articles that do not satisfy the predicate includes
suﬃciently few positive examples that we can conclude all of these items are in
the “don’t-like” class. We may then put a leaf with decision “don’t like” as the
right child of the root. However, the articles that satisfy the predicate includes
a number of articles that user U doesn’t like; these are the articles that mention
the Yankees. Thus, at the left child of the root, we build another predicate.
We might ﬁnd that the predicate “Yankees” OR “Jeter” OR “Teixeira” is the
best possible indicator of an article about baseball and about the Yankees.
Thus, we see in Fig. 9.3 the left child of the root, which applies this predicate.
Both children of this node are leaves, since we may suppose that the items
satisfying this predicate are predominantly negative and those not satisfying it
are predominantly positive.
✷
Unfortunately, classiﬁers of all types tend to take a long time to construct.
For instance, if we wish to use decision trees, we need one tree per user. Con-
structing a tree not only requires that we look at all the item proﬁles, but we
