（管理科学与工程专业论文）模糊和粗糙环境下的网络用户浏览模式研究.pdf

中文摘要 本文从w e b 使用挖掘的序列分析和聚类分析中对w e b 日志进行分析研究， 发现人们感兴趣的浏览模式从w e b 日志中提取出的有用知识可被用于网站设 计、分析系统性能以及网络通讯、理解用户的行为和动机，以及建立个性化的网 站等本文针对用户浏览模式的特点，就用户浏览模式的挖掘和聚类进行了深入 的分析和研究，主要工作如下： 提出了基于f r e q u e n tl i n k _ a n da c c e s st r e e ( f l a a t ) 的用户浏览模式的挖 掘算法，f l a a t 存储了所有用户的浏览信息，在搜索用户偏爱模糊路径时考虑 到了不同前缀的相同子路径的合并问题，使得挖掘信息更完整 给出了模糊环境下使用语言最小支持度和偏爱度挖掘用户模糊偏爱浏览路 径算法，网页上的浏览时间被刻画成模糊语言变量，这样所挖掘出的带模糊时间 值的偏爱路径更能反映用户的兴趣和偏爱程度此外，语言的输入输出控制更自 然、更符合人的推理方式 定义了模糊偏爱度概念，它和表示用户访问频度的支持度一起反映用户的兴 趣和偏爱程度同时给出了基于模糊偏爱度的用户浏览模式的有效挖掘算法模 糊偏爱度综合考虑了网页的权重、网页的相对访问频度和网页上的浏览时间，因 而它更能体现用户的兴趣和偏爱 设计了一种模糊的粗糙近似法用于对w e b 日志中的用户浏览模式进行聚 类在聚类过程中，每个用户浏览模式被表示成等长的模糊向量的形式，以表示 该用户访问过的网页及网页上的模糊浏览时间，最后使用粗糙近似的方法对表示 用户浏览行为的模糊向量进行聚类 提出了模糊环境下基于粗糙k 一均值的聚类方法每个用户浏览模式都被转 换成具有相等长度的模糊向量，然后对代表用户浏览特征的模糊向量使用粗糙 薜均值进行聚类 通过实例分析和相应实验测试，验证了本文所提出算法的有效性与合理性 关键词：数据挖掘，w e b 挖掘，软w e b 挖掘，用户浏览模式，模糊变量，模糊模 拟，聚类 a b s t r a c t w e bl o gi si n v e s t i g a t e dt of i n du s e ri n t e r e s t i n ga c c e s sp a t t e r n si nw e bs e q u e n t i a la n a l y s i sa n dc l u s t e r i n ga n a l y s i s k n o w l e d g ee x t r a c t e df r o mw e bl o g s c a nb eu s e dt oi m p r o v ed e s i g no fw e bs i t e s ，a n a l y z es y s t e mp e r f o r m a n c ea sw e l l a , sn e t w o r kc o m m u n i c a t i o n ，u n d e r s t a n du s e rr e a c t i o na n dm o t i v a t i o n ，a n db u i l d a d a p t i v ew e bs i t e s t h o r o u g hr e s e a r c h e sa r em a d et ou n d e r s t a n dt h ec h a r a c t e r i s t i co fu s e ra c c e s sp a t t e r n sb yw e bs e q u e n t i a la n a l y s i sa n dc l u s t e r i n ga n a l y s i s m a j o rw o r k sa r el i s t e da sf o l l o w s ： t h ea l g o r i t h mb a s e do nf r e q u e n t l i n k a n d a c c e s st r e e ( f l a a t ) i sp r o p o s e d t om i n ef r e q u e n tu s e ra c c e s sp a t t e r n s f l a a ts t o r e sa l lu s e ra c c e s si n f o r m a t i o n a n dc o n s i d e r st h em e r g eo fs a m er o u t e sw i t hd i f f e r e n tp r e f i x e st om a k et h ei n t e g r a t i o no fm i n e di n f o r m a t i o nd u r i n gs e a r c ho ff r e q u e n tu s e ra c c e s sp a t t e r n s a n o t h e ra l g o r i t h mi sp r o p o s e dt on f i n ef u z z yp r e f e r r e da c c e s sp a t t e r n sw i t h m i n i m u ms u p p o r ta n dp r e f e r e n c ei nf u z z ye n v i r o n m e n t ，i nw h i c ht i m ed u r a t i o n s o naw e bp a g ea r ec h a r a c t e r i z e da saf u z z yl i n g u i s t i cv a r i a b l e f u z z yp r e f e r e n c e p a t t e r n sw i t hf u z z yt i m ed u r a t i o n sm o r ed e e p l yr e v e a lu s e ri n t e r e s ta n dp r e f - e r e n c e i na d d i t i o n ，l i n g u i s t i ci n p u t sa n do u t p u t sb x em o r en a t u r a la n dm o r e s i m i l a rt op e o p l er e a s o n i n g a ne f f i c i e n ta l g o r i t h mi sp r o v i d e dt om i n eu s e rp r e f e r r e da c c e s sp a t t e r n s b a s e do nt h ec o n c e p t ，( f u z z yw e b p a g ep r e f e r e n c ef u n c t i o n ) ，w h i c hi sa l o n gw i t h s u p p o r tt od i s c l o s eu s e ri n t e r e s ta n dp r e f e r e n c e i tc o n s i d e r sa l lp o s s i b l ef a c t o r s ， w e i g h to fw e bp a g e ，r e l a t i v ea c c e s sf r e q u e n c yo fw e bp a g e ，a n dt i m ed u r a t i o n so n w e bp a g e t h u si tm o r ed e e p l yr e v e a l su s e ri n t e r e s ta n dp r e f e r e n c e af u z z yr o u g ha p p r o x i m a t i o n b a s e da p p r o a c hi sp r o p o s e dt oc l u s t e ru s e r a c c e s sp a t t e r n sf r o mw e bl o g s i nt h ep r o c e s so fc l u s t e r i n gu s e ra c c e s sp a t t e r n s ， e a c hu s e ra c c e s sp a t t e r ni sd e n o t e db yaf u z z yv e c t o rr e p r e s e n t i n gv i s i t e dw e b p a g e sa n dt i m ed u r a t i o n sd u r i n gas u r f i n g f i n a l l yr o u g ha p p r o x i m a t i o na p p r o a c h i sa d o p t e dt oc l u s t e ru s e ra c c e s sp a t t e r n sd e n o t e db yf u z z yv e c t o r s ar o u g hk - m e a n sc l u s t e r i n ga l g o r i t h mb a s e do np r o p e r t i e so fr o u g hv a r i a b l e i sd e v e l o p e dt og r o u pw e ba c c e s sp a t t e r n s e a c hw e ba c c e s sp a t t e r nf r o mw e b l o g si st r a n s f o r m e da sc o r r e s p o n d i n gf u z z yw e ba c c e s sp a t t e r n f i n a l l yr o u g h k - m e a n sc l u s t e r i n ga l g o r i t h mi sa d o p t e dt oc l u s t e ru s e ra c c e s sp a t t e r n sd e n o t e d 1 l b yf u z z yv e c t o r s t h ea l g o r i t h m sp r o p o s e di nt h i sd i s s e r t a t i o na x et e s t e dt h e i re f f e c t i v e n e s s a n dr e a s o n a b i l i t yb ye x a m p l e sa n de x p e r i m e n t s k e y w o r d s ：d a t am i n i n g ，w e bm i n i n g ，s o f tw e bm i n i n g ，u s e ra c c e s sp a t t e r n s ， f u z z yv a r i a b l e ，f u z z ys i m u l a t i o n ，c l u s t e r i n g 1 1 1 独创性声明 本人声嘲所呈交的学位论文是本人猩导师指导f 进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 绞撰写遘的璐宠残皋，也不镪含为获 莓天津大学或赣德教毒撬控麴学霞或涯 啪而使爵过的材料。与我一黼工作的同志对本研究所擞的任何贡献均氐在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：宴崭签字日期：品m 辞7 月鲴 学位论文版权使用授权书 本学位论文作者完全了躲天津大学有关保留、使用学位论文的规定。 簿授投天津大学霹戮将学疰论文懿全秘或部分癌糍编入育美鼗器摩进好检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阕同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密懿攀位论文在鬃寮蠢适用本技投说嚷) 学霞论文终尝签名：关螂 一剃 签字日期：训6 年7 月孕珏签字日期：川年7 胄孕鞋 1 1 研究背景及意义 第一章绪论 w w w ( w o r l dw i d ew e b ) 自从1 9 9 1 年诞生以来，已经发展成为拥有亿万 用户和上万站点的巨大分布式信息空间w w w 上信息的爆炸性增长，使得 人们迫切需要开发自动挖掘技术从大量的w w w 数据中发现人们感兴趣的模式 ( 知识) ，因此w 曲挖掘越来越成为个热门的研究领域但是如何在如此复杂 数据类型的数据中找到需要的知识，就提出了一个新的挑战 w 曲挖掘技术，主要包含了w 曲的内容挖掘、结构挖掘和使用挖掘他们 分别挖掘w e b 站点文件内容结构以及站点使用信息目前国际上对w 如使用 挖掘的研究比较多，w 曲挖掘的国际权威会议w 曲k d d 也把使用挖掘作为重 点 美国明尼苏达大学的b a m s h a dm o b a s h e x 和r o b e r tc o o l y 将w e b 使用挖 掘定义为数据挖掘技术应用在大型w 曲资源中以分析w 曲站点的使用f 1 8 ，7 9 】 w e b 使用挖掘通过挖掘w e b 浏览记录来发现有意义的信息例如有多少人访问 了该页而，他们从哪里来，那些页面最受欢迎等它可广泛地应用w e b 个性化 服务，系统改进，站点修改、商业智能和浏览推荐等方面当前经济模式变化， 己从传统实体的商店转移到i n t e m e t 上的电子交易，同时也改变了销售商和顾 客的关系通过w 曲使用挖掘可以了解到顾客尽可能多的爱好和价值取向，以 保证在电子商务时代的竞争力综合而言，w e b 使用挖掘具有以下几个方面的 益处【8 9 】： ( 1 ) 为用户提供个性化的服务 根据用户的访问历史，动态地向用户推荐商品正如a m a z o n e o m 所做的， 在电子商务网站上进行个性化营销，具有很大的商业价值 ( 2 ) 提高系统效率 随着w w w 的通信量的增加，影响网站用户满意度的主要原因除了w e b 站 点的内容外，其服务效率也很重要通过w e b 使用挖掘，可以提供网站服务效率 全方位的信息从而有助于找到平衡服务器负荷，优化传输，减少拥塞的方法， 缩短用户等待时间，提高系统效率和服务质量 ( 3 ) 改善网站结构设计 w e b 结构的复杂度在飞速的发展着因此，w e b 站点和w 曲服务器的设 计和维护难度也在增加着，通过w e b 使用挖掘提供的用户使用信息，可以帮助 网站设计者确定如何修改网站结构 1 第一章绪论 ( 4 ) 商务网站的顾客群类确定 分粝枣壤镑售数撵以识剐鬏客戆饕类，饕韵凌定毫子嘉务岁燕在w 如燹覆 上的带飚摆放，向用声有效的推荐产品，以达劐扩大产品销售激的目的同时， 有助予找到顾客访问网站的生命周期，制定相应的营销策略 ( 5 ) 网络安全 分辑弼上镊符，阚上齑鑫交苈糟声嚣恚，霹黻爨范黑客竣鸯，悉意谗骗。 ( 6 ) 网站评估 w 枷使用挖掘可以获取用户对网站使用情况的第一手资料，为网站评估提 供 荧据 瓤以上可以看磁，w e b 使掰撼掘具有径大的现实意义 此外，为了能使w 曲具有智能化，减少人为干预的影响，人们需要的w 曲 工具中榱入或嵌入人工智能技术人们迫切需要农服务器端和释卢端建立智熊系 统，跃褥毙骞效戆发瑗对久察鸯鬻懿知识。然薅，获无蠡谖懿、分豢秘，舅鞠s j w e b 数据中发现、提取、过滤和评估用户所需要的信息是一个福对复杂，庞大的 问题为了能够适应w e b 数据的特点。克服现有方法的缺陷。软计算技术逐渐 被人们斑露蘩w e b 挖握中，这秀秘技术鲍融合髂之为“软w e b 挖握s o f tw e b m i n i n g ) ” 目前，主要的软计算工具包括横糊理论、人工神经网络、激传算法和粗糙理 论模糊理论提供了一种甩于处理不确定信息的自然的常用方法神经网络被广 泛应爱警复杂函数懿建模，势显能够提供学习嚣凝蕹爨鳃髭力遗传募法楚一耱 有效的搜索和优化工舆粗糙理论农粒度计算和知识发现中发撵了重要的作掰 它们的目的是开发出一种有效的方法来处理不准确、不确定，避似推理，以及部 分真实的信意，露这秘方法是易处理酶，筵壮懿，低成本缒曼接近予人靛鲍淡策 铡定 本文系统地研究了w e b 数据挖掘中的w e b 使用挖掘技术，同时在模糊粗糙 环境t 绘出了新概念、新算法，并对其具体的皮用给出了相应的研究 1 2 w e b 用户浏览模式分析研究现状 1 2 1 数据挖掘技术及w e b 挖撼技术 数据挖掘( d a t am i n i n g ) ，簿攀说来，藏蔻祆大量数据串臻掘或发理隐藏在 其中的知识它是猩海基数据中撵索，并从中发现并提取隐藏在其中的有用信 息的种处理分析过穰，是个综食了数据库技术，人工智能、神经网络，模式 识别、统诗学决繁橼、燹睁额分糖、遗传算法、摸凝集，粮糙祭等矮壤蒸旗劳 2 第一章绪论 吸收了大量新颖思想的非常活跃的交叉学科，是k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) 过程中的个关键环节 下面将对知识发现过程和主要的数据挖掘技术进行简单介绍 数据挖掘是知识发现过程中的一个关键环节完整的知识发现过程由以下步 骤组成： ( 1 ) 数据清洗，即去除噪声和不一致的数据； ( 2 ) 数据集成，把多个数据源中的数据集成到一起； ( 3 ) 数据选择，即从数据库中选择与分析任务相关的数据； ( 4 ) 数据变换，通过汇总，聚集等方法，把数据转换为适于进行挖掘的形式； ( 5 ) 数据挖掘，采用智能的方法来提取数据中的模式； ( 6 ) 模式评价，选取正确的有用的模式； ( 7 ) 知识展现，采用可视化的展现技术把知识展示给用户 在过去的十年间，w w w 上的信息量呈爆炸式增长今天，我们可以通过 w e b 浏览器方便地存取w w w 上的信息超过1 ，0 0 0 ，0 0 0 ，0 0 0 的网页被搜索引 擎进行索引，然而，发现我们真正所需的信息却不是一个简单的任务人们迫切 的需要开发一种自动从w w w 挖掘的技术，因此人们提出了w e b 挖掘这个术 语w e b 是一个庞大的不受控制的异构的文档集合，它具有庞大性、多样性以 及动态性。由此带来了相关的度量性、异构性和动态性问题 b 4 】由于这些特点， 我们虽然沉浸在信息当中，却渴求知识 数据挖掘就是从数据中识别合理的、新颖的，潜在有用的，而且最终能被理解 的模式的一个复杂过程，因此人们认为w e b 挖掘是数据挖掘的一个研究领域 w 曲挖掘通常被定义为从w w w 上发现和分析有用信息1 0 4 在w e b 挖掘中， 数据可来自于服务器端、客户端，代理服务器端，或者来自一个机构数据库数 据源不同，所收集的数据类型也不同，这也就使得对一个特定任务所使用的挖掘 技术不同 w 曲数据具有如下特点巾4 】t1 ) 未标示；2 ) 分布性；3 ) 异构性；4 ) 半 结构化；5 ) 随时间变化；6 ) 高维 因此w e b 挖掘主要是挖掘具有上述特点的大量的且带有超级链接的信息 此外，作为一种交互式介质，人的干预也是大部分w e b 应用的个重要的组成 部分，因此也就带来了如下的问题t 0 4 ( 1 ) 需要处理上下文相关的不准确的请求； ( 2 ) 需要概括归纳和演绎推理； ( 3 ) 需要个性化及学习的能力 因此w e b 挖掘尽管被认为是数据挖掘的一个特殊应用，由于它特定的数据 3 第一章绪论 特点以及涉及到人的平预决定了它又是一个不同的研究领域 w 酶挖攮主要谈努藏三令类蘩；w e b 内容羧攘，w e b 缝耩i 窿握褒w 酶使 甩挖掘w e b 内容挖搦是指从w e b 内容( 数据、义档，服务等) 发现有用信息，许 多研究糟们从不同的角度研究了w e b 数据的知识的提取【1 0 ，1 1 2 7 t5 4 】w 曲结 构挖掘怒指挖掘w e b 蜜身的超链按结梅，也就燕一个网站内盼鲢接图或网娥之 阗懿镳按疆，英壅约赣究有k n o n o p n i c k i 释s h m u l e i l 4 1 爱c h a k r a b o r t y ，d o m 和g i b s o n 1 胡w e b 使用挖掘就是发现了解用户的浏览行为，它包括w 如趋势 分析和用户浏览路径分析，典型的研究有c h e n 、p a r k 和y u 训、c o o l e y 、 m o b a a h e r 纛s r i v a s t a v a l l 7 ，1 8 l 等。 w e b 挖掘酶每个蹙塑都包括篓种操作：_ 亭捌分析、聚类分析释关联分析 w e b 日农用于w 如使用挖掘常用的数据集合，我们将从w 幽使用挖掘的序列 分析和聚类分析中对w e b 日志进行分析研究，发现人们感兴趣的浏览模式+ 从 w e b 嚣拳串撬取窭豹蠢秀翔谖霹禳疆予弱菇莰诗、努辑系统嫠锈l ：盂及嚣络逶_ i 嚣， 理解用声的行为和动机，以及建立个性化的网站等 1 2 2 w e b 用户浏鼹模式挖掘研究现状 邃蕊w 粥v 爱声静快速增长，入镌淹没在w 曲售意孛游求着有瑶静麓识， 在线分析用户的浏览行为以及浏览模式已成为越来越重要的研究领域t s e n g ， p e t r o u n i a s 和c h o u n t a s 5 ；s l 给出了一种w e b 挖獭的方法介绍，讨论了在各种限 定条箨，絮溅莲隈定，嚣孛藏豹聚宠( 包摆浚整嚣雩藤、会话羯、辩阕医舞等) 、令 性限定等，如何发现凝繁的甩户浏溉模式及行为s r i v a s t a v a 簿人i l 奶详缎满 述了w b b 使用挖掘的每个阶段，即预处理、模式发现和模式分析 一燧研究者 门使用基于关联栽则挖掘的方法挖掘w e b 用户浏览模式挖掇。 在w e b 籍恚挖箍孛测嚣关联囊戴霄戳发瑷尾声掰访阍茭嚣弱的荧联。关联瓣露 挖掘首先由a g r a w a l 和i m i e l i n k s i 1 1 提出a p n o 茧i 算法a p f i o f i 可以说是数据 挖掘领域的经典算法。目前已经作为研究人员衡爨其新算法性能的基准，同时， 谗多软镣都采曩了它翡器慈。疆嚣，谗多骚究蓍黧予鲤舞提离a p f i o n 箕法懿羧 率，所以i i j j 既了一些辩a p f i o n 变形盼算法p a r k 簿人辫，嘲攥如使用h a s h 寝 提高挖掘关联规则的效率，a g r a w a l 和s r i k a n t i z 、h a n 和f l u 【弱】以及p a r k 、 c h e n 秘y u t i y 】利用攀务压缩技术，s a v a s e r e ，o r n i e c i n s k i 和n a v a t h e 内】袋鼹 赵分羧零将数据痒舞攒次数藏步裂两次或一次聿筝多醑究者稳i f , 9 ，1 0 ，1 3 ，l 鸯摆 数据挖掘中的关联规则挖掘的思想应用到w e b 频挖掘中，用予发现频繁的用户 浏览模式 男多 一些礤究者稚恕露声淄览访l 霹) 模式懿发瑷舞属予廖列模式挖撼鳃楚 4 第一章绪论 畴w 、 n v 用户在访问感兴趣的信息时，倾向于通过连接( 或图标) 来漫游网页 ( 站) 例如，用户为了到达当前主题的一个兄弟主题，总是利用。b a c k w a r d 。图 标后退至父主题( 起源主题) ，再向前作出选择，而不是打开一个新的u r l 从头 开始因此在用户日志中的某些结点，被重复访问并非因其内容相关，而是因其 结构特殊为了从原始日志库中抽取有意义的用户访问模式，我们要消除反向关 联的影响，因为反向关联旨在方便用户访问，而非满足用户的检索需求 c h e n 等人【埘，1 4 】中采用的寻找最大向前关联路径的思想与w w w 的超链结构特点 相结合，用以挖掘用户访问模式 挖掘用户浏览模式的全过程如下； ( 1 ) 从原始日志库中寻找所有最大向前关联路径； ( 2 ) 由找到的最大向前关联路径求出频繁关联路径浏览； ( 3 ) 由频繁关联路径浏览求出最大频繁关联路径浏览 各步骤思想如下； 步骤1 当用户访问一个曾经访问过的u r l 时，称出现了反向关联反向关联 的发生意味着一个正向关联路径的结束，并产生最大向前关联路径然后回 溯到该前向关联路径的起点，再继续寻找其他的前向关联路径另外，源结 点( 即无父结点的结点) 的出现也意味着前向关联路径的结束及新路径的开 始 步骤2 找到所有用户的最大前向关联路径后，我们将发现用户访问模式的问 题映射为从所有最大向前关联路径中找最常出现的连续子浏览问题频繁关 联路径浏览定义为出现次数达到某一阈值的序列这里我们提出了增量式有 序概念格算法 步骤3 称一个频繁关联路径浏览为最大的，如果它不包含于任何一个其他的 最大频繁关联路径中 h a n 和h 【z 现提出一种无须产生候选集挖掘频繁模式的方法一频繁模式增 长( f p g r o w t h ) ，他们提出了一种新的数据结构f p 一树( f r e q u e n tp a t t e r nt r e e ) ， 压缩原来的事务数据库不使用类a p r i o r i 方法的产生一测试策略，它侧重频繁模 式的增长，避免了产生候选集所需的高代价，从而获得了更好的效率而且这种 结构加以变化就可以快速更新频繁项集而不需要扫描原始数据集 9 4 ，1 0 4 ，1 0 5 1 p e i 和h a n 将这种方法应用到w e b 日志挖掘中【舢，将f p - 树修改为适合保存 日志数据的w a p 一树( w e ba c c e s sp a t t e r nt r e e ) 他们首先对日志数据进行预处 理，然后把预处理后的用户浏览模式存储在w a p - 树中，最后对w a p - 树反复 扫描以发现频繁的用户浏览模式s p i l i o u l o u 7b 提出从w e b 日志中建立一棵逼 近树的算法，然后使用m i n t 挖掘语言进行w e b 存取路径的挖掘 5 第一鬻绪论 w o o n 、n g 和l i r a 8 0 提出创臻个新颖的结构w e b t r i e ，用于存储w e b 囊恚中骥鲣理居醒售感，然后袋魍客断骞暴声铸爨戆w e b t r i e 挖攘频繁褥爨声 铡菟模跋，使蓐滚绪祷迸可以进行程线和增量式撼黼 b o r g e s 和l e v e n e 8 ，硼把预处燃濑的w e b 日漱中的用户浏徽模式存储椒 个带投的露匈匿中，然麟剩恩深度优抛躲方法搜索谈蠢恕匿，扶越发褒频繁既粥 产溆蘩攥式。 其他从不同角度探讨频繁用户浏腻模式的挖描的还有【1 7 ，1 8 3 6 ，6 1 ，6 3 ，9 l 】 c o o l e y 、m o b a s h e r 和s r i v a s t a v a “，l 明在挖黼荧联规则和序列模式的软件 平台上撬缨了一秘蠢诲谗害，人稳霹域鑫己为挖掇绻聚设定条律 n i u ，c h e n 帮g o e b e l f 醋 努了w e b 挖掘懿绪浆更荔理解，撩寤了w e b k i v 工具，墩和其他的w e b 可视化工舆一起使得w 龇拣掘的结果可视化 金嘲等人m ，6 1 】撼如了基于农謦概念格的挖搬用户访问模式斡高教增爨域 算法，镳懿恕罴产溺览攘式集存赣擎今骞旁骜念糍母，爨鑫扶鸯謦羲念撂审控 掘频繁的用户浏览模浅。这种方法带虑到了访问贸黼之问的次膨，不再仅仪藏两 面之间的燕联关系，黼恩可以处理劫淼的信息 璎永壤秘骂步擎p l l 疆遗筹建娆彳释基予攥声努类鳃摸溅一多m a r k o v 镳 蔟鹫攒述麓声嚣粥努褥髹，获面熬辩鼷户盼游览徽臻_ 更灌确鹣溪溺+ 然黼，以上的算法火都只考虑网鞭的浏览频皮，简单的认为用户的浏览麟成 就反映了耀户的访问淡艨，这很不横确孵页浏燕额度的影响蹦紫 基多，其申触 茭垂藏鬣燕鬟褒其窀荑囊霹该要蠢懿链接豢趁蓉非常重要懿佟穗。莲踅鄢寒瞧 等人 涮，# 鞠提出了炎撩度一偏爱旋概念，将两崭缔合起来葳鞔厢芦l 的兴趣，如 果一个戴谢的支持度年盯偏爱度都大带指定的阈值，贝! j 该页面才魁用户感兴趣的激 嚣，鸯爨声感兴趣豹笈搿组成鳃蘑声测鼙襄式是惩声豫爱熬攒茂+ 窀与壤繁访瓣 籍径穰溅，更麓爱浚磁建产爨琵翡强熊纛耄登，纛浚步熬群巍巾，毪稚爱褒穗 户对网麟的浏览时间也魁反映用户必趣的一个黧嬲因素，因此文献【9 0 】考虑了 网页的籀融访问颇度朔蹲页上的浏览时间，基于逡豫个要素，黧勰修改了偏爱魔 熬橇念，绱爱麦越嵩，太辍对该溺蒙酶兴莲就越犬。鲑既考惑了众多要素懿谂爨 度更髓葳映用户酌兴燧芹辩偏爱鲍外，为了提裔挽撷豹效率，激熊熏复扫攒甜瓣 文件。x i n g 和s h e n 拯出了种新糨的结构一p n t ， ( 它是一种类似于w a p 撵翦树镶褥，每令节点豁镰了该繁煮靛支持度耪镶爱度x 嗣警撑德最产熬测懿 整慧，瀵炱了产生竣滚寨掰番瓣鬻俄徐，获秀获褥了夏鳋懿效攀。 模糊弱b 论为处理芥确定信息撼供丁一种自然的方法自从z a d e h y ，】年撼出 模糊集概念以来，模糊瑗论得到了张熙的发展n a h m i a s 6 u l 搬1 9 7 8 年提出糗 糖变惫秘摄念，i a u 秘l i u t 发菔了套完馨黥獒叛予攘率论鲢、骚究摸皴健 6 第一章绪论 的公理体系，称之为可信性理论越来越多的研究者逐渐把模糊的方法应用到 w w w 知识发现和分析中，如a r o t a x i t e i 和m i t r a b ，他们列举了在模糊w e b 挖掘中的现有方法，其中强调了模糊理论在处理不确定信息时的重要作用 h o n g ，c h i a n g 和w a n g ：3 b 认为在实际应用中，每个网页的作用对不同的 用户来说是不同的，因而，他们把专家给定的网页的语言评估表示成相应的模糊 集，通过模糊集的相应运算，把这些表示网页重要性的语言评估转换成表示网页 权重的模糊集然后提出了一种基于语言输入和输出的加权w e b 挖掘的方法，其 中最小语言支持度也表示成相应的模糊集最后根据网页的加权支持度( 模糊集 ) 和最小语言支持度( 模糊集) 相比较，判定该网页是否是频繁的加权网页，从而 得到加权的频繁的用户浏览模式该方法是基于关联规则挖掘的算法提出的，缺 点是需要重复扫描预处理后的日志文件产生频繁项集 l o ，h o n g 和w a n g b 瑚认为网页的访问频度是反映用户兴趣的一个重要因 素，然而，网页上的浏览时间也是反映用户浏览兴趣的另个重要因素然而一 个网页上的浏览次数是不确定的，而且被不同的用户以不同的浏览时间进行访 问他们把网页上的浏览时间刻画成若干个模糊区间，然后求每个模糊区间上的 标量势，以最大的标量势的那个模糊区间( 用模糊集表示) 作为该网页浏览时间 的刻画从而提出了交叉的带模糊浏览时间的用户浏览模式的挖掘所获得的带 模糊浏览时间的频繁用户浏览模式不仅体现了用户的访问频繁，而且清晰的表明 频繁访问的网页上的浏览时间是不同的，表明了用户的不同兴趣程度，因而它们 更能体现用户的访问兴趣 p a l 和t a l w a r 0 4 】提出了软w e b 挖掘( s o f tw 曲m i n n g ) 的概念，列举了现 有的w e b 挖掘的方法和工具，其中突出强调了软计算的作用软计算是各种方法 的融合，它们协同工作，给现实生活中存在的模棱两可的信息提供一种灵活的处 理方法它的目的是处理那些不精确的不确定的，近似推理的或部分真实的数 据以获得易处理的，健壮的、低成本的解，而且使得处理过程类似于人们决策的 制定它的指导原则是以低成本近似的获取不精确或不准确的问题的满意解目 前主要的软计算工具包括模糊理论，神经网络、遗传算法和粗糙理论模糊理论 是处理不确定信息的一种最常用、最有效的方法神经网络被广泛应用于复杂问 题的建模，并且提供学习和概括归纳能力遗传算法是一种有效的搜索和优化工 具粗糙理论在粒度计算和知识发现方面的作用非常大，尤其在信息约减和聚类 或分类问题上，它是一种非常有效的数学工具许多研究者们【2 0 ，2 1 4 3 4 4 ，4 5 】 在w e b 挖掘的应用中使用这些软计算工具以获取更加满意的解方案 7 第一章绪论 1 2 3 w b b 用户浏览模式聚类分析 终疆滋：8 餐浚类聚，久瑷群分”。聚类藏莛弱籍骨箕掇羧零寒实瑗这一嚣 的的一种按术其输入怒一组未分类的记录，且事先不知道如何分类，也可能不 知道要分成几类把相似性大的对象聚集为一个类通过分析数据，合理划分记 录集会，确定每个记录黪属的类爱聚类缒标准是使类态辍议藏器霹铯大，类阕 穗叛度尽可镌奎聚类麓把一些数据搬据其裰互阕蠢在鲍耨儆毪箍分成善于个凝 类与分炎有一个明显的不同：分类中，数据的类别是己知的，用这些数据来构 建模型，并用该模型来预测未知数据的类别 而在聚类中，所有数据的类别都燎 寒絮懿，壤捺黪象阗戆鞣锾鍪 或摇雾羧来对数据邃蟹分缝，据穗浚瓣对象竭入瓣 个组，黼差异较大的x 寸象归入不同的组 聚类技术可泛泛地分为两大类，一是分区聚类如【配，瑚，另一种是层次聚 类如l z 铆，它舡的区男4 农于是否产生肇调努区或类的屡次，翅分聚类算法把数 器熹集分为蠢个翔分，每个麓分作为个聚类它般获一个秘始翅努拜始， 然后通过黧复的控制策略，使某个准则函数最优化，而每个聚类幽熊质心来代袭 ( k 一均值算法) ，或者由谈聚类中最靠近中心的一个对象来代表( k - 中心点算法) 楚分聚类葵法l l 雯敛速褒快，嫒点在予宅蔟疯子识羽螽彩分毒大小攘送密度程潦 的聚类，不能发现分布形状比较复杂的聚类，它簧求类别数日k 可以合理地估 计，并且初始中心的选择和噪声对会对聚类结果产缴很大影响分屡聚类算法乎巴 数据对象分组两形成一个聚类树分艨聚类算法有鼹秘途径l 自底向上的聚结滋 a g g l o m e r a t i v e ) 纛塞凌翘下约分裂浚( d i v i s i v e ) 缝粹鳆努篡聚类箨法豹缺赢缀 于一旦进行合并或分裂之后，就无法稃进行调整现在的一些研究侧重于分层聚 类算法与循环的重新分穰己方法的结合 传统豹聚类算法考鹭篷聚类浚l 购，争孛心窳聚类法【3 8 l ，嚣绕孛心熹努 区法( p a m ) 描翻以及n g 等人提出静c l a r a n s 鳓其它的聚类方法可参觅义 献 2 2 ，2 3 ，3 2 ，3 9 ，4 8 ，7 4 ，i 0 1 d o u g h e r t y 和b r u n l 2 2 1 使用概率方法讨论聚擞 问题h i n n e b u r g 和k e i m a 硼提出了一秘基于格的聚类算法甩警寓维空闻的聚 类阕疆，义敲l 碉讨论了莲子密度鳇察簿数据懿蘩类方法。文献【2 3 ，3 9 ，i 8 霹审 给出了各种各样的层次聚类方法，它们可用于大型数据库中的模式聚类问题 w i r l dw i d ew e b 由于其爆炸性的增长以及越来越拓宽的领域已经成为许多 领壤的默认知识源，嚣怒竣诗成熬熬攘梁扶w w w 发褒一些套趱躯壤念以及迭 些概念1 乏勰的关系已越来越重要聚类就是餐决这个 霹题的技术之一聚类是一 种无监督的发现过程，用于对一个数摄集进行分区，使得类内相似性最大化，类 间相似性娥小化应用予w e b 挖掘的聚类技术面临大量的挑战，如信息量庞大， 8 第一章绪论 存取时间，高维数，质量以及有意义的解释 在w e b 挖掘中。与传统聚类分析相比，w 曲聚类面临几个额外的挑战瞄“， 类与类之间可能存在模糊的或不准确的边界，模式集中个模式的隶属不能准确 定义，有可能隶属于多个类此外，数据的记录过程以及不完全的日志使得噪音 数据( n o i s e ) 存在的可能性非常大，因此例外数据( o u t l i e r s ) 出现的可能性很 大，j o s h i 和k r i s h n a p r u a m 3 7 认为w 曲挖掘中的聚类操作需要建立若干个有 重叠的集合；h a t h a w a y 和b e z e k 3 0 ，k r i s h n a p r u a m 等人t 4 2 4 3 ，4 4 j ，提出 使用模糊聚类法来分组w e b 用户 y a o 和c h o i 9 5 提出了w e b 挖掘的个新的在高维空间上的双向分层聚类 系统，该系统部分基于图分区模型，包括的主要步骤是：产生“近邻矩阵；从 下到上类合并阶段；从上到下提炼阶段首先使用所有如最近邻法减少( 稀少) 图以及去除噪音数据，在从下向上的类合并阶段定义了一个新的边匹配法，它不 仅考虑了任两结点之间的内相通性，而且也考虑了结点集内的内在的相通性这 种边匹配方法发现类的层次结构比通常的层次聚类法更快然后从上而下进行精 制处理去除掉在贪婪聚类合并阶段的错误最后一步是从层次结构的类中提取概 念 王太雷岿跏分析了目前在推荐系统中常用的用以计算访问行为相似程度的 距离函数，发现它们仅是测定访问者对象在所有测试属性空间上平均测定、而在 属性集的子维空间上的相似模式并没有有效地挖掘出来，因而给出了一种新的相 似模式聚类算法，它能有效地得到访问者对象在整个或者部分属性空间的相似访 问行为模式 许多算法都认为模式是实值型向量，但在分析w o r l dw i d ew e b 数据时， r u n k l e r 和b e a d e k 坩】考虑如下两种不同的非数值型模式的类型 ( i ) w e b 文档本身以特殊文档格式象包含控制流和文本的h t m l 存储的 ( 2 ) w e b 服务器上的日志文件中包含被特定用户访问的网页的存取序列 文本( 字符序列) 和网页序列都是非数值型的模式序列，它们可通过关系矩 阵表示成数值型，这些模式序列之间的关系可通过序列间的比较计算得出，如使 用l e v e n s h t e i n 距离，这种关系数据集的聚类可通过关系的不断类估计来实现 由于一个模式可能同时以不同的程度属于多个模式集，而且w e b 数据集中 出现错误数据的可能性非常高，因此l i n g r a s 4 j 提出了基于粗糙集理论加遗传算 法的无监督的w e b 用户聚类的方法，使得具有相似浏览行为的用户聚成一类， 而不同类之间的用户的浏览行为尽可能的不相似每个类由一个粗糙集染色体 表示，因为粗糙集的边界是模糊的，因而每个粗糙集由它的上近似和下近似来表 示处于每个粗糙集上近似中的模式可能属于也可能不属于表示该类的粗糙集， 9 第一章绪论 但是如果谈模式处于谈粗糙集的下近似，则它一定属于表示该类的粗糙集 l i n g r a s _ 饔w e s t 4 7 l 捷碴了题犍鼢垮壅懿聚类方法，每今类瞧是壶一令糠 糙集表示，但是由于粗髓集静不确定酌边界，它同榉海该粗糙集的上近似稻下近 似来描述该算法首先选取若干个模式作为k 个类的中心，然后根据每个模式到 这k 个中心的距离把它妇分配到这k 个类的上近似穰下近似当中接着对重新 分配裂每个类静模式诗冀宅懿戆孛心基位置。重复幸 簿每令袭式裁耨鳕类翡中，豁 点的距离，再进行分配，赢到算法收敛为止该算法继承了传统缸均值的聚类 思想，能较好的达到聚炎的效果 m i t r a b t i l 撬出了一耱遴怨夔题犍努区聚类方法，该方法爨然楚曩攫糙如鹭 值豹聚类繇想，把n 个模式聚类到k 个不同酶类申与传统恿想不同的是类与类 之间是有熬叠的，每个擞的边界是模糊的，这样每个类用清晰的粗糙集的上近似 和下近似米表示然而，由于在计算表示类的粗糙集的中心点位黢时，需要设定 艺近囊l 霸近 菝豹程纛较霪，瑟它爨豹投重往茬蔻搬据经验事先滚定妊魏。嚣褥 m i t r a 提出了使用遗传算法来调整这两个权重，使得聚类的结栗爨加令人满意 d e 和k r i s h n a f z l 】使用粗糙近似方法对用户的浏览模式进行聚类由于每个 用户的测燕模式的长炭裙爨不同鹣，饿靛首先把每令露声豹浏览模式转换成等妖 的二进裁囱藿形式，向黛豹长度等于掰肖尾声访麓避的页蓄酶慧个数，这榉藏激 中的每个瓮察是二进制的0 或1 ，表示该网页是否被访问然盾给出了任意两 个用户浏j 5 葭模式之间的糊似性度量，根据相似性度擞可以把每个模式的近似上避 钕求赉，然嚣把程司透纭上近经懿攥武聚为一类该算法甍萃寿效，嚣显彀载糍 度很快 a s h a r a f 和m u r t y 6 】提出了一种模糊粗糙的方法用于w e b 日卷中数据的聚 类，该方浚是传统的l e a d e r 算法在攥凝粗糙环境下瓣改进每个爽是盎一令翌 元组表示，群l e a d e r ，糖糙集静下邋似和上近戗聚缀成葡榉盼租糙集静下邋 似中的模式一定属于该擞，它的上近似中的模式可能属于也可能举属于该类，两 个类之闯的上近似之间魁有重叠的该算法只需要掴描遍数据黎，可分成两个 蒙爱，第羚段蓄先经慧选定若予伞l e a d e r 敷入i 砖a d e r 集孛，影藏个褪始戆 l e a d e r 集，然后对所有的模式进行封怒归类到l e a d e r 集中或s u p p o r t i n gl e a d e r 集中第二阶段，当新的l e a d e r 集形成后，对l e a d e r 集中的每个元素按照一定 的原则，瓣l e a d e r 集酶元素进行归类。该算法由乎织接数强集的次数步，在时 阕效率上翳好于其它聚炎算法。 1 0 第一章绪论 1 3 本文主要研究内容 i 夔饕w e b 数据懿迅猛增长，驮w e b 数舞孛爱瑷稳分辑有趱镄惠已j 霞为越来 越重要的任务，它被分为三类；w e b 内容挖掘，