分类算法综述

    分类的概念很简单，就是给出一个样本x，判断样本所属的类别y，分类器就是映射函数f: y=f(x)。当然，这个函数是需要根据以往的经验（大量已知类别的样本集）来构造的。这个构造的过程，称为训练，而如何构造，就是分类算法了。

     数据挖掘中分类算法有很多，它们通过对已知类别训练集的分析，从中发现分类规则，以此预测新数据的类别。分类算法应用非常广泛，银行中风险评估、客户类别分类、文本检索和搜索引擎分类、安全领域中的入侵检测等等。主要包括以下几种分类模型：

相似度模型：K-近邻，Rocchio

概率模型：贝叶斯

线性模型：SVM

非线性模型：神经网络，决策树

 

K-近邻与Rocchio

     KNN（K-Nearest Neighbor）算法来源于向量空间模型理论(Vector Space Model)。VSM的基本思想是用向量来表示一个文本，之后的过程就可以转化为空间中向量的运算。通常采用TF-IDF来实现。TF-IDF通常用来评估某个特征对于一个文件或文件集的重要程度。特征的重要性与它在文件中出现的次数成正比，与它在语料库中出现的频率成反比。每个文件都表示为一个N维向量，N即特征个数，向量分量是特征的权重。将这些向量都保存下来。给定一个未知文本，首先生成它的特征向量，搜索之前的向量，找出相似度最接近的K个样本，在K个样本中出现次数最多的类别即为答案。相似度可以通过欧几里得或cosin来度量。

      可以发现，KNN是一种懒惰的方法，没有学习过程，只是存放所有训练实例直到接到分类命令才建立分类。正因如此，KNN训练过程较快，而且随时可以添加新训练样本。但分类时间复杂度较高，训练样本的存储也需要较大空间开销，有看法认为在小数据集上KNN表现优异。KNN在多类分类问题上表现也很不错。

      当然，在实现的时候，可以进行一些优化：倒排索引。实现方法是将每个词设一个指针，指向包含该词的所有文档的序号。这样在查询时先找到与待分类文本有交集的训练文本向量，然后再计算相似度。

      Rocchio与KNN类似，只不过它不是保存每个训练文本的向量，而是先计算每类文档向量的平均值作为类别特征向量，即用一个向量代表一个类。对于待分类的文本，只需要与类别向量计算相似度，选取最相似的就OK了。该算法简单易行且分类速度较快。

 

贝叶斯

       朴素贝叶斯（Naive Bayes）是一种统计学分类方法，它基于贝叶斯定理。从理论上，朴素贝叶斯分类的出错概率最小，就试验结果来看，朴素贝叶斯在大型数据集上表现出难得的速度和准确率。但它基于属性之间的条件独立关系，现实中往往是不成立的。小数据集上表现不好。

P( Category | Document) = P ( Document | Category ) * P( Category) / P(Document)

 贝叶斯的改进有诸如树扩展的贝叶斯（Tree Augument NB），加权贝叶斯（Weighted NB）和贝叶斯网络（Bayes Net）。

 

支持向量机

       支持向量机（Support Vector Mechine）是一种有坚实理论基础的新颖的小样本学习方法，不同于现有的统计方法。SVM的最终决策函数只由少数的支持向量所确定，计算复杂性取决于支持向量的数目，而不是样本空间的维数。SVM的目标是对特征空间划分的最优超平面，其核心思想是最大化分类边际。缺点是难以适应大规模训练样本，对多类问题效果不好。

 

决策树

       决策树（Decision Tree）是一种贪心算法，采用自顶向下的方式在训练集的基础上构造决策树。深度越小的节点（特征）具有的区分能力越强（信息增益高）。分类时，取未知文本的属性，在决策树上测试路径由根节点到叶节点，从而得到该文本所属类别。它的优点是很好的抵抗噪声。缺点是大规模数据构造决策树效率比较低下。