基于特征聚类的文本信息检索算法研究
2022-07-17杨宇环张开生
杨宇环, 张开生
(1.陕西科技大学 图书馆信息部, 陕西 西安 710021; 2.陕西科技大学 电气与控制工程学院, 陕西 西安 710021)
0 引言
随着网络通讯、物联网技术和云计算技术等现代通信和网络技术的广泛应用,各种结构化和非结构化数据资源呈现爆发式增长,标志着大数据时代[1]进入一个全新阶段.并且文本数据在所有形式的信息资源中占主导地位[2].大量的数据信息是以文本的形式呈现,海量的文本信息作为互联网信息中的主要表现形式[3],成为计算机领域和情报领域的重点研究对象.文本信息的查询、获取以及有效利用是文本信息检索、文本数据挖掘、自然语言处理等文本处理技术的最终目标,是其经济价值和社会价值的重要体现.因此文本处理技术是大数据时代信息利用的关键途径,其中文本信息检索是文本处理技术的重要基础和前提,如何在海量文本信息中准确、全面的检索到读者需要的信息是文本信息检索技术发展的关键问题和研究热点.
从文本信息出现起,文本信息的检索技术就应运而生,成为学者的研究对象.起先是图书情报领域的专家运用传统、手工检索工具进行图书、期刊等文献的题录分类和检索[4];随着计算机技术的产生,出现利用计算机实现联机检索技术对文本进行查询[5-6];近期随着人工智能技术的发展,机器学习、深度学习等技术在自然语言处理领域应用,使得文本信息检索在计算机学科和图书情报学科协同助力下获得飞速发展.目前主流的文本信息检索方法分为三种文本信息挖掘方法,即基于关联规则挖掘算法、基于语义关系挖掘算法、基于模糊聚类算法[7],以及基于文本特征提取的文本信息检索方法[8].随着人工智能领域机器学习相关技术的发展,基于文本特征提取的文本分类、信息检索和文本信息挖掘成为自然语言处理技术在文本主题识别和信息挖掘的重要研究方向.其中基于潜在狄利克雷分配LDA模型的文本信息检索和文本主题识别成为近期研究热点.LDA模型被用于发掘文献中蕴含的潜在主题,是挖掘文本潜在语义的一种统计模型[9].研究表明,LDA模型的运用克服了采用特征抽取方法带来的分类性能受损问题,避免了使用特征滤取方法存在的未考虑词与词之间语义联系的问题[10].但是LDA是一种有监督学习算法,且其可能出现数据过拟合.
针对LDA模型的局限,本文提出一种基于特征聚类的文本信息检索算法.首先采用主成分分析PCA技术对高维文本信息进行降维,去除文本信息中的冗余数据和噪声,保留文本信息的主要特征;其次利用K-Means++算法对降维后的文本特征信息进行聚类,实现文本信息的快速检索.
1 文本特征降维处理
文本信息特征提取是海量数据下文本信息检索的关键步骤.文本数据特征维度高,数据量大,冗余数据多,呈现高维稀疏的特征[11].因此在对文本信息数据进行分词、停用词过滤和TFIDF算法构建向量矩阵等预处理后,需要进行文本向量数据的降维处理,实现保留文本分类特征的主要信息,去除掉冗余信息,提高检索效率.提高信息检索的速度和准确率的关键是文本分类,而文本特征集的降维又是影响文本分类准确率和效率的关键步骤.特征选择和特征抽取是目前主流的特征降维方法.特征选择是按照既定的规则从原始的特征集合中选择出一组少量的特征,使用这些特征来有效的表征原始数据[12].特征选择的统计工具主要有特征频度(TF),文档频度(DF),特征熵(Term Entropy),互信息(MI),信息增益(IG),X2统计(CHI).特征选择的降维效果除依赖训练数据集合本身的特点,分类器的选择也会影响分类结果,不同的分类器的降维效果也不尽相同[13].
特征抽取是通过特定的映射函数将高维的原始特征空间变换成一个新的低维特征空间,新的特征能更好的表征原始数据[14].潜在语义标引(LSI)、主成分分析(PCA)是常用的特征抽取方法.潜在语义索引中的奇异值分解方法在用于大规模数据集时通常分解非常困难,同时存在对数据变化敏感、运算速度慢以及左、右奇异矩阵对存储要求高等缺点[15].主成分分析相对于文本频度、基于分类频率的文本频度和TFIDF降维效果最好[16].同时相对于LDA模型等的有监督算法,主成分分析(Principal Component Analysis,PCA)属于无监督的机器学习算法,在特征提取过程中不需要分类样本数据.主成分分析最早是由美国统计学家皮尔逊(Pearson)在研究对空间中的一些点进行最佳拟合直线和平面时,提出了主成分分析的方法[17].PCA的基本思想是将原始的、数量较多的彼此相关的指标用较少数量的彼此无关的综合指标来代替,同时尽可能的使较少的综合指标更多的反映原始指标包含的信息[18].通过PCA降维能将原始的高维文本特征矩阵转换为较低维的正交特征矩阵,此矩阵由原始文本特征矩阵的主成分组成,并尽可能多的保留原始特征矩阵的特征信息[19].PCA可以有效缓解维度灾难问题还能够在降维的同时,使有效信息损失最小化.高维数据降维的核心点在于坐标系的合理建立,假设数据X和前K个主成分如下:
(1)
(2)
PCA算法实现降维的仿真如图1所示.
图1 PCA降维仿真图
2 文本特征聚类算法
文本特征聚类属于数据挖掘领域的一个重要应用,它的实现原理是依据文本的相似性,将相似性高的文本划分为一个簇,各个簇之间关联程度较小,因此可实现文本的快速检索,从而帮助读者快速有效地检索出感兴趣的文本信息.
文本聚类方法主要有层次凝聚法、平面划分法、简单贝叶斯聚类法、K-最近邻聚类法、分级聚类法以及基于概念的文本聚类法等[20].聚类算法可以分为两大类:层次聚类算法和划分聚类算法[21].层次聚类算法根据给定的距离定义,计算出每两个对象之间、对象和分组之间以及分组和分组之间的距离,然后按照距离的大小构建一个聚类层次圈.层次聚类法主要分为自底向上和自顶向下两种聚类算法.层次聚类的主要优点是处理速度快,不需要事先指定聚类个数,但是具有o(n3)的时间复杂度[22].
K-Means算法是一种无监督学习,同时也是基于划分的聚类算法,K-Means聚类算法是一个不断迭代的过程[23].K-Means算法的基本思想是,根据参数k,随机选取k个点作为初始聚类中心,根据每个点与初始聚类中心的距离将所有点划分为k个簇,以每个簇的质心作为新的聚类中心,不断地迭代以上的步骤,对簇进行调整,使簇内对象之间的距离尽可能小,而簇间对象之间的距离尽可能大,直至目标函数收敛[24].较好的聚类结果表现为簇内密集,但簇与簇之间具有较为明显的区分.
综合分析,本文选择K-Means算法作为基础聚类算法,K-Means聚类效果如图2(a)~(b)所示.
图2 K-Means算法特征聚类仿真结果图
但是传统的K-Means算法依靠随机选择确定质心位置,势必影响聚类结果和运行时间.因此本文参考俞皓芳提出的改进K-Means++算法进行文本聚类[25].
K-Means算法的结果依赖于由初始聚类中心出发所遇到的第一个局部极值点,不同的初始聚类中心很可能导致截然不同的聚类结果.改进K-Means++算法是在K-Means算法的基础上进行的优化,其步骤为:
Step1首先随机选择输入数据中的一个点作为第一个聚类中心.
Step2计算出数据中所有的点到step1中选取的点的距离.
Step3找出step2中所有距离最小的一个.
Step4依据较大的点被作为聚类中心概率最大的原则,选择一个新的聚类中心.
Step5不断重复step2~step4,一直得到K个聚类质心.
Step6利用得到的K个质心执行K-Means算法.
利用改进K-Means++算法得到的每个聚类中心表示一个文本信息的主要特征,将该特征作为聚类样本,假设将样本信息记为w,则对w进行聚类后,两个样本特征之间的相似度可以表示为:
(3)
式(3)中:n表示文本数据当中总共包含的文本特征数,vi为第i个特征的权重.由此计算文本信息检索的目标函数记为:
(4)
式(4)中:c为特征类别,将文本信息聚类结果的最小值转换为求目标函数的最小值.根据拉格朗日法,得到目标函数所要满足的约束条件,从而求得其最小值.
3 实验结果与分析
本文在Intel(R) Core(TM)i5-6200U CPU,主频为2.30 GHz,GPU显卡为AMD Radeon R5 M315以及4 GB内存配置的Windows7计算机上进行测试.
实验数据集来源于UCI标准数据库中下载的flame数据集.UCI数据库是加州大学欧文分校提出的用于机器学习的数据库,这个数据库共有559个数据,实验采用UCI数据库下的flame数据集,其中记录数为240,维度为2,聚类数为2.
检索准确率和检索时间是信息检索、分类、识别、翻译等领域的重要评价指标.准确率指的是簇划分正确点的个数与样本点总个数的比值,用来反映算法的准确程度.检索时间体现了算法的有效性,在同一个数据集下,检索时间的缩短能够减少迭代和加快收敛速度,从而有效提高算法的计算性能.因此本文采用检索准确率和检索时间作为本文算法的评价指标,分别与合并聚类和传统K-Means聚类算法进行对比.其中,合并聚类是属于层次法,属于聚类算法的其中一种,主要是对给定的数据集进行层次分解,也是文本聚类当中一种常见的算法.三种算法的检索准确率对比图如图3所示.
由图3可以看出,本文算法相较于传统K-Means算法和合并聚类算法检测准确率得到大幅度提高.可以看出不同算法整体上呈现出检索准确率随着文本信息量增大而增大的趋势.传统K-Means算法与合并聚类算法整体检测准确率相当,其中合并聚类算法的检索准确率略胜一筹.经过改进之后的算法在文本检索效率方面表现出了良好的效果,准确率基本符合需求.
为了进一步验证本文算法在文本信息检索中的有效性,本文统计了三种不同算法检索时间,结果如表1所示.
表1 不同算法检索时间
根据表1中的结果可知,本文算法的检索时间,相较于传统K-Means算法,时间降低13.3个百分点,相较于合并聚类算法,时间降低25.7个百分点,充分体现本文算法在文本数据检索方面的优越性.
4 结论
基于文本信息的高维稀疏特征,导致在特征聚类时的信息量过于庞大,使得数据维数过高.本文首先采用主成分分析(PCA)技术对高维文本信息进行降维,去除掉冗余的特征信息,尽可能保留文本的原有特征信息.对K-Means++算法进行了相关分析,K-Means++算法具有较高的运算速率,并且对于数据量较大的情况下,能表现出良好的伸缩性,且K-Means++算法的时间复杂度接近于线性,适合大规模文本数据集挖掘的优点.因此本文将PCA降维和K-Means++算法相结合用于文本信息的检索,选用检索准确率和检索时间两种算法评价指标进行算法效率评价,将本文算法与传统K-Means算法与合并聚类算法进行比较,其性能均优于传统K-Means算法和合并聚类算法,为基于特征提取和特征聚类的文本信息的检索提供了一种新方法.