数据集的抽取式摘要 程龚, 徐丹云.

Presentation on theme: "数据集的抽取式摘要 程龚, 徐丹云."— Presentation transcript:

1 数据集的抽取式摘要 程龚, 徐丹云

2 这个数据集里到底有什么？

3 现有工作：模式提取 A Visual Summary for Linked Open Data Sources (ISWC’14)

4 现有工作：实体划分 按类型 按属性 按…… Efficiency and Precision Trade-Offs in Graph Summary Algorithms (IDEAS’13)

5 摘要的种类 非抽取式摘要： summary = a higher-level abstraction (a coarse-level graph structure)

6 摘要的种类 非抽取式摘要： summary = a higher-level abstraction (a coarse-level graph structure) 抽取式摘要： summary = a salient subset

7 什么是一个“好的”抽取式摘要？ 从用户的角度 信息需求 (Information Needs, IN)
认知需求 (Cognition Needs, CN) CN-1：具有可控的规模 CN-2：提供熟悉易懂的信息 CN-3：提供聚焦连贯的信息

8 什么是一个“好的”抽取式摘要？ 从数据/算法的角度 覆盖度 (Coverage) IN1, IN2 抽取尽可能多种类型的实体、属性 (覆盖)
优先抽取占比高的实体类型、属性 IN1, IN2 (覆盖) 紧致性 (Compactness) 抽取的规模不超过指定大小 CN1 (规模可控) 曝光度 (Visibility) 优先抽取位于数据中心的实体 CN2 (信息熟悉) 连贯性 (Cohesion) 抽取一个或一组相连的实体 CN3 (信息聚焦)

9 什么是一个“好的”抽取式摘要？ 从数据/算法的角度 覆盖度 (Coverage) IN1, IN2 抽取尽可能多种类型的实体、属性 (覆盖)
优先抽取占比高的实体类型、属性 IN1, IN2 (覆盖) 紧致性 (Compactness) 抽取的规模不超过指定大小 CN1 (规模可控) 优化目标 曝光度 (Visibility) 优先抽取位于数据中心的实体 CN2 (信息熟悉) 约束条件 连贯性 (Cohesion) 抽取一个或一组相连的实体 CN3 (信息聚焦)

10 组合优化问题 Maximum-Weight-and-Coverage Connected Graph (MWCCG) 三元组图 (GT)
曝光度 类的占比 属性的占比 覆盖的类 覆盖的属性 三元组图的导出子图 摘要的规模 三元组图 (GT)

11 问题的复杂度 α=0: weighted maximum coverage, NP-hard
β=0: maximum-weight connected graph, NP-hard (connected k-subgraph)

12 算法1 三元组图 (GT)

13 算法1 SOPT ≥ OPT/k Si ≥ OPT/k 三元组图 (GT)

14 算法2 三元组图 (GT)

15 算法2 SOPT ≥ OPT/k S1 ≥ OPT/k (max) 三元组图 (GT)

16 谢谢，欢迎意见建议