毕业设计（论文）-基于图核的复杂数据异常检测算法.doc

摘要摘要I随着信息技术、互联网、云计算等产业的飞速发展，数据的采集、存储与传输变得更加便捷，使得人们迫切的需要从大量的数据中挖掘出重要的信息，数据挖掘得以飞速发展，异常检测则是数据挖掘中的重要组成部分。在海量的复杂数据中存在着一类图数据，他们呈现出一定的拓扑、几何特性，如化学分子、社交网络等。本文的研究内容就是图数据的异常检测，并根据不同数据集提出了相关算法。首先，本文利用图模型、邻接矩阵等方法对图数据进行描述，研究了图数据后选用了图核方法作为图数据之间的相似性度量，并利用KPCA方法对图核处理后的数据进行降维处理。其次，针对训练过程中使用的数据集相对不平衡状态，对图核处理并降维后的数据集采用对不同类别引进不同惩罚因子的加权SVM、加权SVDD-Negative方法，提出了基于图核的相对不平衡数据集异常检测算法，并在小数据集上进行了算法的分析，实验结果表明本文提出的算法在数据量相对不平衡的状态下具有一定的异常检测效果。接着，针对绝对不平衡状态即单类问题，对图核处理并降维后的某一类别数据利用单类分类器方法如One Class SVM、单类SVDD方法进行模型的训练，随后对未知属性的数据进行异常检测，提出了基于图核的绝对不平衡数据集异常检测算法，实验结果表明本文提出的算法对绝对不平衡数据集具有一定的异常检测效果。再次，利用在实际应用中的两个复杂的数据集对本文提出的算法进行了性能验证，表明本文提出的算法具有一定的实际意义。关键词：图核、图数据、数据不平衡、异常检测IVABSTRACT ABSTRACTWith the rapid development of information technology, the rapid progress of internet, cloud computing and other emerging industry, data collection, storage and transmission have become more convenient. People urgent to dig out the useful information from large amounts of data, data mining was developed and anomaly detection is an important part of data mining. There is a kind of graph data in the complex data, and they have the topologicalcharacteristics, such as chemical, social networks, etc. In this paper we make a research on anomaly detection of graph data, and put forward the related algorithm according to different datasets. Firstly, we use the method of graph model or adjacency matrix to describe this graph data, and use the graph kernel method as the similarity measure between the graph data, and using KPCA method to reduce the dimension of the data processing by graph kernel.Secondly, we use the different penalty factor according to different categories of data to solve the relatively imbalances datasets, such as SVM-Weights, SVDD-Negative Weights, and put forward the relatively imbalances anomaly detection algorithm based on graph kernel. We test our algorithm on small data set and the results show that the proposed algorithm has a certain abnormal detection effect on the relative unbalance data set.Thirdly, we use one class classifier such as One Class SVM, SVDD method to train one kind of data and train model, then test the unknown data using the model, and put forward the definitely imbalances anomaly algorithm based on graph kernel, the results show that the proposed algorithm has an certain abnormal detection effect on the definite unbalance data set.Finally, the algorithms are test in two complex data, the result show that our algorithm is practical.Keywords: graph kernel, graph data, imbalances data, anomaly detection目录目录摘要IABSTRACTIII目录V第一章 绪论11.1研究背景及其意义11.2国内外研究现状21.3存在的问题41.4本文研究内容与组织结构5第二章 复杂数据异常检测概述72.1图数据的表示方法72.2图核概述102.3图数据异常检测算法分析122.4总结13第三章 基于图核的相对不平衡数据集异常检测算法153.1问题的描述及分析153.2基于图核的相对不平衡数据集异常检测算法163.2.1算法步骤173.2.2算法具体流程223.3算法仿真验证233.4总结28第四章 基于图核的绝对不平衡数据集异常检测算法314.1问题的描述及分析314.2基于图核的绝对不平衡数据集异常检测算法324.2.1算法步骤324.2.2算法具体描述354.3算法仿真验证364.4总结41第五章 异常检测算法的应用435.1数据集简介435.2算法的应用445.2.1基于图核的相对不平衡数据集异常检测算法的应用445.2.1基于图核的绝对不平衡数据集异常检测算法的应用465.5总结49第六章 总结与展望516.1总结516.2展望52参考文献55致谢61攻读学位期间的研究成果6363河海大学硕士学位论文第一章 绪论1.1研究背景及其意义随着信息技术的快速发展，许多新兴产业如云计算、互联网、社交网络的飞速进步，以及各类图像识别技术、电子扫描枪、条码技术等的广泛使用，使得诸如军事、医学、经济、生物等学科的数据采集和数据传输变得更加便捷和迅速，各种通信设备、传感设备每分每秒都在记录着世界各个角落的数据，越来越多的数据正在不断产生，数据的形式也变得日趋复杂，规模不断增加。有关部门统计得出2009年的数据量为0.8ZB，2010年底的数据量为1.2ZB，2011年的数据量则增加到了1.82ZB，增长的速度目前还在逐年攀升，预计到2020年，数据总量将会是2010年的四十倍之多1。数据的急剧增加是人们面临的重要问题之一，这使得人们迫切的需要从大量的数据中发掘出有用的部分，数据挖掘则是在这样的背景下发展起来的重要研究领域。数据挖掘，从简单方面理解指的是一种从海量、混杂的数据中提取出相关知识或者模式的过程。数据挖掘的研究领域包含了多个学科并彼此间相互融合，例如其中包含了数据库、机器学习、统计学、人工智能等学科的知识。通过数据挖掘，人们可以从海量的数据中去伪存真，提取有用的信息与知识，并通过这些有用的知识和信息帮助人们发现某些事物中的模式与规律。近年来，数据挖掘已经成为信息处理的重要技术之一，也广泛运用于银行、金融、医疗、工业、零售、电信等诸多产业中，它的研究与应用正朝着更为深入的方向发展。数据挖掘的主要任务就是在指定的数据集或者是相关任务中找到特定的模式模型，它主要分为以下四种类别：依赖检测、类的识别、类的描述、异常挖掘2。前面的三类主要针对的是数据集中的大部分对象，异常挖掘则是发现数据集中的少数对象，这些少数的对象就可以称为异常数据。由于应用的背景领域以及使用的方法多种多样，异常数据的定义也各不相同。例如从聚类算法的角度上异常数据指的是其中的背景噪声，若从异常检测算法的角度上来看异常指的是与正常行为有很大不同的一类点，它们既不属于聚类也不属于背景噪声3。Hawkins在1980年曾给出了异常的定义，他指出：“异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。”4这个定义具有一定的通用意义并且能够适用于不同类型的数据及应用背景。异常数据又可以叫孤立点、异常物、偏离点、稀有类、少数类等。由于异常数据在某些情况下可能有其重要的研究价值，因此，异常数据挖掘时下也成为研究学者们研究的重要内容之一。多种研究领域中都包含发现异常数据的研究，根据不同的使用背景以及不同的使用方法，发现异常数据又可以称为异常数据挖掘、奇异点监测、孤立点监测、入侵检测、异常检测等56。异常检测是数据挖掘中的一个重要组成部分，异常数据的存在往往会对其所处的相关领域造成一定的危害，例如银行系统中的异常数据可能代表的是金钱欺诈行为，相关电力系统中异常数据可能代表的是设备的故障，在气象数据领域中异常数据可能代表的是重大自然灾害的发生，因此，如何在这些领域中发掘出异常数据即异常检测对人们的生活、财产都具有重要的意义。研究学者们根据目前提出的异常检测方法将异常检测大量的运用在了实际生活当中，异常检测的主要应用有：（1）欺诈行为的检测，如信用卡行为欺诈检测7，手机管理系统检测8，金融市场的信息安全等。这些恶意的欺诈行为被视为一种异常，2002年，Bolton9等就对金融欺诈分析领域的统计方法进行了回顾。这些方法在一定程度上减少了经济的损失。（2）网络安全，如文献10记载了应用于网络安全方面的异常检测的不同算法，并说明了网络入侵检测系统的相关结构问题。文献11则介绍了基于数理统计的异常检测技术及其在网络安全中的应用。（3）工业机械故障检测，如1994年，石油管道检测中就使用了基于神经网络的异常检测技术12 ，文献13中，作者提出了基于机身张力数据的异常检测技术。（4）图像与视频异常检测，文献14提出了一种基于神经网络的异常检测算法，用于发现视频流图像数据中的异常区域图像，文献15提出了一种基于SVDD的异常检测算法用于检测视频中移动物体。（5）生物医药信息系统中的异常检测，文献16中就提出了异常检测在乳腺癌早期诊断中的应用。1.2国内外研究现状在信息化的时代数据量与日俱增，如何快速的从这些数据中利用有效的手段挖掘出人们关心的隐藏的信息成为人们面临的一个重要问题与挑战。而异常检测是其中的一个重要方面，具有不可忽视的重要研究意义。1887年，统计学家弗朗西斯伊西德罗埃奇沃思发表了一篇不一致观测值的论文，这篇论文使得人们开始关注异常数据的检测。随着人们对异常数据检测的研究，许多异常数据检测的方法被提出并取得了一定的发展。基于统计的异常检测方法是发展的最早的一种并且它也是使用的较为广泛的一种方法，它的关键是对相关数据统计并度量，判断数据的概率密度分布，这种算法认为高概率密度分布区域中大部分都应该是正常的数据，低概率密度分布区域中则应该包含的是非正常的数据即异常数据。但是这个方法最大的缺陷是无法在任何情况下都能知晓判断出数据的分布类型，往往实际数据也并不一定都符合某一种有规律的理想的数学分布，因此专家学者们开始从另外的角度来进行异常数据检测的研究。Knorr和Ng在1998年提出了基于距离的异常检测算法，这种算法认为如果一个数据集中的某个数据称为异常，那么必须先设定好阈值，并且数据集中一定百分比的数据与其的相关距离大于这个阈值。Rastogi和Ramaswam则改进了他们对于异常的定义，F.Abgiulli和C.Pizzuti针对此类算法在高维空间中的运算复杂度较高的缺陷引入了连通图原理，降低了时间复杂度。Rastogi和Ramaswamy指出基于距离的异常检测算法在某种情况下可能会遗漏部分异常数据，例如存在不同密度数据集的情形下，他们认为异常数据不仅和数据之间距离的大小有关，同时也和数据的密度程度相关，因而提出了基于密度的异常检测算法。Breuning 等学者提出了基于密度的局部异常点挖掘算法17。近年来比较流行的异常检测算法主要是基于核的一种分类算法18，它的主要思想是通过一定的关系函数将输入的数据映射到高维空间中去，再通过高维空间中的分类超平面或者超球面等等建立分类模型并利用建立的模型来完成异常检测的目的。国内对异常检测的研究近年来也取得了一定的进展，林士敏提出了基于抽样的近似检测算法19，该算法提出了一个判定孤立点的新定义，对基于距离的异常检测算法进行了一定的改进。邓玉洁，朱庆生20提出了基于聚类的离群点分析方法。金义富提出了一种异常约简算法21，该算法在粗糙集理论中的属性约简技术基础之上，提出了异常约简算法，这种算法对已经挖掘出的异常可以很好的进行下一步的分析与解释。田江在一类支持向量机的基础上，提出了孤立点一类支持向量机算法。综上所述，国内外研究学者们针对异常的背景及相关应用领域提出了许多异常检测的算法，根据不同的分类标准，这些异常检测算法可以分为不同的类别，例如陈斌22等人根据一种广泛的分类方法将这些异常检测算法大致分为两类：有监督的异常检测算法和无监督的异常检测算法，或者是因为使用方法的不同分为基于距离、密度、统计的算法等，下面本文针对已有的异常检测算法进行相关分类并说明算法的局限性与存在的问题。（1）基于分布的方法：这种方法是基于统计学思想的，首先是对给定的数据集进行分析，假设它在一定程度上是符合某种概率分布模型，然后根据样本是否与模型一致来确定异常数据。此类方法适合训练样本数量多，结构简单，维数较低的情况，针对本文的复杂图数据可能面临的高维以及高复杂度特性不具有良好的检测效果，因此在正确率上无法得到保障。（2）基于距离的方法：这种方法的主要缺陷是时间复杂度较高并且在实验过程中对于参数的选择非常敏感，此外对于大规模数据集的使用具有局限性。（3）基于密度的方法：此方法与基于距离的方法一样时间复杂度较高，对于大规模数据集的使用同样具有局限性。（4）基于聚类的方法：这种方法首先进行的是对数据集的聚类，针对得到的聚类簇进行异常数据的判断，此种方法异常检测效果受最终聚类簇的影响较大，并且异常数据的存在又对最终的聚类簇的影响也大，二者相互影响，并且此类算法对于高维度下的数据集异常检测效果会有所下降。（5）基于分类的方法：此种方法是通过对已有的数据样本进行训练，在对未知数据进行判断的时候利用训练得到的分类模型对其进行分类，此种方法往往由两步组成：训练阶段和测试阶段。这种方法具有较为广泛的使用，还可以针对不同的应用背景设计不同的分类方法，本文研究的异常检测方法就可以归为基于分类的方法中。1.3存在的问题由于异常数据产生的背景，使用的环境等等情况的不同，异常检测在实际中仍然面临着很多的问题与挑战，主要有：（1）给定任意一个数据集很难用一个算法生成一个边界完美的将数据集包含其内，因此，无法找到完美的算法使得异常检测的效果达到完美的程度，此外也很难找到通用的适用于所有数据集的异常检测算法；（2）异常的含义与定义可能是不同的；例如Barnet和Lewis23在1994年定义“异常事件或者异常是与同类事件相比具有很大偏差的实例。” Johnson在1992年提出“一个异常事件是数据集中的一个观测实例，并且这个实例与其他实例相比看上去并不一致”等；（3）异常数据的不同分类方法，例如Varun Chandola等人根据异常数据与数据集内其他数据之间的相互关系，将异常数据分为点异常、上下文异常、聚集异常等，点异常是一种简单的异常，上下文异常不仅考虑了数据的本身特点，还考虑了数据所处的环境，而聚集异常则又考虑了数据之间的行为模式；（4）在不同的环境背景下，异常情况可能会随着环境的变化而变化，或者是异常情况与正常情况在某些情况下会互相转变。因此，针对不同的条件背景所采用的异常检测算法也是不同的；（5）此外，异常检测目前都是针对数据集进行学习，通过得到的学习来设定阈值或者根据模型来判定异常，然而数据集的情况又多种多样，难以利用通用的方法达到异常检测目的。1.4本文研究内容与组织结构本文主要研究的是数据挖掘中的一部分即异常检测，重点研究了复杂数据中的图数据异常检测算法，并将其运用到了实际应用中。针对图数据的情况使用了图核方法作为图数据之间的相似性度量，根据训练阶段不同的样本数据集进行分析研究，提出了相关异常检测算法，归纳起来，主要工作有： （1）分析了现有图数据的图模型、邻接矩阵、链表的描述方法，介绍了现有图数据的分析方法，选用了图核作为本文进行图数据异常检测的相似性度量方法，并利用KPCA对图核处理后的数据进行降维处理。（2）重点分析了样本训练过程中图数据集样本不平衡中的相对不平衡状态，针对此类状态提出了基于图核的相对不平衡数据集异常检测算法，并在两个小数据集上进行了算法的相关实验仿真分析。（3）重点分析了图数据集样本不平衡中的极端情况，即绝对不平衡状态，也就是单类问题，针对此类状态提出了基于图核的绝对不平衡数据集异常检测算法，并在小数据集上进行了算法的相关实验仿真分析。（4）将本文的算法运用到了实际的复杂图数据集中，并分析了异常检测的效果，表明本文提出算法的实用性。本文的内容分为六章：第一章，主要介绍了本课题的研究背景及意义，国内外的研究现状，异常检测面临的问题。第二章，介绍了复杂数据中的图数据的表示方法，并对图核方法进行概述，分析了图核在图数据分析中的重要地位，介绍了现有的可以进行图数据异常检测的算法。第三章，针对现实生活中大量存在的数据不平衡状态下的样本数量集相对不平衡情况进行分析，利用KPCA方法对图核处理后的图数据进行降维，利用样本加权（加权SVM或者SVDD-Negative ）解决数据之间的不平衡性，提出了基于图核的相对不平衡数据集异常检测算法。第四章，本章针对现实中存在的数据不平衡状态中的极端现象即样本数据集的绝对不平衡状态，利用解决单类分类问题中的单类分类器（One-class SVM，SVDD）建立异常检测的模型，提出了基于图核的绝对不平衡数据集异常检测算法。第五章，本章将本文提出两种基于图核的异常检测算法运用到了实际应用中，并做了相关实验分析，表明本文提出的算法在一定程度上能够达到异常检测的目的。第六章，本章对本文所做的工作以及研究成果进行归纳总结，并指出工作的相关不足之处以及对未来工作的展望。第二章 复杂数据异常检测概述随着计算机技术尤其是数据库技术的发展与应用，人们产生、收集、存储数据变得更加便捷，每天产生的数据不计其数，数据的复杂多样性已经成为现今社会数据表现出来的主要特性，这些数据在形式上可以表现为高维性、数据结构的复杂性、时空的动态性、规模的海量性等，在海量的复杂数据中存在着一种图数据，它们表现出一定的拓扑结构、几何结构特征，具有复杂的内部结构关系，数据之间也存在着复杂的相互关系，它们大量存在于我们的日常生活中，本文的研究对象即是复杂数据中的图数据。图数据中同样也会存在异常数据，图数据中的异常往往会对它们存在的领域造成一定的危害，例如网络中的入侵异常数据会对网络安全造成极大的危害，严重的威胁着人们的网络信息安全和财产安全，在生物医药信息系统中，突变的异常类基因会对人们的生命健康造成威胁，因此对图数据进行异常检测同样具有重要的意义。本文的工作即是针对复杂数据中的图数据进行异常检测分析，然而在对这类数据进行分析的时候面临着诸多问题需要解决，例如如何计算图数据之间的相似性则是对这些图数据进行下一步异常检测的关键，由于现有的一些机器学习、数据挖掘的算法大部分都适用于向量型数据，而对这类图数据则不能进行直接的利用，因此建立图数据与现有的机器学习、数据挖掘算法的桥梁即数据之间的相似性度量显得非常重要。本文在分析了现有的图数据之间相似性度量的方法后选取了图核方法作为图数据间的相似性度量，接下来本章对图数据的表示方法、图核以及为什么要用图核分析数据进行详细的介绍与分析，并简要介绍了图数据相关算法以及可以利用的异常检测算法。 2.1图数据的表示方法图数据大量存在于我们的日常生活中，常见的这类图数据有：网络数据中的HTML、XML24，神经网络，蛋白质序列，化学分子25等。图2.1显示了在实际生活中常见的图数据，基于图数据的相关算法得到了研究学者的广泛关注26。 图2.1 图数据举例在数据挖掘与机器学习领域中存在着诸多对数据进行分析的常用算法，例如分类与聚类算法等，这些已有的算法在对现实世界中的数据进行分析的时候需要找到一种对数据进行描述的方法。在以往的数据挖掘、机器学习中，涉及的相关数据大都表示为特征向量，将数据看成维空间中的一个点，即向量由个度量或者是特征组成，许多数据都可表示成向量形式，这种数据表示形式具有一定的数学上的优势性，它能够方便的计算出数据之间的和、差、积，还能利用欧式距离等方法计算数据之间的相似性距离等，然而对于图数据则很难用简单的向量形式准确的描述，此时就需要比向量更为合适的方法对其进行描述，如何对这类复杂的图数据进行表示与存储是人们首先需要完成的工作。图模型作为离散数学和计算机学科中的一般性数据结构，可以很好的表示具有拓扑特性以及几何结构的数据，它是一种具有自身优势的描述数据的方法，能够表示数据的各个属性，数据之间的关系也可以通过图模型来表达，并且数据被表示成图模型的时候并没有固定的维数限制，可以利用图模型中顶点代表现实世界中的实体对象，顶点之间的连线代表实体之间的关系，这样的图模型表示方式具有一定的实际意义，并且能够很好的展现出数据内部的结构关系，此外邻接矩阵、链表等方法也是很好的数据描述存储方法。一个图G是指一个二元组，其中是非空有限集，称为顶点集，其中元素称为图G的顶点，是顶点集中的无序或有序的元素偶对组成的集合，称作边集，其中元素称为边。图分为有向图和无向图两类，若图G中的边均为有序偶对，则称G为有向图，若图G中的边均为无序偶对，则称G为无向图。通俗来讲，指的就是连接图中的两个节点的边是否有方向性。图2.2显示了有向图和无向图，本文研究的图数据异常检测中对于方向性没有特殊的要求，因此本文接下来的分析中是以无向图作为主要分析对象。(a) 有向图G (b) 无向图G1图 2.2 有向图和无向图的表示本文中接下来研究的图数据则指的是数据挖掘等领域中待分析的实际数据表示成图模型的形式，由于实际生活中数据复杂多样，往往分析这些图数据的时候不仅仅只包含图模型中节点与边，还包括节点与边的一些属性问题等其他的许多信息，例如节点和边的属性等，如分子中的原子，连接原子之间的键等，因此，实际数据构成图数据集合，集合中的每个图数据都可以用一个四元组来表示，其中V是节点的集合，E是边的集合，是节点的属性集合，是边的属性集合。例如在研究化学分子的时候，可以将每个化学分子中的原子用图中的节点表示，化学分子中原子之间的键则利用节点之间的边表示。目前常用存储方式有邻接矩阵，其原则是对于无向图来说，当两个节点之间有边相连的时候记为1，无边相连的时候记为0，对于有向图来说，存在到的边记为1，则到的边记为-1，无边相连记为0。本文研究的为无向图，邻接矩阵记为，如下式所示，图2.3显示了一种简单图模型的邻接矩阵表示方法。无向图： 图2.3邻接矩阵标签由数组的方式存储，此外，还可以使用链表的方式存储节点与边之间的关系，例如假设节点i与节点x、y、z相连，则可以对节点i记为x,y,z。本文涉及的图数据均是用以上描述的方式存储。 2.2图核概述由于图数据的复杂性，不能像向量型数据那样利用欧氏距离等就可以计算数据间的距离或者相似度，传统的数据挖掘、机器学习中的算法大都不能直接运用于这些图数据中，而核方法则很好的解决了这个问题，使得传统的数据挖掘、机器学习中适用于向量的算法也适用于图数据，图核作为核函数中的一种，在这样的背景下应运而生，图数据之间的相似性度量对于图数据的分析有着不可忽视的重要的作用，图核作为核函数的一种，既能解决传统算法在图数据分析上的局限性，也能作为图数据之间的相似性，成为图数据研究的重要方法之一。此外图核还具有自身的优越性，例如图核不需要得到映射函数即可计算点积的值等27，因此，近年来图核得到了迅猛发展，成为专家学者们研究的热点之一。目前，研究学者们根据图核的特点将其运用到了许多领域中，例如指纹识别、图像分类、蛋白质分类等问题中28。文献29中作者就介绍了图核在人脸识别中的应用，文献30中作者介绍了图核在图像分类中的应用等。下面介绍图核的具体内容。图数据之间的相似性度量对图数据的分析有着不可忽视的重要作用，由于对图数据之间的相似性进行准确定义比较困难，专家学者们提出了具有灵活性的相似性度量，目前为止没有一个通用的适用于所有数据集的相似性度量标准。目前主要有两种方法：图编辑距离（graph edit distance）和图核（graph kernel），它们被广泛研究用来进行图的相似性度量。在字符串匹配的文章中最早提出来了编辑距离的概念，Sanfeliu和Fu最先在图数据的研究中引入编辑距离，图编辑距离是指将一个图转化为另一个图所需要的最小代价，转化的操作主要有：图节点和边的插入、删除、边替换等31。虽然图编辑距离也是一种度量图数据之间相似性的方法，但是，图编辑距离容易受代价函数c（f）的影响，两图之间的编辑距离由于c（f）的变化而变化，专家学者们还在寻找对代价函数的替换方法。因此本文并未选择图编辑距离而是选择图核作为图数据之间相似性度量的方法。核方法在向量型数据的分析中已经得到较为广泛的应用。核方法具体为：数据集合对应一个正定的核，存在一个样本数据到高维特征空间的映射，所有原空间中的样本，使得（2.1）核方法可以应用在高维特征空间中，如何在数据集中定义核函数成为核方法的重点。核方法在特征向量表示的数据中能够很好的适用，同时也可将其适用于图数据中，基于核方法的优势所在和图数据本身的特点，将核方法应用于图数据异常检测中具有现实意义，2002年Kondor和Lafferty最先提出将核运用到图数据之间32。所谓图核就是定义了两图数据之间的相似性或者是定义了核函数。通过映射将图数据映射到高维甚至无穷维向量空间（特征空间）中去，使得下式成立。（2.2）其中的分量可以是两图中某一公共子路径的条数等，核则可以看成是两个图之间的相似性度量，则含有个图的数据集可以通过以上计算得到的核矩阵。经过图核处理后使得图数据更加易于后期异常检测的分析。 近年来，有许多度量图数据之间相似性的图核方法被提出。典型的用于图数据分析，图核定义方法大致可以分为以下三类：（1）基于路径的图核，如最短路径核33，随机路径核等；（2）基于有限规模子图的图核，圈核等；（3）基于子树模式的图核，如快速子树核34等。图核近年来发展迅速，成为图数据分析的一个重要的分支，此方法尊重并且拓展了图的拓扑结构，图核方法成为图数据与成熟的机器学习、数据挖掘算法之间的一个桥梁35。本论文则是首先利用图核的方法对图数据进行处理，再针对样本训练过程中的不同情况进行异常检测模型的训练从而提出了相关异常检测算法。2.3图数据异常检测算法分析对于图数据的分析，专家学者们提出了许多有关图的算法，例如图的匹配研究，图匹配指的是比较图之间结构的相似程度，Conte36等人总结了大量的图匹配算法，并介绍了图匹配技术的相关应用。图匹配算法可以分为精确的和非精确的图匹配，精确的图匹配因为其严格的数学定义在实际中的应用往往较难，例如图同构37最大公共子图38，最小公共子图等，对于非精确的图匹配典型算法编辑距离受代价函数影响较大，很难提出很好的解决方案。图数据中的关键字查询也是图数据分析的一个重要方面，它面临着许多的挑战，例如准确率以及效率的问题等。所谓的图查询指的是使用一个图模式( 检索图) 作为输入，从图数据集中进行查询，搜索到不同的图模式并构成检索图39。然而面对大规模图数据集的时候，由于很难得出图数据的整体结构以及关键字在图数据中的分布，因此，如何挖掘出整体的图结构以及有效的查询关键字具有一定的难度，此种情况下进行图数据关键字带有一定的盲目性。频繁子图挖掘也是图数据分析的一个重要研究领域，常见的频繁子图挖掘算法大致可以分为基于Apriori的算法、基于模式增长的算法、基于最小描述长度近似算法等39。利用核方法将原始图数据中映射到高维空间中，使得传统数据挖掘中的异常检测算法理论上都可以运用到图数据中去，图的聚类则可以作为图数据异常检测的一种方法。一个图数据集可以由很多个图数据组成，同样也可以只包含一个复杂的大型图数据。对于由很多个图数据组成的图数据集图聚类指的是对象的聚类，例如基于距离的结构化方法40，基于概要信息的结构化方法41等。对于一个复杂的大型图数据来说图的聚类就是节点的聚类，类似于图分割42。同样图数据的聚类算法受数据集中数据的类别影响较大。图分类是图数据分析的一个重要方面，同样可以利用图的分类算法来对未知数据进行类别的判断从而得出相关的异常数据，它是一种通过对已知训练样本的学习来判断未知样本分类的问题。目前图数据分类方法主要包括基于频繁模式的分类算法43，基于概率子结构的分类算法44以及基于图核的分类算法39，由于图核函数的优势使得基于图核的分类算法得到了一定的发展，如 Boser45等使用核方法用来分类图结构的样本。 Horvath46等基于核函数定义了图核函数，此种图核函数是根据图中环模式集合和树模式集合提出来的，然后利用支持向量机进行下一步分析的方法。本文选用的图数据异常检测算法则可归为图数据的分类算法中。以上的算法大都具有一定的广泛性，然而在训练图数据样本的时候可能会遇到不同的情况，针对不同的情况则需要不同的解决方案，本文提出的基于图核的异常检测算法对样本数据集的不同进行了细化，更具有针对性，同时具有一定的异常检测效果。由于样本训练过程中使用的数据集大多数情况下是不平衡的，而数量上的不平衡又占了很大的比例，数量上的不平衡分为相对不平衡性以及绝对不平衡性，因此，本文接下来针对这两种情况分别进行研究，提出了基于图核的相对不平衡数据集异常检测算法及基于图核的绝对不平衡数据集异常检测算法，分别在三、四章予以具体分析介绍。2.4总结本章介绍了复杂数据中的图数据，并用图模型、邻接矩阵或者链表的方式对图数据进行描述存储，在分析了现有的图数据之间相似性度量的方法后选取了图核作为图数据间的相似性度量，并对图核进行了详细介绍，同时本章对图数据的已有研究内容进行了相关介绍，并针对图数据异常检测情况进行了相关分析，引出了本文接下来的研究工作，即针对图数据训练过程中使用数据集的不同提出的不同异常检测算法，第三章的研究内容即是基于图核的相对不平衡数据集的异常检测算法分析。第三章 基于图核的相对不平衡数据集异常检测算法异常检测在模型建立的过程中会面临许多不同的背景与问题，因此需要根据不同的背景与问题制定相关异常检测方法，在异常检测的训练阶段由于使用的样本数据集不同可能会需要不同的异常检测方法。如今的机器学习以及相应分类器的设计大致可以通过在训练分类器的时候使用数据的标签个数的多少分为单类、两类和多类这三种类别，其中的多类问题可以通过一对一或者是一对多的方法进行分解最终变为两类问题，因此，分类器大致可以分为两类问题和单类问题。一般的分类器运用的都是两类数据，建立的是两分类器，并且在样本训练过程中使用的数据大致是平衡的，然而在实际情况下经常会遇见样本数据集的不平衡问题，例如异常数据获取的代价较高，不一定能够得到大量的异常样本等等，许多实际情况中仅仅能够获得少量珍贵的异常样本，这种情况就成为模式分类中的数据不平衡问题47，可以大致分为数量上的不平衡，分布上的不平衡以及特征上的不平衡等几大类。当数据的各个类别出现不平衡状态的时候，传统的机器学习方法的性能就会下降，严重的时候则有可能会导致对于学习建立模型失去其应有的意义。本章研究的是在数量上的相对不平衡问题，这种情况大量存在于人们的生活工作中，例如在某银行数据库信用系统中，大部分用户都是无不良信用记录的客户，这些数据中也存在有信用缺失的客户群体，但是这部分客户的数量相对于无不良记录的客户来说是少数的，这就构成了一个数据的相对不平衡问题，还有通过遥感卫星图像检测海面油污48等都是数据的相对不平衡问题。本章则是针对相对不平衡数据集背景下进行异常检测，提出了基于图核的相对不平衡数据集异常检测算法，本章接下来将对算法进行详细说明。3.1问题的描述及分析 样本数据集相对不平衡状态即样本实例中一些类的样本数量较多，而另一类的样本数量则较少，通俗的来说就是样本中某些类的样本数量相对于其他类别的样本数量所占的比例要小，但是它的总数不一定是少的。如何对数据相对不平衡问题进行分析具有重要的意义，例如文献49就对不平衡数据分类及其在肿瘤识别中的应用进行了相关介绍。我们称样本数据集中多数量类别与少数量类别的数量比为这个数据集的不平衡程度，随着实际情况的不同，数据的不平衡程度往往不同，有的时候可能会达到100:1或者更大的比例，曾有学者对数据集的不平衡程度进行了深入研究，发现不能仅用这个不平衡程度的比例来看最终的效果，最终的效果还跟数据集的具体情况有关50。针对样本数据集相对不平衡的问题目前有几种解决方法，例如过采样、欠采样，代价敏感学习等。采样的思想是改变数据集的分布从而减少数据不平衡带来的影响，过采样是增加少数类样本，例如可以复制少数类的样本使得少数类的个数增加，但是这种方法有可能会造成过度拟合50。欠采样则是减少数据量相对较多的类别数据量，这种情况可能会造成重要信息的丢失，会对最后的结果造成影响，研究学者们通过对采样方法的深入研究提出了一些改进方法，例如Chawla等人提出的SMOTE算法，Kubat等人提出了one-sided selection算法50，这些算法虽然在一定程度上能够达到对于采样方法的改进，但是改进的程度有限。集成学习和代价敏感学习算法是针对不平衡数据的解决方法， AdaBoost就是一种迭代集成算法，每次迭代对样本采用不同的权重，通过一次次的迭代减少数据不平衡带来的影响，这种方法对小样本具有良好的性能，对大数据集上随着迭代的增加会造成分类器对样本过于敏感51。代价敏感学习是目前应用的较为广泛的解决样本数据不平衡的方法之一，例如根据数据集中样本的错分代价来对训练集进行重构，或者是在传统的机器学习、数据挖掘算法中的分类算法的基础上引进一种代价敏感因子，这种方式通常是对多数样本和少数样本分别赋予不同的代价，并以此来减少数据不平衡对最终结果造成的影响51，本文就利用了代价敏感学习中的这种方式利用了加权的算法对图数据集中的样本不平衡问题进行分析解决，在图核处理数据并降维之后采用了加权方法训练样本从而达到最终的异常检测效果，提出了基于图核的相对不平衡数据集异常检测算法。3.2基于图核的相对不平衡数据集异常检测算法本章研究的内容是基于图核的相对不平衡图数据集条件下的异常检测算法，首先对于原始图数据利用图模型、邻接矩阵、链表等进行表示，其次利用图核计算图数据集中图与图之间的相似性，将数据映射到高维空间中，由于高维空间中数据有可能具有冗余性，再对其进行降维处理，得到合适维度下的数据集，针对样本数据集相对不平衡的特性利用设计的分类器进行样本学习，将未知属性的数据集送入学习到的模型中进行属性的判断从而达到异常检测的目的，大致流程如图3.1所示未知属性图数据集异常检测样本加权方法训练相对不平衡图数据样本图核处理图3.1 算法流程3.2.1算法步骤（1）Weisfeiler-Lehman 子树核计算本文使用图核的是Nino Shervashidze等人提出的子树核33，这种图核方法的时间复杂度与其迭代的次数相关，假设h为其迭代次数，那么它的时间复杂度为，从其时间复杂度上来看它所消耗的时间相对较少，本文就采用这种图核方法作为图数据之间的相似性度量。图3.2所示的是它的一次迭代过程，先将与每个节点有边相连的节点标出，并对这些标号按序重新标号表示成（3.1）式即可利用欧式距离等进行计算。 ， （3.1） 原始不同节点个数 重新标号后不同节点个数图3.2 Weisfeiler-Lehman 子树核一次迭代（2）KPCA降维图模型对现实世界中的图数据具有很好的表达效果，利用图核的方法可以将含有个图的数据集转化成的核矩阵，随后即可利用异常检测算法对数据集进行异常检测分析。利用图核的方法将原始数据映射到高维特征空间中，高维数据往往存在一些冗余特征，或者是与数据分析不相关的特征，属性太多会增加计算的复杂性甚至可能会导致“维数灾难”，并且如果直接利用这些高维数据可能会导致异常检测的效果降低，因此去掉这些冗余特征即数据降维是很有必要的。图核的定义与在向量数据上定义核函数的本质是相同的，都是通过非线性映射将原始数据映射到特征空间中，使原始空间不可分问题在特征空间线性可分。利用核主成分分析方法(kernel principal component analysis，KPCA)52的思想，将高维数据进行降维，可得到由向量表示的包含了原始数据集的主要特征也使得问题的分析解决更加合理化的低维数据集。假定图数据集为，通过图核映射的方法可以得到核矩阵为，这里的核函数可以是间隔化核，卷积核，最短路径核等已有的核函数，KPCA的目标函数为（3.2） （3.3）式中为降维矩阵（降为维，则含有列），为映射函数，最大化上式则为解如下特征方程： 式中.（3.3）式的解为（3.4）式中为(3.3)式的前个不为0的特征值对应的特征向量，。对于一个新的图则利用下式对数据进行降维：（3.5）（3）样本加权（a）SVM-weights模型（GK-SVMW（Graph Kernel SVM Weights）（3.6）支持向量机（SVM）的方法主要就是寻找最优超平面将样本数据分为两类，即超球面为：如若数据集线性可分，则可以通过求解以下的最优化问题（3.7） 若非线性可分，则引入非负松弛变量，则上式可转变为（3.8） 从上式可以看出SVM算法对样本中所有数据点都采用了相同的惩罚因子C，不能对不平衡的数据进行有效的处理，因此，Veropoulos53等人提出了SVM-weights算法，这种算法的思想是对少数样本以及多数样本分别施加不同的惩罚因子，对样本个数较少的类别采用更大的惩罚因子来减少因为数据的不平衡性而导致的SVM最终分类效果下降的影响，具体如下所示：（3.9）它的对偶形式为：（3.10） 算法的实现通过不断调节样本的惩罚因子来获得最佳的效果。（b）加权SVDD-Negative模型（GK-SVDDNW（Graph Kernel SVDD Negative Weights）支持向量数据描述（SVDD）模型的基本思想是寻求一个超球面将目标类数据尽可能的包围起来，在超球体外的待判定样本则为异常，超球体内的样本则为正常数据，超球面上的样本则为支持向量。如图3.3所示为一简单的模型，样本数据被半径为R圆心为a的超球包围，有三个样本在超球体上，即为所求的支持向量，图中有一个样本在超球体外，则视为异常样本。图3.3 SVDD模型David Tax进一步提出了带野值的SVDD的模型即SVDD-Negative。该模型提出了对SVDD的改进，在训练样本中引入了少量的异常样本即野值，因此在模型的训练过程中包含了两部分：正常样本和少量的野值，通过对野值的引入增强了模型对数据的描述能力，调整超球半径和圆心，最终增强异常检测的效果。（3.11）假设数据集为，数据集中正常样本的下标记为i，j，非正常样本的下标用l，m表示，并且样本的标签设置为正常类记为1，非正常类记为-1，引入松弛变量，则问题变为最小化问题：约束条件为：（3.12），在（3.11）式中C的值与样本的个数有关，每个样本都是被看作对分类器具有相同的重要性的，大多数情况下可以被设