基于聚类特性的大规模文本聚类算法研究

一、引言随着Internet的飞速发展,人们能从网上得到更多的信息,但过多的信息常常会导致信息迷失。将信息进行分类是帮助信息利用的有效方法,聚类则是文本类别划分时常用的技术,其特点是不需训练集即可从给定的文本集合中找到聚类划分。已有的聚类方法大多是针对小规模数据的,当计算资源和时间受到限制时,原有的大部分方法已不能满足要求,需要能够处理大规模数据的算法。标准k均值方法是比较基本也是很常用的一种聚类方法,其计算复杂度与模式数量成线性关系,这使其具有处理大规模数据的可能。k均值方法本质上是一种选代的方法,当数据不能一次全部读入内存时,则需和磁盘进行多次数据交换,并且这种交换相应于迭代次数要反复多次,这无疑需要花费大量的I/O时间。     

一种基于聚类的语义检索算法

潜在语义分析在进行大规模语义检索时计算效率较低、存储开销较大。针对该问题,提出一种基于聚类的潜在语义检索算法。通过文档之间的结构关系对文档进行聚类,利用簇代替文档分析潜在语义,以此减少处理文档的个数。实验结果表明,该算法能减少查询时间,且检索精确度较高。     

一种层次化的检索结果聚类方法

检索结果聚类能够帮助用户快速地浏览搜索引擎返回的结果.传统的聚类方法由于不能生成有意义的类别标签因此是不适合的,为了改善检索结果层次化聚类的效果,采用了基于标签的聚类算法,提出了将DF、查询日志、查询词上下文特征融合的类别标签抽取算法,并以抽取的标签构造基础类别图,通过GBCA算法构建层次化聚类结果.实验证明了多特征融合模型的有效性;GBCA算法在类别标签抽取和F-Measure两个评价指标上都比STC和Snaket算法有很大的提高.     

一种基于关键词的微博话题聚类算法

由于微博跟现实生活有着密不可分的联系,微博的话题聚类可以发掘人们所关注的话题,有利于引导公众舆情。由于传统的文本聚类方法主要适用于长文本,LDA(Latent Dirichlet Allocation)话题模型是一个比较成熟也比较全面的话题聚类方法,实验中利用LDA模型来发掘当前公众讨论的热点话题,提出一种文本关联词算法。利用LDA得到的关键词进行聚类分析,也可以对LDA话题聚类后的结果进行优化调整,得到的结果与标注数据集进行对比分析,实验结果证明该算法能够提高聚类的正确率、召回率和F值。     

一种协同的FCPM模糊聚类算法

比重隶属度模糊聚类(FCPM)算法可从不同角度解决聚类问题,取得较好效果。协同聚类算法利用不同特征子集之间的协同关系,并与其它聚类算法相结合,可提高原有的聚类性能。文中在FCPM聚类算法的基础上进行改进,将其与协同聚类算法相结合,提出一种协同的FCPM聚类算法。该算法在原有FCPM聚类算法的基础上,提高对数据集的聚类效果。在对数据集Wine和Iris进行测试的结果表明,该方法优于FCPM算法,说明该方法的有效性。     

一种基于数据流的软子空间聚类算法

针对高维数据的聚类研究表明,样本在不同数据簇往往与某些特定的数据特征子集相对应.因此,子空间聚类技术越来越受到关注.然而,现有的软子空间聚类算法都是基于批处理技术的聚类算法,不能很好地应用于高维数据流或大规模数据的聚类研究中.为此,利用模糊可扩展聚类框架,与熵加权软子空间聚类算法相结合,提出了一种有效的熵加权流数据软子空间聚类算法——EWSSC(entropy-weighting streaming subspace clustering).该算法不仅保留了传统软子空间聚类算法的特性,而且利用了模糊可扩展聚类策略,将软子空间聚类算法应用于流数据的聚类分析中.实验结果表明,EWSSC 算法对于高维数据流可以得到与批处理软子空间聚类方法近似一致的实验结果.     

一种改进K-means算法的聚类算法CARDBK

CARDBK聚类算法与批K-means算法的不同之处在于,每个点不是只归属于一个簇,而是同时影响多个簇的质心值,一个点影响某一个簇的质心值的程度取决于该点与其它离该点更近的簇的质心之间的距离值。 从聚类结果的熵、纯度、F1值、Rand Index和NMI等5个性能指标值来看,与多个不同算法在多个不同数据集上分别聚类相比, 该算法具有较好的聚类结果;与多个不同算法在同一数据集上很多不同的初始化条件下分别聚类相比,该算法具有较好且稳定的聚类结果;该算法在不同大小数据集上聚类时具有线性伸缩性且速度较快。     

一种区域型模糊聚类算法

使用支撑集和模糊待分集的概念来描述数据集的分布,在此基础上提出了一种区域型模糊聚类算法———re-gionalfuzzyclusteringalgorithm。仿真结果表明该算法有比常用的模糊C均值更好的聚类性能。     

一种基于空间映射及尺度变换的聚类框架

传统聚类算法通常建立在显式的模型之上,很少考虑泛化模型以适应不同的数据,由此导致了模型不匹配问题。针对此问题,该文提出了一种基于空间映射(Mapping)及尺度变换(Rescaling)的聚类框架(简称M-R框架)。具体而言,M-R框架首先将语料映射到一组具有良好区分度的方向所构建的坐标系中,以统计各个簇的分布特性,然后根据这些分布特性对各个坐标轴进行尺度变换,以归一化语料中各个类簇的分布。如上两步操作伴随算法迭代执行,直至算法收敛。该文将M-R框架应用到K-means算法及谱聚类算法上以验证其性能,在国际标准评测语料上的实验表明,应用了M-R框架的K-means及谱聚类在所有语料集上获得了全面的性能提升。     

基于自适应蚁群的FCM聚类优化算法研究

模糊C均值聚类算法在算法初始化时需要人为设定聚类类别数、随机初始化聚类中心,致使该算法容易陷入局部最优值.为解决此类问题,在蚁群算法中引入信息素更新机制,使其输出的聚类中心更具全局优化的特征和较强鲁棒性的特点;用蚁群算法得到的聚类中心来初始化FCM算法的聚类中心,解决了FCM算法对初始聚类中心敏感的问题;使用结合熵信息与数据几何结构的聚类有效性评价方法对FCM算法和优化FCM算法进行评价,评价结果表明优化的FCM算法性能更优.在仿真实验中,利用提出的优化算法和FCM算法对自然图像、纹理图像和SAR图像进行分割实验,从图像分割的准确性和算法的实时性做对比实验,验证了优化算法的有效性.     

基于EM算法的文本聚类优化研究

针对现有的文本聚类算法难以取得满意结果的问题，以EM算法为基础，提出能分别描述相似、不相似聚类对的相似性分布以及重要、不重要文档的重要性分布的文本聚类优化模型（text clustering optimization model, TCOM）．基于该模型，设计一种通过合并不同的文本聚类结果以获取最优性能的方法．实验结果表明，利用该方法同时改善了聚类精度和召回率，其性能优于单独使用现有的硬、软聚类算法．     

基于COSA算法的中文文本聚类

传统聚类算法在计算两个对象间的距离时,每个属性对距离的贡献相同。COSA(Clustering On Subsets of Attributes)算法^[1]认为在不同的分组中,每个属性对计算距离所起的作用可能并不相等,因为不同分组中的对象可能在不同的属性子集上聚集。文献[1]在此基础上定义了新的距离,并提出了两种COSA算法: COSA1算法是一种分割的聚类算法;COSA2算法是一种层次聚类算法。为了对比COSA距离和传统的欧氏距离在文本聚类中的表现,本文对中文文本进行了分割聚类和层次聚类的实验。实验结果显示出COSA算法较基于欧氏距离的聚类算法有更好的性能,而且对于属性数的变化,COSA算法更加稳定。     

基于局部搜索机制的K-Means聚类算法

K-Means聚类算法的结果质量依赖于初始聚类中心的选择。该文将局部搜索的思想引入K-Means算法,提出一种改进的KMLS算法。该算法对K-Means收敛后的结果使用局部搜索来使其跳出局部极值点,进而再次迭代求优。同时对局部搜索的结果使用K-Means算法使其尽快到达一个局部极值点。理论分析证明了算法的可行性和有效性,而在标准文本集上的文本聚类实验表明,相对于传统的K-Means算法,该算法改进了聚类结果的质量。     

位置加权文本聚类算法

文本聚类是自然语言处理研究中一项重要研究课题,文本聚类技术广泛地应用于信息检索、Web挖掘和数字图书馆等领域。本文针对特征词在文档中的不同位置对文档的贡献大小不同,提出了基于特征词的位置加权文本聚类改进算法——TCABPW。通过选取反映文档主题的前L个高权值的特征项构造新的文本特征向量,采用层次聚类和K-means文本聚类相结合的改进算法实现文本聚类。实验结果表明,提出的改进算法在不影响聚类质量的情况下大大地降低了文本聚类的维度,在稳定性和纯度上都有显著提高,获得了较好的聚类效果。     

基于蚁群算法的文本聚类算法

针对目前文本检索后的相关反馈信息较少用于文本聚类中的问题,根据蚂蚁觅食聚类算法的思想,将文本检索后的相关反馈信息应用到文本聚类过程中,提出一种基于蚁群算法的文本聚类算法。分析簇的结构及其生成过程,论述聚类中簇合并的规则及算法。实验结果表明,该算法具有良好的聚类效果,能有效提高查询的文本召回率。     

基于模糊聚类的文本挖掘算法

针对传统FCM算法对孤立点比较敏感,须预先指定聚类数目的缺陷,提出一种新的模糊聚类算法NSFCM,将其应用干文本挖掘中。NSFCM对数据对象的隶属度增加一个权值,以减少孤立点对聚类中心的影响。采用平均信息熵确定聚类数,通过密度函数获得初始聚类中心。仿真结果证明,该算法聚类的精度和执行效率均高于FCM算法,效果较好。     

基于混合并行遗传算法的文本聚类研究

针对传统K-Means聚类算法对初始聚类中心的选择敏感,易陷入局部最优解的问题,提出一种基于混合并行遗传算法的文本聚类方法。该方法首先将文档集合表示成向量空间模型,并在文档向量中随机选择初始聚类中心形成染色体,然后结合K-Means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现。实验表明该算法相对于K-Means算法、简单遗传算法等文本聚类方法具有更高的精确度和全局寻优能力。     

一种实用高效的聚类算法

在信息处理研究领域,现有的大多数聚类算法都需要人为地给出一些参数.然而,在没有先验知识的情况下,人为地确定这些参数是十分困难的,而且现有的聚类算法的时空效率也有待于进一步提高.为了解决这一难题,首先根据样本分布特性,通过数学分析,得到确定样本空间划分间隔数的数学函数,然后,再根据样本分布特性,采用爬山的策略得到样本类的划分,最后提出了一种实用而高效的聚类算法.从多个角度分析了该算法的性能,并将该算法应用于中文文本聚类.理论分析和应用结果都表明,该算法不仅不需要人为确定参数,同时,还可以提高信息处理的时空效率和性能.     

基于移动Agent的WSN多层分簇算法

针对无线传感网分簇中每轮节点能耗不均衡的问题,提出一种基于移动Agent的多层分簇(MABMC)算法.构建多层分簇能量模型,采用移动Agent技术选举每轮簇头并收集数据.仿真实验结果表明,与能量有效的多层分簇算法和低功耗自适应集簇分层型算法相比,该算法可减少网络每层轮数的能耗,提高能耗均衡度,延长网络生命周期.     

基于最优适值保留的蚁群文本聚类算法

蚁群聚类最早是由Deneubourg提出的一种仿生聚类方法,在聚类分析中得到广泛应用。本文在该算法的基础上提出一种基于精英适值保留的蚁群聚类算法,在一般蚁群聚类算法中引入精英保留机制,在每次算法的迭代中保留一定数量的优良解进入到下一次的循环中,以期提高算法的性能。为了验证算法的有效性,本文选择了两个数据集:数值数据集(iris)和一个文本数据集,用两个外部评价指标进行评判。实验结果表明,新算法的性能能够得到有效提高。