基于关联规则的六度分隔系统设计与实现

1、华东师范大学 硕士学位论文 基于关联规则的六度分隔系统设计与实现 姓名：潘玲琳 申请学位级别：硕士 专业：计算机应用技术 指导教师：黄国兴 20070101 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 摘要 以B l o g ( 博客) 、T a g ( 标签) 、S N S ( S o c i a lN e t w o r k i n gS e r v i c e ，社会网络 服务) 、R S S ( 简易信息聚合) 、W i k i ( 维客) 等社会软件的应用为核心的W e b 2 0 热潮在全球范围内愈演愈烈。 在W e b 2 0 的热潮中，S N S 网站的发展潜力

2、最受关注。S N S 网站依据六度分 隔理论建立，以认识的朋友( 一度关系人) 为基础，在已有朋友的基础上扩展自 己的关系网( 一至六度关系) ，从而得到强大而有效的社会资源。六度分隔系统 是S N S 网站上的一个应用，帮助用户在S N S 网站的用户群中寻找、建立稳固的 一至六度关系，使用户在六度关系之上进行广泛的社会及商业应用。由于S N S 是新事物，目前国内外对六度关系的建立采取传统的关键字搜索，所建立的六度 关系“脆弱”，不能体现S N S 的个性化和社会化需求；使得六度关系在功能上不 能发挥应有的强大作用。 针对实际应用需求，本文将数据挖掘领域中最重要的两个技术：关联规则挖 掘技

3、术和分类技术，结合权重的思想，开创性地应用到S N S 六度分隔的实现上 来。这个系统工作在客户端，利用关联规则技术挖掘用户的潜在交友模式，综合 使用“系统评级”和“个性化评级”对属性进行加权，提高了挖掘规则的准确性； 使用了规则加权的分类技术对规则进行修剪。为用户提供了： 1 带有权重的一度关系人，使六度关系更新建立在可靠的一度关系之上； 2 根据不同分类规则对网站陌生用户进行分类，使用户可以基于这样的分 类群发针对性的邮件，实现社会目的( 交友) 和商业目的( 推广商品) 。 本文的主要研究工作和创新包括： 1 在对用户基本信息的处理上，考虑到挖掘的完整性，提出了针对本系统 特点的文本属性

4、概化、数值属性聚类及关联度加权补齐空缺值的方法； 2 在加权类关联规则的挖掘上，考虑到挖掘的准确性，使用“系统评级” 和“个性化评级”综合反馈用户信息，提出属性加权的类关联规则挖掘 算法，以提高类关联规则的精确性； 3 在用户分类的实现上，使用加权分类技术对类关联规则进行加权修剪， 改进了传统的C B A 算法，创建针对个人用户的分类器，挖掘带有权重 的一度关系人； 4 运用以上技术设计并实现了基于关联规则的六度分隔系统。 与传统的六度分隔系统相比，基于关联规则的六度分隔系统具有智能程度高 和针对性强的特点，适应了用户个性化需求，有着很好的实际应用价值。 华东师范大学计算机科学技术系2 0 0

5、 7 年硕士毕业论文 关键词：S N S ，六度分隔，关联规则，分类，概化，聚类，C B A 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 W i t ht h ef a s td e v e l o p m e n to fI n t e r a c tt e c h n o l o g y ，W e b 2 0b e c o m e st h eh o ts p o t i nt h ew o r l d B l o g ，T a g , S N S ，R S S ，W i l d a p p l i c a t i o n sa r ec h i e f r e p r e

6、 s e n t i v e s o f W e b 2 0i nt h eg l o b a ls c o p e I nW e b 2 0u p s u r g e s , S N S ( s o c i a lN e t w o r k i n gS e r v i c e ) w e b s i t e sp o t e n t i a ld e v e l o p m e n ta t t r a c t sm o s ta t t e n t i o n s S N Si sa no n l i n ee x p e d m e n t b a s e do nt h es i x

7、d e g r e e so fs e p a r a t i o nw h e r ei n d i v i d u a l sc a na t t e m p tt oc o n t a c ta s t r a n g e ri na n o t h e rp a r to ft h ew o r l dt h r o u g ht h e i rc o n n e c t i o n sw h i c hc 蛆o f f e r i n d i v i d u a l su s e f u lS O U r C e so fp e o p l e S i xD e g r e e so

8、 f , S e p a r a t i o nS y s t e mi sa l l a p p l i c a t i o nb a s e do nS N Sw e b s i t e ，h e l pU s e r St os e e ka n de s t a b l i s hs t a b l es i xd e g r e e r e l a t i o n si nt h eS N Sw e b s i t e A n dt h e nt a k ec o m m e r c i a lu s ea b o v es i xr e l a t i o n s A t p r

9、e s e n t ，f o r e i g na n dd o m e s t i cr e s e a r c h e so nt h ee s t a b l i s h m e n to fs i 】【d e g r e er e l a t i o n s a r ea l m o s tb a s e do nt h et e c h n o l o g yo fs e a r c he n g i u e sw h i c hm a t c ht h eu s e rb y k e y w o r d s T h e y 啪n o td i go u tt h ei n t e

10、n t i o no fu s e r s q u e r i e sa n dt h es o c i a l i z e d d e m a n d I nv i e wo f p r a c t i c a ld e m a n d ，t h ep a p e rc o m b i n e st w om o s ti m p o r t a n t t e c h n o l o g i e s ；A s s o c i a t i o nR u l e sa n dC l a s s i f yc l u s t e r i n gi nd a t am i n g i n gd o

11、 m a i nw i t h t h em e t h o do fw e i g hi n t ot h ea p p l i c a t i o no fs i xd e g r e es e p a r a t i o n T h i ss y s t e mw o r k s i nt h ec l i e n t ，u s e sa s s o c i a t i o nr o l e st od i go u tf r i e n d p a t t e r n , c o m b i n e s “t h es y s t e m r a t i n g a n d “t h

12、ei n d i v i d u a lr a t i n g t oe n h a n c et h ea c c u r a c yo fr o l e s ，i m p r o v e st h e c l u s t e r i n gt e c h n o l o g yb yw e i g h i n gm e t h o d A sr e s u l t ，t h es y s t e mp r o v i d e se a c hu s e r ： 1 W e i g h e df i r s t d e g r e er e l a t i o n s ； 2 C l a s

13、 s i f i e st h es t r a n g e r sf o rt h eu s e ra c c o r d i n gt ot h ed i f f e r e n tc l a s s i f i e dm l e s ， e n a b l e st h eu s e rt a k ec o m m e r c i a la c t i v i t i e sa b o v et h ec l a s s e s ，s u c ha s s e n d i n ge m a i l sa n d s oo n T h ep a p e r sp r i m a r yw

14、o r k sa r ea sf o l l o w ： 1 T op r e - p r o c e s st h eu s e ri n f o r m a t i o n ，t h ep a p e rp r e s e n t ss e v e r a lm e t h o d s b a s e do nt h es i xd e g r e er e l a t i o ns y s t e m s ，i n c l u d i n gt e x td a t ag e n e r a l i z a t i o n m e t h o d ，n u m e r i c a ld

15、a t a c l u s t e r i n g m e t h o da n dr e l a t i o nb a s e d h o td e c ki m p u t a t i o nm e t h o d ； 2 R e s e a r c h i n go nw e i 曲e dc l a s sa s s o c i a t i o nr o l e s ，t h ep a p e rp r e s e n t s “t h e s y s t e mr a t i n g ”a n d “t h ei n d i v i d u a lr a t i n g t oe n

16、h a n c et h ea c c u r a c yo fr u l e s ； 3 I nt h e i m p l e m e n t a t i o n o fw e i 【g h e dc l a s s i f y i n g ，t h ep a p e ri m p r o v e d t r a d i t i o n a lC B A s t a b i l i t ) ，b yr o l e - w e i g h i n gm e t h o d A d j u s t st h ei n t e n s i t yo f I 华东师范大擎计算杌科学技术系2 0 0

17、7 年硕士毕业论文 r o l e su s i n gm l ew e i g h i n gm e a n sW N e w _ C B A T h em e t h o d 啪i m p r o v e r a d i c a l l yt h eq u a l i t yo ft r a i n i n gs e t a n dr e a c hp u r p o s eo fc l a s s i f i c a t i o n p e r f o r m a n c e ； 4 D e s i g n sa n di m p l e m e n t st h eA s s o c

18、i a t i o nR u l e s b a s e ds i xd e g r e es e p a r a t i o n s y s t e m C o m p a r e dw i t h c o n v e n t i o n a ls i x d e g r e es e p a r a t i o nf u n c t i o n s ， A s s o c i a t i o n R u l e s - b a s e ds i xd e g r e es e p a r a t i o ns y s t e mi s i n t e l l i g e n ta n dt

19、 a r g e t e da t t h eu s e r s i n t e r e s t I tn o to n l ym e e t st h ep e r s o n a l i z e dr e q u i r e m e n t s ，b u ta l s op r o v i d e si n t e l l i g e n t a n dp e r s o n a l i z e ds e a r c h i n ga s s i s t a n c e ，a n di th a sap r o m i s i n ga p p l i c a t i o nf o r e

20、 g r o u n d K E YW o R D ：S o c i a lN e t w o r kS e r v i c e ， r u l e s ，C l a s s i f i c a t i o n ，C o n c e p t u a l i z a t i o n ， A s s o c i a t i O l l S i xD e g r e eS e p a r a t i o n ，A s s o c i a t i o n C l u s t e r i n g ，C l a s s i f i c a t i o nB a s e do n 学位论文独创性声明 本人所

21、呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：日期：趔幽 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者签名：

22、 日期： 华东师范大擘计算机科学技术系2 0 0 7 年硕士毕业论文 第1 章引言 随着信息技术革命的进行，W e b 2 0 正在成为当下的热点。互联网的表现形 式和后台技术架构的重构，使得传统的互联网门户网站已经跟不上发展的脚步， W e b 2 。0 将成为互联网传统门户网站的升级。 W e b 2 0 最基本的特点就是符合用户的习惯。W c b l 0 时代对贴近用户心理方 面也有所关心，但是大多体现在给整体用户提供一类的方案，而不能针对每个用 户。比如W c b l 0 的广告系统是单一的，而W e b 2 0 的广告则可以根据用户页面内 容出现相关广告。不难发现，这样一来使得W e

23、 b 2 0 网站信息量大而分散，网民 个性化的需求成为数据挖掘应用的绝佳机会。 在W e b 2 0 的热潮中，基于六度分隔理论( 两个陌生人最多通过6 个人就可 以建立关系) 的S N S 网站是最受关注的。S N S 网站以认识的朋友为基础，经营 自己的人脉：分享共同的兴趣爱好( 豆瓣网) 、拓展商务人脉( 联络家) 、为求职 做准备( 人联网) 等。从社会和商业需求的角度来看，S N S 是好东西，包括美国 顶级V C ( V e n t u r eC a p i t a l ，简称V C ) 公司A C C B L 在内的许多国内外风险投资 公司，均表示出对S N S 网站的强烈投资

24、兴趣【。但是从实现角度而言，做S N S 网站的难度也不小，大致集中在以下三个方面： 1 “廉价的六度关系”；目前S N S 网站建立好友的模式有两种，其中一种 是静态地将用户与用户认识的人建立维度关系。单纯地把认识的人的认 识的人变成自己的朋友，这样简单地串联起来，而不是通过挖掘其兴趣、 工作、背景等相关信息建立强而有效的维度关系，忽略了S N S 最重要的 特征，将具备相关兴趣的人聚集在一起。 2 “单纯的关键字搜索”：目前S N S 网站建立好友的第二种模式是关键字 搜索。如果一个银行信贷员想在S N S 网站中搜索一些潜在客户成为好 友，他只能通过搜索关键字：如I n c o m e

25、( 收入) 、P o s i t i o n ( 职位) 等属 性来寻找满足条件的客户。但是，I n c o m e 、P o s i t i o n 等属性都属于个人 隐私属性，一般用户不予以公开；如果网站予以公开，搜索结果则数以 千计，无法供用户实际选择。这样一来，单纯的关键字搜索，不足以满 足用户逐一交友的需要。 3 用户激增、信息分散、数据量大：现在运营颇有成效的S N S 网站动辄数 十万用户。如何从海量数据中应用信息，如何建立自动化的工具挖掘用 户间隐藏联系，如何建立陌生用户之问连接，已成为迫切需要解决的研 究课题。 华东师范大擎计算杌科学技术系2 0 0 7 年硕士毕业论文 本章

26、将首先解释W e b 2 0 、S N S 网站、六度分隔理论等概念；介绍国内外现 有S N S 网站六度分隔实现情况及不足；然后阐述论文研究的现实意义，明确本 课题主要研究内容及创新；最后给出论文的章节安排。 1 1 研究背景 W e b 2 o 正在让互联网逐渐找回I n t e m e t 的真正含义：平等、交互。 W e b 2 0 精髓就在于以人为本，提升用户使用互联网的体验。用户不单是互 联网的读者，也应该是互联网的作者。具体而言，W e b 2 0 在模式上是从读向写 到信息共同创造的一个改变；在基本结构上是由网页向发表展示工具演变；在 工具上，是由互联网浏览器向各类浏览器、R

27、S S 阅读器等内容发展；在运行机制 上则是自“C l i e n tS e w e r ”向“W e bS e r v i c e s ”的转变。由此，如图1 - 1 所示，互 联网内容的缔造者也由网站内容提供商向普通用户拓展。 图1 - 1W e b l 0 到W e b 2 0 的转变 在W e b 2 0 的背景下，每个用户都拥有自己的B l o g 、自己维护的W i k i 、社会 化书签或者P o d c a s t 。用户通过T a g 、R S S 或者I M 、邮件等方式连接到一起，按 照六度分隔理论，每个个体的社交圈都不断放大，最后成为一个大型网络，这其 实就是一个大型的

28、S N S 网络【2 l 口本节将对W e b 2 0 、S N S 、六度分隔及相关概念 作出介绍。 1 1 1W e I ) 2 O 目前为止，关于W e b 2 0 并没有清晰的定义。业内普遍的一种说法是B l o g g e r D o n 对W e b 2 0 的诠释。 定义1 - 1W e b 2 0 W e b 2 0 是以F l i c k r 、C r a i g s l i s t 、L i n k e d i n T r i b e s 、R y z e 、 F r i e n d s t e r 、D e l i c i o U S 、4 3 T h i n g s 0

29、 0 n l 等网站为代表，以B l o g 、T a g 、S N S R S S 、 华东师范大擘计算机科学技术系2 0 0 7 年硕士毕业论文 W i k i 等社会软件的应用为核心，依据六度空间、X M L 、A J A X 等新理论和技术 实现的互联网新一代模式1 3 J 。 直观地说，W e b 2 0 是以个人为中心，强调用户“参与性”为核心的网。正 是因为用户的参与，才引发了进一步的互动，原创内容、增加互动性，而互动性 反过来又推动了原创，从而为信息的积累和传播奠定了最根本的基础。W e b 2 0 彻底改变了互联网上人与人的关系，使得互联网成为一个有机的社会性网络，单 个的用

30、户就像大脑的神经，彼此的联系通过复制和强化变得越来越强，而作为所 有网络用户所有活动的直接结果，互联网也将有机地成长。 当然，这个个人不是孤立的个人，而是彼此相连的。个人与个人之间，以及 个人与群体之间，群体与群体之间，都是以不同的组织方式，架构起来。以组织 的方式让人、内容和应用等充分“活动”起来，力量才能最大程度爆发。 所以，不难发现，随着W e b 2 0 的发展，所带来的问题也集中在如何建立自 动化的工具从海量数据中找出规则进行用户细分、为用户提供个性化服务；如何 划分不同群体的用户，将有潜在关系的用户组织起来，以组织的方式让人、内容 充分“活”起来，加剧交互和原创动力。 在W e b

31、 2 0 的热潮中，S N S 网站是最受关注的。S N S 网站于2 0 0 3 年3 月在 美国出现，被众多互联网企业和投资家所看作未来两年内增长最快的业务。很多 用户从S N S 的网站认识兴趣接近的好友，更多用户利用S N S 进行营销。利用S N S 网站的参与者的身份( I d e n t i t y ) 、电子档案( P o r t f o l i o ) 、交流模式( C o m m n i c a t i o n ) 以 及社会关系网络( S o c i a lN e t w o r k ) ，使社区营销的操作更加方便和精确，包括预测 用户的行为、目标市场的确定、产品或服务的

32、定位都将更为准确。 S N S 为什么会受到如此大的关注，什么是s N s ? 在介绍S N S 之前有必要先阐 述两个理论：六度分隔理论和1 5 0 法则。 1 1 2 六度分隔 六度分隔理论是由美国著名社会心理学家米尔格伦( S t a n l e yM i l g r a m ) 于2 0 世 纪6 0 年代最先提出：“你和任何一个陌生人之间所问隔的人不会超过六个，也就 是说，最多通过六个人你就能够认识任何一个陌生人 4 1 。”1 9 6 7 年，哈佛大学的 心理学教授米尔格伦想要描绘一个连结人与社区的人际连系网，他做过一次连锁 信实验，将一套连锁信件随机发送给居住在内布拉斯加州奥马哈

33、达标1 6 0 个人， 信中放了一个波士顿股票经济人的名字，要求每个收信人将这套信寄给自己认为 是比较接近那个股票经济人的朋友。朋友收信后再如此做。最终，大部分信在经 过五六个步骤后都抵达了该股票经济人。“六度分隔”( 也叫“六度空间”) 这个 华东师范大擘计算机科学技术系2 0 0 7 年硕士毕业论文 词由此丽来。 举一个现实的例子，在0 5 届计算机系一个六十人的班级里面找一个同学， 如果限制条件为学生互相不认识，只能询问某个学生“你是某某某吗”不难计 算得到，要找到这个学生最多需要问六十次，最少需要问一次。如果查找是随机 的，平均复杂度是6 0 2 = 3 0 。但是如果将限制条件取消，

34、即学生互相认识，也就 是说通过这个学生可以得到下一个学生的信息。那么最多两次询问，最少一次询 问，就可以找到要找的同学。一如果查找是随机的，平均复杂度( 5 9 2 + 1 W 6 0 约 等于2 。 六度分隔理论实际上描述了任意两个人之间建立联系的复杂度，建立任意两 个人之间的联系，可能只需要六次，或者说只需要惊动六个人。如此看来，我们 所有人都可以在“六度空间”里联系起来。 曾经六度分隔只能作为理论而存在。现在互联网使一切成为现实。然而，六 度分隔的目的不是为了证明地球上所有人都可以通过少于或者等于六度来联系， 而是想说明社会性网络的各个结点是完全有可能链接起来，发挥非常强大的作 用，可形

35、成各种各样的社群，甚至是世界性的社会性网络。 依据六度分隔理论，S N S 网站以认识朋友的朋友为基础，扩展自己的社会资 源。 1 1 31 5 0 法则 六度分隔理论也给研究者带来一个问题，在S N S 网站中，用户A 是不是需 要将所有好朋友的好朋友都建立关系，成为自己的一度好朋友昵? 这就涉及到 六度空间的宽度问题。我们假设深度为6 ( 六度空间) ，那么每一度关系的宽度 ( 联系人数) 设定为多少昵? 由此引发S N S 网站第二个原理：1 5 0 法则。 罗宾邓巴( R o b i n D u n b a r ) f l j 欧洲发源的“赫特兄弟会”( 一个自给自足的农民 自发组织)

36、 的一个不成文的严格规定：每当聚居人数超过1 5 0 人的规模，他们就 把它变成两个，再各自发展，提出了1 5 0 法则：“把人群控制在1 5 0 人以下似乎 是管理人群的一个最佳和最有效的方式l ”。” 罗宾邓巴认为这和人脑的进化程度有关，在灵长类中人的大脑最大，所以可 以有最大的社会关系处理能力。但是如果社会圈子的数量增加，人脑的智力负担 显然要呈现级数增长变化。由他所提出的一个模型方程中，考虑了动物本身的大 脑新皮质相对脑的比率，可以得到某种动物所拥有的活动群体的最大值。如果输 入人的比率，那么这个数值为1 4 7 8 ，大约为1 5 0 。 1 5 0 法则也同样投入了实践，显著的应用

37、是M S N 的1 5 0 个好友限制和中国 - 4 - 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 移动动感地带套餐的1 5 0 人限制。 I I 4S N S 网站 S N S 网站如图1 2 所示，就是一个以六度分隔为深度，以1 5 0 法则为宽度的 网络。假设每个人的人际网络是1 5 0 人，通过6 个人的人际关系网络可达人数便 是：1 5 0 的六次方= 1 5 0 1 5 0 x 1 5 0 1 5 0 1 5 0 x 1 5 0 = 1 1 3 9 0 6 2 5 0 0 0 0 0 0 ，远超过人类 历史上所有各代的人数之和。 一度 二度 六度 图1 - 2 S

38、 N S 网站 S N S 的发展速度非常惊人，G o o g l e 推出1 G B 免费信箱也是一个S N S 应用， 通过网友之间的互相邀请，在很短的时间内就获得了巨大的用户群。传统的B B S 、 1 M 等是关系的S N S ，但现在的S N S 服务更关注帮助用户提供用户之间关系的挖 掘。 1 1 5 六度分隔系统 六度分隔系统是S N S 网站上的一个应用架构，帮助用户在S N S 网站上寻找 六度关系，建立六度关系，更新六度关系，并在六度关系上进行初步的社会和商 业应用。正因为基于六度分隔的理论，使得构建于S N S 网站上的应用越来越人 性化、社会化。网站的社会化，即在功能上

39、能够反映和促进真实的社会关系的发 展和交往活动的形成，使得人的活动与软件网络的功能融为一体。六度理论的发 现和发展向人们表明：社会性软件所构建的“链接”，正在人们的生活中扮演越 来越重要的作用。S N S 网站还处于起步阶段，对于它未来的发展方向，现在也没 有一个统一的认识。因此，迫切需要一些系统化的工具，来解决用户的需求，实 现S N S 的人性化、社会化功能。 华东师范大擘计算机科学技术系2 0 0 7 年硕士毕业论文 1 2 国内外研究现状 通过网络使“六度分隔”理论实现人人之间都可以构成纽带，理想的前提是 人人都置身在连接的世界中，值得兴奋的是，这个目标正在不断接近。这样在网 络中架构

40、人与人之间的关系网，信息就可以在上面有针对性的传播。 S N S 网站最典型的应用就是信息的传播：人、社会、商业都有无数种排列组 合的方式，如果信息不能有目的性的传播，就很容易损耗掉。但是在S N S 网站 构件的关系网上，以用户个人为中心点，信息就可以在上面有针对性的传播。 不妨再以银行信贷员为例，他将导入的好友分类为客户类和普通好友类，以 自身为中心点，向客户类的一至六度好友发送银行信贷新品的邮件，就相当有针 对性，不会被系统、其他用户认为是垃圾邮件；反过来，当他的一至六度好友们 接受到他的邮件，相对于普通的广告他们更乐于接受他的广告内容。“精准营 销”、“分众营销”也伴随着S N S 网

41、站而兴起，这样的应用将发挥巨大的商业价 值。 S N S 网站于2 0 0 3 年兴起于美国，相比之下，国内的S H S 网站从2 0 0 4 年底 才兴起。国内外的研究都刚刚起步，对于S N S 网站尚在研究摸索阶段，所以虽 然呼声很高，但研究都不曾深入。 1 2 1 国外研究现状 国外对S N S 网站的研究集中在自动获取人际关系和六度分隔最短加权路径 问题上。 最早由考茨( K a u t z ) 和斯尔曼( S e l m a n ) 仓t J 建了一个从互联网上获取人际关系 的网络，R f e r r a lW e b l 6 1 。这个抓捕程序的搜索引擎注重页面的重名现象。他将两

42、个联系人x 和Y 在搜索引擎中定义为“Xa n dY ”。这样的关系未免简单而显得 不“牢靠”，于是，迈克限M i k e ) 在此基础上开发了一个新的抓捕系统，综合化在 线语义网络环境下的社区关系，被称作F l i n k 7 1 。它的主要方法足从网络页面， 电子邮件信息，和各种出版物或个人发布资料( F O A F 文件) 中抓捕人际网络， 该系统加入了重名分析，将一系列名字作为输入，组件将用搜索引擎计算出潜在 关联度。接着Y u t a k aM a t s u o 设计并实现了一个人际网络抓捕程序 P O L Y P H O N E T ，语义被加入到搜索问句中来防止歧义，通过分析参

43、与某项会议 的全体人员所发表的论文中的语义，选定特征关系( 如：师生关系、同事关系、 同学关系等) ，寻找关键字的重复性( 如：学校、论文关键字) ，从而快速建立联 系人【8 I 。 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论之 上述研究旨在通过人名和语义的方法在陌生的环境中寻找到已经存在的现 实中的关系，并不是在陌生的环境中，挖掘个人的交友模式来建立潜在的关系， 忽略了S N S 的社会化功能。 六度分隔最短加权路径算法则集中在对六度关系进行加权的处理，即结合路 径权重搜索出一个用户到达另外一个用户的最短路径。也就是找出这两个用户之 间通过最少的用户的链接。在六度关系中每个人可

44、以看作是有向图中的节点，有 大量路径连接着它们，相连接的节点表示互相认识的人。把一度关系的作用看成 路径图中对应点和边的权值，而且一个点或者一条边可以赋予多个权值来描述不 同的场景中关系的作用( 对于非一度作用) ，可以通过定义路径上多个边的权值 计算规则，这样路径也就变成有权值的了。 但是，这种加权与具体的使用环境和经过的联系人密切相关，对人的权重很 难数值化。如何确立路径图中对应点和边的权值，一直无法得以妥善解决，相关 研究也少而甚少。 1 2 2 国内研究现状 国内的研究刚刚开始，绝大多数的S N S 网站把精力放在商业功能的拓展上， 忽视了一度关系的建立和六度关系的发展，而一度关系正是

45、六度分隔的基础。 国内网站建立一度关系的方式目前局限于基于“关键字搜索”和静态的添加 认识的人为好友。如图1 3 ，用户A 在S N S 网站注册为用户，通过关键字搜索， 如；公司名、学校名，找到校友或者同事与他建立联系，再通过查看已经建立联 系的人的一度联系人，与其朋友的朋友建立连接，把所有一度以外的N 度，通 过联系人转变成一度。单纯地把认识的人的认识的人变成自己的朋友，这样简单 地串联起来，而不是通过挖掘其兴趣、工作、背景等相关信息建立强而有效的维 度关系，忽略了S N S 最重要的特征，将具备相关兴趣的人聚集在一起。 可以说国内对六度分隔的研究只是初步，对六度分隔短加权路径的研究也只

46、浮于表面。 华东师范大擘计算机科擘技术系2 0 0 7 年硕士毕业论文 继耋_ 一一一 l 固 网稽体翩署口繁体髑誊 公司名纛r 一 璐名称 l 一一j 越：鬻鞔箍考舞茹谨謦 毕业撒 二二二二二二二二 ( 镪溅屠爆膏麓轭蕞j 所在墟 行业尧剐 职棼羹飘 职务譬蹑 性射 箍髫 谢毒 苹瞄掷翟谳搬露”请选择固 圊e 二二 丽( 二二二毯 M 二二二二二= 誓 0 男O 女0 ：硐 徽， 图1 - 3 国内现有S N S 网站以关键字搜索建立一度关系 六度的目的不是仅仅为了建立关系而把所有的一度以外的N 度关系变成一 度关系。而廉价的一度关系，恰恰就是目前S N S 网站之所以失败的根源所在。 挖掘

47、强而实际的一度关系，将不同类别的一度关系分类，给予不同的权重，是六 度分隔理论实现的基础，再在此基础上进行六度分隔的更新才有社会化的意义。 所以，挖掘带有权重的一度关系是本文研究的重点。 华东师范大学计算机科学技术系2 0 0 7 丰硕士毕业论文 1 3 主要研究内容及创新 国内外S N S 网站的六度分隔系统如图1 4 所示，大致分为如下几个功能： 1 注册功能：用户注册、好友邀请。 2 搜索功能：好友搜索、陌生人搜索。 3 六度分隔功能：更新六度分隔关系。 厂 注毒功能 、 用户A 注册 上土 用户A 导入好友 I7 l 好友B 注册 土 土 广一系统更新用；拿六度关系表 ! l 好友B

48、导入好友I ， 之岁 搜索功能 、 用户关键字搜索想与之建立关系的 上上 系统反馈用户A 查找结果 上土 用户A 选择陌生用户F ，E ，G | ， 六度分隔功能、 弋 7， 系统最短加权路径算法找出到陌生用户F ，E ，G 晟合适的节点( N 度) 上 用户A 通过系统提供的节点发邀请信给陌生用户F ，E ，G 建立N 度关系 上 _ J用户F ，E ，G 接受邀请 图1 4S N S 网站六度分隔系统主要功能模块 就目前S N S 网站六度分隔系统的主要功能来看，面临的问题有：如何建立 有效的一度关系；如何寻找稳固的一度关系和设定一度关系的权重；如何利用六 度分隔，并以用户需求为导向，结合

49、1 5 0 法则，建立一个精确而又有效的分类， 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 为用户划分其它用户，使用户进行商业应用，真正参与到网络中来，发挥良好的 主动性和互动性。本文主要的研究目标就是通过对数据挖掘的若干技术的研究， 提出有效的模型和算法，具体包括数据挖掘中的关联规则、分类技术来解决上述 问题。 针对以上的研究目标，本文的具体研究内容与创新如下： 用户数据预处理 现实世界中的数据一般是不完整的和不一致的。数据预处理技术用于改进数 据的质量，从而有助于提高其后挖掘过程的精度和性能。本文就六度分隔系统用 户信息( U s e r 表) 的不同特点，介绍了数据预处理

50、的一般方法。创造性地提出 了针对文本属性概化、数值属性聚类及关联度加权补齐空缺值的方法，来改善关 联规则挖掘和用户分类的质量。 加权类关联规则挖掘的研究 常见的关联规则挖掘算法基于数据集中每个属性都有相同的重要性，但在实 际运用中的情况往往是某些属性的重要度比普通属性大、而某些属性的重要度比 普通属性小。本文介绍了常见的关联规则挖掘方法，讨论了权值的定义，使用“系 统评级”和“个性化评级”综合反馈用户信息来定义权值。结合六度分隔系统应 用，创造性地提出了加权的类关联规则挖掘算法。 利用加权方法提高分类器的稳定性 分类和关联规则挖掘是两种重要的数据挖掘技术。目前，针对关联规则挖掘 用于分类问题的

51、研究还不多。本文研究了已经提出的关联分类算法，并在此基础 上做了改进，提出了规则加权的分类算法 t , V l q e wC B A ，用来创建用户分类器， 挖掘带有权重的一度关系人。 基于关联规则的六度分隔系统 六度分隔是建立在S N S 网站上的系统，目前国内的研究局限在关键字找人 来建立N 度关系。本文将关联规则和分类技术应用在六度分隔系统之上，创造 性地提出了基于关联规则的六度分隔系统。通过单个用户的一、二度关系人建立 训练集，使用加权的类关联规则算法挖掘类关联规则；再由单个用户的其它N 度联系人建立测试集，使用规则加权的分类算法生成分类规则。为用户提供了带 有权重的一度关系人，为实现

52、六度最短路径提供了基础；根据不同分类规则对网 站陌生用户的分类，使用户可以基于这样的分类群发针对性的邮件，实现商业目 的。 华东师范大学计算机科学技术系2 0 0 7 年项士单业论文 1 4 论文章节安排 本文的章节安排如下： 第一章引言。主要介绍论文研究的背景和现状，阐述了六度分隔和1 5 0 法则 的理论，描述了S N S 网站和六度分隔系统国内外的研究情况。明确论文的主要 研究内容和创新之处。 第二章用户数据预处理。首先阐述用户数据预处理的主要概念和方法，并针 对本文所涉及的数据特点分别提出了针对文本属性的概化算法、针对数值属性的 聚类算法和关联度加权的空缺值补齐算法。 第三章基于关联规

53、则的分类算法。介绍了基于关联规则的六度分隔系统所涉 及的主要技术：关联规则挖掘和分类的基本算法。在此基础上仔细阐述了加权关 联规则的权值定义和基于关联规则的分类算法。 第四章交互加权的关联分类算法。结合第三章的内容，针对六度分隔的特点 提出了两种交互加权的关联分类算法，给出了详细的问题描述和算法流程。 第五章基于关联规则的六度分隔系统设计。介绍了系统框架和各个模块的功 能。该系统应用了基于关联规则的分类思想，并综合使用“系统评级”和“用户 评级”来对属性定义权值。 第六章基于关联规则的六度分隔系统实现。介绍了系统实现的环境和一些关 键技术，并给出了操作界面和运行情况。 第七章总结了论文的研究工

54、作，指出了进一步的工作方向。 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 1 5 本章小结 本章介绍了W e b 2 O 、S N S 和六度分隔的基本概念。分析了现有S N S 网站上 六度分隔的功能和研究状况：人际关系抓捕、最短加权路径搜索、关键字搜索。 阐述了本文的主要研究内容和创新。在第二章中，将介绍数据预处理的相关技术， 并结合六度分隔系统后台数据库的实际情况，提出一些新的处理方法。 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 第2 章用户数据预处理 数据预处理是开始关联规则挖掘和分类的重要步骤，许多因素会影响六度分 隔系统的质量：如何归约文本属性(

55、如学校U n i v e r s i t y ，住址A d d r e s s 等) 。如何 离散化连续的数值属性( 如年龄A g e ，收入I n c o m e ，工作年限W o r k i n g L c n g t h 等) 。 如何处理空缺值( S N S 网站的数据信息由用户在线输入，部分属性如U s e r 表中 的I n c o m e 属性，可能因为用户输入时认为是隐私而不填，导致属性不完整) 。上 述这些都需要首先考虑，以确保关联规则挖掘质量。由此可见，数据预处理至关 重要。 数据预处理技术在许多文献中均有讨论，对相关技术也作出了介绍，本文在 前者讨论的基础上提出了针对基于

56、关联规则的六度分隔系统后台数据的特别处 理方法。 本章将首先介绍用户数据预处理的一般流程，然后结合六度分隔系统详细介 绍了数据变换及归约中数据概念化分层和聚类的方法、数据清理中空缺值的处理 方法，并在这基础上提出了针对基于关联规则的六度分隔系统数据预处理的方 法。 2 1 数据预处理流程 现实世界的数据一般是不完整和不一致的。数据预处理技术可以改进数据的 质量，有助于提高其后挖掘过程的精度和性能。由于高质量的决策必然依赖于高 质量的数据，因此检测数据异常、尽早地调整数据、归约数据，将在挖掘过程中 得到高回报。 数据预处理在【9 J 中已经有了详细的描述，一般有如下四个步骤： 1 数据清理( D

57、 a t aC l e a n i n g ) 操作，通过填写空缺值，平滑噪声数据，识别、 删除孤立点，解决不一致来“清理”数据。 2 数据集成( D a t aI n t e g r a t i o n ) 操作，将多个数据集的数据存储合并，转换成 适合挖掘的数据形式。 3 数据变换( D a t aT r a n s f o r m a t i o n ) 操作，一般采用概化和规范化的方法，也 可以由原来的属性，经概化生成新的属性，添加到属性集中，帮助关联 规则挖掘。 4 数据归约( D a t aR e d u c t i o n ) 操作，通过归约可以得到压缩的数据集，压缩 后的数据集

58、能够产生同样的( 或几乎同样的) 分析结果。有许多数据归 华东师范大学计算机科学技术系2 0 0 7 年硕士毕业论文 约策略，包括数据聚集( 例如，建立数据立方体) 、维规约( 例如，通 过相关分析，去掉不相关的属性) 、数据压缩( 例如，使用诸如最短编 码或小波等编码方案) 和数字归约( 例如，使用聚类或参数模型等较短 的表示“替换”数据) 。 针对六度分隔系统后台数据集的实际情况，本章接下来将主要讨论数据变 换、数据归约和数据清理技术。 华东师范大学计算机科学技术系2 0 0 7 年项士毕业论文 2 2 数据变换及归约 对于小型或中型数据集，一般的数据预处理方法已经足够。但对于大型数据 集

59、，在应用数据挖掘技术以前，需要采取数据变换及归约的方法，在没有牺牲成 果质量的前提下，规范化和减少数据量，使挖掘算法能够在适量的时间和空间里 运算。 L 数据变换 数据变换是指将原始数据转换成适合于数据挖掘的形式，方式有很多种，具 体采用哪种方式，要在挖掘过程中，根据预测的准确率进行调整。 常用的方式有： + ( 1 ) 平滑( S m o o t h i n g ) ：去掉数据中的噪声。主要包括：分箱、聚类和回 归的方法。 ( 2 ) 聚集( C l u s t e r i n g ) ：对数据进行汇总和聚集。例如，可以聚集U s e r 表中月收入，计算年收入等属性。 ( 3 ) 数据概化( G e n e r a l i z a t i o n ) ：使用概念分层，用高层次概念替换低层 次概念。例如，U s e r