摘要翻译:
通勤时间距离(CTD)是一个基于图的随机游动度量。CTD在个性化搜索、协同过滤和增强搜索引擎的抗操纵能力等领域有着广泛的应用。我们的兴趣来自CTD作为异常检测度量的使用。结果表明,CTD可以同时识别全局异常和局部异常。为了便于实时应用,我们提出了一种精确而高效的增量式CTD近似算法。设计了一种在线异常检测算法,该算法可以在恒定时间内估计每个新到达数据点到当前图中任意点的CTD,保证响应的实时性。此外,所提出的方法也可以应用于许多其他利用通勤时间距离的应用。
---
英文标题:
《Online Anomaly Detection Systems Using Incremental Commute Time》
---
作者:
Nguyen Lu Dang Khoa and Sanjay Chawla
---
最新提交年份:
2011
---
分类信息:
一级分类:Computer Science 计算机科学
二级分类:Artificial Intelligence 人工智能
分类描述:Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域,除了视觉、机器人、机器学习、多智能体系统以及计算和语言(自然语言处理),这些领域有独立的学科领域。特别地,包括专家系统,定理证明(尽管这可能与计算机科学中的逻辑重叠),知识表示,规划,和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要:
Commute Time Distance (CTD) is a random walk based metric on graphs. CTD has found widespread applications in many domains including personalized search, collaborative filtering and making search engines robust against manipulation. Our interest is inspired by the use of CTD as a metric for anomaly detection. It has been shown that CTD can be used to simultaneously identify both global and local anomalies. Here we propose an accurate and efficient approximation for computing the CTD in an incremental fashion in order to facilitate real-time applications. An online anomaly detection algorithm is designed where the CTD of each new arriving data point to any point in the current graph can be estimated in constant time ensuring a real-time response. Moreover, the proposed approach can also be applied in many other applications that utilize commute time distance.
---
PDF链接:
https://arxiv.org/pdf/1107.3894