一个基于决策粗糙集理论的信息过滤模型

维普资讯 http://www.cqvip.com Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃｏｔｉｏｎａ计算机工程与应用　２００７．４３（７）　１８５　一个基于决策粗糙集理论的信息过滤模型　赵文清，朱永利，高　伟　ＺＨＡＯ　Ｗｅｎ－ｑｉｎｇ，ＺＨＵ　Ｙｏｎｇ－ｌｉ，ＧＡＯ　Ｗｅｉ　华北电力大学计算机科学与技术学院．河北保定０７１００３　Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎｏｒｔｈ　Ｃｈｉｎａ　Ｅｌｅｃｔｒｉｃ　Ｕｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ，Ｈｅｂｅｉ　０７　１００３，Ｃｈｉｎａ　Ｅ—ｍａｉｌ：ｊｂｚｗｑ＠１２６．ｃｏｍ　ＺＩ－ＩＡＯ　Ｗｅｎ—ｑ．ｍｇ，ＺＨＵ　Ｙｏｎｇ－ｌｉ，ＧＡＯ　Ｗｅｉ．Ｉｎｆｏｒｍａｔｉｏｎ　ｍｔｅｒｍｇ　ｍｏｄｅｌ　ｂａｓｅｄ　ｏｎ　ｄｅｃｉｓｉｏｎ－ｔｈｅｏｒｅｔｉｃ　ｒｏｕｇｈ　ｓｅｔ　ｔｈｅｏｒｙ．　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（７）：１８５—１８７．　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｄｅｃｉｓｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｒｏｕｇｈ　ｓｅｔ　ｔｈｅｏｒｙ　ａｎｄ　ｐｒｅｓｅｎｔｓ　ａ　ｄｅｃｉｓｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｒｏｕｇｈ　ｓｅｔ　ｂａｓｅｄ　ｍｏｄｅｌ　ｔｏ　ｉｆｌｔｅｒ　ｉｎｆｏｒｍａｔｉｏｎ，ｂｙ　ｃｏｍｐａｒｉｎｇ　ｗｉｔｈ　ｔｒａｄｉｔｉｏｎａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｉｌｔｅｒｉｎｇ　ｍｅｔｈｏｄｓ　ｌｉｋｅ　Ｎａｉｖｅ　Ｂａｙｅｓ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｏｄｅｌ　ｈａｓ　ｈｉｇｈ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　ｃａｎ　ｒｅｄｕｃｅ　ｅｒｒｏｒ　ｒａｔｉｏ．　Ｋｅｙ　ｗｏｒｄｓ：Ｄｅｃｉｓｉｏｎ－Ｔｈｅｏｒｅｔｉｃ　Ｒｏｕｇｈ　Ｓｅｔ（ＤＴＲＳ）；ｉｆｏｒｎｍａｔｉｏｎ　ｆｉｌｔｅｒｉｎｇ；Ｎａｉｖｅ　Ｂａｙｅｓ　摘要：介绍了决策粗糙集理论，提出了一个基于决策粗糙集理论的通用信息过滤模型，并通过对电子邮件进行过滤，与传统的基　于文本内容的信息过滤方法——朴素贝叶斯方法进行了比较，比较结果证明该文提出的基于决策粗糙集理论的信息过滤模型可　以降低误判率．有较高的正确率。　关键词：决策粗糙集；信息过滤；朴素贝叶斯　文章编号：１００２—８３３１（２００７）０７－０１８５－０３　文献标识码：Ａ　中图分类号：ＴＰ３１１　１　引言　因特网给人们的生活带来了极大的便利，但是因特网中也　对决策支持进行近似性推理的数学工具，也可以用于对象分　类，其最大的贡献在于给出了机器学习的理论基础，定义了独　立约简和正区域已经用来划分对象。由Ｙａｏ和Ｗｏｎｇ提出的决　策粗糙集　理论，继承了原有粗糙集模式的所有基本属性，针　对于不确定信息的处理。本文首先介绍决策粗糙集理论。　存在着有害信息，比如垃圾邮件、色情以及暴力等有关内容，可　以通过信息过滤来拦截这些内容。信息过滤是指计算机根据用　户提供的需求，从动态变化的信息流（比如Ｗｅｂ、Ｅ—ｍａｉｌ）中自　动检索出满足用户需求的信息。目前针对文本的信息过滤技术　２．１粗糙集理论基础　设一个决策系统　＝＜ｕ，Ａ，ｄ＞，其中　，　，…，　｝是一　个非空对象集合（ｎ是对象的个数）；Ａ＝　，ａ２，…，　｝表示非空　的条件属性集合（ｍ表示属性个数），同时存在映射　—　，　主要采用的是基于贝叶斯算法的信息过滤器『ｌ】，也有一些采用　遗传算法、支持向量机［２１等。传统的信息过滤技术存在“准确性　不足”、易“误判”等问题。所谓“误判”是指原本是用户感兴趣的　信息却被判定为用户不感兴趣的信息，从而被漏掉，在当今的　信息社会，有可能给用户造成巨大的损失。　本文提出了把决策粗糙集理论￣－￣（ＤＴＲＳ，Ｄｅｃｉｓｉｏｎ—Ｔｈｅｏｒｅｔｉｃ　Ｒｏｕｇｈ　Ｓｅｔ　Ｔｈｅｏｒｙ）应用到信息过滤中。用基于决策粗糙集理论　的信息过滤方法对文本信息进行过滤。信息过滤可以针对无结　构的或半结构化的数据进行。而电子邮件是典型的半结构化数　据，有着结构化的邮件头和无结构的邮件正文，同时对邮件过　滤也是对信息过滤的一种应用。因此，本文利用ＵＣＩ机器学习　数据资料库中的电子邮件数据集进行了实验。实验表明，该方　表示Ａ中所有属性　，ａｚ，…，　｝的值域；ｄ是不属于Ａ的决策　属性。如果在　的分量中没有决策属性，则称　为信息系统。　定义１设　＜Ｕ。Ａ＞是一个信息系统，ＢＣＡ且　ＢＸ＝（ｘｌ［ｘ］ｎ　＿Ｘ）Ｃ　ＢＸ＝（ｘｌ［ｘ］ｎ　ｆｉＸ≠　）　Ｕ。通过构　造　关于　的上近似和下近似来表示　的近似，分别表示为　其中　是　的不可分辨关系的等价类。　定义２粗糙集理论中，根据现有知识及不可分辨关系　，　元素　是否属于集合　的不确定性，可以用粗糙隶属函数来表　示。其定义如下：　：　法不仅理论上易于建立和更新，而且降低了信息过滤的误判　率。下面首先对决策粗糙集理论做一个简要的介绍。　２决策粗糙集理论　１９８２年波兰数学家Ｐａｗｌａｋ／ｓ３提出了粗糙集理论。它是一种　基金项目：教育部“新世纪优秀人才”支持计划（Ｎｏ．ＮＣＥＴ－０４－０２４９）。　作者简介：赵文清（１９７３一），女，讲师，主要研究方向：人工智能和数据挖掘。　［０＇ｌ邮　＝　通过粗糙隶属函数可以定义集合　的正区域Ｐｏｓ（ｘ），负　维普资讯 http://www.cqvip.com １８６　２００７，４３（７）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　区域ＮＥｅ（Ｘ）和边界区域ＢＮＤ（Ｘ）分别为　Ｒ　ＰＯＳ（ｘ）＝Ｂ　Ｘ．＝｛ｘ　（　）≥订｝　Ｒ　ＮＥＧ（　）＝　Ｘ＝Ｕ－｛ｘ　（　）＞ｌ一订｝　ＢＮＤ０Ｘ　：Ｂ　Ｘ一　Ｘ　其中，订∈（　，ｌ】，表示粗糙度或精确度，可以看作划分对象时　二　的阈值。也就是说，利用粗糙集理论，可以把数据集分为３部　分：正区域、负区域和边界。限于篇幅，有关粗糙集的其它概念，　诸如可辨识矩阵和函数等，请参看参考文献【７】。下面，本文将介　绍如何在原有的粗糙集方法的基础之上应用决策粗糙集理论　建立信息过滤模型。　２．２决策粗糙集理论　原有的粗糙集方法为数据分析提供了形式化的工具。由Ｙａｏ　和Ｗｏｎｇ提出的决策粗糙集理论（Ｄｅｃｉｓｉｏｎ－Ｔｈｅｏｒｅｔｉｃ　Ｒｏｕｇｈ　Ｓｅｔ　ｈＴｅｏｒｙ）继承了原有粗糙集的基本特点．同时增强了处理不确　定信息的能力。在决策粗糙集理论中，用状态集　，］　｝表　示一个元素是否属于集合　，动作集Ａ＝｛ｎ。，ｎ２，Ⅱ３｝分别表示判　定当前对象　属于ＰＯＳ（Ｘ）、ＮＥＧ（Ｘ）和ＢＮＤ（Ｘ）的动作。　ｎ．表示判定当前对象　∈ＰＯＳ（Ｘ）；　表示判定当前对象　∈ＮＥＧ（Ｘ）；　表示判定当前对象　∈ＢＮＤ（Ｘ）。　用Ａ（ｎ．Ｉｘ∈　）表示当对象　∈Ｘ时，执行动作ｎ　所引起的　损耗，用Ａ（ａｉＩｘ∈７　）表示当对象　∈－ｑ　Ｘ时，进行活动ａｉ所引　起的损耗。　这样，进行三种不同活动的估计损耗值皿（儡Ｉｘ）为　ＥＬ（ａｌ　ｋ）＝ＡｌｌＰ（Ｘ，　）＋Ａｌ２Ｐ（７　Ｘ，　）　观（ｎ２ｋ）＝Ａ２ｌＰ（Ｘ，　）＋Ａ２２Ｐ（７　Ｘ，　）　Ｊ观（ａ３ｋ）＝Ａ１ｌＰ（Ｘ，　）＋Ａ３２Ｐ（７　Ｘ，　）　其中，Ｐ（Ｘ，　）和Ｐ（７　Ｘ，　）分别表示　属于　和　属于］　的　概率，Ａ。ｌ＝Ａ（ａｌｘ∈　），Ａ　＝Ａ（ａｉＩｘ∈７　），　＝ｌ，２，３。按照贝叶斯　决策过程可以推导出下面的最小风险决策规则ＲＵＬ　．Ｂ（ＲＵＬ　，　ＲＵＬⅣ，ＲＵＬＢ）：　ＲＵＬＰ：如果ＥＬ（ａｌｋ）≤皿（ｎ２Ｉｘ）并且ＥＬ（ａｌｋ）≤皿（Ⅱ３Ｉｘ），　那么　∈ＰＤ５（　）；　ＲＵＬⅣ：如果皿（ｎ２Ｉｘ）￣ＥＬ（ａｌｋ）并且皿（ｎ２Ｉｘ）≤皿（ｎ３ｋ），　那么　∈ＮＥＧ（Ｘ）；　ＲＵＬＢ：如果皿（Ⅱ３Ｉｘ）≤皿（ｎｌＩｘ）并且皿（Ⅱ３Ｉｘ）＜￣ＥＬ（ａ２１ｘ），　那么　∈ＢＮＤ（Ｘ）。　由于Ｐ（Ｘ，　）＋Ｐ（７　Ｘ，　）＝ｌ，上面的决策规则可以化简成　只含有概率ｐ（ｘ．　）的形式。因此可以根据概率Ｐ（Ｘ，　），也就　是给定损耗函数Ａ　（　＝ｌ，２，３　＝ｌ，２）和前面２．１节中的粗糙隶　属函数来划分对象　属于哪一区域。　当Ａｌｌ≤Ａ３ｌ＜Ａ２ｌ且Ａ２２≤Ａ３２＜Ａｌ２时，表示对象　ｅＸ时，将　对象　划分到正区域ＰＯＳ（Ｘ）的损耗小于等于将　划分到边界　区域ＢＮＤ（Ｘ）的损耗。并且两种损耗都严格小于将　划分到负　区域ＮＥＧ（Ｘ）的损耗。反之，将一个不属于　的对象划分到　会得到相反的顺序。对于这种类型的损耗函数，最小风险决策　规则ＲＵＬ　（ＲＵＬＰ，ＲＵＬⅣ，ＲＵＬＢ）可以写作：　．ＢＲＵＬ　：如果Ｐ（Ｘ，　）≥卢且Ｐ（Ｘ，　）≥　，习Ｂ么　∈ＰＯＳ（Ｘ）；　ＲＵＬⅣ：女口果Ｐ（Ｘ，　）≤　且Ｐ（Ｘ，　）≤６，习Ｂ么　∈ＮＥＧ（Ｘ）；　ＲＵＬＢ：如果６≤Ｐ（　，　）且Ｐ（Ｘ，　）≤卢，那么　∈ＢＮＤ（Ｘ）。　其中：　ｏ　Ａｌ２一Ａ３２　Ｐ＝　＝　（Ａ２ｌ—Ａｌ１）＋（ＡｌＬ２一Ａ２　２）　（、２）二　　一　銎　。（Ａ２ｌ—Ａ３１）＋（Ａ３２－Ａ２２）　由条件Ａｌｌ≤Ａ３ｌ＜Ａ２ｌ且Ａ２２≤Ａ３２＜Ａ　可知卢∈（０，１），　∈　（０，１），６∈【０，ｌ】。此时，决策规则ＲＵＬ　只依赖于参数卢、　和　．Ｂ，它们可以由用户给出Ａ　值直接计算出来。　若６≤卢，６≤　≤卢，根据决策规则ＲＵＬ　正区域、负区域　和边界区域可以由６和卢来决定。若　，就有卢ｑ　。根据　ＲＵＬ　．Ｂ可知边界区域为空，而此时正区域和负区域可由　来　决定。为了区分三个区域，令６　，即有６ｑ　。此外，当判定　∈ＮＥＧ（Ｘ）和　∈ＢＮＤ（Ｘ）的风险相同时，则判定　∈ＢＮＤ（Ｘ）。　如果判定　∈ＰＯＳ（Ｘ）和　∈ＢＮＤ（Ｘ）的风险一样，则判定　∈　ｐｏｓ（ｘ）。在这些假设前提下，决策规则ＲＵＬ　．Ｂ可以简化为　ＲＵＬ　：如果Ｐ（Ｘ，　）≥卢且６≤　≤卢，那么　∈ＰＯＳ（Ｘ）；　ＲＵＬ　：如果Ｐ（Ｘ，　）　，那么　∈ＮＥＧ（Ｘ）；　ＲＵＬＢ：如果６≤Ｐ（　，　）　，那么　∈ＢＮＤ（Ｘ）。　为了实现信息过滤的目的．要考虑一种特殊类型的损耗函　数。可以认为把一个实际上属于　的对象　划分到正区域　ＰＯＳ（Ｘ）的损耗为眦也就是　被认为是正对象，因此没有损　耗）。相反的情况下，把一个实际上属于　的对象　划分到负　区域ＮＥＧ（Ｘ）的损耗为最大损耗值ｌ。划分到边界区域的损耗　是介于０和ｌ之间的某个值。基于这种假设，可有　ＡＩｌ＝０，Ａｌ２＝ｌ　Ａ２ｌ＝ｌ，Ａ２２＝０　（３）　０≤　３ｌ＜ｌ，０≤Ａ３２＜ｌ　利用公式（３）可将公式（２）中的估计损耗函数简化为下面　的形式：　在这个假设的基础上，如果能够估计Ｐ（Ｘ，　）的值以及损　耗值Ａ，。和Ａ　就可以把任何对象划分到三个区域其中之一了。　２．３估计Ｐ｛Ｘ，　）的值以及损耗值Ａ３，和Ａ３２　令ＲＵＬ表示所有的决策规则，ＲＵＬ（ｘ）Ｃ＿ＲＵＬ表示命中对　象　或至少有一个蕴含前项与　匹配的规则的集合。　Ｐ（Ｘ　＝　×荟ｐｒｅｄｃｉｔｓ（胁ｅ）　其中，ＣＥＲ　表示所有与对象　匹配的规则总数的总和，ｐｒｅｄｉｃｔｓ　（Ｌｉｋｅ）代表用户感兴趣的信息，其值是ａｃｃｕｒａｃｙ（ａ－－｝ｂ）啕：　删ｕｒａｃｙ（　）＝　Ｓ　Ｕｐ　ｐＯ￣　‘ｎ　Ｊ　ａｃｃｕｒａｃｙ（ａ－－－￣）表示由证据ｎ得出结论ｂ的规则的可信度，　而且是对条件概率Ｐｒ（ｂｌａ）的基于频率的估计。　用曰表示出现在决策规则　的前项ｎ中的属性的集　合，　表示ｂ所描述的用户感兴趣的信息。　维普资讯 http://www.cqvip.com 赵文清，朱永利，高　伟：一个基于决策粗糙集理论的信息过滤模型　ｓｕｐｐｏｒｔ（ａ）是含有证据　的属性的信息系统中对象的数量．　ｓｕｐｐｏｒｔ（ｂ）是含有ｂ所描述的属性的信息系统中对象的数量。　因此ａｃｃｕｒａｃｙ（ａ－￣ｂ）与粗糙隶属函数　的值相同，其中这　个隶属函数应用于与ａ匹配的对象　。这样，ａｃｃｕｒａｃｙ（ａ－￣ｂ）利　用属性集曰测量　关于　的隶属度，可以看作Ｐ（Ｘ，　）的估　６－＝　｜　－￣３２　；　２００７４３（７）　．１８７　；　Ｆｏｒ　∈Ｄｉｓ—Ｚ：　Ｄｏ　｛　Ｉｆ　Ｒ比（　）＝　Ｍａｙｂｅ＝Ｍａｙｂｅｕ恤｝　Ｅｌｓｅ　计值。　在本模型中，Ａｌｌ＝Ａ２２：０，Ａｌ２：Ａ２ｌ：１，同时令０＜Ａ３ｌ＜１，０＜Ａ３２＜　１，若６≤Ｐ（　，　）　，则由ＲＵＬ　判定　∈ＢＮＤ（Ｘ），由以上可以　得出结论：如果Ａ　Ａ　接近于０，则／３增大，６减小。边界区域　ＢＮＤ（Ｘ）扩大，这就意味着用户认为将　划分到ＢＮＤ（Ｘ）的损　耗很小，所以理论上可以降低将用户感兴趣的信息划分为用户　不感兴趣的信息的错误率。如果Ａ，．：Ａ，　：０．２，则／３＝ｏ．８，８＝０．２，　决策规则ＲＵＬ　可以简化为　｛　Ｒ＝｛ｒ∈ＲＵＬ（ｘ）ｌｒ　ｐｒｅｄｉｃｔｓ　Ｌｉｋｅ｝；Ｉ＊Ｒ是所有认为　属于Ｌｉｋｅ　的规则　，　估计Ｒｅｌ（Ｄｉｓ—ＴＥＩｘ∈Ｌｉｋｅ）；　Ｒｅｌ（Ｄｉｓ—ＴＥＬｘＥＬｉｋｅ）＝￣ｐｒｅｄｉｃｔｓ（Ｌｉｋｅ）；　Ｌ　：女口果Ｐ（Ｘ，　）≥０．８，习　么　∈ＰＯＳ（Ｘ）；　ＲＵＬ　：女口果Ｐ（Ｘ，　）＜０．２，习　么　∈ＮＥＧ（Ｘ）；　ＲＵＬ　：如果０．２≤Ｐ（　，　）＜０．８，那么　∈ＢＮＤ（Ｘ）。　ｃｅ　壶　ｌ（Ｄｉｓ埘　Ｉｆ　Ｃｅｒｔ≥６ｌ　Ｌｉｋｅ＝Ｌｉｋｅ　ｕ恤｝　ｘＥｌｓｅ　ｉｆ（ｂ２＜￣Ｃｅｒｔ＜ｂ１）Ｍａｙｂｅ＝Ｍａｙｂｅｕ恤ｌ　Ｅｌｓｅ　Ｕｎｌｉｋｅ＝Ｕｎｌｉｋｅｕ恤｝　｝　｝　　’这也是本文案例所选用的阈值。　３建立基于决策粗糙集理论的信息过滤模型　在以上的概念和知识的基础上，本文提出了基于决策粗糙　集（ＤＴＲＳ）理论的信息过滤方案。在本文中，正区域代表用户感　兴趣的信息，负区域代表用户不感兴趣的信息，边界代表介于　二者之间的信息。本文的目的是把用户感兴趣的信息划分为用　Ｏｕｔｐｕｔ：三种信息－Ｌｉｋｅ，Ｕｎｌｉｋｅ和Ｍａｙｂｅ。　４实验结果与分析　如前所述．本文提出的ＤＴＲＳ模型能够降低将用户感兴趣　的信息划分为用户不感兴趣的信息的错误率，为了能够验证这　一户不感兴趣的信息的比例最大可能地降至最低，避免“误判”，　更好地服务于用户。主要步骤如下：　（１）首先把源信息数据集转换为一个决策系统￡，把￡分　为两部分，训练数据集豫和测试数据集陋。然后从豫导出　一点，进行了实验对比。实验数据来自于ＵＣＩ机器学习数据资　料库（ｈｔｔｐ：／／ｗｗｗ．ｉｅｓ．ｕｅｉ．ｅｄｕ／ｍｌｅａｒｎ／ＭＬＲｅｐｏｓｉｔｏｒｙ．ｈｔｍ１）。实验以　４／５的数据对象作为豫（３　６８１个对象），１／５的数据对象作为　ＴＥ（９２０个对象）。参数ｂ．：０．８，ｂ，：０．２。并同基于朴素贝叶斯方　法的实验结果进行了比较。下面分别给出基于本文模型和朴素　贝叶斯方法的实验结果。　个信息过滤器，并把该过滤器用于阿得到学习的结果，因　此，对豫需要做第（２）步和第（３）步的工作。　（２）使用Ｂｏｏｌｅａｎ　ｒｅａｓｏｎｉｎｇ算法［９１进行属性值的离散化。得　到一个关于决策属性的最小割集。　（３）使用遗传算法ＧＡ求得约简之后的规则。ＧＡ已经被集　成到许多粗糙集工具中，如Ｒｏｓｅｔｔａ（ｈｔｔｐ：／／ｒｏｓｅｔｔａ．１ｃｂ．ＵＵ．ｓｅ．），而　本文的实验也用到了Ｒｏｓｅｔｔａ这个工具软件。执行完第（３）步之　后，对测试集陋继续执行第（４）步。　（４）首先利用在第（２）步中得到的ｃｕｔｓ离散化ＴＥ，然后利　本文把数据集的４／５（３　６８１个对象）作为ＴＲ，数据集的１／５　（９２０个对象）作为ＴＥ，在ＴＥ中有５７２封用户感兴趣的信息（正　常邮件），３４８封用户不感兴趣的信息（垃圾邮件）。在训练阶段　输出的是割集和决策规则，据此对含有９２０个对象的阿进行　过滤，结果如表１所示。　表ｌ基于ＤＴＲＳＴ模型的实验结果ＺＲ　（４／５，３　６８１个对象）　用第（３）步得到的规则对陋中的对象进行匹配和判断，这样，　就在基于决策粗糙集理论的基础之上完成了对陋中的对象　的过滤。　令ｂ　为正区域的极限（即２．２节中的卢），ｂ，为负区域的极　限（即２－３里的６）。下面的算法描述了如何预测一条信息在正　区域、负区域还是边界区域。　算法Ｆｉｌｔｅｒ（Ｄ／ｓ—ＴＥ，ＲＵＬ，Ａ３ｌ，Ａ３２）。　／＊Ｄｉｓ—ＴＥ是指离散化之后的ＴＥ．ＲＵＬ指在第（３）步中得到的规则。　可以看出．基于本文的过滤模型，在５７２封用户感兴趣的　邮件中，有５１０封被划分为用户感兴趣的邮件，有６封被划分　为用户不感兴趣的邮件，５６封被认为是用户可能感兴趣，也可　能不感兴趣的邮件。基于相同情况．使用朴素贝叶斯分类方法，　结果如表２所示。在５７２封用户感兴趣的邮件中，有５４４封被划　分为用户感兴趣的邮件，有２８封被划分为用户不感兴趣的邮件。　实验中，使用ＤＴＲＳ模型有６条用户感兴趣的信息被划分　为用户不感兴趣的信息，而使用朴素贝叶斯模型有２８条用户　感兴趣的信息被划分为用户不感兴趣的信息。由此可见，在相　（下转１９４页）　ＲｅＺ（）指对象　属于用户感兴趣的信息的相关度。ＣＥＲ　指判定　为用　户感兴趣的信息的规则总数。　，　Ｌｉｋ　，Ｕｎｌｉｋｅ，　ｅ＋一　／＊Ｌｉｋｅ、Ｕｎｌｉｋｅ、Ｍａｙｂｅ分别代表用户感兴　趣的信息、用户不感兴趣的信息和可能感兴趣的信息，初始化均为空　集　｝，　Ａ３ｌ　、３２－－－０．２；　维普资讯 http://www.cqvip.com １９４　２００７，４３（７）　Ｃｏｍｐｕｔｅｒ　Ｅｎ￣ｎｅｅｎｎｇ　ａｎｄ、Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　成较少的候选频繁访问模式。经过算法分析和实验验证本算　法具有一定的实用价值。（收稿日期：２００６年７月）　，图ｌ给出了基于不同的最小支持度阈值。两个算法各自的　运行时间。当最小支持度阈值很高时，ＧＩＴＣ算法的性能不够理　想。当最小支持度阈值小于７％时，可以看出ＧＩＴＣ算法一直比　类Ａｐｆｉｏｆｉ算法优越。随着支持度的减小，用类Ａｐ　ｏｒｉ算法挖　参考文献：　【ｌ】韩家炜，盂小峰，王静，等．Ｗｅｂ挖掘研究［Ｊ】．计算机研究与发展，　２００１，３８（４）：３０５－３１４．　掘所用的时间呈现不断上升的趋势，而ＧＩＴＣ算法却有很平稳　的时间性能。当最小支持度阈值偏小时本算法表现出很好的性　能，这正好和算法特点分析的结果相吻合。同时由实验结果推　知：与类Ａｐｆｉｏｆｉ算法相比。用ＧＩＴＣ算法一次统计出所有支持　【２】欧阳一鸣，汪曦东，郭骏，等．Ｗｅｂ使用挖掘数据预处理中的会话构　造［Ｊ】．计算机工程与应用，２００５，４１（２５）：１４８—１５１．　数对应的最大访问模式集。然后再查询出所需要的挖掘结果将　会更高效。　［３】Ｃｏｏｌｅｙ　Ｒ，Ｍｏｂａｓｈｅｒ　Ｂ，Ｓｒｉｖａｓ￣ｖａ　ＬＯａｔａ　ｐｒｅｐａｒａｔｉｏｎ　ｆｏｒ　ｍｉｎｉｎｇ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ　ｂｒｏｗｓｉｎｇ　ｐａｔｔｅｒｎｓ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，　１９９９，ｌ（１）．　［４】陈敏，欧阳一鸣，刘红樱．Ｗｅｂ挖掘中基于ＲＤ＿Ａｐｒｉｏｒｉ算法发现用　户频繁访问模式［Ｊ】．微电子学与计算机，２００５，２２（５）：４—７．　【５】欧阳一鸣，陈敏，刘红樱，等．Ｗｅｂ挖掘中发现用户访问模式算法的　改进与分析［Ｊ】．模式识别与人工智能，２００５，１８（６）：７２８—７３４．　［６】Ｗａｎｇ　Ｘｉ－ｄｏｎｇ，Ｏｕｙａｎｇ　Ｙｉ—ｍｉｎｇ，Ｈｕ　Ｘｕｅ—ｇａｎｇ，ｅｔ　ａ１．Ｄｉｓｃｏｖｅｒｙ　ｏｆ　ｕｓｅｒ　ｆｒｅｑｕｅｎｔ　ａｃｃｅｓｓ　ｐａｔｔｅｒｎｓ　ｏｎ　Ｗｅｂ　ｕｓａｇｅ　ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｕｐｐｏｒｔｅｄ　Ｃｏ—　支持度，％　ｏｐｅｒａｔｉｖｅ　Ｗｏｒｋ　ｉｎ　Ｄｅｓｉｇｎ，２００４：７６５—７６９．　图ｌ运行时间比较图　【７】Ｃｈｅｎ　Ｍｉｎｇ－ｓｙａｎ，Ｊｏｎｇ　ＳｏｏＰａｒｋ，Ｙｕ　Ｐ　Ｓ．Ｄａｔａ　ｍｉｎｉｎｇ　ｆｏｒ　ｔｒａｖｅｒｓａｌ　ｐａｔｔｅｒｎｓ　ｉｎ　ａ　Ｗｅｂ　ｅｎｖｉｒｏｎｍｅｎｔ．１９９６　ＩＥＥＥ．　７结束语　与类Ａｐｆｉｏｆｉ算法相比，本文提出的ＧＩＴＣ算法的主要特　点是：　【８】王培吉，王培静，白金牛．关联规则挖掘的一种改进算法［Ｊ】．包头钢　铁学院学报，２００３，２２（１）：８６—８９．　【９】徐健辉．生成频繁项集的逻辑“与”运算算法［Ｊ】．计算机应用，２００４，　２４（１１）：８８－９０．　（１）ＧＩＴＣ算法只要扫描原始事务数据库两次：一次扫描原　始数据库生成所有的候选频繁访问模式．一次扫描原始数据库　来统计各个候选频繁访问模式的支持度计数；　（２）当用户设置的最小支持度阈值偏小时，ＧＩＴＣ算法会生　【ｌＯ】周焕银，张永，蔺鹏．一种不产生候选项挖掘频繁项集的新算法［Ｊ】．　计算机工程与应用，２００４，４ｏ（１５）：１８２—１８５．　【ｌｌ】白石磊，毛雪岷，王儒敬，等．一种快速挖掘频繁项目集算法［Ｊ】．模　式识别与人工智能，２０ｏ３，１６（４）：４６５－－４６９．　（上接１８７页）　表２基于朴素贝叶斯算法的实验结果豫　（４／５，３　６８１个对象）　参考文献：　【ｌ】Ｓａｈａｍｉ　Ｍ．Ａ　Ｂａｙｅｓｉｎ　ａｐｐｒｏａｃｈ　ｔａｏ　ｆｉｌｔｅｒｉｎｇ　Ｊｕｎｋ　Ｅ—ｍａｉｌ［Ｃ］／／Ｌｅａｒｎ—　ｉｎｇ　ｆｏｒ　Ｔｅｘｔ　Ｃａｔｅｇｏｒｉｚａｔｉｏｎ：Ｐａｐｅｍ　ｆｒｏｍ　ｔｈｅ　１９９８　Ｗｏｒｋｓｈｏｐ．ＡＡＡＩ　Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ　ＷＳ一９８－０５，１９９８．　【２】Ｃｒｉｓｔｉｎｉｎｉａ　Ｎ．Ａｎ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　Ｓｕｐｐｏｒｔ　Ｖｅｃｔｏｒ　Ｍａｃｈｉｎｅｓ　ａｎｄ　ｏｔｈｅｒ　ｋｅｒｎｅｌ－ｂａｓｅｄ　ｌｅａｒｎｉｎｇ　ｍｅｔｈｏｄｓ［Ｍ］．Ｃａｍｂｒｉｄｇｅ：Ｃａｍｂｒｉｄｇｅ　Ｕｎｉｖｅｒｓｉｔｙ　Ｐｒｅｓｓ．２ｏｏ２．　【３】Ｙａｏ　Ｙ　Ｙ，Ｗａｎｇ　Ｓ　Ｋ　Ｍ．Ａ　ｄｅｃｉｓｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ａｐｐｒｏ－　同情况下．使用基于决策粗糙集理论的过滤模型会有较少的用　户感兴趣的信息（非垃圾邮件）被划分为用户不感兴趣的信息　（垃圾邮件）。因此，可以得出结论：一般情况下ＤＴＲＳ模型要优　于Ｎａｉｖｅ　Ｂａｙｅｓ算法。　综上所述，本文提出的基于决策粗糙集理论的信息过滤模　型是有效的。　ｘｉｍａｔｉｎｇ　ｃｏｎｃｅｐｔｓ［Ｊ】．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｎ—ｍａｃｈｉｎｅ　Ｓｔｕｄｉｅｓ，　１９９２，３７（６）：７９３－８０９．　［４１　Ｙａｏ　Ｙ　Ｙ．Ｉｆｏｒｍａｔｎｉｏｎ　ｇｒａｎｕｌａｔｉｏｎ　ａｎｄ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ｉｎ　ａ　ｄｅｃｉｓｉｏｎ—　ｈｅｏｒｅｔｔｉｃ　ｍｏｄｅｌ　ｏｆ　ｒｏＵｓｈ　ｓｅｔｓ，ｏＵｇｈ－ｎｅｕｒｒｏ　ｃｏｍｐｕｔｉｎｇ：ａ　ｗａｙ　ｔｏ　ｃｏｉｎ－　ｐｕｔｉｎｇ　ｗｉｔｈ　ｗｏｒｄｓ［Ｍ］．Ｈｅｉｄｅｌｂｅｒｇ：Ｐｈｙｓｉｃａ—Ｖｅｒｌａｇ，２００２．　【５】Ｐａｗｌａｋ　Ｚ．ＲｏｔＩｓｈ　ｓｅｔｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎ－　ｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，１９８２，ｌｌ：３４１－３５６．　５结论　本文提出了基于决策粗糙集理论信息过滤模型．将接收到　的信息划分为三类——用户感兴趣的信息、用户不感兴趣的信　息和用户可能感兴趣的信息。实验结果表明基于决策粗糙集理　［６】陆汝钤．知识科学与计算科学【Ｍ】．北京：清华大学出版社，２００３．　【７】Ｐａｌ　Ｓ，Ｓｋｏｗｒｏｎ　Ａ．Ｒｏｕｓｈ　ｆｕｚｚｙ　ｈｙｂｒｉｄｉｚａｔｉｏｎ：ａ　ｎｅｗ　ｔｒｅｎｄ　ｉｎ　ｄｅｃｉ—　ｓｉｏｎ－ｍａｋｉｎｇ［Ｍ］．ｉｓ．１．】：Ｓｐｒｉｎｇ￣，１９９９．　【８】Ａｌｅｋｓａｎｄｅｒ　Ｈ．Ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ　ａｎｄ　ｒｏＵｓｈ　ｓｅｔｓ　ｉｎ　ｍｅｄｉｃｉｎｅ［Ｄ］．Ｎｏｒｗａｙ：　Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，Ｎｏｒｗｅｇｉｎ　Ｕｎｉａ—　论的信息过滤模型能够降低将用户感兴趣的信息划分为用户　不感兴趣的信息的错误率。在以后的工作中，可以结合信息过　ｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，１９９９．　【９】Ｓｋｏｗｒｏｎ　Ａ，Ｓｏｎ　Ｎ．Ｂｏｏｌｅａｎ　ｒｅａｓｏｎｉｎｇ　ｓｃｈｅｍｅ　ｗｉｔｈ　ｓｏｍｅ　ａｐｐｌｉｃａｔｉｏｎｓ　ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ［Ｃ］／／ＬＮＡＩ　１７０４：Ｄｉｓｃｏｖｅｒｙ　ＰＫＤＤ’９９，Ｐｌａｇｕｅ，Ｃｚｅｃｈ　Ｒｅｐｕｂｌｉｃ．Ｂｅｒｌｉｎ：Ｓｐｎ‘ｎｇｅｒ　Ｖｅｒｌａｇ。１９９９：１０７－１１５．　滤的其它技术，进一步提高信息过滤的准确性。　（收稿日期：２００６年８月）