實體關(guān)系高效發(fā)現(xiàn)課件

實體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠2007.3實體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠提綱—五個問題任務(wù)是什么?--實體關(guān)系發(fā)現(xiàn)現(xiàn)有的方法是什么？--相關(guān)研究如何定義實體間具有關(guān)系？--指標確定如何有效地發(fā)現(xiàn)實體？--算法和實現(xiàn)方法有效嗎？--驗證和實驗結(jié)論是什么？提綱—五個問題任務(wù)是什么?--實體關(guān)系發(fā)現(xiàn)1.任務(wù)是什么背景：Webv.sreallife目標：發(fā)現(xiàn)Web上的實體和他們的關(guān)系本文重點：提高發(fā)現(xiàn)實體之間關(guān)系的效率不關(guān)心實體間關(guān)系的具體類型1.任務(wù)是什么背景：Webv.sreallife2.已有的實體關(guān)系發(fā)現(xiàn)方法所有方法的思想實體共現(xiàn)實體關(guān)系幾個數(shù)量文檔集大小=N;感興趣實體集合大小=n方法一：O(N)掃描文檔集，獲得所有實體的關(guān)系方法二：O(n^2)對興趣實體集合，每對分別檢索方法三：O(n)對興趣實體集合，單個檢索，發(fā)現(xiàn)包含共現(xiàn)實體的文檔Drawback:難以通過searchengine獲得包含實體的所有網(wǎng)頁檢索出來的網(wǎng)頁依舊有很多是無用的—不包含感興趣實體如果只選取top網(wǎng)頁，表現(xiàn)出來的關(guān)系比應(yīng)有關(guān)系稀疏2.已有的實體關(guān)系發(fā)現(xiàn)方法所有方法的思想3.如何定義實體間具有關(guān)系？基本思路：采用共現(xiàn)衡量共現(xiàn)的一些指標MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定義實體間具有關(guān)系？基本思路：采用共現(xiàn)3.如何定義實體間具有關(guān)系？測試共現(xiàn)有效性的實驗Step1:根據(jù)指標獲得兩兩實體的指標量Step2:對每個實體，根據(jù)指標量對相關(guān)實體進行排序Step3:5個指標選取topN結(jié)果進入poolingStep4:人工判斷具有關(guān)系/不具有關(guān)系Step5:用兩個實驗量：MAP,PR11測試共現(xiàn)有效性3.如何定義實體間具有關(guān)系？測試共現(xiàn)有效性的實驗3.如何定義實體間具有關(guān)系？實驗結(jié)果采用Cosine作為指標3.如何定義實體間具有關(guān)系？實驗結(jié)果4.有效地發(fā)現(xiàn)實體—基本思想基本思想利用聚類系數(shù)比較大這一特征聚類系數(shù)定義

4.有效地發(fā)現(xiàn)實體—基本思想基本思想4.有效地發(fā)現(xiàn)實體—基本思想驗證以上直覺印象4.有效地發(fā)現(xiàn)實體—基本思想驗證以上直覺印象4.有效地發(fā)現(xiàn)實體—算法一圖聚類算法：輸入：興趣實體集合初始化：檢索實體i,獲得topm網(wǎng)頁提取出現(xiàn)在這些網(wǎng)頁中的實體設(shè)置關(guān)系矩陣M[i][j]=實體j在實體i的topm中出現(xiàn)的次數(shù)/實體i的topm中出現(xiàn)的實體次數(shù)迭代聚類：反復(fù)以下以致變化程度小于閾值歸一：一行所有元素和為1游走：Me

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

每個實體的topk作為候選實體，采用cosine驗證4.有效地發(fā)現(xiàn)實體—算法一圖聚類算法：4.有效地發(fā)現(xiàn)實體—算法二算法一不能完全解決關(guān)系稀疏問題算法二：概率算法順序加入實體e，初始化它和其他實體關(guān)系概率為平均關(guān)系密度迭代過程：以致和其他所有實體關(guān)系概率低于閾值測試e與已有集合中具有最高關(guān)系概率的實體的關(guān)系采用聚類系數(shù)、反聚類系數(shù)擴散，更新與周圍實體的關(guān)系概率4.有效地發(fā)現(xiàn)實體—算法二算法一不能完全解決關(guān)系稀疏問題5.方法有效嗎？5.方法有效嗎？5.方法有效嗎？5.方法有效嗎？6.結(jié)論Cosine是衡量實體關(guān)系的有效指標實體關(guān)系發(fā)現(xiàn)的算法選擇需要高效率的時候—采用圖聚類方法需要高召回率的時候—采用概率算法6.結(jié)論Cosine是衡量實體關(guān)系的有效指標實體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠2007.3實體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠提綱—五個問題任務(wù)是什么?--實體關(guān)系發(fā)現(xiàn)現(xiàn)有的方法是什么？--相關(guān)研究如何定義實體間具有關(guān)系？--指標確定如何有效地發(fā)現(xiàn)實體？--算法和實現(xiàn)方法有效嗎？--驗證和實驗結(jié)論是什么？提綱—五個問題任務(wù)是什么?--實體關(guān)系發(fā)現(xiàn)1.任務(wù)是什么背景：Webv.sreallife目標：發(fā)現(xiàn)Web上的實體和他們的關(guān)系本文重點：提高發(fā)現(xiàn)實體之間關(guān)系的效率不關(guān)心實體間關(guān)系的具體類型1.任務(wù)是什么背景：Webv.sreallife2.已有的實體關(guān)系發(fā)現(xiàn)方法所有方法的思想實體共現(xiàn)實體關(guān)系幾個數(shù)量文檔集大小=N;感興趣實體集合大小=n方法一：O(N)掃描文檔集，獲得所有實體的關(guān)系方法二：O(n^2)對興趣實體集合，每對分別檢索方法三：O(n)對興趣實體集合，單個檢索，發(fā)現(xiàn)包含共現(xiàn)實體的文檔Drawback:難以通過searchengine獲得包含實體的所有網(wǎng)頁檢索出來的網(wǎng)頁依舊有很多是無用的—不包含感興趣實體如果只選取top網(wǎng)頁，表現(xiàn)出來的關(guān)系比應(yīng)有關(guān)系稀疏2.已有的實體關(guān)系發(fā)現(xiàn)方法所有方法的思想3.如何定義實體間具有關(guān)系？基本思路：采用共現(xiàn)衡量共現(xiàn)的一些指標MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定義實體間具有關(guān)系？基本思路：采用共現(xiàn)3.如何定義實體間具有關(guān)系？測試共現(xiàn)有效性的實驗Step1:根據(jù)指標獲得兩兩實體的指標量Step2:對每個實體，根據(jù)指標量對相關(guān)實體進行排序Step3:5個指標選取topN結(jié)果進入poolingStep4:人工判斷具有關(guān)系/不具有關(guān)系Step5:用兩個實驗量：MAP,PR11測試共現(xiàn)有效性3.如何定義實體間具有關(guān)系？測試共現(xiàn)有效性的實驗3.如何定義實體間具有關(guān)系？實驗結(jié)果采用Cosine作為指標3.如何定義實體間具有關(guān)系？實驗結(jié)果4.有效地發(fā)現(xiàn)實體—基本思想基本思想利用聚類系數(shù)比較大這一特征聚類系數(shù)定義

4.有效地發(fā)現(xiàn)實體—基本思想基本思想4.有效地發(fā)現(xiàn)實體—基本思想驗證以上直覺印象4.有效地發(fā)現(xiàn)實體—基本思想驗證以上直覺印象4.有效地發(fā)現(xiàn)實體—算法一圖聚類算法：輸入：興趣實體集合初始化：檢索實體i,獲得topm網(wǎng)頁提取出現(xiàn)在這些網(wǎng)頁中的實體設(shè)置關(guān)系矩陣M[i][j]=實體j在實體i的topm中出現(xiàn)的次數(shù)/實體i的topm中出現(xiàn)的實體次數(shù)迭代聚類：反復(fù)以下以致變化程度小于閾值歸一：一行所有元素和為1游走：Me

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

每個實體的topk作為候選實體，采用cosine驗證4.有效地發(fā)現(xiàn)實體—算法一圖聚類算法：4.有效地發(fā)現(xiàn)實體—算法二算法一不能完全解決關(guān)系稀疏問題算法二：概率算法順序加入實體e，初始化它和其他實體關(guān)系概率為平均關(guān)系密度迭代過程：以致和其他所有實體關(guān)系概率低于閾值測試e與已有集合中具有最高關(guān)系概率的實體的關(guān)系采用聚類系數(shù)、反聚類系數(shù)擴散，更新與周圍實體的關(guān)系概率