14 Vector space classification

这一章描述了使用vector space model对documents进行分类的方法。
首先提到contiguity hypothesis，该假说认为每一个不同的类中的文档拥有连续性且互不重叠，每一个类中有许多特定的topic，这些topic word不太出现在其他类的documents中。

在vector space classification中我们应该使用有权重的和规范化的参数，即在Chapter 6中阐述的scoring。本章将会阐述两种分类方法：Rocchio和kNN(k nearest neighbor)

14.2 Rocchio classification
在Rocchio中将每篇文章作为二维平面上的点来考虑，每个分类是其中的一块区域，互不重合，这也就是之前提到的contiguity hypothesis。（这么说可能不恰当 因为每个document其实都是一个多维向量）
我们确定每个分类边界的做法是先确定centroid，然后boundary就是到两个centroids距离相等的点的集合，但因为整张图是一个高维空间，所以该boundary也是hyperplane。
而centroid则是一个class中document vector的平均值
boundary方程 
where w is the M-dimensional normal vector of the hyperplane and b is a constant
time complexity of Rocchio
pseudocode of Rocchio
下图是一个实际的例子，d1～d4是四篇training data，d5是要判定的document，计算出两类的centroid。之后再计算w和b（因为是一条边界的向量，猜测w为两个centroid向量相减，w和b都是参数 由training data计算得出，但是我还没看懂怎么算的...）

14.3 k nearest neighbor
kNN中k是个参数，其特例是1NN，表示每篇document属于和其最近的document的类；而kNN则是取和其最近的k篇document，再统计出其中占大多数的是哪个class，则该document归属于其中。kNN中k > 1相对来说会使分类比较可靠，3或5是常用的k。
pseudocode of kNN
一个例子，如果使用1NN star会归于circle 而如果使用大圈表示的3NN，则star会归于X
time complexity of kNN

14.4 linear versus nonlinear
线性分类器算法描述十分简洁，但是由training data得出边界比较复杂，还容易受到noise document的影响。noise document是指包含在training set中，利用线性分类的方法会将其归入错误的类的document，在平面上来说就是这类document离另一类更近。

线性的代表是Naive Bayes和Rocchio，而非线性的代表是kNN（kNN在决定boundary时是使用了每两篇document决定其之间的boundary的方法，所以在局部可能是线性，但最终在平面上表现为折线）

14.5 Classification with more than two classes
在这一节中讨论多于两个类的情况，按类和类之间的互斥性，我们可以分为：any-of classification(不互斥，document可以属于多个类或一个类或不属于任何类) one-of classification(互斥，document属于exactly one class)
对于any-of classification，可以用training set先为每个类单独求出边界，然后为每一个test document单独判断是否在这些边界之内。
对于one-of classification，前两步和上面的一样，但第三步一定要为每篇document找出最符合的一个类来。