文本聚类

文本聚类

正所谓人以类聚，物以群分。人类获取并积累信息时常常需要整理数据，将相似的数据归档到一起。许多数据分析需求都归结为自动发现大量样本之间的相似性，并将其划分为不同的小组，这种根据相似性归档的任务称为聚类。

基本概念

聚类（cluster analysis）指的是将给定对象的集合划分为不同子集的过程，目标是使得每个子集内部的元素尽量相似，不同子集间的元素尽量不相似。这些子集又被称为簇（cluster），一般没有交集。聚类的概念如图所示。

聚类

文本聚类（document clustering）指的是对文档进行的聚类，被广泛用于文本挖掘和信息检索领域。最初文本聚类仅用于文本归档，后来人们又挖掘出了许多新用途。比如改善搜索结果，生成同义词等等。

在文本的预处理中，聚类同样可以发挥作用。比如在标注语料之前，通常需要从生语料中选取一定数量有代表性的文档作为样本。假设需要标注N篇，则可以将这些生语料聚类为N个簇，每个簇随机选取一篇即可。利用每个簇内元素都是相似的这个性质，聚类甚至可以用于文本排重。

目前市面上常见的聚类算法是k-means，但HanLP不光实现了k-means，还实现了速度更快效果更好的repeated bisection算法。我们将在文末比较两种算法的速度与准确率。

文本聚类模块

在HanLP中，聚类算法实现为ClusterAnalyzer，用户可以将其想象为一个文档id到文档向量的映射容器。创建ClusterAnalyzer对象后，向其中加入若干文档之后即可调用k-means接口得到指定数量的簇。文档id在实现上是泛型的，Java用户可以将文档String标题，或数据库Integer主键作为id的类型。

此处以某音乐网站中的用户聚类为案例讲解聚类模块的用法。假设该音乐网站将6位用户点播的歌曲的流派记录下来，并且分别拼接为6段文本。给定用户名称与这6 段播放历史，要求将这6名用户划分为3个簇。

首先，我们需要创建ClusterAnalyzer对象，并向其加入文档。Java示例如下：

        ClusterAnalyzer<String> analyzer = new ClusterAnalyzer<String>();
        analyzer.addDocument("赵一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 摇滚, 摇滚, 摇滚, 摇滚");
        analyzer.addDocument("钱二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲");
        analyzer.addDocument("张三", "古典, 古典, 古典, 古典, 民谣, 民谣, 民谣, 民谣");
        analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金属, 金属, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲");
        analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 摇滚, 摇滚, 摇滚, 嘻哈, 嘻哈, 嘻哈");
        analyzer.addDocument("马六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 摇滚");

文档加入后，ClusterAnalyzer内部会自动对其分词、去除停用词、转换为词袋向量，如表1所示。

	流行	蓝调	摇滚	爵士	舞曲	古典	民谣	金属	嘻哈
赵一	10	6	4	0	0	0	0	0	0
钱二	0	0	0	8	9	0	0	0	0
张三	0	0	0	0	0	4	4	0	0
李四	0	0	0	9	6	0	0	2	0
王五	4	0	3	0	0	0	0	0	3
马六	0	0	1	0	0	8	0	0	0

文本聚类中的词袋向量

有了这些向量后，只需调用ClusterAnalyzer的kmeans或repeatedBisection方法就可以得到指定数量的簇，以3为例：

System.out.println(analyzer.kmeans(3));
System.out.println(analyzer.repeatedBisection(3));

该方法返回指定数量的簇构成的集合，每个簇是一个Set，内部元素为文档的id。此处由于id是姓名，所以可以打印出来直观地感受效果：

[[李四, 钱二], [王五, 赵一], [张三, 马六]]

根据该结果，李四和钱二同属一个簇。对照表1，这二人都喜欢爵士和舞曲。类似地，王五和赵一都喜欢流行和摇滚音乐；张三和马六都喜欢古典音乐。通过k-means聚类算法，我们成功地将用户按兴趣分组，得到了“人以群分”的效果。

聚类结果中簇的顺序是随机的，每个簇中的元素也是无序的。由于k-means是个随机算法，有小概率得到不同的结果。

该聚类模块可以接受任意文本作为文档，而不需要用特殊分隔符隔开单词。另外，该模块还接受单词列表作为输入，用户可以将英文、日文等预先切分为单词列表后输入本模块。统计方法适用于所有语种，不必拘泥于中文。

自动判断聚类个数k

通过上面的介绍，用户可能觉得聚类个数k这个超参数很难准确指定。在repeated bisection算法中，有一种变通的方法，那就是通过给准则函数的增幅设定阈值beta来自动判断k。此时算法的停机条件为，当一个簇的二分增幅小于beta时不再对该簇进行划分，即认为这个簇已经达到最终状态，不可再分；当所有簇都不可再分时，算法终止，此时产生的聚类数量就不再需要人工指定了。

在HanLP中，repeated bisection算法提供了3种接口，分别需要指定k、beta或两者同时指定。当同时指定k和beta时，满足两者的停止条件中任意一个算法都会停止。当只指定一个时，另一个停止条件不起作用。这三个接口列举如下：

    public List<Set<K>> repeatedBisection(int nclusters)
    public List<Set<K>> repeatedBisection(double limit_eval)
    public List<Set<K>> repeatedBisection(int nclusters, double limit_eval)

对于上一个例子，以beta=1.0作为参数试试自动判断聚类个数k，发现恰好可以得到理想的结果，Java示例：

        System.out.println(analyzer.repeatedBisection(1.0)); // 自动判断聚类数量k

标准化评测

前面介绍的音乐案例只有6个样本，只能说是玩具数据（toy data）。用玩具数据来调试算法很方便，但不足以说明算法的实用性。本节我们将介绍聚类任务的标准化评测手段，并且给出两种算法的分值。

聚类任务常用的一种评测手段是沿用分类任务的F1值，将一些人工分好类别的文档去掉标签交给聚类分析器，统计结果中有多少同类别的文档属于同一个簇。

语料库

本次评测选择搜狗实验室提供的文本分类语料的一个子集，笔者称其为“搜狗文本分类语料库迷你版”。该迷你版语料库分为5个类目，每个类目下1000篇文章，共计5000篇文章。配套代码将自动下载该语料到data/test/搜狗文本分类语料库迷你版，其目录结构如下所示：

搜狗文本分类语料库迷你版
├── 体育
│   └── 1.txt
│   └── 2.txt
│   └── 3.txt
│   └── ...
├── 健康
│   └── ...
├── 军事
│   └── ...
├── 教育
│   └── ...
└── 汽车
    └── ...

评测试验

评测程序遍历子目录读取文档，以子目录+文件名作为id将文档传入聚类分析器进行聚类，并且计算F1值返回。该计算过程封装为接口com.hankcs.hanlp.mining.cluster.ClusterAnalyzer#evaluate，欢迎用户自行查阅。此处仅演示评测接口的调用，Java用户可参考com.hankcs.demo.DemoTextClusteringFMeasure：

        for (String algorithm : new String[]{"kmeans", "repeated bisection"})
        {
            System.out.printf("%s F1=%.2f\n", algorithm, ClusterAnalyzer.evaluate(CORPUS_FOLDER, algorithm) * 100);
        }

两者的输出汇总如表2所示。

	F1	耗时
kmeans	83.74	67秒
repeated bisection	85.58	24秒

对比两种算法，repeated bisection不仅准确率比kmeans更高，而且速度是kmeans的三倍。然而repeated bisection成绩波动较大，需要多运行几次才可能得出这样的结果。也许85%左右的准确率并不好看，但考虑到聚类是一种无监督学习，其性价比依然非常可观。

参考文献

1. Steinbach M, Karypis G, Kumar V. A comparison of document clustering techniques[C]//KDD workshop on text mining. 2000, 400(1): 525-526.
2. 实现上参考了 https://github.com/fujimizu/bayon 的C++代码。