实体关系高效发现.ppt

《实体关系高效发现.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、实体关系高效发现何靖刘源涂启琛姚从磊邸楠2007.3提纲—五个问题任务是什么?--实体关系发现现有的方法是什么？--相关研究如何定义实体间具有关系？--指标确定如何有效地发现实体？--算法和实现方法有效吗？--验证和实验结论是什么？1.任务是什么背景：Webv.sreallife目标：发现Web上的实体和他们的关系本文重点：提高发现实体之间关系的效率不关心实体间关系的具体类型2.已有的实体关系发现方法所有方法的思想实体共现实体关系几个数量文档集大小=N;感兴趣实体集合大小=n方法一：O(N)扫描文档集，获得所有实体的关系方法二：O(n^2)对兴趣实体集合，

2、每对分别检索方法三：O(n)对兴趣实体集合，单个检索，发现包含共现实体的文档Drawback:难以通过searchengine获得包含实体的所有网页检索出来的网页依旧有很多是无用的—不包含感兴趣实体如果只选取top网页，表现出来的关系比应有关系稀疏3.如何定义实体间具有关系？基本思路：采用共现衡量共现的一些指标MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定义实体间具有关系？测试共现有效性的实验Step1:根据指标获得两两实体的

3、指标量Step2:对每个实体，根据指标量对相关实体进行排序Step3:5个指标选取topN结果进入poolingStep4:人工判断具有关系/不具有关系Step5:用两个实验量：MAP,PR11测试共现有效性3.如何定义实体间具有关系？实验结果采用Cosine作为指标4.有效地发现实体—基本思想基本思想利用聚类系数比较大这一特征聚类系数定义4.有效地发现实体—基本思想验证以上直觉印象4.有效地发现实体—算法一图聚类算法：输入：兴趣实体集合初始化：检索实体i,获得topm网页提取出现在这些网页中的实体设置关系矩阵M[i][j]=实体j在实体i的topm中出现的

4、次数/实体i的topm中出现的实体次数迭代聚类：反复以下以致变化程度小于阈值归一：一行所有元素和为1游走：Me增距：M[i][j]=M[i][j]λ每个实体的topk作为候选实体，采用cosine验证4.有效地发现实体—算法二算法一不能完全解决关系稀疏问题算法二：概率算法顺序加入实体e，初始化它和其他实体关系概率为平均关系密度迭代过程：以致和其他所有实体关系概率低于阈值测试e与已有集合中具有最高关系概率的实体的关系采用聚类系数、反聚类系数扩散，更新与周围实体的关系概率5.方法有效吗？5.方法有效吗？6.结论Cosine是衡量实体关系的有效指标实体关系发现的算

5、法选择需要高效率的时候—采用图聚类方法需要高召回率的时候—采用概率算法