标题： 基于图的变点检测 显示英文标题

标题： Graph-Based Change-Point Detection

摘要： 我们研究了数据序列中分布发生突然变化的位置（即变点）的检测与估计问题。 提出了一种基于扫描统计量的新方法，该方法利用表示观测值之间相似性的图结构。 基于图的方法是非参数的，只要样本空间上可以定义一个信息量丰富的相似性度量，就可以应用于任何数据集。 提供了图基扫描统计量在单个变点和变化区间备择假设下的显著性水平的精确解析近似。 模拟结果显示，当数据维数适中至较高时，新方法比现有方法具有更好的功效。 新方法在两个应用中得到了展示：经典小说作者身份的确定，以及网络随时间变化的检测。 显示英文摘要

摘要： We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.