9．1．3　K－NN算法

K－NN分类算法是一种传统的基于统计的模式识别方法，基于实例进行分类，即无参数分类器。该算法的核心思想是：对于一篇待分类文档，系统在训练集中找出k（k的确定可以设置相应阈值）个最相近的文档，使用这k个文档所属类别作为待分类文档的候选类别。该文档与k个近邻之间的相似度可以按类别分别求和，再减去一个预先得到的截尾阈值，即可作为该文档的类别测度。公式示意如下^［2］：

其中：

为一篇待分类文本的向量表示；为训练集中的一篇实例文本的向量表示；C_j为一类别；y（，C_j）∈｛0，1｝（当d属于C_j时取1，当不属于C_j时取0）；b_j为预先计算得到的C_j的最优截尾阈值；sim（）为待分类文本与文本实例之间的相似度，由公式（9－4）计算得到：

K－NN是一种lazy－learning算法，分类器不需要使用训练集进行训练，其计算复杂度和训练集中的文档数目成正比。