




已阅读5页,还剩60页未读, 继续免费阅读
(计算机应用技术专业论文)web文档聚类系统的设计与实现.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
西南交通大学硕士研究生学位论文第1 页 摘要 我们生活在一个信息化的时代,各种信息急剧膨胀,为了有效 利用这些信息,数搌挖掘和知识发现技“冬应运褥生,筹显示出强大 的生命力。聚类分析在数据挖掘研究中占有重要的位置。所谓聚类, 就是将物理或抽象对象的集合划分成为由类似的对象组成的多个类 的过程。 本文首先对w e b 文档聚类中豹数据表示方法、特征提取、权僮计 算进行了系统的研究,并开发了整套从网上下载新闻、提取新闻 正文、提取词干、计算权值、聚类、聚类结果可视化的软件,软件 采用了x m l 和多线程技术。 介绍和分析了k m e a n s 聚类算法,并对w e b 文档聚类中的欧氏距 离进行改进。改进后的欧氏距离与传统欧氏距离相比,提高了聚类 的质量和速度。改进的欧氏距离与文本聚类中常用的余弦距离效果 相当。 提出一种基于交集的聚类组合算法,借鉴了选举投票的思想。 给定同一数据集的不同聚类结果,此算法先求出不同聚类结果中每 令簇的对应关系,然后计算这几个聚类结槊中对应簇的交集,对剩 余的有争议对象进行投票,最后把投票之后仍未确定归属的对象分 配给最近的聚类中心,或者不经过投票直接将有争议的对象分配给 最近的聚类中心。 实现了随机点图、顺序点图、电子云图、条形图、饼闰五种聚 类结果可视化方法。这些方法各有优点,可配合起来使用。其中的 顺序点图对象的位置固定,可在图形上显示每个对象的撼关售息, 适合动态显示聚类过程,在本文巾得到广泛应用。 最后用多个w e b 数据集进行实验,验证了基于交集的聚类组合算 法的有效懂。 关键词:数据挖掘;聚类分柝:文本挖掘;预处理;聚类组合;可 视化;欧氏距离 西南交通大学硕士研究擞学位论文第1 i 页 a b s l r a e t w en o wh a v el i v e di na ni n f o r m a t i o n s o c i e t y e a c hk i n d0 f i n f o f m a t i o ni n f l a t e s s u d d e 珏l y 。t h ed a l am i n i n ga n dt h ek n o w l e d g e d i s c o v e r e da r j s e sa tt h ch i s t o r i cm o m e n t ,a n dd i s p l a y st h ef o r m i d a b l e v i t a l i t y , w h l c hc a n h e l pp e o p l e 毽s et h ei 珏f o f m a l i o n e f f e c t i v e l y c l u s t e r i n ga n a l y s i si sa ni m p o r t a n tp a r to fc h ed a t am i n i n gr e s e a r c h c l u s t e r i n gi s t h ep f o c e s so fg r o u p n gt h ep h y s i c a lo rl h ea b s t r a c t o b j e c ls e ti n t oc l a s s e so rc l u s t e r s t h i sp a p e rf i r s tr e s e a r c h e dd a t ae x p r e s s ,c h a r a c t e r i s t i ce x t f a c t i o n a n dw e i g h t sc a l c u l a t o ni nw e bd o c u m e n t sc l 娃s t e r i 珏g , d e v e l o p e da s o f t w a r eo fd o w n l o a dn e w sf r o mi n t e r n e t ,e x t r a c t j o nn e w sc o n t e n t , d i s t i l l o r i g i n a lw o f d s ,w e i g h t sc a l c u l a t i o n ,c l u s t e f i n g ,c l u s l e f i n g r e s u l t sv i s u a l i z a t i o n ,t h i ss o f l w a r ea d o p t sam u l t j t h r e a d i n ga n dx m l e c h n i q u e t h ec l u s t e r i n ga 1 9 0 r i t h m so fk - i n e a n sw e r ei n t r o d u c e da n d a n a l y z e d t h e nw e i m p r 0 v e d t h ee u c l i d e a nd i s t a n c eo nw e b d o c u m e n l sc l u s l e f l n g c o m p a f e dt ot h el f a d i l i o n 矗le 驻c l i d e 鑫珏d l s l a 翦c e , l h ei m p r 0 v e de u c l i d e a nd i s t a n c ei m p r o v el h es p e e da n dq u a l i t yo f d o c u m e n t sc l u s l e f i n g ,n e a rb yt 董l ee f f e c to fc o s i n ed i s t a n c ew h i c h u s e dt oa p p l yj nt e x tc l u s t e r j n g an e wi n t e r s e c t i o n 曲a s e dc l u s t e r i n gc o m b i n a t i o na l g o r i t h mw a s p r e s e n i e d ,w h i c hi m i t a t e sl h ew a y so fv o t i n g a s s i g n ss o m ed i f f e f e n t c l u s t e r i n g r e s u l t s0 fs a m ed a t as e t ,t h i sa 1 9 0 r i t b me x t r a cc st h e c o r f e s p o 霸d i n gr e l a i o n so fe 鑫c he l u s t e ri nt h e s ed i f f er e n lc l u s t e r i n g r e s u l t sf i r s t ,a n dt h e nw ec a l c u l a t et h ej n t e r s e c t i o n0 fc o r r e s p o n d i n g c l u s t e r so fl h e s ef e s u l s ,p u tl h ef e m a i n i n gd i s p u t a b l eo b j e c t s ov o e , f i n a i l yd i s t r i b u t et h eo b j e c t su n a c c e p l e da f t e rv o t i n gt ot h en e a r e s t c e n t e f sc l u s t e r ,o rd i s r i b u t et h er e m a i n i n gd i s p u t a b l eo b j e c tst ot h e n e ar e s tc e n t e r sc l u s t e rw t h o u tv o t i n g 西南交通大学硕士研究生学位论文 第l l i 页 s e v e f a lv i s u a l i z a t o 蘸l n e l h o d so fd l s p l a y i n g c l u s l e f i n gr e s u l t s w e r er e a l i z e d ,王li n c l u d e st h ec h a r to fr a n d o mp o i n l s ,o r d e rp o i n t s , e l e c t r o nc l o u d ,b a r sa n dp i e t h e s ew a y sh a v ed i f f e r e n ta d v a n t a g e sa n d d i s a d v a n t a g e s ,s oa st oc o o p e r a t ew i t ho t h 。f s t h eo b j e c tp l a c ei nt h e o d e fp o i n sc h a f ti sf i x e d ,c o u l ds h o wt h ei n f o f i n a t i o no fc a c ho b j e c t i nt h ec h a n i tj ss u i tf o rd i s p l a y i n gt h ed y n a m i cc l u s t e r i n gp r o c e s s , a n dw i d ea p p i i c a t i o n si nt h i sp a p e r f i n a l l y , w et e s t e dw i 壤 m a n y w e bd o c 毽m e n l s ,v a l i d a t e dt h e i m p f o v e d e u c l i d e a nd i s t a n c ea n di n l e r s e c t i o n b a s e dc l u s t e r i n g c o m b j n a l i o na l g o r i i h m 。 k e yw o r 畦s :d a t am i n i n g ;c l u s t e 妇n ga n a l y s i s ;d o c u m e n tm i n i n g ; p r e p r o c e s s i n g ;c l u s t e r i n gc o m b i n a t i o n ;v j s u a l j z a t i o n ; e u c l i d e a n d i s t a n c e 瑟赢交通大学磺士研究生学技论文第1 页 第1 章绪论 董1 本文研究背景 涎羞蔽数据痒、数握仓鬻等数摇仓撩技本舞基疆豹镶怠系统袁 各行各业的应用,海爨数据不断产生。随之而来的问题怒如此多的 数摇证入难以消亿,无法袋装面上看岛谴们掰蕴涵的有粥信怠,更 不用说有效地指导进一步的工作。如何从大爨的数据中找到真正有 用的信息成为人们关滋的焦点,数据挖掘技术也正是伴随着这种需 求默嫒究态囱农瘸。 近年来,随着i n t e r n e t w e b 技术的快速谱及和迅猛发展,使各 释穰患霹黻戮菲鬻 豪簿成本在溺终上获褥,邀予i n t e 疆e l ,w w w 在 全球互连互通,可以从中取得的数据量难以计算,而且 i n t e r n e t ,w w w 的发展趋势继续看好,特剐是电子商务的灌勃发展为 网络应用提供了强大支持,如何程w w w 这个全球最大的数掇集合 中发现有用信息无疑将成为数据挖掘研究的热点。 w e b 挖撼拯锼臻数撂挖掘技零在w w w 数挺中发现潜在静、套 用的模式威信息。w e b 挖掘研究覆盖了多个研究领域,包括数据库 技术、信慧获取技术、统计学、入工餐钷中翡梳器学习稻神缀阏络 等。 聚类就是穰据某种相似性准则将样本空闻分成多个子空间,使 每个子空蚓内部撰本点尽可能楣似,不同子空间内样本点之间差异 尽可能大,其实质是译找隐藏在数据中不同的数据模型,是一个无 监督学习过程,缝够实现嚣奉空潮熬富分类。聚类广泛纛援予绞诗、 机器学习、模式识别、数据分析簿领域,并越来越受重视。聚类可 班帮助人们更快酶找瓢所需要的倍怠,蠢藏,聚类在瑷实生活中寄 着很重要的意义。现谯,聚类分析己成为一个非常活跃的研究课题。 本论文得到四川省重大基础研究项目( 0 4 j y 0 2 9 一0 0 1 4 1 和西南 交邋大学辩技发展基金a 2 0 0 4 0 1 5 ) 的资助。 西南交通火学硕士研究生举位论文第2 页 1 2 国内外研究现状 鼗撂挖掇,氇可以豫必数据痒孛的知识发现( k 拄o w l e d g e d i s c o v e r d a t a b a s e ,k d d l 。1 9 9 5 年程加拿大蒙特利尔市碟开了第一 矮k d d 莛骣学本会议 1 1 ,以瑟每年摇开一次。近年来,k d d 焱磅 究和应用方面发展迅速,在电信、银行、商业等领域得到了广泛的 应用,s a s 、s p a s s 等缀多软传都提供了数据挖壤的功能。 聚类分析作为数据挖掘中的一个重要研究热点,目前,国外已 摄如了很多静算法,比如:k m e a n s 冀法i ”、b l r c h 算法【”、d b s c a n 算法f 4 l 等。 国内对聚类算法的研究也取褥了不少有意义的成果,如杨燕等 对蚊群算法进行改进,提出了种多蚁群聚类组合算法m a c c a 5 l ; 马帅等提出一种基于参考点和密度的快速聚类算法1 6 j ;王建会等提 出了一种实用商效的聚类算法1 7 l ;谢立宏等提出了一种无距离灞数 聚类方法【“,等等。 1 3 本文主要内容 本论文的主要研究工作和文章缀织结构如下: 第l 章为本文绪论部分。首先分析了本文的选题背景和研究意 义,然赢介绍了国内外研究现状。 第2 章对数据挖掘的概念进行了系统的介绍。并对文本挖掘中 的数攥表示方法、特征提取、权值计算进行了详细的总结。 第3 章是有关聚炎分析的研究。对聚类分折的概念、产生和发 展进行了简要的归缡和总结,露靖辩主要繁类算法迸行了介绍。 第4 章设计和实现了一个完整的w e b 文档聚类系统,包括新闻 下载、掇取耨瓣琵文、攫取溺干、计算较德、聚类帮聚樊结累霹筏 化。并对w e b 文档k m e a n s 聚类中的欧氏距离进行改进,改进后的 敬氏距褒与余弦距离豹簸栗穗当,之嚣黻掇到它主要是黼为磊逑鼗 聚类组台实验时要用这种距离以及其他距离的结果一起进行组台。 鬟出一耪鏊予交集翻聚类缝会算法,实瑗了多释装类结柒可稷纯方 法。 第5 章扶雅浅獒文潮照一芝下载了主子簸耨阉,铡瑗簿4 牵设诗 西南交通大学硕士研究生学位论文第3 页 的系统进行预处理,然后对本文提出的聚类组合算法进行测试,并 对测试结果进行分析。 西南交通大学硕士研究生学位论文第4 页 第2 章数据挖掘 2 1 数据挖掘概述 随着数据库技术的飞速发展以及数据库管理系统的广泛应用, 各个企业和部门通过自己的数据库管理系统,经过长年努力,已经 积累了越来越多的数据。于是,人们开始渴望通过对这些庞大的数 据分析得到更多的有助于决策的信息。虽然,目前的数据库系统可 以高效率地实现数据的录入、查询、统计等功能,但由于数据量庞 大以及数据库系统中分析方法的严重缺乏,使得它无法发现数据中 隐藏的相互联系,更无法根据当前的数据去预测未来的发展趋势。 因此,出现了所谓“数据多,知识少”的现象,造成了严重的资源 浪费。 建立在数据库系统之上的计算机决策支持系统出现,为进行高 层次的数据决策分析提供了好的思路和方法。但由于决策支持系统 在数据的采集、分析方法上的灵活性等方面存在局限性,使得人们 不得不寻求更有效的途径去开拓数据决策分析的思路。计算机人工 智能为此作出了巨大贡献。人工智能经历了博弈、自然语言理解、 知识工程等阶段,已经进入了机器学习的热点阶段。机器学习能够 模拟人类的学习方式,通过对数据对象之间关系的分析,提取出隐 含在数据中的模式,即知识。 正是由于实际工作的需要和相关技术的发展,利用数据库技术 来存储管理数据,利用机器学习的方法来分析数据,从而挖掘出大 量的隐藏住数据背后的知识,这种思想的结合形成了现在深受人们 关注的非常热门的研究领域:数据库中的知识发现( k d d : 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 s ) 。其中,数据挖掘技术便是k d d 中的一个晟为关键的环节。 1 9 9 5 年,在加拿大蒙特利尔召开了第一届知识发现和数据挖掘 国际学术会议,数据挖掘一词被很快流传丌来。数据挖掘( d m :d a l a m i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的数摒 m i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的数据 嚣奄交通大学磺士研究生学 擐论文繁5 贾 中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 怠稻知识懿过程。 数据挖掘是门交叉学科,玄会聚了数据库、人工锗能、统计 学、可视俄、并行计算等不阍学科和领域,近年采受到备赛斡广泛 关注。统计学与数据挖掘有着密切的联系。数据挖掘的出现为统计 学提供了一个崭新的应用领域,也给统计学的理论研究提出了新的 瀑题,它瑟疑会推动绞诗学豹发鼹。嗣粒,摄然绞诗学不可毙绘出 数据挖掘所有问题的答案,但它可以为数据挖掘提供非常有参考价 值的挺价,能够援太蠢蠡丰富数蕹拣据敬方法。 数据挖掘工具能够对将来的趋势和行为进行预测,从而很好地 支持人们的决策,眈如,经过对公司整个数韬库系统的分祈,数耀 挖掘王具w 以回答诸如“哪个客户对我们公司的邮件推销活动最有 可能作出反应,为什么”等类似的问题。有魑数据挖掘工具还能够 解决一些缀瀵嚣入工瓣闰懿转统阏题,强荛窀翻麓够快速迪送蹩整 个数据库,找出一些专家们不易察觉的极有用的僚息。 逐有缀多稻数据挖掘这一末漤籀遥骰靛术语,魏数撵库串戆知 识发现( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。 人们把原始数据看作怒形成知识的源泉,就像从矿石中采矿一样。 原始数据霹以是结构他的,如关系数据库中的数撼,也可以是半结 构化的如文本、图形、图像数据,甚至是分布衣网络上的异构型 数握。发理翘浚懿方法可以是数攀靛,邈可以是辈数学豹:可戳是演 绎的,也可以是归纳的。发现了的知识可以被用于信息管理、查询 优纯、决策支持、过程控裁等,还可疆用子数据蠢身的维护。 特别要指出的是,数据挖掘技术从一丌始就是面向应用的。它 不仅是面向特定数据库的简单硷索查询调用,而鼠要对这些数据进 行微观或宏鼹的缝计、分析、综念和攘理,以指导实嚣蝴题熬求解, 企图发现事件问的相互关联,甚趸利用已有的数据对未来的活动进 行预溺。铡舞麴拿大转e 誊奄话公司要求蠢嚣零大s i m o e 擎r a s e f 大学 k d d 研究组,根据其拥有的十多年的辩户数据,总结、分析并提出 新的电话收费秘管理办法,制定凝有程于公司又裔稠予客户瓣优惠 政策。这样一束,就把人们对数据的应用,从低屡次的末端瓷询操 作,提高到为各级经嚣决策者提供决策支持。同时需要指出的是, 西南交通大学硪士研究生学位论文鬻6 贾 这里髓说的知识发现,不是袋求发现款之四海两誊燃的囊理,瞧不 是要去发现崭新的自然科学定理和纯数举公式,更不是什么机器定 理涯骥。鼹番发袋静知谖都蹩辖对懿,楚毒特定蘸疆稻绞寒条件、 面向特定领域的,同时还要能够易于被用户理解,鼹好能用自然语 言表遮发磷结栗。 2 2 数据挖掘的任务 数据挖掘技朱豹嚣标是飘大塞数甏中,发现豫藏于冀后豹规律 或数据间的关系,从而服务予决策。数据挖掘一般有以下四类主要 任务: l 、数据总续 数据总结目的是对数据进行浓缩,给出它的总体综合描述。通 过对数据懿总结,数撂挖搀簸够姆数撵痒孛戆毒关数据麸较低囊冬个 体层次抽象总结到较高的总体层次上,从而实现对原始繁本数据的 总体撼握。 传统的也是最简单的数据总结方法利用统计学中的方法计黧出 数据蹀的各个数据项的总和、平均、方蒺、最大值、最小值等基本 描述统计量。或瓒通过刹用绫计爱形工具,对数摄制作纛方圆、蛰 状图等。 裁藤l a p 技本安瑷数攫懿多维查询鸯蔻一静广泛嫠蘑熬数据 总结的方法。 2 、分裘 分类的主要功能是学会一个分类函数或分类模懋( 也常常称作 分类器) ,该模型能够根据数据的属性将数据分派到不同的组中。即: 分毒厅数擐懿各种爝性,共找凑数攒的羼饯摸型,臻定鹱些数撵属于 哪些缀。这样我们就可以利用该模型来分析已有数据,并预测新数 据壤瓣予暌一令缝。 分类应用的实例很多。例如,我们可以将银行网点分为好、一 般和较差三种类鍪,并以诧分析这三种类型银行网点的各种属性, 特别怒位置、盈利情 兄等属憔。并决定它们分类的关键属性及相互 间关系。此后就可以根据这嫂关键属性对每一个预期的银行网点进 西南交通大学硕士研究生学位论文第9 页 知识。w e b 内容挖掘和w e b 使用挖掘是w e b 挖掘的两个重要方面。 2 3 1w e b 文本挖掘 w e b 文本挖掘是以计算语言学、统计数理分析为理论基础,结 合机器学习和信息检索技术,从大量的文本数据中发现和提取隐含 的、事先未知的知识,最终形成用户可理解的、有价值的信息和知 识的过程。作为一个新的数据挖掘研究领域,目前尚无统一的、确 切的定义。w e b 内容挖掘多为基于文本信息的挖掘。按照文本挖掘 的对象可把文本挖掘为:基于单文档的数据挖掘和基于文档集的数 据挖掘。基于单文档的数据挖掘对文档的分析并不涉及其它文档, 其主要的挖掘技术有:文本摘要、信息提取( 包括名字提取、短语提 取、关系提取等1 。基于文档集的数据挖掘是对大规模的文档数据进 行模式抽取,其主要的技术有:文本分类、文本聚类、个性化文本 过滤、文档作者归属、因素分析等。从功能上w e b 文本挖掘主要是 对w e b 上大量文档集合的内容进行总结、分类、聚类、关联分析以 及利用w e b 文档进行趋势预测等。w e b 文本挖掘中,文本的特征表 示是挖掘工作的基础,文本的分类和聚类是最重要、最基本的挖掘 功能。 图2 2w e b 文本挖掘的一般过程 w e b 文本挖掘的般处理过程如图2 2 所示。首先,对h t m 1 文档集建立特征表示。h t m l 格式的文档集缺乏像关系数据库中数 据的结构化和组织性,因此要将这些文档转化成一种类似于关系数 据库中的记录、较规整的、能够反映文档内容特征的表示,一般采 用一个文档特征向量。为减少特征向量的维数,需要进行特征子集 的选取。然后,利用机器学习的各种方法束提取面向特定应用目的 的知识模式。最后对获取的特征模式进行质量评价,若评价的结果 西南交通大学硕士研究生学位论文第1 l 页 英文中的a ,i h e ,e a c h ,f o r ,汉语中的“地、得、的、这、虽然”等: 然后排除那些在文档集合中出现频率很低的单字;在英文中还可以 去除前缀,找到词根,如w a l k e r ,w a l k i n g ,w a l k e d 都可以是同一个 词w a l k 。为了便于计算权值,还需要对每个词条编号,即给每个词 条赋予一个唯一的数字,用这个数字来代表该词条,这样可以简化 处理过程。如果不进行编号,要比较两个词条是否相同,需要进行 字符串比较,而编号之后就只需要比较两个数字是否相等。 2 3 3 计算特征词条的权值 特征词条权重x 的计算方法有多种不同的算法。x l f d j 一般定义 为词条f r 在文档d 中出现频率数圻f 鲫的函数,即置似) 一,( 坑( d ) ) 。 常见的计算方法有以下几种: 1 1 布尔值法 ,= :蓼笛瀑 ( 2 1 ) ,一1o 坑( d ) o l 0 1j 2 1 平方根函数 ,坑( d ) 3 1 对数函数 ( 2 - 2 ) ,- l o g ( 呒( d ) + 0 1 )( 2 3 ) 4 1t f i d f 厂- 吼( 驯0 9 ( 等) ( 2 4 ) 其中j v 为所有文档数目,。为词条r ;出现过的文档的数目。 在信息检索和文本机器学习中被频繁采用的文档表示法主要为 t f i d f 向量表示法,t f i d f 算法目前存在多种变形公式。 2 3 4 特征集的缩减 使用以上文档表示法时,表示文档的特征向量会达到数1 0 万维 的大小。如此高维的特征对将进行的分类机器学习未必是重要有益 的而且高维的特征可能会大大增加机器的学习时问而仅产生与小 嚣溺变遗失拳硕士孬 究嫩学位论文繁1 2 页 得多的特征子集相近的举习分类结果。因此,减少维数至燕重要。 特征选取一般是构避一个评价函数对特征集中的每个特征进 行独立的评估,这样,蕊个特征都获褥个评估分值,然偌对所有 的特鬣技照英译 鑫分镶熬大小遗行撑譬,选取羲定数露懿黪缝子集。 选取多少个最佳特征秘及采蠲于 么译徐溺数都需要锌对熬体闽题逶 过实骏来决定。 对于给定的文本( 英文1 数据,要先对宸进行预处理、计算出权 值,辫对它进行分类、聚类等操作。一般预处理的过程怒:先从文 档特繇繁孛去除停止谶,把各种实词都转纯为原形,然鼷对词袈进 霉编譬,谤算强条鹣投缀,浚爨预定数瓣鹃特征投毽。餮e b 文整聚 类的流程图如图2 3 所承,本文第4 章w e b 文档聚类系统的设计与 实现即按照这个流程来粥写。 下载网页 1 l 去掉网页中的标签,提取正文 j l 去虑谣并把实溺转能为骧形 l 计算权值并约简 l 聚类 l 聚类结果可视化 图2 3w e b 文档聚豢流程图 西南交通大学硕士研究生学位论文第1 5 页 种其它限制,我们希望聚类算法可以在考虑这些限制的情况下,仍 旧有较好的表现。 9 ) 结果的可解释性和可用性:聚类的结果最终都是要面向用户 的,所以结果应该是容易解释和理解的,并且是可应用的。这就要 求聚类算法必须与一定的语义环境,语义解释相关联。 3 2 欧氏距离和余弦距离 聚类分析中通常使用欧氏( e u c l i d e a n ) 距离或余弦( c o s i n e ) 距离来度量对象之间的相似性。欧氏距离表示多维空间的几何距离, 其定义为: 一 d ( 。,。,) j 荟( 。* 一。斗) 2 ( 4 4 ) 其中m 表示属性个数。对象o j 和o j 之间的余弦相似度函数,即两 矢量之间的夹角的余弦( 两矢量的点积除以其大小) 为: ) s 拥( d 。,d ,) - 1 窒l _ 一 、荟) 荟( o 余弦距离与余弦相似度刚好相反,余弦相似度越大, 反之,余弦相似度越小,余弦距离越大。 3 3 聚类算法的分类 ( 4 5 ) 余弦距离越小 聚类算法大体可以划分为以下几类:划分方法、层次方法、基 于密度的方法、基于网格的方法和基于模型的方法。 1 ) 划分方法 给定一个包含n 个数据对象或元组的数据库,一个划分方法构 建数据的c 个划分每个划分表示一个簇,且c n 。通常会采用一 个划分准则( 经常称为相似度函数) ,例如距离,以便在同一个簇 中的对象是“相似的”,在不同簇中的对象是“相异的”。这些聚 类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模 西南交通穴学硕士研究生学位论文第1 6 页 的数攫集遴霉亍聚类,以及处理复杂形状豹聚类,基予划分熬方法霉 要进一步的扩展。 獒型鹣鬟分方法包括;k m e a n s f l 4 l 【1 ”,k m e d o i d s p a m 【l c l a r a 【1 6 1 ,c l a r a n s f l ,e m 【1 8j 等。 2 ) 毯次方法 层次方法对飨定数握对象集合进行层次鲍分孵。擐掇层次分鳃 是自底向上还是自顶向下形成,臌次聚类的方法可以进步分为凝 聚熬帮分裂鳇。耀次浆类方法夔缺骧套予,一量个步骤 合并或 分裂) 完成,它就不能被撇消,因此而不能熨正错误的决定。改进 瀑次方法韵聚类蔟蠢豹一个肖零登豹方淘是将屡次聚类鞠其绝聚类 技术进行集成,形成多阶段浆类。 典型的层次方法有b i r c h f l ”、c u b e l 2 “、r o c k t 1 1 、 c h e m a l o e n 【2 2 l 等。 3 ) 基于密度的方法 提出了基于密度懿聚类方法蹩为了发瑗籁意形袄豹聚类结莱。 其主臻思想是:只要临近区域的密度超过某个阈值,就继续聚类。 这样豹方法可戳胡来遗滤“噪声”孤立点数撵,发现任意形状的簇。 赎型的基于密度的聚类算法包括:d b s c a n 【2 ”、0 p t i c s 【24 1 、 d e n c l u e l 瓣i 等。 4 ) 基于模型的方法 熬于模型的方法为每个簇假定了个模型,寻找数据对给定模 型静最佳熬会。蒸于模型匏算法邋遘聿冬建反获数据点空麓分- 奄酶密 度函数来定位聚炎。这种聚类方法试图优化绘定的数据和某些数学 模墅之滴豹适应往。 典型的基于模型的聚类方法有统计学方法c o b w e b f 圳、 c l a s s i t f 2 ,1 、a u l o c l a s s ! 引,神经网络方法s o m 2 9 1 30 1 、a r t f 3 1 i 、l v o l 3 :】 等。 5 ) 基于网格的方法 蒸于麟格静蘩类方法采爝一个多分辨率豹两橇数据缩掏。怒对 象空阳j静蘩类方法采爝一个多分辨率豹两橇数据缩掏。怒对 象空阳j量化为有限数目的单元,形成一个网格结构。所有的聚类操 西南交通大学硕士研究嫩学位论文第1 7 贞 的单元数目有关。 典型的基予两格的浆类方法有s t l n g l 、w a v e e l u s t e r l 3 4 鄂 c l i q u e f 3 5 1 等。 3 4 聚类结果评价 聚类结莱弱质量评价方法露分走终帮和内部溅释,裔数据集纛 验知识的是外部评价方法,没有先验知识的是内部评价方法【”】。这 里介缨一魏常翔熬终部谭侩方法萝m e a s u r e ”1 。 f ,m e a s u r e 组合了信息检索中查准率( p r e c i s i o n ) 岛查全率 ( r e c a “) 的思想。一个聚类j ( 即一个簇) 及与此相关的分类i ( 即 器始熬一类) 熊登f e e i s l o n 与f e c a l l 定义为! p 一盱括f 。,t ( ) 一挚 删,j ) * 等 ( 3 1 ) ( 3 2 ) 其中n j 是在聚类j 中分类i 戆数蛰,鹣是豢类j 枣艨骞对象豹数嚣, n i 是分类i 中所有对蒙的数目。则分类i 的f m e a s u r e 定义为: ,。竺侉3 ) p + r 分类i 对应的聚类可能有多个,哪个聚类的f m e a s u r e 值高。就认 为该黎类代表分类i 懿敬射,分类i 的f 。m e a s u f e 裁取该缀大毽。对 一个聚类结果c 它的总f m e a s u r e 值由每个分类的f m e a s u r e 加校 平均得到: t - 其中;仍然为分类i 中所有对象的数目。 时,全部采用f m e a s u r e 值。 ( 3 4 ) 本文测试聚类算法豹性能 堕 塑m 竖 西南交通大学硕士研究生学位论文第1 8 页 第4 章w e b 文档聚类系统的设计与实现 4 1r s s 方式下载新闻 4 1 1 什么是r s s r s s 是一种描述和同步网站内容的格式,是目前使用最广泛的 x m l 应用。r s s 搭建了信息迅速传播的一个技术平台,使得每个人 都成为潜在的信息提供者。发布一个r s s 文件后,这个r s sf e e d 中包含的信息就能直接被其他站点调用,而且由于这些数据都是标 准的x m l 格式,所以也能在其他的终端和服务中使用【”l 。 r s s 是站点用来和其他站点之间共享内容的一种简易方式,通 常被用于新闻和其他按顺序排列的网站,例如b l o g 。网络用户可以 在客户端借助于支持r s s 的新闻聚合工具软件,在不打开网站页面 的情况下阅读支持r s s 输出的网站内容。网站提供r s s 输出,有利 于让用户发现网站内容的更新。 用户可以在借助于支持r s s 的信息聚合工具阅读支持r s s 输出 的网站内容( 一般网站提供r s s 都会针对其频道进行分类,这样用 户可以更清晰更有针对性地订阅感兴趣的频道) ,而且无需逐个网站 访问,r s s 阅读工具自动为您收集好您订阅的最新信息。 r s s 已成为最流行的x m l 标准之一,涌现出了大量的工具和 r s sf e e d 。r s s 为b i o g 的迅速崛起做出了贡献,并且正在成为其他 w e b 站点的标准部分。 在许多新闻信息服务类网站,会看到这样的按钮豳蓬毙五氇,有 的网站使用一个图标,有的同时使用两个,这就是典型的提供r s s 订阅的标志,这个图标一般链接到订阅r s s 信息源的u r l 。当然, 即使不用这样的图标也是可以的,只要提供订阅r s s 信息源的u r l 即可例如雅虎体育新闻提供的r s s 订阅地址是: h ! ! 口; s s :n 燮s :y h q q :q 婴2 1 乜p q ! ! 。 使用r s s 获取信息的前提足,先安装个r s s 阅读器,然后将 西南交通大学硕士研究生学位论文第1 9 页 r s s 信息源的u r l 加入到r s s 阅读器的频道即可。大部分r s s 阅 读器也预设了部分r s s 频道,如网易新闻、百度新闻等。 4 1 2r s s 阅读器 本文采用的r s s 阅读器是新闻蚂蚁( n e w sa n t s ) ,版本号 1 7 0 1 ,网址:h ! ! p ;出塑盟:n 塑s n 瞧q 婴。它的界面如图4 - 1 所示。 图4 1 新闻蚂蚁主界面 其中左边一栏可包含若干个r s s 频道组,图4 1 中只有一个 y a h o o n e w s 频道组。每个频道组又可包含多个r s s 频道,每个r s s 频道对应一个r s s 地址。图4 - 1 中的b u s i n e s s 频道对应的r s s 地址 是h ! ! p ; s s ! 堕s ! y 4 h q q :q m ! s 也hs i n 。该地址指向的是一个x m l 文件,也称为r s s 文件。图4 2 显示的是北京时间2 0 0 5 年1 2 月1 5 同1 6 :0 2 :1 6 下载的雅虎b u s j n e s s 频道对应的r s s 文件( 删去了一些 西南交通大学硕士研究生学位论文第2 l 页 r s s 阅读器可以定期或手工下载该频道的r s s 文件,然后与上 一次下载的r s s 文件比较,这样就可以发现该网站的更新。同时因 为每个项都提供了一个 g e t b o d y b o d y ) ;,获取文档b o d y 矗o c u m e n t 一 g e t t i t l e 鑫t 土t 王e ; ,菝取文档标趱 b o d y 一 g e t o u t e r t e x t ( c o n t e n t ) ; 获取文本正文内容 嚣e 撩0 1 霉毒x t 拳c o n t e 珏t :,显示交襁歪文 e d i t l t e x t = t i t l e ;显示文档标题 ) 这种方式就糨当于在l e 浏览器中打开本地h t m l 文传,然后另 存为文本文件,因此速度很慢,而且不容易去掉网页中的导航栏、 ,“告等无关黪内褰; 帮二种方式鼹自己编写程序解析h l m l 源文件,这种方式的缺 熹是院较复杂,键是可疆满麓我们懿要求。零文采蹋第二种方式。 在h t m l 语占里中, 和i i t l e 之间的文本是文档标题, 和 之间的内容是文秽主体, 和 之间的文本 是脚本, 和s t y l e 之间鳇文本是文档风格定义,s e l e c t 和 s e l e c l 之间的内容是下拉列表。 舅法第一步蓑先撼赝毒字母转换爻小写,珏t 联l 标签是不区分 大小写的;第二步查找文章的标题并输出:第三步查找新闻谁文开 始菊耜结裘褥;繁强步挺正文歼始符霸结束拿孥之阉的标蕊、瓣奉、 风格定义和广告等去掉,输出新闻f 文,输出时去掉连续的空白字 符( 龟括空格、霹车、换行和跳格) 。 提取掰闻萨文的程序界蕊如图4 4 艇毋,是别是竣入的文件娄, 题甫交通大学硕士研究生学俄论文第2 3 页 通常选取新闻蚂蚊保存新阊全文酌鞘录,右侧是输爨文件夹,单击 下拉箭头可选取最近使用的输出文件夹,其他下拉箭头的功能炎似。 强受文挡鞍多,提取正文的瓣阕较长,数采惩多线援,薮建一个线 獠进行正文提取,主线程负责响应界面操作。 图4 4 提取新闻正文主界面 强4 5 提敬! 女秘耘溺标题鞠爱文 西南交通大学硕士研究生学位论文第2 4 页 在图4 4 所示的程序界面中,点击按钮即可提取输入文件夹 中全部新闻网页的新闻标题和正文,并保存在右侧对应的文件夹中, 每个新闻网页保存为一个文本文件。得到的新闻正文如图4 5 所示。 4 3 转换为对应数字 上一节得到的结果是新闻标题和全文,是一篇篇完整的英文文 章。为了便于计算单词出现的频率,我们需要把这些文章中的单词 转换为对应的数字,每个单词对应的数字由词典文件w o r d d i c 给出。 在转换过程中,需要把一些无意义的词即虚词去掉,这些虚词 由s t o dw o r d s t x t 文件给出。因为一个英语单词可以加上各种后缀 以适应语法需要,但是它们的含义是基本一致的。所以我们在进行 聚类时,需要把同一单词的不同形式都统一为原形。由于单词的变 化形式多样,而且部分单词的变化不规则,因此提取词干统一原形 的工作是本程序的一个难点。提取词干的步骤如下: 第一步:去掉复数、- e d 或一i n g 等,如: caresges 一caress p o n i e s 一 p o n i t i e g一t i care8s- caress c a t s 一c a t f e e d一f e e d a g r e e d 一 a g r e e d i s a b l e d一d i s a b l e m a t t i n g 一m a t m a t i n g 一m a t e m e e t i n g - m e e t m i l - 1 i n g 一m i l l m e s s i n g 一m e s s m e e t i n g s- m e e t 第二步:当词于里含有另外一个元音时把末端的v 换成i 第三步:把双后缀转化为单后缀如: 嚣毫交遗犬学磉圭旗突生攀镶论文繁2 5 茭 一a t 主o n a l一一a t 尊 一t i o n a l一一t i o n e n c i一一e n c e - a n c i一一a n c e 一主z e r一一i z e b 】i一一b l e a 1 】_ i一一a 1 一e n t l i一一e n t e l i - 一e o u 9 1 i一一o u s 一主互a t i o n一一主暮e a t i o n一一a t e a t o r一一a t e a l i s m一一a 1 一i v e n e s 8 一一i v e f u 王珏e s 嚣- 一f 醢王 一o u s n e s 8一一o u 8 一a l i t i - 一a l i v i t i一一i v e - b i 工i t i一一b l e 一王o g i 一 一王o g 第四疹:与第三步类似,处理- i e ,f u l l ,+ n e s s 等。如: 一i c a t e一一i c a t i v e 一鱼接去掉 一a l i z e一一a 1 - 主e i t 主一一主e i c 矗王一一i c f u l一 直接去掉 一n e s s 一直接去摊 第五步:去掉一a n t ,一e n c e ,_ a b l e ,一 b l e ,m e n t ,。o u s ,i v e ,i z e 等 第六步:当元音痔酬帮辕啻序列豹个数郝大予l 薅,去捧鼗惩 麓e 西南交通大学硕士研究生学位论文第2 6 页 单词转化为原形后,就
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年初级机械设计师考试备考指南及模拟题
- 2025年初级音乐创作技巧与实战练习
- 2025年水文水资源调查与评估案例分析教程及模拟题集
- 2025年初级市场营销专员模拟面试题与答案解析
- 【教案版】小学五班级上册 跳绳4
- 2025年建筑行业设计师招聘面试模拟题集及解析
- 2025年汽车技术工程师考试预测题及备考指南
- 2025年外贸销售代表面试要点与预测题
- 2025年物资储备仓库安全管理实践案例分析及模拟题集解析
- 2025年考研政治考点精讲及模拟题集
- 高中日语学习宣讲+课件
- 2022年新高考II卷高考语文试卷试题深度解读及答案详解(精校版)
- 一次调频综合指标计算及考核度量方法
- 车辆段平面布置设计
- 数字媒体艺术概论-第一章-概述
- 四大会计师事务所面试题
- GB/T 4669-2008纺织品机织物单位长度质量和单位面积质量的测定
- GB/T 4604-2006滚动轴承径向游隙
- Fanuc系统宏程序教程
- 药物竹罐临床应用课件
- 2022年咸阳经开城市发展集团有限公司招聘笔试试题及答案解析
评论
0/150
提交评论