（计算机应用技术专业论文）web信息提取及知识发现方法研究.pdf

台肥工业大学硬士学位论文 摘娄 摘( 要 本文燕要研究了w 磅信息的掇墩及数据痒巾静翔识发瑗方浚。论文蘸童要 内容有； 首先，本文广泛练合骥牧了国内步 有关数据挖掘p 购与翔识发现a 国d ) 穷 面斡学术研究成果，弗撮据所研究豹课题，锌对数据挖掘在w e b 上的应霭，奔 绍了其繁本的方法、步骤、算法以及所面临的闻题等。w e b 作为巨大的数据源， 跌w 曲巾提取翔识是零文磅究的一个主要问题。本文讨论了对予h t m l 趸磷， 铡餍信意提取技术，将带结构纯数据转纯为结檎健数据。存储予传统的数据库中， 利用基于数据库的数据挖掘算法提取有用的知识，这是一种离线式w e b 数据挖 握方式；贯一静是在线方式，将w e b 信怠提取技朱号数据挖掇嚣洼结合茭一体， 直接对掇淑的数据避稃挖掘。 其次，阐述从数据库中提取有用知识的预处瑕过程和分类模式挖掘算法。在 数据熬预楚理方委，圭黉磅究疆集壤澹、数据聚类、概念瓣、滋誊耱等颈处瑷方 法。在挖擒模型与算法的选取中，分类是一种重瑟的知识发蕊方法，它能戳祷涪 的模型预测新到达对致的类别。主臻介绍基于粗紫理论的分类规则提取。此外， 峦予w e b 上豹数据嫠塞楚一典型静麓态数据嚣，零文还瑷努娄艇舞l 挖掘为妻题 讨论动态数据环境下的决策树构造方法。 最后，在上述理论方法研究的鏊础上，研究开发了农产品市场行情信息的提 壤与知谈发瑗系统。 关键词：数据挖掘商吣知孥发挚a 跫d 哐l ! o 息提取、w f a p p e r 、数据预处理、 分类摸式、褪集、决繁事孽、农邋髫媾 “ 舍髓童堑大学硬士学键论文 趟瓷莲疑鳗s t 艇st h e w s s t u d m si n f o r m a t i o nr e t r i e v a la n dk n o w l e d g ed i s c o v e r ym e t h o d sf r o m 鬻两骚砖m a i nc o n t e n ti s 勰f o l l o w s ： f i r s to fa l l _ t h i st h e s i ss t m l i e sa s da b s o r b sal o to fi n t e m a ta n di n t e r n a t i o n a l r e s e a r c ha c m e v e m e m so nd a t am i n i n g a n dk n c 砒d g ed i s c o v e r yi nd a t a b a s e $ 晖d 妫；a c c o r d i n gt ot h ep r a c t i c a lp r o b t e m , i te x p l i c - 船l h a t1 糙a p p l i c a t i o no f d a t a m i n i n g i nw e b , i n c l u d i n gi t sb a s i c 强曙氆翻每s t e p s , 霜霉圉溉sa n d f a c i n gc h a l l e n g e s a sav a s td a t as o l l r ( 跫, i nt h i st h e s i s , i tj s 嚣m a i np r o b l c r at h a tr e t r i e v i n gi n f o r m a t i o n f r o mw 曲t h e r ea r et w o w a y so f r e t r i e v i n gi n f o r m a t i o n , o n e i so f f - l i n ed a t am i n i n g , n a m e l y , t ot h eh t m l w e b w ec a nc h a n g e 龇s e m i - s t r u c t u r a ld a t ai n t os t r u c t u r a ld a t a b yt h et e c h n o l o g yo fr e t r i e v i n g 攮羲茸珏鞠翩a n ds t o r e i ti n t ot h et r a d i t i o n a ld a t a b a s e , t h e nk n o w l e d g ew i l lb ed i s c o v e r e db v 基瞎硼蒯d 赫瓣b a s e d a l g o r i t h m s ；t h e o t h e r i so n - l i n ed a t am i n i n g , t h a ti st oc o m b i n et h et e c h n o l o g yo fr e t r i e v i n gi n f o r m a t i o n f r o mw e ba n dt h ea l g o r i t h m so f d a t a m i 血n 舀t h e n t oi 砌e v e k n o w l e d g ed i r e c t l y s e c o n d l y , i t s t u d i e st h ed a t ap r e p r o c e s sa n dt h em i n i n ga l g o r i t h m sb a s e d c l a s s i f i c a t i o np a t t e r ni no r d e rt of i n dk n o w l e d g e a tt h ea s p e c to f p r e p r o c e s s , s o m e p r e p r o c e s sm e t h o d sa g es t u d i e da n di m p r o v e d ，i n c l n d i n gr o u g hs e t ，d a t ac l u s t e r i n g , c o n c e p th i e r a r c h i e sa n dl a n g u a g ef i e l d , e t c a tt h ea s p e c to fm i n i n ga l g o r i t h m s , c l a s s i f i c a t i o ni sa l li m p o r t a g r tk n o w l e d g ed i s c o v e r ym e t h o d i t u s gas i m p l em o d e l t op r e d i c tt h ec l a s so f n e w s a m p l e 。m o r e o v e r , b o c a l i s ew e b i sat y p i c a ld y n a m i cd a t a s o t l 黼, t h i st h e s i ss t u d i e sh o w t oc o n s t r u c tt h ed e c i s i o nt r e ea n dt h ec l a s s i f i c a t i o n r u l e si nt h e d y n a m i cd a t a e n v i r o n m e n t f i n a l l y , b a s e do f t h es t u d yo f t h e o r ya n d m e t h o d s , a 掣s l e mt h a tr e t r i e v i n gt h e i n f o r m a t i o na n dm i n i n g k n o w l e d g ef r o ma g r i c u l t u r ep r o d u c tp r i c e h a sa l r e a d y d e v e l o p e d k e y w o r d s ：d a t am i n i n g k n o w l e d g ed i s c o v e r y i n d a t a b a s e s 嘲d d ) ， i n f o r m a t i o nr e t r i e v a l ，w r a p p e r , d a t ap r e p r o c e s s , c l a s s i f i c a t i o np a t t e r n , r o u g hs e t , d e c i s i o nt r y ) a g r i c u l t o r e p r o d u c tp r i c e 独创性声明 拳入声麴掰呈交鹣学往谂交是零a 在鼯稀稽簿下进行瓣研究汪豫及取褥韵研 究_ 箴栗撼筏蘼秘，豫了文中特嗣瓣以标注释致谢躺地焘辩，埝文书不包客其他 人b 缎发寝鲢撰写过的礤究成槊，璁誉包食为获锶鲤芝数：二缓冀蛾教 育瓠襁妻冬学证或证书藤捷羟l 迸瓣糖辩与巍一辩正榫静丽忠对零轿究所徽翡强何 责黻妁已在论文中搀了爨稿辩说鹈字争表示谶意 学擅论文镎著鸯唧季轴， 签字日艘：2 掌辣年 月夥翔 学位论文版权使用授权书 零学链谂文襻赣竞垒了鳞i 挫缝型星。有关僚螯、】键孺学德论文虢栽定， 有援傺驽簿秘i l l 容裔关舔门或瓤鞫送交论文鹳复印张和激擞，允诲论文鞭蠢鼹袒 1 酱t l t 本人授权钠查! 墼薹可以将学艇论文她全部藏部分内褰编入凑关毂揠 瘁瓣稃检裳。胃瓣采掰影e l i 、绻祭磊翅播等整绸筝段保存、j 躺擎位论文 傺密的学位论文在解窿詹适用零攫较书) 学链谂交槔豢签名：弘彳静1 t 签字臼勰轴瓣每f 只彭e l 学挝谂文佟豢毕她麟去翔： 工体革往： 逦讯璃缝： 导拜螯名：互缝 签字搿怒：弘蛭筝1 1 只五擎毽 电话l 瓤绽： 合肥工业大学硕士学位论文 致谢 致谢 我非常感谢导师王浩教授将我带入这个领域。在做硕士论文之前，数据挖掘 与知识发现对我来说还比较陌生，在王老师的悉心指导和严格要求下，我如饥似 渴地在数据挖掘学科里吸取点点滴滴的营养。导师严谨地治学态度和对学生的严 格要求将使我终生受益。 在这一年多的学习生活中，我尽量参加由王浩老师和胡学钢老师组织的研究 生研讨班，在研讨班中，我逐渐对数据挖掘有了初步的认识，这对我们这些在职 参加研究生班学习的学生来说，的确是一条迅速迈入数据挖掘大门的捷径。同时， 我也对科研选题方法和步骤有了一定的认识，这是我以前所缺乏的，感谢研讨班 的同学们次次精彩地发言和积极地讨论，感谢胡学钢老师和王浩老师所出的点 评与指导。 我还要感谢我所在的安徽农业大学信息与计算机学院计算机系的同事们，他 们给了许多论文上的建议和帮助，并帮我合理安排和承担了部分教学工作，使我 有更多的时间和精力参加研究生班的学习，通过申请学位的考试，并且完成论文。 感谢工大所有给我授课的老师和班主任老师。他们热情地关怀和帮助让我感 觉到无比地温暖，他们严谨地治学和教学态度给我留下了深刻地印象。 合肥工业大学硕士学位论文第一章k d d 概谜 第一章k d d 概述 1 1k d d 的产生及发展概况 信息爆炸是当今数字化社会面临的一个巨大挑战，科学上对先进的现代化观 测仪器的使用，加上先进的自动数据生成和采集工具，使得人们所拥有的数据量 急剧增大。例如，商业上条形码的普遍使用，使得每天很多行业都积累了数以万 计的顾客购买数据，各种同步卫星每小时传回地球的遥感图像数据就达5 0 千兆 字节。同时，i n t e m e t 的迅猛发展使得网络上的各种资源异常丰富，在其中进行 信息的查找就如大海捞针【l l 。 数据库系统提供了对这些数据的管理和简单的处理功能，人们可以在这些数 据之上进行商业分析和科学研究，但如此庞大的数据对人工处理来说是非常困难 的，人们需要能够对数据进行较高层次的处理技术，从中找出规律和模式，毗帮 助人们更好的利用数据进行决策和研究。而这些功能对传统的数据库管理系统来 说是无法做到的。同时数据量的爆炸性增长也使得传统的手工处理方法变得不切 实际，因此需要采用自动化程度更高、效率更高的数据处理方法帮助人们更高效 地进行数据分析。而且由于信息繁杂，在由人工对数据进行处理过程中，很难找 出关于数据的较为全面的信息，这样许多有用的信息仍然隐含在数据中而不能被 发现和利用，造成资源的浪费。面对数据和数据库的飞速增长，人们迫切地感到 需要新的技术和工具以便从大量数据中智能地、自动地发现知识【8 】。与此同时， 人工智能领域的个分支机器学习的研究自5 0 年代开始阱来也取得了很大进 展。不同时期机器学习的研究途径和目的也不尽相同，一般大致可分为三个阶段： 神经模型和决策理论；概念符号获取及知识加强；领域专用学习。根据人类学习的 不同模式人们提出了很多机器学习方法，如：实例学习、观察和发现学习、神经 网络和遗传算法等等。其中某些常用且较成熟的算法己被人们运用于实际的应用 系统及智能计算机的设计和实现中。 随着数据库技术和机器学习技术的发展，数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e , k d d ) 和数据挖掘( d a mm i n i n g , d m ) 应运而生【5 l 。机器学 习是用计算机模拟人类学习的一门科学，始于六十年代末，真正发展是在七十年 代末。1 9 8 0 年，在美国召开了第一届国际机器学习研讨会，1 9 8 4 年，机器学习 杂志问世。我国也很快跟上了国际步伐，在1 9 8 7 年召开了第一届全国机器学习 合肥工业太学硕士学位论文 第一章k d d 概述 研讨会，1 9 8 9 年成立了全国机器学习理事会。机器学习通过对数据对象之河关系 的分析可以提取出隐含在数据中的模式，即知识。正是由于实际工作的需要以及 相关技术的发展，将机器学习应用于大型数据库中，即数据库中的知识发现( k d d ) 逐渐发展起来。 1 9 8 9 年8 月在美国底特律市召开的第1 1 届人工智能联合会议的专题讨论会 暨第一届k d d 学术会议上，正式形成了k d d 一词。国际k d d 学术会议 6 1 起初 每两年召开一次，1 9 9 3 年以后每年召开一次。1 9 9 5 年以后每年召开一次知识发 现与数据挖掘国际学术大会。迄今为止，美国人工智能协会主办的k d d 国际研 讨会已召开了7 次，人数由二三十人发展到七八百人，论文收录比例从2 ：l 到 6 ：l ，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术 的集成，以及多种学科之间的相互渗透。其他内容的专题会议也将数据挖掘和知 识发现列为议题之一。目前，数据挖掘不仅被许多研究人员看作是数据库系统和 机器学习方面一个重要的研究课题，而且被许多工商界人士看作是一个能带来巨 大回报的重要领域1 0 】。从数据库中发现知识可以用在信息管理、查询响应、决策 支持、过程控制等许多方面。 1 2k d d 的定义 k d d 这个概念自1 9 8 9 年以来，定义几经变动，其中得到最广泛认可的是 1 9 9 6 年，由f a y y a d 、p i a t e t s k ys h a p i r o r 和a m y t h 给出的： k d d 是从数据集中识别出有效的、新颖的、潜在有用的且最终可理解的模 式的非平凡过程，这种处理过程是一种高级的处理过程【7 1 。其中： “数据集”是一组事实f ( 如关系数据库中的记录) ，它记录了事物有关方面 的原始信息，如学生档案数据，商场销售数据，银行客户信息。由于k d d 处理 的数据是从现实世界中来的，因而并不能保证所有的数据都规范，一般需要对数 据进行预处理，使之适合于知识发现。 “模式”是一个用语言l 来表示的一个表达式e ，它可阻用来描述数据集f 中数据的特征。只有当表达式e 比列举e 所描述的数据子集f e 中所有元素的方 法更为简单时，e 才能称的上是一个模式。模式可以看作是从大量枚举事实中上 升提炼出来的知识，它给出了数据的特征或数据之间的关系，是对数据包含的信 合肥工业大学硕士学位论文 第一章k i ) d 概述 息更抽象的描述。 “过程”在k d d 中通常是指一个多步骤的对大量数据进行分析的过程，涉 及数据预处理、模式提取、知识评价以及反复求精等步骤。作为核心的模式提取 步骤往往需要经过多次的反复，通过对相关数据的再处理及算法过程的优化不 断提高挖掘效率。所谓非平凡是指整个过程应该具有一定程度的智能性、自动性。 “有效性”指发现的模式应该对特定的应用领域中的新数据在一定确信度上 是成立的。否则k d d 就毫无作用。 “新颖性”是指通过k d d 从当前数据中发现的模式是从前未知的，新颖的。 虽然知识发现可以对已有的知识进行验证，但发现新的知识就更为重要。 “潜在有用的”是指发现的知识应该是有意义的，具有一定的实用价值和应 用前景，如用于决策支持系统里可提高经济效益。并能够根据发现的问题对挖掘 策略进行反复修改，从而得到更精确的知识。 “可理解的”是因为k d d 的目标就是将数据中隐舍的模式提取出来，从而 帮助人们的使用。但一般知识学习算法所得到的模式对于普通用户来说很难理 解，更不用说是使用。因此，k d d 不仅能将知识提取出来，更应该以直观易用 的方式将知识呈现给用户，至少要作到领域专家可以理解，例如：“i f t h e n ” 的形式。 应当指出的是现在许多人认为，数据挖掘是k d d 的其中一个核心的步骤， 它将发现数据中隐藏的模式，但除此之外，k d d 中还包括数据预处理、模式评 估和知识表示等环节。然而，在产业界、媒体和数据库研究者，“数据挖掘”e e 较长的术语“数据库中的知识发现”更流行。而且本文的主要目的是将数据库中 的知识发现技术应用于w e b 领域，即：w e b 挖掘，所以选用术语“数据挖掘”。 数据挖掘的广义观点嘲是：从存放在数据库、数据仓库或其它信息库中的大量数 据挖掘有趣知识的过程。 1 3 数据挖掘的基本过程 数据挖掘的主要目标是从大型数据集中获取知识，这就决定了它不可能是简 单将数据放在一个黑匣子里就能获得知识的封闭过程，而是有许多步骤相互连 接，反复进行人机交互的过程。数据挖掘过程一般包括问题定义、数据收集、数 合肥工业太学硬士学位论文 第一常k d d 擞避 据预楚褒、数据挖摇、翔谖谨赞，辩滚终隧霆形识瓣薅户界霹形式爨窝耀户。盘l 霭1 1 疑鹾。 鬻1 1 数掇挖掘盼娃理溉程 l 、问题定义 涛骥缝定义窭鼗势溺越，谖瓣绦攥豹嚣戆楚熬撵挖撼爨熏簧步，毅糕动 了整个数据挖掘过程，程很犬的裰麟上决定着数据挖掘的效果甚至成败遮阶 段通常需骤有两部分的人员参蹄：数据挖掘分析人员和领域专家。他们栩驻粼龠。 共两竞蔽晦蓬定义。 2 、数据l | 雯集 攫攥霆义羹藏题嚣麓户懿爨袋逡联爱弯与叠磐辩象奏关豹逶蘧予数据携攘 翡数囊。霾集嚣鼗蠢豁颓考虑粼溅下鬼争方嚣：数据瓷式。遥霉特惠黯接攘算 法只能使用特定的数攥格式，溺忿必须进行据应的格式转换。国提取婀数锻瓣具 有代表性。各个类别的数据猩槭帛特布上要符合实黼；情况。 只霈选辑与特定挖 掘任务羲关熬震往。救爨簧瓣数撩黪存入嚣标数懿痒，露票将数据挖糕攘零疲瓣 于i n t e r n e t ，也就是所谓的w e b 摭搠，其数据可以来自服务器( w e b 服务器，代 理服务器) 和客户端的记录文件、w e b 文档的内嚣、w e b 结构簿。 3 、鼗攥鞭楚理 羧糕熬握主蘧获整耩数辫黪审攮袋摇美瓣数攘，荠鼹数撵邂锊鞭麓黑，逶过 程关毪奔耩去臻趸余震缝，捺狳噪声鼗攥，毒 蔗缺豢鼗器，透露数豢鬃宠蘩渡、 台黯董照支学硬圭学技 宅文第一攀k d d 素逮 毁性检验，以及数据的归化、离散化处理等，转换成滚合特定挖攒算法的数 据掇发劳形成挖撅数据库。特别注意的是，涞自于w e b 的数据是半结构优或根 本冤结构，因梵遮个阶段魏任务非常繁杂，往往占整个w 砖挖掘工捧爨的6 0 以上。 4 、确定数据挖掘的蠢标及算法 掇话使用瀚蒙求确定数据挖掘发现翔谖酶类鍪，瓤褥选择舍逶酌知识发现 算法，包括选取合适的模型和参数，并使得知识发现算法和整个k d d 的评判标 准樱一致。同时，可戳通过人橇交互壶专家辕入感兴趣熬知识，指导数掇的挖握 方向，减少挖掘的盲耳性。 5 、数据挖掘 运尾选定瓣数据挖掘算法，放数据孛掇取感兴趣瓣翔识，这些知识可以露 一种特定豹方式袭示或使霜一撩常用豹表承方式，如产镦袁规鲻等形式。 6 、知识评价 这一过程妻蘩矮子对嚣获褥豹燕熨送橙徐篷评定戥蔽定褥到夔戴则是否存 入麓础知识库。主要是通过人机交互过程由专家依靠经瀚来评价，为此黉将发现 的婀识采用易于理解的方式，如；可视化技术表示出来。 1 4 敷据挖撼的分类 从数据挖掘的不同角度可以得到不同的分类标准，常见的有以下几种分类标 准：挖握任务，拣援对象，挖攘方法。辗撵羧攘黠象是盼么撵的数据撵磁暖鲻分 成不同的挖掘种蒜，一般有关藤数据库、面向对象韵数摇库、空间数据库、对态 数据库、事务数据库、多媒体数据库、异质数据库、遗产数据库和环球网w e b 效鬃瘁等。妇扶笑系数撰痒撼糖知谖茨关系数据挖掘。鬏餐挖掘方法霹凝臻豹努 为：机器学习法、统计方法、神经网络方法、数据库方法等。下面我们介绍目前 用的最广泛的根据挖掘任务分类1 0 l 的情况。 1 、糍念箍述 概念描述就怒对某类对象的内涵进行描述，并概括这攥对象的有关特征。概 念描述分为特征性描述和区别性摇述，前者撒述某类对象的共同特征，聪者描述 零潮类对象之嚣瓣嚣裂；生藏令类豹特鬣羧猛邃哭涉及渡类对象孛爨蠢对象豹 台瓣王整天学疆学彀论文慕一蕈k d d 攘述 共饿。生成区别慷播述的方法缀旁，如决繁树方法、遗传葵演等。 2 、荚联努析 熬鬟关联爨数据箨孛存寇粒一爽萋要瓣雨禳获魂豹麴识。麓嚣枣或多个交藿 的撒德之间存在策种溉律性，勰称为关联。装联w 分为简单兼联、时序荧联、因 果关联。关联分掇鹣隧蛉是找溅数爨瘁孛爨藏熬关联瞬。蠢融辨不知道数攥麟孛 数瓣瓣焚联丞数，鞭靛翔遵瞧怒不确跫熬，黧鼗荚鼗势辑黧域熬簸裂带蠢霹痿凌。 3 、聚搽分析 数懿艨中懿诞最可装纯分必一曩鞭旁豢义豹子集，帮豢粪。蘩类增强了天稻 对客蕊瑷实豹认识，憩糕念鬟遴窝镶差分辨靛毙决象搏。爨豢技零圭簧穗藜转缓 的横浅识剐方法和数学分类学。 4 、分类碧鞋疆溅 分类楚一个羧趱撩浚势送努数撵类域橇念魏搂塑或醺数，疆矮慧移谴璎攘 型预测擞标记未知的对象类。鼯出模型是基予对训练数据集( 即其类标记已知盼 数豢黠蒙瓣努爨。 5 、痃羹壤式 序贯模式数据挖搠是与关联规则数据挖撅幅类似的一个熏骤问题，现在爵缝 广涎瘦爱予羧枣波动、垒产滚疆动态蘧豫，瓣学蜜验、嚣攀疗鬟努撬等方瑟。毫 强溺静爨鼗攥之麓在瓣瓣主豹滚嚣羧。 6 、偏差输测 数爨箨串懿数舞黎骞一些努露诞豢，获数器露串疆潮这些谈差黎骞窳义。编 差篷耩缀多灌在鹣翔浚，蘩分类巾豹爱零实穰、零溃罡蕊鲷熬黪铡、麓灏蘩莱譬 模型预测值的偏麓、爨俊随时问的黛化等。偏照梭测的基本方法整，寻找观测结 果每参鬻壤乏弱簿意义戆差弱。 1 5 撤瞩挽摇的商法和技术 1 、入忑棒经题络“1 糖爨豢瑾荐缀麓终鳍拣懿 线形溪溅攘爨，避避学习滋褥摸蓑浚期。窀璐 辨模溅和h e b b 学习规则为基础，蘸藏了前馈式嘲络、反馈式嘲络、自缀缀网络 三大炎多释襻经瓣绦摸型。它稍分裂惩予分类、爨类、特糕发瓒、瑗测敷模式谖 合l g 王业太学壤士学位论文第章k d d 壤述 别。神经网络的知识体现在网络连援的权值上，是个分布筑矩阵结构；神缀网 络鹃学习体糯在神缀两络袄值的逐步调整上，包括葳复迭代蠛累蕊计算。 2 、决策树 利用信息论中的信息增菔寻找数据库中巢有最大信息量的字段，建立决策树 豹一个结点，再摄摄字段豹不同取攥建立辩蛇分支；在每个分支子集孛重复建立 树的下层结点和分支的过稷，可建立决策树。树的生长过程是不断的把数据谶行 切分熬过程，每次螺势对应一令淹鬟，遵对袋若一令肇点。辩每夸穗努都要黎分 成的组之间的“差异j 眨大。 在螽浚工程锈域，决策树是一种篱擎静翔谈表示方法，它冒褥事蠲逐步分成 不同类别，崴观、易于理解。决策树霹丁以用于分析数据，同样也可以用来做预测。 国际上最裔影响和屠早的决策树方法是q u i n l a n 研究的i d 3 方法数据精睦 太窀嗷聚越甄在i d 3 方法鹊基础上，螽人又发展了务耪决繁树方法。 3 、覆盖正倒、排斥反例方法 宅是剥耀覆羲掰膏歪镄、捧嚣所有爱键豹愚憋来寻援援蘩。魄较燕塑 的肖m i c h a l s k i 的a q i l 方法、洪家荣改进的a q l 5 方法，以及洪家荣的a e 5 方 法。 a q 系列妁核心算法怒，在正捌集中任选一个釉示到反倒集中逐个比 较，时字段取值构成的选择子相容贝j j 舍巍相斥则保留。按此思想循环所有 垂铡秘示接怒到燕绸集瓣趣剽。a e 系列方法楚弱扩张矩薄塞建成媳 4 、糨集( r o u g hs e t 谪法 在鼗蠢瘁中，将行元素着藏对象，嗣嚣素是瓣往努两条终嚣牲窝羧蒙 属饿) 。等价关系r 定义为不同对象在某个( 或几个) 属性上取值相凰这些 满慧等价关系的对象组成静集合称为该簿赞关系r 酶等价类。条俘属馥上 豹等价类e 与决策麟性上的等价类y 之间礴三种情况：下近似：y 包含e ； 上近似：y 和e 的交非垫无关：y 和e 的交为空。对下近似建立确寇性 规则，对上避 盈建立不确定蛙援粼( 含霹绩度) | 慰无关臻嚣不狂在授粥e 5 概念树方法 数据瘴巾记录瓣霾性譬段接l 燕类方式送霉弦象，建巍起寒熬层次续糖 称为概念树。如“城市”概念树酌最下层是具体市名或凝名( 如长沙、南京 等它静纛接上屡是省名( 螽游鬻、江苏簿) ，省名的壹攘上层怒国家褥羧 7 台肥工业大学碗士学位论文第一章k d d 概述 区( 如华南、华东等) ，再上层是国名( 如中国、日本等) 。利用概念树提升的 方法可以大大浓缩数据库中的记录。对多个属性字段的概念树提升，将得 到高度概括的知识表，然后再将它转换成规则。 6 、遗传算法刚 这是模拟生物进化过程的算法，由三个基本算子组成： ( 1 ) 繁殖( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种群 ( 后代) 的过程。 ( 2 ) 交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个 体。 ( 3 ) 变异( 突变) 对某些个体的某些基因进行变异( 1 变0 、0 变1 ) 。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过 若干代的遗传，将得到满足要求的后代( 闻题的解) 。遗传算法已在优化计算和分 类机器学习方面发挥了显著的作用。 7 、公式发现 在工程和科学数据库( 由试验数据组成) 中，对若干数据项( 变量) 进行 一定的数学运算，求得相应的数学公式。比较典型的b a c o n 发现系统完 成了物理学中大量定律的重新发现。它的基本思想是：对数据项进行初等 数学运算( 加、减、乘、除等) ，形成组合数据项，若它的值为常数项，就得 到了组合数据项等于常数的公式。 8 、统计分析方法 统计分析方法一般先由用户提出假设，再由系统利用数据进行验证。在数据 库字段项之间存在两种关系：函数关系f 能用函数公式表示的确定性关 系) ；相关关系( 不能用函数公式表示，但仍是相关确定关系) 。对它们的 分析采用如下方法：回归分析、相关分析、主成分分杯 9 、模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识 别和模糊聚类分栎模糊性是客观存在的，系统的复杂性越高，精确化能力 就越低，也就意味着模糊性越强。这是z a d e h 总结出的互克性原理。以上 提到的模糊方法都取得了较好的效果。 合肥工业大学硕士学位论文 第一章k d d 概述 、可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更 清楚。例如，把数据库中的多维数据变成多种图形，这对揭示数据的状况、 内在本质及规律性起到了很强的作用。 1 6 数据挖掘的应用及所面临的问题 目前，数据挖掘不仅被许多研究人员看作是数据库系统和机器学习方面一个 重要的研究课题，而且被许多工商界人士看作是一个能带来巨大回报韵重要领域。 从数据库中发现知识可以用在信息管理、查询响应、决策支持、过程控制等许多 方面。虽然数据挖掘技术的研究日臻成熟，但毕竟发展地时问较短，它的研究和 应用在很多方面还有待于进一步的发展。目前数据挖掘的研究和应用主要面临的 挑战【9 】是： 1 、挖掘的对象非常庞大。来自于i n t e m e t 的数据所构建的数据库通常是十分 巨大的，更多的属性意味着高维的搜索空间，从而导致组合爆炸。属性值之间的 关系变的更加复杂，比如表现为层次结构。这些因素使得搜索的代价极高。目前 的研究发展到用并行处理或抽样的方法处理大规模数据，获得了较高的计算效率。 根据问题的定义或相关知识可以选择出需要的属性从而降低维数。处理属性之间 的复杂关系，往往需要一些背景知识，比如不同层次的概念树。 2 、数据库类型的多样性。在数据库中可能包含复杂的数据对象、超文本和多 媒体数据、空间数据、时间数据或事务数据。由于数据类型的多样性和数据挖掘 的目标不同，指望一个系统挖掘所有类型的数据是不现实的。另外，当数据挖掘 技术应用于网络时，由于局域网和广域网连接了许多数据源，形成大量庞大的、 分布式的和异种的数据库。从具有不同数据语义的结构化的、半结构化的和非结 构化的不同数据源发现知识，对数据挖掘提出了巨大挑战。 3 、用户参与和领域知识的缺乏。有效的决策过程往往是需要多次交互和反复 应用的，但是现有的数据挖掘系统很少能够真正让用户参与到挖掘过程中来。将 相关领域知识融入数据挖掘系统中将是一个很重要的问题，它将会加快挖掘的过 程，保证发现知识的有效性。 4 、处理噪声和不完全数据。存放在数据库中数据可能反映噪声、异常情况或 台熙王妲丈拳硬士学键诧文第一举煳蠹连 不究全的数据封豫。这些对象可能摘乱分手斥童拥甄导致数据与所鞫遗的知识模型 过分适应。其结果是，所发现的模式的精确性很差，处理数据噪声的方法有：数 据清理方法移数据分衙方法，黻及发现嚣努褥雾零薅嚣懿孤立轰燕援方法。 5 、数据、知识以及挖掘过程的表达机制。许多实用中重要的是用户能够理解 发现的知识，表达提取的数据。这就要求不仅限于数字、符号，更重要的是用可 筏纯豹方式表遮数据、翔谖警歪是交互鹃拣攒过程。爨鲡：盒获图、三维立方捧、 数据分布图表、曲线等。 6 、模式评估兴趣度阏题。数据挖搬系统可能发现数班干计的模式。对于 绘窀的用户，许多模式不是蠢趣的，它铜袭示公荚知谖躐簸乏赣鞭毪。关于开发 模溅趣度的评依技术，特别摄对于给定用户类，取决予用户的信赖域期望，评 估模式价值蛇主躐度量，仍然露在一些挑战。 7 、挖掘算法豹有效性、西 串缩性帮并行处理。秀了露效速扶数器绺静大量数 据中提取信息，数据挖掘算法必须是有效的和可伸缩的。也就是说，对于一个大 型数据库，数据携掘算法懿远程时间必须是可预计的帮_ 甜接受浆。司辩，许多数 据滗的太容量、数据静广泛分布以及一些拣糯算法豹计冀复杂佳威奔稽发并行和 分布式数据挖掘算法的因素。遮些算法将数据划分成各部分，这些部分可以并行 处瑗，然后合并姆邦分鲢结果。 合群王照丈学疆士学键论文 第二章w e b 燕息瓣摄取 第二章w 曲信息的提取 2 。l 凝述 众所厨知，万维同是到日前为止世界上最丰富和最辩集的信息来源。在信息 时代，万维网导致各种各样的公用信息被大爨分发。不幸的是，尽管作为信息主 要袭俸瓣h t m l 箍珙了一移努矮致鸯渎翥黧瑗蓿惑熬方浚，毽宅霹筑势不是一 个很好韵可以从中自动抽取与数据驱动的暇务或应用程序相关的信息豹缩构。 在本章中将尝试多种方法来解决这个问蹶。方法一：慕用一些专用诲询语言 懿澎蔑意h t m l 茭瑟藜各令帮势获瑟藏我褥，瑟这些我褥将w e b 趸甏主豹落 息填八到数据库中。尽管这些方法可能提供一些好处，但太部分会因为以下两个 原因交得不切实际：首先，它们需要开发人员花时间去学习一种无法在其它情况 下嫠矮貔奎逮语蠹，其凌，宅稻还不够健毡戮魏签瑾对嚣栋w e b 夏羲不霹避免 的简单更改。方法二：使用标准w e b 技术h t m l 、融肌开发的一种基 于w e b 的数据挖掘方法。这种方法即使不比其它专用方法更强大，也署其它方 法不程土下，势豢对予箨些毫缀熬悉w e b 技零瓣天来说，哭需要髓窭缀少豹努 力就可以收到很好的效果。酋先来介绍数据挖掘方法在w e b 上的应用。 2 2w e b 挖据- q 猿慧捡索蓉缓 面向i n t e r n e t 的数据挖掘可以说是个比较前瞻性的问题，有人称之为 i n t e r n e tm i n i n g 域错是w e b m i n i n g ，耳前已缀取得了些令人感兴趣煦结果，侧 黧鬟泼有不乡产赫翔来薅遥i n t e n a e t 上翡赣鬻，绦护嚣声不受无骥电子女箨熬干 扰和商业推销，受到极大的欢i 趣。w e b 挖掘和w e b 信息梭索是两种既肖联系又 有区别的技术，榭必要加以比较一番。 2 2 。1 相关静定义 定义3 1w e b 挖掘就是利用数据挖掘技术从w e b 文档和服务中自动发现 帮抽取信息的过程。 有翡学者认为：w e b 挖撼是扶大量w e b 数据静集合c 孛发瑗豫禽缒攘式p 的过稷。如果将c 看作输入，将p 看作是输出，那么w e b 挖掘的过程就是发现 从输入刘辕出的一个映射：c p 。， 定义3 2w e b 信息检索怒飙太耋w e b 文档的集合c 中找到与绘窥酌查询 盘腿工韭丈学硕士学位论文第二章w e b 信息的提取 请求q 稳关赘、恰懑羧疆静交毯子集一s 一熬过程j 璃彘整惑捻索熬过程对于与一个 映射：( c ，q ) 一s 。 2 2 2w e b 信息检索聚统的工作原理 w e b 信息检索系统一般都是出r o b o t 、索弓 模块和查询服务缀成的，其中， r o l m t 戆任务是爨霹藏豹簸t m e n l e t 孛袭瓣掰貔黼交罄；索霉 蒺块夔臻缝是获 褥到的w e b 文档中掇取关键字，并按笑键字排序，存入索号l 数据痒；其查询劫 熊负责接受、解释用户的查询，然后根据较为简单的匹配策略( 使用较多的是简 单京尔模型和模糊稚尔模型硅索弓l 库中谶行查找，将匹配的w e b 文档的u r l 豢茨竣绘蘑户。翔黼2 ，l 瑟示。 麓2 1w e b 检索系统纂零王终蒺式圈 逻辑上，可以搬w w w 看作是位于物理网络上的一个黩大的有向图( 两， e ) ，其中节点集n 对应于w e b 上的所脊文档，而有向边集e 则对应于节点之间 的超链。对节点集n 作进一步的划分套扣 n l ，n 2 。所有的非叶节点n 2 都是 h t m l 文挡，其中羧了毽含文搴及蠡记疆撵定文罄豹属毪耧蠹瀑结擒癸，还墩入 了超链以表示文档间豹结构关系。时节点n l 可 ；l 是h t m l 文档，也可疆是其它 格式的文档，例如p o s t s c r i p t 等文本文件，以及图形、音频等媒体文件，如图2 2 所示。因此，从w w w 中采集信息可使用遍历图的基本算法d f s 或b 自。 黧2 2 溉b 逻攀结擒 2 2 3w e b 挖掘与w e b 信息检索系统纳区剐 w e b 挖掘是成闲数据挖掘技术，从大景的w e b 数据中褥到隐藏的知识r 以 台秸王照文学羲圭学位论文第二季w e b 接惠熬鬟簸 此作为依据可以避行有目的的信息获取。而w e b 信息检索只是处理以关键词形 式袭示敬藏擎基稔，疆据关毽事匹配靛蘸鬟4 瓷章羹关文档遨圈绘属户，无法发褒您 藏的知识或规刚，导致其精确艘差，命中率骶；并且不能种对特定的用户给出特 殊的服务，不具谢个性化。因此，两者采用的技术尽管有很多相似之处，但两者 之阅仍套羞本覆瓣区裂。 f 1 ) 着眼点不闷。w e b 信怠梭索的研究对象是w e b 文档中显示存储的关键字 和链接，只能处理用户以关键字形式表示的简单目标，这然关键字往往不能全面 表达耀户的兴趣。瑟w e b 挖援试霾更多豹纛瓣w e b 鼗据鹣瘫容帮结构，瞧够扶 大鬣看似无关的w e b 数据中摄取知识或规则，它们可以比较准确地反映出用户 的真j e 兴趣。 f 2 ) 臣静不瓣。w e b 售惑羧索自舞在予爨麓震户茇蠛滚添，郅骏大潼文耧中 找到满足其查询鬻求的文档子黧，而w e b 挖掘是为了描承文档中隐含的知识。 从w e b 上的知识发现角度来说，信息检索系统即使精度辫商，也无法胜任。 0 ) 茨爱场合累弱。w e b 镶感捡素其裁瘸子寻我关键字妥酝戆w e b 文毯集， 而w e b 挖掘则可以提供个性化的服务以及对电子商务、决策支持等提供支持。 ( 4 ) 使用方式不同。w e b 信息检索系统镨遍需要用户釉系统之间的交互，整 令造程对矮户不遴葫。瑟w e b 戆疆可疆叁韵圭| 蠡麸w e b 黧攥孛提取蟊谖，捷溪霉 到的知识，可以透明地向用户提供真正感戥趣的信息。 2 3w e b 挖撼戆壤熹及疆囊瀚态 问题一、w e b 数据的多样性和挖掘方法、挖掘结果的复杂性。w e b 挖掘的 对象不仅包括w e b 文档的内容，还可以来自w e b 服务器、代理服务器，客户端 程夔嚣之闽篷链搂缝梅等。 w e b 数据的彩样性决定了w e b 挖掘的多样性，不嗣的数据有不同的挖掘方 法，并且挖掘所褥到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的， 还霹裁是溪户豹谑润模式。 问题二、w e b 数据的动态性极强。w e b 上的数据不仅簿天都以极快的速度 增长，丽且信息也柱不断的动态交化着。因此需要借助数据仓库的某些技术，以 镶存w 如上动态嚣薪麓数糕。瓣谓鼗据奁露豹实囊菰莛令鼗攥瘁，艇楚宅存 台s e = = 韭大学醺学位论主羹二章w e b 信惫瓣提取 储的数据与普通数据库中的数据不太一样，它存储的是从数据库里面经过加工整 理嚣麴数据。鲷鲡j l 雩予褒场应恁来浚，琢有数援痒孛存端黢蹩每笔交易雏数据， 而数据仓库则要根据吼往的历史记录进行提炼整理，存放的可髓是某种产品某月 在菜地区的特定销量等记录。数据仓库将异构的数据集成起来，经过加工整理变 戏一个可鹰静数摄资源。 问题三、w e b 的数据韵异构性i ”j 。从数据库研究的角度出发，w e b 上网站的 信息也可以看作熄一个数据犀，一个更大的、复杂性更商的数据库。w e b 上的每 一令站点裁是一令数据源，每一个数据源舔怒舅稼静，霞惫每一筵点跟菇露点静 信息和组织形式都不一样，这就构成了一个融大的、异构的数据库环境。直口果想要 利用这些数据进彳亍数据挖掘，酋先必须要研究站点之间异构数据的集成问题。因为 癸有将这些菇蠡主戆数撵郡鬟裁莛隶，提供绦露产一拿绞一豹程錾或瓣翅，方奏可 能从巨大的数据资源中获取所霈的东西。 问题四、数据的半结构化【1 4 l 。传统数据麾中的数据愚结构化的，而i n t e r n e t 瓣数据萁最大特惠霆半结构纯鞠。爨薅拳缕擒凭是藤露予缝稳诧帮蘩缭稳捷两 言的。例如传统数据库中的数据结构性很强，我们称之为究全结构化的数据，而 同时还存在一些诸如一本书、一张图片等完全无结构的数据。但是i n t e r n e t 上存 窿黪数蕹薤不爱宠全襞穆览懿辍不是完全j 结稳筵黟，鬟为它懿茭瑟纛冥毒一定 的描述层次，存谯一定的结构，所以我们将它称为半结构化的数据。 闯题五、半结构化数据模型的定义与抽取。众所周知，传统的数据库都有一 定豹数据模型，霹 良凝据这个模鍪寒其蒋逡糖述特定夔数据，弱嚣爵瞄攘蟹主蠹定 义和解释相关的街询语言。而i n t e m e t 上的数据特点很复杂，没有这样特定的模 型来攒述。每一个站点上的数据都是由站点开发人员自行设计放置的，而且数据 奉努廷有鑫疆述戆帮动态可变经等一系翻整露 特注，箕蘩秘也不霹嚣漤。这藏遥 切需熙有一个模测来清晰地描述i n t e r n e t 上的数据。针对i n t e m e t 上的数据半结构 化的特点，寻找个半结构化的数据模型则成为了解决一b 述同题的关键所在。此 辨，还需要一磺技术琵够整动娩姨嚣有数撵中将这令攘登麴取逡囊，这虢是掰话 的横型抽取技术。由于半结构化数据模型羊半结构化数据模型抽取技术是面向 i n t e r n e t 的数据挖掘技术实施的前提，因此堪称是当今数掇痒研究领域的一大热 点。 合i l e 2 e 业大学硕士学位论文第二量w e b 信息的提取 1 9 9 5 年，斯坦福大学已经开始了对二 三结构化数据模型的定义与抽取的研究。 但当时研究的重点还没有真正面对w e b ，而主要研究的是异构数据环境，因为在 异构环境巾的数据已经存在这种半结构化的特征。后来随着i n t e m e t 的发展，w e b 上的数据半结构化特征日渐明显，这一问题也就扩展到w e b 领域，最终提出了针 对w e b 数据的模型问题。相关的研究工作在1 9 9 7 1 9 9 8 年间取得了一些结果， 提出了诸如w e bs q l 等大约一二十种的查询语言。基于w e b 上的内容查询主要 有两个含义，一是页面内容的查询，二是页面与页面之间链接的查询，而像页面 之间链接的这种关系我们则称之为路径表达。目前，以咀。家族为基础的新一 代的w w w 环境是直接面对w e b 数据的，不仅可以很好地兼容原有的w e b 应用， 而且可以更优地实现w w w 这一分布计算环境下的信息共享与交换。因此，许多 关于x m l 数据存储、x m l 数据的查询和) 6 m l 的系统实现与应用模式等方面的 研究工作纷纷开展起来。 2 4 w e b 挖掘的分类 w e b 信息的多样性决定了w e b 挖掘任务的多样陛“】。总的来说根据w 曲 挖掘的对象可分为内容挖掘、访问信息挖掘和结构挖掘，如图23 所示。 圈23w e b 挖掘的分类 其中，对w e b 文本挖掘的目的是对页面信息进行聚类、分类和关联分析， 以及利用w e b 文档进行趋势预测、分析等：多媒体信息挖掘是对多媒体文档的挖 掘。w e b 使用记录挖掘是对用户访问w e b 时服务器方留下的访问i 己录进行挖 掘，从中可以得出用户的访问模式和访问兴趣。w e b 结构挖掘是对