Rocchio classification

Figure 14.1 shows three classes, China, UK and Kenya, in a two-dimensional (2D) space. Documents are shown as circles, diamonds and X's. The boundaries in the figure, which we call decision boundaries , are chosen to separate the three classes, but are otherwise arbitrary. To classify a new document, depicted as a star in the figure, we determine the region it occurs in and assign it the class of that region - China in this case. Our task in vector space classification is to devise algorithms that compute good boundaries where ``good'' means high classification accuracy on data unseen during training.

Figure 14.3: Rocchio classification.

Perhaps the best-known way of computing good class boundaries is Rocchio classification , which uses centroids to define the boundaries. The centroid of a class $c$ is computed as the vector average or center of mass of its members:

$$\vec{\mu} (c) = \frac{1}{\vert\docset_c\vert} \sum_{d \in \docset_c} \vec{v}(d)$$ (139)

where $\docset_c$ is the set of documents in $\docsetlabeled$ whose class is $c$: $\docset_c = \{ d:\langle d,c\rangle \in \docsetlabeled \}$. We denote the normalized vector of $d$ by $\vec{v}(d)$ (Equation 25 , page 6.3.1 ). Three example centroids are shown as solid circles in Figure 14.3 .

The boundary between two classes in Rocchio classification is the set of points with equal distance from the two centroids. For example, $\vert a_1\vert=\vert a_2\vert$, $\vert b_1\vert=\vert b_2\vert$, and $\vert c_1\vert=\vert c_2\vert$ in the figure. This set of points is always a line. The generalization of a line in $M$-dimensional space is a hyperplane, which we define as the set of points $\vec{x}$ that satisfy:

$$\vec{w}^{T}\vec{x} = b$$ (140)

where $\vec{w}$ is the $M$-dimensional normal vector of the hyperplane and $b$ is a constant. This definition of hyperplanes includes lines (any line in 2D can be defined by $w_1x_1+w_2x_2=b$) and 2-dimensional planes (any plane in 3D can be defined by $w_1x_1+w_2x_2+w_3x_3=b$). A line divides a plane in two, a plane divides 3-dimensional space in two, and hyperplanes divide higher-dimensional spaces in two.

Thus, the boundaries of class regions in Rocchio classification are hyperplanes. The classification rule in Rocchio is to classify a point in accordance with the region it falls into. Equivalently, we determine the centroid $\vec{\mu}(\tcjclass)$ that the point is closest to and then assign it to $\tcjclass$. As an example, consider the star in Figure 14.3 . It is located in the China region of the space and Rocchio therefore assigns it to China. We show the Rocchio algorithm in pseudocode in Figure 14.4 .

Table 14.1: Vectors and class centroids for the data in Table 13.1 .

	term weights
vector	Chinese	Japan	Tokyo	Macao	Beijing	Shanghai
$\vec{d}_1$	0	0	0	0	1.0	0
$\vec{d}_2$	0	0	0	0	0	1.0
$\vec{d}_3$	0	0	0	1.0	0	0
$\vec{d}_4$	0	0.71	0.71	0	0	0
$\vec{d}_5$	0	0.71	0.71	0	0	0
$\vec{\mu}_c$	0	0	0	0.33	0.33	0.33
$\vec{\mu}_{\overline{c}}$	0	0.71	0.71	0	0	0

Worked example. Table 14.1 shows the tf-idf vector representations of the five documents in Table 13.1 (page 13.1 ), using the formula $(1+\log_{10} \mbox{tf}_{t,d}) \log_{10} (4/\mbox{df}_t)$ if $\mbox{tf}_{t,d} >0$ (Equation 29, page 6.4.1 ). The two class centroids are $\mu_c = 1/3 \cdot (\vec{d}_1+ \vec{d}_2+ \vec{d}_3)$ and $\mu_{\overline{c}} = 1/1 \cdot (\vec{d}_4)$. The distances of the test document from the centroids are $\vert\mu_c - \vec{d}_5 \vert \approx 1.15$ and $\vert\mu_{\overline{c}} - \vec{d}_5 \vert = 0.0$. Thus, Rocchio assigns $d_5$ to $\overline{c}$.

The separating hyperplane in this case has the following parameters:

$$\begin{eqnarray*} \vec{w} &\approx& (0 \ -0.71 \ -0.71 \ \ 1/3 \ \ 1/3 \ \ 1/3 )^T\\ b &=&-1/3 \end{eqnarray*}$$

See Exercise 14.8 for how to compute $\vec{w}$ and $b$. We can easily verify that this hyperplane separates the documents as desired: $\vec{w}^{T}\vec{d_1} \approx 0 \cdot 0+-0.71 \cdot 0+-0.71 \cdot 0+1/3 \cdot 0+1/3 \cdot 1.0+1/3 \cdot 0 = 1/3 > b$ (and, similarly, $\vec{w}^{T}\vec{d_i} > b$ for $i=2$ and $i=3$) and $\vec{w}^{T}\vec{d_4} = -1 < b$. Thus, documents in $c$ are above the hyperplane ( $\vec{w}^{T}\vec{d} > b$) and documents in $\overline{c}$ are below the hyperplane ( $\vec{w}^{T}\vec{d} < b$).

End worked example.

The assignment criterion in Figure 14.4 is Euclidean distance (APPLYROCCHIO, line 1). An alternative is cosine similarity:

$$\mbox{Assign $d$\ to class} \ c = \argmax_{{c'}} \cos (\vec{\mu}({c'}) ,\vec{v}(\onedoc) )$$ (141)

As discussed in Section 14.1 , the two assignment criteria will sometimes make different classification decisions. We present the Euclidean distance variant of Rocchio classification here because it emphasizes Rocchio's close correspondence to $K$-means clustering (Section 16.4 , page 16.4 ).

Figure 14.4: Rocchio classification: Training and testing.

Rocchio classification is a form of Rocchio relevance feedback (Section 9.1.1 , page 9.1.1 ). The average of the relevant documents, corresponding to the most important component of the Rocchio vector in relevance feedback (Equation 49, page 49 ), is the centroid of the ``class'' of relevant documents. We omit the query component of the Rocchio formula in Rocchio classification since there is no query in text classification. Rocchio classification can be applied to $J>2$ classes whereas Rocchio relevance feedback is designed to distinguish only two classes, relevant and nonrelevant.

In addition to respecting contiguity, the classes in Rocchio classification must be approximate spheres with similar radii. In Figure 14.3 , the solid square just below the boundary between UK and Kenya is a better fit for the class UK since UK is more scattered than Kenya. But Rocchio assigns it to Kenya because it ignores details of the distribution of points in a class and only uses distance from the centroid for classification.

The assumption of sphericity also does not hold in Figure 14.5 . We cannot represent the ``a'' class well with a single prototype because it has two clusters. Rocchio often misclassifies this type of multimodal class . A text classification example for multimodality is a country like Burma, which changed its name to Myanmar in 1989. The two clusters before and after the name change need not be close to each other in space. We also encountered the problem of multimodality in relevance feedback (Section 9.1.2 , page 9.1.3 ).

Two-class classification is another case where classes are rarely distributed like spheres with similar radii. Most two-class classifiers distinguish between a class like China that occupies a small region of the space and its widely scattered complement. Assuming equal radii will result in a large number of false positives. Most two-class classification problems therefore require a modified decision rule of the form:

$$\mbox{Assign $\onedoc$\ to class $c$ iff} \ \vert \vec{\mu}(... ... < \vert \vec{\mu}(\overline{c}) - \vec{v}(\onedoc) \vert - b$$ (142)

for a positive constant $b$. As in Rocchio relevance feedback, the centroid of the negative documents is often not used at all, so that the decision criterion simplifies to $\vert \vec{\mu}(c) - \vec{v}(\onedoc) \vert < b'$ for a positive constant $b'$.

mode	time complexity
training	$\Theta(\vert\docsetlabeled\vert L_{ave}+\vert\mathbb{C}\vert\vert V\vert)$
testing	$\Theta( L_{a}+\vert\mathbb{C}\vert M_{a})= \Theta(\vert\mathbb{C}\vert M_{a})$

Training and test times for Rocchio classification. $L_{ave}$ is the average number of tokens per document. $L_{a}$ and $M_{a}$ are the numbers of tokens and types, respectively, in the test document. Computing Euclidean distance between the class centroids and a document is $\Theta(\vert\mathbb{C}\vert M_{a})$.

Table 14.2 gives the time complexity of Rocchio classification. Adding all documents to their respective (unnormalized) centroid is $\Theta(\vert\docsetlabeled\vert L_{ave})$ (as opposed to $\Theta(\vert\docsetlabeled\vert\vert V\vert)$) since we need only consider non-zero entries. Dividing each vector sum by the size of its class to compute the centroid is $\Theta(\vert V\vert)$. Overall, training time is linear in the size of the collection (cf. Exercise 13.2.1 ). Thus, Rocchio classification and Naive Bayes have the same linear training time complexity.

In the next section, we will introduce another vector space classification method, kNN, that deals better with classes that have non-spherical, disconnected or other irregular shapes.

Exercises.

• Show that Rocchio classification can assign a label to a document that is different from its training set label.