（计算机软件与理论专业论文）基于rough集理论的信息过滤研究.pdf

摘要 摘要 互联网的迅速发展，给人们的学习、工作和生活提供了大量的有益进步的 信息，带来了极大的便利，与此同时在大量进步有益的信息的背后同样存在着 大量不良的信息，尤其对青少年的身心健康造成了极大的伤害。为了在动态的 信息流中能根据用户的信息需求搜索用户感兴趣的信息，屏蔽其它无用和不良 的信息，信息过滤技术应运而生。 r o u g h 集理论是一种处理不精确、不一致、不完整等问题的数学工具，无 需提供问题所需处理的数据集合之外的任何先验信息，可直接对数据进行分析 和推理，从中发现隐含的知识，揭示潜在的规律。自2 0 世纪8 0 年代末以来， 关于r o u g h 集理论和应用的研究逐渐成为智能信息处理领域的热点问题。 本文是基于r o u g h 集理论的信息过滤系统研究，把r o u g h 集理论的属性约 简方法应用到信息过滤上，对不良信息进行过滤。本文主要工作如下： 1 概述了r o u g h 集理论、信息过滤技术的发展趋势和研究现状，以及相 关的理论知识和相关技术。 2 详细介绍了信息过滤之前数据预处理方法，特征提取方法等，并针对 r o u g h 集理论只能处理离散化数据问题研究分析了目前几种离散化方法，针对 本实验系统，对n a i v es c a l e 算法进行了改进。 3 讨论了几种属性约简算法，在仔细研究阅读相关文献的基础上分析了 各算法的优缺点，最后给出了基于差别矩阵的改进算法，用数组存储差别矩阵 元素，存储前进行冗余元素的删除，简化了差别矩阵，提高了效率，并将其应 用到信息过滤系统中。 4 最后在完成基于r o u g h 集理论的信息过滤系统实验的理论研究的基础 上，将其理论应用于实践，构建了一个信息过滤系统模型，并给出了实验结果， 实现不良信息的过滤。利用r o u g h 集的属性约简理论降低了信息的冗余度，提 高了准确率，实现较好的过滤效果。 关键词：r o u g h 集理论；信息过滤；属性约简；离散化方法 a b s t t a c t a b s t r a c t t h es c a l eo fi n t e r a c ti si n c r e a s i n ga taf a s t e s ts p e e d t h ed e v e l o p m e n to f i n t e r a c to f f e r sm i l l i o no f u s e f u la n dp r o g r e s s i v ei n f o r m a t i o na n dm a k e st h ep e o p l e s d a i l yl i f ee a s y b u tt h eb a c ko fm i l l i o n so fi n f o r m a t i o n ，s o m eb a di n f o r m a t i o ni s e x i s t e d ，w h i c hs e r i o u s l ya n dh a r m f u l l ya f f e c t st h eh o b b l e d e h o y t or e t r i v et h eu s e f u l o rr e l e v a n ti n f c l r m a t i o na n de l i m i n a t et h eu s e l e s so ri r r e l e v a n ti n f o r m a t i o ni na d y n a m i cd a t as t r e a ma c c o r d i n gt ou s e r sr e q u e s t , t h er e s e a r c ho fi n f o r m a t i o n f i l t e r i n gh a sd r a w nm u c ha t t e n t i o n t h er o u g hs e tt h e o r yi sam a t h e m a t i c st o o li n p r o c e s s i n gi n a c c u r a t e ， i n c o n s i s t e n ta n di n c o m p l e t ep r o b l e m s ，w h i c hc a nf i n dt h ei m p l i c i tk n o w l e d g ea n d p o t e n t i a lr e g u l a t i o n sb yd i r e c t l ya n a l y z i n ga n dd e d u c i n gt h ed a t aw i t h o u ta n yp r i o r i n f o r m a t i o ne x c e p tt h ed a t as e t s i n c et h ee n do f1 9 8 0 s ，t h et h e o r ya n da p p l i c a t i o n s o fr o u g hs e t g r a d u a l l yh a v eb e c o m i n gt h ef o c u so fi n t e l l e c t u a li n f o r m a t i o n p r o c e s s i n g i nt h i sa r t i c l e ，t h er e s e a r c ho fi n f o r m a t i o nf i l t e r i n gs y s t e mb a s e do nr o u g hs e t t h e o r y a p p l yt h ea t t r i b u t er e d u c t i o nb a s e do nr o u g hs e tt h e o r yt oi n f o r m a t i o n f i l t e r i n g ，c a r r i e do u tt h eu n h e a l t h yi n f o r m a t i o nf i l t e r i n g t h em a i nw o r k sa r ea s f o l l o w s 1 t h ed i s s e r t a t i o ng i v e sab r i e fi n t r o d u c t i o nt or o u g hs e ta n di n f o r m a t i o n f i l t e r i n ga b o u ti t sd e v e l o p m e n t , c u r r e n tr e s e a r c h ，a n da c a d e m i ck n o w l e d g ea n d c o r r e l a t i v et e c h n o l o g ya b o u tt h e i r s 2 i ti n t r o d u c e st h ew a y so ft h ed a t ae x c a v a t ea n df e a t u r ed i s t i l li nd e t a i l a n d a i mt op r o b l e mo fr o u g hs e tt h e o r yo n l yt od i s p o s et h ed i s c r e t i z ad a t a , r e s e a r c ha n d a n a l y z es o m ed i s c r e t i z a t i o nm e t h o d sa tp r e s e n t i na l l u s i o nt ot h i se x p e r i m e n t s y s t e m ，t h i sp a p e ri m p r o v e st h en a i v es c a l ea r i t h m e t i c 3 s o m ea r i t h m e t i co fa t t r i b u t er e d u c t i o nh a v eb e e nd i s c u s s e dp a r t i c u l a r y a c c o r d i n gt or e a d i n gi n t e r r e l a t e dl i t e r a t u r e ，w ec o m p a r e ds o m ea r i t h m e t i c so f a t t r i b u t er e s u c t i o n ，a n da n a l y z e dt h ee x c e l l e n c e sa n dd i s a d v a n t a g eo ft h e s e i i a b s t r a c t a r i t h m e t i c s u l t i m a t e l y , aa m e l i o r a t i v ea r i t h m e t i ca b o u ta t t r i b u t er e s u c t i o nb a s e d0 1 1 d i s c e r n i b i l i t ym a t r i xi sb r o u g h tf o r w a r d u s e da r r a yt od e p o s i tt h ee l e m e n t so f d i s c e r n i b i l i t ym a t r i x ，o m i tt os u p e r a b u n d a n c ee l e m e n t sb e f o r ed e p o s i t i n g s oi tc a b p r e d i g e s tt h ed i s c e r n i b i l i t ym a t r i xa n dh e i g h t e nt h ee f f i c i e n c ya n da p p l yt h i sm e a n s t oi n f o r m a t i o nf i l t e r i n gs y s t e m 4 f i n a l l y , b a s e do nb a s i cr e s e a r c h ，w ea p p l i e dat h e o r yt op r a c t i c ea n d d e s i g n e das y s t e m i cm o d e lo fi n f o r m a t i o nf i l t e r i n ga n dp r e s e n tae x p e r i m e n tr e s u l t ， i m p l e m e n tt h eu n h e a l t h yi n f o r m a t i o nf i l t e r i n g t h ea p p l i c a t i o no fr o u g hs e tt h e o r y i ni n f o r m a t i o nf i l t e r i n gc a nr e d u c e dr e d u n d a n ti n f o r m a t i o n ，i m p r o v e dt h ep r e c i s i o n a n dr e a l i z e dp r e f e r a b l ef i l t e r i n ge f f e c t k e y w o r d s ：r o u g hs e t ；i n f o r m a t i o nf i l t e r i n g ；a t t r i b u t er e d u c t i o n ；d i s c r e t i z a t i o n 1 1 1 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 一i 鱼三，胁日学位论文版权使用授权书 本学位论文作者完全了解直昌大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学雠始糍名晰导 签字日期：0 年胡7 凶 签咱 第1 章引言 第1 章引言 1 1 问题的提出及课题来源 自从w v c w 出现以来，互联网技术向社会的各个领域不断的渗透，其发展 极大的促进了信息的交流和沟通，人们可以享受丰富的网络信息，在网上可以 找到各种各样的形形色色的信息。但同时一些网站为达到盈利目的，传输一些 恶意的不良信息，网络上大量的反动资料、宣扬邪教、暴力恐怖等不良信息干 扰了正常的网络生活，产生了消极的后果，尤其影响了青少年的健康成长。 随着互联网上信息量的迅速增加，其快捷的传输方式和丰富的信息资源极 大地方便了人们的生活，也带来了所谓的“信息过载”和“信息迷向”问题【型_ 1 面对类型复杂、结构各异的海量信息，人们为了找到自己需要的信息往往要花 费大量的时间和精力，如何能够充分利用现有的网络资源，有效准确的找到自 己感兴趣的信息，滤除与自己的需求无关的信息已经成为网络信息处理的当务 之急【4 们。随之产生的信息过滤技术正得到越来越广泛的关注。信息过滤 ( i n f o r m a t i o nf i l t e r i n g ，i f ) 是一种系统化的方法，根据用户的信息需求对动态 信息进行过滤，从动态的信息流中抽取符合用户个性化需求的信息，去掉_ 些 冗余的信息，仅把用户感兴趣的文档传送给用户，这样可以提高获取信息的效 率。 信息过滤在为用户提供所需要信息的同时，更着重于剔除用户不需要的信 息，可以提高用户获取信息的效率，减轻用户的认知负担，起到减压阀的作用。 通过信息过滤，可以减少不必要的网络信息传递，节约宝贵的信道资源；利用 信息过滤，可以对网络信息的流向、流量和流速进行合理的配置，使网络更加 顺畅；而对于用户来说，信息过滤由于剔除了大量的不需要的信息的流入，可 以避免“塞车”的现象【3 4 】。 目前有关信息过滤的研究【3 8 ，4 2 - 3 】主要集中在两个方面：一是过滤不良信息， 即设置一定的条件限制用户获取某些不良信息，以净化网络环境，保证网络安 全。这一类信息过滤系统称为阻挡系统( b l o c k i n gs y s t e m ) 。二是过滤不相关 信息，其目的是向用户提供密切相关的信息，这一类信息过滤系统称为推荐系 第1 章引言 统( r e c o m m e n d e rs y s t e m ) 。 本课题是我的导师陈炼教授主持的江西省教育厅2 0 0 7 年度科技项目计划 ( 赣教技字 2 0 0 7 12 3 号) 基于二进制的粗糙集理论决策表约简方法应用研 究的后续研究课题，主要是针对阻挡系统，其主要内容是以r o u g h 集理论 为基础，针对信息过滤中信息规模较大的特点讨论如何进行属性约简和值约 简，如何对数据进行离散化，对当i j f 的有关算法进行分析比较，找出其优缺点， 掌握其思想技术，并将其应用到信息过滤技术中。建立w e b 信息过滤模型， 通过对数据预处理及特征项的提取、属性离散化及约简，最终获得决策规则， 实现较好的过滤效果。 1 2 国内外的研究现状与发展趋势 1 2 1r o u g h 集理论的研究现状与发展趋势 r o u g h 集理论是一种刻画不完整性和不确定性的数学工具，能有效的分析 和处理不精确、不一致和不完整等各种不完备信息，并从中发现隐含的知识， 揭示潜在的规律眦】。1 9 8 2 年，以波兰数学家p a w l a k f l 6 】为代表的研究者在研究 不精确、不确定及不完全知识表示和分类的基础上，首次提出了r o u g h 集理论。 1 9 9 1 年p a w l a k 教授出版的第一本关于r o u g h 集的专著和1 9 9 2 年s l o wi n s k i r 主编论文集的出版，推动了国际上对r o u g h 集理论与应用的深入研究。1 9 9 2 年在波兰ki e k r e 召开了第一届国际r o u g h 集合研讨会，这次会议着重讨论了 集合近似定义的基本思想及其应用和r o u g h 集合环境下的机器学习基础研究， 从此每年都会召开一次以r o u g h 集理论为主题的国际研讨会，从而推动了 r o u g h 集理论的拓展和应用。另外，国际上还成立了r o u g h 集学术研究会，参 加的成员来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰和印度等国 家。目前r o u g h 集理论已成为人工智能领域中的一个较新的学术热点，引起了 越来越多科研人员的关注。 虽然r o u g h 集理论从诞生到现在只有二十几年的时间，但已经在许多的领 域取得的成果是令人瞩目的。它是一种较有前途的软计算方法，为处理不确定 性信息提供了有力的分析手段，如处理新增数据的增量算法、提高处理速度的 并行算法、算法复杂度的研究等。 2 第1 章引言 目前r o u g h 集理论研究的最新进展1 1 2 1 主要包括以下几个方面： ( 1 ) 可变精度r o u g h 集的研究：由p a w l a k 教授提出的传统r o u g h 集理论 虽然是一种有效的软计算工具，但是它有存在一定的局限性，如它处理的分类 必须是完全正确或肯定的所处理的对象是已知的，且从模型中得到的结论仅适 用于这些对象等。这些局限性都限制了它的应用。许多学者从多方面推广了这 一模型，其中最主要的是z i a r k o 教授于1 9 9 3 年提出的可变精度r o u g h 集 ( v p r s ) 模型。这一推广在应用中非常重要，因为在实际问题中绝对的包含 有时是不必要的。目前很多的学者开始对v p r s 模型进行研究，并取得了一定 的成绩。如j u s h e n gm i 和米据生等提出的基于可变精度r o u g h 集模型的知识 约简方法，并给出了基于v p r s 的1 3 下分布约简及1 3 上分布约简的概念及其等 价定义，从而拓展了传统r o u g h 集理论的模型，是不协调目标信息系统知识约 简的新方法。 ( 2 ) 连续属性的离散化处理：r o u g h 集的数学基础是集合论，难以直接 处理连续的属性，而现实决策表中连续属性是普遍存在的，因此连续属性的离 散化是制约r o u g h 集理论实用化的难点之一。这个f j 题一直是人工智能界关注 的焦点。目前国内学者在这方面的研究比较多，提出的方法也比较多，在这套 面做出最新研究的学者主要有张建军、于达仁、吴山产和易韬辉等。 ( 3 ) 不完备信息的处理：不完备信息系统广泛地存在于日常实际数据中， 如带有却使值的数据库、遗产数据库和集成的数据仓库等，而r o u g h 集理论却 只能处理完备的信息系统。为了解决不完备信息的处理问题，目前有关的最新 研究是如何利用r o u g h 集理论在不完备信息系统中提取规则集。 ( 4 ) r o u g h 集理论拓广方面的研究：随着对r o u g h 集理论研究的深入， 其内涵和外延都有了进一步的拓宽和延伸。如山东大学史开泉教授于2 0 0 2 年 提出的奇异r o u g h 集( s ，粗集) ，基于相异关系的r o u g h 集理论、基于相似关 系的r o u g h 集理论、基于相容关系的r o u g h 集理论等，这些都是对传统的r o u g h 集理论在一定程度上的扩展和补充。 ( 5 ) r o u g h 集理论有效算法的研究：目前有关r o u g h 集有效算法的研究 主要集中于规则提取、属性约简和数据挖掘等方面，有关这方面的研究文献比 较多。在规则提取方面主要介绍r o u g h 集和生命周期法( l c a ) 的结合在规则 提取方面的应用、“元组合并”规则提取和规则评估方法、基于遗传算法的增 量式r o u g h 集分类规则挖掘方法等。在属性约简方面主要探讨基于区分矩阵和 3 第1 章引言 主成分分析的算法、利用可辨识矩阵实现属性约简的方法以及基于识别矩阵求 取决策规则值简式的算法d m b v r 等。在数据挖掘方面主要分析知觉计算理论 的主要特征及其重要性、基于r o u g h 集理论的最简规则挖掘方法等。 ( 6 ) 与神经网络、模糊集的结合研究：r o u g h 集和神经网络是数据挖掘 问题中最常用的两种技术。两者的结合可以很好的弥补各自的缺点，因此目前 有众多学者在该方面提出了各自的见解。r o u g h 集和模糊集理论都是研究信息 系统中只是不完备、不精确问题的方法，但r o u g h 集理论解决问题的出发点是 信息系统中知识的不可分辨性，而模糊集理论则关注信息系统中知识的模糊 性，两者在处理方法上各有特色，两者的结合可以更好的解决信息系统中不完 备不精确性知识的问题。 ( 7 ) 与r o u g h 集理论相关方面的研究：随着r o u g h 集理论的发展，与之 相关联的研究也越来越多。这些研究都不约而同的用到了r o u g h 集理论，不论 是在决策方面、评价方面以及与其他方法的相互关系上面，而且也得出了一些 有用的结论。 目前r o u g h 集理论研究的发展趋势【2 】主要有以下几个方面： ( 1 ) 大数据集问题的解决：现实中的数据库已经越来越大，如何降低算 法的执行效率和复杂度，从众多数据中寻找最有用的数据，是r o u g h 集理论需 要应对的一个挑战。虽然目前这方面已有了一些研究成果，但是还不完善，仍 需要进一步研究。 ( 2 ) 缺失值处理方法的研究：对样本数据进行处理是，往往会遇到数据 丢失的问题，即不完备的信息系统。由于经典r o u g h 集理论是基于信息系统的 处理，需要采用特定的方法对缺失值进行处理，建立处理不完备信息系统的扩 展r o u g h 集模型。 ( 3 ) 高效约简算法探索：属性约简的求解是一个n p h a r d 问题，国内外 学者在这方面做了大量的研究，但是目前还不存在一种非常有效的方法，因此 寻找快速的约简算法及其增量版本这一问题仍是r o u g h 集理论的研究热点之 一o ( 4 ) 多方法融合：由于r o u g h 集在处理数据时存在一定的缺点，因_ ! 有 必要把r o u g h 集和其他不确定方法结合起来。目前比较常用的做法是r o u g h 集和神经网络及模糊集的结合应用。虽然在这方面取得了一定的成绩，但是还 有许多难点并没有解决，仍需进一步的研究。 4 第1 章引言 ( 5 ) 连续属性的离散化处理：因为r o u g h 集只能处理离散化的属性，而 现实中存在的数据一般具有连续性的属性，因此连续属性的离散化变得极为重 要，已成为制约r o u g h 集实际应用的一个大障碍。目前也有一些这方面的研究 但这些方法或多或少都存在一定的缺陷，还没有一种比较公理化的方法，因此 该问题的研究仍是今后的热点。 r o u g h 集理论是一种新颖有效的软科学方法，能够分析和处理不完备不确 定信息，其应用中的巨大潜力，必将开拓基于r o u g h 集诸多实际应用领域的发 展空间。但是r o u g h 集理论还处在继续发展之中，正如r o u g h 集理论的创立 人p a wl a kz 所指出的那样，尚有一些理论上的问题需要解决，而且r o u g h 集 理论及其应用研究在我国还处于发展阶段，有待于进一步的研究和探讨。其研 究在我国起步比较晚，但是发展速度很快，目前中科院、清华大学等研究所和 高校已经加入到这个领域，并取得了一定的成果。 1 2 2 信息过滤的研究现状与发展趋势 随着网络技术的发展与普及，利用w e b 网站获取信息已成为人们的共识。 同时w w w 本身作为一个庞大的分布式异构超文本文档库，从诞生至今，箕 信息容量急速倍增，人们从信息缺乏时代过渡到信息爆炸时代，而w e b 搜索 引擎技术的出现与发展，为人们获取信息指明了方向。对于w e b 数据挖掘中 得到的数据进行信息过滤机制就是为了克服“信息过载”、“信息超载”现象l 删， 减少用户在获取信息过程中的负担，同时向用户提供数量适宜、质量优良的信 息应运而生的。 1 9 5 8 年，l u h n 提出了“商业智能机器”的设想【4 3 】。在这个概念框架中， 图书馆的工作人员为每个用户建立用户配置文件，然后这些配置文件被应用到 一个自动文档选择系统中，系统为每个用户产生一个符合用户信息需求的新文 本清单，同时记录下用户所订阅的文本用于更新用户的需求模型。虽然缩微胶 片和打印机技术的发展，使得实现的物理细节有所不同，但他的工作涉及到了 信息过滤系统的每一个方面，为信息过滤的发展奠定了有力的基础。 1 9 6 9 年，选择性信息分发( s e l e e t i v ed i s s e m i n a t i o no fl n f o r m a t i o n ：s d i ) 系统 引起了人们的广泛兴趣，导致了美国信息科学协会成立了选择性信息分发系统 兴趣小组( s i g s d i ) 。当时大多数系统都遵循l u h n 模型，只有很少的系统能够 5 第1 章引言 自动更新用户需求模型，其它大多数仍然依靠专门的技术人员或者由用户自己 维护。s d i 兴起的两个主要的原因是实时电子文本的可用性和用户需求模型与 文本匹配计算的可实现性。 1 9 8 2 年3 月，d e n n i n g 在美国计算机学会通讯杂志中正式提出了“信 息过滤”的概念，他的目的在于拓宽传统的信息生成与信息收集的讨论范围。 他描述了一个信息过滤的需求例子，对于实时的电予邮件，利用过滤机制，识 别出紧急的邮件和一般例行邮件。他采用了一个“内容过滤器”来实现过滤。 其中采用的主要技术有层次组织的邮箱、独立的私人邮箱、特殊的传输机制、 闽值接收、资格验证等。 1 9 8 7 年，m a l o n e 等人发表较有影响的论文，并且研制了系统信息透镜 ( i n f o r m a t i o nl e n s ) 。提出了三种信息选择模式，即认知、经济、社会。所谓 的认知模式相当于d e n n i n g 的“内容过滤器”，即基于内容的过滤；经济模式来 自于d e l m i n g 的“阈值接收”思想：社会模式是他最重要的贡献，目前也称之为 “合作过滤”。在社会过滤系统中，信息的表示是基于以前读者对于信息的标 注，通过交换信息，自动识别具有共同兴趣的团体。 1 9 8 9 年，在这个时期信息过滤获得了大规模的政府赞助。由美国国防部高 级研究计划局( d e f e n s e a d v a n c e dr e s e a r c hp r o j e c t s a g e n c y ：d a r p a ) 资助的消息 过滤会议( m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ：m u c ) 极大地推动了信息过滤的 发展。它对将信息抽取技术支持信息的选择、将自然语言处理技术引入信息过 滤研究等方面进行了积极的探索。1 9 9 0 年，d a r p a 建立了t i p s t e r 计划，以 支持许多消息过滤会议参与者的研究。 1 9 9 2 年，美国国家标准和技术研究所( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n d t e c h n o l o g y ：n i s t ) 与美国国防部高级研究计划局联合赞助了每年一次的国际文 本检索会议t r e c 会议( t e x tr e t r i e v a lc o n f e r e n c e ：t r e c ) ，对于文本检索和 文本过滤倾注了极大的热忱。t r e c 会议有两个基本的任务：一是类似于信息检 索的a d h o c 任务，另一个是过滤( f i l t e r i n g ) 的任务。过滤任务包括三个子任务： 分流子任务( r o o t i n gt a s k ) 、批过滤予任务( b a t c hf i l t e r i n gt a s k ) 、自适应过滤子 任务( a d a p t i v ef i l t e r i n gt a s k ) 。t r e c 在最近的几次会议中，着重于文本过滤的 理论和技术研究以及系统测试评价方面工作，对文本过滤的形成和发展提供了 强有利的支持。 目前随着因特网的迅速发展，需求的不断增加，在信息过滤以及其相关技 6 第1 章引言 术方面，取得了长足的进展，成为了信息产业新的增长点。b e l k i n 和c r o f t ( 1 9 9 2 ) 阐述了“用户角色”( 包括用户兴趣及兴趣表示) 在信息过滤系统中的地位及其 在交互中的作用：l a m 等人( 1 9 9 6 ) 设计了个人兴趣漂移探测算法；y a n g 和 c h u t e ( 1 9 9 4 ) 实现了基于实例和最小平方利益的线性模型文本分类器。 m o s a f a ( 1 9 9 7 ) 构造了智能信息过滤的多层次分解模型。一些信息过滤系统也相 继问世，目前国外研制的一些主要信息过滤系统有：斯坦福大学的t a kw y a n 和h e c t o rg a r c i a m o l i n a 开发的基于内容的过滤系统s i f t 、s t e v e n s 研制的 i n f o s c o p e 系统、n i c h o l s 等人研制的t a p e s t r y 系统、麻省理工学院m i l l e r 等人 开发的g r o u p l e n s 、b r e w e r 等人开发的u r n 系统。 信息过滤是当前国际上信息检索领域研究的热点之一。英文信息过滤的研 究开展较早，人们在用户模板、信息的比较和选择、自适应学习、共享评注和 文档的可视化等方面都进行了一定了研究，但仍有较大的提升空间。中文信息 过滤的研究起步较晚，目前中文信息过滤和推送系统主要还是基于关键词规则 的过滤，真正的文本过滤特别是自适应的过滤的研究很少。这一方面是限于中 文文本的表示和处理的难度，另一方面也是因为缺少适当的有说服力的评测集 和评测标准。 近些年来，以t r e c 会议提供的较为成熟的评测过滤系统的指标为契机， 国内的中科院软件所、清华大学、复旦大学、哈工大、东北大学以及微软亚洲 研究院等机构相继开展了信息过滤技术特别是面向中文的信息过滤技术的研 究，积累了很多宝贵的经验，也取得了些不错的成绩。 中国科学院软件研究所阮彤提出了一种基于贝叶斯网络的信息过滤模型 b m i f ( b m i f 描述了信息过滤的基本结构) ，并在b m i f 定义的基础上提供了它 的各种使用方法。清华大学计算机科学与技术系的田范江等人对进化式信息过 滤方法进行了研究，清华大学自动化系卢增样等对信息过滤中用户需求的表示 进行了研究，并提出了一种用固定文章集表示用户需求的新方法。复旦大学的 吴立德教授和黄首蓄博士等人研制的基于向量空间模型的文本过滤系统参加 了2 0 0 0 年举行的第9 次文本检索会议( n 也c 9 1 的评测，取得了良好的成绩， 在来自多个国家的1 5 个系统中名列前茅，其中自适应过滤和批过滤的平均准 确率分别为2 6 5 和3 1 7 。东北大学的姚天顺教授和林鸿飞博士等人进行了 中文文本过滤的研究，他们提出了基于示例的中文文本过滤模型，在该模型中， 用户需求采用基于示例文本的主题词表示，文本表示采用向量空间模型，需求 7 第1 章引言 与文本的匹配度采用向量夹角余弦来衡量。 中文语言上的特殊性和其特有的复杂性、灵活性，给中文信息过滤技术的 研究工作带来了较大的困难。在借鉴国外信息过滤技术成果的基础上，对中文 信息过滤技术进行深入的研究并开发出适合我国国情的中文信息过滤系统成 为了我国信息化进程的一种迫切需要【5 3 】。 1 3 论文的主要工作与组织结构 本文以r o u g h 集理论为基础，分析研究了当前各种属性约简算法和数据离 散化算法，对其算法进行比较分析找出其优缺点，掌握其思想技术，并将其应 用到信息过滤技术中。通过对数据预处理及特征项的提取、属性离散化及约简， 最终获得决策规则，实现较好的过滤效果。 本文的主要工作包括： ( 1 ) 首先阐述了r o u g h 集的基本概念，通过分析讨论当前r o u g h 集的各 种属性约简算法，试图找到一种针对w e b 信息规模较大数据集较多的特点比 较有效的属性约简及属性值约简。 ( 2 ) 讨论如何对数据进行预处理，怎样提取特征值以及如何对属性权值 进行离散化。通过分析比较当前各种离散化方法的优缺点，针对本实验系统， 对n a i v es c a l e 算法进行了改进。 ( 3 ) 讨论了几种属性约简算法，在仔细研究阅读相关文献的基础上分析 了各算法的优缺点，最后给出了基于差别矩阵的改进算法，用数组存储差别矩 阵元素，存储前进行冗余元素的删除，简化了差别矩阵，提高了效率，并将其 应用到信息过滤系统中。 ( 4 ) 将上述提出的适合w e b 信息处理的属性约简及离散化方法应用到信 息过滤技术中，建立信息过滤模型，实现条件属性集的属性及值约简，实现较 好的过滤效果。 文章的组织结构如下： 第一章为引言，介绍了本论文问题的提出及课题的来源，以及r o u g h 集理 论和信息过滤的研究现状及发展趋势，并介绍了本论文的主要工作和组织结 构。 第二章是本论文的基础，着重介绍了以后用于信息过滤的有关r o u g h 集理 8 第1 章引言 论和信息过滤的基本概念，为下面的工作打下理论基础。 第三章和第四章是本论文的重要内容，主要讨论如何进行数据预处理、特 征项提取、对特征权重如何进行离散化处理和属性约简。通过对当前已有的属 性约简算法的分析比较讨论了如何利用r o u g h 集进行属性及值约简，针对大数 据集，各种方法存在的优缺点，并对其进行总结分析。 第五章是基于r o u g h 理论的信息过滤的设计与实现。要做的工作就是把前 面提到的处理w e b 信息较有效的属性约简算法及数据离散化方法应用到信息 过滤技术中，通过一系列的处理得出结果，实现信息的过滤，并对结果进行分 析，以验证上述算法及本实验的效果。 第六章是结论，通过对本文研究内容的分析总结，提出论文尚存在的问题， 对r o u g h 集理论研究的发展趋势进行展望，分析了亟待进一步解决的问题。 9 第2 章r o u g h 集理论及信息过滤的基本概念 第2 章r o u g h 集理论及信息过滤的基本概念 2 1r o u g h 集理论 r o u g h 集理论【1 6 】是一种处理含糊和不精确性问题的新型数学工具，不精确 性是r o u g h 集理论的关键词，它涉及集合论定义中的许多实质性内容，首先介 绍一下有关集合的一些概念，然后再给出r o u g h 集的一些概念。 2 1 1 集合与关系 自从1 9 世纪康托( c a n t o r ) 创立了集合论以来，集合论就已经成为现代数学 的基础。集合的表示通常有三种，其一是列举法，即把集合的元素全部枚举出 来；其二是性质法，即是用集合中的元素具有某种共性来描述集合；其三是特 征函数法，即集合中的元素与特征值0 和1 对应起来表示。 一个集合通常用大写字母表示，而集合的元素用小写字母表示。某个元素 a 瘸于集合a 或不属于集合a ，分别记为a e a 和a c a 。一个集合的全部元素 书目称为该集合的基数，记为川或者c a r d ( a ) ，其基数可以是无限的。如果集 合b 中的元素全部都能在集合a 中找到，在集合b 被称为集合a 的子集合， 简称子集，记为b a ，如果一个集合不包含任何的元素，则称之为空集，用。 表示。在一定的范围内，如果所有的子集均为某一集合，则称该集合为全集， 记作u 。 集合的运算包括交、并、补和差运算： 交运算：对任何两个集合a 和b ，有集合a 和b 所有共同的元素组成的 集合s 被称为a 和b 的交集，s = a n b = x ：x a 八x b 。 并运算：任何两个集合a 和b ，所有属于a 或b 的元素组成的集合s ， 称为a 和b 的并集，s = a u b = x ：x e a v x b 。 补运算：任何两个集合a 和b ，所有属于a 而不属于b 的一切元素组成 的集合s 称为b 对于a 的补集或差集，s = a b = f x ：x ea x 匹b ，也可记作 s = a b 。 关系，在集合理论中，是指两个不同或相同集合中有序对元素的集合。关 1 0 第2 章r o u g h 集理论及信息过滤的基本概念 系的某些特殊性质是指自反性、对称性和传递性。 定义1 1 设r 是集合a 到a 的二元关系，如果对v a a 有a ) 则称 r 是a 上的自反关系。 ， 定义1 2 设r 是集合a 上的二元关系，如果对v a ，b e a ，有 b ) e r ，也必 有f b ，a ) r ，则称r 是a 上的对称关系。 定义1 3 设r 是集合a 上的二元关系，对va b ，c a ，如果无论什么时 候有“b ) e r 和( b ，c ) r ，必有( a ，c ) e r ，则称r 是a 上的传递关系。 知道了上面的自反性、对称性和传递性的概念，就可以知道什么是等价关 系和等价类。 设r 是集合a 上的二元关系，如果它是自反、对称和传递的，则它是a 上的等价关系。等价关系的集合称为等价类，也即是假设r 是a 上的个等 价关系，与a 中的一个元素a 相关的所有元素的集合被称做a 的一个等价类， 记作【a 】r 。当仅考虑一个关系时，就可以略去下标，简写为【a 】。形式地，【a r = s i 岛 s ) e r 。 2 1 2r o u g h 集的基本概念 知道了上面的等价关系和等价类的概念，接下来可以来了解一下什么叫做 r o u g h 集。设x c u ，r 是u 上的等价关系，a = ( u ，r ) 是一个近似空间，在a 上，如果x 是一些r 基本类的并集，则称x 是r 可定义的；否则称x 是峰0 不可定义的。r - 可定义集是全集u 上那样一些子集，这些子集在个体全集u 上是恰好可被定义，而r - 不可定义集是子集x 上不可能恰好被定义的。r 可 定义集被称为r - 一致集或r 恰当集，而r - 不可定义集也被说成是r - 不一致集 或r - r o u g h 集，简称不一致集或r o u g h 集。如果存在一个等价关系r ei n d ( u ) ， 其中i n d ( u ) 是u 上给定的所有等价关系的交集，使得x c _ u 是r 一致的，则 集合x 被称做u 中一致集；如果x c _ u 对任意r e i n d ( u ) 都是r r o u g h 的， 则x 被称做u 上不一致集或r o u g h 集。 如何近似地定义r o u g h 集呢? 为此借用两个概念：下近似集和上近似集。 形式地，设x _ _ c u 是任一子集，r 是u 上的等价关系，则有 r ( x ) = u y e u r ：y c _ x r + ( x ) = u y e u r ：y a x a ) 分别称它们为x 的r - 下近似和r 上近似，其中a 是空集，y 是u 上按等 第2 章r o u 曲集理论及信息过滤的基本概念 价关系r 作成的等价类。下近似可以被解释为所有那些被包含在x 里面的等价 类的并集；上近似可以被解释为所有那些与x 有交的等价类的并集。 上近似和下近似之间的差将被称做x 的r - 边界线集，它是那些通过等价 关系r 既不能在x 上被分类，也不能在x 上被分类的元素的的集合，可以 表示成：b n r ( ) ( ) = r ( x ) 一r ( ) ( ) 。形式上集合x 是r 分明的当且仅当 b n r ( x ) = a ，否则x 是r - r o u g h 的。 x 的r 正区域被记成p o s r ( x ) = r 。( x ) ，它是如此一些个体元素的集合， 这些元素完全属于x 的成员；x 的r - 负区域被记成n e g r ( x ) = u - - r + ( x ) ，它是 如此一些个体元素的集合，这些元素不是任意模糊地用等价关系r 确定的，它 们不属于x ，而是属于x 的补集x 。 为了更精确地表示r o u g h 近似精度的思想，引入了下面不精确性的数值量 度。设x g u a x a ，则称or ( x ) = c a r d ( 艮( x ) ) c a r d ( r + ) 为x _ c u 的近似 精度，其中c a r d ( s ) 为s 的基数。ar ( ) ( ) 表示获得关于集合x 的知识是否完全 的程度。因为艮( ) ( ) r ( x ) - - c a r d ( r ( x ) ) - c a r d ( r + ( x ) ) ，所以o or ( x ) 1 。当 ar ( x ) = l 时b n r ( x ) = o ，x 是精确可定义的；当r ( x ) 1 时，b n r ( x ) o ， 因此