基于KMeans算法的新闻文本内容过滤传媒

【关键词】:K-Means算法;文本内容过滤;文本聚类;文本表示

1概述

1.1研究背景和意义

1.2研究现状

2文本表示模型

为使计算机能快速有效地对文本进行处理,需要将文本数据进行数学建模,将半结构化的文本数据转化为计算机可以处理的结构化形式,一方面能保留文本内在结构,真实地反映文本的语义内容,另一方面对不同文本也具有一定程度上的区分能力。

2.1空间向量模型

20世纪60年代末Salton提出了向量空间模型(VectorSpaceModel,VSM)[3],成为了目前应用最为广泛的文本表示模型。向量空间模型就是要将文本表示为一个向量空间下的向量,数学表达式如下:

(2-1)

其中,代表文本集中的某一文本,表示文本中的一个特征项,代表特征项在文本中的权值。

在向量空间模型中,需要通过特征项所在维度上的权值大小来反映该特征项对文本内容的贡献程度大小,即对不同文本的区分能力,因此特征权值的计算对于文本表示有着很重要的影响。当下特征权值计算的方法主要有:布尔函数、词频函数、词频-逆文件频率(TF-IDF)函数等,其中最为常用的是TF-IDF函数[7]。

TF-IDF权重计算函数重点考虑以下两个因素:

(1)词频TF(TermFrequency):特征词在该文本中出现的次数,它反映的是该特征词对于文本内容的贡献程度的大小。

(2)逆文件频率IDF(InverseDocumentFrequency):特征词在文本数据集中出现情况。IDF越大,说明文本数据集中出现该特征词的文档总数越少,说明该特征词对文档集有越出色的区分能力。计算公式如下:

(2-2)

N为文本数据集中所有的文本数目,为整个文本数据集中出现过特征词的文档的总数,当越小,就说明该特征词的文档区分能力越好。

综上所述,TF-IDF特征的权重计算公式为:

(2-3)

为特征词的词频。

一方面TF-IDF增大了小范围文本中高频特征词的权重,而另一方面也降低了那些对文本内容贡献很小的极高频词,使用TF-IDF方法进行权重计算可以提高文本表示的精确度。向量空间模型的提出,可以很好地将文本聚类问题映射为向量之间的数学运算处理问题来解决。

2.2概率主题模型

LDA模型包括文档,主题,词汇三层结构。“词汇”作为文本数据的基本单位,构成了文本数据的特征,定义为词汇表上的一项,使用一个单位向量来表示,即这个词在词汇表上的索引;“文档”为N个词的序列,记作,其中表示文档中的第N个词;“语料库”是M个文档的数据集合,记作。

(1)针对文本数据集中的每一篇文档,从主题分布当中随机选择一个主题z;

(2)被选择的主题对应着词袋中的词语的概率分布,在词语分布中对词语进行选择;

(3)重复上面(1)(2),直到文档中的所有单词都被遍历,N个单词被全部选择。

定义为一个主题向量,主题向量矩阵的每一列表示文本数据集中的文档以一定的概率分布选择了这个主题,其中这个主题向量是非负归一化向量;是的分布,具体表现为Dirichlet分布;N代表文本数据集中词的数量,表示选择的主题,而表示词汇表中第n个词汇,表示给定条件下,对应主题的概率分布;表示在给定主题条件下,对应的词汇的概率分布。

LDA模型中主题的混合向量、主题Z和词语的联合概率为:

(2-5)

那么,其模型可以用下图来进行表示:

其中,是参数为的Dirichlet分布,其分布为:

(2-6)

LDA模型其实是通过输入的文本语料库,对两个控制参数和进行学习和训练,通过学习出这两个控制参数确定模型,从而用来生成文档。其中和分别满足以下条件:

:分布需要一个向量参数用于生成一个主题向量,该控制参数也就是Dirichlet分布的参数;

:相应的各个主题分布下的词汇的概率分布矩阵。

在LDA中,估计和这两个参数可以使用EM算法或者吉布斯采样(GibbsSampling)算法。Gibbs采样法的中心思想是贝叶斯估计,是把待估计的参数看作是服从先验分布的随机变量,这样的优点是不会陷入局部最优值,结果较基于最大后验估计MAP的EM算法更为准确,但算法的收敛速度会比较慢。

3文本聚类算法

文本聚类是把抽象或具体的对象或数据以非监督的方式根据文本对象间的相似度自动划分到不同类簇当中去的过程。聚类算法的选择对于最后的聚类结果好坏至关重要。目前应用比较广泛的聚类算法包括:BIRCH算法,DBSCAN算法以及K-Means算法。

3.1BRICH算法

BIRCH(BalancedIterativeReducingandClusteringUsingHierarchies)算法即利用层次方法的平衡迭代规约和聚类。首先,BIRCH是一种聚类算法,它最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类,同时通过单遍扫描数据集能最小化I/O代价。整个算法过程分为三个阶段:

(1)扫描所有数据,把稠密数据分成簇,稀疏数据作为孤立点对待;

(2)补救由于输入顺序和页面大小带来的分裂;

(3)把中心点作为种子,保证重复数据分到同一个簇中,同时添加簇标签。

BIRCH算法的主要优点在于节约内存,聚类速度快,可以识别噪音点,还可以对数据集进行初步分类的预处理。但是缺点也十分显著,聚类的结果可能和真实的类别分布不同,对高维特征的数据聚类效果不好,如果数据集的分布簇不是类似于超球体,或者说不是凸的,则聚类效果不好。

3.2DBSCAN算法

DBSCAN算法核心思想就是先发现密度较高的点,然后把相近的高密度点逐步都连成一片,进而生成各种簇。具体实现步骤:

(1)首先确定半径r和minPoints.从一个没有被访问过的任意数据点开始,以这个点为中心,r为半径的圆内包含的点的数量是否大于或等于minPoints,如果大于或等于minPoints则改点被标记为centralpoint,反之则会被标记为noisepoint;

(2)重复(1)的步骤,如果一个noisepoint存在于某个centralpoint为半径的圆内,则这个点被标记为边缘点,反之仍为noisepoint。重复步骤1,知道所有的点都被访问过。

DESCAN算法的结果中任何簇当中的数据点都不包括噪声点和离群点,对噪声不明显,但也存在着需要调参且参数组合对于最后的聚类结果影响较大,确定距离r和minPoints,当数据集的密度不均匀、聚类的间距相差很大时聚类质量差的问题。

3.3K-Means算法

K-Means算法是目前比较简单易解释而且被普遍使用的聚类算法,原理是首先确定最终的聚类类簇数k,随机选取k个文本数据作为初始的聚类中心,以这k个中心为基准,对剩余的对象以不同点间欧式距离作为衡量相似度的指标,计算剩余对象距离中心点的欧式距离,将其划分到距离最近的点所在的类簇当中去;重新计算类簇平均值,将每个簇的平均值定义为新的簇中心,重新计算各个对象到新的簇中心的距离,继续划分;这个过程不断进行迭代,直到簇中心与簇中数据对象的均值吻合,不发生明显变化为止。假设要将文本数据集划分为k个簇,划分算法的主要内容为随机对文本数据集进行粗略的划分,然后通过不断迭代,文本数据来回移动重新定位改进划分,类簇不断更新,其中划分的标准是要求同一个类簇之间的文本数据尽量靠近,相似度较高,而不同簇之间的对象尽可能远离,相似度较低。

K-Means算法的流程如下:

(1)随机选取k个数据作为此次聚类的初始聚类中心,此时迭代次数为0;

(2)对剩余的数据对象计算其与质心之间的文本相似度,把每个数据对象分配到相似度最高的簇当中去;

(3)计算每个簇中所有数据的均值,形成新的质心;

(4)重复(2)、(3),直至算法收敛,得到k个类簇,算法得以结束。

K-Means算法是目前最为常见的解决聚类问题的经典的聚类算法,很多文本聚类问题都是在K-Means算法的改进或者结合过程中解决的。K-Means算法运行流程简单,易于解释和实现,算法收敛快,可收缩性强,可以用于处理大数据集,当不同类簇对象之间具有较大的差异性且结果簇内部较为密集时,聚类性能较好。相比DBSCAN算法和BIRCH算法,仍然在文本过滤技术方面存在较大优势,因此本文重点研究K-Means算法在新闻文本内容过滤中的实际应用。

4基于K-Means算法的新闻文本内容过滤

本节将针对中文新闻文本数据集,重点研究文本内容过滤过程中的关键聚类技术,采用经典聚类算法—K-Means,采用向量空间模型,对中文新闻文本进行内容过滤,从海量信息中快速有效地为找到用户感兴趣的新闻类别,挖掘用户兴趣点,有效地为用户进行新闻内容的个性化推荐,推进社会主义新时代新闻理论创新,弘扬时代精神。在原有K-Means聚类算法的基础上,针对传统向量空间模型中假设词与词之间独立,割裂了文本中词之间可能存在的语义关系的缺点进行改进,使用概率主题模型进行文本生成,概率主题模型的使用能够挖掘文本更深层次语义。通过引入LDA模型,挖掘文本主题即“关键词”,提高文本聚类的性能,进而提升了文本内容过滤的准确性。

4.1文本数据集的获取

图4-1数据格式

样本打标的代码逻辑为:先逐个读入原始数据集中的.txt文件,然后正则表达匹配出URL(新闻类别)和content(新闻内容),创建以新闻类别命名的文件,然后将content存入不同文件中。此外,本文还去除了字符数小于30的新闻数据,以减少过短文本对结果的影响。

4.2文本内容聚类模块设计

本实验共分为四个模块来进行,第一个模块是文本预处理模块,将中文文本进行分词和去停用词处理。第二个模块是文本表示模块,把文本表示成计算机可以处理的结构,其中包括使用文本表示模型进行文本表示,并进行特征降维和权重计算。第三个模块是聚类模块,对文本向量使用K-Means算法进行文本聚类。第四个模块是将改进前后的K-Means算法聚类结果使用聚类评价指标进行性能对比。

具体流程如下图所示:

4.2.1文本预处理

文本数据是一种非结构化或者半结构化数据,必须对文本进行处理,将其转换为成为计算机可以处理的结构化形式。文本预处理作为其中的关键步骤,主要包括分词和去停用词两个部分。通过中文分词系统将句子最精确地按照词性、语义分开,体现出来词与词之间的间隔,继而通过去除文本中那些本身不具备太多语义,对文本语义区分能力较弱但出现频率很高的词汇,例如中文中的“可以”、“了”、“的”、“如果”等,得到初步的特征词集合。

本文主要采用结巴系统的精确模式分词处理将文本字符串分割为分散的有独立意义的多个词序列,之后过滤掉停用词,减小噪声和离群点,有效地降低特征空间的维度,提高文本聚类的效率和质量。

4.2.2文本表示

针对传统向量空间模型采用词与词之间互相独立的“贝叶斯假设”,割裂了文本词之间可能存在的语义关系,无法发掘文本深层次语义,发现文本潜在“关键词”的缺点,对实验的文本表示部分进行了改进,使用LDA经典概率主题模型进行文本表示,生成了文本的“关键词”挖掘了文本的深层次语义信息。通过这样的偏好挖掘,提高了文本内容过滤,用户个性化推荐的准确度。

4.2.3文本聚类

本文利用K-Means算法进行文本聚类,得出文本聚类结果。值得注意的是,在使用K-Means算法聚类的过程中,可能会由于K值的设定不合理,使得原本属于同一个类别的文本数据被强行划分到了不同类别当中去,或者是原本不属于同一个类别的数据对象被强行归类到一个类别中。类簇的个数即k值的确定对于聚类结果有着相当重要的影响。因此,通过枚举的方法,使k从11增加到18,在每个k值上重复运行数次K-Means(避免局部最优解),并计算当前k的同质性,完整性和V-measure这三个性能评估指标,最后选取在同质性,完整性和V-measure评价标准下聚类质量最好的情况下所对应的K作为最终的类簇数目。

4.2.4聚类结果评价对比

在文本聚类结束后,我们要对聚类结果的好坏进行评估,从而判断文本聚类的改进是否有效。本文中重点使用了同质性(Homogeneity)、完整性(Completeness)、V-measure、调整互信息(AMI)、F值这5个聚类质量评价指标进行聚类性能的评估。这五个指标均为值越高,聚类性能越好,与事先人工标注的类别越发吻合。

本文将传统向量空间模型下的文本聚类结果与LDA模型下的文本聚类结果使用聚类质量评价指标进行性能对比,说明使用LDA模型后的文本聚类性能更优。

4.3聚类结果与分析

4.3.1K-Means文本聚类中类簇个数的确定

前面提到,在K-Means聚类算法中,类簇个数k值的确定十分重要。在实验中,将K固定于11到18,在每个k值上重复运行5次K-Means(避免陷入局部最优),并计算当前k值下的同质性,完整性和V-measure,取5次运算过程中的平均值,并进行画图,最终结果如下图所示:

图3向量空间模型下类簇个数与聚类结果评价指标的关系图

从实验结果可以看出,在传统向量空间模型下进行K-Means文本聚类,同质性随着K值的增加而趋于平稳,而完整性随着K值的增加而趋于平稳,且在K=14之后趋于收敛,而V-measure是同质性和完整性的调和平均。在K=14时,V-measure出现峰值,此后趋于稳定,并且此时同质性和完整性的值也相对较大。综合评价此时聚类效果最好,故选择K=14作为向量空间模型下K-Means聚类的类簇个数。

图4LDA模型下类簇个数与聚类结果评价指标的关系图

从实验结果可以看出,同质性随着K值的增加而逐渐增大,而完整性随着K值的增加而逐渐减少,且在K=16之后趋于下降,而V-measure是同质性和完整性的调和平均。在K=16时,V-measure出现峰值,此后趋于下降,并且此时同质性和完整性的值也相对较大。综合评价此时聚类效果最好,故选择K=16作为LDA模型下K-Means聚类的类簇个数。

4.3.2基于K-Means算法的文本聚类改进前后的聚类效果评价及对比

本文基于传统向量空间模型下的K-Means文本聚类过程,对文本表示模型进行了改进,使用了经典概率主题模型LDA,在此基础上使用K-Means算法进行文本聚类。本文用于评价聚类结果的指标分别为F值,同质性,完整性,V-measure以及调整互信息AMI。根据之前讨论的实验一和实验二的结论,向量空间模型选择类簇个数为14,LDA模型选择类簇个数为16,特征降维的维数为2000,使用K-Means进行文本聚类,迭代次数为5,计算上述文本聚类性能指标平均值,结果如下表所示:

5总结

为实现文本内容过滤,我们采用了K-Means经典文本聚类算法,以无监督学习的方式将新闻文本数据集依据具体的文本内容自动进行归类。此外,针对传统向量空间模型割裂文本语义关系的缺点,引入LDA概率主题模型,对文本“关键词”进行挖掘,实验表明LDA模型确能提升聚类性能,进而提高了文本内容的过滤性能。

本文基于经典聚类算法K-Means,对新闻文本数据集进行了文本聚类,从而达到文本内容过滤的目的。并针对向量空间模型的缺点,对文本聚类过程中文本表示部分进行改进,引入LDA概率主题模型,深层次挖掘文本语义信息,发现潜在“关键词”挖掘了文本隐藏结构和潜在信息,并通过实验证明改进后的文本过滤性能更佳。可以更有效的筛选出与用户历史浏览行为相似的文本数据,并过滤掉有害信息,最大程度上为用户推荐其感兴趣的新闻内容,具有非常的现实意义。

THE END
1.R语言聚类分析:数据聚类算法在数据挖掘与机器学习领域,聚类分析是一种常用的无监督学习方法,其主要目的是将相似的数据点归为一类,从而揭示数据自身的内在结构。R语言作为一种功能强大的数据处理和分析工具,提供了多种聚类分析算法,如K均值聚类、层次聚类、DBSCAN等。本文将从 R 语言的角度介绍数据聚类算法的原理、常用方法和实践案例。 https://www.jianshu.com/p/36fab82dfab2
2.解释聚类分析模型群集中的某些条目具有意义,而其他条目看起来像是随机内容。 部分原因是 k 均值算法必须在群集之间形成任意边界。 所有群集中都有许多条目处于边缘位置,可以属于两个(或更多)群集。 为了减少此类干扰,我们可以按照到各自群集中心的距离对这些条目进行排序,然后查看离中心最近的条目。 https://docs.microsoft.com/zh-cn/learn/modules/unsupervised-learning-clustering/4-interpret-clustering-model
3.大数据最常用的算法主要有哪些1. K-均值聚类算法(K-Means Clustering):将数据集划分为k个簇,每个簇中的数据点与簇中心的距离最小化。常用于数据的无监督聚类。 2. 决策树算法(Decision Tree):通过对数据进行划分和树形结构的建立,预测离散或连续的输出变量。常用于分类和回归问题。 3. 随机森林算法(Random Forest):由多个决策树组成的集成https://wenku.baidu.com/view/faf61cac0366f5335a8102d276a20029bd6463e3.html
4.数据分析中的聚类算法有哪些非负矩阵分解算法是一种基于矩阵分解的聚类算法,它将数据矩阵分解为多个非负矩阵的乘积,每个非负矩阵表示一个潜在的特征空间。算法的基本思想是:先随机初始化多个非负矩阵,然后通过最小化原始数据矩阵和非负矩阵乘积之间的距离来更新非负矩阵,重复以上步骤直到收敛。 https://www.linkflowtech.com/news/1082
5.有哪些常用的聚类算法?无需设定K(可作为K-means聚类探索K的先验算法)对于K-means不擅长的非球形点处理的较好 [缺点]时间https://www.zhihu.com/question/44164453/answer/2751357060
6.聚类算法详解3、算法的数据输入属性:算法处理的结果与数据输入的顺序是否相关,也就是说算法是否独立于数据输入顺序;算法处理有很多属性数据的能力,也就是对数据维数是否敏感,对数据的类型有无要求。 4、聚类算法有哪些类 二、算法介绍 1、基于层次的方法(Hierarchical methods) https://blog.csdn.net/abc200941410128/article/details/78541273
7.机器学习(二)之无监督学习:数据变换聚类分析聚类算法(clustering algorithm)将数据划分成不同的组,每组包含相似的内容。 无监督学习的一个主要挑战就是评估算法是否学到了有用的东西。我们不知道正确的输出应该是什么,很难判断一个模型是否“表现很好”。,通常来说,评估无监督算法结果的唯一方法就是人工检查。 https://www.flyai.com/article/516
8.17个机器学习的常用算法在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。 3.半监督式学习: 在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理https://aidc.shisu.edu.cn/78/aa/c13626a161962/page.htm
9.基于聚类和XGboost算法的心脏病预测1.2 聚类算法 本文引用的聚类算法是K-means 算法, K-means算法中的K代表类簇个数, means代表类簇内数据对象的均值(这种均值表示的是类簇中心)[3]. K-means算法是一种经典的聚类算法, 此算法以数据对象之间的距离作为聚类标准, 即数据对象之间距离越小则表示这类数据拥有较高的相似度, 就会朝着一个中心点聚集https://c-s-a.org.cn/html/2019/1/6729.html
10.8个超级经典的聚类算法腾讯云开发者社区DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,用于将高维数据分组为密度相连的、具有相似特征的多个数据簇。其原理如下: 选择参数:DBSCAN算法需要两个关键参数,即ε(eps)和 MinPts。其中,ε用于定义邻域的大小,MinPts是指在邻域内至少应该有的数据点数目。 https://cloud.tencent.com/developer/article/2430459
11.有监督的聚类算法有哪些有监督分类算法有哪些有监督的聚类算法有哪些 有监督分类算法有哪些 机器学习应用分析–有监督算法-分类算法 ###按学习方式分类: 监督学习 无监督学习 半监督学习 强化学习 ①监督学习 数据集中的每个样本有相应的“正确答案”, 根据这些样本做出预测, 分有两类: 回归问题和分类问题。https://blog.51cto.com/u_12228/10764841