张雪松 贾彩燕
(交通数据分析与数据挖掘北京市重点实验室(北京交通大学) 北京 100044)
(北京交通大学计算机与信息技术学院 北京 100044)
(15120467@bjtu.edu.cn)
文本聚类是文本挖掘中的一个重要课题，是指在没有人工干预的情况下，将大量无标注的数据集根据文本间相似性划分成若干个类，使得同类内的文本相似度较大而类间的文本相似度较低.在文本聚类中要解决三大问题:1)数据的高维问题，解决此问题需要处理稀疏的数据空间或引用数据降维的方法；2)聚类算法在大规模文本集上聚类效果的问题，即聚类算法要有很好的精度和可扩展性；3)对类簇的主题描述，一个好的主题描述方法能够让人们直观地了解每个类簇所代表的主题.在文本聚类中,向量空间模型 (vector space model, VSM) [1] 是常用的模型，在VSM模型中，每个文本集中的词作为空间坐标系中的一个维度，每个文本是特征空间中的1个向量.尽管基于VSM的 K -means聚类方法在文本聚类中被广泛应用，但这种文本表示的方法存在高维问题，向量空间中的特征维度过高导致文本向量过于稀疏，影响聚类的效果，并且VSM模型使用单个词汇作为特征，忽略了词之间的语义关系.
基于频繁词集的文本聚类方法，可以解决传统文本表示的高维和语义缺失问题.频繁词集是指同时出现在一定比例的文本中的词的集合，这些集合在某种程度上能够反映出一些关于主题的语义.基于频繁词集的文本聚类首先挖掘出文本集中的频繁词集，将文本指派到与其具有相同主题的频繁词集中 [2] .Beil等人 [3] 提出FTC(frequent term-based clustering)算法和HFTC(hierarchical frequent term-based clu-stering)算法，该算法将挖掘出的频繁词集当作聚类初始簇，采用贪婪策略优先选择簇重叠度最小的频繁词集进行聚类，该算法采用一种局部最优策略，对项集的选择顺序过于依赖，算法效率较低.Fung等人 [4] 提出一种层次聚类方法，该算法同样将挖掘出的频繁词集当作初始簇，为解决类重叠问题，将每个文本通过打分函数划分到最适合的簇中，然后构建树，运用剪枝策略进行聚类.Zhang等人 [5] 提出的MC(maximum capturing)算法将挖掘出的频繁词集当作特征来表示文本，通过计算文本间共有的词集个数来度量文本间相似性并直接对文本进行聚类.为了充分挖掘语义关系，Hernández-Reyes 等人 [6] 考虑了文本中词集的语序，提出了基于最大频繁序列(maximal frequent sequence, MFS)的文本聚类方法.
除了基于频繁词集的文本聚类方法，基于LDA(latent Dirichlet allocation)的文本聚类算法 [7] 、SP K -means(spherical- K -means)算法 [8] 和GNMF(graph regularized nonnegative matrix factorization)算法 [9] 也是较流行的文本聚类方法.其中，基于LDA的文本聚类方法基于这样一个假设：一个文本中会包含多个主题，每个主题生成各种词语的概率服从多项分布，通过该聚类方法会得到一个文本在不同主题下的分布情况，即文本在各主题下的概率，最后将文本指派到隶属度最高的主题中.并且，通过统计出各个主题下词的概率分布，那些在该主题上概率高的词能够非常好地描述该主题的语义.GNMF是一种基于非负矩阵分解(nonnegative matrix factorization, NMF) [10] 的方法，该方法基于这样的假设：如果2个数据点在高维空间具有相近的几何分布，则在降维后的空间中2个数据点应该也相近.而NMF方法是近年来兴起的无监督聚类方法，其本身也是一种很有效的数据降维的方法，因此GNMF在文本聚类中可以解决文本维度过高的问题.SP K -means算法运用余弦相似度作为衡量文本间相似度的指标，将文本与初始中心间的相似度总和作为待优化的代价函数，在迭代过程中最大化全局代价函数并更新聚类中心.SP K -means运行速度快、内存消耗较小，因为采用余弦相似度，能够有效地处理大文本数据集 [11] .
本文引用频繁词集理论，提出了一种基于频繁词集的文本聚类方法(frequent itemsets based document clustering method, FIC).该方法首先挖掘出频繁词集，运用频繁词集来构建文本表示模型.将每个文本看作网络中的节点，通过度量2个文本间的相似性来构建边，从而构建成一个文本网络，运用社区划分的方法来实现文本的聚类.该方法不仅有效地降低了文本表示的维度，而且文本社区的引入建立了文本之间的关联关系，使得聚类效果得到了有效提升.
基于频繁词集的文本聚类方法是解决数据高维问题的一个重要方法，对于聚类精度也比传统模型有了进一步提高，同时能够更加具体地描述数据集中的每个主题.
FTC算法首先从文本集中挖掘出所有满足最小支持度的频繁词集，将每个频繁词集当作聚类的候选簇，然后通过一种贪心策略，从中选择与其他候选簇重叠度最小的作为结果簇，直到文本全部被指派到相应簇中为止.
由于一个文本通常会包含多个频繁词集，因此候选簇之间会出现重叠的现象，即一个文本可能会属于不同的候选簇，为了消除类间重叠，定义熵重叠度(entropy overlap) EO ( C i )来衡量候选簇 C i 与其他候选簇的重叠情况：
(1)
其中， D j 表示文本， f j 表示文本 D j 所支持的频繁词集的个数.式(1)反映了 C i 所支持的频繁词集在其他候选簇中的分布情况，值越大， C i 与其他簇的重叠度越高.
算法1 . FTC算法.
1) 从文本集中挖掘满足最小支持度( minsup )的频繁词集 F ={ F 1 , F 2 ,…, F n },每个频繁词集 F i 对应的文本集合构成候选簇;
2) 计算每个候选簇 C i 的熵重叠度;
3) 把熵重叠度最小的 C i 加入结果簇集 C 中;
4) 若文本 D j 包含在 C i 中，则将其在其他候选簇中删除;
5) 删除候选簇 C i ;
6)判断文本是否全部包含在结果簇中，如果没有则返回3)续执行，否则结束.
FTC算法虽然在降低文本维度和效率上较传统基于VSM模型的聚类方法提高了效率，但使用贪心策略选择结果簇无法达到全局最优，且对候选簇的选择顺序有依赖，在选择结果簇中会消耗大量时间.
FIHC算法由Fung等人 [4] 提出.步骤分为频繁词集挖掘、构建初始簇、建树、剪枝，最后得到树形结构的结果簇.此方法基于层次聚类，将文本集中挖掘出的频繁词集当作初始簇，在解决类重叠问题中，采用一种打分函数将文本归到最适合的类簇中，将初始簇构建成树结构，运用剪枝策略来实现聚类.其中的文本归档打分函数为
Score ( C i ← D j )= 
(2)
其中， Score ( C i ← D j )表示文本 D j 属于类簇 C i 的分数; global_support 代表全局频繁词集集合，指的是在所有文本集中满足最小支持度的所有频繁词集; cluster_support 表示簇频繁词集集合，它指的是将文本指派到其含有的初始簇之后，根据每个簇内的文本中频繁词集的出现频率筛选出大于某一最小支持度的频繁词集，并将其作为簇频繁词集,簇频繁词集是全局频繁词集的一个子集; x 表示 D j 中出现的既属于全局频繁词集集合又属于簇频繁词集集合的词集; x ′表示只属于全局频繁词集集合而不属于簇频繁词集集合的词集; n (·)是用来统计项集个数的函数.通过式(2)即可将文本对归到其最适合的初始簇中.
在树形结构中，每个节点代表1个类簇，为了得到指定数量的类簇或避免类簇描述过于具体，需要对树进行剪枝.其策略是：通过计算簇之间的相似度，将相似度大于相应阈值的2簇合并.公式如下：
Inter_Sim ( C a ↔ C b )= 
,
(3)
式(3)中通过计算 C b 到 C a 和 C a 到 C b 的相似度并取几何平均来得到2簇间的相似度.式(4)为计算单向相似度的公式.簇间相似度阈值为1，即将相似度大于1的2簇合并.通过这种方法实现对父子节点和兄弟节点的剪枝.FIHC算法在聚类效果和时间效率方面均优于FTC算法.
MC算法是一种直接对文本进行聚类的方法，利用文本中包含的频繁词集来度量文本之间的相似性.此方法运用频繁词集来表示每个文本，构建成文本相似矩阵 A ，其中 A [ i ][ j ]= MC_Sim ( D i , D j ).MC聚类的基本思想是：如果2个文本有最高的相似度，则这对文本应归入同一类簇中.例如：如果文本 D i 和 D j 在同一簇中，若文本 D k 和 D j 有最高的相似度，则 D k 将与 D i 和 D j 归入同一簇中.
算法2 . MC算法.
输入：待聚类的文本集合；
输出：不同簇下的文本集合.
1) 根据相似度构建相似矩阵 A ;
2) 寻找 A 中除0之外的最小相似度值;
3) 寻找具有最大相似度的未被归类的文本对;
4) 如果步骤3中寻找的最大相似度值与步骤2中的最小相似度值相等，则相应的节点对组成一个新的类簇，否则执行下列步骤：①如果文本对中的2个文本中任何一个都未被归类，则将2个文本对构成一个新的类簇;②若文本对中1个文本已被归类，则另1个文本也同样归于此类;③将矩阵 A 中文本对所对应的值置0，返回到步骤3;
5) 如果存在还未被归类的文本，则将其组成一个新的类簇.
由于在文本聚类中文本的类数大部分是预先设定好的，因此需要对MC算法聚成的类簇进行合并，将不同簇中文本间的相似度值的总和作为簇间的相似度然后进行合并：
MC_Sim ( C i , C j )= 
MC_Sim ( D m , D n ).
(5)
FIC算法框架图如图1所示.该算法运用频繁词集来表示文本和衡量文本间的相似度，这些频繁词集同时可以反映出一定的语义关系，使得相同主题下的文本间相似度较之不同主题下的文本相似度更高，运用频繁词集表示的文本相较于传统的VSM模型能够有效地降低维度，减小数据稀疏的问题.在构建文本网络后，可以引用社区划分或谱聚类的方法进行文本聚类，使得聚类方法更加灵活.
Fig. 1 Procedure of FIC
图1 FIC算法流程图
图1中的主要步骤为：数据预处理、频繁词集挖掘、文本表示、构建文本网络、社区划分和主题描述.数据预处理对原始数据进行分词和去掉停用词；然后对处理完的数据进行频繁词集挖掘，将用频繁词集表示的文本构建成文本网络之后进行社区划分，每个社区即为文本聚类中的一个类簇，簇中的节点即为文本；再对划分好的簇进行主题描述.下面将具体介绍算法中的关键步骤.
本文采用FP-Growth [12] 算法来挖掘频繁词集，在进行频繁词集挖掘时，根据文本的数量来设置最小支持度，对进行特征选择之后的文本直接进行频繁词集挖掘.下面给出定义：
定义1 . 文本数据库.将对文本进行分词、去停用词之后的文本组成文本数据库 D ={ D 1 , D 2 ,…, D n }.
定义2 . 频繁词集.通过频繁词集挖掘，得到频率大于最小支持度的频繁词集集合 F ={ F 1 , F 2 ,…, F m },其中 F i 表示1个频繁词集，1个频繁词集中包含1个或多个词语 F i ={ w 1 , w 2 ,…, w t }.
较之传统的VSM模型，本文采用基于频繁词集的文本表示模型.即用挖掘出的频繁词集来表示每个文本，构建文本-频繁词矩阵 M .其中矩阵 M 为0-1矩阵，通过衡量文本中是否含有频繁词集来赋值：
(6)
其中， M [ i ][ j ]表示矩阵 M 中文本 D i 对于频繁词集 F j 的值，若文本 D i 中含有频繁词集 F j ，则 M [ i ][ j ]=1，否则 M [ i ][ j ]=0.对于一个具体的文本可以直接将其中的特征单词用频繁词集来代替.通过这种方法可以有效降低文本特征维度，解决了文本稀疏的问题.频繁词集本身可以在某些程度上反映出文本的主题，它基于这样的假设：若某些词汇经常同时出现在同一文本中，则它们能够呈现出一定的语义关系，例如：{apple}表示水果类，{window}表示装饰类，若两词经常出现在同一文本，则作为频繁词集{apple,window}可以表示出计算机类.因此以频繁词集作为特征在度量文本间相似度时可以避免不同类别间的文本产生过大的相似度而影响聚类效果.
FIC算法将文本集中的每个文本当作文本网络中的节点，根据2文本之间的关联程度来建立边.文本间的关联程度常常用它们之间的相似度来度量，已有的相似度量方法有很多，例如余弦相似度和欧氏距离.本文采用Jaccard相似度来度量：
Jaccard_Sim ( D i , D j )= 
，
(7)
其中, Jaccard_Sim ( D i , D j )表示文档之间的相似度，分子表示2个文档之间共有的频繁词集的个数，分母表示2个文档一共含有的频繁词集的个数.通过此方法可以得到文本集中两两文本间的相似度权值，设置阈值 θ ，若2边相似度大于 θ 则在2个文本间建立1条边，构建成1个文本网络 G ={ V , E },其中 V 为节点的集合， E 为网络中边的集合.文本网络的构建，不仅使相似的文本间有边相连，而且也建立了文本与其他文本间的关联关系.
对于上述构建的文本网络，我们需要对其进行社区划分，得到网络中不同的社团，通过文本与节点的对应关系可以将文本直接匹配到对应的社区，即类簇.我们使用硬划分的社区划分方法，每个文本只能被指派到唯一的社区中，解决了类间重叠的问题.本文中选用 K -rank-D [13] 与谱聚类 [14] (spectral clustering)对网络进行划分.
K -rank-D算法是一种网络社区划分算法，此算法在基于 K -means的基础上，通过计算节点的pagerank中心性来进行初始中心的选择，解决了传统 K -means算法中随机选取初始中心对聚类结果的影响.此算法具有精度高的优点.
谱聚类是一种经典的图切割聚类方法，从图论的角度来说，聚类问题就相当于一个图的分割问题.即给定一个图 G =( V , E )，顶点 V 表示各样本，带权的边表示各样本之间的相似度，谱聚类的目的是要找到一种合理的分割图的方法，使得分割后形成若干子图，连接不同子图的边的权重(相似度)尽可能低，同子图内的边的权重(相似度)尽可能高.
算法3 . 谱聚类算法.
输入：待聚类的文本集合；
输出：不同簇下的文本集合.
1) 根据数据生成图的邻接矩阵;
2) 根据邻接矩阵生成拉普拉斯矩阵并进行归一化;
3) 求最小的前 K 个特征值和对应的特征向量，其中 K 为聚类的类簇个数;
4) 将特征向量用 K -means进行聚类.
因此，FIC算法采用以上2种聚类方法，组成FIC-S和FIC-K这2种算法进行文本聚类.
为了能够更加直观地了解每个类簇下的主题，我们需要对主题进行描述.对于每一个类簇内的文本，统计其中频繁词集的出现频率，将出现频率较大的频繁词集作为主题的描述词.
为了验证本文提出的文本聚类方法，我们选用3个文本聚类中标准的数据集来进行实验，对照实验选用常用的基于 K -means文本聚类方法 [15] 、SP K -means、MC、LDA、FIHC、GNMF算法.其中在MC算法中，根据不同的文本相似度量方案分成MC-1，MC-2，MC-3.这里我们选择精度较高的MC-1作为对照，在MC-1中2个文本间相似度的值为2个文本含有的共同频繁词集的个数.
本次实验采用文本聚类常用的标准数据集20-Newsgroup * http://kdd.ics.uci.edu/databases/20newsgroups/ 和Reuters-21578 * http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.html ，对于中文数据，选择文本分类语料库搜狗新闻数据 * http://www.sougou.com/labs/resources/list_yuliao.php .其中，20-newsgroup数据包括近20 000篇新闻报道，分为20个不同的新闻组，除了小部分文档，每个文档都只属于一个新闻组；Reuters-21578是文本分类的测试集，其中包含的文档来自于路透社1987年的新闻，搜狗新闻数据包括9个新闻类，共有17 910个文本.
由于FIC算法与MC同样采用频繁词集表示的策略，我们选择抽取和MC算法同样量级的数据，从以上数据集中随机抽取文档组成了5组测试集，测试集的详细信息如表1～6所示，其中R12,R5，R8来自数据集Reuters-21578,N4来自20News-group，C6来自搜狗新闻数据.
Table 1 Dataset in the Experiment
表1 实验中的数据集
Table 2 Description of N4
表2 N4数据描述
Table 3 Description of R5
表3 R5数据描述
Table 4 Description of R12
表4 R12数据描述
Table 5 Description of R8
表5 R8数据描述
Table 6 Description of C6
表6 C6数据描述
为了测试FIC算法的性能，我们采用文本聚类中常用的外部评价标准 F -measure.它经常被用作衡量聚类方法的精度，是一种平面和层次聚类结构都适用的评价标准. F -measure综合了召回率和准确率2种评价指标：
Recall ( K i , C j )= 
，
(8)
Precision ( K i , C j )= 
，
(9)
其中， n ij 表示簇 C j 中属于类 K i 的文本数.由召回率和准确率可得到表示簇 C j 描述类 K i 的能力计算:
F ( K i , C j )= 
，
(10)
聚类的总体 F -measure值则可用每个类簇的最大 F -measure值并采用该类簇的大小加权之后的总和:
(11)
F -measure值的取值范围在[0,1]，值越大表示聚类效果越好.
在进行数据的预处理时，我们运用特征选择 [16] 的方法.文本经过分词和去停用词之后，依然会保留大量与主题不相关或无意义的单词，例如Reuters数据中的Reuter，write等和一些未过滤的作者姓名单词.为了只保留那些对划分文本更有利的特征单词，本文采用文档-反文档频率(term frequency-inverse document frequency, TF-IDF)方法对文本中的单词进行进一步过滤.TF-IDF用以评估1个单词对于1个文件或1个语料库的其中1份文件的重要程度.词的重要度随着它在1个文本中出现的次数成正比增加，但同时会随着它在文本集中出现的频率成反比下降：
tfidf i , j = tf i , j × idf i ，
(12)
tf i , j = 
，
(13)
其中， tf i , j 表示单词 i 在文本 d j 中的词频，分子是该词在文本 d j 中出现的次数，分母则是在文本 d j 中所有词的出现次数之和.
idf i =log 
，
(14)
其中， idf i 表示该词的反文档频率，分子表示语料库中的文本总数，分母表示含词语 t i 的文本数目.实验中我们根据每个词的重要度分数进行排序，只保留前3/4的词.通过此方法可以有效地过滤文本中大量无意义的词.
我们在不同的算法上对5组数据进行聚类，其中对于 K -means，SP K -means，LDA，GNMF，FIC-S这5种不确定型算法分别运行10次取平均值作为最后聚类的精度结果，每个算法的聚类结果如表7所示.
从表7中可以看出，FIC算法较之其他方法在精度上有明显的优势.究其原因主要有3个方面：
1) 在数据处理上，我们并不只是分词和去掉停用词，为了保留那些更有代表性的词汇，采用了通过TF-IDF值来筛选特征词.
2) 运用频繁词集来构建文本表示模型，文本集中挖掘出的频繁词集都在千量集以内，较之传统的VSM模型可将维数从上万维度降到只有几千维，另外，从文本集中挖掘的频繁词集本身带有一定的语义，在衡量文本间相似度时，相较单个特征词的衡量方法，能够考虑到频繁词中的语义关系，使得相同主题下的文本相似度更高且降低了不同主题下文本间的相似度.相比于直接用2文本间共有的频繁词集的数量来衡量文本间的相似度，式(7)可以有效地避免类不平衡问题带来的影响.当测试数据集中不同类间文本数量差距较大时，挖掘出的频繁词集集合中关于大类主题的频繁词集会比较多，而关于小类主题的频繁词集较少，因此在用频繁词集表示每个文本时会出现小类文本中所具有的频繁词集较少的情况，若直接按照共有频繁词集的数量来衡量相似度则会出现小类间文本连接不紧密的情况，在社区划分中会出现小类被大类吞并的问题.为了更加准确地衡量文本间相似性，式(7)考虑到文本内频繁词集的数量，将相似度看做文本间共有的频繁词集个数在2文本中所有频繁词集里所占的权重比例.通过这种方法使得小类间的文本连接更加紧密，减小被大类吞并的风险.
3) 引用网络和图论的思想，将文本当作网络中的节点，建立文本建的关联关系，使文本与文本之间不再是独立的两两关系，并且使用文本网络的分析方法可以更加直观地分析文本集中的类结构.同时可以引入更多基于网络社区划分和图切割的聚类算法，使得FIC算法更加灵活.
Table 7 Result of Algorithms
表7 算法精度
本文算法中主要涉及到3个参数，包括在筛选特征词时的阈值、挖掘频繁词集中的最小支持度和计算文本间相似性的相似度阈值.本文通过采用手动调整、多次实验的方式，获得了聚类的最佳效果.其中对于最小支持度的选择要尽量保证每个文本能够至少有5个频繁词集来表示，相似度阈值则通过文本网络中的边数来衡量，避免文本网络过于密集或稀疏，在最佳效果下各个阈值的取值如表8所示.下面我们将以对聚类精度影响最高的相似性阈值为例，介绍本次实验过程.在英文数据集中，我们选取相似度阈值的步长为0.005，由于中文数据中的停用词较多以及每个文档中词数量较少，因此采用与英文数据不同的阈值选择方式，采用0.01的步长进行实验.其中FIC-K算法在处理无权网络时精度较之带权网络高，因此我们将阈值筛选后的文本网络构成一个无权网络作为输入数据，即将权值大于 θ 的权值置1，小于 θ 的权值置0.对于FIC-S算法使用带权网络,权重为文本间的相似度.图2和图3为在固定最佳最小支持度阈值和特征筛选阈值后FIC-K算法在不同相似度阈值下的精度情况.
Table 8 Thresholds in the Data
表8 数据中的阈值
Fig. 2 Accuracy of FIC-K for Chinese data on C6
图2 FIC-K算法在C6数据集的中文数据下的精度
Fig. 3 Accuracy of FIC-K for English data
图3 FIC-K算法在英文数据集上的精度
对于本次实验选取的5组数据，我们采用相同的主题描述方案.对每个类簇内的文本，统计所有文本内的频繁词集的出现频率，并选择按频率排名前10的频繁词集来描述每个主题.这里主要展示由FIC-K算法所聚成类簇的主题描述情况，同时与LDA算法得到的主题描述词进行对比，结果如表9所示.从表9中可看出，FIC算法得到的主题描述词大多围绕主题，用频繁词集合的形式来描述，在一定程度上比起LDA的单个词描述可以将类簇表述的更加详细具体.
Table 9 Topic Description
表9 主题描述
Continued ( Table 9 )
Continued ( Table 9 )
本文提出一种新的文本聚类方法FIC，该方法运用基于频繁词集的文本表示模型，解决了传统的VSM模型的高维和数据稀疏的问题，采用基于网络的社区划分聚类方法和谱聚类算法，由于考虑了多个文本间的关系，聚类性能相比于之前的方法有了一定程度的提升.至今文档聚类一直是一个值得深入研究的课题，其中面临着两大问题：1)数据集规模海量增长；2)文本越来越趋向于短文本的形式.如何在这类数据集上进行有效的文本聚类是我们未来工作的挑战.
参考文献
[1] Lu Yuchang, Lu Mingyu, Li Fan, et al. Analysis and construction of word weighting function in VSM[J]. Journal of Computer Research and Development, 2002, 39(10): 1205-1210 (in Chinese)
(陆玉昌, 鲁明羽, 李凡, 等. 向量空间法中单词权重函数的分析与构造[J]. 计算机研究与发展, 2002, 39(10): 1205-1210)
[2] Peng Min, Huang Jiajia, Zhu Jiahui, et al. Mass of short texts clustering and topic extraction based on frequent itemsets[J]. Journal of Computer Research and Development, 2015, 52(9): 1941-1953 (in Chinese)
(彭敏, 黄佳佳, 朱佳晖, 等. 基于频繁词集的海量短文本聚类与主题抽取[J]. 计算机研究与发展, 2015, 52(9): 1941-1953)
[3] Beil F, Ester M, Xu Xiaowei. Frequent term-based text clustering[C] //Proc of the 8th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 436-442
[4] Fung M, Wang Ke, Ester M. Hierarchical document clustering using frequent itemsets[C] //Proc of the 3rd SIAM Int Conf on Data Mining. San Francisco, CA: SIAM, 2003: 59-70
[5] Zhang Wen, Yoshida T, Tang Xijin, et al. Text clustering using frequent itemsets[J]. Konwledge-Based Systems, 2010, 23(5): 379-388
[6] Hernández-Reyes E, García-Hernández R A, Carrasco-Ochoa J A, et al. Document clustering based on maximal frequent sequences[G] //Advances in Natural Language Processing. Berlin: Springer, 2006: 257-267
[7] Masada T, Kiyasu S, Miyahara S. Comparing LDA with pLSI as a dimensionality reduction method in document clustering[G] //Large-Scale Knowledge Resource. Berlin: Springer, 2008: 13-16
[8] Hornik K, Feinerer I, Kober M, et al. Spherical k-means clustering[J]. Journal of Statistical Software, 2012, 50(10): 1-22
[9] Cai Deng, He Xiaofei, Han Jiawei, et al. Graph regularized bonnegative matrix factorization for data representation[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2011, 33(8): 1548-1560
[10] Hoyer P O. Non-negative matrix factorization with sparseness constraints[J]. Journal of Machine Learning Research, 2004, 5(1): 1457-1469
[11] Xiu Yu, Wang Shitong, Zhu Lin,et al. Maximum-entropy sphere K -means document clusterinf analysis[J]. Frontiers of Computer Science and Technology, 2007, 1(3): 331-339 (in Chinese)
(修宇, 王士同, 朱林, 等. 极大熵球面 K 均值文本聚类分析[J]. 计算机科学与探索, 2007, 1(3): 331-339)
[12] Han Jiawei, Pei Jian,Yin Yiwen. Mining frequent pattern without candidate generation: A frequent-pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8(53): 53-87
[13] Li Yafang, Jia Caiyan, Yu Jian. A parameter-free community detection method based on centrality and dispersion of nodes in complex networks[J]. Physica A Statistical Mechanics & Its Applications, 2015, 438(43): 321-334
[14] Luxburg U V. A tutorial on spectral clustering[J]. Statistics & Computing, 2007, 17(17): 395-416
[15] Steinbach M, Karypis G, Kumar V. A comparison of document clustering techniques[C] //Proc of the 2nd KDD Workshop on Text Mining. New York: ACM, 2000: 525-526
[16] Huang Yuyan. Research and application of text clustering method based on maximal frequent itemsets K -means[D]. Harbin: Harbin Institute of Technology, 2011 (in Chinese)
(黄玉燕. 基于最大频繁词集 K -means的文本聚类算法研究及应用[D]. 哈尔滨: 哈尔滨工业大学, 2011)
Zhang Xuesong and Jia Caiyan
( Beijing Key Lab of Traffic Data Analysis and Mining ( Beijing Jiaotong University ), Beijing 100044)( School of Computer and Information Technology , Beijing Jiaotong University , Beijing 100044)
Abstract Traditional document clustering methods use vector space model (VSM) of words to represent documents. This VSM representation only measures the importance of a single words, while ignores the semantic relationship between words, and has high dimensionality. In this study, we propose a new document clustering method: FIC (frequent itemsets based document clustering method). In the method, we use frequent itemsets (where a frequent itemset is a set of frequently co-occurred words) mined by FP-Growth algorithm in documents to represent each document. We then construct the document-document relationship network based on the similarity between pairs of documents at this new representation. At last, we divide the network into communities using a given community detection method to complete document clustering. Thereby, FIC can not only overcome the high dimensionality of VSM, but also fully make use of topological relationship among documents. The experimental results on two English corpora (Reters-21578 and 20Newsgroup) and one Chinese corpus (Sougou-News) demonstrate that the proposed method FIC is superior to the other existing frequent itemsets based methods and other classical state-of-the-art document clustering methods, and the top K words for characterizing each topic of documents identified by FIC are more meaningful than the classical topic model LDA (latent Dirichlet allocation).
Key words document clustering; frequent itemsets; complex network; community division; text representation model
摘 要 传统的文本聚类方法大部分采用基于词的文本表示模型，这种模型只考虑单个词的重要度而忽略了词与词之间的语义关系.同时，传统文本表示模型存在高维的问题.为解决以上问题，提出一种基于频繁词集的文本聚类方法(frequent itemsets based document clustering method， FIC).该方法从文档集中运用FP-Growth算法挖掘出频繁词集，运用频繁词集来表示每个文本从而大大降低了文本维度，根据文本间相似度建立文本网络，运用社区划分的算法对网络进行划分，从而达到文本聚类的目的.FIC算法不仅能降低文本表示的维度，还可以构建文本集中文本间的关联关系，使文本与文本间不再是独立的两两关系.实验中运用2个英文语料库Reuters-21578,20NewsGroup和1个中文语料库——搜狗新闻数据集来测试算法精度.实验表明:较传统的利用文本空间向量模型的聚类方法，该方法能够有效地降低文本表示的维度，并且，相比于常见的基于频繁词集的聚类方法能获得更好的聚类效果.
关键词 文本聚类；频繁词集；复杂网络；社区划分；文本表示模型
中图法分类号 TP301
收稿日期： 2016-08-30；
修回日期： 2017-07-04
基金项目： 国家自然科学基金面上项目(61473030)；数字出版国家重点实验室专项课题
This work was supported by the General Program of the National Natural Science Foundation of China (61473030) and the Opening Project of State Key Laboratory of Digital Publishing Technology.
Zhang Xuesong , born in 1993. Master candidate in Beijing Jiaotong University. His main research interests include text clustering, community detection in networks.
Jia Caiyan , born in 1976. PhD and professor in Beijing Jiaotong University. Her main research interests include social computing, text clustering, community detection in networks, etc.