文章编号:1001-9081(2008)03-0757-04
基于遗传算法和自组织特征映射网络的文本聚类方法
覃 晓
1,2
,元昌安
1
(1.广西师范学院信息技术系,南宁530001; 2.广西师范学院数学与计算机科学系,南宁530001)
(qhyihui@163.com )
摘 要:自组织映射(S OM )算法作为一种聚类和高维可视化的无监督学习算法,为进行中文W eb 文档聚类提供
了有力的手段。但是S OM 算法天然存在着对网络初始权值敏感的缺陷,从而影响聚类质量。为此,引进遗传算法对S OM 网络加以优化。提出了以遗传算法优化S OM 网络的文本聚类算法(GSTC A );进行了对比实验,实验表明,改进后的算法GSTC A 比S OM 算法在W eb 中文文档聚类中具有更高的准确率,其F 2measure 值平均提高了14%,同时,实验还表明,GSTC A 算法对网络初始权值是不敏感的,从而提高了算法的稳定性。
关键词:自组织特征映射;遗传算法;文本聚类中图分类号:TP311 文献标志码:A
Text cluster i n g m ethod ba sed on geneti c a lgor ithm and S OM network
Q IN Xiao
1,2
,Y UAN Chang 2an
1
(1.D epart m ent of Infor m ation Technology,Guangxi Teachers Education U niversity,N anning Guangxi 530001,China ;
2.D epart m ent of M athe m atics and Co m puter Science,Guangxi Teachers Education U niversity,N anning Guangxi 530001,China )
Abstract:A s a cluster of high 2di m ensi onal visualizati on and unsupervised learning algorith m,Self 2O rganizing M ap (S OM )p r ovided a favorable means for Chinese W eb clustering .However,the S OM algorith m has a natural fla w of being sensitive t o the net w ork initial power value s o as that the accuracy of the cluster made by the S OM has been influenced .T o s olve the p r oble m,this paper app lied genetic algorith m t o op ti m ize S OM.This paper made the f oll owing contributi ons .1)Pr opose a text clustering method based on G A 2S OM 2based Text Clustering A lgorith m s (GSTC A );2)Make comparis on ex peri m ent .The result of the experi m ent shows that the GST CA has higher accuracy rate than S OM algorith m in the W eb Chinese Docu ment Clustering,and the average value of F measure is i m p r oved by 14.5%than traditi onal method .The ex peri m ents als o show that GSTC A is not sensitive t o initial weights of the net w ork,thereby enhancing the stability of the algorith m.
Key words:Self 2O rganizingM ap (S OM );Genetic A lgorith m (G A );text cluster
0 引言
随着I nternet 的普及和应用,网络已经成为人们工作、生活中的重要组成部分,各种搜索引擎也成为人们用以检索所需资源的不可或缺的工具。但是,网上的搜索引擎动辄返回成千上万条相关的检索结果,即使得到了一些有用的信息,也常常混有大量的“噪声”,给用户造成了时间和金钱的浪费。因此,为了高效、经济地检索到与给定的查询请求相关的、数目恰当的资源子集,就必须进行文本聚类,文本聚类成为数据挖掘中一个重要而又热点的研究领域之一。
文档聚类不同于文档分类,后者对于每个类别事先已经有了类别标注,而文档聚类则事先没有类别标注,根据文档内容进行聚类,将文档集合分成若干个簇,要求簇内文档内容的相似性尽可能大,而属于不同簇的文档内容的相似性尽可能小。它既可对W eb 文档进行有效地组织,还可形成分类模板用来指导W eb 文档分类。因此,文档聚类可以对网上信息根据内容进行聚类,以方便我们检索和阅读。
用于文本聚类的方法有很多,其中较典型的方法是近年来学者们提出的用自组织特征映射(Self 2O rganizing M ap,
S OM )神经网络进行文本聚类。S OM 网络模型的基本思想
是:把高维的信息数据以有序方式映射到低维空间上,形成一种有拓扑意义上的有序图[1]。但是,S OM 作为一种无导师学习方法现在发展还不成熟,还存在一定的局限性,如网络连接权的初始状态、算法中的参数选择对网络的收敛性能有较大影响等[2]。对此本文采用将遗传算法引进S OM 算法中,提出
基于遗传算法优化的S OM 网络文本聚类方法(G A 2S OM 2
based Text Clustering A lgorith m s,GSTC A ),对其连接权值及参
数进行优化,提高S OM 用于文本聚类中的聚类质量。实验表明,应用本文提出的改进算法,在文本聚类效果上,GSTC A 较
S OM 具有较高的准确度。
1 S OM 训练算法
神经网络方法中用于聚类的方法主要是S OM 神经网络,它是由文献[1,3]首先提出,并被随后加以研究[4-7]的一种无导师自组织和自学习网络。与其他聚类方法相比,S OM 网络的优点在于:可以实现实时学习,网络具有自稳定性,无需外界给出评价函数,能够识别向量空间中最有意义的特征,抗噪声能力强。这些特点将有利于中文W eb 文档的聚类。
第28卷第3期
2008年3月
计算机应用
Computer App licati ons
Vol .28No .3Mar .2008
S OM 网络由输入层和竞争层组成,输入层由N 个输入神经元
组成,竞争层由M 个输出神经元组成。输入层各神经元与竞争层各神经元之间实现全互连接。如图1所示
。
图1 S OM 网络结构
S OM 算法的聚类功能主要通过以下两个简单规则来实
现
[6]
:
1)对于提供给网络的任一个输入向量X ,确定相应的输
出层获胜神经元i (X )。其中:
i (X )=arg m in ‖X -W j ‖;j =1,2,…,l
(1)2)确定获胜神经元s 的一个邻域范围N s,N s 一般由邻域函数确定。本文的邻域函数采用Gaussian 函数.其形式如下:
h j ,i =
exp (
-|d (j ,i )|
2
2
σ2),
d (j ,i )≤σ0,
d (j ,i )>σ
(2)
其中:d (j ,i )为i 和j 之间在离散空间的欧氏距离,σ是随迭代
次数的增加而减少的方差。
按式(3)调整N s 范围内神经元的权向量:
d (W j )
d (t )
=η(t )・h j ,i (t )(X -W j )
(3)
其中,η(t )为随时间t 减小的参数,表示学习效率。该调整过程使得N s 内神经元的权向量朝着输入向量X 的方向靠拢。
随着学习的不断进行,学习率η(t )将不断减小,邻域N s 也将不断缩小,所有权向量将在输入向量空间相互分离,各自代表输入空间的一类模式,这就是Kohonen 网络特征自动识别的聚类功能。
从S OM 算法的聚类原理可知:该算法主要是通过不断缩小获胜神经元的邻域来达到聚类的目的。而考查获胜神经元的邻域是对离散空间两点j ,i 的距离的梯度近似。这种近似往往不能保证两点间的距离达到最小,因此聚类的效果不佳。为此,本文引进遗传算法对获胜神经元的邻域进行直接优化,提出基于遗传算法优化的S OM 网络文本聚类方法(GST CA )。
2 GSTCA 算法
如前所述,S OM 的启发式训练算法作为一种无导师学习存在着网络连接权的初始状态、算法中的参数选择对网络的收敛性能有较大影响的缺陷。而遗传算法(Genetic A lgorith m,G A )是借鉴生物的自然选择和遗传进化机制而产生的一种全局优化自适应概率搜索算法,其搜索过程从本质上属于随机搜索算法,但其空间便利性比传统的启发式搜索好,遗传操作使得路径可随机跳跃至不同的子空间,从而在全局空间中以若干搜索集方式从时序过程方面逼近全集[8]。遗传算法作为一种全局优化搜索算法为解决上述缺陷提供了一个有效的途径。本文将用遗传算法直接对该S OM 的网络连接权值进行优化,形成基于遗传算法的S OM 算法(GST CA ),对比S OM 基本算法,将可以得到较高的文本聚类准确率,提高文本聚类的质量。
遗传算法一般操作步骤为:1)种群初始化。由于染色体代表的是S OM 网络权值,故染色体采用实数编码。假设训练样本输入向量的维数为N ,则
选择N 个0～1的随机数作为初始网络权值,并组成染色体,染色体的长度为M ×N ,M 为输出神经元的个数。反复执行该步得到X 个染色体。
2)计算每一条染色体的适应度。在本算法中,记适应度最大的染色体为W max ,W max 对应着一个较好的聚集中心。由于是要对获胜神经元邻域近似进行优化,所以距离越小,染色体的适应度应该最大。从上文可知,领域函数反映了神经元之间的亲近关系,并且,神经元i 和j 的距离越小,h j ,i 就越大,故本
文将适应度函数定义为:
fitness =
∑M
j =1
h
c,j
;c 为获胜神经元(4)
3)交叉操作。将染色体群体中的个体随机两两配对,采
用双点交叉算子进行交叉操作,产生新一代群体。
4)变异操作。变异操作是遗传算法种群多样性的保证。在本算法中,由于染色体对应S OM 的网络权值,因此采用位置变异算子,以较小的概率对新一代种群进行变异操作。
基于遗传算法和S OM 网络的文本聚类算法介绍如下:算法 GSTC A 算法
输入:待聚类的文本
输出:反映文本聚类情况的S OM 网络1) Iinitial N et w ork (S OMNet );
//初始化S OM 网络
2)I nitial pop (W );//种群初始化
do {
3)输入文本向量;
4)求输入向量的获胜节点;
5)用公式(4)计算每条染色体的适应度6)求适应度最大的染色体W max ;
7)以W max 对获胜节点进行直接更新;8)调整获胜节点邻域内的节点权值;9)染色体交叉操作;10)染色体变异操作;
11)返回3),直到所有文本向量处理完毕;12)}while (达到最大迭代次数或网络权值收敛)13)
输出S OMNet;
3 实验与讨论
本实验分别用S OM 算法和GSTCA 算法对相同的数据集进行了聚类实验。实验中将每个文本用N 个坐标的输入向量表示,如果文本中有相应的词语则此处坐标为1,否则为0;输入向量在时刻t 到所有输出节点的距离为:
d j =
∑N -1
i =0
(x
i
(t )-w ij (t ))2
(5)
w ij (t )为代表输出神经元节点的权向量,x i (t )是输入向量在
时刻t 的值。
为了便于对实验结果进行评价,我们从新浪网上下载了教育类、体育类、环境类、经济类、计算机类共550篇新闻W eb 文档,将其中的350篇用来训练网络,剩下的200篇用作测试。
实验中训练样本文档经过预处理,去掉文档中的非文本信息,如图形、图形中的文字等;然后经主题词提取(其中包含对同义词的处理),生成维数为182的输入模式向量。
GSTC A 参数选取是:染色体数量size =20,交叉概率P c =0.5,变异概率P m =0.05,S OM 采用8×8网络,η的初始值为0.3。设置算法的最大迭代次数为2万次,一个文本可以多次
提交给系统。实验采用的程序设计语言为VC ++6.0。
定义1 查准率。对于一个聚类i 和一个分类j ,假设N 1为在聚类i 中属于分类j 的数目,N 2为聚类i 中所有对象的数
857 计算机应用第28卷
目,则i 和j 的查准率P 定义为:
P (i,j )=N 1/N 2
(6)
定义2 查全率。对于一个聚类i 和一个分类j ,假设N 1
为在聚类i 中属于分类j 的数目,N 3为分类j 中所有对象的数目,则i 和j 的查全率R 定义为:
R (i,j )=N 1/N 3
(7)查准率P 衡量的是所有被聚类i 分到类别j 的文档中,正确文档的比率;查全率R 衡量的是所有实际属于类别j 的文档被聚类i 分到该类别中的比率。查准率和查全率是两个相互对立的衡量指标,一般情况下,查准率会随着查全率的升高而降低,两者很难兼得。所以很多情况下需要将它们综合在一
起考虑。最常用的综合方法就是F 2测量(F 2Measure )[9]
,定义如下:
定义3 F 2测量。假设一个聚类i 和一个分类j 的查准率和查全率分别是P 和R,则分类j 的F 定义为:
F (j
)
=2PR
P +R
(8)
对聚类i 而言,哪个分类的F 2measure 值高,就认为聚类i 是代表该分类的映射。对于聚类结果,其总的F 2measure 为每个分类的F 2measure 加权平均得到:
F =
∑j
(|j |・F (j ))
∑j
|j |
(9)
其中|j |表示分类j 中所有对象的数目。
表1是用S OM 算法和GSTC A 算法对测试文档集各自进行10次实验的总F 2measure 值。
在以上实验基础上,通过改变学习率η可以看到,η的衰
减速度越大,则邻域函数收缩就越快,这虽然使得S OM 算法的收敛速度加快,但也造成了某些具有更好聚集性质的权向量被跳过,因而聚类质量粗糙。而遗传算法具有在全局搜索最好解的性质,它可以弥补S OM 陷入局部聚点的缺陷,因此,在η学习步长较大时,也能获得较好的聚类质量;η的衰减变慢,邻域函数收缩也放慢,S OM 算法能发现较好的聚集中心,聚类质量有所提高,但迭代次数却大幅增长,算法收敛速度太慢,效率降低。但由于使用了遗传算法对S OM 网络的权值进行了优化,所以选择小的学习率η时,GSTCA 算法的迭代次数变化不大。图2表明,当η小于一定值时,S OM 和GSTCA 算法在聚类质量上都没有太大改变,这与中文文档的特征词选择及文档聚类的特点有关。GSTC A 算法与S OM 算法比较,在聚类质量和算法效率上都有一定程度的改善。
表1 两种聚类方法的总F 2measure 值
序号
采用S OM 算法
采用GST CA 算法
10.5180.66520.5210.70830.5690.70440.5810.950.5090.69860.5490.68570.5660.70180.5140.68490.5760.69710
0.5960.702平均
0.546
0.686
表2 不同η下两种算法的迭代次数和聚类质量比较
算法
η/6
平均F 2measure 值迭代
次数
η/3
平均F 2measure 值迭代次数
η
平均F 2measure 值迭代
次数
2
η平均F 2measure 值迭代
次数
3
η平均
F 2measure 值迭代
次数
S OM 0.552193650.551109810.542630.13327470.019607GSTCA
0.703
2853
0.695
2819
0.686
2630
0.33
1029
0.192
520
图2 两种算法的效率和聚类质量比较
为了比较两种聚类算法对随机选取的初始网络权值的敏感程度,本文考查了S O M 算法的局部权重失真指数(Locally
Weighted D ist orti on I ndex,L WD I )[1]
。S O M 算法的L WD I 定义为:
LWD I =E
(∑M
j =1
h
cj
(t )‖x -w j ‖
)
(10)
其中E 表示数学期望,X 为输入向量,W j 为第j 个神经元网络权值,c 为相对于输入向量X 的获胜神经元,h cj (t )为邻域函数。
LWD I 是衡量S OM 网络拓扑结构质量的重要指标。在S OM 文本聚类算法中,L WD I 刻画了聚类中心随迭代次数的分布情况。如果在算法运行过程中,L WD I 随迭代过程呈现的波动大,说明网络的随机初始值对算法的收敛性造成影响大;L WD I 波动小,则说明算法稳定性好,算法对随机初始值
敏感程度小。
为了便于比较两种算法的LWD I 值随迭代次数的变化情况,我们引入L WD I 平均波动值的概念:
定义4 L WD I 平均波动值。记L WD I 平均波动值为AL,则:
AL =
∑N
i =1
|LWD I
i+1
-LWD I i |
N
(11)
其中,N 为采集LWD I 值的次数。LWD I 平均波动值表明,一个
算法的AL 值越大,说明其对随机初始值越敏感。
表3两种算法的LWD I 平均波动值比较序号
采用S OM 算法
采用GST CA 算法
10.0630.02120.0510.03430.0710.0240.0440.03250.0610.01960.0680.02970.0560.02580.0420.02790.0670.02110
0.062
0.019
957第3期覃晓等:基于遗传算法和自组织特征映射网络的文本聚类方法
图3是10次实验中,分别对两种算法在不同迭代次数进行7次采集LWD I 值后所得的AL 值的比较
。
图3 两种聚类算法的LWD I 平均波动值比较
从以上实验结果可以看出,使用GSTC A 算法之后,文本
聚类的F 2mesure 值比使用S OM 算法进行聚类平均提高了14个百分点。这说明用遗传算法对文本聚类的S OM 网络加以优化之后,能够更准确的找到聚类中心,从而提高了聚类的质量。图2和图3反映了S OM 算法对随机初始权值和参数敏感的缺点,说明了GSTC A 比S OM 具有更好的算法稳定性。
4 结语
针对S OM 算法本身固有的对网络初始权值敏感的缺陷,采用遗传算法对S OM 网络初始权值加以优化,在优化过程中又对获胜神经元进行直接更新,与基本S OM 算法相比,GSTC A 能够发现更好的聚类中心,从而能够明显地改善文档聚类的质量。实验表明,GST CA 算法比S OM 算法具有更好的聚类效果和更好的算法稳定性。在今后的工作中,我们将致力于研究将最新智能算法———基因表达式编程[10]引入到S OM 算法的改进中,并在实验中加以利用,进一步促进文本聚类质量的提高。
参考文献:
[1] K OHONEN T.The self 2organizing map s [J ].Pr oceedings of the
I EEE,1990,78(9):14-1480.
[2] 杨占华,杨燕.S OM 神经网络算法的研究与进展[J ].计算机工
程,2006,16(8):201-202.
[3] K OHONEN T .Self 2organized f or mati on of t opol ogically correct fea 2
ture map s[J ].B i ol ogical Cybernetics,1982,43(1):59-69.[4] FR I TZKEB.Gr owing self 2organizing net w orks 2hist ory ,status quo ,
and pers pectives [C ]//Kohonen map s .Am sterda m:Elservier,
1999:131-144.
[5] FR I TZKE B.Gr owing cell structure 2a self 2organizing net w ork for un 2
supervised and supervised learing [J ].Neural Net w orks,1994,7(9):1441-1460.
[6] FR I TZKE B.Let it gr ow 2self 2organizing feature map swith p r oblem
dependent structure[C ]//A rtificial Neural Net w orks .Am sterda m:Elservier,1991:403-408.
[7] K OHONEN T .Self 2organizing and ass ociative memory[M ].Heidel 2
berg:Sp ringer,1984.
[8] 王小平,曹立名.遗传算法[M ].西安:西安交通大学出版社,
2005:93.
[9] AY AD H,K AMEL M.Top ic discovery fr om text using aggregati on of
different clustering methods[C ]//Pr oceedings of the 15th Confer 2ence of the Canadian Society for Computati onal Studies of I ntelli 2gence on Advances in A rtificial I ntelligence,LNCS 2338.London:Sp ringer 2Verlag,2002:161-175.
[10]Y UAN C,T ANG C,W EN Y,et al .Convergency of genetic regres 2
si on in data m ining based on gene exp ressi on p r ogramm ing and op ti 2m ized s oluti on[J ].I nternati onal Journal of Computers and App lica 2ti ons,2006,28(4):359-366.
(上接第756页)
SC ALER +算法是对S CALER 算法的改进,是一种基于序列匹配的高效X ML 分支查询求解算法。SC ALER +继承了
SCALER 的所有优点,比如整体地处理分支查询而不需要将
分支查询分解为从根到叶的多个路径,再比如它产生的
UDFTS 序列和OSI 索引的空间复杂度在最坏情况下都是线
性的。进一步地,在不牺牲算法性能的前提下,SC ALER +明确地实现了对通配符3和后代轴//的支持,并且实现了兄弟节点无序的模式树的查询。这两个方面的改进,大大扩充了算法处理的问题的范围,使得算法基本上能够高效处理所有类型的X ML 分支查询求解问题,这对于一个完善的X ML 求解算法是至关重要的一点。
下一步将继续优化改进SC ALER +算法,使它具有更好的性能。并与其他优秀分支查询算法(如T wig Join )进行比较,探讨效率更高、处理能力更强的算法。参考文献:
[1] 冯建华.纯X ML 数据库的查询求解关键问题研究[D ].北京:
清华大学,2006.
[2] G OLDMAN R,W I D OM J.App r oxi m ate DataGuides[C ]//Pr oceed 2
ings of the Workshop on Query Pr ocessing f or Se m istructured Data and Non 2standard For mats .Jerusale m,Israel:I EEE Press,1999:436-445.
[3] M I L O T,S UC I U D.I ndex structures for path exp ressi ons[C ]//Pr o 2
ceeding of the 7th I nternati onal Conference on Database Theory,
LNCS 1540.London:Sp ringer 2Verlag,1999:277-295.
[4] K AUSH I K R,SHEONY P,BOHANNON P,et al .Exp l oiting l ocal
si m ilarity for efficient indexing of paths in graph structured Data [C ]//Pr oceedings of the 18th I nternati onal Conference on Data En 2gineering .W ashingt on,DC:I EEE Computer Society,2002:129-140.
[5] AB I TEBOUL S,BUNE MAN P,S UC I U D.Data on the W eb:Fr om
relati ons t o se m istructured data and X ML [M ].San Francisco:Mor 2gan Kauf mann Publishers,1999.
[6] A I 2KHAL I F A S,JAG AD I SH H V.Structural j oins:a p ri m itive for
efficient X ML query pattern matching[C ]//Pr oceedings of the 18th I nternati onal Conference on Data Engineering .San Jose,California:I EEE Press,2002:141-152.
[7] ZHANG CHUN,NAUGHT ON J,DE W I TT D,et al .On supporting
containment queries in relati onal database manage ment syste m s[J ].AC M SI G MOD Record,2001,30(2):425-436.
[8] RAO P,MOON B.PR I X:I ndexing and querying X ML using p r üfer
sequences[C ]//Pr oceedings of the 20th I nternati onal Conference on Data Engineering .Bost on,Massachusetts:I EEE Press,2004:288-300.
[9] WANG HA I 2XUN,P ARK S,F AN W E I,Y U P S .V iST:a dyna m ic
index method for querying X ML data by tree structures[C ]//Pr o 2ceedings of the AC M SI G MOD I nternati onal Conference on Manage 2ment of Data .San D iego,California:AC M Press,2003:110-121.
067 计算机应用
第28卷下载本文
