异质信息网络中离群点检测方法研究.doc

异质信息网络中离群点检测方法研究异质信息网络是无处不在的。挖掘隐藏在异质网络中偏离正常数据对象的离群点是数据挖掘领域的重要任务之一。离群点检测在入侵检测、欺诈检测、预测恐怖袭击、预测可疑事件和数据去噪等领域都有着广泛的应用。研究表明,挖掘偏离正常对象的离群点比挖掘周期性出现的数据更能给用户带来有价值的信息。本文从静态网络离群点检测、动态网络离群点检测和挖掘离群点对等方面对离群点检测技术进行深入研究,具体研究工作如下:1)针对静态异质信息网络提出了一种基于元路径的离群点检测方法。该方法通过分析网络结构中的链接关系得到源对象与目标对象特征间的相关程度,进而计算对象间的语义相似度。结合元路径及对象间的相关程度度量不同类型对象之间的可达概率,最后通过可达概率和路径长度计算任意两个节点间的离群程度。另外,每个节点都被赋予了一个可信度权值来提高准确率。我们在真实数据集和模拟数据集上对该算法进行测试,实验结果表明,该方法在结合节点语义信息的前提下,能够有效地识别静态网络中的离群点;2)聚类作为数据挖掘领域最重要的信息获取方法之一,在异质网络离群点检测中也有广泛的应用。大多数传统的聚类方法在插入新数据的过程中需要重新计算整个数据集而不是增量更新一部分数据。针对上述不足,本文提出了一种自底向上的增量聚类方法并将其用于异质网络的动态离群点检测过程中。进行聚类前,每个节点都作为单独的聚簇。此外,定义了一个新的度量标准CV(comparisonvariation),来迭代判断距离最近的两个聚簇是否能进行合并或当聚簇发生变化时已有聚簇是否能被分裂,并通过调节参数λ来动态控制聚类的严格程度。该度量标准不需要提前确定聚类个数,可以根据不同的数据集大小和数据质量动态确定最适合的聚类个数。实验结果表明,该聚类方法可以有效地进行聚类并且增量地更新数据;3)针对动态异质信息网络提出了一种基于张量表示的离群点检测方法。该方法根据张量表示的高阶数据构建张量索引树。通过搜索张量索引树,将特征加入到直接项集和间接项集中。根据基于短文本相关性的聚类方法判断数据集中的数据对象是否偏离其原本所在聚簇来动态检测网络中的离群点。该模型能够在充分降低时间和空间复杂度的情况下保留异质网络中的语义信息。实验结果表明,该方法能够快速有效地进行动态网络环境下的离群点检测;4)为了深入研究并分析异质网络中链接结构相似度与语义关系相似度间的差异带来的影响,本文还提出了一种基于链接结构与语义关系的差异性来检测离群点对(outlierpair)的方法。首先,构造目标对象间的链接结构相似度与语义关系相似度的邻接矩阵,分别通过分析链接结构和语义关系来得到对象间的相似程度。分析对象在结构上的关联关系,得到目标对象的链接结构相似度。提出k-步索引方法来得到目标对象的特征表示,从语义关系的角度计算目标对象的相似度。最后,利用矩阵的线性变换得到任意目标对象对在链接结构和语义关系上的差异,较高差异值对应的对象对被视为离群点对。实验结果表明,该方法可以有效地识别异质网络中存在的离群点对;5)为了能够增量检测离群点对,本文还提出了一种基于元组的增量离群点对检测方法。利用三元组的形式来表示异质网络中的数据,存储了目标对象以及对象间的链接权值,通过合并及镜像过程得到对象间的结构相似度。定义了前驱节点、后继节点以及覆盖率的概念,在减少参数个数的同时可以高效计算基于内容的相似度。结合基于结构相似度与基于内容相似度来计算离群分数。最后,说明了如何通过对三元组进行插入和删除操作来更新对象对的结构相似度以及内容相似度,进而更新对象对间的离群分数。增量更新离群分数可以有效降低时间及空间复杂度。实验结果表明,用元组形式表示异质网络中的数据可以动态更新离群分数,很大程度上提高了效率。本文对离群点检测的研究主要包含两个方面,首先,是对于单个离群点检测的研究;其次,是对于离群点对检测的研究。对于这两方面的工作,本文分别提出了两种检测方法:1)对于单个离群点检测,分别在静态网络、动态网络的环境下通过基于元路径和基于张量表示的方法对异质网络中的离群点检测进行深入研究;2)对于离群点对检测,分别提出了基于链接结构和语义关系的离群点对检测方法以及基于元组的增量离群点对检测方法。另外,在进行动态网络离群点检测的过程中,提出了一种增量的聚类方法。在异质网络的环境下进行离群点检测研究是一个新的尝试,具有一定实际意义。