实体关系高效发现课件

实体关系高效发现何靖刘源涂启琛姚从磊邸楠2007.3实体关系高效发现何靖刘源涂启琛姚从磊邸楠提纲—五个问题任务是什么?--实体关系发现现有的方法是什么？--相关研究如何定义实体间具有关系？--指标确定如何有效地发现实体？--算法和实现方法有效吗？--验证和实验结论是什么？提纲—五个问题任务是什么?--实体关系发现1.任务是什么背景：Webv.sreallife目标：发现Web上的实体和他们的关系本文重点：提高发现实体之间关系的效率不关心实体间关系的具体类型1.任务是什么背景：Webv.sreallife2.已有的实体关系发现方法所有方法的思想实体共现实体关系几个数量文档集大小=N;感兴趣实体集合大小=n方法一：O(N)扫描文档集，获得所有实体的关系方法二：O(n^2)对兴趣实体集合，每对分别检索方法三：O(n)对兴趣实体集合，单个检索，发现包含共现实体的文档Drawback:难以通过searchengine获得包含实体的所有网页检索出来的网页依旧有很多是无用的—不包含感兴趣实体如果只选取top网页，表现出来的关系比应有关系稀疏2.已有的实体关系发现方法所有方法的思想3.如何定义实体间具有关系？基本思路：采用共现衡量共现的一些指标MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定义实体间具有关系？基本思路：采用共现3.如何定义实体间具有关系？测试共现有效性的实验Step1:根据指标获得两两实体的指标量Step2:对每个实体，根据指标量对相关实体进行排序Step3:5个指标选取topN结果进入poolingStep4:人工判断具有关系/不具有关系Step5:用两个实验量：MAP,PR11测试共现有效性3.如何定义实体间具有关系？测试共现有效性的实验3.如何定义实体间具有关系？实验结果采用Cosine作为指标3.如何定义实体间具有关系？实验结果4.有效地发现实体—基本思想基本思想利用聚类系数比较大这一特征聚类系数定义

4.有效地发现实体—基本思想基本思想4.有效地发现实体—基本思想验证以上直觉印象4.有效地发现实体—基本思想验证以上直觉印象4.有效地发现实体—算法一图聚类算法：输入：兴趣实体集合初始化：检索实体i,获得topm网页提取出现在这些网页中的实体设置关系矩阵M[i][j]=实体j在实体i的topm中出现的次数/实体i的topm中出现的实体次数迭代聚类：反复以下以致变化程度小于阈值归一：一行所有元素和为1游走：Me

增距：M[i][j]=M[i][j]λ

每个实体的topk作为候选实体，采用cosine验证4.有效地发现实体—算法一图聚类算法：4.有效地发现实体—算法二算法一不能完全解决关系稀疏问题算法二：概率算法顺序加入实体e，初始化它和其他实体关系概率为平均关系密度迭代过程：以致和其他所有实体关系概率低于阈值测试e与已有集合中具有最高关系概率的实体的关系采用聚类系数、反聚类系数扩散，更新与周围实体的关系概率4.有效地发现实体—算法二算法一不能完全解决关系稀疏问题5.方法有效吗？5.方法有效吗？5.方法有效吗？5.方法有效吗？6.结论Cosine是衡量实体关系的有效指标实体关系发现的算法选择需要高效率的时候—采用图聚类方法需要高召回率的时候—采用概率算法6.结论Cosine是衡量实体关系的有效指标实体关系高效发现何靖刘源涂启琛姚从磊邸楠2007.3实体关系高效发现何靖刘源涂启琛姚从磊邸楠提纲—五个问题任务是什么?--实体关系发现现有的方法是什么？--相关研究如何定义实体间具有关系？--指标确定如何有效地发现实体？--算法和实现方法有效吗？--验证和实验结论是什么？提纲—五个问题任务是什么?--实体关系发现1.任务是什么背景：Webv.sreallife目标：发现Web上的实体和他们的关系本文重点：提高发现实体之间关系的效率不关心实体间关系的具体类型1.任务是什么背景：Webv.sreallife2.已有的实体关系发现方法所有方法的思想实体共现实体关系几个数量文档集大小=N;感兴趣实体集合大小=n方法一：O(N)扫描文档集，获得所有实体的关系方法二：O(n^2)对兴趣实体集合，每对分别检索方法三：O(n)对兴趣实体集合，单个检索，发现包含共现实体的文档Drawback:难以通过searchengine获得包含实体的所有网页检索出来的网页依旧有很多是无用的—不包含感兴趣实体如果只选取top网页，表现出来的关系比应有关系稀疏2.已有的实体关系发现方法所有方法的思想3.如何定义实体间具有关系？基本思路：采用共现衡量共现的一些指标MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定义实体间具有关系？基本思路：采用共现3.如何定义实体间具有关系？测试共现有效性的实验Step1:根据指标获得两两实体的指标量Step2:对每个实体，根据指标量对相关实体进行排序Step3:5个指标选取topN结果进入poolingStep4:人工判断具有关系/不具有关系Step5:用两个实验量：MAP,PR11测试共现有效性3.如何定义实体间具有关系？测试共现有效性的实验3.如何定义实体间具有关系？实验结果采用Cosine作为指标3.如何定义实体间具有关系？实验结果4.有效地发现实体—基本思想基本思想利用聚类系数比较大这一特征聚类系数定义

4.有效地发现实体—基本思想基本思想4.有效地发现实体—基本思想验证以上直觉印象4.有效地发现实体—基本思想验证以上直觉印象4.有效地发现实体—算法一图聚类算法：输入：兴趣实体集合初始化：检索实体i,获得topm网页提取出现在这些网页中的实体设置关系矩阵M[i][j]=实体j在实体i的topm中出现的次数/实体i的topm中出现的实体次数迭代聚类：反复以下以致变化程度小于阈值归一：一行所有元素和为1游走：Me

增距：M[i][j]=M[i][j]λ

每个实体的topk作为候选实体，采用cosine验证4.有效地发现实体—算法一图聚类算法：4.有效地发现实体—算法二算法一不能完全解决关系稀疏问题算法二：概率算法顺序加入实体e，初始化它和其他实体关系概率为平均关系密度迭代过程：以致和其他所有实体关系概率低于阈值测试e与已有集合中具有最高关系概率的实体的关系采用聚类系数、反聚类系数扩散，更新与周围实体的关系概率