（计算机软件与理论专业论文）文本聚类中参数自动设置技术的研究与实现.pdf

东北大学硕士学位论文摘要 文本聚类中参数自 动设置技术的研究与实现 摘要 随着数据库中和网络上文本资源、 w e b页面的激增，人们需要对大量的 文本 资源进行有效的组织，以有利于信息检索、模式发现、为用户提供推荐服务，以 及为进一步的文本分类提供模式基础。于是，文本聚类技术应运而生。 文本聚类， 即将给定的文本集合划分为多个簇，从而达到簇内文本的主题相关性，簇间文本 的主题无关性的目的。 文本聚类中首先需对文本进行预处理， 将非格式化的文本转化为格式化数据， 再使用经典的聚类算法进行聚类。目 前主要的文本聚类算法有基于划分的算法， 典型的如k - m e a n s 和k - me d o i d s 算法; 基于层次的聚类算法，典型的如h a c( 凝 聚的层次聚类算法) ; 基于神经元网络的算法， 如s o ms ( 自 组织映射网络) ;以及 基于模型的聚类算法。上述算法各有其优缺点，其中大多数算法都需要用户输入 关键参数、即闽值 ( 如k - me a n s . k - me d o i d s . s o ms 和模型方法) ， 而无需参数输 入的算法则时间效率过于低下 ( 如h a c ) 。 为解决文本聚类中的参数设置问题， 本 文提出并实现了支持典型文本聚类算法中参数自动设置的算法。 首先，在特征选取方面，本文提出了 “ 最大序列频繁词组”的概念，并通过 挖掘最大序列频繁词组获取文本特征，以克服最常用的t f i d f方法忽略了词与词 之间关系的缺点，使抽取的特征表示文本内容的准确程度大大提高。 在使用k - m e a n s 进行文本聚类的研究中，针对k - m e a n s 算法在文本聚类中的 缺点，本文提出了利用对多次取样聚类以确定参数 k的方法，使得参数确定过程 自 动化;同时在 k - me a n s 方法中引入了衰减因子，在划分过程中动态地改变簇均 值，以提高聚类质量。 为了克服k - m e a n s 方法对孤立点敏感性的缺点，并进一步提高聚类的质量和 时间效率，本文将基于密度的聚类算法应用于文本对象之上。在基于密度的文本 聚类算法中， 提出了 一种利用曲 线拟合自 动确定参数的方法，利用自 动参数确定 技术，对簇进行收缩以得到细化簇。 实验表明，参数自 动设置技术使文本聚类过程更加自 动化，同时提高了 文本 聚类的质量和效率，产生了更好的聚类结果。 【 关键字】 :数据挖掘、文本聚类、特征选取、参数确定自 动化 东 北大学 硕士学 位论文 s t u d y a n d l m p le m e n t a t i o n of a u t o m a t ic t a r a m e t e r s e t t in g f o r d o c u m e n t c l u s t e r i n g ab s t r a c t wi t h t h e i n c r e a s i n g o f d o c u m e n t r e s o u r c e s in m u l t i m e d i a d a t a b a s e a n d w e b , p r o c e s s i n g d o c u m e n t s b y h a n d n o l o n g e r m a t c h e s t h e i n c r e a s i n g s p e e d a n d m e e t s p e o p l e s r e q u i r e m e n t s . wh a t p e o p l e n e e d i s o r g a n i z i n g d o c u m e n t s i n a n e ff e c t i v e f o r m , f o r t h e c o n v e n i e n c e o f i n f o r m a t i o n r e t r i e v e , p a tt e r n d i s c o v e r y a n d r e c o m m e n d a t i o n , a n d a l s o f o r t h e p u r p o s e o f p r e p a r i n g f o r c a t e g o r i z i n g t h e n e w c o m i n g d o c u m e n t s . a n d t h e n c o m e s t h e d o c u m e n t c l u s t e r i n g t e c h n i q u e s . d o c u m e n t c l u s t e r i n g i s t o s e p a r a t e t h e d o c u m e n t s e t i n t o g r o u p s , i n e a c h g r o u p t h e d o c u m e n t s a r e o f t h e s a m e o r r e l a t e d t o p i c . t h e p u r p o s e o f d o c u m e n t c l u s t e r i n g i s t o g e n e r a t e t h e c l u s t e r s i n w h i c h d o c u m e n t s a r e o f t h e m o s t t o p i c - r e l a t e d , a n d b e tw e e n w h i c h d o c u m e n t s a r e o f t h e m o s t t o p i c - u n r e l a t e d . t h e wo r k s h a v e b e e n d o n e a r e t o t r a n s f o r m t h e u n s t r u c t u r e d d o c u me n t s i n t o t h e s t r u c tu r e d d a t a o b j e c t , t h e n a p p l y t h e c l a s s i c a l c l u s t e r i n g a l g o r i t h m s t o t h e m . t h e d o c u m e n t c l u s t e r in g a l g o r it h m s m a i n l y u s e d a r e p a rt i t i o n i n g m e t h o d , s u c h a s k - me a n s a n d k - m e d o i d s , h i e r a r c h i c a l m e t h o d s u c h a s h i e r a r c h i c a l a g g l o m e r a t i v e c l u s t e r i n g ( h a c ) , n e u r a l n e t w o r k b a s e d m e t h o d s u c h a s s e l f - o r g a n i z i n g ma p ( s o m) , a n d m o d e l - b a s e d c l u s t e r in g a l g o r i t h m . a ll o f t h e s e a l g o r i t h m s h a v e t h e ir d i s a d v a n t a g e s , s o m e o f t h e m n e e d t h e i n p u t p a r a m e t e r s t h a t a r e d i ff i c u l t t o s e t b y u s e r s , a n d s o m e o f t h e m h a v e t o o l o w t i m e e ff ic i e n c y . t h e c o n c e p t m a x im a l s e q u e n t i a l f r e q u e n t p h r a s e ( ms f p ) i s p r o p o s e d i n t h i s t h e s i s f i r s t . c o n t r a r y t o t h e n e g l e c t o f t h e r e l a t i o n s h i p b e t w e e n t e r m s i n t f i d f m e t h o d , m s f p t a k e s t h e r e l a t i o n s h i p i n t o a c c o u n t , a n d g u a r a n t e e s th e o r d e r s b e t w e e n t e r m s . t h i s m e t h o d c a n o b t a in t h e b e t t e r q u a l i t y in t e r m s e l e c t i o n , p r e p a r i n g f o r t h e c l u s t e r i n g i n n e x t s t e p . t h i s t h e s i s s t u d i e s t h e m e t h o d s t o s e t t h e i n p u t p a r a m e t e r s i n d o c u m e n t c l u s t e r i n g a l g o r i t h m a u t o m a t ic a l l y . f o r k - me a n s a l g o r i t h m , a m e th o d t h a t d e t e r m i n e s th e i n p u t p a r a m e t e r k b y m u l t i - s a m p l i n g i s p r o p o s e d . a l s o s c a l a r f a c t o r c o m in g f r o m s o m i s i n t r o d u c e d i n t o t h e c l u s t e r i n g p r o c e s s , a l t e r i n g t h e m e a n v a l u e i n e a c h c l u s t e r d u r i n g t h e s e p a r a t i n g s t e p i n k - me a n s . t h e s e t w o i m p r o v e m e n t s i n d u c e t h e k - me a n s a l g o r i t h m 川. 东 北大学 硕士学 位论文 r e q u i r i n g n o i n p u t p a r a m e t e r a n d g o o d r e s u l t p e r f o r m a n c e . t o e l im i n a t e t h e s e n s i t i v i t y t o o u t li e r s i n k - me a n s a n d t o i m p r o v e t h e c l u s t e r i n g e ff ic i e n c y a n d p e r f o r m a n c e f u r th e r m o r e , d e n s i t y - b a s e d c l u s t e r in g a l g o r i t h m i s a p p li e d t o d o c u m e n t c l u s t e r i n g i n t h i s t h e s i s . f o r t h i s p u r p o s e , o n e n o v e l m e t h o d d e t e r m i n in g t h e p a r a m e te r s b y m u l t i n o m i a l f i t i s p r o p o s e d . a n d w i t h t h e h e l p o f a u t o m a t i c p a r a m e t e r s s e t t i n g m e t h o d , t h e c lu s t e r i s c o n t r a c t e d s t e p b y s t e p , g e n e r a t i n g f i n e c l u s t e r f i n a l l y . e x p e r i m e n t s s h o w t h a t t h e a u t o m a t i c p a r a m e t e r s e t t i n g i n d o c u m e n t c l u s t e r i n g g e n e r a t e s m o r e s a t i s f i e d c l u s t e ri n g r e s u l t a n d i m p r o v e s t h e c l u s t e r i n g e f fi c i e n c y . ( k e y w o r d s 7: d a t a m i n i n g , d o c u m e n t c l u s t e r i n g , t e r m s e l e c t i o n , a u to m a t ic p a r a m e t e r s e t t i n g 4 v。 东北大学硕士学位论文独创性声明 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 但 夯 学位论文作者签名: 日期:五斌夕/ 学位论文版权使用授权书 本学位论文作者和指导教师完全了 解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同意。 ) 学位论文作者签名 签 字日 期 :2 0 0 s : 0位 . 1 . 1 夕 导师签名: 签字日期: 补昨 ) 右 刃 了、 / . r 东北大学 硕士学 位论文第一章 前言 第一章 前言 1 . 1数据挖掘和文本挖掘 我们现在己 经生活在一个相当数字化的时代中，通信、计算机和网络技术正 极大地影响着整个人类社会。 然而海量信息既给人们带来方便，也带来了许多问 题，使我们在惊叹信息爆炸的同时又不得不面对知识贫乏的苦恼:信息过量难以 消化、信息真假难以 辨别、信息安全难以 保证、信息形式相异难以统一处理。人 们开始考虑: “ 如何才能不被信息淹没，而是从中及时发现有用的知识、提高信 息利用率?， 。 面对这一挑战，数据挖掘技术应运而生，并得到长足的发展，显 示出了强大的生命力。 数据挖掘( d a t a m i n i n g ) 简称d m， 也称为数据库中的知识发现 ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e , k d d ) ， 是近年来随着数据库和人工智能发展 起来的一门 新 兴的数据库技术。它是一个众多学科诸如人工智能、机器学习、模式识别、统计 学、数据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有 广阔前景的领域。其处理对象是大量的日常业务数据，目的是从大量的、不完全 的、有噪声的、模糊的、随机的原始数据中提取隐含在其中的、事先未知的、但 又是潜在有用的信息和知识。 数据挖掘的挖掘对象不仅仅局限于数据库中的数据记录，而是可以应用于诸 如空间数据、音频、视频、数据流、文本等各种数据对象之上的。 随着网络上w e b页面的激增，以及文本数据库对各种形式文本统一管理和存 储，仅仅依靠手工来对这些文本资源进行处理是不可能的。人们迫切需要由计算 机自 动地对这些大规模的文本集合进行有效的处理和分析，其中包括分类、聚类、 自 动摘要等等。 于是，针对于文本的数据挖掘方法应运而生。相对于传统数据挖掘算法所针 对的关系的、 事务的和数据仓库的数据， 文本挖掘面对的是由来自 各种数据源 ( 如 新闻文章、研究论文、书籍、数字图书馆、电子邮件消息和we b 页面)的大量的 文档集合。与传统的挖掘算法所处理的数据对象不同，文本挖掘所处理的是半结 构化的或者是非结构化的数据。 半结构化的数据如we b 页面、 x ml 文档等， 它们 中可能包含结构字段，如标题、作者、出版日 期、长度、分类等，也可能包括大 量的非结构化的文本成分，如摘要和内容。相对于结构化数据，半结构化和非结 构化数据上的数据挖掘面临着更大的挑战，同时，也具有非常广阔的应用前景。 东北大学硕士学位论文第一章 前言 1 .2文本聚类及其应用 1 .2 . 1文本聚类的定义及分类 在诸多的文本挖掘方法中， 文本主要探讨的是聚类问 题。 所谓聚类就是将物 理的 或者抽象的对象集合分组成为由 类似的对象组成的多个簇的过程。由 聚类所 形成的簇是多个对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇 内的对象相异。 而文本聚类的目的也是得到这样的一些文本簇，使得文本之间具 有最大的簇内相似性( 主题相关性) ， 同时具有最小的簇间相似性( 主题无关性) 。 定义 1 .1 :文本聚类 ( d o c u m e n t c lu s te ri n g )是对一个给定的文本集合 d - dd z ， 一 ， d o 进行划分， 从而得到一个簇的集合c = c 1 , c z , . . . , c a ， 其中 c , c d ( j 一 1 ,2 , - - - , k ) ， 使 得 对 d d , ( d ; e d ) , 3 c j ( c j e c ) 且 d ; e c i ， 同 时 使 得 代 价 函数f ( c ) 达到 最小。 从定 义1 . 1 来看， 对于一 个文 本对象d , ， 并没 有规定 其所 属的 簇的 数目 ， 一 个 文本对象既可以仅仅属于一个簇，也可以属于多个簇。依据这样的聚类结果，可 以 把 聚 类 算 法 划 分 为 两 类 r o s 9 8 : 如 果 每 个 对 象d 、 在 聚 类 结 果 中 只 属 于 一 个 簇。 ， ， 即 p ( d j e c d = 1 , 那 么称 这 种 聚 类为 硬聚 类c h a r d c l u s te r i n g ) ; 如 果 每 个 对象d , 以 一 定 的 概 率 属 于 某 些 簇 ， 即 p (d ; e c j ) c o m b i n , c o m b i n i n g - c o m b i n , c o m b in e s - c o m b i n , c o m b i n a t io n - c o m b i n , c o m b i n a t i v e - c o m b i n ，经过如此处理， 文本中的相关词意得到了集中，有利于相似度的计算和模型参数的估计。 2 . 1 . 3停用词处理 无论在汉语还是在英语中，都存在一些对文本内容识别意义不大的词，在文 本 挖掘中 ， 称之为s t o p w o r d( 停用词) 。 这些 词没有 什么意义， 而 且在各类文 本 中出现的频率都很高，在计算相似度或者训练模型求参数的过程中会引入很大的 误差，可以看作是一种噪音。最简单的例子是汉语中 “ 的”这个字，以及英语中 o f ” 这个词。 他们没有具体的意义， 不能体现文本所表示的内容， 但在几乎所有 的文本中都会出现，如果在聚类过程中考虑到这些词，那么文本之间的相似性不 能表现出内容的相似性，而是一些无意义的相似性，这不是我们所希望的。 在 本 文的 实际 应用中， 定义中 文的s t o p w o r d 的 集合为“ 的了 是 在有我个他 就 这粉上说和也你到里来都还把去又若要很能十么” ， 这些词的挑选是根据他们在各 种文本中出现的频率而给出的。 英文文本中， 本文使用 h t t p : / / w w w .d c s . g l a .a c .u k / i d o m / i r - r e s o u r c e s / l i n g u i s t ic - u ti l s / s to p we w o r d s 所 提 供的 一 个s t o p w o r d 的 列 表。 该 列 表包 括3 1 9 个 诸 如 “ a t , a n d 单词。 2 . 1 .4特征选取 文本经过上面几步的处理后， 得到一个词空间t。 特征选取的目的就是得到一 个t c t ， 使t 中的词能最大地体现各个文本之间的 相异性， 减少他们之间的共性。 东 北大学 硕士学 位论文第二章 文本聚类过 程 同一个单词有不同的变形，比如单词 “ c o m b i n e ，它有分词形式 “ c o m b i n e d ， 动 名词形式“ c o m b i n i n g ， 第三人称单数形式“ c o m b i n e s ，以 及名词形容词形式 c o m b in a t io n , c o m b in a t iv e ” 等 等 . 某 一 单 词 的 各 种 形 式 都 有 可 能 在 某 一 文 本 中出现，如果把各种变形作为不同的词来看待，无论在相似度的计算中， 还是在 参数估计中，势必会影响聚类的质量。 所以，对各种时态语态的英文单词，需要对其进行词千还原的处理，以使得 文本内容更加明确集中，以保证聚类质量。 各 种 文 献中 经 常 采 用的 ， 也 是 在 本文 中 采 用的s t e m m in g 方 法， 是s tu a rt j . b a r r 提出的p o rt e r 方法 s a n 0 4 。 该方法利用英文单词中的一些普遍规则进行词干还原。 例如还原后缀 b i l i t i ”为 “ b l e ”等等。单词 ， c o m b i n e 各种变形经过p o rt e r 进行 s t e m m i n g 后 的 结 果 如 下 :c o m b i n e d - c o m b i n , c o m b i n i n g - c o m b i n , c o m b in e s - c o m b i n , c o m b i n a t io n - c o m b i n , c o m b i n a t i v e - c o m b i n ，经过如此处理， 文本中的相关词意得到了集中，有利于相似度的计算和模型参数的估计。 2 . 1 . 3停用词处理 无论在汉语还是在英语中，都存在一些对文本内容识别意义不大的词，在文 本 挖掘中 ， 称之为s t o p w o r d( 停用词) 。 这些 词没有 什么意义， 而 且在各类文 本 中出现的频率都很高，在计算相似度或者训练模型求参数的过程中会引入很大的 误差，可以看作是一种噪音。最简单的例子是汉语中 “ 的”这个字，以及英语中 o f ” 这个词。 他们没有具体的意义， 不能体现文本所表示的内容， 但在几乎所有 的文本中都会出现，如果在聚类过程中考虑到这些词，那么文本之间的相似性不 能表现出内容的相似性，而是一些无意义的相似性，这不是我们所希望的。 在 本 文的 实际 应用中， 定义中 文的s t o p w o r d 的 集合为“ 的了 是 在有我个他 就 这粉上说和也你到里来都还把去又若要很能十么” ， 这些词的挑选是根据他们在各 种文本中出现的频率而给出的。 英文文本中， 本文使用 h t t p : / / w w w .d c s . g l a .a c .u k / i d o m / i r - r e s o u r c e s / l i n g u i s t ic - u ti l s / s to p we w o r d s 所 提 供的 一 个s t o p w o r d 的 列 表。 该 列 表包 括3 1 9 个 诸 如 “ a t , a n d 单词。 2 . 1 .4特征选取 文本经过上面几步的处理后， 得到一个词空间t。 特征选取的目的就是得到一 个t c t ， 使t 中的词能最大地体现各个文本之间的 相异性， 减少他们之间的共性。 东 北大学 硕士学 位论文第二章 文本聚类过 程 同一个单词有不同的变形，比如单词 “ c o m b i n e ，它有分词形式 “ c o m b i n e d ， 动 名词形式“ c o m b i n i n g ， 第三人称单数形式“ c o m b i n e s ，以 及名词形容词形式 c o m b in a t io n , c o m b in a t iv e ” 等 等 . 某 一 单 词 的 各 种 形 式 都 有 可 能 在 某 一 文 本 中出现，如果把各种变形作为不同的词来看待，无论在相似度的计算中， 还是在 参数估计中，势必会影响聚类的质量。 所以，对各种时态语态的英文单词，需要对其进行词千还原的处理，以使得 文本内容更加明确集中，以保证聚类质量。 各 种 文 献中 经 常 采 用的 ， 也 是 在 本文 中 采 用的s t e m m in g 方 法， 是s tu a rt j . b a r r 提出的p o rt e r 方法 s a n 0 4 。 该方法利用英文单词中的一些普遍规则进行词干还原。 例如还原后缀 b i l i t i ”为 “ b l e ”等等。单词 ， c o m b i n e 各种变形经过p o rt e r 进行 s t e m m i n g 后 的 结 果 如 下 :c o m b i n e d - c o m b i n , c o m b i n i n g - c o m b i n , c o m b in e s - c o m b i n , c o m b i n a t io n - c o m b i n , c o m b i n a t i v e - c o m b i n ，经过如此处理， 文本中的相关词意得到了集中，有利于相似度的计算和模型参数的估计。 2 . 1 . 3停用词处理 无论在汉语还是在英语中，都存在一些对文本内容识别意义不大的词，在文 本 挖掘中 ， 称之为s t o p w o r d( 停用词) 。 这些 词没有 什么意义， 而 且在各类文 本 中出现的频率都很高，在计算相似度或者训练模型求参数的过程中会引入很大的 误差，可以看作是一种噪音。最简单的例子是汉语中 “ 的”这个字，以及英语中 o f ” 这个词。 他们没有具体的意义， 不能体现文本所表示的内容， 但在几乎所有 的文本中都会出现，如果在聚类过程中考虑到这些词，那么文本之间的相似性不 能表现出内容的相似性，而是一些无意义的相似性，这不是我们所希望的。 在 本 文的 实际 应用中， 定义中 文的s t o p w o r d 的 集合为“ 的了 是 在有我个他 就 这粉上说和也你到里来都还把去又若要很能十么” ， 这些词的挑选是根据他们在各 种文本中出现的频率而给出的。 英文文本中， 本文使用 h t t p : / / w w w .d c s . g l a .a c .u k / i d o m / i r - r e s o u r c e s / l i n g u i s t ic - u ti l s / s to p we w o r d s 所 提 供的 一 个s t o p w o r d 的 列 表。 该 列 表包 括3 1 9 个 诸 如 “ a t , a n d 单词。 2 . 1 .4特征选取 文本经过上面几步的处理后， 得到一个词空间t。 特征选取的目的就是得到一 个t c t ， 使t 中的词能最大地体现各个文本之间的 相异性， 减少他们之间的共性。 东 北大学硕士学位论文第二章 文本聚类过程 特征选取的方法也可以分为两类:一类是在单一文本中进行特征选取，也称 为关键字提取，就是从单一文本中提取出最能体现出该文本内容的词;另一类是 在文本集合中进行特征选取，使得提取出来的词不仅能体现各个文本的内容，而 且能很好的区分各文本之间的不同。本章主要讨论的是在文本集合中进行特征选 取的方法，关于第一种方法，在第三章有详细的讨论。 2 . 1 . 4 . 1 t f i df t f i d f ( t e r m f r e q u e n c y i n v e r s e d o c u m e n t f r e q u e n c y ) 方 法 是应 用的 最为 广 泛 的在文本集合中进行特征选取的方法 h s 0 2 和 k m m0 0 。它依据某个词的词频 ( t e r m fr e q u e n c y ) 和 其出 现 过的 文 本的 频 率( d o c u m e n t fr e q u e n c y ) 来 计算 该词 在 整个文本集合中的权重，依据权重来进行特征选取的。权重越高，说明该词对文 本的区分能力越强，否则其区分能力则越弱。 对于一词t 和某一文本d 来说，t 在d 中 权重的计算公式如( 2 . 1 ) : tf idf (d ,t) = 1f (d ,t) x lo g (其) a ll ) ( 2 . 1 ) 其 中tf ( d , t ) 是 词t 在文 本d 中出 现的 数目 ， d f ( t ) 是 词t 在文 本集合 中出 现过的 文 本 的 数 目 ， 剑 是 整 个 文 本 集 合 中 文 本 的 数目 。 如 果 一 个 词 在 整 个 文 本 集 合 中 出 现 的 频 度很 高， 上 式的 右半 部趋于 零， 从 而使得tf i d f 值很小， 即该词区 分能力比 较 弱。 根 据上面的 描 述， 可以 根据tf i d f 值从大到小选择用户指定数目 的 词作为某篇文本 的特征，生成文本的特征向量。 2 . 1 .4 . 2潜在语义索引( l a t e n t s e m a n t i c i n d e x i n g , l s i ) 一般的文本之间的相似度仅仅是考虑到词的字面意义，然而，间接的证据促 使我们在两个没有共同词的文档中建立语义联系。 举例来说， c a r 和a u t o 在某文档 中共现使我们相信他们是相关的。 这将帮助我们把提到c a r 和g e a r b o x 的文档和提 到a u t o 和t r a n s m i s s i o n 的 另一 个文档 联系 起来。 d d f 9 0 和 y u 0 3 - b 中 提出 用l s i 用线性代数的 概念把这种直觉形式化。 给定 ， 个 词 和。 篇 文 本， 可以 构 建 词 一 文 本 矩 阵a = ( a , ) ,， 其 中 词r 在 文 本d ， 中 不 出 现 时a 。 二 0 , 反 之a ; = i ( 当 然 也 可以 用 词 频 或 者护 刃 ， 作 为 权重 ) 。 如 果 词“ c a r 和 “ a u t o ” 相关， 则期望他们在相似的文档集合中出现。因此，与这些单词对应的 行就会有某种程度的相似性。将这种直觉扩展，我们猜想a可能有比它的维数少 很多的秩r ，很多行和/ 或列可能是冗余的。 东北大学硕士学位论文第二幸 文本聚类过程 胡(z2) 设 a 的 奇 异 值 ( 即 矩 阵 m r 的 特 征 值 ) 是 。 j + o a , , o , ， 且 o f 卜 二 a ， 卜 奇异值分 解( s i n g u l a r v a l u e d e c o m p o s i t i o n , s v d ) 将a 分解为3 个矩阵 id v t : “ 一 u d v t 一 万 u ; a ; v t 其中 d s d ia g ( o . . . . . . a , ) 为 对 角 矩阵 ， u 和v 是 列正 交 矩阵。 l s i 只 保 存 最大 的 k ( 可 调 参 数 ) 个 奇 异 值 及u , v 中 对 应 的 k 列 ， 使 得认几 可- a . u 的 每 一 行 将 一 个 词表 示 成为 一 个k 维向 量， 同 理v k 的 每一行也 将一 个文本表示成 一个k 维向 量。 经 过s v d方法，词空间的维度得到了降低，达到了特征挑选的目的。 2 . 1 5背景知识的应用 前面已经提到过，文本聚类中一个很大的挑战就是对文本的处理不能根据其 潜在的语义关系来发现文本内容的相似性，而仅仅是根据其字面关系，一个例子 就是“ a u t o ” 和“ c a r 。 字面上二 者完 全 不相关， 但是 在语义层 面上， 二者 指的 是 同一事物。这种局限大大的影响了文本聚类的质量。 背景知识就是用来克服上述问题的。根据以各种形式给定的背景知识，在不 同字面意义上的词之间发现其语义上的联系，提高对文本内容的识别。目 前主要 的 方 法 是以 h m s 0 1 和w m a b 0 3 中 使 用的 本 体( o n to lo g y ) ， 或 者 是 s t b p 0 2 中 的 概念格 ( c o n c e p t l a t t i c e s ) 来作为背景知识，用于文本的预处理阶段。 定义 2 . 1 :本体是一个二元组o :一 ( c , !s c ) ，其中c是概念描述符 ( c o n c e p t i d e n t if ie r ) 的 集 合; 。 是c 上的 偏 序 关系 ， 称 之为 概 念 层次 或 者 概 念 分 类( c o n c e p t h i e r a r c h y o r t a x o n o m y ) . 定 义2 .2 : 本 体o 的 字典 是 一 个二 元 组l e x 一 ( s c , r e f , ) ， 其中 集合s 。 中 的 元 素 称为 概 念 标 志( s i g n f o r c o n c e p t ) ， 关 系r e f c c s c x c 称 之为 概 念的 字 典 参 考( l e x ic a l r e f e r e n c e f o r c o n c e p t s ) ， 其中( c , c ) e e r e f c 对所 有的c e c n s 。 都 成 立。 一般来说，应用背景知识都需要一个本体作为支持。针对不同的问题，可以 使用一些特殊领域的本体，或者是一个普遍的本体。目前应用的最为广泛的本体 是w o r d n e t ， 它 由 本 体 和 字 典 组 成， 在w o r d n e t 中 ， 函 数r e f , 把 那 些 在 他 们 对 应 概念间存在一个字典项的词关联起来。 这样，对一个在文本对象d中出现的词t , 可以 使 用r e f c ( t ) 来 检 索 其 相 应的 概 念。 然 后 把词 统 一 到 概 念 ( 语 义) 的 层次 上， 以加强文本之间内容上的相关性。 背景知识的应用还需要考虑到不同的策略。是把概念添加到文本的表示中， 还是用概念替换文本表示中的词，或者是抛弃所有的词而仅仅使用概念;与某些 词相关的概念可能不止一个，在添加概念的时候是考虑所有的概念还是只考虑最 东北大学硕士学位论文第二幸 文本聚类过程 胡(z2) 设 a 的 奇 异 值 ( 即 矩 阵 m r 的 特 征 值 ) 是 。 j + o a , , o , ， 且 o f 卜 二 a ， 卜 奇异值分 解( s i n g u l a r v a l u e d e c o m p o s i t i o n , s v d ) 将a 分解为3 个矩阵 id v t : “ 一 u d v t 一 万 u ; a ; v t 其中 d s d ia g ( o . . . . . . a , ) 为 对 角 矩阵 ， u 和v 是 列正 交 矩阵。 l s i 只 保 存 最大 的 k ( 可 调 参 数 ) 个 奇 异 值 及u , v 中 对 应 的 k 列 ， 使 得认几 可- a . u 的 每 一 行 将 一 个 词表 示 成为 一 个k 维向 量， 同 理v k 的 每一行也 将一 个文本表示成 一个k 维向 量。 经 过s v d方法，词空间的维度得到了降低，达到了特征挑选的目的。 2 . 1 5背景知识的应用 前面已经提到过，文本聚类中一个很大的挑战就是对文本的处理不能根据其 潜在的语义关系来发现文本内容的相似性，而仅仅是根据其字面关系，一个例子 就是“ a u t o ” 和“ c a r 。 字面上二 者完 全 不相关， 但是 在语义层 面上， 二者 指的 是 同一事物。这种局限大大的影响了文本聚类的质量。 背景知识就是用来克服上述问题的。根据以各种形式给定的背景知识，在不 同字面意义上的词之间发现其语义上的联系，提高对文本内容的识别。目 前主要 的 方 法 是以 h m s 0 1 和w m a b 0 3 中 使 用的 本 体( o n to lo g y ) ， 或 者 是 s t b p 0 2 中 的 概念格 ( c o n c e p t l a t t i c e s ) 来作为背景知识，用于文本的预处理阶段。 定义 2 . 1 :本体是一个二元组o :一 ( c , !s c ) ，其中c是概念描述符 ( c o n c e p t i d e n t if ie r ) 的 集 合; 。 是c 上的 偏 序 关系 ， 称 之为 概 念 层次 或 者 概 念 分 类( c o n c e p t h i e r a r c h y o r t a x o n o m y ) . 定 义2 .2 : 本 体o 的 字典 是 一 个二 元 组l e x 一 ( s c , r e f , ) ， 其中 集合s 。 中 的 元 素 称为 概 念 标 志( s i g n f o r c o n c e p t ) ， 关 系r e f c c s c x c 称 之为 概 念的 字 典 参 考( l e x ic a l r e f e r e n c e f o r c o n c e p t s ) ， 其中( c , c ) e e r e f c 对所 有的c e c n s 。 都 成 立。 一般来说，应用背景知识都需要一个本体作为支持。针对不同的问题，可以 使用一些特殊领域的本体，或者是一个普遍的本体。目前应用的最为广泛的本体 是w o r d n e t ， 它 由 本 体 和 字 典 组 成， 在w o r d n e t 中 ， 函 数r e f , 把 那 些 在 他 们 对 应 概念间存在一个字典项的词关联起来。 这样，对一个在文本对象d中出现的词t , 可以 使 用r e f c ( t ) 来 检 索 其 相 应的 概 念。 然 后 把词 统 一 到 概 念 ( 语 义) 的 层次 上， 以加强文本之间内容上的相关性。 背景知识的应用还需要考虑到不同的策略。是把概念添加到文本的表示中， 还是用概念替换文本表示中的词，或者是抛弃所有的词而仅仅使用概念;与某些 词相关的概念可能不止一个，在添加概念的时候是考虑所有的概念还是只考虑最 东北大学硕士学位论文第二章 文本聚类过程 相关的概念，以及如何考虑。这些问题都要根据具体的问题进行分析。 2 . 1 . 6文本表示 预处理的目的之一就是把半结构化或者是非结构化的文本对象转换成为便于 聚类算 法处理的 结构化数据。 通过分 词、 s t e m m i n g 、 特征选取等步骤的 处 理， 则 可以得到对文本的具体表示了。我们首先给出词空间的定义。 定义 2 . 3 :对于一个文本集合d来说，所有在d中出现过的词t ，在经过 s t e m m i n g 、 停用词处理、 特征 选取、 概念提 升等处 理后， 最终得到的 词的集 合t = t ) 称为文本集合d的词空间。 一般常用的文本表示方法是 s k k 0 0 和( d m 0 1 中的向量空间模型 ( v e c to r s p a c e m o d e l , v s m) ， 使用一个向 量 来表示 文本。 向 量空间 模型有简单的 布尔 模型， 即 为 一 文 本d 生 成 一 个 长 度 为 川的 布 尔 向 量 d 与 词 空 间 中 的 词 一 一 对 应 ; 如 果 词 在文本中出现