论文部分内容阅读
从数据分析角度来看，离群点是数据集中偏离大量常规数据、从而表现出离群数据模式和产生机制的数据点。在数据清洗过程中，这些点往往被视作噪声而被抛弃。但在许多实际应用领域，离群点很可能隐藏着大量潜在而重要的信息，对这些离群数据的识别可能比对正常数据的分析更具价值。例如金融、通信、网络等领域，识别出的离群点可能分别意味着信用卡欺诈、移动通信盗窃、网络入侵等行为;在诸如医疗、气象、天文等领域，识别到的离群点意味着新模式的开始或者新现象的产生。离群点检测是利用数据挖掘、机器学习、统计学等多种手段和技术识别离群点的过程，相关研究具有重要的学术意义和广阔的应用前景。目前，离群点检测在非图结构数据构成的传统数据集上取得了丰富的研究成果。然而，近年来诸如合著关系网、罪犯关联网、Email传输网等社会网络的出现，给离群点检测带来了新的挑战。其一，社会网络促使离群点检测技术不仅需要考虑网络中的内容信息，还需要关注网络的拓扑结构信息;其二，社会网络中抽取出的社区，为社会网络的离群点检测提供了一种新的、特定的上下文环境;另外，社会网络可能随着时间不断发生变化。现实生活中，这种变化可能体现在网络中的节点、边、社区甚至社会网络本身。面对社会网络带来的日益复杂的社会网络数据集，如何快速准确地识别出离群点成为一个具有挑战性的课题。 本文对社会网络中的离群点检测相关理论和方法进行了研究，针对静态社会网络和动态社会网络分别提出了相应的离群点检测方法，主要内容包括：⑴对存在于静态社会网络中的社区离群点给出描述性定义和可量化定义。提出一种识别社区离群点的检测方法，即SCODA(Scalable Community OutliersDetection Algorithm)方法。该方法通过考虑社会网络的内容及结构双信息，确定离群点存在的上下文环境，并在此基础上识别社区离群点。⑵定义了存在于动态社会网络中的局部演化离群点。提出一种增量式局部演化离群点检测方法，即IcLEOD(Incremental Local Evolutionary Outlier Detection)方法。该方法基于网络的时序信息、拓扑结构信息以及局部邻域构成的上下文环境来识别局部演化离群点。由于在识别离群点时，仅需考虑增量部分及其邻域，而不必要求事先知道整个网络各时刻的全部信息，提升了算法的效率及通用性。⑶从实验的角度分别评估了本文提出的两种方法，即SCODA方法和IcLEOD方法，在真实数据集合著关系网DBLP以及一系列合成数据集上对方法进行了验证，准确率和检测效率的结果证明了两种方法的实用性和可行性。