您好,欢迎来到爱go旅游网。
搜索
您的当前位置:首页基于用户社交网络的最短距离聚类算法

基于用户社交网络的最短距离聚类算法

来源:爱go旅游网
第33卷第2期 天 津 理 工 大 学 学 报 JoURNAL oF TIANJIN UNIVERSITY OF TECHNoLOGY Vo1.33 No.2 Apr.2017 2017年4月 文章编号:1673—095X(2017)02—0048—05 基于用户社交网络的最短距离聚类算法 王均贤,李文杰 (天津理工大学计算机与通信工程学院天津市智能计算及软件新技术重点实验室,天津300384) 摘要:如何提高大数据环境下推荐系统的推荐效率是一个值得关注的课题.本文提出了一种基于用户社交网络的最 短距离聚类算法.该算法在推荐之前预先对用户进行聚类,降低邻域搜索空间,提高推荐效率.本聚类算法将用户分为 分簇用户和离群簇用户两大类,推荐时以簇为单位输入.离群簇用户可实现对社交网络的简单扩展.最后通过对真实社 交网络的模拟,证明了算法的可行性与有效性. 关键词:大数据;推荐系统;聚类算法;最短距离 中图分类号:TP399 文献标识码:A doi:10.3969/j.issn.1673—095X.2017.002.010 The shortest distance clustering algorithm based on social network WANG Jun—xian.LI Wen-jie (School of Computer and Communication Engineering,Tianjin Key Laboratory of Intelligence Computing and Novel Software Technology,Tianjin University of Technology,Tianjin 300384,China) Abstract ̄How to improve the eficifency of recommendation system in the big data environment is a hot topic.This paper proposes a shortest distance clustering algorithm based on social network.The algorithm can cluster the users before recommendation,in order to reduce the neighborhood search space,and improve the eficifency of recommend.This clustering algorithm divided users into cluster users and outlier cluster users,recommended in cluster unit as input,and outlier cluster users can achieve a simple extension for social network.Finally,the feasibility and effectiveness of the algorithm are proved by the simulation of real social networks. Key words:big data;recommendation system;clustering algorithm;shortest distance 随着网络的发展,海量数据的出现导致了信息 过载的情况ll1,由此产生了推荐系统以满足用户的需 求.推荐系统所依赖的推荐算法,通常需要维护一张 巨大的相似度矩阵表12],需要花费大量的时间来计算 对用户进行聚类,从而对原始数据进行预处理.最典 型社交网络信息是用户之间以用户为节点,用户关 系为边产生的有向社交网络.用户的节点可以存储 用户的一些属性信息,有向边则代表了用户之问的关 注信息.传统的网络聚类方法主要基于链接的稠密 度,如Newman快速算法【9]和Kernighan—Lin算法 1. 本算法将具有相似兴趣的用户分为一簇,簇的数目 相似度,以至于满足不了实际需求.同时用户与物品 的增长导致用户间使用同一物品的概率大大降低, 产生了数据的极端稀疏性【31.针对这些问题,通常做 法是采用分布式计算,利用大数据平台来完成大数 据量的推荐 】.另一种做法是可以在进行推荐之前, 由用户自己定义.同时还有一类是离群簇,由关注量 比较少的欠活跃用户组成,新加入的用户也可以存 对用户或物品进行聚类,降低推荐算法时的邻域搜索 空间,提高推荐效率.目前常见的聚类方式有Kmeans 聚类同,MinHash聚类 ,神经网络[81等. 如今对于一个推荐系统,背后往往已经拥有了 巨大的社交网络信息基础.可以以社交网络为基础 收稿日期:2016-06—28. 入这一类簇中,用于社交网络的扩展.推荐时以簇为 单位进行加载,提高推荐效率. 本文提出了一种新的以边为切入点的基于用户 社交网络的最短距离聚类算法.在对用户进行推荐 之前,利用已有社交网络提前对用户进行聚类处理, 基金项目:国家自然科学基金(51575544);澳门科技发展基金(108/2012/A3). 作者简介:王均贤(1989一通讯作者:李文杰(1975一),男,硕士研究生,E—mail:wan unxianO216@qq.COl'II. ),男,副教授,硕士生导师,E—mail:1wj13579@sina.COB. 王均贤,等:基于用户社交网络的最短距离聚类算法 ・49・ 以减少后续推荐的时间复杂度和空间复杂度.同时 时,把这个节点称为枢纽节点,定义为: (e)={ (m1,e)nO/(m2,e)n (m3,e),…} (3) 考虑到了社交网络的极端数据稀疏性… 21情况,设置 了离群簇,以便适应社交网络的变化. 1算法概述 1,1社交网络模型介绍 在社交网络中,由一个节点向关联节点发起的 有向边代表了节点与节点之间的兴趣关系.如果A 用户关注了B,那么B的兴趣点某种程度上可以代 表A,这种程度随着连接步数的增多而急剧减少.例 如A用户关注了B,B关注了C,则C用户的兴趣点 就不如B能够代表A,但是c仍然存在与A共同的 兴趣点.另外有向边只是单方面的关注关系,A关注 了B,则B的兴趣点一定程度上能代表A,但是A的 兴趣点却不能代表B.从整个社交网络结构来看,节 点的入度能反映出这个节点的受欢迎程度,即所谓 的公众用户,受关注比较多.若有两个节点在同样能 够到达某个公众节点的前提下,所需要的步数越少, 越能体现出这两个节点的相似性,属于同一个簇的 可能性越大. 1,2基于用户社交网络的最短距离聚类算法的基本 定义 假定一个已知的社交网络,转换为一个有向网 络图G={U,E},U是代表用户的节点集合,E为代表 用户关注关系的有向边集合.从节点m到节点n的 有向边可以记为<m,n>,其中m,n∈U.此外,参数k 代表从m到n所需要的步数.在已知网络中,节点人 度大于 的即作为中心节点,选取一个中心节点m, 随机选取的一个节点n,若m能代表n的兴趣点,则 n定义为m的兴趣相似节点,记为 (m,n). a(m,n)={n∈Ul< ,,n>∈E,k</x} (1) 其中n代表到达m节点步数小于 的节点, 为一 个阈值,若步数小于 ,则中心节点某种兴趣点上能 代表n. 根据节点与边的定义与关系,选取的中心节点 m,若有一个节点 到达m的步数小于设定的参数 ,则用户rn一定程度上可以反应用户n的兴趣点, 同样所有到达中心节点m的兴趣相似节点,也能反 映出这些节点的兴趣某个共同点,可以定义为邻居 节点,用来综合归为一簇.邻居节点集合定义为: F(m)={0c(m, 1),ot(m,n2),ot(m,n3),…,ot(m, ),…} (2) 当一个节点到达两个以上的中心节点都小于 其中m ,m:,…,m 表示选取的中心节点,则e即为 枢纽节点,需要预定义一个分组,用来存储枢纽节 点,以便下一次聚类. 还有一种节点是离群簇.由于社交网络的极端 数据稀疏性,这类节点很常见,需要在聚类的过程中 不断对离群节点进行挖掘,找出起其潜在兴趣点.判 断一节点是否离群节点是看这个节点到所有中心节 点的距离是否大于 .首先判断一个节点到某个中心 节点的距离是否大于 : 卢(,n,凡)={n∈Ul< ,m>E E,k</x} (4) 然后看这个节点是否到所有中心节点的距离都 大于 : (p)={ (rn ,P)n/3(m2,P)n (m3,P)… nB(m ̄,P)l (5) 如果是,则为离群节点,如点P.离群节点需要额 外定义一个簇,用来存储这些离群节点,以便以后的 聚类能够进行更深入的挖掘. 1.3基于用户社交网络的最短距离聚类算法的流程 接下来介绍基于社交网络的最短距离聚类算法 的工作流程,包括对节点的遍历与最短距离的分析, 然后分簇.第1步,将所有节点初始化,每个节点未 分簇,同时节点之间的关系用有向边来表示;第2 步,遍历所有节点,找出入度最高的节点作为中心节 点,从中心节点中随机选取P个节点;第3步,遍历 出中心节点之外的所有节点,选出兴趣相似节点,枢 纽节点和离群节点;第4步,随机选取人度最高节 点,重复步骤2对枢纽节点和离群节点进行遍历,扩 展簇,直到枢纽节点全部转换为相应的簇为止.具体 选取的中心节点的方法是从已分簇的簇中分别随机 选取入度最高的节点,扩展的原则是已分簇的节点 不在参与扩展,离群节点可以扩展为节点相应的分 簇,而枢纽节点则可扩展为已分簇节点和离群节点. 具体算法如表1所示. 社交网络最短距离聚类算法的的最终聚类结果 会将所有的节点分为两大类,第一大类是有分簇的 节点,这些节点属于各自自己的簇;第二大类是离群 节点组成的离群簇,这些节点可以用来存储新加入 的用户等等,使社交网络实现了简单的可扩展性. 在聚类算法分簇的过程中,会有一些活跃用户 组成的枢纽节点,这些枢纽节点因为到两种簇以上 的最短距离都小于 ,因此需要重复遍历执行算法, 直到确定相应分簇为止.这些枢纽节点是判断聚类 ——50—— 天津理上大学学报 第33巷 2期 表1 基于用户社交网络的最短距离聚类算法 Tab.1 The shortest distance clustering algorithm based on social network 来进行实验. 本次实验模拟了100个川Jf',的社交网络 ,朋 户编 从1到l00,有向边代表用户之间的关注情 况.其中,边数f1r以自m设定, 为真实的礼交网络 通常是稀疏网络,l大I此,边数通常是比较少的. 2.2实验结果与分析 本义在matlab平 L白‘先模拟了拥有100个节 点的礼交网络.节点之间的有向边表示J}J 之间的 关注关系.图1是边数分别为500,600,700的模拟 输入:给定的邻披矩阼表示的有向社交网络G=lf/,E1.参数 , ,s 输Ⅲ:簇的编号怀签 枢细 点标签h.离群节点标签,,G={(U. E.(r-h.,’)) (1】对 一个 ∈f  。(2) (3) ,/求jfj每个节点的入度 r Ii ii1 f (4) if (, . )> (5) 将大】: 的 点添 Q; 社交网络l矧. (6) (7) //从Qll1随机溃取 个节点 ( ,“.)E(J (8) (9) (10) 将 点添JJI1到q2; 将II,从£ 集合l{|删除; for“ E(J2 (11) (12) (13)将II 添fJ【1到埘嘘 Ip; /,对余下fl'j, ̄fl户节点进行遍历 tbr{ .E£ (14) /l ̄ll断雠个节点刮中心节点的步数t.j s的关系,以及 ,卜1:s的节 数Inlp (15) (16) lll1I)定义为到-{_1|【 节点步数小于 的 点个数; if A (fI1.i)( &&tmp:=l (I7) (I 8) 将桐应的 捕人相应 中;; e1 ̄.e If,v(“ ,i)< &&tl『1p>l (19) (20) 将中H应的 捅人到楸纽集合sII1; else (21) 将卡¨血的IIl椭入到离群节点F一【I. (22)对相J 的T/给与相应的簇的编号“. (23)楸纽 点s怀记为h; (24)离群 点怀i 为,’; 足否完成的标志,在聚类循环时,枢纽节点会不断得 到卡f1啦的分簇, 全部分簇时,聚类结束. 从聚类过程中可以观察¨{,此聚类算法对节点 处理 序不敏感,但是节点一旦在第一次确定簇之 后,就应该把它从下个遍历过程中删除,以防发生重 复遍J 。造成最后分簇不明确.另外,离群簇的设置 使之能够简【丫1.适应礼交网络的扩展,更能反应}}I真 实衬:交网络的情况. 2实验分析 2.1实验数据集 小义 nldtla1)平俞上通过埘真实社交网络的模 拟来进行实验. 为需要确定参数 , ,占的范H爿, 需要分析不l『i】的网络f冬1对参数的影响,真实的社交 网络数据集没法满足这点,【六l此需要模拟社交网络 ((-)700 图1 500、600、700条边时的社交网络结构模型图 Fig.1 Simulation of social network structure of 500。600,700 edges fj均贤,等:J J 川J’・ 交『《IJ络的址 离 炎{’: ・5 l・ 输入 ^ 1\参数, , , . 为节点1'19』 人人 II’I边的惭 直接决定J 、 人 J 参数,I{仃人丁 这个参数的 点 有 能做选 r . J 的分(1i, ‘I= 分忻人瞍与边的天系,以他 确 』J2久人J 参数 .边数fI1 的小同的什交f叫 }} fll 删仃1 川边数的 【冬I 最人人度参数 的火系, 教 的遥f 如 2、 3昕示。 漩久人度参数 图2入度参数与节点数目 Fig.2 Relationship between and number of nodes ^々几八J笪琴数 图3入度参数与最大节点数目 Fig.3 Relationship between y and number of max nodes J。 l()(】个 悄 下, 艾选择J 边数500 的fI 交 . ll1 大人度参数 为5. 銎数F代 步教1'19闽仉. 川 A到川rl l{的 』J:tl圳 离小J lI、』,l{能 一定 度上代 A的I 巡 . 个川 卡¨似. 是, 趣的十日似 度会随行 的增人 世述减少. 此. “1赋】: 合迅的 I,以 他 持III J、t之 I'19卡¨似性.1 点之 的最/. -ii. I11 离一 日 I 边的数I iI1,J J‘曾JJII¨1 减少,同时, 一 制Il rd边 数fII , 址连接父系/f 的刚络 是 ×lf J √ l 勺 啦进上,/f 同边数 ‘j步数 的火系 』『l】 4. 图4不同边数对应的离群节点与枢纽节点个数 Fig.4 The number of outliers nndes and center nodes with different edges 聚炎 的效 足楸 点 f≈斛 i-. 数II 十¨后/f 人,这样利J 续循环聚炎. 此,这I 取离 排 细节点筹值较小时的 =3. 确定 的参数后, 咒确定 - 教 -J#5数,随 机 成 个 络 ,然后与参数・起作为输入,迎j』 离柴炎算法进行聚类.这 选扦_r 500 边 的卞j!拟}f:交I叫络 . 将随机『l,J 络模 进 柴类,聚炎过 『』I 15, 『fl口代表楸纽 ,◇代表 i ̄i巾, -,H ・ .口址 分簇,o代 二类分簇. 52一 图5聚类过程 I ig.5 Fhe process of clustering  -川1人刊f , 、 ,.然 随竹川 交_父系的 f! IJ1.离 』I J J’ il J"以随时转换为新的簇以供后续推 他…. 3 结 论 …J -和lJ J。 J ff:交 的聚炎翰:法,作片J址 摊f 系统 l 数埘进行预处州, 现一个聚类卡JJ 化.这1:、r 拊 数 f1载时i-f以分簇JJl1裁,降低邻 城搜索。 iiiJ, l }ff; 效率. II, 簇结果llI没置r 离肝 t 5 梭.他}f:交网络 仃r一定的扩腱性.然 J 述J J J 』tt 交 络n  ̄-'/_Ilfi离聚类算法, 33 2【JfJ 埘诈法的定义 j流 做丫 休的介 . 通过实 验数 验 _r l’:法的效果. 参 考文 献: ng ̄1 .Zllti igZ K Zh(,ll。1.et_。。II.(1lllhl1.,Ial fiIh 1ing witli(1Imi i【1i1一 lI riS( f1 similal’ih.(1¨1 rilitUIih・ |1 lI}l1H J:. I h、sit-a A:  IlHIl【‘ j M《 (’hani( {lll(i il,4'\pillicalions. !()1().389【(’): 1259一 I264 2 、lltllI X,\、ii (2o111( lit—ha rP【…IIIIII'IllI II_III1 IIIllfff-I iII lnil・i.-blog ̄‘・…'i Ullllllih C∥、laiiagenl(、IIIt —io111111( r£i11(1 ( 『I vl iiI1l1I III(I(:Ml (:( ).2Ol2 Il1II iilldi【ll1“I(:onfl iI・i1t・{ (911.1h iiiiig,(_I1iIlll:I : :.2012:I65一I68. 3 卜1I㈨ g Z.( II I I,|/t-ng I)AI)JlJ iiig;l ’ m、|l 】ll‘(‘hiliql¨es l【1 alh-、iah、ih( p|I rsil>l’fIlI1Ir1ii in I‘IlIlalII}1 l【_、 fiIlel,ing J.、【 、1_r12iii^“(・iit,I1 l}ii II1f ,i111 IIilII/ %sl(q/IS ( r()lS),2004.22(1):1 16一I42. 4; 1 匕。 fI l’技 。卜数瓠‘挖抽日”‘ 、n0 fiJl-';s ̄i『D],成鄙:i6 I1 J 7一 尺 : 2010.。c  ℃. j,lK ILfin  人数 J电l、fi0“f 系统J. 一II2 川 乜几 、 l{I 2015,38(2):I一15. thu’Iigan /1.H ong/1 1. Ig.tillun| I 36 t凡一Meall I‘hisl ̄ i ing iII ‘’rilhln.I.、ppli ̄.1 ̄b.IIislit' .I979.28(1): lO0一l08. I)as S,I)llhll M,(;tilg 1、.1 1 al( llI’ … 、”Ilt-rSOlUlliza— tion: (・al II’ (111Ii111 t・(1llallIlr IiVt、fiI ring(::11 Intel,iIi1一 Jirmal Conll-H Ih"-I f)lJ ¨jh J、x id ・J J.J{ 川n. 、JI,ef・ . (:titill(ill:A(:M,20()7:27 1—280 I/I,II—I Pt.()ll k-】.Il Jill I.T11( t,【1llah(1lati、t fiI i,i Jig rI IlIII— II1( ndati()11 hasi、lj(ill )、1 t‘lustei—iIId(、xing CBII I.Ex1. t ¨ll_、~ilh\ppl ali(ins.2003.25(31:4l 3-423 i. ̄IIIHI1、1 I.I"asl algo ̄’ithn1 t t‘I_『1g(-OlIlilillili| ̄ strII(・III rP iII I1(・IuOI ks.I.J’h、H II lh-vl《 、~l :Shitisit(・ t】 NonliIll!al HII(I Noll Matt( i l)JI、si(:s.20()4,69(6):0661 33一 ()661 33. I LIII(-i‘・hin( IIi、 卜Iill It(ntll() ,K i h"sz.J I)elt ting lhP IJ、Prlap1)il1 alld hit,i LII’‘’hi{‘al(11)1111Iliillih sll’I1( hitf flf.('OIII— lib x iielWOI’k J.、l-w J,,ulIlal l’fl})l1、 ^,2008.1 I(3): l9-44. 、1 H】(Jw A.MⅢf OII M,|;llilllmI,I K f’. 『J.M 川n 『『IPni till(1 anal,,,sis l1I oliIiIll' f itlI I117[%%O1I H( 11 A( M 【(j( ()MM ( …m i… (ill lIlh ⅢI rI、1t tlSll III1 ill 2007. 'lI1 l】 t ,. (:nIiif IIia.t 、:、(:、1,2007:l81 5一l 8l6. i 您,-llIJ盼盼. .J毒 :J1』lJ、t 的 fAJ}f交网 ff}:f l j I.iI‘l 柯l ’ ::}l{,20I 3,36(’i):349—359. … 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- igat.cn 版权所有

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务