K均值算法是聚类分析中使用最为广泛的算法之一。针对文本聚类所面临的维数灾难,稀疏向量以及标准K均值算法初始中心点选择的随机性等问题,提出了一种面向文本聚类的改进的K均值算法,通过运用特征选择及降维、稀疏向量筛除、基于密度及散布的初始中心点搜索等方法进行改进。实验结果表明,改进后的算法无论在聚类精度还是在稳定性等方面,都明显优于标准的K均值算法。
维普资讯 doc.guandang.net
第2 6卷 20 0 6年 6月 文章编号: 0— 0 1 2 0 ) 6 0 7 0 1 1 9 8 ( 06 0 Z一 0 3— 3 0 一
计算机应用 Co u e mp t rApp iai n l to s c
Vo .2 1 6
J n 0 6 u e2 0
种用于文本聚类的改进的 K均值算法 任江涛,婧昊,潇潇,焕宇,孙施黄印 (sr@ m i ss .d . n i j s t a .yu eu a ) l
鉴
(中山大学计算机科学系,东广州 507 )广 12 5 摘要: K均值算法是聚类分析中使用最为广泛的算法之一。针对文本聚类所面临的维数灾难,稀疏向量以及标准 K均值算法初始中心点选择的随机性等问题,出了一种面向文本聚类的改进的 K均提
值算法,通过运用特征选择及降维、稀疏向量筛除、基于密度及散布的初始中心点搜索等方法进行改进。 实验结果表明,改进后的算法无论在聚类精度还是在稳定性等方面,明显优于标准的 K均值算法。都 关键词:文本聚类;特征选择;始化初中图分类号: P 1 .3 T 1文献标识码: T 3 1 1;P 8 A s是接近 0的一个值,:。 s是接近 1的一个值。也即是说,
0引言 聚类分析在数据挖掘、式识别、策支持、模决机器学习等领域有广泛的应用,最重要的数据分析方法之一。它将数是
词t要么在 D中极少的文本中出现,么在 D中绝大多数的文要本中出现,这些词对文本的区分不会产生太大的作用,反而会 影响到聚类的效果,以进行文本的特征选取,所找到能最好的
据对象分为不同的集合,得同一集合中的数据对象相对来使说有更大的相似性,同一集合里的对象相对来说有更大而不 的差别。
区分文本的词的集合。文使用来作为特征选取度量。本该度量方法是给每个文本中的每个词一个权重,权重的计算 如下:  ̄a(,)=t d f dt f,)×lg n ( o 研 l
文本聚类是一个有着广泛应用领域的研究问题。目前流 行的文本聚类方法主要有基于划分的方法 ( K M as为以— en
() 1
代表)及层次化聚类方法等。由于 K均值算法简单易行, 因此是文本聚类中广泛采用的方法之一,由于 K均值算法但初始中心选择的随机性,使得其运行结果不稳定,且易
于陷入 局部极小点。同时,文本聚类问题本身也有其特殊性。一方面,文本向量是高维向量,一般为上千甚至上万维;另外,文本向量通常为稀疏向量,含有较多的 0这也为聚类中心的选择,带来困难。
其中, dt , )是词 t在文本 d中的词频, () D中包含 d t是 f词t的所有文本的数目, n是文本集合 D的大小。 在文本聚类中,常使用向量空间模型来表示每个文通 本,在这种模型中,每个文本 d被认为是向量空间内的一个
向量。在这里,我们使用了一i d f词权重模型,每个文本就则 被表示为: < lg∥ d,, lg n )…,.o (/f )> ( ) o ( f ) o (/, t 1g n d. f 2
针对上述问题,本文一方面采用了一种高效的特征评价指标,进行特征的过滤和筛选,对文本向量进行降维;另一方面,出了一种新的基于密度及散布特性的初始中心点选提择算法, K— as对 Men算法进行改进,较好地解决了初始点的选择的影响以及聚类结果不平衡等问题。
其中是文本中的第个词的频度,是包含第 个词的文本的数目。 此外,为了解决文本的长度不同的问题,每个文本向量的模都被标准化为 1设:。 d=< t lg∥ d,, lg∥ )…, f o( f )。 (,, t 1g n d.> f o (/f ) . () 3
1文本的向量空间模型及相似度定义 文本聚类可以描述如下:一个给定的文本集合 D=对
则标准化之后,表示为: d =
{。d,,} d,… d经过聚类, E 最终得到一个集合 C={。:…, e,, e c}其中 c c D(, i=12,,)使得 Vd(∈ D) c c,… k, d, j ( C )有 d c, ,同时使得目标函数, C ( )达到最小。 1 1文本的向量空间模型 .
lg n )。(/ 、
+.+而 .
’’ ㈩
 ̄( l/,)/ o( + gnd) f l o g> …+ ̄( (,)/ ∥d ) n 于是有 I I I d I=1。 12 .相似度定义
文本集合 D的特征空间就是出现在该文本集合中的所有的词的集合,表示为 r o={ IVt d Vd D}通常文本集 t , 。合 D都具有相
当的规模,因此是非常大的,这其中会包括 这样的一些词, rqec ()表示词 t用feuny t出现在整个文本集合
本文使用欧氏距离[ 1度量文本之间的相似度。设文本 d,∈D, i 则: ds( )= i d, t n一 l l 7 I+…+ ‘+ 1 2 2一 I一 I () 5
中的频度。则有: feuny t s或feu ny t r ec ()≤ l rq ec ()≥ s q 2 收稿日期:o 5一l 2o 2—1;订日期:o 6— 2— 8 4修 2 o 0 2
基金项目:国家自然科学基金 (0 7 0 7; 6 5 3 9 )广东省自然科学基金(4 0 4 20 2 0 0 ) 03 0 6, 0 3 2 5
作者简介:任江涛 (95,, 17一)男广西柳州人,讲师,博士,主要研究方向:数据挖掘与知识发现、生物信息学;孙婧吴 (93。, 18一)女河南许昌人,硕士研究生,主要研究方向:高维数据挖掘及特征选择、信息处理和电子商务;施潇潇 (95一,,东阳江人, 18 )男广主要研究方向:数据挖掘与知识发现;黄焕宇 (90,, 18一)男广东湛江人,硕士研究生,主要研究方向:信息处理和数据挖掘;印鉴 (98,。 16一)男湖北武汉人,教授, 博士,主要研究方向:人工智能、数据挖掘与数据仓库 .

一种用于文本聚类的改进二分K-均值算法_专业资料。在已有聚类算法的基础上,提出了一种新的文本聚类新方法——合作二分K-均值算法(简称CBKM)。该算法以K-均值...
摘 : K均值算法是聚类分析中使用最为广泛的算法之一。针对文本聚类所面临的维数灾难 ,稀要 疏向量以及标准 K均值算法初始中心点选择的随机性等问题 ,提出了一种...
一种用于文本聚类的改进k-means算法_专业资料。k-means是目前常用的文本聚类算法,针对其最终搜索的局部极值与全局最优解偏差较大的缺点,采用一种基于局部搜索优化...
一种改进的K均值聚类算法_专业资料。针对传统K均值算法中采取的欧氏距离计算... 一种用于文本聚类的改进... 27人阅读 4页 2.00 基于遗传算法的一种...
一种改进的K均值聚类算法_专业资料。K均值算法是聚类方法中常用的一种划分方法... 一种用于文本聚类的改进... 26人阅读 4页 2.00 基于遗传算法的一种...
数据挖掘报告 姓名:朱晓康班级: 086121 学号: 20121002250 指导老师:蒋良孝 改进的 K 均值聚类算法摘要:K-means 算法以其简单性和快速性在文本聚类中得到广泛应用,...
一种改进的k-均值聚类算法_专业资料。针对k-均值(k-means)聚类算法中随机... 一种用于文本聚类的改进... 20人阅读 3页 2.002014 Baidu 使用...
一种改进的K-均值聚类算法的研究_专业资料。聚类分析在科研和商业应用中都有着... 一种用于文本聚类的改进... 20人阅读 3页 2.00 改进的K均值聚类红外...
一种改进的K-均值聚类算法的研究_专业资料。聚类分祈在科研和商业应用中都有... 一种用于文本聚类的改进... 14人阅读 3页 2.00 改进的K均值聚类红外...
一种改进的K均值聚类算法_信息与通信_工程科技_专业资料。k均值的改进算法,很... 一种用于文本聚类的改进... 暂无评价 4页 2.00 基于遗传算法的一种...
热门文档