《基于NMF的文本聚类方法》由会员分享，可在线阅读，更多相关《基于NMF的文本聚类方法（3页珍藏版）》请在金锄头文库上搜索。
1、第3 0 卷V o L 3 0第1 1 期11b 1 1计算机工程Co mp u t e r En g i n e e r i n g2 0 0 4 年6 月J u n e 2 0 0 4 人工智能及识别技术 文寒 偏 号.10 0 0 - 3 4 2 8 ( 2 0 0 4 ) 1 1 - 0 1 1 3 - 0 2文 臼 标权 码: A中.分类号 : T P I S基于N MF 的文本聚类方法黄钥 石，防建江.t张 亚霏( 解放军理工大学通信工 程学院，南京2 1 0 0 0 7 ; 2东南大学计算机科学与工程系，南京2 1 0 0 9 6 ) 摘 要:提出一种基 非负矩阵分解的文本聚类方
2、法。该方法利用 N MF 分解项一 文本矩阵来降低特征空间维数， 并得到文本向量在概念空间 上的表示，在此基础上应用聚类算法。实验表明，基于N MF 的文本聚类方法能够提高文本聚类精度。 关健侧: 文本聚类;非负矩阵分解;球形的k -均值算法;自 然语言处理 T e x t C l u s t e r i n g Me t h o d B a s e d o n N o n - n e g a t iv e Ma t r i x F a c t o r iz a t i o nH U A N G G a n g s h i , L U J i a n j i a n g , Z H A N G
3、 Y a f e i ( C o lle g e o f C o m m u n ic a ti o n a n d E n g in e e r i n g , U n i v e rs ity o f S c ie n c e a n d T e c h n o lo g y , P L A , N a n j i n g 2 10 0 0 7 ;2 . D e p a r tm e n t o f C o m p u te r S c ie n c e a n d E n g in e e r i n g , S o u th e a s t U n iv e r s it y , N
4、a n j in g 2 1 0 0 9 6 ) A b s t r a c t A n e w te x t c l u s t e r in g a p p r o a c h b a s e d o n n o n - n e g a t iv e m a t r ix fa c to r iza ti o n is p re s e n te d . T h e m e th o d a p p lie s n o n - n e g a t iv e m a tr ix f a c to ri za t io n to d i m e n s io n a li ty r e d u
5、 c t io n o f t h e t e r m s p a c e , re p r e s e n ts o r ig i n a l te x t v e c t o rs in n e w c o n c e p t s p a c e a n d c lu s t e r s it w ith c lu s te ri n g a lg o r it h mT h e r e s u lts o f e x p e r i m e n t s h o w t h a t t h e a lg o r it h m c a n imp r o v e t h e c lu s t
6、e r i n g p r e c i s io n( K e y w o r d s T e x t c l u s t e r in g ; N o n - n e g a t iv e m a tr ix fa c to r iza tio n ; S p h e r ic a l k - m e a n s a lg o r it h m ; N a t u ra l la n g u a g e p ro c e s s in g随着互联网络的发展，We b 上的文本资源呈现爆炸式增 长。 这些文本信息数据量大、内容繁杂而且处于不断变化之 中， 如何充分有效地利用丰富的文本资源成为人
7、们关往的焦 点。聚类分析作为数据挖掘的一种重要手段，在文本挖掘中 扮演着非常重要的角色。现有的文本聚类方法大多基于文本向量之间的相似度， 常见的基于相似度的聚类方法有k - 均值聚类算i1 i n 、分层聚 类算沼11和球形的 k - 均值算沼2 1。这些算法用于文本聚类时， 选择出现在文本中的一组词作为属性( 或特征项) ，然后将每 个文本表示成属性上的一个多维向量。通常文本向量是高维 的 稀疏向 量， 如何在 高维稀疏向 量之间定义有效的相似度是 一件非 常困 难的事7 。另 外，这些聚类算法假设词的出 现是 独立的，即词与词之间线性无关，这与自然语言中词存在的“ 斜交”现象相互矛盾，也影
8、响了聚类精度。本文 采 用 非 负矩 阵分 解 ( N o n - n e g a t i v e M a t r i x F a c t o r iz a t i o n , N M F ) “ 算 法 分 解 词 一 文 本 矩 阵， 即 用 N M F 算 法 对词一 文本矩阵进行预处理。运用NMF 算法，一方面降低词- 文本矩阵的维数，滤除噪声特征项，为聚类算法选择一组有 效文本特征参与相似度计算，另一方面，N MF 通过矩阵近 似 卡 获取同义词之间的关联，将文本向量转换成概念空间上 的表示。 1 词一 文本矩阵中 文文本中词与词之间没有明显的 切分标志， 首先需对 文本进行分词处理
9、。文本分词后可以通过计算每个词在语料 库中的词频进行粗略的特征提取，方法是依据Z i p 肤 则删除 一些频率很高与很低的词。这些词对聚类作用不大或者是没 有实际意义的功能词。设这一步处理后得到词集合为 D = t t ， 二 ，, t ,) 。然后根据词集D 对文本数字化。文本数字化即 把文 本表 示成词上的一个m维稀疏向量，向 量的 分量是词的权重， 词t 在 文 本x 上 的 权 重 记 为7f i d f ( xt t ) ，tf id j ( x , , t , ) =# ( x t j) lo g dn，其中# ( X , t i ) 表示词 ， 在文本x , 中出现的次数，d表示
10、文本集中包含词r ; 的文本数量。 通常将文本向量表示为单位向量，即L - 模为1 的向量，因此需对权重进 行 余 弦 正 规 化 处 理: w w l =功 刃( x r ; ) I -， ，、 、 :。设有n 个V 山二 . V J l - x , ; 1 1文本，正规化后得到 n 个m维稀疏向量( 记为x i , x , ,、 戈 ， )， 这 n 个m维 稀 疏 向 量 组 成 一 个 词 一文本 矩阵X= ( x殊， 。 X即为常用文本聚类算法中的输入数据。 2 非负矩阵分解给 定 一 个 词 一 文 本 矩 阵X = ( X , ), N M F 寻 找 一 个 m x r 非 负
11、 矩 阵U= ( u u ) . ， 和一个r x n 非 负 矩 阵V = ( V . 从 。 ，满足X d U P ( 1)其中， r 满足( n + m ) r v r c ,“ i , l _ Q 刀y = l d j ( 4 )下列迭代算法可以得到以式( 3 ) 为目标函数的 式(4 ) 问题 的一 个局部最优解” :c1+ 】一 尚 一 “y kl 。 ， 。 艺 x ;, r 夺 下1山1 u ;l v 尸艺xu呼 - . t ,y . L , U I N 艺、 、 +- _ uk,Y U,3 球形的 卜 均值算摺6 1非负 矩阵 分解近似地将x中的每个文本向量x i 投影 到v
12、 中的Y 维列向量V i , J =1, . . . , n。向量吟在一个新的 低维概念空间中，因此为定义一种有效的向量之间的相似度提供 了可能。我们用各种聚类算法对v 中的 列向 量进行聚类。这 里主要介绍球形的鑫均值算法。首先对 v中列向量进行余弦正规化处理其 中 ， m 尸是二 夕 +1)的 中 心 向 量 ( 4 ) 给定6,是任意小的实数，如果回 二 黔 t. ) 一 Q( 味 :+珠 . 习 、 : 则算法停止 a实脸分析从 h tt p :/ / w w w . s i n a .c o m .c n 体育 竟 技 风 暴 专 栏中 选 取 体 操 ( 2 4 1 ) ,羽毛球(
13、 2 1 0 ) ,乒乓球( 2 7 0 ) 、排球( 2 0 0 ) 、赛 车( 1 5 5 ) . 游泳( 3 2 6 ) 、网球( 2 7 4 ) ,棒球( 1 6 0 ) ,冰氰2 8 6 ) 、田 径( 3 0 2 ) , 共1 0 个主题2 4 2 4 篇体育类新闻文本。首先对文本集进行预处理，将所有文本标上主题类别标 签， 并对文本分 词;根据停用词( s t o p w o r d ) 表，除去 停用 词 ( 或虚词);根据 Z ip F 法则， 除去高频词 和低频词。将每个主题的文本分成3 份，进行3 轮计算。每轮从1 0 个 主题中 各选I 份混合在一起，根据余弦正 规化的
14、T F I D F 权重 公式建立文本集的项一 文本矩阵丫 ，分别用k - 均值聚类算法、 球形的k - 均值算法、N MF + k - 均值聚类算法、N MF + 球形的k - 均值算法聚类。每一轮计算后，先计算每个类的聚类精度， 其定义为 1_ j 些 垫 竺 竺 些 塑 竺 x Itxwi然后根据3 轮计算结果， 计算总平均， 见表1 。本类 中 实际 文 本数 得到每个类的平均聚类精度，最后 、 v.班.班类早均箱度定义1 给定两个r维向 量v和v ， ， v和v i 的 相似性定 义为两个向量的内积v r v ， 一 艺v 1, x v ,算 法卜 均 值球形的 卜 均值N M F
15、+ k -均值( - 15 0 )N M F + 球形的 k - 均 值( r -I 5 0 )总 平 均0. 7 60 . 810. 810 . 8 6给 定。 个向 量v i - (v., v z j +二 .， ， ， 二 ， 是” 个向量的一个划分。厅 中向量的中心向量为v , ) ， j = 1 ， 一， n。 设对每个固定的I S j k 时， k 个隐含概念被 进一步地细分成更低层次的子概念， 弱化了 N M F 算法对相 同语义词的关联作用。因此用N MF 算法改善聚类精度时需 要选择适当的r 值。fN MF + k - m e a n s N M F + s p h e d
16、c a lk-m aa s l|卜卜日口“盯“5一望。几巴巴9，哎印1 0 0 1 5 0 2 0 0 2 5 0 9 0 0 3 5 0r圈1 N MF + 琅类葬法的平均粗度5结论聚类分析作为一种数据挖掘的重要手段，在文本挖掘中也扮演着非常重要的 角色。本文提出 一种基于N MF 的文本聚类方 法。 该方法采用N M F 分解词一 文本矩阵来降 低词一 文本矩阵的维数，滤除噪声特征项，从而为定义一种有效的相似度提供可能;另外，NMF 通过矩阵近似来获取同义词之间的关联，将文本向量转换成概念空间上的表示。实验表明，基于 N MF 的 文本聚类方法具有好的 精度。 参考文橄I J a i n A K , D u b e s R C . A lg o r ith m s f o r C lu s te r in g
