实体的关高效发现

《实体的关高效发现》由会员分享，可在线阅读，更多相关《实体的关高效发现（14页珍藏版）》请在金锄头文库上搜索。

1、实体关系高效发现 2007.3提纲五个问题任务是什么?-实体关系发现现有的方法是什么？-相关研究如何定义实体间具有关系？-指标确定如何有效地发现实体？-算法和实现方法有效吗？-验证和实验结论是什么？1.任务是什么背景：Web v.s real life目标：发现Web上的实体和他们的关系本文重点：提高发现实体之间关系的效率不关心实体间关系的具体类型2.已有的实体关系发现方法所有方法的思想实体共现实体关系几个数量文档集大小= N; 感兴趣实体集合大小=n方法一：O(N)扫描文档集，获得所有实体的关系方法二：O(n2)对兴趣实体集合，每对分别检索方法三：O(n)对兴趣实体集合，单个检索，发现包含共

2、现实体的文档Drawback: 难以通过search engine获得包含实体的所有网页检索出来的网页依旧有很多是无用的不包含感兴趣实体如果只选取top网页，表现出来的关系比应有关系稀疏3.如何定义实体间具有关系？基本思路：采用共现衡量共现的一些指标Mutual InformationDice CoefficientOverlap CoefficientJaccard CoefficientCosine Coefficient3.如何定义实体间具有关系？测试共现有效性的实验Step1:根据指标获得两两实体的指标量Step2:对每个实体，根据指标量对相关实体进行排序Step3: 5个指标选取to

3、pN结果进入poolingStep4: 人工判断具有关系/不具有关系Step5: 用两个实验量：MAP, PR11测试共现有效性3.如何定义实体间具有关系？实验结果采用Cosine作为指标4.有效地发现实体基本思想基本思想利用聚类系数比较大这一特征聚类系数定义 4.有效地发现实体基本思想验证以上直觉印象4.有效地发现实体算法一图聚类算法：输入：兴趣实体集合初始化：检索实体i, 获得top m网页提取出现在这些网页中的实体设置关系矩阵Mij = 实体j在实体i的top m中出现的次数/实体i的top m中出现的实体次数迭代聚类：反复以下以致变化程度小于阈值归一：一行所有元素和为1游走：Me 增距：Mij = Mij 每个实体的top k作为候选实体，采用cosine验证4.有效地发现实体算法二算法一不能完全解决关系稀疏问题算法二：概率算法顺序加入实体e，初始化它和其他实体关系概率为平均关系密度迭代过程：以致和其他所有实体关系概率低于阈值测试e与已有集合中具有最高关系概率的实体的关系采用聚类系数、反聚类系数扩散，更新与周围实体的关系概率5.方法有效吗？5.方法有效吗？6.结论Cosine是衡量实体关系的有效指标实体关系发现的算法选择需要高效率的时候采用图聚类方法需要高召回率的时候采用概率算法