龚笔宏，冯是聪
北京大学计算机科学技术系 北京 100871
(gbh@net.cs.pku.edu)
摘要针对中文网页，比较研究了kNN和NB分类算法。主要的实验结果有:（1）kNN 的分类质量明显优于NB；（2）即使是同一个算法对于不同领域的文档，其分类能力也是各有差异的。从总体而言，NB算法对不同类别比较敏感, 是一种不稳定的分类算法。kNN的分类质量受领域的影响不大。 关键词机器学习，中文网页分类，kNN，NB，评测
A comparative study with kNN and N
B categorization
algorithms for Chinese Web pages
华南理工化工学院
GONG Bi-hong, FENG Shi-cong, LI Xiao-ming
Department of Science and Technology, Peking University, Beijing 100871
Abstract This paper reports a comparative study with kNN and NB categorization algorithms for Chinese Web pages. The main experimental results are: (1) kNN significantly outperforms NB in categorization quality; (2) Though for a same algorithm, categorization algorithms have different ability for different domain documents. In general, NB is more sensitive than kNN to different classes and the categorization performance of NB is less stable than kNN’s.
Keywords machine learning, Chinese Web page categorization, kNN, NB, evaluations 一、引言
随着Internet的飞速发展，Web上的网页数据量正在迅猛地增长。为了有效地组织和处理海量的Web信息，需要实现网页的自动分类。从文档分类的准确性来看，人工分类要优于自动分类，但是自动分类在效率上要大大优于人工分类。对于Web上的海量信息而言，单纯使用人工分类代价高昂而且是不现实的。因此，网页自动分类便成了快速且有效地组织网络上海量信息的一个重要技术。
文档自动分类(Automatic Text Classification，ATC)是网页自动分类的理论基础。所谓文档自动分类就是指定文档和预先定义类之间的类属关系[8]。目前，已经出现了多种文档自动分类算法。文献[2]比较研究了k-Nearest Neighbor(kNN)、支持向量机(Support Vector Machines, SVM)、简单贝叶斯(Naïve Bayes，NB)、Linear Least Squares Fits(LLSF)、Neural
1本课题得到国家973重大基础研究项目基金（G1999032706）资助。
Network(NNet)等分类算法对英文普通文本的分类效果。实验结果表明，当训练集中每个类的正面实例比较少(少于10个)的情况下，SVM、kNN、LLSF的性能明显优于NNet和NB算法。但是同普通英文文本相比，中文网页具有自身的特性：(1)中文网页使用中文编辑。不像英语单词之间存在自然的间隔，中文需要分词处理。而且分词的效果能够显著地影响分类效果；(2)网页使用超文本设计。它包含大量的HTML标签和超链接。可以利用这些信息来改进分类的质量；(3)网页通常包含大量的“噪音”。同普通文本相比，网页的设计比较随意，通常包含各类广告，设计人员的注释以及版权申明等无用信息。有时同一个网页甚至会包含多个不 同的主题。因此，针对中文网页，文献[2]
的结论是否还正确，目前还没有很明确的结论。本文使用相同的中文网页数据集来比较kNN和NB两个比较常见的分类算法。
本文如面的部分是这样安排的：第二节简要介绍了KNN 以及NB 算法；第三节为本文的主体部分，给出了相关实验数据及其分析；第四节总结了全文并指出未来的工作方向。
二、分类算法
1. kNN
kNN分类算法是一种传统的基于统计的模式识别方法。算法思想很简单：对于一篇待分类文档χv
，系统在训练集中到k个最相近的邻居，使用这k个邻居的类别为该文档的候选类别。该文档与k个邻居之间的相似度为候选类别的权重，然后使用预先得到的最优截尾阈
值，就可以得到该文档的最终分类列表。kNN算法的定义如公式(1)所示[2]
。
j j i kNN
d i j b c d y d sim c y i −=∑∈),(),(),(v r
v v
v χχ (1)
其中：
χv
为一篇待分类网页向量表示；d v
为训练集中的一篇实例网页向量表示；c j 为一类别；
}1,0{),(∈j i c d y v （当d 属于c v
j 时取1；当d v 不属于c j 时取0）
；b j 为预先计算得到的C j 的最优截尾阈值；
),(i d sim v
v χ为待分类网页与网页实例之间的相似度，由公式（2）计算得到：
|
|||,d x d
x d x Cos r r r r ⋅>=< (2)
kNN 算法本身简单有效，它是一种lazy－learning 算法，分类器不需要使用训练集进行训练，训练时
间复杂度为0。kNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN 的分类时间复杂度为O(n)。
在实验中我们取 k = 20，仅保留相关度最大的20个实例网页。具有相同类别的实例的
相关度相加作为待分类网页的类别相关度。最后，我们把这些实例的类别为候选类别。
2. NB
NB算法是基于贝叶斯全概率公式的一种分类算法。贝叶斯全概率公式的定义如公式(3)所示[2]
。
)
()
(*)|()|(B P A P A B P B A P =
(3)
给定一个类c 以及文档d(a 1，a 2，…，a n )，其中a i 表示文档中出现的第i个特征项，n为文档中出现的特征项的总数。根据全概率公式，可以得到公式(4)：
)
()
(*)|()...|(*)|()()(*)|()|(21d P c P c a P c a P c a P d P c P c d P d c P n =
=
(4) 其中：P(c|d)表示文档d属于类别c的概率；P(c)表示待分类的文档所处的领域中，文档
属于这个类的概率。在具体的计算时，可以分别用训练集中属于这个类的文档所占的比例代替；P(a i |c)表示在类别c中特征项a i 出现的概率。可以近似地用特征项在训练集中所有属于这个类的文档中的出现次数与训练集中该类别的文档总数之比值表示。
由此可以看出，NB 算法假设文档之间的特征项都是相互独立的。但是，这一假设缺乏严格的理论推导作为基础，无法保证它的正确性，这也在一定程度上限制了算法的性能。
NB算法需要使用训练集对分类器进行训练，也就是需要分别计算每个P(a i |c)。假设训练集共有m个类别，n个特征项，待分类文档共有k个特征项，那么训练的时间复杂度为O(m*n)。分类的时间复杂度为O(k)。
三、实验结果及其分析
1. 实验设置
为了系统的比较研究kNN 和NB 分类算法，我们按照下面的方案实现了一个中文网页分类器。
(1) 数据集
中文网页数据集是实现中文网页自动分类的前提和基础。但是到目前为止还没有出现标准的中文网页数据集。为此，我们给出了一个全新的基于层次模型的中文网页数据集。它包括11876个训练网页实例和3695个测试网页实例。网页分类体系从总体上可以分为学术性和非学术性两大类，包含三个层次，12个大类，共739个类别。其中学术性类别按国家标准GB/T 13745-92《学科分类与代码》分类。每个类别平均有15个训练实例和5个测试实例。为方便起见，我们把12个大类从1到12分别编号，本文实验使用的训练集中类别及实例数
量的分布情况如表1所示2
。
2
可以免费提供给有兴趣做类似研究工作的同行，燕穹产品号：YQ-WPBENCH-V1
表1 训练集中类别及实例数量的分布情况表窄播
编号 类别名称 类别数训练实例数
1 人文与艺术 24 419
2 新闻与媒体 1
3 29
4 3 商业与经济 48 1343 4 娱乐与休闲 88 1814
5 计算机与因特网58 1041
6 教育 18 301
7 区域 53 1070
8 自然科学 113 2082
9 政府与政治 18 352 10 社会科学 104 2069 11 医疗与健康 136 2295 12 社会与文化 66 1329
总计
739
11876
(2) 评价指标
由于Macro-F 1可以显示分类器的整体性能，因此，我们使用Macro-F 1 值为分类器性能的
评价标准。F 1如公式(5)所示[2]
。Macro-F 1 如公式(6)所示。
r p pr F +=21 (5) Macro-F 1 = ∑−=1
11m i i F m (6)
其中：
p 为查准率；r 为查全率；m 为训练集类别数。
植兰
我们首先使用公式(5)计算每个类的F 1值，然后使用公式(6)计算Macro-F 1。 (3) 特征选取
为了提高分类算法的效率，需要在不牺牲分类准确度的前提下降低特征空间的纬度。文献[]比较研究了IG、DF、χ2
产量定额(CHI)、MI、TS等5个特征选取算法。结果发现IG、CHI算法最有
效，本系统采用CHI方法为基本的特征项选取算法，其定义为公式(7)所示[3]
：
)()()()()(2
2
),(D C B A D B C A CB AD N c t +×+×+×+−×=
χ (7)
其中：
A 为t 和c 同时出现的次数；
B 为t 出现而c 没有出现的次数。
C 为c 出现而t 没有出现的次数；
D 为t 和c 同时没有出现的次数。N 为所有训练文档数。 (4) 阈值策略
根据公式（1），对于kNN分类算法需要预先确定每个类的最优截尾阈值。我们选用RTCut
阈值策略[4]
，并使用公式 (8) 来计算每个类的阈值。
20
))|(())|((max()|(()|(i
d c f avg d c f d c f avg d c f ×−+
=′ (8)
其中：avg(f(c|d))为f(c|d)的平均值；max(f(c|d)为f(c|d)的最大值；f’(c|d) 是计算得到一个新阈值；i为大于1小于20的整数。当macro-F 1 最优时，我们选择此时的f’(c|d)为该类的阈值。 2. 实验结果及其分析
表2给出了kNN和NB对12个类别的分类结果。图1为kNN、NB分类结果的柱状图表示。其中横轴表示类别编号，纵轴表示Macro-F 1值。从图1可以看出，kNN分类算法明显由于NB 算法，对于所有类别，kNN的分类结果都优于NB。从图1还可以看出，即使是同一个算法对于不同领域的文档，其分类能力也是各有差异的。在“医疗与健康”领域，kNN的Macro-F 1达到最高值0.8299；在“新闻与媒体”领域，kNN的分类Macro-F 1达到最低值0.4228。同样，对于“医疗与健康”领域，NB的Macro-F 1达到最高值0.5031；在“政府与政治”领域，NB 的Macro-F 1达到最低值0.0238。从总体而言，NB算法对不同类别比较敏感, 是一种不稳定的分类算法。kNN的分类质量受领域的影响不大。
表2 kNN 和NB 分类结果比较
编号 名称 KNN Macro- F 1NB Macro- F 11 人文与艺术 0.5859 0.0923 2 新闻与媒体 0.4228 0.0286 3 商业与经济 0.5143 0.0632 4 娱乐与休闲 0.8028 0.3415 5 计算机与因特网0.7236 0.3583 6 教育 0.48
42 0.0414 7 区域 0.5966 0.1954 8 自然科学 0.6642 0.3472 9 政府与政治 0.7059 0.0238 10 社会科学 0.6274 0.3065 11 医疗与健康 0.8299 0.5031 12 社会与文化 0.5958 0.1694
平均
0.6294
0.2059
图1 kNN与NB分类结果的比较
四、总结及进一步工作
本文应用相同的中文网页训练集和测试集，比较研究了kNN和NB分类算法。主要的实验结果有:(1)kNN的分类质量明显优于NB，本文的结论同文献[2]的结论一致；(2)即使是同一个算法对于不同领域的文档，其分类能力也是各有差异的。从总体而言，NB算法对不同类别比较敏感, 是一种不稳定的分类算法。kNN的分类质量受领域的影响不大。本文进一步的工作有:(1)同时比较其它分类算法，如SVM，LLSF等；(2)针对中文网页的特性，改进已有的分类算法或提出新的分类算法；(3)目前的分类器没有考虑分类对象的领域属性，不管是任何内容的文档，都统一使用同一种算法进行分类，这样在很大程度上限制了分类准确率的提高。因此，作者的进一步工作是对不同的领域的文档采用不同的分类算法，从而提高准确率；(4)通过考虑特征项之间的语义关系来提高中文网页分类器的质量；(5)根据用户的反馈信息，增量训练分类器，逐步提高分类器的质量。
致 谢
在这里，我们首先要感谢李晓明老师帮助对本文的修改和定稿；其次要感谢“搜索引擎个性化查询服务”项目小组的单松巍、张志刚同学在中文网页分类器实现过程中给予的帮助；最后，我们还要感谢北京大学物理学院的陈硕、光华管理学院的杨娉、经济学院的黄欢、生物学院的刘贤伟等40多位来自不同专业的同学。正是他们的辛苦工作，中文网页自动分类系统分类目录和实例集的收集整理工作才能够顺利完成。
参 考 文 献
1S.Chakrabarti, M.Joshi, V.Tawde. Enhanced topic distillation using text, markup tags, and hyperlinks. ACM SIGIR, 2001
2Yiming Yang, Xin Liu. A re-examination of text categorization methods. Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99, pp 42--49), 1999
3Yiming Yang, Jan O. Pedersen. A comparative Study on Feature Selection in Text
五月卅一日急雨中
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议