| |||||||||||||||
软件共享：
|
DRAP文本分类系统简介与下载谭松波
DRAP是中科院计算所谭松波博士研制的一种新型分类系统。该系统已在大规模高速数据流过滤中得到应用。在普通PC上它的过滤(分类)速度可以超过4M/秒。若用10k来估计一篇文本的长度，那么本系统每秒钟可以过滤(分类)约400篇文本。 1．原理与算法1.1分类器偏差“没有免费的午餐定理”[6]告诉我们：任何一种模式分类算法都不存在“与生俱来”的优越性。换句话说，所有分类器都存在一定程度上的“分类器偏差”。原因很简单，因为所有分类器都建立在某种假设(模型)之上。于是，当分类器模型与数据的分布相一致时，分类器偏差就小，分类精度就高；反之，则分类器偏差就大，分类精度就低。 朴素贝叶斯就基于两个假设：其一就是特征独立性假设。当分类数据集的特征依赖性较强时，分类质量就比较差，反之亦然；其二就是假设每个类中的文本都是基于某个混合模型产生的，也就是混合模型与类别之间存在一一对应关系。但许多实际数据并不遵守这个假设。比如，垃圾邮件过滤问题。垃圾邮件通常包含许多子类别，如广告、非法信息等众多主题；正常邮件也包括很多主题。这样，混合模型与类别之间的一一对应关系就很难建立。此时，分类器就存在较大偏差。 中心法建立在这个假设之上：每个样本到它所在类的中心的距离(相似度)要小于(大于)它到其它类的中心的距离(相似度)。但这个假设也常常被实际问题所违背。我们来看一个例子，假如有一个数据集包括A、B两类(见图1)。A类样本呈椭圆形分布；而B类样本呈圆形分布。根据中心法的计算公式，我们可以计算出A类中心CA和B类中心CB。 显然，这种数据分布并不遵守中心法的基本假设。从图中可以看出，A类中位于中线右边的大部分样本到A类中心的距离要大于它到B类中心的距离，因此就会被误分到B类。这个图非常直观地解释了实际数据分布与分类器假设之间存在冲突。而这个冲突就导致了分类器精度下降。
图1 圆形与椭圆形分布对中心法的影响 最近邻分类器假设训练集样本的类间分布是基本均衡的。但实际中很多数据都是不均衡的。如路透社的语料Reuter。于是，最近邻就存在倾向于大类的分类决策。图2就是一个标准的不均衡问题。A类为大类，B类为小类。假设样本d来自于B类。并假定最近邻的邻居个数为25。此时，最近邻算法选定的邻居为圆圈所圈定的25个样本点。其中19个来自A类；6个来自B类。根据最近邻决策规则，样本d很可能被误分入A类。这个图说明了最近邻对样本不均衡数据存在较大的偏差。
图2 样本不均衡性对最近邻分类器的影响 1.2 基本原理本节以中心法为例来进行说明。 前一节指出，中心法假设每个样本到它所在类的中心的距离(相似度)要小于(大于)它到其它类的中心的距离(相似度)。但是，这个假设常常被实际问题所否定。于是，传统中心法的分类精度就会受到影响。同样，训练集分类精度也会受到影响。 一个直觉上的解决方案就是，训练集误差可以用来调整中心向量，以至于分类器偏差能够不断地被减小。算法的执行过程大致是：首先在整个训练集上计算中心向量；然后利用误分样本来拉近正确类别中心；同时推远错误中心。举例来说，如果A类样本d被误分入B类，那么，该算法就把A类中心向样本d拉近；同时把B类中心向样本d推远。执行这样的操作后，样本d将更可能被正确分类。 我们来看一个例子。假如一个训练样本集只包括两类，如A、B类，见图3(a)。样本d来自于A类。Aoriginal、Boriginal代表A、B类的原始的归一化中心。Adragged表示拉近后的归一化中心、Bpushed表示推远后的归一化中心。从图3(a)上，我们可以看出样本d到Aoriginal的距离要大于它到Boriginal的距离；也就说样本d到Aoriginal的相似度要小于它到Boriginal的相似度。根据中心法分类规则，样本d被误分入B类。 为了使中心分类器正确对样本d进行分类。拉推算法使用“拉”操作来增大d到A类中心的相似度(减少距离)；同时使用“推”操作来减少d到B类中心的相似度(增大距离)。经过拉推操作之后，我们从图3(a)中可以看出，d到A类中心的相似度要大于d到B类中心的相似度。于是样本d就能够被修正的中心法正确分类。这便是拉推策略的基本原理。 让我们再回到图1所提到的例子。由于A类中位于中线右边的大部分样本被误分到B类，那么，根据拉推策略，这些误分样本将向右拉动A类中心；同时向右推动B类中心。这种拉推操作直到所有样本都能被正确分类时才终止。此时，修正后的类中心如图3(b)所示。从图中可以看出，A类中心与B类中心之间的中线已经向右移到A类之外，此时，根据中心法分类规则，所有样本都能够被正确分类。
图3(a) 拉推策略示意图
图3(b) 修正后的中心示意图
我们再来看更复杂的一种情况，假如有一个数据集包括A、B、D三类(见图3(c))。A类样本呈椭圆形分布；B类与D类样本呈圆形分布。根据中心法可以算出中心CA、CB、CD。中心CB、CA之间的中线为中线BA；中心CD、CA之间的中线为中线DA。 图3(c) 含三个类的数据分布示意图 此时，根据中心法决策规则，A类中位于中线BA右边的大部分样本将被误分入B类；A类中位于中线DA左边的大部分样本将被误分入D类。根据拉推策略，A类中被误分入B类的样本将CA向右拉动，同时将CB向右推动；而A类中被误分入D类的样本将CA向左拉动，同时将CD向左推动。因此，随着拉推策略的不断执行，CA将左右来回运动而达到稳定；CB将一直向右运动直到稳定；CD一直向左运动直到稳定。因此，最终修正后的中心如图3(d)所示。此时，CA基本保持不动，而CB却向右移动到B类的外边，同时，CD却向左移动到D类的外边。相应地，中线BA与中线DA都移动到A类之外，此时，从图中可以看出，所有样本都能够被正确分类。 图3(d) 修正后的三个中心示意图 2. 技术特性l 支持中文分类 l 支持英文分类 l 支持中文最大匹配分词 l 支持特征选择 l 支持英文词根还原 l 支持停用词去除 l 支持双语种分类，即可以同时对中英文进行分类(需要定制) l 支持多线程分类(需要定制) 3. 功能对比3.1 测试语料集3.1.1 OHSUMED它是一个医学文摘语料库。该语料库包含348,566份文本文档，这些文档来自大型医学信息数据库MEDLINE，每份文档的内容均为1987年至1991年这5年间发表在270种国际医学杂志上的论文的标题和摘要。文本类别为每份文档的检索项，总的类别个数高达18,000多个。OHSUMED也是一个多标签文本分类问题。 在本文中，我们采用了Han[7]处理后的一个单标签OHSUMED子集(ohscal)进行实验。该子集包括11,162篇文档。这些文档分布于以下10类：Antibodies；
Carcinoma； DNA；
In-Vitro；Molecular-Sequence-Data；
Pregnancy； Prognosis；
Receptors；
Risk-Factors；Tomography。 3.1.2 WebKBWebKB来自于许多大学计算机系1997年的主页。共有网页8,300篇。这些网页被分为7类：student；faculty；staff；course；project；department；other。在这7类中，student、faculty、course与project是最大的四类。于是WebKB就出现两个版本：WebKB-7与WebKB-4。在本文的实验中，我们采用WebKB-4。总网页数为4,199。 3.1.3 Reuter它是路透社1987间播发的21,578篇财经新闻。每篇新闻可能属于一个或多个类别。最多的达16个，平均1.2个。而且这21,578篇财经新闻还包含许多只有标题，没有内容的报道。该语料是一个典型的多标签分类语料。要是每篇报道只取一个标签的话，就可以作为一个单标签分类语料。该语料还是一个典型的样本严重不均衡的语料集。因此该语料集可以测试许多算法在不均衡语料上的稳定性。在本文的实验中，我们处理后的单标签语料共有10,346篇文档，92个类别。我们把它叫做Reuter-92。 3.1.4 NewsGroup它是由互联网用户在Usenet上张贴的19,997条消息组成的。这些消息均匀分布在20个不同的新闻组中，每个新闻组有1,000条消息(仅有一个新闻组含997条消息)，每个新闻组对应着一个文本类别。NewsGroup是一个典型的单标签文本分类语料。这些新闻组的具体名称如下：alt.atheism；comp.graphics；comp.os.ms-windows.misc；comp.sys.ibm.pc.hardware；comp.sys.mac.hardware；comp.windows.x；misc.forsale；rec.autos；rec.motorcycles；rec.sport.baseball；rec.sport.hockey；sci.crypt；sci.electronics；sci.med；sci.space；soc.religion.christian；talk.politics.guns；talk.politics.mideast；talk.politics.misc；talk.religion.misc。 3.2 对比分类器我们采用三种经典的分类器作为对比：最近邻(KNN)、朴素贝叶斯(Naïve
Bayes)、支持向量机(SVM)。 3.3 实验设置我们采用三份交差验证。首先把整个语料分成三份，然后取其中的两份进行训练，剩余一份作测试。再把这三次的平均结果作为实验结果。实验设备是一台普通计算机，主频为3.0Ghz，内存为512M。 特征选择算法采用信息增益，即IG。 最近邻算法的邻居个数取为13。不采用阈值，因为阈值调整的计算量很大。 贝叶斯算法采用多项式模型。 支持向量机采用SVMTorch(www.idiap.ch/~bengio/projects/SVMTorch.html)。SVMTorch是由瑞士IDIAP机构开发的。IDIAP机构是一个半私有且非营利性的研究所，隶属于瑞士联邦科技研究院。SVMTorch专门为大规模分类问题量身定制，它可以直接处理多类分类问题[8]。 3.4 评价指标为了更客观的评价分类器的性能，我们采用F1-Measure来进行评价。为了计算F1-Measure，我们需要计算召回率与精确率，然后计算F1-Measure。微平均是对所有的类别计算一个F1-Measure；宏平均是对每个类别计算一个F1-Measure，再对求得的F1-Measure进行算术平均即得宏平均。 3.5 实验结果
根据上面的测试结果，我们得出精度与速度排名如下： 精度排名：DRAP(1)，SVM(1)， Naïve Bayes(3)，KNN(4) 速度排名：DRAP(1)， KNN(2)，Naïve Bayes(3)，SVM(4) 根据六种分类算法在四个语料集上的效率与性能比较，我们得出如下结论： 1、 DRAP， 综合性能排名第一。精度第一，速度第一。 2、 SVM，综合性能排名第二。精度第一，速度第四。
本系统的核心部分采用C++编码，界面采用VB开发平台。安装包是在VB6.0环境下使用VB自身的打包工具打包而成。安装后即可使用。 若你在试用中遇到任何问题，请及时与我们联系。为了便于理解我们给出如下运行图示：
图5 初始界面
图6 训练结果界面
图7 分类结果界面
图8 显示每篇文档的内容及分类结果界面
图9 评价结果界面
图10 软件关于界面
参考文献[1] 谭松波, 程学旗. 中心文本分类器的改进算法. PKDD 2007 |
