硕士论文-基于协作过滤的个性化服务技术研究.pdf

Y 1 2 1 9 5 6 8 分类号T P l 8密级 垒珏 重庆邮电大学硕士学位论文 沦文题目 塾士迹笠垫遇鲍仝 些垡丛釜垫盔盟窒 英文题目 h 曼 旦亟YQ f 卫曼 Q 旦垦 i 圣曼亟 旦 i 量b 垦 曼盟Q 坠 题名和副题名 硕士研究牛红盈洼 指导教师至国丛L 趱 论文提交日期垫 笙i 旦 旦论文答辩H 期2 Q Q Z 生 旦2 日 论文评阅人盈地盘丝丝叠垃 煎丛堡鍪丝叠丞垡噬 答辩委员会主席廛堕蝰塾援重压盔堂 2 0 0 7 年5 月2 9 同 重庆邮电大学硕士论文 摘要 当前 W e b 已成为人们获取知识和信息的一个不可或缺的重要途径 然而 随着W e b 信息的同益增加 人们不得不花费更多的时间来搜索 浏览自己所需的 信息 信息过量 和 信息饥饿 的矛盾同益凸现出来 由于目前的搜索引擎不 能满足不同背景 不同目的和不同时期人们的查询请求 个性化服务的需求越来 越多 个性化服务能通过收集和分析用户信息来学习用户的兴趣和行为 实现主 动推荐 从而满足不同用户的需求 论文围绕当前应用最为成功的个性化服务技术 协作过滤所面临的两个主 要问题 数据的高维稀疏 算法的可扩展性 而展开 提出了一种新的推荐算法 基于资源项目类别的协作过滤算法 I C C F 该算法在对资源项目进行分类的 基础上 将传统协作过滤算法中用户对资源项目的评分转换为用户对资源项目依 内容划分所属类别的平均评分 并对评分数据进行加权过滤预处理之后 运用K 一 平均聚类算法对用户聚类 然后在目标用户所在的簇中寻找其最近邻居 根据最 近邻居对资源项目的评分来产生目标用户的预测评分 从而产生推荐 运用协作过滤推荐算法常采用的标准测试数据集 M o v i e L c I l s 对本文提出 的I C C F 算法进行了仿真实验测试 数据稀疏度实验结果表明 I C C F 算法大大降 低了数据的稀疏程度 扩展性实验结果表明 由于各簇中用户数明显低于总用户 数 I C C F 算法在目标用户所在的簇中寻找其最近邻居 比传统的协作过滤算法大 大缩小了目标用户最近邻的查找范围 从而提高了算法的扩展性 而且聚类可以 离线进行 满足了推荐系统实时性的要求 在不同的测试数据集上做预测精度的 实验结果表明 I C C F 算法在推荐质量上也优于传统的协作过滤推荐算法 关键词 个性化服务 协作过滤 智能推荐 信息检索 W e b 搜索 重庆邮电大学硕士论文 A b s t r a c t C u r r e n t l y W e bh a sb e c o m ea l li n t e g r a la n di m p o r t a n tw a y st oa c c e s sk n o w l e d g e a n di n f o r m a t i o n H o w e v e r w i t ht h eW e b Si n c r e a s i n g p e o p l eh a v et os p e n dm o r et i m e t os e a r c ha n db r o w s et h ei n f o r m a t i o nt h e yn e e d I n f o r m a t i o no v e r l o a d a n d i n f o r m a t i o nl a c k h a sb e c o m eab i gp r o b l e mt ob es t u d i e d A ss e a r c he n g i n e sC a nn o t m e e tt h ed i f f e r e n tb a c k g r o u n d s d i f f e r e n tp u r p o s e sa n dd i f f e r e n tt i m e si n p e o p l e S i n q u i r yr e q u e s t T h e r ea r em o r ea n dm o r en e e d sf o rp e r s o n a l i z e ds e r v i c e P e r s o n a l i z e d s e r v i c eC a np r o v i d ea c t i v er e c o m m e n d a t i o na n dm e e tt h en e e d so fd i f f e r e n tu s e r s t h r o u g hc o l l e c t i o na n da n a l y s i st h e i ri n f o r m a t i o n T h et h e s i si sb e g a nw i t ht h et w om a j o rf a c i n gp r o b l e m so fc o l l a b o r a t i v ef i l t e r i n g w h i c hi st h em o s ts u c c e s s f u lp e r s o n a l i z e ds e r v i c et e c h n o l o g ya d o p t e dt od a t e t h a ti s s p a r s i t yo fd a t aa n ds e a l a b i l i t yo fa l g o r i t h m A n dt h e np r o p o s e san e wa l g o r i t h m 一 c o l l a b o r a t i v ef i l t e r i n gb a s e do ni t e mc a t e g o r y I C C F O nt h ef o u n d a t i o no fe l a s s i l y i n g i t e m s i tc o n v e y st h et r a d i t i o n a lu s e r Sr a t i n g si n t ot h ea v e r a g er a t i n g sf o rc a t e g o r i e so f i t e m s A f t e rw e i g h t e ds i f t i n g t h e nu s e sK m e a nc l u s t e r i n gt oc l u s t e ru s e r s a n df i n d st h e n e a r e s tn e i g h b o r so ft h ea c t i v eu s e r si nt h ec l u s t e r st h a tt h ea c t i v eu s e r sl o c a t e di n A c c o r d i n gt ot h en e a r e s tn e i g h b o r s r a t i n g st op r o d u c et h ep r e d i c t e dr m i n g s a n dt h e n g i v et h er e c o m m e n d a t i o n L a s t l y w eu s et h es t a n d a r dd a t as e t M o v i e L e n st ol e s tt h ep r o p o s e dI C C F a l g o r i t h m T h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h eI C C Fg r e a t l yr e d u c e st h ed a t as p a r s e a n ds i n c et h en u m b e ro fa s e P si ne a c hc l u s t e rs i g n i f i c a n t l yl o w e rt h a nt h et o t a ln u m b e r o fu s e r s t h eI C C Ff i n d st h en e a r e s tn e i g h b o r so fa c t i v eu s e r si nt l l ec l u s t e rt h e yl o c a t e d i n w h i c hC a ns m a l l e rt h ea r e ao ff i n d i n gt h en e a r e s tn e i i g h b o r s S Oi tC a ne n h a n c et h e s c a l a b i l i t yo f t h ea l g o r i t h m A n dc l u s t e r i n gc a r lb ec a r r i e do u to f f l i n e w h i c hC a nm e e t t h er e a l t i m e r e q u i r e m e n to ft h er e c o m m e n d a t i o ns y s t e m S i m u l t a n e i t y d o t h e p r e d i c t i o na c c u r a c ye x p e r i m e n t si nd i f f e r e n tt e s t i n gd a t a s e t t h er e s u l t ss h o wt h a tt h e r e c o m m e n dq u a l i t i e so f1 C C Fa r ca l S Os u p e r i o rt ot h et r a d i t i o n a lc o l l a b o r a t i v ei 1 1 r i n g a l g o r i t h m s K e yw o r d s P e r s o n a l i z e ds e r v i e e C o l l a b o r a t i v ef i l t e r i n g I n t e l l i g e n tr e c o m m e n d a t i o n I n f o r m a t i o nr e t r i e v a l W e bs e a r c h I I 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他 人已经发表或撰写过的研究成果 也不包含为获得重庆邮血叁堂或其他教育 机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意 学位论文作者魏知吾 专签字吼工叼年舌一日 学位论文版权使用授权书 本学位论文作者完全了解重庞邮血盍堂有关保留 使用学位论文的规 定 有权保留并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查 阅和借阅 本人授权 重庞邮电太堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论 文 保密的学位论文在解密后适用本授权书 学位论文作者签名 知切 导师签名 堋J 钞 签字日期 砷年6 月6 日签字同期 佃 7 年 月呷同 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 近年来 随着互联网的普及及其应用的不断深入 W e b 已成为人们获取信息 的一个重要途径 然而 随着w 曲信息的同益增长 人们却不得不花费大量的时 间去搜索 浏览自己需要的信息 这就导致了 信息过量 和 信息饥饿 矛盾 现象的出现 搜索引擎 s e a r c he n g i n e 是最普遍的辅助人们检索信息的工具 如传 统的搜索引擎A l t a V i s t a Y a h o o 和新一代的搜索引擎G o o g l e 等 虽然信息检索技 术满足了人们一定的需求 但由于其通用的性质 仍不能满足不同背景 不同目 的和不同时期人们的查询请求 针对这个问题 研究者们提出了个性化服务技术 个性化服务通过收集和分析用户信息来学习用户的兴趣和行为 其能够更好地理 解用户 发现用户隐藏的兴趣和群体用户的行为规律 从而制定相应的信息过滤 策略 按照用户的个性化信息进行主动的推荐服务 它能为不同用户提供不同的 服务 以满足各自不同的需求 运用个性化服务技术能充分提高站点的服务质量 和访问效率 从而吸引更多的访问者 个性化服务系统根据其所采用的推荐技术可以分为两种 1 基于规则的系统和 信息过滤系统 信息过滤系统又可分为基于内容过滤的系统和协作过滤系统 基于规则的系统如 I B M 的W e b S p h e r e B r o a d V i s i o n I L O G 等 它们允许系 统管理员根据用户的静态特征和动念属性来制定规则 规则决定了在不同的情况 下如何提供不同的服务 基于规则的系统简单 直接 缺点是规则质量很难保证 且不能动态更新 此外 随着规则数量的增多 系统将变得越来越难以管理 基于内容过滤的系统如 P e r s o n a lW e b W a t c h e r t 2 1 S y s k i l l W e b e r t t 3 1 L e t i z i a l 4 1 C i t e S e e r i 5 1 i f W e b l 6 1 S I F T E R 7 1 P V A l 引 W e b M a t e l 9 1 W e b A C E l l 0 E L F I 川和 W e b P e r s o n a l i z e r t 2 1 等 它们利用资源与用户兴趣的相似性来过滤信息 基于内容过 滤的系统其优点是简单 有效 缺点是难以区分资源内容的品质和风格 且只能 发现和用户已有兴趣相似的资源 不能为用户发现新的感兴趣资源 协作过滤系统如 W e b W a t e h e r t l 引 L e t SB r o w s e l l4 1 G r o u p L e n s 1 5 1 F i r e f l Y l l 6 1 S E L E C T m J L i k e M i n d s w w w m a c r o m e d i a c o m 和S i t e S e e r I 1 等 它们利用用户 之间的相似性来过滤信息 协作过滤系统的优点是能为用户发现新的感兴趣信息 缺点是主要存在两个难以解决的问题 一是数据高维稀疏性 即在系统使用初期 由于系统资源还未获得足够多的评价 系统很难利用这些评价来发现相似的用户 重庆邮电大学硕士论文第一章绪论 另一个是算法可扩展性 亦即随着系统用户和资源的不断增多 系统的性能会越 来越低 还有一些个性化服务系统如 W e b S I F T t l 9 1 F A B 2 0 A n a t a g o n o m y 2 1 l 弄1 D y n a m i c P r o f i l e r l 2 2 1 等 它们同时采用了基于内容过滤和协作过滤这两种技术 结合这两种 过滤技术可以克服各自的一些缺点 从而提高协作过滤的性能 由于基于内容过滤的信息推荐技术不能处理难以进行机器自动内容分析的信 息 比如艺术品 电影等 也不能基于一些复杂的 难以表达的概念比如质量 品位等进行过滤推荐 同时也不能为用户发现新的感兴趣资源 而协作过滤可以 弥补以上不足 导致其成为应用最为成功的信息推荐技术 然而 随着用户和资源数目的不断增加 协作过滤推荐技术所面临的一些问 题也越来越凸现出来 主要表现在以下三个方面 1 冷启动 问题 冷启动 问题即对于那些从未被任何用户评分过的项 目 无法得到其相似群 2 数据的高维稀疏性 在资源项目很多的情况下 用户的评分数据相对来说 是很少的 比如在大型的电子商务系统中 用户的评分项目一般不会超过项目总 数的1 田J 数据的高维稀疏性 一方面导致不同用户之间交叉评分的项目会很少 这样用传统的用户相似性度量方法计算出来的用户最近邻居集就不准确 从而导 致信息推荐质量的下降 另一方面导致进行用户相似性计算的耗费也会很大 3 算法的可扩展性 随着用户和资源项目数目的增加 系统的计算量会越来 越大 难以满足推荐系统实时性的要求 针对以上三个方面的问题 国内外研究者们给出了很多具体的解决办法 其 中对于数据的高维稀疏性问题 众多学者们给与了更多的研究和关注 对于 冷启动 问题 自从在文献 2 3 中提到后 便引起了研究者们的注意 文献 2 4 认为 冷启动问题 可依靠项目本身属性特征的相关性得以解决 这一问 题也得到了许多研究者们的关注 2 5 之刀 对于数据高维稀疏性问题 目前解决的方法主要有三种 1 设黄初始评分 所谓设置初始评分就是将空缺的项目评分设定为一个固定 的默认评分 2 8 J 或者基于项目的相似性预测用户对未评分项的评分 2 9 川 文献中实 验结果表明设置初始评分的方法可以增加评分数据的稠密性 提高最近邻生成的 效率 2 8 然而这种方法并不能从根本上解决数据稀疏性问题 2 基于人工智能的方法 通过采H o r t i n g 1 3 2 1 聚类1 3 3 卯 贝叶斯网络口6 1 软件代理 3 7 3 8 及粗糙集 3 9 等手段 增加用户在项目评分空间上重叠的数目 以降 低数据稀疏性 但此方法在解决数据稀疏性问题的同时往往牺牲了推荐的精度 并面临推荐计算的可扩展性问题 4 0 2 重庆邮电大学硕士论文第一章绪论 3 基于降维思想的方法 该方法主要采用奇异值分解 4 1 4 2 潜在语义索引 4 3 1 主成分分析 矩阵划分f 4 5 4 6 1 等技术 通过将稀疏的用户项目矩阵转化为由主成 分构成的稠密矩阵以解决数据稀疏问题 实验表明基于降维思想的方法显著提高 了推荐系统的伸缩能力 然而 降维会导致信息的损失 同时 降维的效果与数 据集密切相关 并且在项目空脚数目维数很高时 降维的效果难以保证 4 q 对于扩展性问题 研究者们发现基于模型的算法 如贝叶斯网络模型 虽然 可以在一定程度上解决算法的可扩展性问题 但是该类算法比较适合用户兴趣爱 好变化比较稳定的情况 而且模型训练的代价一般比较大 不太适合数据更新频 繁的系统 文献 4 8 中提到了两种改进的用户最近邻选择方法 当用户数量较大时 可以比较快速 准确地找到目标用户的最近邻居 在一定程度上可以改善扩展性 问题 综上所述 在当前研究一种新的协作过滤推荐算法 有效改善传统算法所面 临的以上问题 提高信息推荐的准确率即个性化服务的质量己显得尤为必要 这 也正是本文研究工作选题的目的和意义 1 2 主要研究内容 针对传统协作过滤推荐技术所面临的两个主要问题 数据的高维稀疏和算法 的可扩展性 结合居前国内外研究现状 提出了一种新的信息推荐算法 基于 资源项目类别的协作过滤算法 该算法在对资源项目分类的基础上 将传统的用 户对资源项目的兴趣转化为用户对资源项目依内容划分所属类别的兴趣 即将用 户对资源项目的评分转换为用户对资源项目所属类别的平均评分 对数据进行加 权过滤数据预处理之后 再运用K 平均聚类算法 对用户进行聚类 在目标用户 所在的簇中寻找其最近邻居集 最后根据最近邻居对项目的评分来预测目标用户 对资源项目的评分 从而产生信息推荐 虽然 资源项哥日益增多 但其依据内容划分所属类射的总数却相对比较固 定 且后者远小于前者 故将用户对资源项目的兴趣转化为用户对资源项目所属 类别的兴趣 可以在很大程度上降低评分数据矩阵的维度和稀疏性 聚类后 在 目标用户所在的簇中寻找其最近邻居 一方面缩小了最近邻的查找范围 提高了 协作过滤算法的扩展性 另一方面 同一簇中的用户由于兴趣较相似 它们共同 评分的数据往往较大 这样可以提高用户相似性计算的正确率 从而提高目标用 户最近邻选择的准确率 提高信息推荐的质量 同时 聚类算法可以离线进行 能够满足个性化服务系统实时往的要求 重庆邮电大学硕士论文第一章绪论 1 3 论文组织与结构 论文的内容安排如下 第一章 介绍了论文的研究背景和意义以及论文的主要研究工作 第二章 对数据挖掘及聚类分析技术傲了简单的论述 先介绍了数据挖掘的 概念 基本任务 过程 分类及其主要技术 然后介绍了聚类分析的概念 常用 数据结构 相似度度量的标准以及常用的聚类算法 第三章对个性化服务技术做了概述 具体包括个性化服务的实现 个性化推 荐技术以及个性化服务的体系结构等 第四章对协作过滤推荐技术进行了概述 具体包括协作过滤推荐技术的基本 原理 数据结构以及两种协作过滤推荐算法 同时介绍了基于用户的协作过滤推 荐算法中三种度量用户相似性的方法 并对协作过滤推荐技术进一步的研究工作 给出了总结与展望 第五章给出了基于项目类别的协作过滤推荐算法 I C C F 的设计思想和具体描 述 同时对算法的具体步骤进行了详细的叙述 最后 采用标准测试数据集 M o v i e L e n s 对I C C F 算法进行了仿真实验 具体包括 数据稀疏度实验 扩展性 实验以及预测精度实验 两种相似性度量对比实验和加权过滤数据预处理效果实 验 并对实验结果进行了分析和总结 论文最后进行了全面的总结 并对未来的工作进行了展望 重庆邮电大学硕士论文 第二章数据挖掘与聚类 2 1 数据挖掘 第二章数据挖掘与聚类 2 1 1 数据挖掘概述 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术 是知识发现过程中的关 键和核心步骤 其起源于商业 科学 工程领域中对隐藏在数据集背后知识的发 现和利用的需求上 数据挖掘是一门交叉学科 涉及机器学习 模式识别 统计 学 数据库 知识获取 知识表达 专家系统 神经网络 模糊数学 遗传算法 等多个领域 内涵和研究热点非常广泛 所谓数据挖掘就是从数据集中抽取或发 现并应用隐含的 以前未知的 具有潜在或者现实应用价值的信息和知识的过程 数据挖掘是一个反复迭代的过程 在这个过程中 所取得的进步用 发现 来定义 而这种发现是通过自动或手工方法取得的 在对什么将会构成一个 有 趣的 结果没有预定概念的初步探测性分析方案中 数据挖掘非常重要 它从大 量的数据中搜寻 有价值的 非同寻常的新信息 是人和计算机合力的结果 它 在人类描述问题和目标的知识与计算机搜索能力之间寻求平衡 以求获得最好的 效果 在实践中 数据挖掘的两个基本目标是预测和插述 预测涉及到使用数据集 中的一些变量或域来预测其他我们所关心的变量的未知或未来的值 另一方面 描述关注的则是找出描述可由人类解释的数据模型 由此 数据挖掘的活动大体可以分为两类 4 9 5 0 第一类侧重于应用已发现的 模式和规律 生成已知数据集所描述的系统模型 主要用于预测 分析评价 偏 差检测等 第二类侧重于在可用数据集上寻找隐藏 潜在的 未知的模式的过程 第 类数据挖掘的方法主要包括最近邻方法 基于案例的推理方法等 第二类数 据挖掘的方法则包括 1 基于逻辑的方法 既可以处理数值型数据 也可以处理非数值型数据 包 括基于规则方法 决策树方法等 2 十字表方法 只能处理非数值型数据 包括概念网等 3 方程方法 只能处理数值型数据 包括统计技术 神经网络等 重庆邮电大学硕士论文 第一二章数据挖掘与聚类 实际上更多方法属于两类方法之间或者不同的细类方法之间 第一类方法从认识论的角度上属于演绎的方法 第二类方法则属于归纳的方 法 由于数据挖掘目的侧重于寻找潜在和未知的模式或者知识 因而大多数的数 据挖掘算法都属于归纳方法的范畴 或者和归纳方法相联系 属于归纳的数据挖 掘算法又可以划分为有监督 教师 的学习方法和无监督 教师 的学习方法 有监督学习从已知输人输出的样本中进行字习 分类 函数逞近等是这种归 纳学习方法的典型应用 在有监督的学习过程中 假定存在具备环境知识和输入 输出样本集知识的老师的存在 但环境及其特性 模型参数等都是未知的 有监 督学习根据期望响应和学习系统实际响应的差值来调整学习系统的参数 学习算 法以误差来衡量系统功能 学习过程可以表示为误差曲面上点的移动过程 4 9 J 误 差曲面上点的移动定义为有监督的学习过程 有监督学习要求误差曲面上的点必 须连续地向误差曲面上的局部或者全局最小点移动 支持这类学习的技术各不相 同 比如对数回归1 5 感知机神经网络 决策树等 无监督学习没有外部老师来监视学习过程 其样本只有输入值而没有预期的 输出值 其要求学习算法自己建立并估计模型 自发地去发现在数据集中的潜在 结构 这种学习质量的衡量是独立于任务的 学习算法中的自由参数就根据这个 衡量的结果进行优化 一旦系统变得和输入相谐振 学习算法就建立输入样本的 内在表述 支持这类学习的技术包括神经网络中的自适应谐振神经网络等 2 1 2 数据挖掘的基本任务 数据挖掘的基本任务如下 1 分类 将被分类数据映射到 组事先指定的类中 但 聚类 根据对象属性实现未知空问分布的样本集的划分 同一组中数据的 相似性最大 组问的差异性最大 3 关联规则挖掘 发现数据变量之间或者数据集或者其一部分之 自J 的特征值 之问的重要相关性 4 预测与趋势性规则挖掘 发现数据集中普遍演变行为的规则 包括各类回 归方法 时间序列挖掘等 5 特征与辨识规则挖掘 发现数据集的所有数据满足的一般性特征和用于不 同数据集区分的辨识特征 6 偏差检测 应用所得到的模式发现异常或者最重要的变化 当然这里列出的只是数据挖掘任务中最主要的一部分 6 重庆邮电大学硕士论文第二章数据挖掘与聚类 2 1 3 数据挖掘的过程 数据挖掘过程一般包括以下步骤 1 陈述问题和阐明假设 这一步要求将应用领域的专门技术和数据挖掘模型 相结合 2 数据收集 数据的产生可以在专家 建模者 的控制之下 也可以随机产 生 3 数据预处理 其通常包括异常点的检测和去除 比例缩放 编码和特征的 选择 数据预处理的步骤不应该与数据挖掘的其他阶段完全独立 在数据挖掘过 程的每一次迭代中 所有活动加在一起都能为后面的迭代定义新的改进的数据集 一种好的预处理方法能为数据挖掘技术提供最佳的陈述 4 模型评估 选择并实现适当的数据挖掘技术是这一阶段的主要任务 5 解释模型和得出结论 对数据挖掘模型进行说明 从而有助于进行决策 整个数据挖掘过程如下图2 1 所示 2 1 4 数据挖掘的主要技术 图2 1 数据挖蜘的过程 数据挖掘的主要技术有 1 统计方法 典型的技术包括贝叶斯推理 对数回归 2 聚类分析 传统的聚类技术包括分裂聚类算法 凝聚聚类算法 划分聚类 算法和增量聚类算法等方法 重庆邮电大学硕士论文 第一二章数据挖掘与聚类 3 决策树和决策规则 典型的技术包括C L S 方法 I D 3 算法 C 4 5 算法等 及其剪枝算法 4 关联规则方法 包括购物篮分析 演绎算法和w w W 路径遍历模式等 5 人工神经网络 反向传播学习的B P 神经网络和K o h o n e n 的自组织映射神 经网络 多层感知机等神经网络 6 遗传算法 基于生物进化原理设计了一系列的基因组合 交叉 变异 自 然选择等过程 进行问题优化 7 模糊方法 基于模糊集合 模糊逻辑 模糊决策等 8 粗集方法 作为研究不确定性的数学工具 属于集合论的扩展 主要用于 研究不完全和不完整信息描述 可以用于聚分类 特征约简和最小属性子集约简 等 9 可视化方法 采用直观的图形方式将数据模式 关联 趋势呈现出来 可 以通过可视化的交互技术分析数据 自J 的关系 其包括几何学 基于图形 象素导 向和分层等技术 2 2 聚类 2 2 1 聚类概述 聚类分析是数据挖掘的基本任务之一 其依据样本问关联的度量标准将其自 动分成几个群组 且使同一群组内的样本相似 而属于不同群组的样本相异的一 种方法 聚类分析属于无监督的学习方式 其输入可以定义为一个二元组O s 其中工表示输入样本集 而S 表示样本间相似度或者相异度的判定函数 一个聚类 分析系统的输入是一组样本和一个度量两个样本问相似度 或相异度 的标准 聚类分析的输出是数据集的几个组 类 这些组构成 个分区或一个分区结构 聚类分析的一个附加的结果是对每个类的综合描述 这种结果对于更进一步深入 分析数据集的特性是尤其重要的 聚类分析作为统计学的一个分支和一种无监督的机器学习的方法 已有几十 年的历史 并已取得了许多研究成果 在数据挖掘领域 研究工作已经集中在为 大型数据库的有效 实际的聚类分析寻找适当的方法 活跃的研究主题集中在聚 类分析的可伸缩性 对复杂形状和类型数据聚类的有效性 高维聚类分析技术以 及对大型数据库中混合数值和分类数据的聚类方法等 不同的聚类算法都有各自 的优缺点和应用的范围 研究各聚类算法的特性使我们能够根据具体的应用领域 扬长避短 从而选择最适当的聚类技术解决实际问题 8 重庆邮电大学硕士论文第二章数据挖捌与聚类 2 2 2 相似度的度量 由于相似度是定义一个聚类的基础 所以同一特征空间中的两个模式的相似 度的度量标准对大多数聚类算法都是必不可少的 因为一个聚类分析过程的质量 取决于对度量标准的选择 所以必须仔细选取度量标准p q 假定每一个样本x 坝i l 2 门 都用向量X i 工j 1 工i 2 X i 来表示 棚的值是样本的维数 特征 n 是一个聚类过程中样本空 自J 中样本的个数 聚类分析按照样本在性质上的亲疏远近的程度进行分类 刻画样本点之1 日J 的 相似性主要有以下两类函数 1 距离函数 一般计算两个样本问的相似度 用特征空间中的距离作为度量标准来计算两 个样本间的相异度 对于某个样本空间来说 距离的度量标准可以是度量的 m e t r i c 或是半度量 q u a s i m e t r i c 的 以便用来量化样本的相异度 通常情况下 相异度的度量标准用d x x V x X 来表示 常称之为距离 当样本X 和l 相似时 距离a x F 很小 反之则很大 不失一般性 假定d x x 0 V x X X 距离的度量标准满足下面的三角 不等式 c l x x S d x 并 d x x V x z x X 最著名的距离度量标准是m 维特征空间的欧氏距离 d 2 x x 芝 h x 且 2 2 1 k l 另外一种经常使用的距离度量标准是L I 距离或城区距离 d l x x I x 一 I 2 2 l 明考斯基距离是包括欧式距离和城区距离的特例 d p x 工 一 石 2 3 k f f i l 2 相似系数 两个样本点越相似 相似系数越接近l 反之两个样本点越不相似 相似系 数越接近0 一般有如下两种度量方法 1 角度相异度度量 用向量夹角余弦公式度量两个m 维样本X 和Y 之间 9 重庆邮电大学硕士论文 第一章数据挖蠡 f 与聚类 的角度相异度 夹角余弦公式为 v Y s i m x Y 2 P e a s o n 相关系数 两个m 维样本x 和Y 之间的相关系数为 v 一弧 一巧 酊似墨力5 商毒雨丽 其中匕 v 为均值 2 2 3 聚类分析的常用数据结构 2 4 2 5 聚类算法最常用的两个有代表性的数据结构为数据矩阵和相异度矩阵 数据矩阵 采用关系表的形式 是一个n m 矩阵 表示具有聊个属性的胛个变 量 矩阵如下所示 扎 x x 1 x q x h i i X I x 相异度矩阵 矩阵中d i 为对象f 和对匆之间相异度的量化表示 它是一个 非负的数值 对象f 和 越相似d f 的值越接近o 反之则反 且d f o d i d j f 相异度矩阵比较全面的反映了各分类对象问的相似程度 是进行聚类分析 所依据的基础 矩阵如下所示 O d 2 1 0 d 3 1 d 3 2 0 10 d n 1 d 0 2 0 重庆邮电大学硕士论文 第二章数据挖捌与聚类 2 2 4 聚类分析的度量标准 聚类的目的是将数据对象分组形成多个簇 簇中的数据对象I 日J 的距离较小 簇间数据对象的距离较大 度量聚类分析的标准有许多 常见的有如下几种 1 可伸缩性 其指聚类算法要能够处理大数据量的数据库对象 有的算法在 数据规模较小的情况下 性能很好 但在大规模数据上会产生偏差 算法性能下 降 没有良好的可伸缩性 2 高维性 其指当数据对象的属性数目增多时 算法是否仍具有较好性能 3 对参数和数据输入顺序的敏感性 聚类分析的结果不仅对输入参数如聚类 数目 结果的支持度 置信度等很敏感 而且对数据的输入顺序很敏感 特别是 高维数据中 聚类分析的结果会因此很难控制 4 能处理噪声数据的能力 噪声是一些异常数据 其和数据集中数据对象不 一致 一些聚类算法对这些数据很敏感 从而导致错误的分析结果 5 结果的可解释性和可用性 聚类的结果最终都要表现为知识 面向用户 所以结果应该是容易解释和理解的同时具有可用性 6 增加限制条件后聚类分析能力 实际应用中会有各种限制 聚类算法在考 虑这些限制的条件下 仍需具有较好的性能表现 2 2 5 聚类算法 聚类算法基本都是基于下述基本思想 层次聚类方法 迭代的非层次的分区 聚类方法 基于密度的聚类方法 5 3 55 1 基于网格旧5 6 的聚类方法 每种思想都有 若干种常见的聚类算法 层次聚类思想有单链接和全链接聚类算法 而迭代的非 层次分区聚类方法则有K 平均算法 下面对应用较为广泛的几种聚类算法分别给 予介绍 1 层次聚类方法 层次聚类方法按类别嵌套规则组织数据 以形成层次的聚类结构 一般结果 可以树状结构来表示 根据聚类的方向可以进一步划分为凝聚算法和分裂算法 凝聚算法首先把每个对象或者小集合作为一个初始类 然后把这些类别合并 到若干个更粗糙的类别中 如此反复合并直到所有的对象都处在一个大类中 这 是一个由底向上的过程 逐渐由从精细到粗糙 而分裂算法正好相反 其首先把整 个样本集作为一个初始类别 再把其分解为若干个小类别 然后把每个小类别继 续依次分解下去 因而这是一个由顶向下的过程 体现出从粗糙到精细 由于聚类往往是在缺乏样本总体分布知识的情况下进行的 因而凝聚算法往 重庆邮电大学硕士论文第 二章数据挖捌与聚类 往比分裂算法更多地应用于实际应用中 层次聚类算法的基本步骤如下所示 1 把每一个样本作为一个类 为所有不同的无序样本对的类 日J 距离构造一 个序列 然后按升序对这个序列进行排序 2 通过已排序的距离序列 对于每一个不同的阈值以形成一个样本图 图 中将距离比巩更近的各对样本合并成一个新的类 如果所有的样本都是这个图的 元素则停止 否则 重复该步骤 3 这个算法的输出是一个嵌套的层次图 可以用希望的相似度水平去截取 在相应的子图中生成一个由简单联合标识的分区 类集 2 迭代的非层次分区聚类方法 迭代的非层次分区方法试图在一个水平上实现类内相似而类问差异的聚类结 果 因而是非层次的 为了获得最优解 往往必须迭代检验n 个样本被聚为k 个类 别的所有可能的分区组合 根据排列组合的计算方法 这个迭代过程在实际计算 上往往是不可行 因而研究了若干种启发算法来减少需要迭代检测的分区组合数 量 但目前研究并不能保证一定得到最优解 对于大型样本集 由于构造层次的聚类模型非常困难 因而分区的算法占有 应用优势 分区算法利用定义在局部或者全局的误差函数来优化生成聚类结果 产生每个类别的原型或者特征向量 然后可依据相似性原则将各个样本分配到各 个类别中 最常用的分区算法的误差函数是基于方差的方法 其目标是对于预先 指定的类数产生总体方差最小的分区结果 分区聚类算法中最常见的是K 平均算法 K 平均算法很容易实现 其时间复 杂度是O n k l 其中n 是样本集中样本数量 k 是类别数 是算法收敛时的迭代 次数 一般k 和 都是事先指定的 因此算法时间复杂度和样本集规模成正比 其 空间复杂度为D 僻 彬 因而空问效率很高 而且具备不依赖输入样本顺序的优良 特性 其缺点是对初始分区的选择较敏感 如果初始分区选择不当 会造成误差 函数的局部收敛 另外对异常点和噪音比较敏感 K 平均算法的基本步骤是 1 选择一个含有随机选择样本的x 个类的初始分区 然后计算这些类的中 心 2 通过把样本分配给与其重心距离最近的类生成一个新分区 3 用类的重心来计算新类的中心距离 4 重复步骤2 和3 直到求出准则函数的最优解 或直到类的成员稳定 基于分区的聚类算法普遍的缺点就是初始分区的选择 类别数目的确定没有 合理的方法 因而要求对样本空间要具备一定的先验知识 而这在实际应用中往 重庆邮电大学硕士论文 第 二章数据挖掘与聚类 往不一定能达到 从而限制了这种方法的广泛应用 3 增量聚类方法m 8 1 增量聚类算法具备广泛的用途 例如内存空间不足时用于从外层分批读入数 据进行空间的整体聚类 当空间分布发生变化时以原聚类结果为基础对聚类结果 修正 子空间内聚类的扩展等多项用途 其基本步骤是基于一定原则将数据向量 分配到现有类别中或者产生一个新类用于表示当前数据向量 在这一点上 增量 聚类方法类似于神经网络模型中的自适应谐振神经网络 其不需要事先指定类别 数目 聚类结果由分配规则和输入样本集动态决定 但只依赖增量聚类算法本身 和分区聚类算法一样不能产生层次结构的聚类结果 另外 大多数增量聚类算法 对于样本输入顺序是敏感的 2 3 本章小结 本章在对数据挖掘的概念 基本任务 数据挖掘的过程 分类以及数据挖掘 中的主要技术进行了概述的基础上 分别介绍了聚类的概念 聚类分析相似性度 量的方法 常用数据结构 度量标准以及常见的几种聚类算法 重庆邮电大学硕士论文 第三章个性化服务 第三章个性化服务 个性化服务通过收集和分析用户信息来学习用户的兴趣和行为 从而实现主 动推荐的目的 它能为不同用户提供不同的服务 以满足各自不同的需求 为了实现个性化服务 首先需要跟踪和学习用户的兴趣和行为 并设计一种 合适的表达方式 为了把资源推荐给用户 必须组织好资源 选取资源的特征 并采用合适的推荐方式 此外 还必须考虑系统的体系结构 考虑在服务器端 客户端和代理端实现的利弊 下面 我们从用户描述文件的表达与更新 资源描 述文件的表达 个性化推荐技术以及体系结构这四个方面来讨论个性化服务的实 现 1 1 0 3 1 用户描述文件 对个性化服务系统来说 最重要的是用户的参与 为了跟踪用户的兴趣与行 为 有必要为每个用户建立一个用户描述文件 u s e rp r o f i l e 用户描述文件刻画用 户的特征及用户之间的关系 在制定用户描述文件之前 需考虑以下几个问题 1 有没有现成的标准 2 收集什么数据 收集的数据用于什么目的 3 如何收集数据 根据什么信息源来收集 4 收集的数据如何组织 5 用户信息能否自适应地更新 用户描述文件还没有一个统一的标准 如W 3 C w w w w 3 c o r g 有两个涉及用户 描述文件的标准 P I C S p l a f f o r mf o ri n t e m e tc o n t e n ts e l e c t i o n 和A P P E L l O aP 3 P p r e f e r e n c ee x c h a n g el a n g u a g e1 o P I C S 是父母和老师用来控制孩子的浏览能力的 提供了过滤规则定义语占P I C S R u l e s A P P E L I O 可定义用户感兴趣的站点和过滤规 则 这些规则大部分是在P I C S R u l e s 的基础上发展起来的 此外 N e t s c a p e F i r e f l y 和V e r i S i g n 曾向W 3 C 的P 3 P I l l a f f o r mf o r 呻v a c yp r e f e r e n c e s T 作组提交了一个O P S o p e np r o f i l i n gs t a n d a r d 草案 由于目f i P 3 P 版本不打算考虑如何进行数据传输 因 此该草案被搁置一边 O P S 描述了如何表示一个用户描述文件以及用户与W e b 站点 交互的问题 在收集用户的信息之前 首先需分析用户愿意提供什么信息 用户一般都很 注意个人信息的保密性1 6 0 1 w w w c y b e r d i a l o g u e c o r n 的调查显示 8 0 的用户愿意 1 4 重庆邮电大学硕士论文第二章个性化服务 向W e b 站点提供自己的姓名 性别 年龄 教育背景和兴趣 但大多数用户不愿意 提供私有 敏感的信息 比如个入收入和信用卡号等 该公司另一项调查显示 2 8 的用户愿意W e b 站点向其他w 曲站点共享自己的信息 为了规范W e b 用户信息 的保密性 W 3 C 成立 J P 3 P 工作组来解决这个问题 它允许用户有选择地向W e b 站 点提供自己的信息 从而达到保护用户信息的目的 目前已有一些站点和浏览器 支持了P 3 P 比如w w w w 3 c o r g w w w m i c r o s o f t t o m w w w a 0 1 e o m w w w a t t p o m 等站点和M i e r o s o f t A T TP 3 P 浏览器等等 但还处于试用阶段 3 1 1 用户描述文件的表达 不同个性化服务系统的用户描述文件各有其特点 用户描述文件从内容上可 以划分为基于兴趣的和基于行为的两种类型1 6 基于兴趣的用户描述文件可以表 示为加权矢量模型 类型层次结构模型 加权语义网模型 书签和目录结构等 基于行为的用户描述文件可以表示为用户浏览模式或访问模式 在具体实现时可 以综合基于兴趣和基于行为这两种表达方式 3 1 2 用户信息的收集与更新 在用户第一次使用个性化服务系统的时候 系统可以要求用户注册自己的基 本信息和感兴趣的内容 系统也可以隐式地收集用户信息 在定制好一个用户描 述文件之后 系统可以让用户自主修改 也可以由系统自适应地修改 这样 系 统就可以随用户兴趣的变化而变化 系统要自适应修改用户信息 必须根据学习 的信息源分析当前用户的行为 从而调整用户兴趣的权重或调整用户兴趣层次结 构 根据学习的信息源 用户跟踪的方法可分为两种 显式跟踪和隐式跟踪 显 式跟踪是指系统要求用户对推荐的资源进行反馈和评价 从而达到学习的目的 隐式跟踪不要求用户提供什么信息 所有的跟踪都由系统自动完成 隐式跟踪又 可分为行为跟踪和同志挖掘 显式跟踪是简单而直接的做法 系统可以要求用户反馈自己对推荐资源的喜 好程度 一般情况下 这种做法很难收到实效 因为很少有用户向系统主动表达 自己的喜好 比较实际的做法是行为跟踪 因为用户的很多动作都能暗示用户的 喜好 用户行为可以表现为查询 浏览页面和文章 标记书签 反馈信息 点击 鼠标 拖动滚动条