文本分类算法-CADAL数字图书馆知识标准规范及应用研究

4.4.2.1 K-近邻算法(K NN)

K-近邻定义:给定一个曲面上的无规则点的集合P={Pi(x i,y i,zi),i=1,2,…,n},某个点定义为V(x v,y v,z v),则称P中距离点V最近的k个点为点V的m邻域点集,记为:MNB|V|={P 1,P 2,…,P m},称为点V的K-近邻,它体现了该点V的部分信息。K-近邻中的每个点称为点V的邻近点。

K-近邻算法(K nearest neighbors,K NN)是一种应用广泛的基于距离度量的分类方法。K-近邻算法的整个训练集不但包含数据集,还包含每个元组期望的类别标签,事实上训练数据本身就是一个模型。当对一个新元组进行分类时,必须首先确定它与训练集中的每个元组之间的距离,然后进一步考虑训练集中与新元组相距最近的元组。新元组将被分配到一个类中,这个类包含了K个最近元组中的最多的元组。K-近邻算法的优点是事先并不要求知道待分样本的分布函数,因此具有直观、无须先验统计知识、无需学习等特点,从而成为非参数分类的一种重要方法。

K-近邻算法描述如下:

(1)根据特征项集合重新描述训练文本向量。

(2)对新文本进行特征词分词,确定新文本的向量表示。

(3)从训练文本集合中得出和新文本最为相似的K个文本,其中,d i和d j分别是训练文本集合、待分文本集合中的文本,V是已经选定的近邻数。

(4)对新文本的K个邻居依次计算每个的权重。

(5)对计算好的K个邻居比较类的权重,最后将文本分到权重最大的类别中。

K-近邻算法也有缺点,由于K-最近邻分类器认为每个属性的作用都是相同的,都是赋予相同权值的,这样在属性集包含有许多不相关属性时,就会误导分类过程。K-近邻算法很容易受到噪声影响,尤其是样本点中孤立点的影响。另外,K值的选取是根据每类样本的数目和分散程度选取的,对不同的应用选取的K值也就不同,最终也会影响到分类结果。

4.4.2.2 朴素贝叶斯分类(NB)

贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。朴素贝叶斯算法(Naive Bayesian,NB)是应用最为广泛的分类算法之一。

朴素贝叶斯分类器(Naive Bayes classifier,NBC)起源于古典数学理论,具有坚实的数学基础,以及稳定的分类效率。同时,NBC模型所需参数比较少,对缺失数据不是很敏感,算法本身也比较简单。从理论上讲,NBC模型与其他分类算法相比具有最小的误差率。但是,在实际应用过程中并不是这样的,这是由于NBC模型假设属性之间是相互独立的,事实上该假设在实际应用中是不成立的,这就给NBC模型的正确分类带来影响。

朴素贝叶斯分类或简单贝叶斯分类的工作过程如下^[3]:

(1)每个数据样本用一个n维特征向量X=x 1,x 2,…,x n(www.xing528.com)

{}表示,分别描述对n个属性A 1,A 2,…,A n样本的n个度量。

(2)假定有m个类C 1,C 2,…,Cm。给定一个未知的数据样本X(即没有类标号),分类法将预测X属于具有最高后验概率(条件X下)的类。即是说,朴素贝叶斯分类将未知的样本分配给类Ci,当且仅当

这样,最大化。其最大的类C i称为最大后验假定。根据贝叶斯定理

(3)由于P(X)对于所有类为常数,因此只需要 (Ci)最大即可。如果类的先验概率未知,则通常假定这些类是等概率的,即P(C 1)=P(C 2)=…=P(Cm),并据此只对最大化;否则,最大化。注意,类的先验概率可以用 计算,其中si是类C i中的训练样本数,而s是训练样本总数。

(4)给定具有许多属性的数据集,计算的开销可能非常大。为降低计算的开销,可以将类Ci条件进行独立的朴素假定。设定样本类的标号,假定属性值是相互条件独立的,也就是在属性之间不存在相互依赖关系,这样,概率可以由训练样本进行估值。

1)如果A k是分类属性,则,其中sik是在属性A k上具有值x k的类C i的样本数,而Si是C i中的训练样本数。

2)如果A k是连续值属性,则通常假定该属性服从高斯分布,因而,

其中,给定类Ci的训练样本属性A k的值,g (x k,μCi,σCi)是属性A k的高斯密度函数,而μCi,σCi分别为平均值和标准差。^[4]

(5)为对未知样本X分类,对每个类Ci,计算。样本X被指派到类Ci,当且仅当

换言之,X被指派到其最大的类C i。

4.4.2.3 决策树算法

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上,决策树是通过一系列规则对数据进行分类的过程。

20世纪60年代末,开始提出决策树方法。到70年代末,Quinlan在先前的决策树方法基础上提出了ID3算法。该算法的作用是在于减少树的深度,但是该算法的缺点是忽略了对叶子数目的研究。C4.5算法是在ID3算法的基础上进行优化和改进,从预测变量的缺值处理、剪枝技术、派生规则等角度做了较大改进,既适合于分类问题,又适合于回归问题。