余晖落尽暮晚霞,黄昏迟暮远山寻
本站
当前位置:网站首页 > 编程知识 > 正文

结构2内容:用于检测的增量方法 异类网络中的异常相关

xiyangw 2023-10-08 13:59 25 浏览 0 评论

异构网络无处不在。人们喜欢从这样的网络中发现稀有但有意义的对象和模式。无论是高结构相似度还是高内容相似度,相应的对象都可以用于数据分析。然而,结构和内容之间的巨大差异应该引起更多的关注。本文提出了一种异常相关检测方法,称为结构2内容,在结构层次和内容层次上逐步发现异常相关。结构2内容解决了三个重要挑战:(1)我们如何衡量目标对象的结构和内容相似性?(2)如何确定目标对象的代表性特征?(3)如何增加插入新数据或删除过时数据。为了解决这些挑战,structure 2内容应用了四种主要技术:(1)分别使用两个矩阵来存储结构和内容相似性;(2)使用三元组来表示对象之间的紧密程度;(3)将镜像步骤和迭代过程相结合以获得Top-K离群值相关性;(4)仅更新NG 3元组可以帮助增量地插入或删除数据,而不是从一开始就训练所有数据。大量实验表明,本文提出的方法对异常相关检测具有很好的效果。

关键词:离群相关;异构网络;结构层次;内容层次;相似性。

1。介绍

在分析异构信息网络中的多类型对象和多类型关系时,识别稀有、有趣和杰出的对象、模式或子图至少比了解

通讯作者。

1013

通用数据分发或模型。离群值检测作为数据挖掘领域的一个重要分支,可以用来提取与网络中其他方法有显著差异的对象、模式或子图。对于由多个节点和边组成的异构网络,提出了许多识别异常或可疑单顶点和子图上顶点的方法[1-4]。例如,在一个书目网络中,当一个作者的出版物与他的研究领域无关时,他可能是一个独立的局外人。以子网离群点为例,在气候研究中心,如果一个游牧浮标显示的温度下降超过10度,它可能会发生故障或被波涛汹涌的海水撞击。然而,如果几个游牧浮标在短时间内在不同点显示相同的现象,这是可疑的。这意味着这些地区正在发生一些极端天气。

本文提出了一种增量异常相关检测方法,称为结构2内容。该方法的主要思想是分别计算目标对象在结构层次和内容层次上的相似性。我们测量了结构相似性和内容相似性之间的差异,得到了异常值相关性。我们使用三元组来表示两个对象之间的关系。对象可以是目标对象或表示目标对象的特征。两个物体之间的权重是它们之间的接近程度。我们还提出了一个镜像步骤来获得两个对象之间的间接E?ECT。此外,由于参数加载方法可能会导致可用性问题,因此我们提出了一个称为覆盖率的概念,以获得足够的特征来表示目标对象,而不是使用太多的参数。最后,我们对结构级别和内容级别之间离群值相关性的差异进行了排名。在插入一些新数据或删除过时数据时,还说明了增量过程。此过程只更新部分数据,而不是从一开始就培训所有数据。我们在Aminer和Yahoo上进行了几次实验!用于验证结构2内容模型的E?有效性的电影。实验结果表明,结构内容物能有效地发现异常相关。

在异构网络中,检测异常值相关性而不仅仅是识别单个异常值是非常重要的。从结构或内容的角度来看,每个对象都可能是正常的。然而,检测单个异常值可能会忽略对象之间的相关性。它们的相似性也可以从不同的角度存在巨大的差异,例如结构级别和内容级别。此外,异类网络中的离群值相关性与同种网络中的离群值相关性也不同。在异构网络中,尽管异常相关的两个对象可能属于同一类型,但在整个计算过程中,我们应该考虑多类型对象和多类型关系。然而,在齐次网络中,离群相关中的两个对象不存在多类型关系,它们可能仅基于统计信息及其值进行关联。

本文的贡献总结如下:

(1)深入研究了异构网络的结构与内容之间的差异,提出了一种检测异构网络异常相关的增量方法。

(2)三元组用于表示多类型对象及其对应关系。

(3)将镜像步骤与迭代计算过程相结合,得到目标对象在内容层次上的特征表示。

(4)插入和删除过程演示了如何逐步获得异常关联。

(5)对两个真实数据集进行的大量实验证明了我们提出的方法的有效性。

本文的其余部分组织如下。我们将在第二节讨论相关工作。2。第3节介绍了本文中使用的定义和概念。我们提出的结构内容模型的总体框架也在第2节中进行了说明。三。第四节讨论了如何使用三元组和镜像步骤来度量结构层次上的相似性。第5节描述了如何使用3元组和迭代过程来度量内容级别的相似性。第6节描述了如何识别异常值相关性,以及如何插入新数据和删除过时数据。我们进行了几项综合实验,以评估我们提出的方法在秒内的效率和效率。7.提供实验设置、性能指标、数据集和结果。第8节得出结论。第9节讨论了未来的工作。

2。相关工作

异常值检测方法已经研究了很长时间。大多数传统方法都用于同构网络,包括基于统计的[1,5]、基于邻近度的[6,7]、基于聚类的[8–10]、基于分类的[11,12]和集合异常值的[13]。Gao等人[14]采用有标号和无标号的数据,利用一种新的目标函数进行半监督异常检测。Rasheed和Alhajj[15]提出了一种基于时间序列周期性的su±x三叉树算法的异常值模式检测框架。他们处理的对象属于同一类型。因此,它们提出的方法只能用于同构信息网络。

近年来,随着异构网络的出现,整个网络中存在着多种类型的对象和多种类型的关系。同构网络的原始方法不适用于异构网络。异类网络的离群值检测方法有单离群值和子图离群值两种。Gupta等人[16]提出了一个称为社区分布异常(cdoutliers)的新概念,该概念使用非负矩阵分解来检测社区分布不遵循其他流行社区分布模式的对象。他们还提取了异类网络中单顶点形式的异常值。庄等人[17]提出了一种基于查询的异构网络子网异常检测方法。他们定义了子网络相似性的概念,并根据异常值对子网络进行排序。异常值用子图表示。

此外,许多研究人员还深入研究了一些增量异常检测方法,以降低时间复杂性和空间复杂性。Pokrajac等人[18]开发了一种增量异常检测方法。他们提出了一个称为基于连接的异常因子(cof)的概念,并说明了如何在每次插入或删除时更新cof。Ju和Li[19]提出了一种增量方法IODM(增量异常检测模型)。它们在数据集中挖掘关联规则,并增量更新关联规则仓库(ARW),以检测异常事务。增量过程只更新部分数据,而不是从一开始就训练所有数据,这样可以节省大量时间和空间。

三。问题定义

我们从一些形式化的问题定义入手,提出了一些新的概念。接下来,我们将概括结构2内容的总体框架。主要的方法和完整的理论是专门针对章。4—6。为了陈述完整的理论,需要以下概念。

定义1(异构信息网络[20])。给出一个有向图G?_V;E;;';A;R_。V是一组节点,E是一组边。和是两个实体类型映射函数。_v_2 a表示每个实体v对应于a中的特定实体类型。e_2 r表示每个边缘e对应于属于r的特定关系。当节点类型jaj>1或边缘类型jrj>1时,网络被视为异构信息网络,否则,它是一个同质信息网络。

在现实世界中,有许多异构的信息网络实例。例如,在书目网络中,有四种类型的节点:论文、作者、术语和地点,以及表示出版和出版、写作和写作、引用和引用关系的多个边。在电影网络中,有四种类型的节点:电影、演员、类型和语言,以及表示它们之间关系的边缘。

定义2(上一个节点和下一个节点)。给出了一个无向图g?_v;e_。A;B 2 V.A和B连接在G中,即_A;B_2 E。访问节点A,未访问节点B。然后,a被认为是b的先验节点(a可以用^ b_表示,b被称为a(b可以用^表示)。

定义3(异常相关)。假设一个异构网络中有n个对象作为输入,那么结构层和内容层中任意两个对象的相似性分别用si、j和ci、j表示。计算si;j和ci;j之间的差异。找出si;j和ci;j之间差异的顶部k值。与顶部k差异相对应的对象相关性_i;j_被认为是异常相关性。

与同构网络中的异常相关检测相比,异类网络中的异常相关检测是不同的。在齐次网络中,可能只有基于两个对象之间的统计信息才能得到离群相关。离群值相关性之间不存在结构信息或内容信息。然而,在异构网络中,存在着多类型对象和多类型关系,使得异常相关检测更加复杂。

定义4(有效功能)。当一个特征X被赋予一个术语权重值时,该特征X被称为一个有效特征,否则,它是一个无效特征。

定义5(覆盖率)。有效特性占特性总数的百分比被定义为覆盖率,用cr表示。

图1显示了我们提议的结构2内容的框架。我们从两个方面计算了异构信息网络中对象之间的相似性。

图1。结构2内容模型的总体框架。

视角。第一个是物体之间结构层次的相似性,如图1左侧所示。第二个是对象之间内容层次的相似性,如图1右侧所示。然后,我们得到矩阵s和c之间的巨大差异,以获得顶部k离群值相关性。

4。结构层组件

在本节中,我们从结构的角度计算两个对象之间的相似性。此外,structure2content模型的结构级组件是一个增量过程。当新数据出现时,不需要从头开始计算,大大降低了时间复杂度。我们以秒为单位呈现组合步骤。4.1和镜子步进分别为4.2。三元组用于计算异构网络中任意两个对象之间的结构关系。

4.1. 组合步骤

给出了一个由多类型对象组成的异构网络G及其对应关系。在离群值检测领域,以前研究过从网络结构或网络内容的角度检测离群值。然而,从网络结构和内容信息之间的差异的角度来检测异常值相关性的研究却很少。此外,在插入新数据或删除过时数据时,传统的离群值检测方法通常从一开始就计算对象的离群值。因此,我们首先提出了一种增量异常相关检测方法来计算物体在结构层次上的相似性。

众所周知,在异构网络中存在多类型的对象。以某一特定类型的对象作为目标对象,用于计算接近度。目标对象以多个记录的形式表示。例如,在书目网络中,作者可以被视为目标对象。这些记录以合著者的形式表示。在电影网络中,演员可以被视为目标对象。这些记录以联合主演的形式呈现。结构层的最终相似性存储在矩阵S中,如下所示。

2s13 2s12;11 s12;22 s21;;nn 3S

SNN?664S..27775?4…;1…;2 SN…;N 56S.666SS777

序号;序号;

为了逐步获得离群值相关性,异类网络中的目标对象以3元组的形式存储,以_oi;eij;oj_表示。oi和oj是目标对象,eij表示oi和oj之间的紧密程度。

表1。十个记录的例子,包括几个作者。

身份证件

合著者ID

身份证件

合著者ID

1

A1;A2;A3;A4

6

A2;A8;A9

2

A1;A2;A4;A5

7

a2;a4;a5;a10

3

A4;A5;A6;A7

8

A3;A6;A11

4

A1;A2;A4;A6

9

A1;A2;A3;A4

5

A2;A8

10

A1;A3;A6;A7

表2.从表1生成的所有3个元组。

身份证件

p1 p2 p3 p4 p5 p6 p7 p8 p9 p10

三项式

f1,1,2g f1,1,2g f4,1,5g f1,1,2g f2,1,8g f2,1,8g f2,1,4g f3,1,6g f1,1,2g f1,1,3g f1,1,3g f1,1,4g f4,1,6g f1,1,4g f2,1,9g f2,1,5g f3,1,11g f1,1,3g f1,1,6g f1,1,4g f1,1,5g f4,1,7g f1,1,6g f8,1,9g f2,1,10g f6,1,11g f1,1,4g f1,1,7g f2,1,3g f2,1,4g f5,1,6g f2,1,4g f4,1,5g f2,1,3g f3,1,6G F 2,1,4g F 2,1,5g F 5,1,7g F 2,1,6g F 4,1,10g F 2,1,4g F 3,1,7g

3,1,4 4,1,5 6,1,7 4,1,6 5,1,10 3,1,4 6,1,7

F G F G F G F G F G F G F G F G G F G

结构层oi与oj的相似性包括两部分:组合步和镜像步,用式(1)计算如下:我oJ

soi;oj?sdoi;oj_smoi;oj;_1_

其中sdo;是oi和oj之间的直接相似性。例如,表1中有10条记录表示10个纸张ID和相应的作者ID。我们使用三元组来表示两个作者之间的关系,如表2所示。根据直接合著关系,将3个元组组合起来(如表3所示),然后我oJ

使用公式(2)计算sdo;。我oJ

X

伊利;J

sdoi;oj?sdoj;oi?n;_2_subject to i<j;

其中n是数据集中包含oi或oj的记录总数。式(2)服从一个条件,即i应小于j,仅考虑直接相似性不够,我们将在下一节讨论镜像步骤,该步骤用于计算间接相似性和增量过程。

4.2. 镜子台阶

在这一部分中,我们提出了一种称为镜像步骤的方法来计算两个对象之间的间接相似性,然后逐步获得异常值。在表3中得到3个元组后,镜像3个元组与原来的相反

表3.合并后的所有3元组。

f1,0.25,2g f1,0.5,3g f1,0.57,4g f1,0.14,5g f1,0.29,6g f1,0.17,7g

F2,0.22,3G

F 2,0.625,4g F 2,0.25,5g F 2,0.1,6g F 2,0.29,8g F 2,0.14,9g F 2,0.14,10g

f3,0.25,4g f4,0.5,5g f5,0.17,6g f3,0.33,6g f4,0.29,6g f5,0.25,7g

f3,0.2,7g f4,0.14,7g f5,0.33,10g f3,0.25,11g f4,0.17,10g

F6,0.5,7g F8,0.5,9g F6,0.25,11g

表4.表3的镜像3元组。

F2,0.25,1g f3,0.5,1g f4,0.57,1g f5,0.14,1g f6,0.29,1g f7,0.17,1g

F3.0.22,2g

f4,0.625,2g f5,0.25,2g f6,0.1,2g f8,0.29,2g f9,0.14,2g

10,0.14,2

f4,0.25,3g f5,0.5,4g f6,0.17,5g f6,0,33,3g f6,0.29,4g f7,0.25,5g

f7,0.2,3g f7,0.14,4g f10,0.33,5g f11,0.25,3g f10,0.17,4g

F7,0.5,6g F9,0.5,8g F11,0.25,6g

F G型

3元组。例如,表3中的3元组f1,0.25,2g成为表4中的3元组f1,0.25,1g。假设我们想测量OA和O之间的紧密度,只提取包含作者的记录,由于忽略了间接的合作关系,因此会造成信息的过度丢失。例如,A和A与A;A;A和A合作几篇论文,A和A仅与A合作一篇论文。当然,A和A之间的紧密度高于A和A之间的紧密度。使用式(3)计算镜像步骤中两个对象之间的间接相似性:3 63 6 3 6 1247 113 11 63 6 3 11

T

smoi;oj?smoj;oi?xei;kek;j;_3_

K 1

其中t是具有间接合作作者关系的作者数。它是smo;中3元组数量的一半。例如,使用表3和表4中的3个元组计算OA和OIN结构级别之间的相似性,如下所示。此外,算法1还描述了计算结构层中对象之间相关性的算法。我oJ3 6

SO3;O6?SDO3;O6_Smo3;O6

?0:33_e3;1e1;6_e3;2e2;6_e3;4e4;6_e3;7e7;6_e3;11e11:6_

?0:33_0:5 0:29_0:22 0:1_0:25 0:29_0:2 0:5_0:25 0:25_0:732:

0:732:

5。内容级别组件

仅考虑异构网络上的链路结构是不准确的,也不全面的。在这一部分中,我们提出了一种迭代方法,将三元组结合起来计算内容层中对象之间的紧密度。在ContentLevel组件中,一些其他类型的对象用作表示目标对象的特征。例如,在书目网络中,关键词可以看作是作者的特征。在电影网络中,体裁可以看作是演员的特征。因此,内容级别中对象之间的紧密度存储在矩阵C中,如下所示:


CNN?62646CCC…N1277735?62664CC12…;;111 CC21…;;222 CCN12…;;NNN 57377;C

中国;中国;

其中,ci;j表示对象oi和oj在内容级别上的相似性。然后,我们演示如何迭代计算ci;j。与矩阵S中的si;j相似,特征及其对应关系用3个元组表示(以_ti;rij;tj_表示,如表5所示。在书目网络中,ti和tj是表示目标对象特征的对象,rij是ti和tj之间的紧密度。表5中列出了所有3个元组。还需要镜像步骤来获得任意两个之间的最终紧密度。

表5.10个纸张ID和相应关键字的示例。

身份证件

关键词

身份证件

关键词

1

A;B;C;H

6

G;I;K;L

2

C;D;E

7

C;F;G;I

3

A;C;F;G

8

C;D;E;I;J

4

C;D;I;J

9

A;C;D

5

G;我

10

A;B;D;E

表6.从表5生成的所有3个元组。

身份证件

p1 p2 p3 p4 p5 p6 p7 p8 p9 p10

三项式

FA,1,BG-FC,1,DG-FA,1,CG-FC,1,DG-FA,1,GG-FG,1,IG-FC,1,FG-FC,1,DG-FA,1,CG-FA,1,BG-FA,1,CG-FC,1,EG-FA,1,FG-FC,1,IG-FA,1,IG-FA,1,BG-FC,1,GG-FC,1,EG-FA,1,DG-FA,1,CG-FA,1,CG-FC,1,LG-FC,1,1,1,ig-FC,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ig-fc,1,dg-fa,1,eg-fb,1,cg-fc,1,fg-fd,1,ig-fi,1,kg-ff,1,ggfc、1、jg fb、1、dg

FB,1,Hg

fc,1,gg fd,1,jg

FI、1、LG FF、1、IG FD、1、EG

FB,1,Eg

FC,1,Hg

FF、1、GG FI、1、JG

fk,1,lg fg,1,ig fd,1,ig fd,1,jg fe,1,ig fe,1jg fi,1,jg

FD,1,Eg

特征。假设作者ap发表了论文p1和p2,用式(4)计算了与ap直接相关的任何关键字q的加权项。

WPQ?N_P_D_PQ_Log_N_S;_4_K磷磷Q1

其中n_p_是作者ap发表的论文数。d_pq_是美联社发表论文中出现的关键词Q数。因此,美联社发表的论文中出现的关键词越多,就越明显地体现在美联社的术语权重中。k_p_是作者ap发布的关键字总数。ns是网络中的论文总数。p_q_是包括关键字p_q_在内的论文数。也就是说,如果一个关键字在收藏的许多论文中非常频繁,它就不被认为是这类论文的特别代表。例如,“关键字\数据挖掘”是一个广泛的研究领域。如果一位作者发表了一篇带有这个关键词的论文,我们可能不知道这篇论文涉及到什么研究领域。一旦关键词变得更为特殊,如时间异常检测、异常相关性检测等,特征在术语权重中就可以更具代表性。因此,


WPC?2对数6 2

710_?0:067:1

使用术语加权值指定的特征称为有效特征。直接与目标对象相关的功能将添加到有效的功能集。仅应用与目标对象直接相关的属性是不够的。与目标对象有间接关联的特性也需要使用术语权重进行分配。在直接获得与作者相关的关键词的词条权重后,我们找到有效特征的子代节点,并用词条权重值分配无效特征。然后,将无效的特性添加到有效的特性集,直到CR达到80%。当cr达到80%时,我们相信这些特征可以用来计算内容级别的相似性。由于图中可能包含圆,因此可以使用辅助数组标记每个顶点,以防止图遍历算法出现在循环中。迭代计算过程如下:

wpq?wp^q rq^q;_5_

其中,rq^q是节点q与其前一个节点^q之间的紧密度,如上所述。wp^q是目标节点ap的^q术语权重。当所有目标对象的覆盖率满足要求时,可以利用余弦相似性计算内容层次的相似性,并将其存储在上面的矩阵C中。算法2描述了计算内容级相关性的算法,如下所示。

6。用于检测离群值相关性的结构2内容模型

在本节中,我们将介绍如何使用structure2content模型检测异常关联(第6.1)。第6.2节和第6.3节描述了当新数据插入数据集中时如何更新现有数据,以及如何废弃某些旧数据。

6.1. 异常相关检测过程

根据第二节的描述。结构层次和内容层次的相似性分别存储在矩阵S和矩阵C中。然后计算S和C的Frobenius范数,即JJSJJF和JJCJJF。jjjf是矩阵的frobenius范数:jj jjf pms_。在S和C具有相同数量级的条件下,结构层次的相似性和内容层次的相似性具有可比性。因此,我们使S和C的Frobenius规范彼此相同。首先,将jjsjjf除以jjjjf得到一个参数。然后将矩阵C中的每个元素乘以参数,使jjsjjf与jjjjf相同。矩阵mos用于存储s c的绝对值,其_i;j_项是每个有序相关性_i;j_的s i;j c i;j的绝对值。每个对象相关性之间的差异存储在mos中,我们可以获得两个目标对象在结构级别和内容级别之间的最大差异。mos中的top-k值意味着两个目标对象在结构和内容之间具有最大差异。在整个异构网络中,相应的对象相关性被视为离群值相关性。γn21= 2

6.2. 插入

在结构2内容模型的插入过程中,在将一系列新记录插入到原始数据集中之后,需要同时更新矩阵S和矩阵C。假设我们插入一组记录,包括多类型对象和相应的关系,插入的目标对象也用三元组表示。整个插入过程包括两个部分:(1)插入新的对象相关性;(2)更新现有的结构级和内容级的相似性。在插入新的对象关联时,上面描述了计算过程。如果插入的对象关联已经存在于原始数据集中,我们首先使用新的对象关联计算结构级别的相似性。插入的目标对象用三元组表示,我们得到所有对象相关性的最终表示。增量部分s

INCO;采用式(1)计算。例如,插入的记录是fa;a;ag。新记录的对象相关性是fa;ag,fa;ag和fa;ag。a a和a之间的直接相似性(用s incdo;_表示)为1=1/40:143。包括aa和ais 7在内的记录数。e白炽灯输入量等于1=7?0:143。使用镜像步骤的间接相似性(用s表示我oJ1361336163 6 我oJ7 3 6 31 16

incmo;_是e inc的e incmultiplicated,等于1=1/4 0:02。那么,增量部分s inco;等于s incdo;加上s incmo;。结构水平的最终相似性为我oJ31 1649 3o6 3o6 3o6

incoplus所以,也就是说,so?0:732_0:143_0:02?0:877。3o6 3o63o6

6.3. 删除

在实际应用中,除了插入新记录外,还需要删除一些过时的数据对象。当我们删除这些过时的记录时,需要消除合并步骤和镜像步骤带来的相似性。例如,我们删除了表1中的一条记录,比如p。应删除表2中的第三列,并更新包括a;a;a a和a a的所有3个元组,而不是重新计算数据集中的所有数据。同样,在计算内容级别的相似度时,特征之间的相似度计算方法与上面相同。目标对象之间的相似性可以迭代获得。3456 7

7。实验和结果

正如我们所知,由于缺乏基本事实,评估异常值一直是一个具有挑战性的问题。在这一节中,我们定义了一个称为pout的异常值度量,用于评估异类网络中的异常值相关性(第7.1)。精度和召回也被用作性能指标(第7.1)。然后,两个数据集aminer和yahoo!电影用于验证拟议结构2内容的有效性(第7.2)。本文的其余部分进行了几项实验,以验证在异构网络中挖掘异常值相关性(sec)时,计算结构级别和内容级别之间的巨大差异是否适用。7.3)。

7.1. 性能指标

为了检验我们提出的异常相关检测方法的质量,设计了一种新的性能指标,即pout。pout可以测量错误标记或丢失的对象关联数。\“标记错误”表示对象相关性为正常数据,但标记为异常相关性。\“缺少”意味着对象相关性应该是离群相关,但它不存在于Top-K离群相关集中。错误标记的离群值相关性的数量用w表示。离群值检测过程中丢失的离群值相关性的数量用m表示。outcorr是数据集中手动注释的总离群值相关性。相应地,我们使用等式(6)计算出:pout?jw_m j 100%:_6_

2 奥科尔

与另一种流行的评估度量(称为准确性)相反,pout使用了两种相反的情况:真-负和假-正,来测试在检测过程中是否识别了所有可能的异常值相关性。另外两个常见的指标,精度和召回,也适用于重新评估我们提出的检测模型的可用性[21]。异常值相关性检测的精度是被指定为Top-K异常值相关性的对象相关性的分数,它衡量了拒绝正常对象相关性的效果。回忆是由手动注释数据分配的对象相关性的分数,它测量了在所有异常相关性结束时的表现。因此,精度和召回使用公式计算。(7)和(8)如下:精度为1/4 J J J WJ 100%;_7_

科尔德

科尔德

科尔德

召回1/4 J J WJ 100%8_

奥科尔

其中corrd是Top-K离群值相关性中的一组对象相关性。outcorr是数据集中手动注释的总离群值相关性。f-measure[22]作为精度和召回的调和平均值,也用于测量我们方法的性能。用式(9)计算:

F测度γ2_精度_召回γ9γ1 精确召回

其中是重新考虑精确性和召回的相对重要性的权重。显然,如果大于1,那么召回值比精度值更重要。在本文中,被赋予一个常数1。

7.2. 数据集集合

我们使用两个真实的数据集进行实验:Aminer[23]和Yahoo!电影[24]。

氨基。我们从aminer生成数据,aminer是一个书目异构信息网络。它主要由三部分组成,分别是阿明的作者、阿明的论文作者和阿明的合著者。它拥有1712433位作者和2092356篇论文,涵盖计算机科学的不同领域。有四种类型的节点:论文、作者、地点和术语,以及构建整个异构信息网络的几种边缘。为了更准确地检测异常值,对原始数据集进行了补充。使用爬虫[25]提取每篇论文的关键字(用k表示),并将其添加到aminer-paper.txt中每个记录的末尾。在每个数据集中有100个异常值关联被手动注释。

雅虎!电影。雅虎!电影作为分级和分类数据集的一部分,可以应用于异构信息网络中。这个数据集包括六个方面的信息,包括电影、演员、电影分级等。多类型顶点及其之间的多类型关系可用于分类、聚类或检测异常值。评级信息可用于预测或推荐系统。我们选择部分数据,包括` lm标题、演员和类型进行实验,并添加100个对象相关性作为异常相关性。

7.3. 结果

在本节中,我们进行了实验,以检验我们提出的结构内容的有效性和效率。我们进行了第一次实验,以证明我们提出的方法的性能。我们提取数据集中不同数量的对象来观察pout、precision、recall和f-measure。图2和图3显示了随着对象数量的增加,两个数据集上的结果。由于我们在图2中选择了前100个值和相应的对象相关性作为离群值相关性,因此jcor rdj在这种情况下等于joutcorrj,这使得精度与

(a)(b)

图2。aminer和yahoo!上结构2内容的pout和f-measure!电影。(选择前100个对象相关性作为离群值相关性)。

(a)(b)

图3。Aminer和Yahoo!上结构2内容的pout、precision、recall和f-measure!电影。(选择前50个对象相关性作为离群值相关性)。

回忆。另外,pout与精度之和为1。因此,我们只在图2中提供pout和f-measure。在图3中,我们选择前50个值和相应的对象相关性。图3中的召回低于图2中的召回,因为手动标注的离群值相关性数量与检测到的离群值相关性(即图3中的joutcorrj?2jcorrdj)不同。aminer中的功能数量高于yahoo!中的功能数量。电影,这可能导致更高的精度在aminer。同时,可能需要较长的时间才能在胺液中获得充分的特性。

在第二个实验中,我们验证了我们提出的算法的可扩展性。在Aminer和Yahoo!电影数据集,我们将对象数量从1000增加到4000,然后观察运行时间。图4显示,随着数据量的线性增长,执行时间几乎是线性增长,而不是指数增长。然后,我们将处理器的数量从2更改为8,然后观察运行时间。图5表明,随着处理器数量的增加,执行时间大大缩短,这意味着我们提出的方法可以执行并行计算。

在第三个实验中,我们使用三个基线算法(cdoutliers[16]、基于查询的[17]、abcoutliers[26])进行了比较实验。CDoutlier基于联合非负矩阵分解发现了所有对象类型的流行社区分布模式。cdoutlier组作者基于他们的研究区域分布。也就是说,它只考虑网络中的内容信息。根据用户输入的查询,基于查询的异常值检测。在整个过程中,它考虑的结构信息多于内容信息。Abcoutliers计算所有匹配的群组结果。它不如基于查询的算法有效。图6中的曲线表明

图4。在aminer和yahoo!上不同数据数量条件下的运行时间比较电影数据集。(选择前100个对象相关性作为离群值相关性)。

图5。在aminer和yahoo!上不同处理器数量条件下的运行时间比较。电影数据集。(选择前100个对象相关性作为离群值相关性)。

(a)(b)

图6。Aminer和Yahoo!四种异常值检测方法的性能比较电影。

structure2内容的性能优于cdoutlier、query-based和abcoutlier。

在第四个实验中,我们验证了该方法的有效性。从图7的曲线可以看出,结构2内容的时间复杂度比其他基线算法要低得多。此外,当我们插入新数据或删除过时数据时,我们的增量方法不需要从头计算相似性。它可以大大降低时间复杂度和空间复杂度。

在第五个实验中,我们提供了一个案例研究来说明什么样的对象相关性应该被视为异常相关性。我们根据数据集的格式对数据进行注释。例如,在aminer中,我们添加了'fty author

(a)(b)

图7。我们建议的结构内容和三个基线算法的运行时间,两个数据集上的对象数不同。

表7.Aminer数据集异常关联的案例研究。

论文编号

作者

关键词

1

A1,A2

k1、k2、k3、k4、k5

2

A1,A2

K6、K7、K8、K9、K10

3

1

k1、k2、k3、k4、k5

4

2

K6、K7、K8、K9、K10

5

A3,A4

K11、K12、K13、K14、K15

6

A5,A6

K11、K12、K13、K14、K15

具有结构相似性但几乎没有内容相似性的关联,并添加另一个具有内容相似性但几乎没有结构相似性的作者关联。在前一个案例中,两位作者是多篇论文的共同作者,但他们的研究领域完全不同。在后一种情况下,两位作者的研究领域几乎相同,但他们从不在论文上合作。基于以上两种情况,我们在aminer中注释数据。表7列出了两种异常值相关性。例如,aa和aa被认为是离群关联,因为它们在两篇论文上协作,但它们的研究领域完全不同。此外,a(a_)和a(a_)被视为离群关联,因为它们的研究领域相同,但以前从未合作过。我们可以互相推荐,看看他们能否进行学术交流。1 2 3 45 6

8。结论

In this paper, we propose an incremental outlier correlation detection method for heterogeneous information networks based on 3-tuples and structure-content difference. The Structure2Content model includes two parts: structure-level and content-level. In these two parts, the 3-tuples and the mirror step are used to measure the closeness degree between target objects. An iterative process and the coverage rate are combined to get su±cient features to represent the target objects in contentlevel. The insertion and deletion process demonstrates that our proposed method does not need to train the data from the beginning when inserting new data or deleting obsoleted data. In addition, using 3-tuples to store the target objects and the corresponding relations can save more space than using the adjacent matrix. Experimental results show that our proposed outlier detection method, Structure2Content, can incrementally discover outlier correlations in heterogeneous information networks.

9. Future Work

Future work on highlighting the heterogeneity during the calculating process is needed. For example, it would be interesting to use 3-tuples to represent the relations between di?erent types of objects. Also, we plan to detect outliers and outlier correlations simultaneously. Then, we can carry on comprehensive analysis about single outliers and outlier correlations. And we should think about how to deal with new objects with little information. The work on development of distributed version of the incremental outlier detection algorithm is also needed.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under grant No. 60903098, the Project of Jilin Provincial Industrial Technology Research and Development (JF2012c016-2), and Graduate Innovation Fund of Jilin University (2016183, 2016184).

References

1. F. Angiulli and F. Fassetti, Towards generalizing the uniˉcation with statistical outliers: The gradient outlier factor measure, ACM Trans. Knowl. Discov. Data 10(3) (2016), Article ID: 27.

2. F. Angiulli, F. Fassetti, L. Palopoli and G. Manco, Outlying property detection withnumerical attributes, Data Mining Knowl. Discov. (2013) 1–30.

3. C. C. Aggarwal and S. Sathe, Theoretical foundations and algorithms for outlierensemblesk, ACM SIGKDD Expl. Newslett. 17(1) (2015) 24–47.

4. F. Dufrenois and J. C. Noyer, One class proximal support vector machines, Pattern Recognition 52 (2016) 96–112.

5. F. Chen, C. T. Lu and A. P. Boedihardjo, GLS-SOD: A generalized local statisticalapproach for spatial outlier detection, in Proc. 16th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2010.

6. G. H. Orair, C. H. C. Teixeira, W. Meira Jr., Y. Wang and S. Parthasarathy, Distancebased outlier detection: Consolidation and renewed bearing, in Proc. VLDB Endowment 3(1–2) 2010.

7. R. Gupta and K. Pandey, Density based outlier detection technique, Adv. Intell. Syst. Comput. 433 (2016) 51–58.

8. T. Zhang, R. Ramakrishnan and M. Livny, BIRCH: An e±cient data clustering methodfor very large databases, in ACM SIGMOD Record (ACM, 1996).

9. S. Guha, R. Rastogi and K. Shim, CURE: An e±cient clustering algorithm for largedatabases, in ACM SIGMOD Record (ACM, 1998).

10. G. Karypis, E. H. Han and V. Kumar, Chameleon: Hierarchical clustering using dynamicmodeling, Computer 32(8) (1999) 68–75.

11. T. B. Wu, Y. Cheng, Z. K. Hu, W. P. Xie and Y. L. Liu, A new PLS and bayesianclassiˉcation based online outlier detection method, in Proc. 3rd Int. Conf. Advanced Design and Manufacturing Engineering, 2013.

12. N. Koochakzadeh, K. Kianmehr, J. Jida, I. Lee, R. Alhajj and J. Rokne, Semi-superviseddynamic classiˉcation for intrusion detection, Int. J. Softw. Eng. Knowl. Eng. 20(2) (2010) 139–154.

13. I. S. Sitanggang and D. A. M. Baehaki, Global and collective outliers detection on hotspotdata as forest ˉres indicator in Riau Province, Indonesia, in Proc. 2nd IEEE Int. Conf. Spatial Data Mining and Geographical Knowledge Services, 2015, pp. 66–70.

14. J. Gao, H. B. Cheng and P. N. Tan, Semi-supervised outlier detection, in Proc. 2006 ACM Symp. Applied Computing, 2006, pp. 635–636.

15. F. Rasheed and R. Alhajj, A framework for periodic outlier pattern detection in timeseries sequences, IEEE Trans. Cybernetics 44(5) (2014) 569–582.

16.

M. Gupta, J. Gao, C. Aggarwal and J. Han, Community distribution outlier detection inheterogeneous information networks, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2013, pp. 557–573.

17. H. Zhuang, J. Zhang, G. Brova, J. Tang, H. Cam, X. Yan and J. Han, Mining query-basedsubnetwork outliers in heterogeneous information networks, IEEE Int. Conf. Data Mining, 2014, pp. 1127–1132.

18. D. Pokrajac, N. Reljin, N. Pejcic and A. Lazarevic, Incremental connectivity-based outlierfactor algorithm, in Proc. Int. Conf. Visions of Computer Science BCS International Academic Conference, 2008, pp. 211–224.

19. C. H. Ju and Y. L. Li, An incremental outlier detection model for transactions datastreams, J. Inf. Comput. Sci. 10(1) (2013) 49–59.

20. Y. Sun, J. Han, X. Yan, P. S. Yu and T. Wu, PathSim: Meta path-based top-k similaritysearch in heterogeneous information networks, in VLDB'11, 2011, pp. 992–1003.

21. B. Liu, Web Data Mining: Exploring Hyperlinks, Contents and Usage Data, 2nd edn. (Springer, Berlin, 2011).

22. W. B. Croft, D. Metzler and T. Strohman, Search Engines: Information Retrieval in Practice (Addison-Wesley, 2009).

23. J. Tang, J. Zhang, L. M. Yao, J. Z. Li, L. Zhang and Z. Su, Arnetminer: Extraction andmining of academic social networks, in Proc. 14th ACM SIGKDD Int. Conf. Knowl. Discovery and Data Mining, 2008, pp. 990–998.

24. Yahoo! webscope program, http://webscope.sandbox.yahoo.com. Accessed: 28/01/2016.

25. T. Peng and L. Liu, Focused crawling enhanced by CBP-SLC, Knowl.-Based Syst. 51 (2013) 15–26.

26. M. Gupta, J. Gao, X. F. Yan, H. Cam and J. W. Han, On detecting association-basedclique outliers in heterogeneous information networks, Advances in Social Networks Analysis and Mining, 2013, pp. 108–115.

相关推荐

排序算法--归并排序_归并排序例题讲解

原理如图所示(先分割再合并):归并排序代码工作原理:1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列2、设定两个指针,最初位置分别为两个已经排序序列的起始位置3、比较两个指针所...

八大排序算法-归并排序_归并排序 算法

算法思想归并排序分为三个步骤:1.分解:将数列分解成n个子数列。(如果是将数列分成2个子数列则为2路归并)2.治理:对每个子数列进行排序操作3.合并:将两个排好序的子数列进行合并生成新的数列算法实现P...

高级排序之归并排序、希尔排序_希尔排序和归并排序区别

前言继上次排序算法简单排序算法之冒泡、插入和选择排序-Java实现版后,本文学习高级排序算法——归并排序、希尔排序,快速排序将在后续更新。本文实现代码调用方法,部分来自前一个文章:简单排序算法之冒泡、...

Excel办公应用:按合并单元格排序的三大方法

1.按姓名对科目排序重点:在"C2"中输入公式=IF(A2<>"",1,C1+1),然后下拉填充。2.按姓名添加连续序号(方法一)重点:选择"A2:A11"单元格区域,在编辑栏中输入公...

快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强的排序算法

知乎上有一个问题是这样的:堆排序是渐进最优的比较排序算法,达到了O(nlgn)这一下界,而快排有一定的可能性会产生最坏划分,时间复杂度可能为O(n^2),那为什么快排在实际使用中通常优于堆排序?昨天刚...

归并排序思路图解 #归并排序_归并排序百度百科

排序算法1.图解。OK,让它排一下。看好了,要开始排了。能看出来像递归吗?肯定算法难,但是这个次数非常的多,不用管次数。这个是帝规,就是递归。这是并,这是并,这是两个有序数,组合成一个最后的大的有序数...

排序算法学习——归并排序_归并排序算法稳定吗

我们先看归并排序的定义归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每...

动画|经典的归并排序究竟怎么玩儿?

作者|菠了个菜责编|郭芮由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列——《图解数据结构》,主要使用动画来描述常见的数据...

Excel中,多列数据统一排名,Rank函数直接搞定

Rank实现多列联合排序排序,那太简单啦,Excel中,升序降序,一个按键就可以。但,那是针对单列情况,若需要联合多列数据进行排序呢?如下图所示,需要对1、3、5列进行统一排序,咋弄嘞?联合排序案例先...

【数据结构与算法】归并排序_数据结构中归并排序

归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序排序思想一天,小一尘和慧能坐在石头上,眺望着远方师傅,我听山下的柳...

C++基础算法:归并排序_经典排序算法-----归并排序(c语言实现)

归并排序(MergeSort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列。...

马士兵说之归并排序_马士兵教育的内推是真的

大家对于排序应该是挺熟悉的吧,马士兵老师特意为排序出了一波视频,当然文章是转自博客园的,马士兵老师的视频观看请点击下方的了解更多概要本章介绍排序算法中的归并排序。内容包括:1.归并排序介绍2.归并...

C++快速排序和归并排序_c++快速排序sort

快速排序每一轮挑选一个基准元素(随机选择,编程时一般选取第一个),并让比它大或小的元素移动到基准元素的两边,把数列拆解成了两个部分。而后对这两部分分别进行快速排序。时间复杂度:O(nlogn),辅助空...

经典的排序算法——归并排序_归并排序算法步骤

归并排序(MergeSort)是一种基于分治策略的高效排序算法。它将原始数组不断地分割成两个子数组,直到每个子数组只剩下一个元素为止(即基本有序),然后再通过合并已排序的子数组来最终得到完全有序的大...

归并排序_归并排序c++实现

归并排序概念:归并排序中涉及到一个概念就是分而治之,总序列化成小序列,将小序列排序好,利用排序好的小序列,再归并排序成原来要排序的序列。所以排序前先要分:functiondivide(arr){...

取消回复欢迎 发表评论: