实体关系高效发现-pku.ppt

实体关系高效发现 何靖 刘源 涂启琛 姚从磊 邸楠 2007.3 提纲—五个问题 任务是什么?--实体关系发现 现有的方法是什么？--相关研究 如何定义实体间具有关系？--指标确定 如何有效地发现实体？--算法和实现 方法有效吗？--验证和实验 结论是什么？ 1.任务是什么 背景：Web v.s real life 目标：发现Web上的实体和他们的关系 本文重点： 提高发现实体之间关系的效率 不关心实体间关系的具体类型 2.已有的实体关系发现方法 所有方法的思想 实体共现?实体关系 几个数量 文档集大小= N; 感兴趣实体集合大小=n 方法一：O(N) 扫描文档集，获得所有实体的关系 方法二：O(n^2) 对兴趣实体集合，每对分别检索 方法三：O(n) 对兴趣实体集合，单个检索，发现包含共现实体的文档 Drawback: 难以通过search engine获得包含实体的所有网页 检索出来的网页依旧有很多是无用的—不包含感兴趣实体 如果只选取top网页，表现出来的关系比应有关系稀疏 3.如何定义实体间具有关系？ 基本思路：采用共现 衡量共现的一些指标 Mutual Information Dice Coefficient Overlap Coefficient Jaccard Coefficient Cosine Coefficient 3.如何定义实体间具有关系？ 测试共现有效性的实验 Step1:根据指标获得两两实体的指标量 Step2:对每个实体，根据指标量对相关实体进行排序 Step3: 5个指标选取topN结果进入pooling Step4: 人工判断具有关系/不具有关系 Step5: 用两个实验量：MAP, PR11测试共现有效性 3.如何定义实体间具有关系？ 实验结果 采用Cosine作为指标 4.有效地发现实体—基本思想 基本思想 利用聚类系数比较大这一特征 聚类系数定义 4.有效地发现实体—基本思想 验证以上直觉印象 4.有效地发现实体—算法一 图聚类算法： 输入：兴趣实体集合 初始化： 检索实体i, 获得top m网页 提取出现在这些网页中的实体 设置关系矩阵M[i][j] = 实体j在实体i的top m中出现的次数/实体i的top m中出现的实体次数 迭代聚类：反复以下以致变化程度小于阈值 归一：一行所有元素和为1 游走：Me 增距：M[i][j] = M[i][j]λ 每个实体的top k作为候选实体，采用cosine验证 4.有效地发现实体—算法二 算法一不能完全解决关系稀疏问题 算法二：概率算法 顺序加入实体e，初始化它和其他实体关系概率为平均关系密度 迭代过程：以致和其他所有实体关系概率低于阈值 测试e与已有集合中具有最高关系概率的实体的关系 采用聚类系数、反聚类系数扩散，更新与周围实体的关系概率 5.方法有效吗？ 5.方法有效吗？ 6.结论 Cosine是衡量实体关系的有效指标 实体关系发现的算法选择 需要高效率的时候—采用图聚类方法 需要高召回率的时候—采用概率算法 信息科学技术学院 · 网络研究所 信息科学技术学院 · 网络研究所