（通信与信息系统专业论文）web中文文本的数据挖掘技术研究.pdf

山东大学硕士学位论文 中文摘要 随着w e b 信息的急剧增长，人们迫切需要一种技术来对信息进行组织和管理， 帮助用户快速、准确地找到需要的信息，数据挖掘和w e b 技术相结合的w e b 挖掘 应运而生。文本作为w e b 上信息的主要形式，文本挖掘近年来成为研究的热点。 中文文本挖掘起步较晚，在理论研究和应用方面都落后于英文文本挖掘，因此本 文以w e b 中文文本挖掘作为研究重点。 本文主要研究的是文本挖掘中w e b 中文文本的聚类和分类问题。文本分类和 聚类是文本挖掘中的关键技术，通过对文本进行归档整理，可以在很大程度上解 决信息爆炸和信息杂乱的问题。同时作为信息检索、信息过滤、搜索引擎、电子 图书馆、文本数据库等领域的技术基础，文本分类和聚类应用领域非常广泛。 文章首先对相关的理论知识进行了介绍，概念从大到小包括数据挖掘、w e b 挖掘、文本挖掘以及文本分类和聚类；对文本进行分类和聚类首先要把文本转化 为计算机可以处理的形式，所以接下来我们对w e b 文档矩阵化形式转化的预处理 过程进行了研究；最后将我们提出的聚类和分类算法应用到中文文本的聚类和分 类中。 文章介绍和实现了常用的聚类算法：k - m e a n s 算法和模糊c 均值( f c m ) 算法。 将w e b 文档矩阵化首先要从网页中去掉h t m l 标记，滤掉无关信息，解析出 纯文本；中文文本和英文文本不同，词与词之间没有自j 隔，所以要进行分词处理； 然后采用权重计算公式计算出特征词项的权重，基本思想是若某特征词在本篇文 档中出现的次数多，而在其他文档中出现的次数少，该词被赋予更高的权重来代 表本文档，并与其他文档进行区分。这样w e b 文档就转化为词项文档的向量空间， 以便后面的聚类和分类算法的执行。 文章分析了文本挖掘过程中文本矩阵的高维性和稀疏性的特点，并针对此特 点提出将基于子空间的聚类算法和基于语义的奇异值分解的聚类算法两种方法应 用于中文文本的聚类。某个主题的文本会有特定的主题词子集，存在着特征子空 间的结构。采用子空问聚类可以忽略掉对分类不重要的维，给重要的维赋予更高 的权重，凸显主题词子集对分类的作用，解决高维性和稀疏性问题，所以基于子 山东大学硕士学位论文 空间的聚类可以提高聚类的准确率和效率，对文档数据的实验结果证明，该算法 聚类效果令人满意。奇异值分解对数据集的特征值按重要性排序，一方面把不重 要的维看做“噪声 忽略掉，凸显词项和文章之间的语义关系，另一方面使得文 档矩阵维数大大缩减，从而提高文档聚类的准确性。我们先用奇异值分解对文档 矩阵降维，后用人工鱼群优化算法对文本聚类，对文档数据的实验结果证明这种 方法在保证准确率的情况下提高了效率。 本文还实现了改进的支持向量机的文本分类。因为支持向量机的惩罚因子和 核函数参数的选择对分类的效果有很大影响，所以本文首先用粒子群优化算法优 化惩罚因子和核函数参数，后用支持向量机进行文本分类，仿真结果证明支持向 量机分类的有效性。 2 关键词：预处理；向量空间模型：文本聚类；文本分类 山东大学硕士学位论文 a b s t r a c t w i t ht h e e x p l o s i v eg r o w t hi n t h ea m o u n to fi n f o r m a t i o n ，i t i s b e c o m i n g i n c r e a s i n g l yd i f f i c u l tt of i n di n f o r m a t i o n p e o p l eb a d l yn e e dak i n do ft e c h n o l o g yt o o r g a n i z ea n dp r o c e s st h el a r g em o u n to fi n f o r m a t i o n u n d e rt h ec i r c u m s t a n c e sw e b m i n i n gc o m b i n e db yd a t am i n i n ga n dw e bt e c h n o l o g ya r o u s e d a st e x ti st h em a i n c o m p o n e n to ft h ew e bi n f o r m a t i o n ，t e x tm i n i n gb e c o m e sah o tr e s e a r c hf i e l d b e c a u s e o ft h el a t es t a r t , c h i n e s et e x tm i n i n gf a l l sb e h i n de n g l i s ht e x tm i n i n g s ow er e g a r dw e b c h i n e s et e x tm i n i n ga so u rr e s e a r c ho b j e c t w ef o c u so nw e bc h i n e s et e x tc l a s s i f i c a t i o na n dc l u s t e r i n gi nt h i sp a p e r t e x t c l a s s i f i c a t i o na n dc l u s t e r i n ga r et h ek e y t e c h n o l o g i e si nt e x tm i n i n g b yo r g a n i z i n ga n d c l a s s i f y i n gt e x td a t a s e t , t h e y 咖s o l v et h ep r o b l e mo fi n f o r m a t i o ne x p l o s i o nt oag r e a t e x t e n t m o r e o v e r , t e x tc l a s s i f i c a t i o na n dc l u s t e r i n gw i l lb ew i d e l ya p p l i e da st h e t e c h n i c a lb a s i so fi n f o r m a t i o nr e t r i e v a l ，s e a r c he n g i n e ，e l e c t r o n i c l i b r a r ya n dt e x t d a t a b a s ea n ds oo n w i t ht h ea d v e n to ft h ei n f o r m a t i o ne r a , t e x tc l a s s i f i c a t i o na n d c l u s t e r i n g a r eb e c o m i n gm o r ea n dm o l ew i d e l yu s e d t h ep a p e rf i r s ti n t r o d u c e st h er e l e v a n tt h e o r i e s ，i n c l u d i n gd a t am i n i n g ，w e bm i n i n g , t e x t m i n i n g ，a n dt e x tc l a s s i f i c a t i o n a n dc l u s t e r i n g b e f o r et e x tc l a s s i f i c a t i o na n d c l u s t e r i n g ，w en e e dt ot r a n s f o r mt h et e x ti n t ot h ef o r mt h a tc o m p u t e rc a nh a n d l e 、i t l l s ow es t u d yt h ep r e p r o e e s s i n gw h i c ht r a n s f o r m st h ew e bt e x td a t a s e ti n t om a t r i x a n d t h e nw ea p p l y0 1 1 1 p r o p o s e dm e t h o d so nc h i n e s et e x tc l a s s i f i c a t i o na n dc l u s t e r i n g w ei n t r o d u c ea n dr e a l i z et h ec o m m o nc l u s t e r i n gm e t h o d si n c l u d i n gk - m e a n s m e t h o da n df u z z yc - m e a n sm e t h o d t h e r ea r es e v e r a ls t e p st ot r a n s f o r mt h ew e bt e x ti n t om a t r i x ，f i r s t l yw es h o u l d r e m o v et h eh t m lr e m a r k s ，f i l t e ro u tt h ei r r e l e v a n ti n f o r m a t i o na n dp a r s eo u tt e x t ； s e c o n d l y c h i n e s et e x ti sd i f f e r e n tf r o me n g l i s ht e x t t h e r ea r en oo b v i o u sb o u n d a r i e s b e t w e e nw o r d si nc h i n e s et e x td o c u m e n t s ，s oc h i n e s ew o r ds e g m e n t a t i o ni st h ef i r s t s t e pi nc h i n e s et e x tp r e p r o c e s s i n g ；a n dt h e nc a l c u l a t et h ew e i g h tb yw e i g h tc a l c u l a t i o n e q u a t i o n t h em a i ni d e ao ft h ew e i g h t ：i faw o r do rp h r a s ea p p e a r sh i g h - f r e q u e n t l yi na d o c u m e n tb u tr a r e l yi no t h e rd o c u r n e n t s ，i tc a l lw e l lr e p r e s e n tt h et e x tf e a t u r e so ft h i s c l a s s ，、i t hv e r yg o o da b i l i t yt od i s t i n g u i s hc l a s s e s i ti ss u i t a b l ef o rc l a s s i f i c a t i o na n d 3 山东大学硕士学位论文 s h o u l db eg i v e nh i g h e rw e i g h t s t h u sw e bt e x t 咖b et r a n s f o r m e di n t oam a t r i xw h e r ea lo w r e p r e s e n t sad o c u m e n ta n d ac o l u m nr e p r e s e n t sau n i q u et e r m ，a n dc a l lb ea n a l y z e d b yc l u s t e r i n ga n dc l a s s i f i c a t i o nm e t h o d s t h ep a p e ra n a l y z e st h ec h a r a c t e ro fh i g h - d i m e n s i o na n ds p a r s e n e s so ft h et e x t m a t r i x ，a n dt h ec h a r a c t e rr e s u l t si nt r a d i t i o n a la l g o r i t h m sf a i l u r ew h e nc l u s t e r i n gs u c h h i g h - d i m e n s i o n a ld a t a t ot h eq u e s t i o n , w ep r o p o s et w om e t h o d st oc l u s t e rc h i n e s et e x t o n ei sb a s e do ns u b s p a c ea n dt h eo t h e ri sb a s e do ns i n g u l a rv a l u ed e c o m p o s i t i o n d o c u m e n t sr e l a t e dt oap a r t i c u l a rt o p i ca r ec a t e g o r i z e db yo n es u b s e to ft e r m s t h a ti s ， t h e r ei st h ef e a t u r es u b s p a e es t r u c t u r ew h e nc l u s t e r i n g s ow ea d o p tt h es u b s p a e e c l u s t e r i n ga l g o r i t h mt c p s ot oc l u s t e rc h i n e s et e x t s a c c o r d i n gt ot h ee x p e r i m e n t a l r e s u l t s ，w ec a ns e et h a ts u b s p a c ec l u s t e r i n gi ss u i t a b l et oc h i n e s et e x tc l u s t e r i n ga n d m o r ee f f e c t i v et h a nt r a d i t i o n a la l g o r i t h m s i n g u l a rv a l u ed e c o m p o s i t i o ns o r t st h e c h a r a c t e r i s t i cv a l u eo ft h ed a t a s e ta c c o r d i n gt ot h ei m p o r t a n c e o nt h eo n eh a n d ，t h e u n i m p o r t a n td i m e n s i o ni si g n o r e da s “ n o i s e ”：o nt h eo t h e rh a n di tm a k e st h ed o c u m e n t m a t r i xd i m e n s i o ng r e a t l yc u r t a i l e d ，s oa st oi m p r o v et h ea c c u r a c yo ft h ed o c u m e n t c l u s t e r i n g w ef k r s ta d o p ts i n g u l a rv a l u ed e c o m p o s i t i o nt or e d u c et h ed i m e m i o n , a n d t h e na d o p ta r t i f i c i a lf i s ho p t i m i z a t i o na l g o r i t h mt oc l u s t e rc h i n e s et e x t f r o mt h e s i m u l a t i o nr e s u l t sw ec a ns e et h em e t h o di m p r o v et h ee f f i c i e n c y w ea l s or e a l i z et h ec h i n e s et e x tc l a s s i f i c a t i o nb a s e do ni m p r o v e ds u p p o r tv e c t o r m a c h i n e t h ep a r a m e t e r so fs u p p o r tv e c t o rm a c h i n eh a v ei m p o r t a n ti m p a c to i lt h e c l a s s i f i c a t i o nc a p a b i l i t y i ft h ep a r a m e t e r sd on o te n a c t m e n ta p p r o p r i a t e l y , w eg a l l tg e t t h eg o o dc l a s s i f i c a t i o nr e s u l t s s ow eu s ep s ot oo p t i m i z ep e n a l t yc o n s t a n tca n dk e r n e l f u n c t i o np a r a m e t e rgo fs v mi nt h i sp a p e r t h es i m u l a t i o nr e s u l t ss h o wt h eg o o d g e n e r a l i z a t i o na b i l i t ya n dc l a s s i f i c a t i o na c c u r a c y k e yw o r d s ：p r e p r o c e s s i n g ；v e c t o rs p a c em o d e l ( v s m ) ；t e x tc l u s t e r i n g ；t e x t c l a s s i f i c a t i o n 4 山东大学硕士学位论文 第一章绪论 1 1 研究背景 随着i n t e r n e t 的广泛应用，计算机技术、网络技术和通信技术正极大地推动着 人类社会各个方面的发展。互联网成为世界性的图书馆，变成了各行各业人们交 流思想、获取信息的平台。目前，网上资源正以指数速度增长，其信息量无论是 数量上还是种类上都是人们难以想象的，如何从这些海量的庞杂的信息中快速有 效地寻找到满足需求的信息，对人们来说是一个很大的挑战。因此迫切需要一种 能快速、有效地从w e b 上发现资源和知识的工具，这就给数据挖掘带来了新的发 展平台，w e b 技术与数据挖掘技术相结合的w e b 挖掘应运而生。 文本是w e b 信息最常见的表现形式。据统计，8 0 的信息是以文本的形式存 放的，这些文本包括不同领域的技术文档、博客、论坛的帖子以及电子邮件等。 因此，w e b 文本挖掘成为数据挖掘中一个日益流行而重要的研究课题，是w e b 挖 掘研究的重心。 文本分类和聚类是文本挖掘中的关键技术。传统的文本分类工作由特定领域 的专家人工完成。目前，绝大多数的文本分类工作仍由人工来完成，无论是个人 电子文本的整理还是国际专利文献的分类。人工分类的优点是组织结构清晰，分 类精度高，服务质量好。但是，随着互联网技术的飞速发展，互联网上的电子文 档信息急剧增加，人工分类的缺点就显现出来，比如要求分类人员具有较多的经 验和专门的知识，人为因素影响分类结果，周期长、费用高、效率低，所以人工 分类现在已经不能满足当今社会的发展需要。因此，利用计算机的文本自动分类 和无监督的文本聚类己作为一项具有较大实用价值的关键技术，同益受到重视。 因为在研究领域文本分类都是指文本的自动分类，所以下文中提到的文本分类都 是利用计算机的文本自动分类，不再作区分。 文本分类和聚类有着广泛的应用，在检索系统中，聚类和分类技术可以帮助 用户快速准确地查找到所需信息，提高检索的精度【1 1 ；还可以通过对用户感兴趣的 文档进行聚类分类，从中发现用户的兴趣模式并用于信息过滤和信息主动推荐等 服务【2 】：文本分类聚类技术可以用于文档集合的自动整理与数字图书馆服务【3 4 l 。 5 山东大学硕士学位论文 还可以用于热点主题发现和流行串预警【5 】，快速发现网络中的热点话题并进行追 踪，识别网络中大规模流行的病毒或蠕虫特征，对维护社会和谐以及保护国家安 全具有重要的意义。 中文在构词成句上比英文复杂，且起步较晚，理论研究还不成熟，随着时代 的发展和信息的全球化，互联网上中文信息急剧增加，作用越来越重要，但是从 中文文本中获取知识的技术没有得到相应的发展，因此，研究中文文本聚类分类 技术，提高中文文本聚类和分类的效率和准确率已经成为促进我国经济发展和国 际知识交流的迫切要求，具有重要的现实意义【6 j 。 1 2 国内外研究状况 1 9 8 9 年8 月，在美国人工智能协会举办的专题研讨会上，首次提出基于数据 库的知识发现技术( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。自此数据挖掘成为 国际上数据库和信息决策领域的最前沿的研究方向之一。 上世纪六十年代，国际文本信息处理领域的大师s a l t o ng 提出向量空间模型 ( v s m ：v e c t o rs p a c em o d e l ) 并成功应用于s m a r t 文本分类系统，成为现代意义 上的文本信息处理研究开始的重要标志。 国外对于文本挖掘的研究发展较早，上世纪六十年代就通过专业人员手工编 写分类规则来指导分类，其中最著名的系统是为路透社开发的c o n s t r u e 系统。后 来在文本挖掘中的文本分类技术、关键词的自动获取和半结构化信息提取等信息 抽取的相关领域进行了较为深入的研究，并取得了不少令人瞩目的研究成果1 7 叫。 近年来，国外的文本挖掘研究进展较快，许多技术已经进入实用化阶段，邮 件分类、电子会议、信息过滤等方面取得广泛应用。一些研究机构研究的各种文 本挖掘应用软件也已经在商业领域得到了很好的应用，例如i b m 的文本智能挖掘 机、a u t o n o m y 公司的核心产品c o n c e p t a g e n t s 和m e g a p u t e r 的t e x t a n a l y s t 等。 相对于国外，我国对文本挖掘的研究起步较晚，1 9 9 8 年，我国国家重点基础 研究发展规划首批实施项目中，将文本挖掘的研究列为“图象、语音、自然语言 理解与知识挖掘”中的重要内容。国内对文本挖掘技术的研究机构主要集中在高 等院校、科研院所和信息公司，并且也取得了不错的成果【i 田，例如： 6 山东大学硕士学位论文 ( 1 ) 中科院计算机语言信息工程中心所研究的汉语分词、自然语言接口、句 法分析、语义分析、音字转换等； ( 2 ) 清华大学电子工程系研究的手写汉字识别、汉字识别多分类器集成； ( 3 ) 上海交通大学计算机系研究的语句语义、自然语言模型、构造解释模型、 范例推理等： ( 4 ) 哈尔滨工业大学计算机系研究的自动文摘、手写汉字识别、自动分词等； ( 5 ) 东北大学的词性标注、中文信息自动抽取、汉语文本自动分类模型等。 1 3 文本挖掘的主要研究领域和难点 文本挖掘的主要研究领域包括：文本的表示方法以及模型的建立【1 1 ，1 2 】；针对文 本数据高维性问题的特征提取以及降维方法的研究【1 3 , 1 4 ；针对不同目标所采用的不 同挖掘算法，用以解决文本分类【1 卯、聚类【1 6 j 的l h - j 题；结合自然语言理解领域的基 础进行更深层次语义挖掘的相关研究1 1 7 】等。 文本对象作为非结构化的数据，与传统的结构化数据不同，同时具有高维性 和稀疏性的特点，对文本对象进行挖掘分析时，存在着其特有的挑战。 ( 1 ) 文本对象的高维性 文本集经过预处理后，仍然包括成千上万甚至几十万个特征词，特征词的维 数直接对应着文本矩阵的维数。面对文本矩阵这样的高维数，一般的数据挖掘方 法由于计算量过大或代价高昂而不具有可行性，或者一些在低维数据上运行得很 好的挖掘算法，在性能上和效果上都有很大的下降。因而有必要对现有方法加以 改进以适应高计算量、高资源消耗的文本处理问题；同时还可以研究文本表示的 新方法或者有效的维数约简方法。 ( 2 ) 文本对象的稀疏性 当采用向量空间模型表示文本时，每个文本都是由整个文本集所包含的特征 词进行描述的，由于文本集中通常包含多个主题，每个主题均由不同的特征词子 集来表达，所以对于一个文本来说，它所包含的特征词只是整个文本集的特征词 中很少的一部分，因此文本向量的非零项通常非常少，从而导致了文本表示形式 的高度稀疏性。而稀疏性导致文本对象间的相似度非常低，都接近0 ，相似度趋向 7 山东大学硕士学位论文 于一致。这些对基于相似度的聚类分类算法产生了很大的负面影响，直接影响了 算法的质量与性能。 ( 3 ) 语义问题 中文文本还具有同义词和近义词等特有的自然语言现象。同义词和近义词的 现象是指可以用多种不同的方式来描述同一个主题或者内容。它们的存在极大地 降低了文本聚类的精确率和效率。通过使用潜在语义索引的方法对文本对象进行 处理，可以达到特征词降维和增强语义关联的目的。 ( 4 ) 聚类描述问题 聚类描述是对聚类结果进行描述，使得聚类结果利于用户理解，帮助用户迅 速确认生成的文档类是否相关。 1 4 论文的研究内容和结构 本文主要对中文文本的分类和聚类进行讨论和研究，结构如下： 第一章为本文绪论，介绍了本文的研究背景、国内外的研究现状以及文本挖 掘的主要研究领域和存在的难点。 第二章首先介绍了相关的理论背景，包括数据挖掘、w e b 挖掘、文本挖掘， 然后对本文的主要研究内容文本聚类和文本分类的相关理论做了介绍。 第三章介绍了w e b 文本预处理中的关键技术，以及本文中所采用的相关技术， 包括h t m l 文档解析、中文分词、权重计算、向量空间模型( v s m ) 的建立等，最 终构建了w e b 中文文本的预处理平台，通过该平台可以将w e b 中文文本转化为便 于计算机和挖掘算法执行的文档词项矩阵的形式。 第四章是基于v s m 的中文文本聚类，首先实现了两种常用的聚类算法： k - m e a n s 算法和模糊c 均值算法( f c m ) 。后针对v s m 的高维性和稀疏性的特点， 采用两种方法对中文文档进行聚类：基于子空间的聚类算法和基于语义的奇异值 分解的聚类算法，仿真结果表明这两种算法的效果明显好于传统的k - m e a n s 聚类 算法。 第五章首先介绍了支持向量机( s v m ) 的相关理论知识，然后实现了改进的 s v m 对中文文本的分类，因为支持向量机的惩罚因子和核函数参数的选择对分类 8 山东大学硕士学位论文 的效果有很大影响，所以本文首先用粒子群优化算法优化惩罚因子和核函数参数， 然后利用优化好参数的s v m 对中文文本进行了分类，结果证明这种方法的有效性。 第六章进行了总结和展望。 9 山东大学硕士学位论文 第二章相关理论基础 2 1 数据挖掘综述 数据挖掘是当前国际学术界一项前沿的研究课题，融合了数据库、人工智能、 机器学习、统计学等多个领域的理论知识。数据挖掘( d a t am i n i n g ) 又称为数据 库知识发现，它通常是指从数据源( 如数据库、文本、图片、万维网等) 中探寻 有用的模式或知识的过程。这些模式必须是有用的、有潜在价值的，并且是可以 被理解的【嘲。发现的知识可以用于信息管理、查询优化、决策支持和过程控制等。 数据挖掘过程大致可以分为四个阶段【1 9 j ： ( 1 ) 确定业务对象阶段：清晰地定义出业务对象，认清数据挖掘的目的是数据 挖掘的首要任务。 ( 2 ) 数据准备阶段：确定目标数据，并对原始的目标数据进行数据的选择、净 化( 消除噪声、冗余数据) 等，使其生成过程数据。然后进行转换，主要是降维 ( d i m e n s i o nr e d u c t i o n ) ，为后面的数据挖掘准备好正确的数据。 ( 3 ) 数据挖掘阶段：使用适当的数据挖掘算法对处理过的数据进行分析，进而 得到可能的模式或模型。 ( 4 ) 解释与评估阶段：数据挖掘将获得的信息通过用户可以理解和观察的方式 反馈给用户。 2 1 1 数据挖掘的功能和内容 数据挖掘的主要功能和研究内容有【2 0 】： ( 1 ) 概念描述 概念描述本质上是对某类对象的内涵特征进行概括。概念描述分为特征化描 述和区别性描述。前者是描述目标类数据的一般特征和特性的汇总，后者是将目 标类对象的一般特征与对比类对象的特性进行比较。获得概念描述的方法主要有 以下两种f 2 1 l ：利用更为广义的属性，对所分析数据进行概要总结；对比目标数据 集和数据集的数据特点，并对对比结果给出概要性总结。 ( 2 ) 关联分析 l o 山东大学硕士学位论文 关联分析是从给定的数据集中发现项集之间有趣的关联或相关联系。若两个 或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时 序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网，一般用支持 度和可信度两个阈值来度量两个元素间的相关性。近年来，提出了许多高效的关 联规则挖掘方法，如：a p r i o r i 算法、b i n n i n g 方法等。 ( 3 ) 聚类 将物理或抽象对象的集合分组为由类似的对象组成的多个类的过程被称为聚 类。由聚类所生成的簇是一组数据对象的集合，同一个簇中的对象彼此相似，不 同簇中的对象相异。聚类是在数据对象没有预定类别的i j 提下，根据类内相似性 最大化、类间相似性最小化的原则，自动对数据分类，是无监督的学习。 ( 4 ) 分类 分类是根据数据集的特点构造一个分类器，然后利用分类器给未知类别的样 本赋予类别的过程。构造分类器的过程一般分为训练和测试两个步骤。在训练阶 段，建立模型来描述一个预先确定的数据类或概念的集合，即进行有监督的学习。 在测试阶段，首先是采用测试数据集检验模型的准确度，如果达到预定要求，则 可将模型用于预测未来数据对象的类别嘲。 ( 5 ) 偏差检测 偏差检测就是对数据库中的偏差数据进行检测和分析。数据库中的数据常有 一些异常记录，在某些特征上与数据库中的大部分数据有显著的不同，这些数据 就是偏差，也叫孤立点。偏差检测方法主要有基于统计的方法、基于距离的方法 和基于偏移的方法。孤立点数据的发现可以在信用卡使用、金融欺诈、医学数据 分析等领域应用幽1 。 ( 6 ) 预测 预测是从历史数据中找出变化规律、建立模型，并由此模型对新的样本数据 类别及特征进行预测。一般意义上的预测是指利用回归方法预测连续值或有序值。 预测关心的是精度和不确定性，通常用预测方差来度量。 ( 7 ) 时序模式 时序模式是指通过时间序列搜索出重复发生概率较高的模式。与回归一样， 它也是用已知的数据预测未来的值，但这些数据的区别是数据变量所处的时间点 山东大学硕士学位论文 不同。 2 1 2 数据挖掘的关键技术 数据挖掘的关键技术是模式识别和关系识别的算法，许多算法源于数据库理 论、统计学、人工智能和机器学习等研究领域。常用的数据挖掘技术大致可以分 为以下几种： ( 1 ) 统计方法 统计技术是处理大量数据的有效方法，利用统计技术可以更好地对数据进行 分析和挖掘。统计方法处理过程可以分为三个阶段：搜集数据阶段、分析数据阶 段、进行推理阶段。 常见的统计方法有回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、 f i s h e r 判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类) 以及探索性分析 ( 主元分析法、相关分析法等) 。利用这些技术可以检查那些异常形式的数据，然 后利用各种统计模型和数学模型解释这些数据，解释隐藏在这些数据背后的市场 规律和商业机会。 ( 2 ) 模糊集方法 模糊集方法是利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊 模式识别和模糊聚类分析的方法 2 4 1 ，是一种应用较早的处理不确定性问题的有效 方法。系统的复杂性越高，模糊性就越强。模糊集合论是用隶属度来刻画模糊事 物的办此办彼性。 在数据挖掘中，使用模糊集方法可以对已挖掘的大量关联规则的有用性、兴 趣度等进行评判，也可用于分类、聚类等挖掘任务。 ( 3 ) 支持向量机 支持向量机( s v m ) 是v a p n i k 等根据统计学习理论( s l t ) 提出的一种新的 机器学习方法。支持向量机建立在统计学习理论的v c 维理论和结构风险最小化原 理的基础上，根据有限样本信息在模型复杂性与学习能力之间寻找最佳折中，以 期获得最好的推广能力圆。 支持向量机较好地解决了小样本学习的问题：将低维的原始空间映射到高维 的特征空间，把非线性问题转化为线性问题，同时又采用核函数的方法，巧妙地 1 2 山东大学硕士学位论文 避开了高维空问的复杂运算，使算法的实现成为可能。它具有理论完备、适应性 强、全局优化、训练时间短和推广性能好等优点，已经成为目前国内外研究的一 个热点。 ( 4 ) 粗糙集方法 粗糙集理论作为一种处理具有信息不确定、不精确、不完善系统的新数学工 具，不需要预先给定某些属性的数量描述，而是直接从给定问题的描述集合出发， 找出该问题的内在规律，是目前使用较多的一种归纳学习方法，也是解决“数量 庞杂，信息稀缺”的一种有效方法【2 们。其基本原理是基于等价类的思想，而这种 等价类中的元素在粗糙集中被视为不可区分的。 和模糊集合需要指定成员隶属度不同，粗糙集的成员是客观计算的，只和已 知数据有关，从而避免了主观因素的影响。粗糙集的数学基础是集合论，难以直 接处理连续的属性，而现实决策表中的连续属性是普遍存在的，因此连续属性的 离散化是制约粗糙集理论实用化的难点之一。 ( 5 ) 贝叶斯网络 贝叶斯网络是用来表示变量集合连接概率的图形模式，它提供了一种自然地 表示因果信息的方法，用来发现数据问的潜在关系鲫。在这个网络中，用节点表 示变量，有向边表示变量问的依赖关系。 贝叶斯网络适合处理不完整数据集问题，可以发现数据间的因果关系，可以 综合先验信息( 领域知识) 和样本信息，在样本难以获得或者代价高昂时特别有 用。可以预见，在数据挖掘和知识发现中，贝叶斯网络将成为一个有力的工具。 ( 6 ) 机器学习方法 机器学习是人工智能研究中最早的课题之一，也是人工智能中最具有智能特 征和最前沿的研究课题之一。机器学习是计算机获取知识的重要途径和人工智能 的重要标志，是一门研究怎样用计算机来模拟或实现人类学习活动的学科。 目前较为常用的机器学习方法有规则归纳、决策树、神经网络技术以及基于 案例的推理等。 ( 7 ) 生物智能算法 生物智能算法在优化与搜索方面应用前景广阔，在数据挖掘中常把任务表示 成优化或搜索问题，利用生物智能算法找到最优解或次优解。生物智能算法主要 1 3 山东大学硕士学位论文 包括遗传算法、蚁群算法、粒子群优化算法及鱼群算法等。 2 2w e b 挖掘概述 w e b 挖掘是数据挖掘与w e b 技术相结合的一种技术，从本质上来说，w e b 挖掘可以被认为是数据挖掘在w e b 上的应用。 w e b 挖掘是使用数据挖掘技术自动地从w e b 文档和w e b 活动中发现和提取 潜在有用的信息和知识的技术瞄l ，它以从w e b 上挖掘有用知识为目标，以数据挖 掘、文本挖掘、多媒体挖掘为基础，并综合运用计算机网络、数据库与数据仓储、 人工智能、信息检索、可视化、自然语言理解等技术，将传统的数据挖掘技术与 w e b 结合起来。一般的将w e b 挖掘定义为【2 9 】： 定义1 ：w e b 数据挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。 如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到输出的一 个映射刍：c p 。 2 2 1w e b 数据的特点 w e b 上数据的特点主要包括以下几点【3 0 l ： ( 1 ) 数据量巨大、动态性强，数据类型复杂多样 万维网上的数据量非常巨大，并快速更新。w e b 上包含了各种信息和资源， 有文本数据、超文本数据、图表、图像、音频数据和视频数据等多种类型的数据。 ( 2 ) 异构数据库环境 w e b 上每一个站点是一个数据源，每一个站点的信息和组织都不一样，所以 每个数据源都是异构的，因此构成了一个巨大的异构数据库环境。 ( 3 ) 半结构化的数据结构 w e b 数据是半结构化或非结构化的，不是计算机或者数据挖掘算法所能理解 的形式，通常数据挖掘的对象是数据库中的结构化数据，并利用关系表格等存储 结构来发现知识，因此有些数据挖掘算法并不适用于w e b 挖掘，即使可用也需要 首先对w e b 数据进行预处理。 这样，对w e b 数据进行预处理，或者开发新的w e b 挖掘技术，便成为w e b 挖掘研究的重点。 1 4 山东大学硕士学位论文 2 2 2w e b 挖掘分类 w e b 上的数据主要包括以下几种1 3 i 】： ( 1 ) w e b 页面数据：w e b 页面数据包含文本和多媒体信息( 图像、语音、图片) 。 ( 2 ) w e b 页面超链接数据：这类数据描述了文档之间的联系，同时为用户浏览 w e b 站点提供了可用的路径。 ( 3 ) 在线信息与服务器同志数据：这是传统的关系数据库结构数据，如客户登 记信息等。用户浏览w e b 服务器时，产生三种类型的r 志文件s e r v e rl o g s ，e r r o r l o g s 和c o o k i el o g s ，用于记录用户访问的基本情况。 根据处理对象的不同，w e b 挖掘一般分为三大类【3 2 】：w e b 内容挖掘( w e b c o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 、w e b 日志挖掘( w e b u s a g em i n i n g ，也可以称为w e b 访问信息挖掘) 。如下图2 1 所示： ( 1 ) w e b 内容挖掘 w e b 内容挖掘就是从网页内容中抽取有用的信息和知识的过程，根据信息来 源是文本还是多媒体，可以分为w e b 文本挖掘和w e b 多媒体挖掘。 w e b 内容挖掘主要应用于信息过滤、知识抽取、网络文档分类等方面。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘是从表征w e b 结构的超链接关系中寻找有用的知识，例如从链 接中找出重要网页，这是搜索引擎采用的一种重要技术，我们也可以挖掘具有共 同兴趣的用户社区等。 目l i i ，最主要的两种w e b 结构挖掘的算法是p a g e r a n k 算法和h i t s 算法。 ( 3 ) w e b 同志挖掘 w e b 同志挖掘也称为w e b 使用挖掘，w e b 同志挖掘是从记录每位用户点击 情况的使用同志中挖掘用户的访问模式。 1 5 山东大学硕士学位论文 w e b 挖掘 土 w e b 内容挖掘w e b 日志挖掘 w e b 结构挖掘 l 文本挖掬if多媒体挖掘 超链接挖掘 i 内部结构挖掘 il 1 r 服务器日志挖掘、 错误日志挖掘 c o o k i e 日志挖掘 图2 1w e b 挖掘的分类 2 3w e b 文本挖掘 w e b 文本挖掘是指针对包括w e b 页面内容、页面之间的结构、用户访问信息、 电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以发现有用的知识来帮 助人们从大量w e b 文档集合中发现隐含的模式，也即从w e b 信息资源中提取潜 在的、有价值的知识的过程1 3 3 1 ，是w e b 挖掘中重要的技术领域。 由于w e b 文本是半结构化或非结构化的，不是机器所能理解的形式，使得有 些数据挖掘技术并不适用于w e b 挖掘，或者不能直接应用到w e b 挖掘中。因而， 对w e b 文本进行预处理，提取该文本的特征以便于数据挖掘算法的应用，或者开 发新的w e b 文本挖掘技术，便成为w e b 文本挖掘研究的重点。 2 3 1w e b 文本挖掘的过程 文本挖掘过程由文本收集、文本预处理、特征提取、文本挖掘、模式生成等 步骤组成，如图2 2 中所示。 1 6 山东大学硕士学位论文 图2 2 文本挖捌的过程 1 ) i n t e r n e t 上的大部分网页是h t m l 文档或x m l 文档，文本的预处理首先要 从网页的内容中去掉跟文本挖掘无关的标记，将其转换成统一格式的t x t 文本； 2 ) 对纯文本进行分词处理，把文本切分成词条或者单个字； 3 ) 由于中文文本使用的是人类的自然语言，计算机是无法理解的，所以必须 将中文文本表示成计算机能够理解的形式，目前用来文本特征表示的方法很多， 向量空间模型( v s m ) 是最近几年用的较多且效果较好的方法之一。 4 ) 文本信息量大，所以文本向量空间的维数特别高，为了提高运行效率，必 须进行特征提取，对特征向量进行降维处理。将一些各个类别都普遍存在的，对 分类贡献小的词条去除。通过适当的权重计算算法计算出每个特征词的权值，仅 保留权值较高的词条作为文本的特征项。 5 ) 在完成特征向量降