蒋 斌，黄恩铭
(南京中医药大学，江苏 南京 210023)
随着互联网中发布信息量的增加，互联网逐渐发展为全球最庞大的知识资源库。异质网络是现实世界的抽象代表，包含各类对象与链接，且存在很多区别于正常数据的局部离群点[1]。在整个异质网络中，局部离群点虽然仅占一小部分，但蕴含很多重要信息，相对于采集正常数据中的信息，检测出局部离群点中的隐藏信息具有更高的研究价值。目前，局部离群点检测被广泛应用于各个领域，对数据分析以及发展趋势预测起着关键作用，例如在军事领域，能对设备异常状况进行分析；
在安防领域，可预测极端天气，从而为人们的生命以及财产安全提供保障；
在工业领域，能用于检测机器故障；
在医疗领域，可对患者检查结果内的异常指标进行判断[2]。因此，研究异质网络中局部离群点检测方法意义十分重大。
许多相关专家学者都在该领域的研究中取得丰硕的成果，如彭涛[3]等人使用排序与聚类方法完成局部离群点检测，该方法需对数据集执行多次扫描，对增量与动态数据的处理能力较弱；
牛少章[4]等人使用网络查询方法完成局部离群点检测，该方法检测用时较短，但内存使用状况紧张。
分形理论以分形几何学作为基础，从分数维度视角出发，使用数学方法对客观事物进行表示与分析，可描述客观事物真实属性及状态能力，所得结果与研究对象的真实状态及属性非常接近。因此，本文提出基于分形理论的异质网络中局部离群点检测方法，通过分形理论将局部离群点检测问题转化为优化分割问题，利用FDOM算法求得最优解，实现局部离群点的精准、快速检测。
2.1 基于Z-ordering的多重分形维数
通常利用一个分形维数，可以对浅显分形集合的特征及复杂度进行较为精确的表示。利用多重分形维数表示复杂对象的层次及特征，是因为很多非线性因素在该对象形成过程中对其产生巨大影响，导致特征差异性显著，无法只利用一个分形维数表示[5，6]。设置多重分形维数，用Dq描述，称其为q次广义维数，能够用于表示多重分形(即复杂对象)。
2.1.1 广义维数
数据点以概率形式分散于空间Rd中，假设划分空间为d维超矩形，边长为ε，各超矩形有数据点光临的几率用pi描述，次数q的信息量用Iq(ε)描述，q为正数，且不等于1，式(1)描述了Iq(ε)的定义
(1)
式内，超矩形的数量用M描述。在ε→0的情况下，多重分形维数定义用式(2)描述
(2)
式内，若要表明Dq为信息维数(D1)，则q的值等于1；
若要表明Dq为容量维数(D0)，则q的值等于0；
若要表明Dq为关联维数(D2)，则q的值等于2。
2.1.2 多重分形
对数据集进行分割，使其变为N个小区域，假定第i个小区域线度规模，用Li描述，分形体生长界面小区域的生长概率，用Pi描述，使用不一样的标度指数αi描述生长概率，是因为不一样的小区域生长概率具有差异[7]，Pi的计算过程用式(3)描述
(3)
如果是在Li→0的情况下，可以将式(3)转化为式(4)所描述的形式
(4)
式内，在分形体中，任意小区域的分维用α描述。能够获得谱f(α)，它由包含不同α的无穷序列组成，因为小区域的规模非常庞大，所以α与f(α)是一套参量，可用于对多重分形进行表示。
将式(3)左右两端分别乘q次方，再进行求和操作，可得到如式(5)所描述的表达式
(5)
通过式(6)描述基于式(2)得到的广义维数定义
(6)
式内，利用q值的变化情况，能够对包含不同αi的子集进行区分。通常利用分形谱Dq-q、f(α)-α表示多重分形，两者之间的关联用Legendre变换描述，如式(7)所示
(7)
根据式(7)可得，Dq可由α与f(α)求得。根据式(5)、(6)可以看出，在已知Pi的情况下也可以求得Dq，进而使用式(8)求出α
(8)
利用式(8)可在计算获得Dq的条件下，求出α与f(α)。
2.1.3 基于Z-ordering的多重分形维数算法
利用尺度δ量度数据集F，即大多数分形维数定义的指导思想[8]。测量值Nδ(F)满足的幂定律对F的维数具有决定作用，在δ趋于0的情况下，若常数c、s满足式(9)所示表达式，那么F存在维数，F的δ-维长度用c描述。
Nδ(F)∝cδ-s
(9)
式(10)为对式(9)左右两端取对数所获得的表达式
lnNδ(F)≅lnc-slnδ
(10)
式内，在δ不断接近于0的条件下，两侧的差值逐渐趋于0，因此，可得到如式(11)描述的表达式
(11)
lnNδ(F)和lnδ的双对数图，可基于合适的δ区间绘制出来，通过图中无标度区斜率，对维数s进行预估。
计算分形维数时，分割数据空间，使其转化为边长一致的网格，对网格内具有的数据点个数，以及总数比率进行合计，并统计其总和，对于边长不一样的网格结构均需重复执行该过程。为减少内存空间占用，使用Z-ordering执行最小网格的编码处理，利用动态更新网格编码，将底层网格映射至高层网格，并根据底层网格结构，对边长不一样的网格具有的数据点个数进行统计[9，10]。
2.2 分形局部离群点检测优化模型
各种实体与链接包含于异质网络中，若使用向量形式描述全部实体，在执行离群计算时难以获得理想的计算效果，因此基于上述分形理论，对异质网络中的实体进行处理，完成局部离群点检测。
2.2.1 异质网络定义
设置G=(V，E；
τ，φ；
A，R)，表示有向图；
节点集与边集分别用V、E描述；
关系类型映射函数，用φ描述；
对象类型映射函数，用τ描述；
各关系e∈E均隶属某给定的关系类，用φ(e)∈R描述；
各对象v∈V均隶属某给定的对象类，用τ(v)∈A描述。节点类型个数用|A|描述，边类型个数用|R|描述，若|A|的值大于1，或者|R|的值大于1，则此种网络为异质网络。
2.2.2 基于分形理论的局部离群点定义
设置数据集D，其分形维数用DIM(D，D)描述；
该数据集将数据点p删除后的分形维数，用DIM(D-p，D)描述。式(12)为p的离群程度表达式
(12)
式内，若要说明p具有局部离群点的几率较高，OD(p，D)的值应越大。
设置数据子集Si，其离群程度用OD(Si，D)描述，若要表明Si中包含局部离群点，那么OD(Si，D)的值应大于1，若要表明局部离群点是d内的点，OD(Si-d，D)的值应最小。
2.2.3 局部离群点检测优化模型
根据2.2.2小节可得，局部离群点不同于数据集内的其它点，且与之差异性极大。出于对大部分数据集复杂度的考虑，将异质网络中局部离群点检测问题转化为优化分割问题[11]。
设置数据集D内属性数量为M，该数据集的属性集合用A={A1，A2，…，Ad}描述。Si⊆D表示随机的子数据集，其分形维数用Dim(Si，D)描述，可用于对数据集进行分割求解。
如果数据集被分解成n个子数据集，那么可用式(13)描述优化分割模型的表达式
[OD(S1-O，D)，OD(S2-O，D)，…，OD(Sn-O，D)]
(13)
式内，最佳局部离群点集合，用O描述，清除O内的点之后，该集合能够最小化数据集在每个子集的离群程度。
2.3 基于FDOM算法的模型求解
根据贪婪算法的理念，提出FDOM算法对局部离群点检测优化模型进行求解。算法的输入为数据集，将其内数据的初始类别设置完成后执行该算法，进行数据集的遍历，若需要修正某条数据类别，是在其修正后可使离群程度减小的条件下，完成修正后对下一条数据进行验证，循环执行该操作，停止条件为数据集中不包含需修正类别的数据，从而获得最优解以最小化离群程度。
数据集用D描述，其内数据点数量为N，各数据点属性数量为M，可将其当作M维向量。将基础数据保存于哈希表中，各哈希表的关键字为属性值，其呈现次数为参考值。以下为FDOM算法求解模型的过程：
1)满意的局部离群点数量用K描述，以K与数据集D作为算法输入；
2)分割数据集D，将其转化为S个子集；
3)通过各数据集内的数据点t，对哈希表进行初始化操作，将各数据点记作非离群点，用0描述；
4)如果未遍历完整个子集，采集下一个子集的数据，并对该子集的离群程度进行计算，若结果大于1，将子集内的数据清除，停止条件为得到该子集最小的离群程度，将符合该条件时清除的数据点作为局部离群点，用1描述；
5)重复执行步骤4)，停止条件为检测到的局部离群点数量为K；
6)将检测到的K个局部离群点数据输出。
将AMiner与Movie dataset两个真实异质网络数据集作为实验对象，利用本文方法检测其内局部离群点，以验证该方法的检测性能，两个数据集所含数据类别及局部离群点数量详情分别用表1、表2描述。
表1 AMiner异质网络数据集详情
表2 Movie dataset异质网络数据集详情
检测AMiner异质网络数据集中局部离群点，将离群程度最大的m个局部离群点中，稀有类数据占全部稀有类数据的比重当作评价指标，占比越高，方法的检测性能越优异。设计对比实验，选择文献[3]的排序聚类检测方法与文献[4]的网格查询检测方法作为本文方法的对比方法，在不同局部离群点数量下，三种方法的局部离群点中稀有类数据的占比情况用图1描述。
分析图1可以看出，随着局部离群点数量的增加，三种方法检测出的局部离群点中，存在的稀有类数据均呈上升趋势。相对于其它两种方法，本文方法的稀有类占比始终保持最高，且上升速率较快，当局部离群点数量增加至100时，稀有类占比高达95%；
当局部离群点数量小于60时，排序聚类检测方法的稀有类占比相对较高；
当局部离群点数量大于50时，网格查询检测方法的稀有类占比上升速率加快，且超过排序聚类检测方法的稀有类占比。对比这些数据可得，本文方法的异质网络中局部离群点检测效果最佳。
图1 AMiner异质网络数据集检测结果
使用F-Measure评价指标(召回率及精确率的调和平均数)，进一步验证异质网络中局部离群点检测能力，该指标的值越高，方法的检测能力越强，以Movie dataset异质网络数据集作为测试对象，在不同数据类别下，三种方法的F-Measure结果用图2描述。
分析图2可得，本文方法检测不同数据类别中局部离群点所得的F-Measure值始终高于0.9，检测结果十分稳定；
排序聚类检测方法的F-Measure值与本文方法的F-Measure值较为接近，无明显起伏，最大F-Measure值接近0.9；
网格查询检测方法的F-Measure值在0.4-0.8区间内起伏剧烈，最大F-Measure与最小F-Measure之间的差值较大，检测结果稳定性较差。对比这些数据可以说明，本文方法对于异质网络中不同数据类别的局部离群点检测都能获得理想的检测效果。
图2 三种方法的F-Measure结果
异质网络中局部离群点检测是从大量数据集中获取少量隐藏信息的过程，本文在分形理论的基础上，将局部离群点检测问题转化为优化分割问题，基于贪婪算法的思想设计FDOM算法求得最优解，实现异质网络中局部离群点检测。该方法的实际应用不仅对安防、医疗等领域的网络化发展具有重要意义，还能极大地促进社会经济的发展，日后可进一步完善该研究方法，使其更好地为国家服务。
猜你喜欢离群异质维数β-变换中一致丢番图逼近问题的维数理论数学物理学报(2022年4期)2022-08-22一类齐次Moran集的上盒维数数学物理学报(2020年3期)2020-07-27关于一维Moran集Hausdorff维数的一个新证明和一个新结果数学年刊A辑(中文版)(2018年2期)2019-01-08一种相似度剪枝的离群点检测算法小型微型计算机系统(2018年8期)2018-09-07离群数据挖掘在发现房产销售潜在客户中的应用中国房地产业(2016年9期)2016-03-01随机与异质网络共存的SIS传染病模型的定性分析云南师范大学学报（自然科学版）(2015年5期)2015-12-26Ag2CO3/Ag2O异质p-n结光催化剂的制备及其可见光光催化性能中央民族大学学报（自然科学版）(2015年2期)2015-06-09MoS2/ZnO异质结的光电特性物理实验(2015年10期)2015-02-28应用相似度测量的图离群点检测方法西安交通大学学报(2014年8期)2014-04-16一种基于核空间局部离群因子的离群点挖掘方法上海电机学院学报(2014年3期)2014-02-28