数据集的抽取式摘要 程龚, 徐丹云
这个数据集里到底有什么?
现有工作:模式提取 A Visual Summary for Linked Open Data Sources (ISWC’14)
现有工作:实体划分 按类型 按属性 按…… Efficiency and Precision Trade-Offs in Graph Summary Algorithms (IDEAS’13)
摘要的种类 非抽取式摘要: summary = a higher-level abstraction (a coarse-level graph structure)
摘要的种类 非抽取式摘要: summary = a higher-level abstraction (a coarse-level graph structure) 抽取式摘要: summary = a salient subset
什么是一个“好的”抽取式摘要? 从用户的角度 信息需求 (Information Needs, IN) 认知需求 (Cognition Needs, CN) CN-1:具有可控的规模 CN-2:提供熟悉易懂的信息 CN-3:提供聚焦连贯的信息
什么是一个“好的”抽取式摘要? 从数据/算法的角度 覆盖度 (Coverage) IN1, IN2 抽取尽可能多种类型的实体、属性 (覆盖) 优先抽取占比高的实体类型、属性 IN1, IN2 (覆盖) 紧致性 (Compactness) 抽取的规模不超过指定大小 CN1 (规模可控) 曝光度 (Visibility) 优先抽取位于数据中心的实体 CN2 (信息熟悉) 连贯性 (Cohesion) 抽取一个或一组相连的实体 CN3 (信息聚焦)
什么是一个“好的”抽取式摘要? 从数据/算法的角度 覆盖度 (Coverage) IN1, IN2 抽取尽可能多种类型的实体、属性 (覆盖) 优先抽取占比高的实体类型、属性 IN1, IN2 (覆盖) 紧致性 (Compactness) 抽取的规模不超过指定大小 CN1 (规模可控) 优化目标 曝光度 (Visibility) 优先抽取位于数据中心的实体 CN2 (信息熟悉) 约束条件 连贯性 (Cohesion) 抽取一个或一组相连的实体 CN3 (信息聚焦)
组合优化问题 Maximum-Weight-and-Coverage Connected Graph (MWCCG) 三元组图 (GT) 曝光度 类的占比 属性的占比 覆盖的类 覆盖的属性 三元组图的导出子图 摘要的规模 三元组图 (GT)
问题的复杂度 α=0: weighted maximum coverage, NP-hard β=0: maximum-weight connected graph, NP-hard (connected k-subgraph)
算法1 三元组图 (GT)
算法1 SOPT ≥ OPT/k Si ≥ OPT/k 三元组图 (GT)
算法2 三元组图 (GT)
算法2 SOPT ≥ OPT/k S1 ≥ OPT/k (max) 三元组图 (GT)
谢谢,欢迎意见建议