（计算机科学与技术专业论文）海量短语信息挖掘技术的研究与实现.pdf

国防科学技术大学研究生院博士学位论文 摘要 互连网和信息技术的飞速发展造成海量的数据积累，其中很大一部分是短文 数据，如文章摘要和聊天室的会话。对海量的短文数据进行自动的分析和挖掘， 从中获取有价值的隐含知识，已经成为一项迫切的需求。与普通文档不同，短文 中关键词出现的次数很少，传统的基于词频的文本挖掘技术在处理短文数据时很 难得到可接受的准确度。同时，面对几百g b 甚至t b 级的海量数据，传统的文本 挖掘算法变的很低效甚至根本无法运行。 本文在对海量短语信息挖掘的研究现状和面临的挑战进行深入分析的基础 上，以海量数据处理系统项目为背景、以开发高准确度和高可伸缩性的海量短语 信息挖掘算法为目标，在海量短语信息数据库中的频繁词集挖掘、分类、聚类等 方面开展了深入的研究。为了提高挖掘算法的准确度主要采用了基于语义的方法。 为了提高算法的性能和可伸缩性主要采用了并行化的方法。本文的贡献主要包括 以下方面： 1 针对海量短文本数据库中的频繁词集挖掘所面临的挑战，提出了一个t o p k 频繁词集挖掘的并行算法p a r t f t 。该算法使用了种新颖的逻辑纵向数据划分方 法来确保t o p k 频繁词集挖掘能够在各数据分区中并行执行。同时在每个挖掘结点 通过启发策略来裁剪h s t r u e t 的h e a d e rt a b l e ，从而提高算法的性能。实验结果表 明该算法在进行海量短文数据库中的频繁词集挖掘时具有比同类算法更好的性能 和可伸缩性。p a r t f t 算法的相关成果发表在第六届w e b 时代信息管理大会 ( w a i m 2 0 0 5 ) 上，s c i 检索号b d g 4 9 。 2 针对短语信息分类中的低准确度问题，提出了一个基于语义的短文分类算 法s d c s 。该算法使用文本语义特征图来表示语义信息，并通过k - 近邻( k n n ) 的思想来进行短文分类。实验结果表明该算法在处理大规模短文数据时，性能和 准确度都超过了其它的短文分类算法。相应的成果已投计算机研究与发展杂志。 3 在对短文本聚类面临的挑战进行分析的基础上，针对不同的应用需求提出 了基于频繁词集的短文本聚类算法f t s d c 和基于密度的短文本聚类算法d s d c 。 f t s d c 首先根据频繁词集进行初始簇划分，然后利用语义信息进行簇优化。d s d c 使用语义信息来计算样本距离，基于共享近邻( s n n ) 图来进行基本聚类，并通 过数据抽样和子图划分来实现并行聚类。实验结果表明两种方法在准确度和可伸 缩性上都比类似的算法有一定的提高。f t s d c 的相关成果发表在w i s e 2 0 0 6 的研 第i 页 国防科学技术大学研究生院博士学位论文 讨会“基于w 曲的海量信息处理( w m d p 2 0 0 6 ) ”上，s c i 检索号b f f 8 2 。d s d c 的相应成果已投软件学报。 4 针对基于语义信息的文本挖掘中准确度仍然有待提高以及语义信息不易 管理和交换的问题，定义了领域本体并给出了其构建方法，并在此基础上提出了 基于频繁词集和领域本体的聚类方法o f s d c ，以及基于密度和领域本体的聚类方 法d f s d c 。实验结果表明基于领域本体的文本挖掘方法能够更好地利用语料中的 语义信息，从而获得更高的准确度。o f s d c 的相关成果发表在v l d b 2 0 0 6 的研讨 会“数据库和信息系统中基于本体的技术( o d b i s 2 0 0 6 ) ”上，s c i 检索号待查。 5 在对并行数据挖掘的体系结构进行研究的基础上，提出了基于c o r b a 的 海量短语信息并行挖掘体系结构，并在大规模事务处理中间件s t a r t p m o n i t o r 的背 景下实现了海量短语信息挖掘引擎。 主题词：海量数据、短语信息、文本挖掘、文本分类、文本聚类、频繁词集、 语义、本体、并行数据挖掘 第i i 页 国防科学技术大学研究生院搏士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e ta n dc o m m u n i c a t i o nt e c h n o l o g y , h u g e d a t ai sa c c u m u l a t e d s h o r td o c u m e n t ss u c ha sp a p e ra b s t r a c t sa n dc o n v e r s a t i o n si n c h a t t i n gt o o l i sa l ec o m m o ni ns u c hd a t a i ti sv e r yu s e f u lt oa n a l y s i sa n dm i n et h es h o r t d o c u m e n t st og e tv a l u a b l ei m p l i c i tk n o w l e d g e h o w e v e r , u n l i k ei nc o m m o nd o c u m e n t s ， k e yw o r d si ns h o r td o c u m e n t sa p p e a rw i t hal o wf r e q u e n c yw h i c hm a k e st r a d i t i o n a l w o r df r e q u e n c yb a s e dm i n i n gt e c h n o l o g yc a nn o tg e ta c c e p t a b l ea c c u r a c yw h e nm i n i n g s h o r td o c u m e n t s o nt h eo t h e rh a n d w h e np r o c e s s i n gt e x td a t aw i t l lh u n d r e d so fg bo r e v e nl a r g e rt h a n1t b ，m o s to ft h ee x i s t i n gm i n i n ga l g o d t h m sb e c o m ei n e f f i c i e n to r e v e nu n a v a i l a b l e b a s e do nt h ea n a l y s i so ft h ec u r r e n ts t a t u sa n dc h a l l e n g e so fs h o r td o c u m e n t s m i n i n gt e c h n o l o g y , t h et h e s i sa l m st od e v e l o ps h o r td o c u m e n t sl l l i n i n ga l g o r i t h m s 、】v i t l l l l i g ha c c u r a c ya n ds e a l a b i l i t y s h o r td o c u m e n tm i n i n gt e c h n o l o g i e ss u c ha sf r e q u e n t t e r ms e t sm i n i n g ，c l a s s i f i c a t i o na n dc l u s t e r i n g ，e t c ，a r es t u d i e di nt h et h e s i s s e m a n t i c i n f o r m a t i o ni nt h es h o r td o c u m e n t si su s e di no r d e rt og e tb e t t e ra c c u r a c yf o rt h em i n i n g a l g o r i t h m s i no r d e rt oi m p r o v et h ep e r f o r m a n c ea n ds c a l a b i l i t y , p a r a l l e lm i n i n g m e t h o d sa r eu s e d t h em a i nc o n t r i b u t i o n so f t h et h e s i sa r ea sf o l l o w s ： 1 a i m i n ga tt h ec h a l l e n g e so nf r e q u e n tt e r ms e t sm i n i n gi nv e r yl a r g es h o r tt e x t d a t a b a s e s ，w ep r e s e n tap a r a l l e lt o p - kf r e q u e n tt e r ms e t sm i i l i n ga l g o r i t h mn a m e d p a r t f t a n o v e ll o g i c a lv e r t i c a ld a t ap a r t i t i o n i n gm e t h o di su s e dt om a k es u r et h et o p k f r e q u e n tt e r ms e t sc a nb em i n e dp a r a l l e la te a c hm i l l i n gn o d e o nt h eo t h e rh a n d , h e u r i s t i cm e t h o d sa l eu s e dt op r u n et h eh e a d e rt a b l eo fh s t r a c ta te a c hn l i n i n gn o d e w h i c hi m p r o v e st h ep e r f o r m a c eo ft h ea l g o r i t h m e x p e r i m e n t a ls t u d i e ss h o wt h a t p a r t f th a sb e t t e rp e r f o r m a n c ea n ds c a l a b i l i t yt h a ns i m i l a ra l g o r i t h m sw h e nm i n i n g v e r yl a r g es h o r tt e x td a t a b a s e s t h ep a p e rf o rp a r t f ta l g o r i t h mi sp u b l i s h e di nt h e p r o c e e d i n g o ft h es i x t hi n t e r n a t i o n a lc o n f e r e n c e o n ，e b a g e i n f o r m a t i o n m a n a g e m e n t ( w a i m2 0 0 5 ) a n dt h es c ii n d e xn u m b e ri sb d g 4 9 2 i no r d e rt oi m p r o v et h ea c c u r a c yw h e n c l a s s i l y i n gs h o r td o c u m e n t s ，w ep r e s e n ta s e m a n t i cb a s e ds h o r td o c u m e n t sc l a s s i f i c a t i o na l g o r i t h mn a m e ds d c s s d c su s e sa 第i i i 页 国防科学技术大学研究生院博士学位论文 n o v e ls y m a n t i cf e a t u r e sg r a p ht or e p r e s e n ts e m a n t i ci n f o r m a t i o na n du s e sk n nm e t h o d t oc l a s s i f ys h o r td o c u m e n t s e x p e r i m e n t a ls t u d i e ss h o wt h a ts d c sh a sb e t t e ra c c u r a c y a n dp e r f o r m a n c et h a ns i m i l a ra l g o r i t h m sw h e nc l a s s i f y i n gm a s s i v es h o r td o c u m e n t s 1 1 l ep a p e rf o rs d c sh a sb e e ns u b m i t t e dt ot h ej o u m a lo fc o m p u t e rr e s e a r c ha n d d e v e l o p m e n t 3 b a s e do nt h ea n a l y s i so ft h ec h a l l e n g e so nm a s s i v es h o r td o c u m e n t sc l u s t e r i n g t e c h n o l o g y , w ep r e s e n tt w oa l g o d t h r n sn a m e df t s d ca n dd s d c f t s d ci saf r e q u e n t t e r ms e t sb a s e dc l u s t e r i n ga l g o r i t h m i tf i r s tp a r t i t i o n st h ed o c u m e n t si n t o c l u s t e r s a c c o r d i n gt ot h ef r e q u e n tt e r ms e t sa n dt h e no p t i m i z e st h ec l u s t e r i n gu s i n gs e m a n t i c i n f o r m a t i o n ，d s d ci sad e n s i t yb a s e dc l u s t e r i n g a l g o r i t h m i t u s e ss e m a n t i c i n f o r m a t i o nt oc a l c u l a t et h ed i s t a n c eb e t w e e nd o c u m e n t sa n dc l u s t e r st h ed o c u m e n t s b a s e do ns n n g r a p h d a t as a m p l i n ga n ds n ng r a p hp a r t i t i o nt e c h n o l o g yi sa l s ou s e d t o c l u s t e rd o c u m e n t sp a r a l l e l e x p e r i m e n t a ls t u d i e ss h o wt h a tt h et w oa l g o r i t h m sb o t h h a v eb e t t e ra c c u r a c ya n dp e r f o r m a n c et h a ns i m i l a ra l g o r i t h m sw h e nc l a s s i f y i n gm a s s i v e s h o r td o c u m e n t s 1 1 1 ep a p e rf o rf t s d ca l g o r i t h mi sp u b l i s h e di np r o c e e d i n go ft h e w i s ew o r k s h o po nw e b b a s e dm a s s i v ed a t ap r o c e s s i n g ( w m d p 2 0 0 6 ) t h ep a p e rf o r d s d ca l g o r i t h mi ss u b m i t t e dt ot h ej o u r n a lo fs o f t w a r e 4 i no r d e rt oi m p r o v et h ea c c u r a c yo fm i n i n gm e t h o d sf u r t h e ra n dm a n a g et h e s e m a n t i ci n f o r m a t i o ni nar e a s o n a b l ew a y , w ed e f i n ed o m a i no n t o l o g yf o rs h o r t d o c u m e n t sa n dp r e s e n tt h ed o m a i no n t o l o g yb u i l d i n gm e t h o d b a s e d0 nd o m a i n o n t o l o g y , w ep r e s e n tf r e q u e n tc o n c e p ts e t sb a s e ds h o r td o c u m e n t sc l u s t e r i n ga l g o r i t h m n a m e do f s d ca n dd e n s i t yb a s e dc l u s t e r i n ga l g o r i t h mn a m e do d s d c e x p e r i m e n t a l s t u d i e ss h o wt h a to n t o l o g yb a s e dm e t h o d sc a nu t i l i z es e m a n t i ci n f o r m a t i o nb e t t e ra n d g e tb e t t e ra c c u r a c y t h ep a p e rf o ro f s d c i sp u b l i s h e di np r o c e e d i n go ft h ev l d b w o r k s h o po no n t o l o g i e s b a s e dt e c h n i q u e s f o rd a t a b a s e sa n di n f o r m a t i o ns y s t e m s 2 0 0 6 ( o d b i s 0 6 ) 5 b a s e do nt h es t u d i e so nt h ea r c h i t e c t u r eo fp a r a l l e ld a t am i m n g ，w ep r e s e n ta p a r a l l e lm i n i n ga r c h i t e c t u r e f o rm a s s i v es h o r td o c u m e n t sb a s e do nc o r b aa n d i m p l e m e n tt h em a s s i v es h o r td o c u m e n t sm i n e ri nt h ev e r yl a r g et r a n s a c t i o n sp r o c e s s i n g m i d d l e w a r es t a r t p m o n i t o r 第1 v 页 国防科学技术大学研究生院博士学位论文 k e y w o r d s ：m a s s i v ed a t a ，s h o r tm e s s a g e t e ) ( tm i n i n g ，t e ) c tc l a s s i f i c a t i o n ，t e x t c l u s t e r i n g ，f r e q u e n tt e r ms e t s e m a n t i c ，o n t o l o g y , p a r a l l e ld a t a m i n i n g 第v 页 国防科学技术大学研究生院博士学位论文 表2 1 表2 2 表2 3 表3 1 表3 2 表3 3 表3 a 表3 5 表3 6 表3 7 表3 8 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表5 - l 表5 2 表5 3 表5 a 表5 5 表5 6 个文本数据库 表目录 个k 词集表2 1 o r a c l e 文本索引的叫啦l 子 向量空间模型短文分类的准确度3 3 1 0 个词的h a l 语义空间3 5 q p o ( w 3 ) 。3 6 q p 4 _ s ( w 3 ) 3 6 4 4 4 4 4 4 准确度对比。4 4 待聚类的文本数据库。5 0 频繁词集 初始聚类 最终聚类 f i s d c 的文档结构零毛 r e u t e r s 语料上准确度 短文本语料上准确度 语境的矩阵表示 语义分类实验数据 基于v s m 的分类结果 o f s d c 中的语义分类结果 r e m e t s 语料上准确度 短文语料匕准确度8 8 第v 页 班n乳研甜舛为盯盯盯卵 国防科学技术大学研究生院博士学位论文 图目录 图1 1 信息技术的演化 图1 2 本文的组织结构图 3 l o 图2 1h - s t n 】c l 1 9 图2 2 图2 3 h a 和a - q u e u e 1 9 相对短词集2 0 图2 4 传统横向数据划分 图2 5 逻辑纵向数据划分。2 2 图2 6 稀疏数据上的性能，k z 2 0 0 图2 7 稀疏数据上的性能，k = - 5 0 0 图2 8 稠密数据上的性能，1 c = 2 0 0 图2 9 稠密数据上的性能，i 两0 0 2 5 2 6 2 6 2 7 图2 1 0 海量稀疏数据上的性能，2 7 图3 1 支持向量机的超平面 图3 2 图3 3 包含带标类签结点的t s f g 大规模数据集上的性能对比 图4 1f t s d c 的数据划分 图4 2 基于密度的聚类中的密度可达和密度相连 图4 3 个娜e 离图 3 2 4 1 4 5 5 2 5 5 图4 4s n n 相似度计算 图4 5 基于密度聚类的并行化 5 6 5 7 6 l 图4 6 较大规模数据集上的性能6 4 图4 7 大规模数据集匕的可伸缩性 图4 8 l 船语料上准确度 图4 9 短文本语料上准确度一第组 图4 1 0 短文本语料上准确度一第二组 图4 1 1 抽样数据量对准确度的影响 图4 1 2 大规模数据集上的可伸缩性。 图5 1 饮料的概念分类 图5 2 图5 3 图5 4 基于本体论的文本挖掘系统模型 概念格的线路图 领域本体构建过程 图5 5o l 唱d c 的总体流程 图5 6 概念映射示例 8 3 8 4 8 8图5 7 较大规模数据集上的性能 图5 8 大规模数据集上的。町 申缩性 第v i 页 贷丽酶的酊醯订记舳 国防科学技术大学研究生院博士学位论文 图5 9 短文语料上准确度8 9 图5 1 0 大规模数据集上的可伸缩性 图6 1s t a r t p m o n i t o r 体系结构 图6 2s l a r s t m i n e r 体系结构 图6 3s t a r s t m i n e r 的并行挖掘体系结构 图6 a 权值分析子模块结构 图6 5 语义信息构建模块结构 图6 6 短文分类器结构 图6 7 频麴司集挖掘模决结构 图6 8 基于频繁词集的聚类模块结构 8 9 9 1 9 3 9 4 9 6 9 7 9 8 9 8 图6 9 基于密度的聚类模块结构1 0 0 第v i i 页 国防科学技术大学研究生院博士学位论文 缩略语 c o r b a ：c o m m o n o b j e c c t r e q u e s t b r o k e r a r c h i t e c t m e c o s a ：c o n c e p ts e l e c t i o na n d a a d g m g a t i o n d s d c ：d e n s i t y b a s e d s h o r t d o c t m a e n t s c l u s t e r i n g f c a ：f o m m lc o n c e p t a n a l y s i s f t s d c ：f r e q u e n t - t e r m sb a s e ds h o r td o e m n e n t sc l u s 劬a g h a l , h y p e r - s p a e e a n a l o g u e t ol a n g u a g e i c t c l a s ：i n s a i t u t e o f c o m p u t i n g t e c h n o l o g y , c h i n e s e l e x i c a l a n a l y s i s s y s t e m k a o n ：k 甜l 轼u l 砖o n t o l o g y 越1 ds e m a n t i cw e b i n f r a s m l e t u r e k n n ：k n e m e s t n e i g h b o r l i g o ：l a s e ri n t c r f c r o m e l e rc a a v i t a l i o m lo b s c r v a t o r y l s a ：l a t e n t s e r n a n l i c a n a l y s i s m s t p s ：m a s s i v es h o r t t e x - t l r o c c s s i i l g s y s t e m n a s a ：n a t i o n a l a e r o n a u t i c s a n d s l x a c e a d m i n i s w 血o n n v o ：n a t i o n a lv h - t u a lo b s e r v a t o r y o d s d c ：o n t o l o g y a n d d c n s i l y b e s c d s h o r t d o e u m e r l t c l u s t e r i n g o f s d c ：o n t o l o g y a n df r e q u e n t - t e r m sb a s e ds h o r td o c u m e n tc l u s t e r i n g o t t o ：o n t o l o g y - b a s e d t e x t m i n i n g f r a m e w o r k p a r t f r ：p a r a l l e lt o p - kf r e q u e n t t e n n s e t s d c s ：s h o r t d o c m n e n t c l a s s i f i c a t i o n u s i n gs i 丑n 蒯c f c a m r c s s n n ：s h , m e d n e a r e s t n e i g h b o r s v i v a ：s u p p o r t v e c t o r m a c l t i n e t s f g ：t e x ts e m i t i cf e a t u r e sg r a p h t d t ：t o p i cd e t e c t i o n a n d t r a c k i n g v s m ：v e c t o rs p a c em o d e l 第v l l l 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材辑与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目 学位论文作者 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文祓查阌和借阕；可以将学位论文的全部或部分内容编入有关数据库进行捡索， 可以采用影印，缩印或扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目 学位论文作者 作者指导教师签名：逸煎日期：刀莎年 月万日 国防科学技术大学研究生院博士学位论文 第一章绪论 信息技术的飞速发展造成了海量的数据累积，其中很大一部分是文本数据。 如何对海量文本数据进行分析和挖掘，从中获取有用的知识，近年来成为很多研 究者关注的问题。短文本在文本数据中占有相当的比例，对短文本进行分析比对 普通的文档进行分析具有更大的难度。同时t b 级的海量数据也给传统的数据挖掘 技术提出了新的挑战。 本文研究t b 级海量文本数据库中的短语信息挖掘技术。本章1 1 节介绍了海 量短文本挖掘的应用背景。1 2 节分析了当前文本挖掘技术的现状以及海量短文本 挖掘面临的挑战。1 3 节介绍了本文的工作。1 4 节给出了论文的结构。 1 1 1 信息时代的数据规模 1 1课题背景 在过去的数十年中，我们产生和收集数据的能力已经迅速提高。起作用的因 素包括条码在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算 机化，以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。近年 来，随着互联网和通信技术的飞速发展，在这个世界上每天都会产生海量的数据 而且这些数据正在以惊人的速度增长。以下统计数字是对我们所处的海量信息时 代的直观说明： w e b 数据。根据a n t o n i og u l l i 的报告【1 1 ，2 0 0 5 年1 月份，w e b 页已经达 到1 1 5 亿。这个数值仍然在迅速增长。 科学数据。根据g r a y 的报告【2 】，美国的国家虚拟天文台( n a t i o n a lv i r t u a l o b s e r v a t o r y ，n v o ) 从2 0 0 4 年起每年有5 0 0 t b 的数据增长。激光干涉仪 重力天文台( l a s e ri n t e r f e r o m e t e rg r a v i t a t i o n a lo b s e r v a t o r y ，l i g o ) 自2 0 0 2 年每年有2 5 0 t b 的数据积累。美国航天局( n a i l o n a l a e r o n a u t i c sa n ds p a c e a d m i n i s t r a t i o n ，n a s a ) 的数据量在2 0 0 7 年将达到1 5 p b 。 搜索引擎。g o o g l e 的数据量在2 0 0 0 年就超过了1 5 p b f 2 1 。 个人数据。根据存储设备提供商e m c 公司的技术主管j a m e sr o t h n i e 的报 告，典型的美国人一生会产生1 0 0 g b 的数据，包括医疗信息，教育信息， 第1 页 国防科学技术大学研究生院博士学位论文 保险信息等。 即时消息工具和电子邮件。即时消息工具如a o l 和m s n ，电子邮件如 y a h o o ! 和h o t m a i l ，数据量都达数百t b t 2 1 。 以上统计数据表明，我们已经由信息贫乏的时代进入了信息极度丰富的时代。 我们不仅需要具备存储和查询海量数据的能力，还需要能够从浩如烟海的数据中 提取隐含在其中的知识，作为决策的依据。 在这些数据中，文本数据占有很大的比例。通常认为商业信息中非结构化信 息和结构化信息的比例是8 0 ：2 0 。最新统计表明高达8 5 的商业信息是文本格式的 4 1 。这些文本数据包括w 曲页面、科研论文、电子邮件及公司订单等。 1 1 2 海量文本挖掘需求 m i c r o s o f t 研究中心的j i mg r a y 说，“我们被数据科学数据、医疗数据、人 口统计数据、财经数据和市场数据淹没。人们没有时间看数据。人类的关注 已经成为一种宝贵的资源。” 面对海量的数据堆积，人们需要从海量的数据中获取隐含的、有价值的信息， 用于商务管理、市场分析、科学探索等。这就是数据挖掘技术产生的应用需求。 数据挖掘是从大量的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。数据挖掘技术的产生和发展是信息技术自 然演化的结果。信息技术的演化过程如图1 1 所示【3 】o 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理演 化到复杂的、功能强大的数据库系统。自7 0 年代以来，数据库系统的研究和开发 已经从层次和网状数据库系统发展到关系数据库系统。自8 0 年代以来，数据库技 术的特点是广泛接受关系技术，研究和开发新的、功能强大的数据库系统。 在过去的3 0 年中，计算机硬件稳定的、令人吃惊的进步导致了功能强大的计 算机、数据收集设备和存储介质的大量供应。这些技术大大推动了数据库和信息 产业的发展，使得数据库和信息系统在事务管理、信息检索和数据分析中获得了 成功的应用。 现在，数据可以放在不同类型的数据库中。近年来出现的一种数据库结构是 数据仓库。这是一种多个异构数据源在单个站点以统一的模式组织的存储，已支 持管理决策。数据仓库技术包括数据清理、数据集成和联机分析处理( o l a p ) 。 o l a p 是一种分析技术，具有汇总、合并和聚集功能，以及从不同角度观察信息的 第2 页 国防科学技术大学研究生院博士学位论文 能力。尽管o l a p 工具支持多维分析和决策，对于更深层次的分析，如数据分类、 数据随时间变化的特征分析等，仍需要其它的分析工具。 图1 1 信息技术的演化 海量的数据积累带来了对强有力的数据分析工具的需求，大量的数据被描述 为“数据丰富，但信息贫乏”。快速增长的海量数据存放在众多大型的数据库和文 件系统中，没有强有力的工具，理解这些数据已经远远超出人的能力。结果，收 集在大型数据库或文件系统中的数据成了“数据坟墓”难得再访问的数据档 案。这样，重要的决策往往不是基于数据库中丰富的数据，而是基于决策者的直 觉，因为决策者缺乏从海量数据中获取有价值知识的工具。此外，当前的专家系 统技术通常依赖用户或领域专家人工地将知识输入知识库。不幸的是这一过程常 第3 页 国防科学技术大学研究生院博士学位论文 常有偏差和错误，而且耗时、费用高。用数据挖掘工具进行数据分析，可以发现 重要的数据模式，对商务决策、知识库、科学研究等具有重要意义。数据和信息 之间的鸿沟要求系统地开发数据挖掘工具，将数据坟墓转换成知识“金块”。 数据挖掘可以在多种类型的数据源上进行，包括数据库、数据仓库和文件系 统等。文本挖掘是数据挖掘的一个重要组成部分，近年来受到研究者的重视。文 本数据是所谓半结构化的数据，它既不是结构化的也不是完全无结构的。例如， 文本数据可以包含标题、作者、日期等结构字段。文本挖掘与信息检索是有区别 的。信息检索是指从大量的文档集合中找到与给定查询请求相关的、恰当数目的 文档子集的过程。信息检索是帮助用户发现资源，而文本挖掘是为了揭示文本中 隐含的知识。有时信息检索系统返回太多的结果以至于用户无法一一浏览，有时 用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、 含义，在这些场合下就需要使用文本挖掘技术。 文本挖掘技术通常包括文本分类、聚类和关联分析等。文本分类是在给定的 分类体系下，根据文本的内容自动地确定文本所属的类别。文本聚类是根据文档 的相似性把文档归入不同的类别，使得同类之间的文档尽可能相似，不同类之间 的文档尽可能不相似。文本分类属于有指导的学习而文本聚类属于无指导的学习。 文本关联分析技术用于发现文档之间隐含的联系，通常是分析文档在一定范围内 共同出现的情况来确定其隐含的联系。 文本挖掘技术能够为很多行业提供有价值的信息。例如亚马逊网站 ( h t t p ：w w w a m a z o n c o r n ) 通过对用户注册信息的分析来发现潜在的买主。话题识 别与跟踪( t o p i cd e t e c t i o na n dt r a c k i n g , t d t ) 是对多种文本挖掘技术的综合运用， 它用来从大量的新闻资料中提取热门话题并跟踪该话题的进展。 除了传统的文本挖掘，近年来对短文本进行挖掘的需求日益增加。短文本的 一种类型是摘要数据。在海量信息的时代，人们往往不会直接查看详细文档而是 首先看其摘要。同时很多互连网上的文档是不能直接访问的( 如收费网站的文档) 。 但其摘要可以访问。短文本的另外一大类是数字通信中的短语信息。近年来数字 通信短语信息在人们的通信中占有了越来越大的比重，如电子邮件、即时聊天工 具、互联网聊天室等。电子邮件已经在很大程度上取代了传统邮件，从y a h o o 和 h o t m a i l 等邮件系统数据量可以看出电子邮件的普及程度。即时聊天工具如m s n 、 a o l 及i c q 等，互连网上众多的公共聊天室，均有着广大的用户群。对海量短语 信息进行挖掘有着重要的实用价值。例如可以从海量短语信息中发现热门话题， 从而发现当前社会中受关注的焦点问题。也可以从海量短语信息中发现异常的事 第4 页 国防科学技术大学研究生院博士学位论文 件，提醒有关部门引起注意。 1 2 1 文本挖掘的相关工作 1 2研究现状 文本挖掘技术是数据挖掘技术与自然语言处理技术的结合。尽管文本挖掘这 个词正式出现是在2 0 世纪9 0 年代，但和文本挖掘得相关研究已经有几十年的历 史。最早的工作来自l u h n ，1 9 5 8 年，他在一篇关于自动文摘的文章【6 】中提出了基 于关键词的方法。d o y l e 在1 9 6 1 年提出了通过统计词的频率和分布的方法来从文 本中获取知识的方法【7 】。s w a n s o n 在1 9 8 8 年对文本分析和挖掘工作的意义和价值 给予了充分的肯定嘲并在后来开发了一个医药行业的文本挖掘系统【9 】。s w a n s o n 的 系统被认为是自动文本挖掘领域的先驱，在此基础上，2 0 世纪9 0 年代末和2 1 世 纪初，出现了大量的文本挖掘研究工作 1 0 , 1 1 , 1 2 , 1 3 】。 在1 9 9 8 年的第1 0 届欧洲机器学习会议( e u r o p e a nc o n f e r e n c eo nm a c h i n e l e a m i n g , e c m l 9 8 ) 上，文本挖掘被正式提出并作为一个专题。会议认为文本挖掘 是从文档集合中搜寻知识，并不试图改进自然语言理解技术而只是利用该领域的 成果。我国的“9 7 3 计划”在1 9 9 8 年首批实施项目中包括了文本挖掘的内容( 中国 科学院计算技术研究所承担的“文本挖掘与知识检索”项目) 。 1 2 1 1 文本关联分析 文本关联分析是传统关联规则挖掘技术 2 4 , 1 3 4 , 1 3 5 】在文本领域的应用。关联规则 挖掘的目标是