韩 普1 刘艳云2
1 (南京大学信息管理系 南京 210093）郑州牧专教务管理
2 (解放军理工大学指挥自动化学院 南京 210007）
[摘要] 利用WEKA平台对中文文本进行了聚类实验研究。作为国外一款优秀的开源数据挖掘软件，在国内用来做中文信息处理研究的却很少。通过调整WEKA中特征选择参数，利用K-means算法对中文文本聚类实验。并采用召回率、准确率和F值对实验结果进行评价分析，希望能为相关研究提供一个参考基准。 [关键词]WEKA 文本聚类 文本特征 文本表示
张少川
[分类号]TP391
The Study of Chinese Document Clustering Based on WEKA
Han Pu1 Liu Yanyun2
1 (Department of Information Management, Nanjing University, Nanjing 210093, China)
2 (Institute of Command Automation, The PLA University of Technology & Science , Nanjing
210097, China)
[Abstract] This paper gives an experiment on Chinese document clustering based on WEKA.WEKA is an excellent open-source of data mining tool in abroad, but which is rarely used at home. We conducted the Chinese document clustering by K-means algorithm through adjusting the parameters in WEKA. Recall, precision and F-measure method was also used to evaluate the experiment. We hope to provide a reference for researchers in this field.
[Keywords]WEKA Document clustering Document feature Document representation
1、引言
聚类就是将一组物理或抽象的对象中相近的对象划分为一组的过程。通过对JSTOR数据库查询[1]，聚类一词首次出现在1954年的一篇处理人类学数据的文章标题里，直到今天，聚类算法及其应用研究仍然是人们研究的热点之一。在文本挖掘领域，文本聚类研究是一个非常重要方法之一。在网络信息迅猛增长的今天，文本聚类受到研究者更多的关注，与文本分类相比，基于文本聚类不需要人工构建繁 冗的文本训练集并可以对未知类别进行预测分类。
目前，文本聚类的研究成果主要用于浏览文本、显示文本集合、组织搜索引擎的返回结果等。如Vivisimo搜索引擎，其最引人注目的特就是对搜索结果进行聚类，让用户快速定位自己需要的信息。针对网络上每天大量更新的新闻信息，清华大学智能技术与系统国家重点实验室开发了新闻事件聚类系统[2]，该系统可以按专题对每天、每周和每月的新闻进行聚类。此外，文本聚类在多文档自动摘要、数字图书馆服务等领域都有着广泛应用。 WEKA是一款优秀的数据挖掘软件，在国外受到了研究者的普遍欢迎[3]，已有研究利用WEKA平台对20 Newsgroups 语料和Reuters-21578语料进行了英文文本分类聚类实验 [4]，甚至一些高校的信息处理课程开设有WEKA的实验。目前在中文文本分类聚类领域，国内使用的并不多见，但已经逐渐受到数据挖掘领域重视。对于文本聚类，WEKA主要提供了三个方面的处理功能：文本转换成文本串；文本串转化为特征-文档矩阵；多种聚类算法。除了
∗本文系2011年南京大学研究生科研创新基金资助项目”（项目编号：2011CW12）的研究成果之一。
简单的特征选择方法，另外还有稍复杂的方法如PCA 等。WEKA 是开源的，用户可以根据需要，只要遵从WEKA 的接口标准，便可改进已有算法或添加新算法。作为一个得到广泛应用的研究性软件一个值得关注的优点：可以提供一个可参照实验，相关研究可将此作为对照试验。
本文结构安排如下：第2节对文本聚类中的关键技术进行介绍；第3节对WEKA 中与文本聚类的有关技术予以分析；第4节利用WEKA 进行文本聚类实验并对结果进行分析；最后对工作进行了总结并指出进一步的研究方向。
2、文本聚类关键技术
2.1文本表示及权重
文本聚类首先要解决的问题是如何将文本内容表示成计算机可以处理的形式。在信息检索和自然语言处理等领域，人们提出了布尔模型、向量空间模型、概率检索模型、N 元语法模型等多种文本表示模型。在早期的文本分类聚类研究中，文本特征表示采用集合模型中的布尔模型，每个特征词在一篇文档中只有两种状态：出现或不出现，对应权重为0或1。文本特征表示使用最为普遍的是代数模型中最为经典空间向量模型（Vector Space Model，VSM)。该模型于1969年由Gerard Salton 提出。VSM 模型可以将给定的文本转换成一个高维度的空间向量，每个特征词代表该向量的一个维度。该模型的主要思想是：对于每一个文
档d，都被看成一个空间向量V(d)，V(d)=((t 1,w 1),(t 2,w 2),…,(t n ,w n ))。
其中，t i 为特征项，w i 为特征项t i 在文档d 中的权重，权重代表了特征项对于所在文档的重要程度。
一般来说，t i 可以是文档d 中的关键词或主题词，w i 一般定义为t i 在文档d 中出现的频率，该值可以采用0和1表示，或通过tf×idf 实现，后一种方法在权重计算中应用最为普遍。tf 反映了特征词在单个文档内的局部特征，idf 反映特征词在所有文档集合中的一个全局特征，通常情况下特征的权重需要综合词的全局特征的和在单个文档内的特征。w i 有很多种计算方法，公式1是经典的权重计算公式。
2southern杂交
(,)i W t d = (1)
向量空间模型的表示方法的优点在于将非结构化和半结构化的文本表示为向量形式，使得各种数学处理成为可能。最大特点是根据向量余弦定理可以方便的求解任意两个文档的相似度，向量空间模型是近些年来应用较多且效果较好的方法之一。空间向量模型也被称为Bag of words(Bow)模型[5]
。 2.2文本特征选择与特征降维
不难发现，如果将文档分词后所有的词都作为文本特征，构建的空间向量维度将会很大，甚至可以达到上万维，所以特征选择和降维几乎是文本处理中必不可少的步骤之一。英文需要Lemmatization，Stemming，并去除停用词如a, an, the 等虚词及没有明确含义的短语。中文也需要构建停用词表，去
除“的”、“他”、“我们”等词或短语。即便经过这些简单预处理之后，剩余的特征词数量依然很大。高度的维数不仅影响着聚类的效率，还会使聚类效果大打折扣。在文本聚类中，特征选择和降维主要有两个作用，一是提高分类效率，这对即时的文档在线聚类很重要；其次是增加聚类的准确性。衡量特征选择的标准是不能损失文档的意义或者尽可能少的丢失文档信息。文本聚类通常只能采用无监督的特征选择方法，需要类
信息的方法一般情况下无法直接用于文本聚类实验研究。文本聚类中常用的特征选择有下面几种方法：
（1）文档频率
特征词的文档频率（Document Frequency，DF）是指在待聚类文档集中出现该特征词的文本数量。在文本分类实验时，测试集的DF值一般可用训练集的DF值替代，在文本聚类中，通常采用计算特征词整个文档集的出现次数作为DF值，这与文本分类中DF值计算有所不同。
采用DF作为特征选择方法基本思想如下：特征词在很少的文章中出现可以定义为低频词，它不含或含有较少的类别信息；特征词在大部分的文档中出现，对文档的区分度低，将这样两个特征词从原始特征空间中移除。DF是最简单的特征选择方法，也非常易于理解，能够容易地用于大规模样本统计。将DF值低的特征词去除可以提高分类聚类的效率和准确度几乎成了共识，但在最近研究中发现DF低的
特征词比DF值高的词具有较多的信息量，不应该将它们完全移除，还有待于进一步研究。
（2）潜在语义分析
潜在语义分析（Latent Semantic Analysis，LSA）也被称为潜在语义索引（Latent Semantic Index，LSI）。它利用数学统计的矩阵运算方法，根据上下文关系锁定同义词，达到大大压缩特征-文档矩阵的目的，最终实现维度大大降低，但聚类效果却得到提升。LSA 在没有对文档句法和语法分析的情况下，利用统计学方法去发现并量化潜在语义结构，解决了向量空间模型中各特征词之间相互独立假设的不足。例如 “picture”, “photo”, “image”
三个单词表达的意思非常接近，在向量空间模型中，它们是没有任何关系的，LSA方法便可以统计这些单词上下文出现的情况，出这些同义词。LSA方法在文本信息检索领域取得了很好的成绩，将信息检索提高了10%-30%[6]。
（3）主成分分析
主成分分析（Principal Component Analysis，PCA）实际上是一种通过投影降维的方法。它利用线性变换的数学思想，将数据变换到一个新的坐标系统中，根据数据方差数值大小投影于不同的坐标上，保留方差比较大方向上的投影。高维度的原始矩阵经过PCA方法处理后，仅保留文本的主要特征。主成分分析方法是聚类分析中对数据进行降维的常用工具之一。
潜在语义分析和主成分分析方法比较复杂，在某些情况下，对于那些更新频率低的文档，可以将其对应的矩阵预先计算好。如果实时聚类要求较高，在数据量较大时，在聚类效率和速度不占优势。
除上面的方法之外，还有选择词性（POS）的方法，识别命名实体的方法，采用词典或本体映射的方法等等，通常情况下，需要根据不同应用情况，选择一种或多种相结合的方法完成特征的抽取和选择。
2.3文本相似度计算
张海钦
文本相似度，也称文档距离，是聚类过程的一个重要环节，相似度的计算方法选取不同，造成的聚类结果也不一样。在聚类实验开始之前，首先需要确定聚类所采用的相似度或距离的方法，并不是每一种聚类算法都支持所有的相似度计算方法。在文本分类聚类中，相似度的计算主要有两类：基于空间距离和基于向量余弦夹角的方法。
（1） 基于空间距离的方法
对于有n个特征属性的文档集合来说，m个文档可以看作n维空间中的m个点。我们可以用点之间的距离来度量文档之间的距离，如公式2。
11(,)1(,)1i j i j ij sim V V d V V d ==++ (2)
d ij 典型的距离公式明考夫斯基(Minkowski)距离、欧氏 (Euclidean)距离、曼哈顿(Manhattan)距离等。最常见的距离度量方法是欧氏距离（公式3），在聚类分析中应用的较广。
ij d
(3)其中，第i 篇文档的特征向量和第j 篇文档的特征向量分别用（w i1, w i2,…, w in ）和（w j1, w j2,…, w jn ）表示。其中d ij 表示文档i 和文档j 之间的距离。
（2）基于向量余弦夹角的方法
trus当文本被表示成空间向量模型时，可以借助向量夹角来表示文本之间的相似程度。夹角越小，说明文本匹配程度高，反之匹配程度就低。用余弦计算法来计算两个文本之间的相似度定义如下： 121212(,)()/||||||||cosine d d d d d d •= ,
(4)其中，分子是d 1和d 2的点积，||d||是向量d 的长度。公式的物理意义表示两个向量空间夹
角的余弦数值。 上面的相似度计算方法是文本分类聚类中比较常用几种方法，尤其是基于向量余弦夹角的方法应用最为普遍。除此之外，还有基于集合模型的Jaccard 系数的方法、字符串编辑距离的
方法、皮尔逊积差系数（Pearson Correlation Coeafficient）的方法等等。 3 、WEKA 中文本聚类技术
3.1文本预处理
（1）文件目录结构转换
WEKA 提供了文本预处理的功能，为确保能够使用这些文本的预处理功能，在使用之前，需要按照WEKA 要求的格式存放文件，如果不采用WEKA 的预处理程序，必须保证WEKA 的输入文件格式为.arff 文件，并且文件内容需要严格遵从其格式要求。TextDirectoryLoader 和StringToWordVector 工具提供了文本预处理的基本功能。TextDirectoryLoader 继承了TextDirectoryToArff 类。如不通过编写代码，可以在simple CLI 简单命令行窗口中调用TextDirectoryLoader 程序。需要处理的文档必须在一个总根目录下，根目录下包含人工分类好的类别文件夹，类别文件下下存放文本文件，可以是txt 格式，也可以是html 格式。默认情况下，系统是不支持中文的处理，需要在RunWeka.ini 系统文件中更改字符编码，即使这样，WEKA 对中文的支持性依然不是很好，常常需要反复更改字符编码。根目录文件下最好存放在WEKA 的安装路行下。按照要求存放文件后，在simple CLI 窗口键入命令
onverters.TextDirectoryLoader -dir test > test.arff
test 为根目录文件夹，test.arff 为处理后生成的文件。出现成功的提示后，会在weka 根目录下生成了一个test.arff 文件，在该文件中，@data 行后的每一行记录一个文本文件内容及其所属类别，第一列默认为文件的类别，即根目录下面子文件夹的名称。在weka 3.6.3版本中，第一个类别的第一列缺少类信息，用户可以自行加上，但这并不影响后续的处理结果。
（2） 文件内容向量格式转换
国际民航组织接下来需要使用StringToWordVector 类将经过初步处理的文本串转换成向量格式，StringToWordVector 主要功能有：分词（中文需要嵌入中文分词组件）、计算每一个词的tf 和idf 值、文本长度归一化、特征词筛选、词干化（英文）、
去除停用词等功能。通过该步骤处理，得到的arff 文件是一个稀疏格式的“特征-文档”矩阵。arff 文件采用稀疏数据格式，可以节省存储空间。稀疏数据表示的格式为{index score}，index 是第index 个特征的索引，score 表示第index 个特征的量值。
在将文本字符串进行向量格式转换过程中，StringToWordVector 的功能主要实现特征权重计算及简单的特征选择的功能。通过WEKA 源代码我们发现，特征的权重计算中，WEKA
使用了下面的权重计算公式。
(,),()(/)i i W i d tf t d log N n =×(5)
t i 为特征项，W(i,d) 为特征项t i 在文档d 中的权重，C 是人工标记好的所有文档类别数目。tf(t i ,d) 为特征项t i 在文档d 中出现的次数，tf 在特征选择中有着重要作用，wordsToKeep 和miniTermFreq 的功能都是基于类别的tf 来实现，所以StringToWordVector 中特征选择的本质可以认为是通过词频tf 计算的。当选择normalizeDocLength 时，W(i,d) 将会被进行归一化处理，WEKA 的归一化处理利用了类信息，公式中的分子是各个类权重求和的平均值并开平方根，分母是W(i,d) 所在类的权重求和的平方根。此外，WEKA 没有对tf 值进行归一化处理，并且特征选择时将整个类作为一个大文档来对待。StringToWordVector 中有几个需要用户选择的参数[7]
，参数的选择直接决定生成的特征-文档矩阵的大小。
如果设置变量TFTransform 为false，tf 的值就是特征项t i 在类c 中出现的次数，不做任何处理。如果为true，则tf = log(tf+1)，即把原先记录的词频fij 变成log （fij+ 1），log 函数起到平滑作用，在权重计算中很有效。在StringToWordVector 中，涉及log 的计算均默认是以e 为底的对数，此处即tf = ln(tf+1)。
idf 为特征词的文档频率，为了参数平滑，一般需设置变量IDFTransform 为true，即idf=log(N/n i )。除此之外，还有一个非常重要的参数OutputWordCounts，如果设为false，特征项的出现频率非0即1，使用的是二值化表示，OutputWordCounts 的选择影响着tf 和idf 的值，为了提高聚类准确率，一般也将该参数的值设为true。
minTermFreq 和wordsToKeep 是选择保留特征项的两个参数，它们根据最小词频数（minTermFreq）和每个类最多保留单词数(wordsToKeep)过滤token；其本质是通过基于类的termFreq 对特征进行选择。两个参数均可以实现同一功能。 3.2文本聚类算法
在诸多的聚类算法中，基于划分的方法和基于层次的方法使用最为普遍。 WEKA 3.6.3版提供了11种聚类算法，包含标准k-means 算法、层次分类法、EM 算法等常用算法。WEKA 的代码是公开的，这些基本的算法如不能满足需要，可以方便的修改或新增算法。此外，WEKA 的Experiment 还提供了不同算法的同时比较功能，这对于需要进行不同算法比较分析提供了方便的途径。
4、 实验设置与聚类结果测评
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议