精华内容
下载资源
问答
  • 数据集是用于文本聚类的中文文本数据,数据集不大属于小型数据集,主要是为了验证本人在博客上写的代码,拿到立马就可使用实现可参考本人的博客
  • 二维多维不同簇数的点集,螺旋分布、月牙分布、环形分布等数据集,共30余种
  • 文本聚类正所谓人以类聚,物以群分。人类获取并积累信息时常常需要整理数据,将相似的数据归档到一起。许多数据分析需求都归结为自动发现大量样本之间的相似性,并将其划分为不同的小组,这种根据相似性归档的任务...

    文本聚类

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

    基本概念

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

    d4946fa958242d62bbbf60791279797f.png

    聚类

    文本聚类(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 analyzer = new ClusterAnalyzer();

    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> repeatedBisection(int nclusters)

    public List> repeatedBisection(double limit_eval)

    public List> 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%左右的准确率并不好看,但考虑到聚类是一种无监督学习,其性价比依然非常可观。

    参考文献

    Steinbach M, Karypis G, Kumar V. A comparison of document clustering techniques[C]//KDD workshop on text mining. 2000, 400(1): 525-526.

    展开全文
  • 包含四个数据集,分别从english20newsgroup、reuters 中提取,分别为500条记录,各含五类,每类文档数目不同!从两个母数据库中提取,存储为sqlserver2008格式,可以直接附加,表结构如下!全部进行了标注,可以用来分类或者...
  • 文本聚类

    2021-08-29 15:53:38
    第10章 文本聚类 10.1 概述 10.2 文档的特征提取 10.3 k均值算法 10.4 重复二分聚类算法 10.5 标准化评测 10.6 总结 第10章 文本聚类 上一章我们在字符、词语和句子的层级上应用了一些无监督学习方法。这些...

    目录

    第10章 文本聚类

    10.1 概述

    10.2 文档的特征提取

    10.3 k均值算法

    10.4 重复二分聚类算法

    10.5 标准化评测

    10.6 总结

    第10章 文本聚类

    上一章我们在字符、词语和句子的层级上应用了一些无监督学习方法。这些方法可以自动发现字符与字符、词语与词语、乃至句子与句子之间的联系,而不需要标注语料。同样,在文档层级上,无监督方法也可以在缺乏标注数据的条件下自动找出文档与文档之间的关联。

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

    10.1 概述

    文本聚类是聚类在文本上的应用,下面先介绍聚类的概念。

    10.1.1 聚类

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

    根据元素从属于集合的确定程度,聚类分为硬聚类和软聚类。

    • 硬聚类(hard clustering):每个元素被确定地归入一个簇。
    • 软聚类(soft clustering):每个元素与每个簇都存在一定的从属程度(隶属度),只不过该程度有大有小。

    硬软聚类的区别类似于规则与统计的区别:硬聚类中从属关系是离散的,非常强硬,而软聚类中的从属关系则用一个连续值来衡量,比较灵活。比如图10-2(左图)中的一维数据点大致可划分为2个簇,硬软聚类的结果分别如图10-2的中图和右图所示。

    其中,纵坐标表示每个元素与第一个簇的隶属程度。可见硬聚类在簇的边界处采用“一刀切”的方式划分,而软聚类则没有。另一个例子如图10-3所示,如果将元素所属聚类视作离散型随机变量的话,软聚类相当于为每个元素都预测了一个概率分布。图10-3硬聚类和软聚类示例

    在实际工程特别是NLP中,由于硬聚类更加简洁,所以使用得更频繁。

    一般将聚类时簇的数量视作由使用者指定的超参数,虽然存在许多自动判断的算法(这些方法包括X-means、elbow method等在内不下三十余种,通常需要比较多份不同簇数的聚类结果,计算某个统计量,根据该统计量决定最优簇数。),但它们往往需要人工指定其他超参数,或者比较多份聚类结果。另外,还可以通过层次聚类来得到树形结构的聚类,通过实际需要选取树的某一层作为聚类结果。

    根据聚类结果的结构,聚类算法也可以分为划分式(partitional)和层次化(hierarchieal)两种。划分式聚类的结果是一系列不相交的子集,而层次化聚类的结果是一棵树,叶子节点是元素,父节点是簇。本章主要介绍划分聚类。

    总之,聚类算法是一个大家族,我们要根据实际需求选择具体方案。

    10.1.2 聚类的应用

    聚类通常用于数据的预处理,或归档相似的数据。其流程除了不需要标注数据外,与其它已知的大多数任务相同,都是提取特征后交给某个机器学习算法。

    不光文本可以聚类,任何事物,只要能够提取特征,都可以聚类。比如电商网站根据价格颜色等特征对商品聚类,应用商店根据App的用户年龄层和下载量等特征进行聚类,电影网站根据影片的题材和年份等特征进行聚类。只要将现实生活中的对象通过特征提取转换为数学世界中的一个向量,就可以进行包括聚类在内的机器学习。

    通过聚类,网站可以为用户提供大众化的推荐。比如科幻题材的影片可能被自动归入同一个簇中,当用户点播了其中一部之后,网站就会为其推荐与该影片最相似的另外几部。这种推荐并非针对每个用户的个性化推荐,因为聚类发生时并没有考虑用户个人的喜好因素,而是仅仅提取了电影本身的特征。大众化推荐对新用户而言特别友好,因为刚注册的用户没有多少播放历史,难以预测喜好,这时通过聚类推荐相似影片常常是一个平稳的“冷启动”策略。

    辅以少量的人工抽查,聚类还可以自动筛选出包含某些共同特质的样本。比如刷好评的App通常好评数和下载量的比值较高,而用户日活跃数和留存率较低。这些指标的具体数值很难人工确定,但应该存在一个固定的区间。通过聚类将新上架的App归入几个簇之后,每个簇随机选几个样本人工抽查。那些被人工鉴定为刷好评的App所在的簇很可能还含有更多类似的App,从而缩小了抽查范围,降低了人力成本。

    总之,聚类是一项非常实用的技术。特别是数据量很大、标注成本过高时,聚类常常是唯一可行的方案。

    10.1.3 文本聚类

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

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

    文本聚类的基本流程分为特征提取和向量聚类两步,如图10-2所示,聚类的对象是抽象的向量(一维数据点)。如果能将文档表示为向量,就可以对其应用聚类算法。这种表示过程称为特征提取,在10.2节中详细介绍。而一旦将文挡表示为向量,剩下的算法就与文档无关了。这种抽象思维无论是从软件工程的角度,还是从数学应用的角度都十分简洁有效。

    10.2 文档的特征提取

    文档是一系列单词(包括标点符号)的有序不定长列表,这些单词的种数无穷大,且可能反复出现。单词本身已然千变万化,它们的不定长组合更加无穷无尽。从细节上尽善尽美地表示一篇文档并不现实,我们必须采用一些有损的模型。

    10.2.1 词袋模型

    词袋(bag-of-words)是信息检索与自然语言处理中最常用的文档表示模型,它将文档想象为一个装有词语的袋子,通过袋子中每种词语的计数等统计量将文档表示为向量。一个形象的例子如图10-4所示。

    文档含有如下两句话:

    人 吃 鱼。
    美味 好 吃!
    

    假设这两句话经过分词与停用词过滤后的结果为:

    人 吃 鱼
    美味 好 吃
    

    将这6个共计5种词语装人袋子后摇一摇,得到的词袋模型如图10-4所示。不在这5种词语之内的词语为OOV,它们散落在词袋之外,为模型所忽略。

    假设我们选用词频作为统计指标的话,则该文档的词频统计为:

    人=1
    吃=2
    鱼=1
    美味=1
    好=1
    

    文档经过该词袋模型得到的向量表示为[1,2,1,1,1],这 5 个维度分别表示这 5 种词语的词频。

    一般选取训练集文档的所有词语构成一个词表,词表之外的词语称为 OOV,不予考虑。一旦词表固定下来,假设大小为 NN。则任何一个文档都可以通过这种方法转换为一个NN维向量,比如对于“人吃大鱼”这个文档,它的词频统计为:

    人=1
    吃=1
    鱼=1
    美味=0
    好=0
    

    那么它的词袋向量就是[1,1,1,0,0],其中后两个维度上的词语都没有出现,所以都是0。而“大”这个词语属于OOV,散落在词袋之外,所以不影响词袋向量。

    由于词袋模型不考虑词序,它的计算成本非常低。也正因为这个原因,词袋模型损失了词序中蕴含的语义。比如,对于词袋模型来讲,“人吃鱼”和“鱼吃人”的词袋向量是一模一样的。这听上去很荒谬,但在实际工程中,词袋模型依然是一个很难打败的基线模型。

    此外,目前工业界已经发展出很好的词向量表示方法了,如 word2vec/bert 模型等。

    10.2.2 词袋中的统计指标

    词袋模型并非只是选取词频作为统计指标,而是存在许多选项。常见的统计指标还包括如下几个:

    • 布尔词频: 词频非零的话截取为1,否则为0,适合长度较短的数据集
    • TF-IDF: 参考9.2.2节,将每个词语的倒排频次也纳入考虑,适合主题较少的数据集
    • 词向量: 如果词语本身也是某种向量的话,则可以将所有词语的词向量求和作为文档向量。适合处理 OOV 问题严重的数据集。
    • 词频向量: 适合主题较多的数据集

    它们的效果与具体数据集相关,需要通过实验验证。一般而言,词频向量适合主题较多的数据集;布尔词频适合长度较短的数据集;TF-IDF适合主题较少的数据集;而词向量则适合处理OOV问题严重的数据集。对新手而言,词频指标通常是一个入门选择。

    除了词袋模型之外,神经网络模型也能无监督地生成文档向量,比如自动编码器和受限玻尔兹曼机等。通过神经网络得到的文档向量一般优于词袋向量,但代价是计算开销较大。

    本章以词频作为统计指标,用词袋模型来提取文档的特征向量。至此,特征提取介绍完毕。为了清晰地叙述接下来的聚类算法,我们用数学记号正式地描述特征向量。

    定义由 nn 个文档组成的集合为 SS,定义其中第 ii 个文档 didi 的特征向量为 didi,其公式如下:

    di=(TF(t1,di),TF(t2,di),⋯,TF(tj,di),⋯,TF(tm,di))di=(TF(t1,di),TF(t2,di),⋯,TF(tj,di),⋯,TF(tm,di))

    其中 tjtj表示词表中第 jj 种单词,mm 为词表大小, TF(tj,di)TF(tj,di) 表示单词 tjtj 在文档 didi 中的出现次数。为了处理长度不同的文档,通常将文档向量处理为单位向量,即缩放向量使得 ||d||=1||d||=1。

    至此,从文本到向量的转换已经执行完毕。转换后得到了一系列向量,或者说一系列数据点。接下来,我们将使用一些聚类算法将这些数据点聚集成不同的簇。

    10.3 k均值算法

    一种简单实用的聚类算法是k均值算法(k-means),由Stuart Lloyd于1957年提出。该算法虽然无法保证一定能够得到最优聚类结果,但实践效果非常好。基于kk均值算法衍生出许多改进算法,本章先介绍朴素的kk均值算法,然后推导它的一个变种。

    10.3.1 基本原理

    定义kk均值算法所解决的问题:给定nn个向量 d1,⋯,dn∈ℝld1,⋯,dn∈Rl以及一个整数kk,要求找出kk个簇S1,⋯,SkS1,⋯,Sk以及各自的质心c1,⋯,ck∈ℝlc1,⋯,ck∈Rl,使得下式最小:

    (10.1)(10.1)

    其中||di−cr||||di−cr|| 是向量与质心的欧拉距离,EuclideanIEuclidean称作聚类的准则函数(criterion function)。也就是说,kk均值以最小化每个向量到质心的欧拉距离的平方和为准则进行聚类,所以该准则函数有时也称作平方误差和(sum-of-squared-errors)函数。而质心的计算就是簇内数据点的几何平均:

    (10.2)(10.2)

    其中,sisi 是簇 SiSi 内所有向量之和,称作合成向量(composite vector)。

    生成 kk 个簇的 kk均值算法是一种迭代式算法,每次迭代都在上一步的基础上优化聚类结果,步骤如下:

    • (1)选取kk个点作为kk个簇的初始质心;
    • (2)将所有点分别分配给最近的质心所在的簇;
    • (3)重新计算每个簇的质心;
    • (4)重复步骤(2)和步骤(3)直到质心不再发生变化。

    kk均值算法虽然无法保证收敛到全局最优,但能够有效地收敛到一个局部最优点。对于该算法,重点需要关注两个问题,即初始质心的选取和两点距离的度量。

    10.3.2 初始质心的选取

    由于kk均值不保证收敛到全局最优,所以初始质心的选取对kk均值的运行结果影响非常大,如果选取不当,则可能收敛到一个较差的局部最优点。

    朴素实现经常用随机选取的方式确定初始质心,相当于逃避了这个问题。使用这种实现时,用户必须多运行几次,根据准则函数选取最佳结果。当数据量很大时,往往不够经济。

    一种更高效的方法是,将质心的选取也视作准则函数进行迭代式优化的过程。其具体做法是,先随机选择第一个数据点作为质心,视作只有一个簇计算准则函数。同时维护每个点到最近质心的距离的平方,作为一个映射数组MM。接着,随机取准则函数值的一部分记作ΔΔ。遍历剩下的所有数据点,若该点到最近质心的距离的平方小于ΔΔ,则选取该点添加到质心列表,同时更新准则函数与MM。如此循环多次,直至凑足kk个初始质心。这种方法可行的原理在于,每新增一个质心,都保证了准则函数的值下降一个随机比率。而朴素实现相当于每次新增的质心都是完全随机的,准则函数的增减无法控制。

    考虑到kk均值是一种迭代式的算法, 需要反复计算质心与两点距离,这部分计算通常是效瓶颈。为了改进朴素 kk均值算法的运行效率,HanLP利用种更快的准则函数实现了kk均值的变种。

    10.3.3 更快的准则函数

    将一个点移入最近的质心所属的簇,等价于这次移动让准则函数减小最快。在kk均值的迭代过程中,数据点被分配给最近的质心,导致簇中的元素频繁发生变动。当移动发生时,我们希望快速计算准则函数的变化。本节介绍另一种准则函数以及它的优势。除了式(10.1)所示的欧拉准则函数,还存在一种基于余弦距离的准则函数:

    该函数使用余弦函数衡量点与质心的相似度,目标是最大化同簇内点与质心的相似度。将向量夹角计算公式代入,该准则函数变换为:

    代入后变换为:

    (10.4)(10.4)

    也就是说,余弦准则函数等于 kk 个簇各自合成向量的长度之和。比较之前的准则函数会发现在数据点从原簇移动到新簇时,EuclideanIEuclidean需要重新计算质心,以及两个簇内所有点到新质心的距离。而对于cosIcos,由于发生改变的只有原簇和新簇两个合成向量,只需求两者的长度即可,计算量减小不少。

    基于新准则函数cosIcos,kk均值变种算法的流程如下:

    • (1)选取kk个点作为kk个簇的初始质心;
    • (2)将所有点分别分配绐最近的质心所在的簇;
    • (3)对每个点,计算将其移入另一个簇时cosIcos的增大量,找出最大增大量,并完成移动;
    • (4)重复步骤(3)直到达到最大迭代次数,或簇的划分不再变化。

    该算法的实现位于com.hankcs.hanlp.mining.cluster.ClusterAnalyzer#refine_clusters,接口如下:

    该接口不仅在kk均值中反复调用,在后面的新算法中也会反复用到。

    10.3.4 实现

    在 HanLP 中,聚类算法实现为 ClusterAnalyzer,用户可以将其想象为一个文档 id 到文档向量的映射容器。创建对象后,往容器中加入若干文档之后即可调用kk均值接口得到指定数量的簇。

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

    from pyhanlp import *
    
    ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
    
    if __name__ == '__main__':
        analyzer = ClusterAnalyzer()
        analyzer.addDocument("赵一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 摇滚, 摇滚, 摇滚, 摇滚")
        analyzer.addDocument("钱二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
        analyzer.addDocument("张三", "古典, 古典, 古典, 古典, 民谣, 民谣, 民谣, 民谣")
        analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金属, 金属, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
        analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 摇滚, 摇滚, 摇滚, 嘻哈, 嘻哈, 嘻哈")
        analyzer.addDocument("马六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 摇滚")

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

    表10-1文本聚类中的词袋向量

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

    print(analyzer.kmeans(3))

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

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

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

    聚类结果中簇的顺序是随机的,每个簇中的元素也是无序的。由于kk均值是个随机算法,有小概率得到不同的结果。

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

    无论朴素实现还是变种,kk均值算法的复杂度都是O(n)O(n),其中nn是向量的个数。虽然任何变种都无法突破该理论值,但当kk较大时,还存在另一种更快的改进kk均值算法。

    10.4 重复二分聚类算法

    10.4.1 基本原理

    重复二分聚类(repeated bisection clustering)是kk均值算法的效率加强版,其名称中的bisection是“二分”的意思,指的是反复对子集进行二分。该算法的步骤如下:

    • (1)挑选一个簇进行划分;
    • (2)利用kk均值算法将该簇划分为2个子集;
    • (3)重复步骤(1)和步骤(2),直到产生足够数量的簇。

    该算法的流程如图10-5所示,每次产生的簇由上到下形成了一棵二叉树结构。

    正是由于这个性质,重复二分聚类算得上一种基于划分的层次聚类算法。如果我们把算法运行的中间结果存储起来,就能输出一棵具有层级关系的树。树上每个节点都是一个簇,父子节点对应的簇满足包含关系。虽然每次划分都基于kk均值,由于每次二分都仅仅在一个子集上进行,输入数据少,算法自然更快。

    至于步骤(1)中如何挑选簇进行划分,有多种方案。可用的标准有:

    • 簇的体积最大;
    • 簇内元素到质心的相似度最小;
    • 二分后准则函数的增幅(gain)最大。

    HanLP采用了最后一种策略,每产生一个新簇,都试着将其二分并计算准则函数的增幅。然后对增幅最大的簇执行二分,重复多次直到满足算法停止条件。

    10.4.2 自动判断聚类个数kk

    在重复二分聚类算法中,有一种变通的方法,那就是通过给准则函数的增幅设定阈值 ββ 来自动判断 kk。此时算法的停止条件为,当一个簇的二分增幅小于 ββ 时不再对该簇进行划分,即认为这个簇已经达到最终状态,不可再分。当所有簇都不可再分时,算法终止,最终产生的聚类数量就不再需要人工指定了。

    在HanLP中,重复二分聚类算法提供了3种接口,分别需要指定kk、ββ或两者同时指定。当同时指定kk和ββ时,满足两者的停止条件中任意一个算法都会停止。当只指定一个时,另一个停止条件不起作用。这3个接口列举如下:

    对于上一个例子,以β=1.0作为参数试试自动判断聚类个数k,发现恰好可以得到理想的结果,示例如下:

    print(analyzer.repeatedBisection(1.)) #自动判断聚类数量k

    当然,β的取值也很难确定,也许这些所谓的自动判断算法只是用一种麻烦替换了另一种麻烦而已。

    10.4.3 实现

    from pyhanlp import *
    
    ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
    
    if __name__ == '__main__':
        analyzer = ClusterAnalyzer()
        analyzer.addDocument("赵一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 蓝调, 摇滚, 摇滚, 摇滚, 摇滚")
        analyzer.addDocument("钱二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
        analyzer.addDocument("张三", "古典, 古典, 古典, 古典, 民谣, 民谣, 民谣, 民谣")
        analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金属, 金属, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
        analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 摇滚, 摇滚, 摇滚, 嘻哈, 嘻哈, 嘻哈")
        analyzer.addDocument("马六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 摇滚")
    
        print(analyzer.repeatedBisection(3))    # 重复二分聚类
        print(analyzer.repeatedBisection(1.0))  # 自动判断聚类数量k

    10.5 标准化评测

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

    10.5.1 PP、RR和F1F1值

    聚类任务常用的一种评测手段是沿用分类任务的F1F1值,将一些人工分好类别的文挡去掉标签交给聚类分析器,统计结果中有多少同类别的文档属于同一个簇。形式化描述,给定簇jj以及类别ii,定义nijnij表示簇中有多少类别ii的文档,njnj为簇jj中的文档总数,nini为类别ii中的文档总数。对每种ii和jj的组合,都计算如下指标:

    为了可读性,我们并不需要那么多的F1F1值。对整个评测任务而言,它的综合F1F1值是所有类目上分值的加权平均,如下式所述:

    F1=∑ininmax{F1(i,j)}F1=∑ininmax{F1(i,j)}

    其中,nn为文档总数,即

    n=∑inin=∑ini

    10.5.2 语料库

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

    第10.5.3节和第11章将用到这个语料库,搜狗实验室发布的原版语料库为GBK编码,现已转换为UTF-8编码。

    10.5.3 评测试验

    评测程序遍历子目录读取文档,以子目录+文件名作为id将文档传入聚类分析器进行聚类,并且计算F1F1值返回。

    代码(tests/book/ch10/demo_clustering_f.py)如下:

    from pyhanlp import *
    
    import zipfile
    import os
    from pyhanlp.static import download, remove_file, HANLP_DATA_PATH
    
    def test_data_path():
        """
        获取测试数据路径,位于$root/data/test,根目录由配置文件指定。
        :return:
        """
        data_path = os.path.join(HANLP_DATA_PATH, 'test')
        if not os.path.isdir(data_path):
            os.mkdir(data_path)
        return data_path
    
    
    
    ## 验证是否存在 MSR语料库,如果没有自动下载
    def ensure_data(data_name, data_url):
        root_path = test_data_path()
        dest_path = os.path.join(root_path, data_name)
        if os.path.exists(dest_path):
            return dest_path
        
        if data_url.endswith('.zip'):
            dest_path += '.zip'
        download(data_url, dest_path)
        if data_url.endswith('.zip'):
            with zipfile.ZipFile(dest_path, "r") as archive:
                archive.extractall(root_path)
            remove_file(dest_path)
            dest_path = dest_path[:-len('.zip')]
        return dest_path
    
    
    sogou_corpus_path = ensure_data('搜狗文本分类语料库迷你版', 'http://file.hankcs.com/corpus/sogou-text-classification-corpus-mini.zip')
    
    
    ## ===============================================
    ## 以下开始聚类
    
    ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
    
    if __name__ == '__main__':
        for algorithm in "kmeans", "repeated bisection":
            print("%s F1=%.2f\n" % (algorithm, ClusterAnalyzer.evaluate(sogou_corpus_path, algorithm) * 100))

    运行结果如下:

    kmeans F1=83.74
    
    repeated bisection F1=85.58
    

    评测结果如下表:

    算法F1耗时
    k均值83.7467秒
    重复二分聚类85.5824秒

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

    10.6 总结

    本章我们在文档上应用了kk均值和重复二分聚类两种聚类算法,并且比较了它们的性能。围绕这两个算法,我们还学习了词袋模型和文档向量等重要概念。这些概念不仅用于文本聚类,还可以用于其他NLP任务。

    在评测试验中,HanLP实现的无监督聚类算法能够给出85%左右的准确率,展示了极高的性价比。然而无监督聚类算法无法学习人类的偏好对文档进行划分,也无法学习每个簇在人类那里究竟叫做什么,下一章我们将解决这两个问题。

    本章其它相关代码

    # -*- coding:utf-8 -*-
    # Author: hankcs
    # Date: 2020-07-31 20:55
    # 《自然语言处理入门》第 10 章 文本聚类 (这段代码来自书籍之外的附赠答疑)
    # 配套书籍:http://nlp.hankcs.com/book.php
    # 讨论答疑:https://bbs.hankcs.com/
    
    import os
    
    from pyhanlp.static import STATIC_ROOT, HANLP_JAR_PATH
    
    java_code_path = os.path.join(STATIC_ROOT, 'MyClusterAnalyzer.java')
    with open(java_code_path, 'w') as out:
        java_code = """
    import com.hankcs.hanlp.mining.cluster.ClusterAnalyzer;
    import com.hankcs.hanlp.mining.cluster.SparseVector;
    
    public class MyClusterAnalyzer<K> extends ClusterAnalyzer<K>
    {
        public SparseVector toVector(String document)
        {
            return toVector(preprocess(document));
        }
    }
    """
        out.write(java_code)
    os.system('javac -cp {} {} -d {}'.format(HANLP_JAR_PATH, java_code_path, STATIC_ROOT))
    # 编译结束才可以启动hanlp
    from pyhanlp import *
    
    ClusterAnalyzer = JClass('MyClusterAnalyzer')
    
    if __name__ == '__main__':
        analyzer = ClusterAnalyzer()
        vec = analyzer.toVector("古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 摇滚")
        print(vec)
        # print(analyzer.kmeans(3))
        # print(analyzer.repeatedBisection(3))
        # print(analyzer.repeatedBisection(1.0))  # 自动判断聚类数量k
    
    展开全文
  • [python] Kmeans文本聚类算法+PAC降维+Matplotlib显示聚类图像 http://blog.csdn.net/eastmount/article/details/50545937 包括输入文档txt,共1000行数据,每行都是分词完的文本。 本文主要讲述以下几点: 1.通过...
  • sklearn做文本聚类分析

    2021-03-28 09:14:31
    文本Kmeans聚类分析前言背景目的与思路数据预处理分词处理采用jieba分词停用词处理获取停用词表去除停用词生成tf-idf矩阵Kmeans聚类获取分类获取分类文档获取主题词结论 前言 背景 为了研究用户对数字音乐付费的...

    前言

    背景

    为了研究用户对数字音乐付费的影响因素,我们采用了配额抽样的调查方法,共发出并收回有效问卷765份,其中问卷最后一题为开放性提问“Q42_H1.您认为当前数字音乐付费模式存在哪些问题以及相应的建议?”。
    我们将问卷中该问题的回答文本进行处理,探究不能类型的建议对于用户是否付费带来的影响。

    目的与思路

    目的:对建议文本进行聚类分析,最终得到几个主题词团
    实验方法:将数据进行预处理之后,先进行结巴分词、去除停用词,然后把文档生成tfidf矩阵,再通过K-means聚类,最后得到几个类的主题词。

    数据预处理

    导入数据,提取最后一列文本数据,去除其空值以及重复项

    data = pd.read_excel('questionnaire_data.xlsx')
    data.columns.values.tolist()
    adv = data[ 'Q42_H1.您认为当前数字音乐付费模式存在哪些问题以及相应的建议?']
    #文本去重
    adv = adv.dropna() # 删除空值
    l1 = len(adv)
    adv1 = pd.DataFrame(adv.unique()) # 删除重复值
    l2 = len(adv1)
    adv1.to_csv('jianyi.csv',index = False,encoding='utf-8')
    print(f'删除了{l1 - l2}条建议')   #删了249条
    

    采用机械压缩去词的方法对文本数据进行处理,并将结果存入jianyi.csv

    # 机械压缩去词
    f = codecs.open('jianyi2.csv' ,'w','utf-8')
    def cutword(strs,reverse = False):
        for A_string in strs: 
            temp1= A_string[0].strip('\n')       #去掉每行最后的换行符'\n' 
            temp2 = temp1.lstrip('\ufeff') 
            temp3= temp2.strip('\r')
            char_list=list(temp3)   
            list1=['']
            list2=['']
            del1=[]
            flag=['']
            i=0
            while(i<len(char_list)):
                if (char_list[i]==list1[0]):
                    if (list2==['']):
                        list2[0]=char_list[i]
                    else:
                        if (list1==list2):
                            t=len(list1)
                            m=0
                            while(m<t):
                                del1.append( i-m-1)
                                m=m+1
                            list2=['']
                            list2[0]=char_list[i]
                        else:
                            list1=['']
                            list2=['']
                            flag=['']
                            list1[0]=char_list[i]
                            flag[0]=i       
                else:
                    if (list1==list2)and(list1!=[''])and(list2!=['']):
                        if len(list1)>=2:
                            t=len(list1)
                            m=0
                            while(m<t):
                                del1.append( i-m-1)
                                m=m+1  
                            list1=['']
                            list2=['']
                            list1[0]=char_list[i]
                            flag[0]=i
                    else:
                        if(list2==['']):
                            if(list1==['']):
                                list1[0]=char_list[i]
                                flag[0]=i
                            else:
                                list1.append(char_list[i])
                                flag.append(i)
                        else:
                            list2.append(char_list[i])
                i=i+1
                if(i==len(char_list)):
                    if(list1==list2):
                            t=len(list1)
                            m=0
                            while(m<t):
                                del1.append( i-m-1)
                                m=m+1 
                            m=0
                            while(m<t):
                                del1.append(flag[m])
                                m=m+1                 
            a=sorted(del1)
            t=len(a)-1
            while (t>=0):
                #print(char_list[a[t]])
                del char_list[a[t]]
                t=t-1
            str1 = "".join(char_list)  
            str2=str1.strip() #删除两边空格
            if len(str2)>4: # 短句过滤
                f.writelines(str2+'\r\n')
        f.close()
        return  
    data1 = pd.read_csv('jianyi.csv',encoding = 'utf-8')
    data2 = cutword(data1.values)
    data2 = pd.read_csv('jianyi2.csv',encoding = 'utf-8',delimiter="\t",header=None)
    

    分词处理

    采用jieba分词

    doc=open('jianyi2.csv',encoding='utf-8').read()
    f = open("wenben.txt", "w", encoding = 'utf-8')
    f.write(doc)
    f.close()
    #jieba分词
    with open('wenben.txt', "r", encoding='utf-8') as fr:
        lines = fr.readlines()
    jiebaword = []
    for line in lines:
        line = line.strip('\n')
        # 清除多余的空格
        line = "".join(line.split())
        # 默认精确模式
        seg_list = jieba.cut(line, cut_all=False)
        word = "/".join(seg_list)
        jiebaword.append(word)
    jiebaword
    

    得到jiebaword如下:
    在这里插入图片描述

    停用词处理

    获取停用词表

    在网上搜索下载停用词文本 stopwords.txt

    stopword = []
    
    with open('stopwords.txt', "r", encoding='utf-8') as fr:
        lines = fr.readlines()
        
    for line in lines:
        line = line.strip('\n')
        stopword.append(line)
    stopword
    

    去除停用词

    # 去除停用词
    fw = open('CleanWords.txt', 'a+',encoding='utf-8')
    for words in jiebaword:
        words = words.split('/')
        for word in words:
            if word not in stopword:
                fw.write(word + '\t')
        fw.write('\n')
    fw.close()
    

    生成tf-idf矩阵

    with open('CleanWords.txt', "r", encoding='utf-8') as fr:
        lines = fr.readlines()
        
    transformer=TfidfVectorizer()
    tfidf = transformer.fit_transform(lines)
    # 转为数组形式
    tfidf_arr = tfidf.toarray()
    tfidf_arr.shape    #(410, 737)
    

    Kmeans聚类

    获取分类

    这里按照经验,将类别设为num_means=3

    kmeans = KMeansClusterer(num_means=3, distance=cosine_distance)  # 分成k类,使用余弦相似分析
    kmeans.cluster(tfidf_arr)
    # 获取分类
    kinds = pd.Series([kmeans.classify(i) for i in tfidf_arr])
    fw = open('ClusterText.txt', 'a+', encoding='utf-8')
    for i, v in kinds.items():
        fw.write(str(i) + '\t' + str(v) + '\n')
    fw.close()
    

    在txt文档中,就有每一条建议与之对应的分类了
    分完类之后,我们还要找出这个类的主题词,所以我们先按照分类结果,把410个文本放到对应的3个类之中。

    获取分类文档

    index_cluser = []
    
    with open('ClusterText.txt', "r", encoding='utf-8') as fr:
        lines = fr.readlines()
    
    for line in lines:
        line = line.strip('\n')
        line = line.split('\t')
        index_cluser.append(line)
    # index_cluser[i][j]表示第i行第j列
    
    with open('CleanWords.txt', "r", encoding='utf-8') as fr:
        lines = fr.readlines()
        
    for index,line in enumerate(lines):
        for i in range(410):
            if str(index) == index_cluser[i][0]:
                fw = open('cluster' + index_cluser[i][1] + '.txt', 'a+', encoding='utf-8')
                fw.write(line)
    fw.close()
    

    得到分类文档之后,再分别统计不同类之中出现频率最高的那个词,默认为我们的主题词。

    获取主题词

    for i in range(3):
            
        with open('cluster' + str(i) + '.txt', "r", encoding='utf-8') as fr:
            lines = fr.readlines()
            
        all_words = []
        for line in lines:
            line = line.strip('\n')
            line = line.split('\t')
            for word in line:
                all_words.append(word)
            c = Counter()
            for x in all_words:
                if len(x) > 1 and x != '\r\n':
                    c[x] += 1
    
            print('主题' + str(i+1) + '\n词频统计结果:')
            # 输出词频最高的那个词,也可以输出多个高频词
            for (k, v) in c.most_common(1):  
                print(k,':',v,'\n')
    
    

    在这里插入图片描述
    最后,将所有建议聚类为三类,三类分别关键词为:1收费;2音乐,付费;3平台

    结论

    我们将所有建议聚类为三类,三类分别关键词为:1收费;2音乐,付费;3平台。此后,在对各个用户的特征处理时,可以将建议文本聚类的类别进行量化,参与对付费与否以及付费程度的探索中。

    展开全文
  • 文本聚类算法

    2020-08-11 10:47:53
    1 聚类思想 聚类是一种无监督学习。也就是说,聚类是在预先不知道欲划分类的情况下,根据信息相似度原则进行信息聚类的一种方法。聚类的思想是使得属于同类别的...2 文本聚类一般步骤 2.1 文本表示(Text Representatio

    1 聚类思想

    聚类是一种无监督学习。也就是说,聚类是在预先不知道欲划分类的情况下,根据信息相似度原则进行信息聚类的一种方法。聚类的思想是使得属于同类别的对象之间的差别尽可能的小,而不同类别上的对象的差别尽可能的大。与分类规则不同,进行聚类前并不知道将要划分成几个组和什么样的组,也不知道根据哪些空 间区分规则来定义组。常见的聚类算法包括:K-均值聚类算法、K-中心点聚类算法、CLARANS、BIRCH、CLIQUE、DBSCAN等。

    2 文本聚类一般步骤

    2.1 文本表示(Text Representation)

    把文档表示成聚类算法可以处理的形式。

    2.2 聚类算法选择或设计(Clustering Algorithms)

    算法的选择,往往伴随着相似度计算方法的选择。在文本挖掘中,最常用的相似度计算方法是余弦相似度。聚类算法有很多种,但是没有一个通用的算法可以解决所有的聚类问题。因此,需要认真研究要解决的问题的特点,以选择合适的算法。

    2.3 聚类评估(Clustering Evaluation)

    因为没有训练文档集合,所以评测聚类效果是比较困难的。 常用的方法是: 选择人工已经分好类或者做好标记的文档集合作为测试集合,聚类结束后,将聚类结果与已有的人工分类结果进行比较。常用评测指标也是查全率、查准率及F1值。

    3 常用文本聚类算法

    3.1 K-means

    作为基于距离的典型聚类算法,“K-means”一词最早于1967年被加州大学的詹姆斯麦奎恩(James MacQueen)首次使用,而其算法思想则可以追溯到术语提出的十年之前——1957年,斯图尔特劳埃德(Stuart Lloyd)在研究一种脉冲码调制技术时首先研发了 K-means 的标准算法,遗憾的是,其学术成果直到1982年才被贝尔实验室公开出版。在此之间的1965年,福吉(E.W.Forgy)在《Biometrics》发表了本质上相同的方法,因此, K-means 算法有时也被人们称为 Lloyd-Forgy 方法。

    已知数据集 D = x 1 , x 2 , . . . x n D={x1,x2,...xn} D=x1,x2,...xn,其中每一个样本都可以由一个 d 维实向量表示, K-means 聚类的目的便是要将数据集中的这 n 个样本划分到 k 个集合之中(k 小于等于 n),使得各个集合的组内平方和(Within-Cluster Sum of Squares)最小。该问题也可以由下式表示:
    在这里插入图片描述

    其中,S 为样本的聚类, μ i μi μi则为 S i Si Si中所有点的均值向量。

    在文本聚类中,文本数据集中的每一个样本(我们将其简单称为“文档”)都可以由一个文档特征向量表示,被划分为同一个集合的文档在 K-means 中也被称之为属于同一个簇(cluster),而用于规定簇的中心点则本称为质心(centroid),当一个向量到某个质心的距离小于其至其他所有质心的距离时,这个向量对应的文档将本划分入质心所对应的簇中。为了在文本数据分析中达到文本聚类的目标,K-means 聚类的算法过程通常分为以下步骤:

    1)文本数据集中随机选取K个文档,作为初始的质心;

    2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心对应的簇;

    3)通过求中心向量的方式重新计算已经得到的各个簇的质心;

    4)迭代2~3步直至新的质心与原质心相等或小于指定阈值(或是迭代次数达到外生给定的最大次数),算法结束。

    K-means 算法的主要优势在于快速简单、对大数据集有较高的效率,在分析大量文本数据时相比与其他聚类算法更加实用,而其缺点在于容易受 K 值、初始类质心样本选择或初始类划分的影响,在进行文本聚类时,确定最优的 K 值往往需要花费大量的时间资源。

    3.2 BIRCH

    BIRCH 算法,全称为利用层次方法的平衡迭代规约和聚类(Balanced Iterative Reducing and Clustering Using Hierarchies),这一在1996年由 Tian Zhang 提出来的聚类算法。虽然名字冗长拗口,但 BIRCH 算法却是广受学界认可的一种节约内存资源的高质量聚类方法。

    相比于其他多遍扫描的聚类算法, BIRCH 算法利用了树结构来帮助我们快速的聚类,我们一般将 BIRCH 算法中的这种树结构称之为聚类特征树(Clustering Feature Tree,CF Tree)。聚类特征(Clustering Feature,CF)是聚类特征树的重要概念,它可以被理解为在聚类特征树某一节点上对样本划分的一种状态,其定义可由下式表示:
    在这里插入图片描述

    可以看到,我们将聚类特征表示为一个三元组结构,其中 N 为这个聚类特征中拥有的样本点的数量, LS 为这个聚类特征中拥有的样本点各特征维度的和向量, SS 则代表这个聚类特征中拥有的样本点各特征维度的平方和向量。聚类特征CF有一个很好的性质,就是满足线性关系,也就是说两个聚类特征可以进行相加,且有

    C F 1 + C F 2 = ( N 1 + N 2 , L S 1 + L S 2 , S S 1 + S S 2 ) CF1+CF2 = (N_1+N_2, LS_1+LS_2, SS_1 +SS_2) CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)

    在这里插入图片描述

    作为 BIRCH 算法中的核心部分,聚类特征树,也称 CF 树,是由多个不同层次下 CF 组成的节点构成的树结构,除了聚类特征 CF 以外, CF 树还涉及另外三个重要概念:是每个内部节点的最大 CF 数 B B B、每个叶子节点的最大 CF 数 L L L ,叶节点中每个 CF 的最大样本半径阈值 T T T ,通过控制这三个参数,在数据集准备充分的情况下,我们就能够构建出一棵聚类特征树。

    聚类特征树的构建过程如下:

    1)从根节点开始,自上而下选择最近的子节点;

    2)到达叶子节点后,检查最近的元组 C F i CF_i CFi 能否在大样本半径阈值 T T T 范围内吸收此数据点,如果可以,则更新CF值;若不能,则考虑是否可以添加一个新的元组,若无法添加则分裂最远的一对元组,作为种子,按最近距离重新分配其它元组;

    3)更新每个非叶节点的CF信息,如果分裂节点,在父节点中插入新的元组,检查分裂,直到root。

    在此基础上, BIRCH 算法的流程分为以下4个阶段:

    1)在内存中构建 CF 树;

    2)对第1阶段中的 CF 树进行瘦身(可选步骤);

    3)以 CF 叶子节点对应的子簇为基础,实现数据点的聚类;

    4)对第3阶段的聚类结果进行精修(可选步骤)。

    @todo 补充算法流程

    在文本聚类中, BIRCH 算法的主要优势体现在它对系统内存的节约,在算法执行过程中,聚类特征树仅仅保存了 CF 节点和对应的指针;树状的结构使得 BIRCH 算法更适用于在分析那种实际种类繁多的文本聚类场景之中;由于可以识别噪音点, BIRCH 算法常用于对大量数据集进行初步分类的预处理。但同时, BIRCH 算法由于在执行过程中对每个节点的 CF 个数加以了限制,故可能导致聚类的结果因此与真实的类别分布不同,另外文本数据高维特征的特点也会使 BIRCH 算法的聚类效果大打折扣,在使用 BIRCH 算法进行文本聚类之前,我们应首先进行一定的降维处理。

    3.3 GMM(高斯混合模型聚类)

    学界对高斯混合模型(Gaussian mixture model,GMM)的研究动力最早来自于动物学,1893年,动物学家瓦尔特弗兰克拉斐尔·韦尔登(Walter Frank Raphael Weldon)在观察观察前人对雌性滨蟹前额身长比的研究报告时突发奇想,推测这些分布直方图的不对称性可能来自于两个不同的进化分歧,关于混合模型的研究也由此启程。

    随着后人在数学计算与统计学方面的努力,今天高斯混合模型已经成为了数据挖掘中广泛应用的聚类模型之一,特别是在图像处理方面广受欢迎。作为一个典型的概率模型类统计学习方法,高斯混合模型的基本思路便是将聚类问题看作为对每个样本的概率密度分布进行估计的问题,且根据中心极限定理,所有的样本都被假设服从于某一参数条件下的高斯分布。

    高斯分布的概率密度分布函数:

    ϕ ( y ∣ θ ) = 1 2 π σ e x p ( − ( y − μ ) 2 2 σ 2 ) \phi \left ( y\mid \theta \right )= \frac{1}{\sqrt{2\pi }\sigma }exp\left ( -\frac{\left ( y-\mu \right )^{2}}{2\sigma^{2}} \right ) ϕ(yθ)=2π σ1exp(2σ2(yμ)2)

    简单来说,高斯混合模型的聚类过程分为以下步骤:

    1)假设数据集样本整体都服从某个由 K K K 个高斯分布加权构成的整体混合分布,该分布被定义为: P ( y ∣ θ ) = ∑ k = 1 K α k ϕ ( y ∣ θ k ) P(y\mid \theta )=\sum{k=1}^{K}\alpha{k}\phi (y\mid \theta_{k}) P(yθ)=k=1Kαkϕ(yθk)

    2)运用极大似然估计的方法对高斯分布概率密度函数中的参数 μ k \mu{k} μk σ k \sigma{k} σk 以及权重 α k \alpha_{k} αk 进行估计;

    3)得到明确的概率密度函数后,对数据集中的样本分别在每一个高斯分布上投影;

    4)选取对应概率最大的分布,作为该样本点所属的类。

    在求解极大似然估计时,实际执行中为了解决计算机函数求导的困难,一般会采用 EM 算法:第一步,对各个高斯模型的参数进行初始化;第二步,基于当前参数估计每个高斯模型的权重;第三步,基于估计的权重,重新确定高斯模型的参数。重复这二三两个步骤,直到两次参数估计的结果差异足够小,即近似达到极值( EM 算法存在陷入局部最优的风险,因此该估计值不一定就是最优值)。

    我们可以发现, EM 算法的思想与 K-means 聚类中的不断迭代过程似乎由异曲同工之妙,与 K-means 相比,高斯混合模型与之的共同点还在于二者都需要指定固定的类别数 K ,并且都运用到了初始化的过程,其中K-means 初始化中心, 高斯混合模型则初始化密度函数参数;而二者的区别则在于优化的目标不同, K-means 强调最短距离,而高斯混合模型则基于极大似然估计,同时二者在最终的类别划分上也不相同,依据分别为距离与概率。

    @todo 补充文本数据分析中 GMM 的优势

    劣势:类别数 K 不能设定过多,不适用于类别数繁多的文本数据分析场景。

    3.4 GAAC(凝聚层次聚类)

    GAAC(Group-average Agglomerative Clustering),也称凝聚层次聚类法,是一种基于层次聚类法(Hierarchical Clustering)思想的无监督学习方法。GAAC 的核心思路是簇与簇之间的合并,在聚类的过程中,所有的样本点在开始时各成一簇,之后不断重复合并两个距离最近的簇,直至簇的个数达到指定的数量。

    GAAC 法聚类的关键点在于明确两个簇之间的相似度度量,常用的度量方法有以下三种:

    1)单链(MIN):将不同两个簇的两个最近的点之间的距离作为两个簇的相似度。

    2)全链(MAX):将不同两个簇的两个最远的点之间的距离作为两个簇的相似度。

    3)组平均:取来自两个不同簇的所有点组合,计算点与点之间的距离,以其平均值作为两个簇的相似度。

    同时,在 GAAC 法中,为了防止出现过度簇与簇合并的现象,在算法执行时会规定一个退出条件,如当前簇数为初始簇数的 10% 等等,以保证凝聚层次聚类法得到理想的聚类结果。

    在文本数据分析中,我们很少会对 GAAC 法进行直接的应用,这是因为 GAAC 在计算簇相似度时往往需要一次性计算大量的样本点间距离,这使得在处理文本数据这一类高维度数据时将耗费大量的资源与时间。因此,当我们面对数据规模较大的文本数据分析时,对 GAAC 法进行使用前一般会结合有效的抽样技术,并将它作为其他聚类方法的铺垫或补充。

    展开全文
  • 文本聚类算法总结

    万次阅读 2019-03-01 14:30:03
    一、文本聚类定义 文本聚类主要是依据著名的聚类假设:同类的文档相似度较大,而不同类的文档相似度较小。作为一种无监督的机器学习方法,聚类由于不需要训练过程,以及不需要预先对文档手工标注类别,因此具有一定...
  • sklearn文本聚类分析

    千次阅读 2020-05-10 19:04:15
    面对如今的大数据时代,各种各样的信息令人眼花缭乱,你根本不知道哪些信息是自己所需要的,而一个个看又会浪费很多时间,更不用说对一大堆信息进行分类或总结了。对于聚类处理,这里使用 birch...
  • 文本聚类浅析

    千次阅读 2018-10-02 14:25:11
    首先我来介绍一下什么是文本聚类,最简单的来说文本聚类就是从很多文档中把一些 内容相似的文档聚为一类。文本聚类主要是依据著名的聚类假设:同类的文本相似度较大,而不同类的文本相似度较小。作为一种无监督的机器...
  • python数据分析:新闻文本聚类

    万次阅读 多人点赞 2019-02-26 14:12:54
    文本聚类应用场景:提供大规模文档进行类别划分并提取公共内容的概括和总览;找到潜在的各个文档间的相似度以进行相似度判别、类别修正,以减少浏览相似文档和信息的时间和精力。 通常,聚类分析(也包括其他算法...
  • 1. 概述 广义的分类(classification或者categorization)有两种含义:一种含义是有指导的学习(supervised learning)过程,另一种是无指导的学习...给定分类体系,将文本集中的每个文本分到某个或者某几
  • tf-idf kmeans文本聚类

    2021-11-09 19:23:44
    文本聚类 数据集 THUnews中文新闻文本分类 方法 jieba分词后,使用tf-idf提取特征,提取时使用停用词表删除停用词,最后使用kmeans进行聚类。 优化 优化停用词表,增加max_feature特征,使用minibatchkmeans增加聚类...
  • K-Means文本聚类python实现

    热门讨论 2011-03-02 21:39:13
    文本进行聚类文本预处理-->构造特征向量-->聚类,压缩包内含有实验用语料
  • 文本聚类

    2021-01-03 15:33:43
    聚类(cluster analysis )指的是将给定对象的集合划分为不同子集的过程,目标是使得每个子集内部的元素尽量相似,不同子集间的元素尽量不相似。 注意,单词的颗粒度(分词、新词提取、关键词提取) < 短语的颗粒...
  • 该工作在8个短文本聚类数据集上取得了显著提升(比如正确率提升3%~11%)。 所谓对比学习,重点在于对比,那对比的对象是谁? 答曰:增强的数据。假设如果两个增强句子的原句子一样,那么拉近它们,否则推远它们。 在CV...
  • 六种常用的文本聚类算法介绍

    千次阅读 2020-05-17 23:21:34
    在分类算法中,训练集为已经标注好的数据集,但是微博文本具有的大数据特性及不确定性决定了标注数据的难度,因此本文选择聚类算法对大量且随机的微博文本进行处理。 大量文本建模后还需要对主题分布进行聚类以得到...
  • 文本聚类是聚类在文本上的应用,即在不需要标注语料的情况下,在文档层级上,用无监督方法自动找出文档与文档间的关联。 1.1 聚类 它是指将给定对象的集合划分为不同子集的过程,目标是使得每个子集内部的元素...
  • 聚类集成中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果....本数据集的实验结果表明: SMSA 和 HSM2MCLA 比其他基于图划分的集成算法更优越; HSM2MCLA 可获得与SMSA 相当的结果 ,而计算需求却明显低于 SMSA.
  • 文章目录一、文本分类和聚类概述1:文本分类概述2:文本聚类概述二、文本分类1:分类的学习算法2:使用相关反馈(Rocchio)3:最近邻学习算法4:贝叶斯理论三、文本聚类1:K-Means 一、文本分类和聚类概述 1:文本...
  • NLP笔记之文本聚类

    2021-02-25 20:01:27
    NLP笔记之文本聚类 一、概述 文本聚类是聚类在文本上的应用。由浅入深,需要先介绍聚类的思想。 二、聚类思想简介 聚类是将给定对象的集合划分为不同子集的过程,目标是使每个子集内部的元素尽量相似,不同子集(簇...
  • 简介鉴于基于划分的文本聚类方法只能识别球形的聚类,因此本文对基于密度的文本聚类算法展开研究。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种典型的基于密度的聚类方法,可以找出...
  • 文本聚类教程

    万次阅读 多人点赞 2017-12-07 15:53:29
    文本聚类教程 本人曾做机器学习方向,由于实习需要转做文本聚类、分类的工作,虽然大致相似,但仍是新手,过程和结果也仅供大神指教。本博包含了作者两周的专心研究调试及由数千行测试得到了300余行...
  • Python基于Kmeans算法实现文本聚类的简单练习

    万次阅读 多人点赞 2018-03-19 17:02:48
    接触机器学习时间不长,也一直有兴趣研究这方面的算法。最近在学习Kmeans算法,但由于工作的原因无法接触到相关的项目实战。为了理清思路、熟悉代码,在参照了...先说一下我的大致思路:1、利用爬虫进行文本数据的爬...
  • 基于sklearn中文文本聚类

    千次阅读 2018-07-25 16:35:42
    目前只是实现了文本聚类。 # -*- coding: utf-8 -*- """ Created on Wed Jul 18 15:53:56 2018 @author: zs """ import re import time import jieba import numpy as np import ...
  • 文本聚类算法介绍

    万次阅读 热门讨论 2015-04-10 12:58:14
    本博客通过对当前比较成熟的聚类算法分析,介绍如何对非结构的数据(文档)做聚类算法;如何利用搜索引擎的相关知识来解决文本聚类问题等
  • 文本特征处理及聚类的几种方法 本项目完整源码地址:https://github.com/angeliababy/textcluster 项目博客地址: https://blog.csdn.net/qq_29153321/article/details/104015257 数据准备 测试数据说明 data_offline...
  • 尝试用bert做文本聚类

    千次阅读 热门讨论 2020-06-14 19:22:38
    尝试用bert做文本聚类 以前文本聚类多以TF-IDF构建词权重的方法进行,在本文中尝试用bert提取的向量做文本聚类。对于bert模型,尝试提取不同层的特征,尝试对bert做fun-tune,观察相应特征对应的文本聚类的效果 ...
  • K-means文本聚类

    2019-12-30 23:38:05
    即无需知道所要搜寻的目标,而是直接通过算法来得到数据的共同特征。如图所示,通过找到合适的K值和合适的中心点,来实现目标的聚类。 其具体算法思想实现过程如下: 1.指定簇的个数 2.随机选取K个中心点 3.将...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,298
精华内容 9,719
关键字:

文本聚类数据集