论文部分内容阅读
从海量数据中发现潜藏着的、有价值的知识,是一项巨大的挑战。在一些情况下,知道什么样的数据显著区别于数据集中的其它数据,也就是发现离群数据,显得非常重要。现有的离群点检测算法,大多针对的是高维数据、不确定数据、流数据和时间序列数据。直到近些年,才逐渐出现针对信息网络的离群点检测研究工作。信息网络中,尤其是异构信息网络中,节点和边的类型多样使之具有更加复杂的结构信息和语义信息,这给离群点检测带来了更多挑战。本文定义了异构信息网络中关联关系离群的概念,其中,关联关系离群具体表现为网络中节点的关联节点在属性特征和连接特征上存在异常特征。本文还扩展了现有的离群点查询语言框架,使之适用于本文离群点检测研究的需要。为了检测上述关联关系存在异常的节点,本文提出了基于节点关联关系的离群点检测算法(Correlation-based Outlier Detection,CBOut)。CBOut算法引入用户偏好,由用户来决定离群节点类型,并基于用户偏好衡量网络中的节点是否离群。CBOut算法先计算节点间相似矩阵,而后基于吸引子传播聚类算法获取簇集信息,最后对聚类结果中簇集的规模进行判定,从而发现关联关系离群的节点。本文分别在模拟数据集和实际数据集上进行了相关实验验证,表明了 CBOut算法的有效性。针对网络中节点相似度量,本文提出了两类条件下的度量方法,分别是单一度量条件下的节点相似性计算方法与复杂度量条件下的节点相似性计算方法。在单一度量条件下,本文提出了针对多个查询的节点相似性计算优化方法。该方法对网络中的关联节点特征向量采用基于长度的最不常用置换策略进行选择性存储,确保在给定关联节点特征向量存储条数的前提下,减少多个查询中相似性计算的时间消耗。本文在实际数据集上进行了优化算法性能实验的验证,结果符合预期。在复杂度量条件下,本文定义的相似度量方法需要对不同度量条件赋予不同的偏好权重。用户可以根据自己的领域知识,在离群点查询语言中直接指定不同度量条件的偏好权重。当用户不能明确给定不同度量条件的偏好权重时,本文提出了一种偏好权重自适应调整机制,用于获取符合网络特征且具有较高聚类质量的偏好权重值,使用这样的偏好权重值发现的离群点将更能代表数据集本身的特征。本文分别在模拟数据集和实际数据集上对偏好权重自适应调整机制进行了相关测试,结果表明本文提出的偏好权重自适应调整方法确实可以提高数据集的聚类质量,从而提高离群点检测的精度。